金 葉， 孫越泓,2， 王加翠， 王 丹

(1.南京師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，江蘇 南京 210023； 2.南京師范大學(xué) 江蘇省大規(guī)模復(fù)雜系統(tǒng)數(shù)值模擬重點實驗室，江蘇 南京 210023)

0 引言

人工蜂群(artificial bee colony，ABC)[1]算法是模擬蜜蜂采蜜機制提出的群體智能隨機搜索優(yōu)化算法，該算法結(jié)構(gòu)簡單，設(shè)置參數(shù)少，不需要求解函數(shù)的梯度，易與其他算法結(jié)合，在函數(shù)優(yōu)化[2]、工程優(yōu)化[3]等方面得到了廣泛應(yīng)用.

近年來，已有不少專家學(xué)者對ABC算法進(jìn)行了改進(jìn).文獻(xiàn)[4]在雇傭蜂階段提出了一種帶有新的搜索算子的改進(jìn)的人工蜂群算法(improved artificial colony algorithm，IABC)；文獻(xiàn)[5]在跟隨蜂階段提出了一種新的選擇策略(improved artificial colony algorithm，iABC)；文獻(xiàn)[6]提出了受粒子群啟發(fā)的多精英人工蜂群算法(particle swarm inspired muliti-elitist artificial bee colony，PS-MEABC).人工蜂群算法具有較好的全局搜索能力，但是文獻(xiàn)[4-5]指出,ABC算法和其他群智能算法一樣,在求解無約束優(yōu)化問題時存在易早熟、局部搜索能力弱、尋優(yōu)得到解的精度低等問題.筆者在受粒子群啟發(fā)的多精英人工蜂群算法[6]的基礎(chǔ)上，提出一種新的基于單純形的改進(jìn)精英人工蜂群(improved muliti-elitist artificial bee colony algorithm based on nelder-mead simplex method，NM-PS-MEIABC)算法：利用定向更新策略，改進(jìn)了蜂群隨機選取鄰居的方式,建立新的跟隨蜂選擇概率公式,并利用單純形方法局部搜索能力強的特點提高算法的局部尋優(yōu)能力.8個基準(zhǔn)函數(shù)上的數(shù)值實驗表明，求解無約束優(yōu)化問題時，本文新算法與ABC和PS-MEABC算法相比，求解精度和收斂速度都有較大改進(jìn).

1 基本人工蜂群算法

ABC算法[1]是通過模擬蜜蜂采蜜過程中的智能機制處理函數(shù)優(yōu)化問題.人工蜂群算法描述如下:首先引入蜜源，它代表解空間中各種可能的解，函數(shù)優(yōu)化過程中通過適應(yīng)度值來衡量蜜源；再引入3種蜂，即雇傭蜂、跟隨蜂和偵查蜂.雇傭蜂在蜂房附近搜索蜜源，側(cè)重對蜜源的探測；跟隨蜂接收其他蜜蜂分享的蜜源信息，主要負(fù)責(zé)開采蜜源；偵查蜂在食物源枯竭時，隨機在蜂巢附近尋找新的蜜源.求解無約束優(yōu)化問題(1)時，

minx∈Xf(x).

(1)

1.1 種群初始化

首先按照式(1)產(chǎn)生SN個個體的初始蜜源，得到初始種群：

(2)

產(chǎn)生初始種群后，通過式(2)計算蜜源的質(zhì)量：

(3)

式中：fi為蜜源xi的目標(biāo)函數(shù)值f(xi)；fiti為蜜源的適應(yīng)度值,適應(yīng)度值越大,表示該蜜源質(zhì)量越優(yōu).

1.2 雇傭蜂階段

雇傭蜂根據(jù)式(3)對每個蜜源進(jìn)行一次鄰域搜索,產(chǎn)生新蜜源：

vij=xij+φij(xij-xkj)，

(4)

式中：k∈{1,…,SN}，j∈{1,…,D},這兩個數(shù)都是隨機選取的,但k≠i；φij是[-1,1]上的隨機數(shù).在每次鄰域搜索過程中隨機更新一維(j)上的數(shù)值,然后評估vi的質(zhì)量,利用貪婪選擇策略更新蜜源.

