Uma investigação sobre os operadores genéticos no Algoritmo Evolutivo aplicado ao Problema do Percurso do Cavalo.

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 de otimização computacional, classificados como problemas NP. Neste trabalho, o
AE (Algoritmo Evolutivo) é implementado para a solução do Problema do Percurso do Cavalo (PPC). Este algoritmo é baseado na Teoria Evolucionista de Darwin, em especial, a Seleção Natural. O PPC, por sua vez, é um famoso problema combinatório, que pode ser utilizado para o aprimoramento ou desenvolvimento de algoritmos e para a solução de outros
problemas, como a criptografia de imagens. Leonhard Euler foi o primeiro a estudá-lo formalmente. O PPC consiste em encontrar uma sequência demovimentos—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, pormeio da implementação de novos operadores (seleção,mutação) e a inicialização central. O primeiro operador foi baseado na exploração de um campo de busca maior pormeio do cruzamento de pais dissimilares;
o segundo, na troca de genes (casas do percurso) por vizinhos válidos e o terceiro, foi utilizada a inicialização na casa central (ou aproximada) do tabuleiro. Os experimentosmostraram que o AE implementado foi capaz de resolver o PPC para tabuleiros nxn, com 5 ≤ n ≤ 20.