¹莆田学院信息工程学院计算机系，福建 莆田

²福建省特种设备检验研究院莆田分院，福建 莆田

收稿日期：2021年3月22日；录用日期：2021年4月16日；发布日期：2021年4月23日

摘要

针对节点分布呈现簇状特征的旅行商问题，提出了一种改进的人工蜂群算法。根据该问题簇内节点分布的密度特点，对引领蜂、跟随蜂和侦查蜂角色转变机制和搜索策略进行了相应的调整。蜂群角色转变基于密度值的大小，引领蜂搜索基于领域优先的原则，侦查蜂搜索在陷入局部最优值时具有跳出领域约束的机制，跟随蜂搜索根据相应的跟随策略从而提高在领域内的运算速度。最后的仿真结果表明，算法对具有簇状特征的TSP问题能够在较短时间内找到满意解，在时间和精度上比经典的仿生算法具有明显的优势。

关键词

TSP，簇状，ABC，域，密度

An ABC Solution of TSP with Cluster Feature

Jianbing Lin¹, Zhongfu Xu²

¹Depatment of Computer Science and Technology, Information Engineering College, Putian University, Putian Fujian

²Putian Branch of Fujian Special Equipment Inspection and Research Institute, Putian Fujian

Received: Mar. 22^nd, 2021; accepted: Apr. 16^th, 2021; published: Apr. 23^rd, 2021

ABSTRACT

In view of the Travel Salema Problem with cluster distribution, an improved Artificial Bee Colony algorithm is proposed. According to the density characteristics of node distribution in and outside the cluster, the role transformation mechanism and search strategy of leading bee, following bee and detection bee are adjusted accordingly. The change of the role of bee colony is based on the size of the density value. The searching strategy of the leading bee search is based on the principle of domain priority, the searching strategy of the detection bee search has the mechanism of jumping out of the domain constraints when it falls into the local optimal value, and strategy of the following bee search improves the operation speed in the domain according to the corresponding following principle. Finally, the simulation results show that the improved ABC algorithm can find a satisfactory solution to the TSP problem with cluster characteristics in a short time, and has obvious advantages over the classical bionic algorithm in time and accuracy.

Keywords:TSP, Cluster, ABC, Domain, Density

Copyright © 2021 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

TSP (Traveling Salesman Problem)是一个经典的优化问题，常被称为“旅行推销员问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。规则虽然简单，但随着节点数量的增多，对目标进行求解的问题变得复杂起来，已被证明是一个NP-hard问题。研究TSP问题并进行求解优化，在很多领域都有广泛地应用，例如社交网络优化、VLSI芯片设计、网络路由、车辆路径问题等 [1] [2]。求解TSP时，随着节点的增多，对应解空间呈指数级增长，计算量剧增。近年来，许多解决旅行商问题的元启发式的算法被提出来，主要有神经网络(Neural Network)、模拟退火(Simulated Annealing, SA)、遗传算法(Genetic Algorithms, GA)、蚁群优化算法(Ant Colony Optimization, ACO)、粒子群优化算法(Particle Swarm Optimization, PSO)和人工蜂群算法(Artificial Bee Colony Algorithm, ABC)等一系列群体智能算法 [3]。蜂群算法是一种相对较新的群智能算法，模拟自然界蜜蜂的采蜜行为。 [4] 分析研究了人工蜂群算法及3种基本算法模型以及三种引领因子更新策略，讨论了转移因子动态更新公式及状态转移公式，并通过典型的TSP实例进行了仿真实验，结果表明该算法能够克服早熟现象，迭代次数少，收敛速度快，通用性强，比标准蚁群算法具有一定优势。于宏涛和高立群等人提出了一种新型的离散人工蜂群算法. 根据该优化问题及离散量的特点，对引领蜂、跟随蜂和侦查蜂角色转变机制和搜索策略进行了重新定义，蜂群角色转变基于定义的收益比因子，从而较好地平衡了算法的探索及开采能力，该算法实验结果能够在较短时间内找到相对满意解，提高了TSP 的求解效率 [5]。现有的蜂群算法解决TSP文献主要是针对通常节点分布特征的，对具有簇状分布特征的TSP没有专门的研究。现实应用中，一些图的节点的分布呈现出一定的特征，这些特征对解空间影响重大，文献 [6] 对此问题进行了探讨。簇状正是用于描述TSP的节点分布的特征，如果一个TSP问题的节点分布符合簇状特征，那么对应的解空间的范围将被压缩，这将对TSP问题的寻优过程中带来效率的提升，省去一些不必要的寻优过程，促进符合条件的TSP问题的进一步求解过程的优化，从而提升算法的效率。本文从具有节点簇状分布特征的TSP角度出发，利用ABC的改进算法进行相应的问题优化和求解。

