.....

sábado, 18 de julio de 2009

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.

9 comentarios:

Cabestany dijo...

Meta-heuresis.

Habría que aplicarla mas que a la situación y distribución de estaciones de metro a la población que lo utiliza y al funcionamiento correcto de este como transporte. En resumen: ¡Que no se estropeara tanto, lechas! Que mi jefe ya no se cree la misma excusa siempre que llego tarde.

Un saludo, interesante la entrada, a pesar de ser mas larga de lo normal. ;)

Un abrazo!!!

SYR Malvís dijo...

Tio, no me explico, despues de esto, como puedes haber suspendido el postgrado.

Rubén Oliver dijo...

Mis cuatro neuronas,en claro amotinamiento,y erigiéndose como portavoz,la coordinadora habitual me hacen saber:primero-"O nos das un neurotransmisor más efectivo,o el colapso está garantizado",segundo:-"El envejecimiento poblacional y posterior acceso al vehículo por los jóvenes al crecer,abandonando el metro,en el ejemplo propuesto,¿puede resolverlo el cálculo?,porque no se pueden estar moviendo las estaciones ¿no?" y -tercero:"el sector neuronal holgazán,pide descanso y que se limite el acceso a estos berenjenales matemáticos,que ya tuvimos bastante con la raiz cúbica(han manifestado)"

Un saludo.

Baruk dijo...

...mm... hablemos de lo realmente importante, que quieres que te haga para comer hoy??

Rubén Oliver dijo...

El ayuntamiento de Barcelona pendiente del blog,para ubicar las paradas de metro,y ella pensando en comer...Si es que son...ja ja ja..

pallaferro dijo...

Por suerte, puedo elegir el plato de comida.
Por suerte, tengo cercana una parada de metro.
Por suerte, cojo cada dia un tren que cumple puntualmente los horarios.
Por suerte, he pagado la cuota suficiente para que me aprueben el postgrado.

... y por suerte, no tenemos que ir aplicando el algoritmo del simulated annealing cada dia en los problemas quotidianos!

Será suerte, libre albedrío, o decreto del destino?

Un abrazo y gracias por vuestros comentarios.

Rubén Oliver dijo...

¿Que cojes un tren a diario que llega puntual?...¡Dios mio!¡Te has ido al extranjero y no nos has dicho nada!

Alkaest dijo...

¡Jo tío, hablas como el brujo de la tribu y su primo el chamán!

¿Eso es lo que ahora llaman ser "friki"?
¿O es lo que antes se llamaba ser sabio?
¿O será lo que por al-Andalus definen como: "Una ná, con colmo"?

En resumen, pa ná te matas Pallaferro, los que tienen nuestra pasta para construir "metros", lo que menos necesitan son "listillos matemáticos". A ellos les basta con satisfacer al sector conveniente, en las próximas elecciones. Así que distribuirán las estaciones, según el "algoritmo del voto probable"...

Pero no te deprimas, hombre, otras neuronas se entretienen haciendo "autodefinidos" y no por eso tienen poca autoestima. Si a ti te entretiene, la cosa esa de las fórmulas, pues "algoritmiza" que algo queda.
Si, a pesar de todo, hasta te dan a elegir comida. ¡Que suerte tienes barbián!

[Lo que me asusta es, la sospecha de que esas fórmulas se utilicen, como seguramente es así, para cosas menos sensatas que construir "metros". Y no me refiero a la carrera espacial, precisamente...]

¡Ay, me recuerdas tanto al chaval de la televisiva serie "Numbers"!

Salud y fraternidad.

Melusina dijo...

Que bárbaro. No se te puede perder de vista. Enseguida algoritmas.

Pues en mi pueblo estan haciendo un metro. No sabemos porque