templado simulado

19/04/2010

Recocido Simulado (RS)

Optimización Heurística

Recocido Simulado
 Problema de la búsqueda local:
 Como siempre trata de mejorar, se atora en los máximos locales
 Idea:
Escapar de máximos locales permitiendo movimientos “malos”.
 Pero gradualmente disminuir su tamaño y frecuencia.
 Explota una analogía entre el proceso de recocido y la

búsqueda por un óptimo enun sistema más general
 Analogía de la bola de ping pong:
ping-pong:
 Sacudir fuerte (= alta temperatura).
 Sacudiendo menos (= reducción de temperatura).

 Aplicaciones: problemas dedistribución en VLSI,

programación de vuelos, etc.

1

19/04/2010

Proceso de recocido
 Incremento de la temperatura hasta un nivel

muy alto (temperatura de derretimiento por
derretimiento,ejemplo), los átomos tienen un estado de más alta
energía y una alta posibilidad de re-arreglar la
estructura cristalina.

 Enfriamiento lento, los átomos tiene un estado
lento

cada vez másbajo de energía y una posibilidad
cada vez más baja de re-arreglar la estructura
cristalina.

Recocido simulado
 Analogía
 Metal  Problema
 Sistema de estados  Soluciones factibles
Nivel de energía  Función de costo
 Cambio de estado  Solución vecina
 Temperatura  Parámetro de control
 Un ordenamiento completo de la estructura cristalina
p
 la solución óptima delproblema

La solución óptima global puede ser lograda si el
proceso de enfriamiento es suficientemente lento

2

19/04/2010

Ciclo Metrópolis
 Es la característica esencial del recocidosimulado
 Determina como explorar aleatoriamente nuevas

soluciones, rechazándolas o aceptándolas a una
temperatura constante T.

 El proceso de movimiento de un estado al siguiente esrepetido por un número de iteraciones en la misma
temperatura

 Es terminado hasta que se logra el equilibrio.

Criterio Metrópolis
 Supongamos que
 X es la solución actual y que X’ es la nueva...