当前位置: 首页 > news >正文

模拟退火 - 学习笔记

前置知识:爬山算法

从爬山算法的局限到模拟退火

对于爬山算法所求解问题:计算一个函数的最大/小值。

我们知道它的核心目标是求解函数的最大值或最小值 —— 就像人沿着山坡向上爬,始终朝着 “更高”(求最大值)或 “更低”(求最小值)的方向移动,直到无法找到更优的下一步。

但爬山算法有个致命局限:极易陷入局部最优解。比如在连绵的山脉中,它可能爬到一座小山的山顶(局部最优),就误以为那是整个山脉的最高峰(全局最优),却看不到不远处更高的山峰。为了突破这个瓶颈,科学家们借鉴了物理中 “固体退火” 的原理,设计出一种看似 “玄学”、实则逻辑严谨的优化算法——模拟退火。

模拟退火的核心思路:主动接受 “不完美” 以跳出局限。

模拟退火的关键突破,在于它不执着于每次都选择更优解,而是在一定概率下主动接受 “非最优解”。这种 “退一步” 的策略,正是它能跳出局部最优、向全局最优靠近的核心。

如图所示:即使当前处于一个局部高点,算法也可能暂时 “向下走”,探索周围区域,最终找到真正的全局最高点。

接受非最优解的依据:Metropolis 准则

刚才提到的 “接受非最优解的概率”,并非随机决定,而是遵循严格的Metropolis准则——其概率计算公式为:\(P=e^{-\frac{\Delta E}{T}}\)

我们来拆解公式中两个关键参数的含义:

  • \(\Delta E\)(能量差):在函数极值问题中,可理解为新解与当前解的目标函数值之差。若我们求函数最大值,\(\Delta E=f(新解)-f(当前解)\)
    \(\Delta E \gt 0\) 时,新解更优,算法会必然接受这个新解(类似爬山算法的逻辑);
    当\(\Delta E \leq 0\)时,新解是 “非最优解”,算法会根据\(e^{-\frac{\Delta E}{T}}\)的概率决定是否接受它。

  • \(T\)(当前温度):模拟退火的 “温度” 是一个动态变化的参数,并非物理中的温度,但其核心作用类似 —— 温度越高,分子运动越剧烈,算法越容易接受非最优解;温度越低,算法越谨慎,接受非最优解的概率越小。

模拟退火的三大关键参数

算法的效果很大程度上依赖于三个核心参数的设置,它们共同控制着 “温度下降” 和 “解的探索” 过程:

  1. 初始温度 \(T_0\):算法开始时的 “初始温度”。\(T_0\) 需要设置得足够高——此时算法接受非最优解的概率大,能更自由地探索整个解空间,避免一开始就被局部最优 “困住”。

  2. 降温系数 \(\Delta T\):控制温度下降的 “速度”,最常用 0.99。每次迭代后,当前温度 \(T\) 会更新为$ T=T \times \Delta T$。降温系数不能太小(否则温度降得太快,容易提前陷入局部最优),也不能太大(否则算法效率太低,耗时过长)。

  3. 最终温度 \(T_t\):算法停止的 “终止条件”,通常是一个极小值(如 \(10^{-8}\)\(10^{-10}\))。当当前温度 \(T\) 降至 \(T_t\) 以下时,算法对非最优解的接受概率已趋近于0,解也基本稳定在全局最优(或近似全局最优)附近,此时算法停止。

模拟退火的核心流程

简单梳理一下算法的执行逻辑,就能更清晰地理解它的工作方式:

  1. 初始化:设定初始温度 \(T_0\)、降温系数 \(\Delta T\)、最终温度 \(T_t\),并随机生成一个初始解;

  2. 迭代探索:在当前温度 \(T\) 下,通过微小扰动生成一个新解,计算新解与当前解的 \(\Delta E\)

  3. 接受判断:若 \(\Delta E \gt 0\)(新解更优),直接接受新解;
    \(\Delta E \leq 0\)(新解非最优),则根据\(e^{-\frac{\Delta E}{T}}\) 的概率决定是否接受;

  4. 降温更新:完成一次迭代后,将当前温度T更新为 \(T \times \Delta T\)

  5. 终止判断:重复步骤2至4,直到 \(T \lt T_t\),此时保留的解即为最终的优化结果。

总结

通过 “高温探索、低温收敛” 的策略,模拟退火既避免了爬山算法 “一叶障目” 的局限,又能在后期稳定到最优解附近,成为解决复杂函数极值、组合优化(如旅行商问题)等问题的经典算法。

http://www.hskmm.com/?act=detail&tid=20296

相关文章:

  • Markdown语法入门一:标题,列表,表格与字体
  • 质数筛
  • pnpm 安装后无法使用
  • 数学解题中常见的“漏解”情况分析
  • 图册
  • 简单的Powershell脚本
  • 基于YOLO8+flask+layui的行人跌倒行为检测系统【源码+模型+数据集】 - 详解
  • 环形链表-leetcode
  • [ABC425C] Rotate and Sum Query 题解
  • 线程--基本使用、线程常用方法
  • 酵母表面展示技术:从蛋白分析到多领域应用,解锁可持续发展的生物新工具
  • 9/28数学错题分析
  • linux查找指定字符串的三种方法 - 指南
  • task
  • SQL逐字稿
  • 实用指南:嵌入式面试高频(十二)!!!C++语言(嵌入式八股文,嵌入式面经)c++11新特性
  • 2025 年粒度仪厂家推荐山东耐克特分析仪器,粒度分析仪,喷雾,激光,纳米,在线,图像粒形,干湿两用粒度仪公司推荐
  • 2025年匹克球厂家推荐义乌亿宁体育 ,滚塑匹克球,匹克球网,静音匹克球,LED 发光匹克球,专业比赛匹克球公司推荐
  • 2025 年粒度仪厂家推荐山东耐克特分析仪器,电位仪 / 纳米粒度及 Zeta 电位仪 / Zeta 电位仪公司推荐
  • 2025攻丝机厂家 TOP 企业品牌推荐排行榜,全自动,半自动,转盘,伺服,平推,全自动钻孔,半自动钻孔攻丝机公司推荐
  • 实用指南:微信公众号网页调试, 某讯参数,drviceToken V2
  • 2025 年芝麻灰厂家 TOP 企业品牌推荐排行榜,芝麻灰路沿石,花岗岩石材,火烧板,地铺石,板材,挡车球,桥栏杆,楼梯踏步,门牌石,水篦子公司推荐
  • 2025.9.28
  • 深入解析:宝塔面板搭建RustDesk教程:告别命令行,一键拥有私有远程桌面
  • Windows 安装达梦数据库
  • 有旋Treap
  • xxO
  • 情绪识别论文阅读——Eyemotion - 详解
  • 2025年山东设备回收公司TOP交易服务推荐排行榜,济宁,梁山设备回收,二手,饮料,食品,制药,实验室,生产线,化工厂,废旧,大型,专业设备回收公司推荐
  • 做了个TIFF图片格式转换工具,感觉怎么样?