基于遗传算法的tsp问题研究_毕设论文.doc

《基于遗传算法的tsp问题研究_毕设论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、设计题目：_____基于遗传算法的TSP问题研究_学院：_______计算机与信息学院_______II毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作者签名：　　　　　日　期：　　　　　指导教师签名：

2、　　　　　日　　期：　　　　　使用授权说明本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名：　　　　　日　期：　　　　　II学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已

3、经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权　　　　大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期：年月日导师签名：日期：年月日II目录摘要IAbstractII第1章绪论-1-1.1

4、旅行商问题-1-1.2研究意义-1-1.3论文的组织结构-1-第2章遗传算法理论概述-2-2.1遗传算法的起源和发展-2-2.2遗传算法基本原理-3-2.3遗传算法的基本步骤-4-2.4遗传算法的流程图-4-2.5遗传算法的特点-5-2.6遗传算法的应用-6-第3章TSP问题及研究的基本方法-8-3.1TSP问题概述-8-3.2TSP的应用与价值-8-3.3TSP问题的数学模型-9-3.4TSP问题的分类-9-3.5现有的求解TSP问题的几种算法-10-第4章遗传算法在TSP的应用-12-4.1遗传算法在TSP上的应用-12-4.2算法的实现-12-4.3编码-

5、12-4.4初始化种群-13-4.5适应度函数-13-4.6选择操作-13-4.7交叉操作-15-4.8变异操作-17-4.9实验结果-18-结论-20-展望-20-参考文献-21-致谢-22-附录程序-23-II摘要TSP问题(TravelingSalesmanProblem)是已知有n个城市，现有一推销员必须遍访这n个城市，且每个城市只能访问一次，最后又必须返回出发城市。要安排其访问次序，使其旅行路线的总长度最短。TSP是经典的NP-hard组合优化问题之一，也是一个测试算法优劣性的标准问题，且现实中有很多应用问题都可归结或转化为TSP问题。故对此问题的求解

6、具有理论与实用两方面的意义。传统的求解方法在面对较大规模的问题时，很不容易得到最优解。遗传算法(GeneticAlgorithms，简称GA)是借鉴生物选择和进化机制发展起来的一种高度并行、随机和自适应搜索算法。特别适合于处理传统搜索算法解决不好的复杂和非线形问题。它的两个最大的显著特点是隐含并行性和全局搜索。对遗传算法及其应用的研究是目前智能计算的研究热点之一。关键词：遗传算法；TSP问题；交叉算子IIAbstractTheTSPquestionisoneofmostclassicalNP—hardcombinationoptimizationquestion

7、s，anditisalsoastandardquestiontotestalgorithmperformance．Inthereality,therealemanyapplicationquestionscanbesummeduporconvertedintoTSP.Thereforesolvethisproblemissignificancewithboththetheoryandpractical．Tolarge-scaleproblems，thetraditionalsolutionmethodistooinadequate.GeneticAlgorith

8、m(GA)isallal