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

В числовой анализ, стохастическое туннелирование (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). «Адаптация в стохастической туннельной глобальной оптимизации сложных потенциальных энергетических ландшафтов». Europhys. Lett. 74 (6): 944–950. Bibcode:2006EL ..... 74..944H. Дои:10.1209 / epl / i2006-10058-0.
• К. Хамахер и В. Венцель (1999). "Поведение масштабирования алгоритмов стохастической минимизации в идеальной воронке ландшафта". Phys. Ред. E. 59 (1): 938–941. arXiv:физика / 9810035. Bibcode:1999PhRvE..59..938H. Дои:10.1103 / PhysRevE.59.938.
• В. Венцель и К. Хамахер (1999). «Стохастический туннельный подход для глобальной минимизации». Phys. Rev. Lett. 82 (15): 3003–3007. arXiv:физика / 9903008. Bibcode:1999PhRvL..82.3003W. Дои:10.1103 / PhysRevLett.82.3003.
• Николай Метрополис, Арианна В. Розенблут, Маршалл Н. Розенблют, Огаста Х. Теллер и Эдвард Теллер (Июнь 1953 г.). «Уравнение состояний на быстрых вычислительных машинах» (PDF). Журнал химической физики. 21 (6): 1087–1092. Bibcode:1953ЖЧФ..21.1087М. Дои:10.1063/1.1699114.
• Минцзе Линь (декабрь 2010 г.). «Улучшение размещения ПЛИС с помощью динамически адаптивного стохастического туннелирования». IEEE Transactions по автоматизированному проектированию интегральных схем и систем. 29 (12): 1858–1869. Дои:10.1109 / tcad.2010.2061670.