2007 September 04 | girino.org

2007 September 02 15:55:52 BRT September 4, 2007

Posted by Girino Vey in : Uncategorized , add a comment

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 f₁ a f₅) que são:

$\begin{array}{lcll} f_1(x) & = & \sum\limits_{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) & = & \sum\limits_{i=1}^{5} \lfloor x_i \rfloor, & -5,12 \le x_i \le 5,12 \\ f_4(x) & = & \sum\limits_{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 + \sum\limits_{j=1}^{25} \dfrac{1}{j + \sum\limits_{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 x_i) 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 f₁ de De Jong - Online performance	Função f₁ de De Jong - Média da geração	Função f₁ de De Jong - Offline performance	Função f₁ de De Jong - Melhor indivíduo
Função f₂ de De Jong - Online performance	Função f₂ de De Jong - Média da geração	Função f₂ de De Jong - Offline performance	Função f₂ de De Jong - Melhor indivíduo
Função f₃ de De Jong - Online performance	Função f₃ de De Jong - Média da geração	Função f₃ de De Jong - Offline performance	Função f₃ de De Jong - Melhor indivíduo
Função f₄ de De Jong - Online performance	Função f₄ de De Jong - Média da geração	Função f₄ de De Jong - Offline performance	Função f₄ de De Jong - Melhor indivíduo
^Novo Função f₅ de De Jong - Online performance	^Novo Função f₅ de De Jong - Média da geração	^Novo Função f₅ de De Jong - Offline performance	^Novo Função f₅ 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 f₁ e f₂, quanto mais “avançada” a política, melhor o desempenho. Esse comportamento se parece também com o observado quando usamos “elitismo”^[1]
Em f₃ 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 f₄ 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 f₅ 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 f₅ de De Jong, e ela corrobora a conclusão de que é apenas o ruído gaussiano que causa problemas em f₄. Em f₅ 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 (n 2)$ ), fica reduzido apenas a parte dos indivíduos.

–girino 22:31, 2 Setembro 2007 (BRT)

girino.org

2007 September 02 15:55:52 BRT September 4, 2007

A quantas anda…

Testes

Notas

Girino Vey!

Archives

Compre no Submarino

wordpress