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

Imaginez que vous essayez de résoudre un puzzle massif et désordonné, comme organiser l'itinéraire d'un camion de livraison pour des centaines d'arrêts ou remplir une valise avec les articles les plus précieux possibles. Ce sont des « problèmes d'optimisation combinatoire », et ils sont notoirement difficiles car le nombre de façons possibles d'organiser les pièces est si immense que même les superordinateurs les plus rapides ne peuvent pas toutes les vérifier. Pendant des décennies, les humains ont essayé d'écrire des « règles empiriques » spéciales (appelées heuristiques) pour résoudre ces puzzles rapidement. Mais voici le hic : une règle qui fonctionne parfaitement pour une ville avec un plan de rues en grille peut échouer lamentablement dans une ville avec des routes sinueuses et circulaires. C'est la réalité du « No Free Lunch » (pas de repas gratuit) : il n'existe pas de règle magique unique qui fonctionne pour toutes les situations.

Récemment, des scientifiques ont commencé à utiliser des « Modèles de Langage de Grande Taille » (LLM) — le même type d'IA qui écrit des histoires et répond à des questions — pour inventer automatiquement ces règles. Cependant, la plupart de ces expériences d'IA étaient comme entraîner un étudiant sur un seul petit manuel scolaire. L'IA devenait très douée pour résoudre les problèmes de ce livre spécifique, mais si on lui donnait un puzzle légèrement différent, elle se perdait. C'était comme apprendre à un chef à faire une omelette parfaite, mais en utilisant uniquement des œufs provenant d'une ferme spécifique ; si on lui donnait des œufs d'une autre ferme, l'omelette pourrait s'effondrer. L'ancienne méthode d'entraînement de ces IA reposait également sur un feedback très simple, comme un enseignant disant simplement « Bon travail » ou « Mauvais travail » sans expliquer pourquoi ou où se trouvait l'erreur.

Entrez en scène MOSAIC, un nouveau cadre développé par des chercheurs de l'Institut de technologie de Géorgie. Voyez MOSAIC non pas comme un étudiant unique essayant de mémoriser un manuel, mais comme une immense bibliothèque vivante où différentes règles « spécialisées » sont entraînées pour différents types de puzzles. Au lieu de simplement demander à une IA de « créer une meilleure règle », MOSIC met en place un jeu de chat et de la souris à enjeux élevés. Il oppose les règles actuelles de l'IA à une équipe de créateurs de puzzles « adverses ». Ces créateurs de puzzles sont aussi des IA, et leur seul travail est de créer les puzzles les plus difficiles et les plus déroutants spécifiquement conçus pour briser les règles actuelles. Lorsqu'une règle échoue, le système ne se contente pas de dire « vous avez perdu ». Il utilise un arbre de décision intelligent pour déterminer exactement quel type de puzzle a brisé la règle, puis stocke ce puzzle et la leçon apprise dans une « cellule » spécifique d'une grille géante. Au fil du temps, cette grille se remplit d'une collection diversifiée de spécialistes : une règle pour les villes en grille, une autre pour les quartiers regroupés, une autre pour les itinéraires longs et sinueux. Le système utilise ensuite ces leçons stockées pour faire évoluer encore mieux les règles, créant ainsi une équipe d'experts où chacun est un maître de son propre territoire.

Les chercheurs ont testé cette idée sur trois problèmes classiques : le Problème du Voyageur de Commerce (trouver l'itinéraire le plus court), le Problème du Sac à Dos (remplir le plus de valeur possible) et le Problème de Tournée de Véhicules avec Capacité (livrer des marchandises avec un espace de camion limité). Ils ont constaté que MOSAIC surpassait systématiquement les autres méthodes d'IA de pointe. Alors que les autres méthodes peinaient lorsque les puzzles changeaient légèrement, l'« équipe de spécialistes » de MOSAIC gérait les changements avec aisance, trouvant souvent des solutions nettement plus proches de la réponse parfaite. Par exemple, sur le Problème du Voyageur de Commerce, la meilleure équipe de règles de MOSAIC était jusqu'à 22 % plus précise que la méthode suivante de meilleur niveau.

Peut-être plus excitant encore, les puzzles « adverses » créés par MOSAIC étaient bien plus diversifiés et stimulants que ceux produits par les méthodes traditionnelles. Le système a réussi à couvrir 33 % de l'« espace de caractéristiques » (les différents types de structures de puzzles) de plus que les méthodes précédentes, ce qui signifie qu'il a appris à gérer une plus grande variété de scénarios du monde réel. L'étude suggère qu'en traitant le problème comme une bataille de co-évolution — où les puzzles deviennent plus difficiles pour exposer les faiblesses, et les règles deviennent plus intelligentes pour les corriger — nous pouvons construire une IA qui ne se contente pas de mémoriser quelques exemples, mais qui comprend véritablement le paysage du problème. C'est un passage de l'entraînement d'un génie unique qui sait tout sur une seule chose, à la construction d'une communauté diversifiée d'experts qui savent un peu de tout, et beaucoup de leur coin de monde spécifique.