模拟退火算法报告.docx

模拟退火算法报告.docx

《模拟退火算法报告.docx》由会员分享，可在线阅读，更多相关《模拟退火算法报告.docx（11页珍藏版）》请在冰点文库上搜索。

电信研17-2贾彦勇SA算法报告

模拟退火算法

一定义

1概念

什么是退火？

在热力学上，退火现象指物体逐渐降温的物理现象，温度愈低，物体的能量状态会低；够低后，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。

大自然在缓慢降温（亦即，退火）时，可“找到”最低能量状态：

结晶。

但是，如果过程过急过快，快速降温（亦称「淬炼」）时，会导致不是最低能态的非晶形。

如下图所示，首先（左图）物体处于非晶体状态。

我们将固体加温至充分高（中图），再让其徐徐冷却，也就退火（右图）。

加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小（此时物体以晶体形态呈现）。

似乎，大自然知道慢工出细活：

缓缓降温，使得物体分子在每一温度时，能够有足够时间找到安顿位置，则逐渐地，到最后可得到最低能态，系统最安稳。

模拟退火算法（SA）最早的思想是由N.Metropolis 等人于1953年提出。

1983年,S.Kirkpatrick等成功地将退火思想引入到组合优化领域。

它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。

模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。

模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。

在迭代更新可行解时，以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。

以下图为例，假定初始解为左边蓝色点A，模拟退火算法会快速搜索到局部最优解B，但在搜索到局部最优解后，不是就此结束，而是会以一定的概率接受到左边的移动。

也许经过几次这样的不是局部最优的移动后会到达全局最优点D，于是就跳出了局部最小值。

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

 。

其中k是波尔兹曼常数，值为，exp表示自然指数，且dE<0。

因此dE/kT<0，所以P（dE）函数的取值范围是（0,1）。

满足概率密度函数的定义。

其实这条公式更直观意思就是：

温度越高，出现一次能量差为P（dE）的降温的概率就越大；温度越低，则出现降温的概率就越小。

在实际问题中，这里的“一定的概率”的计算参考了金属冶炼的退火过程。

假定当前可行解为x，迭代更新后的解为x_new，那么对应的“能量差”定义为：

，其对应的一定概率为：

2SA算法基本要素

（1）状态空间与状态产生函数

1）搜索空间也称为状态空间，它由经过编码的可行解的集合组成。

　　2）状态产生函数（邻域函数）应尽可能保证产生的候选解遍布全部解空间。

通常由两部分组成，即产生候选解的方式和候选解产生的概率分布。

　　3）候选解一般采用按照某一概率密度函数对解空间进行随机采样来获得。

　　4）概率分布可以是均匀分布、正态分布、指数分布等。

（2）状态转移概率

1）状态转移概率是指从一个状态向另一个状态的转移概率。

　　2）通俗的理解是接受一个新解为当前解的概率。

　　3）它与当前的温度参数T有关，随温度下降而减小。

　　4）一般采用Metropolis准则。

（3）内循环终止准则

也称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。

常用的抽样稳定准则包括：

　　1）检验目标函数的均值是否稳定。

　　2）连续若干步的目标值变化较小。

　　3）按一定的步数抽样。

（4）外循环终止准则

即算法终止准则，常用的包括：

　　1）设置终止温度的阈值。

　　2）设置外循环迭代次数。

　　3）算法搜索到的最优值连续若干步保持不变。

　　4）检验系统熵是否稳定。

3算法步骤

（1）初始化：

初始温度T（充分大），温度下限Tmin（充分小），初始解状态x（是算法迭代的起点），每个T值的迭代次数L；

（2）对l=1,2,...,L做第（3）至第（6）步；

（3）产生新解x_new:

（x_new=x+Δx）；

（4）利计算增量Δf=f（x_new）−f（x），其中f（x）为优化目标；

（5）若Δf<0（若寻找最小值，Δf>0）则接受x_new作为新的当前解，否则以概率接受x_new作为新的当前解；

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

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

）；

（7）T逐渐减少，且T>Tmin，然后转第

（2）步。

4SA算法的优缺点

SA算法很容易找到最优解，但是参数难以控制，不能保证一次就收敛到最优值，一般需要多次尝试才能获得（大部分情况下还是会陷入局部最优值）。

观察模拟退火算法的过程，发现其主要存在如下三个参数问题：

（1）温度T的初始值设置问题 

　　温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。

（2）退火速度问题，即每个T值的迭代次数 

　　模拟退火算法的全局搜索性能也与退火速度密切相关。

一般来说，同一温度下的“充分”搜索是相当必要的，但这也需要计算时间。

循环次数增加必定带来计算开销的增大。

（3）温度管理问题 

　　温度管理问题也是模拟退火算法难以处理的问题之一。

实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：

，为了保证较大的搜索空间，α一般取接近于1的值，如0.95、0.9。

5SA算法的改进

（1）设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性；

