毕业设计（论文）-遗传算法在求解TSP问题毕业论文.doc

毕业设计（论文）-遗传算法在求解TSP问题毕业论文.doc:..摘要IAbstractII引言1第一章基本遗传算法 14第三章遗传算法在TSP± 26第四章实例分析 27摘要TSP(TravelingSalesmanProblem)旅行商问题是一类典型的NP完全问题,遗传算法是解决NP问题的一种较理想的方法。文章首先介绍了基本遗传算法的基本原理、特点及其基本实现技术;接着针对TSP问题,论述了遗传算法在编码表示和遗传算子(包括选择算子、交叉算子变异算子这三种算子)等方面的应用情况,分别指出几种常用的编码方法的优点和缺点,并且结合TSP的运行实例详细分析了基本遗传算法的4个运行参数群体大小、遗传算法的终止进化代数、交叉概率、变异概率,对遗传算法的求解结果和求解效率的影响,经过多次的测试设定出了它们一组比较合理的取值。最后,简单说明了混合遗传算法在求解TSP问题屮的应用并对遗传算法解决TSP问题的前景提岀了展望。关键词:TSP遗传算法遗传算子编码AbstractTSP(TravelingSalesmanProblem)icalgorithm(GA),(includingselectionoperation,crossoveroperationandmutationoperation),icoperatorsiselaborated・Accordingtothegivendata,icalgorithm:thesizeofpopulation,terminategeneration,,runandtryforbetterones・Atlast,,:icoperatorsencoding引言现代科学理论研究与实践屮存在着大量与优化、自适应相关的问题,但除了一些简单的情况Z外,人们对于大型复朵系统的优化和自适应问题仍然无能为力。然而,白然界屮的生物却在这方面表现出了其优异的能力,它们能够以优胜劣汰、适者生存的自然进化规则生存和繁衍,并逐步产生出对其牛存环境适应性很高的优良物种。遗传算法正是借鉴生物的口然选择和遗传进化机制而开发出的一种全局优化口适应概率搜索算法。遗传算法使用样体搜索技术,它通过对当前群体施加选择、交义、变异等一系列遗传操作,从而产生出新i代的群体,并逐步使群体进化到包含或接近最优解的状态。由于