[ 论文中心|计算机应用 ]遗传算法在求解TSP问题毕业论文+源代码
登出时间 ： 2008-08-18 09:50:04
写稿时间 ： 2007-3
登 陆 人 ： Andy521
下 载 ： 1
总 页 数 ： 45 Page / 字数 ： 16328
文件类型 ：
大 小 ： [ 185,722Byte
]
资料点评 ： 没有会员的点评.
关键词 ： TSP 遗传算法 遗传算子 编码 遗传基因编码方法
原文：
引 言
现代科学理论研究与实践中存在着大量与优化、自适应相关的问题，但除了一些简单的情况之外，人们对于大型复杂系统的优化和自适应问题仍然无能为力。然而，自然界中的生物却在这方面表现出了其优异的能力，它们能够以优胜劣汰、适者生存的自然进化规则生存和繁衍，并逐步产生出对其生存环境适应性很高的优良物种。遗传算法正是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法。
遗传算法使用群体搜索技术，它通过对当前群体施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解的状态。由于其具有思想简单、易于实现、应用效果明显等优点而被众多应用领域所接受，并在自适应控制、组合优化、模式识别、机器学习、人工生命、管理策略等领域得到了广泛应用。遗传算法给我们呈现出的是一类通用的算法框架，该框架不依赖于问题的种类。遗传算法是一类具有较强鲁棒性的优化算法，特别是对于一些大型、复杂非线性系统，它更表现出了比其他传统优化方法更加独特和优越的性能。隐含并行性和全局搜索特性是遗传算法的两大显著特征。
遗传算法是新发展起来的一门学科，各种理论、方法尚未成熟，有待于进一步地发展和完善，但它却为我们解决许多复杂问题提供了希望。尽管在遗传算法的研究和应用过程中出现许多难题，同时也会产生许多不同的算法设计观点，然而，目前遗传算法的各种应用实践已经展现出了其优异的性能和巨大的发展潜力，它的发展前景激励着各类专业技术人员把遗传算法的理论和方法运用于自己的工作实践中。我们相信，随着研究工作的进一步深入和发展，遗传算法必将在智能计算领域中起到关键作用。
......
目录：
摘要 I
Abstract II
引 言 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
参考资料：
[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] 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
[10]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
[11] Rudolph C. Convergence Properties of Canonical Geneti
点评资料 :
