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

《人工智能原理第二章搜索技术.pptx》由会员分享，可在线阅读，更多相关《人工智能原理第二章搜索技术.pptx（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、人工智能原理人工智能原理第第2 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、)相对，不关心路径的搜索算法就是局部搜索算法局部搜索从一个单独的当前状态出发，通常只移动到相邻状态典型情况下搜索的路径不保留第2章 搜索技术4培训专用局部搜索算法的应用局部搜索算法的应用应用领域集成电路设计工厂场地布局车间作业调度(Job Shop Schedule)自动程序设计电信网络优化车辆寻径文件夹管理局部搜索也称为优化算法wiki中表示为local search(optimization)第2章 搜索技术5培训专用2.4.1 2.4.1 局部搜索与最优化问题局部搜索与最优化问题局部搜索算法的优点：只使用很少的内存(通常是一个常数)经常能在不适合系统化算法的很大或无限的状态空间中找到合理

3、的解最优化问题根据一个目标函数找到最佳状态/只有目标函数，而不考虑(没有)“目标测试”和“路径耗散”局部搜索算法适用于最优化问题第2章 搜索技术6培训专用状态空间地形图状态空间地形图(1)(1)第2章 搜索技术山肩目标函数全 局 最 大值局 部 最 大值“平坦”局部最大值状态空间当前状态7培训专用状态空间地形图状态空间地形图(2)(2)在状态图中，既有“位置”(用状态表示)又有“高度”(用耗散值或目标函数值表示)如果高度对应于耗散值，则目标是找到全局最小值，即图中最低点如果高度对应于目标函数，则目标是找到全局最大值，即图中最高峰如果存在解，则完备的局部搜索算法能够找到解而最优的局部搜索算法能够

4、找到全局最大或最小值第2章 搜索技术8培训专用局部搜索算法局部搜索算法本节简要介绍以下4种局部搜索算法/介绍其算法思想爬山法搜索模拟退火搜索局部剪枝搜索遗传算法从搜索的角度看遗传算法也是搜索假设空间的一种方法(学习问题归结为搜索问题)生成后继假设的方式第2章 搜索技术9培训专用2.4.2 2.4.2 爬山法搜索爬山法搜索爬山法(hill-climbing)就是向值增加的方向持续移动登高过程/如果相邻状态中没有比它更高的值，则算法结束于顶峰爬山法搜索算法思想：(1)令初始状态S0为当前状态(2)若当前状态已经达标，则算法运行结束，搜索成功(3)若存在一个动作可以作用于当前状态以产生一个新状态，使

5、新状态的估计值优于当前状态的估计值，则放弃当前状态，并令刚产生的新状态为当前状态，转(2)(4)取当前状态为相对最优解，停止执行算法第2章 搜索技术10培训专用爬山法搜索的局限爬山法搜索的局限爬山法是一种局部贪婪搜索，不是最优解算法(或是不完备的)/其问题是：局部极大值比其邻居状态都高的顶峰，但是小于全局最大值(参照状态空间地形图)山脊一系列的局部极大值高原评价函数平坦的一块区域(或者山肩)第2章 搜索技术11培训专用爬山法搜索的变形爬山法搜索的变形爬山法的变形随机爬山法随机选择下一步首选爬山法随机选择直到有优于当前节点的下一步随机重新开始爬山法随机生成初始状态，进行一系列爬山法搜索这时算法是

6、完备的概率接近1第2章 搜索技术12培训专用2.4.3 2.4.3 模拟退火搜索模拟退火搜索将爬山法(停留在局部山峰)和随机行走以某种方式结合，以同时获得完备性和效率模拟退火的思想想象在不平的表面上如何使一个乒乓球掉到最深的裂缝中如果只让其在表面滚动，则它只会停留在局部极小点/如果晃动平面，可以使乒乓球弹出局部极小点/技巧是晃动足够大使乒乓球弹出局部极小点，但又不能太大把它从全局极小点中赶出第2章 搜索技术13培训专用模拟退火的解决思路模拟退火的解决思路(1)(1)思路开始使劲晃动(先高温加热)然后慢慢降低摇晃的强度(逐渐降温)退火过程算法的核心移动选择选择随机移动，如果评价值改善，则移动被接

7、受，否则以某个小于1的概率接受概率按照移动评价值变坏的梯度E而呈指数级下降/同时也会随着作为控制的参数“温度”T的降低(数值减小)而降低接受概率=eE/T(注意此时E 0)第5章 搜索技术14培训专用模拟退火的解决思路模拟退火的解决思路(2)(2)温度T是时间的函数，按照模拟退火的思想，数值应该逐渐减小(降温)因为接受概率=eE/T且E f*(S0)由引理2可知，在A*算法结束前，必有最佳路径上的一个节点n在Open表中且有f(n)f*(S0)f(Sg)这时，A*算法一定会选择n来扩展，而不可能选择Sg，从而也不会去测试目标节点Sg，这就与假设A*算法终止在目标节点相矛盾/因此，A*算法只能终

8、止在最佳路径上第2章 搜索技术85培训专用推论推论2推论2在A*算法中，对任何被扩展的任一节点n，都有f(n)f*(S0)证明：令n是由A*选作扩展的任一节点，因此n不会是目标节点，且搜索没有结束/由引理2可知，在Open表中有满足f(n)f*(S0)的节点n若n=n,则有f(n)f*(S0)否则，算法既然选择n扩展，那就必有f(n)f(n)所以有f(n)f*(S0)第2章 搜索技术86培训专用演讲完毕，谢谢观看！培训专用内容总结人工智能原理第2章 搜索技术（下）。人工智能原理第2章 搜索技术（下）。与系统地搜索状态空间(保留各种路径)相对，不关心路径的搜索算法就是局部搜索算法。局部搜索从一个

9、单独的当前状态出发，通常只移动到相邻状态。如果存在解，则完备的局部搜索算法能够找到解。局部极大值比其邻居状态都高的顶峰，但是小于全局最大值(参照状态空间地形图)。随机爬山法随机选择下一步。将爬山法(停留在局部山峰)和随机行走以某种方式结合，以同时获得完备性和效率。接受概率=eE/T(注意此时E 0)。否则从全部后继状态中选择最佳的k个状态继续搜索。(3)根据目标函数，对于每个个体计算适应函数值。(5)根据概率选择个体，所选个体通过交叉/变异等操作产生新一代种群。遗传算法也结合了“上山”趋势和随机搜索，并在并行搜索线程之间交换信息。路径耗散每步耗散均为常数(1)。例1：澳大利亚地图染色问题(1)。例2：密码算术问题(2)。把问题分解为独立的子问题。如果要找出问题的所有解，则排序问题无所谓。不断检验变量之间的约束并将其作用于更大范围，故称为约束传播。由此可跳至回跳点变量NSW，重新赋值后可不产生冲突。-,+。引理1的证明(1)培训专用