基于人工蜂群算法的p-center問題求解算法*

包敏澤，胡秀婷，謝玉瑩，蔣 波

(大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院，遼寧 大連 116026)

1 引言

近年來，p-center問題受到了人們的廣泛關(guān)注。所謂p-center問題，是指對給定的n個點(diǎn)，要求計(jì)算出p個圓，使得這些圓的并集能夠完全覆蓋所有給定的點(diǎn)，且使得最大圓的直徑達(dá)到最小[1]。p-center問題通常限定在平面上，因而也稱之為平面p-center問題，簡稱為p-center問題。p-center問題有2種類型：離散型和連續(xù)型。離散型p-center問題要求計(jì)算出的所有圓心均為給定點(diǎn)集中的點(diǎn)，而連續(xù)型p-center問題則沒有該約束，其圓心可在任意位置上。p-center問題不僅是一個理論問題，而且具有很大的實(shí)際應(yīng)用價值，其中最大距離最小化的位置分配問題就是一個典型實(shí)例，它要求根據(jù)給定的n個位置點(diǎn)，確定p個服務(wù)設(shè)施的位置，并最大限度地減少位置點(diǎn)與其最近服務(wù)設(shè)施間的距離。物流站點(diǎn)、城鎮(zhèn)規(guī)劃、通信基站的設(shè)計(jì)等，均可借助該問題的研究結(jié)果，找到高效合理的解決方案。

平面p-center問題是經(jīng)典的NP難題，求解該問題一般有2種思路：一是確定p的取值，然后在該取值下尋找盡可能高效的精確解；二是探索高效的啟發(fā)式求解策略。當(dāng)p值已知時，p-center問題可在O(n2p-1logn)時間內(nèi)得到解決[2]，且當(dāng)p=1時，存在時間復(fù)雜度為O(n)的求解算法[3]。對于p=2的2-center問題，Sharir[4]首先使用參數(shù)搜索范式設(shè)計(jì)出了時間復(fù)雜度為O(nlog9n)的近似線性時間的求解算法。后來，Eppstein[5]給出了一種預(yù)期時間復(fù)雜度為O(nlog2n)的隨機(jī)算法。Chan[6]優(yōu)化了該算法，在相同時間復(fù)雜度下給出了成功概率更高的隨機(jī)算法。同時，Chan也給出了時間復(fù)雜度為O(n(lognlog logn)2)的確定性算法。最近，Tan等人[7]給出了凸位置點(diǎn)集和任意點(diǎn)集2-center問題的新求解算法，其時間復(fù)雜度均為O(nlog2n)。以上這些成果都是圍繞連續(xù)型2-center問題給出的。對于離散型2-center問題，Agarwal等人[8]提出了一個時間復(fù)雜度為O(n4/3log5n)的求解算法。

針對人工蜂群算法中存在的局部最優(yōu)搜索能力不足等問題，人們從不同角度進(jìn)行了深入的研究，主要包括2個方面：一是改進(jìn)人工蜂群算法的搜索策略；二是通過將人工蜂群算法與其他啟發(fā)式算法結(jié)合以優(yōu)化算法性能[17]。例如，2015年，Ozturk等人[18]使用交叉互換操作處理了二進(jìn)制優(yōu)化問題；2018年，智慧[19]使用與全局最優(yōu)值做交叉的方式來提高算法的探索能力；2019年，肖曉等人[20]在使用交叉算子的同時還引入了高斯變異操作來改進(jìn)算法性能等。盡管人們選擇的交叉或變異的操作方式不同，但整體思路都是依據(jù)不同算子在相應(yīng)求解問題中的不同表現(xiàn)來提升算法性能。

本文提出的用于求解平面p-center問題的高效啟發(fā)式算法(BeeGenP)，也采用了人工蜂群算法和遺傳算法相結(jié)合的方式，設(shè)計(jì)了適合求解該問題的交叉和變異等操作，以改進(jìn)局部搜索策略，提高算法的搜索能力。同時，為了驗(yàn)證算法的有效性，構(gòu)造測試數(shù)據(jù)，并依據(jù)算法的運(yùn)行結(jié)果對比分析BeeGenP算法與M-ABC算法[15]的性能。

