Code World Models for Parameter Control in Evolutionary Algorithms

Este trabajo demuestra que los Modelos Mundiales de Código (CWMs) permiten que un LLM sintetice un simulador de la dinámica de un optimizador evolutivo a partir de trayectorias subóptimas para controlar su parámetro de fuerza de mutación, logrando un rendimiento superior a las líneas base y a la planificación óptima en diversos problemas de optimización combinatoria estocástica.

Lo esencial

Imagina que tienes un jardinero robot (un algoritmo) cuya misión es encontrar la flor más hermosa en un jardín gigante y lleno de trampas. Este robot tiene una herramienta especial: puede cambiar el tamaño de su "poda" (llamado parámetro $k$). Si poda muy poco, avanza lento; si poda demasiado, puede cortar ramas vitales y retroceder.

El gran problema es: ¿Cómo sabe el robot cuándo cambiar el tamaño de su poda?

Los jardineros tradicionales usan reglas fijas (como "si no avanzas, poda menos"). Pero en jardines complejos y engañosos, estas reglas fallan estrepitosamente.

Aquí es donde entra la magia de este paper. Los autores no programaron al robot con reglas nuevas. En su vez, le dieron un Libro de Recetas Inteligente (un modelo de lenguaje o LLM) y le dijeron: "Mira cómo otros robots (aunque no fueran perfectos) intentaron podar este jardín. Escribe tú mismo un manual de instrucciones que prediga qué pasará si cambiamos el tamaño de la poda".

La Analogía: El "Simulador de Sueños"

Aquí está el proceso explicado con una metáfora cotidiana:

1. La Colección de Historias (Entrenamiento):
   Imagina que grabas 200 videos de jardineros novatos intentando arreglar el jardín. Algunos cortan mucho, otros poco. Ninguno es perfecto, pero todos dejan un rastro.

   • En el paper: Recogen trayectorias de un algoritmo que prueba diferentes tamaños de poda.

2. El Escritor Mágico (El LLM):
   Le muestras estos videos a un escritor muy inteligente (la IA). No le das la solución, solo le dices: "Lee estas historias y escribe un pequeño programa de Python que actúe como un simulador".

   • La magia: El escritor no solo copia los videos. Entiende la lógica del jardín. Escribe un código que dice: "Si el jardín está en este estado y cortas 3 ramas, hay un 80% de probabilidad de que mejore, pero si cortas 10, probablemente te caerás al vacío".
   • Este código es el Modelo de Mundo (CWM). Es como si el robot pudiera soñar o simular el futuro antes de actuar.

3. El Planificador (La Ejecución):
   Ahora, el robot real usa ese "simulador de sueños" escrito por la IA. Antes de cada corte, piensa: "Si pruebo con una poda de tamaño 2, ¿qué pasará? ¿Y si pruebo con 5?". Elige la opción que el simulador le dice que es mejor.

¿Por qué es tan impresionante?

El paper prueba esto en cuatro tipos de "jardines" (problemas matemáticos):

• Jardines Suaves (LeadingOnes y OneMax): Aquí, las reglas tradicionales funcionan bien. Pero el robot con el "simulador de sueños" aprende a podar casi tan bien como un experto teórico, sin que nadie le haya enseñado la teoría. Solo aprendió viendo a otros intentar.
• El Jardín Engañoso (Jumpk): Este es el truco. Es un jardín con un "valle" falso. Si el robot se acerca a la cima y no ve progreso, los jardineros tradicionales se asustan y reducen su poda (hacen cortes más pequeños), lo cual es un error fatal porque necesitan un corte grande y preciso para saltar el valle.
  • El resultado: Los jardineros tradicionales fallan el 100% de las veces. El robot con el "simulador de sueños" acierta el 100% de las veces. ¿Por qué? Porque su simulador le dijo: "Oye, aquí no sirve reducir el corte. Necesitas un golpe grande y preciso".
• El Jardín Caótico (NK-Landscape): Aquí no hay reglas matemáticas claras, es puro caos. La IA no puede usar fórmulas. En su lugar, le damos una tabla de estadísticas ("cuando el jardín está en este estado, un corte grande suele funcionar"). La IA escribe un código que usa esa tabla como mapa. ¡Funciona mejor que cualquier otra estrategia!

