遗传算法求解tsp问题的计算机仿真论文

《遗传算法求解tsp问题的计算机仿真论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、遗传算法求解TSP问题的计算机仿真毕业论文目录遗传算法求解TSP问题的计算机仿真IAbstractII1绪论11.1研究背景11.2研究意义21.3研究内容21.4本文的结构32遗传算法理论概述42.1遗传算法的产生及发展42.2遗传算法基本原理52.3遗传算法基本步骤62.4遗传算法算法流程图62.5遗传算法的特点72.6遗传算法的应用83基于遗传算法求解TSP问题103.1旅行商问题的描述与建模103.2编码方式103.3遗传算子的设计（交叉、选择、变异）123.3.1交叉算子123.3.2选择算子133.3.3变异算子143.4适应度函数15533

2、.5遗传算法求解TSP问题的具体流程图16445个城市旅行商问题的仿真软件的设计174.1系统设计模块174.2系统详细设计174.2.1演示模块设计184.2.2帮助模块设计214.3测试结果及分析224.3.1测试一224.3.2测试二244.3.3测试三264.3.4测试四284.3.5测试五295结论31参考文献32谢　辞33附录一程序34附录二外文翻译55531绪论自20世纪60年代以来,一种模拟生物自然遗传与进化过程并将生物进化原理、最优化技术和计算机技术结合起来的优化方法—遗传算法（GeneticAlgorithm,简称GA）被提出并得到广

3、泛研究，该算法特别适用于处理传统搜索方法难以解决的复杂和非线性问题，可以广泛应用于人工智能、机械设计、自适应控制等领域。遗传算法固有的并行性和并行计算的能力，使在搜索过程中不容易陷入局部最优。即使在所定义的适应度函数中是不连续的、不规则的情况下，也可以很大概率找到全局最优解。采用自然进化机制来表现复杂的现象，能够快速可靠地解决求解非常困难的问题，非常适用于本课题涉及的TSP问题的求解与研究。旅行商问题（TravelingSalesmanProblem,TSP）是一个非常经典的组合优化问题的NP难题，长期以来都没有一个十分有效的算法来解决它，但TSP本身在

4、许多领域有着重要的应用，如连锁店的货物配送路线、计算机网络路由器遍历、印刷电路板的钻孔路线等问题都可以建模为旅行商问题。TSP问题其实是“哈密顿回路问题”中的“哈密顿最短回路问题”。在本系统就是要应用遗传算法求解45个城市的TSP问题。因为遗传算法本身是模拟生物自然选择和遗传的过程的，所以用遗传算法求解TSP最先要确定的是问题的建模，即如何用遗传学的算子来表示旅行商问题中的变量。必需要非常的了解，并熟悉每一个遗传学中的术语在遗传学中的具体作用，然后应用到求解具体问题当中来。应用遗传算法求解旅行商问题最关键的是编码方式、交叉、选择、变异算子的设计，直接关系

5、到算法能否求出最优解或近似最优解。所以要在编码方式的确定上做好足够的功夫，以确定程序求解的精确度。本章主要论述本文所研究的主要内容，并对论文的章节结构进行规划。1.1研究背景旅行商问题（TravelingSalesmanProblem,TSP）,也称旅行推销员问题，具体的数学模型可以这样理解：现在给定以下几个城市的位置，旅行商从其中的某一个城市出发，不重复地访问其余的每一个城市，最后又返回到原出发点城市，要求找出这样一条路线，使旅行所付出的代价最小。虽然它是一个比较古老的问题，最早可以追溯到Euler提出的骑士旅行问题，但同时它也是一个新的问题，因为它的

6、计算复杂度较高，虽然人们一直在尝试用新的方法来改进求解该问题的复杂度，但是这一类问题距今都没有能找到一个有效的算法来解决。53TSP问题可以形式化描述为：设G=（V,A,D）是一个图，其中V是n个顶点的集合，A是弧线或边集,D=（dij）是与A关联的距离或费用矩阵。旅行商问题就是要解决一个最小回路问题，回路中所有顶点有且仅经过一次。对于具有一个城市的旅行商问题，其可能的路径数目为（n-1）！/2，5个城市的问题模型就对应120/10=12条路线，10个城市的问题模型对应3628800/20=181440条路线。所以当输入越大，则耗费的时间就是个天文数字了

7、，因此旅行商问题至今都没有能找到一种有效的求解方法。寻求一种能短时间求解出高精度解的算法，已成为此问题研究的热门。尽管旅行商问题至今仍然没有找到最优解，但求解它的算法已经在不断的改进。目前，求解TSP问题常用的算法主要有遗传算法和蚁群算法，另外还有爬山法、模拟退火算法、神经网络方法、贪婪算法、禁忌搜索算法等。1980Crowder和Padberg求解了318个城市的TSP问题；1987年Padberg和Rinaldi成功将城市数量增加到了2392个；最大的成功求解的旅行商问题已经增加到24798个城市。1.2研究意义首先旅行商问题是用于求解N个城市存在（

8、N-1）条闭合路径的排列方案，对于这一类问题很难用全局搜索法精确地求出最优解，这