改进二进制布谷鸟搜索算法求解TSP问题

姜保强

摘 要：针对TSP问题的特点，设计了一种求解TSP问题的改进的二进制布谷鸟算法。该算法采用二进制编码串表示鸟巢的位置，对布谷鸟寻找新鸟巢的莱维飞行路径进行了二进制代码变换，引入了二进制编码控制系数对变换得到的二进制编码进行混合更新，保留了布谷鸟蛋被淘汰的机制等方法，并且引入了贪心思想，将新型高效的布谷鸟搜索（CS）算法改进为二进制布谷鸟搜索（BCS）算法。将BCS算法用于求解TSP问题。通过多组数据的测试，对比"TSP问题数据集合目录（标准测试集）"结果表明，要好于禁忌搜索算法，遗传算法，蚁群算法，粒子群算法。

关键词：二进制；布谷鸟搜索算法；旅行商问题；贪心算法

ABSTRACT：According to the characteristics TSP problem， we design an improved TSP problem solving binary cuckoo algorithm. The algorithm uses a binary code string showing the location of the nest， the nest of the cuckoo to find a new flight path of Levi binary code conversion， this paper introduces the binary coded control coefficient transform binary coding mixed update， the paper retains the cuckoo egg method being eliminated mechanisms， and introduces greedy thought， this article will search for new and efficient cuckoo （CS） algorithm to improve a binary search cuckoo （BCS） algorithm. The BCS algorithm for solving TSP. By testing multiple sets of data， compared to "TSP problem of data collection catalog （standard test set），" The results show that better than tabu search algorithm， genetic algorithm， ant colony algorithm， particle swarm optimization.

Keywords： Binary； Cuckoo search algorithm； traveling salesman problem； greedy algorithm

1 引言

TSP（旅行商）问题是指已知n个城市之间的相互距离，寻找一条遍访n个城市，每个城市只访问一次。最终又回到出发城市的最短旅行路线。这是一个典型的组合优化问题，被证明是NP完全问题，其所有的路线数为n，搜索空间随着城市数n的增大而迅猛增大，这就产生了所谓的“组合爆炸”问题。目前还没有一种完全有效的算法解决TSP问题。由于TSP问题有很高的理论价值和实际应用背景，如何以用来解决分配、调度和网络优化问题等，所以人们一直致力于研究新的算法达到高效求解TSP问题。求解TSP问题传统的方法有穷举搜索法、贪心法、动态规划法等，这些方法都面临着这样一个共同的问题，即当问题的规模 N 大到一定程度时，问题的计算量极大地超出了机器所能允许的极限。现代流行的智能算法主要有遗传算法、郭涛算法、蚁群算法、粒子群优化算法。

英国剑桥大学的Yang等在研究了布谷鸟的繁殖行为和莱维飞行特性之后于2009年创立了布谷鸟搜索（ Cuckoo Search， CS）算法，并用大量的函数对其性能进行了测试，结果表明该算法在许多方面的性能已经超过了微粒群算法和遗传算法：CS算法具有全局搜索能力强、选用参数少、搜索路径优、多目标问题求解能力强等优点。然而，原始的CS算法只能用于求解连续型的优化问题，不能用于求解离散型的优化问题如NP完全问题。本文将原始的CS算法改进成为二进制布谷鸟搜索（Binary Cuckoo Search，BCS）算法，并应用旅行商问题（TSP）。

2 TSP问题数学描述

TSP问题（Traveling Salesman Problem），又称旅行商问题，每两个城市i和j之间的距离为Dij，城市行走的排列顺序用数学符号表示为： X=（C1，C2，……Cn），目标函数 。

3 求解TSP问题的改进的二进制布谷鸟算法

3. 1 编码方法

本文提采用的解码方案如下：采用二进制编码，设TSP问题有n个城市，则用长度为r=n*[log2n ]个二进制位代表一个染色体。设有一染色体的二进制编码为T={t1， t2，... tr}，其中ti=0或ti=1。解码时，把T平均分成n段，然后把分别每一段看成一个二进制数还原成相应的整数，再对这n个整数从小到大排序，用相应的位置当成一条路径中的城市编号。例如，设TSP问题有5个城市，则染色体编码的长度为15，设其中一个染色体的编码为[011010001010100]，解码时，每3个二进制编码为一段，可化为有重复整数序列[3 2 1 2 4]，从小到大排序后，其相应的位置为[4 2 1 3 5]，可看作无重复的城市编号解释为一条回路。在此编码方案下，采用二进制的两点交叉及均匀变异，不仅可以避免产生重复城市编号的问题，而且产生的子代很好的继承了父代的优良路径，使得种群得以进化，并扩大了搜索的空间。

3. 2 适应度函数

适应度函数设置为路径的长度，函数值越小，也就表示个体的适应度越好。

3. 3 CS算法

