基于改进遗传算法的TSP问题研究

第12期第30卷韶关学院学报·自然科学

JournalofShaoguanUniversity·NaturalScience

Dec.2009Vol.30No.12基于自适应选择算子遗传算法的TSP问题优化

李绍中1，2

（1.中山大学软件学院，广东广州510275；2.番禺职业技术学院软件学院，广东广州511483）

摘要：轮盘选择方式往往能保证算法的全局收敛性，但收敛速度较慢，而锦标赛选择方式收敛速度优于轮盘选择方式，但不能保证算法的全局收敛性.选用轮盘选择和锦标赛选择相结合自适应选择算子的遗传算法，并优化TSP问题求解，则可以调整收敛速度，避免被动式搜索.关键词：优化;遗传算法;TSP;选择算子

中图分类号：TP301.6文献标识码：A文章编号：1007-5348（2009）12-0011-06

遗传算法是计算机工程师模拟生物进化原理而提出的一种概率搜索算法，它利用简单的编码机制和自然界生物的遗传机制来表现复杂的现象，从而解决非常困难的问题［1］.用它来解决问题，不受搜索空间的限制性假设的约束，不必要求诸如连续性、导数存在和单峰等假设.使用遗传算法解决实际问题时主要有三个步骤：分别是编码与解码、计算个体适应度、遗传操作.其中遗传操作包括选择操作、交叉操作和变异操作.遗传算法在很多领域得到广泛的应用，特别是与计算机科学相结合，取得了很大的成功.由不同的编码方案和选择策略构成了不同的遗传算法.

在遗传算法中，群体的进化主要靠选择机制和交叉策略来完成,变异只是为选择、交叉过程中可能丢失的某些遗传基因进行修复和补充,在遗传算法的全局意义上只是一个背景操作.而交叉操作是建立在选择操作的结果之上，即交叉操作的对象是选择操作的结果.由此可以看出，在使用遗传算法解决实际难题的过程中，选择操作占据极其重要的位置，它也是决定遗传算法是否收敛的一个主要因素［2］.

1TSP问题

旅行商问题TSP（TravelingSales-manProblem，简记为TSP）是典型NP难题，也是组合优化中研究最多的问题之一.其描述为：设有n座城市集合City={si|1燮i燮n}，si,sj∈city，从si到sj的距离（这里称开销）记为d

(si,sj)，这里只讨论对称的TSP问题，即d(si,sj)=d(sj,si).求解TSP问题，就是在以集合City的元素为结点的图

中，找到一条经过所有结点一次而且仅一次的一条回路，使得此回路在所有满足条件的回路中，总开销最小，即寻找最优回路.

对于回路S=（s1,s2,…,sn）,总开销可以表示为：

n-1

D(S)=Σd(si,si+1)+d(sn,s1).

i=1

目前，针对这一问题有许多解法，如穷举法、贪婪法、免疫算法、蚁群算法等.这些方法都存在一个共同的问题：就是随着问题规模增大时，求解计算量呈指数级增长.如当城市数为50的时候，用每秒钟计算一亿次的计算机，用穷举法计算，所需时间为5×1048年.

遗传算法是在搜索空间中收敛到全局最优解，搜索速度依赖于算法的收敛性.而收敛速度高的算法通

收稿日期：2009-10-28

作者简介：李绍中（1969-），男，湖南娄底人，番禺职业技术学院软件学院副教授，硕士研究生，主要从事遗传算法、神经网络方面研究.

·12·韶关学院学报·自然科学2009年

常导致早熟，使解的质量降低.遗传算法优化的主要目的是要求算法解的质量高，并且计算效率高，即既有好的收敛性，又能避免局部最优.

2TSP问题优化

2．1编码设计

在过去几年，与TSP有关的向量表达有三种：邻接、普通和路径表达.这里选用路径表达.路径表达是对一个旅行最普通的表达［1］.例如一个“6-8-5-1-…-2-4-3-7”旅行可以简单地被表达成（6851…2473）.

表1给出本文实验用城市图表（城市数为20）.表中第一行和第一列的数据代表城市编号.其余数据为它所在行和列所代表的城市之间的开销.

表1

城市

城市间开销表

101468137297345892828

210753834244628294521

347038379125818947484

465303152913573473452

583830231463845281747

618312033954527362371

733753307593459373281

874921370134527633835

922194951013473759217

1094216593103737493525

1174533434330578431593

1236858545475083158583

1342174252737805748353

1458835797378350831845

1582942336744178042184

1699478673593543404184

1724731233931881240437

1885447328255538114026

1922854783129854883204

2081427115753335447640

1234567891011121314151617181920

2．2选择机制

