Алгоритм Ванга — Ландау

Алгоритм Ванга-Ландау, предложенный Фугао Вангом и Дэвидом Ландау[1], это метод Монте-Карло, предназначенный для расчета плотности состояний системы. Метод выполняет немарковские случайные переходы для построения плотности состояний, посещая все возможные состояния. Алгоритм Ванга и Ландау, это важный для получения плотности состояний метод, требуемый для выполнения мультиканонического моделирования

Алгоритм Ванга-Ландау может быть применен к любой системе, которая характеризуется некоторым параметром (например, энергией, объемом и др.). К примеру, он может быть использован для численного интегрирования[2] и моделирования белков[3][4].

Описание

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

Алгоритм

Рассмотрим систему в фазовом пространстве и энергию , изменение которой ограничено диапазоном . Пусть рассматриваемая система имеет плотность вероятности , которую нам требуется посчитать. Поскольку алгоритм Ванга и Ландау работает с дискретным спектром энергии, диапазон разбивается на конечное число () равных отрезков («ящиков»), размер которых равен . Таким образом:

.

С учетом этого дискретного спектра, алгоритм имеет следующие начальные условия:

  • (используется далее, как добавка к энтропии после каждого принятого шага)
  • Выбирается случайная конфигурация системы

Алгоритм выполняет моделирование в мультиканоническом ансамбле: случайное блуждание Метрополиса-Гастингса по фазовому пространству системы с распределением вероятности и вероятностью генерации нового состояния, данной распределением вероятности , которое выбирается произвольно (обычно любое состояние может быть сгенерировано с равной вероятностью). В процессе моделирования, посещение каждого «ящика» записывается в гистограмму (то есть, значение увеличивается на единицу). Как и в алгоритме Метрополиса-Гастингса, генерация и принятие нового состояния выполняется следующим образом:

  1. генерация нового состояния согласно распределению вероятности
  2. принятие/отклонение нового состояния, производится следующим образом:

Если энтропия нового состояния меньше текущего, то оно сразу принимается. Если же энтропия увеличилась, то новое состояние принимается с вероятностью: , где и .

То есть, общая формула выглядит следующим образом:

.

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

После каждого шага генерации-принятия система переходит в некоторое состояние , значение увеличивается на единицу, а также выполняется следующее изменение:

Это важный шаг алгоритма, и это то, что делает алгоритм Ванга-Ландау немарковским: случайный процесс теперь зависит от истории процесса. Таким образом, когда в следующий раз будет предложено состояние с энергией , это состояние будет отклонено с большей вероятностью; в этом смысле, алгоритм принуждает систему посещать все состояния с одинаковой частотой. Как следствие, гистограмма становится все более и более плоской. Хотя, эта равномерность зависит от того, насколько посчитанная энтропия близка к точной энтропии, что зависит от . Для улучшения приближения точной энтропии (и, таким образом, равномерности гистограммы), уменьшается после шагов генерации-принятия:

Через некоторое время было показано, что при изменении постоянным делением на два алгоритм может не сходиться[5]. Небольшая модификация метода Ванга-Ландау позволяет избежать этого: производится деление не на два, а на , при чем пропорционально шагу моделирования.

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

Пример кода

Ниже показан пример кода на Python, в котором предполагается симметричность функции распределения :

currentEnergy = system.randomConfiguration() # случайная генерация начального состояния системы
while (f > epsilon):
    system.proposeConfiguration() # генерация новой конфигурации
    proposedEnergy = system.proposedEnergy() # вычисление энергии нового состояния

    if (random() < exp(entropy[currentEnergy]-entropy[proposedEnergy])):
        # если принято, обновляем энергию и систему
        currentEnergy = proposedEnergy
        system.acceptProposedConfiguration()
    else:
        # если отклонено
        system.rejectProposedConfiguration()
    
    H[currentEnergy] += 1
    entropy[currentEnergy] += f
    
    if (isFlat(H)): # isFlat проверяет достаточно ли гладкая гистограмма (например, 95%)
        H[:] = 0
        f *= 0.5 # refine the f parameter

Примечания

  1. Wang, Fugao & Landau, D. P. (Mar 2001). «Efficient, Multiple-Range Random Walk Algorithm to Calculate the Density of States». Phys. Rev. Lett. American Physical Society. 86 (10): 2050—2053. arXiv (недоступная ссылка). Bibcode: . doi: . PMID .
  2. R. E. Belardinelli and S. Manzi and V. D. Pereyra (Dec 2008). «Analysis of the convergence of the 1∕t and Wang-Landau algorithms in the calculation of multidimensional integrals». Phys. Rev. E. American Physical Society. 78 (6): 067701. arXiv:  (недоступная ссылка). Bibcode: . doi: .
  3. P. Ojeda and M. Garcia and A. Londono and N.Y. Chen (Feb 2009). «Monte Carlo Simulations of Proteins in Cages: Influence of Confinement on the Stability of Intermediate States». Biophys. Jour. Biophysical Society. 96 (3): 1076—1082. Bibcode:2009BpJ….96.1076O. doi:10.1529/biophysj.107.125369
  4. P. Ojeda & M. Garcia (Jul 2010). «Electric Field-Driven Disruption of a Native beta-Sheet Protein Conformation and Generation of alpha-Helix-Structure». Biophys. Jour. Biophysical Society. 99 (2): 595—599. Bibcode:2009BpJ….96.1076O. doi:10.1016/j.bpj.2010.04.040. PMC 2905109Freely accessible. PMID 20643079
  5. Belardinelli, R. E. & Pereyra, V. D. (2007). «Wang-Landau algorithm: A theoretical analysis of the saturation of the error». Jour. Chem. Phys. 127 (18): 184105. arXiv: cond-mat/0702414Freely accessible. Bibcode:2007JChPh.127r4105B. doi:10.1063/1.2803061
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.