遗传算法在求解TSP问题毕业论文

《遗传算法在求解TSP问题毕业论文》由会员分享，可在线阅读，更多相关《遗传算法在求解TSP问题毕业论文（41页珍藏版）》请在毕设资料网上搜索。

1、 1 目 录 摘要 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.

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 单点交叉 . 2

3、0 3.3.2.2 部分映射交叉 . 21 3.3.3 变异算子 . 23 3.4 TSP 的混和遗传算法 . 26 第四章 实例分析 27 4.1 测试数据 . 27 4.2 测试结果 . 27 4.3 结果分析 . 27 2 摘 要 TSP (Traveling Salesman Problem)旅行商问题是一类典型的 NP完全问题，遗传算法是解决 NP问题的一种较理想的方法。 文章首先介绍了基本遗传算法的基本原理、特点及其基本实现技术 ；接着 针对 TSP 问题 ， 论述了遗传算法在编码 表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况 ， 分别指出几种常用的编码方法的优点和缺点 ，并且结合 TSP的运行实例详细分析了基本遗传算法的 4个运行参数群体大小、遗传算法的终止进化代数、交叉概率、变异概率，对遗传算法的求解结果和求解效率的影响，经过多次的测试设定出了它们一组比较合理的取值。 最后 ， 简单说明了混合遗传算法在求解 TSP问题中的应用并对遗传算法解决 TSP问题的前景提出了展望 。 关键词 ： TSP 遗传算法 遗传算子 编码 Abstract