模拟退火算法及其应用研究

前言

模拟退火算法及其应用研究

1 前言

非数值算法是基础科学，工程技术和管理科学等领域中常用的一类计算方法，如许多解组合优化问题的算法就是典型的非数值算法，由于这些问题的尤其是其中的NP完全问题本身所固有的计算复杂性，求其精确解的计算量往往随问题规模呈指数型增长，以致使用任何高速计算都需要耗费大量的时间，甚至根本无法实现.因此，研究非数值计算的近似算法及其并行实现的途径具有十分重要的实际意义.

模拟退火算法是近几年提出的一种适合解大规模组合优化问题，特别是解NP完全问题的通用有效近似算法，它与以往的近似算法相比，具有描述简单，使用灵活，运用广泛，运行效率高和较少受初始条件限制等优点，而且特别适合并行计算.因此不仅具有很高的实用价值，而且对推动并行计算的研究也有着重要的理论意义.

组合优化问题的目标函数是从组合优化问题的可行解集中求出最优解.组合优化问题有三个基本要素：变量，约束和目标函数，在求解过程中选定的基本参数称为变量，对变量取值的种种限制称为约束，表示可行方案衡量标准的函数称为目标函数.货郎担问题（TSP）是组合优化问题中最为著名的问题，它易于描述难于求解，自1932年K.Meber提出以来，已引起许多数学家的兴趣，但至今尚未找到有效的求解算法.

货郎担问题，是由爱尔兰数学家Sir William Rowan Hamilton和英国数学家Thomas Penyngton Kirkman在19世纪提出的数学问题，它是指给定n个城市并给出每两个城市之间的距离，旅行商必须以最短路径访问所有的城市一次且仅一次，并回到原出发地，现已证明它属于NP(Non-deterministic Polynomial---非确定多项式)难题[1].历史上的第一个正式用来解决TSP问题的算法诞生于1954年,它被用来计算49个城市的TSP问题.到现在为止,运用目前最先进的计算机技术可解决找出游历24978个城市的TSP问题.TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点.旅行商问题(TSP)由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题[2]

第 1 页 (共 26 页)

模拟退火算法及其应用研究

旅行商问题是一个经典的图论问题：设有n个城市，用cij=1，2，?，n表示.城市cij之间的距离为dij，i，j=1，2，?，n，设所有城市间两两连通，旅行商需要跑遍n个城市去推销他的商品，而这些城市之间的距离都不一样，这推销员需要从其中一个城市出发，而他老板规定他必须把所有城市跑一遍，则TSP问题就是寻找让旅行商遍访每个城市一次且恰好一次的一条回路，且要求其路径总长度为最短.该问题也可以归结为：有N个城市由公路相互连通，从任一城市到另外城市都要支付相应的费用，一个销售商从其中一城市出发，访问其他N－1个城市且仅一次，如何规划一条路径，使该旅行商的花费最少.当城市数量较小时，通过枚举法就可以找出最短的路径，然而随着问题规模的增加，很难找到一个多项式时间复杂度的算法来求解该问题.TSP是一个典型的组合优化问题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较标准.因此，快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值.旅行商问题代表的一类组合优化问题,在物流配送、计算机网络、电子地图、交通诱导、电气布线、VLSI单元布局等方面都有重要的工程和理论价值，引起了许多学者的关注.

TSP是典型的组合优化问题，并且是一个NP-hard问题.TSP描述起来很简单，早期的研究者使用精确算法求解该问题，TSP问题最简单的求解方法是枚举法.它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）！.可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值.求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程[4].常用的方法包括：分枝定界法、线性规划法和动态规划法等，但可能的路径总数随城市数目n是成指数型增长的，所以当城市数目在100个以上一般很难精确的求出其全局最优解.随着人工智能的发展，出现了许多独立于问题的智能优化算法，如蚁群算法、遗传算法、模拟退火、禁忌搜索、神经网络、粒子群优化算法、免疫算法等，通过模拟或解释某些自然现象或过程而得以发展，为解决复杂组合优化问题提供了新的思路和方法[5].模拟退火算法在迭代搜索过程以Boltzmann分布概率接受目标函数的“劣化解”，具有突出的具有脱离局域最优陷阱的能力，同时具有较强的局部搜索能力，从而可以获取目标函数的全局最优解.因为模拟退火算法具有高效、通用、灵活的优点，将模拟退火算法引入TSP求解，可以避免在求解过程中陷入TSP的局部最优解[6].

第 2 页 (共 26 页)

[3]

研究目的和意义

本文首先介绍传统的TSP问题，先对其进行数学描述，又列举TSP问题的应用.之后介绍模拟退火算法，主要介绍其基本思想和关键技术，在此基础上将模拟退火的思想引入TSP的求解，设计出TSP的一种模拟退火算法并用MATABLE语言编程予以实现.

2 选题背景

2.1 题目类型及来源

题目类型：研究论文 题目来源：专题研究

2.2 研究目的和意义

诸如分技定法或整数规划等严格的算法常常不可行.人们常采用的是启发式算法

