纲要IAbstractII前言1第一章基本遗传算法21.1遗传算法的产生及发展.31.2基来源理.31.3遗传算法的特色.31.4基本遗传算法描绘.51.5遗传算法结构流程.6第二章遗传算法的实现技术62.1编码方法.7二进制编码.7格雷码编码.7符点数编码.8参数编码.82.2适应度函数.102.3选择算子.102.4交错算子.10单点交错算子.10双点交错算子.11均匀交错算子.11部分映照交错.11次序交错.122.5变异算子.122.6运转参数.122.7拘束条件的办理方法.132.8遗传算法流程图.14第三章遗传算法在TSP上的应用153.1TSP问题的建模与描绘.153.2对TSP的遗传基因编码方法.163.3针对TSP的遗传操作算子.17选择算子.17轮盘赌选择.17最优保存策略选择.17交错算子.20单点交错.20部分映照交错.21变异算子.233.4TSP的混和遗传算法.26第四章实例剖析274.1测试数据.274.2测试结果.274.3结果剖析.27摘要1TSP(TravelingSalesmanProblem)旅游商问题是一类典型的NP完好问题，遗传算法是解决NP问题的一种较理想的方法。文章第一介绍了基本遗传算法的基来源理、特色及其基本实现技术；接着针对TSP问题，阐述了遗传算法在编码表示和遗传算子（包含选择算子、交错算子变异算子这三种算子）等方面的应用状况，分别指出几种常用的编码方法的长处和弊端，并且联合TSP的运转实例详尽剖析了基本遗传算法的4个运转参数集体大小、遗传算法的停止进化代数、交错概率、变异概率，对遗传算法的求解结果和求解效率的影响，经过多次的测试设定出了它们一组比较合理的取值。最后，简单说了然混淆遗传算法在求解TSP问题中的应用并对遗传算法解决TSP问题的远景提出了展望。重点词：TSP遗传算法遗传算子编码AbstractTSP(TravelingSalesmanProblem)isatypicalNP-completeproblemandgenetic2algorithm(GA)istheperfectmethodforsolvingNP-completeproblem.Thebasictheories,characteristicsandthebasictechniquesofGAarefirstintroduced.Thentheencodingmodelandgeneticoperators(includingselectionoperation,crossoveroperationandmutationoperation)aboutGAinsolvingTSParediscussed.Theadvantagesanddisadvantagesofvariousencodingmethodarerespectivelyindicated,andtheapplicationofthethreebasicgeneticoperatorsiselaborated.Accordingtothegivendata,theresultsandefficienciesareinfluencedbyfourparametersinthebasicgeneticalgorithm:thesizeofpopulation,terminategeneration,crosserprobabilityandmutationprobability.Adjusttheparameters,runandtryforbetterones.Atlast,theapplicationofhybridgeneticalgorithmisbrieflypresented.Itispointedoutthatabettercrossoverormutationroutinecanbefoundoutwhichretainsthestructurefromtheparentchromosomesandstillendsupwithalegaltourinthechildchromosomes,whichleadstoabettersolutionthaneverbefore.AndtheprospectforthefutureofgeneticalgorithminsolvingTSPismade.Keywords:TSPgeneticalgorithmgeneticoperatorsencoding前言3现代科学理论研究与实践中存在着大批与优化、自适应有关的问题，但除了一些简单的状况以外，人们关于大型复杂系统的优化和自适应问题仍旧力所不及。但是，自然界中的生物却在这方面表现出了其优秀的能力，它们能够以优胜劣汰、适者生计的自然进化规则生计和繁衍，并逐渐产生出对其生计环境适应性很高的优秀物种。遗传算法正是借鉴生物的自然选择和遗传进化体制而开发出的一种全局优化自适应概率搜寻算法。遗传算法使用集体搜寻技术，它经过对目前集体施加选择、交错、变异等一系列遗传操作，进而产生出新一代的集体，并逐渐使集体进化到包含或靠近最优解的状态。因为其拥有思想简单、易于实现、应用成效显然等长处而被众多应用领域所接受，并在自适应控制、组合优化、模式辨别、机器学习、人工生命、管理策略等领域获取了宽泛应用。遗传算法给我们表现出的是一类通用的算法框架，该框架不依靠于问题的种类。遗传算法是一类拥有较强鲁棒性的优化算法，特别是关于一些大型、复杂非线性系统，它更表现出了比其余传统优化方法更为独到和优胜的性能。隐含并行性和全局搜寻特征是遗传算法的两大明显特色。遗传算法是新发展起来的一门学科，各样理论、方法还没有成熟，有待于进一步地发展和完美，但它却为我们解决很多复杂问题供给了希望。只管在遗传算法的研究和应用过程中出现很多灾题，同时也会产生很多不一样的算法设计看法，但是，目前遗传算法的各样应用实践已经显现出了其优秀的性能和巨大的发展潜力，它的发展远景激励着各种专业技术人员把遗传算法的理论和方法运用于自己的工作实践中。我们相信，跟着研究工作的进一步深入和发展，遗传算法势必在智能计算领域中起到重点作用。货郎担问题(TravelingSalesmanProblem,TSP)，也称为巡回旅游商问题，是一个较古的问题。最早能够追忆到1759年Euler提出的骑士旅游问题。TSP问题是一个典型的、简单描绘可是难以办理的NP完好问题，同时TSP问题也是诸多领域内出现的多种复杂问题的集中归纳和简化形式。目前求解TSP问题的主要方法有启迪式搜寻法、模拟退火算法、遗传算法、Hopfield神经网络算法、二叉树描绘算法。所以，有效解决TSP问题在计算理论上和实质应用上都有很高的价值，并且TSP问题因为其典型性已经成为各样启迪式的搜索、优化算法的间接比较标准(如遗传算法、神经网络优化、列表寻优(TABU)法、模拟退火法等)。遗传算法就其实质来说，主假如解决复杂问题的一种鲁棒性强的启迪式随机搜寻算法。所以遗传算法在TSP问题求解方面的应用研究，关于结构适合的遗传算法框架、成立有效的遗传操作以及有效地解决TSP问题等有着多方面的重要意义。4第一章基本遗传算法1.1遗传算法的产生及发展最早