2. ABC改进算法求解簇状TSP平台架构设计

为了描述TSP问题中节点的分布特征，可以利用域和密度的定义，它们从全局对节点的分布特征进行刻画。如果给定的域中密度达到一个特定值，那么给定的域中的节点就构成簇，相应区域总节点数和对应面积的比值就是密度 [6]。对于节点数目众多的TSP问题，节点分布可能存在着一个或多个簇，簇内外的节点寻优将采取不同的策略。TSP的数学描述如下：一个簇状特征的TSP问题的带权无向图用G = (V, E)来表示，其中 $V=\left\{v_1,v_2,\cdots ,v_n\right\}$ 是带有 $n=\left|V\right|$ 个节点的集合，E是完全连接这些点的边的集合。每一条边带有一条权值d(i, j)，d(i, j)表示节点i和节点j之间的距离。ABV算法的最终目标是如何找到图G中所有点的所有路径π中一个权重之和最小的路径，目标函数如式(1)所示：

$\min f\left(\pi \right)=d\left(v_{\pi (N)},v_{\pi (1)}\right)+{\displaystyle \underset{i=1}{\overset{n-1}{\sum }}d\left(v_{\pi (i)},v_{\pi (i+1)}\right)}$ (1)

ABC算法中有三种类型的蜜蜂：引领蜂、侦察蜂和跟随蜂。引领蜂储存着食物源的相关信息，并在采蜜后回到蜂巢中通过摇摆舞的形式传递蜜源的信息，其数量与食物源的数量相等。侦察蜂搜索蜂巢附近的新食物源；跟随蜂等在蜂巢里面并通过与引领蜂分享相关信息找到食物源 [7]。

ABC算法初始化阶段按(2)式随机初始化SN／2个D维的可行解 $x_i{\left(x_{i1},x_{i2},\cdots ,x_{iD}\right)}^{\text{T}}$，$\left(i=1,2,\cdots ,\text{SN}\right)$，SN代表了蜜蜂数量。

$x_{ij}=X_j^{lb}+rand\left(0,1\right)*\left(x_j^{ub}-x_j^{lb}\right)$ (2)

其中 $x_j^{ub}$ 其为搜索空间的上界， $x_j^{lb}$ 其为搜索空间的下界。

在簇状特征的TSP问题中，设图G中对应节点集为 $V=\left\{v_1,v_2,\cdots ,v_n\right\}$，对于每一节点 $v_i\left(i=1,2,\cdots ,n\right)$，对应的位置由 $v_i\left(x_i,y_i\right)$ 来表示， $x_i,y_i$ 分别表示平面上的横坐标和纵坐标。令 $x_{\max }=\max \left(x_1,\cdots ,x_n\right)$，$x_{\min }=\min \left(x_1,\cdots ,x_n\right)$，max()表示取 $x_1,\cdots ,x_n$ 中的最大值函数，min()表示取 $x_1,\cdots ,x_n$ 中的最小值函数，同理，令 $y_{\max }=\max \left(y_1,\cdots ,y_n\right)$，$y_{\min }=\min \left(y_1,\cdots ,y_n\right)$，则包含所有节点的最大域SD_max二维坐标可以表示如(3)式所示：

$S{D}_{\max }\left[O\left(\left(X_{\min }+X_{\max }\right)/2,Y_{\min }+Y_{\max }\right),r_{\max }\right]$ (3)

其中O为中心点， $r_{\max }=\max \left(\left(x_{\max }-x_{\min }\right)/2,\left(y_{\max }-y_{\min }\right)/2\right)$。

可以算出对应最大域的密度如公式(4)所示：

${\rho }_{\max }=n/sqrt\left(4r_{\max }^2\right)=n/2r_{\max }$ (4)

3. 扫描策略及簇状域判定

针对图G的规模，选择一整数记为r_c作为扫描域步进增量，令 $r_c=\mathrm{int}\left(r_{\max }/C\right)$，C表示步进系数，为一整数，int()表示取整函数。步进系数决定步进增量的大小，步进系数可以根据仿真实验的结果进行调整。扫描方式有如下两种情况：一是横向扫描，二是纵向扫描。下面主要介绍横向扫描的具体过程，纵向扫描的过程与此类似。