1.3 跟隨蜂階段

跟隨蜂階段,雇傭蜂先將蜜源信息共享給觀察蜂，然后跟隨蜂依據(jù)蜜源質(zhì)量,選擇蜜源進(jìn)行開采,每個蜜源的選擇概率計算方式如下：

(5)

式中：Pi表示蜜源i的選擇概率.當(dāng)蜜源被選中之后,跟隨蜂將按照式(4)對所選中的蜜源進(jìn)行鄰域搜索，并根據(jù)貪婪選擇策略更新蜜源.

1.4 偵查蜂階段

控制參數(shù)limit用來記錄某個解未被更新的次數(shù).假定某個解經(jīng)過limit次循環(huán)之后都未得到改善，即表明這個解陷入了局部最優(yōu)，應(yīng)該被放棄，與這個解相對應(yīng)的雇傭蜂也轉(zhuǎn)變?yōu)閭刹榉?將按式(2)重新隨機產(chǎn)生新蜜源.

2 基于單純形的改進(jìn)精英蜂群算法

受精英人工蜂群算法[6]和Nelder-Mead單純形方法[7]的啟發(fā)，筆者提出了NM-PS-MEIABC算法.該算法的基本思想是在蜂群中建立精英解集，在雇傭蜂階段借助精英個體引導(dǎo)蜜源搜索，并利用蜂群中蜜源的質(zhì)量排序重新構(gòu)造蜜源的選擇概率公式.在跟隨蜂階段，選擇種群最優(yōu)蜜源引領(lǐng)蜂群，加強算法對全局最好解的局部開采能力，同時將隨機選擇鄰居蜜源變?yōu)槎ㄏ蜻x擇.最后,利用單純形算法對精英解集進(jìn)行再次更新，使得算法的局部尋優(yōu)能力更強，從而達(dá)到提高求解精度的目的.而多精英人工蜂群算法和新算法的3個改進(jìn)之處：多定向更新策略、基于蜜源目標(biāo)函數(shù)值排序的選擇概率公式和基于精英解集的單純形局部搜索機制.

2.1 多精英蜂群算法

為了提高人工蜂群算法的求解精度，Xiang等[6]受粒子群算法[8]和文獻(xiàn)[9]的啟發(fā)，將蜂群中多個蜜源豐富的個體作為精英，構(gòu)建了精英解集.雇傭蜂階段通過輪盤賭從精英解集中隨機選擇一個精英，利用式(6)改進(jìn)蜜源的更新：

vid=xid+φid(xid-xkd)+σid(xid-Elitistmd),

(6)

式中：i∈{1,…,SN}；d∈{1,…,D}；k∈{1,…,SN}；φid、σid是[-1,1]上的隨機數(shù)；Elitistmd表示利用輪盤賭方法從精英種群中選出的第m個精英的第d維.同時,在跟隨蜂階段結(jié)合蜂群的最優(yōu)蜜源信息，通過式(7)加強對優(yōu)質(zhì)蜜源的開采：

vij=xij+φij(xij-xkj)+θij(xij-gbestj)，

(7)

式中：i∈{1,…,SN}；j∈{1,…,D}；k∈{1,…,SN}；φij、θij是[-1,1]上的隨機數(shù)；gbestj表示當(dāng)代蜂群中的最優(yōu)個體的第j維.

2.2 定向更新策略

Van den Bergh[10]等指出，在粒子群算法中，粒子更新會出現(xiàn)整體在優(yōu)化，但是某一維卻惡化的情況.對于ABC算法同樣存在這種現(xiàn)象，由式(4)、(6)和(7)可知，無論是雇傭蜂階段還是跟隨蜂階段，在進(jìn)行蜜源更新時，鄰居食物源xkj,k∈{1,…,SN} 均是隨機從蜂群中選擇的個體，k的隨機選取可能會導(dǎo)致蜜源第j維更新朝著遠(yuǎn)離最優(yōu)蜜源的方向.

圖1 2維空間中蜜源搜索鄰居的選取說明Fig.1 Illustration of how to select the neighbour sources in 2-D solution space

