TileTroop 2: Utilizando Algoritmos Genéticos e outros refinamentos.

Os algoritmos genéticos utilizam conceitos provenientes do princípio de seleção natural para abordar uma série ampla de problemas, em especial de otimização. Robustos, genéricos e facilmente adaptáveis, consistem de uma técnica amplamente estudada e utilizada em diversas áreas.

1) Funcionamento

Basicamente, o que um algoritmo genético faz é criar uma população de possíveis respostas para o problema a ser tratado (inicialização) para depois submetê-la ao processo de evolução, constituído pelas seguintes etapas:

avaliação: avalia-se a aptidão das soluções (indivíduos da população) — é feita uma análise para que se estabeleça quão bem elas respondem ao problema proposto.

seleção: indivíduos são selecionados para a reprodução. A probabilidade de uma dada solução i ser selecionada é proporcional à sua aptidão.

cruzamento: características das soluções escolhidas são recombinadas, gerando novos indivíduos;

mutação: características dos indivíduos resultantes do processo de reprodução são alteradas, acrescentando assim variedade à população.

atualização: os indivíduos criados nesta geração são inseridos na população.

finalização: verifica se as condições de encerramento da evolução foram atingidas, retornando para a etapa de avaliação em caso negativo e encerrando a execução em caso positivo.

2) Representação

Os indivíduos são a unidade fundamental de um algoritmo genético: eles codificam possíveis soluções para o problema a ser tratado, e é através de sua manipulação (pelo processo de evolução) que respostas são encontradas.

A escolha de representação para os indivíduos é a etapa mais importante do desenvolvimento de um AG, visto que ela será a principal responsável pelo desempenho do programa. É de uso comum na área de Algoritmos Genéticos utilizar os termos genoma e mesmo cromossoma como um sinônimo para indivíduo. Tal definição nos sugere que um indivíduo se resume ao conjunto de genes que possui (seu genótipo), e apresenta um problema: o de que apesar de toda representação por parte do algoritmo ser baseada única e exclusivamente em seu genótipo, toda avaliação é baseada em seu fenótipo (conjunto de características observáveis no objeto resultante do processo de decodificação dos genes).

Para o jogo TileTroop 2, realizamos uma numeração padrão para cada terreno e seus vizinhos.

Cada terreno é representado por uma variável e o valor das tropas que podem ser movidas é o resultado da equação. Por exemplo:

X1 + X2 + X3 + X4 + X5 + X6 + X7 = 5

Essa equação foi representada da seguinte maneira: 00000011111 (ou 0000005).

De todas as permutações geradas, excluímos aquelas que não são possíveis quando analisamos o total de tropas dos vizinhos (a soma das tropas não pode ser maior que oito).

3) Avaliação

Aplicamos a seguinte fórmula:

FAB = (n1 * type1 + n2 * type2 + n3 * type3 + … + nk * typek) / ( número de 0’s a partir do segundo caractere + 1 ).

Os pesos para cada tipo encontram-se abaixo:

W_TILE_OPPONENT_CASTLE = 600;

W_TILE_OPPONENT = 400;

W_TILE_GREEN = 200;

W_TILE_ME = 20;

W_TILE_MY_CASTLE = 20;

4) Seleção

Os métodos de seleção implementados neste trabalho foram:

ROULETTE_WHEEL : o método de seleção por giro de roleta funciona da seguinte forma calcula-se o somatório da adequação da população (total) sorteia-se um valor i tal que pertence ao intervalo [0; total] seleciona-se o indivíduo x tal que a ele corresponda à faixa do somatório onde i se localiza.

TOURNAMENT : Grupos de soluções são escolhidos sucessivamente e as mais adaptadas dentro de cada um destes são selecionadas.

RANDOM SALVATIONIST: seleciona-se o melhor indivíduo e os demais são escolhidos aleatoriamente.

5) Cruzamento

Os métodos de reprodução implementados neste trabalho foram:

RANDOM_CHOICE & CROSSING ONE POINT: os pares de indivíduos que devem se reproduzir são escolhidos ao acaso. Dados dois genomas x e y de comprimento lg, sorteia-se um número p qualquer tal que 0 < p < lg, o primeiro filho f0 receberá todos os genes x de 1 até p e todos os genes y de p + 1 até ly, e o segundo filho o inverso.

LINE_BREEDING: um indivíduo de alto desempenho é cruzado com uma subpopulação de indivíduos e os seus filhos são selecionados como pais.

RANDOM_CHOICE & UNIFORM_CROSSOVER: os pares de indivíduos que devem se reproduzir são escolhidos ao acaso. Para cada gene a ser preenchido nos cromossomos filhos, o operador de cruzamento uniforme sorteia de qual dos pais este deve ser gerado. A máscara de cruzamento de tal operador é uma sequência qualquer de zeros e uns.

6) Mutação

O método de mutação implementado neste trabalho foi:

SWAP_MUTATION: os elementos do gene trocam de valor entre si.