Algoritmos Geneticos
Material adaptado de
http://www.dca.ufrn.br/~estefane/metaheuristicas/
Problemas de Permutação

Em muitos problemas de otimização a
meta é encontrar um ordenamento
eficiente de ações ou tarefas.

Exemplos:
 Problema do Caixeiro Viajante
 Problemas de Agendamento
 Coloração de Grafos
Problema do Caixeiro Viajante
 Dado N cidades, achar a caminho
mais curto passando por todas as
cidades uma única vez.
 PCV é NP-dificil
Representação do PCV
 As cidades são representadas
diretamente no cromossomo.
Cromossomos
A B C D F E G
A B C D F G E
Operadores de Permutação
 Order-Based Mutation
 Position-Based Mutation
 Scramble Mutation
 OBX (Order-Based Crossover)
 PBX (Position-Based Crossover)
 PMX (Partially Matched Crossover)
 CX (Cycle Crossover)
 OX (Order Crossover)
Mutação de Permutação
Position-Based Mutation : retira o elemento da posição i
e insere na posição j
A B C D E F G
A C D EB F G
Order-Based Mutation : troca o elemento da posição i
com o elemento na posição j
A B C D E F G
A E C D B F G
Mutação de Permutação
Scramble Mutation - Uma sublista, aleatoriamente
selecionada, é embalharada.
A B C D E F G
A B D E C F G
Order-Based Crossover (OBX)
Elementos são selecionadas aleatoriamente. É imposta
uma ordem nos elementos selecionadas do pai1 igual a
ordem dos respectivos elementos em pai2.
pai1 A B C D F E G
pai2 C E G A D F B
*
*
*
filho1 A D C F B E G
filho2 C A G D E F B
Position-Based Crossover (PBX)
Elementos são selecionadas aleatoriamente e a posição
dos elementos selecionadas no pai2 é imposto ao pai1.
pai1 A B C D F E G
pai2 C E G A D F B
*
*
*
filho1 B E C A D F G
filho2 C B E D F G A
Partially Matched Crossover (PMX)
Realiza trocas no sentido de pai1 para pai2 e depois no
sentido inverso, isto é, de pai2 para pai1, para evitar
cromossomos inválidos.
pai1 A B C D E F G
pai2 C F E B G D A
filho1
filho2
A D E B C F G
E F C D G B A
O Problema da Mochila zero-um
(do inglês, 0-1 knapsack problem)
𝑛
Maximizar
𝑧=
𝑐𝑗 𝑠𝑗
𝑗=1
𝑛
Sujeita a
𝑤𝑗 𝑠𝑗 < 𝑏
𝑗=1
𝑠𝑗 ∈ 0,1
Uma solução s é um vetor de uns e zeros.
Se o objeto j está mochila então sj = 1, caso contrário
sj = 0.
Algoritmo Genético

Cromossomo


A solução s (um vetor de uns e zeros) é naturalmente representada por um
cromossomo binário.
Operadores binários padrão

Crossover de 1-ponto (ou 2-pontos, etc)

Mutação (invertendo os bits)
Uma Instância do Problema da Mochila
Capacidade da mochila:
b = 25
11001110 (cromossomo válido)
peso = 5+4+4+4+6 = 23 < 25
função objetivo = 3+3+2+3+5 = 16
11111001 (inválido)
peso = 36 > 25
Função objetivo = ?
Como Lidar com Indivíduos Inválidos?

Solução 1 – reparar o indivíduo

Solução 2 – penalizar a função objetivo
Reparando o Indivíduo


Indivíduo inválido

11111001

peso = 36 > 25

Função objetivo = 16
1 1 1 1 1 0 0 1
desprezar
Indivíduo “reparado”

11110000

Peso = 24 (ok!)

Função objetivo = 12
visitar cada bit da
esquerda para a direita e
desprezar os bits que
invalidam a solução.
Reparando o Indivíduo


Por qual ordem dos bits devem ser visitados?

Da esquerda para direita?

No sentido oposto?

Aleatoriamente?
Algoritmo Guloso

Visitar primeiro os bits com a maior razão benefício/peso;

Pode produzir melhores resultados.
Penalizando a Função Objetivo
Um exemplo de penalidade é:
Onde a é um coeficiente de penalidade igual a:
Objetos que ultrapassam a capacidade da mochila
são penalizados.
Penalizando a Função Objetivo

Exemplo

11111001

peso = 36 > 25

Função original = 16

Função com penalidade = 16 – 14 x (36-25) = -138
Discussão
Principais Tópicos

População Inicial

Funções Objetivo de Alto Custo

Critérios de Parada

Convergência Prematura

Diversidade

Tipos de Substituição

Problemas na Aptidão

Ranking

Seleção por Torneio

Amostragem Estocástica Uniforme
População Inicial (1/3)

Gerada Aleatoriatoriamente.

Gerada uniformente em uma grade.

Gerada com tendenciosidade para regiões promissoras do espaço de
busca
População Inicial (2/3)

