Avalie os vizinhos, inclusive os que pioram.
METAHEURÍSTICAS CLÁSSICAS · SUBTÓPICO 03
Não volte ao mesmo lugar só porque ele parece familiar.
A Busca Tabu permite movimentos que não melhoram a solução atual, mas registra os retornos recentes em uma memória curta. Assim, ela atravessa platôs e escapa de ciclos previsíveis.
solução atual
A→B→C→B
movimento B ↔ C bloqueadoa memória evita desfazer a última decisão01 · MEMÓRIA DE CURTO PRAZO
O movimento é proibido por um tempo, não para sempre.
Ignore movimentos presentes na lista tabu.
Escolha o melhor candidato permitido.
Insira o movimento e reduza sua validade.
02 · EXCEÇÃO IMPORTANTE
A aspiração quebra a regra quando a oportunidade é realmente melhor.
Se o movimento reaparece cedo, a memória preserva uma trajetória diferente.
tabu(m) = verdadeiroUma solução tabu pode entrar se superar a melhor solução encontrada em toda a execução.
f(x′) < f(melhor)Tenure curto favorece retorno; longo diversifica, mas pode bloquear bons movimentos.
t = 3 … 10 iterações03 · LABORATÓRIO INTERATIVO
Troque cidades, bloqueie retornos e melhore a rota.
O experimento minimiza a distância de uma rota por seis cidades. Cada passo avalia todas as trocas possíveis e escolhe a melhor que não esteja tabu.
Rota atual
O traço violeta representa a solução visitada.
Histórico de custo
O melhor global permanece guardado mesmo que a rota atual piore.
04 · AJUSTE E USO
Memória é uma forma controlada de explorar.
Troca, inserção e inversão determinam o que a busca consegue alcançar.
Escolha uma duração proporcional ao tamanho do problema e ajuste por testes.
Use o recorde global como uma exceção segura à proibição.
Defina orçamento, número de iterações ou estagnação máxima.
05 · NO CÓDIGO
O melhor vizinho permitido conduz o próximo passo.
for (const movimento of vizinhos(atual)) {
const aspirado = custo(movimento) < custo(melhor);
if (!listaTabu.tem(movimento) || aspirado) candidato = melhor(candidato, movimento);
}
atual = candidato;
listaTabu.adicionar(movimento, tenure);Avaliar
Veja toda a vizinhança.
Filtrar
Aplique tabu e aspiração.
Mover
Aceite o melhor permitido.
Atualizar
Envelheça a memória.
PRÓXIMO SUBTÓPICO
GRASP e VNS.
Duas estratégias que alternam construção gulosa, busca local e perturbações de vizinhança.
Continuar estudo →