局部搜索和模拟退火.ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,高级搜索,主要内容,局部搜索方法,模拟退火算法,遗传算法,优化与组合优化问题,很多问题属于优化问题，或者可以转化为优化问题,如,TSP,问题，皇后问题,优化问题的描述,设,x,是决策变量，,D,是,x,的定义域，,f(x),是指标函数，,g(x),是约束条件集合。则优化问题可以表示为，求解满足,g(x),的,f(x),最小值问题。,如果在定义域,D,上，满足条件,g(x),的解是有限的，则优化问题称为组合优化问题。,算法的时间复杂度,对于组合优化问题，由于其可能的解是有限的，当问题的规模比较小时，总可以通过枚举的方法获得问题的最优解，但当问题的规模比较大时，就难于求解了。,常用的算法复杂度函数,输入量,n,复杂性函数,10,20,30,40,100,n,10,ns,20,ns,30,ns,40,ns,100,ns,n,log,n,10,ns,26.0,ns,44.3,ns,64.1,ns,200,ns,n,2,100,ns,400,ns,900,ns,1.6,us,10,us,2,n,1.0,us,1.0,ms,1.1,s,18.3,min,4.0世纪,n,!,3.6,ms,77.1年,8.410,13,世纪,2.610,29,世纪,3.010,139,世纪,时间复杂性函数比较（10亿次/秒）,一些难的组合优化问题,旅行商问题,背包问题,装箱问题,.,寻求在可以接受的时间内得到满意解的方法,邻域的概念,邻域，简单的说就是一个点附近的其他点的集合。,在距离空间，邻域就是以某一点为中心的圆。,组合优化问题的定义：,设,D,是问题的定义域，若存在一个映射,N,，,使得：,则称,N(S),为,S,的邻域。,例：皇后问题,S=,Si,表示一个可能解，其中,Si,表示在第,i,行，第,Si,列有一个皇后。,如四皇后问题的一个解：,S=(2,4,1,3),Q,Q,Q,Q,定义映射,N,为棋盘上任意两个皇后的所在行或列进行交换，即,S,中任意两个元素交换位置。,例：当,S=(2,4,1,3),时，其邻域为：,N(S)=(4,2,1,3),(1,4,2,3),(3,4,1,2),(2,1,4,3),(2,3,1,4),(2,4,3,1),例：旅行商问题,用一个城市的序列表示一个可能的解。,通过交换两个城市的位置获取,S,的邻居,例：简单交换方法,设,S=(x,1,x,2,x,i,-1,x,i,x,i,+1,x,j,-1,x,j,x,j,+1,x,n,),则通过交换,xi,和,xj,两个城市的位置可以得到,S,的一个邻居：,S=(x,1,x,2,x,i,-1,x,j,x,i,+1,x,j,-1,x,i,x,j,+1,x,n,),x,1,x,2,x,n,x,j,+1,x,j,x,j,-1,x,i,-1,x,i,x,i,+1,x,1,x,2,x,n,x,j,+1,x,j,x,j,-1,x,i,-1,x,i,x,i,+1,例：逆序交换方法,设,x,i,、,x,j,是选取的两个城市，所谓的逆序交换方式是指，通过逆转,x,i,、,x,j,两个城市之间的城市次序来得到,S,的邻居。,设：,S=(x,1,x,2,x,i,-1,x,i,x,i,+1,x,j,-1,x,j,x,j,+1,x,n,),则：,S=(x,1,x,2,x,i,-1,x,i,x,j,-1,x,j-2,x,i,+1,x,j,x,j,+1,x,n,),x,1,x,2,x,n,x,j,+1,x,j,x,j,-1,x,i,-1,x,i,x,i,+1,x,1,x,2,x,n,x,j,+1,x,j,x,j,-1,x,i,-1,x,i,x,i,+1,局部搜索算法,基本思想：在搜索过程中，始终向着离目标最接近的方向搜索。,目标可以是最大值，也可以是最小值。,在后面的介绍中，如果没有特殊说明，均假定是最小值。,局部搜索算法（,Local Search）,1，,随机的选择一个初始的可能解,x,0,D，,x,b,=x,0,，P=N(,x,b,)；,2，如果不满足结束条件，则,3，,Begin,4，,选择,P,的一个子集,P，,x,n,为,P,中的最优解,5，如果,f(,x,n,)f(,x,b,),P=P ,x,n,=(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,中选择一个元素，,假设,x,n,=(a,d,c,b,e),f(,x,n,)=45,f(,x,n,)f(,x,b,),P=P ,x,n,=(a,e,c,d,b),(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d),第三次循环,从,P,中选择一个元素，,假设,x,n,=(a,e,c,d,b),f(,x,n,)=44,f(,x,n,)f(,x,b,),P=P ,x,n,=(a,b,d,c,e),(a,b,e,d,c),(a,b,c,e,d),第四次循环,从,P中选择一个元素，,假设,x,n,=(a,b,d,c,e),f(,x,n,)=44,f(,x,n,)f(,x,b,),P=P ,x,n,=(a,b,e,d,c),(a,b,c,e,d),第五次循环,从,P,中选择一个元素，,假设,x,n,=(a,b,e,d,c),f(,x,n,)=34,f(,x,n,)f(,x,b,),P=P ,x,n,=(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,中选择一个元素，,假设,x,n,=(a,d,e,b,c),f(,x,n,)=39,f(,x,n,)f(,x,b,),PP ,x,n,=(a,c,e,d,b),(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d),第八次循环,从,P,中选择一个元素，,假设,x,n,=(a,c,e,d,b),f(,x,n,)=38,f(,x,n,)f(,x,b,),P=P ,x,n,=(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d),第九次循环,从,P,中选择一个元素，,假设,x,n,=(a,b,d,e,c),f(,x,n,)=38,f(,x,n,)f(,x,b,),P=P ,x,n,=(a,b,c,d,e),(a,b,e,c,d),第十次循环,从,P,中选择一个元素，,假设,x,n,=a,b,c,d,e),f(,x,n,)=38,f(,x,n,)f(,x,b,),P=P ,x,n,=(a,b,e,c,d),第十一次循环,从,P,中选择一个元素，,假设,x,n,=(a,b,e,c,d),f(,x,n,)=41,f(,x,n,)f(,x,b,),P=P ,x,n,=,P,等于空，算法结束，,得到结果为,x,b,=(a,b,e,d,c),f(,x,b,)=34。,存在的问题,局部最优问题,解决方法,每次并不一定选择邻域内最优的点，而是依据一定的概率，从邻域内选择一个点，指标函数优的点，被选中的概率比较大，而指标函数差的点，被选中的概率比较小。,选择概率的计算,设求最大值：,选择概率的计算,当求最小值时：,局部搜索算法1（,Local Search 1）,1，,随机的选择一个初始的可能解,x,0,D，,x,b,=x,0,，P=N(,x,b,),2，如果不满足结束条件，则,3，,Begin,4，,对于所有的,xP,计算指标函数,f(x)，,并按照式（3）或者式（4）计算每一个点,x,的概率,5，依计算的概率值，从,P,中随机选择一个点,x,n,，,x,b,x,n,，P=N(,x,b,)，,转2,6，,End,7，,输出计算结果,8，结束,存在的问题,步长问题,初始值,搜索到的最优解,解决方法,变步长,初始值,搜索到的最优解,局部搜索算法2（,Local Search 21，,随机的选择一个初始的可能解,x,0,D，,x,b,=x,0,，,确定一个初始步长计算,P=N(,x,b,),2，如果不满足结束条件，则,3，,Begin,4，,选择,P,的一个子集,P，,x,n,为,P,中的最优解,5，如果,f(,x,n,)f(,x,b,)，,则,x,b,x,n,6，,按照某种策略改变步长，计算,P=N(,x,b,)，,转2,7，否则,P=P P，,转2。,8，,End,9，,输出计算结果,10，结束,存在问题,起始点问题,A,B,全局最大值,局部最大值,解决方法,随机的生成一些初始点，从每个初始点出发进行搜索，找到各自的最优解。再从这些最优解中选择一个最好的结果作为最终的结果。,局部搜索算法3（,Local Search 3）,1，k=0,2，,随机的选择一个初始的可能解,x,0,D，,x,b,=x,0,，,P=N(,x,b,),3，如果不满足结束条件，则,4，,Begin,5，,选择,P,的一个子集,P，,x,n,为,P,中的最优解,6，如果,f(,x,n,)f(,x,b,)，,则,x,b,x,n,，P=N(,x,b,)，,转3,7，否则,P=P P，,转3。,8，,End,9，k=k+1,10，,如果,k,达到了指定的次数，则从,k,个结果中选,择一个最好的结果输出，否则转（2）,11，输出结果,12，结束,多种方法的集成,以上几种解决方法可以结合在一起使用，比如第一、第二种方法的结合，就产生了我们将在后面介绍的模拟退火方法。,皇后搜索算法（,Queen Search）,1，,随机地将,n,个皇后分布在棋盘上，使得棋盘,的每行、每列只有一个皇后。,2，计算皇后间的冲突数,conflicts。,3，,如果冲突数,conflicts,等于0，则转（6）,4，对于棋盘上的任意两个皇后，交换他们的行,或者列，如果交换后的冲突数,conflicts,减少，,则接受这种交换，更新冲突数,conflicts，,转3。,5，如果陷入了局部极小，既交换了所有的皇后,后，冲突数仍然不能下降，则转1。,6，输出结果,7，结束。,不同规模下皇后问题的平均求解时间,皇 后 数,100,500,1000,2000,5000,10000,30000,平均时间（秒）,5,5,12,28,170,900,10000,模拟退火算法,是局部搜索算法的一种扩展,最早由,Metropolis,在1953年提出，,Kirkpatrick,等人在1983年成功地将模拟退火算法用于求解组合优化问题。,基本思想是借用金属的退化过程改进局部搜索算法,固体退火过程,溶解过程：,随着温度的不断上升，粒子逐渐脱离开其平衡位置，变得越来越自由，直到达到固体的溶解温度，粒子排列从原来的有序状态变为完全的无序状态。,退火过程：,随着温度的下降，粒子的热运动逐渐减弱，粒子逐渐停留在不同的状态，其排列也从无序向有序方向发展，直至到温度很低时，粒子重新以一定的结构排列。,粒子不同的排列结构，对应着不同的能量水平。如果退火过程是缓慢进行的，也就是说，温度的下降如果非常缓慢的话，使得在每个温度下，粒子的排列都达到一种平衡态，则当温度趋于0（绝对温度）时，系统的能量将趋于最小值。,如果以粒子的排列或者相应的能量来表达固体所处的状态，在温度,T,下，固体所处的状态具有一定的随机性。一方面，物理系统倾向于能量较低的状态，另一方面，热运动又妨碍了系统准确落入低能状态。,Metropolis,准则,从状态,i,转换为状态,j,的准则：,如果,E(j)E(i)，,则状态转换被接受；,如果,E(j)E(i)，,则状态转移被接受的概率为：,其中,E(i)、E(j),分别表示在状态,i、j,下的能量，,T,是温度，,K0,是波尔兹曼常数。,在给定的温度,T,下，当进行足够多次的状态转换后，系统将达到热平衡。此时系统处于某个状态,i,的概率由波尔兹曼（,Boltzmann,）,分布给出：,（6）,其中 为归一化因子，,S,是所有可能状态的集合。,考察一下式（6）随温度,T,的变化情况：,同一温度下，两个能量不同的状态,高温下的情况,低温下的情况,当温度下降时的情况,在给定的温度,T,下，设有,i、j,两个状态，,E(i)E(j)：,即在任何温度,T,下，系统处于能量低的状态的概率大于处于能量高的状态的概率。,由于,E(i)E(j)，,所以该项小于1,当温度趋于无穷时：,其中|,S|,表示系统所有可能的状态数。,当温度很高时，系统处于各个状态的概率基本相等，接近于平均值，与所处状态的能量几乎无关。,当温度趋于0时：,设,S,m,表示系统最小能量状态的集合，,E,m,是系统的最小能量。上式分子、分母同乘以,当温度趋近于0时，系统以等概率趋近于几个能量最小的状态之一，而系统处于其他状态的概率为0。以概率1达到能量最小的状态。,当温度上升或下降时：,系统落入低能量状态的概率随着温度的下降单调上升，而系统落入高能量状态的概率随着温度的下降单调下降。,在高温下，系统基本处于无序的状态，基本以等概率落入各个状态。在给定的温度下，系统落入低能量状态的概率大于系统落入高能量状态的概率，这样在同一温度下，如果系统交换的足够充分，则系统会趋向于落入较低能量的状态。随着温度的缓慢下降，系统落入低能量状态的概率逐步增加，而落入高能量状态的概率逐步减少，使得系统各状态能量的期望值随温度的下降单调下降，而只有那些能量小于期望值的状态，其概率才随温度下降增加，其他状态均随温度下降而下降。因此，随着能量期望值的逐步下降，能量低于期望值的状态逐步减少，当温度趋于0时，只剩下那些具有最小能量的状态，系统处于其他状态的概率趋近于0。因此最终系统将以概率1处于具有最小能量的一个状态。,达到最小能量状态的三个条件1）初始温度必须足够高；,（2）在每个温度下，状态的交换必须足够充分；,（3）温度,T,的下降必须足够缓慢。,组合优化问题与退火过程的类比,固体退火过程,组合优化问题,物理系统中的一个状态,组合优化问题的解,状态的能量,解的指标函数,能量最低状态,最优解,温度,控制参数,1，随机选择一个解,i，k=0，t,0,=,T,max,（,初始温度），计算指标函数,f(i)。,2，,如果满足结束条件，则转（15）。,3，,Begin,4，,如果在该温度内达到了平衡条件，则转（13）。,5，,Begin,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，,t,k,+1,=Drop(,t,k,)，k=k+1。,14，End,15，,输出结果。,16，结束。,算法中的问题,初始温度的选取,内循环的结束条件，即每个温度状态交换何时结束,外循环的结束条件，即温度下降到什么时候结束,温度的下降方法,在模拟退火过程中，给定温度下状态（解）的转移可以看作是一个马尔可夫链。对于任意两个状态,i,和,j，,我们用,P,t,(i,j),表示温度,t,下，从状态,i,转移到状态,j,的一步转移概率，则有：,其中：,G,t,(i,j),是产生概率，表示从状态,i,产生状态,j,的概率。,A,t,(i,j),是接受概率，表示在状态,i,产生状态,j,后，接受状态,j,的概率。,定理1,满足条件的,G,t,(i,j)、A,t,(i,j),举例：,说明：条件2的后半部分除外，该条件与具体的问题有关。,定理2：,在定理1的条件下，如果对于任意两个状态,有：,则有：,定理3（放宽了定理1的条件）,G,t,(i,j)、A,t,(i,j),满足定理1中除条件（2）以外的所有其他条件，并且：,1，对于任意两个状态,i、j，,它们相互为邻居或者相互都不为邻居；,2，对于任意,i，,G,t,(i,j),满足：,3，状态空间,S,对于邻域是连通的；,则与模拟退火算法相伴的时齐马尔可夫链存在平稳分布，其分布概率为：,算法的实现,（1）初始温度,t,0,；,（2）,温度,t,的衰减函数，即温度的下降 方法；,（3）算法的终止准则，用终止温度,t,f,或 者终止条件给出；,（4）每个温度,t,下的马尔可夫链长度,L,k,。,起始温度的选取（1）,一个合适的初始温度，应保证平稳分布中每一个状态的概率基本相等，也就是接受概率,P,0,近似等于1。在,Metropolis,准则下，即要求：,如果我们给定一个比较大的接受概率,P,0,，,则：,其中，可以有以下估计方式：,起始温度的选取（2）,假设在,t,0,下随机的生成一个状态序列，分别用,m,1,和,m,2,表示指标函数下降的状态数和指标函数上升的状态数，表示状态增加的平均值。则,m,2,个状态中，被接受的个数为：,所以平均接受率为：,求解有：,起始温度的选取（3）,模拟固体的升温过程：,（1）给定一个希望的初始接受概率,P,0,，,给定一个较低的初始温度,t,0,，,比如,t,0,1；,（2）,随机的产生一个状态序列，并计算该序列的接收率：,如果接收率大于给定的初始接受概率,P,0,，,则转（4）；,（3）提高温度，更新,t,0,，,转（2）；,（4）结束。,温度的下降方法（1）,等比例下降,温度的下降方法（2）,等值下降,温度的下降方法（3）,由定理1我们知道，在一定的条件下，与模拟退火算法相伴的时齐马尔可夫链存在平稳分布。如果温度每次下降的幅度比较小的话，则相邻温度下的平稳分布应该变化不大，也就是说，对于任意一个状态,i，,相邻温度下的平稳分布应满足：,一个充分条件是：,两边取对数，并整理得：,用 代替 可得温度的衰减函数：,每一温度下的停止准则（1）,固定长度方法,在每一个温度下，都使用相同的,L,k,。,L,k,的选取与具体的问题相关，一般与邻域的大小直接关联，通常选择为问题规模,n,的一个多项式函数。,每一温度下的停止准则（2）,基于接受率的停止准则：,规定一个接受次数,R，,在某一温度下，只有被接受的状态数达到,R,时，在该温度下的迭代才停止，转入下一个温度。,规定一个状态接受率,R，R,等于该温度下接受的状态数除以总生成的总状态数。如果接受率达到了,R，,则停止该温度下的迭代，转入下一个温度。,在迭代的过程中，若干相邻的状态称为“一代”，如果相邻两代的解的指标函数差值小于规定的值的话，则停止该温度下的迭代。,算法的终止原则,（1）,零度法,设定一个正常数,e，,当时,t,k,e,时，算法结束。,算法的终止原则,（2）,循环总控制法,给定一个指定的温度下降次数,K，,当温度的迭代次数达到,K,次时，则算法停止。,算法的终止原则,（3）,无变化控制法,如果在相邻的,n,个温度中，得到的解的指标函数值无任何变化，则说明算法已经收敛。,算法的终止原则,（4）,接受概率控制法,给定一个小的概率值,p，,如果在当前温度下除了局部最优状态外，其他状态的接受概率小于,p,值，则算法结束。,算法的终止原则,（5）,领域平均概率控制法,设大小为,N,的一个领域，在邻域内一个状态被接受的平均概率为1/,N。,设,f,0,、f,1,为该领域中的局部最优值和局部次最优值。则次最优解是除了局部最优解以外接受概率最大的，其接受概率为：,如果该概率值小于平均值1/,N,时，即：,可以认为从局部最优解跳出的可能性已经很小了，因此可以终止算法。此时的终止温度,t,f,为：,算法的终止原则,（6）,相对误差估计法,设温度,t,时指标函数的期望值为：,则当终止温度1时，由泰勒展开近似有：,由于：,所以可用下式估计当前解与最优解之间的误差：,或者使用相对于 的相对误差：,实际计算时：,其中：,应用举例旅行商问题,解的表示：,n,个城市的任何一种排列均是问题的一个可能解，表示为:,指标函数(能量函数,),其中,新解的产生,采用第一节介绍的两个城市间的逆序交换方式得到问题的一个新解。,设当前解是 ，被选中要逆序交换的城市是第,u,和第,v,个到访的城市，,uv。,则逆序排列,u,和,v,之间的城市，得到问题的新解为：,则两个路径的距离差为：,新解的接受准则,初始参数的确定,康立山等人的方法：,初始温度,t,0,=280；,在每个温度下采用固定的迭代次数，,L,k,=100n，n,为城市数；,温度的衰减系数0.92，即,t,k,+1,=0.92,t,k,；,算法的停止准则为：当相邻两个温度得到的解无任何变化时算法停止。,Nirwan Ansari,和,Edwin,Hou,的方法：,初始温度,t,0,是这样确定的：从,t,0,=1,出发，并以,t,0,=1.05t,0,对,t,0,进行更新，直到接受概率大于等于0.9时为止，此时得到的温度为初始温度；,在每个温度下采用固定的迭代次数，,L,k,=10n，n,为城市数；,温度的衰减系数0.95，即,t,k,+1,=0.95,t,k,；,10,城市旅行商问题求解结果,路径长度,出现次数,平均转移次数,路径,最优,2.691,906,3952,BCADEFGHIJ,次优,2.752,46,4056,BCADEGFHIJ,第三,2.769,10,4053,DEFGHIJCBA,最差,2.898,5,4497,ABCDEFHIJG,20,城市旅行商问题求解结果,路径长度,出现次数,平均转移次数,路径,最优,24.38,792,8740,ACLBIQFTMEPRGSOJHDKN,次优,24.62,167,8638,ADCLBIQFTMEPRGSOJHKN,第三,25.17,39,9902,ANKDHIOJSGRPEMTFQBLC,最差,25.50,1,5794,AQFTMEPRGSJOIBLCDHKN,