Simulated annealing

El otro día dejé el tema de los procedimientos algorítmicos para la resolución de problemas de optimización combinatoria pendiente de retomar el hilo. Voy a coger la madeja, a ver si la desenredo…

Resulta que hay un tipo de problemas de donde se supone que debe haber una (o varias) soluciones optimas, pero que hay un número muy elevado de posibles opciones de solución como para analizar todas y escoger la mejor.

Imaginemos una ciudad en donde queremos distribuir en sus calles el mínimo de estaciones de metro que dé servicio a todos los habitantes, pero optimizando el parámetro de “apreciación de cercanía del servicio” por parte de los ciudadanos para que, el nivel de satisfacción global ofrecido sea el mayor posible.

.

.

Un procedimiento algorítmico meta-heurístico que podría aplicarse para obtener la mejor solución teórica a este problema de optimización combinatoria es el llamado “simulated annealing”, o simulación del temple.

Consiste, en primer lugar, en obtener una expresión de la “función de coste” de cada solución posible. Esta función de coste, para el caso que nos ocupa, sería seguramente la “puntuación de la apreciación global de la cercanía de servicio”, donde se tendrían en cuenta “ingredientes” y variables, para cada ciudadano, como la distancia de su casa a la estación de metro más cercana, posiblemente la ponderaríamos según parámetros de pendiente/desnivel de las calles, según la franja de edad de cada uno… y añadiríamos un factor de atención a las personas con movilidad reducida. También añadiríamos criterios de “qué nivel de servicio” es percibido (o esperado) como satisfactorio por cada ciudadano en función de si éste vive en una zona de viviendas verticales de elevada densidad, o si por lo contrario, vive en un barrio residencial de casas aisladas. Sumando el nivel de apreciación de satisfacción cada ciudadano, para cada solución de distribución de un número de paradas de metro situadas por el municipio, se obtendría el valor de la “función de coste” para este problemita.

A partir de aquí, se deja a un lado la gorra de “técnico municipal” y se coge la gorra de “matemático analista” para empezar a sacar humo a la función de coste de marras aplicando el algoritmo de simulated annealing. Esta técnica proviene de la analogía hecha entre los problemas de la mecánica estadística de encontrar el estado básico de un sistema de varios cuerpos -un líquido, por ejemplo- y el de encontrar un mínimo (o un máximo) global de una función de coste en un problema de optimización combinatoria.

Si la temperatura de la interacción molecular en un líquido se congelase de golpe, el resultado podría ser de un completo desorden cristalino con una energía más alta que la del estado cristalino básico correcto. De hecho, las moléculas se encontrarían en un mínimo local de energía.

Sin embargo, si la temperatura del líquido se reduce lentamente (annealing) se tiende hacia un equilibrio y el líquido se congela a través de un proceso de enfriamiento que conduce a un estado cristalino de mínima energía global.

En la analogía hecha con el problema de optimización combinatoria, los parámetros variables (dónde ponemos las estaciones de metro y cuantas ponemos para que el coste económico global sea mínimo) son equiparados con las posiciones atómicas del líquido y la energía se identifica con la función de coste a optimizar (la “puntuación de la apreciación global de la cercanía de servicio”). La temperatura se define como un parámetro de control del proceso algorítmico y está relacionada con la probabilidad de cambio a un estado de peor coste que tiene que ser aceptado con la finalidad de no caer en un mínimo local.

En el algoritmo de la simulación del temple se acepta un cambio de solución (o de estado) cuando el resultado de la función de coste asociado a la nueva solución es mayor. Lógico. Pero si el resultado de la función de coste en la nueva solución es menor, el cambio es aceptado con cierta probabilidad que depende de la temperatura que controla el sistema y del decremento del valor de la función de coste, utilizando para ello una función exponencial negativa.

El proceso del algoritmo parte de una solución inicial cualquiera y a una temperatura inicial “ambiente”. Obtiene la función de coste y explora, en un número de iteraciones adecuado, el entorno del espacio de estados. El entorno se analiza efectuando una perturbación elemental en la solución actual y aplicando el criterio de aceptación de la nueva propuesta de solución según la probabilidad definida.

Al inicio, cuando la temperatura es relativamente alta, se aceptan cambios de solución a pesar que los empeoramientos de la función de coste sean importantes. Después, a medida que la temperatura decrece, se van aceptando empeoramientos cada vez más pequeños. Esta característica del algoritmo es la que le permite poderse escapar de los mínimos locales y asegurar una buena convergencia del método en un amplio tipo de problemas y espacios de estado. Es una de las claves del éxito de éste método meta-heurístico.

.

La temperatura se decrementa suavemente y el sistema algorítmico se va enfriando hasta pararse cuando se cumpla alguno de los criterios de final de cálculo (pocos cambios aceptados, no se ha aumentado el resultado de la función de coste en la última temperatura, etc.) Entonces, se escoge como mejor resultado aquella solución que, de todos los estados por donde ha pasado el algoritmo, la que mayor función de coste o “puntuación de la apreciación global de la cercanía de servicio” nos ha dado.

El algoritmo de la simulación del temple, si bien no ha pasado por todas las casi infinitas soluciones del espacio de estados, tiene un elevado grado éxito y adaptabilidad a multitud de problemas de optimización combinatoria. El método asegura una buena convergencia hacia la solución óptima global en un número iteraciones asumibles de ser calculadas por un programa informático en un tiempo de cálculo aceptable y acorde con la magnitud del problema a tratar.