湖南大学人工智能课件4

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