研究中，我們約定所有圓心從給定點(diǎn)集中選取，即研究對象是離散型p-center問題。

2 人工蜂群算法

人工蜂群算法是典型的仿生群體智能算法[14]。ABC算法包含3個基本要素：蜜源(Food Sources)、雇傭蜂(Employed Foragers)和非雇傭蜂(Unemployed Foragers)。其中，非雇傭蜂包括觀察蜂和偵察蜂。一個蜜源對應(yīng)于求解問題的一個可行解，可以通過適應(yīng)度值來衡量蜜源的質(zhì)量。雇傭蜂與蜜源一一對應(yīng)，且在蜜源附近做鄰域搜索，記錄相應(yīng)蜜源的信息，并將信息分享反饋給觀察蜂。觀察蜂依靠雇傭蜂所提供的信息挑選適應(yīng)度較好的蜜源，而偵察蜂則隨機(jī)選擇新蜜源。當(dāng)選擇好新蜜源后，則繼續(xù)各自的開采工作。

令SN表示蜜源個數(shù)，即解的個數(shù)，也是雇傭蜂和觀察蜂的個數(shù)。假設(shè)用xi表示第i個蜜源的初始解，則xi=(xi1,xi2,…,xiD)是一個D維向量，i=1,2,…,SN，D是問題的維數(shù)。ABC算法包含如下4個基本步驟：

(1) 在當(dāng)前解空間中隨機(jī)初始化種群，并計(jì)算解的適應(yīng)度值。

(2) 雇傭蜂搜索當(dāng)前蜜源的鄰域，每個雇傭蜂根據(jù)式(1)生成一個新的解，即新的蜜源位置并計(jì)算適應(yīng)度值，之后根據(jù)貪婪原則選擇適應(yīng)度值大的蜜源加以保留。

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

(1)

其中，φij是[-1,1]上均勻分布的隨機(jī)數(shù)，k∈{1,2,…,SN}和j∈{1,2,…,D}都是隨機(jī)選取的。雇傭蜂完成搜索后，將蜜源解信息分享給觀察蜂。

(3) 觀察蜂根據(jù)接收到的信息，通過式(2)的輪盤賭概率選擇一個蜜源，并在該蜜源附近通過式(1)做鄰域搜索以及通過貪婪原則選擇更好的蜜源。

(2)

其中，fiti是解的適應(yīng)度值，按式(3)進(jìn)行計(jì)算。

(3)

其中，fi是第i個解的目標(biāo)函數(shù)值。

(4) 若一個蜜源的解在進(jìn)行了預(yù)先設(shè)定的有限次探索后其適應(yīng)度值仍沒有提高，那么該蜜源就會被舍棄，且所對應(yīng)的雇傭蜂就會變成偵察蜂，并可通過式(4)隨機(jī)搜索新的蜜源。

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

(4)

其中，xij是新蜜源的第j維分量，rand是(0,1)上均勻分布的隨機(jī)數(shù)，Uj和Lj分別是第j維分量的上界和下界。

記錄當(dāng)前所有蜜蜂找到的最優(yōu)蜜源，即局部最優(yōu)解，并重復(fù)上述基本步驟，直到達(dá)到最大迭代次數(shù)或小于誤差允許的值，最后輸出全局最優(yōu)解。

為了克服ABC算法易陷入局部最優(yōu)的缺點(diǎn)，BeeGenP算法引入了GA中的交叉和變異算子。交叉算子每次選取2條染色體進(jìn)行操作，通過組合兩者的特性以產(chǎn)生新的子代染色體。一種簡單的交叉方式是在雙親染色體上隨機(jī)選取一個斷點(diǎn)，并將斷點(diǎn)右部的編碼互換，形成新的后代。適當(dāng)?shù)慕徊媛士傻玫捷^好的解空間，并且降低算法停止在局部最優(yōu)解上的概率。變異算子是讓染色體隨機(jī)發(fā)生變化。一種簡單的變異方式是對染色體上的一個或多個基因進(jìn)行替換，因此變異操作可產(chǎn)生初始種群不具備的基因，或者找到在選擇過程中丟失的基因。

