求解高維復(fù)雜優(yōu)化問題的改進(jìn)人工蜂群算法

賀桂嬌 ，周樹亮 ，馮冬青

1.廣州現(xiàn)代信息工程職業(yè)技術(shù)學(xué)院，廣州 510663

2.鄭州大學(xué) 電氣工程學(xué)院，鄭州 450001

3.中國(guó)中鐵工程裝備集團(tuán)有限公司，鄭州 450016

1 引言

Artificial Bee Colony（ABC[1]）算法是2005年由土耳其學(xué)者Karaboga提出的一種新的群體智能算法。ABC算法因原理簡(jiǎn)單、控制參數(shù)少、靈活性及適應(yīng)度高等特點(diǎn)[2]，越來越受到學(xué)者們的青睞。ABC算法常用于解決函數(shù)離散優(yōu)化[3-4]和無約束優(yōu)化問題[5]，但是ABC算法存在容易早熟收斂、收斂精度低、易陷入局部最優(yōu)、后期跳出局部最優(yōu)能力不足等缺點(diǎn)。究其原因都是因?yàn)锳BC算法的開發(fā)能力不足。

針對(duì)上述問題，研究者提出了很多改進(jìn)方案。暴勵(lì)[6]等人在ABC算法中融合差分進(jìn)化算法，提出BDABC算法，兩種算法互相融合，共享最優(yōu)解，收斂速度提高。汪繼文[7]等人改進(jìn)搜索方程，提出了ABC/current-to-best算法，收斂速度提高但是容易陷入局部最優(yōu)。張?zhí)8]等人引入自適應(yīng)步長(zhǎng)策略，提出SAABC算法。Lv[9]等在全局搜索方程中加入高斯擾動(dòng)，提出GBABC算法，算法的魯棒性提高但是收斂精度改善甚微。Sharma[10]等在搜索方程中加入所有個(gè)體的位置信息，有效防止了算法陷入局部最優(yōu)。Pan[11]等在搜索方程中加入全局最優(yōu)解和一些隨機(jī)個(gè)體，提高了算法的收斂精度，但是對(duì)于多模態(tài)復(fù)雜問題，尋優(yōu)效果并沒有多大改善。李國(guó)亮[12]研究ABC算法在不同的迭代階段設(shè)計(jì)了不同的搜索方式，從而減低了算法陷入局部極值的可能性。Amira[13]結(jié)合量子計(jì)算和ABC算法，提出量子人工蜂群（QABC）算法，不僅提高算法的多樣性，而且提高了計(jì)算能力。Zhang和Liu[14]結(jié)合DE算法改進(jìn)蜂群算法，提出NABC算法，從而提高了算法的收斂精度。Sharma[15]設(shè)計(jì)了一種新穎的ABC算法DABC。DABC算法在兩個(gè)方向上搜索潛在蜜源，有效提高了算法的收斂精度。

在標(biāo)準(zhǔn)ABC算法中，觀察蜂按照輪盤賭策略選擇蜜源。這種根據(jù)隨機(jī)概率選擇蜜源的方法，雖然保證了優(yōu)秀的蜜源更容易被選中，但是選擇失敗經(jīng)常發(fā)生。實(shí)驗(yàn)證明選擇失敗的次數(shù)大約為觀察蜂個(gè)數(shù)的10倍。這無疑會(huì)耗費(fèi)計(jì)算機(jī)資源，延長(zhǎng)迭代時(shí)間。標(biāo)準(zhǔn)ABC采用輪盤賭選擇策略，本質(zhì)上為了保證適應(yīng)度高的蜜源更容易被選中。在不違背這種初衷的情況下，BAABC算法不再通過輪盤賭選擇蜜源，而是直接選擇適應(yīng)度高的蜜源。BAABC算法將吸引子引入到觀察蜂的搜索方程中。種群中所有觀察蜂圍繞吸引子等比例收縮，集中開發(fā)一片區(qū)域，增加了局部開發(fā)能力。而且收縮是有方向意識(shí)的，在單峰函數(shù)求解過程中，方向正好是兩點(diǎn)之間梯度方向，且方向?yàn)檎?/p>

