Algoritmo Evolutivo aplicado ao Problema do Percurso do Cavalo

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 criptografia 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 NxN, com 5 < n < 20.

Confira minha monografia completa no repositório da Universidade Federal de Uberlândia.