文章目录
局部搜索算法和最优化问题
在第3章中讨论的无信息搜索和有信息搜索有如下性质：环境都是在可观察、确定的、已知的，问题解是一个行动序列。
本章将不受这些环境性质的约束，讨论局部搜索（local search）算法，考虑对一个或多个状态进行评价和修改，而不是系统地搜索从初始状态开始的路径。
局部搜索不关心路径代价，但是关注解状态。Agent不知道前面的状态，只知道当前的状态。 比如八皇后问题，不关心是怎么到目的状态的，只关心最终布局对不对，许多重要应用都有这样的性质，如作业空间调度，自动程序设计等。
局部搜索：不关心路径，从单个当前节点（而不是多条路径）出发，通常只移动到它的邻近状态。一般情况下不保留搜索路径。
虽然局部搜索算法不是系统化的，但是有两个关键优点：
1）通常只用常数级的内存；
2）通常能在系统化算法不适用的很大或无限的（连续的）状态空间中找到合理的解。
此外，局部搜索算法对于解决纯粹的最优化问题十分有用，其目标是根据目标函数找到最佳状态。
如果存在解，最优的局部搜索算法总能找到全局最大/最小值
爬山法（贪婪局部搜索）
定义：不断向值增大的方向移动，直到到达局部最优。
也被称为贪婪局部搜索，因为它只选择邻居中状态最好的一个，而不考虑下一步应该贪婪算法很容易改善一个坏的状态，但却经常陷入局部最优无法跳出。
容易出现的问题：
- 局部极大值：比每个相邻的节点都高，但比全局最大要小。
- 山脊：一系列局部极大值
- 高原：一块平坦的局部极大值
可以看到，当迭代深度很大时，搜索陷入局部最优解，要重启动。
但重启动也有陷阱，不能一看到数据不同就重启动，也要设阈值，否则重启动次数过多，有的小山峰只要侧移动一下就能到最优值。
爬山法（最陡上升版本）
简单的循环过程，不断向值增加的方向移动，即“登高”，在到达一个“峰顶”（邻接状态中没有比它更高的）的时候终止。
算法不会考虑与当前状态不相邻的状态，算法不维护搜索树，当前节点的数据结构只记录当前状态和目标函数值。
例子：八皇后问题（当前状态指的是一个棋盘放着8个皇后的冲突状态），而且每一次生成新状态（后继节点）是通过：移动某一个（不是多个）皇后到这列的另一个可能方格中，所以每个状态有7*8=56个后继。 但是，爬山法会经常陷入困境。
爬山法有时被称为贪婪局部搜索，因为它只是选择邻居中状态最好的一个，而不考虑下一步怎么走。
设置允许侧向移动的次数，可以提高爬山法的成功率，但是相应的平均步数会增加。
优化算法
-
随机爬山法
随机爬山法在上山移动中随机选择下一步；被选中的概率可能随着上山移动的陡峭程度不同而不同。这种算法通常比最陡上升算法的收敛速度慢不少，但是在某些状态空间地形图上它能找到更好的解。 -
首选爬山法
实现了随机爬山法，随机地生成后继节点直到生成一个优于当前节点的后继。这个算法在后继节点很多的时候（比如上千个）是个好策略。 -
随机重启爬山法
之前的三个爬山法都是不完备的，经常会在局部极大值卡住。
随机重启爬山法（random restart hill climbing），它通过随机生成初始状态来导引爬山法搜索，直到找到目标。
这种算法完备的概率接近1。原因：它最终会生成一个目标状态来作为初始状态。
如果每次爬山法搜索成功的概率为 p ,那么需要重新开始搜索的期望次数为1/p
模拟退火搜索(Simulated annealing search)
爬山法不完备，因为会碰到局部极大值
随机走是完备的（因为完全等概率选择后续节点，不受局部极大值影响），但是效率极低。
模拟退火算法：把爬山法和随机行走以某种方式结合，同时得到效率和完备性。
选择随机移动，如果移动使情况改善，则接受该移动，否则以小于1的概率接受移动。如果该移动导致状态“变坏”，则概率在使状态变坏的情况下呈指数下降——评估值ΔE变坏。这个概率也随温度T降低而降低。开始T高时，可能允许坏的移动，T越低，则越不允许这种移动。如果调度让T下降的足够慢，算法找到全局最优解的概率趋于1 。
特点
- 迭代搜索效率高，并且可以并行化
- 算法中有一定概率接受比当前解较差的解，因此一定程度上可以跳出局部最优
- 算法求得的解与初始解状态S无关，因此有一定的鲁棒性
- 具有渐近收敛性，已在理论上被证明是一种以概率l收敛于全局最优解的全局优化算法
局部束搜索（Local beam search）
a）概念：从k个随机生成的状态开始，每一步全部k个状态的所有后继状态全部被生成，如果其中有一个是目标状态，则算法停止，否则，它从整个后续列表中选择k个最佳的后继，重复这个过程；
b）变形：随机束搜索（不是从候选后继集合中选择最好的k个后继状态，而是随机选择k个后继状态）；
随机重启的每个搜索过程是独立的。
局部束搜索中并行的搜索线程之间不是独立的，有用信息在并行的搜索线程之间传递。
遗传算法（Genetic algorithm，GA）
Genetic algorithm，或GA，是随机束搜索的一个变形。
把两个父状态结合来生成后继，而不是通过修改单一状态进行。这和随机剪枝搜索一样，与自然选择类似，除了我们现在处理的是有性繁殖而不是无性繁殖。
像束搜索一样，GA从k个随机状态开始，称之为种群(population)。
每个状态都由适应度函数(fitness function)给出评估值。有selection(选择)，crossover(杂交)，小概率mutation(变异)操作。
遗传算法：结合了上山趋势，随机探索，和在并行搜索线程之间交换信息。
连续空间中的局部搜索
我们讨论过的算法,除了首选爬山法和模拟退火,其他算法不能够处理连续的状态和动作空间。
在连续状态空间同样存在局部极大值问题、山脊问题、高原问题。
约束优化:问题的解必须满足变量的某些严格约束,称此优化问题是受约束的。
最著名的一类约束优化问题是线性规划问题,其约束是线性不等式并且能够组成一个凸多边形区域,目标函数也是线性的。线性规划问题的时间复杂度是关于变量数目的多项式时间函数。
使用不确定动作的搜索
在第3章中,我们假设环境是完全可观察的和确定的,并且Agent了解每个行动的
结果。所以,Agent可以准确地计算出经过任何行动序列之后能达到什么状态,Agent总是知道自己处于什么状态。如果环境是不确定的或部分可观察(甚至无观察)的,则Agent无法断定自己处于什么状态。
如果环境是不确定的，部分可观察(甚至无观察)的Agent无法预知未来感知信。Agent的未来行动依赖于未来感知信息。所以问题的解不是一个动作序列,而是一个应急规划(也称作策略),应急规划描述了根据接收到的感知信息来决定行动。
不确定性的问题的解是嵌套的if-then-else语句;这就意味着它们是树而不是序列。这就允许了在执行过程中根据发生的应急情况进行选择。
不稳定吸尘器世界的例子
现在假设我们引入某种不确定形式,吸尘器更强大但却是不稳定的。在不稳定的吸尘器世界中, Suck 的特点是:
- 在一块脏的区域中进行此动作可以使该区域变得干净,有时也会同时清洁邻近区域。
- 如果是在干净区域进行此动作有可能使脏东西掉在地毯上。
与或搜索树
或结点：规范一个活动（在确定性环境中，分支由Agent在每个状态下的选择形成）；
与结点：包含所有可能后果（在不确定环境中，分支由环境选择每个行动的后果形成）；
使用部分可观察信息的搜索
无观察信息的搜索（无传感器问题、相容问题、不可观察问题）
一个无传感器问题P不再搜索物理状态空间,转而搜索信念状态空间，可形式化定义为：
-
信念状态
整个信念状态空间包含物理状态的每个可能集合。如果P有N个状态，那么这个无传感器问题由2^N个状态，尽管有很多状态是不可达的。 -
初转(信念)状态
P中所有状态的集合。 -
行动ACTIONS(b)
假设Agent的信念状态 b ={ s1 , s2 },但ACTIONS P(s1)≠ ACTIONS P(s2);Agent就不确定哪个行动是合法的。 - 转移模型（对每个行动的描述）
-
目标测试
Agent需要一个确保生效的规划,意味着一个信念状态满足目标仅当其中所有的物理状态都满足GOAL-TEST_P。Agent可能不经意间很早就到达了目标,但它并不 知道 它已经做到了。 - 路径耗散
部分可观察问题
联机搜索
脱机搜索：计算出完整的方案（然后“闭着眼睛”执行该方案），脱机搜索只涉及计算过程，不涉及动作执行过程。
联机搜索：计算和动作执行交替进行。 先采取某个行动，然后观察环境变化并且计算出下一行动。
联机搜索的一个典型实例是将机器人放置在新的大楼里，要求它探查大楼，绘制出从A到B的地图。
婴儿对环境的逐步认知在一定程度上也是一个联机搜索的过程。
迄今为止，前面讨论的都是Agent的脱机搜索算法。它们先对实际问题计算出完整的解决方案，然后再涉足现实世界执行解决方案。联机搜素通过交替地计算和行动来完成任务；它先采取某个行动，然后观察环境变化并且计算出下一行动。
Agent不清楚自身的状态和行动的结果,这时的Agent面临联机搜索问题。
脱机算法能在状态空间的一部分扩展一个结点后,马上在状态空间的另一部分扩展另一个结点。
联机算法只会扩展它实际占据的结点。为了避免遍历整个搜索树去扩展下一个结点,按照局部顺序扩展结点看来更好一些,深度优先搜索具有这个性质。—联机深度优先搜索。
总结
本章介绍的搜索算法超越了在确定的、可观察的和离散环境下寻找目标路径的"经典"情况。
- 局部搜索方法如爬山法适用于完整状态形式化，它在内存中只保留少量结点信息。随机算法正在研究中，包括模拟退火，当给定合适的冷却调度安排时能够返回最优解。
- 局部搜索方法也可以应用于连续空间上的问题求解**。线性规划和凸优化**问题遵守状态空间的形状限制和目标函数的特性，并且存在高效实用的多项式时间算法。
- 遗传算法是维护大量状态种群的随机爬山捜索。新的状态通过变异和杂交产生，杂交把来自种群的状态对结合在一起。
- 在不确定的环境中，Agent可以应用AND-OR捜索来生成目标，无论执行过程中产生怎样的后果。
- 当环境是部分可观察时，用信念状态表示Agent可能在的状态集合。
- 标准的搜索算法可直接应用于信念状态空间进行无感知问题求解，信念状态AND-OR捜索可以解决一般部分可观察问题。在信念状态空间中逐个状态构造解的增量算法通常效率更高。
- 探索问题发生在Agent对环境的状态和行动一无所知时。对于可安全探索的环境，联机搜索Agent能够建造地图并且在有解时能够找到目标。根据经验不断修正启发式估计，是一种避免局部极小值的有效方法。
资源分享
实验代码下载：
https://github.com/yyl424525/AI_Homework
人工智能-一种现代方法中文第三版pdf、课件、作业及解答、课后习题答案、实验代码和报告、历年考博题下载：https://download.csdn.net/download/yyl424525/11310392