5.局部搜索算法

1、5 局部搜索算法,2,局部搜索算法,前面的搜索算法都是保留搜索路径的，到达目标的路径就是问题的解然而许多问题中到达目标的路径是无关紧要的 与系统地搜索状态空间(保留各种路径)相对，不关心路径的搜索算法就是局部搜索算法 局部搜索从一个单独的当前状态出发，通常只移动到相邻状态 典型情况下搜索的路径不保留,3,局部搜索与最优化问题,局部搜索算法的优点： 只使用很少的内存(通常是一个常数) 经常能在不适合系统化算法的很大或无限的状态空间中找到合理的解 最优化问题根据一个目标函数找到最佳状态 / 只有目标函数，而不考虑(没有)“目标测试”和“路径耗散” 局部搜索算法适用于最优化问题,4,状态空间地形图(

2、1),5,状态空间地形图(2),在状态图中，既有“位置”(用状态表示)又有“高度”(用耗散值或目标函数值表示) 如果高度对应于耗散值，则目标是找到全局最小值，即图中最低点 如果高度对应于目标函数，则目标是找到全局最大值，即图中最高峰 如果存在解，则完备的局部搜索算法能够找到解 而最优的局部搜索算法能够找到全局最大或最小值,6,局部搜索算法,本节简要介绍以下4种局部搜索算法 / 介绍其算法思想 爬山法搜索 模拟退火搜索 局部剪枝搜索 遗传算法 从学习的角度看遗传算法也是搜索假设空间的一种方法(学习问题归结为搜索问题)生成后继假设的方式,7,爬山法搜索,爬山法(hill-climbing)就是向值

3、增加的方向持续移动登高过程 / 如果相邻状态中没有比它更高的值，则算法结束于顶峰 爬山法搜索算法思想： (1)令初始状态S0为当前状态 (2)若当前状态已经达标，则算法运行结束，搜索成功 (3)若存在一个动作可以作用于当前状态以产生一个新状态，使新状态的估计值优于当前状态的估计值，则放弃当前状态，并令刚产生的新状态为当前状态，转(2) (4)取当前状态为相对最优解，停止执行算法,例子：8皇后问题,目标：任何一个皇后都不会攻击到其他的皇后（皇后可以攻击和它在同一行、同一列或同一对角线上的皇后） h取作可以彼此攻击的皇后对的数目（忽略障碍）,h17的一个状态，,h取局部极小值时的一个状态,5步,1

4、0,爬山法搜索的局限,爬山法是一种局部贪婪搜索，不是最优解算法(或是不完备的) / 其问题是： 局部极大值比其邻居状态都高的顶峰，但是小于全局最大值(参照状态空间地形图) 山脊一系列的局部极大值 高原评价函数平坦的一块区域(或者山肩),11,爬山法搜索的变形,爬山法的变形 随机爬山法随机选择下一步 首选爬山法随机选择直到有优于当前节点的下一步 随机重新开始爬山法随机生成初始状态，进行一系列爬山法搜索这时算法是完备的概率接近1,12,模拟退火搜索,将爬山法(停留在局部山峰)和随机行走以某种方式结合，以同时获得完备性和效率 模拟退火的思想 想象在不平的表面上如何使一个乒乓球掉到最深的裂缝中如果只让

5、其在表面滚动，则它只会停留在局部极小点 / 如果晃动平面，可以使乒乓球弹出局部极小点 / 技巧是晃动足够大使乒乓球弹出局部极小点，但又不能太大把它从全局极小点中赶出,13,模拟退火的解决思路(1),思路开始使劲晃动(先高温加热)然后慢慢降低摇晃的强度(逐渐降温)退火过程 算法的核心移动选择 选择随机移动，如果评价值改善，则移动被接受，否则以某个小于1的概率接受 概率按照移动评价值变坏的梯度E而呈指数级下降 / 同时也会随着作为控制的参数“温度”T的降低(数值减小)而降低 接受概率=eE/T(注意此时E 0),14,模拟退火的解决思路(2),温度T是时间的函数，按照模拟退火的思想，数值应该逐渐减

