SA

模拟退火算法SimulatedAnnealingAlgorithm陕西师范大学计算机科学学院主讲人：雷秀娟•1.引言•2.SA算法简介•3.SA算法流程及步骤主要内容引言•SA算法有人也称为模拟冷却法、统计冷却法、Monte-Carlo退火法、随机松弛法和概率爬山法等。•SA算法往好的方向走的同时，偶尔也往差的方向走。这使得算法即使陷入局部最优值，只要经过足够长的时间后也可跳出来，收敛到全局最优解。•SA算法以概率1收敛到问题的全局最优解。物理退火过程•对固体物质进行退火处理时，通常先将它加热熔化，使其中的粒子可自由运动。然后随着温度的逐渐下降，粒子也逐渐形成了低能态的晶格。若在凝结点附近的温度下降速率足够慢，则固体物质一定会形成最低能量的基态。•退火过程主要由以下三部分组成：物理退火过程（1）加热过程（2）冷却过程目的是使粒子的热运动减弱并趋渐趋有序，系统能量下降，从而得到低能的晶体结构。（3）“热平衡”过程当自由能达到最小时，系统达到平衡态。组合优化问题•组合优化问题解空间中的每一点都代表一个解，不同的解有着不同的成本函数值。所谓优化，就是在解空间中寻找成本函数值最小(或最大)的解。•所谓组合优化即寻找最优解s*,使得siV，C(s*)=minC(si)，其中V={s1,s2,…sn}为所有状态构成的解空间，C(si)为状态si对应的目标函数值。模拟退火算法简介•1982年，Kirkpatrick等将退火思想引入组合优化的领域，提出了一种求解大规模组合优化问题，特别是NP完全组合优化问题的有效近似解的算法——模拟退火算法（simulatedannealingalgorithm），简称为SA。•模拟退火算法是在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，在局部优解处能概率性地跳出并最终趋于全局最优。•基于Metropolis接受准则的优化过程，可避免搜索过程陷于局部极小，并最终趋于问题的全局最优解。Metropolis准则•Metropolis等在1953年提出了重要性采样法，即以概率接受新状态。•在温度t,由当前状态i产生新状态j，二者的能量分别是Ei和Ej，若EjEi,则接受新状态j为当前状态。•否则，若概率pr=exp[-(Ej-Ei)／kt]random(0,1),则仍接受新状态j为当前状态，若不成立则保留状态i为当前状态，其中k为Boltzmann常数。（有些概念中没有这个k参数）SA算法简介•假设在搜寻最佳解的过程中–令i代表在时间k的现有解，其成本为C(i)–下一个搜寻到的解，其成本为C(j)–DE=C(j)-C(i)为两个解之间的成本差，如图所示搜寻方向SA算法简介–当j的成本大于i时，SA会根据一几率決定是否要接受j来取代i成为时间k+1的新解–因此当搜寻到的新解比现有解之成本大时，会有一个几率值来决定是否接受新解。–SA基本上是以Metrolopis接受法则为基础，再配合退火程序，由温度逐渐的降低来修整是否接受成本较差新解的几率，当温度越低时，几率值也跟著降低SA的运作流程•包含了四个基本要素–系统状态(Configuration)：即在某一个温度下，系统产生的初始解，并当作目前的现行解。–搜寻法则(Searchrule)：在退火的过程中，由目前系统状态经由随机扰动而产生变化跳至另一种状态。•一般而言，SA较常用的有梯度搜寻法(GradientType)和迭代改善法(IterativeImprovement)SA的运作流程•包含了四个基本要素–成本函数(CostFunction)：用来横量某一系统状态下之能量函数。–退火程序(AnnealingProcess)：退火程序中包含的参数有初始温度、降温机制、冷却率和终止温度。•在退火的过程中，在温度高的時候，虽然是较差的目标值，但有可能被接受当成目前的目标值，但随着温度慢慢的降低，接受较差目标值的几率逐渐降低。流程图SA的运作流程•SA算法的收敛性由状态产生函数,状态接受函数和温度更新函数三个函数所决定。•用于描述SA算法的一个有力工具就是马尔可夫链。由于组合优化问题的状态空间S是有限的，因此SA算法可用非平稳马尔可夫链来描述。模拟退火算法的马氏链1.令V={s1,s2….}为所有状态构成的解空间，X(k)为k时刻状态变量的取值。随机序列{X(k)}称为马氏链。2.SA算法对应一个马氏链。马氏链可用一个有向图G=(V,E)表示，其中V为所有状态构成的顶点集，E={(i,j)︱i,j,，}为边集。Ni是当前状态i的邻域。jVjNiSA算法的关键参数1.状态产生函数设计状态产生函数（领域函数）的出发点应该是尽可能保证产生的候选解遍布全部解空间。通常，状态产生函数有两部分组成，即产生候选解的方式和候选解产生的概率分布。候选解的产生方式由问题的性质决定，通常在当前状态的邻域结构内以一定概率方式产生。设gi,j为由状态i产生j的概率，则其中，它通常与温度无关。若新状态在当前状态的邻域中以等同概率产生，•则其中为状态i的邻域状态总数(,)(),,0,gijgijNiijjNig()(,)jNigigij(,)1gijgiii2.状态接受函数状态接受函数一般以一定的方式给出，不同接受函数的差别主要在于接受概率的形式不同。记ai,j为由当前状态i接受状态j的概率，接受概率通常定义为其中C(.)为目标函数，t为温度参数,min{1,exp[(()())]}ijCjCita记pi,j为由状态i到状态j的转移概率，则有由gi,j为由状态i产生j的概率，ai,j为由当前状态i接受状态j的概率,,,,,()0,1,(),ijijjNiandjiijpijtjNiandjipiktjikNiga3.温度更新函数温度的下降，用于外循环中修改温度值。单纯的温度下降速度加快并不能保证算法以比较快的速度收敛到全局最优，温度下降的速率必须与状态产生函数相匹配。在时齐SA算法收敛性理论中，要求温度最终趋于零。通常，各温度下产生候选解越多，温度下降的速度可以越快。4.初始温度•在时齐SA算法收敛理论中，虽没有对初温给出限制，但根据与物理退火过程的类比关系，初温应选择充分大以使几乎所有产生的候选解都能被接受，如此保证最终优良的收敛性。•实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，折中考虑优化质量和优化效率，常用的方法为：（1）均匀抽样一组状态，以各状态目标值的方差为初值。(2)随机产生一组状态，确定两两状态间的最大目标值差。5.内循环终止准则内循环终止准则，用于决定在各温度产生候选解的数目。常用的抽样稳定准则包括：1检验目标函数的均值是否稳定2连续若干步的目标值变化较小3按一定的部数抽样在每个温度下只产生一个或少量候选解，不存在候选解内循环终止准则的问题，此时也是非时序的。反之则是时序SA6.外循环终止准则（1）设置终止温度的阀值（2）设置外循环迭代次数（3）算法搜索到的最优值连续若干不保持不变（4）检验系统是否稳定SA算法的收敛性理论中要求tn趋于零，即，不过这显然不符合实际。0limnnt–降温时机乃指马尔可夫链长度，亦即在同一温度下所应反复进行Metropolis演算的次数–最直接的方式是设定一个固定长度，但此长度与问题规模有关，如在1992年Kouvelis与Chiang将其设定为邻近解个数之比率。–此外亦可设定降温时机为达到一定值的转移接受次数，如Heragu以及Alfa（1992）即使用方式。但此方式当温度降至很低时，转移接受之几率将会很小，进而导致马尔可夫链过长，因此必须同时限定马尔可夫链的长度，以免造成求解时间过长。7.降温时机–温度控制参数是指在演算过程中，若达到降温时机时，由目前温度減少到下一温度的下降比率–若温度控制参数越小，则温度下降的差距越大，那么会造成在次一温度达成均衡所需的马尔可夫链长度越長，使得求解时间增加。–因此，为了避免在新温度下的马尔可夫链长度过长，温度控制参数不应过小，Kirkpatrick等学者（1983）将其设定为0.9，而一般则设定在0.5至0.9之间。8.温度控制参数模拟退火算法要实现全局收敛，需满足以下条件：（1）状态可达性，即对应马氏链的状态图是强连通的。（2）算法的最终结果不依赖初值。（3）极限分布的存在性。算法收敛条件SA算法的一般步骤算法从一个初始状态开始后，每一步状态转移均是在当前状态i的邻域Ni中随机产生新状态j,然后以一定概率aij进行接受。接受概率仅依赖于新状态和当前状态，并由温度加以控制。1流程图2SA算法的一般步骤SA算法的一般步骤{i0为任一初始状态，T0为控制参数的初始值}(1)X=i0;k=0;{X表示当前状态}(2)REPEAT(2.1)REPEAT(2.1.1)j=generate(X)，(2.1.2)IFCj≤Cx,THENX=j;ELSEIFaccept(j，X)THENX=j;(2.1)'UNTIL‘inner-loopstopcriterion'(2.2)Tk+1=update(Tk);k=k+1(2)'UNTIL‘finalstopcriterion'算法说明第(1)步是初始化工作。第(2.1.1)步的generate(X)函数是指从X的邻域Nx中随机地产生下一个状态j。若Cj≤Cx,，则接收j为新的当前状态;否则仅以一定的概率接收j为新的当前状态。这就是accept(j,X)函数的功能。在大多数情况下，accept函数可取下面所述的形式。IFexp{一(Cj-Cx)/Tk}}random(0，1)THENaccept:=trueELSEaccept:=false算法说明(2.1)的‘inner-loopstopcriterion’是指SA算法在每一温度T下的迭代次数。(2)则描述了整个算法应在何时结束。(2.2)步是表示温度每次下降的速率，它用update(Tt)函数表示。从上面的叙述中可以看出，SA算法有下列三个重要函数：即产生函数generate,接收函数accept和温度更新函数update。