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

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

Идея

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

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

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

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

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

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

Динамически адаптивное стохастическое туннелирование

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

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

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

Рекомендации

• К. Хамахер (2006). «Адаптация в области стохастического туннелирования, глобальная оптимизация сложных потенциальных энергетических ландшафтов». Еврофиз. Летт. 74 (6): 944–950. Бибкод : 2006EL.....74..944H. doi : 10.1209/epl/i2006-10058-0. S2CID  250761754.
• К. Хамахер и В. Венцель (1999). «Масштабирование алгоритмов стохастической минимизации в идеальной воронкообразной среде». Физ. Преподобный Е. 59 (1): 938–941. arXiv : физика/9810035 . Бибкод : 1999PhRvE..59..938H. doi : 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.