sexta-feira, 17 de fevereiro de 2012

Tetris e algoritmos genéticos em Java - parte 3

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
Para testar o modelo, obtemos uma nova amostra de 1000 games aleatórios e comparamos com os resultados previstos por Prob(X). O polígono de frequências abaixo mostra os resultados:

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!

2 comentários:

  1. Este comentário foi removido pelo autor.

    ResponderExcluir
  2. Olá, fiquei um pouco confuso sobre onde fazer a atribuição "doSleep = true" para agilizar a execução.

    També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.

    ResponderExcluir