Métodos Heurísticos
Genéricos:
Meta-heurísticas e Hiper-heurísticas
Igor Ribeiro Sucupira
(Mestrando em Ciência da Computação pelo IME-USP)
Orientador: Prof. Dr. Flávio S. C. da Silva
Meta-heurísticas e hiper-heurísticas

São métodos heurísticos que podem lidar
com qualquer problema de otimização, ou
seja, que não estão atrelados a um
problema específico.
Neste seminário

Meta-heurísticas:
– Definição.
– Tipos.
– Uma meta-heurística clássica.
– Uma meta-heurística recente.

Hiper-heurísticas:
– Definição.
– Exemplos concretos.
Meta-heurísticas
Do sítio www.metaheuristics.net :
“Uma meta-heurística é um conjunto de
conceitos que podem ser utilizados para
definir métodos heurísticos aplicáveis a um
extenso conjunto de problemas.”
Tipos de meta-heurísticas

Uma possível divisão, por Melián et al.
(Universidad de La Laguna - Espanha):
– Meta-heurísticas de busca por entornos: percorrem o
espaço de busca levando em conta, fundamentalmente, a
“vizinhança” da solução em mãos, definida como o conjunto
de soluções que podem ser obtidas a partir da aplicação de
algum operador à solução atual.
– Meta-heurísticas de relaxação: simplificam o problema
(criando um problema relaxado) e utilizam a solução
encontrada como guia para o problema original.
– Meta-heurísticas construtivas: definem de forma
meticulosa o valor de cada componente da solução.
– Meta-heurísticas evolutivas: lidam com uma população
de soluções, que evolui, principalmente, através da
interação entre seus elementos.
Exemplos (busca por entornos)
GLS (Guided Local Search): busca monotônica.
Porém, altera a função objetivo ao encontrar um
ótimo local.
 Simulated Annealing : não monotônica.
Probabilidade de “movimentos ruins” decresce
exponencialmente com o aumento na diferença
de custo.
 Busca Tabu: não monotônica. Classifica como
tabu os componentes de soluções adicionados
ou removidos recentemente.
 Busca Reativa: Busca Tabu com detecção de
ciclos.

Exemplo (construtiva)

GRASP (Greedy Randomized Adaptive
Search Procedure): cada iteração é
composta por uma fase construtiva e uma
fase de busca por entornos. Em cada passo
da fase construtiva:
– Selecionam-se os componentes que causam
melhor efeito se adicionados à solução atual.
– Acrescenta-se um desses elementos
(selecionado aleatoriamente) à solução.
Exemplo (relaxação)
 Relaxação
Lagrangeana: remove
algumas restrições de um problema de
programação linear, atribui um peso
(multiplicador de Lagrange) a cada
uma delas e altera a função objetivo
para penalizar as soluções que seriam
inviáveis no problema original.
Exemplos (evolutivas)




Algoritmos genéticos.
Algoritmos meméticos: algoritmos genéticos que
realizam otimização local.
Estimação de distribuição: verificam a distribuição
dos componentes nas melhores soluções e criam a
geração seguinte aleatoriamente, segundo essa
distribuição.
Busca dispersa e Path relinking : criam caminhos
entre soluções e geram a população seguinte a
partir das soluções que aparecem nesses
caminhos.
Outros exemplos





Meta-heurísticas de decomposição: indicam
como decompor o problema em instâncias e utilizar
as soluções resultantes na construção da solução
para o problema original.
Ant colony optimization : formigas artificiais
percorrem um grafo em que cada aresta representa
um componente de solução.
Otimização extrema: em cada iteração, remove o
pior componente.
Particle swarm optimization.
Iterated local search : tenta realizar uma espécie
de busca por entornos nos ótimos locais.
Exemplos em detalhes

Uma meta-heurística clássica:
– Algoritmo genético.

Uma meta-heurística recente:
– Particle swarm optimization (1995).
Algoritmo genético
É uma meta-heurística evolutiva.
 Cada elemento da população é uma
seqüência de símbolos (“genes”), chamada
cromossomo.
 Exemplo simples: problema da mochila 0-1
com n itens. Cromossomo tem n genes.
Cada i -ésimo gene é um bit, associado ao i
-ésimo item.

Algoritmo genético






Operador de mutação: escolhe aleatoriamente um
gene do cromossomo e o altera (para um valor
aleatório).
Tm Є [0, 1] é a taxa de mutação.
Operador de cruzamento: gera um par de
cromossomos a partir dos genes de outro par.
Tc Є [0, 1] é a taxa de cruzamento.
Função de aptidão: mede a qualidade de um indivíduo.
Exemplo (mochila - i -ésimo item tem valor vi):
f (c)  (i 1 ci.vi)  penalidade
n
Passagem entre gerações


