Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/39913
Full metadata record
DC FieldValueLanguage
dc.creatorNascimento, Murielly Oliveira-
dc.date.accessioned2023-12-12T18:48:45Z-
dc.date.available2023-12-12T18:48:45Z-
dc.date.issued2023-12-04-
dc.identifier.citationNASCIMENTO, 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.urihttps://repositorio.ufu.br/handle/123456789/39913-
dc.description.abstractBioinspired 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.sponsorshipUFU - Universidade Federal de Uberlândiapt_BR
dc.languageporpt_BR
dc.publisherUniversidade Federal de Uberlândiapt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectAlgoritmos Evolutivospt_BR
dc.subjectMétodos de otimizaçãopt_BR
dc.subjectProblema do Percurso do Cavalopt_BR
dc.subjectEvolutionary algorithmspt_BR
dc.subjectOptimization methodspt_BR
dc.subjectKnight's tourpt_BR
dc.titleAlgoritmo Evolutivo aplicado ao Problema do Percurso do Cavalopt_BR
dc.title.alternativeEvolutionary Algorithm applied to the Knight's Tourpt_BR
dc.typeTrabalho de Conclusão de Cursopt_BR
dc.contributor.advisor1Brasil, Christiane Regina Soares-
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/5064007473299439pt_BR
dc.contributor.referee1Melo, Wendel Alexandre Xavier de-
dc.contributor.referee1Latteshttp://lattes.cnpq.br/4129091940824803pt_BR
dc.contributor.referee2Gabriel, Paulo Henrique Ribeiro-
dc.contributor.referee2Latteshttp://lattes.cnpq.br/3181954061121790pt_BR
dc.creator.Latteshttps://lattes.cnpq.br/3211860287395023pt_BR
dc.description.degreenameTrabalho de Conclusão de Curso (Graduação)pt_BR
dc.description.resumoA 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.countryBrasilpt_BR
dc.publisher.courseSistemas de Informaçãopt_BR
dc.sizeorduration73pt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRApt_BR
dc.orcid.putcode148622075-
Appears in Collections:TCC - Sistemas de Informação (Uberlândia)

Files in This Item:
File Description SizeFormat 
AlgoritmoEvolutivoAplicado.pdfTCC7.26 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.