如何用随机方法求解组合优化问题(五)

模拟退火算法

这是一篇笔记,是对于B站up主马少平的视频(第四篇 如何用随机方法求解组合优化问题(五))的学习与记录。

前置知识回顾

【回顾】:局部最优问题

在局部搜索问题中,可能会陷入局部最优解(如上图中的B、C),解决思路是:以概率接受差解

【回顾】:退火过程中

从状态 \(i\) 转换为状态 \(j\) 的转换准则:

  • 如果 \(E(j)\le E(i)\),则状态转换被接受;

  • 如果 \(E(j)>E(i)\),则状态转移被接受的概率为:

    \[e^{\frac{E(i)-E(j)}{KT}} \]

根据上述特点,可以发现局部搜索和退火过程存在一定关联,可以尝试将局部搜索与退火过程结合用于求解组合优化问题。

组合优化问题与退火过程的类比

算法设计

基本思想

在局部搜索算法中,从领域中随机选择一个解 \(j\) ,如果该解的指标函数好于当前解 \(i\) 的指标函数,则以概率1接受该解,否则按照以下概率接受该解:

\[e^{\frac{f(i)-f(j)}{t}} \]

这里假定求解最小解,其中 \(f(i)\) 为解 \(i\) 的指标函数,\(t\) 为控制参数,也称作温度。

伪代码

  1. 随机选择一个解 \(i\)\(k=0\)\(t_0=T_{\max}\)(初始温度),计算指标函数 \(f(i)\).
  2. \(t=t_k\),如果满足结束条件,则转(15).
  3. Begin
  4.   如果在该温度内达到了平衡条件,则转(13).
  5.   Begin
  6.     从 \(i\) 的领域 \(N(i)\) 中随机选择一个解 \(j\) .
  7.     计算指标函数 \(f(j)\).
  8.     如果 \(f(j)\le f(i)\),则接受 \(j\)\(i=j\)\(f(i)=f(j)\),转(4).
  9.     否则计算 \(P_{i\Rightarrow j}(t)=e^{-\frac{f(j)-f(i)}{t}}\)
  10.       如果 \(Random(0, 1)<P_{i\Rightarrow j}(t)\),则接受 \(j\)\(i=j\)\(f(i)=f(j)\).
  11.     转(4).
  12.   End
  13.   对 \(t\) 降温,\(t_{k+1}=Drop(t_k)\)\(k=k+1\),转(2).
  14. End
  15. 输出结果.
  16. 结束.

分析

  • 首先随机选择一个解,比如旅行商问题中,先随机生成一条路线。
  • 初始温度需要设置一个较大的数,这是因为“接受较差的解”的概率与温度有关,初始温度设置较大在某种程度上可以帮助跳出局部最优解,而提高了找到全局最优解的可能性。
  • 指标函数用于衡量解的优良性,比如在旅行商问题中是“路线长度”。
  • 算法包含内外两层循环:
    • 内循环为“保持温度不变,在邻域内按照退火的特点,尝试找到可以接受的解”。如果是好解则直接接受,如果是差解则按概率接受。
    • 外循环负责“降温”,每次降温后,如果还没达到平衡条件,则继续寻找解。

以上只是算法的简单框架,还有一些问题需要解决。

算法需要解决的问题

  1. 初始温度 \(t_0\)
  2. 温度 \(t\) 的衰减函数
  3. 算法的终止标准
  4. 每个温度 \(t\) 下的马尔可夫链长度 \(L_k\)

只有这些参数确定之后,算法才算完整,才能用于解决实际问题。

算法性质

与退火过程一样,当满足条件时:

  • 初始温度足够高
  • 在每个温度下状态的交换足够充分
  • 温度 \(t\) 的下降足够缓慢

模拟退火算法以概率1收敛到最优解。

热门相关:冉冉心动   未来兽世:买来的媳妇,不生崽   未来兽世:买来的媳妇,不生崽   买妻种田:山野夫君,强势宠!   未来兽世:买来的媳妇,不生崽