Меню Закрыть

Кластерные алгоритмы Монте-Карло

image_pdfimage_print

Многокластерный алгоритм Свендсена-Ванга и однокластерный Вольфа.

В последние годы предложен ряд новых алгоритмов для метода МК, позволяющих в той или иной степени преодолеть проблему критического замедления[4]. К ним можно отнести кластерные алгоритмы МК.

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

При переворачивании, конфигурация спинов сохраняется внутри кластера, изменения энергии происходит только из-за изменения конфигурации на периметре кластера. Также кластерные методы позволяют значительно уменьшить корреляционное время τ вблизи критической точки.

После определенного ряда исследований кластерные алгоритмы МКоказались весьма мощными, надежными и высокоэффективными инструментами исследования критических явления в различных системах и моделях. Для уменьшения эффектов критического замедления обычно используют кластерные алгоритмы Вольфа или Свендсена-Янга. Отличие этих алгоритмов заключается в том, что в случае однокластерного алгоритма Вольфа строится один кластер, который переворачивается с вероятностью, равной 1, а в случае многокластерного алгоритма Свендсена-Янга система разбивается на множество кластеров, каждый из которых переворачивается с вероятностью 1/2.

 Многокластерный алгоритм Свендсена-Янга.

  1. Последовательно просматривается решетка и связывается два ближайших спина i и j с вероятностью \(f=1-exp(-2/T)\), если si =sj .
  2. Создавая связи между ближайшими соседями, узлы образуют кластеры.
  3. Идентифицируются на решетке кластеры (множества спинов).
  4. Каждый кластер переворачивается с вероятностью ½.

Рассмотрим подробно работу алгоритма на примере решетки размером L=5[3]. В каждой ячейке решетки находится спин, направленный вверх или вниз. Решетка просматривается, начиная с левого нижнего угла. Два соседние, одинаково направленные спины связываются в кластер с вероятностью  f=1-exp(-2/T). Также у каждого спина проверяется состояние двух ближайших соседей, например, нижнего и левого.

На рисунке  представлен пример распределения кластеров спинов, образовавшихся в результате связывания. Кластер спинов может состоять из одного или большего количества спинов. После формирования кластеров спинов выполняется их маркировка, в результате чего образуется список, в с метками и значениями спина кластера. Затем список просматривается, и спины всех кластеров переворачиваются с вероятностью ½. Возможный исход изображен на рисунке  г, где были опрокинуты спины кластеров с метками 1, 3, 4, 5 и 8.

Однокластерный алгоритм Вольфа

Вольфом [2] был предложен кластерный алгоритм, немного отличающийся от алгоритма Свендсена-Ванга [1]. В алгоритме Вольфа на решетки образуется только один кластер, начиная с произвольно выбранного спина, затем с равной вероятностью ему присваивается новое значение 1 или -1. Ниже приведен алгоритм:

  1. Выбирается на решетке случайным образом i-ый спин и в дальнейшем рассматривается началом роста кластера, к которому присоединяются ближайшие соседние спины с вероятностью f=1-exp(-2/T), если si =sj. Рост кластера продолжается до тез пор, пока список непроверенных спинов исчерпывается.
  2. Созданному кластеру присваиваются новые значения спина 1 или -1 с равной вероятностью.

Рассмотрим детальнее работу алгоритма Вольфа на примере решетки размером L=5[3]. Выбрана была та же конфигурация спинов, что и в предыдущем примере. В начале выполнения алгоритма в качестве начала роста кластера случайным образом был выбран спин, отмеченный на рисунке а пунктирным кружком. В алгоритме Вольфа ближайшие соседи начального спина могут принадлежать к кластеру с вероятностью  f=1-exp(-2/T), если они направлены одинаково с начальным спином. Если спины соседей направлены противоположно, то они не могут быть присоединены к растущему кластеру. В ходе роста кластера ближайшие соседи каждого спина тестируются на их принадлежность к кластеру. Тестирование происходит один раз. Тестирование выполняется до тех пор, пока все потенциально возможные  спины-кандидаты на участие в кластере не будут протестированы. На рисунке б жирными линиями показаны связи, образованные соседними спинами, на рисунке в созданный кластер выделен серым цветом. После его формирования, ему было присвоено с вероятностью ½ новое значение равное -1, т. е. в данном случае произошел переворот спина. На рисунке  г изображена новая конфигурация спинов, полученная в результате работы алгоритма.

 

Перейдя по ссылке Моделирование модели Изинга, можно наблюдать модель в динамике, самостоятельно изменяя параметры. НА выбор предложены алгоритмы Метрополиса и Вольфа. При наглядном сравнении очень заметна разница в переворачивании спинов.

 

1. Swendsen R.H., Wang J.-S. Nonuniversal critical dynamics in Monte Carlo simulations // Physical Review Letters. V. 58. N. 2. P. 86.

2. Wolff U. Collective Monte Carlo Updating for Spin Systems // Physical Review Letters. V. 62. P. 361.

3.Mitsutake A., Sugita Y., Okamoto Y. Generalized-Ensemble Algorithms for Molecular Simulations of Biopolimers // preprint cond-mat/0012021.

4. Л. А. Булавин, Н.В. Выгорницкий, Н. И. Лебкова. Компьютерное моделирование физических систем. М.: Издательский Дом «Интеллект», 2011. — 354 с.

 

Связанные записи