《湖南大学人工智能幻灯片4》由会员分享，可在线阅读，更多相关《湖南大学人工智能幻灯片4（29页珍藏版）》请在金锄头文库上搜索。
1、第四章,超越经典的搜索,内容提要,局部搜索算法 不确定动作的搜索 使用部分可观察信息的搜索 联机搜索,局部搜索算法,在许多最优化问题中，我们不是要寻找到达目标状态的路径，而是找到目标状态本身。 N皇后问题：,局部搜索算法,局部搜索算法：从单个当前结点出发，通常只移动到它的邻近状态而不保留搜索路径 优点： 很少的内存 能在很大的或者无限的状态空间中找到合理的解,爬山法,爬山法,缺点? 依据初始状态，得到局部最大值,爬山法,h=直接或者间接相互攻击的皇后对数 h=17(左图) h=1(右图),局部极小值,模拟退火搜索,爬山法不完备，随机法效率低，考虑结合两者产生了模拟退火搜索 基本思想：允许算法向
2、坏的方向移动以摆脱局部最大值，但这种移动随着时间的推移概率逐步下降,模拟退火搜索,如果时间下降得足够的慢，那么模拟退火算法找到一个全局最优值的概率接近于1,局部束搜索,随机产生k个状态，然后每一步从所有的后继状态中选择k个最佳的后继状态直到找到目标状态。(内存中保留K个状态) 随机束搜索：不是找到k个最佳，而是随机找到k个后继状态，随机概率与状态值成正比。,遗传算法,一个后继状态由两个父状态决定 以k个随机产生的状态开始(population) 一个状态表示成一个字符串 定义一个健康度量函数用来评价状态的好坏程度 通过选择，交叉，突变的操作产生下一轮状态,遗传算法,健康度量函数: 非冲突的皇后
3、数量(min = 0, max = 8 7/2 = 28) 24/(24+23+20+11) = 31%,23/(24+23+20+11) = 29%,遗传算法,样本被选择繁衍后代的概率正比于它的健康度函数值,发生交叉操作的概率需要预先设定，交叉位置随机产生,发生突变操作的概率需要预先设定，通常远小于交叉概率,使用不确定性动作的搜索,环境是完全可观察的和确定的 可以知道任何动作序列之后达到的状态 环境是部分可观察或者是不确定的 无法准确预知未来状态 需根据未来感知信息制定相应的行为,使用不确定性动作的搜索,例子：真空洗尘器世界的不稳定行为 在一块脏区域洗尘可以使该区域干净，有时也会清洁邻近区域
4、 在干净区域洗尘可能是该区域弄脏 Suck when state=1 If state=5 then right,suck Else do nonthing,与或搜索树,或结点必须选择行动 在用圆圈表示的与结点上必须处理所有后继 解用粗黑线标出,Q: LOOP什么意思？,无观察信息的搜索,Agent 感知不到任何信息，称为无传感问题，也称相容问题 无传感问题是可解的还是无解的？ 可解！ 真空吸尘器世界无传感问题的可解性： 初始状态：1，2，3，4，5，6，7，8 “向右”操作后:2,4,6,8 “洗尘”操作后4,8 “向左”操作后1,7 “洗尘”操作后目标状态7 在信念状态解无观察信息的问题,
5、无观察信息的搜索,无观察信息问题P的定义 信念状态：包含物理状态中每个可能的集合，假定N个物理状态，最多有2N个信念状态 初始状态：所有物理状态的集合 行动： 转移模型： 对于确定行动 对于不确定行动 目标测试：信念状态中的所有物理状态都满足目标状态 路径开销：假定所有状态下一个行动的开销相同,无观察信息的搜索,256个可能的信念状态只有12个可达； 初始状态出发的行动序列S,L,S与R,L,S达到相同的信念状态5,7 如果一个行动序列是信念状态b的解，那么它也是b的任何子集的解,部分可观察信息的搜索,真空吸尘器世界问题的局部感知： 位置传感器和局部垃圾传感器 例如：状态1的可观察信息perc
6、ept(s)=A,dirty 一个信念状态到另一个信念状态的特定行动分三阶段发生： 预测阶段:给定信念状态b和行动a，预测信念状态 观察预测阶段:确定预测信念状态中可观察到的感知信息o: 更新阶段：根据每个可能的感知信息得到信念状态,部分可观察信息的搜索,部分可观察信息的搜索,Suck,Right,if Bstate=6 then Suck else ,部分可观察信息的搜索,部分可观察信息的搜索,部分可观察环境中的问题求解Agent 形式化，搜索算法，执行解行动 解是一个条件规划不是一个序列 if-then-else Agent在完成行动和接收感知信息时维护自身的信念状态,部分可观察信息的搜索,UPDATE(PREDICT(UPDATE(b,NSW),Move),NS),联机搜索Agent,脱机搜索算法：在行动之间计算好完整的解决方案 联机搜索算法：行动，观察环境，下一步行动,联机搜索Agent：竞争比,竞争比=实际代价/最小代价 30/20=1.5 竞争比越小越好 竞争比可以是无穷大，比如达到某些状态后无法达到目标状态(活动不可逆) 可安全探索的状态空间：每个可达到的状态出发都有达到目标状态的行动，如迷宫问题，八数码问题,总结,局部搜索算法 不确定动作的搜索 使用部分可观察信息的搜索 联机搜索,Qa？,
