《第9讲模拟退火算法等.ppt》由会员分享,可在线阅读,更多相关《第9讲模拟退火算法等.ppt(90页珍藏版)》请在三一文库上搜索。
1、第9讲 模拟退火算法等,1.局部搜索方法 2. 模拟退火算法,邻域的概念,邻域,简单的说就是一个点附近的其他点的集合。 在距离空间,邻域就是以某一点为中心的圆。 组合优化问题的定义: 设D是问题的定义域,若存在一个映射N,使得: 则称N(S)为S的邻域。,例:旅行商问题,用一个城市的序列表示一个可能的解。 通过交换两个城市的位置获取S的邻居 例:简单交换方法 设S = (x1, x2, xi-1, xi, xi+1, , xj-1, xj, xj+1, , xn) 则通过交换xi和xj两个城市的位置可以得到S的一个邻居: S = (x1, x2, xi-1, xj, xi+1, , xj-1,
2、 xi, xj+1, , xn),x1,x2,xn,xj+1,xj,xj-1,xi-1,xi,xi+1,x1,x2,xn,xj+1,xj,xj-1,xi-1,xi,xi+1,例:逆序交换方法 设xi、xj是选取的两个城市,所谓的逆序交换方式是指,通过逆转xi、xj两个城市之间的城市次序来得到S的邻居。 设:S = (x1, x2, xi-1, xi, xi+1, , xj-1, xj, xj+1, , xn) 则:S = (x1, x2, xi-1, xi, xj-1, x j-2, xi+1, xj, xj+1, , xn),x1,x2,xn,xj+1,xj,xj-1,xi-1,xi,xi+
3、1,x1,x2,xn,xj+1,xj,xj-1,xi-1,xi,xi+1,1. 局部搜索算法,基本思想:在搜索过程中,始终向着离目标最接近的方向搜索。 目标可以是最大值,也可以是最小值。 在后面的介绍中,如果没有特殊说明,均假定是最小值。,局部搜索算法(Local Search) 1,随机的选择一个初始的可能解x0D,xb=x0,P=N(xb); 2,如果不满足结束条件,则 3,Begin 4, 选择P的一个子集P,xn为P中的最优解 5, 如果f(xn) f(xb),则xb xn,P = N(xb), 转2;f(x)为指标函数。 6, 否则P = P P,转2。 7,End 8,输出计算结果
4、 9,结束,例:5城市旅行商问题,A,B,C,D,E,7,13,6,10,7,10,10,9,6,5,设初始的可能解:x0 = (a, b, c, d, e) f(xb) = f(x0) = 38 通过交换两个城市获得领域 P = (a, c, b, d, e), (a, d, c, b, e), (a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d) 设每次随机从P中选择一个邻居。,第一次循环,从P中选择一个元素, 假设xn = (a, c, b, d, e), f(xn) = 42, f(xn) f(xb), P
5、 = P xn = (a, d, c, b, e), (a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d),第二次循环,从P中选择一个元素, 假设xn = (a, d, c, b, e), f(xn) = 45, f(xn) f(xb), P = P xn = (a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d),第三次循环,从P中选择一个元素, 假设xn = (a, e, c, d, b), f(xn) = 44, f(xn) f(x
6、b), P = P xn = (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d),第四次循环,从P中选择一个元素, 假设xn = (a, b, d, c, e), f(xn) = 44, f(xn) f(xb), P = P xn = (a, b, e, d, c), (a, b, c, e, d),第五次循环,从P中选择一个元素, 假设xn = (a, b, e, d, c), f(xn) = 34, f(xn) f(xb), xb = (a, b, e, d, c), P = (a, e, b, d, c), (a, d, e, b, c),
7、 (a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d),第六次循环,从P中选择一个元素, 假设xn = (a, e, b, d, c), f(xn) = 44, f(xn) f(xb), P = P xn = (a, d, e, b, c), (a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d),第七次循环,从P中选择一个元素, 假设xn = (a, d, e, b, c), f(xn) = 39, f(xn) f(xb), P = P
8、 xn = (a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d),第八次循环,从P中选择一个元素, 假设xn = (a, c, e, d, b), f(xn) = 38, f(xn) f(xb), P = P xn = (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d),第九次循环,从P中选择一个元素, 假设xn = (a, b, d, e, c), f(xn) = 38, f(xn) f(xb), P = P xn = (a, b, c, d, e), (a, b,
9、 e, c, d),第十次循环,从P中选择一个元素, 假设xn = (a, b, c, d, e), f(xn) = 38, f(xn) f(xb), P = P xn = (a, b, e, c, d),第十一次循环,从P中选择一个元素, 假设xn = (a, b, e, c, d), f(xn) = 41, f(xn) f(xb), P = P xn = P等于空,算法结束, 得到结果为xb = (a, b, e, d, c), f(xb) = 34。,存在的问题,局部最优问题,解决方法,每次并不一定选择邻域内最优的点,而是依据一定的概率,从邻域内选择一个点,指标函数优的点,被选中的概率比
10、较大,而指标函数差的点,被选中的概率比较小。,选择概率的计算,设求最大值:,选择概率的计算,当求最小值时:,局部搜索算法1(Local Search 1) 1,随机的选择一个初始的可能解x0D,xb=x0,P=N(xb) 2,如果不满足结束条件,则 3,Begin 4,对于所有的xP计算指标函数f(x),并按照式(3)或者式(4)计算每一个点x的概率 5,依计算的概率值,从P中随机选择一个点 xn,xb xn,P = N(xb),转2 6,End 7,输出计算结果 8,结束,存在的问题,步长问题,解决方法,变步长,局部搜索算法2(Local Search 2) 1,随机的选择一个初始的可能解x
11、0D,xb=x0, 确定一个初始步长计算P=N(xb) 2,如果不满足结束条件,则 3,Begin 4, 选择P的一个子集P,xn为P中的最优解 5, 如果f(xn) f(xb),则xb xn 6, 按照某种策略改变步长,计算P = N(xb), 转2 7, 否则P = P P,转2。 8,End 9,输出计算结果 10,结束,存在问题,起始点问题,A,B,全局最大值,局部最大值,解决方法,随机的生成一些初始点,从每个初始点出发进行搜索,找到各自的最优解。再从这些最优解中选择一个最好的结果作为最终的结果。,局部搜索算法3(Local Search 3) 1,k = 0 2,随机的选择一个初始的
12、可能解x0D,xb=x0, P=N(xb) 3,如果不满足结束条件,则 4,Begin 5, 选择P的一个子集P,xn为P中的最优解 6, 如果f(xn) f(xb),则xb xn,P = N(xb),转3 7, 否则P = P P,转3。 8,End 9,k = k+1 10,如果k达到了指定的次数,则从k个结果中选 择一个最好的结果输出,否则转(2) 11,输出结果 12,结束,多种方法的集成,以上几种解决方法可以结合在一起使用,比如第一、第二种方法的结合,就产生了我们将在后面介绍的模拟退火方法。,2. 模拟退火算法,是局部搜索算法的一种扩展 最早由Metropolis在1953年提出,K
13、irkpatrick等人在1983年成功地将模拟退火算法用于求解组合优化问题。 基本思想是借用金属的退化过程改进局部搜索算法,固体退火过程,溶解过程:随着温度的不断上升,粒子逐渐脱离开其平衡位置,变得越来越自由,直到达到固体的溶解温度,粒子排列从原来的有序状态变为完全的无序状态。 退火过程:随着温度的下降,粒子的热运动逐渐减弱,粒子逐渐停留在不同的状态,其排列也从无序向有序方向发展,直至到温度很低时,粒子重新以一定的结构排列。,粒子不同的排列结构,对应着不同的能量水平。如果退火过程是缓慢进行的,也就是说,温度的下降如果非常缓慢的话,使得在每个温度下,粒子的排列都达到一种平衡态,则当温度趋于0(
14、绝对温度)时,系统的能量将趋于最小值。,如果以粒子的排列或者相应的能量来表达固体所处的状态,在温度T下,固体所处的状态具有一定的随机性。一方面,物理系统倾向于能量较低的状态,另一方面,热运动又妨碍了系统准确落入低能状态。,Metropolis准则,从状态i转换为状态j的准则: 如果E(j)E(i),则状态转换被接受; 如果E(j)E(i),则状态转移被接受的概率为: 其中E(i)、E(j)分别表示在状态i、j下的能量,T是温度,K0是波尔兹曼常数。,在给定的温度T下,当进行足够多次的状态转换后,系统将达到热平衡。此时系统处于某个状态i的概率由波尔兹曼(Boltzmann)分布给出: (6) 其
15、中 为归一化因子,S是所有可能状态的集合。,考察一下式(6)随温度T的变化情况: 同一温度下,两个能量不同的状态 高温下的情况 低温下的情况 当温度下降时的情况,在给定的温度T下,设有i、j两个状态,E(i)E(j) : 即在任何温度T下,系统处于能量低的状态的概率大于处于能量高的状态的概率。,由于E(i)E(j),所以该项小于1,当温度趋于无穷时: 其中|S|表示系统所有可能的状态数。 当温度很高时,系统处于各个状态的概率基本相等,接近于平均值,与所处状态的能量几乎无关。,当温度趋于0时 : 设Sm表示系统最小能量状态的集合,Em是系统的最小能量。上式分子、分母同乘以,当温度趋近于0时,系统
16、以等概率趋近于几个能量最小的状态之一,而系统处于其他状态的概率为0。以概率1达到能量最小的状态。,当温度上升或下降时:,系统落入低能量状态的概率随着温度的下降单调上升,而系统落入高能量状态的概率随着温度的下降单调下降。,在高温下,系统基本处于无序的状态,基本以等概率落入各个状态。在给定的温度下,系统落入低能量状态的概率大于系统落入高能量状态的概率,这样在同一温度下,如果系统交换的足够充分,则系统会趋向于落入较低能量的状态。随着温度的缓慢下降,系统落入低能量状态的概率逐步增加,而落入高能量状态的概率逐步减少,使得系统各状态能量的期望值随温度的下降单调下降,而只有那些能量小于期望值的状态,其概率才
17、随温度下降增加,其他状态均随温度下降而下降。因此,随着能量期望值的逐步下降,能量低于期望值的状态逐步减少,当温度趋于0时,只剩下那些具有最小能量的状态,系统处于其他状态的概率趋近于0。因此最终系统将以概率1处于具有最小能量的一个状态。,达到最小能量状态的三个条件,(1)初始温度必须足够高; (2)在每个温度下,状态的交换必须足够充分; (3)温度T的下降必须足够缓慢。,组合优化问题与退火过程的类比,1,随机选择一个解i,k=0,t0=Tmax(初始温度),计算指标函数f(i)。 2,如果满足结束条件,则转(15)。 3,Begin 4, 如果在该温度内达到了平衡条件,则转(13)。 5, Be
18、gin 6, 从i的邻域N(i)中随机选择一个解j。 7, 计算指标函数f(j)。 8, 如果f(j)j)Random(0, 1),则i=j,f(i)=f(j)。 11, 转(4) 12, End 13, tk+1=Drop(tk),k=k+1。 14,End 15,输出结果。 16,结束。,算法中的问题,初始温度的选取 内循环的结束条件,即每个温度状态交换何时结束 外循环的结束条件,即温度下降到什么时候结束 温度的下降方法,在模拟退火过程中,给定温度下状态(解)的转移可以看作是一个马尔可夫链。对于任意两个状态i和j,我们用Pt(i, j)表示温度t下,从状态i转移到状态j的一步转移概率,则有
19、: 其中:Gt(i,j) 是产生概率,表示从状态i产生状态j的概率。At(i,j) 是接受概率,表示在状态i产生状态j后,接受状态j的概率。,定理7.1,满足条件的Gt(i,j)、At(i,j) 举例:,说明:条件2的后半部分除外,该条件与具体的问题有关。,定理7.2: 在定理1的条件下,如果对于任意两个状态 有: 则有:,定理7.3(放宽了定理1的条件) Gt(i,j)、At(i,j)满足定理1中除条件(2)以外的所有其他条件,并且: 1,对于任意两个状态i、j,它们相互为邻居或者相互都不为邻居; 2,对于任意i,Gt(i,j)满足: 3,状态空间S对于邻域是连通的; 则与模拟退火算法相伴的
20、时齐马尔可夫链存在平稳分布,其分布概率为:,算法的实现,(1)初始温度t0; (2)温度t的衰减函数,即温度的下降 方法; (3)算法的终止准则,用终止温度tf或 者终止条件给出; (4)每个温度t下的马尔可夫链长度Lk。,起始温度的选取(1),一个合适的初始温度,应保证平稳分布中每一个状态的概率基本相等,也就是接受概率P0近似等于1。在Metropolis准则下,即要求:,如果我们给定一个比较大的接受概率P0,则:,其中, 可以有以下估计方式:,起始温度的选取(2),假设在t0下随机的生成一个状态序列,分别用m1和m2表示指标函数下降的状态数和指标函数上升的状态数, 表示状态增加的平均值。则
21、m2个状态中,被接受的个数为:,所以平均接受率为: 求解有:,起始温度的选取(3),模拟固体的升温过程: (1)给定一个希望的初始接受概率P0,给定一个较低的初始温度t0,比如t01; (2)随机的产生一个状态序列,并计算该序列的接收率: 如果接收率大于给定的初始接受概率P0,则转(4); (3)提高温度,更新t0,转(2); (4)结束。,温度的下降方法(1),等比例下降,温度的下降方法(2),等值下降,温度的下降方法(3),由定理1我们知道,在一定的条件下,与模拟退火算法相伴的时齐马尔可夫链存在平稳分布。如果温度每次下降的幅度比较小的话,则相邻温度下的平稳分布应该变化不大,也就是说,对于任
22、意一个状态i,相邻温度下的平稳分布应满足:,一个充分条件是:,两边取对数,并整理得: 用 代替 可得温度的衰减函数:,每一温度下的停止准则(1),固定长度方法 在每一个温度下,都使用相同的Lk。Lk的选取与具体的问题相关,一般与邻域的大小直接关联,通常选择为问题规模n的一个多项式函数。,每一温度下的停止准则(2),基于接受率的停止准则 : 规定一个接受次数R,在某一温度下,只有被接受的状态数达到R时,在该温度下的迭代才停止,转入下一个温度。 规定一个状态接受率R,R等于该温度下接受的状态数除以总生成的总状态数。如果接受率达到了R,则停止该温度下的迭代,转入下一个温度。 在迭代的过程中,若干相邻
23、的状态称为“一代”,如果相邻两代的解的指标函数差值小于规定的值的话,则停止该温度下的迭代。,算法的终止原则 (1),零度法 设定一个正常数e,当时tke时,算法结束。,算法的终止原则 (2),循环总控制法 给定一个指定的温度下降次数K,当温度的迭代次数达到K次时,则算法停止。,算法的终止原则 (3),无变化控制法 如果在相邻的n个温度中,得到的解的指标函数值无任何变化,则说明算法已经收敛。,算法的终止原则 (4),接受概率控制法 给定一个小的概率值p,如果在当前温度下除了局部最优状态外,其他状态的接受概率小于p值,则算法结束。,算法的终止原则 (5),领域平均概率控制法 设大小为N的一个领域,
24、在邻域内一个状态被接受的平均概率为1/N。设f0、f1为该领域中的局部最优值和局部次最优值。则次最优解是除了局部最优解以外接受概率最大的,其接受概率为:,如果该概率值小于平均值1/N时,即: 可以认为从局部最优解跳出的可能性已经很小了,因此可以终止算法。此时的终止温度tf为:,算法的终止原则 (6),相对误差估计法 设温度t时指标函数的期望值为: 则当终止温度1时,由泰勒展开近似有:,由于: 所以可用下式估计当前解与最优解之间的误差 :,或者使用相对于 的相对误差:,实际计算时: 其中:,应用举例旅行商问题,解的表示: n个城市的任何一种排列均是问题的一个可能解,表示为: 指标函数(能量函数)
25、 其中,新解的产生 采用第一节介绍的两个城市间的逆序交换方式得到问题的一个新解。 设当前解是 ,被选中要逆序交换的城市是第u和第v个到访的城市,uv。则逆序排列u和v之间的城市,得到问题的新解为: 则两个路径的距离差为:,新解的接受准则,初始参数的确定 康立山等人的方法: 初始温度t0=280; 在每个温度下采用固定的迭代次数,Lk=100n,n为城市数; 温度的衰减系数0.92,即tk+1=0.92tk; 算法的停止准则为:当相邻两个温度得到的解无任何变化时算法停止。,Nirwan Ansari和Edwin Hou的方法: 初始温度t0是这样确定的:从t0=1出发,并以t0=1.05t0对t0进行更新,直到接受概率大于等于0.9时为止,此时得到的温度为初始温度; 在每个温度下采用固定的迭代次数,Lk=10n,n为城市数; 温度的衰减系数0.95,即tk+1=0.95tk;,10城市旅行商问题求解结果,20城市旅行商问题求解结果,小结,局部搜索 模拟退火算法,
链接地址:https://www.31doc.com/p-2579040.html