Algoritmo genetico

Disponível somente no TrabalhosFeitos
  • Páginas : 8 (1982 palavras )
  • Download(s) : 0
  • Publicado : 29 de outubro de 2012
Ler documento completo
Amostra do texto
Exemplo de aplicação de algoritmo genético

Considere o problema de otimização não linear-convexa

Minimizar
x1-32+ x2- 22 - (função objetivo – f(x1, x2) )
Sujeito as restrições
-2 ≤x1 ≤1
-2≤x2 ≤1
[a,b]=[-2,1]

A figura 1 nos destaca o comportamento da função objetivo dentre valores de x1 e x2 [-100,100], e a figura 2 nos demonstra o comportamento da f (curvas de nível) e sua devidarestrição imposta.

Figura [ 1 ]: Função objetivo

Figura [ 2 ]: Destaque das restrições do problema, dada f(x1,x2)

Conforme a estrutura dos Algoritmos Genéticos (AG) (Figura 3), será resolvido o exercício, tal que o primeiro passo é a determinação da População inicial.

Figura [ 3 ]: Estrutura de um AG
1° passo – População inicial

Considere a seguinte população inicial, cadalinha representa um indivíduo com duas variáveis, os primeiros 4 bits para x1 e os 4 últimos para x2 , ou seja, cada linha representa um cromossomo de 8 bits ou o genótipo de cada indivíduo (Tabela 1).

Tabela [ 1 ]: População inicial onde cada indivíduo é representado por um cromossomo de 8 genes (bits)
Indivíduo | | | | genes | | | | |
| x1 (binário) | x2 (binário) |
1 | 0 | 1 | 0| 1 | 0 | 1 | 1 | 1 |
2 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
3 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
4 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 |
5 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
6 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |

Pede-se:
(a) Determine o valor das variáveis reais x1 e x2, considerando que apenas 4 bits são utilizados para representá-las.
(b) Determine o valor da função objetivo paracada indivíduo
(c) Atribua a aptidão a cada indivíduo
(d) Empregue a roleta, considerando como número aleatório 0,634
(e) Efetue o cruzamento dos dois indivíduos de maior aptidão, considerando um ponto de corte no 3º bit. Determine os valores da função objetivo dos filhos.
(f) Efetue a mutação dos dois indivíduos de menor aptidão, considerando a alteração no 2° bit. Determine osvalores da função objetivo dos filhos. Reordene a população.
(g) Qual a precisão de busca realizada.

RESPOSTAS

(a) x1 e x2? Representados por 4bits.

Visto que é necessário a transformação de base binária para base decimal e por fim a discretização em um intervalo real e contínuo [a,b] para o cálculo de x1 e x2, utilizando-se das equações (1) e (2) para calcular o fenótipo de cadaindivíduo, ou mensurar o valor da característica intrínseca no genótipo de cada indivíduo, onde temos n bits e N indivíduos.

x=i=1nbi.2i-1 (1)



x-ab-a=x-02n-1-0 (2)

No nosso problema o campo de possibilidades, delimitado pelos extremos[a,b], determina a região factível de possível soluções ótimas dadas as variáveis x1 e x2. Para este caso temos a=-2 e b=1, assumindo mesmos valores para x1 e x2. (Figura 4).

Figura [ 4 ]: Região Factível delimitada pelo conjunto de restrições das variáveis x1 e x2

Portanto, da tabela 2 conseguimos expressar os valores de x1 e x2 conforme equações (1) e (2).

x=i=14bi.2i-1=b1.20+b2.21+b3.22+b4.23

x= x 5-2

Tabela [ 2 ]: Determinação dos valores de x1 e x2.
Indivíduo | x1 | x2 | x1 | x2 |
1 | 5 | 7 | -1 | -3/5 |
2 | 15 | 12 | 1 | 2/5 |
3 | 10 | 12 | 0 | 2/5 |
4 | 4 | 3 | -6/5 | -7/5 |
5 | 1 | 9 | -9/5 | -1/5 |
6 | 2 | 10 | -8/5 | 0 |

(b) f(x1 , x2)?

Figura [ 5 ]: 2° passo - Avaliação

Para avaliação da função objetivo, utilizaremos os valoresdas variáveis reais x1 e x2 anteriormente encontrados e apresentados na tabela 3 a seguir.

Tabela [ 3 ]: Valores da f(x1, x2)
Indivíduo | x1 | x2 | f(x1, x2) |
1 | -1 | -3/5 | 22,76 |
2 | 1 | 2/5 | 6,56 |
3 | 0 | 2/5 | 11,56 |
4 | -6/5 | -7/5 | 29,20 |
5 | -9/5 | -1/5 | 27,88 |
6 | -8/5 | 0 | 25,16 |

(c) Aptidão?

Torna-se necessário neste passo, reordenarmos a população...
tracking img