6、小(降温) 因为接受概率=eE/T且E 0，所以当温度高时，接受概率较大(接近1) / 而T越来越低时，E/T变大，因而接受概率降低 可以证明，如果T下降得足够慢，则算法找到全局最优解的概率接近1,15,局部剪枝搜索,基本思想与只从一个单独的起始状态出发不同，局部剪枝搜索从k个随机生成的状态开始，每步生成全部k个状态的所有后继状态 / 如果其中之一是目标状态，算法停止；否则从全部后继状态中选择最佳的k个状态继续搜索 在局部剪枝搜索过程中，有用的信息在k个并行的搜索线程之间传递算法会很快放弃没有成果的搜索而把资源放在取得最大进展的搜索上,16,随机剪枝搜索,如果k个状态缺乏多样性，则局部剪枝搜索

7、会受其影响，性能变差 算法的变种随机剪枝搜索帮助缓解这一问题随机剪枝搜索不是选择最好的k个后代，而是按照一定概率随机地选择k个后继状态 / 选择给定后继状态的概率是状态值的递增函数 类似于自然选择过程状态对应生物体，其值对应于适应性，后代就是后继状态,17,遗传算法,遗传算法(generic algorithm/GA)是随机剪枝的变种不是通过修改单一状态而是通过把两个父状态结合以生成后继状态 与剪枝搜索一样，遗传算法也是从k个随机状态开始这k个状态称为种群，每个状态称为个体 个体用有限长的字符串(通常为0/1串)表示 每个状态用其评价函数(适应度函数)给出评价值(适应值) 随后的操作包括选择/

8、杂交/变异,18,遗传算法的操作,选择(或者称繁殖)按照一定概率随机地选择两对个体进行繁殖(即生成后继状态) 杂交(或者称交叉)杂交点是在表示状态的字符串中随机选择的一个位置，以此形成新状态后代是父串在杂交点上进行杂交(各取一部分)得来的 变异在新生成的串中各个位置都会按照一个独立的小概率随机变异,19,遗传算法简要描述,(1)定义问题和目标函数 (2)选择候选解作为初始种群，每个解作为个体用二进制串表示(个体相当于染色体，其中的元素相当于基因) (3)根据目标函数，对于每个个体计算适应函数值 (4)为每个个体指定一个与其适应值成正比的被选择概率(繁殖概率) (5)根据概率选择个体，所选个体通

9、过交叉/变异等操作产生新一代种群 (6)如果找到了解或者某种限制已到，则过程结束；否则转(3),20,遗传算法的特点,遗传算法也结合了“上山”趋势和随机搜索，并在并行搜索线程之间交换信息 遗传算法的主要优势来自于杂交 数学上可以证明，如果基因编码的位置在初始时就随机转换的话，杂交就没有优势 杂交的优势在于它能够将独立发展的若干个相对固定的字符(能够执行有用的功能“砖块”)组合起来，提高了搜索的粒度 所谓有用的砖块，就是几个结合起来可以构造问题的解参见书中的八皇后问题举例,21,遗传算法的模式,遗传算法上述特点可以用模式(schema)来解释模式是某些位置上的数字尚未确定的一个状态子串 能够匹配

10、模式的字符串称为该模式的实例 如果一个模式的实例的平均适应值超过均值，则种群内这个模式的实例数量会随时间而增长 遗传算法在模式和解的有意义成分相对应时才会工作得最好 遗传算法有很多应用，但是在什么情况下它会达到好效果，还有很多研究要做,遗传算法,通过把两个父状态结合来生成后继,8皇后的例子，其中每个状态用一个长度为8的字符串来表示，适应度函数取作 不相互攻击的皇后对数目。,前一页图中（c）1和2生成（d）1,与或图搜索 超图：由节点集和若干连接符组成的图。 K_连接符：从一个父节点指向一组K个后继节点的K条连线。,n1,n2,a,b,c,d,3_连接,1_连接,1_连接,n0,n1,n3,n6

