Мультиканонический ансамбль

В статистике и физике мультиканонический ансамбль (также называемый мультиканонической выборкой или плоской гистограммой ) представляет собой метод выборки Монте-Карло с использованием цепи Маркова , который использует алгоритм Метрополиса-Гастингса для вычисления интегралов , где подынтегральное выражение имеет грубый ландшафт с несколькими локальными минимумами . Он производит выборку состояний в соответствии с обратной плотностью состояний : ^[1] который должен быть известен априори или быть вычислен с использованием других методов, таких как алгоритм Ванга и Ландау . ^[2] Мультиканоническая выборка — важный метод для спиновых систем, таких как модель Изинга или спиновые очки . ^[1]^[3]^[4]

Мотивация

В системах с большим числом степеней свободы, таких как спиновые системы, интегрирование Монте-Карло требуется . В этой интеграции выборка по важности и, в частности, алгоритм Метрополиса . очень важным методом является ^[3] Однако алгоритм Метрополиса выбирает состояния в соответствии с $\exp(-\beta E)$ где бета — обратная температура. Это означает, что барьер энергетический $\Delta E$ в энергетическом спектре экспоненциально трудно преодолеть. ^[1] Системы с несколькими локальными минимумами энергии, такие как модель Поттса, становится трудными для выборки, поскольку алгоритм застревает в локальных минимумах системы. ^[3] Это мотивирует другие подходы, а именно, другие распределения выборки.

Обзор

Мультиканонический ансамбль использует алгоритм Метрополиса – Гастингса с распределением выборки, определяемым обратной плотностью состояний системы, в отличие от распределения выборки. $\exp(-\beta E)$ алгоритма Метрополиса. ^[1] При таком выборе в среднем количество состояний, выбранных при каждой энергии, является постоянным, т.е. это моделирование с «плоской гистограммой» по энергии. Это приводит к алгоритму, для которого энергетические барьеры уже не сложно преодолеть. Еще одним преимуществом перед алгоритмом Метрополиса является то, что выборка не зависит от температуры системы, а это означает, что одно моделирование позволяет оценить термодинамические переменные для всех температур (отсюда и название «мультиканонический»: несколько температур). Это большой шаг вперед в изучении фазовых переходов первого рода . ^[1]

Самая большая проблема при создании мультиканонического ансамбля состоит в том, что плотность состояний должна быть известна априори . ^[2]^[3] Одним из важных вкладов в мультиканоническую выборку стал алгоритм Ванга и Ландау , который асимптотически сходится к мультиканоническому ансамблю при вычислении плотности состояний во время сходимости. ^[2]

Мультиканонический ансамбль не ограничивается физическими системами. которые имеют функцию стоимости F. Его можно использовать в абстрактных системах , Используя плотность состояний относительно F, метод становится общим для вычисления интегралов более высокой размерности или поиска локальных минимумов. ^[5]

Мотивация

Рассмотрим систему и ее фазовое пространство. $\Omega$ характеризуется конфигурацией ${\boldsymbol {r}}$ в $\Omega$ и функция «стоимости» F из фазового пространства системы в одномерное пространство. $\Gamma$ : $F(\Omega )=\Gamma =[\Gamma _{\min },\Gamma _{\max }]$ , спектр F .

пример:

The Ising model with N sites is an example of such a system; the phase-space is a discrete phase-space defined by all possible configurations of N spins

{\boldsymbol {r}}=(\sigma _{1},\ldots ,\sigma _{i},\ldots ,\sigma _{N})

where

\sigma _{i}\in \{-1,1\}

. The cost function is the Hamiltonian of the system:

H({\boldsymbol {r}})=-\sum _{\langle i~j\rangle }J_{ij}(1-\sigma _{i}\sigma _{j}),

where $<i,j>$ is the sum over neighborhoods and $J_{ij}$ is the interaction matrix.