BeeGenP算法的基本出發(fā)點(diǎn)是在人工蜂群算法的基礎(chǔ)上，利用交叉和變異操作改進(jìn)算法的局部搜索能力，以便有效地解決p-center問題。

3 BeeGenP算法的設(shè)計(jì)與實(shí)現(xiàn)

BeeGenP算法是結(jié)合ABC算法和GA算法所設(shè)計(jì)出的啟發(fā)式算法，用于求解離散型平面p-center問題。假設(shè)在平面上給定點(diǎn)集S和圓的個數(shù)p，希望輸出圓心位置與最大圓的半徑，其中S和p以參數(shù)形式任意給定。下面論述BeeGenP算法的設(shè)計(jì)細(xì)節(jié)，包括解的編碼方式、交叉算子與變異算子、局部搜索方式等，并給出BeeGenP算法的偽代碼及實(shí)驗(yàn)結(jié)果分析。

3.1 解的編碼方式及其初始化

不同的解編碼方式可能會導(dǎo)致不同的算子設(shè)計(jì)方式，本文選擇隨機(jī)鍵編碼方式。隨機(jī)鍵最早是在求解旅行商問題TSP(Traveling Salesman Problem)時被引入到GA算法中的。該方法通過一個隨機(jī)生成的浮點(diǎn)數(shù)向量來實(shí)現(xiàn)，使得向量的分量與問題求解點(diǎn)集中的點(diǎn)一一對應(yīng)。GA算法通過改變該浮點(diǎn)數(shù)向量來改變對應(yīng)點(diǎn)的相應(yīng)位置。本文使用n個m位二進(jìn)制數(shù)代替浮點(diǎn)數(shù)，其中n是給定點(diǎn)集中點(diǎn)的個數(shù)，2m-1

Table 1 An example of given point set and corresponding random keys of points表1 給定點(diǎn)集以及相應(yīng)點(diǎn)的隨機(jī)鍵示例

根據(jù)ABC算法的運(yùn)算要求，算法在開始迭代前需要隨機(jī)生成p個解來定義初始雇傭蜂。在隨機(jī)鍵編碼方式下，可通過選取最大或者最小的p個二進(jìn)制數(shù)所對應(yīng)的點(diǎn)作為初始圓心。如在表1的示例中，可選擇(4,5)，(21,4)，(7,3)為初始圓心。

3.2 交叉算子

交叉運(yùn)算用于提升ABC算法中采蜜蜂的局部搜索能力。交叉運(yùn)算不僅可以使當(dāng)前解盡可能保留前幾輪較優(yōu)解的良好組合，而且還能使算法具有更強(qiáng)的探索最優(yōu)值的能力。在算法執(zhí)行過程中，采蜜蜂以一定概率通過交叉算子來生成新的解。實(shí)驗(yàn)表明，若交叉率過高，則容易導(dǎo)致解早熟；若交叉率較低，則會導(dǎo)致搜索效率降低。一般而言，交叉率設(shè)置在45%～55%左右。通過本文算法的交叉算子生成新解時，算法會根據(jù)式(2)的輪盤賭方式從歷史最優(yōu)解中選取某個解，并與采蜜蜂當(dāng)前所在的蜜源解做交叉運(yùn)算，以得到新的解。傳統(tǒng)的交叉運(yùn)算是任意選取3個隨機(jī)整數(shù)，并以這3個數(shù)為斷點(diǎn)，將運(yùn)算雙方的解分成4段，然后交換其中的幾段以生成新的解。本文算法的交叉運(yùn)算則有所不同，即隨機(jī)選取運(yùn)算對象雙方解的部分元素并組合成新的解。如圖1所示，F(xiàn)ather和Mother分別表示需要做交叉運(yùn)算的2個對象，其中Fi(1≤i≤p)和Mi(1≤i≤p)均是m位的二進(jìn)制數(shù)；Son表示交叉運(yùn)算后得到的子代新解。

Figure 1 A diagram of cross operation圖1 交叉運(yùn)算示意圖

3.3 變異算子