11、,n7,n2,n5,n4,n8,超 图,问题：如何在超图中找出一个解图。,求解图的方法： （从节点n到目标节点集N的解图） 从节点n开始，正确选择一个外向连接符。 从该连接符指向的每个后继节点出发，继续选择一个外向连接符。 依次类推，直到由此产生的每个后继节点都是N中的一个元素为止。,n0,n3,n6,n7,n5,n4,n8,解图1,n1,n5,n0,n8,n7,解图2,上面是两个从节点n0到目标节点集N的解图，N= n7, n8 。,无环解图的递归定义： 一个与或图G中，从节点n到节点集N的解图记为G 如果节点n是N中一个元素，则G由单一元素组成。 如果节点n有一个指向节点集n1, n2 n

12、k的外向连接符K，使得从每个ni到N有一个解图（i =1,2k）,则G由节点n、连接符K及n1, n2 nk中的每个节点到N的解图组成。 否则从n 到N不存在解图。 解图的耗散值计算： 设K_连接符的耗散值为K，G的耗散值为K(n,N) 若n 是N的一个元素，则K(n,N)=0 若n有一个到解图中后继节点集n1, n2 ni的外向连接符，设该连接符的耗散值为Cn，则 K(n,N) Cn+ K(n1,N)+ K(n2,N)+ + K(ni,N),n0,n3,n6,n7,n5,n8,n1,n4,n5,n0,n8,n7,左图耗散值 K(n0,N) 1+ K(n1,N) 1+1+ K(n3,N) 1+

13、1+2+ K(n5,N)+ K(n6,N) 1+1+2+2+ K(n7,N)+ K(n8,N)+2+ K(n7,N)+ K(n8,N) 1+ 1+ 2+ 2+ 0+ 0+ 2+ 0+ 0 8,右图耗散值 K(n0,N) 2+ K(n4,N) + K(n5,N) 2+ 1+K(n5N) + 2+K(n7,N) +K(n8,N) 2+ 1+ 2+K(n7,N) +K(n8,N) + 2+K(n7,N) +K(n8,N) 2+ 1+ 2+ 0+ 0+ 2+ 0+ 0 7,能解节点定义： 终节点是能解节点。 如果非终节点有“或”子节点，当且仅当其子节点至少有一个能解，则该非终节点是能解节点。 如果非终

14、节点有“与”子节点，当且仅当其子节点都能解，则该非终节点是能解节点。 不能解节点定义： 没有后裔的非终节点是不能解节点（该节点是叶节点但不在N中）。 如果非终节点有“或”子节点，当且仅当所有子节点都不能解，则该非终节点是不能解节点。 如果非终节点有“与”子节点，至少有一个子节点不能解，则该非终节点是不能解节点。,AO*算法 建立一个搜索图G，仅包含初始节点s，s 的耗散值为q(s)=h(s)，如果s 是终 节点，则标记s 为SOLVED Until s已标记SOLVED do: begin 从s出发沿着有标记的连接符找出一个G的待扩充的局部解图G 任取G中一个非终节点n作为当前节点。 扩充节点

15、n ，生成n的全部子节点并将其加入到G中。对于未在G中出现 过的子节点nj ，计算其耗散值q(nj)=h(nj)；对于子节点中属于终节点者， 标记SOLVED并赋值为0 建立一个仅包含节点n的单一节点集S Until S为空 do： CONTINUE, begin 从S中移出这样节点m，该m节点的子节点不在S中 计算修改m耗散值 q(m) ：对指向节点集n1i, n2i nki的每个连接 符i，分别计算 qi(m)=Ci+q(n1i)+ q(n2i)+ + q(nKi) 令： q(m)= min qi(m) 即：取耗散值最小的连接符的耗散值作为q(m) 标记该具有最小耗散值的连接符，如果原来对

