|
|
摘要 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
结 论
综上所述，我们可以看到，遗传算法可用于TSP近似最优解的研究。多次测试结果表明，遗传算法在求解过程中能收敛到某一稳定的“最好解”。 在求解质量上和优化效率上均高于其他算法。
针对求解TSP问题，各种遗传算法总是依赖于问题的编码以及遗传操作算子。要发展遗传算法也要以这几个方面作为突破口。各种求解TSP问题的算法里面都包含启发式的信息或者是在编码过程中包含有边的信息(如矩阵表示和矩阵交叉等)，我认为这是一种趋势。尽管对遗传算法有很多改进和发展，但是总是可以找到更好的算法。对于遗传算法求解TSP问题，我认为最大的一个问题是：很难保证染色体的完整结构，从父染色体开始一直到生成一个合法的旅程而得到的子个体的整个过程中，染色体的结构总是会发生变化。也许以后会找到更好的交叉和变异规则而使染色体的结果保持不变。
