《毕业设计（论文）-模拟退火算法在TSP问题中的研究(19页).docx》由会员分享，可在线阅读，更多相关《毕业设计（论文）-模拟退火算法在TSP问题中的研究(19页).docx（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-毕业设计（论文）-模拟退火算法在TSP问题中的研究-第 16 页摘 要：TSP问题是一个典型的NP 完全问题,模拟退火算法是求解此问题的一种理想方法。模拟退火算法是将物理退火过程与组合优化相结合在一起的一种随机迭代寻优算法，TSP问题即旅行商问题是一个组合优化问题，该问题被证明具有NPC计算复杂性。因此，研究模拟退化算法的基本原理及其在TSP问题求解中的应用受到高度的关注。本文主要阐述了模拟退火算法的原理和一些与其相关联的知识结构点。通过对其算法的原理，以及退火算法在函数优化问题上的应用，与优化组合问题的研究来了解TSP问题以及模拟退火算法上解决实际问题上的应用与研究。帮助理解模拟退化算法的
2、基本原理及其在TSP问题求解中的应用。关键词：模拟退火算法，TSP，组合优化，C/C+目 录第一章 前言11.1 TSP问题的基本概念11.2模拟退火算法背景11.3 发展趋势1第二章 相关知识介绍22.1模拟退火算法的原理22.1.1 模拟退火的基本思想22.2 TSP问题简述2第三章 问题描述与算法分析研究33.1应用研究整体规划33.2应用开发环境33.2.1开发语言33.2.2开发平台33.3 TSP问题的描述和分析33.4模拟退火算法的分析43.4.1模拟退火算法模型43.4.2模拟退火算法与优化问题分析4第四章 算法具体设计与编码实现44.1基于模拟退火算法求解TSP问题详细设计4
3、4.1.1求解TSP问题的模拟退火算法及流程图54.1.2算法温度的选择和变化54.1.3定义坐标表的具体参数与具体实现74.1.4新解的产生方法84.2求解TSP问题的算法主体模块详细设计94.3算法的具体编码实现104.3.1建立城市坐标文本文件104.3.2 DOS下界面数据输出以及概率统计与分析10第五章 算法运行分析115.1 运行界面图示115.2 运行结果13第六章 结束语13致 谢13参考文献14第一章 前言模拟退火算法是将物理退火过程与组合优化相结合的一种随机迭代寻优算法，TSP问题即旅行商问题是一个组合优化问题，该问题被证明具有NPC计算复杂性，因此研究模拟退化算法的基本原
4、理及其在TSP问题求解中的应用受到高度的关注。因此采用模拟退火算法来解决TSP旅行问题是一种比较理想的方法。1.1 TSP问题的基本概念旅行商问题( Traveling Salesman Problem) 是一个NP 完全问题,目前求解 TSP 问题的主要方法有模拟退火算法、遗传算法、启发式搜索法、Hopfield 神经网络算法、蚁群算法等，还包括许多算法。TSP(Traveling salesman Problem,旅行商问题)是指给定n个城市和各城市间的距离,要求确定一条经过各个城市当且仅当一次的最短路线。它是一种典型的组合优化问题,其最优解的求解代价是指数级的。已经证明TSP问题是一个N
5、P-hard问题。基于智能优化算法求解TSP问题,是近年来刚刚兴起的热门课题。 然而在科学管理与经济决策的许多应用领域中,现实世界存在着大量的多目标优化问题。对于旅行商问题(Traveling salesman Problem ,TSP),实际中经常要同时考虑多个目标,如路程最短、时间最短、费用最省、风险最小等多方面的因素。目标之间往往存在冲突性。如何在多个目标中寻找一个公平、合理的解是比较复杂的问题。1.2模拟退火算法背景模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在
6、常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-E/(kT)，其中E为温度T时的内能，E为其改变量，k为 Boltzman 常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子t、每个t值时的迭代
7、次数L和停止条件S。1.3 发展趋势TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。TSP由美国RAND公司于1948年引入，该公司的声誉以及线形规划这一新方法的出现使得TSP成为一个知名且流行的问题。TSP在中国的研究，同样的问题，在中国还有另一个描述方法：一个邮递员从邮局出发，到所辖街道投邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应该如何选择投递路线，使所走的路程最短？这个描述之所以称为中国邮递员问题（Chinese Postman Problem CPP）因为是我国学
8、者管梅古教授于1962年提出的这个问题并且给出了一个解法。第二章 相关知识介绍本章主要介绍一些关于模拟退火算法的原理、TSP问题简述以及相关重要算法的原理，并且对其进行了一些细致的阐述，以便于对模拟退火算法了解。2.1模拟退火算法的原理模拟退火算法是近年来在国内外都比较受关注的算法。它的思想最早在1953年由Metropolis提出，在1983年被Kirkpatrick等人成功引入组合优化领域。由于它具有很强的实用性和极佳的性能表现，迅速引起了很多专家学者的兴趣，不断对其进行研究。模拟退火算法主要应用在各种优化问题上，函数优化是其中非常重要的一个方面。NP问题是一个比较麻烦的问题，其解的规模随
9、问题规模的增大而成指数级增长，对于一般的方法而言，当问题规模过大时，就失去了可行性。模拟退火作为一种随机算法，它的特点非常适于求解NP问题，比如著名的旅行商问题(Traveling Salesman Problem)。模拟退火算法在解决这类问题上有着优异的表现。2.1.1 模拟退火的基本思想模拟退火是一种通用概率算法，用来在一个大的搜寻空间内找寻命题的最优解。模拟退火来自冶金学的专有名词淬火。模拟退火的原理也和金属退火的原理近似：将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题
10、的合适程度。算法先以搜寻空间内一个任意点作起始：每一部先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。模拟退火算法可以分解为解空间、目标函数和初始解三部分。(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L； (2) 对k=1，L做第(3)至第6步；(3) 产生新解S；(4) 计算增量 t=C(S)-C(S)，其中C(S)为评价函数；(5) 若 t0，然后转第2步。2.2 TSP问题简述旅行商问题，即TSP问题（Travelling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要
11、走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。旅行商问题TSP( Traveling Salesman Problem) 问题是一个NP 完全问题,目前求解TSP 问题的主要方法有模拟退火算法、遗传算法、启发式搜索法、Hopfield 神经网络算法、蚁群算法等,各种算法各有千秋。模拟退火算法最早思想由Met ropolis 在20世纪1953 年提出,1983 年Kirkpa
12、t rick 等成功地将退火思想引入组合优化领域。模拟退火算法是局部搜索算法的扩展,理论上来说,它是一个全局最优算法。如何在初始解附近找出一个“好的解”是一项关键技术,它直接影响算法的收敛速度。TSP问题是经典的NP Hard组合优化问题之一,求解该问题的启发式算法一直是数学，计算机科学研究的热点之一。假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值，这是一个NP难问题。第三章 问题描述与算法分析研究本章介绍了模拟退火算法解决TSP问题的需求分析阶段的内容，是本次程序
13、设计中的关键环节。主要对系统进行了整体的分析，明确了系统目标，确定了开发环境，构建了基本的框架结构和功能模块。并且确定了模拟退火算法在TSP问题中的应用研究的主要设计思想。3.1应用研究整体规划通过对程序的理解和分析，这个课题项目应该分为2个阶段进行。第一阶段是模拟退火算法的描述和实现；第二阶段是在TSP问题中应用模拟退火算法解决问题，即模拟退火算法在TSP问题中的具体实现。3.2应用开发环境完成一个完整并且优秀的程序，为其配置一个良好的系统开发环境是十分必要的，接下来是介绍模拟退火算法解决TSP问题所需要配置的环境要求。3.2.1开发语言开发语言必须是一种优秀的面向对象程序设计语言并且适合于
14、系统程序设计。C+语言是一种优秀的面向对象程序设计语言，它在C语言的基础上发展而来C+以其独特的语言机制在计算机科学的各个领域中得到了广泛的应用。面向对象的设计思想是在原来结构化程序设计方法基础上的一个质的飞跃，C+完美地体现了面向对象的各种特性。因此采用c+语言进行编写程序。3.2.2开发平台本课题开发语言选用c+语言，可以选用的开发平台可以从c+语言平台中选择一种出来，本课题选用visual C+6.0。3.3 TSP问题的描述和分析旅行商问题，即TSP问题（Travelling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走
15、的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。一个实例如图3.1所示：图3.1 TSP问题的示意图从图3.1中可以看出左面的总体路径要小于右面的总体路径。TSP问题的目的就是选择出路径路程为所有路径之中的最小值的路径。目前人们已经构造出了许多近似求解法，如遗传法、蚁群算法、模拟退火算法等。3.4模拟退火算法的分析下面介绍并且分析模拟退火算法的模型和组合优化的问题。3.4.1模拟退火算法模型模拟退火算法起源于物理退火。物理退火过程：(1) 加温过程 (2) 等温过程 (3) 冷却过程3.4.2模拟退火算法与优化问题
16、分析模拟退火算法用于优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题的相似性11。模拟退火算法用于优化问题的出发点是基于物理中固体物质的退火过程与一般优化问题的相似性。算法的基本思想是从一给定解开始的，从邻域中随机产生另一个解，接受准则允许目标函数在有限范围内变坏。它由一控制参数t决定，其作用类似于物理过程中的温度T，对于控制参数t的每一取值，算法持续进行“产生新解判断接受或舍弃”的迭代过程，对应着固体在某一恒定温度下趋于热平衡的过程。经过大量的解变换后，可以求得给定控制参数t值时优化问题的相对最优解。然后减小控制参数t的值，重复执行上述迭代过程。当控制参数逐渐减小并趋于零时，系统
17、亦越来越趋于平衡状态，最后系统状态对应于优化问题的整体最优解。第四章 算法具体设计与编码实现本章描绘出模拟退火算法的流程图，了解该算法的运行机制，明确算法在系统整体设计中的具体功能和应用，并且对应用模拟退火算法求解TSP问题做个详细的划分和描述。具体分为基于模拟退火算法求解TSP问题详细设计和求解TSP问题的算法主体模块详细设计。4.1基于模拟退火算法求解TSP问题详细设计模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点温度T的初始值设置问题，退火速度问题，温度管理问题。4.1.1求解TSP问题的模拟退火算法及流程图模拟退火算法是解决TSP问题的有效方法之
18、一，其最初的思想由Metropolis在1953年提出，Kirkpatrick在1983年成功地将其应用在组合最优化问题中。求解TSP的模拟退火算法模型可描述如下:解空间：解空间S是遍访每个城市恰好一次的所有路经，解可以表示为w1,w2 , wn，w1, , wn是1,2,n的一个排列，表明w1城市出发，依次经过w2, , wn城市，再返回w1城市。初始解可选为(1, n) ;目标函数：目标函数为访问所有城市的路径总长度;要求的最优路径是目标函数为最小值时对应的路径。随机产生1和n之间的两相异数k和m，不妨设km，将原路径(w1,w2,wk,wk+1,wm,wm+1,wn)变为新路径：(w1,
19、w2,wm,wk+1,wk,wm+1,wn)上述变换方法就是将k和m对应的两个城市在路径序列中交换位置,称为2-opt映射。图4.1展示了模拟退火算法的大体流程图。选一初始状态X0,作为当前解:并且确定初始温度T0，令当前的Xi=X0和Ti=T0。然后从Xi的邻域中随即选择Xj，计算Xi与Xi的路径差，比较差值。按一定方式将T降温，即令T(t+1)kT(t)，i=i+1，然后检查退火过程是否结束，如果不是继续交换，如果是的话输出Si作为最优输出。根据上述描述，模拟退火算法求解TSP问题的流程框图如图4.1所示：图4.1模拟退火算法的流程图4.1.2算法温度的选择和变化温度参数是模拟退火算法中一
20、个关键的参数，初始温度不够高或退火时间不够长将会使得搜索过快，从而使得算法容易陷于局部最优解。反之，如果温度过高或退火时间过长，将会造成算法在计算机上的运行时间过长，从而令人无法接受。因此，温度参数的设定影响到模拟退火算法能否收敛到全局最优解。1初始温度的选取由于模拟退火算法的求解不依赖于初始值，所有可从中随机选取一个初始状态。2温度的下降函数温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：T(t+1)kT(t) 公式（4.1）式中k为正的略小于1.00的常数，t为降温的次数模拟退火算法按照其温度下降的时刻可分为两
21、类，一类是时齐算法，在该算法中对于每一个固定温度t，计算对应的马尔可夫链的变化，直到达到一个稳定状态，然后再使温度下降。另一类是非时齐算法，整个过程仅由一个马尔可夫链构成，要求相连的状态转移中，温度t 是下降的。本文主要考虑了时齐算法的情况。该系统设置的温度下降系数为a=0.92，设置的初始温度为T=280。程序代码实现该部分功能：int *stimulation(int *x) int *result = NULL,*temp = NULL;double random = 0;int *j = new intamount;int *i = new intamount;for(int m=0;
22、m random0_1() )temp = i;i = j;j = temp;time+;while(time 1e-5);result = i;return result;4.1.3定义坐标表的具体参数与具体实现1城市坐标表的定义在这里我们选择了简单的TSP模型，应用10个点之间坐标。首先建立个二维坐标轴。在坐标轴上选择恰当的10个点，描绘和10个城市。分别给出这个10个点所在坐标轴上的坐标,以备主函数调用文本文件中点的坐标轴位置进行计算两个点之间的路径距离建立个表格。如表4.1所示: 表4.1 城市坐标表A4044B2414C1722D2276E5194F8765G6852H8436I66
23、25J6126将这个表4.1中的内容写在txt文本文件中保存并且命名“为huang.txt”。2计算不同城市之间的路径通过应用c+语言，进行编写计算给定坐标的2点之间的路径距离，并且根据每两点之间的距离计算出每产生一个新解的城市之间的距离总和。用来进行比较出所有路径之中的最小值的路径距离。程序代码实现该部分功能：计算两个城市之间的距离double distance(int x,int y)double result = 0;result = sqrt( (citycoordinatex0 - citycoordinatey0) * (citycoordinatex0 - citycoordin
24、atey0) + (citycoordinatex1 - citycoordinatey1) * (citycoordinatex1 - citycoordinatey1) );return result;计算某一个序列中城市之间的距离总和double evaluate(int *x)/double result = 0;for(int counter=0;counterm，则将(w1, w2 ,，wk , wk+1 ,，wm ,，wn)变为：(wm, wm-1 ,，w1 , wm+1 ,，wk-1 ,wn , wn-1 ,，wk)。本程序代码中利用上述所讲的 2-opt 方法产生新的路径。该
25、函数能够从一个父序列中找出一个随机的子序列，使得两个城市坐标位置互换。并且将交换的结果储存在result中。程序代码实现该部分功能：double random0_1(void) /产生随机数,范围在0-1之间return (double)rand() / (double)RAND_MAX;void Neighbour(int *i,int *result) /i代表父序列，result代表子序列。将交换结果存储在result中int n = 0,m = 0,temp = 0;for(int k=0;kamount;k+)resultk = ik;don = rand() % (amount -
26、 1);m = rand() % (amount - 1);while(n = m);n+;m+;temp = resultn;resultn = resultm;resultm = temp;int * random(void)int temp = 0,signal = 1,k=0;int *save =NULL;save = new intamount;for(int j=0;jamount;j+)savej = -1;dosignal = 1;temp = rand() % amount;for(int i=0;iamount;i+)if(savei = temp)signal = 0;
27、break;if(signal != 0)savek = temp;k+;while(signal = 0 | k != amount);for(int i=1;iamount;i+)if(savei=0)temp = savei;savei = save0;save0 = temp;return save;4.2求解TSP问题的算法主体模块详细设计主要介绍整个关键main（）函数主体和DOS界面上的显示计算概率的信息。此部分同时也包括了一些主要的程序代码。 模拟退火算法求解TSP问题的系统编程，主要通过主体函数中的读取文本文件中事先所记录的城市坐标来实现数据输入的。 利用函数中的定义的 *p
28、file 指针来实现函数对文本文件的处理。应用pfile = fopen( filename, r )语句来打开文件，并且通过fscanf(pfile, %d, &city_number);实现城市坐标的数据输入。 然后，通过srand( (unsigned)time( NULL ) );语句来设置的种子，即初始解得序列。并且，初始化序列。然后，将这个初始化序列解，计算它的最短路径。然后将这个初始化的解带入void Neighbour(int *i,int *result)中转化出一个新解。并且一次循环知道温度降低，达到平衡。之后，通过函数的得出的多个选择所要走的路径，路经的限制是每个城市只能
29、拜访一次，而且最后要回到原来出发的城市。选择出现的频率最高的路径最短路径，并且，显示出最短路径的值。其中，中间涉及到了一些函数调用，一个C+语言的程序有一个主函数和多个函数组成。主函数调用其他函数，其他函数也可以互相调用。C语言的函数调用遵循先定义，后调用的原则。主体main函数程序代码实现：int main(int argc, char* argv)charfilename81;floatfirsttemp, secondtemp;inti; FILE*pfile;printf(请输入旅行城市文件全名：);scanf(%s, &filename);/strcpy(filename, TSP1
30、0.txt);if( (pfile = fopen( filename, r ) = NULL )printf( 打不开旅行城市文件（%s）!n, filename);printf(请按任意键结束!);getch();return false;fscanf(pfile, %d, &city_number);amount = city_number;printf(n);for(i=0; icity_number; i+)fscanf(pfile, %st%ft%f, &citylisti, &firsttemp, &secondtemp);citycoordinatei0 = firsttemp
31、;citycoordinatei1 = secondtemp;fclose(pfile);srand( (unsigned)time( NULL ) ); /设置种子int *sequence; /初始序列sequence = random();for(i=0;i4;i+)Recperci.nvalue=1000;printf(序列t距离n);for(i=0; i10*amount; i+)out(stimulation(sequence);以上代码是系统程序的主要main函数代码，通过调用其它编写的代码函数还实行模拟整个模拟退火算法的主要内容。最后，在DOS界面中输出每一次新的邻域解产生的形
32、式和其在计算函数部分算出来的某一个序列中城市之间的距离总和。4.3算法的具体编码实现在前面已经介绍了大部分关键函数代码，以及得到最优解排序，并且统计最优解出现次数和计算出最优解的出现频率。所以，接下来将要把程序正确运行界面进行详细的讲解。4.3.1建立城市坐标文本文件通过4.2.2节中的表4.1，将表中的数据记录在其中并且命名为huang.txt。图4.2 建立的huang.txt同时，也可以自己编写具体的城市坐标，用来自己分析模拟退火算法求解TSP问题的优缺点。4.3.2 DOS下界面数据输出以及概率统计与分析这节主要介绍了输出界面的输出格式和数据的形式。在这里界面的输出输入形式主要应用的p
33、rintf语句和scanf语句进行完成的。Printf是C语言和C+语言提供的按指定格式进行标准输出的函数。而scanf是C语言和C+语言中提供的按指定格式进行标准输入的函数。首先是printf(请输入旅行城市文件全名：); scanf(%s, &filename);语句的输入使DOS界面显示的图4.3：图4.3 输入显示图DOS界面下显示出“清输入旅行城市文件全名”,这个也就是要求输入我们所编写文本文件huang.txt.。然后继续输入命令语句：printf( 打不开旅行城市文件（%s）!n, filename);printf(请按任意键结束!);printf(序列t距离n);printf(
34、最优解排序t序列ttt出现次数t出现的概率n);printf(请按任意键结束!);在输入完需要处理的信息数据之后，通过对新产生的邻域解进行统计列出序列和距离的数据在最后分别计算出所以有排序的路径的前4位数据，并且分别统计对应的序列解得出现次数和出现概率。例如图4.4：图4.4 统计概率和最优解程序代码如下：printf(最优解排序t序列ttt出现次数t出现的概率n);for(i=0;i4;i+)printf(%ft, Recperci.nvalue);for(int j=0; jamount; j+)printf(%c, Recperci.listj);float statlist = (fl
35、oat)(10*(float)Recperci.nflag/(float)amount);printf(tt%dt%2.2fn, Recperci.nflag, statlist);printf(请按任意键结束!);getch();return true;第五章 算法运行分析第4章给出了应用开发的组织结构和各个功能模块的具体实现，这章介绍程序编码实现后的运行界面图示以及结果分析情况。5.1 运行界面图示1成功运行程序到DOS界面下的截图运行Visual C+6.0在打开空间里添加已经编写完成的程序，调试成功后运行程序。然后，跳出DOS界面显示如图5.1：图5.1 成功在DOS下运行程序界面成功
36、运行了程序代码，DOS环境下显示出所要达到的目的。2输入要打的文件名输入要打开的文件名huang.txt。界面如图5.2：图5.2 输入文本文件的文件名3输入错误的文件在输入文件名处输入错误的文件观看反应，输入huan.txt文件名，反应如图5.3：图5.3 输入一个错误的文件名DOS环境下界面显示情况与预先预想的一样没有出现异常情况。4输入正确的文件与上面相反，输入正确的文件名观看系统的反应，程序反应如图5.4：图5.4 输入huang.txt之后运行界面程序运行正确的文件后，程序已经开始运行模拟退火算法进行分析解决TSP问题。图4.8显示的内容是产生的新邻域解和该新邻域解的所产生的路径总和
37、。用来判断并且寻找最优解。4.程序最后运行结果经过上面的一系列操作后，可继续观察程序运行情况，程序得出最终结果，如图5.5中用红色的笔画圈住的就是最优解排序以及其出现的次数和平均出现的概率。图5.5 成功得出最优解排序以及概率5.2 运行结果通过上面的运行图示截图展示了程序的总体流程，在图5.5中可以看出最终程序运行得到的最优解序列为ACBJIHGFED，这个最优解一共在程序运行中出项了42次，通过它计算出文件huang.txt中给出的10个坐标点的最短路径问题，计算的结果为270.273224。第六章 结束语模拟退火算法是将物理退火过程与组合优化相结合的一种随机迭代寻优算法，TSP问题即旅行
38、商问题是一个组合优化问题，该问题被证明具有NPC计算复杂性，因此研究模拟退化算法的基本原理及其在TSP问题求解中的应用受到高度的关注。本文给出了用模拟退火算法求解旅行商问题的流程，给出了各参数的如何取值。程序是在 Visual C +6.0 的环境中编写。该程序研究模拟退化算法的基本原理以及TSP组合优化问题，用一种程序语言实现基于模拟退火算法的TSP问题求解方法。并且本文说明了用模拟退火算法能够较好地求解旅行商问题。因而理论上能够找到最优解，但实际使用过程中诸多的参数如起始温度，温度下降速率，迭代次数等都需要人为的测试和调整，而这些参数将直接影响能否搜索到最优解，所以模拟退火算法仍然存在一些
39、缺点。参考文献1 王大志，汪定伟，闫杨. 一类多旅行商问题的计算及仿真分析J，系统仿真学报，2009年20期2 汪定伟等编著. 智能优化方法M，北京：高等教育出版社，20073 田景文，高美娟. 人工神经网络算法研究及应用M, 北京：北京理工大学出版社，20064 雷德明，严新平编著. 多目标智能优化算法及其应用M，北京：科学出版社，20095 刘升，王行愚，游晓明.求解TSP问题的文化蚁群优化算法J，华东理工大学学报， 2009年02期6 张晓如; 高尚. 求解旅行商问题的蚁群遗传混合算法J，微电子学与计算机，2009年04期7 邢文训著. 现代优化计算方法M,第2版，北京：清华大学出版社，20068 王万森著. 人工智能原理及其应用M,第2版，北京：电子工业出版社，20079 梁艳春等著. 群智能优化算法理论与应用M，北京：科学出版社，200910 Ingber L,Rosen B.Genetic algorithms and fast simulated annealing:A comparison.Mathematic Computer Modeling.1992,16():87-10011 康立山，谢云，罗祖华，非数值并行算法模拟退火算法M,北京:科学出版社,1997