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

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

0 引言

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

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

1 基本人工蜂群算法

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

minx∈Xf(x).

(1)

1.1 種群初始化

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

(2)

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

(3)

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

1.2 雇傭蜂階段

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

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

(4)

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

1.3 跟隨蜂階段

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

(5)

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

1.4 偵查蜂階段

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

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

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

2.1 多精英蜂群算法

為了提高人工蜂群算法的求解精度，Xiang等[6]受粒子群算法[8]和文獻(xiàn)[9]的啟發(fā)，將蜂群中多個(gè)蜜源豐富的個(gè)體作為精英，構(gòu)建了精英解集.雇傭蜂階段通過(guò)輪盤賭從精英解集中隨機(jī)選擇一個(gè)精英，利用式(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]上的隨機(jī)數(shù)；Elitistmd表示利用輪盤賭方法從精英種群中選出的第m個(gè)精英的第d維.同時(shí),在跟隨蜂階段結(jié)合蜂群的最優(yōu)蜜源信息，通過(guò)式(7)加強(qiáng)對(duì)優(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]上的隨機(jī)數(shù)；gbestj表示當(dāng)代蜂群中的最優(yōu)個(gè)體的第j維.

2.2 定向更新策略

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

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

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

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

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

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

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

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

(8)

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

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

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

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

單純形算法的大致過(guò)程如下：

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

步驟3若f(xα)

步驟4若f(xα)

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

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

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

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

(2)若SN

vi=elitesi+φ(xi-xk),

(9)

式中：i∈{1,…,D-SN}；k∈{1,…,SN}；φ是[-1,1]上的隨機(jī)數(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ù)計(jì)數(shù)器t=0,最大函數(shù)計(jì)算次數(shù),蜜源停留最大限制次數(shù)limit,初始化密源停留次數(shù)trial=0.

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

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

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

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

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

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

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

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

3 數(shù)值仿真實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果

由表3可以看出，當(dāng)函數(shù)計(jì)算次數(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算法對(duì)于30維f1(Sphere)函數(shù)和f5(Griewank)函數(shù)，在獨(dú)立運(yùn)行30次時(shí)取平均最優(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é)束語(yǔ)

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