Jose Ignacio Santos1
, María Pereda1,2,3,Virginia Ahedo1, José Manuel Galán1
1Universidad de Burgos, Departamento de Ingeniería de Organización, Escuela Politécnica Superior, Ed. A1, Avda. Cantabria s/n 09006, Spain
2 Universidad Politécnica de Madrid, Grupo de Investigación Ingeniería de Organización y Logística (IOL), Departamento de Ingeniería de Organización, Administración de Empresas, y Estadística. Escuela Técnica Superior de Ingenieros Industriales, C/ José Gutiérrez Abascal, 2, 28006 Madrid, Spain
3 Unidad Mixta Interdisciplinar de Comportamiento y Complejidad Social
(UMICCS), 28911 Leganés, Madrid, Spain
4 Grupo Interdisciplinar de Sistemas Complejos, Madrid, Spain
jisantos@ubu.es, maria.pereda@upm.es, vahedo@ubu.es, jmgalan@ubu.es
Keywords: Recocido simulado, optimización, recurso docente, NetLogo, mecanismos de descenso
Las técnicas metaheurísticas son un conjunto de algoritmos computacionales utilizados con frecuencia para encontrar soluciones satisfactorias a problemas de optimización combinatoria. La ubicuidad de este tipo de problemas (asignación, ordenación, selección, etc) y el propósito general de estos algoritmos ha convertido a las metaheurísticas en parte fundamental del currículo de muchos cursos de optimización en titulaciones de ingeniería y gestión.
Este tipo de algoritmos combinan estrategias de exploración en el espacio de soluciones con mecanismos para intensificar la búsqueda en zonas potencialmente prometedoras. Una de las técnicas metaheurísticas más populares es el recocido simulado. Se trata de un algoritmo basado en trayectorias que implementa un mecanismo de control para tratar de evitar quedarse atrapado en óptimos locales y, pese a su relativa sencillez, proporciona buenas soluciones en multitud de problemas, por lo que su uso está muy extendido.
El mecanismo de control del algoritmo sigue la estrategia de explorar en las fases iniciales de la búsqueda de soluciones, e intensificar cada vez más a medida que el proceso avanza. Está inspirado en la analogía del proceso termodinámico que tiene lugar en el tratamiento térmico de recocido en materiales metálicos, de ahí el nombre del algoritmo. Este tratamiento consiste en elevar la temperatura de un metal hasta la temperatura de recocido, mantener la temperatura durante un tiempo y después enfriarlo lentamente consiguiendo de esta forma reducir las tensiones y recuperar su estructura.
El recocido simulado implementa precisamente como mecanismo de control una simplificación de la distribución de probabilidad de Boltzmann conocida como el Metropolis acceptance criterion, basada en el modelo de Metrópolis [1] que describe los cambios energéticos de un sistema de partículas en función de la temperatura y que rige el comportamiento termodinámico del recocido.
En este trabajo se presenta una herramienta implementada en NetLogo [2] diseñada específicamente para facilitar la comprensión de la analogía del algoritmo de optimización con el proceso termodinámico en el que se basa. En concreto, se trata de un recurso visual, sencillo e interactivo que permite simular el proceso que tiene lugar a nivel energético bajo diferentes perfiles de descenso de temperatura. Este descenso se puede realizar mediante experimentos preprogramados para ilustrar diferentes resultados del algoritmo, bien de forma manual o bien de forma automática configurando los parámetros de los tipos de descenso de temperatura más habituales. La herramienta y el código están públicamente disponibles en el siguiente enlace [3]:
https://www.comses.net/codebases/6088b061-d836-4f98-9945-0601aafe0570/releases/1.0.0/
Está implementada en dos versiones de visualización diferentes: una enfocada a la representación de la energía individual de cada átomo y otra al conjunto de átomos en cada nivel energético dado. La herramienta se puede utilizar mediante la desktop NetLogo app o a través de NetLogo Web en un navegador y sin necesidad de ningún tipo de instalación.
Agradecimientos. Los autores agradecen la financiación del Ministerio de Ciencia, Innovación y Universidades (RED2018‐102518‐T y PGC2018-098186-B-I00), del Ministerio de Economía, Industria y Competitividad (HAR2017-90883-REDC), de la Agencia Española de Investigación (PID2020-118906GB-I00/AEI/10.13039/501100011033) y de la Junta de Castilla y León – Consejería de Educación (BDNS 425389).
References
- Metropolis N, Rosenbluth AW, Rosenbluth MN, et al (1953) Equation of State Calculations by Fast Computing Machines. J Chem Phys 21:1087–1092. https://doi.org/10.1063/1.1699114
- Wilensky U (1999) NetLogo. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL
- Santos, J.I., Pereda, M., Ahedo, V., Galán, J.M. (2021, March 15). Cooling in simulated annealing using Metropolis’ algorithm (version a & b) (Version 1.0.0). CoMSES Computational Model Library. Retrieved from: https://www.comses.net/codebases/6088b061-d836-4f98-9945-0601aafe0570/releases/1.0.0/
