模拟退火算法总结

　

退火算法

Metropolis准则——以概率接受新状态

固体退火问题介绍

退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。

• 加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态；

• 等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；

• 冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。

Metropolis接受准则

先给定以粒子相对位置表征的初始状态old，作为固体的当前状态，该状态的能量是$E_{old}$。然后用摄动装置使随机选取的某个粒子的位移随机地产生一个微小变化，得到一个新状态new，新状态的能量是$E_{new}$。

假设在状态时Xold" role="presentation">Xold$X_{old}$，系统受到某种扰动而使其状态变为Xnew" role="presentation">Xnew$X_{new}$。与此相对应，系统的能量也从E(Xold)" role="presentation">E(Xold)$E(X_{old})$变成E(Xnew)" role="presentation">E(Xnew)$E(X_{new})$，系统由状态Xold" role="presentation">Xold$X_{old}$变为状态Xnew" role="presentation">Xnew$X_{new}$的接受概率P为：

P(Xold⇒Xnew)=1E(Xold)≤E(Xnew)" role="presentation">P(Xold⇒Xnew)=1E(Xold)≤E(Xnew)$$P(X_{old}\Rightarrow X_{new})=1E(X_{old})\le E(X_{new})$$

P(Xold⇒Xnew)=e−E(Xnew)−E(Xold)TE(Xold)≥E(Xnew)" role="presentation">P(Xold⇒Xnew)=e−E(Xnew)−E(Xold)TE(Xold)≥E(Xnew)$$P(X_{old}\Rightarrow X_{new})=e^{-\frac{E(X_{new})-E(X_{old})}{T}}E(X_{old})\ge E(X_{new})$$

在温度T下，当前状态到新状态（1）若E(Xold)≤E(Xnew)" role="presentation">E(Xold)≤E(Xnew)$E(X_{old})\le E(X_{new})$，则接受new为当前状态；（2）否则，以概率p=exp(E(Xnew)−E(Xold)T)" role="presentation">p=exp(E(Xnew)−E(Xold)T)$p=exp(\frac{E(X_{new})-E(X_{old})}{T})$接受该状态为当前状态，否则保持old为当前状态。

接受准则的意义

重复以上新状态的产生过程。在大量迁移（固体状态的变换称为迁移）后，系统趋于能量较低的平衡状态。

接受的概率表达式说明，在高温时接受与当前状态能量差较大的新状态为当前状态的概率较大，而在低温时则概率较小；当T趋近于0时，就不能接受任何能量变高的新状态了。

模拟退火算法

基本架构

把 Metropolis准则引入到优化过程中来，最终得到一种对metropolis算法进行迭代的组合优化算法，即模拟退火算法。

对优化问题，需要有一个控制参数t和非负目标函数f(xit)" role="presentation">f(xti)$f(x_i^t)$，其中xit" role="presentation">xti$x_i^t$是在控制参数为t时的解。对于控制参数的每一取值，算法持续进行”产生新解—判断—接受/舍弃”的迭代过程。

控制参数t模拟了物理过程中的温度T，目标函数模拟了物理过程中的能量E，而解模拟了粒子群的微观状态。对于控制参数的每一取值，算法持续进行”产生新解—判断—接受/舍弃”的迭代过程就对应着固体在某一恒定温度下趋于热平衡的过程，也就是执行了一次Metropolis算法。

模拟退火算法从某个初始解出发，经过大量解的变换后，可以求得给定控制参数值为t时组合优化问题的相对最优解xoptt" role="presentation">xtopt$x_{opt}^t$。然后减少控制参数的值，重复执行Metropolis算法，就可以在控制参数趋于零时，最终求得组合优化问题的整体最优解。

固体退火必须”徐徐”降温，才能使固体在每一温度下都达到热平衡，最终趋于能量最小的基态，控制参数的值也必须缓慢衰减，才能确保模拟退火算法最终趋于组合优化问题的整体最优解集。

流程框图

代码实现

% 使用模拟退火计算这个函数h = @(x) x + 10.*sin(5.*x) + 7.*cos(4.*x) 在[-10,10]上的最小值
% 它真正的最小值在x = -5.398附近
% 在模拟退火算法的中采用一种神奇的算法产生新解
%（在当前解的一个邻域内随机产生一个新解，领域的大小随着温度的下降逐渐变小）

Tf = 0.1^10;     %最小温度限
T = 1;           %初始温度
space = 10;      %初始领域长
alpha = 0.5;     %领域长衰减系数
Tt = @(t) 0.99*t; %温度更新函数
h = @(x) x + 10.*sin(5.*x) + 7.*cos(4.*x); %定义句柄函数(直接作为目标函数）
randm = @(x0,w) (x0 - w + 2*w*rand); %定义领域随机数生成器

x_opt = randm(0,10); %产生初始解
while 1
    %产生新解（保证新解在范围内）
    while 1
        x_new = randm(x_opt,space);
        if (x_new >= -10) && (x_new <= 10)
            break
        end
    end
    %计算delta_f和判断是否接受
    df = h(x_new) - h(x_opt);
    if df < 0
        x_opt = x_new;
    elseif exp(-df/T) > rand
        x_opt = x_new;
    end
    %更新温度
    T = Tt(T);
    %判断是否终止
    if T < Tf
        break
    end
end
x_opt

这个神奇的函数h = @(x) x + 10.*sin(5.*x) + 7.*cos(4.*x)的图像是：

代码输出：

文章最后发布于: 2018-09-14 21:34:05

相关阅读

图论算法——无向图的连通分量

引言 深度优先搜索的一个直接应用就是找出一幅图的所有连通分量。在深度优先搜索的递归调用期间，只要是某个顶点的可达顶点都能在

数据结构与算法——图解平衡二叉树及代码实现

平衡二叉树介绍 平衡二叉树，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差最多等于1。由3位科学家共同发明，用他们首字

常见十大(内部)排序算法 - Sorting Algorithms C++

基本概念 内部和外部排序 内部排序在这里指的是只用到了电脑内存而不使用外存的排序方式。相对的，外部排序就是同时动用了电脑内

人脸识别三大经典算法（附PDF下载、经典论文列表）

后台回复“1814

java递归算法（一）——详解以及几个经典示例

什么是递归 递归就是一个程序或函数在其中定义或说明有之间或者间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一