🤖 machine learning

HeatACO: A Heatmap-Guided Max--Min Ant System for Large-Scale Travelling Salesman Problems

Dit artikel introduceert HeatACO, een predictor-onafhankelijke decoder die niet-autoregressieve TSP-heatmaps integreert in een Max-Min Ant System via een nieuwe graadbewuste bewijsfactor, waarmee een superieure oplossingskwaliteit en efficiëntie wordt bereikt ten opzichte van MCTS en standaard baselines over grootschalige en diverse TSP-instanties zonder dat predictor-specifieke afstemming vereist is.

Oorspronkelijke auteurs: Bo-Cheng Lin, Yi Mei, Mengjie Zhang

Gepubliceerd 2026-07-29

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Bo-Cheng Lin, Yi Mei, Mengjie Zhang

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een bezorger bent met een kaart van een stad en een lijst met stops die je moet maken. Je doel is om elke stop precies één keer te bezoeken en terug te keren naar huis, terwijl je de kortst mogelijke afstand aflegt. Dit is het beroemde "Handelsreizigersprobleem" (Traveling Salesman Problem). Het klinkt eenvoudig, maar naarmate de stad groter wordt, explodeert het aantal mogelijke routes zo snel dat zelfs de krachtigste supercomputers ter wereld niet elke optie kunnen controleren om de perfecte route te vinden. Daarom hebben wetenschappers de hulp ingeroepen van kunstmatige intelligentie. In plaats van te proberen elke route te berekenen, fungeren moderne AI-modellen als deskundige verkenners. Ze bekijken de kaart en markeren snel de wegen die veelbelovend lijken, waardoor ze een "heatmap" creëren waar de helderste kleuren de randen aangeven die waarschijnlijk deel uitmaken van een geweldige route.

Er zit echter een addertje onder het gras. Deze AI-verkenners zijn erg goed in het spotten van goede wegen, maar ze zijn erg slecht in het verbinden van deze wegen tot een volledige, geldige reis. Ze kunnen bijvoorbeeld drie verschillende wegen vanuit hetzelfde huis markeren, maar een echte chauffeur kan er slechts één nemen. De AI geeft je een rommelige stapel aanwijzingen, en je hebt nog steeds een slimme decoder nodig om ze te sorteren tot een enkele, haalbare tour zonder in lussen vast te komen zitten of stops te missen. De grote vraag is: hoe verander je deze vage, rommelige heatmaps in een perfecte route zonder de AI voor elke nieuwe stad of kaartomvang opnieuw te hoeven trainen?

Dit is precies wat de onderzoekers achter HEATACO probeerden op te lossen. Ze ontwikkelden een nieuwe, universele decoder die fungeert als een slimme verkeersregelaar voor deze AI-heatmaps. In plaats van simpelweg de helderste kleuren blindelings te volgen of gebruik te maken van trage methoden van vallen en opstaan, gebruikt HEATACO een slim systeem dat geïnspireerd is door de manier waarop mieren voedsel vinden.

Zo werkt het: Stel je een kolonie mieren voor die een brug probeert te bouwen. Bij de oude methode, als een AI-heatmap zei: "Hé, deze weg is super helder!", zou de decoder deze direct grijpen. Maar soms is die heldere weg een valstrik. HEATACO is slimmer. Het kijkt naar de heatmap en vraagt zich af: "Is deze weg zoveel beter dan de andere dat het de moeite waard is om hem te nemen, zelfs als we hem nog niet geprobeerd hebben?" Het schenkt alleen aandacht aan de echt overtuigende aanwijzingen en negeert de ruis. Vervolgens laat het zijn "mieren" (wat eigenlijk computer simulaties zijn) de route bouwen. Terwijl ze bouwen, laten ze een digitale "geur" (een feromoon genoemd) achter op de wegen die ze gebruiken. Als een mier een korte, goede route vindt, wordt de geur sterker, wat andere mieren vertelt om dat pad de volgende keer te proen.

