基因-表现型的布谷鸟算法求解旅行商问题
林
敏，钟一文，刘必雄，林晓宇
LINMin,ZHONGYiwen,LIUBixiong,LINXiaoyu
福建农林大学计算机与信息学院，福州350002
CollegeofComputerandInformation,FujianAgricultureandForestryUniversity,Fuzhou350002,China
LINMin,ZHONGYiwen,LIUBixiong,etal.Genotype-phenotypecuckoosearchalgorithmfortravelingsalesmanproblem.ComputerEngineeringandApplications,2017,53（24）：172-181.
Abstract：CuckooSearch（CS）algorithmshowsbetterperformanceinsolvingcontinuousproblems,buttheexistingCSalgorithmconvergesslowlyandfailstoreflectthecharacteristicsofLevyflight.Tosolvethedrawback,anewGenotype-PhenotypeCuckooSearch（GPCS）algorithmisproposedinthispaper.IntheGPCSalgorithm,eachcityisencodedwithrandomdecimalcalledgenewhichtheintegerpartisthecitynumber,andthemeaningscontainedinthegenesaretogetherdecidedbythedecimalandtheintegerparts.Thedecimalpartdeterminestheaccessorderofthecity,theintegerpartrep-resentsthecitynumber,andthetwopartstogetherconstitutetheneighborhoodspaceofLevyflight,thenselectstherelo-cateordisplaceoperationaccordingtotheflightresults.TheexperimentalresultsshowthatGPCSalgorithmisnotonlybetterthanothercuckoosearchbasedalgorithms,butisbetterthansomestate-of-the-artswarmintelligencealgorithmstoo.Keywords：cuckoosearch;Levyflight;travelingsalesmanproblem;swarmintelligencealgorithm摘
要：布谷鸟搜索（CuckooSearch，CS）算法在求解连续优化问题时表现出了较好的性能，但现有的CS算法在求
解旅行商问题（TravelingSalesmanProblem，TSP）时收敛较慢且未能体现Levy飞行的特点，针对这些不足提出了一种新的基因-表现型的布谷鸟算法（Genotype-PhenotypeCuckooSearch，GPCS），GPCS算法首先赋予每个城市一个整数部分为城市编号的随机小数编码即基因，而此基因所表现的内容由小数和整数共同决定，小数决定城市的访问次序，整数部分代表某个城市，两个部分组合起来构成Levy飞行的邻域空间，最后根据不同的飞行结果选择重定位或替换操作。实验结果表明，GPCS算法优于同类的CS算法，也优于一些其他的群智能算法，特别在求解大规模TSP时其优势更加明显。
关键词：布谷鸟搜索；莱维飞行；旅行商问题；群智能算法文献标志码：A
中图分类号：TP183
doi：10.3778/j.issn.1002-8331.1708-0001
1引言
群智能算法的出现为这类问题提供了一个新的求旅行商问题（TravelingSalesmanProblem，TSP）是
解途径，群智能算法是通过模拟自然生物的群体行为而组合优化领域的一个典型问题，在运筹学和理论计算机构造的随机优化算法，如新型的鸡群算法（Chicken
科学中非常重要，其求解方案可广泛应用于集成电路布SwarmOptimization，CSO）[1]
、人工萤火虫算法[2]、蛙跳
线、车间调度、物流配送等，由于其所代表的意义以及易算法[3-4]、蝙蝠算法[5-6]、和声搜索算法[7]、帝国竞争算法[8]，描述性，常常作为基准函数用来测试算法的性能。TSP以及经典的蚁群优化（AntColonyOptimization，ACO）属于NP-困难问题，当规模较小时可以通过一些经典的算法[9-11]、粒子群优化（ParticleSwarmOptimization，PSO）算法来求解，但当其规模增大时，因其计算的时间随问算法[12-13]，遗传算法[14-15]等。这类算法被广泛应用于工程题的规模成指数的增长，很快便变得不可计算了。
技术、计算机科学、管理科学等方面的全局最优问题，因
基金项目：福建省自然科学基金（No.2015J01233）；福建省教育厅项目（No.JAT160143）。
作者简介：林敏（1981—），男，讲师，研究领域为智能信息处理，并行计算，生物信息学，E-mail：linmin@fafu.edu.cn；钟一文（1968—），
男，博士，教授，研究领域为智能计算，生物信息学；刘必雄（1979—），男，副教授，研究领域为智能计算；林晓宇(1978—），男，副教授，研究领域为智能计算。
收稿日期：2017-08-01
修回日期：2017-09-01
文章编号：1002-8331（2017）24-0172-10
林敏，钟一文，刘必雄，等：基因-表现型的布谷鸟算法求解旅行商问题2017，53（24）173
此群智能算法已成为众多科研人员研究的一个热点。
其能增加种群多样性，扩大搜索范围，更容易跳出局部布谷鸟算法（CuckooSearch，CS）[16]是一种新型的
最优点，基本CS算法的主要实现步骤见算法1。
群智能算法，其通过Levy飞行来保证群体的多样性，使算法1CuckooSearch
其不易陷入局部最优解，这些优点使CS算法在处理连（1）生成N个鸟巢的初始位置=(x1,x2,⋯,xi,⋯,xD)续函数优化问题时表现出了良好的性能。因此一些学（2）计算适应度值F(X)
者研究将CS算法应用于组合优化问题，如TSP问题，其（3）当不满足迭代停止条件时，重复下述操作中典型的代表为离散布谷鸟算法（DiscreteCuckoo
（4）对种群中的每个个体X，重复下述操作
SearchAlgorithm，DCS）[17]
，基于随机键的布谷鸟算法（5）采用Levy飞行生成候选解Y（Random-KeyCuckooSearch，RKCS）[18]和混合模拟退
（6）计算候选解Y的适应度F(Y)火的布谷鸟算法（CuckooAlgorithmwithSimulated
（7）IfF(Y)>F(X)Then
Annealing，SA-CS）[19]。但这些算法依然存在一些不足，
（8）用候选解Y替代种群中的解X
DCS算法根据Levy飞行每次产生的步长来进行不同的（9）
按发现概率pa丢弃差的解
操作，当飞行的步长较小时进行2-OPT操作，当步长较（10）用偏好随机游动产生新解替代丢弃的解长时进行双桥操作，但是其Levy飞行与鸟巢位置更新（11）记录全局最优解没有直接关联，即并没有使用公式（1）来实现位置更新，（12）返回全局最优解
仅仅是根据Levy飞行产生的扰动大小以决定不同的操为了实现CS算法，假设种群中有N只布谷鸟，每作。而RKCS算法采用随机小数对城市编码并排序，其只布谷鸟寻得的鸟巢位置X代表D维空间问题的一个排序序列就是一个城市访问路径，但其采用Levy飞行解，X=(x1,x2,⋯,xi,⋯,xD),xi表示D维空间某一分对位置进行更新时实际上改变的是某一城市的小数值，量的值，则鸟巢位置更新公式如下：
然后再根据小数进行排序，也就是说RKCS算法实际上xti+1=xti+α⊕Levy(λ)（1）
并没有发挥Levy飞行的特点，无论飞行长短，其最终的其中xti和xti+1分别表示解的分量xi的第t代和第t+1操作都是根据更新后的小数进行排序来重新决定访问代值，
α为步长，Levy(λ)代表Levy飞行。CS算法的步顺序。SA-CS算法是在CS算法中引入模拟退火算法，长α其计算如公式（2）所示，其中α0是一个常数，通常可但根据实验结果，其算法性能十分低下，仅能处理很小以取0.01，xbest代表当前整个种群找到的全局最优解。
规模的城市，且运行时间很长。
α=α0(xti-xbest)（2）
因此，本文提出一种新的基因-表现型的布谷鸟算公式（1）中的Levy(λ)是一个随机数，它服从Levy法（Genotype-PhenotypeCuckooSearch，GPCS），GPCS概率分布，分布如公式（3）所示：
算法充分发挥了Levy飞行的优势，并能依据Levy飞行的结果进行位置更新，它通过整数部分为城市的随机小Levy(λ)=ϕ×μ
(1≤λ≤3)（3）
数编码即基因，而基因所表现的信息由两部分组成，小|1υ|λ数部分决定城市的访问顺序，整数部分代表所在的城其中参数u和v为服从标准正态分布的随机数，λ取值市，将小数部分和整数部分合成起来构成连续的邻域空范围为[1，3]，一般取1.5，ϕ的取值可根据公式（4）计算
间，布谷鸟在此邻域空间内进行Levy飞行实现位置更得到，公式（4）中的Γ函数表示Gamma函数。
1
新，并根据位置更新的结果实现重定位或替换操作，即ì位置变化较短时实现重定位操作，较长时实现替换操φ=ïïΓ(1+λ)×sinæçèπ×λö÷üλ作。最后通过采用多组不同规模的TSP实例和多种智í2øï（4）
ï能优化算法的对比实验验证了GPCS算法的有效性，特ïΓìé1+λùλ-ï21üýïî
íêúîë2û
×λ×2ýþïþ别对于求解大规模TSP问题其优势更加明显。
2.2TSP问题
TSP问题是找出一个包含所有N个城市的最短路
2布谷鸟算法及TSP问题
程的环路，假设N个的城市集合为{x1,x2,x3,⋯,xn}，2.1布谷鸟算法
而其目标就是找到一个遍历序列πi=(x1,x2,x3,⋯,布谷鸟算法由Yang和Deb于2009年提出的一种新xn)，使得路径长度总和f(πi)最短，函数f(π)定义如下：
型群智能算法，它通过模拟某些种属布谷鸟的寄生育雏来有效地求解最优化问题。在传统的布谷鸟算法中，布f(π)=∑n-1
D(xi,xi+1)+D(xn,x1（5）
i=1)谷鸟通过Levy飞行和偏好随机游走来寻优，Levy飞行其中xi为第i个访问城市，xi+1为第i+1个被访问的行走的步长满足一个重尾的稳定分布，在这种形式的飞城市，D(xi,xi+1)表示两个城市的欧拉距离，假设两个行中，短距离的探索和偶尔较长距离的飞行相结合，使
城市的坐标为(x1,y1)和(x2,y2)，则其距离计算如公
1742017，53（24）ComputerEngineeringandApplications计算机工程与应用
式（6）所示：
离探索相结合，不容易陷入局部最优，也解决了RKCS
D=(x1-x2)2+(y1-y2)2
（6）
算法中没有根据Levy飞行步长选择不同操作的缺点。
2.3求解TSP的布谷鸟算法
3.1基因-表现型编码方案
CS算法从诞生开始，许多学者对其提出了许多改
遗传算法中的基因型与表现型的概念已经被应用
进的策略，主要有逐维改进的布谷鸟搜索算法[20]，动态于优化问题的编码方案[24]，一个典型的例子是随机键编适应布谷鸟搜索算法[21]，采用搜索趋化策略的布谷鸟全码方案，例如如图1中（a）所示，要访问的城市为6个，首局优化算法[22]，以及基于种群特征反馈的布谷鸟搜索先对每一个城市给定（0，1）之间的随机数，然后按照小算法[23]。
数进行排序，排序后得到城市的访问路径为4-3-1-5-0-但这些CS算法适合求解连续优化问题，而TSP问2，如图1中（b）所示，这里小数编码就像染色体中的6个题是组合优化问题，要将CS算法应用于组合优化问题，基因，而小数所对应的城市就像基因所译码的信息，称需要设计CS算法的离散化方案，因此一些学者提出了
为表现。
离散的布谷鸟方案，主要有离散布谷鸟算法（DCS）[17]
、编码0.50.30.90.20.10.4基于随机键的布谷鸟算法（RDCS）[18]和混合模拟退火的城市
0
1
2
3
4
5
布谷鸟算法（SA-CS）[19]。DCS算法根据Levy飞行产生
（a）城市编码
的步长大小来决定不同的操作，当飞行的步长较小时进编码0.10.20.30.40.50.9行2-OPT操作，当步长较长时进行双桥操作。但其无论城市431502执行2-OPT操作和双桥操作都要遍历TSP问题的整个最终编码
4.1
3.2
1.3
5.4
0.5
2.9
邻域空间，以获得更优的解，而且其Levy飞行的步长仅（b）按小数排序后最终编码
仅作为一个决定操作的依据而无法将Levy飞行的结果图1
城市编码方案
导入到CS算法的位置更新公式中进行计算，这使得其GPCS算法中的每一个基因由小数和城市编号组合下一个解的值与Levy飞行值关系不大，因此并没有发而成，例如原基因为0.1，对应的城市为4，则最终编码挥Levy飞行的特点。RKCS算法给予每一个城市随机（基因）为4.1，基因所表现的信息由小数和整数共同决键编码，按照随机键进行排序即得到一个TSP解，巧妙定，其中小数部分仍然决定着城市的访问次序，而整数地将TSP问题转换成CS算法可求解的连续问题，然后部分表示对应的城市编号，而整数部分和小数部分合起它通过Levy飞行改变城市所对应的随机键值，对这些来的数值构成Levy飞行的邻域范围，如图1中有6个城数值重新进行排序从而得到新解。但这种方法实际上市，则每一维的邻域范围为xi∈(0,6)。通过这样的改存在一个很大的不足，即Levy飞行的步长长短与解无变，使Levy飞行的邻域转化为连续空间，可以直接通过关，比如某个城市的随机键值为0.1，通过Levy飞行并CS算法的位置更新公式获得新解，且又有利于判断步根据位置更新公式计算后某个城市的随机键值有可能长的长短，便于根据不同的步长进行的不同操作。
变为0.11或者1.2，而无论是0.11还是1.2，RKCS算法都经过这种编码后，使用公式（1）对下一飞行的位置无视这种区别，而直接根据键值重新进行排序，这样的进行更新，如图1中所示假设有6个城市，令某一城市的话就无法发挥CS算中短距离的探索和偶尔较长距离的当前编码值为xi，而经过Levy飞行后编码值更新为飞行相结合的特点，容易陷入局部最优。而SA-CS算法yi,xi和yi均属于（0，6），如果yi的值超过此范围则将
在CS算法中引入模拟退火算法，SA-CS算法在求解连yi整数部分进行求余运算，
保证其仍在（0，6）之间。然续问题时性能还可以，但将其用于求解TSP问题时性能后计算(int)yi-(int)xi的值，若为0则判断飞行步长较短较差，从实验结果看，其仅能处理小规模TSP问题，而且进行重定位操作，若不为0则说明步长较长需进行替换其得到的最优结果偏差率也都非常大，花费时间也很操作，3.2节和3.3节将具体说明重定位操作和替换操作大，其性能十分低下。
的步骤。
3.2
重定位操作
3
基因-表现型布谷鸟算法（GPCS）
当通过Levy飞行获得候选解时，根据飞行的步长
本文在分析上述算法的基础上结合遗传算法中的进行不同的操作，GPCS算法根据(int)yi-(int)xi来判定基因-表现型的思想提出了GPCS算法，GPCS算法将飞行的长短，其中yi为第i个城市新的编码值，xi为第Levy飞行结果引入公式（1）中以实现位置更新，弥补了i个城市新的原编码值，计算结果若为0则说明整数部
DCS算法的不足，同时根据Levy飞行的结果实现不同分未发生改变，即所表示的城市不变，此时只需重定位的操作，飞行的步长较短时进行重定位操作，飞行的步操作，简单的说即根据小数部分进行重新排序即可。
长较长时进行替换操作，使得精密的小范围搜索和远距
图2描述了重定位操作的过程，首先随机选择城市1，
林敏，钟一文，刘必雄，等：基因-表现型的布谷鸟算法求解旅行商问题2017，53（24）175
其编码值为1.3，通过Levy飞行其值突变为1.56，需要按机小数，M代表城市数目，然后对这些小数进行排序，照小数0.56的大小将它重定位到合适的位置，如图2中排序后将这些小数再加上对应的城市编号，这些带城市的（c）将城市1重新定位到城市0.5之后。
编号的小数就是每个城市的编码。然后对每个个体算法2relocate(xi,yi)
Xi(x1,x2,xi,⋯,xm)从M个城市中随机选择一城市i，其xi为原城市编码，yi为该城市新编码
中xi表示城市编码值，根据Levy飞行公式得到yi，当（1）计算城市xi的上一城市pre和下一城市next；(int)yi-(int)xi=0时，认为其飞行步长较短，通过排序操
（2）将pre指向next；作获得候选解，并计算适应度值Fi,若(int)yi-(int)xi≠0,（3）Ifyi>xi则其飞行步长较长，则采用替代操作获得候选解，并计（4）从pre开始向后搜索找到yi的插入位置k；算此时Fj。若候选解Fj 算法4GPDCuckooSearch （6） 从pre开始向前搜索找到yi的插入位置k； （1）初始化各参数，设定布谷鸟数目N,循环次数times；（7）将yi插入位置k； （2）读取TSP城市信息，建立近邻矩阵，保存城市数目M；4.13.21.35.40.52.9（3）初始化种群，生成N条TSP路径及城市编码，并计（a）随机选择城市1.3 算这N条路径的长度Fi； 4.13.21.565.40.52.9（4）当k （6）根据Levy飞行获得下一个鸟yi=xi+α0(xi-图2 重定位操作 xbest)*levy(λ)； 3.3替换操作 （7）If((int)yi-(int)xi==0) （8）relocate(xi,yi)操作，获得候选解； 当(int)yi-(int)xi不为0时，说明其所代表的城市已 （9）Else 发生改变，并有两个编码值表示同一个城市，则此时先（10）displace(xi,yi)操作，获得候选解； 将yi插入到正确的位置，并找到编码同一城市的基因（11）根据获得的候选解计算路径长度Fj；zi，将zi的整数部分用xi的整数部分直接替换，算法3 （12）If(Fj （13）用Fj替代Fi； 算法3displace(xi,yi) （14） 在新解基础上进行局部搜索操localsearch(M)； xi为原城市编码，yi为该城市新编码 初始化各参数（1）计算城市xi的上一城市pre和下一城市next；（2）将pre指向next； 初始化种群，生成N条路径（3）按小数查找yi对应的插入位置，并插入到该位置（4）查找与yk (int)yi-(int)xi==04.12.451.35.40.52.9YesNo（b）将3.2突变成2.45Relocate(xi,yi)操作displace(xi,yi)4.11.35.42.450.52.9（c）按小数排序 计算Fj,若Fj 按发现概率pa丢弃差的解；用偏好随机游动产生新解替代丢弃的解新解替代丢弃的解3.4GPCS算法的实现 图4和算法4表示了GPCS主要算法执行的主要过 times++程，首先初始化各个参数，设定种群数N，初始化N条结束路径，初始化时对每条路径中生成M个（0，1）之间的随 图4 GPDCuckooSearch算法流程图 1762017，53（24）ComputerEngineeringandApplications计算机工程与应用 （15）按发现概率pa丢弃差的解； 算法5中的局部搜索在选择城市时不是在所有城（16）用偏好随机游动产生新解替代丢弃的解；市中进行搜索，而是在城市的近邻列表中进行搜索。因（17）times++； 为如果某路径是全局最短路径，那么该路径中的城市到（18） 记录当前最优解Fbest； （19）返回全局最优解F其近邻城市的距离也应该较短，根据此原理，算法中取best 算法4中第（15）行按照一定发现概率p每个城市所能到达的最近的数十个城市组成近邻列表，a抛弃旧解，这时候通过随机游走产生新解并替换新解，随机游并将所有城市的近邻列表预先计算好并建立近邻矩走产生新解的方式同局部搜索，也是通过逆转和插入操阵。建立近邻矩阵使得进行局部搜索时，仅在城市的近作产生新解。 邻范围进行搜索，这样加快了搜索速度。 3.5局部搜索 基因决定所要表现的信息，而表现的信息通过外部 4实验与比较 刺激也可以反作用于基因，局部搜索就起到这样的作为了分析GPCS算法的性能，在本章中选取了 用，局部搜索通过逆转和插入操作反作用基因，改变基TSBLIB库中的城市数量从最少为30到最大为33810因编码值，从而生成新解。当通过Levy飞行得到新解的几十个不同的基准实例，进行了仿真实验，将GPCS后，在此解的基础上进行局部搜索，使其在局部范围进算法分别与同为CS算法的DCS算法和RKCS算法以及行充分的搜索，避免其过快陷入局部最优。局部搜索采其他群智能算法进行比较。 用两种策略，一种是逆转操作，一种是插入操作，图5描4.1实验环境和算法参数设置 述了逆转操作的过程，而图6则描述了插入操作的过实验软件为VS2012，CPU为IntelCorei72.40GHz， 程。无论哪种操作，首先都要随机选择一个城市x，然内存为8GB，Windows7操作系统。在仿真实验中，每后在该城市的近邻列表中随机选择另一个城市y，将x个TSP实例分别单独优化20次，算法中的各参数取值与y进行逆转和插入操作，并选择两者中较好的方案与如表1所示。 当前解进行比较，若比当前解好，则替换当前解。 表1 GPCS算法的参数 算法5局部搜索算法localsearch(M) 参数值说明M代表局部搜索内循环次数，这里取城市数目。 n30种群规模（1）i=0； α01步长参数（2）whilei 1.5 调整系数 并计算其适应度值Finv； 在仿真实验的分析中，PDav表示得到的平均解与（5）将城市y插入到城市x之前，并计算其适应度值已知最优解的偏差比，其值越小说明算法的总体性能较Fins； 好，PD为最好解与已知最优解的偏差比，其值越小说（6）IfFins>Finv 明寻得的最优解与已经最优解越接近，其计算公式分别（7）将Finv与当前解F进行比较；（8）Else 由式（7）和（8）给出。 （9）将F平均解-已知最优解 ins与当前解F进行比较； PDav= ×（7）（10）若F大于F已知最优解100% ins和Finv的较小解，则被新解替换；（11）i++； PD=最好解-已知最优解已知最优解×100% （8） 4.13.25.40.51.562.9实验中所比较的算法有的文献中有提供运行时间，（a）选择城市4和1 所以本文也提供算法的运行时间做为补充参考。虽然4.11.20.45.53.562.9各算法运行的环境有所差异，但都是在PC平台上，所以（b）将城市3与城市1之间进行 这种差异不是很显著不会使算法的时间相差太多，而在图5 逆转操作 所运行的环境性能相近的情况下可以看到本算法的运行时间比部分算法快很多，甚至快数10倍，因此本文提 4.13.25.40.51.562.9供的算法运行时间可以当做一个辅助参考指标。 （a）找到城市1和3 4.2GPCS算法与DCS算法及RKCS算法的比较 4.11.23.45.50.562.9求解TSP问题的CS算法的方法主要有DCS算法[17] （b）将城市1插入到城市1前 和RKCS（Random-keyCuckooSearch，RKCS）算法[18]，图6 插入操作 而混合SA-CS算法[19]其性能较差且仿真实例较少，所以 林敏，钟一文，刘必雄，等：基因-表现型的布谷鸟算法求解旅行商问题2017，53（24）177 本文不做比较。由于RKCS算法最大的求解规模只到值来看，在城市数小于100时，三个算法的PDav值十分144个，表2将RKCS算法、DCS算法和GPCS算法在小相近，说明性能比较接近，当城市在100以上，特别当规规模TSP问题上进行了比较，而表3将GPCS算法与模越大是，GPCS算法表现出了最好的性能，DCS算法DCS算法在大规模TSP问题上进行了比较。 次之，特别当规模增大时更加明显。从运行时间来看，DCS、RKCS和GPCS算法的时间复杂度虽然均为GPCS算法的运行时间远远优于DCS算法，而RKCS算O(m×n),m为种群数，n为迭代次数，但从表2的比较结 法并未给出算法的执行时间，所以对RKCS算法的时间果看在相同复杂度的情况下，GPCS算法的各项性能优无从比较，但是根据其算法执行过程中每次都需要遍历于其他两种算法。表2的实例一列是TSPLIB仿真库中所有城市以寻找最优解，可以推测其运行时间较长，所的实例名，Opt表示目前已知的最优解，Best、Mean、以仅对最大规模为144的城市进行求解。表3中将Worst分别是最好解、平均解和最差解，PDav表示得到GPCS算法和DCS算法在大规模TSP问题上进行了比的平均解与已知最优解的偏差比， PD为最好解与已知较，DCS算法的最大规模仅达到1379，而GPCS算法的最优解的偏差比，Time是运行时间，单位为s，后续的表最大规模可以达到33810。从两者的运行时间看，格中列的含义同此表格。从表2的PD值来看，GPCS的GPCS算法的运行时间远比DCS算法要短，特别是当PD值均为0， 说明其在小规模问题上都能找到最优解，城市规模增大时更加显著，对于DCS算法所能求解而RKCS算法在ch130和pr136两个问题上未能找到最的最大规模为1379的实例Nrw1379，其执行时间为优解，DCS算法在pr136中未能找到最优解。再从PDav 3160.47s，这是因为DCS算法在邻域的搜索过程中花 表2 GPCS算法与RKCS算法及DCS算法在小规模TSP问题的比较 序号实例Opt算法Best Mean Worst PDav PD Time/s RKCS 4226.94300.210—1 Eil51 426 DCS42226001.16GPCS4226.504270.1200.15RKCS 75427542754200—2Berlin527542DCS754275427542000.09GPCS754275427542000.03RKCS 675677.36840.30—3St70675DCS675675675001.56GPCS675677.056840.300.18RKCS 1081591082021090850.040—4Pr76108159DCS108159108159108159004.73GPCS1081591083801090430.0700.09RKCS 538539.15410.20—5Eil76538DCS538538539006.54GPCS538538.45460.0700.15RKCS 21282212.65213430.040—6KroA10021282DCS212822128221282002.70GPCS2128221295.9213790.0700.32RKCS 629631.16360.330—7Eil101629DCS629630.436330.23018.74GPCS629629.656310.100.28RKCS 118282118798.11207730.440—8Bier127118282DCS118282118359.631187300.070GPCS118282118525.31199260.2100.45RKCS 61266163.362100.870.26—9Ch1306110DCS61106135.9661740.42025.50GPCS61106131.9561880.3600.49RKCS 9704697708.99360.960.28—10Pr13696772DCS9679097009.26971380.240.0235.82GPCS9677296880.4971420.1100.RKCS 5853758554.45586070.030—11Pr14458537DCS585375853758537002.96GPCS 58537 58579.95 59290 0.07 0 0.59 1782017，53（24）ComputerEngineeringandApplications计算机工程与应用表3 GPCS算法与DCS算法的在大规模TSP问题上的比较 序号实例Opt DCS算法 GPCS算法Best Mean PD PDav Time/s Best Mean PD PDav Time/s 1Ch150652865286549.900.3327.7465286560.9700.500.742KroA150265242652426569.2600.1731.232652426563.6700.380.753KroB150261302613026159.300.1133.012613226172.970.010.240.7Pr15273682736827368200.0014.867368273821.9000.180.695Rat195232323242341.860.040.8157.2523242331.600.040.371.026D198157801578115807.6600.1759.951578815803.800.050.171.157KroA200293682938229446.660.040.2662.082936829455.6000.331.078KroB200294372944829542.490.030.29.062943829495.4700.331.119Ts22512631263126659.2300.0147.511263126756.7300.121.1810Tsp225391639163958.7601.0976.1639163926.9700.611.1511Pr226803698036980386.6600.0250.008036980416.9700.021.2212Gil262237823822394.50.160.68102.3923792381.100.040.261.613Pr2491354913549257.500.2482.934913549201.9000.051.1314A280257925792592.3300.51115.5725792581.4300.121.7615Pr299481914820748470.530.030.58138.204819148230.8700.131.9716Lin318420294212542434.730.220.96156.1742162263.670.330.732.1217Rd400152811544715533.731.081.652.941530615332.670.160.503.5618Fl417118611187311910.530.100.41274.591191311950.370.441.044.2819Pr439107217107447107960.50.210.69308.75107628108245.270.380.953.4820Rat5756773666956.731.812.71506.6767856810.100.180.53421Rat783880690439109.262.693.44968.6688218858.770.170.516.1522Pr1002259045266508268630.032.883.701662.61259963261303.970.350.9.6623Nrw13795663855159349.534.084.783160.4756857021.430.440.5915.3824U2319234256—————234847235312.300.250.3438.4025Pcb3038137694—————138468138560.970.560.7061.5426Fnl4461182566—————183937183962.830.750.87124.8827Rl5934556045————— 559070560734.030.540.179.5528Pla739723260728————2354801623596237.101.241.44482.3529Usa1350919982859— — — — 20119920191312.700.911.041426.3130 Pla33810 660445 67267377 67312014.30 1.84 1.91 10975.60 费了大量的时间，计算速度十分缓慢，这也了其所优化算法，文献[5]和文献[6]对BA算法进行了改进，提求解的问题规模。而GPCS算法的执行时间为15.38s，出了离散的蝙蝠算法（DiscreteBatAlgorithm，DBA）和而且GPCS算法在求解问题的规模达到13509个城市混沌混合离散蝙蝠算法（ChaoticHybridDiscreteBat时，其时间仍只需30多分钟。对比两者的PDav数据可Algorithm，CHDBA），并将它们用于求解TSP问题，本节以看出，在较小规模问题上，两者性能相近，但在城市数中将GPCS算法与DBA及CHDAB这两种改进的新型大于300的8个TSP问题上，GPCS算法明显优于DCS蝙蝠算法进行比较。DBA和CHDAB算法的时间复杂算法，可见GPCS在大规模TSP问题上具有明显优势。度也为O(m×n)，但从实验结果看，GPCS算法在相同复再来看PDav值，在问题规模不超过7000时，GPCS算法杂度情况下，求解结果明显优于这两种改进的蝙蝠的PDav始终保持在1%以下，而DCS算法在问题超过算法。 500时，PDav值就超过2%。最后比较两者的PD值，表4将GPCS算法与CHDBA算法进行了比较，GPCS算法的PD值除了实例Pla7397在1%以上，其他CHDBA算法的最大求解规模只有200，而根据表3的结均在1%以下，而DCS算法在城市规模500以上时，PD果看，GPCS最大规模可以到33810，所以CHDBA宣称值就增长明显，说明其随着规模增大，其寻得最优解其求解大规模TSP问题，而实际最多只到200。从表中的能力下降得更加明显，而GPCS算法相对十分稳定。显示的运行时间看，GPCS算法明显优于CHDBA算法，所以从各方面来看，GPCS算法优于DCS算法和RKCS对求解的6个TSP基本都在1s左右，而CHDBA计算到算法。 规模为200的城市时所需要时间居然为1734s。从PD4.3GPCS算法与蝙蝠算法的比较 值来看，GPCS算法均为0，而CHDBA有4个问题未能蝙蝠算法（BatAlgorithm，BA）是一种新型群智能 寻得最优解。 林敏，钟一文，刘必雄，等：基因-表现型的布谷鸟算法求解旅行商问题 2017，53（24）179 表4 GPCS算法与CHDBA算法的比较 序号实例Opt CHDBA算法 GPCS算法 Best PD Time/s Best PD Time/s 1Oliver304204230.710.01942000.022Eil5142280.475.37542600.123Pr7610815910815902.05010815900.214Ch13061106110074.690611000.565Krob15026130262171.412012613200.876 Krob200 29437 29554 0.39 1734 29445 0 1.25 表5 GPCS算法与DBA算法的比较 序号实例Opt DBA算法 GPCS算法Best Mean PD PDav Time/s Best Mean PD PDav Time/s 1Eil5142228.100.491.74226.6000.140.182Berlin52754275427542.0002.175427542000.033St70675675679.100.613.9675677.6000.390.244Eil76538539548.10.191.885.1538538.6500.120.115KroA100212822128221445.300.7710.62128221308.2000.120.356KroB100221402214022506.401.6511.12214122220.9500.370.457KroC100207492074921050.001.4512.02074920803.1500.260.398KroD100212942129421593.401.4111.72129421346.2500.250.479KroE100220682206822349.601.2811.42212122192.650.240.560.5610Eil1016296346.40.792.7713.1629629.5500.090.2911Pr107443034430344793.801.1112.14430344375.8500.160.5012Pr124590305903059412.100.6518.55903059084.3000.090.5913Pr136967729754799351.20.792.6723.49677296868.3500.100.7814Pr144585375853758876.200.5830.35853758610.1000.120.6015Pr152736827392174676.90.321.3531.07368273796.5000.160.7216Pr2491354975650908.31.253.6192.54913549214.9500.161.5117Pr299481914831049674.10.253.08147.24819148256.8500.142.1418Pr439107217111538115256.43.877.50201.9107486108328.200.251.043.9219 Pr1002 259047 270016 274419.7 4.06 5.93 681.7 260561 261294.80 0.58 0.87 12.50 表5将GPCS算法与DBA算法进行了比较，从表中4.4.1GPCS算法与GSA-ACS-PSO算法及DMRSA 可以看到，无论是平均解、最优解，还是运行时间，GPCS算法的比较 算法都优于DBA算法，DBA在19个问题上的平均PDav本节中将GPCS算法与DMRSA算法及GSA-ACS-是2.04，而GPCS算法的平均PDav是0.27。DBA算法PSO算法进行了比较，实验中GSA-ACS-PSO算法的种有多个实例无法求得最优解，而GPCS算法在本次运行群数为100，迭代次数为1000，HDCS算法种群数从30，中只有KroE100、Pr439和Pr1002这三个实例未求得最最大迭代次数不超过2000，而DMRSA所采用的局部佳解。从运行时间上看，GPCS算法19个实例的平均运搜索策略，实际需要更多的迭代次数。从表6中的数据行时间只有1.38s，DBA算法则为69.54s。 看，当问题规模小于500时，DMRSA算法与GPCS算法4.4与其他经典的智能优化算法相比较 性能比较接近，各有优势，而当问题规模超过500时，为了进一步验证GPCS算法的性能，本节选择了3 GPCS算法的PDav仍然保留在1以下，而DMRSA都超个基于经典智能优化算法的方法进行比较，即混合GA、过了1，所以当规模增大时，GPCS算法明显较优。而对SA、ACS和PSO算法思想的GSA-ACS-PSO算法[25]和动比GSA-ACS-PSO算法，GPCS算法的各项数据十分占态多尺度区域搜索算法（DynamicMultiscaleRegion 优，GSA-ACS-PSO算法应该是三种算法中性能最差的。SearchAlgorithm，DMRSA）[26] 、扩展蚁群优化（AntCol- 4.4.2GPCS算法与ACE算法的比较 onyExtended，ACE）[27]。DMRSA、GSA-ACS-PSO和ACE是对蚁群优化算法的改进，是一种扩展的蚁群ACE算法的时间复杂度也为O(m×n)，并且在实际运行算法。ACE总的迭代次数是个变量，最多不超过400n，当中这三种算法的m×n值大于等于GPCS算法中的其中n为城市规模。为了将GPCS算法与ACE算法进m×n值，后续的比较中在相同时间复杂度情况下，对各 行比较，这里设定GPCS算法种群数仍为30，迭代次数种指标进行了分析比较。 为m,m需满足30m≤400n的关系。在表7中选择了22 1802017，53（24） ComputerEngineeringandApplications计算机工程与应用 表6 GPCS算法与GSA-ACS-PSO算法及DMRSA算法在TSPLIB中的24个基准函数的比较 序号实例Opt GSA-ACS-PSO算法DMRSA算法 GPCS算法 Best Mean PDav Best Mean PDav Best Mean PDav 1eil514227427.270.304226.4800.114226.50.122berlin52754275427542.0007542754207542754203eil76538538540.200.41538540.3600.44538538.40.074eil101629630635.230.99629630.9800.31629629.150.025bier127118282118282119421.830.96118282118435.6300.13118282118373.10.086ch130611061416205.631.5761106120.3600.1761106117.550.127ch150652865286563.700.5565286547.2800.365496554.550.418rd100791079107987.570.9879107912.5300.0379107919.60.129lin105143791437914406.370.19143791437901437914386.70.0510lin318420294248743002.902.324204042232.040 0.484205042225.90.4711kroA100212822128221370.470.42212822128202128221286.60.0212kroA1502652426524269.201.412652426568.6700.172652426556.90.1213kroA200293682938329738.731.262936829439.0800.242938329458.50.3114kroB100221412214122282.870.2214122184.6100.22214122207.50.3015kroB1502613026130248.331.222613026144.8500.062613226142.550.0516kroB200294372954130035.232.032943829578.4400.482943729490.90.1817kroC100207492074920878.970.632074920751.1400.012074920779.90.1518kroD100212942130921620.471.532129421296.7000.012129421311.650.0819kroE100220682206822183.470.522206822114.9600.212206822157.350.4020rat5756773616933.872.3869096953.2252.6667876799.250.3921rat78388068079.233.1090319090.3703.23881288370.3522rl13232701992772280181.473.692710274083.4201.44270231270876.70.2523fl1400201272059321349.636.0720348204.3101.682021520262.850.6724 d1655 62128 151 65621.13 5.62 63847 202.700 3.34 62347 62558.8 0.69 表7 GPCS算法与ACE算法性能的比较 序号实例Opt ACE算法GPCS算法Best Worst Mean PDav Best Worst Mean PDav 1Ry4814422144221488314495.8000.51144221472714512.350.622Eil5142232426.8180.194227426.500.103Berlin527542754277157543.0400.0175427542754204Ftv701950195020601968.1600.93195019961955.650.285St70675675691676.4180.21675684677.550.406Eil76538538546538.3110.06538538538 07Pr761081591081591090851082510.09108159109043108291.600.108Rat991211121112461213.2900.19121112121211.6009Kroa10021282212822160021298.6000.08212822130521284.80010Eil1016296294633.6190.73629631629.450.1011Lin10514379143791451414385.5000.05143791440114387.800.1012Kro124p362303623037777360.8000.362303635236267.100.1013Ch1306110611062596153.960 0.72611061566127.300.3014Ch15065286528667065500.34652865886557.550.4515Pr15273682736827480273766.8000.127368274073830.350.2016U159420804208043812199.8000.28420804250042376.150.7017Ftv1702755275530072824.0802.51275527992771.850.6118D198157801578015915813.3000.21157801581715801.850.1319Gil2622378237824132390.0600.51237823952381.650.1520D49335002351233577035449.3001.28351113522835176.150.5021Rat783880688601036.7001.48882188818856.550.6022 Fl1400 20127 20328 21067 20491.700 1.81 20232 20382 20283.70 0.80 个TSPLIB中的实例，将GPCS算法与ACE算法进行了TSP问题。从比较结果的PDav来看，GPCS算法十分稳比较，其中Ry48、Ftv70、Ftv170和Kro124p为非对称 定，均保持在1以下，而ACE算法当规模增大时，其值变 林敏，钟一文，刘必雄，等：基因-表现型的布谷鸟算法求解旅行商问题2017，53（24）181 化较明显，另外对比当规模小于159的16个城市，两者法[J].计算机学报，2001，24（12）：1328-1333. 性能十分接近，GPCS算法有7个实例的PDav值略低于[10]冀俊忠，黄振，刘椿年，等.基于多粒度的旅行商问题描述 ACE算法。再比较它们的最差解数据，GPCS算法在所及其蚁群优化算法[J].计算机研究与发展，2010，47（3）：有TSP实例上均优于ACE算法，而从找到的最优解来434-444. 看，GPCS算法与ACE算法在小规模问题上均能找到最[11]杜占玮，杨永健，孙永雄，等.基于互信息的混合蚁群算法 优解，在较大规模问题上如D493、Rat783、Fl1400这几及其在旅行商问题上的应用[J].东南大学学报：自然科学个问题上GPCS算法更加接近最优解。 版，2011，41（3）：478-481. [12]ShiXH，LiangYC，LeeHP，etal.Particleswarm 5结束语 optimization-basedalgorithmsforTSPandgeneralizedTSPinformationprocessingletters[J].InformationPro-本文提出的GPCS算法是一种CS算法的离散化方 cessingLetters，2007，103（5）：169-176. 案，通过这种基因-表现型的编码方案，给每一城市赋予[13]易云飞，林郭隆，董文永，等.一种基于粒子优势分析的异 一个基因，即整数部分为城市编号的随机小数编码，解步混合粒子群算法[J].小型微型计算机系统，2015，36（6）：码过程小数部分决定了该城市的访问次序，而整数部分1379-1383. 则直接解码为所对应的城市，通过这种方法，将TSP问[14]于莹莹，陈燕，李桃迎.改进的遗传算法求解旅行商问题[J]. 题的邻域转化为连续问题的空间，再结合Levy飞行，根控制与决策，2014，29（8）：1483-1488. 据Levy飞行步长的长短选择不同的操作，当步长较短[15]刘荷花，崔超，陈晶.一种改进的遗传算法求解旅行商问 时进行重定位操作，当步长较长时进行替换操作。最后题[J].北京理工大学学报，2013，33（4）：390-393. 在大量TSP实例上对GPCS的性能进行了仿真实验，表[16]YangXS，DebS.CuckoosearchviaLévyflights[C]// 明GPCS算法能够在较短的运行时间内处理大规模TSPWorldCongressonNature&BiologicallyInspired问题并获得满意的结果，其总体性能不但优于同为CSComputing，2009，NaBIC2009，2009：210-214. 算法的DCS算法和RKCS算法，也优于新型群智能优化[17]OuaarabA，AhiodB，YangXS.Discretecuckoosearch 算法CHDBA和DBA，还优于基于经典智能优化算法的algorithmforthetravellingsalesmanproblem[J].Neu-DMRSA算法、GSA-ACS-PSO及ACE算法，当问题规模ralComputing&Applications，2014，24（7/8）：1659-1669.大时优势特别明显。GPCS算法所提出的基因-表现形[18]OuaarabA，AhiodB，YangXS.Random-keycuckoo searchforthetravellingsalesmanproblem[J].SoftCom-的编码方案，不仅可以应用于TSP问题，还可以通过改puting，2015，19（4）：1099-1106. 造将其应用其他组合优化问题。 [19]马灿，刘坚，余方平.混合模拟退火的布谷鸟算法研究[J]. 小型微型计算机系统，2016，7（9）：2029-2034. 参考文献： [20]王李进，尹义龙，钟一文.逐维改进的布谷鸟搜索算法[J]. [1]MengX，LiuY，GaoX，etal.Anewbio-inspiredalgo-软件学报，2013，24（11）：2687-2698. rithm：Chickenswarmoptimization[M]//AdvancesinSwarm[21]张永韡，汪镭，吴启迪.动态适应布谷鸟搜索算法[J].控制 Intelligence.[S.l.]：SpringerInternationalPublishing，2014：与决策，2014，29（4）：617-622. 86-94. [22]马卫，孙正兴.采用搜索趋化策略的布谷鸟全局优化算法[J]. [2]于宏涛，高立群，韩希昌.求解旅行商问题的离散人工萤火 电子学报，2015，43（12）：2429-2439. 虫算法[J].华南理工大学学报：自然科学版，2015，43（1）：[23]贾云璐，刘胜，宋颖慧.基于种群特征反馈的布谷鸟搜索 126-131. 算法[J].控制与决策，2016，31（6）：969-975. [3]罗雪晖，杨烨，李霞.改进混合蛙跳算法求解旅行商问题[J]. [24]BeanJC.Geneticalgorithmsandrandomkeysfor 通信学报，2009，30（7）：130-135. sequencingandoptimization[J].InformsJournalonCom-[4]吴新杰，王静文，黄国兴，等.一种求解旅行商问题的改进 puting，1994，6：154-160. 蛙跳算法[J].小型微型计算机系统，2015，36（5）：1078-1081.[25]ChenSM，ChienCY.Solvingthetravelingsalesman [5]OsabaE，YangXS，DiazF，etal.Animproveddiscrete problembasedonthegeneticsimulatedannealingantbatalgorithmforsymmetricandasymmetrictravelingcolonysystemwithparticleswarmoptimizationtech-salesmanproblems[J].EngineeringApplicationsofArtifi-niques[J].ExpertSystemswithApplications，2011，38（12）：cialIntelligence，2016，48（C）：59-71. 14439-14450. [6]戚远航，蔡延光，蔡颢，等.旅行商问题的混沌混合离散蝙 [26]ZhangHG，ZhouJ.Dynamicmultiscaleregionsearch 蝠算法[J].电子学报，2016，44（10）：2543-2547. algorithmusingvitalityselectionfortravelingsales-[7]王勇臻，陈燕，张金松.用于求解旅行商问题的多策略离散 manproblem[J].ExpertSystemswithApplications，2016，型和声搜索算法[J].华南理工大学学报：自然科学版，60：81-95. 2016，44（1）：131-138. [27]EscarioJB，JimenezJF，Giron-SierraJM.Antcolony [8]张鑫龙，陈秀万，肖汉，等.一种求解旅行商问题的新型帝 extended：Experimentsonthetravellingsalesmanprob-国竞争算法[J].控制与决策，2016，31（4）：586-592.lem[J].ExpertSystemswithApplications，2015，42（1）：[9]吴斌，史忠植.一种基于蚁群算法的TSP问题分段求解算 390-410.
因篇幅问题不能全部显示，请点此查看更多更全内容