Resumen Técnico: Búsqueda Heurística Latente (LHS)

Enunciado del Problema

El diseño de algoritmos heurísticos de alta calidad para problemas de optimización combinatoria (por ejemplo, Problema del Viajante, Enrutamiento de Vehículos, Mochila) es tradicionalmente un proceso impulsado por expertos que requiere refinamiento iterativo y conocimiento profundo del dominio. Los avances recientes han integrado Modelos de Lenguaje Grandes (LLM) en marcos evolutivos (por ejemplo, FunSearch, EoH, ReEvo) para automatizar este descubrimiento. Sin embargo, estos métodos existentes operan principalmente en el espacio discreto de la sintaxis del programa. Confían en el muestreo estocástico, mutaciones a nivel de token y recombinación para navegar un paisaje de optimización altamente no convexo. Este enfoque a menudo requiere un gran número de evaluaciones costosas basadas en la ejecución para descubrir mejoras consistentes y lucha contra la fragilidad de los espacios de búsqueda discretos.

Metodología

El artículo propone Búsqueda Heurística Latente (LHS), un marco que desplaza el proceso de optimización del espacio de tokens discretos a una variedad latente continua aprendida. La metodología consta de cuatro componentes interconectados:

1. Codificación Latente: Un codificador de código preentrenado ($E$) mapea programas heurísticos discretos en incrustaciones vectoriales continuas ($z \in \mathbb{R}^d$).
2. Modelado de Suplantación: Se entrena un modelo de suplantación diferenciable ($f_\theta$) para predecir la puntuación de rendimiento de una heurística basándose en su incrustación latente. Para garantizar la robustez frente a evaluaciones ruidosas y variaciones de escala, el modelo se entrena utilizando una pérdida de clasificación por pares (RankNet) en lugar de regresión punto a punto, centrándose en el ordenamiento relativo de los candidatos.
3. Optimización Regularizada mediante Flujos Normalizadores: Para abordar la anisotropía y las regiones de baja densidad que a menudo se encuentran en las incrustaciones de codificadores crudos, el marco emplea un flujo normalizador invertible ($F_\phi$). Este flujo mapea el espacio complejo de incrustaciones de programas a un espacio de prior gaussiano estructurado y convexo ($u \in \mathbb{R}^d$). La optimización se realiza mediante ascenso de gradiente dentro de este espacio de prior, asegurando que la trayectoria de búsqueda permanezca cerca de la variedad de heurísticas plausibles y válidas.
4. Decodificación mediante Prompts Suaves: Los vectores latentes optimizados se proyectan de nuevo en el espacio de entrada de un LLM congelado solo de decodificador utilizando un mapeador latente-a-prompt aprendido ($\phi_\omega$). Este mapeador genera "prompts suaves" continuos (incrustaciones de condicionamiento) que guían al LLM para sintetizar nuevo código heurístico ejecutable. El código generado se valida sintácticamente y se evalúa en instancias de referencia para actualizar el conjunto de datos.

El proceso general es iterativo: los programas semilla se codifican, se optimizan en el espacio de prior latente, se decodifican en nuevo código, se evalúan y se añaden al grupo de entrenamiento para refinar los modelos de suplantación y flujo.

Contribuciones Clave

• Descubrimiento Heurístico Continuo: El artículo introduce un cambio de paradigma desde la búsqueda evolutiva a nivel de token discreto hacia la optimización continua sobre representaciones de programas aprendidas, permitiendo el uso de métodos basados en gradiente para el diseño heurístico.
• Búsqueda Regularizada por Flujos: Demuestra la necesidad de utilizar flujos normalizadores para mapear incrustaciones de programas a un prior estructurado. Esta regularización evita que la búsqueda se desvíe hacia regiones inválidas del espacio latente, mejorando significativamente la tasa de éxito del código generado en comparación con la optimización directa en el espacio de incrustación crudo.
• Suplantación Basada en Clasificación: El uso de un modelo de suplantación de clasificación por pares proporciona una señal de aprendizaje estable para el ascenso de gradiente, evitando la fragilidad asociada con la regresión de puntuaciones absolutas en entornos de evaluación ruidosos.
• Condicionamiento mediante Prompts Suaves: El marco utiliza un mapeador aprendible para traducir vectores latentes en prompts suaves, permitiendo la dirección de un LLM congelado sin modificar sus parámetros internos.

Resultados Experimentales

El marco LHS se evaluó en cuatro tareas de optimización combinatoria: TSP, Problema de Enrutamiento de Vehículos con Capacidad (CVRP), Problema de la Mochila (KSP) y Empaquetado en Línea (OBP).

• Rendimiento: En tareas de enrutamiento (TSP y CVRP), LHS logró un rendimiento de vanguardia, superando consistentemente a las líneas base evolutivas discretas (FunSearch, EoH, ReEvo) y a los enfoques basados en MCTS. Por ejemplo, en TSP-200, LHS alcanzó un objetivo de 12.49, superando a ReEvo (12.58) y EoH (13.15).
• Eficiencia: LHS demostró una eficiencia de tiempo de ejecución competitiva o superior. En los experimentos de TSP, LHS requirió significativamente menos tiempo (por ejemplo, 4.86s para TSP-200) en comparación con ReEvo (29.61s) mientras lograba mejores resultados.
• Estudios de Ablación:
  • Sin Flujo: Eliminar el flujo normalizador y optimizar directamente en el espacio de incrustación crudo resultó en una caída significativa en la tasa de éxito del código generado (61% vs. 74%), confirmando el papel del flujo en la estabilización de la búsqueda.
  • Sin Gradiente: Reemplazar el ascenso de gradiente con una interpolación simple produjo una alta validez (86%) pero una capacidad de optimización deficiente (peores puntuaciones de objetivo), destacando la necesidad de la señal de gradiente para descubrir heurísticas de alta calidad.
• Generalización: El método mostró una fuerte generalización cruzada por tamaño, funcionando bien en tamaños de instancia (por ejemplo, TSP-100, TSP-200) que eran más grandes que aquellos utilizados durante la fase de búsqueda.

Significado y Afirmaciones

Los autores afirman que LHS ofrece una alternativa metodológica complementaria a los enfoques evolutivos discretos existentes. Al tratar los programas como vectores latentes continuos, el marco permite una navegación sistemática del espacio de diseño heurístico mediante información de gradiente, manteniendo al mismo tiempo el rigor de la evaluación basada en ejecución.

El artículo enfatiza que la optimización continua es un complemento poderoso para la búsqueda discreta, capaz de lograr objetivos superiores dentro de presupuestos de evaluación fijos. Sin embargo, los autores permanecen modestos respecto a las limitaciones, señalando que la eficacia de LHS está fundamentalmente ligada a la calidad del modelo de suplantación y al corpus de entrenamiento inicial. Reconocen que pasos de optimización demasiado agresivos pueden empujar a los candidatos fuera de la variedad de código ejecutable, sugiriendo que el trabajo futuro debería explorar la hibridación de LHS con operadores evolutivos discretos para equilibrar la exploración global con el refinamiento local. El marco se presenta como un paso hacia una pipeline más diferenciable para el diseño automatizado de algoritmos, particularmente efectivo en escenarios que involucran búsquedas repetidas en tareas relacionadas donde el costo de la generación inicial de datos puede amortizarse.