Ag Continuo

Algoritmos Genéticos

Algoritmos Genéticos com Parâmetros Contínuos

Estéfane G. M. de LacerdaDCA/UFRNMaio/2008


Exemplo

0,2

0,4

0,6

0,8

1,0

0,0-100 -75 -50 -25 0 25 50 10075

f x yx y

x y( , ) ,

sen ,

, ,

0 5

0 5

1 0 0 001

2 22

2 2 2FUNÇÃO OBJETIVO :

Exemplo extraído de Davis (1991)


Representação Real x Binária

Cromossomo Binário:

Cromossomo Real: (-17,85; 11,04)

Representação do ponto x = -17,85 e y = 11,04

01101001001001101000001000111000100001110010

0110100100100110100000 1000111000100001110010

1722784 2328690

-17,85 11,04

x y


Representação Binária

É historicamente importante, foi utilizado nos trabalhos pioneiros de Holland (1975).

A representação tradicional. Fácil de usar e manipular. Simples de analisar teoricamente. Não há uniformidade nos operadores.

Mutação nos primeiros bits do gene afeta mais a aptidão que mutação nos últimos bits do gene


Representação Real

Para um ser humano é mais natural do que uma cadeia de bits.

Cromossomos compactos e com precisão numérica padrão (IEEE 754).

Vários autores tem obtido desempenho melhor com representação real do que com representação binária.

Permite larga variedade de operadores.


Operadores paraRepresentação Real

Crossover´s convencionais n-Pontos, uniforme Não criam novas informações (i.e. novos

números reais). Crossover´s aritméticos

Operadores que realizam operações aritméticas entre os parâmetros.

Baseados da direção (usam derivadas)


Crossover Média (1/2)

(Davis, 1991)Dado dois cromossomos p1 = (p11, p12,..., p1l)p2 = (p21, p22,..., p2l)

é produzido um cromossomo

onde c = (c1, c2,..., cl).

2)( 21 ppc


Crossover Média (2/2)

Tende a levar os genes para o centro do espaço de busca causando perda de diversidade.

Não extrapola para além da região da população inicial.

Este problema é melhorado com o blend crossover (BLX-).


Blend Crossover (BLX-) (1/4)

(Eshelman e Shaffer, 1993)Dado dois cromossomos p1 e p2 , é produzido um cromossomo c da seguinte forma:

onde ~U(-,1+).Onde U representa uma distribuição uniforme.Tipicamente = 0,5 ou 0,25

)( 121 pppc



Exemplop1 = (30,173; 85,342)p2 = (75,989; 10,162)

= 0,5 e = 1,262

c1 = 30,173 +1,262(75,989-30,173) = 87,993c2 = 85,342 +1,262(10,162-85,342) = -9,535

assim, c = (87,993; -9,535).



Usando o mesmo para cada parâmetro

possível filho

pai

Parâ

met

ro 2

Parâmetro 1

I

I

I



Usando diferente para cada parâmetro

define a região de possíveis filhos

Parâmetro 1

Parâ

met

ro 2 possível filho

pai


Crossover Linear

(Wright, 1991)Gera três filhos:

Apenas o melhor dos três filhos é escolhido, os outros dois são descartados.

211 5,05,0 ppc

212 5,05,1 ppc

213 5,15,0 ppc


Operadores Genéticos de Michalewicz

(Michalewicz, 1994) Crossover Simples Crossover Aritimético Crossover Heurístico Mutação Uniforme Mutação de Limite Mutação Não-uniforme Mutação Não-uniforme Múltipla


Crossover Simples

É uma variação do crossover convencional de 1 ponto adaptado para representação real.


Crossover Aritmético

Este operador difere do crossover BLX-. por não extrapolar o intervalo entre p1 e p2

onde U(0,1).

211 )1( ppc

212 )1( ppc


Crossover Heurístico (1/2)

Extrapolação linear entre os pais usando a informação da aptidão.

Evita que o crossover aritmético leve os genes para o centro do intervalo.

)()( onde ),( 21211 pppppc ffr

onde r ~ U(0,1). Caso o crossover produza um filho infactível, gera-se outro número aleatório r.


Crossover Heurístico (2/2)

f ( )p1

c

f ( )p2

p1 p2

Funç

ão o

bjet

ivo


Mutação Uniforme

Substitui um gene por um número aleatório. Mutação no j-ésimo gene (aleatoriamente

escolhido) do cromossomo p:

onde ai e bi representam os limites dointervalo permitido para o gene ci

contrário caso

se ),,(

i

iii p

jibaUc


Mutação de Limite

Substitui o gene por um dos limites do intervalo factível [ai,bi].

onde r U(0,1). Evita que o crossover aritmético leve os genes

para o centro do intervalo factível [ai,bi].

contrário caso

e 5,0 se e 5,0 se

i

i

i

i

pjirbjira

c


Mutação Não-Uniforme

Substitui um gene por um número extraído de uma distribuição não-uniforme.

onde

r1 e r2 U(0,1), G é o número da geração.

contrário caso

e 5,0 se)()( e 5,0 se )()(

1

1

i

iii

iii

i

pjirGfappjirGfpbp

c

b

GGrGf

max2 1)(


Mutação Não-Uniforme Múltipla

Aplicação do operador mutação não-uniforme em todos os genes do cromossomo p.


Mutação Gaussiana

Substitui o gene por um número aleatório de uma distribuição gaussiana.

onde N(pi,) é uma distribuição normal com média pi e desvio padrão .

Pode-se diminuir o valor de , à medida que aumenta a número de gerações (imitando a redução de temperatura no Recozimento Simulado).

contrário caso

se ),,(

i

ii p

jipNc


Mutação Creep

Adiciona ao parâmetro pequeno valor aleatório (obtido de uma distribuição uniforme ou normal)

Provoca uma pequena pertubação nos genes a fim de levá-los mais rapidamente ao máximo local.


Exemplo

Problema da Unidade de Emergência Médica Qual a melhor localização da Unidade

Emergência médica em uma cidade? Cada bairro possui uma frequência de

chamadas de emergência diferente.


Exemplo

Cidade

8 4 5 5 3 4423 5 9 2 1 3641 8 7 8 7 8323 5 8 9 1 5434 3 5 7 9 6732 1 9 3 7 3964 7 9 3 7 812

1 km

1 km

8 Bairro

Frequência de chamadas de emergência do bairro.

Legenda


Exemplo

Cromossomo (representação real)

Função Objetivox , y =coordenadas da unidade de emergência

f x , y=∑i=1

56

wiai−x2bi− y2

a i ,bi= coodernadas (no centro) do bairro iwi= freqüência de chamadas do bairro i


Exemplo

Adicionando restrições ao problema

8 4 5 5 3 4423 5 9 2 1 3641 8 7 8 7 8323 5 8 9 1 5434 3 5 7 9 6732 1 9 3 7 3964 7 9 3 7 812

vvrio

pontes

Documents

Ag Continuo