《人工智能 一种现代方法》第三版 第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

相关文章

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

mysql出现ERROR 2003 (HY000): Can‘t connect to MySQL server on ‘localhost‘ (10061)的解决方法

《mysql出现ERROR2003(HY000):Can‘tconnecttoMySQLserveron‘localhost‘(10061)的解决方法》本文主要介绍了mysql出现... 目录前言:第一步:第二步:第三步:总结:前言:当你想通过命令窗口想打开mysql时候发现提http://www.cpp

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

CentOS 7部署主域名服务器 DNS的方法

《CentOS7部署主域名服务器DNS的方法》文章详细介绍了在CentOS7上部署主域名服务器DNS的步骤,包括安装BIND服务、配置DNS服务、添加域名区域、创建区域文件、配置反向解析、检查配置... 目录1. 安装 BIND 服务和工具2.  配置 BIND 服务3 . 添加你的域名区域配置4.创建区域

mss32.dll文件丢失怎么办? 电脑提示mss32.dll丢失的多种修复方法

《mss32.dll文件丢失怎么办?电脑提示mss32.dll丢失的多种修复方法》最近,很多电脑用户可能遇到了mss32.dll文件丢失的问题,导致一些应用程序无法正常启动,那么,如何修复这个问题呢... 在电脑常年累月的使用过程中,偶尔会遇到一些问题令人头疼。像是某个程序尝试运行时,系统突然弹出一个错误提

电脑提示找不到openal32.dll文件怎么办? openal32.dll丢失完美修复方法

《电脑提示找不到openal32.dll文件怎么办?openal32.dll丢失完美修复方法》openal32.dll是一种重要的系统文件,当它丢失时,会给我们的电脑带来很大的困扰,很多人都曾经遇到... 在使用电脑过程中,我们常常会遇到一些.dll文件丢失的问题,而openal32.dll的丢失是其中比较

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

Mysql中深分页的五种常用方法整理

《Mysql中深分页的五种常用方法整理》在数据量非常大的情况下,深分页查询则变得很常见,这篇文章为大家整理了5个常用的方法,文中的示例代码讲解详细,大家可以根据自己的需求进行选择... 目录方案一:延迟关联 (Deferred Join)方案二:有序唯一键分页 (Cursor-based Paginatio