基于遗传算法的tsp问题研究毕业设计

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

1、中央广播电视大学开放教育计算机专业毕业论文基于遗传算法的tsp问题研宄姓名：_学校：_学号：_指导教师:定稿曰期:河南广播电视大学15410012113882016年12月5日摘要TSP问题又称为货郎担问题。TSP是一个典型的优化组合问题，它需要求出旅行商从某一城市出发经过所有城市所走路程的最短路径，其可能的路径数与城市个数成指数关系增长。找出有效的近似求解算法具有重要的意义。选择用遗传算法去解决TSP问题。本论文对各个算子分别选择的是基于序的评估函数、轮盘赌选择法、两点交叉法、两点区间随机排序变异法，并且通过30个城市的实际的例子来验证，结果求出最短路径为

2、421.5977,优于二叉树描述法的结果428.90,启发式搜索法的结果436.01，表明遗传算法在求解TSP问题上是存效的。关键词：组合优化；TSP问题；遗传算法；最短路径AbstractTSPproblemisalsoknownasthetravelingsalesmanproblem.TSPisatypicalportfoliooptimizationproblemandneedstocalculatetheshortestpaththatatravelingsalesmangoesthroughallcities.Thenumberoftheposs

3、iblepathsmaygrowwithindexofthenumberofcities.Itisofgreatsignificancetofindoutaneffectiveapproximatealgorithm.ItisusedgeneticalgorithmstosolvetheTSPproblem.Inthispaper,theoperatorsarefitnessfunctionbasedonsequencechoice,selectionwiththelawofroulettegambling,two-pointcrossover,two-po

4、intrandomintervalmutation.Anactualexamplethrough30citiesisgot.Theresultis421.5977oftheshortestpath,whichisbetterthanbinarytreedescriptionwiththeresultof428.90,heuristicsearchwiththeresultof436.01，andshowsthatthegeneticalgorithmforTSPiseffective.Keywords:CombinatorialOptimization;TS

5、P;GeneticAlgorithm;theShortestPath@4穀4遗传算法的设计思想8系统实现9程序的运行演示12测试运行13模块测试13整体测试13在测试过程中使用到的调试技术：13评估运行的可靠性问题：13测试结论14街仑15参考文献16绪论一、遗传算法概述和发展背景(1)遗传算法简介遗传算法(GeneticAlgorithm,简称GA)是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Ada

6、ptationinNaturalandArtificialSystems»,GA这个名称方逐渐为人所知，J.Hilland教授所提出的GA通常为简单遗传算法(SGA)。遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的，而一个种群则由经过基因(gene)编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现(即基因型)是某种基因组合，它决定Y个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的

7、。这个过程将导致种群像自然进化一样，后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码(decoding),可以作为问题近似最优解［1］。(2)遗传算法特点遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要右以下特点:(1)遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便地应用遗传操作算子。（2）遗传算法直接以适应度作为搜索信息，无需导数等其它辅助

8、信息。二、关于TSP问题的简介TSP（Traveli