Publicação: Algoritmo genetico aplicado ao problema do 8-puzzle
Carregando...
Tipo do documento
Data
Direito de acesso
Programa
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Título da Revista
ISSN da Revista
Título de Volume
Orientador
Coorientador
Resumo
Este trabalho apresenta a implementação e análise de um Algoritmo Genético (AG) para
a solução do problema do quebra-cabeça de 8 peças, visando investigar a eficiência desse
método em problemas de busca combinatória. O objetivo principal foi desenvolver uma
abordagem que combinasse operadores de seleção, crossover e mutação para encontrar
a solução ótima ou próximas da ótima em diferentes configurações do quebra-cabeça.
O método consistiu na representação do estado do quebra-cabeça como cromossomos,
a aplicação de operadores genéticos e a avaliação da população com base em uma função
de aptidão. Os experimentos demonstraram que o AG é capaz de encontrar soluções
viáveis com número limitado de movimentos e apresentou desempenho consistente em diferentes
taxas de mutação, crossover e elitismo, evidenciando a importância do equilíbrio
entre exploração e diversidade da população. Os resultados obtidos mostraram-se bastante
satisfatórios quando comparados à literatura, confirmando a relevância do ajuste
adequado dos parâmetros. Conclui-se que a aplicação de AGs em problemas de busca,
como o 8-puzzle, proporciona resultados promissores, sendo possível ajustar parâmetros
para otimizar eficiência e qualidade das soluções.
Abstract
This study presents the implementation and analysis of a Genetic Algorithm (GA) applied
to the solution of the 8-puzzle problem, with the purpose of investigating the efficiency
of this method in combinatorial search problems. The main objective was to develop an
approach that combined selection, crossover, and mutation operators to identify optimal
or near-optimal solutions under different puzzle configurations. The method consisted of
representing puzzle states as chromosomes, applying genetic operators, and evaluating the
population based on a fitness function. The experiments demonstrated that the GA could
find viable solutions within a limited number of moves and showed consistent performance
across different mutation, crossover, and elitism rates, highlighting the importance of balancing
exploration and population diversity. The results obtained were highly satisfactory
when compared to the literature, confirming the relevance of proper parameter tuning. It
is concluded that the application of GAs to search problems, such as the 8-puzzle, yields
promising results, making it possible to adjust parameters to optimize both efficiency and
solution quality.
Palavras-chave
Algoritmo genético, 8-puzzle, Otimização, Problemas de busca, Inteligência artificial, Genetic algorithm, Optimization, Search problems, Artificial intelligence
Citação
MUNIZ, Laura Rosado Rodrigues. Algoritmo genético aplicado ao problema do 8-puzzle. 2025. 54 f. Trabalho de Conclusão de Curso (Graduação em Sistemas de Informação) – Universidade Federal de Uberlândia, Uberlândia, 2025.