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
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
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).
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.
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.
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).
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
Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.
Abrir referência DOICopiado.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 DOICopiado.