基于人工蜂群算法的p-center问题求解算法*

包敏泽，胡秀婷，谢玉莹，蒋 波

(大连海事大学信息科学技术学院，辽宁 大连 116026)

1 引言

近年来，p-center问题受到了人们的广泛关注。所谓p-center问题，是指对给定的n个点，要求计算出p个圆，使得这些圆的并集能够完全覆盖所有给定的点，且使得最大圆的直径达到最小[1]。p-center问题通常限定在平面上，因而也称之为平面p-center问题，简称为p-center问题。p-center问题有2种类型：离散型和连续型。离散型p-center问题要求计算出的所有圆心均为给定点集中的点，而连续型p-center问题则没有该约束，其圆心可在任意位置上。p-center问题不仅是一个理论问题，而且具有很大的实际应用价值，其中最大距离最小化的位置分配问题就是一个典型实例，它要求根据给定的n个位置点，确定p个服务设施的位置，并最大限度地减少位置点与其最近服务设施间的距离。物流站点、城镇规划、通信基站的设计等，均可借助该问题的研究结果，找到高效合理的解决方案。

平面p-center问题是经典的NP难题，求解该问题一般有2种思路：一是确定p的取值，然后在该取值下寻找尽可能高效的精确解；二是探索高效的启发式求解策略。当p值已知时，p-center问题可在O(n2p-1logn)时间内得到解决[2]，且当p=1时，存在时间复杂度为O(n)的求解算法[3]。对于p=2的2-center问题，Sharir[4]首先使用参数搜索范式设计出了时间复杂度为O(nlog9n)的近似线性时间的求解算法。后来，Eppstein[5]给出了一种预期时间复杂度为O(nlog2n)的随机算法。Chan[6]优化了该算法，在相同时间复杂度下给出了成功概率更高的随机算法。同时，Chan也给出了时间复杂度为O(n(lognlog logn)2)的确定性算法。最近，Tan等人[7]给出了凸位置点集和任意点集2-center问题的新求解算法，其时间复杂度均为O(nlog2n)。以上这些成果都是围绕连续型2-center问题给出的。对于离散型2-center问题，Agarwal等人[8]提出了一个时间复杂度为O(n4/3log5n)的求解算法。

针对人工蜂群算法中存在的局部最优搜索能力不足等问题，人们从不同角度进行了深入的研究，主要包括2个方面：一是改进人工蜂群算法的搜索策略；二是通过将人工蜂群算法与其他启发式算法结合以优化算法性能[17]。例如，2015年，Ozturk等人[18]使用交叉互换操作处理了二进制优化问题；2018年，智慧[19]使用与全局最优值做交叉的方式来提高算法的探索能力；2019年，肖晓等人[20]在使用交叉算子的同时还引入了高斯变异操作来改进算法性能等。尽管人们选择的交叉或变异的操作方式不同，但整体思路都是依据不同算子在相应求解问题中的不同表现来提升算法性能。

本文提出的用于求解平面p-center问题的高效启发式算法(BeeGenP)，也采用了人工蜂群算法和遗传算法相结合的方式，设计了适合求解该问题的交叉和变异等操作，以改进局部搜索策略，提高算法的搜索能力。同时，为了验证算法的有效性，构造测试数据，并依据算法的运行结果对比分析BeeGenP算法与M-ABC算法[15]的性能。

研究中，我们约定所有圆心从给定点集中选取，即研究对象是离散型p-center问题。

2 人工蜂群算法

人工蜂群算法是典型的仿生群体智能算法[14]。ABC算法包含3个基本要素：蜜源(Food Sources)、雇佣蜂(Employed Foragers)和非雇佣蜂(Unemployed Foragers)。其中，非雇佣蜂包括观察蜂和侦察蜂。一个蜜源对应于求解问题的一个可行解，可以通过适应度值来衡量蜜源的质量。雇佣蜂与蜜源一一对应，且在蜜源附近做邻域搜索，记录相应蜜源的信息，并将信息分享反馈给观察蜂。观察蜂依靠雇佣蜂所提供的信息挑选适应度较好的蜜源，而侦察蜂则随机选择新蜜源。当选择好新蜜源后，则继续各自的开采工作。

