Finalmente, chegamos a parte mais interessante da série: implementar a GA. Partindo de uma população randômica de k agentes, cada um será testado em uma série de n games aleatórios, conforme discutido no post anterior. A cada geração, os agentes de maior desempenho terão uma probabilidade maior de serem selecionados para reprodução, o que dará origem aos membros da próxima geração, e assim sucessivamente.
Usaremos uma GA contínua, com operações de mutação e crossover relativamente simples, mas que parecem funcionar bem em diversos casos. O encode/decode de um cromossomo binário requer um pouco mais de código e provavelmente o desempenho seria inferior, por isso o evitamos.
O algoritmo nos retornará uma lista com o histórico de todas as gerações, assim podemos visualizar claramente a evolução dos agentes ao longo do tempo. Há uma infinidade de dados e estatísticas interessantes que podem ser modelados, por exemplo: qual a distribuição de probabilidade do número de linhas removidas por um determinado agente? Dado um determinado agente, qual a distribuição de probabilidade da altura da grade? Estamos interessados na evolução dos agentes, por enquanto.
Lembrando que os agentes não sabem qual a próxima peça, o que levante outra questão interessante: qual efeito isso causa no desempenho do agente? As distribuições de probabilidade comentadas acima serão as mesmas? Hora de sujar as mãos...
Crossover
Para efetuar a troca de material genético, podemos aplicar as técnicas clássicas da GA binária: crossover de 1 ou 2 pontos, uniforme, etc. O problema com essa abordagem é que informação nova não é introduzida no sistema: os mesmos genes são propagados na próxima geração, apenas em locus diferentes (posições diferentes no cromossomo).
Uma maneira de evitar isso é adotar uma técnica mista, combinando os genes dos pais em uma nova variável. O método blendCrossover da classe GeneticAlgorithm, implementa esta técnica. Basicamente escolhemos um ponto de corte aleatório, e a partir deste ponto, combinamos os genes correspondentes dos pais em um novo valor, utilizando a variável aleatória beta como fonte de variação. Um dos filhos herdará este novo valor, sendo os genes do outro filhos calculados da mesma maneira, mas agora utilizando 1 - beta no lugar de beta.
Esta técnica parece funcionar bem no nosso caso, mas nada impede o uso de outro tipo de crossover, basta implementar o método e alterar a chamada no loop da GA, que veremos em breve.
Mutação
Ao repetidamente selecionar e reproduzir os indivíduos, podemos atingir uma situação onde certas combinações de genes são impossíveis de serem obtidas, e consequentemente o espaço de busca irá congelar. Eventualmente, a população pode convergir para cópias do mesmo indivíduo, o que impede a entrada de novo material genético no sistema. Esse é um dos motivos que tornam a mutação dos indivíduos indispensável na GA.
O caso contínuo novamente exige uma técnica especial. Para manter as coisas simples, o método mutateNoise apenas percorre os genes, e introduz ou não, uma pequena variação noise. A probabilidade de um gene sofrer mutação, probMutate, é um dos parâmetros mais importantes da GA, e deve ser ajustado para cada problema.
Seleção
Como comentado anteriormente, agentes com melhor desempenho terão mais chances de serem selecionados para reprodução e passar seus genes adiante. O método doSelection usa roulette wheel selection para selecionar e retornar um agente, lembrando que os valores de fitness devem ser não-negativos ao utilizar esta técnica.
Classe GeneticAlgorithm
Esta é a classe que implementa a GA e os métodos discutidos acima. O método runGA executa o algoritmo, e retorna a ArrayList hist, onde cada item representa uma geração de agentes. Os parâmetros popSize, maxGens e probMutate representam respectivamente o número de agentes em cada geração, o número máximo de gerações e a probabilidade de ocorrer mutação em um gene. Os parâmetros gamesPerAgent e eliteRate representam respectivamente o número de jogos por agente, e a taxa de elitismo utilizada.
Repare que no começo do método forçamos popSize e elite a assumirem valores par, isso evitará problemas caso haja elitismo, pois garantimos que o número de agentes necessários para completar a população, (popSize - elite)/2, também seja par.
O loop principal do método parece complicado, mas é bem simples. Começamos sorteando um inteiro que servirá como ponto de partida para semear o gerador aleatório. Em seguida, para cada agente, iniciamos um game passando como argumento o número de linhas e colunas, o tamanho do bloco, o valor para semear o gerador, e a variável doneSignal. Como não temos uma GUI associada, o tamanho do bloco não importa, desde que seja diferente de zero.
A variável doneSignal representa um objeto da classe CountDownLatch, inicializado com o número de Threads que desejamos esperar terminarem. Caso não lembre, veja o final do método run da classe AIGame: invocamos doneSignal.countDown(), sinalizando que esta Thread terminou a execução. Agora, ao invocar doneSignal.await(), podemos ter certeza que o programa só continuará a execução após todos os games/threads terem finalizado.
Em seguida, calculamos a média de linhas removidas por cada agente e atualizamos fitness e bestAgent. Seguindo com o código, alocamos a array que vai acomodar a nova população e invocamos sort na população atual. Agora os agentes estão ordenados de acordo com o desempenho quantificado em fitness (lembre-se que a classe TetrisAgent implementa a interface Comparable), e prosseguimos selecionando a elite, que automaticamente fará parte da nova população.
Por fim, o restante da nova população é preenchido: selecionamos indivíduos da população aos pares, efetuamos o crossover e mutação, e adicionamos os filhos a nova população. Ao final do loop adicionamos a população ao histórico, fazemos a troca population = newPopulation e incrementamos a geração atual. Por curiosidade, logamos o melhor agente obtido até então, já que não temos uma GUI. Repare que adotamos como critério de parado o número máximo de gerações.
Agora só nos falta setar os parâmetros de forma razoável e executar o algoritmo. Para avaliar os resultados, vamos gerar um arquivo .csv, partindo do output da GA (veja o método formatResults). Segue a classe GeneticAlgorithm:
import java.util.concurrent.*; import java.util.ArrayList; import java.util.Random; public class GeneticAlgorithm { public static TetrisAgent[] blendCrossover(TetrisAgent father, TetrisAgent mother) { TetrisAgent copy1 = father.cloneAgent(); TetrisAgent copy2 = mother.cloneAgent(); Random random = new Random(); int N_GENES = father.genes.length; int index = random.nextInt(N_GENES); for (int i = index; i < N_GENES; i++) { float beta = random.nextFloat(); float var1 = father.genes[i]; float var2 = mother.genes[i]; float newVar1 = beta * var1 + (1 - beta) * var2; float newVar2 = (1 - beta) * var1 + beta * var2; copy1.genes[i] = newVar1; copy2.genes[i] = newVar2; } return new TetrisAgent[]{copy1, copy2}; } public static void mutateNoise(TetrisAgent agent, float probMutate) { int N_GENES = agent.genes.length; Random random = new Random(); for (int i = 0; i < N_GENES ; i++) { float sort = random.nextFloat(); if (sort < probMutate) { float prob = random.nextFloat(); if (prob < 0.5f) { float genValue = agent.genes[i]; float complement = 1.0f - genValue; float noise = random.nextFloat() * complement; agent.genes[i] += noise; } else { float genValue = agent.genes[i]; float noise = random.nextFloat() * genValue; agent.genes[i] -= noise; } } } } public static TetrisAgent doSelection(TetrisAgent[] population) { TetrisAgent sorted = null; float totalFitness = 0.0f; for (TetrisAgent agent : population) totalFitness += agent.fitness; float frac = new Random().nextFloat(); float cut = frac * totalFitness; for (TetrisAgent agent:population) { cut -= agent.fitness; if (cut <= 0.0f) { sorted = agent; break; } } return sorted; } public static ArrayList<TetrisAgent[]> runGA(int popSize, int maxGens, float probMutate, int gamesPerAgent, float eliteRate) { ArrayList<TetrisAgent[]> hist = new ArrayList<TetrisAgent[]>(); //popSize par, importante caso haja elitismo if (popSize % 2 == 1) popSize += 1; int elite = (int)(popSize * eliteRate); //elite par, importante caso haja elitismo if (elite % 2 == 1) elite += 1; int currentGeneration = 0; Random random = new Random(); TetrisAgent[] population = new TetrisAgent[popSize]; TetrisAgent bestAgent = null; int rows = 20; int cols = 10; int blockSize = 1; //qualquer valor diferente de zero //cria populacao inicial e inicia fitness for (int i = 0; i < population.length; i++) population[i] = TetrisAgent.randomAgent(); int seed = random.nextInt(); do { CountDownLatch doneSignal = new CountDownLatch(popSize * gamesPerAgent); for (TetrisAgent agent : population) { for (int i = 0; i < gamesPerAgent; i++) { AIGame game = new AIGame(rows, cols, blockSize, i + seed, doneSignal); game.agent = agent; new Thread(game).start(); } } //espera games terminarem try { doneSignal.await(); } catch(InterruptedException ex){} //calcula fitness for (TetrisAgent agent : population) { float average = 0.0f; for (Integer cleared : agent.clearedRowsArray) average += cleared; agent.fitness = 1.0f * average/gamesPerAgent; agent.clearedRowsArray.clear(); } //atualiza bestAgent for (TetrisAgent agent : population) if (bestAgent == null || agent.fitness > bestAgent.fitness) bestAgent = agent; TetrisAgent[] newPopulation = new TetrisAgent[popSize]; java.util.Arrays.sort(population); //elite TetrisAgent[] eliteArray = new TetrisAgent[elite]; for (int i = 0; i < elite;i++) newPopulation[i] = population[popSize - i - 1]; int newIndex = elite; for (int i = 0; i < (popSize - elite)/2; i++) { TetrisAgent parentA = doSelection(population); TetrisAgent parentB = doSelection(population); TetrisAgent[] children = blendCrossover(parentA, parentB); TetrisAgent childA = children[0]; TetrisAgent childB = children[1]; mutateNoise(childA, probMutate); mutateNoise(childB, probMutate); newPopulation[newIndex] = childA; newIndex++; newPopulation[newIndex] = childB; newIndex++; } hist.add(population); population = newPopulation; currentGeneration++; System.out.println("Melhor da geracao " + currentGeneration + ": " + bestAgent.fitness); for (int i = 0; i < bestAgent.genes.length; i++) System.out.print(bestAgent.genes[i] + " "); System.out.println(); } while(currentGeneration < maxGens); return hist; } /* formata output em .csv */ public static void formatResults(ArrayList<TetrisAgent[]> generations, String file) { BufferedWriter writer = null; try { writer = new BufferedWriter(new FileWriter(file, false)); } catch(IOException ex){ex.printStackTrace();} int gens = generations.size(); //header for(int i = 0; i < gens; i++) { try { if (i == gens - 1) writer.write("g" + i + "\n"); else writer.write("g" + i + ","); } catch (IOException ex){ex.printStackTrace();} } int pop = generations.get(0).length; for(int indiv = 0; indiv < pop; indiv++) { //dados for(int i = 0; i < gens; i++) { TetrisAgent agent = generations.get(i)[indiv]; float fitness = agent.fitness; try { if (i == gens - 1) writer.write(fitness + "\n"); else writer.write(fitness + ","); } catch (IOException ex){ex.printStackTrace();} } } try { writer.close(); } catch(IOException ex){ex.printStackTrace();} } } //fim da classe GeneticAlgorithm
Executando a GA
Dependendo dos valores usados em popSize, maxGens e gamesPerAgent, o algoritmo levará mais ou menos tempo para finalizar. Ao passar um valor maior do que 1 para gamesPerAgent, aumentamos a chance de agentes com bom desempenho contribuir para a evolução dos indivíduos, já que maus agentes serão desmascarados ao tomarmos a média do número de linhas removidas. No meu teste, usei os seguintes valores:
- popSize = 20
- maxGens = 30
- probMutate = 0.2
- gamesPerAgent = 10
- eliteRate = 0.2
No meu macbook (2.4 GHz Intel Core 2 Duo, memória de 4 GB 1067 MHz DDR3), usando os valores acima, o algoritmo demorou um tempo absurdo para finalizar. A princípio não achei estranho, pois conforme os agentes evoluem, os jogos ficam cada vez mais longos. Na verdade, como apontado pelo leitor Kevin Nash, o problema está no método run da classe AIGame. Ao final deste método invocamos Thread.sleep(20L), causando uma queda generalizada na performance. Para resolver este problema, o construtor da classe AIGame agora aceita uma variável boolean doSleep, inicializada como false. Somente ao visualizar o agente jogando, setamos doSleep para true. Atualize sua classe AIGame antes de testar o algoritmo!
Existem algumas otimizações que podem ser feitas no código, uma delas é garantir que um agente que não teve seus genes modificados não seja testado novamente. Outra possibilidade seria detectar agentes que sejam muito ruins, e simplesmente abortar o jogo. A primeira sugestão parece mais fácil de implementar, mas realmente não me preocupei com desempenho neste caso. Adicione o método main na classe GeneticAlgorithm:
public static void main (String[] args) { int popSize = 20; int maxGens = 30; float probMutate = 0.2f; int gamesPerAgent = 10; float eliteRate = 0.2f; ArrayList<TetrisAgent[]> hist = runGA(popSize, maxGens, probMutate, gamesPerAgent, eliteRate); GeneticAlgorithm.formatResults(hist, "outputGA.csv"); }
Evolução
Para analisar o arquivo gerado vamos usar a Linguagem R. Para quem não conhece, R é uma linguagem voltada para computação estatística e gráficos, com versões para Windows, Mac OS X e várias plataformas UNIX. Com certeza postarei mais coisas sobre R neste blog, é uma linguagem fascinante e que vem ganhando muito espaço nos últimos anos, principalmente no meio acadêmico. Para reproduzir os gráficos desta seção, faça o download do R em http://www.r-project.org.
Após o download, precisamos instalar o pacote ggplot2 para plotar os gráficos. Poderíamos usar as funções gráficas dos pacotes que já vem instalados, mas ggplot2 facilita muito a criação de gráficos mais complexos e é muito superior visualmente. Execute o ambiente R e digite:
install.packages("ggplot2")Agora é só aguardar a instalação dos pacotes necessários.
Após a instalação dos pacotes, mova o nosso .csv para o working directory do R. Caso não saiba qual o diretório, execute getwd() e R te responderá.
Agora sim, hora de ver o resultado de tanto código! Você pode simplesmente copiar e colar, ou ser um pouco mais organizado: salve o código abaixo como criaGrafico.R, mova o arquivo salvo para o working directory e execute o comando source('criaGrafico.R').
#cria o data frame gaCols = read.csv("outputGA.csv", header = TRUE) #renomeia as colunas library(reshape) gaStack = melt(gaCols) names(gaStack) = c('generation', 'cleared') #extrai vetores com media e maximo de cada geracao generationFactors = factor(gaStack$generation) meanClr = tapply(gaStack$cleared, generationFactors, mean) maxClr = tapply(gaStack$cleared, generationFactors, max) #cria data frame com media e maximo de cada geracao gaMeanMax = data.frame(generation = 1: ncol(gaCols), meanCleared = meanClr, maxCleared = maxClr) #plot library(ggplot2) basicPlot = ggplot(data = gaStack, mapping = aes(x = generation, y = cleared)) + geom_boxplot() basic.mean = basicPlot + geom_line(aes(x = generation, y = meanCleared), data = gaMeanMax, colour = 'forestgreen') basic.mean.max = basic.mean + geom_line(aes(x = generation, y = maxCleared), data = gaMeanMax, colour = 'tomato2') basic.mean.max + geom_smooth(aes(group = 1))
Você não precisa entender o código acima, mas resumindo: a função read.csv() escaneia o conteúdo do arquivo passado e o transforma num objeto da classe data.frame. Geralmente, as colunas de um Data Frame representam variáveis, e cada linha representa uma observação diferente. Esse é um padrão comum em análise de dados. Após obter o Data Frame, quebramos ele em 2 colunas: a primeira coluna representa a geração, a segunda nos diz o desempenho do agente. A seguir, extraímos o desempenho médio e máximo para cada geração, e criamos um novo Data Frame com esses vetores. Os comandos restantes produzem o gráfico abaixo.
Observamos uma evolução rápida entre g0 e g11, onde o desempenho médio de cada geração (linha verde) é estritamente crescente. A partir daí, há uma oscilação em torno do valor 2500, com um pico de aproximadamente 3800 em g23. A linha vermelha representa o melhor agente de cada geração, e mostra claramente que conforme os agente evoluem, o intervalo de gerações necessário para o surgimento de um novo melhor agente fica cada vez maior, e a diferença de desempenho entre a elite se torna cada vez menor.
A curva de regressão (azul) resume bem as observações acima. Observando cada geração, os boxplots nos mostram que o desempenho não segue uma distribuição normal, sendo bastante assimétrico. Apesar do aspecto estacionário, os agentes de elite tendem a evoluir mais lentamente do que o resto da população (observe a tendência em g16, g18, g23 e g29) e esse desequilíbrio pode levar a combinações até então não exploradas, resultando em um novo salto em desempenho. Mas e quanto ao melhor agente, o que podemos dizer? Na próxima seção vamos olhar isso mais de perto.
Resultados
O melhor agente ocorre em g22, com um desempenho médio de 6248.7 linhas/game, e corresponde aos genes: 0.8775823, 0.109419234, 0.8726228, 0.5850601, 0.073843196, 0.21980879 e 0.19367324. Sabemos que esse resultado corresponde a média de 10 games, mas não sabemos nada sobre a distribuição de probabilidade desta variável. Para investigar melhor esse comportamento, vamos testar o agente novamente: 10 runs de 100 games aleatórios cada. O gráfico abaixo mostra os resultados:
O valor médio obtido foi de 3261.871 linhas/game com desvio padrão de 3196.501 linhas. Observando a quantidade de outliers, esses valores não são uma surpresa. Considere o histograma abaixo, com bin = 500:
Como o número de linhas removidas é uma variável discreta, os gráficos acima nos sugerem uma distribuição geométrica. Vamos modelar essa variável, assumindo que a cada peça nova, existe uma probabilidade constante p de que o jogo irá terminar. Parece uma hipótese fraca, mas lembre-se de que o game-over só ocorre devido a uma sequência ruim de peças, que certamente irá ocorrer com probabilidade q, determinada pelo gerador aleatório. Consequentemente, o histórico passado de peças não tem influência prática na duração do jogo: é impossível distinguir uma grade com um milhão de linhas removidas, de uma outra que tenha acabado de iniciar. Essa falta de memória é justamente uma das propriedades da distribuição geométrica.
Seja K a variável aleatória número de lances até o término do jogo, p a probabilidade de game-over e k um número de lances qualquer. Assumimos que Prob(K = k) = (1 - p)(k - 1) * p. Ou seja, a probabilidade do jogo terminar após k lances é determinada pelo produto entre as probabilidades de sobrevivermos (k - 1) lances e a probabilidade de ocorrer game-over no próximo lance. Se E(K) é a média de K, temos que p = 1/E(K).
Agora, seja X a variável número de linhas removidas até o término do jogo. Conforme o número de lances ultrapassa 45, sabemos que as linhas devem ser removidas a uma taxa de 2.5 peças/linha para evitar o término do jogo. Isso ocorre porquê o número máximo de blocos na grade é 20 x 9 = 180, ou seja, é possivel que 180/4 = 45 peças caiam sem nenhuma linha ser removida. Como K e X estão relacionados quando k >> 45, podemos concluir que possuem a mesma distribuição de probabilidade.
De acordo com a discussão acima, temos:
- E(X) = 3261.871
- p = 1/E(X) = 0.000306572516203
- σ2 = (1 - p)/p2
- σ = 3261.371
- Prob(X = x) = (1 - p)(x - 1) * p
Nada mal, o modelo parece funcionar bem! Uma outra opção seria modelar o desempenho médio do agente usando uma distribuição exponencial, o análogo contínuo da distribuição geométrica. Existem alterações interessantes que podem ser feitas na programa, por exemplo:
- alterar os métodos de mutação e crossover
- Usar uma função não-linear para avaliar as posições
- Usar uma GA de estado-estacionário
- Investigar o efeito do agente conhecer a próxima peça
- Investigar a distribuição de probabilidade de outras variáveis (altura da grade, por exemplo)
Acho que é isso pessoal! Essa foi uma aplicação simples de GA, mas os conceitos valem para qualquer situação. Como vimos o algoritmo pode levar um bom tempo para retornar uma solução, que nem sempre é a melhor. O importante é conhecer bem o problema e identificar quais os algoritmos que realmente valem a pena aplicar. Até a próxima!
Este comentário foi removido pelo autor.
ResponderExcluirOlá, fiquei um pouco confuso sobre onde fazer a atribuição "doSleep = true" para agilizar a execução.
ResponderExcluirTambém, em questão a análise dos dados, não entendi muito bem o processo de geração dos gráficos 2, 3 e 4.
Como não tenho muita familiaridade com o "R", vou perguntar:
- Para o gráfico 2, basta alterar minha classe TestAgent para rodar 100 jogos por dez vezes e salvar os resultados em um arquivo (como na classe GeneticAlgorithm) para então, pelo mesmo procedimento do gráfico 1, plotar os dados?
- No gráfico 3, quem é "count"?
- No gráfico 4, quem é "count"? Para gerar os 1000 jogos é assim como questionei para o gráfico 2? Como não entendi muito bem a modelagem proposta não entendi como gerar os resultados da curva teórica.
Estou tendo meus primeiros contatos com o campo de "Inteligência Computacional" esse ano e confesso bastante entusiasmo. Estratégias que escapam dos métodos determinísticos são extremamente surpreendentes em sua eficiência.
Sendo assim, tendo dito todo o acima, gostaria de pedir mais orientações em relação a análise dos dados. Já estou quebrando a cabeça para conseguir interpretar os resultados, porém, um pouco de orientação é sempre bem-vindo.
No mais, muitíssimo obrigado pelo post (e pelo blog), explicações e demonstrações sensacionais.