Skip to content
Voltar aos resultados

Tabu Search — Metaheurística de Busca Local

Proposto por
Fred Glover
Ano
1989
Tipo
Local-search metaheuristic

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

Tabu Search é uma metaheurística de busca local introduzida por Fred Glover em 1989 que utiliza uma lista tabu — uma memória de curto prazo de soluções visitadas recentemente — para prevenir ciclagem e escapar de ótimos locais.

Ao proibir explicitamente movimentos que revertem decisões recentes, o algoritmo explora o espaço de busca de forma mais ampla e, através de estruturas de memória de longo prazo como critérios de aspiração, visa aproximar-se do ótimo global mesmo em problemas combinatórios grandes e complexos.

A intuição por trás do método

Imagine navegar em um terreno montanhoso no escuro, tentando encontrar o pico mais alto. Um simples escalador de busca local sempre sobe e fica preso na colina mais próxima que alcança. Tabu Search carrega um bloco de notas de locais visitados recentemente e se recusa a retornar a eles, mesmo que retroceder pareça tentador. Essa amnésia forçada sobre movimentos recentes tira a busca de becos sem saída e a leva para território inexplorado, permitindo que ela eventualmente descubra um terreno muito mais alto do que uma busca local simples jamais faria.

História

Tabu Search foi introduzido por Fred Glover em um artigo marcante de 1989 no ORSA Journal on Computing, onde foi apresentado como uma estratégia para guiar a busca local explorando a memória de movimentos passados. As ideias fundamentais foram consolidadas e estendidas na monografia de 1997 de Glover e Laguna pela Springer, que estabeleceu a lista tabu canônica de curto prazo, os critérios de aspiração e as estratégias de diversificação e intensificação de longo prazo que permanecem centrais para o método hoje. Desde sua introdução, Tabu Search tem sido amplamente aplicado em pesquisa operacional, escalonamento, logística e design combinatório, e continua sendo uma metaheurística de referência padrão ao lado de simulated annealing e algoritmos genéticos.

Quando usar

Tabu Search é bem adequado para problemas de otimização combinatória e discreta onde o espaço de soluções é muito grande para métodos exatos e a estrutura do problema permite a definição de uma vizinhança significativa. Aplicações típicas incluem problemas de escalonamento, roteamento, alocação e sequenciamento. É particularmente eficaz quando o cenário de busca tem muitos ótimos locais que prendem métodos mais simples. Não requer que a função objetivo seja diferenciável ou contínua. A definição da vizinhança e a tenência tabu devem ser adaptadas cuidadosamente ao problema específico; uma vizinhança mal escolhida ou uma tenência muito curta ou muito longa pode degradar significativamente o desempenho. Pelo menos várias centenas — e idealmente mais de mil — iterações são necessárias para que a busca explore o espaço adequadamente.

Limitações e considerações

  • O desempenho é sensível à definição da vizinhança e à tenência tabu; escolhas ruins podem prender a busca ou fazê-la ciclar apesar do mecanismo tabu.
  • Requer um orçamento mínimo de iterações — tipicamente mais de 1.000 iterações — para explorar a vizinhança suficientemente; com poucas iterações, os resultados não são melhores do que a busca local simples.
  • A lista tabu armazena atributos de movimento em vez de soluções completas, portanto, o critério de aspiração é necessário para evitar bloquear inadvertidamente movimentos genuinamente bons.
  • Ao contrário de solvers exatos, Tabu Search não oferece garantia de otimalidade e a qualidade do resultado pode variar entre execuções se a solução inicial ou a vizinhança for estocástica.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Escapa de ótimos locais através do mecanismo tabu sem exigir informação de gradiente.
  • Aplicável a problemas combinatórios, de tipo misto e até contínuos — não assume normalidade ou qualquer propriedade distribucional.
  • Incorpora memória em múltiplos horizontes temporais (lista tabu de curto prazo, diversificação/intensificação de longo prazo), permitindo uma exploração principiada do espaço de busca.
  • Frequentemente encontra soluções de alta qualidade com orçamentos computacionais relativamente modestos em comparação com métodos exatos em instâncias grandes.

Aplicações

  • Escalonamento job-shop e flow-shop — otimização da sequência de operações para minimizar makespan ou tardiness.
  • Roteamento de veículos — encontrar rotas de entrega eficientes sujeitas a restrições de capacidade e janelas de tempo.
  • Alocação e localização de instalações — atribuir tarefas a recursos ou localizar instalações para minimizar custos.
  • Coloração de grafos, projeto de redes e telecomunicações — resolução de problemas de otimização estrutural discreta.
  • Seleção de características e busca de hiperparâmetros — exploração de espaços de configuração discretos em pipelines de aprendizado de máquina.

Como funciona

Como funciona

1

A busca começa a partir de uma solução candidata inicial, que pode ser construída aleatoriamente ou com uma heurística gulosa. A lista tabu é configurada como uma fila vazia de comprimento fixo, e a melhor solução encontrada até o momento é registrada. A estrutura de vizinhança — a regra que define quais soluções estão a um passo da solução atual — deve ser definida de forma significativa para o problema específico.

2

