基于遗传算法的旅行商问题求解毕业论文

《基于遗传算法的旅行商问题求解毕业论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于遗传算法的旅行商问题求解摘要采用MATLAB，对TSP问题进行基于遗传算法的求解。TSP问题是典型的NP完全问题，通过MATLAB进行遗传算法编程，从而有效提出一个较好的TSP解，实现对问题的解答。进而讨论遗传算法的特点，以及对本问题的可行性。关键词：TSP问题遗传算法35毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和

2、做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作者签名：　　　　　日　期：　　　　　指导教师签名：　　　　　日　　期：　　　　　使用授权说明本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名：　　　　　日　期：　　　　　35学位论文原创性声明本人郑重声明：所呈交的论文

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

4、名：日期：年月日导师签名：日期：年月日35一．问题重述假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。二．遗传算法（GA）概述遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Ho

5、lland教授于1975年首先提出来的，并出版了颇有影响的专著《AdaptationinNaturalandArtificialSystems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。三．问题分析TSP问题就是寻找一条最短的遍历n个城市的最短路径,即搜索自然数子集W={1,2,⋯,n}(W的元素表示对n个城市的编号)的一个排列π(W)={V1,V2,⋯,Vn},使len=∑d(Vi,Vi+1)+d(V1,Vn)取最小值,式中的d(Vi,Vi+1)表示城市Vi到城市Vi+1的距离.遗传算法是具有“生成+检测”的迭代过程的搜索算法。它

6、的基本处理流程如图1所示。由此流程图可见，遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。选择（Selection）、交叉（Crossover）和变异（Mutation）是遗传算法的3个主要操作算子，它们构成了所谓的遗传操作（geneticoperation），使遗传算法具有了其它传统方法所没有的特性。遗传算子包含如下6个基本因素：（1）参数编码：由于遗传算法不能直接处理解空间的解数据，因此必须通过编码将它们表示成遗传空间的基因型串结构数据。（2）生成初始群体：由于遗传算法的群体型操作需要，所以必须为遗传操作准备一个由若干初始解组成的初始群体。初始群体的每个个体都是通过随机

7、方法产生。（3）适应度评估检测：遗传算法在搜索进化过程中一般不需要其他外部信息，仅用适应度（fitness）值来评估个体或解的优劣，并作为以后遗传操作的依据。（4）选择（selection）：选择或复制操作是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。个体适应度越高，其被选择的机会就越多。此处采用与适用度成比例的概率方法进行选择。具体地说，就是首先计算群体中所有个体适应度的总和（），再计算每个个体的适应度所占的比例（），并以此作为