Resumen Técnico: PathWise

Enunciado del Problema

El Diseño Heurístico Automatizado (AHD) tiene como objetivo generar automáticamente algoritmos heurísticos para Problemas de Optimización Combinatoria (COP), reduciendo la dependencia de diseños manuales elaborados por expertos. Aunque los Modelos de Lenguaje Grandes (LLM) han permitido recientemente el AHD al integrarse en procesos de búsqueda evolutiva, los marcos existentes sufren limitaciones significativas. Los métodos basados en poblaciones a menudo dependen de reglas evolutivas fijas y plantillas de prompts estáticas, lo que conduce a una generación de heurísticas miope, evaluaciones redundantes y convergencia prematura. Los métodos basados en árboles, como los que utilizan Búsqueda en Árbol Monte Carlo (MCTS), imponen estructuras jerárquicas impulsadas por estadísticas de rendimiento en lugar de una comprensión semántica del paisaje de búsqueda. Crucialmente, los enfoques actuales carecen de una representación semántica con estado de cómo se derivan las heurísticas, cómo se propagan las ediciones a través de las generaciones o por qué las modificaciones tienen éxito o fracasan. Esto resulta en un uso ineficiente de las llamadas a LLM y en una incapacidad para llevar adelante las decisiones pasadas de manera efectiva.

Metodología

Los autores proponen PathWise (Planificación a través de Modelo del Mundo para el Diseño Heurístico Automatizado mediante LLMs Autoevolutivos), un novedoso marco de razonamiento multiagente que formula la generación de heurísticas como un proceso de decisión secuencial sobre un grafo de implicación. Este grafo sirve como una memoria compacta y con estado de la trayectoria de búsqueda.

Componentes Principales

1. Grafo de Implicación ($G = (V, E)$):

   • A diferencia de los árboles evolutivos o poblaciones estándar, el grafo de implicación codifica el historial de derivación.
   • Nodos ($v$): Representan tuplas que contienen código heurístico ($h$), una justificación de derivación en lenguaje natural ($\kappa$), una descripción algorítmica ($d$), métricas de rendimiento ($P(h; D)$) y metadatos de los padres ($PM$).
   • Aristas ($E$): Conectan conjuntos de padres con nodos hijos, codificando la justificación específica utilizada para derivar al hijo de sus padres.
   • Esta estructura permite que el sistema condicione las decisiones futuras sobre el historial de derivación en lugar de tratar los pasos como eventos de muestreo aislados.

2. Sistema Multiagente:
   El marco opera mediante un ciclo coordinado de planificación, ejecución y reflexión en dos escalas de tiempo (actualizaciones de población externa y pasos de implicación internos):

   • Agente de Política ($\pi_p$): Actúa como un planificador de alto nivel. Observa el estado actual (el frente del grafo de implicación) y propone acciones definidas por una tupla de nodos padres seleccionados ($S$) y una justificación de derivación en lenguaje natural ($\kappa$). Esto permite que la política invente dinámicamente nuevos tipos de operadores en lugar de depender de plantillas fijas.
   • Agente de Modelo del Mundo ($\pi_{wm}$): Actúa como un ejecutor de bajo nivel. Traduce las acciones de alto nivel de la política en código heurístico ejecutable (lanzamientos) condicionado a los padres seleccionados y la directiva.
   • Agentes Críticos:
     • Crítico de Política ($\pi_{p\_critic}$): Analiza los resultados de las acciones de la política (selecciones de padres y directivas) para proporcionar reflexiones enrutadas que guían las estrategias evolutivas futuras.
     • Crítico de Modelo del Mundo ($\pi_{wm\_critic}$): Compara los lanzamientos heurísticos con mejor y peor rendimiento para proporcionar retroalimentación sobre la calidad de la síntesis de código, guiando al modelo del mundo a refinar la estructura algorítmica y la eficiencia.

