Algoritmos Evolucionários
Híbridos (Meméticos)
Caio Fleming Ferreira de Carvalho Cunha
Fellipe de Oliveira Pinto
16 de Maio de 2012
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
1
Ementa
 Objetivos
 Motivações para hibridização dos AEs.
 Introdução aos algoritmos meméticos.
 Busca local:
– Adaptação de Lamarck vs. de Baldwin.
 Estrutura de um algoritmo memético.
 Problemas de design para algoritmos meméticos:
– Diversidade, escolha de operadores e uso de
conhecimento.
 Exemplo de aplicação:
– Problema Timetabling
 Referências bibliográficas.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
2
Objetivos
 Discutir algoritmos baseados em AE, os quais são
incorporados a outros métodos ou estruturas de
dados incorporados a eles, denominados Algoritmos
Meméticos (MA);
 Explicitar o raciocínio por trás dos MAs;
 Mostrar as possíveis combinações dos AEs com
outras técnicas;
 Fornecer os pontos para projetar adequadamente
um Algoritmo Hibrido;
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
3
Motivações para Hibridização de AEs
 Problemas complexos podem ser decompostos em sub-
problemas, os quais podem ser resolvidos com métodos
apropriados para cada um deles;
 Na verdade o AE puro não exibe uma performance uniforme para
uma ampla faixa de problemas.
Pode-se combinar heurísticas específicas a um AE formando
modelos híbridos, alterando a performance global do método;
 Pode-se
obter melhores resultados
conhecimentos específicos do problema.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
quando
se
possui
4
Performance do método
Motivações para Hibridização de AEs
Métodos adaptados
EA puro
EA enriquecido com conhecimento
Faixa de problemas
 O conhecimento específico no algoritmo híbrido é variável,
podendo ser ajustada;
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
5
Motivações para Hibridização de EAs
 AEs não são bons em encontrar a solução final, pois evoluem
lentamente devido a natureza estocástica dos operadores.
 Pode-se melhorar o algoritmo incorporando um passo de busca
local.
 A combinação de AEs com operadores de busca local que atuam
dentro do laço AE ou entregam conhecimento específico de
instâncias do problemas é denominado Algoritmo Memético;
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
6
Algoritmos Meméticos
Memes
Unidades de transmissão cultural
Genes
Unidades de transmissão biológica
 Ideia de meme como agente que pode transformar um candidato a
solução.
 A adição de uma fase de aprendizagem (desenvolvimento) ao ciclo
evolucionário pode ser vista como uma interação meme-gene.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
7
Busca Local
 Busca local é um processo iterativo para examinar o
conjunto de pontos na vizinhança da solução atual e a
substituir por um vizinho melhor, caso exista.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
8
Busca Local
 Componentes que afetam o algoritmo:
Regra de pivoteamento (laço interno) :
steepest ascent – busca entre todos os vizinhos o mais apto,
contar = n(i);
greedy ascent – busca o primeiro vizinho que se mostra
rápido, (contar = |n(i)|) ou (melhor!= i);
mais
Regra de profundidade (laço externo):
determina número de iterações da busca local;
Pode ser aplicado a uma única iteração (iterações = 1) ou contínua
(contar = |n(i)| e melhor =i) ;
Efeitos na performance do algoritmo, tempo e qualidade;
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
9
Busca Local
Função geradora de vizinhança:
n(i) - conjunto de pontos que podem ser alcançados
através da aplicação de algum operador de movimento ao
ponto i.
Representação equivalente: Grafo não direcionado G(v,e)
– v é o conjunto de vértices que representa todos pontos no
espaço de busca, as soluções em potencial.
– e é o conjunto de arestas que representa as possíveis
transições que podem ocorrer a partir da aplicação de um
único operador. As arestas podem ser direcionadas e
ponderadas.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
10
Busca Local
Definida pela combinação de vizinhança, n(x), e regra de
pivoteamento. Em que n(x) constitui o conjunto de
pontos alcançáveis com aplicação do operador de
movimento (fitness landscapes), os quais afetam a
eficiência e efetividade da busca local.
v = {a, b , c, d, e, f, g, h}
h
e
a
d
f
g
n(g) = {c, f, h}
e1 = {ab, ad, ae, bc, bf, cd, cg, dh,
fg, fe, gh, eh}
simétrica e valores equiprováveis
c
b
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
11
Busca Local
 Pontos localmente ótimos para uma estrutura de vizinhança
podem não ser para outra, exceto se localmente ótimo.
 Variações:
Pode-se aplicar a busca ao espaço de busca ou espaço de
soluções;
Ajustando o número de iterações a serem realizadas pela
busca local;
Busca local pode ser aplicada:
- a população total;
- para o indivíduo mais apto;
- para o indivíduo menos apto;
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
12
Lamarckianismo e Efeito Baldwin
 Lamarckiano se as características adquiridas durante seu
tempo de vida são herdadas por sua prole.
ex: substituir o indivíduo com vizinho mais apto.
 Baldwiniano se o processo evolucionário for guiado pelas