隨著算法的推進(jìn)，得到的當(dāng)前最優(yōu)解會出現(xiàn)趨于單一化趨勢，容易造成算法過早地收斂于一個局部最優(yōu)解，因而影響了全局最優(yōu)解的產(chǎn)生。變異算子用于增加解搜索空間的多樣性。BeeGenP算法使用了2種變異算子，分別記為X和Y。其中，X將隨機(jī)選擇當(dāng)前解中的一個編碼元素并將其刪除，然后隨機(jī)選取一個未在當(dāng)前解中出現(xiàn)的點(diǎn)，并將對應(yīng)的編碼添加到當(dāng)前解中，產(chǎn)生一個新解；Y則在當(dāng)前解中隨機(jī)選取一個點(diǎn)p1及其相鄰的點(diǎn)p2，根據(jù)式(5)生成點(diǎn)p3。生成點(diǎn)p3后，其對應(yīng)的編碼會隨機(jī)替換點(diǎn)p1或點(diǎn)p2所對應(yīng)的編碼，產(chǎn)生一個新的解。

p3=min(p1,p2)+

(5)

對需要做變異運(yùn)算的解，可任選X或Y做運(yùn)算，計(jì)算新解的適應(yīng)度值并加以判別。

3.4 算法實(shí)現(xiàn)

BeeGenP算法采用ABC算法的主框架完成基本的迭代過程，該過程包括初始化蜂群、觀察蜂選擇蜜源以及偵察蜂搜索新蜜源的規(guī)則、解的選擇方式、何時舍棄當(dāng)前蜜源與如何判斷算法是否結(jié)束等操作。但是，在采蜜蜂對解的局部搜索過程中，BeeGenP算法將按照一定概率，有的放矢地對當(dāng)前解做交叉或變異運(yùn)算，以獲得新的局部解。BeeGenP算法的主要步驟如下所示：

(1) 初始化各類參數(shù)，包括蜜蜂的種群數(shù)量，算法迭代次數(shù)的上限，一個蜜源的最大探索次數(shù)，以及交叉和變異運(yùn)算的發(fā)生概率等。

(2) 初始化蜂群隊(duì)列bee_queue、記錄歷史局部最優(yōu)解的隊(duì)列his_best、記錄當(dāng)前可探索蜜源的隊(duì)列flower_queue以及步數(shù)計(jì)數(shù)器iter。

(3) 步數(shù)計(jì)數(shù)器增加1，判斷是否達(dá)到最大迭代次數(shù)，若達(dá)到最大迭代數(shù)，則進(jìn)行步驟(6)；否則進(jìn)行步驟(4)。

(4) 將當(dāng)前flower_queue中較優(yōu)的解，加入到his_best中。遍歷bee_queue中的成員，做交叉運(yùn)算或變異運(yùn)算以獲得局部的新解。若新解適應(yīng)度值優(yōu)于舊解，則用新解替換舊解；否則，舍棄新解，并將蜜源的搜索次數(shù)增加1。將bee_queue中適應(yīng)度值最好的解加入到his_best中，并舍棄已達(dá)到最大搜索次數(shù)的蜜源。被舍棄蜜源上的蜜蜂，若轉(zhuǎn)換為觀察蜂，則根據(jù)輪盤賭的方式，在當(dāng)前flower_queue中選擇一個蜜源；若轉(zhuǎn)換為偵察蜂，則根據(jù)規(guī)則生成新的解。

(5) 根據(jù)bee_queue中蜜蜂所擁有的蜜源，更新flower_queue中的元素，轉(zhuǎn)到步驟(3)。

(6) 輸出his_best的最優(yōu)解，算法結(jié)束。

BeeGenP算法的偽代碼如下所示：

算法BeeGenP

Input:平面點(diǎn)集S和待求解的中心點(diǎn)數(shù)p。

Output:點(diǎn)集S的p-center解。

步驟1初始化各類參數(shù)，包括最大迭代次數(shù)CycMax，蜜源的最大探索次數(shù)Limit，蜂群數(shù)量N，交叉算子執(zhí)行的概率cp；

步驟2sizeS←S包含元素的個數(shù)；

步驟3初始化隊(duì)列bee_queue，his_best，flower_queue；

