5.局部搜索算法PPT学习课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,5,局部搜索算法,1,2,局部搜索算法,前面的搜索算法都是保留搜索路径的，到达目标的路径就是问题的解,然而许多问题中到达目标的路径是无关紧要的,与系统地搜索状态空间,(,保留各种路径,),相对，不关心路径的搜索算法就是局部搜索算法,局部搜索从一个单独的当前状态出发，通常只移动到相邻状态,典型情况下搜索的路径不保留,3,局部搜索与最优化问题,局部搜索算法的优点：,只使用很少的内存,(,通常是一个常数,),经常能在不适合系统化算法的很大或无限的状态空间中找到合理的解,最优化问题,根据一个目标函数找到最佳状态,/,只有目标函数，而不考虑,(,没有,),“,目标测试,”,和,“,路径耗散,”,局部搜索算法适用于最优化问题,4,状态空间地形图,(1),山肩,目标函数,全局最大值,局部最大值,“平坦”局部最大值,状态空间,当前状态,5,状态空间地形图,(2),在状态图中，既有,“,位置,”,(,用状态表示,),又有,“,高度,”,(,用耗散值或目标函数值表示,),如果高度对应于耗散值，则目标是找到全局最小值，即图中最低点,如果高度对应于目标函数，则目标是找到全局最大值，即图中最高峰,如果存在解，则完备的局部搜索算法能够找到解,而最优的局部搜索算法能够找到全局最大或最小值,6,局部搜索算法,本节简要介绍以下,4,种局部搜索算法,/,介绍其算法思想,爬山法搜索,模拟退火搜索,局部剪枝搜索,遗传算法,从学习的角度看遗传算法也是搜索假设空间的一种方法,(,学习问题归结为搜索问题,),生成后继假设的方式,7,爬山法,搜索,爬山法,(hill-climbing),就是向值增加的方向持续移动,登高过程,/,如果相邻状态中没有比它更高的值，则算法结束于顶峰,爬山法搜索算法思想：,(1),令初始状态,S,0,为当前状态,(2),若当前状态已经达标，则算法运行结束，搜索成功,(3),若存在一个动作可以作用于当前状态以产生一个新状态，使新状态的估计值优于当前状态的估计值，则放弃当前状态，并令刚产生的新状态为当前状态，转,(2),(4),取当前状态为相对最优解，停止执行算法,例子：,8,皇后问题,目标：任何一个皇后都不会攻击到其他的皇后（皇后可以攻击和它在同一行、同一列或同一对角线上的皇后）,h,取作可以彼此攻击的皇后对的数目（忽略障碍）,8,h,17,的一个状态，,h,取局部极小值时的一个状态,5,步,9,10,爬山法搜索的局限,爬山法是一种局部贪婪搜索，不是最优解算法,(,或是不完备的,)/,其问题是：,局部极大值,比其邻居状态都高的顶峰，但是小于全局最大值,(,参照状态空间地形图,),山脊,一系列的局部极大值,高原,评价函数平坦的一块区域,(,或者山肩,),11,爬山法搜索的变形,爬山法的变形,随机爬山法,随机选择下一步,首选爬山法,随机选择直到有优于当前节点的下一步,随机重新开始爬山法,随机生成初始状态，进行一系列爬山法搜索,这时算法是完备的概率接近,1,12,模拟,退火搜索,将爬山法,(,停留在局部山峰,),和随机行走以某种方式结合，以同时获得完备性和效率,模拟退火的思想,想象在不平的表面上如何使一个乒乓球掉到最深的裂缝中,如果只让其在表面滚动，则它只会停留在局部极小点,/,如果晃动平面，可以使乒乓球弹出局部极小点,/,技巧是晃动足够大使乒乓球弹出局部极小点，但又不能太大把它从全局极小点中赶出,13,模拟退火的解决思路,(1),思路,开始使劲晃动,(,先高温加热,),然后慢慢降低摇晃的强度,(,逐渐降温,),退火过程,算法的核心,移动选择,选择随机移动，如果评价值改善，则移动被接受，否则以某个小于,1,的概率接受,概率按照移动评价值变坏的梯度,E,而呈指数级下降,/,同时也会随着作为控制的参数,“,温度,”,T,的降低,(,数值减小,),而降低,接受概率,=e,E,/T,(,注意此时,E,0),14,模拟退火的解决思路,(2),温度,T,是时间的函数，按照模拟退火的思想，数值应该逐渐减小,(,降温,),因为,接受概率,=e,E,/T,且,E,0,，所以当温度高时，接受概率较大,(,接近,1)/,而,T,越来越低时，,E,/T,变大，因而接受概率降低,可以证明，如果,T,下降得足够慢，则算法找到全局最优解的概率接近,1,15,局部,剪枝搜索,基本思想,与,只从一个单独的起始状态出发不同，局部剪枝搜索从,k,个随机生成的状态开始，每步生成全部,k,个状态的所有后继状态,/,如果其中之一是目标状态，算法停止；否则从全部后继状态中选择最佳的,k,个状态继续搜索,在局部剪枝搜索过程中，有用的信息在,k,个并行的搜索线程之间传递,算法会很快放弃没有成果的搜索而把资源放在取得最大进展的搜索上,16,随机剪枝搜索,如果,k,个状态缺乏多样性，则局部剪枝搜索会受其影响，性能变差,算法的变种,随机剪枝搜索帮助缓解这一问题,随机剪枝搜索不是选择最好的,k,个后代，而是按照一定概率随机地选择,k,个后继状态,/,选择给定后继状态的概率是状态值的递增函数,类似于自然选择过程,状态对应生物体，其值对应于适应性，后代就是后继状态,17,遗传,算法,遗传算法,(generic algorithm/GA),是随机剪枝的变种,不是通过修改单一状态而是通过把两个父状态结合以生成后继状态,与剪枝搜索一样，遗传算法也是从,k,个随机状态开始,这,k,个状态称为种群，每个状态称为个体,个体用有限长的字符串,(,通常为,0/1,串,),表示,每个状态用其评价函数,(,适应度函数,),给出评价值,(,适应值,),随后的操作包括,选择,/,杂交,/,变异,18,遗传算法的操作,选择,(,或者称繁殖,),按照一定概率随机地选择两对个体进行繁殖,(,即生成后继状态,),杂交,(,或者称交叉,),杂交点是在表示状态的字符串中随机选择的一个位置，以此形成新状态,后代是父串在杂交点上进行杂交,(,各取一部分,),得来的,变异,在新生成的串中各个位置都会按照一个独立的小概率随机变异,19,遗传算法简要描述,(1),定义问题和目标函数,(2),选择候选解作为初始种群，每个解作为个体用二进制串表示,(,个体相当于染色体，其中的元素相当于基因,),(3),根据目标函数，对于每个个体计算适应函数值,(4),为每个个体指定一个与其适应值成正比的被选择概率,(,繁殖概率,),(5),根据概率选择个体，所选个体通过交叉,/,变异等操作产生新一代种群,(6),如果找到了解或者某种限制已到，则过程结束；否则转,(3),20,遗传算法的特点,遗传算法也结合了“上山”趋势和随机搜索，并在并行搜索线程之间交换信息,遗传算法的主要优势来自于杂交,数学上可以证明，如果基因编码的位置在初始时就随机转换的话，杂交就没有优势,杂交的优势在于它能够将独立发展的若干个相对固定的字符,(,能够执行有用的功能,“,砖块,”,),组合起来，提高了搜索的粒度,所谓有用的砖块，就是几个结合起来可以构造问题的解,参见书中的八皇后问题举例,21,遗传算法的模式,遗传算法上述特点可以用模式,(schema),来解释,模式是某些位置上的数字尚未确定的一个状态子串,能够匹配模式的字符串称为该模式的实例,如果一个模式的实例的平均适应值超过均值，则种群内这个模式的实例数量会随时间而增长,遗传算法在模式和解的有意义成分相对应时才会工作得最好,遗传算法有很多应用，但是在什么情况下它会达到好效果，还有很多研究要做,遗传算法,通过把,两个父,状态结合来生成后继,8,皇后的例子，其中每个状态用一个长度为,8,的字符串来表示，适应度函数取作,不相互攻击的皇后对数目。,22,前一页图中（,c,）,1,和,2,生成（,d,）,1,23,与或图搜索,超图：由节点集和若干连接符组成的图。,K_,连接符：从一个父节点指向一组,K,个后继节点的,K,条连线。,n,1,n,2,a,b,c,d,3_,连接,1_,连接,1_,连接,n,0,n,1,n,3,n,6,n,7,n,2,n,5,n,4,n,8,超 图,问题：如何在超图中找出一个解图。,24,求解图的方法,：（从节点,n,到目标节点集,N,的解图）,从节点,n,开始，正确选择一个外向连接符。,从该连接符指向的每个后继节点出发，继续选择一个外向连接符。,依次类推，直到由此产生的每个后继节点都是,N,中的一个元素为止。,n,0,n,3,n,6,n,7,n,5,n,4,n,8,解图,1,n,1,n,5,n,0,n,8,n,7,解图,2,上面是两个从节点,n,0,到目标节点集,N,的解图，,N=n,7,n,8,。,25,无环解图的递归定义：,一个与或图,G,中，从,节点,n,到节点集,N,的解图记为,G,如果节点,n,是,N,中一个元素，则,G,由单一元素组成。,如果节点,n,有一个指向节点集,n,1,n,2,n,k,的外向连接符,K,，使得从每个,n,i,到,N,有一个解图（,i=1,2k,）,则,G,由节点,n,、连接符,K,及,n,1,n,2,n,k,中的每个节点到,N,的解图组成。,否则从,n,到,N,不存在解图。,解图的耗散值计算：,设,K,_,连接符的耗散值为,K,，,G,的耗散值为,K(n,N),若,n,是,N,的一个元素，则,K(n,N)=0,若,n,有一个到解图中后继节点集,n,1,n,2,n,i,的外向连接符，设该连接符的耗散值为,C,n,，则,K(n,N),C,n,+K(n,1,N)+K(n,2,N)+K(n,i,N),26,n,0,n,3,n,6,n,7,n,5,n,8,n,1,n,4,n,5,n,0,n,8,n,7,左图耗散值,K(n,0,N),1+K(n,1,N),1+1+K(n,3,N),1+1+2+K(n,5,N)+K(n,6,N),1+1+2+2+K(n,7,N)+K(n,8,N)+2+K(n,7,N)+K(n,8,N),1+1+2+2+0+0+2+0+0,8,右图耗散值,K(n,0,N),2+K(n,4,N)+K(n,5,N),2+1+K(n,5,N)+2+K(n,7,N)+K(n,8,N),2+1+2+K(n,7,N)+K(n,8,N)+2+K(n,7,N)+K(n,8,N),2+1+2+0+0+2+0+0,7,27,能解节点,定义：,终节点是能解节点。,如果非终节点有“或”子节点，当且仅当其子节点至少有一个能解，则该非终节点是能解节点。,如果非终节点有“与”子节点，当且仅当其子节点都能解，则该非终节点是能解节点。,不能解节点,定义：,没有后裔的非终节点是不能解节点（该节点是叶节点但不在,N,中）。,如果非终节点有“或”子节点，当且仅当所有子节点都不能解，则该非终节点是不能解节点。,如果非终节点有“与”子节点，至少有一个子节点不能解，则该非终节点是不能解节点。,28,AO*,算法,建立一个搜索图,G,，仅包含初始节点,s,，,s,的耗散值为,q(s)=h(s),，如果,s,是终,节点，则标记,s,为,SOLVED,Until,s,已标记,SOLVED,do:,begin,从,s,出发沿着有标记的连接符找出一个,G,的待扩充的局部解图,G,任取,G,中一个非终节点,n,作为当前节点。,扩充节点,n,，生成,n,的全部子节点并将其加入到,G,中。对于未在,G,中出现,过的子节点,n,j,，计算其耗散值,q(n,j,)=h(n,j,),；对于子节点中属于终节点者，,标记,SOLVED,并赋值为,0,建立一个仅包含节点,n,的单一节点集,S,Until S,为空,do,：,CONTINUE,29,begin,从,S,中移出这样节点,m,，该,m,节点的子节点不在,S,中,计算修改,m,耗散值,q(m),：对指向节点集,n,1i,n,2i,n,ki,的每个连接,符,i,，分别计算,q,i,(m)=C,i,+q(n,1i,)+q(n,2i,)+q(n,Ki,),令：,q(m)=min q,i,(m),即：取耗散值最小的连接符的耗散值作为,q(m),标记该具有最小耗散值的连接符，如果原来对,m,的某个连接符所做,的标记与新标记的连接符不同，则保留新标记，去掉原来标记。,如果该连接符的所有后继节点都已标记,SOLVED,，则此,m,节点标记,SOLVED,如果,m,已标记,SOLVED,或者,m,修正后的耗散值与原来的耗散值不同，则,将,m,的所有父节点加入到,S,中，这些父节点必须通过有标记的连接符与,节点,m,相连,end,end,30,例题：（预先给出了各节点,h,值的估计值，实际的,h,值在搜索中计算得出）,h(n,0,)=0,，,h(n,1,)=2,，,h(n,2,)=h(n,3,)=4,，,h(n,4,)=h(n,5,)=1,，,h(n,6,)=2,，,h(n,7,)=h(n,8,)=0 N=n,7,n,8,循环,1,：,n,0,n,5,n,4,n,1,外循环：初始状态,G=S,，取当前节点,n=n,0,，扩充节点,n,0,，,得到,n,1,n,5,n,4,并加入,G,中，计算各节点耗散值得：,h(n,1,)=2,，,h(n,5,)=1,，,h(n,4,)=1,，,组成单一节点集,S=,n,0,内循环：取出节点,n,0,，,n,0,有,2,个外向连接符，分别计算：,h(n,0,)=C,0,+h(n,1,)=1+2=3 (1_,连接符,),h(n,0,)=C,0,+h(n,5,)+h(n,4,)=2+1+1=4 (2_,连接符,),取,q(n,0,)=min 3,4,=3,，标记选定的,1_,连接符,节点,n,1,无标记 节点,n,0,不能标记，内循环结束,标记,31,循环,2,：,n,0,n,5,n,4,n,1,外循环：沿标记取当前节点,n=n,1,，扩充节点,n,1,，,得到,n,2,n,3,并加入,G,中，计算耗散值得：,h(n,2,)=4,，,h(n,3,)=4,组成单一节点集,S=,n,1,内循环：取出节点,n,1,，,n,1,有,2,个外向连接符，分别计算：,h(n,1,)=C,1,+h(n,2,)=1+4=5 (,左,1_,连接符,),h(n,1,)=C,1,+h(n,3,)=1+4=5 (,右,1_,连接符,),取,q(n,1,)=min 5,5,=5,，按照自然排序，标记选定的左,1_,连接符,节点,n,3,无标记 节点,n,1,不能标记,节点,n,1,的,h,值由原来的,2,修改为,5,，将,n,1,的父节点,n,0,加入到单一节点集,S,中,重新计算,h(n,0,),h(n,0,)=C,0,+h(n,1,)=1+5=6 (1_,连接符,),h(n,0,)=C,0,+h(n,5,)+h(n,4,)=2+1+1=4 (2_,连接符,),取,q(n,0,)=min 6,4,=4,，取消原来,n,0,n,1,标记，重新标记,2_,连接符,节点,n,4,n,5,无标记 节点,n,0,不能标记，内循环结束,n,2,n,3,32,循环,3,：,n,0,n,5,n,4,n,1,外循环：沿标记取当前节点,n=n,5,，扩充节点,n,5,，,得到,n,6,n,7,n,8,并加入,G,中，计算耗散值得：,h(n,6,)=2,，,h(n,7,)=0,，,h(n,8,)=0,组成单一节点集,S=,n,5,n,7,n,8,是终节点，标记节点,n,7,n,8,内循环：取出节点,n,5,，,n,5,有,2,个外向连接符，分别计算：,h(n,5,)=C,5,+h(n,6,)=1+2=3 (1_,连接符,),h(n,5,)=C,5,+h(n,7,)+h(n,8,)=2+0+0=2 (2_,连接符,),取,q(n,5,)=min 3,2,=2,，记选定的,2_,连接符,节点,n,7,n,8,有标记 标记节点,n,5,并将,n,5,的父节点,n,0,加入到,S,中,内循环：,取,n,0,，计算,h(n,0,)=C,0,+h(n,1,)=1+5=6 (1_,连接符,),h(n,0,)=C,0,+h(n,5,)+h(n,4,)=2+2+1=5 (2_,连接符,),取,q(n,0,)=min 6,5,=5,，原来连接不变,节点,n,5,有标记但是,n,4,无标记 节点,n,0,不能标记，内循环结束,n,2,n,3,n,6,n,7,n,8,33,循环,4,：,n,0,n,5,n,4,n,1,外循环：沿标记取当前节点,n=n,54,扩充节点,n,4,，,得,n,5,n,8,，计算耗散值得：,h(n,5,)=2,，,h(n,8,)=0,组成单一节点集,S=,n,4,内循环：取节点,n,4,，,n,4,有,2,个外向连接符，计算：,h(n,4,)=C,4,+h(n,5,)=1+2=3 (,左,1_,连接符,),h(n,4,)=C,4,+h(n,8,)=1+0=2 (,右,1,_,连接符,),取,q(n,4,)=min 3,2,=2,，记选定的右,1_,连接符,节点,n,7,n,8,有标记 标记节点,n,4,并将,n,4,的父节点,n,0,加入到,S,中,内循环：,取,n,0,，计算,h(n,0,)=C,0,+h(n,1,)=1+5=6 (1_,连接符,),h(n,0,)=C,0,+h(n,5,)+h(n,4,)=2+2+1=5 (2_,连接符,),取,q(n,0,)=min 6,5,=5,，原来连接不变,节点,n,5,n,4,有标记 标记节点,n,0,，内、外循环结束，算法结束。,n,2,n,3,n,6,n,7,n,8,34,讨论：,在外循环选择当前节点,n,并对其扩充时，如果节点,n,无后继节点，则在内循,环修改耗散值时可以对节点,n,赋一个很大的,q,值，即放弃此路径。,外循环选择当前节点的原则：选最可能使局部解图耗散值变化较大的节点，,以加快算法收敛速度。,对,h(n),的单调限制：设节点,n,的子节点集为,n,1,n,2,n,k,，其耗散值为,h(n)C,n,+h(n,1,)+h(n,2,)+h(n,k,),C,n,：,连接符的耗散值,如果,h(n),满足单调限制，且,h(t,i,)=0 t,i,N,，则有,h(n)h*(n),此时，,AO*,算法一定能够找到最佳解图 （如果,sN,有解）,AO*,算法仅考虑,h(n),而不考虑,g,(n),，原因是内循环的回溯修正计算使计算,g,(n),值没有意义。,AO*,算法,不适用于有环图（因为耗散值的计算可能会无休止）。,与或节点并存，,h(n),代表解图而不仅仅是一条路径。,35,