Para garantir que toda posição da cadeia tem 0 e 1 na população:

Gera a primeira metade da população aleatoriamente.

Inverte todos os bits da primeira metade: tem-se a segunda metade.
1a.
metade
2a.
metade
1011010
0100101
0111011
100010
0001101
1110010
1100110
0011001
População Inicial (3/3)

Seeding: insere a solução obtida por outro método de otimização na
população inicial (garante que AG não fará pior do que o outro método)

Iniciar com uma larga população inicial e depois reduzir o tamanho.
Convergência Prematura (1/2)

O AG converge para um mínimo/máximo local.
Convergência Prematura (2/2)

Causas:

Excessivo números de filhos de um mesmo indivíduo (o superindivíduo)

Perda de diversidade.

Deriva Genética (Genetic Drift)


Desaparecimento de genes na população devido puramente ao acaso.

Ocorre principalmente em pequenas populações.
Alta pressão de seleção.
Diversidade (1/2)

Combatendo a perda de diversidade

Aumentar a taxa de mutação.

Evitar cromossomos duplicatas na população.

Diminuir a pressão da seleção.
Diversidade (2/2)

Combatendo a perda de diversidade

Controlar o número de filhos do superdíviduo (indivíduo com alta aptidão,
mas não com aptidão ótima) usando:

Ranking.

Escalonamento.

Seleção por torneio.
Tipos de Substituição

Substituição Geracional

Substituição Geracional com Elitismo

Substituição de Regime Permanente (do inglês steady state)
Substituição Geracional
Seja N o tamanho da população:

Os N pais são substituídos pelos N filhos em cada geração.

Os N pais são substituídos por N individuos do conjunto união de pais e
filhos.

Comentário: o segundo caso aumenta a pressão de seleção.
Substituição Geracional
com Elitismo

Os k < N melhores pais nunca são substituídos.

Tipicamente k = 1

Aumentando k aumenta a pressão de seleção (risco de convergência
prematura).
Substituição de
Regime Permanente (1/2)


Em cada “geração” apenas 2 (ou 1) filhos são gerados e substituem:

Os 2 piores indivíduos da população.

Os pais.

Os 2 indivíduos mais velhos (i.e., que estão a mais tempo da população),
pois já transmitiram os seus genes.
Taxa de crossover é geralmente alta (~1).
Substituição de
Regime Permanente (2/2)

Alternativamente, k < N filhos são gerados e substituem os k piores
indivíduos.

Evitar inserir um filho na população quando já existe uma duplicata
dele na população.
Problemas na Aptidão (1/3)

Aptidão negativa não funciona com a roleta.

Aptidão excessivamente alta


Poucos individuos ocupando larga fatia da roleta

Muitos individuos ocupando pequena fatia da roleta

Causa convergência prematura
Solução: controlar o número de filhos do superindivíduo.
.
Problemas na Aptidão (2/3)

Resolução insuficiente para diferenciar os melhores dos piores
individuos.

A seleção torna-se aleatória (Passeio ao Acaso).

Convergência lenta
Problemas na Aptidão (3/3)

Exemplo:

Soluções

Expandir o intervalo da aptidão (usando ranking, escalamento linear)

Seleção por torneio
Ranking Linear (1/3)
Onde i é o índice do cromossomo na população
em ordem decrescente de valor da função
objetivo.
Ranking linear requer:
1  Max  2
Max + Min = 2
Valores bons para Max: de 1.2 a 1.5
Ranking Linear (2/3)
Ranking Linear (3/3)

Controlando a pressão da seleção por Ranking linear:

maior pressão => mais intensificação;

menos pressão => mais diversificação.
Ranking Exponencial
𝑓𝑖 = 𝑞(1 − 𝑞)𝑖−1
q  [0, 1] e i é o índice do cromossomo na população em
ordem decrescente de valor da função objetivo.
Ranking exponencial permite maior pressão de seleção do
que o ranking linear.
Escalonamento Linear

Escalonamento linear
onde g é o valor da função objetivo
a e b são determinados tal que o
número máximo de filhos do melhor
indivíduo seja no máximo igual a C
(onde tipicamente C = 2)
Seleção por Torneio

Escolhe-se k (tipicamente 2) indivíduos aleatoriamente da população e
o melhor é selecionado.

Não é proporcional a aptidão,

Não é necessário roda da roleta, escalamento da aptidão ou ranking.
Seleção por Torneio
Os indivíduos são selecionados
para os torneios com igual
probabilidade.
O torneio é vencido
pelo indivíduo com
maior aptidão
Seleção por Torneio


Aumentando o tamanho k do torneio acarreta:

Aumento da pressão de seleção.

Risco de convergência prematura.
Por isso, o torneio binário é o mais utilizado.
Seleção por Torneio

Seleção por torneio com probabilidades

