一種應(yīng)用于函數(shù)優(yōu)化問(wèn)題的多種群人工蜂群算法

王守娜， 劉 弘， 高開周

(1.山東師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 濟(jì)南 250014； 2.山東師范大學(xué) 山東省分布式計(jì)算機(jī)軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室，山東 濟(jì)南 250358； 3.南洋理工大學(xué) 海事研究所，新加坡 639798)

0 引言

群體智能(swarm intelligence，SI)算法來(lái)源于自然界生物的覓食行為或進(jìn)化過(guò)程的模擬，是一類新型的進(jìn)化算法，主要特點(diǎn)是群體搜索策略和群體之間的信息交換.典型的群體智能算法包括蟻群優(yōu)化算法(ant colony optimization，ACO)[1]、粒子群優(yōu)化算法(particle swarm optimization，PSO)[2]和人工蜂群算法(artificial bee colony，ABC)[3]等.蟻群算法在求解性能上有很強(qiáng)的魯棒性，但算法收斂速度慢，容易陷入局部最優(yōu)，一般需要較長(zhǎng)的搜索時(shí)間，而且該算法容易出現(xiàn)停滯現(xiàn)象，不利于發(fā)現(xiàn)更好的解.粒子群算法具有相當(dāng)快的逼近最優(yōu)解的速度，其個(gè)體可以充分利用自身經(jīng)驗(yàn)調(diào)整自身狀態(tài)，缺點(diǎn)是容易產(chǎn)生早熟收斂，局部尋優(yōu)能力較差.

人工蜂群算法(artificial bee colony，ABC)是D.Karaboga[4]在2005年將蜜蜂的覓食行為應(yīng)用到函數(shù)優(yōu)化問(wèn)題中而提出的，該算法計(jì)算簡(jiǎn)單、便于實(shí)現(xiàn)、魯棒性強(qiáng)，在復(fù)雜組合優(yōu)化問(wèn)題中有明顯的優(yōu)勢(shì)[5]，目前已經(jīng)成功應(yīng)用到模糊聚類[6]、人工神經(jīng)網(wǎng)絡(luò)[7]、傳感器網(wǎng)絡(luò)[8]等多個(gè)領(lǐng)域中.與其他群體智能算法一樣，ABC算法也存在收斂速度慢、易陷入局部最優(yōu)解等問(wèn)題[9].針對(duì)以上問(wèn)題，已有學(xué)者提出了相應(yīng)的改進(jìn)算法，這些改進(jìn)算法在一定程度上提高了算法的收斂速度、尋優(yōu)精度，改善了算法的性能，但是很難實(shí)現(xiàn)在避免算法早熟收斂的同時(shí)加快算法的收斂速度.目前，大多數(shù)關(guān)于ABC算法的改進(jìn)都是基于單一種群模型，沒(méi)有考慮算法在基于多種群模型改進(jìn)時(shí)相較于原始算法的優(yōu)勢(shì).

聚類(clustering)[10]是把所有數(shù)據(jù)對(duì)象劃分到若干個(gè)子集的過(guò)程，每個(gè)子集是一個(gè)簇(cluster)，主要指導(dǎo)思想是盡量使相同簇內(nèi)對(duì)象具有最大相似度.在眾多聚類方法中，K均值算法[11]是一種非常重要的聚類算法，主要思想是依據(jù)參數(shù)k將給定數(shù)據(jù)集劃分成k個(gè)簇，從而讓各聚類中心的數(shù)據(jù)對(duì)象到其對(duì)應(yīng)的中心點(diǎn)的距離平方和最小，該算法原理簡(jiǎn)單、易于實(shí)現(xiàn).

筆者在原始人工蜂群算法的基礎(chǔ)上，利用K均值算法的思想將蜂群劃分為多個(gè)子蜂群，提出一種多種群人工蜂群算法(multi-swarm artificial bee colony，MABC).子種群將全局通信模式和局部通信模式相結(jié)合，基于局部通信的適應(yīng)度函數(shù)擴(kuò)展了解方案的多樣性，基于全局通信的蜜源位置更新方式加速算法收斂，避免算法陷入局部最優(yōu).在Matlab編程環(huán)境下選取6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)對(duì)算法進(jìn)行測(cè)試，證明了該算法能顯著提高ABC算法的收斂速度和尋優(yōu)精度.

