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

Imagina que estás intentando resolver un rompecabezas masivo y desordenado, como organizar la ruta de un camión de reparto para cientos de paradas o empacar una maleta con los artículos más valiosos posibles. Estos son "problemas de optimización combinatoria", y son notoriamente difíciles porque el número de formas posibles de organizar las piezas es tan enorme que incluso las supercomputadoras más rápidas no pueden revisarlas todas. Durante décadas, los humanos han intentado escribir "reglas de oro" especiales (llamadas heurísticas) para resolver estos rompecabezas rápidamente. Pero aquí está el problema: una regla que funciona perfectamente para una ciudad con un diseño de calles en forma de cuadrícula podría fallar estrepitosamente en una ciudad con caminos sinuosos y circulares. Esta es la realidad del "No Free Lunch" (No hay almuerzo gratis): no existe una única regla mágica que funcione para cada situación.

Recientemente, los científicos comenzaron a utilizar "Modelos de Lenguaje de Gran Escala" (LLM, por sus siglas en inglés)—el mismo tipo de IA que escribe historias y responde preguntas—para inventar estas reglas automáticamente. Sin embargo, la mayoría de estos experimentos de IA fueron como entrenar a un estudiante usando solo un libro de texto único y pequeño. El IA se volvía muy bueno resolviendo los problemas de ese libro específico, pero si le dabas un rompecabezas ligeramente diferente, se confundía. Era como enseñarle a un chef a hacer una tortilla perfecta, pero usando solo huevos de una granja específica; si le dabas huevos de una granja diferente, la tortilla podría desmoronarse. La forma antigua de entrenar estas IA también dependía de una retroalimentación muy simple, como un profesor que solo decía "Buen trabajo" o "Mal trabajo" sin explicar por qué o dónde ocurrió el error.

Aquí entra MOSAIC, un nuevo marco de trabajo desarrollado por investigadores del Instituto de Tecnología de Georgia. Piensa en MOSAIC no como un solo estudiante tratando de memorizar un libro de texto, sino como una biblioteca masiva y viva donde se entrenan diferentes reglas "especialistas" para distintos tipos de rompecabezas. En lugar de solo pedirle a una IA que "cree una mejor regla", MOSAIC establece un juego de gato y ratón de alto riesgo. Enfrenta las reglas actuales de la IA contra un equipo de creadores de rompecabezas "adversarios". Estos creadores de rompecabezas también son IA, y su único trabajo es crear los rompecabezas más difíciles y confusos diseñados específicamente para romper las reglas actuales. Cuando una regla falla, el sistema no se limita a decir "perdiste". Utiliza un árbol de decisión inteligente para determinar exactamente qué tipo de rompecabezas rompió la regla, y luego almacena ese rompecabezas y la lección aprendida en una "celda" específica de una cuadrícula gigante. Con el tiempo, esta cuadrícula se llena con una colección diversa de especialistas: una regla para ciudades con diseño de cuadrícula, otra para vecindarios agrupados, otra para rutas largas y sinuosas. El sistema utiliza entonces estas lecciones almacenadas para evolucionar reglas aún mejores, creando un equipo de expertos donde cada uno es un maestro de su propio territorio específico.

Los investigadores probaron esta idea en tres problemas clásicos: el Problema del Viajante (encontrar la ruta más corta), el Probleente de la Mochila (empacar el mayor valor) y el Problema de Rutas de Vehículos con Capacidad (entregar mercancías con espacio limitado en el camión). Encontraron que MOSAIC superó consistentemente a otros métodos de IA de vanguardia. Mientras que otros métodos tenían dificultades cuando los rompecabezas cambiaban ligeramente, el "equipo de especialistas" de MOSAIC manejaba los cambios con facilidad, encontrando a menudo soluciones que estaban significativamente más cerca de la respuesta perfecta. Por ejemplo, en el Problema del Viajante, el mejor equipo de reglas de MOSAIC fue hasta un 22% más preciso que el siguiente mejor método.

Quizás aún más emocionante, los rompecabezas "adversarios" que creó MOSAIC fueron mucho más diversos y desafiantes que los creados por los métodos tradicionales. El sistema logró cubrir un 33% más del "espacio de características" (los diferentes tipos de estructuras de rompecabezas) que los métodos anteriores, lo que significa que aprendió a manejar una variedad mucho más amplia de escenarios del mundo real. El estudio sugiere que, al tratar el problema como una batalla coevolutiva—donde los rompecabezas se vuelven más difíciles para exponer debilidades, y las reglas se vuelven más inteligentes para corregirlas—podemos construir una IA que no solo memoriza algunos ejemplos, sino que realmente comprende el panorama del problema. Es un cambio de entrenar a un genio único que lo sabe todo sobre una sola cosa, a construir una comunidad diversa de expertos que saben un poco de todo, y mucho sobre su rincón específico del mundo.