왕과 란다우 알고리즘

푸가오 왕과 데이비드 P. 랜다우가 제안한 왕과 란다우 알고리즘은 시스템의 상태 밀도를 추정하기 위해 고안된 몬테카를로 방법이다.^[1]이 방법은 모든 가용 에너지 스펙트럼을 신속하게 방문하여 상태 밀도를 구축하기 위해 비 마르코비안 무작위 워크를 수행한다.왕과 란다우 알고리즘은 다원적 시뮬레이션을 수행하는 데 필요한 상태 밀도를 얻기 위한 중요한 방법이다.

Wang-Landau 알고리즘은 비용(또는 에너지) 함수로 특징지어지는 어떤 시스템에도 적용될 수 있다.예를 들어, 그것은 수치적 통합의^[2] 해법과 단백질의 접힘에 적용되었다.^[3][4]왕-란다우 표본 추출은 메타다이나믹스 알고리즘과 관련이 있다.^[5]

개요

Wang과 Landau 알고리즘은 비용 함수로 특징지어지는 시스템의 상태 밀도에 대한 추정치를 얻기 위해 사용된다.비 마르코비아 확률적 과정을 사용하며, 이는 점증적으로 다원적 앙상블에 수렴한다(^[1]즉, 상태 밀도에 역행하는 샘플링 분포를 갖는 Metropolitan-Hastings 알고리즘).주요 결과는 이러한 샘플링 분포가 에너지 장벽이 보이지 않는 시뮬레이션으로 이어진다는 것이다.이것은 알고리즘이 메트로폴리스 알고리즘보다 훨씬 빨리 접근 가능한 모든 상태(호감하고 덜 호감)를 방문한다는 것을 의미한다.^[6]

알고리즘.

Consider a system defined on a phase space ${\displaystyle \Omega }$, and a cost function, E, (e.g. the energy), bounded on a spectrum ${\displaystyle E\in \Gamma =[E_{\min },E_{\max }]}$, which has an associated density of states ${\displaystyle \rho (E)}$, which is to be estimated.The estimator is ${\displaystyle {\hat {\rho }}(E)\equiv \exp(S(E))}$. Because Wang and Landau algorithm works in discrete spectra,^[1] the spectrum ${\displaystyle \Gamma }$ is divided in N discrete values with a difference between them of ${\displaystyle \Delta }$, such that