布谷鸟搜索算法是由布谷鸟的寄宿孵生的繁殖行为和levy飞行机制演化而来的。在大自然中布谷鸟是一种会将自己的鸟蛋产在别的鸟类的巢穴里，让别的鸟来帮助它孵化它的后代的寄宿繁殖的鸟类。布谷鸟产的蛋在别的鸟巢时很有可能会被发现，那么寄宿其他鸟巢孵化自己后代的计划就失败，只能另寻更好的鸟巢，如果宿主鸟没有发现这个计划的实施，就会帮布谷鸟孵化鸟蛋，并且布谷鸟幼雏会比宿主鸟先被孵化出来，只要布谷鸟幼鸟被孵化出来它就会将其他的鸟蛋从鸟巢里推出去，以助其加快成长。Levy飞行在自然界中很多动物和昆虫的飞行行为中普遍存在，比如在飞行过程中可能会突然转一个90度的弯接着飞行。

布谷鸟搜索算法是在以下三个理想的假定前提下提出的：

（1）一只布谷鸟只产一个蛋，而且随机的寄宿在某个被选中的鸟巢中；

（2）最好的鸟巢位置将被保留到下一代；

（3）布谷鸟能够利用的多样性的鸟巢数量是固定的n个，布谷鸟蛋被发现的概率为pa，pa∈[0，1]。

莱维飞行取决于由公式（3）和公式（5）产生的两个正态分布的随机数v，u，v，u可大可小，可正可负，故布谷鸟每次按Levy飞行机制随机搜索的路径长短和方向都是高度随机改变的，很容易从一个区域跃入到另一个区域，是个CS算法的全局多样性特别强。另一方面，CS算法借鉴了布谷鸟的繁殖行为，定义布谷鸟蛋被宿主鸟发现的概率pm=0.25，不适应环境的较差的布谷鸟蛋被淘汰，适应环境的优秀的布谷鸟蛋被孵化，保证新生的布谷鸟都是优秀个体组成，使得CS算法具有较强的收敛性。

3. 4 BCS算法

原始的CS算法用于求解连续空间的优化问题，取得了很好的效果。欲将CS算法用于求解离散型的优化问题，须对其进行二进制改进，已得到二进制布谷鸟搜索（BCS）算法。

首先，用一个长度为nc的二进制编码串来表示的m代第i个鸟巢第j维变量的值，那么 就表示第m代第i个鸟巢第j维变量的第k个二进制编码，其中k=1，2，..，nc。

其次，对Levy飞行每次位置更新的跳跃路径step进行二进制代码变换。按照Kennedy和Eberha 公式[1]变换得到Levy飞行的二进制代码变换公式为：

按照刘建华[2] 进行变换则得到Levy飞行的二进制代码变换公式，当Step<=0时为：

当Step>0时为：

然后，采用二进制编码的混合更新方法。按照文献[2]的分析可知，的分析可知，若只用式（5）和式（6）进行二进制编码的更新，其全局多样性很强，而几乎没有收敛性；而只用式（7）～式（11）进行更新，其收敛性很强，但全局多样性较弱。为使BCS算法的性能更好，在BCS算法中引人二进制编码控制系数pr ∈[0，1]，在算法的每一代均使用上述两类公式对二进制编码进行混合更新，得到BCS算法中Levy飞行的二进制编码混合更新方法为：

If rand（）<=pr

利用公式（5）和（6）对二进制编码进行更新

Else

If Step<=0

利用公式（7）和（8）对二进制编码进行更新

Else

利用公式（9）和（10）对二进制编码进行更新

Endif

Endif

在混合更新时：若pr越大，则BCS算法的全局多样性就越强；若pr越小，则BCS算法的收敛性越强。

最后保留布谷鸟蛋被淘汰的机制，即设定布谷鸟蛋被宿主鸟发现而淘汰的概率为pa，以保证BCS算法的收敛性。

3.5 贪心算法求解TSP问题

贪心算法通常包含用来寻找具备最优的迭代过程，在很少的计算基础上作出相对正确的猜想而不着急去考虑后面的情况，这样一步一步的来构造解，每一步都是找到局部最优解的后，在最优解的基础上，并且每走一步都会扩大部分解的规模，每次的选择都能产生最大的直接收益，同时还能保持稳定性可行性。

在求解最短路径时，设G（V，E）是以一个每条边有非负长度的有向图，有一个源点v，要确定从v到V中每个其他顶点的距离，这里从顶点v到顶点x的距离定义为从v到x的路径长度。假设V={1，2，3，...，n}，并且v=1。首先将顶点分为两个集合X={1}和Y={2，3，4，...，n}。从源点到这些点的距离都是确定的，在接下来的每一步中，将选定源点到它的距离已经获得的一个顶点y，y属于Y，并将y移动到X中。

在实际生活中的最短路径问题认为两两城市之间都有通路且没有方向，根据三角形定理，两边之和必然会大于第三边，因此不会出现更新在Y中与y相邻的顶点的边的权值。因此引入在该算法中的贪心思想为：确定一个城市坐标为源点放在s中，然后从剩下的城市中找到与源点城市距离最小的城市移入s中。再将刚放入到s中的顶点去剩下的城市中搜索跟它距离最短的城市，并将找到的城市放入s中，以此类推将所有的城市都移入到s中。

