Resumen Técnico: ImprovEvolve: Basin-Hopping se encuentra con la búsqueda evolutiva guiada por LLM

Declaración del Problema

El artículo aborda el desafío de utilizar Modelos de Lenguaje Extensos (LLMs) para resolver problemas complejos de optimización matemática, particularmente aquellos con paisajes rugosos, no convexos y no suaves (por ejemplo, problemas de empaquetamiento, desigualdades funcionales y códigos esféricos). El trabajo previo como AlphaEvolve evolucionó programas monolíticos para producir soluciones candidatas directamente, pero los autores argumentan que este enfoque impone una carga cognitiva excesiva al LLM. El modelo debe diseñar simultáneamente un esquema de inicialización, una estrategia de búsqueda y criterios de terminación, lo que a menudo conduce a programas generados que dependen de rutinas estándar (como L-BFGS-B) que fallan al manejar eficazmente las restricciones específicas y la no convexidad del problema. En consecuencia, las soluciones generadas por LLM mezclan la intuición matemática con heurísticas en lugar de resolver rigurosamente la tarea de optimización, y tienen dificultades para generalizarse a tamaños de problemas no vistos o para mejorar las soluciones construidas por expertos.

Metodología: ImprovEvolve

Los autores proponen ImprovEvolve, una alternativa algorítmica que descompone la tarea de optimización en subrutinas especializadas, integrando eficazmente técnicas de optimización global de Basin-Hopping con la búsqueda evolutiva guiada por LLM.

Descomposición Central

En lugar de evolucionar una única función que devuelva una solución, ImprovEvolve evoluciona una clase de Python que implementa tres operadores distintos:

1. generate_config(seed): Inicializa una solución factible a partir de una semilla aleatoria.
2. improve(x): Realiza la optimización local para refinar una configuración $x$, devolviendo una solución $x'$ con un fitness al menos tan bueno como $x$.
3. perturb(x, \sigma): Explora aleatoriamente el espacio de búsqueda a una intensidad específica $\sigma$.

Esquema de Validación (Basin-Hopping)

La clase evolucionada se utiliza dentro de un esquema de validación de dos etapas (Algoritmo 1) que imita el Monotonic Basin-Hopping ($T=0$):

