Trabalho para a disciplina de Otimização
Natural
Autor: Adriano Gomes
Roteiro

1.
2.
3.
4.
Introdução
Exemplos de mudança de parâmetros
Classificação das técnicas de controle
Outros exemplos de variação de parâmetros de EAs
Introdução

 Objetivo: escolher os parâmetros ótimos para
algoritmos evolucionários (EA)
 Parâmetros de algoritmo ou parâmetros de estratégia




Tamanho da população
Probabilidade de mutação
Probabilidade de cross over
etc
Introdução

 Duas formas de definir os valores dos parâmetros do
algoritmo
 Afinação de parâmetros (parameter tuning)
 Abordagem comumente praticada
 Consiste em definir bons valores de parâmetros antes de
executar o algoritmo
 Rodar o algoritmo com os parâmetros fixos
Introdução

 Controle de parâmetros (parameter control)
 Rodar o algoritmo com parâmetros iniciais
 Parâmetros são modificados no decorrer da execução do
algoritmo
Introdução

 Sabe-se que:
 Os parâmetros não são independentes e testar todas as
combinações é impraticável
 Para 4 parâmetros que podem assumir 5 valores cada um,
existem 54 = 625 combinações
 Se para cada combinação rodarmos o algoritmo 100 vezes,
executaríamos ele 62500 vezes
 O processo de afinação de parâmetros consome muito
tempo (mesmo se desconsiderarmos a relação entre os
parâmetros)
 Os valores selecionados após o processo de afinação não são
necessariamente ótimos
Introdução

 Devido os EA’s serem processos dinâmicos e
adaptativos:
 Conjuntos de valores de parâmetros distintos podem ser
ótimos em diferentes estágios do processo evolucionário
 Conclusão: Usos de parâmetros estáticos podem levar
a uma performance inferior do algoritmo
 Em outras palavras: parâmetros que variam com o
decorrer do algoritmo sempre podem ser melhores
que parâmetros estáticos
Introdução

 Solução: Definir os parâmetros como funções do tempo (p
=> p(t))
 Problema: como o processo para definir parâmetros
estáticos já é complexo, definir parâmetros dinâmicos é
ainda mais
 Outra abordagem: Utilizar um EA para afinar os
parâmetros do EA que tenta resolver um problema
particular
 Duas maneiras
 Utilizar dois EAs, onde um deles (META-EA) é utilizado
para afinar os parâmetros do outro
 Utilizar apenas um EA, o qual afina os próprios parâmetros
e resolve o problema
Exemplos de mudança de
parâmetros

 Problema: otimização numérica para minimizar:
f(X) = f(x1, ..., xn)
 Sujeita a alguma desigualdade e restrições de igualdade:
gi(X) ≤ 0 , i=1, ..., q
hj(X) = 0, j = q+1, ..., m
 Domínio das variáveis dados pelos limites superior e
inferior li ≤ xi ≤ ui , 1 ≤ i ≤ n
 Algoritmo evolucionário baseado na representação de
ponto flutuante (X representado como um vetor de ponto
flutuante)
Exemplos de mudança de
parâmetros

 Mudança do tamanho do passo da mutação
 Assumindo que a prole é produzida por crossover aritmético e por
mutação gaussiana, substituindo componentes do vetor X por:
xi’ = xi + N(0, σ)
 Método mais simples: utilizar σ fixo
 Mas, pode ser vantajoso variar o tamanho do passo da mutação (variar
σ)
 Primeiro modo de variar o parâmetro σ
 Mantendo o mesmo σ para todos os vetores X e para todas as
variáveis/componentes de X
 Usando um σ dinâmico de acordo com o número da geração
 Exemplo:
σ(t) = 1 – 0.9 * (t/T)
 t é o número da geração atual (variando de 0 a T)
 o passo decresce conforme t aumenta(σ(0)=1 até σ(T)=0.1 )
Exemplos de mudança de
parâmetros

 A mudança do valor de σ é completamente determinístico
 Métodos de mudança deste tipo são chamados de controle de
parâmetros determinísticos
 Implica em total controle por parte do usuário
 Segundo modo de variar o parâmetro σ
 Mantendo o mesmo σ para todos os vetores X e para todas as
variáveis/componentes de X
 Incorporando feedback do processo de busca
 Este tipo de variação (que incorpora feedback) é chamado de Controle
de parâmetro adaptativo
 Exemplo bem conhecido (Rechenberg’s 1/5 rule):
 Taxa de sucesso de todas as mutações deve ser 1/5
 Se a taxa é maior que 1/5, o tamanho do passo deve ser incrementado
 Se a taxa é menor que 1/5, o tamanho do passo deve ser decrementado
Exemplos de mudança de
parâmetros

 A regra é executada em intervalos periódicos (depois de k iterações) e
