curso: (30232) algoritmia para problemas...

Curso: (30232) Algoritmia para problemasdifıciles

Fernando Tricas Garcıa

Departamento de Informatica e Ingenierıa de SistemasUniversidad de Zaragoza

http://webdiis.unizar.es/~ftricas/

http://moodle.unizar.es/

[email protected]



[email protected]

Tema 3. Recocido simulado

Fernando Tricas Garcıa

Departamento de Informatica e Ingenierıa de SistemasUniversidad de Zaragoza



[email protected]

(30232) Algoritmia para problemas difıciles. Fernando Tricas Garcıa. 2



[email protected]

Recocido simulado

Tambien:

I Simulated annealing.

I Enfriamiento simulado.

Algoritmo de busqueda probabilista meta-heurıstica para unproblema de optimizacion global.


Recocido simulado

En algunos procesos metalurgicos se calienta un material y despuesse enfrıa gradualmente de manera controlada, para aumentar eltamano de los cristales que lo componen y reducir sus defectos.

Si la temperatura es suficientemente alta para asegurar un estadoaleatorio y el enfriamiento es suficientmente lento para asegurar elequilibrio termico los atomos alcanzaran un estado siguiendo unpatron que corresponde al mınimo de energıa global para obtenerun cristal perfecto.


Recocido simulado

I Templado: despues de calentar, enfriamiento rapido.Objetivo: incrementar dureza.

I Recocido: despues de calentar, enfriamiento lento.Objetivo: ablandamiento.


Recocido simulado

La analogıa del enfriamiento simulado se hace mediante lareduccion de la probabilidad de aceptar malas soluciones (peores)conforme exploramos el espacio de estados.Las malas soluciones contribuyen a hacer una busqueda masextensiva.


Recocido simulado

http://upload.wikimedia.org/wikipedia/commons/d/d5/Hill_Climbing_with_Simulated_Annealing.gif


http://upload.wikimedia.org/wikipedia/commons/d/d5/Hill_Climbing_with_Simulated_Annealing.gif

Recocido simulado

I Kirkpatrick, S.; Gelatt Jr, C. D.; Vecchi, M. P. (1983).‘Optimization by Simulated Annealing’. Science 220 (4598):671-680. doi:10.1126/science.220.4598.671. JSTOR 1690046.PMID 17813860.

I Cerny, V. (1985). ‘Thermodynamical approach to thetraveling salesman problem: An efficient simulationalgorithm’. Journal of Optimization Theory and Applications45: 41-51. doi:10.1007/BF00940812.


Recocido simulado

Adaptacion del metodo del algoritmo Metropolis-Hastings(Montecarlo).

I Metropolis, Nicholas; Rosenbluth, Arianna W.; Rosenbluth,Marshall N.; Teller, Augusta H.; Teller, Edward (1953).‘Equation of State Calculations by Fast Computing Machines’.The Journal of Chemical Physics 21 (6): 1087.doi:10.1063/1.1699114.

I Hastings, W.K. (1970). ‘Monte Carlo Sampling MethodsUsing Markov Chains and Their Applications’. Biometrika 57(1): 97-109. doi:10.1093/biomet/57.1.97. JSTOR 2334940.Zbl 0219.65008.


Recocido simulado

1. Inicializacion. Solucion aleatoria. ‘Temperatura’ muy alta.

2. Movimiento. Perturbar la solucion con algun tipo demovimiento.

3. Evaluar. Calcular la variacion de la puntuacion (energıa).

4. Elegir. Dependiendo del resultado de la evaluacion aceptar orechazar. La probabilidad de aceptacion depende de la‘temperatura’.

I Aceptar una solucion mala con probabilidad variante.

5. Actualizar y repetir. Reducir el valor de la temperatura.Volver al paso 2 hasta que alcancemos el ‘punto deenfriamiento’.


Algoritmo. Elegir...

I Si el vecino es mejor, lo elegimos

I Si es peor, lo elegimos con probabilidad1:

e(−|E (s)−E (s

′)|KB ·Temp

)

1Distribucion de Boltzmann(30232) Algoritmia para problemas difıciles. Fernando Tricas Garcıa. 11

Algoritmo

e(− |E(s)−E(s′)|

KB ·Temp )

s es el estado actual, s ′ es el vecinoE es la funcion objetivo (o alguna medida relacionada).∆E =| E (s)− E (s ′) |Temp disminuye conforme avanza el algoritmo

(Por ejemplo: Temp ← Temp ∗ 0.9 ).KB Constante

I Temperatura alta → aceptar casi cualquier vecino (randomwalk).

I Temperatura baja → seguir la direccion de mejora (hillclimbing aleatorio).

Cuando la ∆E es grande la probabilidad es baja.


Parametros

I Temperatura inicial.

I Solucion inicial.

I Movimiento (vecindario).

I Planificacion (para el enfriamiento).I Fin:

I Numero determinado de iteracionesI No ha habido cambios en un numero determinado de

iteraciones.


Ejemplo

Problema de planificacion, 1 | dj |∑

wj · Tj

jobs 1 2 3 4

pj 9 9 12 3dj 10 8 5 28wj 14 12 1 12

Aplicar procedimiento de templado simulado.Tj retraso.

I Secuencia inicial: 3, 1, 4, 2I Vecinos: intercambios entre parejas.

I Elegir uno aleatoriamente.

I Probabilidad: t ′ = 0.9 · tI t0 = 0.9

De Clifford Stein (Columbia University)


Ejemplo

I s = 3, 1, 4, 2

I E (s) = 1 · 7 + 14 · 11 + 12 · 0 + 12 · 25 = 461

I t0 = 0.9

I s1 = 1, 3, 4, 2

I E (s1) = 316(< 461), smejor = s1

I t = 0.9 · 0.9 = 0.81


Ejemplo

I s2 = 1, 3, 2, 4

I E (s2) = 340(> 316)I U1 = 0.17 (entre 0..1, aleatorio)

0.17 > e−340−316

0.81 = 1.35 · 10−13

I Se rechaza


Ejemplo

I s3 = 1, 4, 3, 2 (Vecino de s1 = 1, 3, 4, 2)

I t = 0.81 · 0.9 = 0.729

I E (s3) = 319(> 316)

I U2 = 0.91 > e−319−316

0.729 = 0.16


Ejemplo

I s4 = 1, 4, 3, 2

I t = 0.729 · 0.9 = 0.6561

I . . .


TSP

Kirkpatrick, S.; Gelatt Jr, C. D.; Vecchi, M. P. (1983).‘Optimization by Simulated Annealing’.


Ideas finales

I El esquema de enfriamiento es importante

I Cuidado con la eleccion de vecinos (parte realmenteimportante)

I No mucho soporte teorico

I Facil de implementar

I Hill climbing primero? (con reinicios aleatorios)

I Evaluar vecinos vs evaluar cambios

I Evaluacion aproximada en lugar de exacta


curso: (30232) algoritmia para problemas...

Documents