3. Proceso de Búsqueda:

   • Bucle Externo: Mantiene una población de nodos raíz.
   • Bucle Interno: Construye incrementalmente un grafo de implicación enraizado en la población actual. En cada paso, el sistema muestrea múltiples acciones y lanzamientos, selecciona el nodo resultante mejor y actualiza el grafo.
   • Mecanismos de Diversidad: Para prevenir resultados de baja diversidad, PathWise emplea Diversidad a Nivel de Prompt (perturbando los prompts con frases exploratorias) y Mezcla de Estados (aleatorizando el orden de los nodos para mitigar el sesgo posicional).

Contribuciones Clave

1. Formulación Híbrida Grafo-Población: Los autores introducen una formulación donde un grafo de implicación codifica la justificación de la derivación y el historial de rendimiento, sirviendo como un estado compartido para la interacción entre la política y el modelo del mundo.
2. Marco Multiagente Coordinado: Un sistema donde un agente de política controla la estrategia evolutiva, un modelo del mundo ejecuta la generación de código y agentes críticos proporcionan reflexiones enrutadas, permitiendo una generación de heurísticas autoevolutiva y consciente del estado sin actualizar los parámetros del LLM.
3. Diversidad a Nivel de Prompt: Mecanismos para asegurar variedad en la selección de padres y en los lanzamientos heurísticos, permitiendo una exploración más amplia sobre el grafo de implicación.
4. Validación Empírica: Experimentos extensos que demuestran que PathWise descubre heurísticas más fuertes con menos evaluaciones, logra una convergencia más rápida y escala efectivamente a tamaños de problema más grandes en diversos COPs.

Resultados Experimentales

PathWise fue evaluado en múltiples COPs NP-difíciles, incluyendo el Problema del Viajante de Comercio (TSP), el Problema de la Mochila (KP), el Problema de Enrutamiento de Vehículos con Capacidad (CVRP), el Problema de la Mochila Múltiple (MKP), el Problema de Orientación (OP) y el Problema de Empaquetado en Contenedores (BPP). El marco fue probado en tres paradigmas de búsqueda: Construcción Paso a Paso, Optimización de Colonias de Hormigas (ACO) y Búsqueda Local Guiada (GLS).

• Rendimiento: PathWise superó consistentemente a las líneas base de AHD basadas en LLM de última generación (FunSearch, EoH, ReEvo, HSEvo, MCTS-AHD) y a heurísticas diseñadas manualmente. Logró brechas de optimalidad más bajas tanto en conjuntos de prueba dentro del dominio como fuera de él.
• Eficiencia: PathWise convergió más rápido hacia heurísticas mejores. En varios experimentos, PathWise logró un rendimiento superior con solo 500 evaluaciones, mientras que a las líneas base se les permitieron 1000 evaluaciones.
• Escalabilidad: El método demostró una fuerte generalización a tamaños de problema más grandes (por ejemplo, TSP con $N=200$, KP con $N=500$) y diferentes arquitecturas de LLM (GPT-4o-mini, GPT-5-nano con niveles de razonamiento variables).
• Estudios de Ablación: Eliminar los agentes críticos o los mecanismos de diversidad degradó significativamente el rendimiento, confirmando la necesidad de retroalimentación consciente del estado y exploración.

Significado y Afirmaciones

El artículo afirma que PathWise representa un cambio de la "evolución de prueba y error" hacia la "planificación consciente del estado a través del razonamiento". Al tratar el descubrimiento de heurísticas como un proceso de decisión secuencial sobre un grafo de implicación, el sistema puede llevar adelante las decisiones pasadas y reutilizar o evitar información de derivación a través de las generaciones.

Los autores enfatizan que PathWise es libre de entrenamiento en el sentido de que no actualiza los parámetros del LLM; en su lugar, aprovecha el conocimiento preentrenado de los LLMs reforzado mediante reflexiones en lenguaje natural. El significado radica en su capacidad para superar la miopía de los métodos AHD existentes al proporcionar una memoria estructurada del proceso de búsqueda, reduciendo así las evaluaciones redundantes y permitiendo un descubrimiento más efectivo de heurísticas de alta calidad para problemas combinatorios complejos. El trabajo sugiere que el razonamiento estructurado sobre el historial de derivación es un componente crítico para escalar el diseño automatizado de algoritmos basado en LLM.