模拟退火算法优秀.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第5章 模拟退火算法,模拟退火算法,（,Simulated Annealing,简称,SA,）,是,Kirkpatrick,等人于,1982,年提出的一种适合求解大规模组合优化问题，特别是,NP-,难问题的通用启发式算法,算法思想源于对,固体物质退火过程,的模拟；采用,Metropolis,接受准则,；并用一组称之为,冷却进度表,的,参数,控制算法进程，使算法在多项式时间里给出一个近似最优解,SA,的物理背景：固体物质退火过程,使算法跳离局部最优的关键：,Metropolis,接受准则,算法应用的前提：冷却进度表的合理选择,1,主要内容,5.1 固体退火过程和,Metropolis,准则,5.2 模拟退火算法的基本思想和步骤,5.3 模拟退火算法关键参数和操作的设计,5.4 模拟退火算法实现与应用,5.5 模拟退火算法的改进,2,5.1,固体退火过程和,Metropolis,准则,固体物质退火是先将固体加热至熔化，再徐徐冷却使之凝固成规整晶体的热力学过程,.,固体物质的退火过程由三部分组成：,加温过程：增强粒子的热运动；系统能量随之增大,等温过程：系统达到该温度下能量最小状态，即平衡态,冷却过程：使粒子的热运动减弱并逐渐有序化,对于固体在恒定温度下达到热平衡的过程模拟，,Metropolis,等人在,1953,年提出了“重要性采样法”，即以概率接受新状态,若,E,j,E,i,，,要依据概率 来确定,3,5.2,模拟退火算法的基本思想和步骤,1.,固体退火与组合优化之间的相似性,固体退火概念与优化问题的对应关系,固体退火,组合优化问题,状态,i,系统能量,E,i,能量最低状态,加温熔化,等温过程,冷却过程,解,x,i,目标函数,f,(,x,i,),最优解,设定初温,t,0,产生新解、判断、接受/舍弃,控制参数,t,的变化,4,2.算法思想和步骤,Metropolis,算法：从某一初始状态出发，通过计算系统的时间演化过程，求出系统最终达到的状态,SA,：,从某个初始解出发，经过大量解的变换后，求得给定控制参数值,t,时优化问题的相对最优解然后，减少,t,的值，重复执行,Metropolis,算法，就可以在,t,趋于零时，求得优化问题的全局最优解,SA,由与,Metropolis,准则对应的转移概率,P,t,确定是否接受从当前解,x,i,到新解,x,j,的转移，即,5,Procedure Simulated_Annealing;,Begin,任选一个初始解,x,0,；确定初始温度,t,0,和每一个,t,值下进行迭代的次数,L,；,x,i,:=,x,0,;,（置初始解为当前解）,k,:=0;,（温度变化计数器置0）,Repeat,l,:=0;,（迭代次数计数器）,Repeat,从邻域,N,(,x,i,)中随机选一,x,j,；计算,f,=,f,(,x,j,)-,f,(,x,i,),；,if(,f,0)then,x,i,:=,x,j,;,else if,exp,(-,f,/,t,k,)random 0,1 then,x,i,:=,x,j,;,l,:=,l,+1;,until,l,=,L,;,k,:=,k,+1;,t,k,:=,t,(,k,);,until 满足终止条件；,End;,6,3.模拟退火算法的特点分析,SA,依据,Metropolis,准则接受新解，因此除接受优化解外，还在一定范围内接受恶化解，这正是,SA,与局部搜索算法的本质区别所在,SA,具有如下,特点,：,(1),优于局部搜索算法,(2),若在每个,t,值都达到平衡分布，且所构造的邻域结构能使解空间中的任何两个状态可达，则,SA,渐近收敛于全局最优解,(3),随着控制参数,t,值的减小，算法返回某个全局最优解的概率单调增大,.,7,与局部搜索算法相比，,SA,的,性能,可概括为高效、健壮、通用和灵活,(1),高效性,SA,可在较短时间里求得更好的最终解,(2),健壮性（鲁棒性，,robust,）,即算法的最终解并不十分依赖初始解的选取,(3),通用性和灵活性,SA,能应用于求解多种组合优化问题，为一个问题编制的程序可以有效地用于其它问题,8,5.3,SA,关键参数及其操作设计,SA,主要包括“,三函数两准则,”：解产生函数（邻域结构）、解接受函数、温度更新函数、内循环终止准则和外循环终止准则,1.,解产生函数（邻域结构）,通常选择当前解经简单变换即可产生新解的方法,尽可能保证产生的候选解遍布整个解空间,应能使解空间中的任何两个状态可达,2.,解接受函数,判断新解是否被接受的依据是,Metropolis,准则：,9,3.初始温度,从理论上说，初始温度,t,0,应使平稳分布中每一状态被接受的概率相等，也就是使,若取,P,0.9,，,则在,f,=100,时，,t,0,949,在实际应用中可用以下方法进行简单地估计：,(1),f,=,(,目标函数值的上界,),(,目标函数值的下界,),(2),随机产生若干个解，求所有解对间的目标函数差，然后取其中的最大者作为,f,10,4.温度更新函数,表示温度下降的方式并控制温度下降的速度,常用的温度更新函数是,t,k+,1,=,t,k,，,0,1,，,通常,=0.750.99,5.,内循环终止准则,用于决定在各温度下产生候选解的数目，即每一个,t,k,值下进行迭代的次数,L,L,往往只能取一个近似的足够大的数，如,L,=100,n,300,n,，,其中,n,为问题的规模,还可用如下的抽样稳定准则来判断,L,是否足够大：,(1),目标函数的均值是否稳定,(2),连续若干步的目标值变化较小,11,6.外循环终止准则,用于决定,SA,何时结束常用的终止准则有：,(1),设定终止温度在实际应用中，可以给定一个足够小的正数,，,当温度,t,k,时，算法终止,(2),给定一个确定的外循环总迭代次数,(3),给定当前的最好解保持不变的最大连续迭代次数,7.,冷却进度表,初始温度,t,0,，,温度更新函数,t,k+,1,=,t,k,，,每一个,t,k,值下进行迭代的次数,L,和,外循环终止准则,称为模拟退火过程的冷却进度表，是,SA,应用的关键参数,这些参数之间存在相互影响,12,5.4 模拟退火算法实现与应用,讨论如何在,SA,所提供的通用算法框架下，针对具体问题予以实现,对问题的简明描述：,解空间,：指问题的所有可能解的集合，它限定了初始解选取和新解产生时的范围,目标函数,：通常表述为若干优化目标的一个和式目标函数值不一定就是问题的优化目标值，但其对应关系应是明显的此外，目标函数式应当是易于计算的,初始解,：可以考虑随机生成,13,1.旅行商问题,设有,n,个城市和距离矩阵,D,=(,d,ij,),，,其中,d,ij,表示城市,i,到城市,j,的距离,问题是要找遍访每个城市恰好一次的一条回路，且其路径长度为最短,求解,TSP,的模拟退火算法描述如下：,解空间：可表示为,1,2,n,的所有循环排列的集合，即,S,=(,1,2,n,)|(,1,2,n,),为,1,2,n,的循环排列,i,=,j,表示在第,i,个次序访问城市,j,，并约定,n,+1,=,1,初始解：可选为,（1,2,n,）,目标函数：访问所有城市的一个回路的长度,14,新解的产生：设用以下方法产生（分别或交替使用）,2-,交换任选访问的序号,u,和,v,（设,u,v,），,逆转,u,和,v,及其之间的访问顺序,当前,解,：,1,u,-1,u,u,+1,v,-1,v,v,+1,n,新解：,1,u,-1,v,v,-1,u,+1,u,v,+1,n,3-,交换任选序号,u,、,v,和,w,（设,uvw,），将,u,和,v,之间的子路径插到,w,之后访问,当前,解,：,1,u,-1,u,v,v,+1,w,w,+1,n,新解,：,1,u,-1,v,+1,w,u,v,w,+1,n,目标函数差（,2-,交换）,15,当距离矩阵,D,=（,d,ij,）,为对称矩阵时，因为,d,ij,=,d,ji,，上式可简化为,目标函数差（,-,交换）,16,2.,01,背包问题,（Zero-one Knapsack Problem）,给定一个装载量为,M,的背包及,n,件物品，物品,i,的重量和价值分别为,w,i,和,c,i,，,i,=1,2,n,要求选择若干件物品装入背包，使其价值之和为最大,设,则问题的数学模型为,x,i,0,1,i,=1,2,n,17,求解,0-1,背包问题,的模拟退火算法描述如下：,解空间,S,=(,x,1,x,2,x,n,)|,w,1,x,1,+,w,n,x,n,M,x,i,0,1,目标函数,f,(,x,1,x,2,x,n,)=,c,1,x,1,+,c,2,x,2,+,c,n,x,n,max,新解的产生,随机选取物品,i,，,执行下列三种操作之一：,若,i,不在背包中，则将其装入背包,若,i,不在背包中，则将其装入背包，同时从背包中随机取出另一物品,j,若,i,已在背包中，则将其取出，并同时随机装入另一物品,j,归纳：,x,i,:=1,x,i,，,且（或）,x,j,:=1,x,j,，,i,j,18,背包价值差（目标函数差）及重量差,根据产生新解的三种可能，相应的背包价值差为,为判定解的可行性，求出对应的背包重量差为,其中,m,为当前背包重量,m,的增量,19,接受准则：是增加了可行性测定的,Metropolis,准则,20,5.5 模拟退火算法的改进,SA,的,主要不足,:,返回一个高质量的最终解要花费较长的时间,提高搜索效率是主要的改进内容，可能的途径：,(1),选择适当的邻域结构和随机数序列,(2),选择合理的冷却进度表,(3),SA,执行过程是一系列“产生新解、判断、接受,/,舍弃”的迭代过程，提高各个环节的时效可以缩减运算时间,(4),改变算法进程的各种变异方法，如有记忆的,SA,、,回火退火法、加温退火法等,(5),大规模并行计算,21,