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

Immagina di cercare di risolvere un puzzle enorme e disordinato, come organizzare il percorso di un camion delle consegne per centinaia di fermate o riempire una valigia con gli oggetti più preziosi possibili. Questi sono "problemi di ottimizzazione combinatoria" e sono notoriamente difficili perché il numero di possibili modi per disporre i pezzi è così vasto che persino i supercomputer più veloci non possono controllarli tutti. Per decenni, gli esseri umani hanno cercato di scrivere delle "regole empiriche" speciali (chiamate euristiche) per risolvere questi puzzle rapidamente. Ma ecco il problema: una regola che funziona perfettamente per una città con una struttura stradale a griglia potrebbe fallire miseramente in una città con strade tortuose e circolari. Questa è la realtà del "No Free Lunch": non esiste un'unica regola magica che funzioni per ogni situazione.

Recentemente, gli scienziati hanno iniziato a usare i "Large Language Models" (LLM) — lo stesso tipo di IA che scrive storie e risponde a domande — per inventare automaticamente queste regole. Tuttavia, la maggior parte degli esperimenti con l'IA era come addestrare uno studente usando solo un singolo, piccolo libro di testo. L'IA diventava bravissima a risolvere i problemi di quel libro specifico, ma se le avessi dato un puzzle leggermente diverso, si sarebbe confusa. Era come insegnare a uno chef a fare un'omelette perfetta, ma usando solo uova provenienti da una specifica fattoria; se gli avessi dato le uova di una fattoria diversa, l'omelette sarebbe potuta andare in pezzi. Il vecchio modo di addestrare queste IA si basava anche su un feedback molto semplice, come un insegnante che diceva solo "Bravo" o "Sbagliato", senza spiegare perché o dove fosse avvenuto l'errore.

Entra in scena MOSAIC, un nuovo framework sviluppato dai ricercatori del Georgia Institute of Technology. Pensa a MOSAIC non come a un singolo studente che cerca di memorizzare un libro di testo, ma come a una vasta biblioteca vivente dove diverse regole "specialistiche" vengono addestrate per diversi tipi di puzzle. Invece di chiedere semplicemente a un'IA di "creare una regola migliore", MOSAIC mette in scena un gioco di inseguimento ad alta tensione tra gatto e topo. Mette le attuali regole dell'IA contro una squadra di creatori di puzzle "avversari". Questi creatori di puzzle sono anch'essi un'IA, e il loro unico compito è creare i puzzle più difficili e confondenti, progettati specificamente per rompere le regole attuali. Quando una regola fallisce, il sistema non si limita a dire "hai perso". Utilizza un albero decisionale intelligente per capire esattamente che tipo di puzzle ha incrinato la regola e poi memorizza quel puzzle e la lezione appresa in una "cella" specifica di una griglia gigante. Nel tempo, questa griglia si riempie di una collezione diversificata di specialisti: una regola per le città a griglia, un'altra per i quartieri raggruppati, un'altra ancora per i percorsi lunghi e tortuosi. Il sistema utilizza poi queste lezioni memorizzate per far evolvere regole ancora migliori, creando una squadra di esperti in cui ognuno è un maestro del proprio territorio specifico.

I ricercatori hanno testato questa idea su tre problemi classici: il Problema del Commesso Viaggiatore (trovare il percorso più breve), il Problema dello Zaino (impacchettare il massimo valore) e il Problema del Veicolo con Capacità Limitata (consegnare merci con spazio limitato nel camion). Hanno scoperto che MOSAIC supera costantemente altri metodi di IA all'avanguardia. Mentre altri metodi faticavano quando i puzzle cambiavano leggermente, MOSAIC, grazie alla sua "squadra di specialisti", gestiva i cambiamenti con facilità, trovando spesso soluzioni significativamente più vicine alla risposta perfetta. Ad esempio, sul Problema del Commesso Viaggiatore, la migliore squadra di regole di MOSAIC è stata fino al 22% più accurata rispetto al secondo miglior metodo.

Forse ancora più eccitante è che i puzzle "avversari" creati da MOSAIC erano molto più diversificati e impegnativi rispetto a quelli creati dai metodi tradizionali. Il sistema è riuscito a coprire il 33% in più dello "spazio delle caratteristiche" (i diversi tipi di strutture dei puzzle) rispetto ai metodi precedenti, il che significa che ha imparato a gestire una varietà molto più ampia di scenari del mondo reale. Lo studio suggerisce che, trattando il problema come una battaglia co-evolutiva — dove i puzzle diventano più difficili per esporre le debolezze e le regole diventano più intelligenti per correggerle — possiamo costruire un'IA che non si limita a memorizzare alcuni esempi, ma comprende davvero il panorama del problema. È un passaggio dall'addestrare un singolo genio che sa tutto di una sola cosa, al costruire una comunità diversificata di esperti che sanno un po' di tutto, e molto di un loro specifico angolo di mondo.