模拟退火算法介绍

解析模拟退火算法

一.爬山算法(Hill Climbing)

介绍模拟退火前，先介绍爬山算法。爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。

爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如图1所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。

二.模拟退火(SA,Simulated Annealing)思想

爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。

模拟退火算法描述： 若J(Y(i+1))>=J(Y(i))(即移动后得到更优解)，则总是接受该移动

若J(Y(i+1))

这里的“一定的概率”的计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来。

根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为P(dE)，表示为：

P(dE)=exp(dE/(kT))

其中k是一个常数，exp表示自然指数，且dE<0。这条公式说白了就 是：温度越高，出现一次能量差为dE的降温的概率就越大；温度越低，则出现降温的概率就越小。又由于dE总是小于0（否则就不叫退火了），因此dE/kT < 0 ，所以P(dE)的函数取值范围是(0,1) 。

随着温度T的降低，P(dE)会逐渐降低。

我们将一次向较差解的移动看做一次温度跳变过程，我们以概率P(dE)来接受这样的移动。

[键入文字]

[键入文字]

模拟退火算法

摘要：本文采用一种模拟退火算法（SAA），通过对热力学中退火过程的模拟，寻找全局极小值，可望在较短时间里求得更优近似解。

关键词：退火；迭代;

引言

金属物体被加热到一定程度后，它的所有分子在状态空间自由运动，随着温度的逐渐下降，分子停留在不同状态，分子运动逐渐趋于有序，最后以一定的结构排列。这种由高温向低温逐渐降低温度的热处理过程就称为退火。退火是一种物理过程，在退火过程中系统的熵值不断减小，系统能量随温度的降低趋于最小值，也就是说，金属物体从高能状态转移到低能状态，变得较为柔韧。一个退火过程一般由三个部分组成。

1．加温过程 目的是怎强分子的热运动使其偏离平衡位置。

2. 等温过程 这个过程是为了保证系统在每一个温度下都达到平衡态。最终达到固体的基态。

3. 冷却过程 其目的是使分子的热运动减弱并渐趋于有序，系统能量逐渐下降，当温度降至结晶温度后，分子运动变成了围绕晶格点的微小振动，液体凝固成固体的晶态，从而得到低能的晶体结构。

这个过程可以用蒙特卡洛（MonteCarlo）的方法加以模拟，该方法虽然比较简单，但需要大量采样才能获得比较精准的结果，计算量大。鉴于物理系统倾向于能量较低的状态，而热运动又妨碍它准确落到最低状态的物理形态，采样时只需着重取那些有贡献作用的状态，则可较快达到较好的结果。

在SAA中，优化问题中的一个解及其目标函数分别可以看成物理退火中物体的一个状态和能量函数，而最优解就是最低能量的状态。而设定一个初始高温、基于Metropolis准则的搜索和控制温度参数t的下降分别相当于物理退火的加温、等温和冷却过程。下表就描述了一个算法问题的对应关系。

表1

算法问题 物理退火

解 状态

目标函数 能量函数

最优解 最低能量的状态

设定初始高温 加温过程

基于metropolis准则的搜索 等温过程

温度参数t的下降 冷却过程

一. 爬山算法 ( Hill Climbing )

介绍模拟退火前，先介绍爬山算法。爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。

爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如图1所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。

图1

二. 模拟退火(SA,Simulated Annealing)思想

爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。

模拟退火算法描述：

若J( Y(i+1) )>= J( Y(i) ) (即移动后得到更优解)，则总是接受该移动

若J( Y(i+1) )< J( Y(i) ) (即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）

这里的“一定的概率”的计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来。

根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为P(dE)，表示为：

P(dE) = exp( dE/(kT) )

其中k是一个常数，exp表示自然指数，且dE<0。这条公式说白了就是：温度越高，出现一次能量差为dE的降温的概率就越大；温度越低，则出现降温的概率就越小。又由于dE总是小于0（否则就不叫退火了），因此dE/kT < 0 ，所以P(dE)的函数取值范围是(0,1) 。

算法设计与分析 计算机101-04 顾鑫

1

模拟退火算法

一、模拟退火算法概念

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。

二、模拟退火算法的模型

模拟退火算法可以分解为解空间、目标函数和初始解三部分。

模拟退火的基本思想:

(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)， 每个T值的迭代次数L

(2) 对k=1，……，L做第(3)至第6步：

(3) 产生新解S′

(4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数

(5) 若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.

(6) 如果满足终止条件则输出当前解作为最优解，结束程序。

终止条件通常取为连续若干个新解都没有被接受时终止算法。

(7) T逐渐减少，且T->0，然后转第2步。

算法对应动态演示图：

模拟退火算法新解的产生和接受可分为如下四个步骤：