曹亞麗 余牧舟 楊俊峰 宋昕

摘 ?要： 針對人工蜂群算法在更新策略中精度與穩(wěn)定性不高的問題，提出一種改進的人工蜂群算法。該改進的人工蜂群算法通過增加每次更新維度的個數(shù)來改善算法的精度，在文中所選擇的每次更新維度的個數(shù)為可行解維數(shù)的[12];同時，該算法選擇當(dāng)前適應(yīng)值最優(yōu)的蜂蜜源在其周圍進行鄰域搜索，避免了由于隨機性而帶來的算法精度降低問題。最后，比較改進的人工蜂群算法與經(jīng)典的粒子群算法，通過多個高維測試函數(shù)的仿真實驗表明，改進的人工蜂群算法比粒子群算法具有更高的精度和穩(wěn)定性，展現(xiàn)了更好的性能。

關(guān)鍵詞： 人工蜂群算法; 算法改進; 數(shù)據(jù)分析; 更新維度; 領(lǐng)域搜索; 仿真實驗

中圖分類號： TN919?34 ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標(biāo)識碼： A ? ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2020）12?0133?05

Abstract： In allusion to the problem that the artificial bee colony algorithm has low accuracy and stability in the update strategy， an improved artificial bee colony algorithm is proposed. The accuracy of the algorithm is improved by increasing the number of dimensions per update， and the selected number of dimensions per update is half of the feasible solution dimensions in this paper; the honeycomb source with the best adaptive value is chosen to conduct a neighbourhood search around it， which avoids the reducing the accuracy of the algorithm caused by the randomness. The simulation results with multi high?dimensional testing functions show that， in comparison with the classical particle swarm optimization algorithm， the improved artificial bee colony algorithm has a higher accuracy and stability， and show better performance.

Keywords： artificial bee colony algorithm; algorithm improvement; data analysis; update dimension; area search; simulation experiment

0 ?引 言

人工蜂群算法（ABC）通過模仿蜜蜂覓食時群體之間的相互作用求得最優(yōu)解，是一種有效的單目標(biāo)問題的解決方案。該算法在2005年由Karaboga首次提出，有三種類型的蜜蜂參與人工蜂群算法[1]，分別是雇傭蜂、跟隨蜂和偵察蜂。它們參與不同的搜索過程。雇傭蜂多次通過鄰域搜索在特定范圍內(nèi)鎖定蜜源的位置，并通過搖擺舞的方式將食物的相關(guān)信息傳遞給跟隨蜂[2]。搖擺舞中包含的信息有食物的數(shù)量和與蜂窩之間的間距等信息。蜜蜂覓食過程如圖1所示，在ABC中，雇傭蜂的數(shù)量與食物位置數(shù)量相同，即食物與雇傭蜂是一一對應(yīng)的。每個蜜源位置坐標(biāo)即代表優(yōu)化問題的解坐標(biāo)。蜜源的數(shù)量對應(yīng)的是蜜源的適應(yīng)值。蜜源數(shù)量越大，可行解的適應(yīng)值越?。▎文繕?biāo)最小化優(yōu)化問題），可行解質(zhì)量越高。當(dāng)雇傭蜂多次位置未更新時，說明該位置陷入了局部最優(yōu)值，雇傭蜂變?yōu)閭刹旆洌ㄟ^局部搜索確定新蜜源位置[3]。跟隨蜂依據(jù)各個雇傭蜂所供給的關(guān)于食物的信息，按照比例與概率選擇蜜源，概率越大，代表食物越多，在各個跟隨蜂選定相應(yīng)雇傭蜂之后，執(zhí)行鄰域搜索，確定蜜源位置。在重復(fù)循環(huán)多次上述步驟之后，跟隨蜂中適應(yīng)值最小食物源位置就是優(yōu)化問題的最優(yōu)可行解[4]。

