Resumen Técnico: CoupleEvo

Definición del Problema

Los sistemas de optimización del mundo real a menudo consisten en múltiples subproblemas estrechamente acoplados donde las soluciones deben coordinarse para lograr un alto rendimiento global. Estos problemas acoplados frecuentemente combinan dos o más subproblemas NP-difíciles, como en el Problema de Enrutamiento de Inventarios (IRP) o el Problema de Pre-estibado de Unidades de Carga Multi-robot Multi-bay (MR-MUPMP). Aunque optimizar subproblemas de forma aislada a menudo produce resultados globales subóptimos, la optimización simultánea totalmente integrada es frecuentemente computacionalmente intratable debido al crecimiento combinatorio del espacio de soluciones conjunto.

Los marcos existentes de diseño automático de heurísticas impulsados por Modelos de Lenguaje Grande (LLM) están actualmente limitados a configuraciones de un solo problema, evolucionando una única heurística para un único objetivo. Existe una brecha en la literatura respecto al diseño sistemático de múltiples heurísticas interactivas para problemas de optimización acoplados, careciendo específicamente de una estrategia de coordinación evolutiva para gestionar las interdependencias entre subproblemas.

Metodología: CoupleEvo

Los autores proponen CoupleEvo, el primer marco impulsado por LLM para el diseño automático de heurísticas en problemas de optimización acoplados. El marco opera dentro de un contexto de Búsqueda en Vecindad Grande (LNS) iterativo, donde se le asigna al LLM la tarea de generar heurísticas de destrucción para cada subproblema, mientras que las heurísticas de reparación permanecen deterministas.

Estrategias de Coordinación Evolutiva

CoupleEvo introduce tres estrategias distintas para gobernar la búsqueda evolutiva a través de subproblemas interdependientes:

1. Evolución Secuencial: Las heurísticas se evolucionan para un subproblema tras otro. La evolución del subproblema $k$ procede durante un número fijo de generaciones mientras todos los demás subproblemas utilizan sus heurísticas actuales de mejor rendimiento (fijas). Esto ofrece simplicidad conceptual pero conlleva el riesgo de convergencia prematura, donde la primera heurística evolucionada restringe el espacio de búsqueda para los subproblemas posteriores.
2. Evolución Iterativa: La evolución alterna entre subproblemas a lo largo de múltiples rondas de control. En cada ronda, el algoritmo recorre todos los subproblemas, refinando sus heurísticas basándose en los mejores rendimientos de la ronda anterior. Esta estrategia busca evitar el sobreajuste a un solo subproblema y mantiene la flexibilidad para la coordinación.
3. Evolución Integrada: Las heurísticas para todos los subproblemas se evolucionan simultáneamente. Se le solicita al LLM que genere una tupla completa de heurísticas (código y pensamientos para todos los subproblemas) en un solo paso. Aunque esto modela explícitamente las interdependencias, aumenta la complejidad de la búsqueda y exige más capacidades generativas del LLM.

Detalles de Implementación

• LLM: El marco utiliza el modelo de código abierto Qwen3-coder:30b.
• Prompting: El sistema emplea un conjunto de estrategias de prompt adaptadas de trabajos anteriores (EoH, ReEvo), incluyendo prompts de inicialización (I1), exploración (E1, E2) y modificación (M1, M2).
• Evaluación: La aptitud se calcula basándose en el valor objetivo de las instancias del problema acoplado. Para IRP, la aptitud es la brecha relativa frente a una línea base HGS de última generación; para MR-MUPMP, es el valor objetivo promedio.
• Configuración Experimental: El marco fue probado en dos dominios:
  • IRP: Integrando gestión de inventarios y enrutamiento de vehículos.
  • MR-MUPMP: Integrando búsqueda de movimientos (secuenciación de reubicaciones) y enrutamiento de vehículos con precedencias.
  • Todas las estrategias recibieron un presupuesto evolutivo igual (40 generaciones totales) para garantizar una comparación justa.

Contribuciones Clave

1. Marco CoupleEvo: La formulación del primer marco impulsado por LLM que extiende el diseño automático de heurísticas desde configuraciones de un solo problema hasta problemas de optimización acoplados con múltiples subproblemas NP-difíciles interdependientes.
2. Estrategias Evolutivas: La propuesta e investigación sistemática de tres estrategias de coordinación (Secuencial, Iterativa, Integrada) que definen cómo se generan y refinan las heurísticas para subproblemas interactivos.
3. Evaluación Exhaustiva: Evaluación experimental extensa en dos dominios representativos de optimización acoplada, proporcionando conocimientos empíricos sobre las compensaciones entre estabilidad de convergencia, complejidad de búsqueda y calidad de la solución.

Resultados Experimentales

El estudio evaluó las tres estrategias en 6 ejecuciones por estrategia tanto para IRP como para MR-MUPMP.

• Descomposición vs. Integración: Las estrategias basadas en descomposición (Secuencial e Iterativa) demostraron consistentemente una convergencia más estable y una mayor calidad de solución en comparación con la estrategia Integrada.
• Estrategia Secuencial: Exhibió una mejora rápida de la aptitud inicial al evolucionar el primer subproblema. Sin embargo, la convergencia a menudo se ralentizó o se estancó al cambiar al segundo subproblema, sugiriendo que la primera heurística evolucionada restringió el espacio de búsqueda. Logró el mejor rendimiento medio para MR-MUPMP.
• Estrategia Iterativa: Mostró una trayectoria más gradual pero consistentemente en mejora. Al alternar el enfoque, mitigó el sobreajuste prematuro y mantuvo la adaptabilidad. Logró los mejores valores mínimos y medianos de aptitud para MR-MUPMP y los resultados más estables (menor rango) para IRP.
• Estrategia Integrada: Sufrió de una complejidad de búsqueda aumentada y alta variabilidad. Aunque algunas ejecuciones lograron resultados competitivos, la estrategia generalmente exhibió un rendimiento más débil y una mayor varianza, indicando dificultad para refinar consistentemente tuplas de heurísticas de alta calidad para problemas acoplados.

Comparación con Referencias

Las heurísticas evolucionadas de mejor rendimiento (CoupleLNS) se compararon con la literatura establecida:

• IRP: CoupleLNS superó a las metaheurísticas clásicas (MH) en un promedio del 5.61%. Logró resultados competitivos frente a la Búsqueda Genética Híbrida (HGS) de última generación, con una brecha promedio del 2.96%, sin depender de una ingeniería específica del problema extensiva.
• MR-MUPMP: Comparado con un enfoque secuencial basado en pasos (SBS) que utiliza A* óptimo, CoupleLNS tuvo una calidad de solución ligeramente inferior en instancias resolubles, pero resolvió con éxito todas las instancias dentro del límite de tiempo, mientras que SBS falló en algunas. Cuando se comparó con un SBS* adaptado (utilizando una heurística guiada por LLM), CoupleLNS lo superó en un promedio del 5.01%.

Significado y Afirmaciones

El artículo afirma que CoupleEvo demuestra el potencial del diseño automático de heurísticas impulsado por LLM para problemas complejos de optimización acoplada. El hallazgo principal es que coordinar la búsqueda evolutiva a través de subproblemas interdependientes es crítico; las estrategias basadas en descomposición (secuencial e iterativa) son actualmente más efectivas que la evolución integrada para estos tipos específicos de problemas.

Los autores posicionan su trabajo no como un reemplazo de los métodos clásicos, sino como un enfoque complementario. Sugieren que los métodos basados en LLM pueden evolucionar componentes heurísticos altamente ajustados y específicos del problema que mejoran marcos existentes como LNS. El trabajo destaca que, aunque la evolución integrada es teóricamente atractiva para capturar interacciones entre componentes, las capacidades actuales de los LLM y la complejidad de la búsqueda favorecen estrategias que descomponen el problema mientras mantienen una coordinación iterativa.

Las direcciones de investigación futura identificadas por los autores incluyen adaptar el marco a problemas con más de dos subproblemas, mejorar la estabilidad de la estrategia integrada y desarrollar estrategias de coordinación adaptativas que cambien dinámicamente entre problemas de optimización.