Ag Continuo

Algoritmos Genéticos

Algoritmos Genéticos com Parâmetros Contínuos

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

Algoritmos Genéticos

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)

Algoritmos Genéticos

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

Algoritmos Genéticos

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

Algoritmos Genéticos

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.

Algoritmos Genéticos

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)

Algoritmos Genéticos

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

Algoritmos Genéticos

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

Algoritmos Genéticos

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

Algoritmos Genéticos

Blend Crossover (BLX-) (2/4)

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

Algoritmos Genéticos

Blend Crossover (BLX-) (3/4)

Usando o mesmo para cada parâmetro

possível filho

pai

Parâ

met

ro 2

Parâmetro 1

I

I

I

Algoritmos Genéticos

Blend Crossover (BLX-) (4/4)

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

Algoritmos Genéticos

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

Algoritmos Genéticos

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

Algoritmos Genéticos

Crossover Simples

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

Algoritmos Genéticos

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

Algoritmos Genéticos

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.

Algoritmos Genéticos

Crossover Heurístico (2/2)

f ( )p1

c

f ( )p2

p1 p2

Funç

ão o

bjet

ivo

Algoritmos Genéticos

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

Algoritmos Genéticos

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

Algoritmos Genéticos

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)(

Algoritmos Genéticos

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

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

Algoritmos Genéticos

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

Algoritmos Genéticos

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.

Algoritmos Genéticos

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.

Algoritmos Genéticos

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

Algoritmos Genéticos

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

Algoritmos Genéticos

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