Simulated Bifurcation Aprimorada com Tabu para otimização combinatória

Por que buscas mais inteligentes importam

De roteirizar caminhões de entrega a relacionar partículas em um colisor, muitas das tarefas computacionais mais difíceis de hoje se reduzem a um desafio: encontrar a melhor escolha em um número estonteante de possibilidades. Esses chamados problemas combinatórios impulsionam logística, finanças, biologia e engenharia, mas são tão complexos que até supercomputadores podem ter dificuldades. Este artigo apresenta uma nova variação algorítmica, chamada Simulated Bifurcation Aprimorada com Tabu (TESB), que ajuda os computadores a evitar ficar presos em becos sem saída e a alcançar respostas melhores muito mais rápido.

Decisões difíceis em uma paisagem de possibilidades

Pesquisadores frequentemente imaginam problemas combinatórios como uma paisagem acidentada cheia de colinas e vales. Cada ponto nessa paisagem representa uma solução possível, e a altura corresponde à sua “energia” ou custo; vales baixos são boas soluções, e o vale mais profundo é a melhor. Muitas tarefas do mundo real, como dividir uma rede em duas partes bem separadas (o problema Max‑Cut) ou reconstruir trajetórias de partículas em um detector, podem ser traduzidas para essa paisagem de energia usando um modelo matemático conhecido como modelo de Ising. O problema é que essas paisagens têm um número astronômico de vales, de modo que um procedimento de busca pode facilmente se acomodar em um buraco apenas razoável e nunca descobrir que existe um muito mais profundo em outro lugar.

De ideias quânticas à velocidade clássica

Simulated Bifurcation (SB) é uma abordagem relativamente nova, inspirada na física, para explorar essas paisagens acidentadas. Em vez de saltar de uma solução discreta para outra, o SB imagina um sistema de partículas movendo‑se em uma versão contínua da paisagem, regido por equações semelhantes às da mecânica clássica. À medida que um parâmetro de controle é alterado lentamente, o sistema “bifurca” e as posições das partículas tendem a inclinar‑se para vales de baixa energia que codificam boas soluções. O SB já demonstrou desempenho forte em problemas grandes e roda de forma eficiente em processadores gráficos, mas compartilha uma fraqueza com muitos métodos de busca: pode ficar preso em mínimos locais, especialmente em problemas irregulares e densamente conectados, onde algumas regiões da paisagem são muito mais emaranhadas que outras.

Adicionar memória para evitar velhas armadilhas

A ideia central por trás do TESB é dar ao SB uma espécie de memória de curto prazo, inspirada por uma estratégia bem conhecida em otimização chamada busca tabu. Na busca tabu, o algoritmo mantém uma lista de soluções ruins exploradas recentemente e proíbe temporariamente movimentos que retornariam a elas. O TESB traduz esse conceito para a imagem da paisagem de energia. Primeiro, uma fase de “aquecimento” usa o algoritmo SB original para gerar rapidamente muitas soluções aproximadas. Essas correspondem a vales locais onde o sistema tende a ficar preso. Em seguida, o TESB modifica a paisagem adicionando uma penalidade suave ao redor dessas regiões, elevando efetivamente o piso desses vales. Durante a subsequente fase de “verificação”, o sistema evolui novamente nessa paisagem remodelada, agora encorajado a contornar as velhas armadilhas e a buscar vales mais profundos, previamente não explorados.

Manter a busca viva com pequenos empurrões

Um desafio prático é como usar essa memória sem exagerar. Se o TESB penalizasse igualmente e permanentemente todo vale passado, poderia achatar a paisagem a ponto de desaparecer a orientação útil. Para evitar isso, o método toma emprestada outra ideia do aprendizado de máquina moderno: mini‑lotes. A cada passo da fase de verificação, o TESB seleciona aleatoriamente apenas um pequeno subconjunto das soluções subótimas armazenadas para contribuir com a penalidade. Isso mantém a paisagem mudando o suficiente para afastar o sistema de áreas muito percorridas, preservando a estrutura geral e a diversidade na busca. Testes numéricos mostram que essa estratégia permite ao TESB continuar melhorando muito depois que a dinâmica do SB original já estagnou efetivamente.

Testando o método

Os autores avaliaram o TESB em grafos padrão de teste do Max‑Cut e em problemas exigentes da física de altas energias, onde reconstruir as trajetórias de partículas carregadas é ao mesmo tempo vital e computacionalmente intenso. Nos benchmarks de Max‑Cut, o TESB frequentemente alcança cortes ótimos ou quase ótimos com muito mais confiabilidade do que as variantes SB originais. Medido pelo “tempo até a solução” — quanto tempo leva, em média, para obter uma resposta com qualidade alvo — o TESB pode ser até mil vezes mais rápido nos exemplos mais desafiadores. Em tarefas de reconstrução de trajetórias de partículas envolvendo mais de cem mil variáveis, o TESB consistentemente encontra configurações com energia mais baixa (ou seja, melhores ajustes aos dados) enquanto usa menos tempo de computação que os métodos de referência, destacando sua escalabilidade para sistemas reais e muito grandes.

O que isso significa adiante

Em termos simples, o TESB transforma um buscador rápido mas por vezes míope em um explorador mais estratégico que lembra onde esteve e aprende a evitar bairros ruins. Ao remodelar a paisagem de energia em torno de passos em falso do passado em vez de recomeçar do zero, aumenta muito a chance de atingir soluções de alta qualidade em tempo razoável. Essa combinação de dinâmicas inspiradas na física com ideias clássicas de tabu sugere um caminho mais amplo a seguir: muitos motores de otimização não convencionais, sejam clássicos ou inspirados em ideias quânticas, poderiam ganhar um impulso semelhante ao incorporar penalidades inteligentes e conscientes da história. Para aplicações que dependem de resolver quebra‑cabeças combinatórios cada vez maiores e mais difíceis, o TESB oferece uma nova ferramenta promissora para ultrapassar limites de desempenho anteriores.

Citação: Tao, XZ., Zeng, QG., Huang, ZJ. et al. Tabu-Enhanced Simulated Bifurcation for combinatorial optimization. Commun Phys 9, 100 (2026). https://doi.org/10.1038/s42005-026-02538-2

Palavras-chave: otimização combinatória, simulated bifurcation, busca tabu, Max-Cut, reconstrução de trajetórias de partículas