【人工智能】—局部搜索算法、爬山法、模拟退火、局部剪枝、遗传算法

这篇具有很好参考价值的文章主要介绍了【人工智能】—局部搜索算法、爬山法、模拟退火、局部剪枝、遗传算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

局部搜索算法

  • 在某些规模太大的问题状态空间内,A*往往不够用【人工智能】—局部搜索算法、爬山法、模拟退火、局部剪枝、遗传算法

    • 问题空间太大了
    • 无法访问 f 小于最优的所有状态
    • 通常,甚至无法储存整个边缘队列
  • 解决方案

    • 设计选择更好的启发式函数
    • Greedy hill-climbing (fringe size = 1)
    • Beam search (limited fringe size)

内存限制

  • 瓶颈:内存不足,无法存储整个边缘队列
  • 爬山搜索:
    • 只有“最佳”节点保留在周围,没有边缘队列
    • 通常按h优先选择继任者(贪婪的爬山)
    • 与贪婪的回溯相比,它仍然有边缘队列
  • 剪枝搜索(有限内存搜索)
    • 介于两者之间:保持边缘中的K个节点
    • 根据需要转储优先级最低的节点
    • 可以单独按h(贪婪剪枝搜索)或h+g(有限内存A*)进行优先级排序

局部搜索算法

  • 在许多优化问题中,通往目标的路径是不相关的;目标状态本身就是解决方案
  • 状态空间=“完整”配置集(完全状态)
    • 查找满足约束的配置,例如n皇后
  • 在这种情况下,我们可以使用本地搜索算法
  • 保持一个单一的“当前”状态,尝试改善它
    • 直到你无法让它变得更好
  • 恒定空间,适合在线和离线搜索
  • 通常效率更高(但不完备)

示例:n-皇后

  • 将n个皇后区放在n×n板上,同一行、同一列或同一对角线上没有两个皇后区#【人工智能】—局部搜索算法、爬山法、模拟退火、局部剪枝、遗传算法

爬山算法

  • 简单、概括的想法:
    • 从任何地方开始
    • 总是选择最好的邻居
    • 如果没有邻居的分数比当前分数高,退出
  • 这在理论上效果很糟糕,因为他不具有完备性(算法不会陷入死循环,即一定能结束)也不保证得到最优解
  • 问题:根据初始状态,可能会陷入局部最大值【人工智能】—局部搜索算法、爬山法、模拟退火、局部剪枝、遗传算法
    • 随机重新开始爬山算法一定程度克服了局部最大值
    • 随机侧向移动逃离肩膀
    • 但可能在最大值处循环

随机重启爬山

  • 非常简单的修改:

    1. 当被卡住时,随机选择一个新的启动状态,然后从那里重新运行爬山
    2. 重复此操作k次
    3. 返回k个局部最优值中的最佳值
  • 可以做到非常高效

  • 每当使用爬山时都应该尝试

  • 快速、易于实施;对于解决方案空间表面不太“颠簸”(即不太多局部最大值)的许多应用来说,效果很好

  • 仍然以8皇后问题为例:【人工智能】—局部搜索算法、爬山法、模拟退火、局部剪枝、遗传算法

    • h=直接或间接相互攻击的成对皇后数量
    • 对于上述状态,h=17
    • 一个局部最优解如下:h=1【人工智能】—局部搜索算法、爬山法、模拟退火、局部剪枝、遗传算法

模拟退火算法

  • 思想: 通过允许一些“坏”动作,但逐渐降低其频率,来逃避局部最大值【人工智能】—局部搜索算法、爬山法、模拟退火、局部剪枝、遗传算法

  • 可以证明:如果T下降得足够慢,那么模拟退火搜索将找到概率接近1的全局最优

  • 广泛应用于超大规模集成电路布局、航空公司调度等文章来源地址https://www.toymoban.com/news/detail-421075.html

局部剪枝搜索

  • 跟踪k个状态,而不仅仅是一个。
  • 从k个随机生成的状态开始。
  • 在每次迭代时,生成所有k个状态的所有后续状态。
  • 如果任何一个是目标状态,则停止;否则,从完整列表中选择k个最佳继任者,然后重复。
  • 像贪婪搜索一样,但始终保持K状态:【人工智能】—局部搜索算法、爬山法、模拟退火、局部剪枝、遗传算法
  • 多种实用设置中的最佳选择
  • 与并行运行的k个搜索不同!
  • 找到好状态的搜索,会招募其他搜索加入他们
  • 变量:分支大小,鼓励多样性?
  • 问题:通常情况下,所有k个状态最终都在同一个局部山丘上
  • 思想:随机选择k个继任者,偏向于优秀的继任者

遗传算法

  • 遗传算法使用自然选择隐喻
  • 通过组合两个父状态生成后续状态
  • 从k个随机生成的状态开始(总体种群)
  • 状态表示为有限字母表上的字符串(通常是0和1的字符串)
  • 评价函数(适应度函数适应度函数). 值越高,状态越好。
  • 通过选择、交叉和突变产生下一代状态(选择,杂交,变异)
  • 示例:每个状态由8个数字表示,按照概率随机选择两对交叉,适应度就是互不攻击的皇后对数,概率就是适应度的占比【人工智能】—局部搜索算法、爬山法、模拟退火、局部剪枝、遗传算法【人工智能】—局部搜索算法、爬山法、模拟退火、局部剪枝、遗传算法【人工智能】—局部搜索算法、爬山法、模拟退火、局部剪枝、遗传算法