仿真實(shí)驗(yàn)結(jié)果表明，BAABC算法的收斂速度和收斂精度都有很大的提高。更值得一提的是BAABC算法的收斂效果與問題維數(shù)無關(guān)。在解決高維復(fù)雜問題上，收斂效果明顯優(yōu)于其他算法，具有良好的魯棒性。

2 標(biāo)準(zhǔn)人工蜂群算法

蜂群由雇傭蜂、跟隨蜂和偵查蜂三部分組成。雇傭蜂（employed bee）處于特定的食物源，并且攜帶有關(guān)食物源的信息。跟隨蜂（onlookers）通過雇傭蜂共享的信息尋找食物源。偵查蜂（scouts）負(fù)責(zé)在食物源附近搜索新的潛在食物源。

2.1 初始化

設(shè)蜂群大小為2×SN，目標(biāo)函數(shù) f(x)是一個(gè)D維的優(yōu)化問題。蜜源代表了算法在搜索空間里隨機(jī)生成的可行解，搜索空間內(nèi)的可行解依照式（1）隨機(jī)產(chǎn)生。

式中，j=1,2,…,D;i=1,2,…,SN,D為個(gè)體向量維數(shù)；lbj為第 j維下界；ubj為第 j維上界。

2.2 蜂群進(jìn)化階段

雇傭蜂在當(dāng)前依附的蜜源附近進(jìn)行鄰域搜索，尋找更好的蜜源，如果發(fā)現(xiàn)比當(dāng)前更優(yōu)秀的蜜源，更新當(dāng)前蜜源。雇傭蜂搜索方程式如式（2）所示：

式中，j=1,2,…,D;k=1,2,…,D;k是一個(gè)隨機(jī)整數(shù)且k≠i;?ij是在[-1,1]范圍內(nèi)的隨機(jī)數(shù)。

跟隨蜂根據(jù)雇傭蜂所攜帶的蜜源信息，按照輪盤賭選擇策略進(jìn)行依附，進(jìn)而轉(zhuǎn)化為雇傭蜂，并在蜜源鄰域內(nèi)搜索新的蜜源。跟隨蜂依附后，按照式（2）進(jìn)行搜索新蜜源。跟隨蜂選擇蜜源的方式采用輪盤賭方式，其選擇概率如式（3）所示：

式中，fit(xi)是蜜源xi的適應(yīng)度值；Pi是xi被選擇的概率。

當(dāng)雇傭蜂在迭代閾值limit范圍內(nèi)，未找到更好的蜜源，則雇傭蜂轉(zhuǎn)變?yōu)閭刹榉洌M(jìn)行全局搜索，按照式（4）產(chǎn)生新解。

式中，向量Xmin=(lb1,lb2,…,lbD)；Xmax=(ub1,ub2,…,ubD)；R=(?1,?2,…,?D)；?1,?2,…,?D是在 [-1,1]范圍內(nèi)的隨機(jī)數(shù)。

3 求解高維復(fù)雜優(yōu)化問題的改進(jìn)人工蜂群算法

在標(biāo)準(zhǔn)ABC算法中，觀察蜂根據(jù)輪盤賭選擇蜜源。輪盤賭雖然可以保證優(yōu)秀蜜源更容易被選中，但是無法保證不出現(xiàn)選擇失敗。ABC算法通過迭代計(jì)算尋找最優(yōu)解。若出現(xiàn)選擇失敗，那無疑會(huì)浪費(fèi)一次迭代時(shí)間。這明顯會(huì)浪費(fèi)計(jì)算機(jī)資源。本文設(shè)計(jì)實(shí)驗(yàn)統(tǒng)計(jì)選擇失敗的次數(shù)。實(shí)驗(yàn)設(shè)置，種群大小20，迭代次數(shù)2 000次，運(yùn)行10次。實(shí)驗(yàn)結(jié)果如表1所示。

表1 觀察蜂選擇失敗的次數(shù)