The energy spectrum is $\Gamma =[E_{\min },E_{\max }]$ which, in this case, depends on the particular $J_{ij}$ used. If all $J_{ij}$ are 1 (the ferromagnetic Ising model), $E_{\min }=0$ (e.g. all spins are 1.) and $E_{\max }=2DN$ (half spins are up, half spins are down). Also notice that in this system, $\Gamma \in \mathbb {Z}$

Вычисление средней величины $\langle Q\rangle$ по фазовому пространству требует вычисления интеграла:

\langle Q\rangle =\int _{\Omega }Q({\boldsymbol {r}})P_{r}({\boldsymbol {r}})\,d{\boldsymbol {r}}

где $P_{r}({\boldsymbol {r}})$ — это вес каждого состояния (например, $P_{r}({\boldsymbol {r}})=1/V$ соответствуют равномерно распределенным состояниям).

Когда Q не зависит от конкретного состояния, а только от конкретного значения F состояния. $F({\boldsymbol {r}})=F_{\boldsymbol {r}}$ ,формула для $\langle Q\rangle$ может быть проинтегрировано по f путем добавления дельта-функции Дирака и записано как

{\begin{aligned}\langle Q\rangle &=\int _{\Gamma _{\min }}^{\Gamma _{\max }}\int _{\Omega }Q(F_{\boldsymbol {r}})P_{r}(F_{\boldsymbol {r}})\delta (f-F_{\boldsymbol {r}})\,d{\boldsymbol {r}}\,df\\&=\int _{\Gamma _{\min }}^{\Gamma _{\max }}Q(f)\int _{\Omega }\delta (f-F_{\boldsymbol {r}})P_{r}(F_{\boldsymbol {r}})\,d{\boldsymbol {r}}\,df\\&=\int _{\Gamma _{\min }}^{\Gamma _{\max }}Q(f)P(f)\,df\\\end{aligned}}

где

P(f)=\int _{\Omega }P_{r}(r)\delta (f-F({\boldsymbol {r}}))\,d{\boldsymbol {r}}

является маргинальным распределением F.

пример:

A system in contact with a heat bath at inverse temperature

\beta

is an example for computing this kind of integral. For instance, the mean energy of the system is weighted by the Boltzmann factor:

\langle E\rangle ={\frac {1}{V}}\int _{\Omega }H_{\boldsymbol {r}}{\frac {e^{-\beta H_{\boldsymbol {r}}}}{Z}}d{\boldsymbol {r}}

where

Z={\frac {1}{V}}\int _{\Omega }e^{-\beta H_{\boldsymbol {r}}}d{\boldsymbol {r}}.

The marginal distribution $P(E)$ is given by

P(E)={\frac {1}{V}}\int _{\Omega }e^{-\beta H_{\boldsymbol {r}}}\delta (E-H_{\boldsymbol {r}})d{\boldsymbol {r}}=e^{-\beta E}{\frac {1}{V}}\int _{\Omega }\delta (E-H_{\boldsymbol {r}})d{\boldsymbol {r}}=e^{-\beta E}\rho (E)

where $\rho (E)$ is the density of states.

The average energy $\langle E\rangle$ is then given by

\langle E\rangle =\int _{E_{\min }}^{E_{\max }}EP(E)\,dE

Когда система имеет большое число степеней свободы, аналитическое выражение для $\langle Q\rangle$ часто трудно получить, и вычислении при $\langle Q\rangle$ . В простейшей формулировке метод выбирает N равномерно распределенных состояний. ${\boldsymbol {r}}_{i}\in \Omega$ и использует оценку

{\overline {Q}}_{N}=\sum _{i=1}^{N}Q({\boldsymbol {r}}_{i})VP_{r}({\boldsymbol {r}}_{i})

для вычислений $\langle Q\rangle$ потому что ${\overline {Q}}_{N}$ почти наверняка сходится к $\langle Q\rangle$ по сильному закону больших чисел :

\lim _{N\rightarrow \infty }{\overline {Q}}_{N}=\langle Q\rangle .

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

