Problema das N-Rainhas

...

Como a primeira abordagem não ofereceu valores concisos, foi necessária pensar em outra abordagem mais simples para servir com solidez o propósito da função fitness. À partir disso, pensou-se em utilizar o cálculo da inclinação das retas entre duas rainhas dispostas em um tabuleiro para averiguar se elas se atacam ou não. Essa abordagem mostrou-se muito mais simplificada e sólida do que a primeira e independentemente dos valores das coordenadas das rainhas em um tabuleiro, o valor da inclinação das retas é sempre a tangente do Ângulo de inclinação delas. Os angulos que configuram ocasiões de ataque entre as rainhas são somente 3: 0°, 45° e 90° e os valores da tangente de cada um desses ângulos são respectivamente 0, 1 e infinito e esses valores foram considerados para a função de fitness avaliar se uma situação de ataque exisitia ou não. Quando essas condicções de ataque eram verdadeiras, assim como na primeira abordagem, o valor da variável interna pares diminuia em 1.

- Algorítmo de subida de encosta

O algoritmo de subida de encosta foi implementado tal qual o exemplo que encontra-se na transparência utilizada em sala de aula. Sendo uma função que recebe como parâmetros: s – um indivíduo a ser avaliado inicialmente, N – conjunto de vizinhos de s que podem ser úteis para adentrarem a vizinhança e f – um objeto apontando para uma função de fitness a ser avaliada, apontando por padrão para a função fitness. Quando o algoritmo de subida de encosta é chamado, ele avalia o indivíduo inicial s e todos os possíveis vizinhos que podem ser úteis para encontar um pico da função, ou seja, todos aqueles cujo o valor de fitness seja maior ou igual ao valor do fitness de s. À partir daí, ele passa a explorar a vizinhança de s e atualiza a variável s para o indivíduo de maior valor na vizinhança. E esse processo é repetido até não existir mais vizinhos úteis (que tenham valor maior ou igual a s). No final, o indivíduo s de maior fitness é retornado e a execução finaliza.

- Algoritmo Genético

O algoritmo genético também foi implementado como os exemplos estudados em sala de aula, porém, com algumas alterações, como a adição do parâmetro x para indicar a quantidade de valores mais aptos a serem retornados para a junção hibrida do AG e do subida de encosta e tal como o algoritmo de subida de encosta, também existe um objeto f para apontar para uma função de fitness a ser avaliada – por padrão a fitness já implementada. O processo de funcionamento do algoritmo genético é exatamente o mesmo que o visto em sala, onde, um indivíduo inicial é gerado como uma disposição de rainhas nas colunas sem repetir o número das linhas (ex.: [0,1,2,3,4,5,6,7]) e uma população inicial do tamanho de população definido pelo usuário é gerado à partir de seleções aleatórias de permutações desse indivíduo. À partir daí, ocorre o processo de seleção e pareamento dos indivíduos a serem reproduzidos (de maneira aleatória) para a partir de então ocorrer o processo de cross-over com ponto de corte de 1 coluna – modificado para corte ox após consulta ao professor, para garantir a permutação. Depois, se a probabilidade mutação for atingida, ocorre uma mutação. Após essa mutação uma nova população é gerada e então, os indivíduos para fazer parte da nova população são selecionados pelo método da roleta. O algoritmo repete esses passos até o numero máximo de gerações definido pelo usuário ou até encontrar o valor máximo de função objetivo, que é (n-1)*n rainhas que não se atacam no tabuleiro.

- Junção Hibrida.

A junção hibrida nada mais é que rodar o AG, selecionar os x indivíduos mais aptos gerados pelo AG, construir vizinhanças para esses indivíduos através de permutações e colocar esses indivíduos como entradas do algorítmo de subida de encosta para ele, a partir de uma vizinhança mais seleta, contribuir na busca pelo indivíduo ótimo para a resolução do problema.

5. Execuções e resultados obtidos

Para se efetuar os testes necessários, foi criado um bash script chamado bateria_testes.sh que recebe como parâmetro o tipo de solução a ser feita pelo programa n_rainhas.py (1 – Subida de Encosta, 2 – AG, 3 – Hibrido) bem como o numero de indivíduos mais aptos a serem considerados no AG para a aplicação do Hibrido.

Esse script consistiu em rodar o programa em python para os seguintes valores de n: (6, 8, 16, 32, 64, 128, 256 e 512) por uma quantidade de execuções de y vezes (no caso 10 pelo enunciado do exercício) para validar as soluções implementadas. Alguns parâmetros eram fixos como por exemplo: tamanho da população (100), gerações (30) e probabilidade de mutação (0.25). A saída padrão do script foi direcionada para arquivos de texto que armazenaram os resultados, os resultados foram processados, analisados e encontrados seus máximos, mínimos, médias e desvios padrões para cada valor de n.

Abaixo a tabela comparativa mostrando os resultados obtidos:

Conclusões:

O algoritmo de subida de encosta por si só, para valores muito grande de n fica bem abaixo da solução do problema n*(n-1), algo que o genético já se aproxima com mais facilidade. Porém, quando as duas soluções são combinadas, o de subida de encosta contribui para a partir dos melhores indivíduos obtidos no algoritmo genético, pesquisar vizinhanças deles não exploradas no AG que podem retornar indivíduos mais aptos.

Referências