A quantas anda…
meu algoritmo genético assíncrono? Bom Já fiz bastante coisa de implementação. A ultima jogada foi rodar uma bateria de testes e gerar graficozinhos…
Testes
Vamos primeiro às explicações:
Os testes foram feitos usando as funções de De Jong[1] (de f1 a f5) que são:
onde:
Os indivíduos para cada uma dessas fórmulas foram modelados como possuindo um cromossomo para cada dimensão (cada variável xi) e cada cromossomo era um valor numérico nativo do python mesmo (preguiça de implementar coisas mais sofisticadas).
Foram definidas 5 políticas:
- Tradicional, ou seja, um GA clássico (roleta, população fixa, crossing over e mutação);
- Política 1 que mata indivíduos pela idade e cria um número fixo de indivíduos a cada geração;
- Política 2 que pondera a idade do indivíduo coma função de fitness antes de matá-lo;
- Política 3 que introduz comportamento estocástico no número de nascimentos a cada geração; e
- Política 4 que introduz comportamento estocástico nas mortes.
Rodei com os seguintes parâmetros:
- Tamanho inicial da população: 500 indivíduos
- Número de gerações: 2000
- Probabilidade de mutação: 0.01
- Idade máxima (para as políticas de 1 a 4): 10 gerações
E repeti cada teste 20 vezes, coletando estatísticas de:
- Offline e online performance[1]
- Melhor indivíduo da geração
- Média dos indivíduos da geração.
Os gráficos com esses resultados pra cada uma das funções de De Jong estão abaixo:
 Função f1 de De Jong – Online performance |
 Função f1 de De Jong – Média da geração |
 Função f1 de De Jong – Offline performance |
 Função f1 de De Jong – Melhor indivíduo |
 Função f2 de De Jong – Online performance |
 Função f2 de De Jong – Média da geração |
 Função f2 de De Jong – Offline performance |
 Função f2 de De Jong – Melhor indivíduo |
 Função f3 de De Jong – Online performance |
 Função f3 de De Jong – Média da geração |
 Função f3 de De Jong – Offline performance |
 Função f3 de De Jong – Melhor indivíduo |
 Função f4 de De Jong – Online performance |
 Função f4 de De Jong – Média da geração |
 Função f4 de De Jong – Offline performance |
 Função f4 de De Jong – Melhor indivíduo |
 Novo Função f5 de De Jong – Online performance |
 Novo Função f5 de De Jong – Média da geração |
 Novo Função f5 de De Jong – Offline performance |
 Novo Função f5 de De Jong – Melhor indivíduo |
Não fiz nenhuma análise mais aprofundada dos dados, mas tenho algumas observações preliminares que podem ser pertinentes:
- Nas funções f1 e f2, quanto mais “avançada” a política, melhor o desempenho. Esse comportamento se parece também com o observado quando usamos “elitismo”[1]
- Em f3 tem uma aparente piora, mas se olharmos o gráfico de “melhor indivíduo” ou na “média da geração” vemos que é só uma demora para convergir (devido a população não se renovar com tanta freqüência como no GA tradicional).
- Por último, a função f4 teve um comportamento completamente diferente das demais. Eu atribuo isso ao “ruído” gaussiano introduzido, mas precisaria de um base matemática melhor pra afirmar isso. Aparentemente o GA assíncrono não responde bem ao ruído na função objetivo.
A função f5 ainda não tinha terminado de executar quando gerei os gráficos, então ainda não sei os resultados dela. Mais tarde posto um update.
Notas
- ? 1,0 1,1 1,2 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 20:03, 2 Setembro 2007 (BRT)
- Update
Acrescentei agora as imagens correspondentes a função f5 de De Jong, e ela corrobora a conclusão de que é apenas o ruído gaussiano que causa problemas em f4. Em f5 o GA assíncrono já se mostra melhor que o tradicional novamente. Aparentemente o GA assíncrono proporciona ganhos na maioria dos casos estudados. Além disso, temos ganhos significativos de desempenho computacional (tempo de execução) já que o processo de seleção por roleta, que é bastante custoso (O(n2)), fica reduzido apenas a parte dos indivíduos.
—girino 22:31, 2 Setembro 2007 (BRT)
Leave a Reply