A partir da solução atual, todos os movimentos na vizinhança definida são gerados e avaliados em relação à função objetivo. Cada movimento corresponde a uma pequena perturbação, como trocar dois elementos em uma sequência ou inverter uma variável binária. A vizinhança deve ser rica o suficiente para permitir uma exploração significativa, mas pequena o suficiente para ser tratável dentro de cada iteração.

3

Cada movimento candidato é testado contra a lista tabu. Se o movimento — ou o atributo que o caracteriza — aparece na lista, ele é classificado como tabu e é proibido, a menos que satisfaça um critério de aspiração: tipicamente, se a solução resultante fosse melhor do que a melhor solução encontrada até o momento, o status tabu é anulado e o movimento é permitido. Esse mecanismo de aspiração confere flexibilidade ao algoritmo sem abandonar sua disciplina anti-ciclagem.

4

Entre todos os movimentos não-tabu (e quaisquer movimentos tabu que passem pelo critério de aspiração), o movimento de melhor desempenho é selecionado e executado, mesmo que piore o valor objetivo. Essa disposição em aceitar deterioração é o que permite ao algoritmo escapar de ótimos locais, que é a característica definidora do Tabu Search em comparação com o simples hill climbing.

5

Após a execução do movimento, a lista tabu é atualizada adicionando a reversão do movimento recém-feito (ou seu atributo caracterizador), e a entrada mais antiga é removida se a lista estiver cheia, mantendo seu comprimento fixo — a tenência tabu. Se a nova solução for melhor do que a melhor solução registrada, a melhor solução é atualizada. Estruturas opcionais de memória de longo prazo podem rastrear a frequência ou a recência das soluções para guiar a diversificação para regiões menos visitadas ou a intensificação em torno de regiões promissoras.

6

O algoritmo continua iterando até que um critério de parada seja atendido: um número máximo de iterações, um valor objetivo alvo ou uma contagem fixa de iterações sem melhoria. A melhor solução encontrada durante toda a busca é retornada como resultado. A escolha de um orçamento de iteração adequado é crítica — poucas iterações impedem a exploração suficiente da vizinhança.

Erros comuns

  • Definir a tenência tabu muito curta permite que a ciclagem ocorra novamente, frustrando o propósito do mecanismo tabu; a tenência deve ser ajustada para o tamanho do problema.
  • Definir a tenência muito longa restringe excessivamente a busca e impede que o algoritmo revisite regiões que podem conter melhorias.
  • Executar menos de aproximadamente 1.000 iterações significa que a busca não explorou o suficiente da vizinhança — se o tempo de computação for limitado, recorra ao simulated annealing, que pode produzir resultados úteis mais rapidamente com menos iterações.
  • Usar uma vizinhança muito estreita (por exemplo, apenas movimentos de troca única em uma estrutura complexa) leva a uma busca superficial; garanta que a vizinhança seja rica o suficiente para conectar todas as regiões promissoras do espaço de soluções.
  • Ignorar o critério de aspiração pode bloquear permanentemente o caminho para o ótimo global se esse movimento por acaso for tabu; sempre implemente pelo menos a substituição padrão da melhor solução.

Perguntas frequentes

Como o Tabu Search difere do simulated annealing?

Ambos os métodos aceitam movimentos de piora para escapar de ótimos locais, mas diferem no mecanismo. Simulated annealing aceita movimentos piores probabilisticamente, guiado por um parâmetro de temperatura de resfriamento. Tabu Search aceita o melhor movimento não-tabu disponível deterministicamente, guiado por memória explícita de movimentos recentes. Tabu Search é geralmente mais eficaz em problemas combinatórios estruturados; simulated annealing pode ser mais fácil de ajustar em problemas com cenários contínuos ou quase contínuos e é preferível quando o orçamento de iterações é pequeno (abaixo de aproximadamente 1.000 iterações).

Qual deve ser o tamanho da lista tabu?

A tenência tabu — o número de iterações que um movimento permanece proibido — é dependente do problema. Um ponto de partida comumente citado é uma tenência proporcional à raiz quadrada do tamanho do problema, mas isso deve ser ajustado empiricamente. Tenência muito curta permite ciclagem; tenência muito longa restringe excessivamente a busca. Estratégias de tenência adaptativas ou aleatórias podem reduzir a sensibilidade a essa escolha.

O Tabu Search garante encontrar o ótimo global?

Não. Tabu Search é uma metaheurística e não oferece garantia de otimalidade. Ele visa encontrar soluções de alta qualidade de forma eficiente, mas o resultado depende da estrutura da vizinhança, tenência, número de iterações e da solução inicial. Para uma garantia de otimalidade, um método exato como programação inteira é necessário, embora métodos exatos possam ser computacionalmente inviáveis para instâncias grandes.

O que é um critério de aspiração e por que ele é necessário?

Um critério de aspiração é uma regra que anula o status tabu de um movimento sob condições especiais. O critério mais comum é: se executar um movimento tabu resultasse em uma solução melhor do que a melhor solução encontrada até o momento, a restrição tabu é removida e o movimento é permitido. Sem essa anulação, o mecanismo tabu poderia bloquear permanentemente o caminho para o ótimo global se esse caminho passasse por um movimento recentemente visitado.

Métodos relacionados

Fontes

  1. Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.

    Abrir referência da publicação
    Copiado.
  2. Glover, F. & Laguna, M. (1997). Tabu Search. Springer.

    ISBN: 9780792349907
    Copiado.