目录
摘要I
AbstractII
引言1
第一章基本遗传算法2
1.1遗传算法的产生及发展3
1.2基本原理3
1.3遗传算法的特点3
1.4基本遗传算法描述5
1.5遗传算法构造流程6
第二章遗传算法的实现技术6
2.1编码方法7
2.1.1二进制编码7
2.1.2格雷码编码7
2.1.3符点数编码8
2.1.4参数编码8
2.2适应度函数10
2.3选择算子10
2.4交叉算子10
2.4.1单点交叉算子10
2.4.2双点交叉算子11
2.4.3均匀交叉算子11
2.4.4部分映射交叉11
2.4.5顺序交叉12
2.5变异算子12
2.6运行参数12
2.7约束条件的处理方法13
2.8遗传算法流程图14
第三章遗传算法在TSP上的应用15
3.1 TSP问题的建模与描述15
3.2对TSP的遗传基因编码方法16
3.3针对TSP的遗传操作算子17
3.3.1选择算子17
3.3.1.1 轮盘赌选择17
3.3.1.2 最优保存策略选择17
3.3.2交叉算子20
3.3.2.1单点交叉20
3.3.2.2部分映射交叉21
3.3.3变异算子23
3.4TSP的混和遗传算法26
第四章实例分析27
4.1测试数据27
4.2测试结果27
4.3结果分析27
摘要
TSP(TravelingSalesmanProblem)旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。文章首先介绍了基本遗传算法的基本原理、特点及其基本实现技术；接着针对TSP问题，论述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况，分别指出几种常用的编码方〖本文来自：毕业设计论文网www.paper51.com〗法的优点和缺点，并且结合TSP的运行实例详细分析了基本遗传算法的4个运行参数群体大小、遗传算法的终止进化代数、交叉概率、变异概率，对遗传算法的求解结果和求解效率的影响，经过多次的测试设定出了它们一组比较合理的取值。最后，简单说明了混合遗传算法在求解TSP问题中的应用并对遗传算法解决TSP问题的前景提出了展望。
关键词：TSP遗传算法遗传算子编码
1.1遗传算法的产生及发展
最早美国Ｍichigan(密执安大学)的Holland教授提出，起源于60年代对自然和人工自适应系统的研究。70年代DeJong基于遗传算法的思想在计算机上进行了大量纯数值函数优化计算实验。在一系列研究工作的基础上80年代Goldberg进行总结归纳，形成了遗传算的基本框架。
主要以一些关键人物所做出的主要贡献见证了遗传算法的发展进程:
1J.H.Holland
60年代提出在研究和设计人工自适应系统时,可以借鉴生物遗传的机制；
70年代初提出了遗传算法的基本定理－模式定理(SchemaTheorem)，从而奠定了遗传算法的理论基础；
80年代实现了第一个基于遗传算法的机器学系统－分类器系统(ClassifierSystems),开创了基于遗传算法的机器学习的新概念。
2J.D.Bagley
1967年在其博士论文中首次提出了：“遗传算法”一词，发展了复制、交叉、变异、显性、倒位等遗传算子，创立了自适应遗传算法的概念。
3K.A.DeJong
1975年在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，定义了评价遗传算法性能的在线指标和离线指标。
4D.J.Golgberg
1989年出版了专著《搜索、优化和机器学习中的遗传算法(GeneticAlgorithmsinSearch，OptimizationandMachineLearning)》，系统总结了遗传算法的主要研究成果，全面而完整的论述了遗传算法的基本原理及其应用。
5L.Davis
1991年编辑出版了《遗传算法手册(HandbookofGeneticAlgorithms)》书中包括遗传算法在科学计算、工程技术和社会经济中的大量应用实例。
6J.R.Koza
1992年将遗传算法应用于〖本文来自：毕业设计论文网www.paper51.com〗计算机程序的优化设计及自动生成，提出了遗传编程(GeneticProgramming)的概念，并成功的将其提出的遗传编程应用于人工智能、机器学习符号处理等方面。
参考文献
[1]王小平，曹立明编著，<<遗传算法——理论、应用与软件实现>>，西安：西安交通大学出版社，2002.1
[2]周明，孙树编著，<<遗传算法原理及应用>>，北京：国防工业出版社，1999.6
[3]谢政，李建平编著，<<网络算法与复杂性理论>>，长沙：国防科技大学出版社，1995
[4]陈国良等，<<遗传算法及其应用>>，北京：人民邮电出版社，1995
[5]刘勇等，<<非数值并行算法（二）>>——遗传算法，北京：科学出版社，1995
[6]刘值义等，<<遗传学>>，北京：人民教育出版社，1982
[7]谢胜利等“求解TSP问题的一种改进的遗传算法[J]”，<<计算机工程与应用>>,2002(8)：58～245
[8]王俊海,“TSP问题的一种高效Memetic算法[J]”，<<交通与计算机>>,2002,20(1)：14～17
[9]GrefenstetteeJJ.GeneticAlgorithmsfortheSalesmanProblem[C].In:ProceedingsoftheFirstInternationalConferenceonGeneticAlgorithms,LawrenceErlbaumAssociates,Publishers,1985,160～165
[10]FoxBR,McMahonMB.GeneticOperatorsfortheSequencingProblems.FoundationsofGeneticAlgorithms[M].In:RawlinsGJE.MorganKaufmannPublishers,1991.284～300
[11]RudolphC.ConvergencePropertiesofCanonicalGeneticAlgorithms[J].IEEETrans.NeuralNetworks,1994;5(1):96～101
[12]KonstantinBoukreev.GeneticAlgorithmandTravelingSalesmanProblem[OL].http://www.Codeguru.com/misc/index.shtml
[13]GoldbergDE,