表1中數(shù)據(jù)是算法運(yùn)行一次，在每次迭代中，觀察蜂選擇失敗的次數(shù)。那么算法運(yùn)行一次，觀察蜂選擇失敗的次數(shù)是表中數(shù)據(jù)乘以2 000后的結(jié)果。可見，這個(gè)數(shù)目還是相當(dāng)龐大的。根據(jù)表1得出，每次觀察蜂選擇失敗的次數(shù)大約是100次。種群大小為20，那么觀察蜂的個(gè)數(shù)為10。因此每次觀察蜂搜索時(shí)，選擇失敗的次數(shù)大約是觀察蜂個(gè)數(shù)的10倍。因此如果種群越大，選擇失敗的次數(shù)也就越多。進(jìn)而，浪費(fèi)的搜索時(shí)間也越多。

BAABC算法摒棄輪盤賭策略，并通過引進(jìn)吸引子cr改變觀察蜂的搜索方式。所有觀察蜂都以吸引子為中心等比例收縮，共同開發(fā)同一區(qū)域，從而提高了算法的開發(fā)能力。吸引子cr作為蜂群中的“蜂王”，吸引所有觀察蜂等比例靠近它，并共同開發(fā)“蜂王”所在的區(qū)域。BAABC算法的搜索示意圖如圖1所示。其中紅色球代表吸引子cr，黑色球代表種群個(gè)體的當(dāng)前位置，綠色球代表種群個(gè)體圍繞吸引子cr收縮后的新位置，R為種群個(gè)體圍繞吸引子收縮后的搜索空間半徑。

圖1 BAABC搜索示意圖

BAABC算法分兩種情況得到吸引子cr。當(dāng)種群個(gè)體是全局最優(yōu)解，吸引子cr根據(jù)式（5）得到，否則吸引子cr根據(jù)式（6）得到：

式中，vi是當(dāng)前代表可行解的蜜源;r1、r2、r3是一組隨機(jī)數(shù)且r1∈(0.5,1.5)，r2∈(-1,1)，r3∈(0,1)。 r1、r2、r3根據(jù)問題動(dòng)態(tài)調(diào)整。如果測(cè)試函數(shù)局部最優(yōu)點(diǎn)比較多，可以令r3∈(-1,1)。式（5）產(chǎn)生吸引子依賴于全局最優(yōu)個(gè)體。式（6）中個(gè)體分量占主體，全局最有個(gè)體作為擾動(dòng)分量。BAABC根據(jù)兩種情況產(chǎn)生吸引子，較好地保留了種群的多樣性，有效地避免了算法陷入局部最優(yōu)解。在偵查蜂階段，BAABC算法重新初始化未更新次數(shù)達(dá)到閾值的個(gè)體。這種方式進(jìn)一步降低了算法陷入局部最優(yōu)的可能性。

吸引子cr作為蜂群中心，每一個(gè)觀察蜂都以它為中心，向它等比例收縮，既減少了個(gè)體飛出邊界的可能，同時(shí)又增加了算法開發(fā)能力。收縮是有方向意識(shí)的，在單峰函數(shù)求解過程中，梯度在兩點(diǎn)之間的分量正好為正，這說明兩點(diǎn)之間任一可行解都會(huì)優(yōu)于當(dāng)前可行解，當(dāng)然這是在吸引子優(yōu)于當(dāng)前可行解的情況下。在多峰函數(shù)求解過程中，由于局部峰值較多，難免會(huì)出現(xiàn)梯度在兩點(diǎn)之間的分向量為負(fù)，但是這種收縮機(jī)制增強(qiáng)了局部開發(fā)能力，加快了后期的收斂速度和開采能力。對(duì)種群個(gè)體進(jìn)行位置更新的公式，如式（7）所示：

式中，%是取模運(yùn)算符；r=K×rand；K是大于零的整數(shù)；K的值決定了算法的縮放比例，所以對(duì)算法收斂精度有一定的影響，在本文第4章會(huì)分析K值大小對(duì)算法的影響;xmax，xmin分別是種群個(gè)體每一維的上界和下界。在算法每一代進(jìn)化過程中，r的取值為定值。

本文中將雇傭蜂的搜索方程（2）改為式（8）：

式中，α是[0，1]之間的隨機(jī)數(shù)；?ij是[-1,1]之間的隨機(jī)數(shù)；xg,j是全局最優(yōu)解 j維。搜索方程加入全局最優(yōu)解的引導(dǎo)，增強(qiáng)了算法的開發(fā)能力。

