Algoritmo Evolutivo aplicado ao Problema do Percurso do Cavalo

Nascimento, Murielly Oliveira

Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/39913

ORCID:	http://orcid.org/0009-0007-4210-0666
Document type:	Trabalho de Conclusão de Curso
Access type:	Acesso Aberto
Title:	Algoritmo Evolutivo aplicado ao Problema do Percurso do Cavalo
Alternate title (s):	Evolutionary Algorithm applied to the Knight's Tour
Author:	Nascimento, Murielly Oliveira
First Advisor:	Brasil, Christiane Regina Soares
First member of the Committee:	Melo, Wendel Alexandre Xavier de
Second member of the Committee:	Gabriel, Paulo Henrique Ribeiro
Summary:	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.
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.
Keywords:	Algoritmos Evolutivos Métodos de otimização Problema do Percurso do Cavalo Evolutionary algorithms Optimization methods Knight's tour
Area (s) of CNPq:	CNPQ::CIENCIAS EXATAS E DA TERRA
Language:	por
Country:	Brasil
Publisher:	Universidade Federal de Uberlândia
Quote:	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.
URI:	https://repositorio.ufu.br/handle/123456789/39913
Date of defense:	4-Dec-2023
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

Show full item record