pode ser expressa matematicamente por:
σ’ = σ/c
, se ps>1/5
σ’ = σ * c , se ps<1/5
σ’ = σ
, se ps=1/5
 0.817 ≤ c ≤ 1
 Valores de σ(t) são não determinísticos
 Terceiro modo de variar o parâmetro σ
 Atribuir um tamanho individual de passo da mutação para cada
solução
 Para isso, estender a notação de indivíduos para o tamanho n+1
X = (x1, ..., xn, σ)
 Então, o σ de cada indivíduo também sofrerá evolução
 Possível solução:
σ‘ = σ * e^(τ * N(0,1))
xi‘ = xi + σ‘ * Ni(0,1)
Exemplos de mudança de
parâmetros

 Se desejarmos um tamanho de parâmetro do passo da
mutação para cada xi, estendemos X da seguinte forma:
X = (x1, ..., xn, σ1, ..., σn)
 E a solução passa a ser:
σ‘ = σ * e^(τ * Ni (0,1))
xi‘ = xi + σi‘ * Ni(0,1)
 Esse modo de variar o passo através da evolução é
chamado de controle de parâmetro Self-adaptive (Selfadaptive parameter control)
Exemplos de mudança de
parâmetros

 Mudança nos coeficientes de penalidade
 Quando lida-se com funções que possuem restrições
 Frequentemente usa-se funções de penalidade para penalizar a função
objetivo
 Se queremos minimizar a função, a penalidade é positiva
 Se queremos maximizar a função, a penalidade é negativa
 No exemplo inicial, podemos reescrever a função de avaliação como:
eval(X) = f(X) + W * penalty(X)
 Como queremos minimizar a função, penalty(X) será positiva se alguma
restrição for violada e zero caso contrário
 Em muitos métodos, um conjunto de funções fj (1 ≤ j ≤ m) é utilizado
para construir a penalidade. No exemplo:
fj(X) = max{0, gj(X)}
fj(X) = |hj(X)|
, se 1 ≤ j ≤ q
, se q+1 ≤ j ≤ m
 W é o peso e é definido pelo usuário
Exemplos de mudança de
parâmetros

 Podemos usar W fixo ou variar utilizando os três métodos
descritos na mudança do passo da mutação:
 Controle de parâmetro determinístico
 Exemplo:
 W(t) = (C * t)α , C,α ≥ 1
 Controle de parâmetro adaptativo
 Exemplo:
 W(t+1) = (1/β1) * W(t)
 W(t+1) = (β2) * W(t)
 W(t)




, se bi ϵ ϝ para todo t-k+1 ≤ i ≤ t
, se bi ϵ S-ϝ para todo t-k+1 ≤ i ≤ (t)
, caso contrário
S é o conjunto de todos os pontos de busca (soluções)
ϝ é o conjunto de todas as soluções possíveis (ϝ S)
bi é o melhor indivíduo com base na função eval
β1 ,β2>1 e β1β2
Exemplos de mudança de
parâmetros

 Em palavras



Se nas últimas k gerações todos os melhores indivíduos são indivíduos possíveis
(que não violam restrições), então W(t+1) é diminuído
Se nas últimas k gerações todos os melhores indivíduos são indivíduos não possíveis
(que violam restrições), então W(t+1) é aumentado
Se existem indivíduos possíveis e não possíveis nas últimas k gerações, então
W(t+1)=W(t)
 Controle de parâmetro self-adaptive
 Exemplo
 Representação do indivíduo
X = (x1, ..., xn, w1, ..., wn)
 Função de avalição
eval(X) = f(X) +
 Problema:
𝑚
𝑗=1 𝑤𝑗 𝑓𝑗 (𝑋)
eval(X,W) = fw(X)
 A função de avaliação fica dependente dos pesos e a evolução pode focar na
minimização dos pesos ao invés de otimizar f e satisfazer as restrições
Classificação das técnicas
de controle

 Alguns aspectos que devem ser levados em conta em
técnicas de controle de parâmetros
 O que varia?
 Componentes de um EA






Representação de indivíduos
Função de avaliação
Operadores de variação e as suas probabilidades
Operadores de seleção (seleção de pais)
Operadores de substituição (seleção de sobrevivente)
População (tamanho, topologia, etc)
 Não sabemos ao certo o número de parâmetros, pois cada
componente pode ser parametrizado e gerar um ou mais
parâmetros
Classificação das técnicas
de controle

 Como são feitas as mudanças?
 Já visto:
 Tipos de configuração de parâmetros
 Afinação de parâmetros
 Controle de parâmetros
 Categorias do controle de parâmetros
 Controle de parâmetro determinístico
 Controle de parâmetro adaptativo
 Controle de parâmetro self-adaptive
Classificação das técnicas
de controle

 Quais evidências informam as mudanças?
 Evidência absoluta
 O valor do parâmetro de estratégia é alterado por alguma
regra que é aplicada quando um evento predefinido ocorre
 Usa o feedback da busca
 Exemplos
 Aumento da taxa de mutação quando a diversidade da
