Una mirada a las híper-heurísticas

Por Jorge M. Cruz-Duarte, Iván M. Amaya Contreras y José C. Ortiz Bayliss
Artículo de divulgación científica

¿Cómo puedo calendarizar apropiadamente un conjunto de operaciones? Este problema de optimización combinatoria es común en las industrias, particularmente en la industria manufacturera. Allí, se busca gestionar los activos para completar una serie de tareas de forma eficiente.

Aunque estos problemas son simples en su descripción, el sinnúmero de posibles soluciones hace de éstos un verdadero reto en aplicaciones prácticas, incluso en las más simples. Por ejemplo, si asumimos la condición más sencilla tendremos n!^m posibles soluciones a explorar, siendo n el número de tareas a realizar y m el número de máquinas disponibles en la planta. Si una industria desea programar tres tareas a realizarse en tres máquinas, aplicando la expresión anterior tenemos: (n!)^m = (3!)^3 = (3×2×1)^3 = 216 posibles soluciones. Por tanto, existirán “solamente” 216 soluciones posibles, que deben ser analizadas para encontrar la mejor de ellas. Si incrementamos el número de trabajos a cinco, el número de soluciones asciende a 1’728.000. Note que, aun así, esto no es nada comparado con las cifras reales de una industria. La siguiente figura muestra cómo crece el número de combinaciones.

Para este tipo de problemas es impensable probar todas las opciones. Por ello, los investigadores han propuesto una gran variedad de métodos desde hace más de 70 años, entre ellos las heurísticas. Una heurística se puede definir como una regla (procedimiento) que se realiza una o varias veces para cumplir con una tarea. Las heurísticas suelen ser intuitivas. Para comprender mejor esto, consideremos el problema de organizar la despensa en un compartimento del refrigerador. Nuestra heurística consiste en guardar primero el objeto más grande. Al repetir este proceso varias veces, habremos guardado todas las compras. ¡Hemos cumplido el objetivo! Pero… es posible que queden espacios vacíos, muy pequeños para el siguiente artículo que se iba a guardar, pero adecuados para otros más pequeños. Así, las heurísticas son fáciles de implementar, pero la calidad de sus soluciones no está garantizada.

Una heurística se puede definir como una regla o procedimiento que se realiza una o varias veces para cumplir con una tarea

Para reducir dicha incertidumbre, los expertos se han planteado diversas propuestas, entre ellas, las híper-heurísticas (HHs). Éstas son heurísticas controladas por otra heurística: una idea simple y bastante efectiva. Para entenderlas mejor utilizaremos la siguiente analogía: Una chef tiene una libreta con diversas recetas, algunas de revistas de cocina y otras propias. Dicha chef tiene el objetivo de preparar un platillo exquisito. Para lograrlo, elegirá algunos elementos de diferentes recetas y creará una nueva. Al culminar, tendrá un platillo que evaluar. Para ello pedirá ayuda a algunos comensales, con diferentes gustos, quienes darán su veredicto. Es probable que al primer intento las cosas no salgan tan bien, aunque depende de la experticia de nuestra chef. Entonces, ella ajustará la receta inicial con base en otras recetas de la libreta y su experiencia previa. El proceso se repite varias veces hasta dar con un veredicto positivo y unánime de los comensales.

Pongamos en contexto el ejemplo anterior: Las heurísticas son acciones por realizar; entonces, corresponden a cada anotación (paso) en la libreta. Así, la nueva receta será la híper-heurística. ¿Qué papel desempeñan la chef y los comensales? La primera representa a un algoritmo de entrenamiento cuyo “razonamiento” permite evaluar cómo modificar un conjunto de acciones. Este algoritmo puede ser un método un poco más elaborado como una metaheurística o un algoritmo de inteligencia artificial. Los comensales representan las características del problema, y al tener diferentes gustos evalúan el platillo bajo diferentes puntos de vista, por ejemplo, presentación, consistencia, aroma o sabor. Estas características son fundamentales para la obtención del mejor resultado en la resolución de un problema. Dicho rol se hace más importante si, en vez de evaluar la solución al final, lo hacemos después de realizar cada acción. Además, es pertinente mencionar que cada intento en el proceso culinario lo asociamos a una iteración del proceso de optimización.

El tamaño del problema y el desempeño de las HHs

