HeatACO: A Heatmap-Guided Max--Min Ant System for Large-Scale Travelling Salesman Problems
Non-autoregressive neural solvers predict an edge-confidence heatmap for the Travelling Salesman Problem (TSP) in one forward pass, but a decoder must still produce a feasible Hamiltonian cycle. As instance size grows, this stage must reconcile a quadratic number of edge scores with global tour constraints. Greedy edge merging is fast and deterministic but produces low-quality tours, whereas Monte Carlo Tree Search (MCTS) over k-opt moves recovers better tours at high computational cost and requires predictor-specific tuning. We propose HeatACO, a predictor-agnostic heatmap-to-tour decoder. Its key is a capped, degree-aware evidence factor that integrates a fixed heatmap into a Max--Min Ant System (MMAS). The factor rewards only edge confidence beyond a node's tour-degree capacity, and its strength is scaled automatically from the pheromone dynamic range, allowing one configuration to decode heatmaps from different predictors without retraining or per-predictor tuning. Across four heatmap sources, HeatACO produces higher-quality solutions in less decoding time than the MCTS baseline on TSP500, TSP1K and TSP10K. Against matched standard MMAS baselines with the same search budget, heatmap guidance improves construction for all four predictors at both scales and remains beneficial with local search. HeatACO also transfers competitively to several distribution shifts and the asymmetric TSP (ATSP). Our post-hoc analysis identifies measurable heatmap properties associated with the observed performance variation.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problems
Recent advancements in solving large-scale traveling salesman problems (TSP) utilize the heatmap-guided Monte Carlo tree search (MCTS) paradigm, where machine learning (ML) models generate heatmaps, indicating the probab…
PositionEDGER: EDge-Guided with HEatmap Refinement for Generalizable Image Forgery Localization
Text-guided inpainting has made image forgery increasingly realistic, challenging both SID and IFL. However, existing methods often struggle to point out suspicious signals across domains. To address this problem, we pro…
Domain GeneralizationTop-down Visual Saliency Guided by Captions
Neural image/video captioning models can generate accurate descriptions, but their internal process of mapping regions to words is a black box and therefore difficult to explain. Top-down neural saliency methods can find…
DecoderSentenceVideo CaptioningLocally Grouped and Scale-Guided Attention for Dense Pest Counting
This study introduces a new dense pest counting problem to predict densely distributed pests captured by digital traps. Unlike traditional detection-based counting models for sparsely distributed objects, trap-based pest…
Graph-PCNN: Two Stage Human Pose Estimation with Graph Pose Refinement
Recently, most of the state-of-the-art human pose estimation methods are based on heatmap regression. The final coordinates of keypoints are obtained by decoding heatmap directly. In this paper, we aim to find a better a…
Pose EstimationregressionVocal Bursts Valence Prediction