（2）设计高效的退火策略；

　　（3）避免状态的迂回搜索；

　　（4）采用并行搜索结构；

　　（5）为避免陷入局部极小，改进对温度的控制方式；

　　（6）选择合适的初始状态；

　　（7）设计合适的算法终止准则。

也可通过增加某些环节而实现对模拟退火算法的改进。

主要的改

进方式包括：

（1）增加升温或重升温过程。

在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部极小解处停滞不前。

（2）增加记忆功能。

为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将一些在这之前好的态记忆下来。

（3）增加补充搜索过程。

即在退火过程结束后，以搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。

（4）对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。

（5）结合其他搜索机制的算法，如遗传算法、混沌搜索等。

（6）上述各方法的综合应用。

二SA算法的应用

模拟退火算法的应用很广泛，可以高效地求解NP完全问题，如TSP问题（TravellingSalesmanProblem，简记为TSP）、最大截问题（MaxCutProblem）、0-1背包问题（ZeroOneKnapsackProblem）、图着色问题（GraphColouringProblem）等等。

模拟退火算法作为一种通用的随机搜索算法，现已广泛用于VLSI设计、图像识别和神经网计算机的研究。

模拟退火算法的应用如下：

模拟退火算法作为一种通用的随机搜索算法，现已广泛用于VLSI设计、图像识别和神经网计算机的研究。

模拟退火算法的应用如下：

1）模拟退火算法在VLSI设计中的应用

利用模拟退火算法进行VLSI的最优设计，是目前模拟退火算法最成功的应用实例之一。

用模拟退火算法几乎可以很好地完成所有优化的VLSI设计工作。

如全局布线、布板、布局和逻辑最小化等等。

2）模拟退火算法在神经网计算机中的应用 

模拟退火算法具有跳出局部最优陷阱的能力。

在Boltzmann机中，即使系统落入了局部最优的陷阱，经过一段时间后，它还能再跳出来，再系统最终将往全局最优值的方向收敛。

3）模拟退火算法在图像处理中的应用

模拟退火算法可用来进行图像恢复等工作，即把一幅被污染的图像重新恢复成清晰的原图，滤掉其中被畸变的部分。

因此它在图像处理方面的应用前景是广阔的。

其中，SA算法在图像处理领域应用比较广泛。

比如：

1）SA算法在多阈值图像分割中的应用

图像分割是图像处理与计算机视觉领域中最为基础和关键的任务之一,是对图像进行视觉分析和模式识别的前提。

它不仅可以大量压缩数据,减少存储容量,而且能极大地简化后续处理步骤。

在众多图像分割方法中,阈值分割主要利用图像中目标与背景在灰度特征上的差异将图像划分为若干部分。

因实现简单、计算量小、性能较稳定,阈值分割已成为最基本和应用最广泛的分割技术。

1979年日本学者大津提出了最大类间方差法因计算方法简单、自适应强而成为使用最广泛的图像阈值自动选取方法之一。

但传统的Otsu是采用遍历的方式寻找使类间方差最大的阈值T,计算量会随分类数增加呈几何级数增长,这在很大程度上限制了Otsu算法的应用，为了解决多阈值图像分割时最大类间方差法计算量庞大的问题，引入了SA算法，用模拟退火演进代替穷举法搜索最优阈值向量可以使计算量大大减少。

然而为了能够更快地逼近最优值，需要对初始阈值做处理，由直方图提取初始阈值向量的任务分如下三步进行：

a）对直方图进行高斯滤波。

图像的直方图包含了图像的分类信息,但它通常是一条呈现很多微小波峰的不光滑曲线,从原始直方图很难识别和提取出符合应用要求的阈值向量。

b）计算滤波后的直方图的梯度得并找出直方图的谷点序列,称之为候选阈值点列。

这些点几乎蕴涵了图像的全部分类信息。

那么最大类间方差法的SA算法的目标函数为最大方差：

那么SA算法可以找出最优的阈值序列来对图像进行分割。

2）SA算法在超分辨率图像重建中的应用

采用传感器对外界图像进行采集传输和变换过程中，由于成像设备自身条件的限制常难以获得高分辨图的图像，而改善成像设备的硬件成本高，短期内技术难以突破、无法应用实践，因此目前主要采用软件技术提高图像的分辨率，改善图像的质量，其中超分辨率重建是一种改善图像质量技术。

而目前应用最广泛的超分辨率重建方法是LLE算法，LLE算法是一种局部线性嵌入算法，它的原理是建设在局部领域内的数据点是线性的，所以领域内任意一点都可由局部近邻点线性表示，其中权值能反映出局部领域的信息，根据这些信息可是这种低维空间仍然保留原高维空间中的几何性质，通过重叠的局部领域得到整体的信息，实质上是在保持原始数据性质不变的情况下，将高维空间的信息映射到低维空间。

LLE算法的难点在于确定邻域K值的大小，若K值过大，容易丢失整体信息；若K值过小，则会造成庞大的计算量。