пример

Для улучшения этой сходимости алгоритм Метрополиса – Гастингса был предложен . Как правило, идея методов Монте-Карло состоит в использовании выборки по важности для улучшения сходимости оценщика. ${\overline {Q}}_{N}$ путем выборки состояний по произвольному распределению $\pi ({\boldsymbol {r}})$ и используйте соответствующую оценку:

{\overline {Q}}_{N}=\sum _{i=1}^{N}Q({\boldsymbol {r}}_{i})\pi ^{-1}({\boldsymbol {r}}_{i})P_{r}({\boldsymbol {r}}_{i})

.

Эта оценка обобщает оценку среднего значения для выборок, взятых из произвольного распределения. Поэтому, когда $\pi ({\boldsymbol {r}})$ является равномерным распределением, оно соответствует тому, которое использовалось выше для равномерной выборки.

Когда система представляет собой физическую систему, находящуюся в контакте с тепловой баней, каждое состояние ${\boldsymbol {r}}$ взвешивается в соответствии с фактором Больцмана , $P_{r}({\boldsymbol {r}}_{i})\propto \exp(-\beta F_{\boldsymbol {r}})$ .В Монте-Карло канонический ансамбль определяется выбором $\pi ({\boldsymbol {r}})$ быть пропорциональным $P_{r}({\boldsymbol {r}}_{i})$ . В этой ситуации оценка соответствует простому среднему арифметическому:

{\overline {Q}}_{N}={\frac {1}{N}}\sum _{i=1}^{N}Q({\boldsymbol {r}}_{i})

Исторически это произошло потому, что первоначальная идея ^[6] заключалась в использовании алгоритма Метрополиса – Гастингса для вычисления средних значений для системы, находящейся в контакте с тепловой баней, где вес задается фактором Больцмана, $P({\boldsymbol {x}})\propto \exp(-\beta E({\boldsymbol {r}}))$ . ^[3]

Хотя часто бывает, что выборочное распределение $\pi$ выбрано распределение веса $P_{r}$ , это не обязательно так.Одна из ситуаций, когда канонический ансамбль не является эффективным выбором, — это когда для сходимости требуется сколь угодно много времени. ^[1]Одна из ситуаций, когда это происходит, — это когда функция F имеет несколько локальных минимумов.Вычислительные затраты алгоритма на выход из определенной области с локальным минимумом экспоненциально возрастают с увеличением минимального значения функции стоимости. То есть, чем глубже минимум, тем больше времени алгоритм там проводит, и тем труднее будет уйти (экспоненциально растет с глубиной локального минимума).

Один из способов избежать застревания в локальных минимумах функции стоимости — сделать метод выборки «невидимым» для локальных минимумов. Это основа мультиканонического ансамбля.

Мультиканонический ансамбль

Мультиканонический ансамбль определяется выбором распределения выборки, которое будет

\pi ({\boldsymbol {r}})\propto {\frac {1}{P(F_{\boldsymbol {r}})}}

где $P(f)$ — предельное распределение F, определенное выше.Следствием этого выбора является то, что среднее количество выборок с заданным значением f , m(f), определяется выражением

m(f)=\int _{\Omega }\delta (f-F_{\boldsymbol {r}})\pi ({\boldsymbol {r}})P_{r}({\boldsymbol {r}})\,d{\boldsymbol {r}}\propto \int _{\Omega }\delta (f-F_{\boldsymbol {r}})P_{r}({\boldsymbol {r}}){\frac {1}{P(F_{\boldsymbol {r}})}}d{\boldsymbol {r}}={\frac {1}{P(f)}}\int _{\Omega }\delta (f-F_{\boldsymbol {r}})P_{r}({\boldsymbol {r}})d{\boldsymbol {r}}=1