De magie van HEATACO is dat het de initiële gok van de AI (de heatmap) in evenwicht brengt met de eigen ervaring van de mieren (de feromonen). Het laat de gok van de AI niet volledig de overhand nemen; in plaats daarvan gebruikt het de gok om een voorsprong te krijgen, om vervolgens de mieren de route te laten verfijnen terwijl ze bezig zijn. Dit betekent dat je een heatmap van elke getrainde AI-model kunt nemen — of het nu getraind is op kleine dorpjes of enorme steden — en HEATACO kunt gebruiken om er een geweldige route van te maken zonder de AI opnieuw te hoeven trainen of de instellingen voor elke nieuwe kaart aan te passen.

De onderzoekers testten dit op enkele enorme uitdagingen, inclusief kaarten met tot wel 10.000 stops. Ze ontdekten dat HEATACO sneller was en betere routes vond dan de voorheen beste methoden, die vaak veel tijd moesten besteden aan gissen en controleren. Het was vooral goed in het omzetten van de rommelige AI-aanwijzingen in een solide plan voordat de mieren überhaupt aan hun zoektocht begonnen. Ze ontdekten echter ook een limiet: zodra de route al zeer goed is en je krachtige lokale verbeteringen begint toe te passen (zoals het omwisselen van een paar wegen om de rit te verkorten), wordt de initiële heatmap van de AI minder nuttig. In die gevallen werken de ouderwetse geometrische trucjes net zo goed.

Kortom, HEATACO is een veelzijdig instrument dat de kloof overbrugt tussen rommelige AI-voorspellingen en perfecte reisplannen. Het bewijst dat je niet voor elke AI-model een andere decoder nodig hebt; met de juiste balans tussen "luisteren naar de expert" en "leren van ervaring", kun je enorme routeringsproblemen snel en efficiënt oplossen, ongeacht hoe groot de stad ook wordt.

Technische Samenvatting: HEATACO – Een Heatmap-gestuurd Max–Min Mierensysteem voor Grote Schaal TSP's

1. Probleemstelling

Het artikel behandelt het Travelling Salesman Problem (TSP), met een specifieke focus op de decoderingsfase van niet-autoregressieve (NAR) neurale solvers. Deze solvers voorspellen een rand-betrouwbaarheidsheatmap in één enkele forward pass, waarbij scores worden toegekend aan potentiële randen. Echter, een heatmap is geen geldige tour; deze bevat vaak discontecteerde cycli, schendt graadbeperkingen (knopen met meer dan twee incidentele randen) en bevat fout-positieven.

De kernuitdaging is het heatmap-naar-tour decoderingsprobleem: het omzetten van een vaste, dichte heatmap ( $O(n^2)$ scores) naar een haalbare Hamiltoniaanse cyclus ( $n$ randen) die voldoet aan globale beperkingen. Bestaande decoders staan voor een afweging:

Greedy Merging: Snel en deterministisch, maar levert tours van lage kwaliteit op omdat het niet in staat is om vroege, potentieel misleidende randkeuzes te herzien.
MCTS-gestuurde k-opt zoektocht: Produceert tours van hogere kwaliteit, maar is computationeel duur, vereist predictor-specifieke afstemming van hyperparameters (bijv. exploratieconstanten) en is afhankelijk van per-instantie boomzoektochten.

De auteurs stellen dat er behoefte is aan een predictor-agnostische decoder die heatmaps van verschillende voorgetrainde modellen kan omzetten in haalbare tours zonder hertraining of specifieke afstemming, terwijl de computationele efficiëntie en de kwaliteit van de oplossingen hoog blijven.

2. Methodologie: HEATACO

De auteurs stellen HEATACO voor, een schaalbare decoder gebaseerd op het Max–Min Ant System (MMAS), een robuuste variant van Ant Colony Optimization (ACO). HEATACO integreert de vaste heatmap in de MMAS-constructieregel via een nieuwe beperkte, graadbewuste evidence factor.

Kerncomponenten:

Constructie van de Candidate List:
- In plaats van alle $O(n^2)$ randen te overwegen, beperkt het algoritme de constructie tot een ijle candidate list van grootte $k=20$ per knoop.
- Kandidaten worden geselecteerd op basis van de heatmap (randen met betrouwbaarheid $> \theta_h$ ) en aangevuld met dichtstbijzijnde buren als de heatmap ijl is, om connectiviteit te garanderen.
Graadbewuste Evidence Bias ( $e_{ij}$ ):
- De heatmap wordt behandeld als ordinale bewijsvoering in plaats van gekalibreerde waarschijnlijkheid.
- Voor elke knoop wordt een graad baseline ( $b_i$ ) berekend op basis van de $(d^*+1)$ -de hoogste betrouwbare rand, waarbij $d^*$ de tour-graad is (2 voor symmetrische TSP, 1 voor uitgaande ATSP).
- De evidence factor $e_{ij}$ voor een rand is de ratio van de betrouwbaarheid tot deze baseline, begrensd op een minimum van 1. Dit zorgt ervoor dat een rand alleen een bias-boost krijgt als de betrouwbaarheid de capaciteit van de knoop overstijgt om deze te accepteren, waardoor "ruisachtige" hoog-betrouwbare randen die slechts de beste zijn tussen vele vergelijkbare opties, worden weggefilterd.
Automatische Schaling ( $\kappa$ ):
- Om te voorkomen dat de heatmap de feromonen-feedback permanent overrulet (die de instantie-specifieke structuur leert), wordt de sterkte van de evidence bias ( $\kappa$ ) automatisch geschaald.
- $\kappa$ wordt afgeleid van het feromonen dynamisch bereik ( $\tau_{max}/\tau_{min}$ ) en het 90e percentiel van de log-marges van de evidence factoren.
- Deze schaling zorgt ervoor dat de heatmap de vroege sampling beïnvloedt, maar de feromonen-feedback toestaat de misleidende sturing te corrigeren naarmate de zoektocht vordert. Eén enkele configuratie werkt over verschillende predictors heen zonder hertraining.
Zoekproces:
- Initialisatie: Een nearest-neighbor tour initialiseert de feromonen-grenzen.
- Constructie: $m$ mieren bouwen parallel tours met behulp van een pseudorandom proportionele regel die feromonen, heuristische afstand en de heatmap evidence factor combineert.
- Update: Feromonen verdampen en worden versterkt door de beste tour gevonden in de iteratie (of de restart/globale best).
- Lokale Zoektocht: Optionele 2-opt of 3-opt (voor symmetrische TSP) of gerichte 2-opt (voor ATSP) wordt toegepast om tours te verfijnen vóór de feromonen-updates.

3. Belangrijkste Bijdragen

Een Predictor-Agnostische Decoder: HEATACO decodeert heatmaps van diverse voorgetrainde modellen (AttGCN, DIMES, UTSP, DIFUSCO) zonder de predictor te hertrainen of de decoder per model af te stemmen.
Beperkte, Graadbewuste Evidence: Een mechanisme dat randen beloont alleen wanneer ze de graadcapaciteit van de knoop overschrijden, wat voorkomt dat de decoder wordt overspoeld door dichte, laag-discrimineerbare heatmaps.
Automatische Schaling: Een methode om de heatmap bias te schalen ten opzichte van het feromonen dynamisch bereik, wat robuustheid garandeert over verschillende heatmap-kwaliteiten en instantie-schalen.
Uitgebreide Evaluatie: De methode wordt geëvalueerd op TSP500, TSP1K, en TSP10K, evenals op out-of-distribution (OOD) benchmarks (Clustered, Gaussian, TSPLIB) en de Asymmetrische TSP (ATSP).

4. Experimentele Resultaten

Het artikel vergelijkt HEATACO met standaard MMAS, greedy merging en MCTS-gestuurde k-opt zoektocht over vier heatmap-bronnen.