1 原始人工蜂群算法(ABC)

人工蜂群算法是模擬蜜蜂的采蜜行為提出的一種智能優(yōu)化算法，由蜜源，被雇傭蜂(引領(lǐng)蜂)和未被雇傭蜂(跟隨蜂、偵查蜂)3項(xiàng)基本元素構(gòu)成.同時(shí)，引入3種基本的行為模式：搜索蜜源、招募蜜源和放棄蜜源.其中，蜜源的位置代表優(yōu)化問(wèn)題的可行解；蜜源的質(zhì)量對(duì)應(yīng)解的適應(yīng)度.

最優(yōu)蜜源的搜索過(guò)程如下:首先，算法隨機(jī)產(chǎn)生含有N個(gè)偵查蜂的初始種群，初始時(shí)所有蜜蜂都為偵查蜂，同時(shí)也是蜜源的數(shù)量，每個(gè)解Xi是一個(gè)d維向量，Xi={xi1,xi2,…,xid}.計(jì)算解對(duì)應(yīng)函數(shù)值，設(shè)定一個(gè)臨界值，將大于臨界值的解作為蜜源位置.一個(gè)引領(lǐng)蜂與一個(gè)蜜源是相對(duì)應(yīng)的，與第i個(gè)蜜源相對(duì)應(yīng)的引領(lǐng)蜂依據(jù)式(1)尋找新的蜜源.

Vij=Xij+Rij(Xkj-Xij),

(1)

式中：i=1,2,…,N，Vij代表更新后的蜜源;j代表蜜源更新的維度，j=1,2,…d；k代表學(xué)習(xí)的蜜源位置，k≠i，k，j都是隨機(jī)選擇的，并且k≠j；R為[-1,1]的隨機(jī)數(shù).跟隨蜂采用輪盤賭策略選擇蜜源，蜜源選擇的概率公式如下:

(2)

式中：pi代表第i個(gè)蜜源被選擇的概率；fitnessi代表第i個(gè)蜜源的質(zhì)量，即第i個(gè)解的適應(yīng)度值，計(jì)算公式如式(3)所示；N代表解的個(gè)數(shù).

(3)

式中：fi是第i個(gè)解的目標(biāo)函數(shù)值，每個(gè)蜜源被選擇的概率與適應(yīng)度成正比.

所有引領(lǐng)蜂和跟隨蜂經(jīng)過(guò)一次鄰域搜索后，檢查蜜源未更新的次數(shù)Limit，如果一個(gè)蜜源經(jīng)過(guò)Limit次循環(huán)后沒(méi)有得到改善，則該蜜源將會(huì)被放棄，它所對(duì)應(yīng)的引領(lǐng)蜂轉(zhuǎn)為偵查蜂，偵查蜂通過(guò)公式(4)搜索新的蜜源Vij[12].

(4)

原始人工蜂群算法具有控制參數(shù)少、計(jì)算簡(jiǎn)單、便于實(shí)現(xiàn)等優(yōu)點(diǎn)，已經(jīng)被越來(lái)越多的研究者關(guān)注.但是該算法存在收斂速度慢、容易陷入局部最優(yōu)解等缺點(diǎn)，需要在收斂速度和尋優(yōu)精度等方面加以改進(jìn).

2 多種群人工蜂群算法(MABC)

2.1 種群分割

種群分割的具體步驟如下:

步驟2將蜜源按照基于歐氏距離的方法依次劃分到每個(gè)聚類中心；

步驟4分別計(jì)算當(dāng)前所有蜜源到相應(yīng)的聚類中心的均方差之和；

步驟5如果當(dāng)前迭代次數(shù)的均方差之和與前次相同，結(jié)束蜜源聚類，轉(zhuǎn)到步驟6，否則轉(zhuǎn)到步驟2；

步驟6輸出蜜源聚類結(jié)果，即種群分割結(jié)果.

假設(shè)在邊長(zhǎng)為300 cm×200 cm的空間中蜜源數(shù)量為100，按照本文的種群分割方法將其劃分為10個(gè)子種群，其中相同顏色的個(gè)體為同一個(gè)子種群，劃分結(jié)果如圖1所示.

圖1 種群分割結(jié)果Fig.1 The result of population segmentation

2.2 蜜源位置更新方式

ABC算法利用原始的位置更新公式(1)時(shí)，引領(lǐng)蜂缺乏與整個(gè)蜂群的信息交流和共享，算法易陷入局部最優(yōu).種群分割之后，提出基于全局通信的新蜜源位置更新公式(5):

Vij=Xij+Rij(Xkj-Xij)+θij(XCbest,j-Xij),

(5)

式中：Vij代表更新后的蜜源；θij∈[0,1]是一個(gè)隨機(jī)數(shù)；XCbest,j代表蜜源豐富度最高的子種群的聚類中心.

公式(1)只能權(quán)衡自己所在位置和歷史最優(yōu)位置的食物源的豐富度.公式(5)基于全局通信方式加入引導(dǎo)因子X(jué)Cbest,j-Xi,j，使引領(lǐng)蜂能夠參考所有子種群中當(dāng)前最優(yōu)的位置，有很好的方向性.

2.3 適應(yīng)度函數(shù)

(6)

基于局部通信的適應(yīng)度函數(shù)由式(7)代替ABC算法中式(3)：

(7)

改進(jìn)的目標(biāo)函數(shù)值Fi計(jì)算公式如式(8)所示:

Fi=∑Xi∈CjD(Xi,Cj)/NumCj,

(8)

式中：∑Xi∈CjD(Xi,Cj)代表種群Cj中所有蜜源到聚類中心的距離之和；NumCj代表種群Cj中蜜源的數(shù)量.

公式(7)中的適應(yīng)度函數(shù)同時(shí)考慮了子種群中的蜜源數(shù)量和距離，提高了算法的魯棒性.

2.4 MABC算法步驟

步驟1根據(jù)ABC算法初始化蜂群，包括種群規(guī)模N，最大迭代次數(shù)MaxCycle，適應(yīng)度閾值Limit，維度Dim等.

步驟3根據(jù)公式(7)分別計(jì)算Cj個(gè)子種群中蜜蜂的適應(yīng)度值，適應(yīng)度值高的一半作為引領(lǐng)蜂，剩余的作為跟隨蜂.

步驟4Cj中的引領(lǐng)蜂根據(jù)公式(5)搜索蜜源，根據(jù)公式(7)計(jì)算蜜源適應(yīng)度值，若適應(yīng)度值提高，則更新蜜源，否則保留原蜜源不變.

步驟5引領(lǐng)蜂提供蜜源豐富度信息，跟隨蜂根據(jù)公式(6)選擇引領(lǐng)蜂，并采用公式(5)進(jìn)行鄰域蜜源搜索.

步驟6更新Cj狀態(tài)，迭代次數(shù)加1，若迭代次數(shù)達(dá)到Limit后仍有未更新的蜜源，由偵查蜂根據(jù)公式(4)產(chǎn)生一個(gè)新蜜源.

步驟7迭代次數(shù)達(dá)到最大迭代次數(shù)MaxCycle時(shí)，算法結(jié)束；否則，返回步驟3.

3 實(shí)驗(yàn)仿真及分析

實(shí)驗(yàn)中采用操作系統(tǒng)是Windows 10，處理器是Intel(R)Core(TM)i5-6300HQ CPU @2.30 GHz，內(nèi)存4 GB的計(jì)算機(jī)，編譯軟件為Matlab-R2016a.

筆者使用6個(gè)典型的測(cè)試函數(shù)[5]對(duì)MABC算法、ABC算法[14]及文獻(xiàn)[15]中改進(jìn)ABC(CSABC)算法的魯棒性、收斂速度和尋優(yōu)精度進(jìn)行對(duì)比試驗(yàn).

3.1 測(cè)試函數(shù)

為了測(cè)試本文MABC算法在函數(shù)優(yōu)化問(wèn)題中的性能，選擇6個(gè)常用的函數(shù)作為測(cè)試函數(shù)，見表1.其中，f1～f3是單峰函數(shù)，主要用來(lái)測(cè)試算法的收斂速度和尋優(yōu)精度；f4～f6是多峰函數(shù)，主要用來(lái)測(cè)試算法的全局尋優(yōu)能力和避免早熟的能力.

表1 測(cè)試函數(shù)Tab.1 Testing functions

測(cè)試函數(shù)f1～f6表達(dá)式如下：

3.2 測(cè)試結(jié)果對(duì)比分析

