Así está mi cerebro, pero sin el simulado. Y eso que ha tenido tiempo de enfriarse un poco a lo largo de este fin de semana… Este post se gestó en estado de ebullición cerebral pero, ya que estaba escrito, publiquémoslo.
Esto del recocido es una de las metáforas curiosas que reinan en el mundo de la metaheurística; no es la única, comparte protagonismo con los algoritmos genéticos, los cúmulos de partículas y las colonias de hormigas…
Traducido también como enfriamiento simulado, el simulated annealing consiste en imitar el proceso del recocido industrial: se calienta un metal y se enfría lentamente para que las moléculas tengan tiempo de configurarse óptimamente; por lo visto, los cristales que se forman así son más perfectos y se reduce la energía interna. Esta idea inspira, en pocas palabras, un algoritmo que busca un valor lo más cercano posible al óptimo global de una función.
La manera más simple de buscar el óptimo podría ser aplicar búsqueda local a partir de una solución cualquiera. Imaginemos una función que queremos, por ejemplo, minimizar; elegimos un valor al azar, y nos dejamos caer siguiendo menos el gradiente hasta alcanzar un mínimo y quedar parados en un valle. ¿Cuál es el problema? Que lo más seguro es que acabemos en un mínimo local, si no tenemos la suerte de elegir caer por la pendiente adecuada.
Ahora imaginemos que estamos aplicando búsqueda local pero que, de vez en cuando, elegimos soluciones «peores», es decir, que no minimizan la función. Esto haría que pudiéramos saltar montañas enteras, para acabar en un valle mucho más profundo que en el que nos encontramos. El problema es ahora que saltar mucho puede ser también perjudicial, pues el algoritmo no se centra en mejorar exhaustivamente una solución, que es al fin y al cabo el objetivo de todo esto, conseguir un mínimo lo suficientemente bueno. ¿Qué se hace? Aquí entra en juego el recocido. Se usa un parámetro, llamado metafóricamente temperatura, que va descendiendo, es decir, enfriándose. Cuando la temperatura es alta, hay también una alta probabilidad de aceptar soluciones en principio «malas»; cuando es baja, la probabilidad de aceptar una solución peor es casi nula. Lo normal es que la probabilidad de aceptar una solución siga una distribución de Boltzmann; a efectos prácticos, significa que dicha probabilidad desciende exponencialmente.
Supongamos que la bola verde marca la solución inicial, que vamos mejorando a lo largo de la flecha 1; sin embargo, en un momento dado decidimos aceptar la solución que está arriba del todo, de calidad pésima si lo que queremos es minimizar. Sin embargo, esta solución nos lleva a un mínimo mejor que el que nos esperaba por el otro camino, con lo que quedaríamos más contentos que unas pascuas cuando termine de ejecutarse el algoritmo.
Y esto es todo, aquí acaba el primer capítulo de metaheurísticas divulgativas.