adaptações favoráveis sem que as modificações nas
aptidões dos indivíduos, devido a aprendizagem ou
desenvolvimento, se convertam em mudanças de
características genéticas.
ex: indivíduo recebe aptidão (mas não genótipo) do
vizinho mais apto.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
13
Estrutura de um Algoritmo Memético
POP. INICIAL
-Soluções conhecidas
-Heurística
-Inicialização Seletiva
-Busca Local
GRUPO DE
REPRODUÇÃO
Cruzamento
Seleção
Seleção modificada
de operadores
DESCENDENTE
Mutação
DESCENDENTE
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
Uso de informações de
um problema específico
No operador
Busca Local
Uso de informações de
um problema específico
No operador
Busca Local
14
Estrutura de um Algoritmo Memético
Inicialização Heurística ou Inteligente
 Um conhecimento existente pode ser incorporado ao AE na fase
de inicialização.
 benefícios por iniciar AEs com soluções existentes:
– Evitar a perda de esforço computacional refletindo aumento de
eficiência (velocidade);
– Direcionar busca para regiões promissoras do espaço de busca
levando a aumentar efetividade;
– Dividir o esforço computacional entre inicialização heurística e
busca evolucionária pode gerar melhores resultados do que
gastar todo o esforço em busca evolucionária apenas;
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
15
Estrutura de um Algoritmo Memético
Inicialização Heurística ou Inteligente
 Maneiras de se alterar a função inicialização:
Seeding (Semeadura): semeia a população com uma ou mais
soluções boas a partir de outras técnicas (tentativa e erro,
heurísticas usando informações de instância específica);
Inicialização seletiva: gera-se grande número de soluções
aleatórias e seleciona-se a população inicial a partir delas:
- Realizar N torneios de tamanho k;
- Selecionar um conjunto baseado na força e diversidade.
Realizar busca local em cada membro da população
(aleatoriamente), formando um conjunto de indivíduos
localmente ótimos.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
16
Estrutura de um Algoritmo Memético
Inicialização Heurística ou Inteligente
 Maneiras de se alterar a função inicialização:
Empregar um ou mais métodos anteriores para identificar uma ou
mais boas soluções, e então clonar e aplicar mutação com altas
taxas (mass mutation) para formar um número de indivíduos na
vizinhança do ponto inicial.
 Efeito de se variar a proporção da população inicial :
-Uso de pequena proporções das soluções na população inicial
auxilia na busca genética;
-Performance média melhora com o aumento da proporção;
-Melhor performance vem de uma população inicial mais aleatória.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
17
Estrutura de um Algoritmo Memético
Hibridização com Operadores de Variação
 Operadores
inteligentes de variação incorporam
conhecimento específico da instância ou do problema, uma
forma de introduzir tendência dentro dos operadores:
Exemplo 1: Aumentar a probabilidade de escolha de
características mais compactas para emprego em um
classificador.
Exemplo 2: Genes codificando instruções de
microprocessador de modo a serem agrupados em
conjuntos de efeitos similares.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
18
Estrutura de um Algoritmo Memético
Hibridização com Operadores de Variação
 Uso de conhecimento específico do problema:
Incorporação de uma fase de busca local dentro de um
operador de recombinação.
Ex.: Testar todas as possíveis orientações dos dois
fragmentos de estrutura de uma proteína “separados” pelo
ponto de cruzamento e pegar a mais favorável. Se nenhum
ajuste possível for encontrado é escolhido outro ponto de
cruzamento.
 Uso de conhecimento específico da instância:
Operadores recebem heurística muito específica.
Ex.: Operador DPX para TSP, preserva a diversidade
evitando convergência prematura.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
19
Estrutura de um Algoritmo Memético
Busca Local na Saída de Operadores de Variação
 Consiste de uma ou mais fases de melhora no indivíduo da
população durante o ciclo AE;
 A busca Local atua sobre toda solução criada pela mutação
ou recombinação, pode ocorrer em fases distintas do ciclo;
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
20
Estrutura de um Algoritmo Memético
Busca Local na Saída de Operadores de Variação
 Krasnogor – para reduzir o pior caso de execução, é
preciso escolher uma busca local em que o operador
movimento é diferente
dos operadores da
recombinação e mutação.
Implica em diversificação dos pontos gerados, a qual é
melhorada com altas taxas de mutação ou uso de
operadores com estruturas de vizinhança distintas
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
21
Estrutura de um Algoritmo Memético
Hibridização no Mapeamento genótipo - fenótipo
 Usado no mapeamento antes da avaliação da aptidão;
Ex: Uso de conhecimento específico da instância
dentro do decodificador ou da função de reparo.
Problema da mochila.
Uma linha comum destas aproximações é fazer uso de
heurísticas existentes e informações do domínio onde
possível.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
22
Problemas de Projetos em Algoritmos
Meméticos
 AMs não são “soluções mágicas” para problemas de
otimização.
 Deve-se tomar cuidado com:
–Diversidade da população.
–Escolha dos operadores.
–Uso do conhecimento adquirido durante o
processo de otimização.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
23
Preservação de Diversidade
 O problema da convergência prematura.
 Técnicas para combater este problema:
- Usar somente uma proporção pequena de boas soluções
conhecidas na população inicial.
- Usar operadores de recombinação que são projetados
para preservar diversidade (como Merz’s DPX).
- Modificar operador de seleção para prevenir duplicações.
- Usar um método de Boltzmann (Simulated anneling) para
o operador de seleção ou o critério de aceitação da busca
local.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
24
Preservação de Diversidade
 Manutenção
do sucesso de diversidade para
população pode ser justificado:
O cruzamento DPX de Merz explicitamente gera
indivíduos que são eqüidistantes para cada pai, tendo
a mesma distância entre os pais.
Operador adaptativo de Boltzmann, por Krasnogor,
usa critério de aceitação de novo indivíduo baseado no
cozimento simulado. A temperatura é inversamente
proporcional à diversidade da população.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
25
Critério de Boltzmann
A dinâmica induzida é tal que:
População é diversa - espalhamento da aptidão é alto,
portanto temperatura é baixa, então aceita apenas de
movimentos melhores em relação à aptidão (Explotação).
População é pouco dispersa, portanto, temperaturas
altas, mais provável a aceitação de movimentos que
pioram a aptidão (Exploração).
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
26
Escolha dos operadores
 O fator Principal no projeto de um AM é:
- Escolha da heurística de melhoramento ou do
operador de movimento da busca local.
- A escolha do operador de movimento pode ter efeito
dramático na eficiência e na efetividade da busca local.
- Vantagens em usar busca local com um operador de
movimento que é diferente dos operadores de
movimento usados pela mutação e pelo cruzamento.
- Podem-se disponibilizar múltiplos operadores de
busca local, escolhendo-se qual a ser aplicado em cada
caso.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
27
Uso do Conhecimento
 AM concentram o uso e o reuso de conhecimento
ganho durante o processo de otimização (automático
ou não)
 Tabu search – Lista de Pontos visitados é mantido para
proibir que o Algoritmo retorne a estes (mantém a
diversidade).
 A seleção/aceitação de Boltzmann utiliza o
espalhamento do genótipo da população atual ou
passada, para decisão de aceitação de novas
indivíduos.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
28
Resumo sobre Algoritmos Híbrido
 São utilizados em diversos problemas ;
 Pode envolver operadores de outros algoritmos ou
incorporar um domínio específico do conhecimento do
problema.
 AMs têm se mostrado mais rápidos e mais precisos do
que os AGs sobre alguns problemas
 Deve-se controlar a escolha dos operadores e cuidar da
preservação da diversidade com o objetivo de fugir de
ótimos locais.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
29
Exemplo:
Problema “Timetabling”
 Atribuição de horários e salas para cursos para restrições:
Hard:
- Estudantes não podem ser atribuídos a mais de um curso ao
mesmo tempo;
- A sala deve satisfazer características requeridas pelo curso;
- O número de estudantes ≤ a capacidade da sala;
- Não mais do que um curso é atribuído a um horário por sala;
Soft:
- Um estudante tenha um curso no último horário;
- Um estudante tem mais do que 2 cursos consecutivos;
- Um estudante tem um único curso em um dia;
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
30
Problema “Timetabling”
 O problema possui:
-Um conjunto de N cursos;
-45 horários
-Um conjunto de R salas;
-Um conjunto de F sala a
-Um conjunto de M estudantes;
 O objetivo do problema é satisfazer a restrição hard e
minimizar a violação das restrições soft.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
31
Problema “Timetabling”
 A técnica usada é um operador de mutação leve (light) por um
algoritmo de melhora interativa aleatória.
Representação: direta, cada gene contém informação sobre
horário e sala para um curso particular (ci), i {1,..,N).
População inicial: usa um algoritmo de construção que gera
timetables aleatórios, 100 indivíduos.
Seleção de indivíduos para nova população: Roulette Wheel.
Mutação: aleatória sobre 20% dos cursos de 20% dos indivíduos
selecionados.
Busca Aleatória: Randomised Iterative Improvement Algorithm,
sempre aceita uma solução melhor e uma pior com certa
probabilidade (critério de monte carlo
).
Condição de Terminação: Após 200000 rodadas.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
32
Problema “Timetabling”
Algoritmo:
POPULAÇÃO
SELEÇÃO
ROULETTE WHEEL
MUTAÇÃO
GRUPO DE
SELEÇÃO
BUSCA LOCAL:
Ramdomised iterative
improvement
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
33
Referência Bibliografica
 Abdullah, Salwani, Burke, E. K., and McCollum, Barry
“A Hybrid Evolutionary Approach to the University
Course Timetabling Problem”. IEEE Congress on
Evolutionary Computation, pp. 1764 1768 (2007b).
 Burke, E. K., Newall, J. P. “A multi-stage evolutionary
algorithm for the timetable problem”. IEEE
Transactions on Evolutionary Computation, v. 3,
n. 1, p. 63-74, April 1999.
UFRJ – COOPE
16/05/2012
Algoritmos Evolucionários Híbridos
34