为简单起见，设节点分布图的最大域为：SD_max[O((0,0)), 100]，根据上节的内容，则初始的扫描域SD_s半径r_s = r_max/2 = 100/2 = 50。选择步进系数C = 10，则步进增量r_c = int(100/10) = 10。横向扫描开始时，将最大域左下角的顶点和扫描域左下角顶点重合，然后固定最大域，从水平方向向右每隔步进增量个单位移动扫描域，一直到最大域的右边和扫描域的右边重合，则第一行的扫描结束。接着开始第二行的扫描，第二行的左下角的顶点坐标为(0, r_c)即(0, 10)，将扫描域左下角顶点与此点重合，然后继续横向扫描，重复第一行扫描的过程，如图1所示，图中红色方框为扫描域在第一行第一次扫描时所处位置，蓝色方框为扫描域在第一行第二次扫描时扫描域所处的位置，绿色虚框为扫描域在第三行第一次扫描时扫描域所处的位置。可以推导出总共需要扫描的次数S_num如公式(5)所示：

$S_{num}={\left(\mathrm{int}\left(\left(2r_{\max }-2r_s\right)/r_c\right)+1\right)}^2$ (5)

图1. 扫描过程中的域和步进增量

在扫描域对最大域进行扫描的过程中，每次都将计算扫过位置的密度，扫描完成后，形成一系列密度值集 $r_1,r_2,\cdots ,r_{Snum}$。根据问题的特征，设定一个密度阈值 ${\rho }_{\text{th}}$，密度阈值的大小选择根据问题的规模和仿真实验的效果进行确定。如果 ${\rho }_i>={\rho }_{th}，i=1,2,\cdots ,S_{num}$，则认为该密度对应的域中的节点分布构成簇状特征，该域称为簇状域；否则，不构成簇状特征。如果一个图形，没有任何一个域出现簇状特征的情况，那么通过调整步进系数的大小，再重复上述扫描的过程，以确定是否出现构成簇状特征的扫描域。通过调整扫描系数的办法如果始终不能出现簇状域，那么可以通过减小扫描域的面积继续重复上述的扫描过程。如果在扫描过程中，出现一半以上的密度大于阈值的情况，则可以增大扫描域的面积，再重复上述过程进行扫描。扫描域面积具体的增加值，则依据新的密度值来确定，如果新的密度值集合中继续出现半数以上大于或等于密度阈值，则继续调整扫描域的面积，直到出现的密度值集合中半数以上的密度值低于密度阈值。

4. ABC改进算法流程

初始时刻，蜜蜂以侦查蜂的方式在随机的簇状域内搜索。其搜索可以由系统的先验知识决定，也可以完全随机。经过一轮侦查后，若蜜蜂找到食物源，蜜蜂利用它本身的存储能力记录位置信息并开始采蜜。此时，蜜蜂将称为“引领峰”。蜜蜂在食物源采蜜后回到蜂巢卸下蜂蜜，然后将有如下选择：一是放弃食物源而成为非雇佣蜂；二是跳摇摆舞为所对应的食物源招募更多的蜜蜂，然后回到食物源采蜜；三是继续在食物源采蜜而不进行招募。对于非雇佣蜂有如下两种选择方式：一是转变为侦查蜂并搜索蜂巢附近的食物源，其搜索可以由先验知识决定也可以完全随机；二是在观察完摇摆舞以后，被雇佣成为跟随蜂，开始搜索对应食物源领域并采蜜。每一个观察蜂依据概率选择一个蜜源，选择概率p_i如公式(6)所示：

$p_i=\frac{fi{t}_i}{{\displaystyle {\sum }_{j=1}^{SN}fi{t}_j}}$ (6)

其中， $fi{t}_i$ 中是可能解可行解 $x_i{\left(x_{i1},x_{i2},\cdots ,x_{iD}\right)}^T$ 的适应值，SN为蜜蜂的数量。

