人工智能原理2章搜索技术下.ppt
《人工智能原理2章搜索技术下.ppt》由会员分享,可在线阅读,更多相关《人工智能原理2章搜索技术下.ppt(83页珍藏版)》请在三一文库上搜索。
1、人工智能原理 第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、搜索算法 局部搜索从一个单独的当前状态出发,通常只移动到相邻状态 典型情况下搜索的路径不保留,第2章 搜索技术,5,局部搜索算法的应用,集成电路设计 工厂场地布局 车间作业调度 自动程序设计 电信网络优化 车辆寻径 文件夹管理,第2章 搜索技术,6,2.4.1 局部搜索与最优化问题,局部搜索算法的优点: 只使用很少的内存(通常是一个常数) 经常能在不适合系统化算法的很大或无限的状态空间中找到合理的解 最优化问题根据一个目标函数找到最佳状态 / 只有目标函数,而不考虑(没有)“目标测试”和“路径耗散” 局部搜索算法适用于最优化问题,第2章 搜索技术,7,状态空间地形图(1),第2章 搜索技术,8
3、,状态空间地形图(2),在状态图中,既有“位置”(用状态表示)又有“高度”(用耗散值或目标函数值表示) 如果高度对应于耗散值,则目标是找到全局最小值,即图中最低点 如果高度对应于目标函数,则目标是找到全局最大值,即图中最高峰 如果存在解,则完备的局部搜索算法能够找到解 而最优的局部搜索算法能够找到全局最大或最小值,第2章 搜索技术,9,局部搜索算法,本节简要介绍以下4种局部搜索算法 / 介绍其算法思想 爬山法搜索 模拟退火搜索 局部剪枝搜索 遗传算法 从搜索的角度看遗传算法也是搜索假设空间的一种方法(学习问题归结为搜索问题)生成后继假设的方式,第2章 搜索技术,10,2.4.2 爬山法搜索,爬
4、山法(hill-climbing)就是向值增加的方向持续移动登高过程 / 如果相邻状态中没有比它更高的值,则算法结束于顶峰 爬山法搜索算法思想: (1)令初始状态S0为当前状态 (2)若当前状态已经达标,则算法运行结束,搜索成功 (3)若存在一个动作可以作用于当前状态以产生一个新状态,使新状态的估计值优于当前状态的估计值,则放弃当前状态,并令刚产生的新状态为当前状态,转(2) (4)取当前状态为相对最优解,停止执行算法,第2章 搜索技术,11,爬山法搜索的局限,爬山法是一种局部贪婪搜索,不是最优解算法(或是不完备的) / 其问题是: 局部极大值比其邻居状态都高的顶峰,但是小于全局最大值(参照状
5、态空间地形图) 山脊一系列的局部极大值 高原评价函数平坦的一块区域(或者山肩),第2章 搜索技术,12,爬山法搜索的变形,爬山法的变形 随机爬山法随机选择下一步 首选爬山法随机选择直到有优于当前节点的下一步 随机重新开始爬山法随机生成初始状态,进行一系列爬山法搜索这时算法是完备的概率接近1,第2章 搜索技术,13,2.4.3 模拟退火搜索,将爬山法(停留在局部山峰)和随机行走以某种方式结合,以同时获得完备性和效率 模拟退火的思想 想象在不平的表面上如何使一个乒乓球掉到最深的裂缝中如果只让其在表面滚动,则它只会停留在局部极小点 / 如果晃动平面,可以使乒乓球弹出局部极小点 / 技巧是晃动足够大使
6、乒乓球弹出局部极小点,但又不能太大把它从全局极小点中赶出,第2章 搜索技术,14,模拟退火的解决思路(1),思路开始使劲晃动(先高温加热)然后慢慢降低摇晃的强度(逐渐降温)退火过程 算法的核心移动选择 选择随机移动,如果评价值改善,则移动被接受,否则以某个小于1的概率接受 概率按照移动评价值变坏的梯度E而呈指数级下降 / 同时也会随着作为控制的参数“温度”T的降低(数值减小)而降低 接受概率=eE/T(注意此时E 0),第5章 搜索技术,15,模拟退火的解决思路(2),温度T是时间的函数,按照模拟退火的思想,数值应该逐渐减小(降温) 因为接受概率=eE/T且E 0,所以当温度高时,接受概率较大
7、(接近1) / 而T越来越低时,E/T变大,因而接受概率降低 可以证明,如果T下降得足够慢,则算法找到全局最优解的概率接近1,第5章 搜索技术,16,2.4.4 局部剪枝搜索,基本思想与只从一个单独的起始状态出发不同,局部剪枝搜索从k个随机生成的状态开始,每步生成全部k个状态的所有后继状态 / 如果其中之一是目标状态,算法停止;否则从全部后继状态中选择最佳的k个状态继续搜索 在局部剪枝搜索过程中,有用的信息在k个并行的搜索线程之间传递算法会很快放弃没有成果的搜索而把资源放在取得最大进展的搜索上,第2章 搜索技术,17,随机剪枝搜索,如果k个状态缺乏多样性,则局部剪枝搜索会受其影响,性能变差 算
8、法的变种随机剪枝搜索帮助缓解这一问题随机剪枝搜索不是选择最好的k个后代,而是按照一定概率随机地选择k个后继状态 / 选择给定后继状态的概率是状态值的递增函数 类似于自然选择过程状态对应生物体,其值对应于适应性,后代就是后继状态,第2章 搜索技术,18,2.4.5 遗传算法,遗传算法(generic algorithm/GA)是随机剪枝的变种不是通过修改单一状态而是通过把两个父状态结合以生成后继状态 与剪枝搜索一样,遗传算法也是从k个随机状态开始这k个状态称为种群,每个状态称为个体 个体用有限长的字符串(通常为0/1串)表示 每个状态用其评价函数(适应度函数)给出评价值(适应值) 随后的操作包括
9、选择/杂交/变异,第2章 搜索技术,19,遗传算法的操作,选择(或者称繁殖)按照一定概率随机地选择两对个体进行繁殖(即生成后继状态) 杂交(或者称交叉)杂交点是在表示状态的字符串中随机选择的一个位置,以此形成新状态后代是父串在杂交点上进行杂交(各取一部分)得来的 变异在新生成的串中各个位置都会按照一个独立的小概率随机变异,第2章 搜索技术,20,遗传算法简要描述,(1)定义问题和目标函数 (2)选择候选解作为初始种群,每个解作为个体用二进制串表示(个体相当于染色体,其中的元素相当于基因) (3)根据目标函数,对于每个个体计算适应函数值 (4)为每个个体指定一个与其适应值成正比的被选择概率(繁殖
10、概率) (5)根据概率选择个体,所选个体通过交叉/变异等操作产生新一代种群 (6)如果找到了解或者某种限制已到,则过程结束;否则转(3),第2章 搜索技术,21,遗传算法的特点,遗传算法也结合了“上山”趋势和随机搜索,并在并行搜索线程之间交换信息 遗传算法的主要优势来自于杂交 数学上可以证明,如果基因编码的位置在初始时就随机转换的话,杂交就没有优势 杂交的优势在于它能够将独立发展的若干个相对固定的字符(能够执行有用的功能“砖块”)组合起来,提高了搜索的粒度 所谓有用的砖块,就是几个结合起来可以构造问题的解参见书中的八皇后问题举例,第2章 搜索技术,22,遗传算法的模式,遗传算法上述特点可以用模
11、式(schema)来解释模式是某些位置上的数字尚未确定的一个状态子串 能够匹配模式的字符串称为该模式的实例 如果一个模式的实例的平均适应值超过均值,则种群内这个模式的实例数量会随时间而增长 遗传算法在模式和解的有意义成分相对应时才会工作得最好 遗传算法有很多应用,但是在什么情况下它会达到好效果,还有很多研究要做,第2章 搜索技术,2.5 约束满足问题 2.5.1 约束满足问题的定义 2.5.2 CSP的回溯搜索 2.5.3 变量赋值次序的启发式 2.5.4 变量约束的启发式 2.5.5 关于失败变量的启发式,第2章 搜索技术,24,2.5.1 约束满足问题的定义,约束满足问题(Constrai
12、nt Satisfying Problem, CSP)由一个变量集合X1Xn和一个约束集合C1Cm定义 每个变量都有一个非空可能值域Di 每个约束指定了包含若干变量的一个子集内各变量的赋值范围 CSP的一个状态对一些或全部变量的赋值 Xi=vi, Xj=vj, ,第2章 搜索技术,25,CSP问题的解,一个不违反任何约束的对变量的赋值称为相容赋值或合法赋值 对每个变量都进行赋值称为完全赋值 一个(一组)既是相容赋值又是完全赋值的对变量的赋值就是CSP问题的解 CSP问题常常可以可视化,表示为约束图,更直观地显示问题,帮助思考问题的答案,第2章 搜索技术,26,从搜索角度看待CSP问题,CSP看
13、作搜索问题的形式化 初始状态空赋值集合,所有变量都是未赋值的 后继函数给未赋值的变量一个赋值,要求该赋值与先前的变量赋值不冲突 目标测试测试当前的赋值(组)是否是完全赋值 路径耗散每步耗散均为常数(1) 每个解必须为完全赋值 / 如果有n个变量,则解出现的深度为n(有限) / 常使用深度优先搜索,第2章 搜索技术,27,例1:澳大利亚地图染色问题(1),澳大利亚地图:用红绿蓝3色标出各省,相邻者颜色不同,第2章 搜索技术,28,对应于澳大利亚地图的约束图,相互关联的节点用边连接,第5章 搜索技术,例1:澳大利亚地图染色问题(2),WA,NT,SA,NSW,Q,V,T,西澳大利亚 WA 北领地
14、NT 南澳大利亚 SA 昆士兰 Q 新南威尔士 NSW 维多利亚 V 塔斯马尼亚 T 一组满足约束的完全赋值 WA=R, NT=G, Q=R, SA=B, NSW=G, V=R, T=R,29,例2:密码算术问题(1),算式 T W O + T W O F O U R 直观地求解此问题: F=1 如不考虑O/U有进位,则R/U/O为偶数 R=4,6,8 O=2?,3?,4! R=8/O=4则T=7(由O/R/U/W共同限制) T=7则U=6/W=3 由此得到一组解1468 | 734 考虑U有进位:R=0,2,4,6,8 O=5, R=0/O=5(有进位)/T=7/W=6/U=3 解=1530
15、 | 765,第2章 搜索技术,30,各算式约束,四列算式约束 O+O=R+10*X1 X1+W+W=U+10*X2 X2+T+T=O+10*X3 X3=F 对应的约束超图如右 六个变量互不相等约束可化为两两不等约束二元约束,第2章 搜索技术,例2:密码算术问题(2),F,T,W,U,O,R,X3,X1,X2,约束:互不相等,两两不等,31,CSP问题的分类,变量离散值域 有限值域如地图染色问题 无限值域如作业规划,要使用约束语言(线性约束/非线性约束) 变量连续值域 如哈勃望远镜实验日程安排 / 线性规划问题 约束的类型 一元约束只限制一个变量的取值 二元约束与2个变量相关 高阶约束涉及3个
16、或更多变量,第2章 搜索技术,32,CSP问题求解的复杂度,搜索相容的完全赋值,最朴素的想法是依次取变量的赋值组合并检查其是否满足约束条件指数级计算量 若CSP问题的任何一个变量的最大值域为d,那么可能的完全赋值数量为O(dn) 有限值域CSP问题包括布尔CSP问题其中有一些NP完全问题,如3SAT问题(命题逻辑语句的可满足性) / 最坏情况下不会指望低于指数级时间复杂性解决该问题,第2章 搜索技术,33,2.5.2 CSP的回溯搜索,CSP问题具有一个性质:可交换性变量赋值的顺序对结果没有影响 / 所有CSP搜索算法生成后继节点时,在搜索树每个节点上只考虑单个变量的可能赋值 CSP问题的求解
17、使用深度优先的回溯搜索 算法思想: 每次给一个变量赋值,当没有合法赋值(不满足约束时)就要推翻前一个变量的赋值,重新给其赋值,这就是回溯,第2章 搜索技术,34,简单回溯法生成的搜索树,澳大利亚地图染色问题的搜索树,第2章 搜索技术,35,回溯搜索的通用算法,可以改善上述无信息搜索算法的性能,这些改进是一些通用性的考虑: 变量赋值的次序对性能的影响在若干变量已经赋值的条件下,如果下一步赋值有多个选择,该选择哪一个? 当前变量的赋值会对其他未赋值变量产生什么约束?怎样利用这种约束以提高效率? 当遇到某个失败的变量赋值时,怎样避免同样的失败?就是说找到对这种失败起到关键作用的某个变量赋值,第2章
18、搜索技术,36,2.5.3 变量赋值次序的启发式,随机的变量赋值排序难以产生高效率的搜索 如:在WA=red/NT=green条件下选取SA赋值比Q要减少赋值次数(1:2) / 并且一旦给定SA赋值以后,Q/NSW/V的赋值只有一个选择 因此,选择合法取值最少的变量或者称为最少剩余值(MRV)启发式,或者称为最受约束变量/失败优先启发式 称为失败优先启发式是因为它可以很快找到失败的变量,从而引起搜索的剪枝,避免更多导致同样失败的搜索,第2章 搜索技术,37,MRV启发式,当有多个变量需要选择时优先选择在当前约束下取值最少的变量 当赋值的变量有多个值选择时优先选择为剩余变量的赋值留下最多选择的赋
19、值 如,WA=red/NT=green时,如果给Q赋值,则Q=blue的选择不好,此时SA没有一个可选择的了 如果要找出问题的所有解,则排序问题无所谓,第2章 搜索技术,38,度启发式,对于初始节点,选择什么变量更合适? 度启发式选择涉及对其他未赋值变量的约束数量大(与其他变量关联最多)的变量 地图染色例子中,度(SA)=5 / 其他均为2/3 实际上,一旦选择了SA作为初始节点,应用度启发式求解本问题,则可以不经任何回溯就找到解 SA=red NT=green Q=blue NSW=green WA=blue V=blue,第2章 搜索技术,39,2.5.4 变量约束的启发式,在搜索中尽可能
20、早地考虑某些约束,以便减少搜索空间 前向检验如果X被赋值,前向检验就是检查与X相连的那些变量Y,看看它们是否满足相关约束,去掉Y中不满足约束的赋值,第2章 搜索技术,WA=red Q=green V=blue,蓝色字体为赋值结果,40,前向检验,地图染色问题中的前向检验 前向检验与MRV启发式相结合实际上,MRV要做的就是向前找合适的变量 赋值V=blue引起矛盾,此时SA赋值为空,不满足问题约束算法就要立刻回溯 注意这里只是检验一步,即和当前节点是否矛盾 / 至于被检验节点之间的约束检验还不能进行改进:约束传播,第2章 搜索技术,41,约束传播弧相容,约束传播将一个变量的约束内容传播到其他变
21、量 希望约束传播检验更多的变量 / 花费的代价更少快速 弧相容依次检验约束图中各个相关节点对(这里弧是有向弧) 例如:给定SA/NSW当前值域,对于SA的每个取值x,NSW都有某个y和x相容,则SA到NSW的弧是相容的 / 反过来是NSW到SA的弧相容,第2章 搜索技术,42,弧相容(1),在地图染色约束的前向检验图中:第三行SA=blue/NSW=red,blue,则SA的取值有一个NSW=red与之相容 / 反过来NSW=blue,则SA为空值,即不相容通过删除NSW值域中的blue可使其相容 同样,弧相容检测也能更早地发现矛盾如第二行SA/NT值域均为blue,如必须删去SA=blue,
22、则发现不相容 保持弧相容(MAC)算法思想反复检测某个变量值域中的不相容弧,进行值删除,直到不再有矛盾,第2章 搜索技术,43,弧相容(2),弧相容算法思想: 用队列记录需要检验不相容的弧 每条弧Xi, Xj依次从队列中删除并被检验,如果任何一个Xi值域中的值需要删除,则每个指向Xi的弧Xk, Xi都必须重新插入队列进行检验因为指向这个变量的弧可能产生新的不相容(因为原来可能就是因为这个值产生了它们之间的相容) 时间复杂度二元CSP约束至多有O(n2)条弧 / 每条弧至多插入队列d次(d个取值),检验一条弧为O(d2) /算法最坏情况下为O(n2d2),第2章 搜索技术,44,特殊约束,实际问
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 原理 搜索 技术
链接地址:https://www.31doc.com/p-2584184.html