解决TSP 的遗传算法初始种群改进方法研究1
贾海鹏，郑丽英，何天斌，徐顼
兰州交通大学电子与信息工程学院，甘肃兰州（730070）
E-mail ：
摘 要：遗传算法受实际系统计算能力的限制，种群个体和迭代次数有限，因此初始种群的选择成为算法成败的一个至关重要的因素，直接影响到算法的寻优效率和效果。遗传算法初始种群的构造普遍采用均匀取种法或随机取种法，但这两种策略的搜索效率都难以保证。针对这类算法的缺陷，本文结合图论中相关理论提出了三种基于最小生成树原理的初始种群改进方法。
关键词：遗传算法；初始种群；最小生成树；旅行商问题；普里姆算法；奇偶点图上作业法
中图分类号：TP301 文献标识码：A
1. 引言
旅行商问题（Traveling Salesman Problem , TSP）是运筹学，图论，组合优化以及计算机算法设计中的精典课题，由于它有着广泛的应用背景，所以引起了大量学者的关注。同时TSP 问题也属于NP-Hard 题，求准确的最优解实际意义不大，因此启发式算法的研究就越发显示出其魅力。从图论的角度分析，TSP 问题实质上是寻找一条权值最小的哈密顿（Hamilton ）回路的问题。
遗传算法（Genetic Algorithm, GA）是一种基于生物自然选择和基因遗传原理的随机搜索启发式算法[1]。算法自提出以来对它的理论和应用的研究就从未停止过，出现了相当多别具特色的改进形式，但是这些改进几乎全都集中在编码方式和遗传算子操作上，对初始种群的研究目前非常匮乏。遗传算法受实际系统计算能力的限制，种群个体和迭代次数有限，因此初始种群的选择就成为算法中一个至关重要的因素，直接影响到算法的寻优效率和效果[2]。
2. 当前遗传算法初始种群的构造算法
初始种群（第一代种群）的获取一般采用均匀取种法或随机取种法，这是两种现阶段比
较普遍采用的算法，但是这两种算法构造出的初始种群具有很大的随机性，种群的平均适应度较低。
2.1 均匀取种法
首先它将搜索域的解空间分成n 个大小相等的子空间（n 为种群的规模），然后等概率的在每个子空间中选取一个种子，把选出的这n 个种子合并成第一代种群。
算法的搜索过程是：先经过前M 次遗传迭代，算法并行搜索到各个局部最大值附近（如图1中的A,B,C ），再经过N 次迭代，收敛到全局极大值(图1中的B 点) 。
2.2 随机取种法
在搜索域的解空间中每个种子被选择的机会是相等的。随机取种算法实际操作首先是1本课题得到教育部春晖计划（Z2004-1-62018）和甘肃省自然科学基金项目（3ZS042-B25-038）的资助。
选择一个种子，然后再对该种子在解空间内进行基因位重组。选出n 个种子后，就形成了第一代种群。算法的搜索过程与均匀取种法相似。
图1 搜索解空间
Fig1. Search Solution Space
3. 基于TSP 问题的初始种群改进算法
初始种群中一个染色体的有效基因概率越大，它的适应度就越高。如果采用有效的初始化方法，使初始种群本身就能集中到最优解邻近区域，显然要收敛到同样的结果，采用有效初始化方法的GA 所需的迭代次数比随机或均匀取种法要少的多，因而搜索速度也就提高了。
一个完全图的最小生成树, 是所有经过n 个结点生成树中代价最小的一棵树。TSP 也是求经过n 个结点最小代价的问题，因此两者之间有许多的相似之处[3]。所以TSP 的求解, 可以通过对最小生成树部分有效信息的改造来完成。下面我们分别对对称和非对称的TSP 问题初始种群进行重新构造。
3.1 对称TSP 问题
对称TSP 是指一个旅行商从驻地出发去某些城镇旅行，然后再回到出发地。各城镇之间的路程是已知的，并且城镇甲到乙的路程与城镇乙到甲路的相等，求如何安排他的旅行路线，才能使经过每个城镇恰好一次，且总的旅行路程最短[4]。
3.1.1 最小生成树连续出度法
这是一种DNA 和RNA 的嫁接算法。在这里我们把一条完整的染色体分为二部分：前部和后部。前部动态生成，用来存储最小生成树中的局部有效信息可近似理解为生物体中基因相对稳定的DNA ；染色体后部采用随机优化方式排列产生，其基因位相对前部不够稳定，这尤其生物体中的RNA 。再由这两部分嫁接构成一条完整的染色体。
连续出度法解决TSP 问题：
1）利用普里姆（Prim ） 算法产生最小生成树;
2）遍历最小生成树，判断结点的出度，当出度大于1时停止遍历。并记录经过的路径，把该路径上的i 个结点作为初始种群中染色体前部，并且基因相对固定，不参与交叉和变异操作。
3） 剩余n-i 个结点采用随机组合的方式产生染色体后部，进而形成改进后的初始种群。
3.1.2 奇偶点图上作业法
定理1：一个非平凡连通图G 是Euler 图当且仅当图G 没有奇点[5]。
定理2：（管梅谷，1960）设G 是一个连通的赋权图，&&&&G 是G 的一个Euler 赋权生成
母图，则
&&) −E (G ) e ∈E (&&G ∑w (e ) =min{&&&) −E (G ) e ∈E (&G ∑w (e ) G *是 G 的一个赋权生成母图}当且仅当&&&&G
没有重复数大于2的边。并且G 的每一个长度至少是3的回路中多重边的权和不超过此回路权和的一半[5]。
奇偶点图上作业法是图论中为解决中国邮路问题而采用的一种算法。此算法设计出了一套求解非欧拉（Euler ）赋权连通图的最优环游的方法。
最小生成树是一种带权的非Euler 强连通图，因此我们可以利用奇偶点图上作业法的思想并进行稍加改造，进而产生有效的初始种群。
奇偶点图上作业法求解TSP 问题：
1） 利用Prim 算法产生最小生成树;
2） 根据定理1，要构建Euler 图就必须消除奇点。完全图中奇数顶点成对出现，所以可以
把图中度为奇数的顶点两两配对，记为x 1, x 2, x 3...... x n , y 1, y 2, y 3...... y n 。对每个i (i=1,2,….k),图中取一条（x i −y i ）路p i , 将p i 上的每一条边都添加一条边，从而得到生成树的一个赋权Euler 生成母图G *;
3） 如果G *中关于G 的某一对相邻顶点有多于2条边连接它们，则去掉其中的偶数条边，
留下1条或2条边连接这两个顶点。直到每一对相邻顶点至多由2条边连接;
4） 检查G 中的每一个回路，如果某一个回路C 上多重边的权和超过此回路权和的一半（与
定理2相悖），则将C 中原来无重边的边各添加一条重边，而将C 上的各多重边分别删去一条。重复这一过程，直至对G 的所有回路其多重边的权和不超过此回路权和的
&&*; 一半，得&&G
&&*的Euler 环游; 5） 用Fleury 算法求&&G
6） 在Euler 回路中去除重复结点转换成多个Hamilton 回路。
7） 每个Hamilton 回路都作为遗传算法中的一条染色体，进而组合形成初始种群。
3.2 非对称TSP 问题
当各城镇间的距离为非对称距离时，旅行商问题称为非对称的旅行商问题。也就是说设一个旅行商要访问N 个城镇，城镇i 与城镇j 间的距离为C ij 和C ji , 且C ij ≠C ji 。 收发货矩阵法解决非对称TSP 问题：
1）忽略弧的方向，令弧长l ij =min{C ij , C ji },求解关于l ij 的最小生成树T ；
2）若边[i,j]在T 中，则当l ij =C ij 时，给边加方向i →j ; 当l ij =C ji 时，给边加方向为j →i , 如此得到一个原图G 的最小有向生成图MDSG ；
3） 有MDSG 上计算各顶点的入度d (v j ) 与出度d (v j ) , 当入度大于出度时，称点v j 为发
货点，发货量为d (v j ) −d (v j ) ; 当入度小于出度时，v j 称为收货点，收货量为−+−+
d +(v j ) −d −(v j ) [6]；
4） 建立收发货矩阵，解对应的运输问题；
5） 把得到的运输问题的解对应弧加到MDSG 上，使有向图含有Euler 链；
6） 在有向图中寻找一Euler 回路；
7） 在Euler 回路中去掉重复结点从而转换成多条Hamilton 回路, 即初始种群。
4. 结论与展望
文章所构造的三种初始种群生成算法都是利用图中最小生成树的局部有效信息。如此形成的种群染色体具有较高的适应度，并且初始种群中的染色体本身就是TSP 问题的一个近似最优解，最后再利用遗传算法的全局寻优功能就能快速，更加准确的求得TSP 问题的近似解。然而本算法也存在着不足之处，若采用传统遗传算子操作容易陷入局部最优和产生早熟现象。针对这个问题我们可以在传统遗传算法中引进病毒机理，实现水平搜索和纵向搜索相结合，这也是我们下一阶段要研究的课题。
参考文献
[1] Ahmad husban. An Exact Solution Method for The MTSP[J]. Journal of the Operational Research Society, 1989. 40 (5): 461-459.
[2] P. Ponterosso, D. S. J. Fox. Heuristically Seeded Genetic Algorithms Applied to Truss Optimisation[J]. Engineering with Computers 1999.4(15): 345-355.
[3] 姚建华, 杨成涛，用最小生成树解决TSP 问题[J]，湖北师范学院学报，2004.04(24):52-56.
[4] 宋海洲，求解度约束最小生成树的快速近似算法[J]，系统工程学报，2006.3(21):232-236.
[5] 卜月华，图论及其应用[M]，东南大学出版社，2000.3.
[6] 李军，非对称距离的旅行商问题的构造算法[J]，运筹与管理，2000.1(9):1-6.
Study on Improved Method of GA’s Initiation Population
for Solving TSP
Jia Haipeng, Zheng Liying, He Tianbin, Xu Xu
College of Electronic & Information Engineering , Lanzhou Jiaotong University, Lanzou,
China (730070）
Abstract
Genetic Algorithm (GA) is restricted by actual system computing ability. Because of the limited number of population and iteration, the choice of initiation Population is a vital of fact, which directly influents the efficiency and the result of algorithm. GA’s Initiation Population is created by the path of well-proportioned choosing seed or stochastic choosing seed generally, but both of them have a vice of inefficient search. The paper, combining with interrelated theories in graph theory, brings forward three kinds of Optimization Algorithms of Initiation Population based on Minimize Spanning Tree Theory towards the limitations of them.
Keywords: Genetic Algorithm; Initiation Population; Minimize Spanning Tree; Traveling Salesman Problem; Prim Algorithm; Even-Odd Point Graphic Operation Method
作者简介：贾海鹏（1980—），男，甘肃灵台人，硕士研究生。主要研究领域：计算智能，数据挖掘，软件形式化。
解决TSP 的遗传算法初始种群改进方法研究1
贾海鹏，郑丽英，何天斌，徐顼
兰州交通大学电子与信息工程学院，甘肃兰州（730070）
E-mail ：
摘 要：遗传算法受实际系统计算能力的限制，种群个体和迭代次数有限，因此初始种群的选择成为算法成败的一个至关重要的因素，直接影响到算法的寻优效率和效果。遗传算法初始种群的构造普遍采用均匀取种法或随机取种法，但这两种策略的搜索效率都难以保证。针对这类算法的缺陷，本文结合图论中相关理论提出了三种基于最小生成树原理的初始种群改进方法。
关键词：遗传算法；初始种群；最小生成树；旅行商问题；普里姆算法；奇偶点图上作业法
中图分类号：TP301 文献标识码：A
1. 引言
旅行商问题（Traveling Salesman Problem , TSP）是运筹学，图论，组合优化以及计算机算法设计中的精典课题，由于它有着广泛的应用背景，所以引起了大量学者的关注。同时TSP 问题也属于NP-Hard 题，求准确的最优解实际意义不大，因此启发式算法的研究就越发显示出其魅力。从图论的角度分析，TSP 问题实质上是寻找一条权值最小的哈密顿（Hamilton ）回路的问题。
遗传算法（Genetic Algorithm, GA）是一种基于生物自然选择和基因遗传原理的随机搜索启发式算法[1]。算法自提出以来对它的理论和应用的研究就从未停止过，出现了相当多别具特色的改进形式，但是这些改进几乎全都集中在编码方式和遗传算子操作上，对初始种群的研究目前非常匮乏。遗传算法受实际系统计算能力的限制，种群个体和迭代次数有限，因此初始种群的选择就成为算法中一个至关重要的因素，直接影响到算法的寻优效率和效果[2]。
2. 当前遗传算法初始种群的构造算法
初始种群（第一代种群）的获取一般采用均匀取种法或随机取种法，这是两种现阶段比
较普遍采用的算法，但是这两种算法构造出的初始种群具有很大的随机性，种群的平均适应度较低。
2.1 均匀取种法
首先它将搜索域的解空间分成n 个大小相等的子空间（n 为种群的规模），然后等概率的在每个子空间中选取一个种子，把选出的这n 个种子合并成第一代种群。
算法的搜索过程是：先经过前M 次遗传迭代，算法并行搜索到各个局部最大值附近（如图1中的A,B,C ），再经过N 次迭代，收敛到全局极大值(图1中的B 点) 。
2.2 随机取种法
在搜索域的解空间中每个种子被选择的机会是相等的。随机取种算法实际操作首先是1本课题得到教育部春晖计划（Z2004-1-62018）和甘肃省自然科学基金项目（3ZS042-B25-038）的资助。
选择一个种子，然后再对该种子在解空间内进行基因位重组。选出n 个种子后，就形成了第一代种群。算法的搜索过程与均匀取种法相似。
图1 搜索解空间
Fig1. Search Solution Space
3. 基于TSP 问题的初始种群改进算法
初始种群中一个染色体的有效基因概率越大，它的适应度就越高。如果采用有效的初始化方法，使初始种群本身就能集中到最优解邻近区域，显然要收敛到同样的结果，采用有效初始化方法的GA 所需的迭代次数比随机或均匀取种法要少的多，因而搜索速度也就提高了。
一个完全图的最小生成树, 是所有经过n 个结点生成树中代价最小的一棵树。TSP 也是求经过n 个结点最小代价的问题，因此两者之间有许多的相似之处[3]。所以TSP 的求解, 可以通过对最小生成树部分有效信息的改造来完成。下面我们分别对对称和非对称的TSP 问题初始种群进行重新构造。
3.1 对称TSP 问题
对称TSP 是指一个旅行商从驻地出发去某些城镇旅行，然后再回到出发地。各城镇之间的路程是已知的，并且城镇甲到乙的路程与城镇乙到甲路的相等，求如何安排他的旅行路线，才能使经过每个城镇恰好一次，且总的旅行路程最短[4]。
3.1.1 最小生成树连续出度法
这是一种DNA 和RNA 的嫁接算法。在这里我们把一条完整的染色体分为二部分：前部和后部。前部动态生成，用来存储最小生成树中的局部有效信息可近似理解为生物体中基因相对稳定的DNA ；染色体后部采用随机优化方式排列产生，其基因位相对前部不够稳定，这尤其生物体中的RNA 。再由这两部分嫁接构成一条完整的染色体。
连续出度法解决TSP 问题：
1）利用普里姆（Prim ） 算法产生最小生成树;
2）遍历最小生成树，判断结点的出度，当出度大于1时停止遍历。并记录经过的路径，把该路径上的i 个结点作为初始种群中染色体前部，并且基因相对固定，不参与交叉和变异操作。
3） 剩余n-i 个结点采用随机组合的方式产生染色体后部，进而形成改进后的初始种群。
3.1.2 奇偶点图上作业法
定理1：一个非平凡连通图G 是Euler 图当且仅当图G 没有奇点[5]。
定理2：（管梅谷，1960）设G 是一个连通的赋权图，&&&&G 是G 的一个Euler 赋权生成
母图，则
&&) −E (G ) e ∈E (&&G ∑w (e ) =min{&&&) −E (G ) e ∈E (&G ∑w (e ) G *是 G 的一个赋权生成母图}当且仅当&&&&G
没有重复数大于2的边。并且G 的每一个长度至少是3的回路中多重边的权和不超过此回路权和的一半[5]。
奇偶点图上作业法是图论中为解决中国邮路问题而采用的一种算法。此算法设计出了一套求解非欧拉（Euler ）赋权连通图的最优环游的方法。
最小生成树是一种带权的非Euler 强连通图，因此我们可以利用奇偶点图上作业法的思想并进行稍加改造，进而产生有效的初始种群。
奇偶点图上作业法求解TSP 问题：
1） 利用Prim 算法产生最小生成树;
2） 根据定理1，要构建Euler 图就必须消除奇点。完全图中奇数顶点成对出现，所以可以
把图中度为奇数的顶点两两配对，记为x 1, x 2, x 3...... x n , y 1, y 2, y 3...... y n 。对每个i (i=1,2,….k),图中取一条（x i −y i ）路p i , 将p i 上的每一条边都添加一条边，从而得到生成树的一个赋权Euler 生成母图G *;
3） 如果G *中关于G 的某一对相邻顶点有多于2条边连接它们，则去掉其中的偶数条边，
留下1条或2条边连接这两个顶点。直到每一对相邻顶点至多由2条边连接;
4） 检查G 中的每一个回路，如果某一个回路C 上多重边的权和超过此回路权和的一半（与
定理2相悖），则将C 中原来无重边的边各添加一条重边，而将C 上的各多重边分别删去一条。重复这一过程，直至对G 的所有回路其多重边的权和不超过此回路权和的
&&*; 一半，得&&G
&&*的Euler 环游; 5） 用Fleury 算法求&&G
6） 在Euler 回路中去除重复结点转换成多个Hamilton 回路。
7） 每个Hamilton 回路都作为遗传算法中的一条染色体，进而组合形成初始种群。
3.2 非对称TSP 问题
当各城镇间的距离为非对称距离时，旅行商问题称为非对称的旅行商问题。也就是说设一个旅行商要访问N 个城镇，城镇i 与城镇j 间的距离为C ij 和C ji , 且C ij ≠C ji 。 收发货矩阵法解决非对称TSP 问题：
1）忽略弧的方向，令弧长l ij =min{C ij , C ji },求解关于l ij 的最小生成树T ；
2）若边[i,j]在T 中，则当l ij =C ij 时，给边加方向i →j ; 当l ij =C ji 时，给边加方向为j →i , 如此得到一个原图G 的最小有向生成图MDSG ；
3） 有MDSG 上计算各顶点的入度d (v j ) 与出度d (v j ) , 当入度大于出度时，称点v j 为发
货点，发货量为d (v j ) −d (v j ) ; 当入度小于出度时，v j 称为收货点，收货量为−+−+
d +(v j ) −d −(v j ) [6]；
4） 建立收发货矩阵，解对应的运输问题；
5） 把得到的运输问题的解对应弧加到MDSG 上，使有向图含有Euler 链；
6） 在有向图中寻找一Euler 回路；
7） 在Euler 回路中去掉重复结点从而转换成多条Hamilton 回路, 即初始种群。
4. 结论与展望
文章所构造的三种初始种群生成算法都是利用图中最小生成树的局部有效信息。如此形成的种群染色体具有较高的适应度，并且初始种群中的染色体本身就是TSP 问题的一个近似最优解，最后再利用遗传算法的全局寻优功能就能快速，更加准确的求得TSP 问题的近似解。然而本算法也存在着不足之处，若采用传统遗传算子操作容易陷入局部最优和产生早熟现象。针对这个问题我们可以在传统遗传算法中引进病毒机理，实现水平搜索和纵向搜索相结合，这也是我们下一阶段要研究的课题。
参考文献
[1] Ahmad husban. An Exact Solution Method for The MTSP[J]. Journal of the Operational Research Society, 1989. 40 (5): 461-459.
[2] P. Ponterosso, D. S. J. Fox. Heuristically Seeded Genetic Algorithms Applied to Truss Optimisation[J]. Engineering with Computers 1999.4(15): 345-355.
[3] 姚建华, 杨成涛，用最小生成树解决TSP 问题[J]，湖北师范学院学报，2004.04(24):52-56.
[4] 宋海洲，求解度约束最小生成树的快速近似算法[J]，系统工程学报，2006.3(21):232-236.
[5] 卜月华，图论及其应用[M]，东南大学出版社，2000.3.
[6] 李军，非对称距离的旅行商问题的构造算法[J]，运筹与管理，2000.1(9):1-6.
Study on Improved Method of GA’s Initiation Population
for Solving TSP
Jia Haipeng, Zheng Liying, He Tianbin, Xu Xu
College of Electronic & Information Engineering , Lanzhou Jiaotong University, Lanzou,
China (730070）
Abstract
Genetic Algorithm (GA) is restricted by actual system computing ability. Because of the limited number of population and iteration, the choice of initiation Population is a vital of fact, which directly influents the efficiency and the result of algorithm. GA’s Initiation Population is created by the path of well-proportioned choosing seed or stochastic choosing seed generally, but both of them have a vice of inefficient search. The paper, combining with interrelated theories in graph theory, brings forward three kinds of Optimization Algorithms of Initiation Population based on Minimize Spanning Tree Theory towards the limitations of them.
Keywords: Genetic Algorithm; Initiation Population; Minimize Spanning Tree; Traveling Salesman Problem; Prim Algorithm; Even-Odd Point Graphic Operation Method
作者简介：贾海鹏（1980—），男，甘肃灵台人，硕士研究生。主要研究领域：计算智能，数据挖掘，软件形式化。