Melhorando o algoritmo Hill Climbing
Durante a última aula de IA na faculdade, nosso professor, nos apresentou o algoritmo Hill Climbing, aplicado ao problema das N-Rainhas. Fizemos alguns testes e fomos introduzidos ao tema de mínimo local.
Como desafio, o professor nos propôs achar uma maneira de escapar dos mínimos locais para este problema.
Logo após esta proposta, uma extrema excitação dentro de mim se instaurou, e acabei passando o final de semana inteiro trabalhando nesse problema.
O algoritmo proposto em aula, randomizava um movimento de uma rainha e em seguida verificava se esse movimento melhoraria a situação do tabuleiro, caso sim, o movimento era feito, caso contrário um novo movimento era testado.
Para atacar o problema, testei duas versões:
-
Remover o passo randômico por um passo baseado na melhor posição atual. Ou seja, a cada iteração, o algoritmo calcula a melhor posição no momento atual e muda para este novo estado encontrado.
Caso o algoritmo fique preso em uma configuração que não alcance um global optima, aplicamos um movimento randômico e continuamos com as iterações. -
Ao invés de iniciar com um tabuleiro padrão, iniciamos com um tabuleiro randômico. Dessa forma, poderíamos incentivar o algoritmo a explorar novas partes não exploradas.
Resultados:
A primeira versão conseguiu alcançar o marco de 92.6% de acertos !!! No entanto, a segunda versão não conseguiu tal feito, mas conseguiu melhorar o tempo para encontrar a solução, chegando ao resultado com menos iterações.