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

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

Идея

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

Методы оптимизации, основанные на методе Монте-Карло , производят выборку целевой функции путем случайного «перескока» от текущего вектора решения к другому с разницей в значении функции . Допустимая вероятность такого пробного прыжка в большинстве случаев выбирается равной ( критерий Метрополиса ) с соответствующим параметром . ${\ displaystyle \ Delta E}$${\ Displaystyle \ мин \ влево (1; \ ехр \ влево (- \ бета \ CDOT \ Дельта Е \ вправо) \ вправо)}$${\ 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 \ мин \ влево (1; \ ехр \ влево (- \ бета \ cdot \ Delta f_ {STUN} \ вправо) \ вправо)}$

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

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

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

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

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

Ссылки

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