• Etapa A (Inicialización): Se generan múltiples configuraciones iniciales y se refinan mediante improve. Se selecciona el mejor resultado como el punto de partida $x^*$.
• Etapa B (Búsqueda Iterativa): El algoritmo realiza $R$ rondas de perturbación y mejora. En cada ronda, la intensidad de la perturbación $\sigma$ decae geométricamente de $\sigma_{max}$ a $\sigma_{min}$. El proceso involucra:
  1. Perturbar la solución actual más óptima: $x' = \text{perturb}(x^*, \sigma)$.
  2. Refinar la solución perturbada: $x'' = \text{improve}(x')$.
  3. Aceptación Monotónica: $x^*$ se actualiza a $x''$ solo si el fitness mejora estrictamente.

Esta descomposición desplaza la tarea del LLM de diseñar un optimizador de extremo a extremo a codificar heurísticas específicas del dominio para la inicialización, la búsqueda local y la exploración, que luego son orquestadas por el marco clásico de Basin-Hopping.

Marco Evolutivo

El sistema utiliza el marco GigaEvo con un bucle MAP-Elites. El fitness de un programa candidato se determina ejecutando el esquema completo de validación de dos etapas sobre este. El LLM (Gemini 3 Pro para la inicialización, Gemini 3 Flash para la evolución) muta el código de la clase Improv, guiado por la retroalimentación de fitness y la información de linaje.

Contribuciones Clave y Resultados

1. Empaquetamiento Hexagonal (HEX $n$)

• Tarea: Empaquetar $n$ hexágonos regulares unitarios en el hexágono regular envolvente más pequeño.
• Resultados:
  • Para $n=11$, ImprovEvolve descubrió un nuevo estado del arte (SOTA) de empaquetamiento con un lado de longitud $L=3.9245$, mejorando el $3.9301$ de AlphaEvolve y el récord humano previo de $3.9434$.
  • El programa evolucionado se generalizó a tamaños de problemas no vistos ($11 \le n \le 24$) sin re-evolución, encontrando nuevos empaquetamientos SOTA para $n=12, 15, 16$.
  • ImprovEvolve+E: Con ediciones humanas menores (cambio de optimizadores, ajuste de pesos de penalización), el sistema encontró nuevos empaquetamientos SOTA para $n=14, 17, 23$ y proporcionó empaquetamientos estructurados para $n=25-30$ donde no existían resultados previos.
• Comparación: ImprovEvolve superó significativamente al baseline de GigaEvo (enfoque monolítico), el cual falló al generalizarse a $n > 11$ debido a errores de traslape.

2. Segunda Desigualdad de Autocorrelación (ACI 2)

• Tarea: Encontrar una función no negativa $f$ que maximice la constante $C_2$ en la desigualdad $\|f * f\|_2^2 \le C_2 \|f * f\|_1 \|f * f\|_\infty$.
• Resultados:
  • El programa base de ImprovEvolve logró $C(f) = 0.9512$, superando los baselines de código abierto pero quedando por debajo del $0.96102$ de AlphaEvolve.
  • ImprovEvolve+E: Al reanudar la optimización desde la solución de AlphaEvolve y aplicar ediciones guiadas por humanos (escalado progresivo de resolución hasta 1.6M de pasos, eliminando el recorte inferior), el sistema logró un nuevo límite inferior SOTA de $C(f) = 0.96258$.
• Significado: Esto demuestra la capacidad del marco para refinar soluciones de alta calidad ya existentes proporcionadas por expertos u otros modelos, una capacidad con la que los enfoques monolíticos de LLM tienen dificultades.

3. Códigos Esféricos

• Tarea: Disponer $N$ puntos en una esfera unitaria $S^{d-1}$ para minimizar el producto interno máximo (coherencia).
• Resultados:
  • Evaluado en 90 configuraciones diversas del catálogo de Cohn ($d \in [8, 16]$).
  • ImprovEvolve++ (un mejorador general calibrado evolucionado a través de múltiples dimensiones) redujo estrictamente el coseno máximo para 53 de las 90 configuraciones, logrando una mejora relativa media de 0.1765%.
  • Esto representa una mejora de 2.35$\times$ sobre el mejor programa anterior (ImprovEvolve).
  • Los diagnósticos (UMAP y distribuciones de producto interno) mostraron que ImprovEvolve++ realizó reordenamientos estructurales globales, moviendo los puntos hacia regiones distintas del espacio de búsqueda, mientras que otras variantes solo realizaron ajustes locales.

Robustez Estadística

Los estudios de múltiples ejecuciones confirmaron que las mejoras de ImprovEvolve son estadísticamente significativas ($p < 0.05$) en comparación con el baseline de GigaEvo, validando que la descomposición modular ofrece una ventaja reproducible sobre el aprendizaje de un optimizador monolítico.

Significado y Reivindicaciones

El artículo sostiene que descomponer las tareas de optimización en subproblemas modulares es un principio crítico para el descubrimiento guiado por LLM.

• Reducción de la Carga Cognitiva: Al separar la inicialización, la mejora local y la perturbación, el LLM se enfoca en codificar la estructura matemática y las heurísticas en lugar de orquestar todo el proceso de búsqueda.
• Colaboración Humano-LLM: La interfaz modular permite a los expertos en el dominio aplicar ediciones dirigidas y mínimas (por ejemplo, cambiar optimizadores, ajustar cronogramas de resolución) para aumentar significativamente el rendimiento, cerrando la brecha entre el código generado por LLM y el ajuste de nivel experto.
• Generalización: La interfaz improve/perturb permite que los programas evolucionados se generalicen a tamaños de problemas no vistos y que reanuden la optimización a partir de soluciones proporcionadas por expertos, superando la fragilidad de los programas monolíticos de extremo a extremo.

Los autores posicionan este trabajo como un paso hacia la escala del descubrimiento matemático impulsado por LLM, sugiriendo que los sistemas futuros deberían combinar tales descomposiciones personalizadas con flujos de trabajo agénticos que decidan autónomamente qué módulos refinar. El artículo mantiene la modestia respecto a la generalizabilidad más amplia, señalando que la evaluación cuantitativa actualmente se limita a estos tres dominios de optimización específicos.