步驟4 while(bee_queue的長度小于N){

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

步驟6對flower_queue中的初始解按適應(yīng)度值排序，保留適應(yīng)度值高的N/2個雇傭蜂，并將flower_queue中適應(yīng)度值最好的解加入his_best中；

步驟7根據(jù)flower_queue中的適應(yīng)度值和輪盤賭概率，讓觀察蜂選擇蜜源，并加入bee_queue中；

步驟8iter←0；

步驟9 while(iter

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

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

步驟12if(random(0,1)

步驟13根據(jù)輪盤賭的規(guī)則在his_best中選取運(yùn)算對象fa；

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

步驟15elseson←Variation(bee_queue[i])；//需要執(zhí)行變異操作

步驟16if(son的適應(yīng)度優(yōu)于bee_queue[i]的適應(yīng)度值){

步驟17bee_queue[i]=son；}

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

步驟19將bee_quene當(dāng)前解中適應(yīng)度值最好的解加入隊(duì)列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轉(zhuǎn)換為偵察蜂選擇蜜源，并加入bee_queue[i]；}}

步驟28iter+= 1；}

步驟29returnhis_best中適應(yīng)度值最優(yōu)的解

3.5 實(shí)驗(yàn)結(jié)果分析

針對無約束p-center問題，盡管M-ABC算法的性能優(yōu)于其它啟發(fā)式算法，但仍然存在一些缺陷。本文通過隨機(jī)生成的測試數(shù)據(jù)(共生成了50組樣例)，分別測試了BeeGenP算法和M-ABC算法，實(shí)驗(yàn)結(jié)果如表2和表3所示。其中，n是給定點(diǎn)集中點(diǎn)的數(shù)量。

Table 2 Comparison of the optimal solutions between BeeGenP and M-ABC表2 BeeGenP與M-ABC算法的最優(yōu)解

Table 3 Comparison of the iterations between BeeGenP and M-ABC表3 BeeGenP與M-ABC的迭代次數(shù)

表2是確定最大迭代次數(shù)為1 000時2個算法所得到的最優(yōu)解；表3則記錄了當(dāng)趨近收斂于最優(yōu)解時，2個算法的迭代次數(shù)。

由表2可看出，對于隨機(jī)生成的由任意n個點(diǎn)構(gòu)成的點(diǎn)集，BeeGenP算法得到的p-center解中最大圓的半徑普遍小于M-ABC算法的對應(yīng)結(jié)果，這說明BeeGenP算法更有效，它比M-ABC算法具有更強(qiáng)的局部搜索能力。同時，通過表3也可看出，當(dāng)2個算法趨近收斂于最優(yōu)解時，BeeGenP算法所需要的迭代次數(shù)普遍小于M-ABC算法的迭代次數(shù)。

4 結(jié)束語

針對離散型平面p-center問題，在人工蜂群算法的基礎(chǔ)上，通過改進(jìn)局部解的搜索策略，本文提出了新的BeeGenP啟發(fā)式算法。BeeGenP算法采用遺傳算法中的交叉與變異操作產(chǎn)生新的子代解，以此增強(qiáng)算法的搜索能力，并使搜索空間具有多樣性。實(shí)驗(yàn)結(jié)果表明，對于隨機(jī)生成的點(diǎn)集和參數(shù)p，BeeGenP算法所求出的最大圓的半徑普遍小于M-ABC算法的對應(yīng)結(jié)果，且當(dāng)算法趨近收斂于最優(yōu)解時，BeeGenP算法的迭代次數(shù)要小于M-ABC算法的迭代次數(shù)，改進(jìn)算法要快于M-ABC算法獲得相應(yīng)的最優(yōu)解。BeeGenP算法不僅具有更強(qiáng)的局部搜索能力，而且也更加高效。

與所有啟發(fā)式算法一樣，由于p-center問題中求解最大圓半徑時需要遍歷整個點(diǎn)集，故是一個十分耗時的運(yùn)算。BeeGenP算法的迭代計(jì)算也很耗時，尤其是當(dāng)點(diǎn)集規(guī)模和參數(shù)p較大時，運(yùn)算將更加耗時。一個可行的改進(jìn)方法是首先采用聚類方法，將給定點(diǎn)集劃分為若干個子集，并將最大圓半徑的搜索問題局限在某子集范圍內(nèi)，以此減少計(jì)算時間。如何融合聚類算法，并在保障解質(zhì)量的前提下降低算法的耗時，是值得進(jìn)一步研究的課題。