小结

  • 局部搜索算法——通往目标的路径是不相关的;目标状态本身就是解决方案,保持单一的“当前”状态,并尝试改进它
  • 登山搜索
    • 根据初始状态,可能会陷入局部最大值
  • 模拟退火搜索
    • 通过允许一些“坏”的移动来逃避局部最大值,但逐渐降低其频率
  • 局部剪枝搜索
    • 跟踪k个状态,而不仅仅是一个
  • 遗传算法
  • 好的启发式搜索能大大提高搜索性能
  • 但由于启发式搜索需要抽取与问题本身有关的特征信息,而这种特征信息的抽取有时会比较困难,因此盲目搜索仍不失为一种有用的搜索策略
  • 好的搜索策略应该
    • 引起运动—避免原地踏步
    • 系统—避免兜圈
    • 运用启发函数—缓解组合爆炸
  • 搜索树 vs 搜索图
    • 搜索树:结点有重复,但登记过程简单
    • 搜索图:结点无重复,但登记过程复杂(每次都要查重)
    • 省空间,费时间。

到了这里,关于【人工智能】—局部搜索算法、爬山法、模拟退火、局部剪枝、遗传算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 人工智能在法律智能搜索中的应用

    作者:禅与计算机程序设计艺术 《人工智能在法律智能搜索中的应用》 1.1. 背景介绍 随着人工智能技术的快速发展,自然语言处理、机器学习、深度学习等技术已经在人们的生活中发挥了越来越重要的作用。在法律领域,人工智能技术可以高效地帮助律师和法律从业人员进

    2024年02月09日
    浏览(68)
  • 人工智能头歌实验(盲目搜索)

    本关任务:编写代码实现广度优先搜索一个给定的树。 相关知识 为了完成本关任务,你需要掌握广度优先搜索算法的原理与实现。 广度优先搜索步骤 广度优先搜索一般是采用先进先出( FIFO )的队列来实现的,在这里我们用到了两个表: Open :是一个 先进先出的队列 ,存

    2024年01月18日
    浏览(42)
  • 人工智能 与 搜索引擎的较量

    随着科技的不断进步,人工智能(AI)已经渗透到了我们生活的方方面面,搜索引擎也不例外。AI与传统搜索引擎之间的较量成为了科技界和互联网用户关注的热点话题。 搜索引擎是一种互联网工具,旨在帮助用户在互联网上查找相关信息。它们通过扫描互联网上的网页、文

    2024年02月08日
    浏览(50)
  • 【人工智能】— 深度优先搜索、代价一致搜索、深度有限搜索、迭代深度优先搜索、图搜索

    搜索问题是指既不能通过数学建模解决,又没有其他算法可以套用或者非遍历所有情况才能得出正确结果。这时就需要采用搜索算法来解决问题。搜索就是一种通过穷举所有解的状态,来求得题目所要求的解或者最优解的方法。 搜索的基本概念: 状态:对某一系统在某一时

    2024年02月08日
    浏览(48)
  • 【人工智能】—_深度优先搜索、代价一致搜索、深度有限搜索、迭代深度优先搜索、图搜索

    搜索问题是指既不能通过数学建模解决,又没有其他算法可以套用或者非遍历所有情况才能得出正确结果。这时就需要采用搜索算法来解决问题。搜索就是一种通过穷举所有解的状态,来求得题目所要求的解或者最优解的方法。 搜索的基本概念: 状态:对某一系统在某一时

    2024年02月10日
    浏览(65)
  • 禁忌搜索在人工智能伦理中的位置

    人工智能(Artificial Intelligence, AI)是一门研究如何让计算机模拟人类智能的科学。在过去的几十年里,人工智能研究者们已经开发出许多有趣和有用的算法,这些算法可以解决许多复杂的问题。然而,随着人工智能技术的不断发展和进步,我们面临着一系列新的挑战和道德问题

    2024年02月19日
    浏览(57)
  • 【人工智能】对研究方法,智能模拟,学科范畴,涉及学科,研究范畴,安全问题,实现方法,人工智能与人类差距等方面的详细讲解

    作者简介: 辭七七,目前大一,正在学习C/C++,Java,Python等 作者主页: 七七的个人主页 文章收录专栏: 七七的闲谈 欢迎大家点赞 👍 收藏 ⭐ 加关注哦!💖💖 用来研究人工智能的主要物质基础以及能够实现人工智能技术平台的机器就是计算机,人工智能的发展历史是和

    2024年02月16日
    浏览(48)
  • 【复习】人工智能 第六章 搜索求解策略(又多又难)

    在求解一个问题时,涉及到两个方面: (1)该问题的表示 (2)相对合适的求解方法:由于绝大多数需要人工智能方法求解的问题缺乏直接求解的方法,因此, 搜索 为一种求解问题的一般方法。 另外如果真的想拿下这一章,还是走一下ppt或书上的八数码的对应的每一种情况

    2024年01月16日
    浏览(53)
  • OpenAI Embedding:基于人工智能的搜索新篇章

    本文正在参加「金石计划」 Embedding模型在许多应用场景中都有广泛的应用。在OpenAI中,文本嵌入技术主要用于衡量文本字符串之间的相关性。 嵌入(Embeddings)是一种将离散变量表示为连续向量的方法。它在机器学习中起到了不可或缺的作用。例如,在机器翻译中的词嵌入和分

    2024年02月04日
    浏览(57)
  • 人工智能:一种现代的方法 第三章 经典搜索 上

    3.1 问题求解智能体 环境假设:单Agent、确定的、可观察的、离散的、已知的 问题求解智能体的工作流程通常如下: 目标设定 :首先,问题求解智能体需要有一个明确的目标或需要解决的问题。 问题形式化 :然后,智能体需要将这个目标或问题形式化为一个搜索问题。这通

    2024年02月05日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包