人工智能原理第二章搜索技术

人工智能原理,第,2,章 搜索技术（下）,1,培训专用,本章内容,2.1,搜索与问题求解,2.2,无信息搜索策略,2.3,启发式搜索策略,2.4,局部搜索算法,2.5,约束满足问题,2.6,博弈搜索,参考书目附录,A*,算法可采纳性的证明,第,2,章 搜索技术,2,培训专用,2.4,局部搜索算法,2.4.1,局部搜索与最优化,2.4.2,爬山法搜索,2.4.3,模拟退火搜索,2.4.4,局部剪枝搜索,2.4.5,遗传算法,第,2,章 搜索技术,3,培训专用,局部搜索算法,前面的搜索算法都是保留搜索路径的，到达目标的路径就是问题的解,然而许多问题中到达目标的路径是无关紧要的,与系统地搜索状态空间,(,保留各种路径,),相对，不关心路径的搜索算法就是局部搜索算法,局部搜索从一个单独的当前状态出发，通常只移动到相邻状态,典型情况下搜索的路径不保留,第,2,章 搜索技术,4,培训专用,局部搜索算法的应用,应用领域,集成电路设计,工厂场地布局,车间作业调度,(Job Shop Schedule),自动程序设计,电信网络优化,车辆寻径,文件夹管理,局部搜索也称为优化算法,wiki,中表示为,local search (optimization),第,2,章 搜索技术,5,培训专用,2.4.1,局部搜索与最优化问题,局部搜索算法的优点：,只使用很少的内存,(,通常是一个常数,),经常能在不适合系统化算法的很大或无限的状态空间中找到合理的解,最优化问题,根据一个目标函数找到最佳状态,/,只有目标函数，而不考虑,(,没有,),“目标测试,”,和“路径耗散”,局部搜索算法适用于最优化问题,第,2,章 搜索技术,6,培训专用,状态空间地形图,(1),第,2,章 搜索技术,山肩,目标函数,全局最大值,局部最大值,“平坦”局部最大值,状态空间,当前状态,7,培训专用,状态空间地形图,(2),在状态图中，既有“位置”,(,用状态表示,),又有“高度,”(,用耗散值或目标函数值表示,),如果高度对应于耗散值，则目标是找到全局最小值，即图中最低点,如果高度对应于目标函数，则目标是找到全局最大值，即图中最高峰,如果存在解，则完备的局部搜索算法能够找到解,而最优的局部搜索算法能够找到全局最大或最小值,第,2,章 搜索技术,8,培训专用,局部搜索算法,本节简要介绍以下,4,种局部搜索算法,/,介绍其算法思想,爬山法搜索,模拟退火搜索,局部剪枝搜索,遗传算法,从搜索的角度看遗传算法也是搜索假设空间的一种方法,(,学习问题归结为搜索问题,),生成后继假设的方式,第,2,章 搜索技术,9,培训专用,2.4.2,爬山法搜索,爬山法,(hill-climbing),就是向值增加的方向持续移动,登高过程,/,如果相邻状态中没有比它更高的值，则算法结束于顶峰,爬山法搜索算法思想：,(1),令初始状态,S,0,为当前状态,(2),若当前状态已经达标，则算法运行结束，搜索成功,(3),若存在一个动作可以作用于当前状态以产生一个新状态，使新状态的估计值优于当前状态的估计值，则放弃当前状态，并令刚产生的新状态为当前状态，转,(2),(4),取当前状态为相对最优解，停止执行算法,第,2,章 搜索技术,10,培训专用,爬山法搜索的局限,爬山法是一种局部贪婪搜索，不是最优解算法,(,或是不完备的,) /,其问题是：,局部极大值,比其邻居状态都高的顶峰，但是小于全局最大值,(,参照状态空间地形图,),山脊,一系列的局部极大值,高原,评价函数平坦的一块区域,(,或者山肩,),第,2,章 搜索技术,11,培训专用,爬山法搜索的变形,爬山法的变形,随机爬山法,随机选择下一步,首选爬山法,随机选择直到有优于当前节点的下一步,随机重新开始爬山法,随机生成初始状态，进行一系列爬山法搜索,这时算法是完备的概率接近,1,第,2,章 搜索技术,12,培训专用,2.4.3,模拟退火搜索,将爬山法,(,停留在局部山峰,),和随机行走以某种方式结合，以同时获得完备性和效率,模拟退火的思想,想象在不平的表面上如何使一个乒乓球掉到最深的裂缝中,如果只让其在表面滚动，则它只会停留在局部极小点,/,如果晃动平面，可以使乒乓球弹出局部极小点,/,技巧是晃动足够大使乒乓球弹出局部极小点，但又不能太大把它从全局极小点中赶出,第,2,章 搜索技术,13,培训专用,模拟退火的解决思路,(1),思路,开始使劲晃动,(,先高温加热,),然后慢慢降低摇晃的强度,(,逐渐降温,),退火过程,算法的核心,移动选择,选择随机移动，如果评价值改善，则移动被接受，否则以某个小于,1,的概率接受,概率按照移动评价值变坏的梯度,E,而呈指数级下降,/,同时也会随着作为控制的参数,“温度,”T,的降低,(,数值减小,),而降低,接受概率,=e,E,/T,(,注意此时,E,0),第,5,章 搜索技术,14,培训专用,模拟退火的解决思路,(2),温度,T,是时间的函数，按照模拟退火的思想，数值应该逐渐减小,(,降温,),因为,接受概率,=e,E,/T,且,E,f*(S,0,),由引理,2,可知，在,A*,算法结束前，必有最佳路径上的一个节点,n,在,Open,表中且有,f(n),f*(S,0,)f(Sg),这时，,A*,算法一定会选择,n,来扩展，而不可能选择,Sg,，从而也不会去测试目标节点,Sg,，这就与假设,A*,算法终止在目标节点相矛盾,/,因此，,A*,算法只能终止在最佳路径上,第,2,章 搜索技术,85,培训专用,推论,2,推论,2,在,A*,算法中，对任何被扩展的任一节点,n,，都有,f(n),f*(S,0,),证明：,令,n,是由,A*,选作扩展的任一节点，因此,n,不会是目标节点，且搜索没有结束,/,由引理,2,可知，在,Open,表中有满足,f(n)f*(S,0,),的节点,n,若,n=n,则有,f(n)f*(S,0,),否则，,算法既然选择,n,扩展，那就必有,f(n)f(n),所以有,f(n)f*(S,0,),第,2,章 搜索技术,86,培训专用,演讲完毕，谢谢观看！,培训专用,内容总结,人工智能原理第2章 搜索技术（下）。人工智能原理第2章 搜索技术（下）。与系统地搜索状态空间(保留各种路径)相对，不关心路径的搜索算法就是局部搜索算法。局部搜索从一个单独的当前状态出发，通常只移动到相邻状态。如果存在解，则完备的局部搜索算法能够找到解。局部极大值比其邻居状态都高的顶峰，但是小于全局最大值(参照状态空间地形图)。随机爬山法随机选择下一步。将爬山法(停留在局部山峰)和随机行走以某种方式结合，以同时获得完备性和效率。接受概率=eE/T(注意此时E 0)。否则从全部后继状态中选择最佳的k个状态继续搜索。(3)根据目标函数，对于每个个体计算适应函数值。(5)根据概率选择个体，所选个体通过交叉/变异等操作产生新一代种群。遗传算法也结合了“上山”趋势和随机搜索，并在并行搜索线程之间交换信息。路径耗散每步耗散均为常数(1)。例1：澳大利亚地图染色问题(1)。例2：密码算术问题(2)。把问题分解为独立的子问题。如果要找出问题的所有解，则排序问题无所谓。不断检验变量之间的约束并将其作用于更大范围，故称为约束传播。由此可跳至回跳点变量NSW，重新赋值后可不产生冲突。-, +。引理1的证明(1),培训专用,