1、 前言 第 1 页 (共 70 页 ) 模拟退火算法及其应用研究 1 前言 非数值算法是基础科学，工程技术和管理科学等领域中常用的一类计算方法，如许多解组合优化问题的算法就是典型的非数值算法，由于这些问题的尤其是其中的NP 完全问题本身所固有的计算复杂性，求其精确解的计算量往往随问题规模呈指数型增长，以致使用任何高速计算都需要耗费大量的时间，甚至根本无法实现 .因此，研究非数值计算的近似算法及其并行实现的途径具有十分重要的实际意义 . 模拟退火算法是近几年提出的一种适合解大规模组合优化问题，特别是解 NP完全问题的通用有效近似算法，它与以往的近似算法相 比，具有描述简单，使用灵活，运用广泛，运
2、行效率高和较少受初始条件限制等优点，而且特别适合并行计算 .因此不仅具有很高的实用价值，而且对推动并行计算的研究也有着重要的理论意义 . 组合优化问题的目标函数是从组合优化问题的可行解集中求出最优解 .组合优化问题有三个基本要素：变量，约束和目标函数，在求解过程中选定的基本参数称为变量，对变量取值的种种限制称为约束，表示可行方案衡量标准的函数称为目标函数 .货郎担问题（ TSP）是组合优化问题中最为著名的问题，它易于描述难于求解，自 1932年 K.Meber提出以来，已引起许多数 学家的兴趣，但至今尚未找到有效的求解算法 . 货郎担问题， 是 由爱尔兰数学家 Sir William Rowa
3、n Hamilton 和英国数学家Thomas Penyngton Kirkman 在 19世纪提出的数学问题，它是指给定 n个城市并给出每两个城市之间的距离，旅行商必须以最短路径访问所有的城市一次且仅一次，并回到原出发地，现已证明它属于 NP(Non-deterministic Polynomial-非确定多项式 )难题 1.历史上的第一个正式用来解决 TSP 问题的算法诞生于 1954 年 ,它被用来计算49 个城市的 TSP 问题 .到现在为止 ,运用目前最先进的计算机技术可解决找出游历24978 个城市的 TSP 问题 .TSP 的历史很久，最早的描述是 1759 年欧拉研究的骑士周游
4、问题，即对于国际象棋棋盘中的 64个方格，走访 64 个方格一次且仅一次，并且最终返回到起始点 .旅行商问题 (TSP)由美国 RAND 公司于 1948 年引入，该公司的声誉以及线性规划这一新方法的出现使得 TSP 成为一个知名且流行的问题 2模拟退火算法及其应用研究 第 2 页 (共 70 页 ) 旅行商问题是一个经典的图论问题：设有 n 个城市，用 ijc =1， 2， ， n表示 .城市 ijc之间的距离为 ijd ， i， j=1， 2， ， n，设所有城市间两两连通，旅行商需要跑遍 n个城市去推销他的商品，而这些城市之间的距离都不一样，这推销员需要从其中一个城市出发，而他老板规定他
5、必须把所有城市跑一遍，则 TSP 问题就是寻找让旅行商遍访每个城市一次且恰好一次的一条回路，且要求其路径总长度为最短 .该问题也可以归结为：有 N个城市由公路相互连通，从任一城市到另外城市都要支付相应的费用，一个销售商从其中一城市出发，访问其他 N 1 个城市且仅一次， 如何规划一条路径，使该旅行商的花费最少 3.当城市数量较小时，通过枚举法就可以找出最短的路径，然而随着问题规模的增加，很难找到一个多项式时间复杂度的算法来求解该问题 .TSP是一个典型的组合优化问题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较标准 .因此，快速、有效地解决
6、 TSP 有着重要的理论价值和极高的实际应用价值 .旅行商问题代表的一类组合优化问题 ,在物流配送、计算机网络、电子地图、交通诱导、电气布线、 VLSI 单元布局等方面都有重要的工程和理论价值，引起 了许多学者的关注 . TSP 是典型的组合优化问题，并且是一个 NP-hard 问题 .TSP 描述起来很简单，早期的研究者使用精确算法求解该问题， TSP 问题最简单的求解方法是枚举法 .它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是 n个点的所有排列的集合，大小为（ n-1） ！ .可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值 .求解 TS
7、P，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程 4 .常用的方法包括：分枝定界法、 线性规划法和动态规划法等，但可能的路径总数随城市数目 n 是成指数型增长的，所以当城市数目在 100个以上一般很难精确的求出其全局最优解 .随着人工智能的发展，出现了许多独立于问题的智能优化算法，如蚁群算法、遗传算法、模拟退火、禁忌搜索、神经网络、粒子群优化算法、免疫算法等，通过模拟或解释某些自然现象或过程而得以发展，为解决复杂组合优化问题提供了新的思路和方法 5 .模拟退火算法在迭代搜索过程以Boltzmann 分布概率接受目标函数的 “ 劣化解 ” ，具有突出的具有脱离局域 最优陷阱的能力，同时
8、具有较强的局部搜索能力，从而可以获取目标函数的全局最优解 .因为模拟退火算法具有高效、通用、灵活的优点，将模拟退火算法引入 TSP 求解，可以避免在求解过程中陷入 TSP 的局部最优解 6 .研究目的和意义 第 3 页 (共 70 页 ) 本文首先介绍传统的 TSP 问题，先对其进行数学描述，又列举 TSP 问题的应用 .之后介绍模拟退火算法，主要介绍其基本思想和关键技术，在此基础上将模拟退火的思想引入 TSP 的求解，设计出 TSP 的一种模拟退火算法并用 MATABLE 语言编程予以实现 . 2 选题背景 2.1 题目类型及来源 题目类型：研究论文 题目来源：专题研究 2.2 研究目的和意
9、义 诸如分技定法或整数规划等严格的算法常常不可行 .人们常采用的是启发式算法7 .启发式算法“ .分为两类：一是从待解决问题的原始数据结构着手进竹构造性求解，另一类是迭代改进现有的解 .构造性方法是根据待解决问题的特征来设计的，很难推广到不同应用领域：迭代改进方法更为一般 .这类算法的结构一般是这样的：从一个初始解开始，产生一个解序列，直到获得满意解为止 .新解的产生规则及终止迭代准则决定了一个具体算法 .这类算法的不足之处是： 1)算法往往终止于局部最优解 . 2)最终解取决于初始解的选择及产生新解的规则 .许多启发式算法在做迭代改进时都选择最快的减少目标函数值的策略，也就是所谓的贪一 b策
10、略 .这种“心”算法往往导致陷入局部最优解，而不是全局最优解 8 . 为了改善迭代型启发算法的行为，有时选择一批初始解，然后做相同的迭代以提高获得全局最优解的概率 .也可借助于随机搜索的算法 9 ，其特点是 随机的产生下一新解 .若新解比当前解的值更低，则将新解作为暂存解 .如果最优解与总解的比例越高，找到最优解的概率也就越大 .故当最优解的数目很大时，随机搜索算法的功能还是很好的 .作为一种通用的随机搜索算法，模拟退火 (Simulated Annealing，以下简称 SA)算法有着更好的渐进行为 .它是近年来提出的一种适合解大规模组合优化问题通用而 模拟退火算法及其应用研究 第 4 页
11、(共 70 页 ) 有效的近似算法 .它与以往的近似算法相比，具有描述简单、使用灵活、运用广泛、运行效率高和较少受初始条件约束等优点，而且特别适合并行计算，因此具有很高的实用价值 .随着计算机技 术的发展和普及，最优化理论和方法在诸多领域都得到了迅速发展和推广 .目前，它已成为现代科学技术中一个必不可少、重要的数学手段和方法，其应用和发展为诸多领域中非线性问题的解决，提供了孥实而有力的理论基础和有效的方法 .本论文利用模拟退火算法的高效性和优越性，将其用在货郎担问题的求解中 . 2.3 国内外现状和发展趋势与研究的主攻方向 模拟退火算法 (SA)在理论上已得到证明，它可以达到全局极小值，所以它
12、备受专家与学者的青睐 .目前，关于模拟退火算法的研究通常分为两类 .笫一类是基于有限状态奇异马尔可夫链的有关理论 11 ，给出模拟退火算法的某些关于理想收敛模型的充分条件或充要条件，这些条件在理论上证明了当退火三原则 (初始温度足够高、降温速度足够慢、终止温度足够低 )满足时 12 ，模拟退火算法以概率 l 达到全局最优解；第二类是针对某些具体问题，给出了模拟退火算法的很多成功应用 .事实上，正是由于专家和学者对该算法的钻研，才让该算法从经典的模拟退火算法走到了今天的多样型的模拟退火算法，比如快速模拟退火算法，使得该算法的速度和收敛性都得到较 大提高，再比如适应性的模拟退火算法，使得该算法具有
13、智能性；再比如现在有学者提到的遗传一模拟退火算法，就是将遗传算法和模拟退火算法二者的优越性结合起 .不能忽略的是每种算法的提出都与其应用范围紧密结合 13 ，这样才使得改进的算法在其应用领域具有较好的适用性 .由于模拟退火算法 (SA)从理论上可以达到全局极小值，所以对该算法的研究更有实际意义，众多学者正在努力钻研将其一般化，使其具有普遍适用性 . 3 模拟退火算法的一些知识 3.1 模拟退火算法的描述 模拟退火算法 (Simulated Annealing)最早见于 IBM托马斯 .J.沃森研究中心的S.Kirkpatrick 等人的文章 , 他们在对组合优化进行研究后 , 根据迭代改进的思
14、想提出了“模拟退火算法” ,模拟退火算法具有很强的局部搜索能力 .模拟退火算法来源于固体退火原理 , 将固体加温至充分高 , 再让其缓慢降温 (即退火 ), 使之达到能量模拟退火算法的描述 第 5 页 (共 70 页 ) 最低点 .反之 , 如果急速降温 (即淬火 )则不能达到最低点 .加温时 , 固体内部粒子随温升变为无序状 , 内能增大 , 而缓慢降温时粒子渐趋有序 , 在每个温度上都达到平衡态 ,最后在常温时达到基 态 , 内能减为最小 .根据 Metropolis 准则 ,粒子在温度 T 时趋于平衡的概率为 exp(- E/(kT), 其中 E 为温度 T 时的内能 , E 为其改变量
15、 , k 为 Boltzman 常数 .用固体退火模拟组合优化问题 , 将内能 E 模拟为目标函数值 f, 温度 T 演化成控制参数 t, 即得到解组合优化问题的模拟退火算法 :由初始解 i 和控制参数初值 t 开始 , 对当前解重复产生“新解计算目标函数差接受或舍弃”的迭代 , 并逐步衰减 t 值 , 算法终止时的当前解即为所得近似最优解 14 , 这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程 .退火过程由冷却进度表 (Cooling Schedule)控制 15 , 包括控制参数的初值 t 及其衰减因子 a、每个 t 值时的迭代次数 L 和停止条件 c.所以我们可以通过上面的思想写出
16、解决 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 ，则接受新状态 J，反之，则舍弃 . 如果新状态 j可以接受，那么就以 j.取代 i成为当前
17、状态，重复以上新状态的产生过程 .在大量迁移 (固体状态的变换称为迁移 )后，系统趋于能量较低的平衡状态 . 通过对上述物理现象的模拟，假定 L(S， f)存在邻域以及相应解的产生机制，)(xf 、 )(yf 分别为对应于解 i， j的目标函数值 .由解 i过渡到解 j的接受概率用以下的MetropoliS准则确定： P(tk )=P(i j )= )()(),)()(e x p ( )()(,1 jfift jfifjfifk(5) 合理的停止准则既要确保算法收敛于某一近似解，又要使最终解具有一定量 .从有限模拟退火算法的基本思想 第 9 页 (共 70 页 ) 的 CPU时间考虑， Nah
18、ar等人提出用事先确定好的控制参数的个数，亦即 Markov链的个数或迭代次数 k作为停止准则 .他们选取的迭代次数是 6 50次 .此类用迭代次数构造的停止准则虽能在等参数的协同下，直接控制算法进程的 CPU时间 .但对最终解质量的控制很弱， 也缺乏灵活性 . 控制模拟退火的渐进收敛特性给人们以新的启示：算法收敛于最优解集是随控制参数 t值的缓慢减小而渐进进行 .只有在 t“充分小”时，才有可能得出高质的最优解 .因此， t“充分小”在某种程度上可以替代“最终解质量”的判据，为停止准则所用 .一是让控制参数 t值小于某个充分小正数 e，直接构成停止准则的判断式 te：二是由算法进程的接受概率
19、随控制参数值递减的性态，确定一个终止参数，若算法进程的当前接受率，就终止算法 .Johnson等采用的就是这种停止准则，这种方法兼顾了最终解质量和 CPU时间两个方面对停止准则的要 求，只要值选取恰当， CPU时间可望缩减而最终解的质量仍有保证 . 常用的选取停止准则的另一个途径是不改进规则控制法，以算法进程所得到的某些近似解为衡量标准，判断算法当前解的质量是否持续得到明显提高，从而确定是否终止算法，如在若干个相继的 Markov链中解无任何变化就可以终止算法 .这类方法同样兼顾最终解质量和 CPU时间，在 和等参数的配合下，不仅可望得到高质量的最终解，而且对于 CPU时间有相对控制作用 (即
20、 CPU时间随问题规模的增大而增大 )，解质相对稳定 . 3.5 组合优化与物理退火的相似性 引进模拟退火算法 (SA)的原动力是基于这样的模拟：具有大规模解空叫的组合优化问题和带有多自由度的物理系统显示出类似的性质 .该算法用于解决组合优化问题的出发点是鉴于物理中晶体物质的退火过程与一般组合优化问题的相似性 . 在对固体物质进行退火处理时，通常是先对它加温，使其熔化，让其中的粒子可以自由运动，然后随着温度缓慢下降，粒子逐渐形成低能态的晶格 .若在凝结点附近的温度下降速率过快，则不能达这个能量最低态，而是以一种耋强的或者以一种非晶的具有高能量的亚稳态结束 .因此，这个过程的本质是慢速冷却，让粒
21、子有充分模拟退火算法及其应用研究 第 10 页 (共 70 页 ) 的时间失去可动性，进行 重新分布，这是退火的技术定义，立能确保粒子达到低能态势 .对于组合优化问题来说，也有类似的过程，组合优化问题解空间的每一点都代表一个具有不同目标函数的解 .所谓优化，就是在解空间寻找函数最小解的过程 .若把函数看成能量函数，把控制参数视为温度，解空间作为状态空间，那么模拟退火算法 (SA)寻找基态的过程就是求目标函数极小值的优化过程，因此，基于 MetropoliS接受准则的最优化过程与物理退火过程存在一定的相似性 .将这种相似性归纳在下表 2.1中 . 表 1 组合优化与物理退火的相似 性 组合优化 物理退火 组合优化 物理退火 解 粒子状态 Metropolis抽样过程 等温过程 最优解 能量最低态 控制参数的下降 冷却 设定初始温度 熔解过程 目标函数 能量 众所周知，处于热平衡的物理系统的各种可能状态服从波兹曼 (80ltzmann)概率分布，即如式 (2)所示 . 这里先研究由式 (2)所确定的函数随 T的变化趋势，选定两个能量 E1 E2 ，在同一温度 T下，有： P( 1EE )-P( 2EE ) = )e x p (1)e x p ()(1 121 kT EEkTETZ (6) 式（ 6）中恒存在 exp(- ,0,1)12 TkT EE 因此式 (6)大于零总成立 .