在遗传算法中，常用的选择算子有：轮盘式选择算子、锦标赛选择算子、具有排名的轮盘式选择算子、随机一致选择算子.轮盘选择算子保证上一代群体所有适应度大于零的个体都有机会被选择到下一代中，从而保证了算法的全局收敛性.但实验发现这种选择算子收敛较慢.而锦标赛选择算子往往有较好的收敛性，但对于适应度小的个体没有机会被选择到下一代，在全局收敛性问题上不够理想，容易造成局部最优.为了保证算法的全局收敛性，同时提高收敛速度，本文提出采用轮盘和锦标赛选择算子相结合的方法进行个体选择.首先选用轮盘选择算子，当某代个体的标准差是否小于某一数值Stdev时，算法已达到了一定的全局收敛性，对该种群的选择就使用锦标赛选择算子.Stdev定义如下：

popsize

1Stdev=

adaptationΣeval(v)/popsize,

i

i=1

第12期

其中，Popsize为种群的规模.eval(vi)为种群中个体的适应值.ataptation为某一常数，称它为适应因子.可以根据收敛速度适当调整适应因子，如果收敛速度过快可增大适应因子ataptation的值，反之，减少适应因子ataptation的值，从而达到好的效果.

（1）轮盘式先选择算子

先计算种群中每个个体的相对适应值eval(vi)，然后再计算每个个体选择概率Pi：

eval(vi)Pi=popsize

i=1

.

i

Σeval(v)

i

再计算每条染色体累积概率：

qi=Σpk.

k=1

选择时，先产生一个［0，1］内的随机数r.如果r1）成立，则选择第i条染色体.

（2）锦标赛选择算子

锦标赛选择算子在选择时，从种群中随机地选取k个个体，找出这k个个体中适应值最好的个体作为最优个体，这个最优个体就是下一代种群中的一个个体.将这个过程重复popsize次就产生了新的种群［3］.

在锦标赛选择算法中，k的值越大，算法的收敛速度越快，但全局收敛效果会更差.

2.3适应函数

选用适应函数为：