圖1中,種群個體數(shù)目SN=5，維數(shù)D=2，gbest為當(dāng)前種群中的最優(yōu)解.對于第一維,種群中個體x2距離gbest最近;對于第二維,個體x4距離gbest最近,雖然它在第一維上是種群中距離gbest最遠(yuǎn)的個體.

對于優(yōu)化問題minx∈Xf(x)而言,整個蜂群在尋優(yōu)過程中不斷尋找質(zhì)量高的蜜源，也即函數(shù)值不斷下降的解.然而函數(shù)的下降依賴于搜索過程中蜂群中個體不斷趨向問題的解x*(x*∈X).最優(yōu)定向策略應(yīng)用于觀察蜂階段,通過Distj的大小來衡量種群中不同個體在第j維和gbest的距離.

通過上述過程,在更新第j維時,借助當(dāng)前最優(yōu)解的同時,將整個種群中的所有個體進(jìn)行比較.一方面加強了個體間的信息交流,定向引導(dǎo)蜜源更新；另一方面隨著迭代的進(jìn)行,種群當(dāng)前最優(yōu)蜜源不斷趨向問題的解x*,也保證了種群Foods={x1,x2,…,xSN}最終能夠收斂到問題的最優(yōu)解x*，文獻(xiàn)[13]中有詳細(xì)的收斂證明.

2.3 基于蜜源目標(biāo)函數(shù)值排序的選擇概率公式

基本的人工蜂群算法在跟隨蜂階段，利用式(5)計算每只蜂的跟隨概率.在數(shù)值實驗中發(fā)現(xiàn)，在迭代前期，整體蜜源的質(zhì)量都不是很好，對應(yīng)的選擇概率也就相對較低，從而被跟隨的可能性較??；到了迭代后期，蜜源的整體質(zhì)量都很高，即fiti比較相近，蜜源的選擇概率大部分接近1/SN.產(chǎn)生這一現(xiàn)象的主要原因是對于目標(biāo)函數(shù)值小于一定數(shù)量級的蜜源，已經(jīng)很難通過蜜源適應(yīng)度值的計算公式(3)和概率計算公式(4)將這些蜜源加以區(qū)分.

為了解決這一問題，筆者受文獻(xiàn)[14]的啟發(fā)，在構(gòu)造選擇概率公式時，不采用蜜源的適應(yīng)度值，而是直接利用蜜源目標(biāo)函數(shù)值從大到小排序后的序標(biāo)，借助式(8)重新定義：

(8)

式中：a=0.1；b=0.9；c為常數(shù)；j為第i個蜜源在整個蜂群中按照目標(biāo)函數(shù)值從大到小排序得到的序標(biāo).第i個蜜源越好，它的序標(biāo)j將越大，通過式(8)計算得到的選擇概率Pi也就越接近1.

2.4 精英解集Nelder-Mead單純形局部搜索機制

單純形法(nelder-mead simplex method, NM-SM)[7]是一種局部搜索算法，具有較強的局部搜索能力.近年來，單純形法被用于一些全局優(yōu)化算法中來增強局部搜索能力.單純形法和人工魚群算法[15]、頭腦風(fēng)暴算法[16]等優(yōu)化算法都做過結(jié)合.單純形算法的基本思想是：對于D維優(yōu)化問題，利用D+1個點作為頂點構(gòu)成凸包，即單純形.在已有單純形的基礎(chǔ)上通過反射、擴張和收縮去尋找一個目標(biāo)函數(shù)值更小的點.如果得到這樣的點就可以用該點作為頂點構(gòu)造新的單純形，否則將已有單純形縮小.具體算法流程見文獻(xiàn)[17].

在單純形算法每次迭代過程中，反射系數(shù)、擴張系數(shù)、收縮系數(shù)分別為α、γ、β，定義如下：

單純形算法的大致過程如下：

步驟2對最差的點進(jìn)行反射，得到反射點xα.

步驟3若f(xα)

步驟4若f(xα)

步驟5若f(xh)>f(xα)>f(xp)，執(zhí)行收縮操作得到收縮點xw;若f(xw)

