[Optimización] --> Recocido simulado / Simulated annealing

Introducción
El método de recocido simulado es una técnica de optimización no determinística o estocástica (con aleatoriedad en la búsqueda de soluciones) que presenta una analogía con el proceso químico de recocido de materiales metálicos.

Al someter un metal a altas temperaturas los átomos absorben energía, se rompen los enlaces químicos confiriendo a los átomos un mayor grado de libertad para moverse. En el método de recocido se somete el metal a un enfriamiento controlado (más o menos lento), conforme la temperatura va disminuyendo los átomos poseen menos libertad de movimiento y se logra una estructura química más resistente y ordenada. Los átomos tienen a posicionarse en lugares donde la energía es mínima.

Este tipo de métodos es empleado en problemas combinatorios complejos, por ejemplo en el diseño óptimo de ordenadores, algoritmos de transporte (TSP), etc.. donde existe un gran número de parámetros a optimizar y el número de mínimos locales es muy grande.

El algoritmo
Se basa en la metaheurística de la relación entre el proceso químico del recocido y la optimización combinatoria. La relación entre ambas se muestra a continuación:

• Configuración cristalina => Solución factible.
• Configuración cristalina de mínima energía => Solución óptima.
• Energía de la configuración => Coste de la solución.
• Temperatura => Parámetro de control.

Por ser un método iterativo necesita partir de una solución inicial, la elección de esta nos determinará el coste computacional del resultado obtenido, aunque al ser un método estocástico no será tan crítica como en los métodos directos como gradiente-conjugado o Newton.


La diferencia entre este algoritmo y el de Monte Carlo es que este último sólo acepta soluciones mejores, mientras que el SA acepta soluciones peores según una cierta probabilidad. Debido a esto evita quedarse estancado en óptimos locales tan fácilmente (Mecanismo hill-climbing).

Parámetros importantes

• Temperatura inicial. Si dicha temperatura es demasiado alta serán necesarias más iteraciones y el método tardará más en converger, si por el contrario es baja no llegará al mínimo. La solución sería partir de una temperatura alta y realizar pasos pequeños pero el problema sería intratable computacionalmente. Debe ser seleccionada con la idea de que casi todas las transiciones entre los estados sean aceptadas.
• Esquema de enfriamiento. Determina como se va a realizar el descenso de la temperatura. Normalmente es usado un descenso geométrico de la forma:  Tnew = k·Told   donde k toma valores entre 0.80 y 0.99.
• Temperatura mínima. Tiene que ser suficientemente baja para permitir llegar al máximo global.
• Tiempo antes de la disminución de temperatura. Normalmente se usan número de iteraciones entre cada descenso de temperatura.
• Criterio de parada. Se pueden considerar 3 métodos:
• Tolerancia. Suponiendo que se conoce teóricamente una solución.
• Cantidad de iteraciones.
• Cambios relativos entre sucesivas iteraciones.
• Movimientos. Determina como se realizan los cambios de parámetros. Deben ser inteligentes, es decir, estudiados matemáticamente para cada caso en particular. También son usados mutaciones y cruces. Un método sencillo de implementar sería realizar pequeñas alteraciones en un parámetro aleatorio.

Aplicaciones

• Asignación: como acomodar los componentes de un circuito, generalización de asignación de cuadrados.
• TSP: Partir de A, visitando N ciudades una sola vez y llegar a A, trayectoria de longitud mínima.
• Particionamiento de grafos.
• Arboles de Steiner.
• Clustering.
• Problemas de planificación.
• Problemas de Organización de la Producción.
• Simulación de reacciones químicas.
• Ajustes de curvas en n-dimensiones.