具有自適應(yīng)趨向性和引導(dǎo)因子的人工蜂群算法*

臧培荃，孫晨驁，顧曉峰，吳 濱，周長喜

(1.輕工過程先進控制教育部重點實驗室，江蘇 無錫 214122；2.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

具有自適應(yīng)趨向性和引導(dǎo)因子的人工蜂群算法*

臧培荃，孫晨驁，顧曉峰，吳 濱，周長喜

(1.輕工過程先進控制教育部重點實驗室，江蘇 無錫 214122；2.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122)

針對人工蜂群算法中存在的收斂速度慢、尋優(yōu)精度低的問題，提出了一種改進的人工蜂群算法。該算法將自適應(yīng)趨向性加入雇傭蜂的搜索方案中，同時在觀察蜂的搜索方案中加入引導(dǎo)因子。通過雇傭蜂對優(yōu)秀蜜源的動態(tài)趨向搜索以及觀察蜂在引導(dǎo)因子引領(lǐng)下的協(xié)同搜索，顯著提高了算法的局部搜索能力。基于八個標(biāo)準(zhǔn)測試函數(shù)的仿真結(jié)果表明，與基本人工蜂群算法相比，改進后的算法在尋優(yōu)精度和收斂速度方面均有明顯提升。

人工蜂群算法；局部搜索；搜索方案；自適應(yīng)趨向性；引導(dǎo)因子

1 引言

Karaboga D[1]于2005年提出的人工蜂群ABC(Artificial Bee Colony)算法是一種模擬蜜蜂采蜜行為的新型群智能算法，具有結(jié)構(gòu)簡單、參數(shù)設(shè)置少及全局尋優(yōu)能力強等特點，被廣泛應(yīng)用于無約束優(yōu)化問題[2]。但是，與其他群智能算法一樣，傳統(tǒng)ABC算法在求解函數(shù)優(yōu)化問題時也存在計算精度低、收斂速度慢、適應(yīng)范圍小等問題。針對這些缺點，不少學(xué)者提出了改進方案[3～7]。例如，文獻(xiàn)[3]提出在原搜索區(qū)域的基礎(chǔ)上，根據(jù)尋優(yōu)結(jié)果調(diào)整搜索空間，縮小搜索區(qū)域，并利用混沌變量的內(nèi)在隨機性和遍歷性，跳出局部最優(yōu)，最終獲得最優(yōu)解；文獻(xiàn)[4]提出將混沌局部搜索算子嵌入到蜂群算法框架中，以實現(xiàn)在最優(yōu)食物源周圍進行局部搜索，并隨著進化代數(shù)增加逐步縮小搜索范圍，提高局部搜索能力；文獻(xiàn)[5]則指出，可利用全局最優(yōu)解和個體極值的信息來改進人工蜂群算法中的搜索模式，并引入異步變化學(xué)習(xí)因子，維持全局和局部搜索的平衡；文獻(xiàn)[6]利用ABC算法求解單模式資源受限項目調(diào)度問題，實現(xiàn)了ABC算法在組合優(yōu)化中的應(yīng)用；文獻(xiàn)[7]總結(jié)了人工蜂群算法解決組合優(yōu)化問題的框架，并應(yīng)用于解決旅行商問題TSP(Travelling Salesman Problem)和背包問題?？梢?，改進ABC算法的局部搜索能力，對提高其性能和擴大其適用范圍具有重要意義。本文提出了一種具有自適應(yīng)趨向性和引導(dǎo)因子的人工蜂群算法ZABC(Zealous Artificial Bee Colony)，有助于提高局部搜索能力，改善算法的尋優(yōu)精度和收斂速度。

2 人工蜂群算法

ABC算法中將蜜蜂分為雇傭蜂(Employed Bees)、觀察蜂(Onlooker Bees)和偵察蜂(Scout Bees)三種類型[8]，蜜蜂尋找優(yōu)質(zhì)蜜源的過程就是算法搜尋最優(yōu)解的過程。其中，蜜源位置代表被優(yōu)化問題的候選解，蜜源的花蜜量代表相應(yīng)解的適應(yīng)度值。求解一個函數(shù)f(X)的最小值優(yōu)化問題的過程如下。

假設(shè)初始種群含有M個解(M個蜜源)，每個解Xi(i=1,2,…,M)是一個D維向量，其中f(X)即被優(yōu)化問題的目標(biāo)函數(shù)。

(1)雇傭蜂負(fù)責(zé)進行全局搜索：即隨機選擇蜜源Xi中任意的一維分量按公式(1)進行變異，產(chǎn)生新蜜源Xi′。由貪婪選擇機制[9]確定蜜源，即比較前后蜜源的優(yōu)劣，若新蜜源含蜜量高于舊蜜源，則替換；否則仍保留舊蜜源。

(1)

(2)觀察蜂在部分優(yōu)質(zhì)蜜源附近作局部搜索：觀察蜂根據(jù)公式(2)計算蜜源Xi的選擇概率Pi，然后針對選中的Xi執(zhí)行與雇傭蜂相同的變異與選擇操作[10]。

(2)

其中，fiti是Xi對應(yīng)的適應(yīng)度函數(shù)值。

(3)偵察蜂處理進化停滯的蜜源：若某蜜源Xi經(jīng)過指定的lim次循環(huán)后仍未得到改善，則放棄該蜜源，同時由偵察蜂通過公式(3)隨機搜索一個新蜜源來代替該蜜源[11]。

Xi=Xmin+φ×(Xmax-Xmin)

(3)

其中，φ為[0,1]的隨機數(shù)，Xmax和Xmin分別為蜜源解空間的上、下邊界。

3 改進的人工蜂群算法

在ABC算法的尋優(yōu)過程中，雇傭蜂負(fù)責(zé)全局搜索，觀察蜂主要在優(yōu)質(zhì)蜜源附近作局部搜索，促使優(yōu)秀個體逐步向最優(yōu)位置演化[12]。本文針對雇傭蜂和觀察蜂搜索行為中存在的不足進行討論，并提出改進方案。

3.1 具有自適應(yīng)趨向性的雇傭蜂搜索模式

ABC算法中，雇傭蜂在蜜源附近按公式(1)隨機選擇的新方向進行變異，雖然隨機方向的選擇在一定程度上擴大了搜索空間，但盲目的搜索會導(dǎo)致無效搜索次數(shù)的增加，進而降低收斂速度。另外，搜索后期蜜蜂已處于最優(yōu)蜜源附近，若仍以R×(xij-xkj)大小的隨機范圍進行搜索，可能導(dǎo)致蜜蜂躍過最優(yōu)蜜源區(qū)域，造成算法搜尋精度不高。

(4)

3.2 具有引導(dǎo)因子的觀察蜂搜索模式

ABC算法中，觀察蜂在部分優(yōu)質(zhì)蜜源附近隨機選擇一維分量進行局部搜索，搜得的優(yōu)質(zhì)蜜源和劣質(zhì)蜜源是等概率的[13]。然而，只有比原蜜源優(yōu)秀，新蜜源才會替代原蜜源。因此，50%份額劣質(zhì)蜜源的引入，將降低算法的尋優(yōu)精度和收斂速度。

為了提高觀察蜂的搜索能力，提出一種具有引導(dǎo)因子的觀察蜂搜索方案。具體思路是：選擇每只雇傭蜂個體到目前為止搜尋到的最好位置Xp為個體引導(dǎo)因子；選擇觀察蜂群體到目前為止搜尋到的蜜源中的最優(yōu)蜜源Xg為整體引導(dǎo)因子。通過引入引導(dǎo)因子，使觀察蜂群體內(nèi)彼此存在著信息交流，避免了孤立個體搜索存在的盲目性大、穩(wěn)定性差等不足。另外，引導(dǎo)因子本身亦為優(yōu)質(zhì)蜜源所處位置，對于觀察蜂搜索有較好的方向指引作用，算法收斂速度更快。

觀察蜂在隨機維度j上的搜索模式如下：

(5)

4 改進的ZABC算法的實驗流程

步驟1初始時刻隨機生成M個可行解(X1j，X2j，…，XMj)，j∈{1，2，…，D}。設(shè)置進化停滯控制參數(shù)lim，最大迭代次數(shù)tmax和在有利方向最大引導(dǎo)步數(shù)Ns的值。

步驟2雇傭蜂在當(dāng)前蜜源Xi附近根據(jù)公式(4)逐維搜索。若新蜜源更優(yōu)，則對其更新并將該維的搜索方向看作具有引導(dǎo)性的有利方向，沿該方向繼續(xù)向前搜索，直至適應(yīng)度值不再改善或達(dá)到Ns。

步驟3選擇公式(5)的個體引導(dǎo)因子Xp和整體引導(dǎo)因子Xg。

步驟4根據(jù)公式(2)計算蜜源被選擇的概率Pi，觀察蜂在選中的蜜源周圍根據(jù)公式(5)逐維進行變異和更新。

步驟5偵察蜂檢查是否存在連續(xù)lim次迭代都沒有更新的蜜源，若存在，則由偵察蜂根據(jù)公式(3)隨機產(chǎn)生一個新的蜜源。

步驟6記錄到目前為止的最優(yōu)蜜源。

步驟7判斷是否達(dá)到最大迭代次數(shù)tmax，若滿足，則輸出最優(yōu)蜜源，否則轉(zhuǎn)至步驟2。

5 算法實例測試及分析

5.1 測試函數(shù)選擇

為了評估本文所提算法的性能，從尋優(yōu)精度、收斂速度和算法穩(wěn)定性三個方面對ZABC算法、標(biāo)準(zhǔn)ABC算法和文獻(xiàn)[14]提出的改進ABC(Best-so-far ABC)算法進行對比。選用下述八個典型測試函數(shù)[15]進行數(shù)值實驗。

(1)Step函數(shù)：

(2)Schwefel’s函數(shù)：

(3)Rastrigin函數(shù)：

(4)Ackley函數(shù)：

(5)Griewank函數(shù)：

(6)Rosenbrock函數(shù)：

(7)Sphere函數(shù)：

(8)Levy函數(shù)：

其中，單峰值函數(shù)f1、f2、f7的定義域內(nèi)只有一個極值點，常用來測試算法收斂速度和尋優(yōu)精度[16]；多峰值函數(shù)f3、f4、f5、f8的定義域內(nèi)有許多局部極值點，常用來測試算法避免早熟和全局尋優(yōu)的能力；f6為單峰值、非凸、病態(tài)函數(shù)，較為特殊，函數(shù)變量間有很強的關(guān)聯(lián)性，常用來評價優(yōu)化算法的性能；x*為測試函數(shù)的最優(yōu)解。

5.2 實驗結(jié)果與分析

實驗參數(shù)設(shè)置為：種群個體數(shù)目SN=90，最大進化代數(shù)tmax=1 000，最大引導(dǎo)步數(shù)Ns=3，進化停滯控制參數(shù)lim=100。三種算法均在CPU主頻2.4 GHz、內(nèi)存為2 GB的實驗硬件環(huán)境下進行測試運行。對比實驗中，八個測試函數(shù)均在空間維度D=30的情況下分別進行30次獨立實驗。每個測試函數(shù)的最優(yōu)值、最差值、平均最優(yōu)值、方差和平均時耗如表1所示。圖1～圖8給出了八個測試函數(shù)的平均適應(yīng)度進化曲線。

由表1中的最優(yōu)值、最差值和平均最優(yōu)值可看出，對于f1和f3，本文提出的ZABC算法收斂達(dá)到了理論最優(yōu)值0；對于其余測試函數(shù)，ZABC算法的尋優(yōu)精度也明顯高于另外兩種算法。由方差可看出，對于f1，三種算法穩(wěn)定性相同；對于其他測試函數(shù)，ZABC算法方差值有顯著的提升，具有更好的穩(wěn)定性。另外，由平均時耗可看出，ZABC算法達(dá)到穩(wěn)定收斂精度所需的平均運行時間均低于另外兩種算法，表明其可以更快地完成尋優(yōu)過程。

由圖1～圖8的平均適應(yīng)度進化曲線可以看出，ZABC算法在單峰函數(shù)、多峰函數(shù)和非凸病態(tài)函數(shù)的測試中，達(dá)到穩(wěn)定收斂精度所需的迭代次數(shù)遠(yuǎn)小于另外兩種算法，且收斂精度更高。雖然引入自適應(yīng)趨向性和引導(dǎo)因子一定程度上增加了算法的復(fù)雜度和單次迭代的計算量，使算法單次運行時間增大，但由于ZABC算法達(dá)到穩(wěn)定高收斂精度所需的迭代次數(shù)更少，使得完成整個搜尋過程的耗時大為減少。這是因為自適應(yīng)趨向性和引導(dǎo)因子在尋蜜過程中起到了較好的方向指引作用，減少了無效搜索的比重，加快了收斂速度；而搜索步長的動態(tài)調(diào)整，也在一定程度上減少了搜索后期蜜蜂因躍過最優(yōu)值而重新搜索的行為，提高了搜索精度，從而獲得了更佳的搜索性能。

Table 1 Function test results of the three different ABC algorithms表1 三種不同ABC算法的函數(shù)測試結(jié)果

Figure 1 Evolution curve of Step function

Figure 2 Evolution curve of Schwefel’s function

Figure 3 Evolution curve of Rastrigin function

Figure 4 Evolution curve of Ackley function

Figure 5 Evolution curve of Griewank function

Figure 6 Evolution curve of Rosenbrock function

Figure 7 Evolution curve of Sphere function

6 結(jié)束語

為了解決ABC算法局部搜索能力差、收斂慢、尋優(yōu)差的問題，針對傳統(tǒng)ABC算法中雇傭蜂、觀察蜂各自搜索方案的不足，通過在雇傭蜂搜索方案中引入自適應(yīng)趨向性，在觀察蜂搜索方案中加入引導(dǎo)因子，提出了一種改進的人工蜂群算法。基于測試函數(shù)的仿真結(jié)果表明，提出的ZABC算法具有更快的收斂速度和更高的收斂精度。

[1] Karaboga D. An idea based on honey bee swarm for numerical optimization:Technical Report-TR06[R]. Kayseri: Computer Engineering Department,Engineering Faculty,Erciyes Unversity,2005.

[2] Karaboga D,Basturk B. On the performance of artificial bee colony (ABC) algorithm[J]. Applied Soft Computing,2008,8 (1): 687-697.

[3] Bao Li,Zeng Jian-chao. Self-adapting search space chaos-artificial bee colony algorithm[J]. Application Research of Computers,2010,27(4): 1331-1335.(in Chinese)

[4] Wang Xiang, Li Zhi-yong. Artificial bee colony algorithm based on chaos local search operator[J]. Computer Applications,2012,32(4): 1033-1036.(in Chinese)

[5] Wang Hui-ying,Liu Jian-jun,Wang Quan-zhou. Modified artificial bee colony algorithm for numerical function optimization[J]. Computer Engineering and Applications,2012,48(19): 36-39. (in Chinese)

[6] Akbari R,Zeighami V,Ziarati K. Artificial bee colony for resource constrained project scheduling problem[J]. International Journal of Industrial Engineering Computations,2011,2(1):45-60.

[7] Zheng Wei,Liu Jing,Zeng Jian-chao. The research and application of artificial bee colony algorithm in combinatorial optimization[J]. Journal of Taiyuan University of Science and Technology, 2010,31(6): 467-471.

[8] Bader G D,Donaldson I,Wolting C,et al. BIND-the biomolecular interaction network database[J]. Nucleic Acids Research,2004,31(1): 242-245.

[9] Wang Hui. Artificial bee colony algorithm with sharing factor[J]. Computer Engineering,2011,11(4): 139-142. (in Chinese)

[10] Kang Fei, Li Jun-jie, Ma Zhen-yue. Rosenbrock artificia1 bee colony algorithm for accurate global optimization of numerical functions[J]. Information Sciences,2011,181(16): 3508-353l.

[11] Wang Zhi-gang,Xia Hui-ming. An artificial bee colony algorithm for the vehicle routing problem[J]. Computer Engineering & Science,2014,36(6): 1088-1094.(in Chinese)

[12] Karaboga D,Akay B. A comparative study of artificial bee colony algorithm[J]. Applied Mathematics and Computation,2009,214(1): 108-132.

[13] Ning Ai-ping,Zhang Xue-ying. Convergence analysis of artificial bee colony algorithm[J]. Control and Decision,2013,28(10): 1554-1558.(in Chinese)

[14] Banharnsakun A, Achalakul T, Sirinaovakul B. The best-so-far selection in artificial bee colony a1gorithm[J]. Applied Soft Computing,2011,11(2): 2888-2901.

[15] Zhang Yin-xue,Tian Xue-min,Cao Yu-ping. Artificial bee colony algorithm with modified search strategy[J]. Computer Applications,2012,32(12): 3326-3330.(in Chinese)

[16] Zhao Liang-hui,Wang Tian-qing. A bee colony optimization algorithm for clustering-constraint scheduling[J]. Computer Engineering & Science,2011,33(11): 84-89.(in Chinese)

附中文參考文獻(xiàn):

[3] 暴勵,曾建潮. 自適應(yīng)搜索空間的混沌蜂群算法[J]. 計算機應(yīng)用研究,2010,27(4):1331-1335.

[4] 王翔,李志勇. 基于混沌局部搜索算子的人工蜂群算法[J]. 計算機應(yīng)用,2012,32(4):1033-1036.

[5] 王慧穎,劉建軍,王全洲. 改進的人工蜂群算法在函數(shù)優(yōu)化問題中的應(yīng)用[J]. 計算機工程與應(yīng)用,2012,48(19):36-39.

[7] 鄭偉,劉靜,曾建潮. 人工蜂群算法及其在組合優(yōu)化中的應(yīng)用研究[J]. 太原科技大學(xué)學(xué)報,2010,31(6):467-471.

[9] 王輝. 一種帶共享因子的人工蜂群算法[J]. 計算機工程,2011,11(4):139-142.

[11] 王志剛,夏慧明. 求解車輛路徑問題的人工蜂群算法[J]. 計算機工程與科學(xué),2014,36(6):1088-1094.

[13] 寧愛平,張雪英. 人工蜂群算法的收斂性分析[J]. 控制與決策,2013,28(10):1554-1558.

[15] 張銀雪,田學(xué)民,曹玉蘋. 改進搜索策略的人工蜂群算法[J]. 計算機應(yīng)用,2012,32(12):3326-3330.

[16] 趙良輝,王天擎. 蜂群算法解決集約束調(diào)度問題[J]. 計算機工程與科學(xué),2011,33(11):84-89.

臧培荃(1989-),男,山東萊西人，碩士生，研究方向為嵌入式智能研究。E-mail:986025648@qq.com

ZANG Pei-quan,born in 1989,MS candidate,his research interest includes research of embedded intelligence.

孫晨驁(1990-),男，浙江金華人，碩士生，研究方向為嵌入式智能。E-mail:517818554@qq.com

SUN Chen-ao,born in 1990,MS candidate,his research interest includes embedded intelligence.

An artificial bee colony algorithm with adaptive chemotaxis and guiding factors

ZANG Pei-quan,SUN Chen-ao,GU Xiao-feng,WU Bin，ZHOU Chang-xi

(1.Key Laboratory of Advanced Process Control for Light Industry (Ministry of Education,Wuxi 214122;2.School of Internet of Things Engineering,Jiangnan University,Wuxi 214122,China)

We propose an improved artificial bee colony (ABC) algorithm to overcome the drawbacks of slow convergence rate and low optimization precision of the conventional ABC algorithm. The self-adaptive chemotaxis and guiding factors are introduced into the search schemes of employed bees and onlooker bees, respectively. Under the guidance of the guiding factors, the local search capability is significantly improved due to the employed bees’ dynamic search for the high quality nectar sources and the onlooker bees’ cooperative search for the better nectar sources. Simulation results based on the eight standard functions show that the improved ABC algorithm is superior to the conventional one in both computational accuracy and convergence rate.

artificial bee colony algorithm;local search;search scheme;self-adaptive chemotaxis;guiding factor

1007-130X(2015)09-1692-06

2014-09-22;

2014-12-22基金項目：中央高?；究蒲袠I(yè)務(wù)費專項資金資助項目(JUSRP51323B)；江蘇省科技廳產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金資助項目(BY2013015-19)；江蘇高校優(yōu)勢學(xué)科建設(shè)工程資助項目(PAPD)

TP301.6

A

10.3969/j.issn.1007-130X.2015.09.016

通信地址：214122 江蘇省無錫市江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院

Address:School of IoT Engineering,Jiangnan University,Wuxi 214122,Jiangsu,P.R.China