то есть среднее количество выборок не зависит от f : все затраты f выбираются одинаково независимо от того, более или менее вероятны они. Это объясняет название «плоская гистограмма». Для систем, контактирующих с тепловой баней, отбор проб не зависит от температуры, и одно моделирование позволяет изучить все температуры.

пример:

On the ferromagnetic Ising model with N sites (exemplified on previous section), the density of states can be analytically computed. In this case, a multicanonical ensemble can be used to compute any other quantity Q by sampling the system according to

P({\boldsymbol {r}})

and using the proper estimator

{\overline {Q}}

defined on the previous section.

Время туннелирования и критическое замедление

Как и в любом другом методе Монте-Карло, существуют корреляции выборок, взятых из $P({\boldsymbol {r}})$ . Типичным измерением корреляции является время туннелирования . Время туннелирования определяется количеством шагов Маркова (цепи Маркова), которые необходимы моделированию для выполнения обхода между минимумом и максимумом спектра F . Одной из причин использования времени туннелирования является то, что когда оно пересекает спектры, оно проходит через область максимума плотности состояний, тем самым декоррелируя процесс. С другой стороны, использование туда и обратно гарантирует, что система посещает весь спектр.

Поскольку гистограмма плоская по переменной F , мультиканонический ансамбль можно рассматривать как диффузионный процесс (т.е. случайное блуждание ) на одномерной линии F. значений Детальный баланс процесса диктует отсутствие отклонений в процессе. ^[7] Это означает, что время туннелирования в локальной динамике должно масштабироваться как диффузионный процесс, и, таким образом, время туннелирования должно масштабироваться квадратично с размером спектра N :

\tau _{tt}\propto N^{2}

Однако в некоторых системах (наиболее парадигматичной является модель Изинга) масштабирование страдает от критического замедления: $N^{2+z}$ где $z>0$ зависит от конкретной системы. ^[4]

Нелокальная динамика была разработана для улучшения масштабирования до квадратичного масштабирования. ^[8] (см. алгоритм Вольфа ), преодолевая критическое замедление. Однако до сих пор остается открытым вопрос, существует ли локальная динамика, которая не страдает от критического замедления в спиновых системах, подобных модели Изинга.

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж Берг, Б.; Нейхаус, Т. (1992). «Мультиканонический ансамбль: новый подход к моделированию фазовых переходов первого рода». Письма о физических отзывах . 68 (1): 9–12. arXiv : hep-lat/9202004 . Бибкод : 1992PhRvL..68....9B . дои : 10.1103/PhysRevLett.68.9 . ПМИД 10045099 . S2CID 19478641 .
^ Jump up to: ^а ^б ^с Ван, Ф.; Ландау, Д. (2001). «Эффективный многодиапазонный алгоритм случайного блуждания для расчета плотности состояний». Письма о физических отзывах . 86 (10): 2050–2053. arXiv : cond-mat/0011174 . Бибкод : 2001PhRvL..86.2050W . doi : 10.1103/PhysRevLett.86.2050 . ПМИД 11289852 . S2CID 2941153 .
^ Jump up to: ^а ^б ^с ^д ^и Ньюманн, МЭЖ; Баркема, GT (2002). Методы Монте-Карло в статистической физике . США: Издательство Оксфордского университета. ISBN 0198517971 .
^ Jump up to: ^а ^б Даял, П.; Требст, С.; Вессель, С.; Вюрц, Д.; Тройер, М.; Сабхапандит, С.; Копперсмит, С. (2004). «Ограничения производительности методов плоских гистограмм». Письма о физических отзывах . 92 (9): 097201. arXiv : cond-mat/0306108 . Бибкод : 2004PhRvL..92i7201D . doi : 10.1103/PhysRevLett.92.097201 . ПМИД 15089505 . S2CID 1128445 .
^ Ли, Дж.; Чой, М. (1994). «Оптимизация путем мультиканонического отжига и задача коммивояжера». Физический обзор E . 50 (2): R651–R654. Бибкод : 1994PhRvE..50..651L . дои : 10.1103/PhysRevE.50.R651 . ПМИД 9962167 .
^ Метрополис, Северная Каролина; Розенблут, AW; Розенблут, Миннесота; Теллер, А.Х.; Теллер, Э. (1953). «Уравнение вычислений состояния с помощью быстрых вычислительных машин». Журнал химической физики . 21 (6): 1087. Бибкод : 1953ЖЧФ..21.1087М . дои : 10.1063/1.1699114 . ОСТИ 4390578 . S2CID 1046577 .
^ Роберт, Кристиан; Казелла, Джордж (2004). Статистические методы Монте-Карло . Спрингер. ISBN 978-0-387-21239-5 .
^ Вольф, У. (1989). «Коллективное обновление Монте-Карло для спиновых систем». Письма о физических отзывах . 62 (4): 361–364. Бибкод : 1989PhRvL..62..361W . дои : 10.1103/PhysRevLett.62.361 . ПМИД 10040213 .