Ahora bien, ¿qué tanto puede mejorar el ejemplo anterior? ¿No retrasará demasiado la resolución de un problema? Pues bien, justamente estas preguntas fueron resueltas en nuestro estudio “Influence of Instance Size on Selection Hyper-Heuristics for Job Shop Scheduling Problems”. En él analizamos el efecto que tiene el tamaño del problema en el desempeño de las HHs durante la solución de problemas de calendarización. Recordemos que el tamaño de estos problemas está dado por el número de máquinas y tareas a realizar. Para ello, implementamos una metaheurística llamada Recocido Simulado (SA, por sus siglas en inglés) como método de entrenamiento (chef) para las HHs.

El SA está inspirado en el proceso de templado del acero, donde se eleva su temperatura a un valor máximo y luego se enfría lentamente para promover la organización de sus átomos en estructuras cristalinas. Macroscópicamente, se evidencia en acero de mayor dureza. Una vez implementado SA, variamos sistemáticamente el tamaño de los problemas de entrenamiento y de ejecución, además del número de iteraciones para encontrar la solución. ¿Por qué entrenamiento y ejecución? Bueno, los métodos de inteligencia artificial (de forma análoga a cualquier cerebro animal) deben ser entrenados para ejecutar una tarea. Luego de varios procesos de entrenamiento y ejecución con diferentes escenarios, observamos que el mejor desempeño de las HHs se encuentra cuando entrenamos y ejecutamos con problemas del mismo tamaño, pero con más iteraciones. El tiempo requerido para esto fue excesivamente alto, ya que esta es la opción ganar-o-ganar. Esta inferencia fue sólo una confirmación de lo que, por lógica, podría suceder. Sin embargo, también notamos que el tiempo de entrenamiento se puede reducir si disminuimos el número de iteraciones, pero con el efecto secundario de que el desempeño de las HHs fue dramáticamente perjudicado. No obstante, pudimos apreciar que, si utilizamos el máximo número de iteraciones y problemas pequeños para entrenar las HHs, el desempeño solo es ligeramente afectado mientras el tiempo de entrenamiento se reduce significativamente.

La explicación a este fenómeno, creemos, yace en la naturaleza de las características y cómo éstas describen el problema. Así las cosas, mejores características o herramientas para describir el problema simplificarán naturalmente el proceso de solución a través de las híper-heurísticas.

Esta idea, aunque parezca sencilla, no se había probado antes para este tipo de problemas. Al reducir el tiempo de entrenamiento, podemos emplear el tiempo ahorrado en mejorar las heurísticas, el método de entrenamiento y las características, por ejemplo. Por el momento, este trabajo sirvió como punto de partida para llevar estas inferencias a otros problemas comunes en áreas como la producción industrial, el diseño de piezas en ingeniería, la administración de recursos, etc.; todas relacionadas con la Industria 4.0. Actualmente, en el Grupo de Investigación con Enfoque Estratégico en Sistemas Inteligentes (GIEE-SI), de la Escuela de Ingeniería y Ciencias (EIC), seguimos investigando éste y otros temas, relacionados con optimización en diversas aplicaciones industriales.

¿Quieres saber más?

Para mayor información sobre este trabajo, te invitamos a consultar desde cualquier red institucional:

F. Garza-Santisteban et al., “Influence of Instance Size on Selection Hyper-Heuristics for Job Shop Scheduling Problems,” 2019, IEEE Symposium Series on Computational Intelligence (SSCI), Xiamen, China, 2019, pp. 1708-1715. https://doi.org/10.1109/SSCI44817.2019.9002653

Los autores

Jorge M. Cruz-Duarte es Doctor en Ingeniería Eléctrica. Actualmente es Investigador Posdoctoral del Grupo de Investigación en Sistemas Inteligentes, de la Escuela de Ingeniería y Ciencias, del Tec de Monterrey. Pertenece al Sistema Nacional de Investigadores, Nivel I. jorge.cruz@tec.mx

Iván M. Amaya-Contreras es Doctor en Ingeniería, área Ingeniería Electrónica. Actualmente es Profesor Investigador del departamento de Computación y está adscrito al Grupo de Investigación en Sistemas Inteligentes, de la Escuela de Ingeniería y Ciencias, del Tec de Monterrey. Pertenece al Sistema Nacional de Investigadores, Nivel I. iamaya2@tec.mx

José C. Ortiz Bayliss es Doctor en Tecnologías de Información y Comunicaciones. Actualmente es Profesor Investigador del departamento de Computación y está adscrito al Grupo de Investigación en Sistemas Inteligentes, de la Escuela de Ingeniería y Ciencias, del Tecnológico de Monterrey. Pertenece al Sistema Nacional de Investigadores, Nivel I. jcobayliss@tec.mx