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

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

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

1 引言

近年來，p-center問題受到了人們的廣泛關(guān)注。所謂p-center問題，是指對給定的n個點，要求計算出p個圓，使得這些圓的并集能夠完全覆蓋所有給定的點，且使得最大圓的直徑達到最小[1]。p-center問題通常限定在平面上，因而也稱之為平面p-center問題，簡稱為p-center問題。p-center問題有2種類型：離散型和連續(xù)型。離散型p-center問題要求計算出的所有圓心均為給定點集中的點，而連續(xù)型p-center問題則沒有該約束，其圓心可在任意位置上。p-center問題不僅是一個理論問題，而且具有很大的實際應(yīng)用價值，其中最大距離最小化的位置分配問題就是一個典型實例，它要求根據(jù)給定的n個位置點，確定p個服務(wù)設(shè)施的位置，并最大限度地減少位置點與其最近服務(wù)設(shè)施間的距離。物流站點、城鎮(zhèn)規(guī)劃、通信基站的設(shè)計等，均可借助該問題的研究結(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è)計出了時間復(fù)雜度為O(nlog9n)的近似線性時間的求解算法。后來，Eppstein[5]給出了一種預(yù)期時間復(fù)雜度為O(nlog2n)的隨機算法。Chan[6]優(yōu)化了該算法，在相同時間復(fù)雜度下給出了成功概率更高的隨機算法。同時，Chan也給出了時間復(fù)雜度為O(n(lognlog logn)2)的確定性算法。最近，Tan等人[7]給出了凸位置點集和任意點集2-center問題的新求解算法，其時間復(fù)雜度均為O(nlog2n)。以上這些成果都是圍繞連續(xù)型2-center問題給出的。對于離散型2-center問題，Agarwal等人[8]提出了一個時間復(fù)雜度為O(n4/3log5n)的求解算法。

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

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

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

2 人工蜂群算法

人工蜂群算法是典型的仿生群體智能算法[14]。ABC算法包含3個基本要素：蜜源(Food Sources)、雇傭蜂(Employed Foragers)和非雇傭蜂(Unemployed Foragers)。其中，非雇傭蜂包括觀察蜂和偵察蜂。一個蜜源對應(yīng)于求解問題的一個可行解，可以通過適應(yīng)度值來衡量蜜源的質(zhì)量。雇傭蜂與蜜源一一對應(yīng)，且在蜜源附近做鄰域搜索，記錄相應(yīng)蜜源的信息，并將信息分享反饋給觀察蜂。觀察蜂依靠雇傭蜂所提供的信息挑選適應(yīng)度較好的蜜源，而偵察蜂則隨機選擇新蜜源。當(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)前解空間中隨機初始化種群，并計算解的適應(yīng)度值。

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

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

(1)

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

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

(2)

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

(3)

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

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

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

(4)

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

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

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

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

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

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

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

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

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

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

3.2 交叉算子

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

Figure 1 A diagram of cross operation圖1 交叉運算示意圖

3.3 變異算子

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

p3=min(p1,p2)+

(5)

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

3.4 算法實現(xiàn)

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

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

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

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

(4) 將當(dāng)前flower_queue中較優(yōu)的解，加入到his_best中。遍歷bee_queue中的成員，做交叉運算或變異運算以獲得局部的新解。若新解適應(yīng)度值優(yōu)于舊解，則用新解替換舊解；否則，舍棄新解，并將蜜源的搜索次數(shù)增加1。將bee_queue中適應(yīng)度值最好的解加入到his_best中，并舍棄已達到最大搜索次數(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:平面點集S和待求解的中心點數(shù)p。

Output:點集S的p-center解。

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

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

步驟3初始化隊列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中選取運算對象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)度值最好的解加入隊列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 實驗結(jié)果分析

針對無約束p-center問題，盡管M-ABC算法的性能優(yōu)于其它啟發(fā)式算法，但仍然存在一些缺陷。本文通過隨機生成的測試數(shù)據(jù)(共生成了50組樣例)，分別測試了BeeGenP算法和M-ABC算法，實驗結(jié)果如表2和表3所示。其中，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可看出，對于隨機生成的由任意n個點構(gòu)成的點集，BeeGenP算法得到的p-center解中最大圓的半徑普遍小于M-ABC算法的對應(yīng)結(jié)果，這說明BeeGenP算法更有效，它比M-ABC算法具有更強的局部搜索能力。同時，通過表3也可看出，當(dāng)2個算法趨近收斂于最優(yōu)解時，BeeGenP算法所需要的迭代次數(shù)普遍小于M-ABC算法的迭代次數(shù)。

4 結(jié)束語

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

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