← 返回起始笔记位置

知识卡片

结构图卡 · 9843.q · 生成模型:Hunyuan

Boltzmann机的最短路径搜索

理解等级:中级

Boltzmann 机求解 TSP 最短路径时,把每条路径当作一个状态、路径长度当作能量。算法先用欧氏距离构造城市间的距离矩阵,随机生成一条初始路径并打乱,进入内外两层循环。内层:计算当前路径长度,用路径交换产生新路径,计算新长度;若新路径更短就直接接受,否则按玻耳兹曼函数以 exp(−(new−old)/T) 的概率接受,使算法有机会跳出局部最优。外层每轮按 λ 降温,直至达到最大迭代次数。最后取所有路径中长度最小者为最优解。要点:收敛曲线前段震荡下降表示不断逃离局部最优,后段平稳表示已接近全局最优;接受较差解是它区别于贪心搜索的关键。

结构图:

flowchart TD
  A[初始化距离矩阵与随机路径] --> B[计算当前路径长度]
  B --> C[交换城市生成新路径]
  C --> D{新路径更短?}
  D -->|是| E[接受新路径]
  D -->|否| F[以exp(-Δ/T)概率接受]
  E --> G[按λ降温]
  F --> G
  G --> H{达到最大迭代?}
  H -->|否| B
  H -->|是| I[取最短路径为最优解]
这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第6章 神经网络初步 · 查看原书依据

      从图6.14中可以看出,前500次迭代路径的距离在不断的震荡中显著下降,说明在温度下降过程中,路径距离不断逃离局部最优解。500次迭代之后,震荡明显减少,到800次迭代左右接近最优。之后曲线平稳,无上升或下降情况,说明算法已经达到全局最优。

    参考来源

    - 位置:《机器学习算法原理与编程实践》第6章 神经网络初步(源文件:extracted/机器学习算法原理与编程实践/_epub-src/OEBPS/text00022.html) - 结论依据:原文给出 Boltzmann 机主循环中路径交换、玻耳兹曼函数接受、降温、提取最优路径的步骤,并以收敛曲线说明逃离局部最优与达到全局最优。 - 原始内容:从图6.14中可以看出,前500次迭代路径的距离在不断的震荡中显著下降,说明在温度下降过程中,路径距离不断逃离局部最优解。500次迭代之后,震荡明显减少,到800次迭代左右接近最优。之后曲线平稳,无上升或下降情况,说明算法已经达到全局最优。