m : tamanho da população.
Partindo de M = {}, repetir m vezes:
– Selecione aleatoriamente um indivíduo da população.
Probabilidades são proporcionais às aptidões.
– Adicionar a M o indivíduo selecionado.

Para formar a próxima população, repita m/2
vezes:
– Selecione um par de indivíduos de M e, com
probabilidade Tc, realize cruzamento em um ponto
aleatório, gerando dois outros indivíduos.
– Adicione os dois indivíduos gerados à nova população.
– Realize mutação nos indivíduos (probabilidade Tm).
Algumas aplicações
Problema da mochila (múltiplo e 0-1).
Problemas de agendamento.
 Problemas de coloração de vértices (ou arestas).
 Terminal assignment problem.
 Problema da soma de subconjunto (subset sum).
 Problema do corte máximo.
 Problema da cobertura por conjuntos (set covering).
 Conjunto independente máximo.
 Problema da cobertura mínima de vértices.
 Codificação e decodificação de códigos de grupo.
 Problema da montagem de fragmentos de DNA
(fragment assembly).


Particle Swarm Optimization
Desenvolvida por James Kennedy (psicólogo) e
Russell Eberhart (engenheiro), com base no
comportamento de pássaros em revoadas,
modelado pelo biólogo Frank Heppner.
 Elementos do algoritmo:

–
–
–
–
–
–
A : população de agentes.
xi : posição do agente ai no espaço de soluções.
f : função de avaliação.
vi : velocidade do agente ai.
V(ai) : conjunto fixo de vizinhos do agente ai.
Todos os agentes estão conectados, direta ou
indiretamente.
Iteração

Para cada agente ai :
vi := ω.vi + η1.rand().(yi - xi) + η2.rand().(zi - xi)
xi := xi + vi

Sendo:
– yi : melhor posição em que ai já esteve.
– zi : melhor posição em que algum vizinho de
ai já esteve.
Aplicações de PSO

Aplicações bem-sucedidas mais comuns:
– Evolução de redes neurais artificiais.
– Extração de regras de RNAs.


Aplicação recente:
– Bandwidth Minimization Problem (2003).
Algumas aplicações pontuais recentes (2004):
– Caminho ótimo para operações de perfuração
automatizadas.
– Mineração de dados para tarefas de classificação.
– Posicionamento de bases em computação móvel.
– Aproximação poligonal ótima de curvas digitais.
Motivação para as hiper-heurísticas
Implementações de meta-heurísticas podem ser
algoritmos extremamente poderosos. Porém,
normalmente isso exige alterações substanciais
para cada novo problema a ser tratado.
 O objetivo das hiper-heurísticas é resolver esse
conflito entre facilidade de implementação e
qualidade. Portanto, a idéia não é
necessariamente superar a qualidade das outras
técnicas.

Conceito de hiper-heurística
O termo hiper-heurística (2000) se refere aos
algoritmos heurísticos que operam em um alto
nível de generalidade. O domínio de uma hiperheurística é composto por conjuntos de
heurísticas (e não pelo conjunto das instâncias
de um problema de otimização).
 Uma hiper-heurística encontra soluções
indiretamente, utilizando de maneira inteligente
as heurísticas que lhe foram fornecidas.

Ross et al.
(Napier /
Nottingham) 2003
Vantagens
Simplicidade: para adaptar uma hiper-heurística
a um novo problema, basta alterar o conjunto
de heurísticas simples de baixo nível.
 Vantagens potenciais:

– Robustez: uma hiper-heurística é um algoritmo bem
definido que, idealmente, apresenta eficiência e
eficácia no tratamento de diversos problemas de
otimização, pois sua “inteligência” está implementada
em um nível independente do domínio do problema.
– Os erros de decisão praticados por cada uma das
heurísticas pouco elaboradas são suprimidos em um
processo de intercalação. A hiper-heurística é,
portanto, insensível a essas falhas.
Um exemplo concreto
Hiper-heurística desenvolvida em 2002, por
Cowling et al. (Bradford / Nottingham).
 A hiper-heurística é um algoritmo genético:

– Cada cromossomo é uma seqüência de inteiros no
intervalo [0, nh - 1], sendo nh o número de
heurísticas de baixo nível.
– A população inicial é criada com números aleatórios.
Tamanho da população: 30.
Número de gerações: 200. Porém, 100
gerações fornecem resultados semelhantes.
 Elitismo: população com os 30 melhores entre
a população atual e a população gerada.


Versões da hiper-heurística

Oito versões:
– Quatro com tamanho fixo de cromossomo.
– Quatro com tamanho adaptativo de cromossomo.
Taxas fixas e função de aptidão simples.
2. Taxas adaptativas e função de aptidão simples.
3. Taxas fixas e função de aptidão com tempo de
CPU.
4. Taxas adaptativas e função de aptidão com
tempo de CPU.
1.
Características das versões