引领蜂搜索时将首先计算收益比，若收益比不都大于或等于设定值r，则引领蜂执行簇状域内的节点选择操作，然后继续按照公式(5)搜索新蜜源，并得到邻域解 ${X^{\prime }}_i$。引领蜂只能从位于标号最小的簇状域中的节点随机选取一点作为始发点，该始发点到可选节点的各条路径上的概率根据公式(6)来进行计算，并按照轮盘赌的方式选择下一节点。下一节点确定后，引领蜂在行进到下一节点的过程中获取一定的概率增量。在选择下一节点的过程中，引领蜂将会判断当前节点和下一节点是否都位于同一个簇状域内，这时将出现以下几种种情况：一是两节点都位于同一个簇状域内，引领蜂将对按照公式(6)计算出来的概率增加一概率增量，以表示当前簇状域内部的节点在下步路径选择中优先考虑，概率增量的值和密度值正相关。第二种情况是如果当前节点位于当前簇状域内，而下一节点没有位于当前簇状域内，引领蜂将搜索当前簇状域内是否还有未被选择节点，如果尚有未被选节点，则随机选择其中一尚未被选节点为下一节点，然后重复第一种情况的做法。第三种情况是如果当前节点位于当前簇状域内，而下一节点没有位于当前簇状域内部，引领蜂将搜索当前簇状域内是否还有未被选择节点，如果没有未被选节点，引领蜂将选择下一节点的概率按照公式(6)计算。

对于单独占据一个段落的公式，通常建议采用居中设置，并在段前、段后设置0.3行间隔。但该规则并不是强制性的，对于公式较多的论文，作者可以根据情况适当调整对其方式和段落间距，以求美观。

为求美观，应注意公式中的字体大小。字体过大会导致比例失调，字体过小会导致看不清楚。

5. 仿真结果分析

为了测试求解具有簇状特征的TSP的ABC算法的性能，下面结合ABC算法的具体构建过程，来对算法进行仿真测试和结果分析，在此过程中将同时进行AS (Ant System)、MMAS (Max-Min Ant System)、ABC和本文的ABC改进算法(ABC-P)仿真测试来比较分析，所有的仿真测试都是在一台具有16 G RAM系统主频为3.80 GHZ的Intel四核个人PC (联想启天M415)上进行的，上述四种算法的其他测试条件相同。仿真测试利用的节点数据分别是一个具有200个节点、呈现单簇特征的TSP问题以及一个具有600个节点、呈现五簇特征的多簇TSP问题，如图2和图3所示所示，图2和图3中横纵坐标单位都为标准单位。

图2. 200个节点的单簇图

在图2中，部分节点在图的中间呈现明显的簇状分布，根据图形的性质，可以设定密度阈值为0.13。在扫描过程中，可以获取系列密度值r_i =0.21，r₂ =0.23，r₃ =0.19，r₄ =0.22，r₅ =0.16。可以认为该图形具有簇状特征，按照公式(6)进行的概率选择下节点，最后对图2的仿真结果如图4所示。

图3. 600个节点的多簇图

图4. 200个节点的单簇图仿真结果

图5. 600个节点的多簇图仿真结果

在图3中，节点在图的五个区域中间呈现明显的簇状分布，根据图形的性质，可以设定密度阈值为0.16。在扫描过程中，可以获取系列密度值r_i = 0.23，r₂ = 0.25，r₃ = 0.20，r₄ = 0.24，r₅ = 0.19。可以认为该图形具有簇状特征，按照公式(6)进行的概率选择下节点，最后对图3的仿真结果如图5所示。

在图4和图5中，横坐标表示算法执行的循环次数，纵坐标为标准的距离单位。从图中可以看出，改进的ABC算法ABC-P较原来的算法在时间和收敛值上比较有明显的优势。从图中还可以看出，ABC-P相对于其他的仿生算法如AS、MMAS在综合性能上也有明显的优势。

6. 结论

对于节点呈现明显的簇状特征的TSP，在簇状区域内可以对蜂群的路径寻优行为进行适当的调整，从而达到优化路径的目的。本文利用密度和域对簇状特征进行了描述，并在此基础上对TSP的所有节点进行扫描，从而判断图形是否构成簇状特征图。针对簇状特征的TSP问题，对引领蜂、侦察蜂和跟随蜂的路径选择策略进行调整，从而达到优化最终解的目的。在实际的应用过程中，存在着密度阈值无法精确确定的缺点，同时在簇内核簇外节点之间的跳转时优化路径还有待改进，针对簇状特征不明显的图形算法的优势不够明显，这些问题有待后续进一步研究。

基金项目

本文受福建省自然科学基金项目(2019J01814)资助。

文章引用

林建兵,许忠福. 一种具备簇状特征的TSP问题的ABC改进解法
An ABC Solution of TSP with Cluster Feature[J]. 计算机科学与应用, 2021, 11(04): 1001-1007. https://doi.org/10.12677/CSA.2021.114103

参考文献