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

Stel je voor dat je een enorme, rommelige puzzel probeert op te lossen, zoals het organiseren van de route van een bezorgwagen met honderden stops of het inpakken van een koffer met de meest waardevolle items mogelijk. Dit zijn "combinatorische optimalisatieproblemen", en ze zijn berucht moeilijk omdat het aantal mogelijke manieren om de stukjes te rangschikken zo groot is dat zelfs de snelste supercomputers ze niet allemaal kunnen controleren. Decennialang hebben mensen geprobeerd om speciale "vuistregels" (heuristieken genoemd) te schrijven om deze puzzels snel op te lossen. Maar hier is de crux: een regel die perfect werkt voor een stad met een roosterachtig straatpatroon, kan rampzalig falen in een stad met kronkelende, cirkelvormige wegen. Dit is de "No Free Lunch"-realiteit: er is geen enkele magische regel die voor elke situatie werkt.

Onlangs zijn wetenschappers "Large Language Models" (LLM's) gaan gebruiken—dezelfde soort AI die verhalen schrijft en vragen beantwoordt—om automatisch deze regels te verzinnen. Echter, de meeste AI-experimenten waren als het trainen van een student op slechts één enkel, klein tekstboek. De AI werd heel goed in het oplossen van de problemen in dat specifieke boek, maar als je het een iets ander puzzeltje gaf, raakte het in de war. Het was alsof je een chef-kok leerde om een perfect omelet te maken, maar alleen gebruikmaakte van eieren van één specifieke boerderij; als je hem eieren van een andere boerderij gaf, kon de omelet uit elkaar vallen. De oude manier van AI trainen vertrouwde ook op zeer eenvoudige feedback, zoals een leraar die alleen zegt "Goed gedaan" of "Slecht gedaan" zonder uit te leggig waarom of waar de fout precies zat.

Maak kennis met MOSAIC, een nieuw framework ontwikkeld door onderzoekers aan de Georgia Institute of Technology. Zie MOSAIC niet als een enkele student die probeert een tekstboek uit het hoofd te leren, maar als een enorme, levende bibliotheek waar verschillende "specialistische" regels worden getraind voor verschillende soorten puzzels. In plaats van de AI alleen te vragen om "een betere regel te maken", zet MOSAIC een hoogwaardig spel van kat en muis op. Het zet de huidige regels van de AI tegenover een team van "adversariële" puzzelmakers. Deze puzzelmakers zijn ook AI, en hun enige taak is om de moeilijkste, meest verwarrende puzzels te creëren die specifiek ontworpen zijn om de huidige regels te breken. Wanneer een regel faalt, zegt het systeem niet alleen "je hebt verloren". Het gebruikt een slimme beslissingsboom om precies te achterhalen welk type puzzel de regel heeft gebroken, en slaat die puzzel en de geleerde les vervolgens op in een specifieke "cel" van een gigantisch raster. Na verloop van tijd vult dit raster zich met een diverse collectie specialisten: één regel voor roosterachtige steden, een andere voor geclusterde buurten, een andere voor lange, kronkelende routes. Het systeem gebruikt vervolgens deze opgeslagen lessen om nog betere regels te laten evolueren, waardoor er een team van experts ontstaat waarbij elk onderdeel een meester is van zijn eigen specifieke terrein.

De onderzoekers testten dit idee op drie klassieke problemen: het Handelsreizigersprobleem (het vinden van de kortste route), het Knapzakprobleem (het inpakken van de meeste waarde) en het Capacitated Vehicle Routing Problem (het leveren van goederen met een beperkte vrachtwagenruimte). Ze ontdekten dat MOSAIC consequent beter presteerde dan andere state-of-the-art AI-methoden. Terwijl andere methoden moeite hadden wanneer de puzzels licht veranderden, hanteerde MOSAIC de veranderingen met gemak dankzij zijn "team van specialisten", en vond vaak oplossingen die aanzienlijk dichter bij het perfecte antwoord lagen. Zo was het beste team van regels van MOSAIC voor het Handelsreizigersprobleem tot wel 22% nauwkeuriger dan de op één na beste methode.

Misschien nog wel opwindender is dat de "adversariële" puzzels die MOSAIC creëerde, veel diverser en uitdagender waren dan die van traditionele methoden. Het systeem slaagde erin om 33% meer van de "feature space" (de verschillende soorten puzzelstructuren) te dekken dan voorgaande methoden, wat betekent dat het leerde om een veel breder scala aan real-world scenario's aan te kunnen. De studie suggereert dat door het probleem te behandelen als een co-evolutionaire strijd—waarbij de puzzels moeilijker worden om zwakheden bloot te leggen, en de regels slimmer worden om die te herstellen—we AI kunnen bouwen die niet alleen een paar voorbeelden uit het hoofd leert, maar de landschap van het probleem echt begrijpt. Het is een verschuiving van het trainen van een enkele genie die alles weet over één ding, naar het bouwen van een diverse gemeenschap van experts die een beetje weten van alles, en heel veel van hun eigen specifieke hoekje van de wereld.