【优化】一篇入门之-模拟退火(SA)

模拟退火算法(Simulated Annealing，SA)是一种借鉴物理退温过程而设计出来的智能优化算法，不得不说，它是我最喜欢用的一种智能优化算法了，简单又纯粹，实现起来非常方便，原理又容易理解，所以每次需要用到智能优化算法，我第一个想起的都是模拟退火算法，那今天就来说说模拟退火算法吧！

一、模拟退火算法原理

模拟退火算法是一个借鉴物理退温过程设计的智能优化算法，我们先看下它的思想，再看下它的算法流程，就很容易理解它了，闲话少说，上车！

1.1. 模拟退火算法-物理背景

模拟退火算法就是借鉴物理退温的过程，那么我们先来简单看一下什么是物理退温，如下：

一个高温物体，在冷觉后的能量并不总是一样的，它与退火(降温)的过程有关。如果让它缓慢退火，最终物体的能量会比急速退火更加低，因为在降温过程中，粒子有充足的时间，来转移到不同位置，在高温时甚至能凭借热能跃迁到能量更高的位置来寻找更好的位置，而如果急速降温，则会使每个粒子被迫迅速收缩到稳定位置，导致最终能量更高。好了，随便了解一下就好了，都是故事背景。

1.2. 模拟退火算法-思想原理

模拟退火算法借鉴物理退火的原理，用来解决函数优化问题，我们不妨来看下它的思路。

借鉴物理退火的原理，我们所要优化的目标函数，就相当于物体的能量E，我们希望它越小越好。而函数的自变量，它里面的每个就相当于物体的粒子，通过充分调整它，来使得目标函数尽量小：

模拟退火算法先设置一个较高的初始温度T，然后慢慢地降低温度T，而在每个温度下，都对进行充分的调整，在温度较高时，的调整相对也较自由，哪怕的调整会令目标函数值更高，也以一定的概率接受它，而随着温度慢慢下降，x调整的自由度也渐渐变小，最后，当温度下降到一定程度时，基本只接受更优的X，随着不断的迭代，最终收敛到一个局部最优。

二、模拟退火-算法流程

2.1. 模拟退火-算法流程图

好了，我们先来展示一下模拟退火算法的流程图，如下：

比较值得注意的是，模拟退火共包含了内外两层循环，外循环是温度的变化，内循环是当前温度下X的迭代。大家结合下面流程描述来看，就理解它的每一步了。

2.2. 模拟退火-算法流程描述     

模拟退火算法的流程描述如下：

一、初始化

    1.1. 初始化初始解
    1.2. 初始化温度

二、外循环

     2.1. 内循环（直接循环N次）：
     (1) 生成新解
          从x的邻域随机选择一个x作为新解
     (2) 计算新解的能量
     (3) 根据能量差按概率接受新解
          (3.1) 计算新解与旧解的能量差
                      
          (3.2) 根据能量差决定接受新解的概率
                       
          (3.3) 如果 则接受新解，否则放弃新解，进入下一轮
           每次接受新解时，需要更新以下信息：
                   更新当前解
                   更新当前能量 
                   更新历史最优解
                   更新本轮内循环找到的最优最差解所需的能量
     2.2 降温
            
     2.3 判断终止条件
           如果本轮找到的最优、最差解的能量差异不大，则终止循环

三、输出

       输出历史找到的最优解X

三、模拟退火算法-概率公式的解释 

在模拟退火算法中，对于是否接受新解使用了下述公式：

 该公式是非常巧妙的，下面让我们来分步讨论它的意义。

1. 当新解比旧解更优秀时

    当新解比旧解更优秀时，此时，则

    因此，不管随机数是多少，条件一定成立，即只要新解不比旧解差就一定接受新解。

2. 当新解比旧解更差时

 当新解比旧解更差时，此时，则。

p的取值能量差成正比，与温度T成反比，也就是：

    1. 新解越大时(越大)，p就越小，这就意味着新解越差接受新解的概率越小。

    2. 温度T越大时，p越大，这就意味着温度大时接受新解的概率越小。

总的来说，就是新解越差，接受的概率越小，但同时温度会提升这个概率，如果温度很高，即使新解很差，也有很大的概率接受新解。

所以说，这个公式非常的巧妙，仅仅用一个公式，就蕴含了多个机制。

四、模拟退火-代码实现

好了，最后我们随便找个函数出来，用模拟退火来尝试优化它吧！

不妨设要优化的目标函数为：

易知，y的最小值在处取得0，下面我们使用模拟退火算法来进行求解，看看模拟退火算法会给出什么样的结果。在这个问题中，模拟退火中的能量就是我们的目标函数，而在邻域获取新时，我们就随机选择就好了。模拟退火的具体实现代码如下:

% 本代码展示模拟退火算法求解函数极小值问题,目标函数为:y = (x1-2)^2+(x2-3)^2
% 本代码来自《老饼讲解神经网络》www.bbblearn.com ,matlab版本：2018a   
setdemorandstream(888);                                                     % 为方便复现结果,设定随机种子
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                                                             % 迭代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
	fprintf('第%d轮:x=[%.4f,%.4f],E=%.5f,teamp:%.5f\n',t,x(1),x(2),E,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]的差异极小，可见，模拟退火算法已经取得了较好的效果。

总结

模拟退火算法就是借鉴物理退火原理而设计出来的一种智能优化算法，它的算法流程是比较简单的，共包含了内外两层循环，外循环是温度的变化，内循环是当前温度下X的迭代，每次迭代中，只需要邻域找一个x，然后判断是否接受x就可以了，核心步骤就只有几步而已，实现起来非常方便，最喜欢用它了！