| 4 damas escalada | 4 damas genético |

Até este momento, a procura desenvolve-se apenas num estado de cada vez. Os algoritmos genéticos utilizam uma população de estados, em vez de um só estado, cruzando informação dos diferentes estados para obter novos estados. Baseia-se do paradigma da seleção natural, em que cada solução do problema é um indivíduo, que tem um determinado valor. Os melhores indivíduos têm mais probabilidade de se reproduzirem, e passarem à geração seguinte, existindo também mutações, a que correspondem a alterações aleatórias nas soluções, de forma a permitir que a população adquira características que não possui, sendo essas características mantidas se forem boas.

A base para este algoritmo funcionar assenta em mais funções, parâmetros e opções que os algoritmos anteriores, mas nem todas elas inteiramente novas:

• Gerador de soluções aleatório (necessário também para a escalada do monte);
• Operador de cruzamento (dadas duas soluções constrói uma nova baseada nas duas);
• Operador de mutação (dada uma solução, altera a solução aleatoriamente, o que pode ser considerado como sendo um vizinho aleatório);
• População (quantos indivíduos fazem parte de uma geração);
• Estratégia de seleção.

Mantendo o problema nas 4 damas, o gerador aleatório já foi utilizado no algoritmo da escalada do monte. No operador de cruzamento pode-se utilizar qualquer ideia que permita fazer uma nova solução com base em duas. Um operador conhecido, é o "one-point-crossover", que corresponde em considerar um ponto na solução aleatório, e a zona da esquerda ser obtida através de uma das soluções, e a zona da direita através da outra solução. Este operador é simples e pode ser implementado numa grande variedade de estados. A mutação pode ser a escolha de uma coluna e de uma linha aleatoriamente. Como população vamos considerar com a técnica PnP uma população de 4 indivíduos.

A estratégia de seleção define como se passa de uma geração para a outra. O algoritmo genético começa por gerar uma primeira geração aleatória, e de seguida aplica a estratégia de seleção para passar de uma geração para outra até que o critério de paragem seja atingido.

Uma estratégia de seleção simples, para PnP, pode ser o seguinte (para população = 4):

• Ordenar os indivíduos por valor;
• Cruzar os indivíduos: (1º,2º); (1º,3º); (1º,4º); (2º,3º).
• Mutar todos os indivíduos gerados;
• Da geração seguinte, pertencem os melhores indivíduos cruzados (mutados ou não), sendo o desempate favorável aos indivíduos mutados.

É normal que a mutação seja feita apenas a alguns indivíduos, e que os indivíduos para cruzar sejam escolhidos aleatoriamente, dando mais probabilidade de escolha aos melhores indivíduos. É comum incluírem-se a elite da geração anterior na geração seguinte (para não perder os melhores), e entre gerações gerar-se mais indivíduos que os permitidos numa geração, escolhendo os melhores para ficar na geração. Há ainda outras variantes, como assegurar uma distância mínima entre indivíduos, de forma a permitir que a procura percorra espaços distintos, fazer alguma optimização local aos indivíduos de uma geração (chamar o algoritmo de escalada do monte), e por vezes utilizar mais que uma população, de forma a simular evoluções em zonas distintas, que mais tarde se vêm a cruzar, de forma a aumentar a diversidade, e simular a organização da sociedade em cidades. Podem também ser introduzidos numa geração, indivíduos estrangeiros, gerados aleatoriamente.

As variantes não são muito relevantes para a aprendizagem, a estratégia acima descrita, já dá mais hipótese à melhor solução para se manter na geração, e de seguida à 2ª e 3ª solução. Vamos correr o algoritmo com a seguinte sequência aleatória (conjuntos de 4 números): 4322, 3132, 3222, 1412, 1333, 4214, 3344, 3421, 2331, 2342, 3242, 4443, 1343, 1212.

Ficheiro de Excel, passo a passo:

Para explicar o funcionamento, vamos identificar os estados com o número da linha e coluna. A geração 0 foi completamente gerada utilizando os números aleatórios. De seguida, a geração 1 resultou primeiramente de 4 operações de cruzamento. O estado 2,1 (primeiro estado da geração 1), resultou da primeira coluna do 1º indivíduo da geração 0 (estado 1,2), e das 3 colunas restantes do 2º indivíduo da geração 0 (estado 1,4). Isto porque o número aleatório para o operador foi 1. Já o segundo (estado 2,2) foi resultado das 3 primeiras colunas do 1º indivíduo da geração 0, e a última coluna do 3º indivíduo da geração 0.

A terceira linha foi feita com base nos indivíduos resultantes dos cruzamentos, tendo o primeiro sofrido uma mutação 4,2, portanto a quarta coluna ficou na linha 2. No entanto, como essa dama já estava nessa posição, o estado ficou igual. Já o estado 3,2, tem uma mutação 1,4, o que significa que a dama na 1ª coluna deve passar para a linha 4, estando anteriormente na linha 2. Neste caso, esta mutação melhorou a anterior solução, ficando com apenas duas damas a atacarem-se mutuamente.

Para a geração 2, passam os 4 melhores indivíduos da geração 1, incluindo antes e depois da mutação, e que são diferentes. Neste caso a geração 1 ficou: (3,2);(3,3);(3,4);(2,4).

A segunda geração teve um procedimento idêntico, sempre utilizando os valores aleatórios para o operador cruzamento.

Embora o algoritmo genético não tenha chegado em 4 gerações à solução, estes resultados não significam que não seja um algoritmo potente, mas apenas que em problemas pequenos poderá não ser indicado, e que necessita de afinação para poder funcionar corretamente.

| 4 damas escalada | 4 damas genético |