Surrogate-Assisted Genetic Programming with Rank-Based Phenotypic Characterisation for Dynamic Multi-Mode Project Scheduling

Este artículo propone un algoritmo de Programación Genética asistido por modelos sustitutos que utiliza una caracterización fenotípica basada en rangos para reducir significativamente el costo computacional y encontrar reglas heurísticas de alta calidad más rápido en la resolución del problema de programación dinámica de proyectos con recursos y modos múltiples.

Lo esencial

Imagina que eres el director de una obra de construcción gigante. Tienes cientos de tareas (poner ladrillos, instalar ventanas, pintar), cada una puede hacerse de varias formas (rápida pero cara, o lenta pero barata), y tienes recursos limitados (pocos grúas, pocos albañiles). Además, el tiempo que tarda cada tarea es una incógnita hasta que la empiezas: a veces llueve y se retrasa, a veces el material llega antes.

Tu trabajo es decidir en tiempo real: ¿Qué tarea hago ahora? ¿Con qué método? ¿Qué grupo de tareas puedo hacer en paralelo?

Hacer esto manualmente es imposible. Aquí es donde entra la Inteligencia Artificial, específicamente un tipo llamado Programación Genética (PG). Imagina que la PG es como un "jardín de ideas". Creas miles de reglas diferentes (como "si hay poca madera, haz la tarea X") y las dejas "evolucionar". Las reglas que funcionan bien se reproducen y mezclan; las que fallan mueren.

El Problema: La Prueba y Error es Muy Lenta

El problema con este "jardín de ideas" es que para saber si una regla es buena, tienes que simular toda la obra de construcción una y otra vez. Es como si tuvieras que construir la obra completa en un videojuego solo para ver si tu regla de "pintar primero" funcionaba. Esto consume muchísimo tiempo y energía de computadora.

La Solución: El "Oráculo" (Modelo Sustituto)

Los autores de este paper (Yuan Tian y su equipo) se preguntaron: "¿Podemos predecir qué tan buena es una regla sin tener que construir toda la obra?".

Para ello, crearon un Modelo Sustituto (o "Oráculo"). Es como tener a un experto que, en lugar de ver la obra completa, solo mira un resumen rápido de la regla y te dice: "Oye, esta regla parece muy prometedora, no hace falta que la simulemos todo el proceso".

Pero, ¿cómo le explica el experto a la computadora qué hace la regla? Aquí es donde entra la gran innovación del paper: la Caracterización Fenotípica Basada en Rangos.

La Analogía Creativa: El "Ranking" de los Candidatos

Imagina que en cada momento de la obra, tienes una lista de 10 tareas que podrías hacer.

• El método antiguo (usado en otros problemas) era como decir: "La regla elegió la tarea número 3". Pero eso no cuenta por qué la eligió. ¿La eligió porque era la 3ª mejor, o porque la 1ª y la 2ª estaban ocupadas? Se perdía mucha información.

• El nuevo método de este paper es como pedirle a la regla que ordene a todos los candidatos del 1 al 10.

  • La regla dice: "La tarea A es mi favorita (1), la B es la segunda (2), la C es la tercera (3)...".
  • Luego, la regla también elige un grupo de tareas para hacer juntas.
  • La computadora toma esta lista de preferencias (el "ranking") y la convierte en una huella digital numérica (un vector).

Es como si cada regla tuviera un "DNI" que dice exactamente cómo piensa y prioriza las tareas. Con este DNI, el "Oráculo" (el modelo sustituto) puede comparar reglas nuevas con reglas que ya conoce y decir: "Esta nueva regla piensa igual que la regla #50, que fue muy buena, así que esta nueva también será buena".

¿Qué lograron?