現(xiàn)階段，已有許多文獻對人工蜂群算法的改進和應(yīng)用進行了研究。文獻[5]將人工蜂群算法與前饋人工神經(jīng)網(wǎng)絡(luò)（FF?ABC）相結(jié)合，用于混凝土中氯化物的滲透預(yù)測。文獻[6]針對柔性生產(chǎn)線的問題，提出了一種基于帕累托的人工蜂群算法（PGABC）。該算法可以得到具有三種不同導(dǎo)向機構(gòu)的帕累托近似最優(yōu)解。文獻[7]提出了一種多目標(biāo)人工蜂群算法，該算法集成了兩種性能增強方案，首次解決了負載平衡和傳輸延遲的網(wǎng)絡(luò)編碼問題。在Khan的研究論文中，采用更新規(guī)則和k?opt操作對人工蜂群算法進行了改進，解決了旅行商問題[8]。Choong在人工蜂群算法中應(yīng)用了一種超啟發(fā)式方法，即改進了選擇函數(shù)（MCF），該算法可以自動調(diào)節(jié)雇傭蜂和跟隨蜂的鄰域搜索選擇[9]。文獻[10]針對蒸汽驅(qū)注方案的優(yōu)化問題，提出了一種基于改進人工蜂群算法的蒸汽驅(qū)注方案優(yōu)化方法。文獻[11]基于子空間分解（ISD）和人工蜂群（ABC）算法，提出了一種稱為ISD?ABC的帶選擇技術(shù)，解決了HSI分類中維數(shù)減少的問題。

1 ?人工蜂群算法

在人工蜂群算法（ABC）中，人工蜂群包含三種類別的蜜蜂。它們分別是雇傭蜂、跟隨蜂和觀察蜂。其中雇傭蜂和跟隨蜂的數(shù)量相同，并且分別占蜂群總數(shù)的[12]。每個雇傭蜂對應(yīng)一個蜂蜜源，這些雇傭蜂的主要工作是尋找并記錄與之對應(yīng)的蜂蜜源。然后將蜂蜜源的相關(guān)信息通過圓擺舞的方式傳遞給跟隨蜂，跟隨蜂就根據(jù)這些信息來選擇蜂蜜源[12]。當(dāng)雇傭蜂對應(yīng)的蜂蜜源的位置多次未改變，雇傭蜂變?yōu)橛^察蜂，通過局部搜索確定新蜂蜜源的位置[13?15]。

在該算法中，每個蜂蜜源位置坐標(biāo)表示一個可行解。本文給出了每個蜂蜜源的適應(yīng)值[fit（i）]，該值用于評估每個蜂蜜源的花蜜量[16]。在算法每一次循環(huán)中，雇傭蜂都通過鄰域搜索尋找每個蜂蜜源，并計算每個蜂蜜源對應(yīng)的適應(yīng)值。根據(jù)雇傭蜂傳遞的信息（即每個蜂蜜源的適應(yīng)值），跟隨蜂通過一定的概率來選擇蜂蜜源，并在選擇的蜂蜜源周圍尋找新的蜂蜜源，并計算它們的適應(yīng)值[17?19]。

這種學(xué)習(xí)策略使得雇傭蜂和跟隨蜂在當(dāng)前最優(yōu)的蜂蜜源周圍進行鄰域搜索，提高了搜索的精度，并且每次的搜索過程是多維度的，提高了搜索的速度。圖3是改進的人工蜂群算法在每一個維度上的潛在搜索空間。

3 ?仿真實驗分析

3.1 ?測試函數(shù)

為了測試改進ABC算法的求解精度與收斂速度[20?21]，采用5個標(biāo)準(zhǔn)測試函數(shù)：Sphere函數(shù)、Rosenbrock 函數(shù)、Rastrigin函數(shù)、Griewank 函數(shù)和Ackley 函數(shù)，并與粒子群算法（PSO）進行了比較。

3.1.6 ?PSO算法

