人工智能学习之第四章--超越经典搜索

Posted by liveipool on October 11, 2016

人工智能学习之第四章–超越经典搜索

第四章–超越经典搜索

如果到达目标的路径是无关紧要的,我们可能考虑不同的算法,这类算法不关心路径。局部搜索算法从单个当前结点(而不是多条路径)出发,通常只移动到它的领进状态,一般情况下不保留搜索路径。虽然局部搜索算法不是系统化的,但是有两个关键的优点:1.只用很少的内存(通常是常数)2.它们经常能在系统化算法不适用的很大或无限的(连续的)状态空间中找到合理的解。
除了找到目标,局部搜索算法对于解决纯粹的最优化问题十分有用,其目标是根据目标函数找到最佳状态。

局部搜索

爬山法

最基本的局部搜索技术,在每一步,当前的节点都会被它的最佳邻接结点所代替。
爬山法有时被称为贪婪局部搜索,因为它只是选择邻居中状态最好的一个,而不考虑下一步该如何走,所以容易出现局部最大值而陷入困境。

  • 最陡上升:不断向值增加的方向持续移动。
  • 随机爬山法:在上山移动中随机地选择下一步。
  • 首选爬山法:实现了随机爬山法,随机地生成后继结点直到生成一个优于当前结点地后继。
  • 随机重启爬山法:通过随机生成初始状态来导引爬山法搜索,直到找到目标。(对于八皇后问题,随即重启爬山法实际上是有效的,即使有300万个皇后,这种方法找到解的时间不超过1分钟)

模拟退火搜索

爬山法搜索从来不“下山”,即不会向值比当前结点低地(或代价高的)方向搜索,它肯定是不完备的,理由是容易卡在局部极大值上。与之相反,纯粹的随机行走——就是从后继集合中完全等概率的随机选取后继,是完备的,但是效率极低。
模拟退火搜索 同时具有效率和完备性,允许下山的随机爬山法。在退火初期下山移动容易被采纳,随时间推移下山的次数越来越少。可以想象为一个人变更职业,年轻时容易,越老越不容易。

局部束搜索

内存总是有限的,但在内存中只保存一个结点又有些极端。局部束搜索算法记录K个状态而不只是记录一个。它从K个随机生成的状态开始。每一步全部K个状态的所有后继状态全部被生产。如果其中有一个是目标状态,则算法停止。否则,它从整个后继列表中选择K个最佳的后继,重复这个过程。
随机束搜索是随机选择K个后继状态,避免出现所有选中的后继结点集中在状态空间中的一小块区域内。

遗传算法

遗传算法是随机束搜索的一个变形,它通过把两个父状态结合来生成后继,而不是通过修改单一状态进行。使用杂交,如21365448和13947728杂交成21347728(单纯举例)

连续空间中的局部搜索

绝大多数现实世界的环境都是连续的,但大部分算法都不能处理连续的状态和动作空间,因为连续空间里的分支因子是无限的。下面是一些能在连续状态空间上寻找最优解的一些局部搜索技术。

使用不确定动作的搜索

如果假设环境是完全可观察的和确定的,那么Agent可以总是知道自己的状态并且能够算出任何行动序列之后的状态。而如果环境是部分可观察的或是不确定的,都无法预知未来的信息,因此在这种情况下,问题的解不再是一个序列,而是一个应急规划(或称策略)
当环境是部分可观察或是不确定的时候,解决问题的关键概念是信念状态

与或搜索树

与或搜索问题的解是一棵子树:1.每个叶子上都有目标结点 2.在或结点上规范一个活动 3.在与结点上包含所有可能后果。

不断尝试

如果行动不稳定,比如吸尘器向右移动可能会失败,就一直尝试Right直至生效。

联机搜索Agent

术语“联机”通常用于计算机科学,说明算法是边接受输入数据边处理的,而不是等到整个输入数据集都可以用以后再处理。 竞争比=实际旅行经过的路径开销/实际的最短路径。

本章小结

  • 局部搜索方法如爬山法适用于完整状态形式化,它在内存中只保留少量结点信息。随机算法正在研究中,包括模拟退火 ,当给定合适的冷却调度安排时能够返回最优解。
  • 局部搜索方法也可以应用于连续空间上的问题求解。线性规划和凸优化问题遵守状态空间的形状限制和目标函数的特性,并且存在高效实用的多项式时间算法。
  • 遗传算法是维护大量状态种群的随机爬山搜索。新的状态通过变异杂交产生,杂交把来自种群的状态对结合在一起。
  • 不确定的环境中,Agent可以应用与或搜索来生成应急规划达成目标,无论执行过程中产生怎样的后果。
  • 当环境是部分可观察时,用信念状态表示Agent可能在的状态集合。
  • 标准的搜索算法可直接应用于信念状态进行无感知问题求解。与或搜索可以解决一般部分可观察问题。在信念状态空间中逐个构造解的增量算法通常效率更高。
  • 探索问题发生在Agent对环境的状态和行动一无所知时。对于可安全探索的环境,联机搜索Agent能够建造地图并且在有解时能够找到目标。根据经验不断修正启发式估计,是一种避免局部极小值的有效方法。