模拟退火算法的可视化

金属固体退火原理

• 金属固体在经过高温加热后，暴露于空气中使其自然冷却。在这个过程中，由于固体份子的运动剧烈程度逐步降低，从而使得固体本身的温度逐步降低。整个过程是一个连续的过程，从而不会产生温度骤减的情况。

局部最优陷阱

• 舍弃差解，接受当前较优解，是普通算法求解最优解的一般逻辑。然而这往往会使算法陷入局部最优陷阱，使得得出的结果并不是最优解。

Metropolis准则

1. 若新解<当前解，则接受新解作为当前解

2. 若新解>当前解，则启动概率算法：

   1. 若概率函数得出的值>rand（1），则接受新解作为当前解；

   2. 否则，保持当前解不变

新解产生策略

1. 二变换：两个随机数调换位置

2. 三变换：三个随机数调换位置

3. 逆变换：对任意两个随机数之间的序列逆序变换

降温策略

1. 指数降温

   • 经典降温曲线

2. 多普勒降温

   • 指数型基础上的变形

3. 振动型多普勒降温

   • 多普勒型基础上的变形

4. 锯齿形降温

   • 指数型基础上的变形

5. 山丘型降温

   • 指数型基础上的变形

编程实现

1. MATLAB

   1. 模型初始化

      1. 确定各环节的初始系数

   2. 降温曲线

      1. 初始温度由目标函数极值决定

      2. 降温次数由终止温度决定

      3. 降温指数a由降温次数和终止温度决定

   3. 内外双层while循环实现

      1. 外循环

         1. 降温曲线

         2. 当前解的图形可视化

         3. 使用plot函数将静态曲线画出动态效果

      2. 内循环

         1. 产生新解

         2. Metropolis准则判断

应用实例

1. 最短路径问题

2. 背包问题

3. 数独魔方

4. 图像校准

5. 数据拟合

6. 线性方程组求解