Publicação: Algoritmo Evolutivo aplicado ao Problema do Percurso do Cavalo
Carregando...
Tipo do documento
Data
Direito de acesso
Programa
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA
Título da Revista
ISSN da Revista
Título de Volume
Orientador
Coorientador
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.
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.
Palavras-chave
Algoritmos Evolutivos, Métodos de otimização, Problema do Percurso do Cavalo, Evolutionary algorithms, Optimization methods, Knight's tour
Citação
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.