Recocido simulado
Páginas: 12 (2769 palabras)
Publicado: 18 de octubre de 2010
RECOCIDO SIMULADO
(SIMULATED ANNEALING, SA)
LEONEL IGNACIO AGUILAR OCHOA 11130828
HUGO ARMANDO PULIDO RODRÍGUEZ 1123899
EDWIN FABIAN PARADA ALFONSO
JHON ALEXANDER TORRES 1130719
Presentado a:
Ing. Juan Carlos Poveda D´Otero
UNIVERSIDAD PEDAGOGICA Y TECNOLOGICA DE COLOMBIA
FACULTAD DE INGENIERIA
ESCUELA DE TRANSPORTE Y VIAS
METAHEURÍSTICAS
2010
RECOCIDO SIMULADOAnalogía Física
El método del recocido se utiliza en la industria para obtener materiales más resistentes, o más cristalinos, en general, para mejorar las cualidades de un material.
Es un tratamiento de calor que altera la microestructura de un material causando cambios en las propiedades tales como fuerza y dureza, es una técnica que involucra calentado y enfriado controlado de un material paraincrementar el tamaño de sus cristales y reduce sus defectos.
El calor causa que los átomos se desatoren de sus posiciones iníciales (un mínimo local de la energía interna) y vaguen aleatoriamente a través de estados de energía más altos; el enfriado lento les da más oportunidades de encontrar configuraciones con menor energía interna que la inicial.”
El proceso consiste en “derretir” elmaterial (calentarlo a muy alta temperatura). En esa situación, los átomos adquieren una distribución “aleatoria” dentro de la estructura del material y la energía del sistema es máxima. Luego se hace descender la temperatura muy lentamente por etapas, dejando que en cada una de esas etapas los átomos queden en equilibrio (es decir, que los átomos alcancen una configuración óptima para esa temperatura).Al final del proceso, los átomos forman una estructura cristalina altamente regular, el material alcanza así una máxima resistencia y la energía del sistema es mínima.
Experimentalmente se comprueba que si la temperatura se hace descender bruscamente o no se espera suficiente tiempo en cada etapa, al final la estructura del material no es la optima.
La rama de la Física llamada MecánicaEstadística se encargo de desarrollar una serie de métodos para estudiar el comportamiento de grandes cantidades de átomos de un sistema. Debido a que en promedio, en un sistema hay 1023 átomos por cm3, solamente puede estudiarse el comportamiento más probable del sistema en equilibrio a una dada temperatura. La experimentación mostro que los átomos de un sistema en un proceso de recocido se comportansegún el factor de probabilidad de Boltzman. En 1953 Metropolis modelo el proceso de recocido: en cada paso del algoritmo se le da al átomo un desplazamiento azaroso y se mide el cambio de energía ∆E. Si ∆E ≤ 0 se acepta el desplazamiento. Si ∆E > 0, se acepta el desplazamiento con probabilidad exp (-∆E / T.K), donde T es la temperatura del sistema y K es la constante de Boltzman.
Algoritmo RecocidoSimulado
El Recocido Simulado es una de las metaheurísticas más clásicas. Su simplicidad y buenos resultados en numerosos problemas, la han convertido en una herramienta muy popular, con cientos de aplicaciones en los más variados campos. Su fundamentación se basa en el trabajo de Metropolis et al. (1953) en el campo de la termodinámica estadística. Básicamente, Metropolis modeló el proceso derecocido simulando los cambios energéticos en un sistema de partículas conforme decrece la temperatura, hasta que converge a un estado estable (congelado). Las leyes de la termodinámica dicen que a una temperatura t la probabilidad de un incremento energético de magnitud dE se puede aproximar por:
P[dE]=exp (-dE/kt) (1)
Siendo k una constante física denominada de Boltzman.
A principios de ladécada de los 80, publicaciones independientes de Kirkpatrick et al. (1983) sobre diseño de circuitos VLSI, y Cerny (1985) para el TSP, mostraron cómo este proceso podría ser aplicado a problemas de optimización, asociando conceptos clave del proceso original de simulación, con elementos de optimización combinatoria.
Por tanto, cualquier implementación de búsqueda local puede convertirse en...
(SIMULATED ANNEALING, SA)
LEONEL IGNACIO AGUILAR OCHOA 11130828
HUGO ARMANDO PULIDO RODRÍGUEZ 1123899
EDWIN FABIAN PARADA ALFONSO
JHON ALEXANDER TORRES 1130719
Presentado a:
Ing. Juan Carlos Poveda D´Otero
UNIVERSIDAD PEDAGOGICA Y TECNOLOGICA DE COLOMBIA
FACULTAD DE INGENIERIA
ESCUELA DE TRANSPORTE Y VIAS
METAHEURÍSTICAS
2010
RECOCIDO SIMULADOAnalogía Física
El método del recocido se utiliza en la industria para obtener materiales más resistentes, o más cristalinos, en general, para mejorar las cualidades de un material.
Es un tratamiento de calor que altera la microestructura de un material causando cambios en las propiedades tales como fuerza y dureza, es una técnica que involucra calentado y enfriado controlado de un material paraincrementar el tamaño de sus cristales y reduce sus defectos.
El calor causa que los átomos se desatoren de sus posiciones iníciales (un mínimo local de la energía interna) y vaguen aleatoriamente a través de estados de energía más altos; el enfriado lento les da más oportunidades de encontrar configuraciones con menor energía interna que la inicial.”
El proceso consiste en “derretir” elmaterial (calentarlo a muy alta temperatura). En esa situación, los átomos adquieren una distribución “aleatoria” dentro de la estructura del material y la energía del sistema es máxima. Luego se hace descender la temperatura muy lentamente por etapas, dejando que en cada una de esas etapas los átomos queden en equilibrio (es decir, que los átomos alcancen una configuración óptima para esa temperatura).Al final del proceso, los átomos forman una estructura cristalina altamente regular, el material alcanza así una máxima resistencia y la energía del sistema es mínima.
Experimentalmente se comprueba que si la temperatura se hace descender bruscamente o no se espera suficiente tiempo en cada etapa, al final la estructura del material no es la optima.
La rama de la Física llamada MecánicaEstadística se encargo de desarrollar una serie de métodos para estudiar el comportamiento de grandes cantidades de átomos de un sistema. Debido a que en promedio, en un sistema hay 1023 átomos por cm3, solamente puede estudiarse el comportamiento más probable del sistema en equilibrio a una dada temperatura. La experimentación mostro que los átomos de un sistema en un proceso de recocido se comportansegún el factor de probabilidad de Boltzman. En 1953 Metropolis modelo el proceso de recocido: en cada paso del algoritmo se le da al átomo un desplazamiento azaroso y se mide el cambio de energía ∆E. Si ∆E ≤ 0 se acepta el desplazamiento. Si ∆E > 0, se acepta el desplazamiento con probabilidad exp (-∆E / T.K), donde T es la temperatura del sistema y K es la constante de Boltzman.
Algoritmo RecocidoSimulado
El Recocido Simulado es una de las metaheurísticas más clásicas. Su simplicidad y buenos resultados en numerosos problemas, la han convertido en una herramienta muy popular, con cientos de aplicaciones en los más variados campos. Su fundamentación se basa en el trabajo de Metropolis et al. (1953) en el campo de la termodinámica estadística. Básicamente, Metropolis modeló el proceso derecocido simulando los cambios energéticos en un sistema de partículas conforme decrece la temperatura, hasta que converge a un estado estable (congelado). Las leyes de la termodinámica dicen que a una temperatura t la probabilidad de un incremento energético de magnitud dE se puede aproximar por:
P[dE]=exp (-dE/kt) (1)
Siendo k una constante física denominada de Boltzman.
A principios de ladécada de los 80, publicaciones independientes de Kirkpatrick et al. (1983) sobre diseño de circuitos VLSI, y Cerny (1985) para el TSP, mostraron cómo este proceso podría ser aplicado a problemas de optimización, asociando conceptos clave del proceso original de simulación, con elementos de optimización combinatoria.
Por tanto, cualquier implementación de búsqueda local puede convertirse en...
Leer documento completo
Regístrate para leer el documento completo.