《人工智能 一种现代方法》第三版 第4章 超越经典搜索 笔记摘录

本文主要是介绍《人工智能 一种现代方法》第三版 第4章 超越经典搜索 笔记摘录,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

第4章 超越经典搜索

综述:

本章讨论不受环境性质的约束。

一、二状态空间的局部搜索算法,考虑对一个活着多个状态进行评价和修改,而不是系统的探索从初始状态开始的路径。

局部搜索算法包括模拟退火法和进化生物学带来的遗传算法

三、四不在强调环境的确定性和可观察性,主要思想是如果Agent不能准确预测传感器的接受,那么它需要考虑当传感器接收到应急状态发生时该做什么,由于只具备部分可观察性,Agent需要跟踪可能的状态。

五在线搜索,Agent面对的是完全位置的空间要从头开始搜索。

正文

  • 局部搜索算法和最优化问题
    1. 局部最优算法和最优化问题
      1. 如果到目标的路径是无关紧要,可以考虑不关心路径的算法,局部搜索算法从单个当前节点处罚,通常只移动到它的邻近状态。一般情况下不保留搜索路径。
      2. 搜索算法不是系统化,但是又两个关键的优点
        1. 他们只用很少的内存—通常是常数
        2. 他们经常能在系统化算法不适用的很大或者无限的(连续的)状态空间中找到合适的解
      3. 借助状态空间地形图理解局部搜索:局部搜索算法就是探索这个地形图,如果存在解,那么完备的局部搜索算法总能找到解;最优的局部搜索算法总能找到全局最小值/最大值。

Ps:

横坐标:状态定义 纵坐标:启发式代价函数或者目标函数定义

如果纵坐标对应于代价,那么目标就是找到最低谷—即全局最小值

如果纵坐标对应于目标函数,那么目标就是找到最高峰—即全局最大值

    1. 爬山法
      1. 最陡上升版本:简单的循环过程,不断向值增加的方向持续移动。
      2. 局部搜索算法一般使用完整状态形式化。
      3. 爬山法有事也被称为贪婪局部搜索:因为她只选择邻居中状态最好的一个,而不考虑下一步该如何走。

    1. 爬山法容易陷入的困境:
      1. 局部极大值:局部极大值比他的每个邻接结点都高的封顶,但是比全局最大值要小。爬山算法达到局部最大值附近就会被拉向封顶,然后卡在局部极大值出无法前进。
      2. 山脊:山脊造成一系列的局部最大值,贪婪算法很难处理这种情况
      3. 高原:在状态空间地形图上的一块平原区域,他可能是一块平的局部最大值,不存在上山的出口,或者是山肩。爬山法在高原可能会迷路。
    2. 爬山法有很多变形:
      1. 随机爬山法:在上山移动中随机地选择下一步,被选择的概率可能随着上山移动的陡峭程度不同而不同。
      2. 首选爬山法:实现了随即爬山法,随机的生成后继结点知道生成一个优于当前结点的后继。(在后继结点很多的时候是个好策略)
      3. 随机重启爬山法:通过随机生成初始状态来导引爬山搜索,知道找到目标。
    3. 模拟退火法搜索
      1. 爬山法从来不下山,即不会向值比当前结点低的(或代价高的)方向搜索,是不完备的,可能卡在局部最大值上
      2. 纯粹的随机是完备的,但是效率太低
      3. 模拟退火算法,把爬山法和随机行走以某周方式结合:开始使劲摇晃(先高温加热)然后慢慢降低摇晃的强度(也就是逐渐降温)
      4. 模拟退火算法的内层循环和爬山法类似,只是它没有选择最佳移动,选择的是随机移动,如果改移动使情况改善,该移动则被接受,否则,算法以某个小于1的概率接受该移动。如果移动导致状态变坏,概率则成指数级下降—评估值变坏,这个概率也随温度而下降:开始T高的时候可能允许“坏的”移动,T越低则越不可能发生,如果调度让T下降的足够慢,算法找到全局最优解的概率逼近1.

      1. 模拟退火法现在广泛用于工厂调度、其他大型最优化任务
    1. 局部束搜索
      1. 局部束搜索算法记录K个状态,而不是只记录一个。它从k个随机生成的状态开始,每一步全部k个状态的所有后继状态全部被生成,如果其中有一个目标状态,则算法停止,否则,它从整个后继状态列表中选择k个最佳的后继,重复该过程。
      2. 虽然局部束搜索算法看起来像并行运行的k个随机重启搜索,但是两者却不同,随机重启搜索,每个搜索运行过程都是独立的,而局部束搜索中,有用的信息在并行的搜索线程之间传递。
      3. 随机束搜索:为了解决k个状态缺乏多样性,很快会聚集在状态空间中的一小快区域内的问题。将从后继集合中选择最好的k个后继状态,改为随机选择k个后继状态,其中选择给定后继状态的概率是状态值的递增函数。
    2. 遗传算法
      1. 是随机束搜索的变形,通过把两个父状态结合生成后继,而不是通过修改单一状态进行。
      2. 算法思想:
        1. 概念解释
          1. 种群:k个随机生成的状态
          2. 个体:每个状态叫做个体
        2. 算法思想:
          1. 从k个随即成长的状态开始,每个状态都由它的目标函数或适应度函数给出评估值,对于好的状态,适应度函数应返回较高的值。
        3. 算法图示

 

        1. 算法注意点:如果两个父串差别很大,那么咋叫产生的状态和每个父状态都相差很远,通常的情况早期的种族是多样性的,因此咋叫在搜索过程的早起阶段在状态空间中采用较大的步调,而后来当大多数个体都很相似的时候采取较小的步调。
      1. 主要优点:遗传算法和随机束搜索一样,结合了上山趋势、随机探索、和并行线程之间交换信息。遗传算法最主要的优点在于杂交。杂交的优势在于他能够将独立发展出来的能执行有用功能的的字符区域结合起来,提高了搜索的粒度。
  • 连续空间中得局部搜索

    1. a为步长
  • 使用不确定动作的搜索
    1. 与或搜索树
      1. 在确定环境中,分支是由Agent在每个状态下的选择形成的,我们称这样的结点为或结点。
      2. 在不确定的环境中,分支是由环境选择每个行动的后果,我们称这样的结点为与结点
      3. 由这两种结点构成的树称之为与或树
      4. 与或搜索问题的解是一颗子树:
        1. 每个叶子上都有目标结点
        2. 在或结点上规范一个活动
        3. 在与结点上包含了所有后果。
      5. 对比了解与或图
  • 使用部分可观察信息的搜索
    1. 无观察信息的搜索
      1. 如果Agent感知不到任何信息,我们称之为无传感问题,有时也成为相容问题。
      2. 如下定义无传感的无传感问题:
        1. 信念状态:整个信念状态空间包含物理状态的每个可能的集合。若问题P有N个状态,那么这个无传感问题就有2的N次方个状态,尽管很多状态是不可达的。
        2. 初始状态:显然是P中所有状态的集合,尽管有些状态Agent具有很多知识。
        3. 行动
        4. 转移模型
        5. 目标测试
        6. 路径开销
        7.  
    2. 有观察信息的搜索
    3. 求解部分可观察环境中的问题
    4. 部分可观察环境中的Agent
  • 联机搜索Agent和未知环境
    1. 联机搜索问题
    2. 联机搜索Agent
    3. 联机局部搜索
    4. 联机搜索中的学习
  • 本章小结

