2007 September 02 15:55:52 BRT


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:

begin{array}{lcll} f_1(x) & = & sumlimits_{i=1}^{3} x_i^2, & -5,12 le x_i le 5,12 \ f_2(x) & = & 100 ( x_1^2 - x_2)^2 + ( 1 - x_1)^2, & -2,048 le x_i le 2,048 \ f_3(x) & = & sumlimits_{i=1}^{5} lfloor x_i rfloor, & -5,12 le x_i le 5,12 \ f_4(x) & = & sumlimits_{i=1}^{30} i x_i^4 + mathrm{Gauss}(0,1), & -1,28 le x_i le 1,28 \ f_5(x) & = & dfrac{1}{0,002 + sumlimits_{j=1}^{25} dfrac{1}{j + sumlimits_{i=1}^{2} (x_i - a_{ij})^6}}, & -65,536 le x_i le 65,536 end{array}

onde:

a_{ij} =  begin{cases} -32 & i = 1, j equiv 1 pmod{5} mbox{ ou } i = 2, left lceil frac{j}{5} right rceil = 1 \ -16 & i = 1, j equiv 2 pmod{5} mbox{ ou } i = 2, left lceil frac{j}{5} right rceil = 2 \ 0   & i = 1, j equiv 3 pmod{5} mbox{ ou } i = 2, left lceil frac{j}{5} right rceil = 3 \ 16  & i = 1, j equiv 4 pmod{5} mbox{ ou } i = 2, left lceil frac{j}{5} right rceil = 4 \ 32  & i = 1, j equiv 5 pmod{5} mbox{ ou } i = 2, left lceil frac{j}{5} right rceil = 5 end{cases}

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:

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. ? 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