LLM-gestützte Heuristik: Game-Theoretic Co-Evolution steigert Generalisierung

Mit großen Sprachmodellen (LLMs) hat sich die automatische Entdeckung von Heuristiken (AHD) rasant weiterentwickelt. Doch bisherige Ansätze starren häufig an statische Bewertungssets, was zu Überanpassung und schlechter Leistung bei veränderten Datenverteilungen führt.

Die neue Methode, Algorithm Space Response Oracles (ASRO), nutzt ein spieltheoretisches Konzept, um die Heuristik-Entwicklung als kooperative Evolution zwischen einem Solver und einem Instanzgenerator zu modellieren. Dabei wird das Problem als Zwei-Spieler-Nullsummenspiel formuliert, wobei beide Seiten ihre Strategiepools kontinuierlich erweitern.

ASRO setzt auf LLM-basierte Best-Response-Orakel, die gegen gemischte Meta-Strategien des Gegners arbeiten. Durch diese iterative Erweiterung entsteht ein dynamisches, selbstgeneriertes Curriculum, das die Bewertung von Heuristiken von statisch zu adaptiv wandelt.

In mehreren Bereichen der kombinatorischen Optimierung übertrifft ASRO die bisherigen statischen AHD-Baselines, die auf denselben Programmsuchmechanismen beruhen. Die Ergebnisse zeigen deutlich verbesserte Generalisierung und Robustheit gegenüber vielfältigen und außerhalb der Trainingsverteilung liegenden Instanzen.