4 改進(jìn)人工蜂群算法BAABC的流程步驟

步驟1設(shè)置種群規(guī)模2×SN，維數(shù)D，搜索區(qū)間等參數(shù)，按照式（1）隨機(jī)生成代表可行解的初始蜜源。

步驟2雇傭蜂階段：雇傭蜂按照式（8）進(jìn)行蜜源鄰域搜索新蜜源。計(jì)算適應(yīng)度值，選擇適應(yīng)度好的蜜源。

步驟3觀察蜂階段：設(shè)定K值（每次迭代都是隨機(jī)的），遍歷種群中的每個(gè)觀察蜂，根據(jù)式（5）和式（6）得到吸引子，根據(jù)式（7），所有觀察蜂等比例向吸引子收縮。計(jì)算適應(yīng)度值，選擇適應(yīng)度好的蜜源。

步驟4偵查蜂階段：若存在放棄的蜜源，該處的雇傭蜂變?yōu)閭刹榉洌鶕?jù)式（4）產(chǎn)生新解。

步驟5判斷是否滿足循環(huán)終止條件，如果滿足停止循環(huán)，輸出結(jié)果，否則執(zhí)行步驟2。

5 仿真實(shí)驗(yàn)和結(jié)果分析

為了驗(yàn)證改進(jìn)算法的有效性，本文中選用了9個(gè)經(jīng)典測(cè)試函數(shù)。

設(shè)計(jì)實(shí)驗(yàn)驗(yàn)證系數(shù)K對(duì)算法的影響。種群大小20，維數(shù)30，迭代次數(shù)2 000，實(shí)驗(yàn)結(jié)果如表2所示。

從表2中得出，K值影響算法收斂精度的大小。這是因?yàn)镵值決定了算法的縮放比例，從而影響搜索空間。當(dāng)K值比較大的時(shí)候，搜索空間的半徑R就會(huì)過于小，致使算法很難跳出局部最優(yōu)。如果搜索空間不對(duì)，那么無論多么努力，也找不到最優(yōu)解。一般情況下，K取值不超過1.5。

為了進(jìn)一步驗(yàn)證改進(jìn)算法的效果，對(duì)比近年來幾種改進(jìn)ABC算法：ABCCTB算法[7]、基于交叉運(yùn)算的全局人工蜂群算法CGABC[16]、基于邊界改進(jìn)的人工蜂群算法ABCMB和原始人工蜂群算法ABC分兩組進(jìn)行對(duì)比，第一組種群大小20，最大迭代次數(shù)1 000，維數(shù)100維，搜索范圍(-30,30)，運(yùn)行30次求平均值。兩組實(shí)驗(yàn)結(jié)果見表3。第一組收斂曲線如圖2所示。第二組種群大小20，最大迭代次數(shù)1 000，維數(shù)50維，搜索范圍(-30,30)，運(yùn)行30次求平均值。第二組收斂曲線如圖3所示。

表2 K值對(duì)實(shí)驗(yàn)結(jié)果（平均值）的影響

表3 D=100,D=50,5種對(duì)比算法的實(shí)驗(yàn)結(jié)果

圖2 D=100時(shí)，實(shí)驗(yàn)收斂曲線（關(guān)于迭代次數(shù)）

圖3 D=50時(shí)，實(shí)驗(yàn)收斂曲線（關(guān)于迭代次數(shù)）

在BAABC算法中，觀察蜂摒棄輪盤賭選擇蜜源，而是采用圍繞吸引子收縮更新蜜源。采用該方法可以省去選擇失敗的時(shí)間。為了驗(yàn)證BAABC算法關(guān)于時(shí)間的收斂速度。本文又設(shè)計(jì)了兩組實(shí)驗(yàn)，第一組實(shí)驗(yàn)種群大小20，迭代時(shí)間6 s，問題維數(shù)50，運(yùn)行30次；第二組實(shí)驗(yàn)種群大小20，迭代時(shí)間6 s，問題維數(shù)100，運(yùn)行30次。實(shí)驗(yàn)?zāi)康木褪牵谟邢奘諗繒r(shí)間內(nèi)，對(duì)比4種改進(jìn)ABC算法和標(biāo)準(zhǔn)ABC算法的收斂效果。實(shí)驗(yàn)結(jié)果如圖4所示。

