遗传算法在求解TSP问题(论文程序全套)
【网学提醒】：本文主要为网上学习者提供遗传算法在求解TSP问题(论文程序全套)，希望对需要遗传算法在求解TSP问题(论文程序全套)网友有所帮助，学习一下吧!
资料包括： 论文(45页16329字) 程序 源码 图纸
说明：
摘 要
TSP (Traveling Salesman Problem)旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。文章首先介绍了基本遗传算法的基本原理、特点及其基本实现技术；接着针对TSP 问题，论述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况，分别指出几种常用的编码方法的优点和缺点，并且结合TSP的运行实例详细分析了基本遗传算法的4个运行参数群体大小、遗传算法的终止进化代数、交叉概率、变异概率，对遗传算法的求解结果和求解效率的影响，经过多次的测试设定出了它们一组比较合理的取值。最后，简单说明了混合遗传算法在求解TSP问题中的应用并对遗传算法解决TSP问题的前景提出了展望。
关键词：TSP 遗传算法 遗传算子 编码
Abstract
TSP (Traveling Salesman Problem) is a typical NP - complete problem and genetic algorithm (GA) is the perfect method for solving NP - complete problem. The basic theories, characteristics and the basic techniques of GA are first introduced. Then the encoding model and genetic operators (including selection operation, crossover operation and mutation operation) about GA in solving TSP are discussed. The advantages and disadvantages of various encoding method are respectively indicated, and the application of the three basic genetic operators is elaborated. According to the given data, the results and efficiencies are influenced by four parameters in the basic genetic algorithm: the size of population, terminate generation, crosser probability and mutation probability. Adjust the parameters, run and try for better ones. At last, the application of hybrid genetic algorithm is briefly presented. It is pointed out that a better crossover or mutation routine can be found out which retains the structure from the parent chromosomes and still ends up with a legal tour in the child chromosomes, which leads to a better solution than ever before. And the prospect for the future of genetic algorithm in solving TSP is made.
Keywords: TSP genetic algorithm genetic operators encoding
目录：
目 录
摘要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.4 TSP的混和遗传算法26
第四章 实例分析27
4.1 测试数据27
4.2 测试结果27
4.3 结果分析27
参考文献：
王小平，曹立明编著，<<遗传算法——理论、应用与软件实现>>，西安：西安交通大学出版社，2002.1
周明，孙树编著，<<遗传算法原理及应用>>，北京：国防工业出版社，1999.6
谢政，李建平编著，<<网络算法与复杂性理论>>，长沙：国防科技大学出版社，1995
陈国良等，<<遗传算法及其应用>>，北京：人民邮电出版社，1995
刘勇等，<<非数值并行算法（二）>>——遗传算法，北京：科学出版社，1995
刘值义等，<<遗传学>>，北京：人民教育出版社，1982
谢胜利等“求解TSP问题的一种改进的遗传算法[J ]”，<<计算机工程与应用>>,2002 (8)：58～245
王俊海, “TSP问题的一种高效Memetic算法[J ]”， <<交通与计算机>>, 2002 ,20 (1) ：14～17
Grefenstettee J J .Genetic Algorithms for the Salesman Problem[C] .In :Proceedings of the First International Conference on Genetic Algorithms , Lawrence Erlbaum Associates, Publishers, 1985,160～165
Fox B R , McMahon M B. Genetic Operators for the Sequencing Problems. Foundations of Genetic Algorithms[M] . In : RawlinsGJ E. Morgan Kaufmann Publishers, 1991.284～300
Rudolph C. Convergence Properties of Canonical Genetic Algorithms [J ] . IEEE Trans. Neural Networks, 1994 ;5(1) :96～101
Konstantin Boukreev. Genetic Algorithm and Traveling Salesman Problem[OL ]. http :/ /www. Codeguru.com/ misc/ index.shtml
Goldberg D E, &Lingle R. Alleles , loci, and the Traveling Salesman Problem[C]. Proceedings of an International Conference on Genetic Algorithms and Their Applications , 1985.154～159
Davis L.Job Shop Scheduling with Genetic Algorithms [C]. In : Proceedings of an International Conference on Genetic Algorithms and Their Applications, 1985.136～140
[15] Grefenstette J J, Gopal R , Rosmaita B J, Gucht D V. Genetic Algorithms for the Travaling Salesman Problem[C ].In J.J .Grefenstette . Editor.Proceedings of the First International Conference on Genetic Algorithms .Lawrence Erlbaum .1985.160～180
[16]Oliver L M,smith D J,Holland J R C, A study of Permutation Crossover Operators on the Traveling Salesman Problem[C]. In : Proceedings of the Second International Conference on Genetic Algorithms , Lawrence Erlbaum Associates ,1987.224～230
[17]Whiley L D. Starkweather T, Fuquay D A. Scheduling Problems and Traveling Salesman :The Genetic Edge Combination Op2erator[C] .In : Proceedings of the 3rd International Conference on Genetic Algorithm ,Morgon Kaufamann Publishers, 1989.133～140
[18] Stakweather T, McDaniel S, Mathias K, Whitley C,Whitley D. A Comparison of Genetic Sequencing Operators[C]. Proceed2ings of the 4th International Conference on Genetic Algorithm. Morgon Kaufamann, Los Altos, 1991.69～76。
[19] Sushil J.Louis.Genetic Algorithm for TSP[OL ].http :/ /www.cs. unr .edu/～sushil/ papers/ conference/ newpapers/ 99/ gecco99/ iga/ GECCO/ gecco/ node3.html
[20Hiroaki SENGOKU,Ikuo YOSHIHARA. A Fast TSP Solver Using GA on JAVA[OL ]. http :/ /www。 Gcd.org/ sengoku/ docs/arob98.pdf
[21] Croes G A. A Method for Solving Traveling Salesman Problems[J ]. Operations Research, 1958,6 :791～812
[22 ] Ranieri Baraglia , Jose Ignacio Hidalgo, Raffaele Perego.A Parallel Hybrid Heuristic for the TSP [OL ].http :/ / malvasia cnuce .cnr .it/ ～raffaele/ papers - ps/ EvoWorkshop.pdf 。
[23 ] Prasanna Jog , J ung Y.Suh , and Dirk Van Gucht. Parallel Genetic Algorithms Applied to the Traveling Salesman Problem[J ]. SIAM Journal of Optimization , 1991,1(4) :515～529
__
作者点评：
综上所述，我们可以看到，遗传算法可用于TSP近似最优解的研究。多次测试结果表明，遗传算法在求解过程中能收敛到某一稳定的“最好解”。 在求解质量上和优化效率上均高于其他算法。
针对求解TSP问题，各种遗传算法总是依赖于问题的编码以及遗传操作算子。要发展遗传算法也要以这几个方面作为突破口。各种求解TSP问题的算法里面都包含启发式的信息或者是在编码过程中包含有边的信息(如矩阵表示和矩阵交叉等)，我认为这是一种趋势。尽管对遗传算法有很多改进和发展，但是总是可以找到更好的算法。对于遗传算法求解TSP问题，我认为最大的一个问题是：很难保证染色体的完整结构，从父染色体开始一直到生成一个合法的旅程而得到的子个体的整个过程中，染色体的结构总是会发生变化。也许以后会找到更好的交叉和变异规则而使染色体的结果保持不变。
资料包括： 论文(45页16329字) 程序 源码 图纸
说明：
摘 要
TSP (Traveling Salesman Problem)旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。文章首先介绍了基本遗传算法的基本原理、特点及其基本实现技术；接着针对TSP 问题，论述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况，分别指出几种常用的编码方法的优点和缺点，并且结合TSP的运行实例详细分析了基本遗传算法的4个运行参数群体大小、遗传算法的终止进化代数、交叉概率、变异概率，对遗传算法的求解结果和求解效率的影响，经过多次的测试设定出了它们一组比较合理的取值。最后，简单说明了混合遗传算法在求解TSP问题中的应用并对遗传算法解决TSP问题的前景提出了展望。
关键词：TSP 遗传算法 遗传算子 编码
Abstract
TSP (Traveling Salesman Problem) is a typical NP - complete problem and genetic algorithm (GA) is the perfect method for solving NP - complete problem. The basic theories, characteristics and the basic techniques of GA are first introduced. Then the encoding model and genetic operators (including selection operation, crossover operation and mutation operation) about GA in solving TSP are discussed. The advantages and disadvantages of various encoding method are respectively indicated, and the application of the three basic genetic operators is elaborated. According to the given data, the results and efficiencies are influenced by four parameters in the basic genetic algorithm: the size of population, terminate generation, crosser probability and mutation probability. Adjust the parameters, run and try for better ones. At last, the application of hybrid genetic algorithm is briefly presented. It is pointed out that a better crossover or mutation routine can be found out which retains the structure from the parent chromosomes and still ends up with a legal tour in the child chromosomes, which leads to a better solution than ever before. And the prospect for the future of genetic algorithm in solving TSP is made.
Keywords: TSP genetic algorithm genetic operators encoding
目录：
目 录
摘要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.4 TSP的混和遗传算法26
第四章 实例分析27
4.1 测试数据27
4.2 测试结果27
4.3 结果分析27
参考文献：
王小平，曹立明编著，<<遗传算法——理论、应用与软件实现>>，西安：西安交通大学出版社，2002.1
周明，孙树编著，<<遗传算法原理及应用>>，北京：国防工业出版社，1999.6
谢政，李建平编著，<<网络算法与复杂性理论>>，长沙：国防科技大学出版社，1995
陈国良等，<<遗传算法及其应用>>，北京：人民邮电出版社，1995
刘勇等，<<非数值并行算法（二）>>——遗传算法，北京：科学出版社，1995
刘值义等，<<遗传学>>，北京：人民教育出版社，1982
谢胜利等“求解TSP问题的一种改进的遗传算法[J ]”，<<计算机工程与应用>>,2002 (8)：58～245
王俊海, “TSP问题的一种高效Memetic算法[J ]”， <<交通与计算机>>, 2002 ,20 (1) ：14～17
Grefenstettee J J .Genetic Algorithms for the Salesman Problem[C] .In :Proceedings of the First International Conference on Genetic Algorithms , Lawrence Erlbaum Associates, Publishers, 1985,160～165
Fox B R , McMahon M B. Genetic Operators for the Sequencing Problems. Foundations of Genetic Algorithms[M] . In : RawlinsGJ E. Morgan Kaufmann Publishers, 1991.284～300
Rudolph C. Convergence Properties of Canonical Genetic Algorithms [J ] . IEEE Trans. Neural Networks, 1994 ;5(1) :96～101
Konstantin Boukreev. Genetic Algorithm and Traveling Salesman Problem[OL ]. http :/ /www. Codeguru.com/ misc/ index.shtml
Goldberg D E, &Lingle R. Alleles , loci, and the Traveling Salesman Problem[C]. Proceedings of an International Conference on Genetic Algorithms and Their Applications , 1985.154～159
Davis L.Job Shop Scheduling with Genetic Algorithms [C]. In : Proceedings of an International Conference on Genetic Algorithms and Their Applications, 1985.136～140
[15] Grefenstette J J, Gopal R , Rosmaita B J, Gucht D V. Genetic Algorithms for the Travaling Salesman Problem[C ].In J.J .Grefenstette . Editor.Proceedings of the First International Conference on Genetic Algorithms .Lawrence Erlbaum .1985.160～180
[16]Oliver L M,smith D J,Holland J R C, A study of Permutation Crossover Operators on the Traveling Salesman Problem[C]. In : Proceedings of the Second International Conference on Genetic Algorithms , Lawrence Erlbaum Associates ,1987.224～230
[17]Whiley L D. Starkweather T, Fuquay D A. Scheduling Problems and Traveling Salesman :The Genetic Edge Combination Op2erator[C] .In : Proceedings of the 3rd International Conference on Genetic Algorithm ,Morgon Kaufamann Publishers, 1989.133～140
[18] Stakweather T, McDaniel S, Mathias K, Whitley C,Whitley D. A Comparison of Genetic Sequencing Operators[C]. Proceed2ings of the 4th International Conference on Genetic Algorithm. Morgon Kaufamann, Los Altos, 1991.69～76。
[19] Sushil J.Louis.Genetic Algorithm for TSP[OL ].http :/ /www.cs. unr .edu/～sushil/ papers/ conference/ newpapers/ 99/ gecco99/ iga/ GECCO/ gecco/ node3.html
[20Hiroaki SENGOKU,Ikuo YOSHIHARA. A Fast TSP Solver Using GA on JAVA[OL ]. http :/ /www。 Gcd.org/ sengoku/ docs/arob98.pdf
[21] Croes G A. A Method for Solving Traveling Salesman Problems[J ]. Operations Research, 1958,6 :791～812
[22 ] Ranieri Baraglia , Jose Ignacio Hidalgo, Raffaele Perego.A Parallel Hybrid Heuristic for the TSP [OL ].http :/ / malvasia cnuce .cnr .it/ ～raffaele/ papers - ps/ EvoWorkshop.pdf 。
[23 ] Prasanna Jog , J ung Y.Suh , and Dirk Van Gucht. Parallel Genetic Algorithms Applied to the Traveling Salesman Problem[J ]. SIAM Journal of Optimization , 1991,1(4) :515～529
__
作者点评：
综上所述，我们可以看到，遗传算法可用于TSP近似最优解的研究。多次测试结果表明，遗传算法在求解过程中能收敛到某一稳定的“最好解”。 在求解质量上和优化效率上均高于其他算法。
针对求解TSP问题，各种遗传算法总是依赖于问题的编码以及遗传操作算子。要发展遗传算法也要以这几个方面作为突破口。各种求解TSP问题的算法里面都包含启发式的信息或者是在编码过程中包含有边的信息(如矩阵表示和矩阵交叉等)，我认为这是一种趋势。尽管对遗传算法有很多改进和发展，但是总是可以找到更好的算法。对于遗传算法求解TSP问题，我认为最大的一个问题是：很难保证染色体的完整结构，从父染色体开始一直到生成一个合法的旅程而得到的子个体的整个过程中，染色体的结构总是会发生变化。也许以后会找到更好的交叉和变异规则而使染色体的结果保持不变。