精品毕业论文--基于遗传算法的tsp问题研究

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

1、目录摘要IAbstractII第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的应用

2、-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-II摘要TSP问题(TravelingSalesmanProblem)是已知有n个城市，现有一推销员必须遍访这n个城市，且每个城市只能访问一次，最后又必须返回出发城市。要安排其访问次序，使其旅行路线的总长度最短。TSP是经典的NP-hard组合优

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

4、heTSPquestionisoneofmostclassicalNP—hardcombinationoptimizationquestions，anditisalsoastandardquestiontotestalgorithmperformance．Inthereality,therealemanyapplicationquestionscanbesummeduporconvertedintoTSP.Thereforesolvethisproblemissignificancewithboththetheoryandpract

5、ical．Tolarge-scaleproblems，thetraditionalsolutionmethodistooinadequate.GeneticAlgorithm(GA)isallalgorithmwhichishighlyparallel，stochasticandauto—adaptedsearching．Itisprofitsfromonekindwhichthebiologicalchoiceandtheevolutionmechanism．Especially,itqualifiesinthequestions

6、thatcomplexandnon-linearfortraditionsearchingalgorithm．Itstwomostmajoroutstandingfeaturesareconcealparallelismandtheglobalsearch．Tothegeneticalgorithmandtheapplicationresearchofitisonehotspotoftheintelligentcomputationstratosphere．Keywords：geneticalgorithm;TSP;crossove

7、roperaII第1章绪论1.1旅行商问题旅行商问题(TravelingSalesmanProblem，TSP)，也称货郎担问题，是指对于给定的甩个城市，旅行商从某一个城市出发，不重复地访问其余每一个城市，最后又返回到原出发城市，要求找出一条旅行路线，使其的旅行所付出的代价最小。旅行商问题是一个比较古老的问题，最早可追溯到Euler提出的骑士旅行问题，同时它也是个“新问题"，因为计算的复杂性较高，人们一直在尝试用新的方法来改进求解该问题的复杂度。TSP问题是一个具有广泛的应用背景和重要理论价值的组合优化问题，它是一个典型的NP问题。

8、G=（V，E）为赋权图，V=1，2，…，N为顶点集，E为边集，Cij表示旅行商经过对应弧段（i，j）所花的费用，如时间、距离、花费等。TSP问题就是要决定一条经过图中所有顶点，当且仅当一次且代价最小的回路，即代价最小的Hamilton