Стохастическое туннелирование

В численном анализе стохастическое туннелирование (STUN) — это подход к глобальной оптимизации, основанный на методе Монте-Карло — выборке функции, подлежащей объективной минимизации, при которой функция нелинейно преобразуется, чтобы облегчить туннелирование между областями, содержащими минимумы функции. Более простое туннелирование позволяет быстрее исследовать пространство выборки и быстрее сходиться к хорошему решению.

Идея

Схематическая одномерная тестовая функция (черный) и эффективный потенциал STUN (красный и синий), где минимум, указанный стрелками, является лучшим минимумом, найденным на данный момент. Все скважины , находящиеся выше найденного наилучшего минимума, подавляются. Если динамический процесс может выйти из колодца вокруг текущей минимальной оценки, он не будет захвачен другими локальными минимумами, которые находятся выше. Улучшаются скважины с более глубокими минимумами. Этим ускоряется динамический процесс.

Методы оптимизации, основанные на методе Монте-Карло, выбирают целевую функцию путем случайного «перескока» от текущего вектора решения к другому с разницей в значении функции $\Delta E$. Вероятность принятия такого пробного прыжка в большинстве случаев выбирается равной $\min \left(1;\exp \left(-\beta \cdot \Delta E\right)\right)$ ( критерий Метрополиса ) с соответствующим параметром $\beta$.

Общая идея STUN состоит в том, чтобы обойти медленную динамику энергетических функций неправильной формы, с которой можно столкнуться, например, в спиновых стеклах, путем туннелирования через такие барьеры.

Эта цель достигается путем отбора проб методом Монте-Карло.трансформированная функция, в которой отсутствует эта медленная динамика. В «стандартной форме»преобразование гласит $f_{STUN}:=1-\exp \left(-\gamma \cdot \left(E(x)-E_{o}\right)\right)$ где $E_{o}$— это самое низкое значение функции, найденное на данный момент. Это преобразование сохраняет места минимумов.

$f_{STUN}$ затем используется вместо $E$ в исходном алгоритме, дающем новую вероятность принятия $\min \left(1;\exp \left(-\beta \cdot \Delta f_{STUN}\right)\right)$

Эффект такого преобразования показан на графике.

туннелирование

Вариант постоянного туннелирования заключается в том, чтобы делать это только в случае ловли на локальном минимуме. $\gamma$ затем корректируется таким образом, чтобы выйти из минимума и найти более глобально оптимальное решение. Анализ флуктуаций с устранением тренда является рекомендуемым способом определения того, находится ли сигнал в ловушке локального минимума.

Другие подходы

• Имитация отжига
• Параллельный отпуск
• Генетический алгоритм
• Дифференциальная эволюция

Ссылки

• К. Хамахер (2006). «Адаптация в области стохастического туннелирования, глобальная оптимизация сложных потенциальных энергетических ландшафтов». Еврофиз. Летт. 74 (6): 944–950. Бибкод : 2006EL.....74..944H . дои : 10.1209/epl/i2006-10058-0 . S2CID   250761754 .
• К. Хамахер и В. Венцель (1999). «Масштабирование алгоритмов стохастической минимизации в идеальной воронкообразной среде». Физ. Преподобный Е. 59 (1): 938–941. arXiv : физика/9810035 . Бибкод : 1999PhRvE..59..938H . дои : 10.1103/PhysRevE.59.938 . S2CID   119096368 .
• В. Венцель и К. Хамахер (1999). «Стохастический туннельный подход для глобальной минимизации». Физ. Преподобный Летт. 82 (15): 3003–3007. arXiv : физика/9903008 . Бибкод : 1999PhRvL..82.3003W . doi : 10.1103/PhysRevLett.82.3003 . S2CID   5113626 .
• Николас Метрополис , Арианна В. Розенблут, Маршалл Н. Розенблут , Августа Х. Теллер и Эдвард Теллер (июнь 1953 г.). «Уравнение расчета состояния с помощью быстрых вычислительных машин» (PDF) . Журнал химической физики . 21 (6): 1087–1092. Бибкод : 1953ЖЧФ..21.1087М . дои : 10.1063/1.1699114 . ОСТИ   4390578 . S2CID   1046577 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
• Минцзе Линь (декабрь 2010 г.). «Улучшение размещения FPGA с помощью динамически адаптивного стохастического туннелирования» . Транзакции IEEE по автоматизированному проектированию интегральных схем и систем . 29 (12): 1858–1869. дои : 10.1109/tcad.2010.2061670 . S2CID   8706692 .