vs. Greedy Merging: HEATACO presteert aanzienlijk beter dan greedy decoding, waarbij de optimaliteitsgaps van >10% (vaak >30% op grote instanties) worden teruggebracht naar bijna optimale niveaus.
vs. MCTS: Op in-distributie benchmarks (TSP500, TSP1K, TSP10K) bereikt HEATACO met 2-opt lagere optimaliteitsgaps en kortere decoding tijden dan de gepubliceerde MCTS-baselines voor dezelfde vaste heatmaps. Bijvoorbeeld, op TSP1K bereikt HEATACO+2-opt ~0,2–0,4% gap in ~4–8 seconden, terwijl MCTS ~100 seconden nodig heeft voor ~0,5–1,5% gap.
vs. Standaard MMAS:
- Constructiefase: Heatmap-sturing verbetert de initiële constructiekwaliteit aanzienlijk voor alle predictors en schalen, wat de gaps met enkele procentpunten verlaagt vóór lokale zoektocht.
- Met Lokale Zoektocht:
  - Op TSP500 en TSP1K blijft HEATACO voordelig, zelfs met 2-opt en 3-opt, hoewel de marginale winst afneemt naarmate de kracht van de lokale zoektocht toeneemt.
  - Op TSP10K neemt het voordeel van heatmap-sturing af of keert het om na sterke lokale zoektocht (3-opt). Het artikel schrijft dit toe aan verminderde complementariteit: sterke geometrische reparatie (3-opt) kan de tourstructuur onafhankelijk herstellen, waardoor de bijdrage van de heatmap redundant of soms zelfs nadelig wordt als deze de zoektocht wegstuurt van geometrisch optimale paden.
Generalisatie:
- ATSP: HEATACO vertaalt goed naar de Asymmetrische TSP, waarbij het significante winsten laat zien waar lokale zoektocht (gerichte 2-opt) minder sterk is.
- Distributieverschuivingen: Prestaties op OOD-data (Clustered, Gaussian, TSPLIB) correleren met de betrouwbaarheid van de heatmap. Wanneer de heatmap ijl en discrimineerbaar blijft (bijv. DIFUSCO op TSPLIB), slaagt HEATACO. Wanneer de heatmap te dicht wordt of de discriminatie verliest (bijv. DIMES op pr1002), verslechtert de prestatie.
- SoftDist Controle: Experimenten met een niet-geleerde "SoftDist" heatmap (gebaseerd op pure afstand) tonen aan dat bij grote schalen met sterke lokale zoektocht, een geometrische prior vaak voldoende is, wat bevestigt dat geleerde heatmaps alleen waardevol zijn wanneer ze structuur bieden die verder gaat dan eenvoudige nabijheid.

5. Betekenis en Claims

Het artikel claimt dat HEATACO een gemeenschappelijke, automatisch geschaalde procedure biedt voor het omzetten van heatmaps van verschillende modellen in haalbare tours. De betekenis ligt in:

Ontkoppeling van Predictie en Decoding: Het stelt onderzoekers in staat om bestaande heatmap-predictors te hergebruiken zonder ze te hoeven hertrainen of een specifieke decoder per model te moeten afstemmen.
Efficiëntie: Het bereikt state-of-the-art decoding snelheden en oplossingskwaliteiten vergeleken met MCTS, wat computationeel onhaalbaar is voor problemen op grote schaal.
Diagnostisch Inzicht: Het werk identificeert dat de waarde van geleerde heatmaps wordt begrensd door twee factoren: heatmap betrouwbaarheid (onder distributieverschuivingen) en complementariteit met lokale zoektocht (bij grote schalen waar geometrische reparatie sterk is).
Praktisch Nut: Het biedt een robuuste fallback of verbetering voor neurale combinatorische solvers, met name in scenario's waar lokale zoektocht zwak is (bijv. ATSP) of waar snelle decoding vereist is.

De auteurs concluderen bescheiden dat hoewel neurale heatmaps krachtig zijn, ze niet altijd klassieke zoektochten overtreffen; hun nut hangt af van de kwaliteit van de edge evidence en de kracht van de geometrische reparatie die beschikbaar is. Toekomstig werk suggereert het combineren van deze diagnostiek om dynamisch te kiezen tussen HEATACO en een pure MMAS fallback.