粒子群優(yōu)化算法（PSO）是一種進化計算技術(shù)（Evolutionary Computation），1995 年由Eberhart和Kennedy提出，源于對鳥群捕食的行為研究。該算法最初是受到飛鳥集群活動的規(guī)律性啟發(fā)，進而利用群體智能建立的一個簡化模型。粒子群算法在對動物集群活動行為觀察基礎(chǔ)上，利用群體中的個體對信息的共享使整個群體的運動在問題求解空間中產(chǎn)生從無序到有序的演化過程，從而獲得最優(yōu)解。

3.2 ?實驗結(jié)果

在仿真實驗中，為了保證結(jié)果的公平與有效性，對改進的ABC算法與PSO算法進行了初值的設(shè)置，其中，蜂群數(shù)量與粒子群數(shù)量大小均設(shè)置為100，算法的運算次數(shù)均為50次。每次算法執(zhí)行中，循環(huán)的次數(shù)均設(shè)置為1 500次。在這兩種算法中就5個測試函數(shù)分別運行50次后，求平均值得到了改進的ABC算法與PSO算法在50維空間與100維空間的數(shù)據(jù)結(jié)果如表1和表2所示。

表1、表2中，均值分別代表兩種算法就每個函數(shù)運行50次后的平均水平，且能最大程度地降低偶然誤差的影響，因此將均值作為兩種算法的評價指標(biāo)，并將該結(jié)果數(shù)字在表中加粗。均值越接近理論值，則代表該算法的優(yōu)化效果越好。根據(jù)表中的數(shù)據(jù)可知，在50維和100維的空間中，對于Sphere，Rosenbrock，Rastrigin，Griewank和Ackley 函數(shù)的優(yōu)化結(jié)果，改進的ABC算法較PSO算法更接近理論值。由此可見，改進的ABC算法有更好的求解精度。

5個測試函數(shù)的仿真曲線如圖4～圖8所示。根據(jù)圖4 ～圖8運行結(jié)果可知，對于Sphere 函數(shù)，改進的ABC算法在大約第250次循環(huán)時達到1，PSO算法在大約第100次循環(huán)時穩(wěn)定到1.5;對于Rosenbrock 函數(shù)，改進的ABC算法在大約第500次循環(huán)時穩(wěn)定在160，PSO算法在大約第100次循環(huán)時穩(wěn)定到200;對于Rastrigin 函數(shù)，改進的ABC算法在大約第500次循環(huán)時達到80，PSO算法在大約第100次循環(huán)時穩(wěn)定到200;對于Griewank 函數(shù)，改進的ABC算法在大約第500次循環(huán)時達到0.01，PSO算法在大約第100次循環(huán)時穩(wěn)定到0.025;對于Ackley 函數(shù)，改進的ABC算法在大約第400次循環(huán)時達到0.5，PSO算法在大約第50次循環(huán)時穩(wěn)定到2。由此可見，改進的ABC算法較PSO算法展示了更好的求解精度與穩(wěn)定性，但在收斂效果方面略有不足，這也是以后有待于改進的地方。

4 ?結(jié) ?語

為了解決這個問題，本文提出了一個改進的人工蜂群算法。通過增加每次更新的維度個數(shù)來改善算法的穩(wěn)定性，并且選擇當(dāng)前適應(yīng)值最優(yōu)的蜂蜜源周圍進行鄰域搜索來提高算法的精度，但在收斂速度方面存在不足，有待于進一步改善?？傊疚膶⑺岢龅乃惴ㄅc粒子群算法在高維空間進行比較，通過多組測試函數(shù)的仿真表明所提出的算法具有較好的性能。

參考文獻

[1] KIRAN M S， HAKLI H， GUNDUZ M， et al. Artificial bee colony algorithm with variable search strategy for continuous optimization [J]. Information sciences， 2015， 300： 140?157.

[2] 梁靜，葛宇，冉曉娟，等.一種人工蜂群算法改進方案[J].計算機應(yīng)用研究，2015，32（11）：3295?3299.

