模拟退火算法.pptx

1模拟退火算法——第二小组

2Outline1.Background2.CouplingmodetheoryEquationsandsolutionsCodirectionalcoupling;Contradirectionalcoupling;3.Couplingtoexcitethemodesinopticalwaveguides

3模拟退火算法的简介提出：模拟退火算法(SimulatedAnnealing，SA)最早的思想是由N.Metropolis[1]?等人于1953年提出。1983年,S.Kirkpatrick等成功地将退火思想引入到组合优化领域。目的：解决NP复杂性过程；克服优化过程陷入局部极小；克服初值依赖性。

4物理退火过程统计力学表明材料中粒子的不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过程被称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。

5数学描述假设材料在状态之下的能量，那么材料在温度T时从状态进入状态就遵循如下规律：（1）如果，接受该状态被转换。（2）如果，则状态转换以如下概率被接受：其中K是物理学中的波尔兹曼常数，T是材料温度

6在某一个特定温度下，进行了充分的转换之后，材料将达到热平衡。这时材料处于状态的概率满足波尔兹曼分布：其中x表示材料当前状态的随机变量，S表示状态空间集合。

所有状态在高温下具有相同的概率。当温度很高时其中表示集合S中状态的数量。

8当温度降至很低时，材料会以很大概率进入最小能量状态。当温度下降时，其中且

Metropolis准则——以概率接受新状态

若在温度T，当前状态i→新状态j，若EjEi，则接受j为当前状态；否则，若概率p=exp[-(Ej-Ei)/kBT]大于[0,1)区间的随机数，则仍接受状态j为当前状态；若不成立则保留状态i为当前状态。

组合优化与物理退火的相似性组合优化问题金属物体解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量

模拟退火算法过程优化函数为，其中，它表示优化问题的一个可行解，S表示函数的定义域。其中表示示x的一个邻域集合。假定我们要解决的问题是一个寻找最小值的优化问题。将物理学中模拟退火的思想应用于优化问题就可以得到模拟退火寻优方法。

12首先给定一个初始温度T和该优化问题的一个初始解x（0），并由x(0)生成下一个解，是否接受作为一个新解x(1)依赖于下面概率：若其它

对于某一个温度和该优化问题的一个解,可以生成。接受作为下一个新解(k+1)的概率为：在温度下，经过很多次转移之后，降低温度，得到。在下重复上述过程。因此整个优化过程就是不断寻找新解和缓慢降温的交替过程。最终的解是对该问题寻优的结果。若其它（1）

从任何一个状态生成的概率，在中是均匀分布的，且新状态被接受的概率满足式(1)，那么经过有限次的转换，在温度下的平衡态的分布由下式给出：(2)

并且当温度T下降为0时，的分布为：若其它如果温度下降十分缓慢，而在每个温度都有足够多次的状态转移，使之在每一个温度下达到热平衡，则全局最优解将以概率1被找到。

马尔可夫过程在每个下，所得到的一个新状态完全依赖于前一个状态，可以和前面的状态16无关。使用马尔可夫过程对上述模拟