原始贪心算法的流程如下。

Step1：将源点1移入X中，Y中的顶点个数为V-1，λ [1]=0。

Step2：对于每个属于Y的顶点v，如果存在从1到顶点v的边，则令λ [v]为边的长度；否则令λ [v]为无穷大，并设λ [1]=0。

Step3：while Y ≠{}

Step4： 令y Y，使得λ [y]为最小

Step5： 将y从Y移动到X

Step6： 更新那些在Y中与y相邻的顶点的标记

For每条边（y，w）

If w ∈Y and λ[y]+length[y，w]< λ [w] then

λ [w]=λ [y]+length[y，w]

End for

Step7：end while

在实际生活中，经过的城市存放在s中，初始化是让所有城市都不在s中即s[x]=0，表示编号为x的城市不在s中，若s[x]=1，表示编号为x的城市在s中。D是存储最短路径的城市顺序的编号。

设源点为v，流程如下。

Step1：s[v]=1，D[0]=v； m=v； //m是存储将要移入s中的城市的编号。

Step2：for n从1到CityNum

Step3： 从其他剩余的城市里找到与源点城市距离最小的城市d

Step4： D[n]=d；m=d；s[m]=1； //将编号为m的城市放入s中

Step5：end for

Step6：输出D。

3. 6 BCS结合贪心算法解决TSP的算法流程

Step1：给定参数pa和pr，随机产生n个染色体作为初始种群。（同样也是当前最优群体）染色体为二进制编码，编码长度如上所述。

Step2 ：对染色体进行解码，方法如上所述，进行适应度评估。得到初始群体的最优值作为全局最优解（bestindividual）。

Step3 ：在给定的pr下，将Levy飞行的路径Step按公式（5）～（10）进行二进制代码变换后，采用二进制编码混合更新。产生新的种群规模为n的布谷鸟群体，对新找到的n个鸟巢进行解码，之后进行适应度评价，并同当前的群体的每个个体比较，得到当前最优解（bestindividual），和最优群体。

Step4：产生服从均匀分布的随机数rand（）∈[0，1]，与布谷鸟蛋被发现的概率pa进行比较，若rand（）>pa，则应用这个个体与当前最优个体进行多点交叉，并且进行换位变异的方法（为了保证进化前期的稳定性和防止后期进化的陷入局部最优解，所以前期变异概率小，后期变异概率适当增大），得到新的位置，否则不变。

Step5：为了增强算法的收敛性，在算法的后期每隔100代，对群体的10%进行一次贪心算法，优化一下群体。这样即增强的收敛性，也不影响算法搜索的全局多样性。

Step6：回到步骤2 重复迭代，直到达到最大迭代次数。即算法结束，输出最优解bestindividual。

4 实验结果

4.1 实验条件和测试集

（1）实验条件

实验条件如表4-1所示。

（2）测试集

为了最好地说明本文算法的有效性，本文选用了国际上最通用的 TSP 测试库 TSPLIB（http：//elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html）中的多个问题实例进行测试，每个问题的求解均运行本算法10 次。以下给出了每个问题求解时的参数设置，以及10次运行每次所得的最优值，10次运行的平均路径，并和TSPLIB中公布的最短路径进行了对比。

4.2 试验参数和结果

（1）试验参数的设置

实验参数的设置如表4-2所示。

（2）实验结果

先对pr76进行将问题执行十次的结果进行罗列，并与其他算法进行比较。

表4-2 eil76运行10的结果及平均值、最优值及与其他算法和tsplib公布的最优值的对比

（3）与其他算法比较

将本文算法中的得到的结果跟其他算法求解TSP问题的结果以及TSPLIB公布的最优的结果进行比较。

对于文中用到比较数据进行如下说明：

在下表中MPSO、MFFA、FFA和GN算法得出的结果出自参考文献[3]。在此文献中，GA，TS，PSO算法来自于TSP问题数据集合目录（标准测试集）。为了排除随机性每个算法都运行了25次，本文取其最优值进行比较；MACO算法出自于参考文献[8]，TSPLIB最有解来自于TSPLIB最新公布的最优解。

改进后的BCS算法在经过上一节中测试后与原始的布谷鸟搜索算法、其他的比较新颖的算法以及TSPLIB公布的数据比较的结果如表4- 3所示。

5 结论

经过以上各表的分析我们发现在解决中TSP问题时，本算法表现出优越的性能，其收敛速度和收敛精度都有不小的提高。虽然和tsplib公布的最优解还有些差距，但是比起GA，POS等算法，还是有很大的优势的。进而证实了改进的二进制布谷鸟搜索算法具有一定的可行性和有效性。

参考文献：

[1]KENNEDY J，EBERHARTR.Particle swarm optimization[C]//Proceedings of the IEEE International Conference on Neural Networks.Pisalaway：IEEE，1995：1942-1948

[2]刘建华.粒子群算法的基本理论及其改进研究[D].长沙：中南大学，2009：77-98

[3]王忠英，白艳萍，岳利霞.经过改进的求解TSP问题的蚁群算法[J].数学的实践与认识，2012，2