基于遗传算法的TSP问题研究

设计题目：_____基于遗传算法的TSP问题研究_学院：_______计算机与信息学院_______专业年级：________学号：________________学生姓名：___郑海钦__________指导教师、职称：____2011年5月25日I目录摘要..........................................................................IAbstract.....................................................................II第1章绪论...............................................................-1-1.1旅行商问题.........................................................-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编码..............................................................-12-4.4初始化种群........................................................-13-4.5适应度函数........................................................-13-4.6选择操作..........................................................-13-4.7交叉操作..........................................................-15-4.8变异操作..........................................................-17-4.9实验结果..........................................................-18-结论...................................................................-20-展望.....................................................................-20-参考文献..............................................................-21-致谢...................................................................-22-附录程序.................................................................-23-I摘要TSP问题(TravelingSalesmanProblem)是已知有n个城市，现有一推销员必须遍访这n个城市，且每个城市只能访问一次，最后又必须返回出发城市。要安排其访问次序，使其旅行路线的总长度最短。TSP是经典的NP-hard组合优化问题之一，也是一个测试算法优劣性的标准问题，且现实中有很多应用问题都可归结或转化为TSP问题。故对此问题的求解具有理论与实用两方面的意义。传统的求解方法在面对较大规模的问题时，很不容易得到最优解。遗传算法(GeneticAlgorithms，简称GA)是借鉴生物选择和进化机制发展起来的一种高度并行、随机和自适应搜索算法。特别适合于处理传统搜索算法解决不好的复杂和非线形问题。它的两个最大的显著特点是隐含并行性和全局搜索。对遗传算法及其应用的研究是目前智能计算的研究热点之一。关键词：遗传算法；TSP问题；交叉算子IIAbstractTheTSPquestionisoneofmostclassicalNP—hardcombinationoptimizationquestions，anditisalsoastandardquestiontotestalgorithmperformance．Inthereality,therealemanyapplicationquestionscanbesummeduporconvertedintoTSP.Thereforesolvethisproblemissignificancewithboththetheoryandpractical．Tolarge-scaleproblems，thetraditionalsolutionmethodistooinadequate.GeneticAlgorithm(GA)isallalgorithmwhichishighlyparallel，stochasticandauto—adaptedsearching．Itisprofitsfromonekindwhichthebiologicalchoiceandtheevolutionmechanism．Especially,itqualifiesinthequestionsthatcomplexandnon-linearfortraditionsearchingalgorithm．Itstwomostmajoroutstandingfeaturesareconcealparallelismandtheglobalsearch．Tothegeneticalgorithmandtheapplicationresearchofitisonehotspotoftheintelligentcomputationstratosphere．Keywords：geneticalgorithm;TSP;crossoveropera福建农林大学本科毕业论文-1-第1章绪论1.1旅行商问题旅行商问题(TravelingSalesmanProblem，TSP)，也称货郎担问题，是指对于给定的甩个城市，旅行商从某一个城市出发，不重复地访问其余每一个城市，最后又返回到原出发城市，要求找出一条旅行路线，使其的旅行所付出的代价最小。旅行商问题是一个比较古老的问题，最早可追溯到Euler提出的骑士旅行问题，同时它也是个“新问题，因为计算的复杂性较高，人们一直在尝试用新的方法来改进求解该问题的复杂度。TSP问题是一个具有广泛的应用背景和重要理论价值的组合优化问题，它是一个典型的NP问题。G=（V，E）为赋权图，V=1，2，…，N为顶点集，E为边集，Cij表示旅行商经过对应弧段（i，j）所花的费用，如时间、距离、花费等。TSP问题就是要决定一条经过图中所有顶点，当且仅当一次且代价最小的回路，即代价最小的Hamilton回路，为简化问题。1.2研究意义旅行商问题是一个理想化的问题，大多数对于此问题的研究都不是为了直接的实际应用，但这些研究可以经转化后用于许多现实的组合优化问题。在现实生活中，有许多问题都可以归结为TSP问题，如电路板钻孔路线选择、车辆路线问题、计划任务、连锁店货物配送路线、管道铺设、火炬接力等问题，这些问题的求解策略均可依据TSP问题的求解算法来加以实施。所以TSP问题在计算理论上和实际应用上都有很高的价值，将直接带动整个组合优化领域新的发展。而遗传算法是一种的元启发式优化算法,基于遗传算法在许多方面有重要的应用空间。基于此原因，本文的主要是用遗传算法的基本算子解决TSP这个有意义的NP难问题。1.3论文的组织结构第1章绪论。本章论述旅行商问题的基本概念，以及本课题的主要研究内容及其研究意义，并对本文的章节结构加以概述。第2章，概要介绍了遗传算法的起源和发展、思想及应用等问题，并重点介绍了基本遗传算法。第3章概要介绍了TSP问题的定义和数学模型、研究现状及评价标准，现有的求解TSP问题的几种算法。第4章本章论述如何用基于遗传算法求解TSP问题。详细论述了用遗传算法在TSP的实现方法和主要参数设置、程序实现。第5章总结福建农林大学本科毕业论文-2-第2章遗传算法理论概述2.1遗传算法的起源和发展20世纪40年代以来，科学家努力从生物学中寻找用于计算机科学和人工系统的新思维、新方法和新途径，生命科学与工程科学相互交叉、相互渗透、相互促进成为近代科学发展的显著特点之一。遗传算法正是从大自然的杰作——生物进化论中得到的灵感和启迪，其基本思想是Darwin进化论和Mendel的遗传学说。Darwin进化论最核心的是自然选择学说。他认为，生物进化是一个缓慢的变化过程，物种不是被创造出来的，而是自然选择的必然结果。“物竞天择，适者生存”。生物要想生存下来，就必须进行生存斗争。斗争是多方面的，有种内斗争、种间斗争以及生物与无机环境间的斗争。只有适应性强的个体才能在斗争中存活下来，并且有更多的机会将有利变异传给后代；而不适应斗争环境、具有不利变异的个体将面临淘汰。Darwin把这种在生存斗争中适者生存、不适者淘汰的过程称为自然选择。Mendel遗传学说最重要的是基因遗传原理。他认为遗传以密码方式存在于细胞中