Resumen Técnico: CoEvo-AHD para la Optimización Combinatoria de Componentes Acoplados Bi-Componente

1. Definición del Problema

El artículo aborda problemas de Optimización Combinatoria (CO) de Componentes Acoplados Bi-Componente, donde una solución consiste en dos componentes de decisión semánticamente distintos pero interdependientes. El desafío central es que la factibilidad o el valor objetivo de modificar un componente depende enteramente del estado del otro. En consecuencia, la utilidad de un operador es relacional en lugar de intrínseca; un operador que funciona bien de forma aislada puede degradar la solución global cuando se acopla con un estado subóptimo del segundo componente.

Los autores instancian este marco en dos problemas representativos:

• Traveling Thief Problem (TTP): Acopla el enrutamiento (Problema del Viajante) con el empaquetado (Problema de la Mochila 0–1). El orden del recorrido afecta la velocidad de viaje según la carga transportada, mientras que el plan de empaquetado determina el peso transportado en cada paso.
• Traveling Purchaser Problem (TPP): Acopla la selección de mercados/enrutamiento con las decisiones de compra. El orden de las visitas y la selección de mercados determinan las opciones de compra factibles y los costos, mientras que las decisiones de compra influyen en el valor de visitar mercados específicos.

Los métodos actuales de Diseño de Heurísticas Automatizado (AHD) impulsados por Modelos de Lenguaje de Gran Escala (LLM) suelen evolucionar heurísticas como unidades algorítmicas o estrategias de búsqueda aisladas (por ejemplo, construcción frente a reparación). Estos métodos no logran capturar la complementariedad inducida por la estructura del problema requerida para los problemas de bi-componentes acoplados, donde los operadores deben co-evolucionarse para funcionar sinérgicamente a través de componentes de solución heterogéneos.

2. Metodología: CoEvo-AHD

Los autores proponen CoEvo-AHD, un marco de co-evolución de doble población impulsado por LLM diseñado para descubrir y refinar automáticamente operadores de componentes emparejados. El marco opera a través de cuatro etapas:

2.1 Inicialización de la Doble Población

Se mantienen dos poblaciones de operadores separadas: $P_A$ para el componente A (por ejemplo, operadores de ruta) y $P_B$ para el componente B (por ejemplo, operadores de empaquetado).

• Inicialización: Las poblaciones comienzan con una mezcla de operadores semilla especificados manualmente y operadores generados por LLM.
• Validación: Todos los operadores generados se someten a validaciones de sintaxis, interfaz, ejecución acotada y factibilidad de componente antes de entrar en la población.
• Interfaz: Los operadores devuelven actualizaciones candidatas solo para su componente específico, dependiendo de una memoria de información compartida y herramientas externas para el contexto global.

2.2 Evaluación Cooperativa

A diferencia de los métodos tradicionales que califican a los operadores de forma aislada, CoEvo-AHD evalúa los operadores mediante la ejecución emparejada en soluciones completas.

• Selección: Una estrategia de Thompson Sampling local selecciona un operador de $P_A$ y uno de $P_B$ para cada reinicio de búsqueda.
• Optimización Alternada: El par seleccionado se invoca alternativamente dentro de una trayectoria de búsqueda. Por ejemplo, un operador de ruta propone una permutación de ciudades, que luego se pasa a un operador de empaquetado (o viceversa).
• Reparación y Reconstrucción: Debido a que los componentes están acoplados, los candidatos intermedios pueden ser infactibles. El marco utiliza un entorno de problemas aumentado con herramientas para realizar la reparación de la factibilidad, la reconstrucción y la evaluación del objetivo completo.
• Información Compartida: Un diccionario mutable (shared_info) permite a los operadores intercambiar señales de búsqueda suaves (por ejemplo, perfiles de carga, pistas de inserción de candidatos) sin sobrescribir directamente la lógica del otro componente.

2.3 Gestión y Evolución de la Población

El marco emplea un bucle de co-evolución para refinar las poblaciones:

• Calificación: Las recompensas se calculan basadas en la mejora de la solución acoplada completa. Estas recompensas actualizan tres estadísticas: puntuaciones individuales para $o_A$ y $o_B$, y una puntuación de sinergia de pares ($S_{ij}$) para el par de operadores específico.
• Poda: Los operadores de bajo rendimiento son eliminados de sus respectivas poblaciones.
• Evolución Impulsada por LLM: Las vacantes se llenan mediante tres operaciones evolutivas:
  1. Mutación Intra-componente: Refina un único operador padre.
  2. Cruce Homogéneo Intra-componente: Recombina dos operadores de la misma población.
  3. Cruce Conjunto entre Componentes: Selecciona el par con mejor desempeño $(o_A^*, o_B^*)$ basado en las puntuaciones de sinergia y solicita al LLM que los reescriba como una entidad unificada y coordinada. Esto fomenta la generación de operadores con protocolos de comunicación compatibles y supuestos de búsqueda complementarios.

2.4 Entorno Aumentado con Herramientas

Para evitar que los LLM generen código de bajo nivel ineficiente o propenso a errores, el marco encapsula las operaciones principales (por ejemplo, computación de delta de búsqueda local, reconstrucción codiciosa, verificaciones de factibilidad) en herramientas estandarizadas y llamables. Esto permite que los operadores generados por LLM se centren en el diseño de vecindad de alto nivel y la coordinación entre componentes.

3. Contribuciones Clave

1. Formulación del Problema: El artículo formula el AHD impulsado por LLM específicamente para la optimización combinatoria de componentes acoplados bi-componente, definiendo la utilidad del operador como relacional y necesitando una evaluación conjunta a través de componentes de solución heterogéneos.
2. Marco CoEvo-AHD: Una novedosa arquitectura de co-evolución que presenta:
   • Poblaciones de operadores específicas por componente.
   • Evaluación basada en la ejecución emparejada para capturar las interacciones entre componentes.
   • Puntuación de sinergia de pares para guiar la selección de pares de operadores complementarios.
   • Cruce conjunto entre componentes para evolucionar operadores mutuamente compatibles.
3. Comunicación Estructurada y Herramientas: La introducción de un protocolo de comunicación entre componentes estructurado y un entorno aumentado con herramientas que estandariza las operaciones específicas del problema, permitiendo a los LLM generar una lógica heurística de alto nivel y robusta.

4. Resultados Experimentales

El marco fue evaluado en los benchmarks TTP y TPP contra heurísticas tradicionales de última generación y bases recientes basadas en LLM.

• Traveling Thief Problem (TTP):

  • CoEvo-AHD logró los mejores resultados en instancias pequeñas a medianas (TTP20, TTP50), superando a bases como MATLS, S5 y CoCo.
  • En instancias más grandes (TTP100, TTP200), logró el segundo mejor promedio general, quedando solo detrás de CoCo, pero superando significativamente a MATLS y S5.
  • Esto sugiere que el marco captura eficazmente el acoplamiento en espacios de búsqueda más pequeños, pero enfrenta desafíos en la profundidad de búsqueda para instancias muy grandes.

• Traveling Purchaser Problem (TPP):

  • CoEvo-AHD demostró una ventaja general pronunciada, logrando los mejores resultados en cinco escalas de instancias (incluyendo escalas grandes como 150×100 y 150×150) y el segundo mejor en otras tres.
  • Redujo el valor objetivo promedio aproximadamente un 2.76% en comparación con la segunda mejor base (TA) y hasta un 11.42% en comparación con ALNS.
  • Los resultados indican que el marco es particularmente efectivo para explotar la sinergia entre las decisiones de enrutamiento y de compra en TPP.

• Estudios de Ablación:

  • Eliminar la co-evolución de la doble población (evolucionando solo un componente) causó una degradación significativa del rendimiento (por ejemplo, una caída de ~11% en TPP), confirmando que optimizar los componentes de forma aislada es insuficiente.
  • Eliminar el entorno aumentado con herramientas también provocó caídas en el rendimiento (~5.5% en TTP), resaltando la importancia de las interfaces estandarizadas para la fiabilidad y la eficiencia.

5. Significado y Reivindicaciones

El artículo afirma que CoEvo-AHD representa un cambio en el AHD impulsado por LLM, pasando de generar roles algorítmicos aislados a modelar la complementariedad de operadores inducida por la estructura del problema. Al co-evolucionar explícitamente poblaciones de operadores heterogéneos y evaluarlos mediante la ejecución conjunta, el marco aborda la limitación de los métodos existentes que no pueden manejar el fuerte acoplamiento entre las subestructuras de decisión.

Los autores posicionan este trabajo como un paso hacia un diseño de heurísticas más generalizable para problemas de optimización complejos del mundo real donde los componentes de la solución son profundamente interdependientes. Observan modestamente que, si bien el marco es altamente competitivo, queda margen de mejora en la profundidad de búsqueda y la robustez para instancias de escala muy grande, y el trabajo futuro buscará extender el marco a problemas con más de dos componentes acoplados.