Simulated annealing
Páginas: 12 (2895 palabras)
Publicado: 17 de diciembre de 2011
Integrantes: Cristian Cayún, Pablo Rodríguez. Fecha: 02/11/2011
Simulated Annealing (SA)
Resumen: En la actualidad existen diversas maneras de resolver problemas ligados a combinaciones, están las heurísticas, heurística voraz entre otras, pero una técnica muy interesante para resolver este tipo de problemas combinatoriales es la técnica Simulated Annealing (SA),técnica que ayuda a la optimización combinatorial. Esta técnica será aplicada en dos problemas combinatoriales; Problema del viajante de comercio y el puzzle de 8 bloques.
Problema del viajante de comercio.
Descripción del problema:
El problema del viajante de comercio consiste en encontrar un recorrido de longitud mínima para un viajante que tiene que visitar varias ciudades y volver al punto departida, conocida la distancia existente entre cada dos ciudades. Este problema presenta una variación con respecto al problema clásico, y es que las ciudades estarán ubicadas en un plano cartesiano 3D, es decir (x, y, z), a diferencia del problema clásico que se hace en un plano 2D, ósea (x, y).
Este problema se puede solucionar básicamente con un algoritmo que consista en intentar todas lasposibilidades, es decir, calcular la longitud de todos los recorridos posibles y seleccionar la de longitud mínima. Esto lo podemos lograr definiendo una heurística o una heurística voraz, pero en esta ocasión se intentara darle solución en base a la técnica Simulated annealing.
Marco Teórico.
La técnica Simulated Annealing (SA) fue definida en el inicio de la década de los 80, como una nuevaherramienta a ser empleada en la solución de grandes problemas combinatoriales. Surgió del campo de la termodinámica como consecuencia de la comparación de problemas formulados en este campo, con los del campo
de la investigación operacional; es una metodología simple y de gran potencialidad para ser aplicada a una gran variedad de problemas.
El Simulated Annealing es una técnica deoptimización combinatorial que se usa para afrontar problemas de gran complejidad matemática, de modo que se obtengan soluciones cercanas a la óptima de Montecarlo, con el cual se estudian las propiedades de equilibrio en el análisis del comportamiento microscópico de los cuerpos.
Se fundamenta en el proceso físico de calentamiento de un sólido, seguido por un enfriamiento hasta lograr un estadocristalino con una estructura perfecta. Durante este proceso, la energía libre del sólido es minimizada. A una temperatura T, en el estado con nivel de energía Ei, se genera el estado siguiente j a través de de una pequeña perturbación. Si la diferencia de energía E2 – E1 es menor o igual a cero, el estado j es aceptado. Si la diferencia de energía es mayor que cero, el estado j es aceptado con unaprobabilidad dada por (1), donde KB es la constante de Boltzmann. Si la disminución de la temperatura es hecha de manera paulatina, el sólido puede alcanzar el estado de equilibrio en cada nivel de temperatura.
Un cambio de configuración de energía de E1 a E2 es definido por:
Para la comparación de las energías (E2<E1 y E2 >E1) existen dos casos con formulas asociadas:
CASO a)
SI E2 < E1ENTONCES P = e-(E2-E1)/KT=eE/kT
CASO b)
SI E2 > E1 ENTONCES P = e-(E2-E1)/KT=e-E/kT
La distancia entre ciudades es fundamental para el desarrollo de este problema, así la distancia entre dos ciudades en el plano (x, y, z) está dada por la formula:
DISTANCIA (A, B)= √ [ (X2 – X1)² + (Y2 – Y1)² + (Z2 – Z1)² ]
Donde A y B son coordenadas en el plano cartesiano 3D, es decirA=(x, y, z) y B (x, y, z).
Ámbito de Aplicaciones
El problema del viajante de comercio se lo plantean por ejemplo, las compañías telefónicas para escoger las rutas que deben seguir los recolectores de dinero a las cabinas públicas instaladas en una ciudad. Así mismo se puede encontrar este mismo problema en la ruta que un cartero debe seguir para entregar las cartas a diferentes villas o...
Simulated Annealing (SA)
Resumen: En la actualidad existen diversas maneras de resolver problemas ligados a combinaciones, están las heurísticas, heurística voraz entre otras, pero una técnica muy interesante para resolver este tipo de problemas combinatoriales es la técnica Simulated Annealing (SA),técnica que ayuda a la optimización combinatorial. Esta técnica será aplicada en dos problemas combinatoriales; Problema del viajante de comercio y el puzzle de 8 bloques.
Problema del viajante de comercio.
Descripción del problema:
El problema del viajante de comercio consiste en encontrar un recorrido de longitud mínima para un viajante que tiene que visitar varias ciudades y volver al punto departida, conocida la distancia existente entre cada dos ciudades. Este problema presenta una variación con respecto al problema clásico, y es que las ciudades estarán ubicadas en un plano cartesiano 3D, es decir (x, y, z), a diferencia del problema clásico que se hace en un plano 2D, ósea (x, y).
Este problema se puede solucionar básicamente con un algoritmo que consista en intentar todas lasposibilidades, es decir, calcular la longitud de todos los recorridos posibles y seleccionar la de longitud mínima. Esto lo podemos lograr definiendo una heurística o una heurística voraz, pero en esta ocasión se intentara darle solución en base a la técnica Simulated annealing.
Marco Teórico.
La técnica Simulated Annealing (SA) fue definida en el inicio de la década de los 80, como una nuevaherramienta a ser empleada en la solución de grandes problemas combinatoriales. Surgió del campo de la termodinámica como consecuencia de la comparación de problemas formulados en este campo, con los del campo
de la investigación operacional; es una metodología simple y de gran potencialidad para ser aplicada a una gran variedad de problemas.
El Simulated Annealing es una técnica deoptimización combinatorial que se usa para afrontar problemas de gran complejidad matemática, de modo que se obtengan soluciones cercanas a la óptima de Montecarlo, con el cual se estudian las propiedades de equilibrio en el análisis del comportamiento microscópico de los cuerpos.
Se fundamenta en el proceso físico de calentamiento de un sólido, seguido por un enfriamiento hasta lograr un estadocristalino con una estructura perfecta. Durante este proceso, la energía libre del sólido es minimizada. A una temperatura T, en el estado con nivel de energía Ei, se genera el estado siguiente j a través de de una pequeña perturbación. Si la diferencia de energía E2 – E1 es menor o igual a cero, el estado j es aceptado. Si la diferencia de energía es mayor que cero, el estado j es aceptado con unaprobabilidad dada por (1), donde KB es la constante de Boltzmann. Si la disminución de la temperatura es hecha de manera paulatina, el sólido puede alcanzar el estado de equilibrio en cada nivel de temperatura.
Un cambio de configuración de energía de E1 a E2 es definido por:
Para la comparación de las energías (E2<E1 y E2 >E1) existen dos casos con formulas asociadas:
CASO a)
SI E2 < E1ENTONCES P = e-(E2-E1)/KT=eE/kT
CASO b)
SI E2 > E1 ENTONCES P = e-(E2-E1)/KT=e-E/kT
La distancia entre ciudades es fundamental para el desarrollo de este problema, así la distancia entre dos ciudades en el plano (x, y, z) está dada por la formula:
DISTANCIA (A, B)= √ [ (X2 – X1)² + (Y2 – Y1)² + (Z2 – Z1)² ]
Donde A y B son coordenadas en el plano cartesiano 3D, es decirA=(x, y, z) y B (x, y, z).
Ámbito de Aplicaciones
El problema del viajante de comercio se lo plantean por ejemplo, las compañías telefónicas para escoger las rutas que deben seguir los recolectores de dinero a las cabinas públicas instaladas en una ciudad. Así mismo se puede encontrar este mismo problema en la ruta que un cartero debe seguir para entregar las cartas a diferentes villas o...
Leer documento completo
Regístrate para leer el documento completo.