2007 August 27 00:10:38 BRT


Resumo da semana

Bom, eu fiquei sem assunto pra falar aqui, então acabei resolvendo retomar um projeto que eu deveria ter feito a anos atrás: Meu segundo projeto de final de curso (eu tive 3 projetos, o único que terminei foi o terceiro). Bom, eu nem sei se ainda tenho algum dos documentos que produzi na época. Provavelmente só escrevi o resumo inicial do projeto, porque logo logo eu abandonei (como sempre).

A idéia era basicamente uma variação de algoritmo genético que funcionasse de forma assíncrona. Mais ou menos assim:

Um GA tradicional tem uma geração de tamanho fixo. A partir dela você aplica operações de "mating" (como chama isso? cruzamento?) de mutação e de cópia, para formar uma nova geração, com novos indivíduos, e do mesmo tamanho da anterior. Aí você repete geração por geração até cansar ou achar o resultado desejado.

No GA assíncrono, os indivíduos da nova geração "convivem" com os indivíduos da geração anterior. A população não tem tamanho fixo. Aí você precisa de um novo operador, o operador de "morte", que é responsável por se livrar dos indivíduos "ruins" pra que a população não cresça demais.

Na minha implementação simplória do negócio, eu associei uma "idade" com cada indivíduo, e eu "mato" eles quando ficam velhos demais. Cada "rodada" do algoritmo passa por 3 etapas:

  • "mating"
  • mutação
  • morte

E em cada etapa eu atuo sobre a população como um todo. A solução é bem diferente do que eu tinha pensado em 99, quando era preu ter feito isso. Na época eu pensava em associar probabilidades pras operações e aplicar elas nos indivíduos isoladamente. Não cheguei a nenhuma solução prática pra isso, entretanto, porque abandonei antes...

A separação em rodadas também ajuda a fazer comparativos com o GA tradicional: uma rodada pode ser comparada com uma geração do GA tradicional.

A "expectativa de vida" dos individuos é um parâmetro do sistema. Eu usei nos testes o valor de 10 rodadas. Esse valor define também o número de indivíduos novos em cada geração na minha versão simplista: Eu produzo sempre tfrac{mbox{Numero inicial de individuos}}{mbox{Expectativa de vida}} indivíduos novos a cada rodada.

A mutação é aplicada com probabilidade igual na população inteira.

Na hora da morte eu implementei duas soluções:

  • morte por idade
  • morte por idade ponderada pela função objetivo

Na morte por idade, tudo vai muito bem. A população sempre tem tamanho constante, etc e tal.

Quando se pondera a idade com a função objetivo, os "mais aptos" vivem mais tempo enquanto os menos aptos vivem menos. Por enquanto esta estratégia tem dado bons resultados, mas não fiz nenhum teste "sério" com ela. Eu usei as funções f1 e f2 de De jong[1] só pra ver como a coisa ficaram e "me pareceu" que a convergência é mais rápida (na verdade a convergência leva o mesmo número de rodadas, mas as rodadas do assíncrono são mais curtas).

Agora é ver o que mais de idéias eu vou ter em cima disso e rodar uns testes de verdade (pelo menso com todas as 5 funções de De Jong).


Links


Notas

  1. ? De Jong, K. A.. An analysis of the behaviour of a class of genetic adaptative systems. Dissertação de doutorado, University of Michigan, 1975. in Goldberg, David E.. Genetic Algorithms in Search, Optimization, and Machine Learning. EUA: Addison-Wesley, 1989.

--girino 00:41, 27 Agosto 2007 (BRT)

Update

O código está sob licença MIT no Google Code, mas só porque não tinha a opção de usar a Girino's Anarchist License. Considerem o produto duplamente licenciado (MIT ou Girino's Anarchist License).

Leave a Reply