模拟退火算法探讨

开篇：润墨网以专业的文秘视角，为您筛选了一篇模拟退火算法探讨范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

旅行商问题是组合优化领域里的一个典型的、易于描述却难以处理的问题.在解决旅行商问题的诸多方法中，模拟退火算法是一种通用且有效的近似算法.论文给出解决旅行商问题的一种比较精确的算法――模拟退火算法。

一、模拟退火算法

模拟退火算法由Kirk Patrick于1982提出，他将退火思想引入到组合优化领域，提出一种求解大规模组合优化问题的方法，对于NP-Hard类组合优化问题尤其有效。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其缓慢降温（即退火），使之达到能量最低点。反之，如果急速降温（即淬火）则不能达到最低点.加温时，固体内部粒子随温升变为无序状，内能增大，而缓慢降温时粒子渐趋有序，在每个温度上都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度时趋于平衡的概率为，其中为温度时的内能，为其改变量，为Boltzmann常数，用固体退火模拟组合优化问题，将内能模拟为目标函数值，温度演化成控制参数，即得到解组合优化问题的模拟退火算法：由初始解和控制参数初值开始，对当前解重复产生“新解计算目标函数差接受或舍弃”的迭代，并逐步衰减值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程.退火过程由冷却进度表控制，包括控制参数的初值及其衰减因子、每个值时的迭代次数和停止条件。

（一）基本思想

模拟退火算法可以分解为解空间、目标函数和初始解三部分.其基本思想是：

①初始化：初始温度（充分大），初始解状态（算法迭代的起点），每个值的迭代次数；

②对做第③至第⑥步；

③产生新解；

④计算增量，其中为评价函数；

⑤若，则接受作为新的当前解，否则以概率接受作为新的当前解；

⑥如果满足终止条件则输出当前解作为最优解，结束程序.终止条件通常取为连续若干个新解都没有被接受时终止算法；

⑦逐渐减少，且趋于0，然后转第2步运算。

（二）关键技术

①新解的产生和接受

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

a、由一个函数从当前解产生一个位于解空间的新解，为便于后续的计算和接受，减少算法耗时，常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响；

b、计算与新解所对应的目标函数差，因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算.事实表明，对大多数应用而言，这是计算目标函数差的最快方法；

c、判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则：若则接受作为新的当前解，否则以概率接受作为新的当前解；

d、当新解被确定接受时，用新解代替当前解。这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可，此时，当前解实现了一次迭代，可在此基础上开始下一轮试验.而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验；

模拟退火算法与初始值无关，算法求得的解与初始解状态（是算法迭代的起点）无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率收敛于全局最优解的全局优化算法；同时模拟退火算法具有并行性.

②参数控制问题

模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下3点：

a、温度的初始值设置.温度的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一.初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响.实际应用过程中，初始温度一般需要依据实验结果进行若干次调整；

b、温度衰减函数的选取.衰减函数用于控制温度的退火速度，一个常用的函数为：

（2-2）

式中是一个非常接近于1的常数，为降温的次数；

c、马尔可夫链长度的选取.通常的原则是：在衰减参数的衰减函数已选定的前提下，的选取应遵循在控制参数的每一取值上都能恢复准平衡的原则。

（作者单位：黄淮学院数学科学系）