população cai abaixo de um dado valor
 Mudança da probabilidade de realização da mutação ou
crossover de acordo com um conjunto de regras fuzzy usando
uma variedade de estatísticas da população
 Métodos para regular o tamanho da população baseado nas
estimativas de aptidão e variância
Classificação das técnicas
de controle

 Evidência relativa
 Os valores dos parâmetros são comparados de acordo com
a aptidão da prole que eles produzem e os melhores
valores são recompensados
 A direção ou magnitude da mudança do parâmetro não é
especificado deterministicamente, mas relativo a
performance de outros parâmetros
 Relação entre evidência absoluta, relativa e controle de
parâmetro determinístico, adaptativo e self-adaptative
Determinístico
Adaptativo Self-adaptative
Absoluto
Possível
Possível
Não possível
Relativo
Não possível
Possível
Possível
Classificação das técnicas
de controle

 Qual é o escopo da mudança?





Afeta o gene (parâmetro)
Afeta o cromossomo inteiro (indivíduo)
Afeta a população inteira
Afeta outro componente (ex: seleção)
Afeta a função de avaliação
Outros exemplos de
variação de parâmetros de
EAs

 Variação da função de avaliação
 Problema de satisfação de restrições (o objetivo é
encontrar um vetor S que satisfaça todas as restrições)
𝑚
𝑓 𝑆 =
𝑤𝑖 ∗ 𝑥(𝑆, 𝑐𝑖 )
𝑖=1
𝑥 𝑆, 𝑐𝑖 = 1,
𝑆𝑒 𝑆 𝑣𝑖𝑜𝑙𝑎 𝑐𝑖
𝑥 𝑆, 𝑐𝑖 = 0,
𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟á𝑟𝑖𝑜
 wi é peso atribuído a cada restrição (expressa a
dificuldade de satisfazê-la)
 ci’s são as restrições
Outros exemplos de
variação de parâmetros de
EAs

 Variação da probabilidade de mutação
 Controle de parâmetro determinístico
−𝑡
exp(
)
α
2
𝑝𝑚 =
𝑥
β
λ 𝐿




α, β,  são constantes
L é o comprimento do cromossomo
λ é o tamanho da população
t é o tempo (número da geração)
Outros exemplos de
variação de parâmetros de
EAs

 Controle de parâmetro self-adaptative
 Como fazer a mutação?
 Estender o cromossomo de 20 bits
 Seguir os passos:
1.
2.
3.
4.

Problema


Decodificar os 20 bits para pm
Fazer a mutação nesses 20 bits com probabilidade pm
Decodificar os bits resultantes da mutação para pm’
Fazer a mutação nos bits que codificam a solução com
probabilidade pm’
Fica preso em regiões sub-ótimas com baixa taxa de mutação
para cada indivíduo da população
Solução

Eliminar o primeiro passo e realizar a mutação do segundo
passo com probabilidade fixa
Outros exemplos de
variação de parâmetros de
EAs

 Variação da taxa de Crossover
 Exemplo
 É usado mais de um operador de Crossover
 Cada operador possui uma probabilidade pc(opi)
 Cada operador têm um valor di que representa a força
do operador (recompensa obtida de acordo com a
qualidade da cria gerada)
 di‘s atualizados a cada uso do operador i
 pc(opi)’s são recalculados a cada k gerações
 Ideia: redistribuir 15% das probabilidades baseado na
força do operados
Outros exemplos de
variação de parâmetros de
EAs

 Para isso, os di’s são normalizados para ter soma 15
(dinorm)
 As probabilidades são recalculadas de acordo com:
pc(opi) = 0.85 * pc(opi) + 0.01 * dinorm
Outros exemplos de
variação de parâmetros de
EAs

 Variação de parâmetros da seleção
 Existem mecanismos que variam a pressão de seleção baseado
no fator de Boltzmann
 Exemplo
 Uso do critério de aceitação de Boltzmann em uma parte da busca
local de um algoritmo memético
 A temperatura é inversamente relacionada com a diversidade de
aptidão da população
 Quanto mais espalhados forem os valores de aptidão, menor é a
temperatura
 Muito espalhado implica em temperatura baixa (menos provável
aceitar soluções piores)
 Pouco espalhado implica em temperatura alta (mais provável
aceitar soluções piores
 Consequência: contribui para elevar a diversidade da população
Outros exemplos de
variação de parâmetros de
EAs

 Variação do tamanho da população
 Exemplo
 Atribuir um tempo de vida aos indivíduos da população
 Em cada geração, reduzir o tempo de vida dos
indivíduos de um
 Se o tempo de vida chega a zero, o indivíduo é removido
 Aos indivíduos recém-nascidos são atribuídos tempos de
vida baseados nas suas aptidões
 O número de crias de um indivíduo é proporcional ao
número de gerações que ele sobrevive (propaga genes
bons)