La Gran Ventaja: Eficiencia y Transparencia

Imagina que quieres entrenar a un robot con aprendizaje automático tradicional (como un DQN). Necesitas que el robot intente y falle miles de veces en tiempo real, gastando mucha energía y tiempo, y al final, el robot es una "caja negra": nadie sabe por qué tomó esa decisión.

• El enfoque de este paper:
  • Ahorro: Necesita 200 intentos "offline" (fuera de línea) en lugar de 500 intentos en vivo.
  • Transparencia: El resultado no es una red neuronal oscura, es un código Python legible. Puedes leer el "simulador" y entender exactamente qué lógica está usando. Es como tener un manual de instrucciones escrito por un experto, en lugar de un cerebro mágico que no puedes abrir.

En resumen

Este paper demuestra que podemos usar la Inteligencia Artificial no para reemplazar al experto, sino para escribirle el manual de instrucciones.

En lugar de darle al algoritmo una regla fija, le pedimos a una IA que observe el comportamiento pasado, entienda la lógica del problema y escriba un pequeño programa que le diga al algoritmo cómo comportarse en el futuro.

Es como si le pidieras a un chef experto que, tras ver a varios aprendices cocinar, escribiera una receta perfecta para un plato nuevo. El resultado es un chef (el algoritmo) que cocina mejor que nadie, con menos ingredientes (datos) y con una receta que cualquiera puede leer y entender.

Resumen técnico

Resumen Técnico: Modelos de Mundo de Código para el Control de Parámetros en Algoritmos Evolutivos

1. El Problema

El control adaptativo de parámetros es un desafío fundamental en la computación evolutiva. Específicamente, para el algoritmo (1+1)-RLS$_k$ (que invierte exactamente $k$ bits por paso), la pregunta crítica es: ¿qué valor de $k$ (fuerza de mutación) se debe utilizar en cada paso?

• En paisajes unimodales (como LeadingOnes y OneMax), las políticas óptimas son conocidas, pero en paisajes complejos y engañosos (como Jump$_k$ o NK-Landscape), no existen fórmulas cerradas para la política óptima.
• Los enfoques adaptativos existentes (como las reglas multiplicativas de actualización) suelen fallar en paisajes engañosos porque reducen $k$ durante el estancamiento, lo cual es contraproducente cuando se necesita aumentar la fuerza de mutación para cruzar un "valle" de fitness.
• Los métodos de Aprendizaje por Refuerzo (RL) tradicionales, como DQN, a menudo requieren muchas muestras y luchan para generalizar en entornos donde las transiciones críticas (cruce de valles) son raras.

2. Metodología: Modelos de Mundo de Código (CWM)

Los autores extienden el concepto de Code World Models (CWMs), originalmente diseñado para juegos deterministas, hacia la optimización combinatoria estocástica. En lugar de usar redes neuronales como modelos del mundo, utilizan un LLM (Large Language Model) para sintetizar un programa de Python ejecutable que simula la dinámica del optimizador.

El flujo de trabajo consta de tres etapas:

1. Recolección de Trayectorias: Se ejecuta el algoritmo (1+1)-RLS$_k$ con diversas políticas (aleatorias, fijas, decrecientes) para generar 200-300 trayectorias de datos. Crucialmente, ninguna de estas políticas utiliza conocimiento óptimo (oráculo) ni el valor del parámetro del problema ($k_{jump}$).
2. Síntesis del CWM: Un LLM (Claude Sonnet 4) recibe una descripción del problema y muestras de las trayectorias. El LLM genera una clase SynthesizedCWM en Python con métodos para:
   • Predecir el siguiente estado (predict_next_state).
   • Evaluar el estado (evaluate_state).
   • Obtener acciones legales.
   • Innovación: Para problemas difíciles (Jump$_k$, NK), el prompt se enriquece con tablas de transición empíricas (probabilidad de mejora y cambio medio de fitness) en lugar de solo descripciones matemáticas, permitiendo que el modelo aprenda la dinámica estocástica sin una fórmula cerrada.