${\displaystyle N}$= ${\displaystyle E\frac{{}_{}}{}}$ ${\displaystyle \frac{{max}_{}}{}}$- ${\displaystyle \frac{{Emin}_{}}{}}$ ${\displaystyle \frac{{}_{}}{\mathrm{}}}$ ${\$ N$={\frac {E_{\max }-E_{\min }{\delta$

이 이산 스펙트럼에 따라 알고리즘은 다음을 통해 초기화된다.

• 마이크로캐논 엔트로피의 모든 항목을 0으로 설정, $S{\displaystyle ({}_{}}$ ${\displaystyle i_{}}$)${\displaystyle }$= 0 ${\displaystyle i}$= ${\displaystyle 1}$,${\displaystyle 2}$,${\displaystyle }$.${\displaystyle }$.${\displaystyle }$N ${\displaystyle$ S$(E_{i}}=0\\ \ i=$1,$2,...,N}$
• ${\displaystyle \mathrm{초기화}}$${\displaystyle }$f = 1 ${\displaystyle f=1}$및
• 임의 구성 $r{\displaystyle \mathit{}}$ ${\displaystyle \in }$ ${\displaystyle \mathrm{\Omega }}$ ${\displaystyle {\boldsymbol{r}\in \Oomega$

The algorithm then performs a multicanonical ensemble simulation:^[1] a Metropolis–Hastings random walk in the phase space of the system with a probability distribution given by ${\displaystyle P({\boldsymbol {r}})=1/{\hat {\rho }}(E({\boldsymbol {r}}))$$=\exp(-S(E({\boldsymbol {r}})))}$ and a probability of proposing a new state given by a probability distribution ${\displaystyle g({\boldsymbol {r}}\rightarrow {\boldsymbol {r}}')}$. A histogram ${\displaystyle H(E)}$ of visited energies is stored.메트로폴리스-해스팅 알고리즘에서와 마찬가지로 제안-수용 단계가 수행되며, 다음과 같이 구성된다(메트로폴리스-해스팅 알고리즘 개요 참조).

1. 임의 제안 분포 $g{\displaystyle (r\mathit{}}$→ ${\displaystyle {\mathit{}}^{}}$ $){\$$displaystyle$ g$({\$boldsymbol${r$}}}\$displaystyle g({\boldsymbol{r}\boldsymbol {r}}})$에 따른 상태 $.$
2. 에 따라 제안된 주를 받아들이다/거부하다

${\displaystyle A({\boldsymbol {r}}\rightarrow {\boldsymbol {r}}')=\min \left(1,e^{S-S'}{\frac {g({\boldsymbol {r}}'\rightarrow {\boldsymbol {r}})}{g({\boldsymbol {r}}\rightarrow {\boldsymbol {r}}')}}\right)}$

여기서 $S{\displaystyle }$= ${\displaystyle S(}$ ${\displaystyle E\mathit{}}$( ${\displaystyle r}$)${\displaystyle S=S(E)({\boldsymbol{r}})}$ 및$$ $S{\displaystyle {}^{}=}$ = ${\displaystyle S(E}$ ( ${\displaystyle {\mathit{}}^{}{}^{}}$)${\displaystyle$ S$'=S({\boldsymbol {r$

각 제안-수락 단계 후 시스템은 특정 값 ${\displaystyle {Ei}_{}}$ ${\$ $H{\displaystyle ({Ei}_{}}$) ${\displaystyle H(E_{i}})$로 전송되며$$ 다음 업데이트가 수행된다.

${\displaystyle S}$( ${\displaystyle E_{}}$ ${\displaystyle {}_{}}$) ${\displaystyle \leftarrow }$ ${\displaystyle S}$( E ${\displaystyle i_{}}$)${\displaystyle }$+ f ${\displaystyle S(E_{i})\왼쪽$ 화살표 $S(E_{i}+f}$.

이것이 알고리즘의 중요한 단계로서 왕과 란다우 알고리즘을 비마코비안적으로 만드는 것이다: 이제 확률적 과정은 프로세스의 역사에 달려 있다.따라서 다음에 특정 에너지 $E{\displaystyle {}_{}}$ ${\$를 가진 주에 제안이 있을 때 그러한 제안은 이제 더 거부될 가능성이 높다. 이러한 의미에서 알고리즘은 시스템이 모든 스펙트럼을 동등하게 방문하도록 강제한다.^[1]그 결과 히스토그램 $H{\displaystyle (E}$) ${\디스플레이$ 스타일 $H(E)}$이(가) 점점 더 평탄해진다.그러나 이 평탄도는 계산된 엔트로피가 정확한 엔트로피에 대해 얼마나 잘 추정하느냐에 따라 달라지는데, 이는 당연히 f의 값에 따라 달라진다.^[7]정확한 엔트로피(따라서 히스토그램의 평탄도)에 더 잘 근사하게 하려면 M 제안-수락 단계 후에 f를 줄인다.

${\displaystyle f}$ ${\displaystyle \leftarrow }$ ${\displaystyle f}$/ ${\displaystyle 2\mathrm{}}$ ${\displaystyle f\leftarrow f/2$

지속적으로 2로 나누어 f를 업데이트하면 포화 오차가 발생할 수 있다는 것이 나중에 밝혀졌다.^[7]이 문제를 피하기 위해 Wang과 Landau 방법을 약간 수정하면 1/${\displaystyle t}$ ${\displaystyle$ 1$/t}$에 비례하는 f 계수를 사용하는 것이다$.$ 여기서 $t{\displaystyle }$ ${\displaystyle t}$은 시뮬레이션 단계 수에 비례한다$$.^[7]

테스트 시스템

우리는 조화 발진기 전위에 대한 DOS를 얻기를 원한다.

${\displaystyle E(x)=x^{2},\,}$

분석 DOS는 다음에 의해 주어진다.

${\displaystyle \rho(E)=\int \delta(E(x)-E)\,dx=\int \dx,}$

우리가 얻은 마지막 적분을 수행함으로써

${\displaystyle \rho(E)\propto {\begin{case}E^{-1}/2}}: \x\in \mathb {R} ^{1}\{\text{const}, \mathb {R} \mathb {R} ^{2}\E^{1/2}, }}\x\in \mathb {R} ^{3}\case}$

일반적으로 다차원 고조파 오실레이터에 대한 DOS는 E의 어떤 힘에 의해 주어지며, 지수는 시스템 차원의 함수가 될 것이다.

따라서 우리는 상태 밀도의 분석 형태를 이미 알고 있기 때문에 단순한 고조파 발진기를 사용하여 왕-란도 알고리즘의 정확성을 시험할 수 있다.따라서 ${\displaystyle \mathrm{왕-란다우}}$ 알고리즘에서 얻은$$ $상태{\displaystyle \stackrel{}{}}$ ${\displaystyle \stackrel{}{^}}$ (${\displaystyle }$E${\displaystyle }$) ${\displaystyle {\hat{\rho }}}}$의 추정 밀도를 $\rho {\displaystyle }$(${\displaystyle E}$ ${\displaystyle )}$ ${\displaysty \rho (E)}$와 비교한다$.$

샘플코드

다음은 Python에서 Wang-Landau 알고리즘의 샘플 코드인데, 여기서는 대칭 제안 분포 g가 사용된다고 가정한다.

${\displaystyle g({\boldsymbol{x}'\오른쪽 화살표 {\\sysymbol {x}=g\\\symbol {\sysymbol}}}$

이 코드는 연구 중인 기본 시스템인 "시스템"을 고려한다.

전류 에너지 = 계통.임의 구성()  # 임의의 초기 구성  하는 동안에 (f > 엡실론):     계통.구성 제안()  # 제안된 구성이 제안됨     프로포즈 에너지 = 계통.프로포즈 에너지()  # 계산된 제안된 구성의 에너지      만일 (무작위의() < 생략하다(엔트로피[전류 에너지]-엔트로피[프로포즈 에너지])):         # 승인되면 에너지 및 시스템을 업데이트하십시오.         전류 에너지 = 프로포즈 에너지         계통.acceptProposedConfiguration구성()     다른:         # 기각될 경우         계통.거부프로포즈구성()      H[전류 에너지] += 1     엔트로피[전류 에너지] += f      만일 (이스플랫(H)):  # isFlat 히스토그램이 평평한지 테스트(예: 95% 평탄도)         H[:] = 0         f *= 0.5  # f 매개변수 다듬기 

왕과 란다우 분자 역학

왕과 란다우 알고리즘은 몬테카를로 시뮬레이션뿐만 아니라 분자역학 시뮬레이션에서도 구현할 수 있다.이를 위해서는 다음과 같은 시스템 온도 상승이 필요하다.

${\displaystyle T'(E)\오른쪽 화살표 {\dfrac {\partial S(E)}{\partial E}\cdot T(E),}$

${\displaystyle \mathrm{여기}}$서 $S{\displaystyle }$( E${\displaystyle }$) ${\displaystyle S($${\displaystyle E}$$)}$은 시스템의 엔트로피, $T{\displaystyle }$ (${\displaystyle }$E )${\displaystyle T(E)}$ 마이크로캐논$$ 온도, $T{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$( ${\displaystyle E)}$ ${\displaystytle T'(E)}$은 시뮬레이션에 사용되는 "스케일링된" 온도다$$.

참조