本章考虑对一个或多个状态进行评价和修改，而不是系统地搜索从初始状态开始的路径。也就是说，本章注重找到解状态，而忽略初始状态到解的路径。

局部搜索算法，有统计物理学家带来的 模拟退火法，进化生物学家带来的遗传算法。

 

4.1局部搜索和最优问题

局部搜索算法从单一当前节点出发，通常只移动到它的临近状态。

优点：内存消耗很小，适用于 系统算法不适用的 很大或无限的状态空间中 寻找合理的解。

状态空间地形图（见下），坐标（表示状态），高度（表示代价函数或目标函数）。如标高对应代价，最低谷即全局最小值。如标高对应目标函数，最高点即全局最优解。

爬山法（最陡上升法）

一个循环，不停的向值增加的地方移动，在到达一个顶峰时停止。

容易出现的问题：

1. 局部最大值
2. 山脊，造成了一系列的局部极大值
3. 高原，造成了一大块局部最大值，最速梯度下降会迷路。

可以看到，当迭代深度很大时，搜索陷入局部最优解，要重启动。

但重启动也有陷阱，不能一看到数据不同就重启动，也要设阈值，否则重启动次数过多，有的小山峰只要侧移动一下就能到最优值。

 

模拟退火法

选择随机移动，如果移动使情况改善，则接受该移动，否则以小于1的概率接受移动，且该概率在使状态变坏的情况下 呈指数下降——评估值ΔE变坏。这个概率也随温度T降低而降低。开始T高时，可能允许坏的移动，T越低，则越不允许这种移动。如果调度让T下降的足够慢，算法找到全局最优解的概率趋于1 。

1. 1. 1. 迭代搜索效率高，并且可以并行化
      2. 算法中有一定概率接受比当前解较差的解，因此一定程度上可以跳出局部最优
      3. 算法求得的解与初始解状态S无关，因此有一定的鲁棒性
      4. 具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法

 

局部束搜索

记录k个状态而不是1个状态，从k个随机生成的状态开始，每一步生成所有k个状态的所有后继状态。如果有一个后继满足条件，则终止。否则，从整个后继列表中选择k个最佳的后继，重复这个过程。

遗传算法

局部束搜索的变形，通过将两个亲本结合后生成后继。从k个随机生成的状态（种群）开始，每个状态称之为个体。

这里最好用估价函数再优化，收敛太慢了！

 

4.2连续空间的局部搜索

连续空间的分支因子是无限的。

离散化

Newton-Raphson method

凸优化

牵涉20章，先略过

 

4.3 使用不确定动作的搜索

环境不确定，信息由感知提供。Agent的未来行动依赖于未来感知信息。问题的解是应急规划而不是一个序列。

4.3.1 不稳定的吸尘器世界

引入不确定因素。

一块脏区域会因Suck变干净，有时会同时清洁邻近区域。一块干净的区域进行Suck可能会弄脏。

推广得到应急规划

[Suck, if State == 5 then [Right, Suck] else []]//好像专家系统呀

4.3.2 与或搜索树

与或搜索问题的解是一棵子树：（1）每个叶子都有目标节点，（2）在或节点上规范了一个活动，（3）在与节点上包含所有可能后果

与或图搜索可使用深搜。算法的一个关键是处理环的方法，环常出现在不确定问题中。如果当前状态从根出发的某条路径上的状态相同，则返回失败，表示 这个解可丢弃，因为前面有更优解。算法不检查当前状态是否从根出发的其他路径上的重复状态。也可用BFS，A*等。

4.3.3 不断的尝试

简化循环规则。存在 在 因不确定因素导致的错误解上死循环。

 

4.4 使用部分可观察信息的搜索