人工蜂群算法雖然全局搜索能力不錯，但是存在著局部搜索能力差、在接近最優(yōu)解時搜索效率下降、求解復(fù)雜問題時容易陷入局部最優(yōu)而停滯不前的缺點[18]，而單純形法具有很強的局部搜索能力，它和人工蜂群算法的全局搜索能力互補，如果將兩者結(jié)合必然相得益彰.

因此，為了進(jìn)一步加強算法對蜜源的開采能力，將更新后的精英解集在偵查蜂階段之后結(jié)合當(dāng)前全局最優(yōu)蜜源，利用D+1個蜜源構(gòu)成初始單純形，初始單純形的構(gòu)造具體如下.

(1)若SN>D,則對更新后的精英解集按照函數(shù)值從小到大排序,利用前D個精英蜜源和全局最優(yōu)蜜源構(gòu)成初始單純形.

(2)若SN

vi=elitesi+φ(xi-xk),

(9)

式中：i∈{1,…,D-SN}；k∈{1,…,SN}；φ是[-1,1]上的隨機數(shù).然后利用Nelder-Mead單純形法進(jìn)行局部搜索，加快算法的收斂.單純形方法的迭代次數(shù)和食物源數(shù)目保持一致，取為SN.

2.5 NM-PS-MEIABC算法步驟

步驟1參數(shù)設(shè)置.設(shè)置蜂群規(guī)模NP,雇傭蜂數(shù)SN=NP/2,跟隨蜂數(shù)SN=NP/2.迭代步數(shù)計數(shù)器t=0,最大函數(shù)計算次數(shù),蜜源停留最大限制次數(shù)limit,初始化密源停留次數(shù)trial=0.

步驟2初始化種群.按式(2)隨機產(chǎn)生SN個蜜源.利用式(3)對蜜源質(zhì)量進(jìn)行評價.并記錄下此時的全局最優(yōu)蜜源gbest,并利用初始種群初始化精英解集.

步驟3精英個體引導(dǎo)雇傭蜂搜索.利用輪盤賭方法,隨機從精英解集中選取一個精英個體Elitistm,利用式(6)對蜜源進(jìn)行搜索.對超出搜索范圍的解直接利用精英Elitistm代替,接著利用貪婪選擇決定是否更新蜜源, 更新gbest和密源停留次數(shù)trial.

步驟4選擇概率計算.將所有蜜源按照目標(biāo)函數(shù)值從大到小排列.蜜源xi質(zhì)量越高,序標(biāo)j越大.利用式(8)計算跟隨蜂選擇蜜源xi的概率Pi.

步驟6偵查蜂更新.若蜜源的停留次數(shù)trial>limit成立，則該蜜源轉(zhuǎn)為偵查蜂，用式(2)重新隨機產(chǎn)生新的蜜源將其更新.

步驟7精英解集的更新.如果種群中全局最優(yōu)蜜源優(yōu)于輪盤賭選出的最差精英個體，則將其替換從而更新精英解集，保持精英蜜源個數(shù)為SN.

步驟8基于精英解集的單純形局部搜索機制.用更新后的精英解集和全局最優(yōu)蜜源構(gòu)造初始單純形，接下來采用Nelder-Mead單純形進(jìn)行局部再開采，最后利用輸出的單純形更新對應(yīng)的精英個體.若單純形最優(yōu)解優(yōu)于蜂群最差個體，則替換蜂群最差個體，將利用單純形進(jìn)行局部搜索得到的最優(yōu)蜜源信息傳遞給蜂群.

步驟9記錄全局最優(yōu).單純形開采后的最優(yōu)蜜源和gbest進(jìn)行比較，記錄較優(yōu)的蜜源作為當(dāng)前全局最優(yōu)蜜源.

步驟10停止準(zhǔn)則.判斷是否達(dá)到最大函數(shù)計算次數(shù)FES,若滿足則輸出全局最優(yōu)解，否則轉(zhuǎn)步驟3.

3 數(shù)值仿真實驗結(jié)果

3.1 測試函數(shù)