本文選擇的8個(gè)測(cè)試函數(shù)，涵蓋單峰函數(shù)、多峰函數(shù)、復(fù)雜單峰函數(shù)。Sphere函數(shù)、SumSquares函數(shù)和Akely函數(shù)是收斂比較簡(jiǎn)單的單峰函數(shù)。這類測(cè)試函數(shù)主要是用來檢驗(yàn)算法的收斂速度和全局搜索能力。Ronsenbrock函數(shù)雖然是一個(gè)單峰函數(shù)，但是很難找到它的全局最優(yōu)解。這是因?yàn)樵谄渥顑?yōu)解附近有一條平滑、狹長(zhǎng)的拋物線形山谷，并且算法在這個(gè)山谷內(nèi)很難辨別搜索方向。因此Ronsenbrock函數(shù)主要用來評(píng)價(jià)算法的開發(fā)能力和收斂精度。根據(jù)圖2、3，從Sphere函數(shù)、SumSquares函數(shù)和Akely函數(shù)的收斂效果可以看出，BAABC算法的收斂速度是可圈可點(diǎn)的。從Ronsenbrock函數(shù)的收斂效果可以看出，BAABC算法的收斂精度和開發(fā)能力也是十分顯著的。

圖4 D=50,100時(shí)，實(shí)驗(yàn)收斂曲線（關(guān)于迭代時(shí)間）

根據(jù)圖4可得，BAABC算法無論在收斂速度還是在收斂精度上都優(yōu)于其他算法，且其突出性能是收斂速度快。BAABC算法不僅關(guān)于迭代次數(shù)收斂速度快，而且關(guān)于迭代時(shí)間收斂速度快。BAABC算法是真正意義上的收斂速度快。

BAABC算法不同于標(biāo)準(zhǔn)ABC算法，摒棄輪盤賭方式，同時(shí)加強(qiáng)了魯棒性。為了進(jìn)一步測(cè)試BAABC算法的魯棒性，本文設(shè)計(jì)了實(shí)驗(yàn)檢驗(yàn)BAABC算法對(duì)高維復(fù)雜問題的優(yōu)化效果，進(jìn)行了兩組實(shí)驗(yàn)，第一組設(shè)定維數(shù)200維，迭代次數(shù)1 000，搜索空間[-100,100]，運(yùn)行50次，第二組設(shè)定維數(shù)300，500，…，1 000維，迭代次數(shù)2 000，搜索空間[-100,100]，運(yùn)行50次，測(cè)試函數(shù)Rosenbrock、Ackley和Zakharov。運(yùn)行結(jié)果和文獻(xiàn)[13]中4種算法進(jìn)行對(duì)比，數(shù)據(jù)來自于文獻(xiàn)[13]。實(shí)驗(yàn)結(jié)果如表4所示，其中，MEAN代表均值；STD代表方差；OPT代表最優(yōu)值；WST代表最差值。當(dāng)維數(shù)為1 000維及2 000維時(shí)，BAABC算法的收斂性能如圖5、6所示。

由表4可知，BAABC算法在解決高維復(fù)雜優(yōu)化問題上，具有明顯的優(yōu)勢(shì)，優(yōu)化效果明顯優(yōu)于其他4種算法。當(dāng)維數(shù)為200維時(shí)，BAABC算法收斂精度最高。當(dāng)維數(shù)從300維到1 000維，對(duì)比BAABC算法的收斂效果，發(fā)現(xiàn)BAABC算法的收斂效果與問題維數(shù)無關(guān)，收斂精度基本上維持在10左右。從圖5，6看出，即便在維數(shù)2 000維的時(shí)候，BAABC算法仍然可以得到不錯(cuò)的收斂精度。可見，BAABC算法具有非常好的魯棒性，適合解決高維復(fù)雜優(yōu)化問題，如無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位問題、無線Mesh網(wǎng)絡(luò)QoS路由問題。

表4 5種算法和對(duì)比結(jié)果

圖5 BAABC算法對(duì)Rosenbrock的收斂性能

圖6 BAABC算法對(duì)Zakharov的收斂性能

6 結(jié)論

