Computação Evolutiva
Osvaldo R. Saavedra
Grupo de Sistemas de Potência
DEE - UFMA
São Luís- MA
www.dee.ufma.br
Metáforas utilizadas em IA
• Cérebro e sistema nervoso
⇒ conexionismo
• Linguagem + processos cognitivos
⇒ IA simbólica
• Teoria da evolução
⇒ computação evolutiva
Introdução
Herança Genética --> Sobrevivência
do mais apto
♦ 1859: “Seleção natural”
princípio evolucionário
fundamental formulado por
Charles Darwin antes da
descoberta dos mecanismos
genéticos.
Sobre Darwin
• Charles Darwin era, antes da viagem do Beagle,
um ardoroso criacionista e membro da igreja
ortodoxa anglicana.
• Aparentemente continuou criacionista até pouco
após o retorno à Inglaterra, quando as primeiras
idéias "transformistas" lhe vieram em 1837
discutindo sobre diferentes espécies de pássaros de
galápagos com um ornitologista.
Sobre Darwin
• A seleção natural emergiu em 1838 lendo
Malthus sobre o Princípio das populações.
• Em 1844 escreveu um ensaio sobre seleção
natural mas não chegou a apresentá-lo à
comunidade científica com medo de
represálias.
Sobre Darwin
• Em 1856 começou a escrever sua grande
obra que se chamava "Natural Selection" a
qual não terminou porque recebera de
Alfred Russel Wallace, em 1858, a carta
com a descrição do manuscrito "Sobre a
tendência de variedades de se afastarem
indefinidamente a partir do ponto
original".
Seleção natural
• As espécies evoluem pelo
principio da seleção natural e
sobrevivência do mais apto.
♦Hipótese da mistura
das
heranças: qualidades dos pais
fluem,
misturadas,
no
organismo do descendente.
• A polêmica sobre a origem do
homem....
Pesadelo de Jenkins (1867)
♦ a Hipótese de Darwin é objetada:
♦ As distinções entre indivíduos rapidamente
desaparecem, não havendo seleção num
população homogênea.
Leis de Mendel (1865)
♦ Gregor Medel:
♦ Princípios
básico
de
transferência
de
fatores
genéticos pais-filhos
⇒
Natureza discreta
♦ Experimentos do cruzamento
genético de ervilhas
Leis de Mendel
•
A herança dos caracteres era particulada, cada
parental (pai) contribuía uma parte para a prole. Esta
parte (partícula, fator) é agora chamada de gene que
codifica o que chamamos de fenótipos (caracteres).
• Um gene pode existir em várias formas diferentes, e
cada uma destas formas é chamada de alelo.
• Em alguns casos, pode existir dominância de um alelo
(dominante) sobre o outro (recessivo).
Leis de Mendel
• Cada planta carregava duas cópias do mesmo
gene, portanto foram chamadas diplóides, e de
acordo com este conceito deduziu que os
homozigotos possuíam cópias idênticas do mesmo
alelo, enquanto que heterozigotos possuíam cópias
de alelos diferentes.
• Posteriormente, Mendel também deduziu que as
células sexuais deveriam ser haplóides pois
conteriam apenas uma das cópias.
Leis de Mendel
♦ As Leis de Mendel foram redescobertas
independentemente (1900) por Hugo de
Vries, K. Correns e K. Tschermark:
– Só a seleção natural não é responsável
pela produção de novas espécies:
– Tem que existir mecanismo de mudança
genética.
•
Teoria da Mutação
Leis de Mendel
♦ Morgan e equipe: provam experimentalmente
que cromossomos são o principal meio de
transferência
da
herança
e
genes
representam os fatores hereditários.
Leis de Mendel
♦ Durante muitos anos as Leis de Mendel e a
Teoria da Seleção Natural de Darwin ficaram
independentes e opostas entre elas.
♦ Década dos 20: Cetverikov mostra que
ambas teorias não são conflitantes.
• Sobre este feliz casamento descansa a
teoria evolucionária moderna.
O Paradigma Neo-Darwiniano
• O paradigma neo-Darwiniano estabelece
que a história da vida envolve apenas uns
poucos processos estatísticos que agem
nas -e entre- as populações e espécies.
• Estes processos são : reprodução, mutação
competição e seleção.
Computação Evolutiva
• A Evolução Simulada - ou Computação
Evolutiva - é baseada em processos de
aprendizagem coletiva dentro de uma
população de indivíduos, onde cada um
representa um ponto de busca no espaço de
possíveis soluções para um determinado
problema.
Correntes Algorítmicas
Algoritmos Evolutivos
Algoritmos Genéticos
Estratégias Evolutivas
Programação Evolucionária
Programação Genética
Simulated Annealing
Colónias de Formigas
...
...
Computação Evolutiva
• A maioria das implementações atuais de
algoritmos Evolutivos derivam-se de três
grandes correntes independentes, ainda
que fortemente relacionadas, que são:
♦ Algoritmos Genéticos;
♦ Estratégias Evolutivas;
♦ Programação Evolutiva.
Computação Evolutiva
• Em cada um destes métodos, uma
população de indivíduos é inicializada e
evolui para sucessivas regiões melhores no
espaço de busca, através de um processo
estocástico de seleção, mutação e, se
apropriado, recombinação (cruzamento).
Computação Evolutiva
• Em que diferem estes Métodos ?
Os métodos diferem com relação à:
– representação específica;
– operações de mutação e
– processo de seleção
Breve Histórico
• Os Algoritmos Genéticos (AG’s) foram
introduzidos por J. Holland na década dos
60, tendo posteriormente a atenção de
vários autores, entre eles De Jong,
Goldberg, Davis e Koza, entre outros.
AG´s
• Enfatizam os operadores cromossômicos,
sendo estes baseados na observação dos
mecanismos genéticos, isto é, cruzamento e
mutação.
• Os AG´s canônicos utilizam representação
binária
Estratégias Evolutivas (EE’s)
• Foram
inicialmente
desenvolvidas
na
Alemanha, por Schewefel e Rechenberg,
também na década de 1960, e posteriormente estendidas por Herdy, Rudolph e
Schwefel, entre outros.
• Esta técnica foi inicialmente orientada para a
resolução de problemas complexos de
otimização de parâmetros.
Programação Evolutiva (PE)
• Foi introduzida por L. Fogel em 1962 e
estendida por Burgin, Atmar e D. Fogel
recentemente, entre outros.
• A meta original da Programação Evolutiva
foi criar inteligência artificial, através do
desenvolvimento de máquinas de estado
finito para predizer eventos a partir de
observações prévias.
EE´s e PE
• O Paradigmas Estratégias Evolutivas e
Programação Evolutiva são muito similares.
• Ambos métodos operam com uma
população de soluções, sujeitando essas
soluções a alterações através de mutações
aleatórias e competição entre soluções
existentes com base em uma função
objetivo externa
Por que Computação Evolutiva ?
• Muitos problemas encontrados na
engenharia envolver otimizar um ou
vários critérios.
Por que Computação Evolutiva ?
• Em termos gerais, um problema de
otimização consiste em encontrar um vetor x
∈ M, onde M define a região de soluções
viáveis, tal que um certo critério de qualidade
f é maximizado (ou minimizado):
Maximizar f(x)
Por que Computação Evolutiva ?
• A função objetivo pode ser para sistemas
reais de complexidade arbitrária.
• A solução para a otimização global para este
problema, denominada x*, é caracterizada
como:
x* / ∀ x ∈ M, f(x) < f(x*)
Complexidade de f - Dificuldades
•
•
•
•
•
•
•
Multimodalidade;
Dimensionalidade;
Fortes não-linearidades;
Não-diferenciabilidades;
ruídos;
Funções objetivos variantes no tempo;
etc.
Métodos de busca: otimização
• Tipo gradiente: hill-climbing
– problema: mínimos locais
• Enumerativos -> cada ponto é avaliado
– Problema: custa caro
Métodos de busca: otimização
• Heurísticos: Resfriamento simulado (simulated
annealing)
• Heurísticos : computação evolutiva
– indivíduo = solução
Processo adaptativo e paralelo
Complexidade de f : Dificuldades
• Essas dificultades levam a problemas de
otimização de difícil solução, ou às vezes,
insolúveis.
• Neste último caso, a obtenção de soluções
próximas - e não apenas uma indicação de
divergência - são de grande ajuda em
problemas práticos.
Modelos aproximados
• Com o excesso de simplificações, as
soluções obtidas não resolvem o problema
original.
• Tais problemas, como no caso de modelos
para simulações, são na maioria das vezes
considerados sem solução.
Técnicas Evolutivas
• A maioria dos autores destaca três
aspectos chave, que são:
• O grau de adaptabilidade e flexibilidade;
• Robustez;
• Busca global.
Técnicas Evolutivas
• Não há restrição quanto à complexidade dos
problemas:
• Podem ser tanto discretos como contínuos;
• As funções objetivos e restrições podem ser:
– lineares,
– não lineares,
– contínuas ou discretas.
Técnicas Evolutivas
• A diferença fundamental da Computação
Evolutiva está em adaptar os métodos aos
problemas a serem tratados.
• Os Algoritmos Evolutivos não devem ser
considerados como um conjunto de algoritmos
prontos para serem utilizados.....
Técnicas Evolutivas
• É um conceito geral que pode ser adaptado
para as aplicações do mundo real, geralmente
encontrando melhores soluções quando
comparados aos
resultados obtidos
utilizando métodos tradicionais.
Conceitos biológicos
- Genes: blocos funcionais responsáveis de
determinar as características de un indivíduo
– Codifica um simples parâmetro do problema
– Cromosomos: “anteprojeto” do indivíduo(cadeia
de ADN); Estão compostos de Genes
– As possibilidades de escolher uma caracteristica
são os Alelos
– Ex.: Um gene representando a cor de um objeto
pode ter alelos como azul, preto, verde etc...
Conceptos biológicos
– Cada gene tem uma posição no
cromossomo ou Locus
– Genoma O conjunto do material genético
– Genótipo O conjunto de genes;
Na biologia, representa a composição
genética contida no Genoma. Nos AGs,
representa a informação contida no
cromossomo ou genoma.
Conceptos biológicos
– Fenótipo: é o conjunto de características
finais físicas e mentais do indivíduo
– É o cromossomo decodificado.
• Exemplo: Se o cromossomo codifica as
dimensões de um edifício, então o fenótipo é o
edifício construído.
Conceitos (II)
Natureza
Algoritmos Genéticos
Cromosomo (Indivíduo)
Alelo
Palavra binária, vector,...
(Solução)
Característica do problema
(parâmetro)
Alfabeto de representação
Locus
Posição dos bits no cromosomo
Genótipo
Configuração concreta de bits
Geração
Ciclo
Gene
Estratégias Evolutivas
(EE’s)
Estratégias Evolutivas (EE’s)
• Desenvolvidas inicialmente na Alemanha, na
década dos 60, focalizando a resolução de
problemas contínuos de otimização paramétrica;
• Estendidas recentemente para tratamento de
problemas discretos;
Exemplo de Motivação
• Consideremos apenas a geração de um
novo indivíduo através da regra:
x i+1 = xi + N(0, 1)
• Com estes elementos será possível criar
um procedimento de otimização ????
Estratégias Evolutivas (EE’s)
• Representação:
Par de vetores reais :
v = (x, σ)
• x representa o ponto de busca no espaço;
• σ
o vetor de desvio padrão associado.
EE’s Atuais
• Utilizam dois operadores: cruzamento e
mutação.
• Seleção Determinística.
• O parâmetro σ :
– determina a mutação de x;
– também está sujeito ao processo de evolução.
EE’s Atuais
“ Assumindo algumas hipóteses, é possível
provar que as EE’s convergem ao ótimo
global com probabilidade 1, considerando
um tempo de busca suficientemente longo”
EE’s - População Unitária
• Denominada (1+1)-ES:
Um único descendente é criado a partir de um
único genitor e ambos são confrontados numa
competição por sobrevivência, onde a seleção
elimina a solução mais pobre.
♦Elas processam apenas um indivíduo;
♦Único operador genético: mutação.
EE’s - População Unitária
• Geração de um novo indivíduo:
É realizada pela mutação de x, seguindo a
seguinte regra:
x i+1 = xi + N(0, σ 2)
• Onde N(0,σ2) é um vetor de números
Gaussianos independentes com média zero e
desvio padrão σ.
EE’s - População Unitária
Competição:
• O indivíduo x
e seu genitor xi competem
i+1
para ganhar a vaga na população;
• Neste estágio
tem-se temporariamente
a
população dobrada.
• Ganha quem tem
fitness melhor e satisfaz as
restrições do problema.
EE’s - População Unitária
Competição:
No caso de maximização:
Se f(xi+1) > f (xi) então (xi+1, σ) substitui (xi, σ);
caso contrário, permanece o indivíduo original.
EE’s - População Unitária
Exemplo:
Maximizar x2
sujeito a 0<x<100
1.- População Inicial:
• Unitária;
• Aleatória entre 0-100
EE’s - Exemplo
1.- População Inicial: {11} , σ = 1, Nger = 0
2.- Mutação:
x i+1 = xi + N(0, 1)
assumindo N(0, 1)= -0.5
x i+1 = 11 - 0.5 = 10.5
EE’s - Exemplo
3.- Competição
População intermediária: {11, 10.5}
Fitness: f(11)= 121
f(10.5)= 110.25
Melhor fitness = 121
==> Permanece o genitor
Nova população: {11}
Nger = Nger +1
EE’s - Exemplo
4.- Segunda geração: {11}
Mutação:
x i+1 = xi + N(0, 1)
assumindo N(0, 1)= +0.8
x i+1 = 11 + 0.8 = 11.8
EE’s - Exemplo
5.- Competição
População intermediária: {11, 11.8}
Fitness: f(11)= 121
f(10.5)= 139.24
Melhor fitness = 139.24
==> Vence o descendente
Nova população: {11.8}
Nger = Nger +1
EE’s - Evolução
•Fitness
•Nger
EE’s - Comentários
- As EE´s são robustas;
- (1+1)-EE é uma estratégia lenta (pouco prática)
Solução: estratégias multi-indivíduos
Estratégias Evolutivas
Multi-indivíduos
Estratégias Evolutivas Multi-indivíduos
Existem dois tipos:
• Estratégias (µ +λ)-EE
• Estratégias (µ , λ)-EE
Estratégias (µ +λ)-EE
• µ indivíduos produzem λ descendentes,
gerando-se uma população temporária de µ +λ
indivíduos;
• São escolhidos
geração.
µ indivíduos para a próxima
Estratégias (µ ,λ ) - EE
•
µ indivíduos produzem λ descendentes, com
λ >µ ;
• A nova população de µ indivíduos é formada
por indivíduos selecionados do conjunto de λ
descendentes.
• Assim, o período de vida de cada indivíduo é
limitado apenas a uma geração.
EE´s: algoritmo geral
begin
t←0
initializar P(t)
avaliar P(t)
while( critério de Parada não Satisfeito) do
begin
P’(t):= recombinar e mutar [P(t)]
avaliar [P’(t)]
P(t+1):=selecionar [P’(t) ∪ Q]
t ← t+1
end
end
Onde Q = P(t) ou Q=φ;
vi = (x, σ) , i=1, ...., µ
EE´s: algoritmo geral
População Inicial:
• Aleatória, tanto para x, como para σ;
• x deve respeitar as restrições do problema;
• Tamanho típico da população:
µ =10 ... 100
• Número de descendentes típico:
λ= 1...4 vezes o valor de µ
EE´s: algoritmo geral
Recombinação
i) Selecionar dois (ou mais) indivíduos:
v1 = (x1, σ1) = ((x11,...., xj1 ..., xn1 ), ( σi1, ..., σj1 .... ,σn1))
v2 = (x2, σ2) = ((x12,...., xj2 ..., xn2 ), ( σi2, ..., σj2 .... ,σn2))
Duas formas de recombinar (há várias):
• Discreto
• Intermediário
Recombinação Discreta
v1 = (x1, σ1) = ((x11,...., xj1 ..., xn1 ), ( σi1, ..., σj1 .... ,σn1))
v2 = (x2, σ2) = ((x12,...., xj2 ..., xn2 ), ( σi2, ..., σj2 .... ,σn2))
• O novo descendente é dado por:
v = ((x1q1,....., xjqj ...., xnqn ), ( σiq1, ...., σjqj ..... ,σnqn))
Onde qi ={ 1 ou 2}, i = 1, ....n; cada componente
provém do primeiro ou segundo genitor
selecionado.
Recombinação Intermediária
v1 = (x1, σ1) = ((x11,...., xj1 ..., xn1 ), ( σi1, ..., σj1 .... ,σn1))
v2 = (x2, σ2) = ((x12,...., xj2 ..., xn2 ), ( σi2, ..., σj2 .... ,σn2))
• Cada descendente é dado por:
v = (((x11+ x12)/2, ..., (xn1+ xn2)/2), ( (σ11+ σ12)/2, ...,
(σn1+ σn2)/2))
• Cada componente é dado pela média dos
componentes dos genitores selecionados.
Mutação
• Aplicar mutação ao descendente v obtido dos
passos anteriores.
• O novo descendente é v’ = (x’, σ’)
onde:
x'i = xi + σ i ⋅ N (0,1)
j
j
j
j
j
j
σ ' i = σ i ⋅ exp( τ '⋅ N ( 0,1) + τ ⋅ N ( 0,1))
Mutação
• Os fatores τ e τ' são normalmente definidos por:



2
n



− 1
e
(
2 n
)
− 1
respectivamente.
• O parâmetro n representa a dimensão dos
vetores do problema.
Recapitulando ....
População inicial
Parar?
Fim
Cruzamento
Mutação
Seleção
Nova População
Aplicações
Aplicações a Sistemas de Potência
• Aplicação em Otimização de reativos;
• Planejamento de sistemas de distribuição,
• Reconfiguração de sistemas de distribuição;
• Unit Commitment;
• Fluxo de Potência Ótimo;
• Expansão de sistemas de transmissão, etc.
Dificuldades:
• Característica multimodal;
• Não convexidade;
• A maioria das técnicas convergem a uma
solução local;
• Vários tipos de
variáveis de controle
(posições de taps, bancos de capacitores,
etc.): inteiras, discretas, contínuas.
Dificuldades - Exemplos
Planejamento da expansão de sistemas de
transmissão
• Problema de otimização combinatorial de
grande porte, de difícil solução;
• O número de opções cresce exponencialmente com o tamanho da rede;
• Elevado número de soluções locais.
Dificuldades - Exemplos
Reconfiguração de redes de distribuição:
• Problema de otimização combinatorial;
• Os resultados típicos reportados:
mínimos locais ;
• A manipulação das variáveis inteiras
envolvidas se torna simples
quando é
utilizado AG.
Otimização de Potência Reativa em
Sistemas de Energia Elétrica
∗ Grande desafio em controle e planejamento
de sistemas de potência;
∗ As caraterísticas não convexas restringem
utilização de métodos de otimização clássica.
Operação econômica de um
sistema de energia elétrica
∗ A operação econômica de um sistema de
energia elétrica consiste basicamente em
dois aspectos:
– a regulação de potência ativa e
– despacho de potência reativa.
• Isto leva a um problema de otimização
global multiobjetivo de grande porte.
Operação econômica de um
sistema de energia elétrica
♦ Tipicamente envolve:
♦Determinar os níveis de geração visando
minimizar custo de combustíveis nas
usinas;
♦Minimização de perdas no sistema
através do controle de tensão em barras
PV e de taps de transformadores
♦Restrições operacionais e de segurança.
Despacho de potência reativa
• Pode ser definido como um problema de
otimização global de uma função não linear
descontínua, com um grande conjunto de
restrições lineares e não lineares, atingido
dimensões elevadas para sistemas de
energia elétrica de grande porte”
Formulação do Problema
• Despacho ótimo de potência reativa
“Minimizar as perdas reais de potência
na rede e melhorar o perfil de tensão,
utilizando como controles as tensões
das barras geradoras, compensadores
estáticos e taps de transformadores”.
Formulação do Problema
Min f = ∑(k,m) ∈ NL Prdkm
• s. a.:
• Pdi - Pi (V, θ) =0,
• Qdi - Qi (V, θ) =0,
i ∈ NB-1
i ∈ NPQ
• Qmingi ≤ Qgi ≤ Qmaxgi
• amini
≤ ai
• Vmini ≤ Vi
(1)
≤ amaxi
≤ Vmaxi
,
(2)
(3)
i ∈ NPV
(4)
i ∈ NTAP
(5)
i ∈ NB
(6)
• onde:
• Prdkm = gkm(V2k + Vm2 - Vk Vm cosθkm ) : perdas no
ramo k-m;
Formulação para Resolução Utilizando
Estratégias Evolutivas
Variáveis de controle:
– tensões nos geradores;
– posição de
controláveis.
tap
em
transformadores
Formulação para Resolução Utilizando
Estratégias Evolutivas
Forma penalizada:
Min f = ∑(k,m) ∈ NL Prdkm + ∑i ∈ NPV ρqi(Qgi - Qlgi)2 + ∑i ∈ NB ρvi(Vi - Vli)2
s. a.:
Pdi - Pi(V, θ) = 0 ,
Qdi - Qi(V, θ) = 0 ,
i ∈ NB-1
i ∈ NPQ
ρqi ρvi: fatores de penalidade para as violações de potência reativa
e de tensões, respectivamente;
Qlgi e Vli são os limites violados correspondentes.
Modificações Incluidas
1.- População inicial:
• Os µ candidatos devem satisfazem as
equações de fluxo-de-carga
“As restrições de igualdade sempre são
respeitadas”
Modificações Incluídas
2.- Mutação:
O intervalo das variáveis de controle é
incluído como ganho na mutação:
x i+1 = xi + σi (ximax - ximin )N(0, 1)
Também é possivel utilizar mutações com
distribuição de Cauchy.
Distribuições de Gauss e Cauchy
Modificações Incluídas
2.- Controle da Mutação (σ ):
Para obter mais eficiência no algoritmo,
a mutação nos σ é controlada:
“Limites Dinâmicos”
Limites para os desvios padrão
Variantes Implementadas
Variantes
Nome
MPEE1
EEE0
Meta-PE
Extendida 1
Meta-PE
Extendida 2
EE Extendida 0
EEE1
EE Extendida 1
Gaussiana
EEE2
EE Extendida 2
Gaussiana
EEE3
EE Extendida 3
Gaussiana
EEE4
EE Extendida 4
Cauchy
MPEE2
Mutação
Principal
Gaussiana
Seleção
Recombinação
Torneio
-
Gaussiana
Determinística
-
Gaussiana
Determinística
(µ+λ)
Determinística
(µ+λ)
Determinística
(µ+λ)
Determinística
(µ,λ)
Determinística
(µ+λ)
Seleção
Aleatória
IG-II R1
IG-II R2
IG-II R2
IG-II R2
Sistemas Testados
Sistema
Geradores
Barras PQs
IEEE57
IEEE118
7
54
50
64
Ramos Trafos com tapes
variáveis
80
17
179
9
Limites dos tapes e das tensões de barra
Barras PVs
Barras PQs
Tapes
m in
max
m in
ma x
m in
Vg
Vg
V
V
a
a max
0.90
1.10
0.95
1.05
0.90
1.10
Sistema
IEEE57
IEEE118
ρ Qi
ρ Vi
10
10 6
10
10 8
4
5
Perdas ativas (PU)
0.2793
1.5237
Parâmetros
Parâmetros
µ
λ
TMAX
βO
βf
βPASSO
Tβ
Seleção
q
LM
60
60
200
0.10
-4
5.10
0.10
1
Sq
60
MPEE1
60
60
200
Sq
60
MPEE2
60
60
200
Sd
-
EEE0100
30
60
100
Sd
-
σomax
σomin
σfmax
σfmin
1
1.10
1.10
1.10
-2
-2
-4
EEE0200
30
60
200
Sd
-
Desempenho
Performance geral
Método
LM
MPEE1
MPEE2
EEE0100
EEE0200
f
min
l
0.2484
0.2474
0.2482
0.2438
0.2417
f
max
l
0.2922
0.2848
0.2830
0.2630
0.2486
fl
σl%
f lr %
0.2641
0.2643
0.2592
0.2541
0.2443
4.89
3.68
3.38
2.30
0.82
94.56
94.62
92.79
90.99
87.47
CPU
(min)
1.56
1.55
1.36
0.69
1.34
Evolução do melhor indivíduo
Computação Evolutiva
Programação Evolutiva ( PE)
• A Programação Evolutiva original foi
similar às EE’s desenvolvidas por Schwefel
e Rechenberg, porém envolvendo um
problema mais complexo, que era criar
inteligência artificial.
• Posteriormente David Fogel estendeu
este procedimento para problemas de
otimização numérica.
• Neste modelo, cada componente de uma
solução candidata é visto como um rasgo
comportamental e não como um gene.
• É pressuposta a existência de uma fonte
genética para esses rasgos fenotípicos,
porém a natureza do elo não é detalhada.
• É assumido que qualquer que seja a
transformação genética que aconteça, a
alteração resultante em cada traço
comportamental seguirá de uma
distribuição Gaussiana de média nula e
algum desvio padrão.
• Em razão que algumas alterações genéticas
podem afetar as características do fenótipo
por pleitropia e poligenia, é apropriado que
todos os componentes de um genitor sejam
perturbados na criação de um descendente
O que são esses conceitos?
• Pleitropia: Capacidade de um único gene
ser o responsável, no fenótipo do
organismo, por múltiplos efeitos que
aparentemente não se relacionam.
• Poligenia: Condição do caráter
determinada por vários genes.
Algoritmo Canônico
• O algoritmo padrão ou canônico
proposto por Fogel é dado a seguir,
sendo que várias modificações têm
sido propostas por outros autores.
i) A população inicial S, de dimensão m, é
determinada aleatoriamente, a partir de
um conjunto uniformemente distribuído
num intervalo [a, b].
ii) Avaliação: Para cada si ∈ S é associada
uma fitness individual definida em geral
como:
•
φ(si) = G( F(si) , vi )
φ(si) = G( F(si) , vi )
Onde:
• F(si) denota a fitness verdadeira de si
• vi representa uma alteração aleatória em
si , uma variação aleatória na avaliação de
F(si) ou outra relação com si .
iii) Mutação: Cada indivíduo si ∈ S , i=1, ...., m, é
alterado e associado a si+m tal que:
si+m, j = si, j + N(0, βjφ(si) + zj), ∀ j =1, ....., k
onde:
• si, j : elemento j do indivíduo i;
N(µ, σ2) representa uma variável aleatória
com média µ e variância σ2;
βj é uma constante de escala de φ(si)
zj representa um valor de ajuste de offset; k
é a dimensão de si.
iv) A cada indivíduo si+m, j, i=1, ..., m, é
associado um valor de fitness dado por:
φ(si+m) = G( F(si+m) , vi+m )
Competição : torneio
v) Para cada si , i=1, ...,2m, é associado um valor wi de
acordo com:
wi =∑ t=1 w t ;
c
*
•ondee:
w t = 1, se φ(si) ≤ φ(sr);
= 0, caso contrário.
*
• Com:
r = [2mu1 + 1] , r ≠ i
que representa o maior inteiro menor ou igual
a 2mu1 + 1
c : número de competições
u1 um número aleatório de distribuição
uniforme no intervalo [0,1].
vi) Os indivíduos si, i=1, .....2m são classificados
em ordem decrescente de seus valores wi.
Os m primeiros indivíduos são selecionados
para formar a próxima geração.
vii) Se o critério de parada é satisfeito, parar;
caso contrário voltar para iii).
Resumindo....
Algoritmo de CE:
•
•
•
•
Solução inicial aleatória de m indivíduos
Aplicar mutação para gerar m descendentes
Aplicar torneio e selecionar o m melhores
Testar critério de parada
Discussão
• Diferenças entre Programação Evolutiva e
Estratégias Evolutivas.
• Como foi dito anteriormente, há poucos anos as
técnicas de PE foram generalizadas para
manipular problemas de otimização numérica.
• Elas são muito similares com relação às EE’s.
• Elas usam representação de ponto flutuante e o
operador chave é a mutação.
Diferenças entre PE e EE´s
As diferenças básicas entre elas são:
• Em PE não são utilizados operadores de
recombinação;
• Em PE é utilizada uma seleção
probabilística (torneio), ao passo que EE´s
selecionam os µ melhores indivíduos para
a próxima geração;
Diferenças entre PE e EE´s
• Em PE os valores de fitness são obtidos a
partir dos valores da função objetivo
escalados e eventualmente impondo algum
componente aleatório.
• O desvio padrão para cada mutação de
indivíduo é calculado como a raiz quadrada
de uma transformação linear de seus
valores de fitness.
Diferenças entre PE e EE´s
EE´s:
• Mutação dos desvios é baseado em distribuição
exponencial
•
Garante positividade dos desvios
CE:
• È necessário um off-set para evitar negatividade
Algoritmos Genéticos
Fundamentos dos Algoritmos
Genéticos
“Quanto melhor um indivíduo se adaptar ao
seu meio ambiente, maior será sua chance
de sobreviver e gerar descendentes.”
(DARWIN, 1859)
O que são?
• Os Algoritmos Genéticos são uma
classe de procedimentos, com passos
distintos bem definidos.
• Essa classe se fundamenta em
analogias a conceitos biológicos já
testadas à exaustão.
• Cada passo distinto pode ter diversas
versões diferentes.
Para que servem?
• Busca e Otimização
• Amplamente utilizados, com sucesso, em
problemas de difícil manipulação pelas
técnicas tradicionais
• São considerados como metodologia de
propósito geral
Características Gerais
•
•
•
•
Utilizam uma codificação do conjunto de
parâmetros (indivíduos) e não com os próprios
parâmetros (estados);
Varrem várias regiões do espaço de busca de
cada vez;
Utilizam como direção de busca a qualidade, em
contraste com as derivadas utilizadas nos
métodos tradicionais de otimização;
Utilizam regras de transição probabilísticas e
não regras determinísticas.
Características Gerais
Algoritmos Genéticos podem ser
considerados como métodos que trabalham
com
Buscas Paralelas Randômicas Direcionadas
Forma canônica
1. Gerar População Inicial
2. Seleção: Descartar uma parte dos
Indivíduos menos aptos
3. Reprodução
4. Mutação
5. Se o critério de parada foi satisfeito,
encerrar. Senão, voltar ao passo 2.
Modelagem
Indivíduos
• Cada indivíduo possui um código genético
• Esse código é chamado cromossomo
• Tradicionalmente, um cromossomo é um
vetor de bits
• Representação binária: nem sempre é o
ideal
Operadores Fundamentais
Seleção Natural: escolha dois mais aptos
Criação de novas estruturas:
Operador Reprodução
Operador Mutação
Cromossomo
– Estrutura de dados que representa uma
possível solução para o problema.
– Os parâmetros do problema de otimização
são representados por cadeias de valores.
Exemplos:
• Vetores de reais, (2.345, 4.3454, 5.1, 3.4)
• Cadeias de bits, (111011011)
• Vetores de inteiros, (1,4,2,5,2,8)
• ou outra estrutura de dados.
Seleção
Seleção Natural
• É o princípio básico para o direcionamento
da evolução de uma população
• Utiliza uma função de avaliação para medir
a aptidão de cada indivíduo
• Essa aptidão pode ser absoluta ou relativa
• Existem vários métodos de seleção
Aptidão ou Fitness
• Aptidão
– Nota associada ao indivíduo que avalia quão
boa é a solução por ele representada.
• Aptidão pode ser:
– Igual a função objetivo
– Resultado do escalonamento da função
objetivo.
– Baseado no ranking do indíviduo da população.
Principais Métodos de Seleção
Natural
• Roleta
• Torneio
• Amostragem Universal Estocástica
População: Exemplo
Indivíduo
Aptidão Absoluta
Aptidão Relativa
1
2
0,052631579
2
4
0,105263158
3
5
0,131578947
4
9
0,236842105
5
18
0,473684211
Total
38
1
Método da Roleta
• Coloca-se os indivíduos em uma roleta, dando a
cada um uma “fatia” proporcional à sua aptidão
relativa
• Depois roda-se a agulha da roleta. O indivíduo em
cuja fatia a agulha parar permanece para a
próxima geração
• Repete-se o sorteio quantas vezes forem
necessárias para selecionar a quantidade desejada
de indivíduos
Roleta - Exemplo
Método do Torneio
• Utiliza sucessivas disputas para realizar a
seleção
• Para selecionar k indivíduos, realiza k
disputas, cada disputa envolvendo n
indivíduos escolhidos ao acaso
• O indivíduo de maior aptidão na disputa é
selecionado
• É muito comum utilizar n = 3
Torneio - Exemplo
Indiv 1, Indiv 2, Indiv 4
Indiv 4
Indiv 1, Indiv 2, Indiv 3
Indiv 3
Indiv 2, Indiv 3, Indiv 4
Indiv 4
Indiv 3, Indiv 4, Indiv 5
Indiv 5
Amostragem Universal
Estocástica - SUS
• SUS – Stochastic Universal Sampling
• Semelhante à Roleta, mas para selecionar k
indivíduos utiliza k agulhas igualmente
espaçadas, girando-as em conjunto uma só
vez
• Apresenta resultados menos variantes que a
Roleta
SUS - Exemplo
Operador de Cruzamento
Operador de Cruzamento
• Também chamado de reprodução ou
crossover
• Combina as informações genéticas de dois
indivíduos (pais) para gerar novos
indivíduos (filhos)
• Versões mais comuns criam sempre dois
filhos para cada operação
Operador de Cruzamento
• Operador principal do AG
• Responsável por gerar novos indivíduos
diferentes (sejam melhores ou piores) a
partir de indivíduos já promissores
• Aplicado a cada par de indivíduos com alta
probabilidade (normalmente entre 0,6 e
0,99)
Abordagens para Cruzamento
• Cruzamento Um-Ponto
• Cruzamento Multi-Pontos
• Cruzamento Uniforme
Cruzamento Um-Ponto
0
0
0
0
Pais
1
1
1
1
0
0
1
1
Filhos
1
1
0
0
Cruzamento Multi-Ponto
0
0
0
0
Pais
1
1
1
1
0
1
1
0
Filhos
1
0
0
1
Cruzamento Uniforme
Máscara
0
1
0
1
0
0
0
0
Pais
1
1
1
1
0
1
0
1
Filhos
1
0
1
0
Operador Mutação
Operador de Mutação
• Introduz e mantém a variedade genética da
população
• Garante a possibilidade (potencial) de se
alcançar qualquer ponto do espaço de busca
• Útil para evitar mínimos locais
Operador de Mutação
• É um operador genético secundário
• Se seu uso for exagerado, reduz a evolução
a uma busca totalmente aleatória
• Logo, um indivíduo sofre mutações com
probabilidade baixa (normalmente entre
0,001 e 0,1)
Exemplo de Mutação
0
1
1
0
0
0
1
0
1
0
0
0
0
1
Parâmetros Genéticos
•
•
•
•
•
Tamanho da população
Taxa de cruzamento
Taxa de mutação
Intervalo de geração
Critério de parada
Convergência do Algoritmo
Genético
Convergência do Algoritmo
Genético
• Apesar do sucesso uso dos AG’s em
problemas de otimização, os avanços nos
aspectos teóricos têm sido limitados.
• As atuais bases teóricas dos AG’s
descansam na representação binária das
soluções e na noção de Esquemas, que
permite explorar as similaridades entre
cromossomos.
• Considere-se um caso onde alguns bits de
uma string são fixados em valores
específicos, enquanto os restantes são
considerados livres.
• Define-se o símbolo # para representar os
bits que estão nesta última condição.
Teoria dos Esquemas
• Por exemplo:
• a string (01##) define o conjunto:
{(0100), (0101), (0110), (0111)}.
Esquema é uma família de configurações que
compartilham um conjunto de genes
comuns
Teoria dos Esquemas
• O número de # no esquema define o número
de strings associadas a ele ( 2^{n} )
• Existem duas importantes propriedades
associadas com os Esquemas:
• Ordem
• Comprimento Definido
Ordem de um Esquema
• Definida como o(S), é o número de
posições fixas presentes no esquema.
• Por exemplo, a ordem do esquema
S = (##001#11) é o(S) = 5.
Este conceito é útil no cálculo da
probabilidade de sobrevivência de um
esquema sob mutações.
Comprimento Definido
É a distância δ(S) entre a primeira e a última
posição fixada da string S
⇒ “grau de compactação da informação
contida no esquema”.
No exemplo anterior:
S = (##001#11)
δ(S) = 8 - 3 = 5.
Esquemas
•
Uma string específica é simultaneamente a
instância de 2l esquemas, sendo l o comprimento
da string
Esquemas: um visão 3D
• Uma vez que um esquema representa um
subconjunto de strings, podemos associar a ele
uma fitness, que é determinada pela fitness
média das instâncias do esquema.
• Através do conceito de esquema, um processo de
busca do ótimo através de AG pode ser visto
como uma competição entre esquemas para
incrementar o número de suas instâncias na
população
• Se definimos a string ótima como a
contraposição de esquemas com pequeno
comprimento definido e altos valores de
fitness média, então o vencedor das
competições individuais de esquemas pode,
potencialmente, incluir a string ótima.
Blocos Construtivos
• Esses esquemas com pequenos
comprimentos definidos e alta fitness são
chamados de building blocks.
Hipótese dos Blocos Construtivos
• A noção de que strings com altos valores
de fitness podem ser conseguidas mapeando
building blocks com valores altos de fitness
e combinando-os efetivamente é chamada
de hipótese dos building blocks
Hipótese dos Blocos Construtivos
• Esta hipótese nem sempre se cumpre;
• Dependendo da natureza da função
objetivo, podem ser geradas strings de
baixa qualidade a partir de bons building
blocks.
• Essas funções objetivos são chamadas de
funções AG-ilusórias
Teorema dos Esquemas
• Desconsiderando o cruzamento, um
esquema com alta fitness média cresce
exponencialmente para vencer a
competição. Porém, uma alta fitness média
não é suficiente para uma alta razão de
crescimento. Um esquema deve ter também
um comprimento definido pequeno.
Teorema dos Esquemas
• Como o cruzamento é disruptivo,
comprimentos definido elevados levam a
uma alta probabilidade que o ponto de
cruzamento esteja entre as posições fixas
do esquema, causando a destruição de uma
instância.
Teorema dos Esquemas
• Logo, esquemas com alta fitness e
pequenos comprimentos definidos crescem
exponencialmente no tempo.
• Esta é a essência do Teorema dos
Esquemas, proposto por Holland.
Fim
Parte I