Instituto Chileno de Investigación Operativa


Strict Standards: Only variables should be assigned by reference in /home/ichiocl/public_html/modules/mod_jt_superfish_menu/tmpl/default.php on line 23
jtemplate.ru - free templates joomla

Simulated Annealing

El método SA es un algoritmo probabilístico que permite resolver problemas de optimización. Se basa en una analogía de un proceso termodinámico, conocido como annealing, consistente en el lento enfriamiento de una sustancia desde su estado líquido hasta su estado sólido. Durante este proceso sus átomos forman un compuesto solido puro que corresponde al estado de mínima energía de la sustancia. Luego, la sustancia es calentada hasta alcanzar su estado líquido y gradualmente su temperatura es disminuida hasta alcanzar su estado sólido. La analogía entonces se realiza interpretando una solución del problema de optimización como un estado sólido-liquido en equilibrio, entendiendo que la energía que está siendo minimizada en el proceso termodinámico, corresponde con la función objetivo del problema a resolver.

El procedimiento esquematizado en la figura 1 visita el espacio de búsqueda del problema de optimización reduciendo gradualmente el valor de la función objetivo. A partir de una solución actual se visita una solución vecina la que siempre se acepta en el caso de ser mejor y se acepta eventualmente en el caso de ser peor que la actual respetando una función de probabilidades definidas en este caso como la función de probabilidad de Boltzmann. El algoritmo cuenta con dos ciclos, en el ciclo interno se regula la disminución de la temperatura, mientras que en ciclo externo, se realiza una búsqueda local aleatoria a una temperatura dada.

simulated annealing

Figura 1: Esquematización algoritmo SA

 

  1. Historia
  2. Aplicaciones
  3. Videos
  4. Links

Acceso (Plantilla Atomic)