3. Planificación Greedy (Voraz): Durante la ejecución en línea, en cada paso, el planificador consulta al CWM sintetizado para evaluar todos los valores posibles de $k$. Se selecciona el $k^*$ que maximiza la mejora esperada en un solo paso de visión hacia adelante (lookahead). No se requiere búsqueda Monte Carlo (MCTS); la planificación greedy es suficiente.

3. Contribuciones Clave

1. Extensión a Optimización Estocástica: Adaptación de CWMs desde juegos deterministas a problemas de optimización combinatoria estocástica, demostrando que la planificación greedy de un paso es suficiente en estos entornos.
2. Desempeño en Paisajes Engañosos: Logro de una tasa de éxito del 100% en el problema Jump$_k$, donde todas las líneas base adaptativas (incluyendo reglas multiplicativas y heurísticas de estancamiento) fallan (0% de éxito).
3. Independencia del Oráculo: El CWM infiere la estrategia correcta (aumentar $k$ en el borde del valle) sin haber visto nunca trayectorias óptimas ni conocer el valor de $k_{jump}$ durante el entrenamiento.
4. Superioridad sobre RL Tradicional: El CWM supera a DQN en eficiencia de muestras (200 trayectorias offline vs. 500 episodios online), tasa de éxito y capacidad de generalización.
5. Generalización sin Re-entrenamiento: El modelo sintetizado en Jump$_k$ con $k=2$ generaliza exitosamente a $k=3$ (78% de éxito) sin reconfiguración, algo que DQN no logra.

4. Resultados Experimentales

Los experimentos se realizaron con $n=50$ en cuatro benchmarks:

• LeadingOnes y OneMax (Paisajes Unimodales):

  • El CWM-greedy alcanza un rendimiento dentro del 6% de la política óptima teórica en LeadingOnes y dentro del 2% en OneMax, superando significativamente a las reglas adaptativas estándar.
  • El modelo logra recuperar la estructura de la política óptima (rampas suaves o "acantilados" abruptos) solo a partir de datos subóptimos.

• Jump$_k$ (Paisaje Engañoso):

  • Resultado principal: CWM-greedy logra 100% de tasa de éxito con un promedio de 1,342 pasos.
  • Todas las líneas base adaptativas (EA$\alpha$, fifth_rule, self-adjusting) tienen un 0% de éxito porque reducen $k$ al estancarse, impidiendo cruzar el valle.
  • Comparación con DQN: DQN logra solo un 58% de éxito y sufre de sobreajuste al ruido de exploración ($\epsilon$-greedy), fallando al evaluar sin ruido. El CWM, al codificar la estructura en código, es inmune a este problema.

• NK-Landscape (Sin Modelo Matemático):

  • En un entorno rugoso sin modelo cerrado, el CWM utiliza únicamente una tabla de transición empírica como entrada.
  • Supera a todos los baselines (36.94 vs 36.32 de fitness medio) en 15 instancias independientes.
  • Muestra que los resúmenes de datos estructurados pueden sustituir a los modelos matemáticos cerrados.

• Generalización:

  • El modelo entrenado en $n=50$ mantiene su ventaja en $n=100$ y $n=200$.
  • En Jump$_k$, el modelo entrenado con $k=2$ logra un 78% de éxito en $k=3$, mientras que DQN y las reglas adaptativas caen al 0%.

5. Significado y Conclusión

El trabajo demuestra que los LLMs pueden actuar como sintetizadores de modelos del mundo efectivos para la optimización evolutiva.

• Eficiencia de Muestras: Requiere significativamente menos datos que el RL basado en gradientes (DQN) y produce un programa de Python auditable en lugar de pesos de red opacos.
• Complemento a la Teoría: El enfoque no reemplaza el análisis formal, sino que lo complementa. Traduce la experiencia estadística en heurísticas explícitas y ejecutables, permitiendo la planificación analítica incluso en paisajes donde no existen modelos cerrados.
• Robustez: La síntesis es estable a través de múltiples ejecuciones independientes, capturando comportamientos críticos (como el cruce de valles) de manera fiable.

En resumen, el uso de Code World Models representa un avance significativo en el control de parámetros adaptativo, ofreciendo una solución robusta, eficiente y generalizable para problemas de optimización que desafían a los métodos tradicionales y al aprendizaje por refuerzo estándar.