第9讲模拟退火算法等.ppt
《第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,xi,xj+1,xn),x1,x2,xn,xj+1,xj,xj-
2、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+1,x1,x2,xn,xj+1,xj,xj-1,xi-1,xi,xi+1,1.局部搜索算法,基本思想:在搜索过程中,始终向着离目标最
3、接近的方向搜索。目标可以是最大值,也可以是最小值。在后面的介绍中,如果没有特殊说明,均假定是最小值。,局部搜索算法(Local Search)1,随机的选择一个初始的可能解x0D,xb=x0,P=N(xb);2,如果不满足结束条件,则3,Begin4,选择P的一个子集P,xn为P中的最优解5,如果f(xn)f(xb),则xb xn,P=N(xb),转2;f(x)为指标函数。6,否则P=P P,转2。7,End8,输出计算结果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
4、 通过交换两个城市获得领域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=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
5、,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(xb),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
6、,c),(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 xn=(a,c,e,d,b),(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d),第八次循环,从P中选择一个元素,假设xn
7、=(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,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等于空,算法
8、结束,得到结果为xb=(a,b,e,d,c),f(xb)=34。,存在的问题,局部最优问题,解决方法,每次并不一定选择邻域内最优的点,而是依据一定的概率,从邻域内选择一个点,指标函数优的点,被选中的概率比较大,而指标函数差的点,被选中的概率比较小。,选择概率的计算,设求最大值:,选择概率的计算,当求最小值时:,局部搜索算法1(Local Search 1)1,随机的选择一个初始的可能解x0D,xb=x0,P=N(xb)2,如果不满足结束条件,则3,Begin4,对于所有的xP计算指标函数f(x),并按照式(3)或者式(4)计算每一个点x的概率5,依计算的概率值,从P中随机选择一个点 xn,xb
9、 xn,P=N(xb),转26,End7,输出计算结果8,结束,存在的问题,步长问题,解决方法,变步长,局部搜索算法2(Local Search 2)1,随机的选择一个初始的可能解x0D,xb=x0,确定一个初始步长计算P=N(xb)2,如果不满足结束条件,则3,Begin4,选择P的一个子集P,xn为P中的最优解5,如果f(xn)f(xb),则xb xn6,按照某种策略改变步长,计算P=N(xb),转27,否则P=P P,转2。8,End9,输出计算结果10,结束,存在问题,起始点问题,A,B,全局最大值,局部最大值,解决方法,随机的生成一些初始点,从每个初始点出发进行搜索,找到各自的最优解
10、。再从这些最优解中选择一个最好的结果作为最终的结果。,局部搜索算法3(Local Search 3)1,k=02,随机的选择一个初始的可能解x0D,xb=x0,P=N(xb)3,如果不满足结束条件,则4,Begin5,选择P的一个子集P,xn为P中的最优解6,如果f(xn)f(xb),则xb xn,P=N(xb),转37,否则P=P P,转3。8,End9,k=k+110,如果k达到了指定的次数,则从k个结果中选 择一个最好的结果输出,否则转(2)11,输出结果12,结束,多种方法的集成,以上几种解决方法可以结合在一起使用,比如第一、第二种方法的结合,就产生了我们将在后面介绍的模拟退火方法。,
11、2.模拟退火算法,是局部搜索算法的一种扩展最早由Metropolis在1953年提出,Kirkpatrick等人在1983年成功地将模拟退火算法用于求解组合优化问题。基本思想是借用金属的退化过程改进局部搜索算法,固体退火过程,溶解过程:随着温度的不断上升,粒子逐渐脱离开其平衡位置,变得越来越自由,直到达到固体的溶解温度,粒子排列从原来的有序状态变为完全的无序状态。退火过程:随着温度的下降,粒子的热运动逐渐减弱,粒子逐渐停留在不同的状态,其排列也从无序向有序方向发展,直至到温度很低时,粒子重新以一定的结构排列。,粒子不同的排列结构,对应着不同的能量水平。如果退火过程是缓慢进行的,也就是说,温度的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模拟 退火 算法
链接地址:https://www.31ppt.com/p-5136010.html