← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3741.a

模拟退火按概率选择邻域状态

理解等级:中级

模拟退火(SAA)是一种用于组合优化的随机搜索,可看作局部搜索的拓展。“邻域状态”指对当前解做一次小改动能得到的候选解。普通局部搜索只接受更好的邻居,一旦周围没有更好的解就停在局部最优;SAA 则以一定概率也接受较差的邻居,因此有机会离开局部最优。

它借用固体退火的对应关系:

  • 目标函数值对应物体的内能 E(最小化问题中越小越好)。
  • 控制参数 t 对应温度 T,随迭代逐步降低。
  • 每步产生候选,比较目标差,再决定接受或舍弃;温度越高,越容易接受较差候选,具体规则见 [[较差候选仍可按温度概率接受]]。

“理论上是全局最优算法”依赖足够慢的冷却等条件;实际效果取决于冷却规则和问题,不能当作无条件保证。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第11章《模拟退火算法概述》(源文件:`_epub-src/EPUB/xhtml/chapter11_0001.xhtml`) - 结论依据:导言定义SAA为组合优化随机搜索并指出按概率选邻域状态,但没有给出温度参数、接受准则或全局收敛条件;卡片明确限定目前可确认的范围。 - 原始内容:SAA以一定的概率选择邻域中目标值相对较小的状态,从理论上来说,它是一种全局最优算法。 - 位置:《智能算法导论》第11章《1 1 . 1 . 2 模 拟 退 火 算 法 发 展 历 程》(源文件:`_epub-src/EPUB/xhtml/chapter11_0003.xhtml`) - 结论依据:本节把SAA界定为局部搜索的拓展,并称其可概率性跳出局部最优;本卡保留该机制描述,但不将全局收敛评价外推为无条件结论。 - 原始内容:SAA是一种通用的随机搜索算法,是局部搜索算法的拓展, - 原始内容:由于SAA可以在搜索过程中概率性地跳出局部最优解并最终趋于全局最优 [ 7 ] - 位置:《智能算法导论》第11章《1 1 . 2 . 1 模 拟 退 火 算 法 基 本 思 想》(源文件:`_epub-src/EPUB/xhtml/chapter11_0004.xhtml`) - 结论依据:正文将内能映射为目标函数、温度演化为控制参数,并把状态转移写成产生候选、比较目标差、接受或舍弃;这补足了概率搜索与优化目标之间的对应关系。 - 原始内容:将内能 E 模拟为目标函数值 f ,温度 T 演化成控制参数 t ,即得到解组合优化问题的SAA