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

前言第 1 页 (共 74 页)模拟退火算法及其应用研究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模拟退火算法及其应用研究第 2 页 (共 74 页)旅行商问题是一个经典的图论问题：设有 n 个城市，用 =1，2，n 表示.城市ijc之间的距离为 ，i，j=1，2，n，设所有城市间两两连通，旅行商需要跑遍ijcjdn 个城市去推销他的商品，而这些城市之间的距离都不一样，这推销员需要从其中一个城市出发，而他老板规定他必须把所有城市跑一遍，则 TSP 问题就是寻找让旅行商遍访每个城市一次且恰好一次的一条回路，且要求其路径总长度为最短.该问题也可以归结为：有 N 个城市由公路相互连通，从任一城市到另外城市都要支付相应的费用，一个销售商从其中一城市出发，访问其他 N1 个城市且仅一次，如何规划一条路径，使该旅行商的花费最少 3.当城市数量较小时，通过枚举法就可以找出最短的路径，然而随着问题规模的增加，很难找到一个多项式时间复杂度的算法来求解该问题.TSP 是一个典型的组合优化问题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较标准.因此，快速、有效地解决 TSP 有着重要的理论价值和极高的实际应用价值.旅行商问题代表的一类组合优化问题,在物流配送、计算机网络、电子地图、交通诱导、电气布线、VLSI 单元布局等方面都有重要的工程和理论价值，引起了许多学者的关注.TSP 是典型的组合优化问题，并且是一个 NP-hard 问题.TSP 描述起来很简单，早期的研究者使用精确算法求解该问题，TSP 问题最简单的求解方法是枚举法.它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是 n 个点的所有排列的集合，大小为（n-1）！.可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值.求解 TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程 .常用的方法包括：分枝定界法、线性规划法和动4态规划法等，但可能的路径总数随城市数目 n 是成指数型增长的，所以当城市数目在 100 个以上一般很难精确的求出其全局最优解.随着人工智能的发展，出现了许多独立于问题的智能优化算法，如蚁群算法、遗传算法、模拟退火、禁忌搜索、神经网络、粒子群优化算法、免疫算法等，通过模拟或解释某些自然现象或过程而得以发展，为解决复杂组合优化问题提供了新的思路和方法 .模拟退火算法在迭代搜索5过程以 Boltzmann 分布概率接受目标函数的“劣化解” ，具有突出的具有脱离局域最优陷阱的能力，同时具有较强的局部搜索能力，从而可以获取目标函数的全局最优解.因为模拟退火算法具有高效、通用、灵活的优点，将模拟退火算法引入 TSP 求解，可以避免在求解过程中陷入 TSP 的局部最优解 .6研究目的和意义第 3 页 (共 74 页)本文首先介绍传统的 TSP 问题，先对其进行数学描述，又列举 TSP 问题的应用.之后介绍模拟退火算法，主要介绍其基本思想和关键技术，在此基础上将模拟退火的思想引入 TSP 的求解，设计出 TSP 的一种模拟退火算法并用 MATABLE 语言编程予以实现.2 选题背景2.1 题目类型及来源题目类型：研究论文题目来源：专题研究2.2 研究目的和意义 诸如分技定法或整数规划等严格的算法常常不可行.人们常采用的是启发式算法.启发式算法“.分为两类：一是从待解决问题的原始数据结构着手进竹构造性求7解，另一类是迭代改进现有的解.构造性方法是根据待解决问题的特征来设计的，很难推广到不同应用领域：迭代改进方法更为一般.这类算法的结构一般是这样的：从一个初始解开始，产生一个解序列，直到获得满意解为止.新解的产生规则及终止迭代准则决定了一个具体算法.这类算法的不足之处是：1)算法往往终止于局部最优解.2)最终解取决于初始解的选择及产生新解的规则.许多启发式算法在做迭代改进时都选择最快的减少目标函数值的策略，也就是所谓的贪一b策略.这种“心”算法往往导致陷入局部最优解，而不是全局最优解 .8为了改善迭代型启发算法的行为，有时选择一批初始解，然后做相同的迭代以提高获得全局最优解的概率.也可借助于随机搜索的算法 ，其特点是随机的产生下9一新解.若新解比当前解的值更低，则将新解作为暂存解.如果最优解与总解的比例越高，找到最优解的概率也就越大.故当最优解的数目很大时，随机搜索算法的功能还是很好的.作为一种通用的随机搜索算法，模拟退火(Simulated Annealing，以下简称SA)算法有着更好的渐进行为.它是近年来提出的一种适合解大规模组合优化问题通用而模拟退火算法及其应用研究第 4 页 (共 74 页)有效的近似算法.它与以往的近似算法相比，具有描述简单、使用灵活、运用广泛、运行效率高和较少受初始条件约束等优点，而且特别适合并行计算，因此具有很高的实用价值.随着计算机技术的发展和普及，最优化理论和方法在诸多领域都得到了迅速发展和推广.目前，它已成为现代科学技术中一个必不可少、重要的数学手段和方法，其应用和发展为诸多领域中非线性问题的解决，提供了孥实而有力的理论基础和有效的方法.本论文利用模拟退火算法的高效性和优越性，将其用在货郎担问题的求解中.2.3 国内外现状和发展趋势与研究的主攻方向模拟退火算法(SA)在理论上已得到证明，它可以达到全局极小值，所以它备受专家与学者的青睐.目前，关于模拟退火算法的研究通常分为两类.笫一类是基于有限状态奇异马尔可夫链的有关理论 ，给出模拟退火算法的某些关于理想收敛模型1的充分条件或充要条件，这些条件在理论上证明了当退火三原则(初始温度足够高、降温速度足够慢、终止温度足够低)满足时 ，模拟退火算法以概率 l 达到全局最12优解；第二类是针对某些具体问题，给出了模拟退火算法的很多成功应用.事实上，正是由于专家和学者对该算法的钻研，才让该算法从经典的模拟退火算法走到了今天的多样型的模拟退火算法，比如快速模拟退火算法，使得该算法的速度和收敛性都得到较大提高，再比如适应性的模拟退火算法，使得该算法具有智能性；再比如现在有学者提到的遗传一模拟退火算法，就是将遗传算法和模拟退火算法二者的优越性结合起.不能忽略的是每种算法的提出都与其应用范围紧密结合 ，这样才使13得改进的算法在其应用领域具有较好的适用性.由于模拟退火算法(SA)从理论上可以达到全局极小值，所以对该算法的研究更有实际意义，众多学者正在努力钻研将其一般化，使其具有普遍适用性.3 模拟退火算法的一些知识3.1 模拟退火算法的描述模拟退火算法(Simulated Annealing)最早见于IBM托马斯.J.沃森研究中心的S.Kirkpatrick 等人的文章, 他们在对组合优化进行研究后, 根据迭代改进的思想提出了“模拟退火算法”,模拟退火算法具有很强的局部搜索能力.模拟退火算法来源于固体退火原理, 将固体加温至充分高, 再让其缓慢降温(即退火), 使之达到能模拟退火算法及其应用研究第 4 页 (共 74 页)量模拟退火算法的描述第 5 页 (共 74 页)最低点.反之, 如果急速降温(即淬火)则不能达到最低点.加温时, 固体内部粒子随温升变为无序状, 内能增大, 而缓慢降温时粒子渐趋有序, 在每个温度上都达到平衡态,最后在常温时达到基态, 内能减为最小.根据Metropolis 准则,粒子在温度T 时趋于平衡的概率为exp(- E/(kT), 其中E 为温度T 时的内能, E 为其改变量, k 为Boltzman 常数.用固体退火模拟组合优化问题, 将内能E 模拟为目标函数值f, 温度T 演化成控制参数t, 即得到解组合优化问题的模拟退火算法:由初始解i 和控制参数初值t 开始, 对当前解重复产生“新解计算目标函数差接受或舍弃”的迭代, 并逐步衰减t 值, 算法终止时的当前解即为所得近似最优解 , 这是基于蒙特14卡罗迭代求解法的一种启发式随机搜索过程.退火过程由冷却进度表(Cooling Schedule)控制 , 包括控制参数的初值t 及其衰减因子a、每个t 值时的迭代次数15L 和停止条件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 ，则接受新状态 J，反之，则舍弃.如果新状态