Algoritmo: Recocido simulado


Recocido simulado o en inglés Simulated annealing (SA) es un algoritmo de aproximación a la solución óptima, y se basa en una analogía del comportamiento de sistemas termodinámicos simples. Esta técnica se utiliza en la búsqueda de soluciones a problemas de optimización de gran tamaño, desde el punto de vista práctico se ha usado para resolver el problema del viajero.

Se ha empleado en problemas prácticos como el diseño automático de circuitos integrados, análisis sintáctico del lenguaje, simulación del funcionamiento neuronal, etc.

Otras aplicaciones de recocido simulado son:
– Comunicaciones
– Teoría de grafos
– Predicción de estructuras de cromosomas
– Clasificación de imágenes
– Diseño de circuitos electrónicos

El recocido simulado busca mejorar alguna de las propiedades de un objeto, consiste en producir al azar cambios en sus valores.

La simulación del proceso puede usarse para describir la generación de soluciones de un problema de optimización combinatoria, en donde conforme el proceso cambia (azar) y teniendo como resultado la mejor solución.

Las soluciones de un problema de optimización combinatoria son equivalentes a los estados de un sistema físico. El costo de una solución es equivalente a la energía de un estado.

Descripción breve del algoritmo:

En cada iteración, el método evalúa algunos vecinos del estado actual denominado S, y probabilísticamente decide entre efectuar una transición a un nuevo estado S’ o quedarse en el estado inicial S. La comparación entre estados vecinos se repite hasta que se encuentre un estado óptimo que minimice la energía del sistema o hasta que se cumpla cierto tiempo computacional u otras condiciones.

Fuentes:
Wikipedia.
Recocido Simulado. Departamento de Matemáticas
Recocido Simulado – Inteligencia computacional. 

Anuncios

Acerca de silvercorp

Blog personal de Ye§i creado el 18/Ag/06 enfocado al diseño gráfico, tecnología y programación.

Publicado el noviembre 7, 2013 en Inteligencia Artificial. Añade a favoritos el enlace permanente. Deja un comentario.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: