Publicada By  V铆ctor Yepes Piqueras - algoritmo, Docencia, investigaci贸n operativa, optimizaci贸n, ordenadores, Polimedia, programaci贸n    

La cristalizaci贸n simulada (tambi茅n llamado recocido simulado)聽 鈥Simulated Annealing, SA鈥 constituye una de las estrategias a las que se recurre en la resoluci贸n de los problemas de optimizaci贸n combinatoria. Kirkpatrick, Gelatt y Vecchi la propusieron por primera vez en 1983 y Cerny en 1985 de forma independiente. Estos autores se inspiraron en los trabajos sobre Mec谩nica Estad铆stica de Metr贸polis et al. (1953). La metaheur铆stica despliega una estructura que se inserta c贸modamente en la programaci贸n, mostrando adem谩s una considerable habilidad para escapar de los 贸ptimos locales. Fue una t茅cnica que experiment贸 un auge considerable en la d茅cada de los 80 para resolver los modelos matem谩ticos de optimizaci贸n.

La energ铆a de un sistema termodin谩mico se compara con la funci贸n de coste evaluada para una soluci贸n admisible de un problema de optimizaci贸n combinatoria. En ambos casos se trata de evolucionar de un estado a otro de menor energ铆a o coste. El acceso de un estado metaestable a otro se alcanza introduciendo 鈥渞uido鈥 con un par谩metro de control al que se denomina temperatura. Su reducci贸n adecuada permite, con una elevada probabilidad, que un sistema termodin谩mico adquiera un m铆nimo global de energ铆a. Conceptualmente es un algoritmo de b煤squeda por entornos, que selecciona candidatos de forma aleatoria. La alternativa se aprueba si perfecciona la soluci贸n actual (D menor o igual que cero); en caso contrario, ser谩 aceptada con una probabilidad聽 (e(-D/T) si D>0, donde T es el par谩metro temperatura) decreciente con el aumento de la diferencia entre los costes de la soluci贸n candidata y la actual. El proceso se repite cuando la propuesta no es admitida. La selecci贸n aleatoria de soluciones degradadas permite eludir los m铆nimos locales. La cristalizaci贸n simulada聽se codifica f谩cilmente, incluso en problemas complejos y con funciones objetivo arbitrarias. Adem谩s, con independencia de la soluci贸n inicial, el algoritmo converge estad铆sticamente a la soluci贸n 贸ptima (Lundy y Mees, 1986). En cualquier caso, SA proporciona generalmente soluciones valiosas, aunque no informa si ha llegado al 贸ptimo absoluto. Por contra, al ser un procedimiento general, en ocasiones no resulta competitivo, aunque s铆 comparable, ante otros espec铆ficos que aprovechan informaci贸n adicional del problema. El algoritmo es lento, especialmente si la funci贸n objetivo es costosa en su tiempo de computaci贸n. Adem谩s, la cristalizaci贸n simulada聽pierde terreno frente a otros m茅todos m谩s simples y r谩pidos como el descenso local cuando el espacio de las soluciones es poco abrupto o escasean los m铆nimos locales.

Os dejo un v铆deo explicativo:聽https://www.youtube.com/watch?v=wtw_B_3lrjE

Referencias

CERNY, V. (1985). Thermodynamical approach to the traveling salesman problem: an efficient simulated algorithm. Journal of Optimization Theory and Applications, 45: 41-51.

KIRKPATRICHK, S.; GELATT, C.D.; VECCHI, M.P. (1983). Optimization by simulated annealing. Science, 220(4598): 671-680.

LUNDY, M.; MEES, A. (1986). Convergence of an Annealing Algorithm. Mathematical programming, 34:111-124.

METROPOLIS, N.; ROSENBLUTH, A.W.; ROSENBLUTH, M.N.; TELLER, A.H.; TELER, E. (1953). Equation of State Calculation by Fast Computing Machines. Journal of Chemical Physics, 21:1087-1092.

GONZ脕LEZ-VIDOSA-VIDOSA, F.; YEPES, V.; ALCAL脕, J.; CARRERA, M.; PEREA, C.; PAY脕-ZAFORTEZA, I. (2008)聽Optimization of Reinforced Concrete Structures by Simulated Annealing. TAN, C.M. (ed):聽Simulated Annealing. I-Tech Education and Publishing, Vienna, pp. 307-320.聽(link)