[7].启发式算法“.分为两类：一是从待解决问题的原始数据结构着手进竹构造性求解，

另一类是迭代改进现有的解.构造性方法是根据待解决问题的特征来设计的，很难推广到不同应用领域：迭代改进方法更为一般.这类算法的结构一般是这样的：从一个初始解开始，产生一个解序列，直到获得满意解为止.新解的产生规则及终止迭代准则决定了一个具体算法.这类算法的不足之处是： 1)算法往往终止于局部最优解.

2)最终解取决于初始解的选择及产生新解的规则.许多启发式算法在做迭代改进时都选择最快的减少目标函数值的策略，也就是所谓的贪一b策略.这种“心”算法往往导致陷入局部最优解，而不是全局最优解[8].

为了改善迭代型启发算法的行为，有时选择一批初始解，然后做相同的迭代以提高获得全局最优解的概率.也可借助于随机搜索的算法[9]，其特点是随机的产生下一新解.若新解比当前解的值更低，则将新解作为暂存解.如果最优解与总解的比例越高，找到最优解的概率也就越大.故当最优解的数目很大时，随机搜索算法的功能还是很好的.作为一种通用的随机搜索算法，模拟退火(Simulated Annealing，以下简称SA)算法有着更好的渐进行为.它是近年来提出的一种适合解大规模组合优化问题通用而

第 3 页 (共 26 页)

模拟退火算法及其应用研究

有效的近似算法.它与以往的近似算法相比，具有描述简单、使用灵活、运用广泛、运行效率高和较少受初始条件约束等优点，而且特别适合并行计算，因此具有很高的实用价值.随着计算机技术的发展和普及，最优化理论和方法在诸多领域都得到了迅速发展和推广.目前，它已成为现代科学技术中一个必不可少、重要的数学手段和方法，其应用和发展为诸多领域中非线性问题的解决，提供了孥实而有力的理论基础和有效的方法.本论文利用模拟退火算法的高效性和优越性，将其用在货郎担问题的求解中.

2.3 国内外现状和发展趋势与研究的主攻方向

模拟退火算法(SA)在理论上已得到证明，它可以达到全局极小值，所以它备受专家与学者的青睐.目前，关于模拟退火算法的研究通常分为两类.笫一类是基于有限状态奇异马尔可夫链的有关理论[11]，给出模拟退火算法的某些关于理想收敛模型的充分条件或充要条件，这些条件在理论上证明了当退火三原则(初始温度足够高、降温速度足够慢、终止温度足够低)满足时[12]，模拟退火算法以概率l达到全局最优解；第二类是针对某些具体问题，给出了模拟退火算法的很多成功应用.事实上，正是由于专家和学者对该算法的钻研，才让该算法从经典的模拟退火算法走到了今天的多样型的模拟退火算法，比如快速模拟退火算法，使得该算法的速度和收敛性都得到较大提高，再比如适应性的模拟退火算法，使得该算法具有智能性；再比如现在有学者提到的遗传一模拟退火算法，就是将遗传算法和模拟退火算法二者的优越性结合起.不能忽略的是每种算法的提出都与其应用范围紧密结合[13]，这样才使得改进的算法在其应用领域具有较好的适用性.由于模拟退火算法(SA)从理论上可以达到全局极小值，所以对该算法的研究更有实际意义，众多学者正在努力钻研将其一般化，使其具有普遍适用性.

3 模拟退火算法的一些知识

3.1 模拟退火算法的描述

模拟退火算法(Simulated Annealing)最早见于IBM托马斯.J.沃森研究中心的S.Kirkpatrick 等人的文章, 他们在对组合优化进行研究后, 根据迭代改进的思想提出了“模拟退火算法”,模拟退火算法具有很强的局部搜索能力.模拟退火算法来源于固体退火原理, 将固体加温至充分高, 再让其缓慢降温(即退火), 使之达到能量

第 4 页 (共 26 页)

模拟退火算法的描述

最低点.反之, 如果急速降温(即淬火)则不能达到最低点.加温时, 固体内部粒子随温升变为无序状, 内能增大, 而缓慢降温时粒子渐趋有序, 在每个温度上都达到平衡态,最后在常温时达到基态, 内能减为最小.根据Metropolis 准则,粒子在温度T 时趋于平衡的概率为exp(- E/(kT)), 其中E 为温度T 时的内能, E 为其改变量, k 为Boltzman 常数.用固体退火模拟组合优化问题, 将内能E 模拟为目标函数值f, 温度T 演化成控制参数t, 即得到解组合优化问题的模拟退火算法:由初始解i 和控制参数初值t 开始, 对当前解重复产生“新解→计算目标函数差→接受或舍弃”的迭代, 并逐步衰减t 值, 算法终止时的当前解即为所得近似最优解[14], 这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程.退火过程由冷却进度表(Cooling Schedule)控制[15], 包括控制参数的初值t 及其衰减因子a、每个t 值时的迭代次数L 和停止条件c.所以我们可以通过上面的思想写出解决TSP 问题的模拟退火算法.步骤如下: (1) 初始化:初始温度T(充分大), 初始解状态s(随机选取一条TSP 路线, 算出走完此路线的长度Cost(s)作为评价函数, 这是算法迭代的起点), 每个T 值的迭代次数L;