1. Ahorro de Tiempo: Al usar este "Oráculo", la computadora puede descartar las malas reglas muy rápido, sin gastar tiempo en simulaciones completas. Solo simula en profundidad las reglas que el Oráculo considera prometedoras.
2. Mejores Resultados: Descubrieron reglas de gestión de obras mucho más inteligentes y eficientes que las que se encontraban con los métodos tradicionales, y lo hicieron mucho más rápido.
3. El Equilibrio Justo: Probaron generar diferentes cantidades de "hijos" (nuevas reglas) para filtrar. Descubrieron que generar un poco más de candidatos (el doble que el tamaño original) y filtrarlos con el Oráculo era el punto dulce: suficiente variedad para encontrar ideas geniales, pero no tanta que el Oráculo se confundiera.

En Resumen

Este paper es como inventar un filtro de calidad ultra-rápido para un proceso de diseño. En lugar de probar cada diseño de coche en una pista de carreras real (que es caro y lento), primero le pides al diseñador que te explique su lógica de priorización (¿qué pone primero: seguridad o velocidad?). Con esa explicación, un experto (el modelo sustituto) puede predecir si el coche será rápido sin encender el motor.

Gracias a esto, ahora podemos encontrar las mejores formas de gestionar proyectos complejos y dinámicos en una fracción del tiempo que antes se necesitaba.

Resumen técnico

A continuación presento un resumen técnico detallado del artículo en español, estructurado según los puntos solicitados:

Título: Programación Genética Asistida por Surrogados con Caracterización Fenotípica Basada en Rangos para la Programación Dinámica de Proyectos Multi-Modo

1. El Problema: DMRCPSP

El artículo aborda el Problema de Programación de Proyectos con Restricciones de Recursos Multi-Modo Dinámico (DMRCPSP).

• Naturaleza del problema: Es una extensión del clásico problema de programación de proyectos (RCPSP) donde las actividades pueden ejecutarse en diferentes modos (con distintas duraciones y requisitos de recursos).
• Dinamismo: A diferencia de los entornos estáticos, en el DMRCPSP las duraciones exactas de las actividades son inciertas y solo se revelan durante la ejecución. Esto obliga a tomar decisiones en tiempo real (qué actividad ejecutar y en qué modo) a medida que avanza el estado del proyecto.
• Desafío computacional: Las reglas heurísticas evolucionadas mediante Programación Genética (GP) son efectivas para este tipo de toma de decisiones, pero su proceso evolutivo requiere un número masivo de evaluaciones de aptitud (fitness) basadas en simulaciones costosas. Esto limita la escalabilidad y la aplicabilidad práctica.

2. Metodología Propuesta

Los autores proponen un marco de Programación Genética Asistida por Surrogados (Surrogate-Assisted GP) para reducir el costo computacional. La metodología se basa en tres pilares principales:

• Esquema de Caracterización Fenotípica (PC) Basado en Rangos:

  • Se identifica que los métodos existentes de PC no son aplicables al DMRCPSP porque las reglas heurísticas involucran tanto la ordenación de actividades como la selección de grupos de actividades (subconjuntos), lo cual es complejo de mapear.
  • Innovación: Se diseña un nuevo esquema de PC que captura el comportamiento de las reglas heurísticas en situaciones de decisión específicas.
  • Mecanismo: Para cada individuo GP (que contiene dos árboles: una regla de ordenación y una regla de selección de grupos), se extraen vectores de decisión basados en los rangos que la regla asigna a las parejas "actividad-modo" elegibles y a los grupos de actividades elegibles.
  • Estos vectores de rangos se concatenan para formar un vector fenotípico único que representa el comportamiento del individuo sin necesidad de ejecutar la simulación completa.

• Modelo Surrogado (Estimación de Aptitud):

  • Se utiliza un modelo de vecino más cercano (nearest-neighbour) para estimar la aptitud de los descendientes no evaluados.
  • El modelo calcula la distancia de Manhattan entre el vector PC de un nuevo descendiente y los vectores PC de la población actual (cuyas aptitudes reales ya se conocen).
  • La aptitud estimada del nuevo individuo se asigna basándose en la aptitud real de su vecino más cercano en el espacio de vectores PC.
  • Nota importante: La base de datos del surrogado se reinicia en cada generación debido a la naturaleza estocástica de las simulaciones, lo que hace que las aptitudes de diferentes generaciones no sean directamente comparables.

