Resumo Técnico: HEATACO – Um Sistema de Formiga Máximo-Mínimo Guiado por Mapas de Calor para TSPs em Grande Escala

1. Definição do Problema

O artigo aborda o Problema do Caixeiro Viajante (TSP - Travelling Salesman Problem), focando especificamente na etapa de decodificação de solvers neurais não autorregressivos (NAR). Esses solvers predizem um mapa de calor de confiança de arestas em uma única passagem direta (forward pass), atribuindo pontuações às arestas potenciais. No entanto, um mapa de calor não é um tour válido; ele frequentemente contém ciclos desconectados, viola restrições de grau (nós com mais de duas arestas incidentes) e inclui falsos positivos.

O desafio central é o problema de decodificação de mapa de calor para tour: converter um mapa de calor denso e fixo ($O(n^2)$ pontuações) em um ciclo hamiltoniano viável ($n$ arestas) que satisfaça restrições globais. Os decodificadores existentes enfrentam um compromisso (trade-off):

• Fusão Gananciosa (Greedy Merging): Rápida e determinística, mas produz tours de baixa qualidade porque não consegue revisar escolhas iniciais potencialmente enganosas.
• Busca k-opt guiada por MCTS: Produz tours de maior qualidade, mas é computacionalmente dispendiosa, requer ajuste de hiperparâmetros específicos do preditor (ex.: constantes de exploração) e depende de buscas em árvore por instância.

Os autores argumentam que há necessidade de um decodificador agnóstico ao preditor que possa converter mapas de calor de diferentes modelos pré-treinados em tours viáveis sem necessidade de retreinamento ou ajustes específicos, mantendo a eficiência computacional e alta qualidade da solução.

2. Metodologia: HEATACO

Os autores propõem o HEATACO, um decodificador escalável baseado no Sistema de Formiga Máximo-Mínimo (MMAS - Max–Min Ant System), uma variante robusta da Otimização por Colônia de Formigas (ACO). O HEATACO integra o mapa de calor fixo na regra de construção do MMAS através de um novo fator de evidência limitado e consciente do grau.

Componentes Chave:

1. Construção de Lista de Candidatos:

   • Em vez de considerar todas as $O(n^2)$ arestas, o algoritmo restringe a construção a uma lista esparsa de candidatos de tamanho $k=20$ por nó.
   • Os candidatos são selecionados com base no mapa de calor (arestas com confiança $> \theta_h$) e preenchidos com vizinhos próximos caso o mapa seja esparso, garantindo conectividade.

2. Viés de Evidência Consciente do Grau ($e_{ij}$):

   • O mapa de calor é tratado como evidência ordinal, não como probabilidade calibrada.
   • Para cada nó, uma linha de base de grau ($b_i$) é calculada com base na $(d^*+1)$-ésima aresta de maior confiança, onde $d^*$ é o grau do tour (2 para TSP simétrico, 1 para saída de ATSP).
   • O fator de evidência $e_{ij}$ para uma aresta é a razão entre sua confiança e esta linha de base, limitada (capped) a um mínimo de 1. Isso garante que uma aresta só receba um aumento de viés se sua confiança exceder a capacidade do nó de aceitá-la, filtrando arestas de alta confiança "ruidosas" que são meramente as melhores entre muitas opções similares.

3. Escalonamento Automático ($\kappa$):

   • Para evitar que o mapa de calor sobreponha permanentemente o feedback de feromônio (que aprende a estrutura específica da instância), a força do viés de evidência ($\kappa$) é automaticamente escalonada.
   • $\kappa$ é derivado da amplitude dinâmica de feromônio ($\tau_{max}/\tau_{min}$) e do percentil 90 dos log-margens dos fatores de evidência.
   • Este escalonamento garante que o mapa de calor influencie a amostragem inicial, mas permite que o feedback de feromônio corrija orientações equivocadas conforme a busca progride. Uma configuração única funciona em diferentes preditores sem retreino.

4. Processo de Busca:

   • Inicialização: Um tour de vizinho próximo inicializa os limites de feromônio.
   • Construção: $m$ formigas constroem tours em paralelo usando uma regra proporcional pseudorandom que combina feromônios, distância heurística e o fator de evidência do mapa de calor.
   • Atualização: Os feromônios evaporam e são reforçados pelo melhor tour encontrado na iteração (ou pelo melhor global/de reinício).
   • Busca Local: Um 2-opt ou 3-opt opcional (para TSP simétrico) ou 2-opt direcionado (para ATSP) é aplicado para refinar os tours antes das atualizações de feromônio.

3. Principais Contribuições

• Um Decodificador Agnóstico ao Preditor: O HEATACO decodifica mapas de calor de diversos modelos pré-treinados (AttGCN, DIMES, UTSP, DIFUSCO) sem precisar retreinar o preditor ou ajustar o decodificador por modelo.
• Evidência Limitada e Consciente do Grau: Um mecanismo que recompensa arestas apenas quando elas excedem a capacidade de grau do nó, evitando que o decodificador seja sobrecarregado por mapas de calor densos e de baixa discriminabilidade.
• Escalonamento Automático: Um método para escalar o viés do mapa de calor em relação à amplitude dinâmica do feromônio, garantindo robustez frente a diferentes qualidades de mapa de calor e escalas de instâncias.
• Avaliação Abrangente: O método é avaliado nos conjuntos TSP500, TSP1K e TSP10K, bem como em benchmarks fora de distribuição (OOD) (Clustered, Gaussian, TSPLIB) e no TSP Assimétrico (ATSP).

4. Resultados Experimentais

O artigo compara o HEATACO contra o MMAS padrão, fusão gananciosa (greedy merging) e busca k-opt guiada por MCTS através de quatro fontes de mapas de calor.

• Vs. Fusão Gananciosa (Greedy Merging): O HEATACO supera significativamente a decodificação gananciosa, reduzindo lacunas de otimalidade de >10% (muitas vezes >30% em instâncias grandes) para níveis próximos ao ótimo.
• Vs. MCTS: Nos benchmarks de distribuição interna (TSP500, TSP1K, TSP10K), o HEATACO com 2-opt alcança menores lacunas de otimalidade e tempos de decodificação menores do que as linhas de base publicadas de MCTS para os mesmos mapas de calor fixos. Por exemplo, no TSP1K, o HEATACO+2-opt atinge cerca de 0,2–0,4% de lacuna em aproximadamente 4–8 segundos, enquanto o MCTS leva cerca de 100 segundos para atingir 0,5–1,5% de lacuna.
• Vs. MMAS Padrão:
  • Fase de Construção: A orientação pelo mapa de calor melhora significativamente a qualidade da construção inicial para todos os preditores e escalas, reduzindo as lacunas em vários pontos percentuais antes da busca local.
  • Com Busca Local:
    • No TSP500 e TSP1K, o HEATACO continua benéfico mesmo com 2-opt e 3-opt, embora o ganho marginal diminua conforme a força da busca local aumenta.
    • No TSP10K, a vantagem da orientação pelo mapa de calor diminui ou reverte após a busca local forte (3-opt). O artigo atribui isso à redução da complementaridade: a reparação geométrica forte (3-opt) pode recuperar a estrutura do tour independentemente, tornando a contribuição do mapa de calor redundante ou ocasionalmente prejudicial se este enviesar a busca longe de caminhos geometricamente ótimos.
• Generalização:
  • ATSP: O HEATACO transfere-se bem para o TSP Assimétrico, mostrando ganhos significativos onde a busca local (2-opt direcionado) é mais fraca.
  • Mudanças de Distribuição: O desempenho em dados OOD (Clustered, Gaussian, TSPLIB) correlaciona-se com a confiabilidade do mapa de calor. Quando o mapa permanece esparso e discriminativo (ex.: DIFUSCO em TSPLIB), o HEATACO tem sucesso. Quando o mapa torna-se muito denso ou perde a discriminabilidade (ex.: DIMES em pr1002), o desempenho degrada-se.
  • Controle SoftDist: Experimentos com um mapa de calor "SoftDist" não aprendido (baseado puramente em distância) mostram que, em grandes escalas com busca local forte, um prior geométrico costuma ser suficiente, reforçando que mapas de calor aprendidos são valiosos apenas quando fornecem estrutura além da simples proximidade.

5. Significância e Alegações

O artigo afirma que o HEATACO fornece um procedimento comum e automaticamente escalonado para converter mapas de calor de diferentes modelos pré-treinados em tours viáveis. Sua significância reside em:

• Desacoplamento da Predição da Decodificação: Permite aos pesquisadores reutilizar preditores de mapas de calor existentes sem a necessidade de retreiná-los ou ajustar um decodificador específico para cada um.
• Eficiência: Alcança velocidades de decodificação e qualidades de solução de estado da arte comparadas ao MCTS, que é computacionalmente proibitivo para problemas de grande escala.
• Insight Diagnóstico: O trabalho identifica que o valor dos mapas de calor aprendidos é limitado por dois fatores: confiabilidade do mapa de calor (sob mudanças de distribuição) e complementaridade com a busca local (em grandes escalas onde a reparação geométrica é forte).
• Utilidade Prática: Oferece um suporte (fallback) robusto ou um incremento para solvers combinatórios neurais, particularmente em cenários onde a busca local é fraca (ex.: ATSP) ou onde a decodificação rápida é necessária.

Os autores concluem modestamente que, embora os mapas de calor neurais sejam poderosos, eles nem sempre superam a busca clássica; sua utilidade depende da qualidade da evidência das arestas e da força da reparação geométrica disponível. Sugere-se como trabalho futuro combinar esses diagnósticos para selecionar dinamicamente entre o HEATACO e um retorno puro para MMAS.