max(d(si,sj)city-D(S)

其中(d(si,sj)为城市si到sj的距离，city为城市数，D(S)为当前回路S的总开销.

2.4交叉策略

与路径表达相对应的交叉方式常有的有：PMX（部分映射杂交）、OX（次序杂交）和CX（循环杂交）［1］.这里选用OX次序杂交方式.

OX是通过从一个亲体中挑选一个子序列旅行保存另一

个城市相对次序来构造后代［1］.如两个亲体：

燮P=21356748.

P1=（23418567）,

2

（）

产生后代的算法如下：

（1）产生1到7间的两个随机数；

图1

选择方向示意图

（2）用随机数作为分隔位，将P1和P2分隔成三段，假设随机数为2和5，则将P1和P2分隔为：

P=23‖418‖567,

‖P=21‖356‖748.

12

（（

））

（3）将分隔点之间的片断拷贝到后代中，得到：

‖O=xx‖356‖xxx.

O1=（xx‖418‖xxx）,

2

（）

（4）从P1串第二个分隔点后的一个数字开始，按图1所示方向写出数字序列：56723418.因为第二串中两个分隔点间的356已保留，所以将3、5、6从该序列中删除，得到子序列：72418，将该子序列从

·14·韶关学院学报·自然科学2009年

O2第二个分隔符后开始填充，得到后代：

O2=（18356724）；

同样的方法，可以得另一后代：

O1=（56418723）.

2.5变异技术

常用的变异算子有单点变异和多点变异.本文选用多点变异中的双点变异.多点变异可以增强变异算子的全局搜索能力，促使种群向多样化进化，避免早熟.但是变异点过多容易造成优良模式的破坏，所以选用双点变异.如P=（23418567），算法如下：

（1）产生两个1到8间的随机数，如2和7.

（2）交换第2位和第7位，得到新的染色体（粗体数字已交换）：

P=（26418537）.2.6算法流程设计

用自适应选择算子优化TSP问题的算法流程如下：（1）设置算法参数；（2）解码并计算适应度；

（3）检查是否满足条件，即个体的标准差是否小于2.2中定义的Stdev.如满足转（5），否则转（4）；（4）进行轮盘选择操作，转（5）（5）进行锦标赛选择操作；（6）交叉变异操作，产生下代种群；

（7）判断是否满足程序结束条件，如果满足，则转（8），否则转（2）；（8）解码并输出最短路径和最短路径开销.

3实验结果分析

交叉概率：0.1燮pcross燮0.8，步长为0.1;变异概率：0.1燮pmutation燮0.1，步长为0.01;种群大小：popsize=50;

染色体长度（即城市数）：city=20;最大代数：maxgen=300;总运行次数：maxruns=90;

选择算子切换时适应因子：adaptation=200.

3．1实验参数设置

3.2实验结果

以交叉概率为X轴坐标，变异概率为Y轴坐标，以300次运算的平均适应值为Z轴坐标，做出反映适应值与交叉概率、变异概率的关系图如图2所示.观察图2，不难看出变异概率对适应值影响不大，但当交叉概率由0.1增加0.5时，适应值有较大优化.但由0.5增加到0.8时，适应值没有明显的优化.

表2列出了每组概率所对应的最优开销，从表2可以看出，交叉概率和变异概率对最优开销的影响与对适应值的影响非常类似.本实验的最优开销为28，最优路径为：14-17-15-11-7-19-2-1-6-4-10-18-20-

9-3-12-8-5-16-13-12-14.

第12期李绍中：基于自适应选择算子遗传算法的TSP问题优化·15·

表3列出了轮盘选择算子、锦标赛选择算子和为里采用的自适应选择算子在收敛速度及最优值求解情况统计表.在收敛速度上锦标赛选择算子最快，平均为56.8代，但获取最优解的几率最低，平均比例仅为

68.48%，而轮盘选择算子在获取最优解的能力上与本文提出的自适应选择算子不相上下，平均比例分别为96.83%和96.42%，但收敛速度明显不如自适应选择算子.轮盘选择算了的收敛速度为84.53代，自适应选择

算子的平均收敛速度仅为62.66代.

图3平均适应值统计图

表2

各种概率组合的最优开销（P）

Px0.010.020.030.040.050.060.070.080.090.10

0.130313129303030303029

0.228303029292928292829

0.329282828282828282828

0.428282829282829282828

0.528282828282828282828

0.628282928282828282828

0.728282828282828282828

0.828282828282828282828

·16·韶关学院学报·自然科学

表3

算子类型

收敛速度和最优解对比表

锦标赛选择算子

2009年

轮盘选择算子

轮盘和锦标赛相结合的自适应选择算子

平均收敛速度/代获取最优值运算次数的

百分比/%

84.5396.83

56.8068.48

62.6696.42

3．3实验结果分析

（1）当选择算子由轮盘选择改为轮盘选择和锦标赛选择相结合的自适应选择算子后，在80种概率组

合的300次运算中，平均收敛速度由原来的84.53代提高到62.66代，且求取最优解的次数没有明显降低.当选择算子由锦标赛选择算改为自适应选择算子后，虽然收敛速度有所下降，但获取最优解的能力大大提高，获取最优解的比例由68.48%提高到96.42%.可见，选择算子在很大程度上影响了遗传算法的收敛性和全局收敛能力.自适应选择算子既能保证算法的全局收敛性，同时还具备较高的收敛速度.

（2）通过改变适应因子ataptation的值来观察收敛速度和全局收收敛性，发现适应因子值越小，收敛的速度越快，但获最优解的能力下降.通过反复实验，选定一个理想的适应因子ataptation值为200.

（3）通过改变交叉概率和变异概率大小来观察它们对最优值的影响，发现变异概率对最优值的影响不大，但当交叉概率由0.1增加0.5时，最优值有较大的优化，而交叉概率由0.5增加到0.8时，最优值没有明显的优化.所以在交叉和变异概率的选取上不宜太大，以提高算法的效率.

4结语

自适应问题是遗传算法如何最快地找到最优解的一种有效探索方式，在探索中，可以感到收敛的速度

的变化，从而进行自适应的调整，避免了以前的被动式搜索.本文的算法在保证全局收敛的同时，一定程度上提高了算法的收敛速度.但文中提出的适应因子值，是通过大量实验得出的一个经验值，而没有提供可靠的理论依据.另外，对于不同规模的TSP问题，适应因子如何选择也有待进一步探讨.自适应选择算子不仅适用于TSP问题求解，也可以用于其它遗传算法的优化问题.参考文献:

［1］米凯利维茨.演化程序———遗传算法和数据编码的结合［M］.北京：科学出版社,2000.

［2］肖启莉.遗传算法中几种常用的选择算子在C语言中的实现［J］.计算机与数字工程,2005,9(33)：140-42.［3］夏桂梅,曾建潮.基于锦标赛选择遗传算法的随机微粒群算法［J］.计算机工程与应用,2007,43（4）：51-53.

OptimizationforTSPproblembasedongeneticalgorithmof

adaptiveselectionoperator

LIShao-zhong1,2

(1.SchoolofSoftware,SunYat-senUniversity,Guangzhou501275,Guangdong,China;2.SchoolofSoftware,PanyuPolytechnicUniversity,Guangzhou511483,Guangdong,China)

Abstract：Althoughroulettewheelselectionguaranteesglobalconvergenceofanalgorithm,itsspeedisquiteslow.Ontheotherhand,tournamentselectionconvergesveryfast.Butitcannotensureglobalconvergenceofthealgorithm.Toovercometheproblem,inthispaper,weoptimizethesolutionoftheTSPproblembyusinganadaptiveoperatorselectionmethod,whichcombinestheroulettewheelselection.Keywords：optimization;geneticalgorithm;TSP;selectionoperator

（ED.：X，J）