為了驗證NM-PS-MEIABC算法的有效性，筆者進(jìn)行了數(shù)值實驗，將其與ABC算法[1]和PS-MEABC[6]算法,NMABC[18]作比較.實驗設(shè)備為：臺式電腦HP LV2011，CPU為Intel Core2 Duo CPU E7500 2.93 GHz, 2 012 MB內(nèi)存，實驗仿真軟件Matlab2012b.所有用于比較的算法的種群大小SP=100，食物源數(shù)目SN=50，最大限制次數(shù)limit=100，決策變量維數(shù)為30維，函數(shù)計算次數(shù)(maximum function evaluations,MFE)為300 000次.參照基于精英蜂群搜索策略的人工蜂群算法[19], 筆者選取8個基本測試函數(shù)，如表1所示.

表1 測試函數(shù)Tab.1 Test functions

新算法在構(gòu)建好的精英解集上引入了Nelder-Mead單純形局部搜索機制,以增強人工蜂群的局部尋優(yōu)能力.單純形中反射系數(shù)、擴張系數(shù)以及收縮系數(shù)的不同取值,在不同問題中對算法影響程度不同.通常反射系數(shù)α=1,擴張系數(shù)1<γ≤2,收縮系數(shù)0<β<1[20].接下來對反射系數(shù)和收縮系數(shù)設(shè)置不同取值,進(jìn)行實驗分析,測試中選取單峰函數(shù)f1,多峰函數(shù)f4、f7.在30維上進(jìn)行30次模擬,最大函數(shù)計算次數(shù)為300 000.

表2給出了取定單純形收縮系數(shù)β=0.5時，擴張系數(shù)γ不同取值下在3個測試函數(shù)上的實驗結(jié)果.由表2得知，擴張系數(shù)γ=2時，算法在選取的測試函數(shù)上效果最差；γ=1.2時，效果一般；動態(tài)變化γ從2遞減至1.2時，效果最好.綜上，將γ的取值設(shè)在2～1.2變化，隨著迭代的進(jìn)行，在算法后期減小對單純形的擴張，實驗得到的結(jié)果是最好的.故新算法中，γ=2～1.2.

表2還給出了取定單純形擴張系數(shù)γ=1.2時，收縮系數(shù)β取值不同時的實驗結(jié)果.收縮系數(shù)β=0.2時，算法在3個給定函數(shù)上的結(jié)果最差，可知局部尋優(yōu)的單純形收縮過小容易導(dǎo)致算法陷入局部最優(yōu).當(dāng)β=0.8時，算法的效果最好，故在新算法NM-PS-MEIABC中取β=0.8.

表2 算法NM-PS-MEIABC關(guān)于擴張系數(shù)γ的不同取值(β=0.5)和關(guān)于收縮系數(shù)β的不同取值(γ=1.2)Tab.2 The different values of the expansion coefficient and contraction coefficient

3.2 實驗結(jié)果

由表3可以看出，當(dāng)函數(shù)計算次數(shù)相同時，很明顯NM-PS-MEIABC 算法具有較好的尋優(yōu)性能，比ABC算法、PS-MEABC、NMABC算法有更高的求解精度.

表3 本文算法與其他人工蜂群算法在30維上結(jié)果比較Tab.3 The comparison results with ABC variants

圖2、圖3分別給出了ABC算法、PS-MEABC算法、NMABC算法和NM-PS-MEIABC算法對于30維f1(Sphere)函數(shù)和f5(Griewank)函數(shù)，在獨立運行30次時取平均最優(yōu)值的收斂情況.從圖2～圖3可以看出，筆者算法在收斂速度和搜索精度上要優(yōu)于其余3種算法.

圖2 Sphere函數(shù)收斂情況Fig.2 The convergence of Sphere function

圖3 Griewank函數(shù)收斂情況Fig.3 The convergence of Griewank function

4 結(jié)束語

筆者提出了一種基于單純形的改進(jìn)精英人工蜂群算法，算法利用單純形算法加強對解的局部尋優(yōu)，并提出了新的鄰域搜索方法和跟隨概率的計算公式.數(shù)值實驗結(jié)果表明，新算法與ABC、PS-MEABC、NMABC算法相比，求解精度和收斂速度均有顯著提高，尋優(yōu)性能也更加穩(wěn)定，未來可以進(jìn)一步做ABC算法的應(yīng)用以及綜述.