Algoritmo de recocido simulado

El algoritmo de recocido simulado es un método algorítmico general para resolver un problema de optimización global, especialmente la optimización discreta y combinatoria . Un ejemplo de los métodos de Monte Carlo .

Descripción general

El algoritmo se basa en la simulación del proceso físico que ocurre durante la cristalización de una sustancia , incluido el recocido de metales . Se supone que los átomos de la materia ya están casi alineados en una red cristalina , pero aún son aceptables las transiciones de átomos individuales de una celda a otra. La actividad de los átomos es mayor cuanto mayor es la temperatura , que se reduce gradualmente, lo que lleva al hecho de que la probabilidad de transiciones a estados con mayor energía disminuye. Una red cristalina estable corresponde a la energía mínima de los átomos, por lo que el átomo entra en un estado con un nivel de energía más bajo o permanece en su lugar. (Este algoritmo también se llama algoritmo N. Metropolis , en honor a su autor).

La simulación de un proceso similar se usa para resolver un problema de optimización global, que consiste en encontrar tal punto o conjunto de puntos en los que se alcanza el mínimo de alguna función objetivo ("energía del sistema"), donde ( es el "estado de la sistema", es el conjunto de todos los estados). $F(x)$ ${\ estilo de visualización {x} \ en X}$ ${X}$ $X$

El algoritmo para encontrar el mínimo por el método de simulación de recocido asume una configuración libre:

${\ estilo de visualización {x_ {0}} \ en X}$ — el estado inicial del sistema;
un operador que genera aleatoriamente un nuevo estado del sistema después del i-ésimo paso, teniendo en cuenta el estado actual (este operador, por un lado, debería proporcionar un paseo aleatorio bastante libre en el espacio , y por otro lado, trabajar deliberadamente hasta cierto punto, asegurando la velocidad de búsqueda); $A({x},i):X\times \mathbb {N} \to X$ ${X}$ $X$
$T_{i}>0$ — secuencia positiva decreciente a cero, que establece el análogo de la temperatura decreciente en el cristal. La tasa de enfriamiento (ley decreciente) también puede establecerse (y variarse) arbitrariamente, lo que le da al algoritmo una flexibilidad considerable.

El algoritmo genera un proceso de paseo aleatorio sobre el espacio de estados . La solución se busca mediante el cálculo sucesivo de puntos en el espacio ; cada punto, a partir de , "pretende" aproximar la solución mejor que los anteriores. En cada paso, el algoritmo (que se describe a continuación) calcula un nuevo punto y reduce el valor de la cantidad (inicialmente positiva) entendida como "temperatura". $X$ ${x_{0)),\;{x_{1)),\;{x_{2)),\;\ldots,\;$ $X$ ${\ estilo de visualización {x_{1))}$

La secuencia de estos puntos (estados) se obtiene de la siguiente manera. El operador se aplica al punto , lo que da como resultado un punto candidato para el cual se calcula el cambio correspondiente en "energía" . Si la energía disminuye ( ), el sistema pasa a un nuevo estado: . Si la energía aumenta ( ), la transición a un nuevo estado solo puede ocurrir con cierta probabilidad, dependiendo de la magnitud del aumento de energía y la temperatura actual, de acuerdo con la ley de distribución de Gibbs : ${\ estilo de visualización {x_ {i}}}$ $A$ ${x_{i}^{*}}=A(x_{i},i)$ $\Delta F_{i}=F({x_{i}^{*)))-F({x_{i)))$ ${\ estilo de visualización \ Delta F_ {i} \ leq 0}$ ${x_{i+1}}={x_{i}^{*}}$ $\Delta F_{i}>0$

P({x_{i}^{*}}\to {x_{i+1}}\mid {x_{i}})=\exp(-\Delta F_{i}/{T_{i }})

Si la transición no se produjo, el estado del sistema sigue siendo el mismo: . El algoritmo se detiene cuando llega a un punto que resulta estar a temperatura cero. ${\ estilo de visualización {x_{i+1}}={x_{i}}}$

El algoritmo de recocido de simulación es similar al descenso de gradiente , pero debido a la aleatoriedad de la elección del punto intermedio y la capacidad de salir de los mínimos locales, debería ser menos probable que se atasque en los mínimos locales, pero no globales, que el descenso de gradiente. El algoritmo de recocido simulado no garantiza encontrar el mínimo de la función, sin embargo, con la configuración correcta de generar un punto aleatorio en el espacio , por regla general, se produce una mejora en la aproximación inicial. $X$

Aplicación

Entrenamiento de redes neuronales
Resolver problemas combinatorios, por ejemplo, el problema de colocar reinas
Resolviendo el problema del viajante de comercio [1]

Véase también

Método de recocido cuántico

Notas

↑ El problema del ciclo hamiltoniano . Consultado el 19 de febrero de 2014. Archivado desde el original el 25 de febrero de 2014. (indefinido)

Literatura

Callan Roberto. Conceptos básicos de redes neuronales. - M. : Williams Publishing House, 2003. - 288 p. — ISBN 5-8459-0219-X . - S. 146-148.
Kirsanov M. N. Gráficos en Maple . — M. : Fizmatlit, 2007. — 168 p. - ISBN 978-5-9221-0745-7 . - S. 151-154.
Jones M. T. Programación de inteligencia artificial en aplicaciones. - M. : DMK Press, 2004. - 312 p. — ISBN 5-94074-275-0 . - S. 25-42.

Enlaces

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock Método Powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial