Technische Samenvatting: Het begrijpen van mensachtige oplossingen in combinatorische optimalisatie via leren en zoeken

1. Probleemstelling

Combinatorische optimalisatieproblemen, zoals het Euclidische Handelsreizigersprobleem (TSP), zijn computationeel moeilijk (NP-hard), maar worden door mensen vaak met bijna optimale efficiëntie opgelost onder zware tijd- en cognitieve beperkingen. Hoewel mensen routinematig tours produceren die slechts ~10% langer zijn dan het wiskundige optimum, blijven de specifieke cognitieve algoritmen en geometrische principes die ten grondslag liggen aan deze "mensachtige" prestaties onduidelijk. Bestaande computationele modellen vertrouwen vaak ofwel op exhaustief zoeken (computationeel duur) of op eenvoudige heuristieken (vaak suboptimaal en niet in staat om menselijke structurele patronen te vangen). De centrale uitdaging is het identificeren van een computationeel kader dat niet alleen de TSP efficiënt oplost, maar ook de specifieke geometrische signaturen en systematische afwijkingen reproduceert die kenmerkend zijn voor menselijke oplossingen.

2. Methodologie

2.1 Grootschalige gedragsgegevensverzameling (tsp150k)

De auteurs voerden het grootste gedragsexperiment naar menselijke TSP-prestaties tot nu toe uit, waarbij de tsp150k dataset werd gegenereerd.

• Deelnemers: 1.107 deelnemers.
• Schaal: 150.000 unieke TSP-instanties met meer dan 20 miljoen door mensen gegenereerde tours.
• Complexiteitsniveaus: Vijf niveaus gebaseerd op het aantal steden: 10, 12, 15, 19 en 24 steden.
• Protocol: Deelnemers losten TSP-instanties online op via een platform geïntegreerd met WeChat. Tijdlimieten werden ingesteld op tweemaal het aantal steden (bijv. 20s voor 10 steden). Er werd geen feedback over de tourlengte gegeven tijdens de taak.
• Datadichtheid: Elke instantie ontving tussen de 92 en 207 menselijke tours (gemiddeld 139), wat een robuuste statistische karakterisering van menselijk gedrag mogelijk maakt.

2.1 Computationeel Modelleringskader

De studie evalueerde een brede hypotheseruimte van computationele modellen, gecategoriseerd in zoek-alleen methoden en hybride leer-en-zoek methoden.

• Zoek-alleen Baselines:

  • Exact: Concorde (branch-and-cut) voor optimale oplossingen.
  • Heuristieken: Nearest Neighbor, Convex Hull Cheapest Insertion, Largest Interior Angle.
  • Relaxatie: Elastic Net (gradiëntafdaling op een vervormbare ring).

• Neurale Netwerkmodellen (Pointer Networks):
  De auteurs gebruikten Pointer Networks (RNN's met attention-gebaseerde pointing mechanismen) om waarschijnlijkheidsverdelingen over geldige tours te definiëren. Vier verschillende trainingsregimes werden getest:

  1. $p_{optimal}$: Supervised learning op optimale tours (Concorde-oplossingen).
  2. $p_{RL}$: Reinforcement Learning (RL) met negatieve Euclidische tourlengte als beloning.
  3. $p_{optimal+RL}$: Supervised pretraining op optimale tours gevolgd door RL fine-tuning.
  4. $p_{human}$: Supervised learning direct op menselijke tours (als een empirische bovengrens).

• Decoding Strategieën:
  Om tours te genereren uit de getrainde policies, werden drie zoekstrategieën toegepast:

  1. Greedy Decoding: Myope selectie van de meest waarschijnlijke volgende stad.
  2. Beam Search: Heuristische benadering van de meest waarschijnlijke volledige sequentie.
  3. Best-of-$N$ Sampling: Het willekeurig samplen van $N$ volledige tours en het selecteren van de kortste daarvan.

2.3 Evaluatiemetrieken

De prestaties van modellen werden beoordeeld op een onafhankelijke testset (50.000 instanties) met behulp van vijf paarwijze gelijkenis-metrieken die model-tours vergelijken met menselijke tours:

1. Edge Overlap Ratio (EOR): Proportie gedeelde randen.
2. Longest Common Substring (LCS): Lengte van de langste gedeelde opeenvolgende stadensequentie.
3. Levenshtein Afstand (LD): Minimale bewerkingen om één tour in een andere te transformeren.
4. Fréchet Afstand (FD): Ruimtelijke scheiding tussen overeenkomstige punten in de doorloopvolgorde.
5. Kendall's $\tau$: Rangcorrelatie van bezoekvolgordes.

• Geometrische Analyse: Acht specifieke geometrische kenmerken (bijv. gladheid, draaihoek-entropie, convex-hull preservatie, 2-opt optimaliteit) werden geëxtraheerd om de "geometrische bekken" van menselijke oplossingen te karakteriseren.

3. Belangrijkste Resultaten

3.1 Kenmerken van Menselijke Prestaties

• Menselijke tours zijn nabij-optimaal, maar vertonen systematische afwijkingen en bezetten een "nabij-optimaal geometrisch bekken".
• Mensen besteden aanzienlijk meer tijd aan overweging bij de initiële positie, wat wijst op een "denk-dan-implementeer" strategie.
• Na het negeren van eerder bezochte steden stabiliseren de keuzes van de mens voor de volgende stad zich op een hoog niveau van lokale optimaliteit.

3.2 Vergelijking van Modelprestaties

• Zoek-alleen Modellen: Optimale tours (Concorde) en Elastic Net presteerden beter dan eenvoudige heuristieken en een willekeurige menselijke baseline, en bereikten een hoge gelijkenis met menselijke tours. Ze faalden echter in het vangen van specifieke menselijke sub-optimaliteitssignaturen (bijv. lagere gladheid en zwakkere convex-hull preservatie dan het wiskundige optimum).
• Pure Supervised Learning ($p_{human}$): Het model dat direct op menselijke tours is getraind met Beam Search bereikte de hoogste algehele alignment (Aggregate Score: 0.600), wat de empirische bovengrens vormt.
• Het Beste Generaliseerbare Model ($p_{optimal+RL}$): Onder de modellen niet getraind op menselijke data, bereikte de PointerNet gepretraind op optimale tours en gefinetuned met RL, gedecodeerd via Best-of-$N$ sampling ($N=100$), de sterkste menselijkheid (Aggregate Score: 0.600).
  • Dit model kwam nauw overeen met de geometrische kenmerken van menselijke tours (Pearson's $r = 0.583$ over acht kenmerken) en bereikte de laagste Mean Absolute Error (MAE = 0.021).
  • Het reproduceerde succesvol de karakteristieke menselijke sub-optimaliteit (bijv. niet-perfecte convex-hull preservatie) die pure optimale solvers misten.

3.3 Geometrische Bekkenanalyse

• Menselijke tours zijn verschillend van pure optimale tours; ze vertonen lagere gladheid en lagere 2-opt lokale optimaliteit.
• $p_{optimal}$ modellen convergeren te snel naar de optimale geometrische regio, waardoor ze menselijke afwijkingen missen.
• $p_{RL}$ modellen worden te geconcentreerd op een smalle set met hoge beloningen, waardoor ze de diversiteit missen die nodig is voor test-time search om mensachtige variaties te vinden.
• $p_{optimal+RL}$ vindt een balans: supervised pretraining biedt brede ondersteuning voor geometrisch nabij-optimale tours, terwijl RL fine-tuning de distributie bias richting kortere paden zonder de diversiteit te elimineren. Dit stelt Best-of-$N$ sampling in staat om te convergeren naar een regio die overeenkomt met menselijk gedrag.

4. Belangrijkste Bijdragen

1. tsp150k Dataset: De creatie van een enorme, hoogwaardige dataset bestaande uit 150.000 TSP-instanties en 20+ miljoen menselijke tours, wat een systematische karakterisering van menselijk gedrag mogelijk maakt.
2. Identificatie van Mensachtige Mechanismen: Het aantonen dat mensachtige oplossingen niet louter imitaties zijn van optimale tours, maar voortkomen uit een specifieke combinatie van gestructureerd supervised learning (verwerven van geometrische kennis), reinforcement learning (optimaliseren voor efficiëntie), en test-time search (Best-of-$N$ sampling).
3. Geometrische Karakterisering: Het definiëren van een "geometrisch bekken" voor menselijke oplossingen, waarbij wordt aangetoond dat mensen structurele eigenschappen delen met optimale oplossingen, terwijl ze systematische afwijkingen behouden (bijv. in gladheid en convex-hull preservatie) die standaard heuristieken en pure optimale solvers niet kunnen vangen.
4. Cognitief Modelleringskader: Het voorstellen dat menselijke probleemoplossing in combinatorische ruimtes gemodelleerd kan worden als een tweestaps-proces: het verwerven van structurele kennis van hoogwaardige voorbeelden (imitatie) en het verfijnen via feedback (RL), gevolgd door deliberatie (zoeken) op test-time.

5. Betekenis en Claims

Het artikel claimt dat mensachtige prestaties in combinatorische optimalisatie niet voortkomen uit vaste, handmatig ontworke heuristieken, maar uit een computationele architectuur die leren en zoeken integreert. Specifiek:

• Synergie tussen Leren en Zoeken: Het meest accurate model van menselijk gedrag is niet een directe imitatie van menselijke data, maar een model getraind op optimale data, verfijnd door RL, en gedecodeerd met search. Dit suggereert dat mensen brede geometrische kennis kunnen verwerven door blootstelling aan hoogwaardige voorbeelden en deze representaties kunnen verfijnen door ervaring-gebaseerde feedback.
• Rol van Test-Time Compute: De studie benadrukt dat "test-time compute" (bijv. Best-of-$N$ sampling) een cruciaal, vaak over het hoofd gezien onderdeel is van cognitieve modellering. Het stelt een statisch neuraal netwerk in staat om menselijke variabiliteit in oplossingkwaliteit te genereren zonder de gewichten aan te passen, wat parallel loopt aan mechanismen zoals chain-of-thought reasoning in large language models.
• Generaliseerbaarheid: De bevindingen suggereren dat de "bitter lesson" van AI — het vertrouwen op leren en computationele kracht in plaats van vaste heuristieken — ook van toepassing is op de menselijke cognitie. Menselijke oplossingen voor complexe problemen kunnen het cognitieve analogon weerspiegelen van algemene methoden die leren van ervaring en computationele kracht exploiteren via zoekprocessen.

De auteurs merken bescheiden op dat hoewel hun model menselijke geometrieën reproduceert zonder directe training op menselijke tours, de bron van de "optimale demonstraties" voor menselijk supervised learning een open vraag blijft, wat potentieel verband houdt met curriculum learning van eenvoudigere instanties.