Busca Tabu Robusta — Meta-heurística baseada em Tabu com robustez contra incerteza
- Proposto por
- Glover, F. (Tabu Search); robustness extensions by various authors
- Ano
- 1989 (TS); robust variant ~2000s
- Tipo
- Metaheuristic with robustness mechanism
- 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 Robusta (RTS) estende a meta-heurística clássica de Busca Tabu avaliando soluções candidatas não apenas pelo seu valor objetivo nominal, mas também pelo seu desempenho sob incerteza.
Em vez de buscar a melhor solução para um único cenário, a RTS busca soluções que apresentem bom desempenho em uma variedade de cenários ou realizações, trocando a otimalidade de pico por confiabilidade.
A intuição por trás do método
A Busca Tabu clássica encontra excelentes soluções proibindo movimentos visitados recentemente e guiando a busca através de uma vizinhança. Na prática, no entanto, as entradas do mundo real — custos, demandas, tempos de viagem — variam. Uma solução que parece ótima sob valores assumidos pode ter um desempenho ruim quando a realidade diverge. A Busca Tabu Robusta incorpora um critério de robustez diretamente na função de avaliação: cada solução candidata é avaliada em múltiplos cenários (amostrados ou enumerados), e a busca favorece soluções com desempenho estável e de baixa variância. Isso torna a solução final resiliente a flutuações de parâmetros sem a necessidade de reotimizar após o fato.
História
A Busca Tabu foi introduzida por Fred Glover em 1989–1990 como uma meta-heurística baseada em memória que escapa de ótimos locais proibindo movimentos recentemente revertidos. Extensões robustas surgiram no final dos anos 1990 e 2000, juntamente com o crescente interesse em otimização robusta; pesquisadores incorporaram avaliações baseadas em cenários e de pior caso na avaliação da vizinhança da TS, dando origem à Busca Tabu Robusta como uma ferramenta prática para problemas de engenharia e logística sob incerteza.
Quando usar
Use a Busca Tabu Robusta quando você enfrenta um problema de otimização combinatória ou discreta onde os principais parâmetros de entrada são incertos ou variáveis — problemas de roteamento, agendamento, atribuição ou projeto de rede sob incerteza de demanda ou custo. É particularmente adequada quando o custo de reotimização após a implantação é alto, ou quando as soluções devem ser certificadas como confiáveis antes da implementação. Evite a RTS quando o problema é puramente determinístico (a Busca Tabu clássica é suficiente), quando o conjunto de incerteza é muito grande para ser amostrado de forma tratável sem computação proibitiva, ou quando o problema é suave e convexo (métodos robustos baseados em gradiente serão mais rápidos e confiáveis).
Limitações e considerações
- A avaliação da robustez sobre um grande conjunto de cenários multiplica o custo computacional por |S| por iteração, o que pode ser proibitivo.
- A qualidade da robustez depende fortemente da qualidade do conjunto de cenários; uma cobertura de cenário deficiente pode gerar falsa confiança.
- A "tenure" da lista tabu e o tamanho da vizinhança são hiperparâmetros específicos do problema que exigem ajuste.
- Não garante otimalidade global ou um certificado de qualidade da 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
- Encontra soluções robustas à variabilidade de entrada sem exigir uma verificação de robustez pós-hoc separada.
- Herda o forte desempenho empírico da Busca Tabu em problemas combinatórios difíceis (agendamento, VRP, variantes do TSP).
- Critério de robustez flexível: suporta objetivos minimax, valor esperado, média-variância e baseados em percentil.
- Não requer convexidade ou diferenciabilidade do problema — aplicável a objetivos de caixa preta e discretos.
- O mecanismo tabu impede o aprisionamento em soluções localmente robustas, mas globalmente medíocres.
Aplicações
- Roteamento de veículos robusto sob tempos de viagem ou demandas de clientes estocásticos
- Agendamento de "job-shop" e "flow-shop" com tempos de processamento incertos
- Projeto de rede e planejamento de capacidade sob flutuação de demanda
- Otimização da cadeia de suprimentos com tempos de entrega ou custos de fornecedores incertos
- Atribuição de frequência em telecomunicações sob incerteza de interferência
- Otimização de portfólio com retornos de ativos incertos usando restrições combinatórias
Como funciona
Como funciona
Defina o problema de otimização combinatória ou contínua, identifique os parâmetros incertos (por exemplo, demandas, custos, tempos de processamento) e especifique um conjunto de cenários S representando realizações plausíveis — seja por amostragem de distribuições ou pela construção de um conjunto de incerteza discreto. Defina o objetivo de robustez: minimizar o custo no pior caso, minimizar o custo esperado ou minimizar uma combinação ponderada de média e variância.
Para cada solução candidata x encontrada durante a busca, avalie seu objetivo f(x, s) em cada cenário s em S. Calcule a medida de robustez R(x) — por exemplo, R(x) = max_{s in S} f(x,s) para robustez minimax, ou R(x) = E[f(x,s)] + lambda * Var[f(x,s)] para robustez média-variância. Isso substitui a avaliação nominal única usada na Busca Tabu clássica.
Gere a vizinhança N(x) da solução atual x aplicando todos os movimentos viáveis (trocas, inserções, reversões, etc.). Avalie R(x') para cada vizinho x', excluindo movimentos atualmente na lista tabu, a menos que um critério de aspiração seja atendido. Selecione o vizinho x* com o melhor valor de robustez R(x*).
Mova-se para x* e registre o inverso do movimento aplicado na lista tabu com "tenure" t (tipicamente 5–20 iterações). A lista tabu evita ciclos e encoraja a exploração. Critérios de aspiração — como aceitar um movimento tabu se ele produzir uma solução robusta globalmente melhor — podem anular a restrição tabu.
Atualize a melhor solução robusta conhecida se R(x*) melhorar o melhor atual. Continue iterando até que um critério de parada seja satisfeito: número máximo de iterações, tempo decorrido ou nenhuma melhoria em um número prescrito de passos. Retorne a melhor solução robusta encontrada juntamente com seu perfil de desempenho por cenário.
Erros comuns
- Usar poucos cenários subestima a verdadeira incerteza e produz soluções que parecem robustas, mas falham na prática.
- Confundir Busca Tabu Robusta com Busca Tabu Estocástica: a otimização robusta minimiza a exposição aos piores casos, enquanto a TS estocástica amostra para aproximar um valor esperado — os objetivos e interpretações diferem.
- Aplicar robustez minimax quando o cenário de pior caso tem probabilidade insignificante leva a soluções excessivamente conservadoras com custo desnecessário.
- Ignorar os critérios de aspiração pode fazer com que a busca perca soluções globalmente robustas que por acaso envolvem movimentos tabu.
- Definir a "tenure" tabu muito alta cria restrição excessiva; muito baixa causa ciclos — ambos degradam a qualidade da solução.
Perguntas frequentes
Como a Busca Tabu Robusta difere da Busca Tabu Estocástica?
A Busca Tabu Estocástica tipicamente usa amostragem aleatória dentro do próprio procedimento de busca (por exemplo, aceitação probabilística ou amostragem aleatória de vizinhança) para aproximar valores esperados. A Busca Tabu Robusta otimiza explicitamente um critério de robustez — como o desempenho no pior caso ou média-variância — avaliado sobre um conjunto de incerteza definido. O objetivo na TS robusta é a estabilidade da solução entre cenários, não apenas o desempenho esperado.
Qual deve ser o tamanho do conjunto de cenários S?
Não há uma regra universal. Para conjuntos de incerteza discretos, enumere todos os cenários críveis, se viável. Para distribuições contínuas, 50–500 cenários amostrados frequentemente fornecem cobertura adequada; técnicas de redução de variância, como amostragem de hipercubo latino, podem melhorar a eficiência. A análise de sensibilidade em |S| é aconselhável antes de se comprometer com uma contagem final de cenários.
A Busca Tabu Robusta pode lidar com problemas multi-objetivo?
Sim. Quando combinada com estruturas de Busca Tabu multi-objetivo, a robustez se torna um objetivo adicional ou uma restrição. As frentes de Pareto de (desempenho nominal, robustez) podem ser exploradas, produzindo um conjunto de soluções que equilibram otimalidade e confiabilidade — útil quando as partes interessadas devem escolher entre opções tolerantes ao risco e avessas ao risco.
Qual medida de robustez devo escolher?
Minimax (pior caso) é apropriado quando as falhas são catastróficas e mesmo resultados ruins de baixa probabilidade são inaceitáveis. O valor esperado é adequado para tomadores de decisão neutros ao risco. Média-variância equilibra o desempenho médio e a variabilidade e é comum no projeto de engenharia. Métricas de Valor em Risco (VaR) ou VaR Condicional são usadas em aplicações financeiras e logísticas onde garantias baseadas em percentis são importantes.
A Busca Tabu Robusta é adequada para instâncias muito grandes?
Depende do custo de avaliação do cenário. Se cada avaliação f(x,s) for barata (milissegundos), a robustez em centenas de cenários permanece tratável mesmo para instâncias grandes. Se cada avaliação exigir uma simulação ou uma chamada de "solver" cara, a redução agressiva de cenários ou modelos substitutos se tornam necessários. A avaliação paralela de cenários em "threads" ou máquinas é uma mitigação comum.
Métodos relacionados
Fontes
Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206.
Abrir referência DOICopiado.Dolan, E. D., Lewis, R. M., & Torczon, V. (2003). On the local convergence of pattern search. SIAM Journal on Optimization, 14(2), 567–583.
Abrir referência da publicaçãoCopiado.