在標(biāo)準(zhǔn)ABC算法中，觀察蜂采用輪盤賭策略選擇蜜源。但是這種方式會(huì)出現(xiàn)大量的選擇失敗，這無疑是浪費(fèi)計(jì)算機(jī)資源的表現(xiàn)。鑒于標(biāo)準(zhǔn)ABC算法開發(fā)能力不足的情況，在觀察蜂階段，本文摒棄輪盤賭選擇策略，改進(jìn)觀察蜂的搜索方式，以提高算法的開發(fā)能力。BAABC算法摒棄輪盤賭策略，并通過引進(jìn)吸引子改變觀察蜂的搜索方式。所有觀察蜂以吸引子為中心等比例收縮，共同開發(fā)同一區(qū)域，從而提高了算法的開發(fā)能力。吸引子作為種群中心，所有觀察蜂向吸引子靠攏，集中開發(fā)一片區(qū)域，提高算法的開發(fā)能力。通過實(shí)驗(yàn)證明，該方法明顯提高了算法后期的局部開發(fā)能力。此外，在高維復(fù)雜優(yōu)化問題上，BAABC算法的優(yōu)化能力明顯高于對(duì)比算法，具有良好的魯棒性，適合在高維復(fù)雜優(yōu)化問題上推廣應(yīng)用。

[1]Karaboga D.An idea based on honey bee swarm for numerical optimization[R].Turkey：Erciyes University，2005：1-10.

[2]Karaboga D，Basturk B.On the performance of artificial bee colony algorithm[J].Applied Soft Computing，2008，8（1）：687-697.

[3]李俊清，潘全科，王法濤.求解混合流水線調(diào)度問題的離散人工蜂群算法[J].運(yùn)籌與管理，2015，24（1）：157-163.

[4]周遜，郭敏，馬邈.一種求解圖像分割問題的限速—離散蜂群優(yōu)化算法[J].計(jì)算機(jī)工程，2014，40（8）：212-216.

[5]Karaboga D，Basturk B.A powerful and efficient algorithm for numerical function optimization：Artificial Bee Colony algorithm[J].Journal of Global Optimization，2007，39（3）：459-471.

[6]暴勵(lì)，曾建潮.一種雙種群差分蜂群算法[J].控制理論與控制應(yīng)用，2011，28（2）：266-272.

[7]汪繼文，楊丹，邱劍鋒，等.改進(jìn)人工蜂群算法求解非線性方程組[J].安徽大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，38（3）：16-23.

[8]張?zhí)浪歼h(yuǎn).增強(qiáng)尋優(yōu)能力的自適應(yīng)人工蜂群算法[J].計(jì)算機(jī)應(yīng)用研究：2016，33（10）.

[9]Lv Li，Han Longzhe，F(xiàn)an Tanghuai，et al.Artificial bee colony algorithm with accelerating convergence[J].International Journal of Wireless and Mobile Computing，2016，10（1）：76-82.

[10]Sharma K，Gupta P C，Sharma H.Fully informed artificial bee colony algorithm[J].Journal of Experimental&Theoretical Artificial Intelligence，2016，28（1/2）：403-416.

[11]Pan Xiuqin，Lu Yong，Li Sumin，et al.An improved artificial bee colony with new search strategy[J].International Journal of Wireless and Mobile Computing，2015，9（4）：391-396.

[12]李國(guó)亮，魏振華，徐蕾.分階段搜索的改進(jìn)人工蜂群算法[J].計(jì)算機(jī)應(yīng)用，2015，35（4）：1057-1061.

[13]Amira B，Amer D，Salim C.A quantum-inspired artificial bee colony algorithm for numerical optimization[C]//Proceedings of International Symposium on Programming and Systems，Algiers，2013：81-88.

[14]Zhang Song，Liu Sanyang.A novel artificial bee colony algorithm for function optimization[J].Mathematical Problems in Engineering，2015：1-10.

[15]Sharma T K，Pant M.Improved search mechanism in ABC and its application in engineering[J].Journal of Engineering Science&Technology，2015，10（1）：111-133.

[16]江銘炎，袁東風(fēng).人工蜂群算法及其應(yīng)用[M].北京：科學(xué)出版社，2014：84-85.