哈工大人工智能课件chpt2-2

人工智能原理第2章搜索技术（下）本章内容2.1搜索与问题求解2.2无信息搜索策略2.3启发式搜索策略2.4局部搜索算法2.5约束满足问题2.6博弈搜索参考书目附录A*算法可采纳性的证明第2章搜索技术2.4局部搜索算法2.4.1局部搜索与最优化2.4.2爬山法搜索2.4.3模拟退火搜索2.4.4局部剪枝搜索2.4.5遗传算法第2章搜索技术4局部搜索算法•前面的搜索算法都是保留搜索路径的，到达目标的路径就是问题的解—然而许多问题中到达目标的路径是无关紧要的•与系统地搜索状态空间(保留各种路径)相对，不关心路径的搜索算法就是局部搜索算法•局部搜索从一个单独的当前状态出发，通常只移动到相邻状态•典型情况下搜索的路径不保留第2章搜索技术5局部搜索算法的应用•集成电路设计•工厂场地布局•车间作业调度•自动程序设计•电信网络优化•车辆寻径•文件夹管理第2章搜索技术62.4.1局部搜索与最优化问题•局部搜索算法的优点：•只使用很少的内存(通常是一个常数)•经常能在不适合系统化算法的很大或无限的状态空间中找到合理的解•除了找到目标之外，局部搜索算法也适用于最优化问题•最优化问题—根据一个目标函数找到最佳状态/只有目标函数，而不考虑(没有)“目标测试”和“路径耗散”第2章搜索技术7状态空间地形图(1)第2章搜索技术山肩目标函数全局最大值局部最大值“平坦”局部最大值状态空间当前状态8状态空间地形图(2)•在状态图中，既有“位置”(用状态表示)又有“高度”(用耗散值或目标函数值表示)•如果高度对应于耗散值，则目标是找到全局最小值，即图中最低点•如果高度对应于目标函数，则目标是找到全局最大值，即图中最高峰•如果存在解，则完备的局部搜索算法能够找到解•而最优的局部搜索算法能够找到全局最大或最小值第2章搜索技术9局部搜索算法•本节简要介绍以下4种局部搜索算法/介绍其算法思想•爬山法搜索•模拟退火搜索•局部剪枝搜索•遗传算法•从搜索的角度看遗传算法也是搜索假设空间的一种方法(学习问题归结为搜索问题)—生成后继假设的方式第2章搜索技术102.4.2爬山法搜索•爬山法(hill-climbing)—就是向值增加的方向持续移动—登高过程/如果相邻状态中没有比它更高的值，则算法结束于顶峰•爬山法搜索算法思想：(1)令初始状态S0为当前状态(2)若当前状态已经达标，则算法运行结束，搜索成功(3)若存在一个动作可以作用于当前状态以产生一个新状态，使新状态的估计值优于当前状态和其他所有候选状态的估计值，则放弃当前状态，并令刚产生的新状态为当前状态，转(2)(4)取当前状态为相对最优解，停止执行算法第2章搜索技术11爬山法搜索算法functionHILL-CLIMBING(problem)returnastatethatisalocalmaximuminputs:problemlocalvariables:current(anode)/neighbor(anode)current←MAKE-NODE(Initial-State[problem])loopdoneighbor←ahighest-valuedsuccessorofcurrentIfValue[neighbor]=Value[current]thenreturnState[current]current←neighbor第2章搜索技术12爬山法搜索的局限•爬山法是一种局部贪婪搜索，不是最优解算法(或是不完备的)，优点在于能很快朝着解的方向进展。•缺点在于：•局部极大值—比其邻居状态都高的顶峰，但是小于全局最大值(参照状态空间地形图)•山脊—一系列的局部极大值•高原—评价函数平坦的一块区域(或者山肩)第2章搜索技术13爬山法搜索的变形•爬山法的变形•随机爬山法—按某种概率选择下一步•首选爬山法—随机选择直到有优于当前节点的下一步•随机重新开始爬山法—大不了从头再来•随机生成初始状态，进行一系列爬山法搜索—这时算法是完备的概率接近1第2章搜索技术142.4.3模拟退火搜索•将爬山法(停留在局部山峰)和随机行走以某种方式结合，以同时获得完备性和效率•模拟退火的思想•想象在不平的表面上如何使一个乒乓球掉到最深的裂缝中—如果只让其在表面滚动，则它只会停留在局部极小点•如果晃动平面，可以使乒乓球弹出局部极小点•技巧是晃动足够大使乒乓球弹出局部极小点，但又不能太大把它从全局极小点中赶出第2章搜索技术15模拟退火的解决思路(1)•思路—开始使劲晃动(先高温加热)然后慢慢降低摇晃的强度(逐渐降温)[退火过程]•算法的核心—移动选择•选择随机移动，如果评价值改善，则移动被接受，否则以某个小于1的概率接受•概率按照移动评价值变坏的梯度ΔE而呈指数级下降/同时也会随着作为控制的参数—“温度”T的降低(数值减小)而降低•接受概率=eΔE/T(注意此时ΔE0)第5章搜索技术16模拟退火的解决思路(2)•温度T是时间的函数，按照模拟退火的思想，数值应该逐渐减小(降温)•因为接受概率=eΔE/T且ΔE0，所以当温度高时，接受概率较大(接近1)/而T越来越低时，ΔE/T变大，因而接受概率降低•可以证明，如果T下降得足够慢，则算法找到全局最优解的概率接近1第5章搜索技术17模拟退火搜索算法functionSimulated-Annealing(problem,schedule)returnasolutionstateinputs:problem/schedule(amappingfromtimetotemperaturelocalvariables:current(anode)/next(anode)/T(a“temperature”controllingtheprobabilityofdownwardstepscurrent←MAKE-NODE(Initial-State[problem])fort←1to∞doT←schedule[t]IfT=0thenreturncurrentnext←arandomlyselectedsuccessorofcurrent∆E←Value[next]–Value[current]if∆E0thencurrent←nextelsecurrent←nextonlywithprobabilitye∆E/T第2章搜索技术182.4.4局部剪枝搜索•基本思想—与只从一个单独的起始状态出发不同，局部剪枝搜索从k个随机生成的状态开始，每步生成全部k个状态的所有后继状态/如果其中之一是目标状态，算法停止；否则从全部后继状态中选择最佳的k个状态继续搜索•在局部剪枝搜索过程中，有用的信息在k个并行的搜索线程之间传递—算法会很快放弃没有成果的搜索而把资源放在取得最大进展的搜索上第2章搜索技术19随机剪枝搜索•如果k个状态缺乏多样性，则局部剪枝搜索会受其影响，性能变差•算法的变种—随机剪枝搜索帮助缓解这一问题—随机剪枝搜索不是选择最好的k个后代，而是按照一定概率随机地选择k个后继状态/选择给定后继状态的概率是状态值的递增函数•类似于自然选择过程—状态对应生物体，其值对应于适应性，后代就是后继状态第2章搜索技术202.4.5遗传算法•遗传算法(genericalgorithm/GA)是随机剪枝的变种—不是通过修改单一状态而是通过把两个父状态结合以生成后继状态•与剪枝搜索一样，遗传算法也是从k个随机状态开始—这k个状态称为种群，每个状态称为个体•个体用有限长的字符串(通常为0/1串)表示•每个状态用其评价函数(适应度函数)给出评价值(适应值)•随后的操作包括—选择/杂交/变异第2章搜索技术21遗传算法的操作•选择(或者称繁殖)—按照一定概率随机地选择两对个体进行繁殖(即生成后继状态)•杂交(或者称交叉)—杂交点是在表示状态的字符串中随机选择的一个位置，以此形成新状态—后代是父串在杂交点上进行杂交(各取一部分)得来的•变异—在新生成的串中各个位置都会按照一个独立的小概率随机变异第2章搜索技术22遗传算法简要描述(1)定义问题和目标函数(2)选择候选解作为初始种群，每个解作为个体用二进制串表示(个体相当于染色体，其中的元素相当于基因)(3)根据目标函数，对于每个个体计算适应函数值(4)为每个个体指定一个与其适应值成正比的被选择概率(繁殖概率)(5)根据概率选择个体，所选个体通过交叉/变异等操作产生新一代种群(6)如果找到了解或者某种限制已到，则过程结束；否则转(3)第2章搜索技术遗传算法FunctionGenetic-Algorithm(population,Fitness-FN)returnanindividualInputs:populations/Fitness-FNRepeatnew_population←emptysetloopforifrom1toSize(population)dox←Random-Selection(population,Fitness-FN)y←Random-Selection(population,Fitness-FN)child←Reproduce(x,y)if(smallrandomprobability)thenchild←Mutate(child)addchildtonew_populationPopulation←new_populationUntilsomeindividualisfitenough,orenoughtimeelapsedReturnthebestindividualinpopulationaccordingtoFitness-FN第2章搜索技术遗传算法FunctionReproduce(x,y)returnanindividualInputs:x,y(parentindividuals)n←Length(x)c←randomnumberfrom1tonreturnAppend(Substring(x,1,c),Substring(y,c+1,n))第2章搜索技术25遗传算法的特点•遗传算法也结合了“上山”趋势和随机搜索，并在并行搜索线程之间交换信息•遗传算法的主要优势来自于杂交•杂交的优势在于它能够将独立发展的若干个相对固定的字符(能够执行有用的功能—“砖块”)组合起来，提高了搜索的粒度•所谓有用的砖块，就是几个结合起来可以构造问题的解•参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定等5个要素组成了遗传算法的核心内容。第2章搜索技术26遗传算法的模式•遗传算法上述特点可以用模式(schema)来解释—模式是某些位置上的数字尚未确定的一个状态子串•能够匹配模式的字符串称为该模式的实例•如果一个模式的实例的平均适应值超过均值，则种群内这个模式的实例数量会随时间而增长•遗传算法在模式和解的有意义成分相对应时才会工作得最好•遗传算法有很多应用，但是在什么情况下它会达到好效果，还有很多研究要做第2章搜索技术2.5约束满足问题2.5.1约束满足问题的定义2.5.2CSP的回溯搜索2.5.3变量赋值次序的启发式2.5.4变量约束的启发式2.5.5关于失败变量的启发式第2章搜索技术282.5.1约束满足问题的定义•约束满足问题(ConstraintSatisfyingProblem,CSP)由一个变量集合{X1~Xn}和一个约束集合{C1~Cm}定义•每个变量都有一个非空可能值域Di•每个约束指定了包含若干变量的一个子集内各变量的赋值范围•CSP的一个状态—对一些或全部变量的赋值{Xi=vi,Xj=vj,…}第2章搜索技术29CSP问题的解•一个不违反任何约束的对变量的赋值称为相容赋值或合法赋值•对每个变量都进行赋值称为完全赋值•一个(一组)既是相容赋值又是完全赋值的对变量的赋值就是CSP问题的解•CSP问题常常可以可视化，表示为约束图，更直观地显示问题，帮助思考问题的答案第2章搜索技术30从搜索角度看待CSP问题•CSP看作搜索问题的形式化•初始状态—空赋值集合，所有变量都是未赋值的•后继函数—给未赋值的变量一个赋值，要求该赋值与先前的变量