【MATLAB】模拟退火算法

模拟退火算法的MATLAB实现

模拟退火算法简介
模拟退火算法应用实例
关于计算结果

模拟退火算法简介

1982年，Kirkpatrick 将退火思想引入组合优化领域，提出了一种能够有效解决大规模组合优化问题的算法，尤其对 NP 完全问题表现出显著优势。模拟退火算法的灵感源自固体退火过程，即先将温度升至极高，然后缓慢降温（即退火），使系统达到能量的最低点。相较于快速降温（即淬火）无法达到最低能量状态，退火的缓慢降温过程更有助于系统找到全局最优解。

模拟退火算法是一种适用于求解最小化问题或更新学习过程（随机或确定性）的随机搜索算法。在该过程中，每一步的更新长度与对应的参数成正比，这些参数类似于物理过程中的温度。在优化开始时，为了更快地实现最小化或学习，温度被设置得很高，随后逐渐降温以实现系统的稳定性。

这算法将物理系统的退火过程类比于优化问题的求解过程，优化的目标函数对应于金属的内能，优化问题的自变量组合状态空间对应于金属的内能状态空间，求解过程即是在组合状态空间中寻找目标函数值最小的组合状态。

根据 Metropolis 准则，粒子在温度 $\mathrm{T}$ 时趋于平衡的概率为 $\exp(-\bigtriangleup E/(k\mathrm{T}))$ ，其中 $E$ 为温度 $\mathrm{T}$ 时的内能， $\bigtriangleup E$ 为其变化量， $k$ 为 Boltzmann 常数。将固体退火过程模拟到组合优化问题中，内能 $E$ 对应于目标函数值 $f$ ，温度 $\mathrm{T}$ 演化为控制参数 $t$ ，从而得出模拟退火算法：从初始解 $i$ 和控制参数初值 $t$ 开始，对当前解反复进行 “生成新解、计算目标函数差、接受或舍弃” 的迭代，并逐步衰减 $t$ 值。算法终止时的当前解即为近似最优解。这是基于蒙特卡罗迭代求解方法的一种启发式随机搜索过程。退火过程由冷却进度表（Cooling Schedule）控制，包括控制参数初值 $t$ 及其衰减因子 $\bigtriangleup t$ 、每个 $t$ 值时的迭代次数 $L$ 和停止条件 $S$ 等。

模拟退火算法应用实例

MATLAB 遗传算法和模式搜索工具箱提供了 simulannealbnd 函数，用于通过模拟退火算法求解无约束或带有边界约束的多变量最小化问题。该函数的调用语法如下：

x = simulannealbnd(fun, x0)：从初始值 x0 开始，搜索目标函数 fun 的最小值 x。目标函数的输入为变量 x，并在 x 处返回一个标量值。x0 可以是标量或向量。
x = simulannealbnd(fun, x0, lb, ub)：在边界条件 lb 和 ub 的约束下，优化求解目标函数 fun。
x = simulannealbnd(fun, x0, lb, ub, options)：使用自定义的 options参数，而非默认值，进行优化求解。
x = simulannealbnd(problem)：求解 problem，其中 problem 是一个包含输入变量的结构体。
[x, fval] = simulannealbnd(...)：返回点 x 处的目标函数值 fval。
[x, fval, exitflag] = simulannealbnd(...)：返回退出标志 exitflag，用于描述函数计算的退出条件。
[x, fval, exitflag, output] = simulannealbnd(fun, ...)：返回结构体 output，其中包含优化过程中的信息。

【例1】求解 MATLAB 自带的测试函数 De Jong 第五函数的最小值。De Jong 第五函数是一个具有多个局部极小值的二维函数。在 MATLAB 命令行中输入 dejong5fcn 可查看 De Jong 第五函数的图像，如图 1 所示。

>> dejong5fcn% 注意：命令行中输入查看 De Jong 第五函数的图像。

在这里插入图片描述

图1. De Jong 第五函数

x0 = [0 0];
[x,fval] = simulannealbnd(@dejong5fcn,x0)% 注意：.m文件名必要和simulannealbnd一样，否则报错。

运行结果：

在这里插入图片描述

另外，在具有上下边界条件约束的情况下也可以调用simulannealbnd数来求解:

x0 = [0 0];
lb = [-64 -64];  % 下边界约束
ub = [64 64];   % 上边界约束
[x,fval] = simulannealbnd(@dejong5fcn,x0,lb,ub)

运行结果：

在这里插入图片描述

在优化过程中，可以实时绘制图像，显示优化信息，包括当前迭代中的最优点、最优值、当前点和当前值等。可以使用以下 MATLAB 命令实现这一功能。

x0 = [0 0];
options = saoptimset('PlotFcns' {@saplotbestx, @saplotbestf, @saplotx, @saplotf});  %绘图参数设置
simulannealbnd(@dejong5fcn, x0, [ ], [ ], options)

运行结果：

在这里插入图片描述

图2. 使用模拟退火算法优化 De Jong 第5函数

在模拟退火算法的运行过程中，程序实时显示了结果的图形。最终生成的图像如图2所示，其中展示了最优点、最优值、当前点和当前值等优化信息。算法在点 (-31.9772, -31.9778) 处找到了函数的最小值。

关于计算结果

由于模拟退火算法是一种随机算法，在优化过程中存在随机选择的因素，因此每次运行相同的命令，结果可能会有所不同。有时算法可能会陷入局部最优，导致某些结果较大。为了获得更理想的解，即更小的目标函数值，通常需要多次调用优化函数，并在多次计算结果中选择最优的结果作为最终输出。

在模拟退火算法的计算过程中，MATLAB 使用了均匀随机数和正态随机数生成器。决定是否接受新的点时，算法会使用 rand 和 randn 函数进行选择。由于每次调用 rand 和 randn 函数时，其种子都会发生变化，因此每次调用这些函数时都会生成不同的随机数。

如果需要精确地再现计算结果，可以在调用 simulannealbnd 函数时返回 output 结构数组。output 结构数组中包含了当前随机数生成器的种子状态。在再现计算前，可以将种子设置为 output 中保存的种子。例如，在使用模拟退火算法计算 De Jong 第5函数的最优值时，可以返回变量 output，相应的 simulannealbnd 调用语法为：

[x, fval, exitflag, output]= simulannealbnd(@dejong5fcn, [0 0]);

运行结果：

随机种子包含在 output.rngstate 中，可以通过以下命令重新设置随机数生成器的状态。如果现在再次运行 simulannealbnd 命令，就可以验证是否得到与上次相同的结果。

>> set(RandStream.getGlobalStream,'State', output.rngstate.State);
>> [x, fval, exitflag, output]= simulannealbnd(@dejong5fcn, [0 0])% 注意：这两句在运行过一次退火寻优后，在命令行中直接运行。

运行结果：

在这里插入图片描述