16、m的某个连接符所做 的标记与新标记的连接符不同，则保留新标记，去掉原来标记。 如果该连接符的所有后继节点都已标记SOLVED，则此m节点标记 SOLVED 如果m已标记SOLVED或者m修正后的耗散值与原来的耗散值不同，则 将m的所有父节点加入到S中，这些父节点必须通过有标记的连接符与 节点m相连 end end,例题： （预先给出了各节点h值的估计值，实际的h值在搜索中计算得出） h(n0)=0， h(n1)=2， h(n2)= h(n3)=4， h(n4)= h(n5)=1， h(n6)=2， h(n7)= h(n8)=0 N= n7, n8 循环1：,n0,n5,n4,n1,外循环：初始

17、状态 G=S，取当前节点n=n0，扩充节点 n0 ，得到n1, n5, n4 并加入G中，计算各节点耗散值得： h(n1)=2，h(n5)=1， h(n4)=1，组成单一节点集S=n0 内循环：取出节点n0， n0有2个外向连接符，分别计算：,h(n0)=C0+h(n1)=1+2=3 (1_连接符) h(n0)=C0+h(n5) +h(n4) =2+1+1=4 (2_连接符) 取 q(n0)= min 3, 4 = 3，标记选定的1_连接符 节点n1无标记 节点n0不能标记，内循环结束,标记,循环2：,n0,n5,n4,n1,外循环：沿标记取当前节点n=n1，扩充节点n1 ，得到 n2, n3

18、 并加入G中，计算耗散值得： h(n2)=4，h(n3)=4 组成单一节点集S=n1 内循环：取出节点n1， n1有2个外向连接符，分别计算： h(n1)=C1+h(n2)=1+4=5 (左1_连接符) h(n1)=C1+h(n3) =1+4=5 (右1_连接符), 取 q(n1)= min 5, 5 = 5，按照自然排序，标记选定的左1_连接符 节点n3无标记 节点n1不能标记 节点n1的h 值由原来的2修改为5， 将n1的父节点n0加入到单一节点集S中 重新计算h(n0) h(n0)=C0+h(n1)=1+5=6 (1_连接符) h(n0)=C0+h(n5) +h(n4) =2+1+1=4

19、 (2_连接符) 取 q(n0)= min 6, 4 = 4，取消原来n0 n1标记，重新标记2_连接符 节点n4, n5无标记 节点n0不能标记，内循环结束,n2,n3,循环3：,n0,n5,n4,n1,外循环：沿标记取当前节点n=n5，扩充节点n5 ，得到 n6, n7 , n8 并加入G中，计算耗散值得： h(n6)=2，h(n7)=0 ，h(n8)=0 组成单一节点集S=n5 n7, n8是终节点， 标记节点n7, n8 内循环：取出节点n5， n5有2个外向连接符，分别计算： h(n5)=C5+h(n6)=1+2=3 (1_连接符) h(n5)=C5+h(n7) +h(n8) =2+

20、0 +0 =2 (2_连接符), 取 q(n5)= min 3, 2 = 2，记选定的2_连接符 节点n7, n8有标记 标记节点n5 并将n5 的父节点n0 加入到S中 内循环：取n0， 计算 h(n0)=C0+h(n1)=1+5=6 (1_连接符) h(n0)=C0+h(n5) +h(n4) =2+2+1=5 (2_连接符) 取 q(n0)= min 6, 5 = 5，原来连接不变 节点n5有标记但是n4无标记 节点n0不能标记，内循环结束,n2,n3,n6,n7,n8,循环4：,n0,n5,n4,n1,外循环：沿标记取当前节点n=n54扩充节点n4 ，得 n5, n8 ，计算耗散值得： h(n5)=2，h(n8)=0 组成单一节点集S=n4 内循环：取节点n4， n4有2个外向连接符