求解高維復雜優化問題的改進人工蜂群算法

賀桂嬌 ，周樹亮 ，馮冬青

1.廣州現代信息工程職業技術學院，廣州 510663

2.鄭州大學 電氣工程學院，鄭州 450001

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

1 引言

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

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

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

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

2 標準人工蜂群算法

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

2.1 初始化

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

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

2.2 蜂群進化階段

雇傭蜂在當前依附的蜜源附近進行鄰域搜索，尋找更好的蜜源，如果發現比當前更優秀的蜜源，更新當前蜜源。雇傭蜂搜索方程式如式（2）所示：

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

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

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

當雇傭蜂在迭代閾值limit范圍內，未找到更好的蜜源，則雇傭蜂轉變為偵查蜂，進行全局搜索，按照式（4）產生新解。

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

3 求解高維復雜優化問題的改進人工蜂群算法

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

表1 觀察蜂選擇失敗的次數

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

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

圖1 BAABC搜索示意圖

BAABC算法分兩種情況得到吸引子cr。當種群個體是全局最優解，吸引子cr根據式（5）得到，否則吸引子cr根據式（6）得到：

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

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

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

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

式中，α是[0，1]之間的隨機數；?ij是[-1,1]之間的隨機數；xg,j是全局最優解 j維。搜索方程加入全局最優解的引導，增強了算法的開發能力。

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

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

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

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

步驟4偵查蜂階段：若存在放棄的蜜源，該處的雇傭蜂變為偵查蜂，根據式（4）產生新解。

步驟5判斷是否滿足循環終止條件，如果滿足停止循環，輸出結果，否則執行步驟2。

5 仿真實驗和結果分析

為了驗證改進算法的有效性，本文中選用了9個經典測試函數。

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

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

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

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

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

圖2 D=100時，實驗收斂曲線（關于迭代次數）

圖3 D=50時，實驗收斂曲線（關于迭代次數）

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

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

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

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

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

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

表4 5種算法和對比結果

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

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

6 結論

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

[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]李俊清，潘全科，王法濤.求解混合流水線調度問題的離散人工蜂群算法[J].運籌與管理，2015，24（1）：157-163.

[4]周遜，郭敏，馬邈.一種求解圖像分割問題的限速—離散蜂群優化算法[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].控制理論與控制應用，2011，28（2）：266-272.

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

[8]張泰，屠思遠.增強尋優能力的自適應人工蜂群算法[J].計算機應用研究：2016，33（10）.

[9]Lv Li，Han Longzhe，Fan 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].計算機應用，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]江銘炎，袁東風.人工蜂群算法及其應用[M].北京：科學出版社，2014：84-85.