本科生毕业论文（设计）
题目模拟退火算法在TSP问题中的应用研究学生姓名
指导教师
学院
专业班级
完成时间2010年6月
目录
摘要............................................................. I II ABSTRACT........................................................... I V 第一章前言. (1)
1.1 TSP问题的基本概念 (1)
1.2 模拟退火算法的背景 (1)
1.3 发展趋势 (2)
第二章相关知识介绍 (3)
2.1模拟退火算法的原理 (3)
2.1.1 模拟退火的基本思想 (3)
2.1.2 算法对应动态演示步骤 (4)
2.2 TSP问题简述 (4)
2.3组合优化问题简述 (5)
2.4 蚁群算法及其它算法原理 (6)
2.4.1蚁群优化算法 (6)
2.4.2其它优化算法 (6)
第三章问题描述与算法分析研究 (9)
3.1应用研究整体规划 (9)
3.2应用开发环境 (9)
3.2.1开发语言 (9)
3.2.2开发平台 (9)
3.3 TSP问题的描述和分析 (9)
3.4模拟退火算法的分析 (10)
3.4.1模拟退火算法模型 (10)
3.4.2模拟退火算法与优化问题分析 (11)
3.5应用研究方案分析 (11)
第四章算法具体设计与编码实现 (12)
4.1基于模拟退火算法求解TSP问题详细设计 (12)
4.1.1求解TSP问题的模拟退火算法及流程图 (12)
4.1.2算法温度的选择和变化 (14)
4.1.3定义坐标表的具体参数与具体实现 (15)
4.1.4新解的产生方法 (17)
4.2求解TSP问题的算法主体模块详细设计 (19)
4.3算法的具体编码实现 (20)
4.3.1建立城市坐标文本文件 (21)
4.3.2 DOS下界面数据输出以及概率统计与分析 (21)
第五章算法运行分析 (24)
5.1 运行界面图示 (24)
5.2 运行结果 (27)
第六章结束语 (28)
致谢 (29)
参考文献 (30)
摘要
TSP问题是一个典型的NP 完全问题,模拟退火算法是求解此问题的一种理想方法。
模拟退火算法是将物理退火过程与组合优化相结合在一起的一种随机迭代寻优算法，TSP问题即旅行商问题是一个组合优化问题，该问题被证明具有NPC 计算复杂性。因此，研究模拟退化算法的基本原理及其在TSP问题求解中的应用受到高度的关注。
本文主要阐述了模拟退火算法的原理和一些与其相关联的知识结构点。通过对其算法的原理，以及退火算法在函数优化问题上的应用，与优化组合问题的研究来了解TSP问题以及模拟退火算法上解决实际问题上的应用与研究。帮助理解模拟退化算法的基本原理及其在TSP问题求解中的应用。
关键词模拟退火算法，TSP，组合优化，C/C++，遗传算法
ABSTRACT
TSP problem is a typical NP-complete problem, using simulated annealing algorithm to solve this problem is an ideal way.
Simulated Annealing Algorithm combines the process of physical annealing and combinatorial optimization together ,it is a stochastic iterative optimization algorithm, TSP problem that the traveling salesman problem is a combinatorial optimization problem that is shown to have NPC computational complexity. Therefore, studying the basic principles of simulated annealing algorithm and its application in problem solving TSP should have a high degree of attention.
This article focuses on the principle of simulated annealing algorithm and some of the knowledge structure what associated with the first point. By studying the principle of their algorithm, simulated annealing algorithm to optimize the application function, and optimization of research to understand the problem and the simulated annealing algorithm for TSP The practical application and research. Help to understand the basic principles of simulated annealing algorithm and its application in solving TSP problems.
KEY WORDS: SAA，Genetic Algorithm，Combinatorial Optimization，
TSP，C/C++
第一章前言
模拟退火算法是将物理退火过程与组合优化相结合的一种随机迭代寻优算法，TSP问题即旅行商问题是一个组合优化问题，该问题被证明具有NPC 计算复杂性，因此研究模拟退化算法的基本原理及其在TSP问题求解中的应用受到高度的关注。因此采用模拟退火算法来解决TSP旅行问题是一种比较理想的方法。
1.1 TSP问题的基本概念
旅行商问题( Traveling Salesman Problem) 是一个NP 完全问题,目前求解TSP 问题的主要方法有模拟退火算法、遗传算法、启发式搜索法、Hopfield 神经网络算法、蚁群算法等，还包括许多算法。
TSP(Traveling salesman Problem,旅行商问题)是指给定n个城市和各城市间的距离,要求确定一条经过各个城市当且仅当一次的最短路线。它是一种典型的组合优化问题,其最优解的求解代价是指数级的。已经证明TSP问题是一个NP-hard 问题。基于智能优化算法求解TSP问题,是近年来刚刚兴起的热门课题。然而在科学管理与经济决策的许多应用领域中,现实世界存在着大量的多目标优化问题。对于旅行商问题(Traveling salesman Problem ,TSP),实际中经常要同时考虑多个目标,如路程最短、时间最短、费用最省、风险最小等多方面的因素。目标之间往往存在冲突性。如何在多个目标中寻找一个公平、合理的解是比较复杂的问题。
1.2 模拟退火算法的背景
模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T 时的内能，ΔE为其改变量，k为Boltzman 常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的
当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t 及其衰减因子Δ t、每个t值时的迭代次数L和停止条件S[1]。
1.3 发展趋势
TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。
TSP由美国RAND公司于1948年引入，该公司的声誉以及线形规划这一新方法的出现使得TSP成为一个知名且流行的问题。
TSP在中国的研究，同样的问题，在中国还有另一个描述方法：一个邮递员从邮局出发，到所辖街道投邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应该如何选择投递路线，使所走的路程最短？这个描述之所以称为中国邮递员问题（Chinese Postman Problem CPP）因为是我国学者管梅古教授于1962年提出的这个问题并且给出了一个解法。
TSP问题是一个典型的、容易描述但是难以处理的NP完全问题，同时TSP 问题也是诸多领域内出现的多种复杂问题的集中概括和简化形式。目前求解TSP 问题的主要方法有启发式搜索法、模拟退火算法、遗传算法、Hopfield神经网络算法、二叉树描述算法。
对于用模拟退火算法对求解旅行商组合优化问题做来了在满足模拟退火算法全局收敛性的情况下，子排列反序并移位抽样方式对求解NP完全问题是非常有效的。
很多实际问题，经过简化处理后均可转化为TSP问题，对TSP问题求解方法的研究具有重要的应用价值。人们在努力寻找大维数最优化算法的同时，构造出了许多近似求解法，如遗传法、局部搜索算法、蚁群算法等，特别是提出了如模拟退火等用统计方法近似求解TSP的随机算法，为人们求解TSP问题开辟了新的途径。
第二章相关知识介绍
本章主要介绍一些关于模拟退火算法的原理、TSP问题简述以及相关重要算法的原理，并且对其进行了一些细致的阐述，以便于对模拟退火算法了解。
2.1模拟退火算法的原理
模拟退火算法是近年来在国内外都比较受关注的算法。它的思想最早在1953年由Metropolis提出，在1983年被Kirkpatrick等人成功引入组合优化领域。由于它具有很强的实用性和极佳的性能表现，迅速引起了很多专家学者的兴趣，不断对其进行研究。模拟退火算法主要应用在各种优化问题上，函数优化是其中非常重要的一个方面。NP问题是一个比较麻烦的问题，其解的规模随问题规模的增大而成指数级增长，对于一般的方法而言，当问题规模过大时，就失去了可行性。模拟退火作为一种随机算法，它的特点非常适于求解NP问题，比如著名的旅行商问题(Traveling Salesman Problem)。模拟退火算法在解决这类问题上有着优异的表现。
2.1.1 模拟退火的基本思想
模拟退火是一种通用概率算法，用来在一个大的搜寻空间内找寻命题的最优解。模拟退火来自冶金学的专有名词淬火。
模拟退火的原理也和金属退火的原理近似：将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一部先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。
模拟退火算法可以分解为解空间、目标函数和初始解三部分。
(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L
(2) 对k=1，……，L做第(3)至第6步：
(3) 产生新解S′
(4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数。
(5) 若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.
(6) 如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。
(7) T逐渐减少，且T->0，然后转第2步。
2.1.2 算法对应动态演示步骤
模拟退火算法新解的产生和接受可分为如下四个步骤：
第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则: 若Δt′<0则接受S′作为新的当前解S，否则以概率exp(-Δt′/T)接受S′作为新的当前解S。
第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。
模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。
2.2 TSP问题简述
旅行商问题，即TSP问题（Travelling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。
因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。
旅行商问题TSP( Traveling Salesman Problem) 问题是一个NP 完全问题,目前求解TSP 问题的主要方法有模拟退火算法、遗传算法、启发式搜索法、Hopfield 神经网络算法、蚁群算法等,各种算法各有千秋。模拟退火算法最早思想由Met ropolis 在20世纪1953 年提出,1983 年Kirkpat rick 等成功地将退火思想引入组合优化领域。模拟退火算法是局部搜索算法的扩展,理论上来说,它是一个全局最优算法。如何在初始解附近找出一个“好的解”是一项关键技术,它直接影响算法的收敛速度。
TSP问题是经典的NP Hard组合优化问题之一,求解该问题的启发式算法一直是数学，计算机科学研究的热点之一。假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值，这是一个NP难问题。
2.3组合优化问题简述
在给定有限集的所有具备某些条件的子集中，按某种目标找出一个最优子集的一类数学规划。又称组合规划。从最广泛的意义上说，组合规划与整数规划这两者的领域是一致的，都是指在有限个可供选择的方案的组成集合中，选择使目标函数达到极值的最优子集。
组合最优化发展的初期，研究一些比较实用的基本上属于网络极值方面的问题，如广播网的设计、开关电路设计、航船运输路线的计划、工作指派、货物装箱方案等。自从拟阵概念进入图论领域之后，对拟阵中的一些理论问题的研究成为组合规划研究的新课题，并得到应用。现在应用的主要方面仍是网络上的最优化问题，如最短路问题、最大（小）支撑树问题、最优边无关集问题、最小截集问题、推销员问题等[2]。
组合优化（Combinatorial Optimization ）问题的目标是从组合问题的可行解集中求出最优解，通常可描述为：令Ω＝{s1，s2，…，sn} 为所有状态构成的解空间，C (si) 为状态si 对应的目标函数值，要求寻找最优解s*，使得对于所有的si ∈Ω，有C(s*)＝minC(si) 。组合优化往往涉及排序、分类、筛选等问题，它是运筹学的一个重要分支[3]。
典型的组合优化问题有旅行商问题（Traveling Salesman Problem－TSP）、加工调度问题（Scheduling Problem，如Flow-Shop，Job-Shop）、0-1背包问题（Knapsack Problem）、装箱问题（Bin Packing Problem）、图着色问题（Graph Coloring Problem）、聚类问题（Clustering Problem）等。这些问题描述非常简单，
并且有很强的工程代表性，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间，以致根本不可能在现有计算机上实现，即所谓的“组合爆炸”。正是这些问题的代表性和复杂性激起了人们对组合优化理论与算法的研究兴趣。组合优化问题在实践中有着广泛的应用，同时也是计算机科学中的重要研究课题[4]。
2.4 蚁群算法及其它算法原理
2.4.1蚁群优化算法
受蚂蚁觅食时的通信机制的启发，90年代Dorigo提出了蚁群优化算法(Ant Colony Optimization，ACO)来解决计算机算法学中经典的“货郎担问题”。如果有n个城市，需要对所有n个城市进行访问且只访问一次的最短距离[5]。
在解决货郎担问题时，蚁群优化算法设计虚拟的“蚂蚁”将摸索不同路线，并留下会随时间逐渐消失的虚拟“信息素”。虚拟的“信息素”也会挥发，每只蚂蚁每次随机选择要走的路径，它们倾向于选择路径比较短的、信息素比较浓的路径。根据“信息素较浓的路线更近"的原则，即可选择出最佳路线。由于这个算法利用了正反馈机制，使得较短的路径能够有较大的机会得到选择，并且由于采用了概率算法，所以它能够不局限于局部最优解。
蚁群优化算法对于解决货郎担问题并不是目前最好的方法，但首先，它提出了一种解决货郎担问题的新思路；其次由于这种算法特有的解决方法，它已经被成功用于解决其他组合优化问题，例如图的着色(Graph Coloring)以及最短超串(Shortest Common Supersequence)等问题[6]。
2.4.2其它优化算法
随着计算机技术的飞速发展，智能计算方法的应用领域也越来越广泛，
算法的内容也越来越多。如人工神经网络技术、遗传算法、模拟退火算法、
模拟退火技术和群集智能技术等。
1．人工神经网络算法
“人工神经网络”(ARTIFICIAL NEURAL NETWORK，简称ANN)是在
对人脑组织结构和运行机制的认识理解基础之上模拟其结构和智能行为的
一种工程系统。早在本世纪40年代初期，心理学家McCulloch、数学家Pitts
就提出了人工神经网络的第一个数学模型，从此开创了神经科学理论的研
究时代。其后，F Rosenblatt、Widrow和J. J .Hopfield等学者又先后提出了
感知模型，使得人工神经网络技术得以蓬勃发展[7]。
神经系统的基本构造是神经元(神经细胞)，它是处理人体内各部分之间
相互信息传递的基本单元。据神经生物学家研究的结果表明，人的一个大
脑一般有1010～1011个神经元。每个神经元都由一个细胞体，一个连接其
他神经元的轴突和一些向外伸出的其它较短分支——树突组成。轴突的功
能是将本神经元的输出信号(兴奋)传递给别的神经元。其末端的许多神经末
梢使得兴奋可以同时传送给多个神经元。树突的功能是接受来自其它神经
元的兴奋。神经元细胞体将接受到的所有信号进行简单处理(如：加权求和，
即对所有的输入信号都加以考虑且对每个信号的重视程度——体现在权值上——有所不同)后由轴突输出。神经元的树突与另外的神经元的神经末梢
相连的部分称为突触[8]。
2．Hopfield神经网络
1986年美国物理学家J.J.Hopfield陆续发表几篇论文，提出了Hopfiel神经网络。他利用非线性动力学系统理论中的能量函数方法研究反馈人工神经网络的稳定性，并利用此方法建立求解优化计算问题的系统方程式。基本的Hopfield 神经网络是一个由非线性元件构成的全连接型单层反馈系统。
网络中的每一个神经元都将自己的输出通过连接权传送给所有其它神经元，同时又都接收所有其它神经元传递过来的信息。即：网络中的神经元t时刻的输出状态实际上间接地与自己的t-1时刻的输出状态有关。所以Hopfield神经网络是一个反馈型的网络。其状态变化可以用差分方程来表征。反馈型网络的一个重要特点就是它具有稳定状态。当网络达到稳定状态的时候，也就是它的能量函数达到最小的时候。这里的能量函数不是物理意义上的能量函数，而是在表达形式上与物理意义上的能量概念一致，表征网络状态的变化趋势，并可以依据Hopfield工作运行规则不断进行状态变化，最终能够达到的某个极小值的目标函数。网络收敛就是指能量函数达到极小值[9]。如果把一个最优化问题的目标函数转换成网络的能量函数，把问题的变量对应于网络的状态，那么Hopfield神经网络就能够用于解决优化组合问题。
3．遗传算法
遗传算法（Genetic Algorithms）是基于生物进化理论的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它是在70年代初期由美国密执根（Michigan）大学的霍兰（Holland）教授发展起来的。1975年霍兰教授发表了第一本比较系统论述遗传算法的专著《自然系统与人工系统中的适应性》
（《Adaptation in Natural and Artificial Systems》）。遗传算法最初被研究的出发点不是为专门解决最优化问题而设计的，它与进化策略、进化规划共同构成了进化算法的主要框架，都是为当时人工智能的发展服务的。迄今为止，遗传算法是进化算法中最广为人知的算法。
近几年来，遗传算法主要在复杂优化问题求解和工业工程领域应用方面，取得了一些令人信服的结果，所以引起了很多人的关注。在发展过程中，进化策略、进化规划和遗传算法之间差异越来越小。遗传算法成功的应用包括：作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题等等。
4．粒子群优化算法
粒子群优化算法(PSO)是一种进化计算技术(Evolutionary Computation)，有Eberhart博士和Kennedy博士发明。源于对鸟群捕食的行为研究。
PSO同遗传算法类似，是一种基于叠代的优化工具。系统初始化为一组随机解，通过叠代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)。而是粒子在解空间追随最优的粒子进行搜索。
同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域。
粒子群优化算法(PSO) 也是起源对简单社会系统的模拟，最初设想是模拟鸟群觅食的过程，但后来发现PSO是一种很好的优化工具。
目前的智能计算研究水平暂时还很难使“智能机器”真正具备人类的常识，但智能计算将在21世纪蓬勃发展。不仅仅只是功能模仿要持有信息机理一致的观点。即人工脑与生物脑将不只是功能模仿，而是具有相同的特性。这两者的结合将开辟一个全新的领域，开辟很多新的研究方向。智能计算将探索智能的新概念，新理论，新方法和新技术，而这一切将在以后的发展中取得重大成就。
第三章问题描述与算法分析研究
本章介绍了模拟退火算法解决TSP问题的需求分析阶段的内容，是本次程序设计中的关键环节。主要对系统进行了整体的分析，明确了系统目标，确定了开发环境，构建了基本的框架结构和功能模块。并且确定了模拟退火算法在TSP 问题中的应用研究的主要设计思想。
3.1应用研究整体规划
通过对程序的理解和分析，这个课题项目应该分为2个阶段进行。第一阶段是模拟退火算法的描述和实现；第二阶段是在TSP问题中应用模拟退火算法解决问题，即模拟退火算法在TSP问题中的具体实现。
3.2应用开发环境
完成一个完整并且优秀的程序，为其配置一个良好的系统开发环境是十分必要的，接下来是介绍模拟退火算法解决TSP问题所需要配置的环境要求。接下来为开发语言和系统运行平台做下简介。
3.2.1开发语言
开发语言必须是一种优秀的面向对象程序设计语言并且适合于系统程序设计。C++语言是一种优秀的面向对象程序设计语言，它在C语言的基础上发展而来C++以其独特的语言机制在计算机科学的各个领域中得到了广泛的应用。面向对象的设计思想是在原来结构化程序设计方法基础上的一个质的飞跃，C++完美地体现了面向对象的各种特性。因此采用c++语言进行编写程序。
3.2.2开发平台
本课题开发语言选用c++语言，可以选用的开发平台可以从c++语言平台中选择一种出来，本课题选用visual C++6.0。
3.3 TSP问题的描述和分析
旅行商问题，即TSP问题（Travelling Salesman Problem）是数学领域中著名
问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。一个实例如图3.1所示
图3.1 TSP问题的示意图
从图3.1中可以看出左面的总体路径要小于右面的总体路径。TSP问题的目的就是选择出路径路程为所有路径之中的最小值的路径。目前人们已经构造出了许多近似求解法，如遗传法、蚁群算法、模拟退火算法等[10]。
3.4模拟退火算法的分析
下面介绍并且分析模拟退火算法的模型和组合优化的问题。
3.4.1模拟退火算法模型
模拟退火算法起源于物理退火。物理退火过程：
（1）加温过程
（2）等温过程
（3）冷却过程
模拟退火算法可以分解为解空间、目标函数和初始解三部分。
模拟退火的基本思想:
(1)初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每
个T值的迭代次数L;
(2) 对k=1，……，L做第(3)至第6步：
(3) 产生新解S′
(4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数
(5) 若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为
新
的当前解
(6) 如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常
取为连续若干个新解都没有被接受时终止算法。
(7) T逐渐减少，且T->0，然后转第2步。
3.4.2模拟退火算法与优化问题分析
模拟退火算法用于优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题的相似性[11]。模拟退火算法用于优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题的相似性。算法的基本思想是从一给定解开始的，从邻域中随机产生另一个解，接受准则允许目标函数在有限范围内变坏。它由一控制参数t决定，其作用类似于物理过程中的温度T，对于控制参数t的每一取值，算法持续进行“产生新解——判断——接受或舍弃”的迭代过程，对应着固体在某一恒定温度下趋于热平衡的过程。经过大量的解变换后，可以求得给定控制参数t值时优化问题的相对最优解。然后减小控制参数t的值，重复执行上述迭代过程。当控制参数逐渐减小并趋于零时，系统亦越来越趋于平衡状态，最后系统状态对应于优化问题的整体最优解。
3.5应用研究方案分析
根据该课题要求，研究模拟退化算法的基本原理以及TSP组合优化问题，用一种程序语言实现基于模拟退火算法的TSP问题求解方法。并且在3.3中构建了1个TSP问题，问题的目标是选择出路径路程为所有路径之中的最小值的路径。
通过C++语言编写并且实现出模拟退火算法。在利用编写出的模拟退火算法模型去解决之前所建立的TSP问题模型。
第四章算法具体设计与编码实现
前面的章节主要介绍了问题描述与算法分析研究的内容，而本章主要是对该系统的具体实现进行了详细设计。描绘出模拟退火算法的流程图，了解该算法的运行机制，明确算法在系统整体设计中的具体功能和应用，并且对应用模拟退火算法求解TSP问题做个详细的划分和描述。具体分为基于模拟退火算法求解TSP 问题详细设计和求解TSP问题的算法主体模块详细设计。
4.1基于模拟退火算法求解TSP问题详细设计
第三章提供了模拟退火算法的大体框架和组合优化要注意的问题，这节将了解模拟退火算法的具体流程图和算法模型描述以及模拟退火算法的参数控制问题。模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点温度T的初始值设置问题，退火速度问题，温度管理问题。并且这部分包括一些关键代码。
4.1.1求解TSP问题的模拟退火算法及流程图
模拟退火算法是解决TSP问题的有效方法之一，其最初的思想由Metropolis 在1953年提出，Kirkpatrick在1983年成功地将其应用在组合最优化问题中。
模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。
求解TSP的模拟退火算法模型可描述如下:
解空间：解空间S是遍访每个城市恰好一次的所有路经，解可以表示为
{w1,w2 ,……, wn}，w1, ……, wn是1,2,……,n的一个排列，表明w1城市出发，依次经过w2, ……, wn城市，再返回w1城市。初始解可选为(1,……, n) ;
目标函数：目标函数为访问所有城市的路径总长度;
我们要求的最优路径为目标函数为最小值时对应的路径。新路径的产生：随机产生1和n 之间的两相异数k 和m ，不妨假设k (w1,w2,…,wm,wk+1,…,wk,wm+1,…,wn)上述变换方法就是将k 和m 对应的两个城市在路径序列中交换位置,称为2-opt 映射。 根据上述描述，模拟退火算法求解TSP 问题的流程框图如图4.1所示。 图4.1模拟退火算法的流程图 Y Y Y Y N N N N 选择初始路径X0 确定初始温度T0 当前路径Xi=X0 当前温度Ti=T0 当前路径Xi=Xj △f<=0 Exp(-△f/Ti)>r andom(0,1) 跳出内循环 跳出外循环 结 束 当前温度Ti 下降 从Xi 的邻域中随机选择Xi ， 计算Xi 与Xj 的路程差 △f=f(Xj)-f(Xi) 图4.1展示了模拟退火算法的大体流程图。选一初始状态X0,作为当前解:并且确定初始温度T0，令当前的Xi=X0和Ti=T0。然后从Xi的邻域中随即选择Xj，计算Xi与Xi的路径差，比较差值。按一定方式将T降温，即令T(t+1)＝k×T(t)，i=i+1，然后检查退火过程是否结束，如果不是继续交换，如果是的话输出Si作为最优输出。 4.1.2算法温度的选择和变化 温度参数是模拟退火算法中一个关键的参数，初始温度不够高或退火时间不够长将会使得搜索过快，从而使得算法容易陷于局部最优解。反之，如果温度过高或退火时间过长，将会造成算法在计算机上的运行时间过长，从而令人无法接受。因此，温度参数的设定影响到模拟退火算法能否收敛到全局最优解。 1．初始温度的选取 由于模拟退火算法的求解不依赖于初始值，所有可从中随机选取一个初始状态。 2．温度的下降函数 温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式： T(t+1)＝k×T(t) 公式（4.1）式中k为正的略小于1.00的常数，t为降温的次数模拟退火算法按照其温度下降的时刻可分为两类，一类是时齐算法，在该算法中对于每一个固定温度t，计算对应的马尔可夫链的变化，直到达到一个稳定状态，然后再使温度下降。另一类是非时齐算法，整个过程仅由一个马尔可夫链构成，要求相连的状态转移中，温度t 是下降的。本文主要考虑了时齐算法的情况。该系统设置的温度下降系数为a=0.92。 程序代码实现该部分功能： int *stimulation(int *x) { int *result = NULL,*temp = NULL; double random = 0; int *j = new int[amount]; int *i = new int[amount]; for(int m=0;m { i[m] = x[m]; j[m] = 0; } double t = 280, alpha = 0.92; //初始温度，降温系数 int k = 0; //降温次数 int L = 100*amount; //每个温度的迭代次数,也就是每一个温度上的平衡条件 int time = 0; //记录某一温度下的迭代次数 double f1 = 101,f2 = 100; do { f1 = f2; time = 0; do { Neighbour(i,j); random = P(i,j,t); if ( (random == 1.0) || (random > random0_1()) ) { temp = i; i = j; j = temp; } time++; }while(time < L); f2 = evaluate(i); t = alpha * t; k++; }while( fabs(f2 - f1) > 1e-5); result = i; return result; } 温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。 该系统设置的初始温度为T=280。 4.1.3定义坐标表的具体参数与具体实现 1．城市坐标表的定义 在这里我们选择了简单的TSP模型，应用10个点之间坐标。首先建立个二维
相关主题
文本预览