MOSAIC: Adversarial Co-evolution of Specialist Heuristics and Problem Instances for LLM-based Automated Heuristic Design

Stellen Sie sich vor, Sie versuchen, ein riesiges, chaotisches Puzzle zu lösen, wie etwa die Planung einer Lieferwagenroute für hunderte von Stopps oder das Packen eines Koffers mit den wertvollsten Gegenständen, die möglich sind. Dies sind „kombinatorische Optimierungsprobleme“, und sie sind notorisch schwierig, weil die Anzahl der möglichen Möglichkeiten, die Teile anzuordnen, so gewaltig ist, dass selbst die schnellsten Supercomputer nicht alle prüfen können. Jahrzehntelang haben Menschen versucht, spezielle „Faustregeln“ (genannt Heuristiken) zu schreiben, um diese Rätsel schnell zu lösen. Aber hier liegt der Haken: Eine Regel, die perfekt für eine Stadt mit einem gitterartigen Straßenlayout funktioniert, kann in einer Stadt mit gewundenen, kreisförmigen Straßen kläglich scheitern. Dies ist die Realität des „No Free Lunch“-Prinzips: Es gibt keine einzige magische Regel, die in jeder Situation funktioniert.

Kürzlich begannen Wissenschaftler, „Large Language Models“ (LLMs) einzusetzen – dieselbe Art von KI, die Geschichten schreibt und Fragen beantwortet) –, um diese Regeln automatisch zu erfinden. Die meisten dieser KI-Experimente ähnelten jedoch dem Training eines Schülers, der nur ein einziges, kleines Lehrbuch lernt. Die KI wurde zwar sehr gut darin, die Probleme in diesem speziellen Buch zu lösen, aber wenn man ihr ein etwas anderes Rätsel gab, geriet sie durcheinander. Es war, als würde man einen Koch darauf trainieren, ein perfektes Omelett zuzubereiten, aber dabei nur Eier von einem ganz bestimmten Bauernhof verwenden; wenn man ihm Eier von einem anderen Bauernhof gibt, könnte das Omelett zerfallen. Die alte Art des KI-Trainings stützte sich zudem auf sehr einfaches Feedback, wie etwa einen Lehrer, der nur „Gut gemacht“ oder „Schlecht gemacht“ sagt, ohne zu erklären, warum oder wo der Fehler passierte.

Hier kommt MOSAIC ins Spiel, ein neues Framework, das von Forschern am Georgia Institute of Technology entwickelt wurde. Betrachten Sie MOSAIC nicht als einen einzelnen Schüler, der versucht, ein Lehrbuch auswendig zu lernen, sondern als eine massive, lebendige Bibliothek, in der verschiedene „Spezialisten-Regeln“ für unterschiedliche Arten von Rätseln trainiert werden. Anstatt die KI lediglich zu fragen, „erfinde eine bessere Regel“, setzt MOSIC ein hochkarätiges Katz-und-Maus-Spiel auf. Es stellt die aktuellen Regeln der KI gegen ein Team von „adversariellen“ Rätselerstellern. Diese Rätselersteller sind ebenfalls KIs, und ihre einzige Aufgabe ist es, die schwierigsten, verwirrendsten Rätsel zu entwerfen, die speziell darauf ausgelegt sind, die aktuellen Regeln zu brechen. Wenn eine Regel versagt, sagt das System nicht einfach nur „Du hast verloren“. Es verwendet einen intelligenten Entscheidungsbaum, um genau herauszufinden, welche Art von Rätsel die Regel besiegt hat, und speichert dieses Rätsel sowie die daraus gelernte Lektion in einer spezifischen „Zelle“ eines riesigen Gitters. Im Laufe der Zeit füllt sich dieses Gitter mit einer vielfältigen Sammlung von Spezialisten: eine Regel für gitterartige Städte, eine andere für Cluster-Nachbarschaften, eine weitere für lange, gewundene Routen. Das System nutzt diese gespeicherten Lektionen, um noch bessere Regeln zu entwickeln, und erschafft so ein Team von Experten, von denen jeder ein Meister seines eigenen spezifischen Territoriums ist.

Die Forscher testeten diese Idee an drei klassischen Problemen: dem Traveling Salesman Problem (das Finden der kürzesten Route), dem Knapsack Problem (das Packen des höchsten Wertes) und dem Capacitated Vehicle Routing Problem (die Lieferung von Waren mit begrenztem LKW-Platz). Sie fanden heraus, dass MOSAIC andere moderne KI-Methoden konsequent übertrifft. Während andere Methoden Schwierigkeiten bekamen, wenn sich die Rätsel leicht veränderten, bewältigte MOSAIC diese Veränderungen mit Leichtigkeit durch sein „Team von Spezialisten“ und fand oft Lösungen, die der perfekten Antwort signifikant näher kamen. Beispielsweise war das beste Team von Regeln bei MOSAIC beim Traveling Salesman Problem bis zu 22 % genauer als die nächstbeste Methode.

Vielleicht noch spannender ist, dass die von MOSAIC erstellten „adversariellen“ Rätsel weitaus vielfältiger und anspruchsvoller waren als jene traditioneller Methoden. Das System schaffte es, 33 % mehr des „Feature Space“ (der verschiedenen Arten von Rätselstrukturen) abzudecken als bisherige Methoden, was bedeutet, dass es lernte, eine viel größere Vielfalt an realen Szenarien zu bewältigen. Die Studie legt nahe, dass wir, indem wir das Problem als koevolutionären Kampf betrachten – bei dem die Rätsel schwieriger werden, um Schwachstellen aufzudecken, und die Regeln klüger werden, um diese zu beheben –, eine KI bauen können, die nicht nur ein paar Beispiele auswendig lernt, sondern die Landschaft des Problems wirklich versteht. Es ist ein Wechsel von der Ausbildung eines einzelnen Genies, das alles über eine Sache weiß, hin zum Aufbau einer vielfältigen Gemeinschaft von Experten, die von vielem ein wenig wissen, aber von ihrem spezifischen Teil der Welt sehr viel.