一種改進(jìn)的人工蜂群算法研究

曹亞麗 余牧舟 楊俊峰 宋昕

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

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

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

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

1 ?人工蜂群算法

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

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

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

3 ?仿真實(shí)驗(yàn)分析

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

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

3.1.6 ?PSO算法

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

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

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

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

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

4 ?結(jié) ?語

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

參考文獻(xiàn)

[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ìn)方案[J].計(jì)算機(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ī)范知識(shí)引導(dǎo)的改進(jìn)人工蜂群算法[J].模式識(shí)別與人工智能，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] 李華，盧靜.改進(jìn)人工蜂群算法的無線傳感器網(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ìn)的人工蜂群算法[J].西南師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2018，43（7）：39?45.

[15] 劉曉芳，柳培忠，駱炎民，等.一種增強(qiáng)局部搜索能力的改進(jìn)人工蜂群算法[J].智能系統(tǒng)學(xué)報(bào)，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ìn)的人工蜂群算法：粒子蜂群算法[J].工程科學(xué)學(xué)報(bào)，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] 張志強(qiáng)，魯曉鋒，孫欽東，等.一種增強(qiáng)開發(fā)能力的改進(jìn)人工蜂群算法研究[J].計(jì)算機(jī)應(yīng)用，2018（12）：1?9.