VC376 C语言遗传算法在求解TSP问题

摘  要
TSP (Traveling Salesman Problem)旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。文章首先介绍了基本遗传算法的基本原理、特点及其基本实现技术；接着针对TSP 问题，论述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况，分别指出几种常用的编码方法的优点和缺点，并且结合TSP的运行实例详细分析了基本遗传算法的4个运行参数群体大小、遗传算法的终止进化代数、交叉概率、变异概率，对遗传算法的求解结果和求解效率的影响，经过多次的测试设定出了它们一组比较合理的取值。最后，简单说明了混合遗传算法在求解TSP问题中的应用并对遗传算法解决TSP问题的前景提出了展望。
关键词：TSP  遗传算法  遗传算子   编码
2.4.5 顺序交叉（Order Crossover）算子
主要思想：先进行常规的双点交叉，然后进行个体巡回顺序的有效顺序修改，修改时
要尽量维持个点原有的相对访问顺序。
例如:以下两个个体选取第三、六个基因座之后进行交叉运算，得到两个新个体： [资料来源：http://THINK58.com]

2.5  变异算子
在生物的遗传和自然进化中，其细胞分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制差错，就会导致生物的某些基因发生某种变异，从而产生新的染色体，表现出新的生物性状。在遗传算法中的变异运算，是指将基因座上的基因值用该基因座的等位基因来替换，从而产生新个体。从遗传运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力；而变异运算只是产生新个体的辅助方法，但它也是一个必不可少的运算步骤，因为它决定了遗传算法的局部搜索能力。它们共同完成对搜索空间的全局搜索和局部搜索，使遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。
变异算子有以下两个作用：
(1) 改善遗传算法的局部搜索能力。
(2) 维持群体多样性，防止早熟现象。
较常用的基本位变异、均匀变异、边界变异、非均匀变异和高斯变异等。
2.6  运行参数
在遗传算法中需要选择的运行参数主要有个体编码串长度l、群体大小M、交叉概率pc、变异概率pm、、终止代数T、代沟G等。
(1) 编码串长度L。使用二进制编码时，编码串长度l的选取与问题所要求的求解精度有关；使用浮点数编码时，编码串长度l与决策变量的个数n相等；使用符号变量来表示个体时。编码串长度l由问题的编码方式来确定；另外，也可以使用变长度的编码来表示个体。 内容来自think58

(2) 群体大小M表示群体中所含个体的数量。当M较小时，可提高遗传算法的运算速度，却降低了群体的多样性，有可能会引起遗传算法早熟现象；而当M较大时，又会使得遗传算法的运行效率降低。一般的建议范围是20～100。
(3) 交叉概率pc。交叉操作是产生新个体的主要方法，一般应取较大值，但取值过大的话，它会破坏群体中的优良模式，对进化运算反而产生不利影响；取值过小的话，产生新个体的速度较慢。一般取0.4～0.99。
(4) 变异概率pm。取值较大，虽然能产生较多的新个体，但有可能破坏掉很多的较好模式，使得遗传算法的性能近似于随机搜索算法的性能；取值过大的话，则变异操作产生新个体的能力和抑制早熟的能力就差。一般取0.0001～0.1。
(5) 终止代数T。表示遗传算法运行到指定的进化代数之后就停止，并将当前群体中的最佳个体作为所求问题的最优解输出。一般为100～1000。
(6) 代沟G。表示每一代群体中被替换掉的个体中所占的百分率，即每一代中有(M×G个个体被替换掉)。
2.7  约束条件的处理方法
主要有搜索空间限定法、可行解变换法、罚函数法。 内容来自think58 [资料来源：http://think58.com]

摘要 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 think58好，好think58

[资料来源：www.THINK58.com]

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