一、概论
在自然科学以及大多数科学当中和社会生活里经常出现最大或最小的问题，我们从小学开始学习大小比较，一直到高中大学时的最优解问题，都是一种名为最优化问题.最优化问题在大多是领域中都有重要的地位，例如管理科学、计算机科学、图像处理等等需要大量数据的学科中都存在着需要解决的组合优化问题。用我们比较容易理解的说法就是已知一组固定的函数，令这组函数所对应的函数到达最大或最小值.而我们所想到的最简单的方法便是穷举法，然而这种方式存在这大量的数据计算穷举的缺点。优化组合问题中的NP问题是一个很麻烦的问题，它解得规模会随着问题的规模增大而增大，求解所需的时间也会随问题的规模增大而成指数级增长，而当规模过大时就会因为时间的限制而失去了可行性。旅行商问题（TSP）是优化组合问题中最为著名的一个问题，它的特点是容易描述却难于求解.这是一个经典的图论问题，假设有n个城市，用表示.城市之间距离为，i，j=1，2，3，···，n，假设所有城市之间两两连通，要求从一个城市出发，把所有城市都走一遍，而TSP问题就是恰好所有城市都走一遍，而所走路径形成回路且路径最短.将这个问题对应在一个n个顶点的完全图上，假设图为对称图，则要从个可能的解当中到最小的解，需要的对比则要进行次，当 的数值增大时，那么需要的次数也会随之以几何数倍增长，例如每秒运算一亿次的计算机，当需要的时间也只是0.0018秒，当需要的时间却是17年，可当
软暴力将被严惩
时所需的时间却猛增到年，这个结果是我们所不想看到的。
优化组合问题的目标函数是从组合优化问题的可行解集当中求出最优解。组合优化问题有三个基本要素：变量，约束和目标函数，在求解过程中选定的基本参数成为标量，对于变量的取值的所有限制称之为约束，表示可行的方案的标准的函数称之为目标函数。随着问题种类的不同以及问题规模的扩大，要到一种能够已有限代价来求解最优化问题的通用方法一直都是一个难题，建立用最大的可能性求解全局解一直是一个重要问题。但是传统方式却有以下难以处理的问题：（1）非凸可行域和具有多个局部极值问题；（2）不连通的可行域；（3）变量全部或部分是离散的、整型的；（4）目标具有多个极值；（5）难于求解目标函数和约束函数的梯度。于是在这样的环境下出现了一种可以处理以上难题的方式模拟退火法。 模拟退火法最早是由Metropolis在1953年提出的，而在1983年由Kirkpatrick 等人成功的引入到了组合优化领域并目前已经在工程当中得到了广泛的应用。
模拟退火算法的思想是来源于冶金当中的退火过程，是对于固体退货降温过程的模拟。退火过程就是
将材料加热后再让其慢慢的冷却，它的目的是增大晶体的体积，减小晶体的缺陷。而在加热固体的过程中使其原子的热运动加强，内能增大，随着热量的不断增加，原子会离开原来的位置而随机在其他的位置中移动。冷却时，粒子运动速率较慢，慢慢到达平衡，最后到达常温下的基态，内能降低为最小状态。
模拟退火的原理与金属冶炼退货的原理相似：我们可以将热力学的理论利用在统计运筹当中，将搜寻空间中的每一个点想象成空气内的分子；分子的能量即它的动能；搜寻空间内的每一点，也像空气分子一样带有能量，以表示该点对于命题的合适程度.算法以任意点作为起始：每一步先选择一个邻点，然后计算到达邻点的概率.可以说明，模拟退火法所得解根据概率收敛到全局最优解。
1.3模拟退火算法的研究内容及现状舒曼童年情景
模拟退火法的思想在1983年被引入到组合优化领域之后，在实际应用当中以其在解决局部极小问题上的突出表现迅速得到了大家的青睐，同时也引起了大量学者的研究兴趣，使得模拟退火法得到迅猛的发展.相比较国外，我国引进模拟退火法的历史较短，研究的程度也不深。但是其在工程方面的实际应用以及考察算法的实际效果和效率也有不错的优越性，但是它也存在着收敛速度较慢的缺点。
模拟退火法的研究通常分为两类，第一类是基于有限的理论在给出模拟退火法的某些理想收敛的模型所具有的充分或充要条件，当条件满足理论上的退火的三种原则（初始温度、降温速度、终止温度）
时，模拟退火法以概率1达到全局最优解；第二类则是针对特定的具体问题做出研究以得到许多模拟退火法的应用。
也正是根据对于模拟退火算法的研究，才有了当今多种多样的模拟退火算法，而不是单单的经典模拟退火算法.例如快速模拟退火算法、适应性模拟退火算法、遗传模拟退火算法、有记忆的模拟退火算法、并行模拟退火算法与单纯型模拟退火算法等.
二、模拟退火算法的原理及应用
2.1 模拟退火算法的基本原理
前文我们已经知道模拟退火算法是源自于对热力学中退火过程的模拟.也已知模拟退火的原理与金属退火的原理近似.这次我介绍模拟退火算法之前首先介绍一种简单的算法----爬山算法.
爬山算法是一种简单的算法，这种算法从当前的临近解空间中选择一个最优解作为当前解知道达到一个最优解.这种简单的算法主要缺点在于会陷入一种局部最优解的状态，而不一定得到全局最优解.如图1，假设C点为当前解，爬山算法搜索到A 点这个局部最优解就会停止搜索，因为在A点无论从哪个方向移动都不会得到更优的解.
厦门理工学院学报图1
超导体使爬山法是一种贪心的方法，每一次都是选择一个当前的最优解，因此选择的却不一定是最优解，而只能选择到一个局部最优解.模拟退火算法其实也是一种贪心的方法，但是这种贪心的方法却引入了随机的因素.所以模拟退火算法以一定的概率来接受一个比当前解要差的解，从而跳出这个局部最优解，达到全局最优解.再以图1为例，模拟退火算法到局部最优解A时会以一定概率接受E的移动，经过多次像这样的不是局部最优解的移动之后会到达D，从而跳出A这个局部最优解.
模拟退火全局优化算法的基本原理描述如下：
（1）确定初始的温度与初始点，能够计算这一点的函数值
决策支持系统
（2）随机的生成一个，得到一个新的点，计算新点的函数值
（3）若，作为下一次模拟退货的初始点
（4）若则计算新点的接受概率：，产生区间上均匀分布的伪随机函数r，。若则接受新点作为下一次模
拟的初始点；否则扔去原来的点作为下一次的模拟退火的初始点.
由上，模拟退火算法以1的概率收敛到全局最优解，但渐进收敛到最优解需要经 历无线多次的变化.对最优解任意的近似逼近，对于多数的组合优化问题都会导致比解空间规模大的变换数，从而导致了算法指数时间执行.
解决办法：牺牲保证得到最优解为代价，在多项式的时间当中，逼近模拟退火算法的渐进收敛状态，返回一个近似的最优解.
2.2 模拟退火算法的模型
模拟退火算法的模型，也即模拟退火算法的实现形式，可以从以下几个方面来描述:
1.数学模型：包括解空间、目标函数和初始解三部分
解空间：就是所有可能解的集合.如果问题的所有可能的解都是可行解的话，那么解空间就定义为所有可能解的集合
目标函数：它是对优化问题所要达到的目标的一个数学的量化描述，是解空间到某个数集的一个映射，通常情况下表示为若干个优化目标的一个和式.目标函数应该能够正确体现优化问题对整体优化的要求，并且比较容易计算"同时，当解空间包含不可行解时，目标函数中还要包括罚函数项。
初始解：它是算法迭代开始的起点部分局部搜索算法所求得的最终解的质量很大程度上取决于初始解的选取，这样在不知道最终优化解的情况下无法有目的的选择初始解，也不能保证算法有良好的表现。
2.邻域的产生与新解的接受机制
邻域的产生：按某种随机机制由当前解产生一个新解，通常通过简单变化(如对部分元素的置换、互换或反演等)产生，可能产生的新解构成当前解的邻域。连续变量存在着无数个状态，邻域的产生方法应该保证算法的迭代能达到变量的所有取值，且在产生新解时没有倾向性；对离散变量而言，设X 为离散变量的取值序列,m 为当前变量的取值位置，即）（m X X k =，则在当前离散位置的基础上随机产生一个位置的增值*m ，令）（*1k m m X X +=+。
新解的接受机制：根据产生的新解计算新解伴随的目标函数差，一般可由变化的改变部分直接求得；根据接受准则，即新解更优，或恶化但满足Metropolis 准则，判断是否接受新解，对有不可行解而限定了解空间仅包含可行解的问题还要判断新解是否具有可行性；最后，如果新解满足接受准则则进行当前解和目标函数值的迭代，否则舍
弃新解。
中国投资环境3.冷却进度表：冷却进度表是一组控制算法进程的参数，其中包括的参数有， 初始温度0T 充分大且温度衰减的足够慢，Markov 链的长度k L 足够大，终止温度f T 即算法的停止准则.冷却进度表是模拟退火算法的重要支柱，对于算法的性能有着非同寻常的作用。
2.3模拟退火算法的可行性
对于一个算法，我们不可避免的要讨论它的有限终止性和可行性，即算法能否在一个我们可以接受的有限的时间内终止，以及算法能否达到我们的要求，得到我们所需要的解.首先讨论第一个问题，即算法的有限步终止性问题.对于模拟退火算法，由于其随机性，就转为讨论其渐进收敛性，即算法按渐进的概率原则是否收敛.根据MaPkob 理论可以证明：在多项式时间里算法渐进的收敛于一近似最优解.这个结果对于NP 完全问题已经是比较好的了.对于恶化解，随着T 值的衰减,）（f/T exp ∆-趋近于无穷，故当T 衰减到一定程度时即不再接受；至于优化解，一般都可以较快的搜索到该邻域的最优解.因此，
算法在有限时间内必定会出现解在连续M 个MaPkob 链中无任何改变的情况，即完全可以在有限时间内终止，所以算法从概率的角度是渐进收敛的.其次讨论第二个问题，即算法求得的解的好坏.我们知道，模拟退火算法根据
MetroPofis 准则接受新解，因此除了接受优化解外，它还在一定限度内接受恶化解，这也正是模拟退火算法与局部搜索算法的本质区别.开始时t 值较大, ）（f/T exp ∆-也较大，比较容易接受较差的恶化解，随着t 值的减小, ）（f/T exp ∆-也逐渐减小,
）
（f/T exp ∆-最终趋向于∞/1，则只能接受较少的恶化解，最后在T 值趋于零时，就不再接受恶化的解了"从而使模拟退火算法能够从局部最优的“陷阱”中跳出来，最后得到全局的最优解.所以算法的结果是令人满意的。
2.4冷却进度表
冷却进度表是一组控制算法的参数，它的合理选取是保证算法在可以接受的有限时间内返回问题的最优就的关键，也就是保证全局收敛性的效率的关键。
虽然模拟退火算法的渐近收敛性已经被证明.但这并不能保证冷却进度表都能够确保算法的收敛，不合
理的冷却进度表会使算法在某些解之间来回波动却不能收敛于某一个近似的解。模拟退火算法的最终解的质量与其所需的时间是相互矛盾的，它不能确保两全其美的短时间内得到最好的解.而最好的办法就是折中的将其利用，也就
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议