(2) 对k=1 至k=L 做第(3)至第6 步;

(3) 产生新解s′(一般利用2- opt 算法来产生新的路径); (4) 计算增量Cost=Cost(s')- Cost(s), 其中Cost(s)为评价函数;

(5) 若t'<0 则接受s'作为新的当前解, 否则以概率exp(- t'T)接受s'作为新当前解; (6) 如果满足终止条件则输出当前解作为最优解, 结束程序.终止条件通常取为连续若干个新解都没有被接受时终止算法;

(7) T 逐渐减少, 且T 趋于0, 然后转第2 步运算.

模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其缓慢降温(即退火)，使之达到能量最低点.反之，如果急速降温(即淬火)则不能达到最低点.加温时，固体内部粒子随温升变为无序状，内能增大，而缓慢降温时粒子渐趋有序，在

第 5 页 (共 26 页)

模拟退火算法及其应用研究

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

3.2 模拟退火算法的基本思想

模拟退火算法可以分解为解空间、目标函数和初始解3部分.其基本思想是： (1)初始化：初始温度T(充分大)，初始解状态s(是算法迭代的起点)，每个T值的迭代次数L；

(2)对k=1，??，L做第(3)至第6步； (3)产生新解s'；

(4)计算增量cost=cost(s')-cost(s)，其中cost(s)为评价函数；

(5)若t'?0则接受s'作为新的当前解，否则以概率exp(-t'/T)接受s'作为新的当前解；

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

(7)T逐渐减少，且T趋于0，然后转第2步运算.

3.3 模拟退火算法的关键技术

（1）新解的产生和接受

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

第 6 页 (共 26 页)

模拟退火算法的基本思想

选取有一定的影响.②计算与新解所对应的目标函数差.因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算.事实表明，对大多数应用而言，这是计算目标函数差的最快方法.③判断新解是否被接受.判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则：若t'?0则接受S'作为新的当前解S，否则以概率exp(-t'/T)接受S'作为新的当前解S.④当新解被确定接受时，用新解代替当前解.这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可.

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

模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下3点：①温度T的初始值设置.温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一.初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响.实际应用过程中，初始温度一般需要依据实验结果进行若干次调整.②温度衰减函数的选取.衰减函数用于控制温度的退火速度，一个常用的函数为：

T(t?1)??T(t) (1) 式中是一个非常接近于1的常数，t为降温的次数.③马尔可夫链长度L的选取.通常的原则是：在衰减参数T的衰减函数已选定的前提下，L的选取应遵循在控制参数的每一取值上都能恢复准平衡的原则.

3.4 Metropolis准则

固体在恒定温度下达到热平衡的过程可以用Morte Carlo算法方法加以模拟，虽然该方法简单但必须大量采样得到比较精确的结果，因而计算量很大.鉴于物理系统倾向于能量较低的状态，而热运动又防碍它准确落到最低态.采样时着重选取那些有重要贡献的状态则可较快达到较好的结果.因此，MetropoliS等在1953年提出了重要的采样法，即以概率接受新状念.其具体描述先给定以粒子相对位置表征的初始状态

第 7 页 (共 26 页)

模拟退火算法及其应用研究

i0作为固体的当前状态，该状态的能量为Ei0，然后用摄动装置使随机选取的某个粒子的位移随机地产生一微小变化，得到一个新的状态J，新状态的能量是Ej，如果Ej?Ei0则接受新状态j为当前状态：否则，考虑到热运动的影响，该新状态是否“接受”要依据粒子处于该状态的几率来判断.由统计力学知道，物体退火过程的统计性质服从下式所示的正则分布：

P{E=Ej}=

?E1exp(i) (2) Z(T)kT式中，exp（

?Ei）称为Boltzmann因子，T是绝对温度，k是Boltamann常熟，Z(T)kT为概率分布的标准因子

Z(T)=?exp(?Ei) (3) kT由式(2.2)可知，物体处于状态i和状态j的几率的比值等于相应的Boltzmann因子的比值，即

r=exp(

Ei?EjkT) (4)

r是一个小于1的数.用随机数发生器产生一个在[0，1]区间均匀分布的随机数?，若r>?，则接受新状态J，反之，则舍弃.

如果新状态j可以接受，那么就以j.取代i成为当前状态，重复以上新状态的产生过程.在大量迁移(固体状态的变换称为迁移)后，系统趋于能量较低的平衡状态.

通过对上述物理现象的模拟，假定L(S，f)存在邻域以及相应解的产生机制，

f(x)、f(y)分别为对应于解i，j的目标函数值.由解i过渡到解j的接受概率用以下的

MetropoliS准则确定：

?1,f(i)?f(j) P(tk)=P(i?j)=? (5) f(i)?f(j)?),f(i)?f(j)?exp(tk?合理的停止准则既要确保算法收敛于某一近似解，又要使最终解具有一定量.从有限

第 8 页 (共 26 页)

模拟退火算法的基本思想

的CPU时间考虑，Nahar等人提出用事先确定好的控制参数的个数，亦即Markov链的个数或迭代次数k作为停止准则.他们选取的迭代次数是6～50次.此类用迭代次数构造的停止准则虽能在等参数的协同下，直接控制算法进程的CPU时间.但对最终解质量的控制很弱，也缺乏灵活性.

控制模拟退火的渐进收敛特性给人们以新的启示：算法收敛于最优解集是随控制参数t值的缓慢减小而渐进进行.只有在t“充分小”时，才有可能得出高质的最优解.因此，t“充分小”在某种程度上可以替代“最终解质量”的判据，为停止准则所用.一是让控制参数t值小于某个充分小正数e，直接构成停止准则的判断式t

常用的选取停止准则的另一个途径是不改进规则控制法，以算法进程所得到的某些近似解为衡量标准，判断算法当前解的质量是否持续得到明显提高，从而确定是否终止算法，如在若干个相继的Markov链中解无任何变化就可以终止算法.这类方法同样兼顾最终解质量和CPU时间，在^和等参数的配合下，不仅可望得到高质量的最终解，而且对于CPU时间有相对控制作用(即CPU时间随问题规模的增大而增大)，解质相对稳定.

3.5 组合优化与物理退火的相似性

引进模拟退火算法(SA)的原动力是基于这样的模拟：具有大规模解空叫的组合优化问题和带有多自由度的物理系统显示出类似的性质.该算法用于解决组合优化问题的出发点是鉴于物理中晶体物质的退火过程与一般组合优化问题的相似性.

在对固体物质进行退火处理时，通常是先对它加温，使其熔化，让其中的粒子可以自由运动，然后随着温度缓慢下降，粒子逐渐形成低能态的晶格.若在凝结点附近的温度下降速率过快，则不能达这个能量最低态，而是以一种耋强的或者以一种非晶的具有高能量的亚稳态结束.因此，这个过程的本质是慢速冷却，让粒子有充分

第 9 页 (共 26 页)

模拟退火算法及其应用研究

的时间失去可动性，进行重新分布，这是退火的技术定义，立能确保粒子达到低能态势.对于组合优化问题来说，也有类似的过程，组合优化问题解空间的每一点都代表一个具有不同目标函数的解.所谓优化，就是在解空间寻找函数最小解的过程.若把函数看成能量函数，把控制参数视为温度，解空间作为状态空间，那么模拟退火算法(SA)寻找基态的过程就是求目标函数极小值的优化过程，因此，基于MetropoliS接受准则的最优化过程与物理退火过程存在一定的相似性.将这种相似性归纳在下表2.1中.

表1 组合优化与物理退火的相似性

组合优化 解 物理退火 粒子状态 组合优化 Metropolis抽样过程 最优解 态 设定初始温度 众所周知，处于热平衡的物理系统的各种可能状态服从波兹曼(80ltzmann)概率分布，即如式(2)所示.

这里先研究由式(2)所确定的函数随T的变化趋势，选定两个能量E1

P(E?E1)-P(E?E2) =

EE?E11exp(?1)[1?exp(?2)] (6) Z(T)kTkTE2?E1)?1,?T?0,因此式(6)大于零总成立.kT物理退火 等温过程 能量最低控制参数的下降 冷却 熔解过程 目标函数 能量 式（6）中恒存在exp(-

第 10 页 (共 26 页)

组合优化和物理退火的相似性

在同一温度下，(6)式表示分子停留在能量小的状态的概率比停留在能量大的状态的概率大.当温度相当高时，(2)式的概率分布使得每个状态的概率基本相同，

?P{E?E(r)}

?TE(s)E(r)E(s)exp{?}exp{?}?kTkT[E(i)?s?D] (7) =2Z(T)Z(T)kT当r为状态D中能量最低的状态时，有:

?P{E?E(r)}?0

?T所以，P{E?E(r)}关于温度T是单调下降的.又有： P{E?E(r)}?1E(r)1 exp(?)?Z(T)kT|D0?R|其中，D0是具有最低能量的状态集合.令T?0时，有

R=

N?D,E(N)?E(r)?exp(?E(s)?E(r))?0 （8） kT亦有P{E?E(r)}?1. |D0|可见，当温度趋于0时，式(2)决定的概率渐进1／|D0|.据此可以得到，在此温度趋于0时，分予停留在最低能量状态的概率接近于1.综合上面的讨论，分子在能量最低的状态的概率变化可以由图1(a)所示.对于能量最小的状态，由式(3)和分子在能量最小状态的概率是单调减小可知，在温度较高时，分子处于这些状态的概率在l／|D|：附近，依赖于状念的不同，可能超过1／|D |.由式(7)和(8)可知存在一个温度t，使式(7)决定的概率在(0，1)使单调升的：再出式(7)可知，当温度趋于O时式(2)定义的概率趋进于0.

第 11 页 (共 26 页)

模拟退火算法及其应用研究

概率变化曲线图见图1(b).由上面的讨论可知，在温度很低时{T?O}，能量越低的状态的概率值越高.在极限状况，只有能量最低的点概率不为零.

(a)能量在最低状态 (b)在非能量最低状态

图 1 波兹曼函数曲线

3.6 整体最优解，邻域结构与局部最优解

定义2.1：设(S，f)是组合优化问题的一个实例，iopt?S，若f(iopt)≤f(i)，对所有i∈S成立，称iopt为最小化问题minf(i)，i∈S的整体最优解.

定义2.2：设(s，f)是组合优化问题的一个实例，则一个领域结构是一个映射N：S?2n，其中2n表示S的所有子集组成的集合，其涵义是，对每一个解i∈S，有一个解的集合Si?S，这些解在种意义上是“邻近”i的，集合S.称为i的邻域，每个J∈S，称为i的一个邻近解.

定义2.3：设(S，f)是组合优化问题的一个实例，而N是一个邻域结构，i∈sj，称i为最小化问题minf(x)，i∈S，的局部最优解.即

f(i)?f(j),对所有j∈S，成立

^

第 12 页 (共 26 页)

局部搜索算法的算法描述

4 局部搜索算法

局部搜索算法是一种通用的近似算法，其基本法则是在邻近解中迭代，使目标函数逐步优化，直至不能再优为止.局部搜索法灵活、简便，能求解多种组台优化问题，并能给出较好的近似解.

4.1 局部搜索算法的算法描述

局部搜索算法从一个初始解i0∈S开始，然后运用一个产生器，持续的在解i(称为当前解)的邻域S中搜索比i更优的解，若找到比i更优的解，就用这个解取代i成为当前解，再对当前解的领域继续搜索：直至满足算法终止条件，当前解就是算法的最终解.下面给出伪C语言描述的求解最小化问题的局部搜索算法. 算法2.1最小化问题的局部搜索算法 LOCAL—SEARCH() {

INITALIZE(i.，)： i=i.： do {

for(i=j)j∈S

if(f(J)

while(S内还有解未被搜索到)： }

4.2 局部搜索算法的算法的特点

由算法描述可知，局部算法具有以下特点：

(1)通用性：只要给定组合优化问题的实例(s，f)，产生器和邻域结构，就能实现算法；

(2)灵活性：可以选用不同机制的产生器，设定不同复杂程度的邻域结构： (3)最终解可能是某个局部最优解：在大多数情况下，无法设定恰当的邻域结构，所以不能保证最终解的质量；

(4)最终解的质量依赖初始解的选择：对大多数组合优化问题来说，不存在选择初始

第 13 页 (共 26 页)

模拟退火算法及其应用研究

解的准则，算法执行时的初始解常常是随机选取，这可能导致较差的最终解.

4.3 改善局部搜索算法性能的途径

在保持局部搜索算法通用性和灵活性的前提百，以下方案有利于提高最终解的质量：

(1)对大量初始解执行算法，从中选优；

(2)引入更复杂的邻域结构，使算法能对解空间的更大范围进行搜索：

(3)改变局部搜索算法只能接受优化解迭代的准则，在一定限度内接受恶化解.第一种方案由于受至n运行时间的限制，不可能对所有解施行，因而最终解仍然可能是某个局部最优解；第二种方案需要对求解问题的透彻了解，而专注于某类问题又将使局部搜索算法失去通用性而成为一种专用算法；第三种方案需要确定新的接受准则.第三种方案使得局部搜索算法演变为一种新的算法——模拟退火算法(SA).

5 货郎担问题的模拟退火算法的实现

5.1 货郎担问题的描述

货郎担问题，是威廉·哈密尔顿爵士和英国数学家克克曼(T.P.Kirkman)于19世纪初提出的一个数学问题，也是著名的组合优化问题.问题是这样描述的：一名商人要到若干城市去推销商品，已知城市个数和各城市间的路程（或旅费），要求找到一条从城市1出发，经过所有城市且每个城市只能访问一次，最后回到城市1的路线，使总的路程（或旅费）最小.TSP刚提出时，不少人认为这个问题很简单.后来人们才逐步意识到这个问题只是表述简单，易于为人们所理解，而其计算复杂性却是问题的输入规模的指数函数，属于相当难解的问题.这个问题的数学描述为：假设有n个城市，并分别编号，给定一个完全无向图G=(V,E),V={1，2，??，n}，n>1.其每一边(i,j)?E有一非负整数耗费Cij(即上的权记为Cij,i,j ?V).并设

?1，边（i，j）在最优线路上 (9) Xij = ??0，其他G的一条巡回线路是经过V中的每一个顶点恰好一次的回路.一条巡回路线的耗费是这条路线上所有边的权值之和.TSP问题就是要找出G的最小耗费回路.

第 14 页 (共 26 页)

货郎担问题的描述

人们在考虑解决这个问题时，一般首先想到的最原始的一种方法就是:列出每一条可供选择的路线(即对给定的城市进行排列组合)，计算出每条路线的总里程，最后从中选出一条最短的路线.假设现在给定的4个城市分别为A、B、C和D，各城市之间的耗费为己知数，如图2所示.我们可以通过一个组合的状态空间图来表示所有的组合 如图

C D C A A B B B D C D B

C D

D A 图2 定点带权图 图 3 TSP问题解空间树

从图中不难看出，可供选择的路线共有6条，从中很快可以选出一条总耗费最短的路线：顶点序列为（A,C,B,D,A）.由此推算，若设城市数目为n时，那么组合路径数则为(n-1)!.很显然，当城市数目不多时要找到最短距离的路线并不难，但随着城市数目的不断增大，组合路线数将呈指数级数规律急剧增长，以至达到无法计算的地步，这就是所谓的“组合爆炸问题”.假设现在城市的数目增为20个，组合路径数则为(20-1)!≈1.216×1017，如此庞大的组合数目，若计算机以每秒检索1000万条路线的速度计算，也需要花上386年的时间[6].

5.2货郎担问题的应用

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

第 15 页 (共 26 页)

模拟退火算法及其应用研究

1.电路板钻孔进度的安排.机器在电路板上钻孔的调度问题是TSP应用的经典例子，在一电路板上打成百上千个孔，转头在这些孔之间移动，相当于对所有的孔进行一次巡游.把这个问题转化为TSP，孔相当于城市，转头从一个孔移到另一个孔所耗的时间相当于TSP中的旅费.

2.车辆选路.一个经典的路由问题是在一个网络上发现从源节点到一个目的节点的最佳交通线路，使与距离成比例的流动费用降低到最小.这个问题的关键是在交通网络上计算从源节点到目的节点之间的最短路径.对这个最小费用流动问题进行扩展，就构成TSP问题，在这个问题中，车辆从源点出发访问多个目的地并且最后回到源点.

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

更重要的是，TSP提供了一个研究组合优化问题的理想平台.很多组合优化问题，比如背包问题、分配问题、车间调度问题，和TSP同属NP-Hard类，它们难度同等，如果其中一个能用多项式确定性算法解决，那么其他所有的NP-Hard类问题也能用多项式确定性算法解决.很多方法都是从TSP发展起来的，后来推广到其他NP-Hard类问题上去.

5.3 TSP算法的描述

（1）TSP问题的解空间和初始解

TSP的解空间S是遍访每个城市恰好一次的所有回路，是所有城市排列的集合.TSP问题的解空间S可表示为{1,2,?,n}的所有排列的集合，即S = {(c1,c2,?,cn) | ((c1,c2,?,cn)为{1,2,?,n}的排列）}，其中每一个排列Si表示遍访n个城市的一个路径，ci= j表示在第i次访问城市j.模拟退火算法的最优解与初始状态无关，故初始解为随机函数生成一个{1,2,?,n}的随机排列作为S0.

（2）目标函数

TSP问题的目标函数即为访问所有城市的路径总长度，也可称为代价函数：

第 16 页 (共 26 页)

货郎担问题的描述

C?c1,c2,…，cn???d?ci,ci?1??d?c1,cn? (10)

i?1n?1 现在TSP问题的求解就是通过模拟退火算法求出目标函数C(c1,c2,?,cn)的

'''最小值，相应地，s'= (c1',c2)即为TSP问题的最优解.（3）新解产生 ,c3?cn新解的产生对问题的求解非常重要.新解可通过分别或者交替用以下2种方法产

生：

①二变换法：任选序号u，v(设u??v??n)，交换u和v之间的访问顺序，若交换前的解为si= (c1,c2,?,cu,?,cv,?,cn),交换后的路径为新路径，即：

s1'= (c1,?,cu-1,cv,cv-1,?,cu+1,cu,cv+1,?,cn)

②三变换法：任选序号u,v和ω(u≤v??ω)，将u和v之间的路径插到ω之后访问，若交换前的解为si= (c1,c2,?,cu,?,cv,?,cω,?,cn)，交换后的路径为的新路径为：

s1'= (c1,?,cu-1,cv+1,?,cω,cu,?,cv,c??1,?,cn) （4）目标函数差

计算变换前的解和变换后目标函数的差值： Δc1'= c(s1')- c(si) （5）Metropolis接受准则

根据目标函数的差值和概率exp(-ΔC'/T)接受s1'作为新的当前解si，接受准则：

p?{?????1?????????????????,?????c'?0exp(??c'/T)?????????c'?0

5.4 TSP算法的流程

根据以上对TSP的算法描述，可以写出用模拟退火算法解TSP问题的流程图4所示：

第 17 页 (共 26 页)

模拟退火算法及其应用研究

选择初始路径X0 确定初始温度T0 当前路径 Xi=X0 当前温度 Ti=T0 从Xi的邻域中随机选择 与Xi的路程差 Xj计算Xj f=f(Xj)-f(Xi) ?f<=0 exp(??f/Ti) ?random(0.1) 当前路径Xi=Xj 跳出内循环 当前温度Ti下降 跳出外循环 结束

图 4 TSP的模拟退火流程图

第 18 页 (共 26 页)

模拟退火算法及其应用研究

5.5 模拟退火算法的源程序

function [MinD,BestPath]=MainAneal(CityPosition,pn) function [MinD,BestPath]=MainAneal2(CityPosition,pn)

%CityPosition_31=[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;...

% 3238 1229;4196 1044;4312 790;4386 570;3007 1970;2562 1756;...

% 2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;... % 3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376;... % 3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;2370 2975]; %T0=clock

global path p2 D;[m,n]=size(CityPosition);TracePath=zeros(1e3,m); Distance=inf*zeros(1,1e3);

D = sqrt((CityPosition( :, ones(1,m)) - CityPosition( :, ones(1,m))').^2 +... (CityPosition( : ,2*ones(1,m)) - CityPosition( :,2*ones(1,m))').^2 ); for i=1:pn

path(i,:)=randperm(m);%构造一个初始可行解 end

t=zeros(1,pn); p2=zeros(1,m);

iter_max=100;%input('请输入固定温度下最大迭代次数iter_max=' );

m_max=5;%input('请输入固定温度下目标函数值允许的最大连续未改进次数m_nax=' ) ; T=1e5; N=1;

tau=1e-5;%input('请输入最低温度tau=' ); %nn=ceil(log10(tau/T)/log10(0.9));

while T>=tau%&m_num

m_num=1;%某固定温度下目标函数值连续未改进次数计算器 %iter_max=100

第 19 页 (共 26 页)

模拟退火算法及其应用研究

%m_max=10;?il(10+0.5*nn-0.3*N);

while m_num

%MRRTT(Metropolis, Rosenbluth, Rosenbluth, Teller, Teller)过程: for i=1:pn

Len1(i)=sum([D(path(i,1:m-1)+m*(path(i,2:m)-1)) D(path(i,m)+m*(path(i,1)-1))]);

[path2(i,: )]=ChangePath2(path(i,: ),m);%更新路线 Len2(i)=sum([D(path2(i,1:m-1)+m*(path2(i,2:m)-1)) D(path2(i,m)+m*(path2(i,1)-1))]); end %Len1 %Len2

%if Len2-Len1<0|exp((Len1-Len2)/(T))>rand R=rand(1,pn);

%Len2-Len1R if

find((Len2-Len1R)~=0)

path(find((Len2-Len1R)~=0), : )=path2(find((Len2-Len1R)~=0),

);

Len1(find((Len2-Len1R)~=0))=Len2(find((Len2-Len1R)~=0));

[TempMinD,TempIndex]=min(Len1);%TempMinDTracePath(N,: )=path(TempIndex,: ); Distance(N,: )=TempMinD; N=N+1; %T=T*0.9;m_num=0; else m_num=m_num+1;end iter_num=iter_num+1; end T=T*0.9 %m_num,iter_num,N end

[MinD,Index]=min(Distance); BestPath=TracePath(Index,: )

第 20 页 (共 26 页)

模拟退火算法的源程序

disp(MinD) %T1=clock %更新路线子程序

function [p2]=ChangePath2(p1,CityNum) global p2;

while(1) R=unidrnd(CityNum,1,2); if abs(R(1)-R(2))>1 break;end end R=unidrnd(CityNum,1,2); I=R(1);J=R(2);

%len1=D(p(I),p(J))+D(p(I+1),p(J+1)); %len2=D(p(I),p(I+1))+D(p(J),p(J+1)); if I

p2(1:I)=p1(1:I); p2(I+1:J)=p1(J:-1:I+1);

p2(J+1:CityNum)=p1(J+1:CityNum); else

p2(1:J)=p1(1:J); p2(J+1:I)=p1(I:-1:J+1);

p2(I+1:CityNum)=p1(I+1:CityNum); end

输入参数：inputcities的作用是将n个城市的坐标表示两行和n列，并且传递给simulatedannealing作为新的参数.initial_temperature则是开始模拟退火过程的起始温度.cooling_rate是模拟退火过程的冷却速率，并且它是n个城市的可接受的距离.numberofcitiestoswap指定用于交换城市对数量的最大值.随着温度的降低，用于交换的城市对也减少，最终达到一对城市.

5.6 仿真分析与评价

为了验证用MATLAB实现的模拟退火算法的有效性，选择29个点作为仿真研究对象，它们在坐标平面的坐标(Location)如表5所示

第 21 页 (共 26页)

模拟退火算法及其应用研究

表 5 29个城市的坐标

城市序号 X坐标 Y坐标 1 1150.0 1760.0 2 630.0 1660.0 3 40.0 2090.0 4 750.0 1100.0 5 750.0 2030.0 6 1030.0 2070.0 7 1650.0 650.0 8 1490.0 1630.0 9 790.0 2260.0 10 710.0 1310.0 城市序号 X坐标 Y坐标 11 840.0 550.0 12 1170.0 2300.0 13 970.0 1340.0 14 510.0 700.0 15 750.0 900.0 16 1280.0 1200.0 17 230.0 590.0 18 460.0 860.0 19 1040.0 950.0 20 590.0 1390.0 城市序号 X坐标 Y坐标 21 830.0 1770.0 22 490.0 500.0 23 1840.0 1240.0 24 1260.0 1500.0 25 1280.0 790.0 26 490.0 2130.0 27 1460.0 1420.0 28 1260.0 1910.0 29 360.0 1980.0 运行结果如图5：

图 5 运行结果一

第 22 页 (共 26 页)

仿真分析与评价

初始温度为2000，交换城市数为2，冷却速率为0.97，29个城市的TSP运行结果如上图，该优化路径的总路程近似为9122.

图 6 运行结果二

第 23 页 (共 26 页)

模拟退火算法及其应用研究

初始温度为2000，交换城市数为2，冷却速率为0.97，29个城市的TSP运行结果 如上图，该优化路径的总路程近似为9703.

图 7 运行结果三

第 24 页 (共 26 页)

参考文献

参考文献

[1]康立山,谢云，尤矢勇，罗祖华.非数值并行算法（第一册）—模拟退火算法[M].北京:科学出版社,1994：1～242

[2]祝崇俊,刘民,吴澄.供应链中车辆路径问题的研究进展及前景[J].CMS.2001:1~6 [3]陈文兰,戴树贵.旅行商问题算法研究综述[J].滁州学院学报,2006:1~6

[4]Z.米凯利维茨.演化程序—遗传算法和数据编码的结合[M].科学出版社,2007:1007~1008 [5]曲晓丽,潘 昊,柳向斌. 旅行商问题的一种模拟退火算法求解[M].现代电子技术,2007:1~78 [6]吴小菁. 求解旅行商问题的模拟进化算法[J].福建金融管理干部学院学报,2008:55~57. [7]万军洲. 基于模拟退火技术的旅行商问题求解算法[J].软件导刊,2006:88~89.

[8]曲强，陈雪波.基于MATLAB的模拟退火算法的实现[J].鞍山科技大学学报,2003:197~198 [9] 刘朝霞,刘景发.一种求解圆形Packing问题的模拟退火算法[J].计算机工程，2011:141～144 [10] 赵越.模拟退火算法求解指派问题新探[J].吉林建筑工程学院学报,2011,61～63

[11] 杨瑞明. 模拟退火算法在带约束的送货路线优化设计中的应用[J].计算技术与自动化,2011:100～104

[12] 赵卫. 模拟退火遗传算法在车间作业调度中的应用[J].计算机仿真,2011，361～364 [13] 谢云，尤矢勇，一种并行模拟退火算法[J].武汉大学学报，并行计算专刊，1991，49～59 [14] 谢云，模拟退火算法并行实现的若干策略[J].武汉大学学报，并行计算专刊，1991,84～91 [15] 何军，解优化问题的退火回火算法[J].武汉大学学报，并行计算专刊，1991,43～48

第 25 页 (共 26 页)

模拟退火算法及其应用研究

致谢

本论文是在赵天玉老师的指导下完成的，在完成过程中还得到了许多其他人的 帮助和支持，值此论文完成之际，我由衷地感激所有给予我指导、关心、帮助和支持的老师、同学、朋友们.

首先，我要感谢我的指导老师赵天玉老师.从我论文开始的查阅文献、论文的选题、修改到最后的定稿，都得到了赵老师悉心的指导和无微不至的关怀.赵老师严谨的治学态度、敏锐的洞察力、认真负责的工作态度和诲人不倦的师长风范给我留下了深刻的印象，他教导我进行模拟退火算法的研究及其应用，指导我完成了这一篇毕业论文，帮助我在学习中不断提高分析问题和解决问题的能力，这些都将使我受益终生.

感谢信计学院的授课老师和与我一起学习的同学，没有他们的谆谆教诲和热心帮助，我不可能顺利地完成本次毕业论文设计.

最后，我还要感谢在百忙之中参加我的论文答辩的各位老师！

第 26 页 (共 26 页)

模拟退火算法及其应用研究

致谢

本论文是在赵天玉老师的指导下完成的，在完成过程中还得到了许多其他人的 帮助和支持，值此论文完成之际，我由衷地感激所有给予我指导、关心、帮助和支持的老师、同学、朋友们.

首先，我要感谢我的指导老师赵天玉老师.从我论文开始的查阅文献、论文的选题、修改到最后的定稿，都得到了赵老师悉心的指导和无微不至的关怀.赵老师严谨的治学态度、敏锐的洞察力、认真负责的工作态度和诲人不倦的师长风范给我留下了深刻的印象，他教导我进行模拟退火算法的研究及其应用，指导我完成了这一篇毕业论文，帮助我在学习中不断提高分析问题和解决问题的能力，这些都将使我受益终生.

感谢信计学院的授课老师和与我一起学习的同学，没有他们的谆谆教诲和热心帮助，我不可能顺利地完成本次毕业论文设计.

最后，我还要感谢在百忙之中参加我的论文答辩的各位老师！

第 26 页 (共 26 页)

本文来源：https://www.bwwdw.com/article/7aep.html