Versões com taxas fixas:
– Taxa de cruzamento: 0,6.
– Taxa de mutação: 0,1.
Taxas adaptativas: Tm se eleva (e Tc diminui) quando
não há aumento na aptidão média por três gerações
seguidas. O inverso ocorre quando há aumento de
aptidão por três gerações. Aumento de uma taxa T := (T
+ 1) / 2. Diminuição: divisão por 2.
 Função de aptidão simples: valor objetivo resultante da
aplicação do cromossomo à melhor solução já
encontrada em todo o processo.
 Função de aptidão com tempo de CPU: o valor acima é
dividido pelo tempo de CPU tomado na aplicação do
cromossomo.

Número variável de genes

Operadores adicionais, que lidam com
subseqüências de genes:
– Um operador de cruzamento permuta a melhor
seqüência de um cromossomo com a melhor
seqüência do outro.
– Um operador de mutação remove a pior seqüência do
cromossomo.
– Outro operador de mutação insere no cromossomo a
melhor seqüência de um outro cromossomo
(selecionado aleatoriamente).

Cromossomos muito grandes são penalizados
pela função de aptidão.
Aplicação






Problema: agendamento de cursos.
D : conjunto de docentes.
L : centros de treinamento (localidades), cada um com
um certo número de salas.
P : matriz de penalidades (D x L).
n : número de vagas na grade horária.
C : conjunto de cursos. A cada curso c estão associados:
–
–
–
–
–
Um conjunto de docentes competentes para ministrá-lo.
Um intervalo dentro do qual c deve se iniciar.
Um conjunto de localidades.
Uma duração (entre 1 e 5 vagas da grade horária).
Um valor que indica a sua prioridade (importância).
Agendamento de cursos

Objetivo: maximizar W - D, sendo:
– W : soma das prioridades dos cursos
realizados.
– D : soma das penalidades aplicadas.

Restrições adicionais:
– Nenhum docente pode ministrar dois cursos
simultaneamente.
– Nenhum docente pode trabalhar em mais de
60% das vagas de horários.
Heurísticas de baixo nível
Tipo 1 (5 heurísticas): escolhem um curso e
tentam agendá-lo.
 Tipo 2 (4 heurísticas): idem, mas, na presença
de conflitos, tentam trocar os dados entre o
curso escolhido e outro curso já agendado. Pode
ser exaustivo.
 Tipo 3 (3 heurísticas): agendam o curso de
maior prioridade que melhore a solução mesmo
após a remoção dos cursos conflitantes.

Experimentos
Para efeito de comparação, também foram
desenvolvidas duas meta-heurísticas,
implementadas de forma não trivial: um
algoritmo genético e um algoritmo memético.
 As heurísticas de baixo nível da hiper-heurística
foram utilizadas como operadores para o
algoritmo memético.
 Heurísticas H1, ..., H5 : cinco execuções da hiperheurística mais simples em uma instância
complexa.

Experimentos
Todas as instâncias têm 25 professores, 10
localidades e 60 vagas de horários. São
baseadas em um caso real ocorrido em uma
instituição financeira de grande porte.
 Defeito: poucas instâncias (5).
 Instâncias diferem na complexidade:

– Número médio de professores associados a cada
curso.
– Número médio de localidades associadas a cada
curso.

Instância mais complexa: para cada curso, 1
localidade e 5 docentes.
Outro exemplo concreto
Hiper-heurística desenvolvida em 2001 por Cowling et al.
(Nottingham).
 Seleciona uma heurística de baixo nível a cada iteração.
 Recebe os componentes da função objetivo, com seus
respectivos pesos.
 f1c(Hi) : desempenho histórico de Hi em relação ao
componente c.
 f2c(Hi, Hk) : desempenho histórico (em relação ao
componente c) de Hi quando executada logo após Hk.
 f3(Hi) : tempo decorrido desde a última execução de Hi.
 αc, βc e δ : pesos dos fatores históricos.

Fatores históricos
 f1
e f2 são critérios de intensificação.
 f3 é um critério de diversificação.
 Intensificação : exploração do espaço de busca
através de componentes e de tipos de
movimentos que, historicamente, levam a
soluções de boa qualidade.
 Diversificação : tentativa de construção de
soluções que pertencem a regiões não
exploradas do espaço de busca e diferem
significativamente das soluções já encontradas.
Iteração da hiper-heurística



Seleciona aleatoriamente um
componente c, com probabilidades
proporcionais aos pesos.
Hk : última heurística executada.
Executar-se-á a heurística Hi que
maximiza o valor:
fc(Hi) = αc∙f1c(Hi) + βc∙f2c(Hi, Hk) + δ∙f3(Hi).
Versões
1.
2.
3.