[3] ZHU G P， KWONG S. Gbest?guided artificial bee colony algorithm for numerical function optimization [J]. Applied mathematics & computation， 2010（7）： 3166?3173.

[4] 林小軍，葉東毅.一種帶規(guī)范知識引導(dǎo)的改進人工蜂群算法[J].模式識別與人工智能，2013，26（3）：307?314.

[5] MEYSAM N， NADER G， MEHDI N. Modeling chloride penetration in self?consolidating concrete using artificial neural network combined with artificial bee colony algorithm [J]. Journal of building engineering， 2019， 22： 216?226.

[6] YUE L， GUAN Z L， ZHANG L， et al. Multi?objective lotsizing and scheduling with material constraints in flexible parallel lines using a Pareto based guided artificial bee colony algorithm [J]. Computers & industrial engineering， 2018（16）： 659?680.

[7] XING H L， SONG F H， YAN L S， et al. On multicast routing with network coding： a multiobjective artificial bee colony algorithm [J]. China communication， 2019， 16（2）： 170?186.

[8] KHAN I， MAITI M K. A swap sequence based Artificial Bee Colony algorithm for traveling salesman problem [J]. Swarm and evolutionary computation， 2019， 44： 428?438.

[9] CHOONG S S， WONG L P， LIM C P. An artificial bee colony algorithm with a modified choice function for the traveling salesman problem [J]. Swarm and evolutionary computation， 2019， 44： 622?635.

[10] NI H M， LIU Y J， FAN Y C. Optimization of injection scheme to maximizing cumulative oil steam ratio based on improved artificial bee colony algorithm [J]. Journal of petroleum science and engineering， 2019， 173： 371?380.

[11] XIE F D， LI F F， LEI C K， et al. Unsupervised band selection based on artificial bee colony algorithm for hyper?spectral image classification [J]. Applied soft computing， 2019， 75： 428?440.

[12] 李華，盧靜.改進人工蜂群算法的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化[J].現(xiàn)代電子技術(shù)，2018，41（3）：14?18.

[13] MUSTAFA Servet Kiran， HUSEYIN Hakli， MESUT Gunduz， et al. Artificial bee colony algorithm with variable search strategy for continuous optimization [J]. Information sciences， 2015， 300： 140?157.

[14] 田屏.一種基于混沌搜索改進的人工蜂群算法[J].西南師范大學(xué)學(xué)報（自然科學(xué)版），2018，43（7）：39?45.

[15] 劉曉芳，柳培忠，駱炎民，等.一種增強局部搜索能力的改進人工蜂群算法[J].智能系統(tǒng)學(xué)報，2017，12（5）：684?693.

[16] MARJAN Mernik， SHIH Hsi Liu， DERVIS Karaboga， et al. On clarifying misconceptions when comparing variants of the artificial bee colony algorithm by offering a new implementation [J]. Information sciences， 2015， 291： 115?127.

[17] XUE Yu， JIANG Jiongming， ZHAO Binping， et al. Aself?adaptive ?artificial bee colony algorithm ?based on ?global best for global optimization [J]. Soft computing， 2017（8）： 1?18.

[18] 王繼超，李擎，崔家瑞，等.一種改進的人工蜂群算法：粒子蜂群算法[J].工程科學(xué)學(xué)報，2018，40（7）：871?881.

[19] LIN Qinzhen， ZHU Miaomiao， LI Genghui， et al. A novel artificial bee colony algorithm with local and global information interaction [J]. Applied soft computing journal， 2018， 62： 702?735.

[20] 楊慧婷，楊文忠，殷亞博，等.基于深度信念網(wǎng)絡(luò)的K?means 聚類算法研究[J].現(xiàn)代電子技術(shù)，2019，42（8）：145?150.

[21] 張志強，魯曉鋒，孫欽東，等.一種增強開發(fā)能力的改進人工蜂群算法研究[J].計算機應(yīng)用，2018（12）：1?9.