Please use this identifier to cite or link to this item:
https://repositorio.ufu.br/handle/123456789/39913
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.creator | Nascimento, Murielly Oliveira | - |
dc.date.accessioned | 2023-12-12T18:48:45Z | - |
dc.date.available | 2023-12-12T18:48:45Z | - |
dc.date.issued | 2023-12-04 | - |
dc.identifier.citation | NASCIMENTO, Murielly Oliveira. Algoritmo Evolutivo aplicado ao Problema do Percurso do Cavalo. 2023. 73 f. Trabalho de Conclusão de Curso (Graduação em Sistemas de Informação) – Universidade Federal de Uberlândia, Uberlândia, 2023. | pt_BR |
dc.identifier.uri | https://repositorio.ufu.br/handle/123456789/39913 | - |
dc.description.abstract | Bioinspired Computing is an area of research focused on developing techniques inspired by natural phenomena to solve intractable problems in polynomial time (NP). In this work, Evolutionary Algorithm (EA) is implemented to solve the Knight's Tour. This algorithm is strongly based on Darwin's Evolutionary Theory, in particular, Natural Selection. The Knight's Tour, in turn, is a combinatorial problem widely used as a basis for improving or developing algorithms and for solving real problems, such as image encryption. Leonhard Euler was the first to formally study it. The Knight's Tour consists of finding a sequence of moves — made by the chess piece corresponding to the knight — that travels across the entire board without visiting a square more than once. Therefore, this work aimed to implement EA for the Knight's Tour solution, improving the results found in the literature, through the implementation of a new selection and mutation operator. The first is based on the exploration of a larger search field through the crossing of dissimilar parents, and the second is the exchange of genes (pathways) for valid neighbours. The experiments showed that the implemented EA was able to solve Knight's Tour for 𝑛𝑥𝑛 boards, with 5 ≤ 𝑛 ≤ 20. | pt_BR |
dc.description.sponsorship | UFU - Universidade Federal de Uberlândia | pt_BR |
dc.language | por | pt_BR |
dc.publisher | Universidade Federal de Uberlândia | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | Algoritmos Evolutivos | pt_BR |
dc.subject | Métodos de otimização | pt_BR |
dc.subject | Problema do Percurso do Cavalo | pt_BR |
dc.subject | Evolutionary algorithms | pt_BR |
dc.subject | Optimization methods | pt_BR |
dc.subject | Knight's tour | pt_BR |
dc.title | Algoritmo Evolutivo aplicado ao Problema do Percurso do Cavalo | pt_BR |
dc.title.alternative | Evolutionary Algorithm applied to the Knight's Tour | pt_BR |
dc.type | Trabalho de Conclusão de Curso | pt_BR |
dc.contributor.advisor1 | Brasil, Christiane Regina Soares | - |
dc.contributor.advisor1Lattes | http://lattes.cnpq.br/5064007473299439 | pt_BR |
dc.contributor.referee1 | Melo, Wendel Alexandre Xavier de | - |
dc.contributor.referee1Lattes | http://lattes.cnpq.br/4129091940824803 | pt_BR |
dc.contributor.referee2 | Gabriel, Paulo Henrique Ribeiro | - |
dc.contributor.referee2Lattes | http://lattes.cnpq.br/3181954061121790 | pt_BR |
dc.creator.Lattes | https://lattes.cnpq.br/3211860287395023 | pt_BR |
dc.description.degreename | Trabalho de Conclusão de Curso (Graduação) | pt_BR |
dc.description.resumo | A Computação Bioinspirada é uma área de pesquisa focada no desenvolvimento de técnicas inspiradas em fenômenos da natureza para a solução de problemas intratáveis em tempo polinomial (NP). Neste trabalho, o Algoritmo Evolutivo (AE) é implementado para a solução do Problema do Percurso do Cavalo (PPC). Este algoritmo é fortemente baseado na Teoria Evolucionista de Darwin, em especial, a Seleção Natural. O PPC, por sua vez, é um problema combinatório amplamente utilizado como base para o aprimoramento ou desenvolvimento de algoritmos e para a solução de problemas reais, como a criptograĄa de imagens. Leonhard Euler foi o primeiro a estudá-lo formalmente. O PPC consiste em encontrar uma sequência de movimentos — realizados pela peça de xadrez correspondente ao cavalo — que percorra todo o tabuleiro sem visitar uma casa mais de uma vez. Portanto, este trabalho teve como objetivo implementar o AE para a solução do PPC, melhorando os resultados encontrados na literatura, por meio da implementação de um novo operador de seleção e mutação. Sendo o primeiro, baseado na exploração de um campo de busca maior através do cruzamento de pais dissimilares; e o segundo na troca de genes (casas do percurso) por vizinhos válidos. Os experimentos mostraram que o AE implementado foi capaz de resolver o PPC para tabuleiros 𝑛𝑥𝑛, com 5 ≤ 𝑛 ≤ 20. | pt_BR |
dc.publisher.country | Brasil | pt_BR |
dc.publisher.course | Sistemas de Informação | pt_BR |
dc.sizeorduration | 73 | pt_BR |
dc.subject.cnpq | CNPQ::CIENCIAS EXATAS E DA TERRA | pt_BR |
dc.orcid.putcode | 148622075 | - |
Appears in Collections: | TCC - Sistemas de Informação (Uberlândia) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
AlgoritmoEvolutivoAplicado.pdf | TCC | 7.26 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.