本站原创文章，转载请说明来自《老饼讲解-BP神经网络》www.bbbdata.com
模拟退火算法(Simulated Annealing，SA)是借鉴于物理退温而设计的一种函数优化算法
本文讲解模拟退火算法的思想、原理，以及算法流程，并展示模拟退火的代码实现例子
通过本文可以快速了解模拟退火算法是什么，以及如何使用模拟退火算法来解决函数优化问题
本节讲解模拟退火算法解决函数优化问题的思想与原理
模拟退火算法是什么
模拟退火算法(Simulated Annealing，SA)是一个借鉴物理退温过程设计的智能优化算法
物理退温原理如下：
一个高温物体，可以让它缓慢降温，也可以急速降温，但缓慢降温能使物体最终的内能更加低
因为在降温过程中，粒子可转移到不同位置，甚至跃迁到能量更高的位置，这种跃迁取决于温度
急速降温会使每个粒子被迫迅速收缩到稳定位置，因此它最终的状态是匆促的，所以能量会更高
通过缓慢降温，能让粒子在不同温度得到不同的尝试后，再随着温度下降，慢慢收缩到稳定位置
模拟退火算法原理
模拟退火算法解决函数优化问题的思路如下：
借鉴物理退温的原理，所要优化的目标函数，就相当于物体的能量，我们希望它越小越好
而里的每个就相当于物体的粒子，通过充分调整它，来使得目标函数尽量小
模拟退火算法在刚开始时先设置一个较高的温度T，再缓慢降低T，并在每个温度下充分调整
在温度高时，的调整相对较自由，哪怕的调整会令目标函数值更高，也以一定的概率接受它
随着温度慢慢下降，接受更差的X的概率也降低，渐渐的X只向更优位置调整，最终收敛到一个局部最优
本节介绍模拟退火算法的具体流程与算法流程图
模拟退火-算法流程描述
模拟退火算法的流程描述如下：
一、初始化
1.1. 初始化初始解
1.2. 初始化温度
二、外循环
2.1 内循环（直接循环N次）：
(1) 生成新解
从x的邻域随机选择一个x作为新解
(2) 计算新解的能量
(3) 根据能量差按概率接受新解
(3.1) 计算新解与旧解的能量差
(3.2) 根据能量差决定接受新解的概率
(3.3) 如果 则接受新解,否则放弃新解，进入下一轮
每次接受新解时，需要更新以下信息：
👉更新当前解
👉更新当前能量
👉更新历史最优解
👉更新本轮内循环找到的最优最差解所需的能量
2.2 降温
2.3 判断终止条件
如果本轮找到的最优、最差解的能量差异不大，则终止循环
三、输出历史找到的最优解
✍️ 关于概率公式的解释
在模拟退火算法中，对于是否接受新解使用了下述公式
该公式是非常巧妙的，下面我们分步讨论它的意义
一、当新解比旧解更优秀时
当新解比旧解更优秀时，此时，则
因此，不管随机数是多少，条件一定成立，即只要新解不比旧解差就一定接受新解
二、当新解比旧解更差时
当新解比旧解更差时，此时
p的取值受当前温度T与能量差两者的影响
当新解越差时，能量差就越大，此时p越小，同时温度T作为分母，T越大时，p越大
也就是说，当温度很高时，即使能量差很大，也有很大的概率接受新解
所以说，这个公式非常的巧妙，仅仅用一个公式，就蕴含了多个机制
模拟退火-算法流程图
模拟退火共包含了内外两层循环，模拟退火的算法流程图如下：
本节展示如何使用模拟退火算法来解决函数最小值问题
模拟退火算法-代码实现
求 为何值时， 取得最小值
易知，y的最小值在处取得0，下面我们使用模拟退火算法来进行求解
用模拟退火解决该问题时，主要需要确定以下两点：
1. 能量函数是什么：在这里我们将目标函数作为能量函数就可以
2. 邻域中获得新解的方式：这里我们在解的邻域随机选择就可以
模拟退火算法的具体实现代码如下:
%------代码说明：展示模拟退火算法求解函数极小值问题 -----------------
% 目标函数为:y = (x1-2)^2+(x2-3)^2,求解x1,x2取何值时y最小
% 来自《老饼讲解神经网络》www.bbbdata.com ,matlab版本：2018a
%-------------------------------------------------------------------%
setdemorandstream(88); % 老饼为了每次运行的结果一致,在此指定随机种子，实际中可以去掉
%变量初始化
x = [0,0]; % 初始化x
E = calE(x); % 初始化能量
teamp = 100; % 设置初始温度
% -------温度初始化可用此方法(取N次邻域能量差均值的10倍)--------
try_cn = 20; % 尝试20次
En = zeros(1,try_cn); % 初始化邻域能量
for i = 1:try_cn
new_x = x+ 0.1*(rand(size(x))-0.5); % 在邻域中随机取一个解作为新解
En(i)= calE(new_x); % 记录本次邻域解的能量
end
teamp = mean(abs(En-E))*10 ; % 初始化温度
% -------------外循环------------
for t =1:10000
minE = E; % 初始化本次温度下的最小能量为当前能量
maxE = E; % 初始化本次温度下的最大能量为当前能量
% --------内循环-------------
for i=1:100
new_x = x+ 0.05*(rand(size(x))-0.5); % 在邻域中随机取一个解作为新解
new_E = calE(new_x); % 计算新解的能量
% 按概率接受新解
if(exp((E-new_E)/teamp)>rand()) % 如果接受新解
x = new_x; % 更新解
E = new_E; % 更新当前能量
minE = min(E,minE); % 更新本次温度下的最小能量
maxE = max(E,maxE); % 更新本次温度下的最大能量
end
end
disp(['第',num2str(t),'轮:x=[',num2str(x),'],E=',num2str(E),',teamp:',num2str(teamp)])
% -----------降温，并检查是否退出循环------------
teamp = teamp*0.5;
if( (maxE-minE)/maxE<0.01 ) % 如果最大最小能量没什么区别
break % 则终止迭代
end
end
%定义能量计算函数（目标函数）
function y = calE(x)
y = (x(1)-2).^2+(x(2)-3).^2;
end代码运行结果如下：
最终的解为x = [2.004,2.9999]，与我们预期的[2,3]的差异极小
可见，模拟退火算法已经取得了较好的效果
End
