Flashcard FC241303
O que é a Busca Tabu e qual a função da lista tabu e do tenure?
Programação Linear
CESGRANRIO · 2012
O que é a Busca Tabu e qual a função da lista tabu e do tenure?
Mostrar resposta e comentário
Resposta
É um meta‑heurístico que guia uma busca local usando memória.Explicação:
Busca Tabu é um meta‑heurístico que dirige uma busca local para escapar de ótimos locais, mantendo uma lista tabu de movimentos/soluções proibidos por um período (o tenure) para evitar retrocessos imediatos.
O tenure controla por quantas iterações um movimento fica proibido; valores pequenos permitem ciclos, valores grandes restringem a exploração.
Existe um critério de aspiração que permite aceitar um movimento tabu se ele produzir solução melhor que a melhor conhecida. Além disso, usam‑se memórias para intensificação (refinar boas regiões) e diversificação (explorar novas áreas).
Exemplo:
Considere um pequeno TSP com distâncias simétricas: A–B=10, A–C=35, A–D=25, B–C=20, B–D=30, C–D=15. O custo de um tour é \(C=\sum d_{i,i+1}\).
Tour atual: A–C–B–D–A → \(C=35+20+30+25=110\).
Vizinho (movimento) proposto: A–B–C–D–A → \(C=10+20+15+25=70\).
Se o movimento A trocar posições de B e C estiver marcado como tabu por 5 iterações (tenure=5), normalmente não seria permitido; porém, se a melhor solução conhecida tem custo 100, o critério de aspiração permite aceitar o movimento tabu porque 70 < 100, assim escapando do ótimo local e melhorando a solução global.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/236119
Conteúdo do catálogo FC Concursos · Atualizado em