LLM-gestützte Heuristik-Entwicklung für A* verbessert Suchleistung

Ein neues Verfahren nutzt große Sprachmodelle (LLMs), um Heuristiken für den A*-Suchalgorithmus automatisch zu entwerfen. Traditionell werden solche Leitfunktionen von Experten manuell erstellt, was viel Fachwissen erfordert. Durch die Kombination von LLMs mit evolutionären Optimierungsframeworks lässt sich dieser Prozess nun automatisieren.

Das vorgestellte Konzept, Algorithmic‑Contextual Evolution of Heuristics (A‑CEoH), erweitert das bestehende Evolution of Heuristics (EoH)-Framework. Dabei wird der A*-Code selbst in den Prompt eingebunden, sodass das Sprachmodell kontextbezogen lernen kann. Diese domänenunabhängige Prompt‑Augmentation ermöglicht es, gezielt Heuristiken zu generieren, die für unterschiedliche Suchaufgaben geeignet sind.

In umfangreichen Experimenten wurden zwei Problem­bereiche untersucht: das Unit‑Load Pre‑Marshalling Problem (UPMP) aus der Lagerlogistik und das klassische Schiebepuzzle (SPP). Die Ergebnisse zeigen, dass A‑CEoH die Qualität der erzeugten Heuristiken deutlich steigert und sogar bei beiden Aufgaben die von Experten entworfenen Leitfunktionen übertrifft.

Die Studie demonstriert damit, dass LLM‑basierte Prompt‑Augmentation ein vielversprechender Ansatz ist, um die Effizienz von Suchalgorithmen zu erhöhen und gleichzeitig den Aufwand für die manuelle Heuristik‑Entwicklung zu reduzieren.