令SN表示蜜源个数，即解的个数，也是雇佣蜂和观察蜂的个数。假设用xi表示第i个蜜源的初始解，则xi=(xi1,xi2,…,xiD)是一个D维向量，i=1,2,…,SN，D是问题的维数。ABC算法包含如下4个基本步骤：

(1) 在当前解空间中随机初始化种群，并计算解的适应度值。

(2) 雇佣蜂搜索当前蜜源的邻域，每个雇佣蜂根据式(1)生成一个新的解，即新的蜜源位置并计算适应度值，之后根据贪婪原则选择适应度值大的蜜源加以保留。

vij=xij+φij(xij-xkj),k≠i

(1)

其中，φij是[-1,1]上均匀分布的随机数，k∈{1,2,…,SN}和j∈{1,2,…,D}都是随机选取的。雇佣蜂完成搜索后，将蜜源解信息分享给观察蜂。

(3) 观察蜂根据接收到的信息，通过式(2)的轮盘赌概率选择一个蜜源，并在该蜜源附近通过式(1)做邻域搜索以及通过贪婪原则选择更好的蜜源。

(2)

其中，fiti是解的适应度值，按式(3)进行计算。

(3)

其中，fi是第i个解的目标函数值。

(4) 若一个蜜源的解在进行了预先设定的有限次探索后其适应度值仍没有提高，那么该蜜源就会被舍弃，且所对应的雇佣蜂就会变成侦察蜂，并可通过式(4)随机搜索新的蜜源。

xij=Lj+rand(0,1)(Uj-Lj)

(4)

其中，xij是新蜜源的第j维分量，rand是(0,1)上均匀分布的随机数，Uj和Lj分别是第j维分量的上界和下界。

记录当前所有蜜蜂找到的最优蜜源，即局部最优解，并重复上述基本步骤，直到达到最大迭代次数或小于误差允许的值，最后输出全局最优解。

为了克服ABC算法易陷入局部最优的缺点，BeeGenP算法引入了GA中的交叉和变异算子。交叉算子每次选取2条染色体进行操作，通过组合两者的特性以产生新的子代染色体。一种简单的交叉方式是在双亲染色体上随机选取一个断点，并将断点右部的编码互换，形成新的后代。适当的交叉率可得到较好的解空间，并且降低算法停止在局部最优解上的概率。变异算子是让染色体随机发生变化。一种简单的变异方式是对染色体上的一个或多个基因进行替换，因此变异操作可产生初始种群不具备的基因，或者找到在选择过程中丢失的基因。

BeeGenP算法的基本出发点是在人工蜂群算法的基础上，利用交叉和变异操作改进算法的局部搜索能力，以便有效地解决p-center问题。

3 BeeGenP算法的设计与实现

BeeGenP算法是结合ABC算法和GA算法所设计出的启发式算法，用于求解离散型平面p-center问题。假设在平面上给定点集S和圆的个数p，希望输出圆心位置与最大圆的半径，其中S和p以参数形式任意给定。下面论述BeeGenP算法的设计细节，包括解的编码方式、交叉算子与变异算子、局部搜索方式等，并给出BeeGenP算法的伪代码及实验结果分析。

3.1 解的编码方式及其初始化

不同的解编码方式可能会导致不同的算子设计方式，本文选择随机键编码方式。随机键最早是在求解旅行商问题TSP(Traveling Salesman Problem)时被引入到GA算法中的。该方法通过一个随机生成的浮点数向量来实现，使得向量的分量与问题求解点集中的点一一对应。GA算法通过改变该浮点数向量来改变对应点的相应位置。本文使用n个m位二进制数代替浮点数，其中n是给定点集中点的个数，2m-1

Table 1 An example of given point set and corresponding random keys of points表1 给定点集以及相应点的随机键示例

根据ABC算法的运算要求，算法在开始迭代前需要随机生成p个解来定义初始雇佣蜂。在随机键编码方式下，可通过选取最大或者最小的p个二进制数所对应的点作为初始圆心。如在表1的示例中，可选择(4,5)，(21,4)，(7,3)为初始圆心。