(Reduz ainda mais a pressão de seleção)
1)O melhor indivíduo do torneio é selecionado com
probabilidade p > 0,5
2)O segundo melhor é selecionado com probabilidade
p(1-p)
3)O terceiro é selecionado com probabilidade p(1-p)2
4)e assim por diante...
Amostragem Estocástica Uniforme
Evita a grande variância de filhos esperados do
método da roleta (é tão perfeito quanto possivel)
N ponteiros igualmente
espaçados.
e
d
a
c
b
Pais selecionados
a a b c d
Critérios de Parada
Atingiu um dado número de gerações ou avaliações.
 Encontrou a solução (quando esta é conhecida).
 Perda de diversidade.
 Convergência: não ocorre melhora significativa na solução durante um
dado número de gerações.

Funções Objetivo
de Alto Custo (1/3)
Em muitos problemas do mundo real o custo computacional do AG está
concentrado na avalição do individuo.
 Exemplo:


Simulação completa de um processo.

Um treinamento de uma rede neural.
Funções Objetivo
de Alto Custo (2/3)

Dicas para reduzir o números de reavaliações do indivíduo:

Evitar cromossomos iguais na população inicial.

Verificar se o filho já existe nas populações passadas e na atual.

Verificar se filho = pai (e.g. checar se crossover e mutação foi aplicado).

Manter a população com cromossomos distintos.
Funções Objetivo
de Alto Custo (3/3)
Simplificar a função objetivo (pelo menos nas gerações iniciais)
 Usar um método de subida de encosta quando o AG já encontrou as
regiões promissoras do espaço de busca (nas gerações finais).

Como os Algoritmos
Genéticos Funcionam
Esquemas
Cadeias formadas por três símbolos: 0, 1, e *
O simbolo * (um curinga) significa 0 ou 1.
Em inglês, o simbolo * é chamado de “don't care”.
Esquemas
 O número esperado de esquemas H
na geração seguinte (sem levar em
conta a destruição causada pelo
crossover e mutação) é dado por:
onde: m 
a
m
b
m é o número de cromossomos da população atual que
contém o esquema H
b é a média das aptidões de toda população
a é a média das aptidões dos cromossomos que contém o
esquema H
Esquemas
H1 = 1**** está presente em
A1, A2 e A3: m1 = 3
3+2+4
𝑎1 =
=3
3
𝑏=
3 + 2 + 4 + 11
=5
4
𝑚′1 = 3 ×
3
= 1,8
5
É esperado que esquema H1 esteja presente em 1,8 indivíduos
na geração seguinte.
Esquemas
H3 = *0*01 está presente em
A3 e A4.
𝑚′3 = 2 ×
4 + 11
=3
2×5
Na geração seguinte, espera-se ter três indivíduos com H3 na
população.
Conclusões
: (acima da aptidão média) aumenta na geração seguinte.
H
3
H1 (abaixo da aptidão média) diminui na geração seguinte.
Tamanho do Esquema
O tamanho do esquema H , denotado por (H), é a
diferença entre a última posição ocupada por 1 ou 0 e a
primeira posição ocupada por 1 ou 0.
Exemplos,
H1 = 1****,
H2 = **10*,
H3 = *0*01,
(H1) = 0
(H2) = 1
(H3) = 3
(H) representa o
número de possíveis
pontos de corte que
destroi H.
Ordem do Esquema
A ordem do esquema H , denotado por O(H), é o
número de posições em H que não tem o símbolo *.
Exemplos,
H1 = 1****,
H2 = **10*,
H3 = *0*01,
O(H1) = 1
O(H2) = 2
O(H3) = 3
O(H) representa o número
de posições em que a
mutação pode destruir H.
O Efeito Destrutivo do Crossover
Um grande esquema em pai1
(01*|**10)
Um pequeno esquema em pai2
(***|*101)
filho
(01*|*101)
O primeiro esquema está presente filho, mas o segundo
esquema foi destruído pelo crossover.
Conclusão: pequenos esquemas possuem maior
probabilidade de sobrevivência.
O Efeito Destrutivo da Mutação
Esquemas de baixa ordem possuem maior probabilidade de
sobrevivência ao operador de mutação.
Teorema dos Esquemas (Holland)

Mesmo considerando os efeitos destrutivos do crossover e mutação,
este teorema afirma que:
Esquemas pequenos e de baixa ordem contidos
em bons cromossomos aumentam
exponencialmente nas gerações seguintes, ao
passo que esquemas contidos em cromossomos
ruins tendem a desaparecer nas gerações
seguintes.
A Hipótese dos
Blocos de Construção

Blocos de construção são os esquemas pequenos e de baixa ordem.

A hipótese: bons blocos de construção são passados de uma geração
para outra e recombinados para formar cromossomos cada vez
melhores.
Paralelismo implícito

AG manipula uma população de apenas N cadeias de bits, mas processa
em paralelo grande número de esquemas (na ordem de O(N3)
esquemas).
Problemas Deceptivos

Não obedecem a Hipótese dos Blocos de Construção.

Genes com alta epitasia.

São difíceis para os Algoritmos Genéticos resolver (e para outras
técnicas de otimização também).

São raros em problemas do mundo real.