毕业设计（论文）--一种改进的遗传算法求解TSP问题

《毕业设计（论文）--一种改进的遗传算法求解TSP问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、毕业设计（论文）2010届题目一种改进的遗传算法求解TSP问题专业数学与应用数学学生姓名袁成平学号06071246指导教师姜长元论文字数8000完成日期2010年5月湖州师范学院教务处印一种改进的遗传算法求解TSP问题袁成平06071246摘要：TSP问题是一个典型的组合优化问题，在实际应用中有很高的价值，而且TSP问题由于其典型性已经成为各种启发式的搜索优化算法的间接比较标准。不过如何求解TSP问题一直是国际上的一个难题。因其可能的路径总数与城市数目n成指数型增长，一般很难精确地求出最优解。而遗传算法是一种广泛使用的全局优化算法，并且已经成功地用于求解TSP问题。

2、这里对TSP问题提出了一种改进的遗传算法，通过对遗传算法的评估函数、交叉和变异方法以及参数选择等方面的分析和修改,构造了一种自适应函数以及交叉、变异方法。通过对CHN144的测试，实验结果证明此处提出的方法能更有效的求解TSP问题。关键词：TSP，遗传算法，组合优化，编码AnImprovedGeneticAlgorithmforTSPproblemYuanchengping06071246Abstract:TSPproblemisatypicalcombinatorialoptimizationproblem,inpracticalapplicationsisofg

3、reatvalue,butalsobecauseofitstypicalTSPproblemhasbeenvariousheuristicsearchalgorithmoftheindirectstandardforcomparison.ButhowtosolvetheTSPproblemhasalwaysbeenaproblemfortheinternationalcommunity.Becausethetotalnumberofpossiblepathsintothecitynthenumberofexponentialgrowth,thegeneralisdi

4、fficulttoaccuratelydeterminetheoptimalsolution.Thegeneticalgorithmisawidelyusedglobaloptimizationalgorithm,andhasbeensuccessfullyusedtosolvetheTSPproblem.ThisarticlewillintroducetheTSPproblemandthebasicprinciplesofgeneticalgorithmsandfeatures;forsolvingTSPproblemsDiscussesthegeneticalg

5、orithmcodingandgeneticoperators,saidtheareasofapplication.Keywords:TSP;geneticalgorithm;combinatorialoptimization;coding目录前言…………………………………………………………………………………………………1第一章基础知识简介第一节TSP问题简介………………………………………………………………………1第二节遗传算法简介………………………………………………………………………1第二章遗传算法求解TSP问题一般过程……………………………………………………2第

6、三章算法分析………………………………………………………………………………3第四章TSP问题的改进遗传算法………………………………………………………………3结论…………………………………………………………………………………………………7参考文献……………………………………………………………………………………………8致谢…………………………………………………………………………………………………9前言11TSP问题有着很长的历史，早在18世纪就被人们提出。遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方

7、法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《AdaptationinNaturalandArtificialSystems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。后来经过人们的不断探索创新，遗传算法很快被人们广为使用，使用领域也越来越广泛。这里就来介绍一种改进的遗传算法求解TSP问题。第一章：基础知识简介第一节、TSP问题简介TSP问题,也称为货郎担问题（或旅行商问题），最早可以追溯到1759年Euler提出的骑士旅行问题。TSP问题的简单描述