Computação Evolutiva

CAP 254

CAP 254

Otimização Combinatória
Professor: Dr. L.A.N. Lorena
Assunto: Metaheurísticas
Antonio Augusto Chaves

Conteúdo

C01 – Simulated Annealing (20/11/07).
C02 – Busca Tabu (22/11/07).
C03 – Colônia de Formigas (27/11/07).
C04 - GRASP e VNS (29/11/07).
C05 – Metaheurísticas Híbridas – CS (04/12/07).

Material baseado nas notas de aula do Prof. Dr. Marcone Jamilson Freitas Souza (UFOP) http://www.decom.ufop.br/prof/marcone/ Busca Tabu (Tabu Search)

Busca Tabu
• Proposto por Fred Glover
– "Future Paths for Integer Programming and Links to
Artificial Intelligence," Computers and Operations
Research, Vol. 13, No. 5, 533-549, 1986.

• Método de busca local
– explorar o espaço de soluções movendo-se de uma solução para outra que seja seu melhor vizinho.
– estrutura de memória para armazenar as soluções geradas (ou características dessas)
– essas características possibilitam Busca Tabu escapar de ótimos locais

Busca Tabu

Busca Tabu
• 1ª Idéia: Utilizar Heurística de Descida

Busca Tabu
• 1ª Idéia: Utilizar Heurística de Descida

Busca Tabu
• 1ª Idéia: Utilizar Heurística de Descida

Problema: Fica-se preso no primeiro ótimo local

Busca Tabu
• 2ª Idéia: Mover para o Melhor Vizinho

O melhor vizinho pode ser de piora!

Busca Tabu
• 2ª Idéia: Mover para o Melhor Vizinho

Problema: Ciclagem

Busca Tabu
• 3ª Idéia: Criar uma Lista Tabu

TABU

Busca Tabu
• 3ª Idéia: Criar uma Lista Tabu

Problemas com uma Lista Tabu de soluções
• É computacionalmente inviável armazenar todas as soluções geradas! – Idéia: Armazenar apenas as últimas |T| soluções geradas
– Observação: Uma lista com as |T| últimas soluções evita ciclos de até |T| iterações – Problema: Pode ser inviável armazenar |T| soluções e testar se uma solução está ou não na Lista Tabu
– Idéia: Criar uma Lista Tabu de movimentos reversos

• Problema: Uma Lista Tabu de movimentos pode ser muito restritiva (impede o retorno