• Flujo del Algoritmo (SKGGP):

  1. Se genera una población de descendientes intermedios (multiplicador $k$).
  2. Se calculan los vectores PC para estos descendientes.
  3. Se eliminan duplicados basados en el vector PC.
  4. El modelo surrogado estima la aptitud de los descendientes únicos.
  5. Se seleccionan los mejores descendientes según la estimación del surrogado para someterlos a la evaluación completa (simulación real).
  6. Se repite el ciclo evolutivo.

3. Contribuciones Clave

• Desarrollo de un Esquema PC Específico: La principal contribución teórica es la creación de un esquema de caracterización fenotípica basado en rangos, diseñado específicamente para manejar la complejidad de la selección de subconjuntos y la ordenación en el DMRCPSP, llenando un vacío en la literatura existente.
• Integración en GP Asistido por Surrogados: Se integra exitosamente este esquema en un algoritmo GP (denominado SKGGP), permitiendo la estimación de aptitud sin simulaciones completas para la mayoría de los candidatos.
• Análisis de Multiplicadores de Descendencia: Se estudia el impacto de generar diferentes cantidades de descendientes intermedios ($k = 1, 1.5, 2, 4$) para optimizar el equilibrio entre la exploración del espacio de búsqueda y la precisión del modelo surrogado.

4. Resultados Experimentales

Los experimentos se realizaron en escenarios con 200 actividades, 3 modos y 12 tipos de recursos, comparando el algoritmo propuesto (SKGGP) con el estado del arte (KGGP).

• Rendimiento Superior: Las variantes SKGGP (especialmente con $k=2$ y $k=4$) lograron encontrar reglas heurísticas de mayor calidad (menor makespan relativo) que el algoritmo base KGGP.
• Convergencia Acelerada: Las curvas de convergencia mostraron que SKGGP alcanza soluciones de alta calidad significativamente antes que KGGP.
• Ahorro de Presupuesto Computacional: El análisis de "presupuesto guardado" reveló que SKGGP puede alcanzar el mismo nivel de rendimiento que KGGP utilizando entre un 20% y un 40% menos de evaluaciones completas (simulaciones costosas).
• Precisión del Surrogado:
  • La precisión del modelo para seleccionar los mejores individuos disminuye a medida que aumenta el número de descendientes intermedios ($k$), cayendo de ~80-90% para $k=1.5$ a ~50-60% para $k=4$.
  • Sin embargo, incluso con $k=4$, la generación de descendientes extra permite reemplazar a los peores individuos originales, mejorando la calidad general de la población.
• Sobrecarga Computacional: El tiempo adicional requerido para la estimación del surrogado (cálculo de vectores PC y distancias) es marginal, representando solo entre 1/20 y 1/40 del tiempo de una evaluación completa.

5. Significado e Impacto

• Viabilidad Práctica: Este trabajo demuestra que es posible aplicar técnicas de GP evolutivo a problemas de programación de proyectos dinámicos y complejos en entornos donde el tiempo de cómputo es crítico, reduciendo drásticamente la carga de simulación.
• Generalización de Métodos: Proporciona una solución metodológica a la falta de esquemas de caracterización fenotípica para problemas de selección de subconjuntos en programación genética, lo cual podría inspirar soluciones similares en otros dominios de optimización combinatoria dinámica.
• Eficiencia Evolutiva: Confirma que la combinación de una caracterización fenotípica bien diseñada con modelos surrogados simples (como el vecino más cercano) puede guiar eficazmente la búsqueda evolutiva, permitiendo descubrir reglas heurísticas robustas con recursos computacionales limitados.

En conclusión, el artículo presenta un avance significativo en la automatización de la toma de decisiones en gestión de proyectos bajo incertidumbre, logrando un equilibrio óptimo entre la calidad de la solución y el costo computacional mediante una ingeniería de características fenotípicas innovadora.