这篇关于《人工智能 一种现代方法》第三版 第4章 超越经典搜索 笔记摘录的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1096641

相关文章

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Java中Switch Case多个条件处理方法举例

《Java中SwitchCase多个条件处理方法举例》Java中switch语句用于根据变量值执行不同代码块,适用于多个条件的处理,:本文主要介绍Java中SwitchCase多个条件处理的相... 目录前言基本语法处理多个条件示例1:合并相同代码的多个case示例2:通过字符串合并多个case进阶用法使用

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

html5的响应式布局的方法示例详解

《html5的响应式布局的方法示例详解》:本文主要介绍了HTML5中使用媒体查询和Flexbox进行响应式布局的方法,简要介绍了CSSGrid布局的基础知识和如何实现自动换行的网格布局,详细内容请阅读本文,希望能对你有所帮助... 一 使用媒体查询响应式布局        使用的参数@media这是常用的

Spring 基于XML配置 bean管理 Bean-IOC的方法

《Spring基于XML配置bean管理Bean-IOC的方法》:本文主要介绍Spring基于XML配置bean管理Bean-IOC的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录一. spring学习的核心内容二. 基于 XML 配置 bean1. 通过类型来获取 bean2. 通过

基于Python实现读取嵌套压缩包下文件的方法

《基于Python实现读取嵌套压缩包下文件的方法》工作中遇到的问题,需要用Python实现嵌套压缩包下文件读取,本文给大家介绍了详细的解决方法,并有相关的代码示例供大家参考,需要的朋友可以参考下... 目录思路完整代码代码优化思路打开外层zip压缩包并遍历文件:使用with zipfile.ZipFil

Python处理函数调用超时的四种方法

《Python处理函数调用超时的四种方法》在实际开发过程中,我们可能会遇到一些场景,需要对函数的执行时间进行限制,例如,当一个函数执行时间过长时,可能会导致程序卡顿、资源占用过高,因此,在某些情况下,... 目录前言func-timeout1. 安装 func-timeout2. 基本用法自定义进程subp

Python列表去重的4种核心方法与实战指南详解

《Python列表去重的4种核心方法与实战指南详解》在Python开发中,处理列表数据时经常需要去除重复元素,本文将详细介绍4种最实用的列表去重方法,有需要的小伙伴可以根据自己的需要进行选择... 目录方法1:集合(set)去重法(最快速)方法2:顺序遍历法(保持顺序)方法3:副本删除法(原地修改)方法4:

Python中判断对象是否为空的方法

《Python中判断对象是否为空的方法》在Python开发中,判断对象是否为“空”是高频操作,但看似简单的需求却暗藏玄机,从None到空容器,从零值到自定义对象的“假值”状态,不同场景下的“空”需要精... 目录一、python中的“空”值体系二、精准判定方法对比三、常见误区解析四、进阶处理技巧五、性能优化

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a