Pesos fixos para os fatores históricos e função objetivo
atômica.
Pesos adaptativos e função objetivo atômica.
Pesos adaptativos e função objetivo decomposta.
Adaptabilidade:
– Quando a heurística selecionada aumenta a qualidade da
solução, o peso do maior fator de intensificação (max{α, β})
sofre elevação proporcional.
– O mesmo peso é reduzido quando não há ganho de qualidade.
– Quando não há progresso durante b iterações, o fator de
diversificação se eleva (b é o número de heurísticas de baixo
nível).
– Quando há progresso em b iterações seguidas, o fator de
diversificação é reduzido.
Quatro versões simples

1.
2.
3.
4.
Também foram desenvolvidas quatro hiper-heurísticas
simples, semelhantes a meta-heurísticas de busca por
entornos.
SimpleRandom : seleciona uma heurística
aleatoriamente e a aplica à solução corrente.
RandomDescent : seleciona uma heurística
aleatoriamente e a aplica repetidamente até que não
haja ganho de qualidade.
RandomPerm : cria aleatoriamente uma permutação
das heurísticas e a aplica.
RandomPermDescent : semelhante ao método acima,
mas cada heurística é aplicada, repetidamente, até que
não haja ganho de qualidade.
Aplicação a um problema







Problema real: feira comercial.
Companhia promove um evento que envolve fornecedores e
delegados.
Fornecedores indicam os delegados que desejam encontrar,
classificando alguns encontros como prioritários.
Delegados também participam de seminários. Cada delegado indica
os seminários de que gostaria de participar. Todas as participações
são garantidas, para os delegados convidados.
Cada encontro ocupa um horário na grade.
Cada seminário ocupa três horários.
O objetivo é selecionar quais delegados serão convidados e agendar
encontros.
Feira comercial
Um delegado não pode participar de mais de 12
encontros.
 Um delegado não pode participar de duas atividades
(seminário ou encontro) ao mesmo tempo e um
fornecedor não pode participar de dois encontros ao
mesmo tempo.
 Restrições desejáveis (soft constraints):

– Cada fornecedor deve ter ao menos 20 encontros.
– Cada fornecedor deve ter ao menos 17 encontros prioritários.

Função a ser minimizada: E = B + 0,05∙C + 8∙H.
– C : penalidades pela não realização dos 20 encontros.
– B : idem, para os encontros prioritários.
– H = d - 72, onde d é o número de delegados convidados e 72 é
um limite inferior (se cada fornecedor tem 20 encontros).
Resolução
Apenas a versão 3 da hiper-heurística foi
utilizada.
 Solução inicial para a hiper-heurística: resultado
de um algoritmo guloso desenvolvido pelos
autores.
 Componentes da função objetivo: (1, B), (0,05,
C), (8, H).
 10 heurísticas de baixo nível, que adicionam
e/ou removem encontros ou delegados.

Experimentos

Deixam a desejar:
– Não comparam as hiper-heurísticas com
outros métodos.
– A instância é um caso real, mas foi a única
utilizada. Dados:
 43
 99
 12
 24
fornecedores.
potenciais delegados.
seminários.
horários disponíveis.
Resultados
Outro problema
Problema real: agendamento de
apresentações de projetos em um
curso de graduação.
 Apenas uma instância.
 As três versões da hiper-heurística foram
utilizadas.
 8 heurísticas de baixo nível.

Principais referências (metaheurísticas)
MELIÁN, B. et al. Metaheuristics: A Global View. In
Revista Iberoamericana de Inteligencia Artificial.
Asociación Española de Inteligencia Artificial, 2003. v. 2,
n. 19.
2. REEVES, C. R. Genetic Algorithms. In GLOVER, F.,
KOCHENBERGER, G. Handbook of Metaheuristics.
Kluwer, 2003. Cap. 3.
3. POMEROY, P. An Introduction to Particle Swarm
Optimization. 2003.
(http://www.adaptiveview.com/articles/ipsop1.html)
4. Metaheuristics Network.
(http://www.metaheuristics.net)
1.
Principais referências (hiperheurísticas)
1.
2.
3.
ROSS, P. et al. Hyper-heuristics: An Emerging Direction
in Modern Search Technology. In Handbook of
Metaheuristics. Kluwer, 2003.
COWLING, P. et al. An Adaptive Length Chromosome
Hyperheuristic Genetic Algorithm for a Trainer
Scheduling Problem. Submitted to SEAL 2002
Conference). University of Nottingham.
COWLING, P. et al. Hyperheuristics: A Tool for Rapid
Prototyping in Scheduling and Optimization. In LNCS
2279, Applications of Evolutionary Computing:
Proceedings of Evo Workshops 2002.
Mais referências na minha monografia:
http://www.ime.usp.br/~igorrs/monografias/metahiper.pdf
Meta-referência:
http://www.ime.usp.br/~igorrs/seminarios/metahiper.ppt