3.2 交叉算子

交叉运算用于提升ABC算法中采蜜蜂的局部搜索能力。交叉运算不仅可以使当前解尽可能保留前几轮较优解的良好组合，而且还能使算法具有更强的探索最优值的能力。在算法执行过程中，采蜜蜂以一定概率通过交叉算子来生成新的解。实验表明，若交叉率过高，则容易导致解早熟；若交叉率较低，则会导致搜索效率降低。一般而言，交叉率设置在45%～55%左右。通过本文算法的交叉算子生成新解时，算法会根据式(2)的轮盘赌方式从历史最优解中选取某个解，并与采蜜蜂当前所在的蜜源解做交叉运算，以得到新的解。传统的交叉运算是任意选取3个随机整数，并以这3个数为断点，将运算双方的解分成4段，然后交换其中的几段以生成新的解。本文算法的交叉运算则有所不同，即随机选取运算对象双方解的部分元素并组合成新的解。如图1所示，Father和Mother分别表示需要做交叉运算的2个对象，其中Fi(1≤i≤p)和Mi(1≤i≤p)均是m位的二进制数；Son表示交叉运算后得到的子代新解。

Figure 1 A diagram of cross operation图1 交叉运算示意图

3.3 变异算子

随着算法的推进，得到的当前最优解会出现趋于单一化趋势，容易造成算法过早地收敛于一个局部最优解，因而影响了全局最优解的产生。变异算子用于增加解搜索空间的多样性。BeeGenP算法使用了2种变异算子，分别记为X和Y。其中，X将随机选择当前解中的一个编码元素并将其删除，然后随机选取一个未在当前解中出现的点，并将对应的编码添加到当前解中，产生一个新解；Y则在当前解中随机选取一个点p1及其相邻的点p2，根据式(5)生成点p3。生成点p3后，其对应的编码会随机替换点p1或点p2所对应的编码，产生一个新的解。

p3=min(p1,p2)+

(5)

对需要做变异运算的解，可任选X或Y做运算，计算新解的适应度值并加以判别。

3.4 算法实现

BeeGenP算法采用ABC算法的主框架完成基本的迭代过程，该过程包括初始化蜂群、观察蜂选择蜜源以及侦察蜂搜索新蜜源的规则、解的选择方式、何时舍弃当前蜜源与如何判断算法是否结束等操作。但是，在采蜜蜂对解的局部搜索过程中，BeeGenP算法将按照一定概率，有的放矢地对当前解做交叉或变异运算，以获得新的局部解。BeeGenP算法的主要步骤如下所示：

(1) 初始化各类参数，包括蜜蜂的种群数量，算法迭代次数的上限，一个蜜源的最大探索次数，以及交叉和变异运算的发生概率等。

(2) 初始化蜂群队列bee_queue、记录历史局部最优解的队列his_best、记录当前可探索蜜源的队列flower_queue以及步数计数器iter。

(3) 步数计数器增加1，判断是否达到最大迭代次数，若达到最大迭代数，则进行步骤(6)；否则进行步骤(4)。

(4) 将当前flower_queue中较优的解，加入到his_best中。遍历bee_queue中的成员，做交叉运算或变异运算以获得局部的新解。若新解适应度值优于旧解，则用新解替换旧解；否则，舍弃新解，并将蜜源的搜索次数增加1。将bee_queue中适应度值最好的解加入到his_best中，并舍弃已达到最大搜索次数的蜜源。被舍弃蜜源上的蜜蜂，若转换为观察蜂，则根据轮盘赌的方式，在当前flower_queue中选择一个蜜源；若转换为侦察蜂，则根据规则生成新的解。

(5) 根据bee_queue中蜜蜂所拥有的蜜源，更新flower_queue中的元素，转到步骤(3)。

(6) 输出his_best的最优解，算法结束。

BeeGenP算法的伪代码如下所示：

算法BeeGenP

Input:平面点集S和待求解的中心点数p。

Output:点集S的p-center解。

步骤1初始化各类参数，包括最大迭代次数CycMax，蜜源的最大探索次数Limit，蜂群数量N，交叉算子执行的概率cp；