[Berg-1] Jump up to: ^а ^б ^с ^д ^и ^ж Берг, Б.; Нейхаус, Т. (1992). «Мультиканонический ансамбль: новый подход к моделированию фазовых переходов первого рода». Письма о физических отзывах . 68 (1): 9–12. arXiv : hep-lat/9202004 . Бибкод : 1992PhRvL..68....9B . дои : 10.1103/PhysRevLett.68.9 . ПМИД 10045099 . S2CID 19478641 .

[Landau-2] Jump up to: ^а ^б ^с Ван, Ф.; Ландау, Д. (2001). «Эффективный многодиапазонный алгоритм случайного блуждания для расчета плотности состояний». Письма о физических отзывах . 86 (10): 2050–2053. arXiv : cond-mat/0011174 . Бибкод : 2001PhRvL..86.2050W . doi : 10.1103/PhysRevLett.86.2050 . ПМИД 11289852 . S2CID 2941153 .

[Newmann-3] Jump up to: ^а ^б ^с ^д ^и Ньюманн, МЭЖ; Баркема, GT (2002). Методы Монте-Карло в статистической физике . США: Издательство Оксфордского университета. ISBN 0198517971 .

[Dayal-4] Jump up to: ^а ^б Даял, П.; Требст, С.; Вессель, С.; Вюрц, Д.; Тройер, М.; Сабхапандит, С.; Копперсмит, С. (2004). «Ограничения производительности методов плоских гистограмм». Письма о физических отзывах . 92 (9): 097201. arXiv : cond-mat/0306108 . Бибкод : 2004PhRvL..92i7201D . doi : 10.1103/PhysRevLett.92.097201 . ПМИД 15089505 . S2CID 1128445 .

[Lee-5] Ли, Дж.; Чой, М. (1994). «Оптимизация путем мультиканонического отжига и задача коммивояжера». Физический обзор E . 50 (2): R651–R654. Бибкод : 1994PhRvE..50..651L . дои : 10.1103/PhysRevE.50.R651 . ПМИД 9962167 .

[Metropolis-6] Метрополис, Северная Каролина; Розенблут, AW; Розенблут, Миннесота; Теллер, А.Х.; Теллер, Э. (1953). «Уравнение вычислений состояния с помощью быстрых вычислительных машин». Журнал химической физики . 21 (6): 1087. Бибкод : 1953ЖЧФ..21.1087М . дои : 10.1063/1.1699114 . ОСТИ 4390578 . S2CID 1046577 .

[Robert-7] Роберт, Кристиан; Казелла, Джордж (2004). Статистические методы Монте-Карло . Спрингер. ISBN 978-0-387-21239-5 .

[Wolff-8] Вольф, У. (1989). «Коллективное обновление Монте-Карло для спиновых систем». Письма о физических отзывах . 62 (4): 361–364. Бибкод : 1989PhRvL..62..361W . дои : 10.1103/PhysRevLett.62.361 . ПМИД 10040213 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]