点击上方“数学建模 and MATLAB”可以关注我们哦！
模拟退火算法是所谓三大非经典算法之一，它脱胎于自然界的物理过程，与优化问题相结合。在百度百科上对于模拟退火算法的定义是：模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。
模拟退火算法（simulated annealing，SA）是一种通用概率算法，用来在一个大的搜寻空间内寻找问题的最优解。由于它能够有效解决NP难问题、避免陷入局部最优解等优点，已经在生产调度、控制工程、机器学习、神经网络、图像处理等领域获得了广泛应用。
什么是退火
退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。
温度越低，物体的能量状态越低，到达足够的低点时，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低，缓慢降温时，可达到最低能量状态；但如果快速降温，会导致不是最低能态的非晶形。但因为物理系统总是趋向于能量最低，而分子热运动则趋向于破坏这中的能量的状态，故而只需着重取贡献比较大的状态即可达到比较好的效果，因而1953年Metropolis提出了这样一个重要性采样的方法，即设从当前状态i生成新状态j，若新状态的内能小于状态i的内能即(Ej<Ei)，则接受新状态j作为新的当前状态；否则，以概率
接受状态j，其中k为Boltzmann常数，这就是通常所说的Metropolis准则。
自然界退火与一般优化问题的相似性
模仿自然界退火现象而得，利用了物理中固体物质的退火过程与一般优化问题的相似性。从某一初始温度开始，伴随温度的不断下降，结合概率突跳特性在解空间中随机寻找全局最优解。
1953年，Kirkpatrick把模拟退火思想与组合优化的相似点进行类比，将模拟退火应用到了组合优化问题中。在把模拟退火算法应用于最优化问题时，一般可以将温度T当作控制参数，目标函数值f视为内能E，而固体在某温度T时的一个状态对应一个解xi，然后算法试图随着控制参数T的降低，使目标函数f（内能E）也逐渐降低，直至趋于全局最小值（退火中低温时的最低能量状态），就像固体退火过程一样。
将模拟退化法应用于最优化问题时，一般将温度T当做控制参数，目标函数值视为内能E，而固体在温度T时的一个状态对应一个解。然后算法试图控制参数T的降低，使目标函数值也逐渐降低，直至趋于全局最小值。
参数说明
退火过程由一组初始参数，即冷却进度表控制，它的核心是尽量使系统达到转平衡，以使算法在有限的时间内逼近最优解。冷却进度表包括：
（1）控制参数的初值T0：冷却开始的温度。
（2）控制参数T的衰减函数：因计算机能够处理的都是离散数据，因此把连续的降温过程离散化成降温过程中的一系列温度点，衰减函数即计算这一系列温度的表达式。
（3）控制参数T的终值Tf (停止准则)。
（4）Markov链的长度Lk：任一温度T 的迭代次数。
基本步骤
算法实质分两层循环，在任一温度随机扰动产生新解，并计算目标函数值的变化，决定是否被接受。由于算法初始温度比较高，这样，使 E 增大的新解在初始时也可能被接受，因而能跳出局部极小值，然后通过缓慢地降低温度，算法就最终可能收敛到全局最优解，具体程序框图见下图。
参数设置
（1）控制参数T的初值T0
求解全局优化问题的随机搜索算法一般都采用大范围的粗略搜索与局部的精细搜索相结合的搜索策略。只有在初始的大范围搜索阶段找到全局最优解所在的区域，才能逐步缩小搜索的范围，最终求出全局最优解。模拟退火算法是通过控制参数T的初值T0和气衰减变化过程来实现大范围的粗略搜索与局部的精细搜索。在问题规模较大时，过小的T0往往导致算法难以跳出局部陷阱而达不到全局最优。一般为100℃。
（2）控制参数 T 的衰减函数
衰减函数可以有多种形式，一个常用的衰减函数是
其中，α 是一个常数，可以取为0.5~0.99，它的取值决定了降温过程的快慢。
（3）Markov链长度
Markov链长度的选取原则是：在控制参数T的衰减函数已经选定的前提下，Lk应能使在控制参数T的每一取值上达到准平衡。从经验上说，对简单的情况可以令Lk=100n，n为问题规模。
算法停止准则：对Metropolis准则中的接受函数
分析可知，在T比较大的高温情况，指数上的分母比较大，而这是一个负指数，所以整个接受函数可能会趋于1，即比当前解 xi 更差的新解 xj 也可能被接受因此就有可能跳出局部极小而进行广域搜索，去搜索解空间的其他区域；而随着冷却的进行，T减小到一个比较小的值时，接收函数分母小了整体也小了，即难于接受比当前解更差的解，也就不太容易跳出当前的区域。如果在高温时，已经进行了充分的广域搜索，找到了可能存在的最好解的区域，而在低温再进行足够的局部搜索，则可能最终找到全局最优了。因此，一般终止温度 Tj 应设为足够小的正数，比如0.01~5。
关于模拟退火算法理论，小编今天先介绍到这里，在接下来这个系列中，小编会用几个简单的例子演示模拟退火算法的具体实现过程。
