Túnel estocástico

Método estocástico de optimización global

En el análisis numérico , la tunelización estocástica (STUN) es un enfoque de optimización global basado en el método de Monte Carlo : muestreo de la función que se va a minimizar objetivamente, en el que la función se transforma de manera no lineal para permitir una tunelización más sencilla entre las regiones que contienen los mínimos de la función. Una tunelización más sencilla permite una exploración más rápida del espacio muestral y una convergencia más rápida hacia una buena solución.

Idea

Función de prueba unidimensional esquemática (negra) y potencial efectivo STUN (roja y azul), donde el mínimo indicado por las flechas es el mejor mínimo encontrado hasta el momento. Todos los pozos que se encuentran por encima del mejor mínimo encontrado se suprimen. Si el proceso dinámico puede escapar del pozo alrededor de la estimación mínima actual, no quedará atrapado por otros mínimos locales que sean más altos. Los pozos con mínimos más profundos se mejoran. El proceso dinámico se acelera por eso.

Las técnicas de optimización basadas en el método de Monte Carlo muestrean la función objetivo "saltando" aleatoriamente del vector de solución actual a otro con una diferencia en el valor de la función de . La probabilidad de aceptación de dicho salto de prueba se elige en la mayoría de los casos como ( criterio de Metropolis ) con un parámetro apropiado . ${\displaystyle \Delta E}$ ${\displaystyle \min \left(1;\exp \left(-\beta \cdot \Delta E\right)\right)}$ ${\displaystyle \beta }$

La idea general de STUN es eludir la dinámica lenta de las funciones de energía mal formadas que se encuentran, por ejemplo, en los vidrios de espín, al atravesar dichas barreras.

Este objetivo se logra mediante el muestreo de Monte Carlo de una función transformada que carece de esta dinámica lenta. En la "forma estándar", la transformación se lee donde es el valor de función más bajo encontrado hasta el momento. Esta transformación conserva los lugares geométricos de los mínimos. ${\displaystyle f_{STUN}:=1-\exp \left(-\gamma \cdot \left(E(x)-E_{o}\right)\right)}$ ${\displaystyle E_{o}}$

${\displaystyle f_{STUN}}$Luego se utiliza en lugar de en el algoritmo original dando una nueva probabilidad de aceptación de ${\displaystyle E}$ ${\displaystyle \min \left(1;\exp \left(-\beta \cdot \Delta f_{STUN}\right)\right)}$

El efecto de tal transformación se muestra en el gráfico.

Tunelización estocástica adaptativa dinámica

Una variación de la tunelización constante es hacerlo solo cuando se está atrapado en un mínimo local. Luego se ajusta para salir del mínimo y buscar una solución globalmente óptima. El análisis de fluctuación sin tendencia es la forma recomendada de determinar si se está atrapado en un mínimo local. ${\displaystyle \gamma }$

Otros enfoques

• Recocido simulado
• Templado paralelo
• Algoritmo genético
• Evolución diferencial

Referencias

• K. Hamacher (2006). "Adaptación en optimización global por efecto túnel estocástico de paisajes energéticos potenciales complejos". Europhys. Lett. 74 (6): 944–950. Bibcode :2006EL.....74..944H. doi :10.1209/epl/i2006-10058-0. S2CID  250761754.
• K. Hamacher y W. Wenzel (1999). "El comportamiento de escalamiento de los algoritmos de minimización estocástica en un paisaje de embudo perfecto". Phys. Rev. E . 59 (1): 938–941. arXiv : physics/9810035 . Código Bibliográfico :1999PhRvE..59..938H. doi :10.1103/PhysRevE.59.938. S2CID  119096368.
• W. Wenzel y K. Hamacher (1999). "Un enfoque de tunelización estocástica para la minimización global". Phys. Rev. Lett. 82 (15): 3003–3007. arXiv : physics/9903008 . Código Bibliográfico :1999PhRvL..82.3003W. doi :10.1103/PhysRevLett.82.3003. S2CID  5113626.
• Nicholas Metropolis , Arianna W. Rosenbluth, Marshall N. Rosenbluth , Augusta H. Teller y Edward Teller (junio de 1953). "Cálculos de ecuaciones de estado mediante máquinas de computación rápida" (PDF) . The Journal of Chemical Physics . 21 (6): 1087–1092. Bibcode :1953JChPh..21.1087M. doi :10.1063/1.1699114. OSTI  4390578. S2CID  1046577.{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
• Mingjie Lin (diciembre de 2010). "Mejora de la colocación de FPGA con tunelización estocástica adaptativa dinámica". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 29 (12): 1858–1869. doi :10.1109/tcad.2010.2061670. S2CID  8706692.