Skip to content
Voltar aos resultados

Busca Tabu Estocástica — Metaheurística Randomizada com Memória

Proposto por
Glover, F. (base TS); stochastic extensions by various authors (1990s–2000s)
Ano
1990s
Tipo
Stochastic metaheuristic optimizer
Família
Simulation / optimization

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?

A Busca Tabu Estocástica (BTE) é uma extensão da Busca Tabu clássica que introduz aleatoriedade nas fases de exploração de vizinhança e seleção de movimentos.

Ao combinar memória tabu — que proíbe soluções visitadas recentemente — com aceitação probabilística ou amostragem aleatória de candidatos, a BTE escapa de ótimos locais de forma mais eficaz e explora paisagens de solução acidentadas que a BT determinística pode falhar em atravessar.

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

A Busca Tabu Clássica navega um espaço de solução movendo-se sempre para o melhor vizinho permitido, usando uma memória de curto prazo (a lista tabu) para evitar ciclagem. Na prática, no entanto, o melhor movimento permitido ainda pode prender o algoritmo em uma região da paisagem. A Busca Tabu Estocástica injeta aleatoriedade controlada: o próximo movimento é escolhido probabilisticamente a partir de um conjunto de vizinhos candidatos em vez de gananciosamente, e perturbações aleatórias são ocasionalmente introduzidas para diversificar a busca. Isso preserva a disciplina guiada por memória da BT, enquanto adiciona o poder exploratório que a descida determinística pura carece.

História

A Busca Tabu foi formalmente introduzida por Fred Glover em 1986 e elaborada em artigos marco entre 1989-1990. Extensões estocásticas surgiram nos anos 1990 à medida que pesquisadores reconheceram que a avaliação determinística da vizinhança era um gargalo em problemas de larga escala. Amostragem aleatória de candidatos, aceitação probabilística de movimentos e injeção de ruído foram incorporadas para melhorar a diversificação, dando origem ao que é amplamente chamado de Busca Tabu Estocástica. A técnica é amplamente aplicada em pesquisa operacional, projeto de engenharia e otimização de hiperparâmetros de aprendizado de máquina.

Quando usar

Usar Busca Tabu Estocástica ao resolver problemas de otimização combinatória ou contínua de caixa preta com paisagens acidentadas e multimodais onde a busca local determinística fica consistentemente presa (por exemplo, escalonamento, roteamento, seleção de características). É especialmente valiosa quando a avaliação completa da vizinhança é computacionalmente cara, tornando a subamostragem aleatória necessária. NÃO usar BTE quando o problema é convexo ou unimodal — métodos baseados em gradiente ou exatos são mais rápidos e ótimos. Evitá-la quando se necessita de otimalidade global garantida, pois a BTE não oferece garantia de convergência além de soluções heurísticas de melhor achado. Evitar também quando a função objetivo é barata de avaliar completamente e uma BT determinística com busca exaustiva de vizinhos é factível.

Limitações e considerações

  • Não há garantia teórica de encontrar o ótimo global; a qualidade da solução depende fortemente das configurações de parâmetros.
  • A tenência tabu e o tamanho da lista de candidatos requerem ajuste específico do problema; escolhas ruins levam à convergência prematura ou progresso lento.
  • Execuções estocásticas não são reprodutíveis sem uma semente aleatória fixa, complicando benchmarking e auditoria.
  • O overhead de memória cresce com o tamanho da lista tabu; representações tabu baseadas em atributos são necessárias para grandes espaços de solução.

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 de forma mais eficaz do que a Busca Tabu determinística, combinando memória com exploração probabilística.
  • Escala para estruturas de vizinhança grandes por meio de subamostragem de candidatos, reduzindo o custo computacional por iteração.
  • A memória tabu previne ciclagem, um modo de falha comum de métodos puramente estocásticos como o hill climbing de reinício aleatório.
  • Framework flexível: a probabilidade de perturbação e a tenência tabu podem ser ajustadas para balancear intensificação e diversificação.
  • Aplicável a problemas combinatórios (TSP, escalonamento) e otimização contínua com adaptação menor.

Aplicações

  • Roteamento de veículos e otimização logística sob demanda incerta
  • Escalonamento job-shop e open-shop com tempos de processamento estocásticos
  • Seleção de características em conjuntos de dados de aprendizado de máquina de alta dimensionalidade
  • Projeto de redes e otimização de topologia
  • Otimização de portfólio com restrições combinatórias de seleção de ativos
  • Ajuste de hiperparâmetros para modelos de simulação complexos

Como funciona

Como funciona

1

Gerar uma solução inicial x0 (aleatoriamente ou heuristicamente). Definir a lista tabu T como vazia, definir a tenência tabu tau, o limite de iterações I_max e os parâmetros estocásticos (por exemplo, tamanho da lista de candidatos k, probabilidade de perturbação p_perturb).

2

Em cada iteração, amostrar aleatoriamente um subconjunto N_s da vizinhança completa N(x_atual) em vez de avaliar todos os vizinhos. Isso reduz o custo por iteração e introduz estocasticidade em quais regiões do espaço são exploradas.

3

Selecionar a próxima solução x_próxima de N_s: ou (a) escolher o melhor candidato não-tabu com probabilidade 1-p_perturb, ou (b) com probabilidade p_perturb escolher um candidato não-tabu aleatório para diversificar. Critérios de aspiração podem sobrepor o status tabu se x_próxima melhorar a melhor solução conhecida.

4

Adicionar x_atual (ou o atributo do movimento) à lista tabu T. Remover a entrada mais antiga se |T| > tau. Atualizar a melhor solução incumbente x_melhor se f(x_próxima) < f(x_melhor).

5

Repetir amostragem_de_vizinhança até atualização_tabu até que I_max iterações sejam alcançadas, um valor objetivo alvo seja atingido, ou nenhuma melhoria tenha ocorrido por uma janela de paciência. Retornar x_melhor como a solução final.

Erros comuns

  • Definir a tenência tabu muito curta permite ciclagem apesar da lista tabu; muito longa bloqueia regiões promissoras desnecessariamente.
  • Usar uma lista de candidatos muito pequena (subamostragem agressiva) pode fazer com que a busca perca consistentemente bons vizinhos.
  • Negligenciar critérios de aspiração faz com que o algoritmo rejeite movimentos globalmente melhoradores que por acaso são tabu.
  • Relatar apenas uma única execução sem múltiplos reinícios ou sementes dá uma imagem enganosa da qualidade típica da solução.
  • Confundir Busca Tabu Estocástica com Recozimento Simulado: ambos são estocásticos, mas diferem fundamentalmente — a BTE usa memória explícita, enquanto o RS usa aceitação probabilística baseada em temperatura sem memória.

Perguntas frequentes

Como a Busca Tabu Estocástica difere do Recozimento Simulado?

Ambas são metaheurísticas estocásticas, mas a BTE usa uma memória tabu explícita para proibir movimentos visitados recentemente, prevenindo ciclagem. O RS não tem memória — ele aceita soluções piores com uma probabilidade que diminui ao longo do tempo (esquema de temperatura). A BTE é geralmente mais forte em problemas combinatórios onde revisitar movimentos é um perigo claro.

Quantas iterações (I_max) devo executar?

Não há regra universal. Uma prática comum é executar múltiplos ensaios independentes (por exemplo, 10-30 reinícios) com um orçamento proporcional ao tamanho do problema, e então relatar os melhores e os resultados médios. Para benchmarking, igualar o orçamento total de avaliação de função usado por métodos concorrentes.

A Busca Tabu Estocástica pode lidar com variáveis contínuas?

Sim, mas requer a definição de uma vizinhança contínua (por exemplo, perturbação Gaussiana em torno da solução atual) e um atributo adequado para a lista tabu (por exemplo, uma região ou direção). A maioria da literatura de BTE foca em problemas combinatórios; para espaços contínuos, Evolução Diferencial ou CMA-ES são frequentemente alternativas mais naturais.

Qual é o papel dos critérios de aspiração?

Critérios de aspiração sobrepõem o status tabu de um movimento se aceitá-lo resulta em uma solução melhor do que a melhor encontrada até agora. Sem aspiração, o algoritmo pode rejeitar permanentemente movimentos globalmente melhoradores que por acaso são tabu, limitando severamente a qualidade da solução.

Devo fixar a semente aleatória para reprodutibilidade?

Sim, fixe a semente ao relatar resultados em pesquisa para garantir a reprodutibilidade. Na prática, execute com múltiplas sementes e relate estatísticas (média, melhor, desvio padrão) para dar uma imagem confiável do desempenho do algoritmo na paisagem estocástica.

Métodos relacionados

Fontes

  1. Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.

    Abrir referência DOI
    Copiado.
  2. Hu, J., Fu, M. C., & Marcus, S. I. (2007). A model reference adaptive search method for global optimization. Operations Research, 55(3), 549-568.

    Abrir referência DOI
    Copiado.