毕业论文题目基于遗传算法的tsp问题研究学院计算机与科学技术专业计算机科学与技术学号200213137193学生姓名张三指导教师李四日期二·〇〇八年六月摘要TSP问题又称为货郎担问题。TSP是一个典型的优化组合问题，它需要求出旅行商从某一城市出发经过所有城市所走路程的最短路径，其可能的路径数与城市个数成指数关系增长。找出有效的近似求解算法具有重要的意义。选择用遗传算法去解决TSP问题。本论文对各个算子分别选择的是基于序的评估函数、轮盘赌选择法、两点交叉法、两点区间随机排序变异法，并且通过30个城市的实际的例子来验证，结果求出最短路径为421.5977，优于二叉树描述法的结果428.90，启发式搜索法的结果436.01，表明遗传算法在求解TSP问题上是有效的。关键词：组合优化；TSP问题；遗传算法；最短路径AbstractTSPproblemisalsoknownasthetravelingsalesmanproblem.TSPisatypicalportfoliooptimizationproblemandneedstocalculatetheshortestpaththatatravelingsalesmangoesthroughallcities.Thenumberofthepossiblepathsmaygrowwithindexofthenumberofcities.Itisofgreatsignificancetofindoutaneffectiveapproximatealgorithm.ItisusedgeneticalgorithmstosolvetheTSPproblem.Inthispaper,theoperatorsarefitnessfunctionbasedonsequencechoice,selectionwiththelawofroulettegambling,two-pointcrossover,two-pointrandomintervalmutation.Anactualexamplethrough30citiesisgot.Theresultis421.5977oftheshortestpath,whichisbetterthanbinarytreedescriptionwiththeresultof428.90,heuristicsearchwiththeresultof436.01,andshowsthatthegeneticalgorithmforTSPiseffective.Keywords:CombinatorialOptimization;TSP;GeneticAlgorithm;theShortestPath目录TOC\o"1-3"\h\z\uHYPERLINK\l"_Toc467333343"目录PAGEREF_Toc467333343\h4HYPERLINK\l"_Toc467333344"绪论PAGEREF_Toc467333344\h5HYPERLINK\l"_Toc467333345"1遗传算法的设计思想PAGEREF_Toc467333345\h8HYPERLINK\l"_Toc467333346"2系统实现PAGEREF_Toc467333346\h9HYPERLINK\l"_Toc467333347"3程序的运行演示PAGEREF_Toc467333347\h12HYPERLINK\l"_Toc467333348"4测试运行PAGEREF_Toc467333348\h13HYPERLINK\l"_Toc467333349"4.1模块测试PAGEREF_Toc467333349\h13HYPERLINK\l"_Toc467333350"4.2整体测试PAGEREF_Toc467333350\h13HYPERLINK\l"_Toc467333351"4.2.1在测试过程中使用到的调试技术：PAGEREF_Toc467333351\h13HYPERLINK\l"_Toc467333352"4.2.2评估运行的可靠性问题：PAGEREF_Toc467333352\h13HYPERLINK\l"_Toc467333353"4.3测试结论PAGEREF_Toc467333353\h14HYPERLINK\l"_Toc467333354"结论PAGEREF_Toc467333354\h15HYPERL