所以我们引进了SA算法来求出最优的K值。

引入SA算法的LLE算法的操作步骤：

1）对图像进行均匀分块操作，将其划分成多个子图像块。

2）对于每一个子图像块，分别提取归一化亮度和小波变换子带系数特征。

3）用LLE算法对图像特征向量进行选择。

4）采用模拟退火算法优化K个近邻的值。

5）将高分辨率图像的梯度作为目标梯度域，采用LLE算法重构权值，根据重构权值实现超分辨率图像重建。

SA算法在TSP问题中取得了显著的效果，TSP是最有代表性的优化组合问题之一，其应用已逐步渗透到各个技术领域和我们的日常生活中.它一开始是为交通运输而提出的，比如飞机航线安排、送邮件、快递服务、设计校车行进路线等等，实际上其应用范围扩展到了许多其他领域，如在VLSI芯片设计、电路板布局、机器人控制、车辆选路、物流配送等方面，下面举几个实例：

（1）电路板钻孔进度的安排.机器在电路板上钻孔的调度问题是TSP应用的经典例子，在一电路板上打成百上千个孔，转头在这些孔之间移动，相当于对所有的孔进行一次巡游。

把这个问题转化为TSP，孔相当于城市，转头从一个孔移到另一个孔所耗的时间相当于TSP中的旅费。

（2）车辆选路.一个经典的路由问题是在一个网络上发现从源节点到一个目的节点的最佳交通线路，使与距离成比例的流动费用降低到最小.这个问题的关键是在交通网络上计算从源节点到目的节点之间的最短路径。

对这个最小费用流动问题进行扩展，就构成TSP问题，在这个问题中，车辆从源点出发访问多个目的地并且最后回到源点。

（3）基因测序。

Cnoocdre是一种求解旅行商问题的程序.美国国家卫生机构的研究人员利用这一程序来进行基因测序.在这一应用中，DNA片断作为城市，它们之间的相似程度作为城市与城市的距离.研究人员试图寻找一种可能性最高的连接方式把这些DNA片断合成为整张DNA。

SA算法解决TSP问题的基本思想：

（1）选S_0作为初始状态，令S（0）=S_0，同时设初始温度T，令i=0。

（2）令T=T_i，以T和S_i调用Metorpolis抽样算法，返回状态S作为本算法的当前解，S_i=S_0。

（3）按照一定方式降温，即T=T_（i+1），其中T_（i+1）

（4）检查终止条件，如果满足则转步骤（5）,否则转步骤

（2）

（5）当前解S_i为最优解，输出结果，停止。

Metropolis抽样算法描述如下：

    1）令k=0时，当前解S（0）=S_0，在温度T下，进行以下各步操作。

     2）按某个规定的方式根据当前解S（k）所处的状态S产生一个近邻子集N（S（k））+S，从N（S（k））中随机得到一个新状态S'作为下一个候选解，计算能量之差：

△C'=C（S'）-C（S（k））。

    3）如果△C'< 0，则接受S'作为下一个当前解，否则，以概率exp（一△C'/T）接受S'作为下一个当前解。

若S'被接受，则令S（k十1）=S'，否则S（k+1）=S（k）。

     4）k=k+1，检查算法是否满足终止条件，若满足，则转步骤（5），否则转步骤

（2）。

    5）返回S（k），结束。

三SA算法研究现状

模拟退火算法最早的思想是由Metropolis在1953年提出，直到1983年才由rkPatrick等将模拟退火的思想成功引入组合优化领域。

在其得到实际应用后，由于其在解决局部极小问题上的突出表现迅速得到大家的青睐，也引起了众多学者广泛的研究兴趣，使模拟退火算法也得到了突飞猛进的发展。

国内引进模拟退火算法的历史较短，相比于蚁群算法等所进行的研究也不是很多，而且大多数都是关于模拟退火在工程等方面的实际应用以及考察算法的实际效果和效率，较少对其理论性有深入的研究。

在国外，模拟退火算法（SA）在理论上已得到证明，它可以达到全局极小值。

模拟退火算法有其在寻找全局极小方面的优越性，但也存在着收敛速度较慢的缺点。

事实上，正是由于专家和学者对该算法的钻研，才让该算法从经典的模拟退火算法走到了今天的多样型的模拟退火算法，比如快速模拟退火算法，使得该算法的速度和收敛性都得到较大提高，再比如适应性的模拟退火算法，使得该算法具有智能性;再比如现在有学者提到的遗传一模拟退火算法，就是将遗传算法和模拟退火算法二者的优越性结合起来。

不能忽略的是，每种算法的提出都与其应用范围紧密结合，这样使得改进的算法在其应用领域具有较好的适用性。

由于模拟退火算法（SA）从理论上可以达到全局极小值，所以对该算法的研究才更有实际意义，众多学者正在努力钻研将其一般化，使其具有普遍适用性。

11