数学建模优秀方法 模拟退火算法简介.doc

《数学建模优秀方法 模拟退火算法简介.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、模拟退火算法算法简介模拟退火算法得益于材料的统计力学的研究成杲。统计力学表明材料中粒子的不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温(这个过程被称为退火),粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。如果用粒子的能量定义材料的状态，Metropolis算法用一个简单的数学模型描述了退火过程。假设材料在状态，之下的能量为EQ),那么材料在温度T时从状态i进入状态丿•就遵循如下规律：(1)如果E(

2、j)5E⑴,接受该状态被转换。(2)如果E(j)>E(i),则状态转换以如下概率被接受:ekt其中K是物理学中的波尔兹曼常数，T是材料温度。在某一个特定温度下，进行了充分的转换之后，材料将达到热平衡。这时材料处于状态j的概率满足波尔兹曼分布：£(/)Pt(x=i)=—jwS其中无表示材料当前状态的随机变量，S表示状态空间集合。显然lim7->oce府ISIE(J)工£KTjwS其中ISI表示集合s中状态的数量。这表明所有状态在高温下具有相同的概率。而当温度下降时,limTtOlimT->0E(J)-E(j)-EminKT+工£灯>

3、e5mineKT&KT15minI0若iWS^in其它=limr->oE(i)%□J)-%DKTJe5min其中盅七呷)且上式表明当温度降至很低吋，材料会以很大概率进入最小能量状态。假定我们要解决的问题是一个寻找最小值的优化问题。将物理学屮模拟退火的思想应用于优化问题就可以得到模拟退火寻优方法。考虑这样一个组合优化问题：优化函数为F：2R+,其中xeS,它表示优化问题的一个可行解，R+={yyeR,y>0},S表示函数的定义域。N(x)uS表示兀的一个邻域集合。首先给定一个初始温度几和该优化问题的一个初始解班0),并由x(O)生

4、成下一个解VeN(x(O)),是否接受*作为一个新解兀⑴依赖于下面概率：1P(X(O)T〈八小-/心⑼)其它换句话说，如果生成的解f的函数值比前一个解的函数值更小，则接受41）=/作为一个新解。否则以概率£L接受丄作为一个新解。泛泛地说，对于某一个温度7；和该优化问题的一个解兀伙），可以生成丄。接受”作为下一个新解兀伙+i）的概率为：1若£（*）%1）=

5、过程就是不断寻找新解和缓慢降温的交替过程。最终的解是对该问题寻优的结果。我们注意到，在每个7；下，所得到的一个新状态无伙+1）完全依赖于前一个状态x伙），可以和前面的状态班0）,…，兀伙-1）无关，因此这是一个马尔可夫过程。使用马尔可夫过程对上述模拟退火的步骤进行分析，结果表明：从任何一个状态兀伙）生成f的概率，在NO伙））中是均匀分布的，且新状态f被接受的概率满足式（1）,那么经过有限次的转换，在温度7；下的平衡态兀的分布由下式给岀：八“）et/（A；）jwS（2）当温度了降为0时，石的分布为：——!——若儿gs.D*ICI1m

6、,nPi九皿I0其它并且=iAre5min这说明如果温度下降十分缓慢，而在每个温度都有足够多次的状态转移，使之在每一个温度下达到热平衡，则全局最优解将以概率1被找到。因此可以说模拟退火算法可以找到全局最优解。在模拟退火算法中应注意以下问题：（1）理论上，降温过程要足够缓慢，要使得在每一温度下达到热平衡。但在计算机实现屮，如果降温速度过缓，所得到的解的性能会较为令人满意，但是算法会太慢，相对于简单的搜索算法不具有明显优势。如果降温速度过快，很可能最终得不到全局最优解。因此使用时耍综合考虑解的性能和算法速度，在两者之间采取一种折衷。（

7、2）要确定在每一温度下状态转换的结束准则。实际操作可以考虑当连续次的转换过程没有使状态发生变化时结束该温度下的状态转换。最终温度的确定可以提前定为一个较小的值7；，或连续儿个温度下转换过程没有使状态发生变化算法就结束。（3）选择初始温度和确定某个可行解的邻域的方法也耍恰当。