Heurísticas e Metaheurísticas 04

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

ENP557 –Heur. e Metaheurísticas
Aula 05 – Buscas em Vizinhança
ESPAÇO DE SOLUÇÕES
 Conjunto de soluções viáveis para o problema
 Discreto e finito
OTIMIZAÇÃO COMBINATÓRIA
𝑓 𝑠∗ = 𝑚𝑖𝑛 𝑓 𝑠 : 𝑠 ∈ 𝑆
𝑜𝑛𝑑𝑒 𝑆 é 𝑜 𝑒𝑠𝑝𝑎ç𝑜 𝑑𝑒 𝑠𝑜𝑙𝑢çõ𝑒𝑠
ALGORITMOS DE BUSCA
 Algoritmos que solucionam problemas de otimização
combinatória através de uma amostragem do espaço
de soluções
EXEMPLOS
 Algoritmos de busca exaustiva
 Backtracking
 Algoritmos de enumeração implícita
 Branch-and-bound
 Metaheurísticas
 Busca em vizinhança
 Busca local, VND, Tabu Search, GRASP, VNS, ILS
 Populacionais
 Algoritmos genéticos e evolucionários
VIZINHANÇA
 Qualquer função 𝑁: 𝑆 → 2𝑛
 Mapeia uma solução 𝑠 ∈ 𝑆 a um conjunto 𝑁 𝑠 ⊆ 𝑆
VIZINHANÇA
 Qualquer função 𝑁: 𝑆 → 2𝑛
 Mapeia uma solução 𝑠 ∈ 𝑆 a um conjunto 𝑁 𝑠 ⊆ 𝑆
VIZINHANÇA
 Introduz uma noção de proximidade entre as soluções 
de S
 Duas soluções em S podem ser vizinhos ou não
ESPAÇO DE BUSCA
 Grafo que conecta as soluções do problema
 Os vértices representam as soluções viáveis
 As arestas representam a relação de vizinhança
ESPAÇO DE BUSCA
 Grafo que conecta as soluções do problema
 Pode ter mais de uma componente conexa
ESPAÇO DE BUSCA
 O espaço de busca é caracterizado por pequenas
modificações na solução corrente, de forma que
quando realizada:
 Gera uma nova solução para o problema
 Mantém a viabilidade para a solução gerada
ESPAÇO DE BUSCA
 Vizinhança N1 para o espaço {0,1}³
ESPAÇO DE BUSCA
 Superfície definida pelo custo das soluções
ESPAÇO DE BUSCA
 Superfície definida pelo custo das soluções
ESPAÇO DE BUSCA
 Superfície definida pelo custo das soluções
ótimo global
ESPAÇO DE BUSCA
 Superfície definida pelo custo das soluções
ótimo global
ESPAÇO DE BUSCA
 Superfície definida pelo custo das soluções
ótimo global ótimo local
ESPAÇO DE BUSCA
ó𝑡𝑖𝑚𝑜 𝑔𝑙𝑜𝑏𝑎𝑙 → 𝑓 𝑠∗ ≤ 𝑓 𝑠 , ∀𝑠 ∈ 𝑆
ESPAÇO DE BUSCA
ó𝑡𝑖𝑚𝑜 𝑔𝑙𝑜𝑏𝑎𝑙 → 𝑓 𝑠∗ ≤ 𝑓 𝑠 , ∀𝑠 ∈ 𝑆
ó𝑡𝑖𝑚𝑜 𝑙𝑜𝑐𝑎𝑙 → 𝑓 𝑠∗ ≤ 𝑓 𝑠 , ∀𝑠 ∈ 𝑁 𝑠∗
FORMAS DE BUSCA
 A forma de explorar o espaço de soluções pode utilizar
de qualquer critério definido ou, inclusive, com a
ausência de critério algum
 Ao definir o modo de operação da busca, deve-se ter