步骤2sizeS←S包含元素的个数；

步骤3初始化队列bee_queue，his_best，flower_queue；

步骤4 while(bee_queue的长度小于N){

步骤5add(flower_queue,CreateAns(p,sizeS))； }//生成初始解

步骤6对flower_queue中的初始解按适应度值排序，保留适应度值高的N/2个雇佣蜂，并将flower_queue中适应度值最好的解加入his_best中；

步骤7根据flower_queue中的适应度值和轮盘赌概率，让观察蜂选择蜜源，并加入bee_queue中；

步骤8iter←0；

步骤9 while(iter

步骤10for(i←0toN-1){

步骤11if(bee_queue[i]!= null ){

步骤12if(random(0,1)

步骤13根据轮盘赌的规则在his_best中选取运算对象fa；

步骤14son←CrossOver(fa,bee_queue[i],p)；}

步骤15elseson←Variation(bee_queue[i])；//需要执行变异操作

步骤16if(son的适应度优于bee_queue[i]的适应度值){

步骤17bee_queue[i]=son；}

步骤18elsebee_queue[i].tail+= 1；}}

步骤19将bee_quene当前解中适应度值最好的解加入队列his_best中；

步骤20for(i←0toN-1)；

步骤21if(bee_queue[i].tail>Limit){

步骤22bee_queue[i] = null；}}

步骤23将flower_queue清空；

步骤24将bee_queue中非null的元素添加到flower_queue中；

步骤25for(i←0toN-1){

步骤26if(bee_queue[i] = null ){

步骤27转换为侦察蜂选择蜜源，并加入bee_queue[i]；}}

步骤28iter+= 1；}

步骤29returnhis_best中适应度值最优的解

3.5 实验结果分析

针对无约束p-center问题，尽管M-ABC算法的性能优于其它启发式算法，但仍然存在一些缺陷。本文通过随机生成的测试数据(共生成了50组样例)，分别测试了BeeGenP算法和M-ABC算法，实验结果如表2和表3所示。其中，n是给定点集中点的数量。

Table 2 Comparison of the optimal solutions between BeeGenP and M-ABC表2 BeeGenP与M-ABC算法的最优解

Table 3 Comparison of the iterations between BeeGenP and M-ABC表3 BeeGenP与M-ABC的迭代次数

表2是确定最大迭代次数为1 000时2个算法所得到的最优解；表3则记录了当趋近收敛于最优解时，2个算法的迭代次数。

由表2可看出，对于随机生成的由任意n个点构成的点集，BeeGenP算法得到的p-center解中最大圆的半径普遍小于M-ABC算法的对应结果，这说明BeeGenP算法更有效，它比M-ABC算法具有更强的局部搜索能力。同时，通过表3也可看出，当2个算法趋近收敛于最优解时，BeeGenP算法所需要的迭代次数普遍小于M-ABC算法的迭代次数。

4 结束语

针对离散型平面p-center问题，在人工蜂群算法的基础上，通过改进局部解的搜索策略，本文提出了新的BeeGenP启发式算法。BeeGenP算法采用遗传算法中的交叉与变异操作产生新的子代解，以此增强算法的搜索能力，并使搜索空间具有多样性。实验结果表明，对于随机生成的点集和参数p，BeeGenP算法所求出的最大圆的半径普遍小于M-ABC算法的对应结果，且当算法趋近收敛于最优解时，BeeGenP算法的迭代次数要小于M-ABC算法的迭代次数，改进算法要快于M-ABC算法获得相应的最优解。BeeGenP算法不仅具有更强的局部搜索能力，而且也更加高效。

与所有启发式算法一样，由于p-center问题中求解最大圆半径时需要遍历整个点集，故是一个十分耗时的运算。BeeGenP算法的迭代计算也很耗时，尤其是当点集规模和参数p较大时，运算将更加耗时。一个可行的改进方法是首先采用聚类方法，将给定点集划分为若干个子集，并将最大圆半径的搜索问题局限在某子集范围内，以此减少计算时间。如何融合聚类算法，并在保障解质量的前提下降低算法的耗时，是值得进一步研究的课题。