MABC、ABC和CSABC 3種算法對(duì)比試驗(yàn)參數(shù)設(shè)置如下：種群規(guī)模N=100，其中引領(lǐng)蜂和跟隨蜂的數(shù)目均為50，最大迭代次數(shù)Max-

Cycle=1 000，適應(yīng)度閾值Limit=50，維度Dim=50.

3種算法對(duì)每個(gè)測(cè)試函數(shù)分別獨(dú)立進(jìn)行50次實(shí)驗(yàn)，得到對(duì)應(yīng)的最優(yōu)值、最差值、平均值和方差，測(cè)試結(jié)果見表2.其中，最優(yōu)值和最差值反映算法的質(zhì)量，平均值反映算法的收斂速度和尋優(yōu)精度，方差反映算法的穩(wěn)定性和數(shù)據(jù)的離散程度.

表2 函數(shù)測(cè)試結(jié)果對(duì)比Tab.2 Comparison of functions test results

圖2 測(cè)試函數(shù)結(jié)果Fig.2 The results of test functions

通過(guò)表2可以看出，筆者提出的MABC算法在單峰函數(shù)和多峰函數(shù)測(cè)試中均有較高的尋優(yōu)精度.算法的最優(yōu)值、最差值與ABC算法和CSABC算法相比有明顯的提升，說(shuō)明MABC算法穩(wěn)定性更高；在相同的迭代次數(shù)下，MABC算法在各測(cè)試函數(shù)上均得到了最小均值和最小方差，表明其收斂速度更快，尋優(yōu)精度更高，性能明顯優(yōu)于ABC算法和CSABC算法.

圖2中給出了MABC算法、ABC算法和CSABC算法獨(dú)立運(yùn)行50次的平均適應(yīng)度值進(jìn)化曲線.由圖2(a)、(b)可以看出，MABC算法達(dá)到穩(wěn)定收斂的次數(shù)遠(yuǎn)小于ABC算法和CSABC算法；由圖2(c)可以看出，ABC算法和CSABC算法在搜索過(guò)程中陷入局部極值，種群分割策略使MABC算法分組尋優(yōu)，收斂值明顯小于其他兩種算法；由圖2(d)可以看出，ABC算法和CSABC算法收斂較快，迭代次數(shù)較少，但過(guò)早停滯，尋優(yōu)精度不如MABC算法；由圖2(e)、(f)可以看出，MABC算法在搜索后期表現(xiàn)出較強(qiáng)的優(yōu)勢(shì)，而ABC算法和CSABC算法則容易陷入局部最優(yōu).

由以上分析可以看出，MABC算法達(dá)到穩(wěn)定收斂時(shí)的尋優(yōu)精度遠(yuǎn)高于ABC算法和CSABC算法，尤其對(duì)單峰函數(shù)而言收斂速度更加明顯.

4 結(jié)束語(yǔ)

筆者針對(duì)原始人工蜂群算法存在的收斂速度慢、易陷入局部最優(yōu)解等不足，提出了一種基于種群分割的多種群人工蜂群算法(MABC)，該算法利用K均值聚類算法中基于歐氏距離的方式對(duì)人工蜂群進(jìn)行種群分割，將大的種群劃分為多個(gè)子種群，每個(gè)子種群分別獨(dú)立運(yùn)行，在子種群中引入基于全局通信的蜜源位置更新方式加速算法收斂，同時(shí)引入基于局部通信的適應(yīng)度函數(shù)擴(kuò)展解方案的多樣性.通過(guò)6組標(biāo)準(zhǔn)測(cè)試函數(shù)的仿真實(shí)驗(yàn)結(jié)果可知，筆者提出的MABC算法比ABC算法及CSABC算法收斂速度快、尋優(yōu)精度高、魯棒性高、適應(yīng)度好.

在未來(lái)的工作中，我們計(jì)劃進(jìn)一步提高算法的性能，并通過(guò)更加多樣性的測(cè)試問(wèn)題進(jìn)行驗(yàn)證，比如最優(yōu)點(diǎn)不在原點(diǎn)或者各維度最優(yōu)點(diǎn)不一樣的測(cè)試函數(shù)進(jìn)行測(cè)試，以證明沒(méi)有偏差.另外筆者計(jì)劃下一步將本文的MABC算法有效地應(yīng)用到實(shí)際工程問(wèn)題中，并采用數(shù)學(xué)方法使其表現(xiàn)出更多的價(jià)值.