Algoritmo Genético com Busca Local aplicado ao Problema das N-Rainhas utilizando Interface Web

O Problema das N-Rainhas consiste em posicionar N rainhas em um tabuleiro N × N sem conflitos em linhas, colunas ou diagonais, sendo um clássico problema de otimização combinatória devido ao crescimento exponencial do espaço de busca. Neste contexto, este trabalho propõe um aprimoramento de um Algoritmo Genético aplicado ao problema, com o objetivo de reduzir o custo computacional e melhorar a convergência das soluções. As melhorias incluem uma estratégia de inicialização baseada na geração de permutações válidas, otimizações na função de aptidão para contagem direta de conflitos e adaptações nos operadores genéticos para preservar soluções válidas, além da incorporação de uma etapa de busca local que explora trocas entre posições e mantém a melhor solução encontrada. Também foi desenvolvida uma interface web interativa, integrada a um servidor em Node.js, que permite a configuração dinâmica dos parâmetros do algoritmo e a visualização gráfica das soluções e da convergência. Os experimentos, realizados em instâncias de tamanho 10 a 25 com os mesmos parâmetros de um trabalho de referência, demonstraram que o algoritmo proposto obteve soluções válidas com menor número médio de gerações em todas as instâncias, evidenciando ganhos de desempenho e maior eficiência na busca por soluções.