em mente as características do problema, bem como
as características de suas restrições
RANDOM WALK
 Inicio
 Qualquer solução viável
 Iteração
 Mover-se para um vizinho aleatório
 Parada
 Qualquer critério de convergência
 Tempo de execução
 Número de transições
 Quantidade de passos repetidos
BUSCAL LOCAL
 Forma de explorar o espaço de soluções
 Início
 Qualquer solução viável
 Iteração
 Mover-se para um vizinho com custo melhor
 Busca exaustiva na vizinhança
 Parada
 Quando a solução corrente é um ótimo local
CRITÉRIOS DE TRANSIÇÃO
 Primeiro aprimorante
 Mover-se para o primeiro vizinho que gerar uma solução
melhor que a solução corrente
 Melhor aprimorante
 Avalia todos os vizinhos e move-se para o melhor vizinho
encontrado
CRITÉRIOS DE TRANSIÇÃO
𝑓 0,0,0 = 5
𝑓 0,1,0 = 2𝑓 1,0,0 = 4 𝑓 0,0,1 = 5
𝑓 0,1,1 = 1𝑓 0,0,0 = 5 𝑓 1,1,0 = 2 𝑓 0,0,0 = 5 𝑓 1,0,1 = 2
𝑓 1,1,1 = 1 𝑓 0,1,0 = 2𝑓 1,0,0 = 4 𝑓 0,0,1 = 5
𝑓 1,0,1 = 2𝑓 0,1,1 = 1 𝑓 1,1,0 = 2
MELHOR APRIMORANTE
𝑓 0,0,0 = 5
MELHOR APRIMORANTE
𝑓 0,0,0 = 5
𝑓 0,1,0 = 2𝑓 1,0,0 = 4 𝑓 0,0,1 = 5
MELHOR APRIMORANTE
𝑓 0,0,0 = 5
𝑓 0,1,0 = 2𝑓 1,0,0 = 4 𝑓 0,0,1 = 5
𝑓 0,1,1 = 1𝑓 1,1,0 = 2 𝑓 0,0,0 = 5
MELHOR APRIMORANTE
𝑓 0,0,0 = 5
𝑓 0,1,0 = 2𝑓 1,0,0 = 4 𝑓 0,0,1 = 5
𝑓 0,1,1 = 1𝑓 1,1,0 = 2 𝑓 0,0,0 = 5
𝑓 1,1,1 = 1 𝑓 0,1,0 = 2 𝑓 0,0,1 = 5
PRIMEIRO APRIMORANTE
𝑓 0,0,0 = 5
PRIMEIRO APRIMORANTE
𝑓 0,0,0 = 5
𝑓 0,1,0 = 2𝑓 1,0,0 = 4 𝑓 0,0,1 = 5
PRIMEIRO APRIMORANTE
𝑓 0,0,0 = 5
𝑓 0,1,0 = 2𝑓 1,0,0 = 4 𝑓 0,0,1 = 5
𝑓 0,1,1 = 1𝑓 0,0,0 = 5 𝑓 1,1,0 = 2
PRIMEIRO APRIMORANTE
𝑓 0,0,0 = 5
𝑓 0,1,0 = 2𝑓 1,0,0 = 4 𝑓 0,0,1 = 5
𝑓 0,1,1 = 1𝑓 0,0,0 = 5 𝑓 1,1,0 = 2
𝑓 1,1,1 = 1 𝑓 0,1,0 = 2𝑓 1,0,0 = 4
PRIMEIRO APRIMORANTE
𝑓 0,0,0 = 5
𝑓 0,1,0 = 2𝑓 1,0,0 = 4 𝑓 0,0,1 = 5
𝑓 0,1,1 = 1𝑓 0,0,0 = 5 𝑓 1,1,0 = 2
𝑓 1,1,1 = 1 𝑓 0,1,0 = 2𝑓 1,0,0 = 4
𝑓 1,0,1 = 2𝑓 0,1,1 = 1 𝑓 1,1,0 = 2
REGIÃO DE ATRAÇÃO
REGIÃO DE ATRAÇÃO