中国科学院合肥物质科学研究院.pdf

中国科学院合肥物质科学研究院中国科学院合肥物质科学研究院蒙特卡洛方法与模拟退火方法蒙特卡洛方法与模拟退火方法中国科学院固体物理研究所 计算材料科学研究室 范巍主要内容主要内容• 蒙特卡洛方法的历史蒙特卡洛方法的历史 • 蒙特卡洛方法基本原理蒙特卡洛方法基本原理 • 模拟退火方法模拟退火方法 • 蒙特卡洛方法的应用蒙特卡洛方法的应用蒙特卡洛方法的历史蒙特卡洛方法的历史?十八世纪中叶发展起来的随机抽样方法,如 Buffon针实验，W.S.Gossett的t-distribution?二次大战曼哈顿工程与计算机技术几乎同时发 展起来 ?1948年Von Neumann和Ulam用随机抽样方法研 究了中子在核燃料中的扩散 ?1952-3年Metropolis提出了著名的Metropolis方 法随机抽样方法估算π值随机抽样方法估算π值豆子落入圆中的比例为粒落入圆中粒豆子，其中有均匀地在正方形中撒circleNNNNcircleP = =PNPNNNRRcircle4,44422≈⇒=∞→=≈⇒=∞→=ππππ时为有限因此在时就是说当，也与正方形的面积与圆么落入圆中的比例正比，那如果均匀撒无穷粒豆子R蒙特卡洛方法基本原理蒙特卡洛方法基本原理• 蒙特卡洛方法主要是用来计算积分∫∑∑ =−====∫∑∑ =−====baNiiNabNiixfxxfdxxfF11)()()(∆ ∆•用均匀采样方法∫∑ ===∫∑ ===baNiiNxxfdxxfF11)()(∆ ∆均匀采样方法对于高维积分不是很有效往 往需要巨大数目地采样点。

采用权重函数 可以在相同地采样点时有更高地积分精度∑ ∑∑ ∑= =iiiiixxxfxF)()()(ωω∆ ∆)()()(xfxxf= =ω，如果选择值的极大值处也应有极大权重函数在∑ ∑∑ ∑= =iiiixfxxfF)()(2∆ ∆重点采样方法重点采样方法• 上面我们必需选择权重函数，我们也可以采 用重点采样的方法达到同样目的∑∫∑∫∫∫========∑∫∑∫∫∫========stateiiiiiNixxf MnbaMixxf MibaxxfbabadxxfFxxxdxxdxxfFdxxx1)()(1)()(1)()()(}{)()()(1)()(ρρρρρρρ那么的集合分布的如果我们产生按满足如果我们选择分布函数统计物理中的蒙特卡洛方法统计物理中的蒙特卡洛方法• 统计物理主要任务是计算下面的积分∫∫−−= ∫∫−−= dRedROeOBkREBkRE)()(∫ ∫−−==−−==dReZeRTBkRE TBkREZ)()( ,)(1其中我们很自然的选取ρ∑ ==∑ ==state iNiiMnROO1)(为温度是玻尔兹曼常数，TkBee MnMiTBkiRETBkiREi,1)()(∑ =−−≈∑ =−−≈Metropolis方法方法• 产生一条马尔可夫链。

在链上变量x按规定的 ρ(x)分布，我们以统计物理的玻尔兹曼分布来 介绍Metropolis方法方法.尔可夫过程如随机行走稳定的状态常见的马不到一个的稳定状态或永远也打到一个与初始状态无关，最后达化将失去对过去的记忆马尔可夫链随时间的演可写为和最近的过去时刻有关的几率只时刻处于状态是在第马尔可夫链的主要特点.)],([),(t11iiiiii RtPRtPRψ=++=++平衡原理，的接收几率根据细致到从状态是体系的尝试几率，其中到系从状态是体，其中的跃迁几率为到从刻的几率为时体系处于时刻的几率为体系处于时刻的状态，标记第时刻的状态标记第我们用11111111111),(),(),(),(),()(,)(1,)1()(++++++++−++−+===++++++++−++−+===+ ++ +iiiiiiiiiiiiiiiiiiiiiiRRRRQRRRRSRRQRRSRRPRReRNReRNRiRiRTBkiRETBkiRE),(),()(),(),()(),()(),()(11111111iiiiiiiiiiiiiiii RRQRRSRNRRQRRSRNRRPRNRRPRN++++++++ =++++++++ == =),(),(11iiiiRRSRRS++=++=用对称的尝试跳跃在实际的模拟中我们采TBkiREiREiiiiiieRNRN RRQRRQ)()1( 111 )()( ),(),(−+ +++−==−+ +++−==), 1 (),(), 1 (),(),(), 1 (), 1 (),(,)()1(1)()1( 11)()( 11)()( 1TBkiREiREiiTBkiREiREiieMinRRSMinRRSRRPRReMinMinRRQMetropolisiiRNRN iiiiRNRN ii−++−+ +−+++−+====−++−+ +−+++−+====的跃迁几率为那么从状态采用了下面的接受几率式完全确定接受几率的形单根据上式我们还不能), 1 (),,()()1(11TBkiREiRE eMinRRSRRiiii−+−++−+−++而背接受的几率为态的尝试几率为状向其它状态跳跃，跳向等几率从状态在实际的模拟中系统以蒙特卡洛方法流程图蒙特卡洛方法流程图模拟退火方法模拟退火方法• 顾名思义模拟退火方法就是一个降温方 法。

在统计物理中，蒙特卡洛模拟是一 个有限温度过程，因此只要引进一个降 温过程就可以实现退火过程请参见蒙 特卡洛方法的流程图 • 模拟退火方法可以用来优化系统的结构， 比如材料科学中寻找能量有利的原子排 列方式为什么模拟退火方法能优化系统的结构？为什么模拟退火方法能优化系统的结构？接受的过程有两种从流程图我们可以看到randomePRERERERETBkiREiREiiii>=>>=>< <−+−++−+−++)()1()()()2()()() 1 (11但能量升高能量降低)0, 0( , 00221→→→→→→PTBBB时而减少，当温度趋于随温度减小受次数由于第二种过程而被接与温度无关受次数由于第一种过程而被接1B2B1− −T1 1− −T第一个过程降低能量继续以个过程停止，系统可以时，第二演化当温度趋于的方向导，系统沿着能量降低时第一个过程占主温度小于，当我们看到一定存在温度011 TT适的优化切入点其作用是选择合二个过程占主导，时第当温度大于1T1E2E的跳跃在不同的能量极小点间不同的模拟退火方法不同的模拟退火方法式根据不同的尝试跳跃方接受方式选择不同的尝试跳跃和)()(FSALorrentzCSAGauss快速模拟退火分布一般模拟退火分布⇒⇒⇒⇒推广模拟退火方法推广模拟退火方法(GSA)基于基于Tsallis统计统计∑−=→∑==→ −−=∑−=→∑==→ −−=W iiiB qpBqppksksWiq i 11 11ln1∑∑−→−→=→−−≡=→−−=−−∑∑−→−→=→−−≡=→−−=−−iq iiqZiq iZiiqieZqZepqpβεβεεβεβ1111111111])1 (1 [])1 (1 [布范围。

分布有比较宽的能量分减到尔兹曼分布则是迅速衰比较可观的分布值玻值比较远时仍有分布当能量偏离最可几分布的特殊形式玻尔兹曼分布是TsallisTsallisqTsallis, 0) 1( →→统计和接受方式基于采用的尝试跳跃分布，Tsallis接受几率尝试跳跃分布], 1 [),( 111]))()()(1(1[1 1− +−−++− +−−++= =α ααq aqiiTREREqiiMinRRP)21 11(32 ][)2(321 1121 11 2})1(1{][)()(1)()(−+−−−−−−− −−+−+−=−+−−−−−−− −−+−+−=D vqvqv vqTtx vvqD v vqvqD vqD vvqTq tqxg ∆ΓΓ∆ ∆ΓΓ∆π降温方式1)1(12 1) 1 ()(−+− −=−+− −=vqvqvvtqv qTtT并从局域极小中跳出来多的机会进行长程跳跃有更的增加缓慢趋于零有很长的尾巴，随着,vg v。