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

賀桂嬌 ，周樹亮 ，馮冬青

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

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

3.中國中鐵工程裝備集團有限公司，鄭州 450016

1 引言

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

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

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

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

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

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

2.1 初始化

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

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

2.2 蜂群進化階段

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

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

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

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

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

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

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

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

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

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

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

圖1 BAABC搜索示意圖

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

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

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

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

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

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

4 改進人工蜂群算法BAABC的流程步驟

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

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

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

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

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

5 仿真實驗和結(jié)果分析

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

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

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

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

表2 K值對實驗結(jié)果（平均值）的影響

表3 D=100,D=50,5種對比算法的實驗結(jié)果

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

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

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

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

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

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

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

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

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

圖5 BAABC算法對Rosenbrock的收斂性能

圖6 BAABC算法對Zakharov的收斂性能

6 結(jié)論

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

[4]周遜，郭敏，馬邈.一種求解圖像分割問題的限速—離散蜂群優(yōu)化算法[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]暴勵，曾建潮.一種雙種群差分蜂群算法[J].控制理論與控制應(yīng)用，2011，28（2）：266-272.

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

[8]張?zhí)浪歼h.增強尋優(yōu)能力的自適應(yīng)人工蜂群算法[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]李國亮，魏振華，徐蕾.分階段搜索的改進人工蜂群算法[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.