一種增強局部搜索能力的改進人工蜂群算法

劉曉芳，柳培忠，駱炎民，范宇凌

(1. 華僑大學 工學院，福建 泉州 362021； 2. 華僑大學 計算機科學與技術學院，福建 廈門 361021)

一種增強局部搜索能力的改進人工蜂群算法

劉曉芳1，柳培忠1，駱炎民2，范宇凌1

(1. 華僑大學 工學院，福建 泉州 362021； 2. 華僑大學 計算機科學與技術學院，福建 廈門 361021)

針對人工蜂群算法初始化群體分布不均勻和局部搜索能力弱的問題，本文提出了一種增強局部搜索能力的人工蜂群算法(ESABC)。首先，在種群初始化階段采用高維洛倫茲混沌系統，得到遍歷性好、有規律的初始群體，避免了隨機初始化的盲目性。然后，采用基于對數函數的適應度評價方式，以增大種群個體間差異，減小選擇壓力，避免過早收斂。最后，在微分進化算法的啟發下，提出了一種新的搜索策略，采用當前種群中的最佳個體來引導下一代的更新，以提高算法的局部搜索能力。通過對12個經典測試函數的仿真實驗，并與其他經典的改進人工蜂群算法對比，結果表明：本文算法具有良好的尋優性能，無論在解的精度還是收斂速度方面效果都有所提高。

人工蜂群算法；高維混沌系統；適應度評價；搜索策略；優化算法；演化算法；收斂性分析；精度分析；智能算法

人工蜂群算法[1-3]是于2005年土耳其學者提出的用于解決優化問題的群智能算法。與其他智能算法相比，最大的優點在于：開采和開發同時進行，增加了尋找到最優解的概率。但它仍然存在收斂速度慢，易陷入局部最優，開采和開發能力不平衡等問題[4]。

針對以上問題，許多學者對該算法進行改進研究。G.Zhu和S. Kwong[5]受粒子群算法(particle swarm optimization， PSO)[6]的啟發，提出了一種改進算法(gbest-guide ABC， GABC)，通過把全局最優解加入到原始的搜索方程中，引導粒子向全局最優的方向更新，并通過測試函數驗證了其有效性。Gao 和 Liu[7-11]對人工蜂群算法的改進進行了眾多研究：在2011年，提出了IABC，采用logistic混沌映射進行初始化，并使用了ABC/best/1和ABC/rand/1兩個搜索策略[7]；2012年，提出MABC，通過正弦迭代器和反向學習方法進行初始化改進，并采用ABC/best/1進行迭代更新，具有很好的收斂性并得到了較高質量的解[8]；2013年，提出PABC，采用Powell方法作為局部搜索工具以提高局部搜索能力[9]；2014年，提出EABC，在采蜜蜂階段和觀察蜂階段分別采用兩種不同的搜索方程，以達到平衡開發和開采能力的效果[10]；2015年，提出BABC，在觀察蜂階段采用高斯搜索方程生成新的候選個體提高開采能力[11]。雖然許多學者已對人工蜂群算法進行了各種改進，并取得了良好的效果，但是仍存在收斂速度慢、局部搜索能力弱的缺點，可繼續改進。

針對以上問題，本文提出了一種收斂速度更快、局部搜索能力更強的人工蜂群算法。該算法采用高維混沌系統進行初始化，避免隨機初始化帶來的盲目性；并采用一種新的搜索策略，通過當前種群中的最優解引導進化方向，增強算法的局部搜索能力，進而達到提高解精度的效果，并且通過基于對數函數的適應度評價方式，增大個體間差異，減小選擇壓力，更容易選擇出優秀個體。

1 基本的人工蜂群算法

在人工蜂群算法中，把蜜蜂種群分為3種類型，即采蜜蜂、觀察蜂和偵察蜂，把蜜蜂的行為分為以下3種，即搜索、招募和放棄[2]。在蜜蜂種群中取一半作為采蜜蜂，另一半作為觀察蜂。蜜蜂種群在多維搜索空間中更新時，采蜜蜂負責根據自身經驗搜索食物源，然后把食物源的具體信息告訴觀察蜂；觀察蜂根據采蜜蜂共享的信息選擇將要跟隨的蜜蜂；偵察蜂在食物源經過有限次搜索后仍未更新時發揮作用，重新初始化種群生成新的食物源。在優化問題中，食物源與優化問題的可行解相對應，采集食物源的過程相當于搜索最優解的過程。解的好壞取決于優化問題的適應度值，即較高的適應度值代表較好的食物源(可行解)。

首先，該算法根據公式(1)隨機生成初始食物源(初始解)：

然后，采蜜蜂在食物源鄰域進行搜索，尋找優良食物源的位置。當采蜜蜂搜索到食物源時，評估該食物源的適應度值。若該食物源具有較好的適應度值，則用新的食物源取代原來的食物源，否則不做更新。食物源鄰域的搜索方程如式(2)所示：

對于最小化問題，適應度值的計算公式如式(3)所示：

式中：fi表示Vi對應的函數值，fi越小，則fiti越大。貪婪選擇機制的公式如式(4)所示：

式中：Ts表示蜜蜂個體間的一種映射關系，該式子能夠確保種群中始終保留精英個體，即進化方向不會出現倒退現象。

采蜜蜂搜索結束后，進入觀察峰階段，該類蜜蜂指待在蜂巢內等待采蜜蜂采到食物源后返回分享食物源信息的個體。因此，觀察蜂需要根據概率來選擇將要跟隨的采蜜蜂。概率選擇公式如式(5)所示：

當觀察蜂根據式(5)選擇到采蜜蜂進行跟隨時，接下來觀察蜂根據采蜜蜂共享的信息，到其附近進行局部深度搜索，搜索公式同式(2)，然后再通過適應度值評估食物源的質量。

在經過一定次數的迭代之后(用limit表示迭代次數)，若采蜜蜂或者觀察蜂的食物源的質量一直沒有更新，則認為該蜜蜂個體陷入了局部最優，此時放棄該食物源，并且采蜜蜂或觀察蜂轉變為偵察蜂，然后偵察蜂將會根據式(2)生成新的蜜蜂群體(新的可行解)，進而跳出局部最優。

2 改進的人工蜂群算法

在原始的人工蜂群算法中，初始種群由隨機函數產生，所以該算法具有較強的全局搜索能力。但是，原始搜索方程的局部搜索能力比較弱，導致對解沒有充分開采。全局搜索能力和局部搜索能力的不平衡是影響收斂速度和解質量的關鍵因素之一。另外，搜索進行到后期時，種群多樣性會有所下降，嚴重影響算法的搜索效率。針對以上問題，本文提出3個改進策略提高算法的性能。

2.1 種群初始化

種群初始解的質量在一定程度上影響最終解的質量，初始解分布越均勻，覆蓋越廣泛，在最優解鄰域搜索的可能性就越大。所以，我們需要設計一種策略增加種群多樣性。

混沌是一種非線性現象，具有隨機性、遍歷性和有界性。在一定范圍內，根據規則可不重復地轉變成所有狀態。B. Alatas[12]已證明混沌映射是一種可有效地在整個搜索空間搜索解的方法。目前，應用在群智能算法上的混沌系統大多數為一維的，但是，一維混沌系統具有以下不足：1)迭代操作后產生單一序列；2)分布不均勻。因此，本文提出采用一種高維的混沌系統——洛倫茲混沌系統，該系統可產生3個不同的混沌迭代序列，增加了優良序列的可選擇性，提高了序列的分布性。混沌迭代序列的生成公式如式(6)所示：

式中：取x(0)、y(0)、z(0)為初始值；δ、γ、β為洛倫茲系統的參數，取值分別為δ=10，β=8/3,γgt;24.74。最后，從產生的三組混沌序列中隨機選一維，記作φ，把該參數代入式(1),得到新的初始化方程，如式(7)所示：

2.2 改進的適應度評價方式

在原始人工蜂群算法中，觀察蜂通過式(5)的概率選擇優良食物源跟隨，進行局部開采。概率的大小反映了采蜜蜂攜帶食物源的質量，食物源質量通過適應度值體現，適應度值越大，食物源質量越好，被選擇的概率就越大。但是，在式(3)中，當函數值fi滿足條件limfi=0,limfj=0,fi≠fj時，適應度值則limfiti=1,limfitj=1，那么公式(5)中的概率值也會相同，體現不出個體之間的差異[8]。為了解決該問題，本文采用基于對數的適應度評價方式，通過該方法把個體間差異明顯化，進而把函數值相似但不同的種群個體區分開，使得優秀個體有更大的概率被跟隨開采[13]。改進后的適應度評價方式如式(8)所示：

式中：λ由計算機的計算精度決定。此處，取λ=8。

2.3 新的搜索機制

2.4 改進算法流程圖

通過以上分析可得出：以上策略可以平衡算法的搜索能力，提高算法的性能。改進算法的具體流程如圖1所示。

圖1 ESABC算法流程圖Fig.1 ESABC flowchat

3 實驗結果與分析

3.1 測試函數

為了驗證ESABC的性能，本文采用12個基準測試函數進行實驗。表1給出了測試函數的編號、名稱、理論最優值和搜索范圍。其中，F01～F04為單峰函數，F05～F12為多峰函數。函數的具體定義見參考文獻[15-17]。

表1 基準函數

3.2 實驗分析

本文改進算法ESABC與ABC[2]和GABC[5]進行對比，參數設置如下：SN=150，limit=100，MCN=1 000。3個算法在相同的實驗背景下運行，且每個測試函數獨立運行10次以避免偶然性，并記錄最優值、最差值、平均值和方差。表2 和表3分別為D=30和D=60的實驗結果。其中，D=30的情況在11個函數進行測試，D=60的情況在10個函數進行測試。

由表2可看出：對于單峰函數，ESABC解的精度和穩定性均優于ABC和GABC；對于多峰函數，除了himmelblau函數，ESABC的性能均優于ABC和GABC。除此之外，根據圖2可以更形象地比較3個算法的收斂速度，由圖2可以看出：對于himmelblau函數，3個算法的收斂精度一樣，ESABC的收斂速度比GABC慢，比ABC快；對于其他函數，ESABC的收斂精度均好于ABC和GABC，收斂速度總體上快于另外兩個算法。在圖2、3中，縱坐標平均誤差為lg(|f(x)-f(x*)|，f(x)表示實際函數值，f(x*)表示理論函數值)。

由表3可以看出：D=60時，除了ackley函數，ESABC的解均優于ABC和GABC。由圖3可看出：ackley函數的精度和收斂速度都差于GABC，優于ABC。

總體來說，ESABC在解的精度和收斂速度方面都有所提高。

表2 實驗結果(D=30)

續表2

表3 實驗結果(D=60)

續表3

圖2 進化曲線(D=30)Fig.2 Evolution curves(D=30)

圖3 進化曲線(D=60)

4 結束語

本文針對基本ABC算法存在初始化群體分布不均勻和局部搜索能力弱的問題，提出了一種基于增強局部搜索能力的人工蜂群算法。該算法首先采用洛倫茲混沌系統將初始解的分布盡量均勻化，然后采用改進的搜索策略以達到增強局部搜索能力的效果，并通過基于對數函數的適應度評價方式減小選擇壓力，更容易選擇出優秀個體。通過12個測試函數的仿真實驗表明，本文算法能夠提高基本人工蜂群算法的性能，但該算法也有其局限性，并不能解決所有的問題。如何使算法能夠有更好的普適性以及將所采用到的改進策略應用到多目標優化、機器人路徑規劃等領域是下一步的研究工作。

[1]KARABOGA D. An idea based on honey bee swarm for numerical optimization. technical report-TR06[R]. Kayseri: Erciyes University, 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]KARABOGA D, AKAY B. A comparative study of artificial bee colony algorithm[J]. Applied mathematics and computation, 2009, 214(1): 108-132.

[4]秦全德，程適，李麗，等. 人工蜂群算法研究綜述[J]. 智能系統學報， 2014， 9(2)： 127-135.

QIN Quande, CHENG Shi, LI Li,et al. Artificial bee colony algorithm: a survey[J]. CAAI transactions on intelligent systems, 2014, 9(2): 127-135.

[5]ZHU G, KWONG S. Gbest-guided artificial bee colony algorithm for numerical function optimization[J]. Applied mathematics amp; computation, 2010, 217(7): 3166-3173.

[6]姜建國, 葉華, 劉慧敏，等. 融合快速信息交流和局部搜索的粒子群算法[J]. 哈爾濱工程大學學報, 2015，36(5): 687-691.

JIANG Jianguo, YE Hua, LIU Huimin, et al. Particle swarm optimization method with combination of rapid information communication and local search[J]. Journal of Harbin engineering university, 2015, 36(5): 687-691.

[7]GAO Weifeng, Liu Sanyang, et al. Improved artificial bee colony algorithm for global optimization[J]. Information processing letters, 2011, 111(17): 871-882.

[8]GAO Weifeng, LIU Sanyang. A modified artificial bee colony algorithm[J]. Computers and operations research, 2012, 39(3): 687-697.

[9]GAO W F, LIU S Y, HUANG L L. A novel artificial bee colony algorithm with method[J]. Applied soft computing, 2013, 13(9): 3763-3775.

[10]GAO W F, LIU S Y, HUANG L L. Enhancing artificial bee colony algorithm using more information-based search equations[J]. Information sciences, 2014, 270(1): 112-133.

[11]GAO W, CHAN F T S, HUANG L, et al. Bare bones artificial bee colony algorithm with parameter adaptation and fitness-based neighborhood[J]. Information sciences, 2015, 316(C):180-200.

[12]ALATAS B. Chaotic bee colony algorithms for global numerical optimization[J]. Expert systems with applications, 2010, 37(8): 5682-5687.

[13]陳杰，沈艷霞，陸欣. 基于信息反饋和改進適應度評價的人工蜂群算法[J].智能系統學報， 2016，11(2)： 172-179.

CHEN Jie, SHEN Yanxia, LU Xin. Artificial bee colony algorithm based on information feedback and an improved fitness value evaluation[J]. CAAI transactions on intelligent systems, 2016, 11(2): 172-179.

[14]YI, Wenchao,et al. Differential evolution algorithm with variable neighborhood search for hybrid flow shop scheduling problem[C]//IEEE, International Conference on Computer Supported Cooperative Work in Design IEEE. Nanchang, China 2016: 233-238.

[15]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.

[16]SUGANTHAN P N, HANSEN N, LIANG J J, et al. Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization[R]. KanGAL Report #2005005. India: IIT Kanpur, 2005.

[17]王志剛，王明剛. 基于符號函數的多搜索策略人工蜂群算法[J]. 控制與決策， 2016， 31(11): 2037-2044.

WANG Zhigang, WANG Minggang. Multi-search strategy of artificial bee colony algorithm based on symbolic function[J]. Control and decision, 2016, 31(11): 2037-2044.

劉曉芳，女，1993年生，碩士研究生，主要研究方向為智能優化算法及其應用。

柳培忠，男，1976年生，講師，博士，美國杜克大學高級訪問學者，主要研究方向為仿生智能計算、仿生圖像處理技術、多維空間仿生信息學等,主持及參與課題6項,發表學術論文15篇。

駱炎民，男，1975年生，副教授，博士，主要研究方向為人工智能、機器學習、圖像處理、數據挖掘。主持及參與課題8項，發表學術論文16篇。

Improvedartificialbeecolonyalgorithmbasedonenhancedlocalsearch

LIU Xiaofang1， LIU Peizhong1， LUO Yanmin2， FAN Yuling1

(1. Engineering school, Huaqiao University, Quanzhou 362021, China; 2. School of Computer Science and Technology, Huaqiao University, Xiamen 361021, China)

The shortcomings of the artificial bee colony algorithm (ABC) are its uneven initial population distribution and weak local search. In this paper, we propose an ABC algorithm based on enhanced local search (ESABC). First, we employ a high-dimension chaotic system (Lorenz system) to obtain the ergodic and regular initial populations and to avoid the blindness of random initialization in the population initialization stage. Then, we introduce improved fitness evaluation methods based on the logarithmic function to increase the differences between individuals, reduce selection pressure, and avoid premature convergence. Lastly, inspired by the differential evolution algorithm, we propose a new search tactic that uses the best individual in the contemporary population to guide the renewal of the next generation, and thereby enhance the local search ability. We examined the performance of the proposed approach with 12 classic testing functions and compared the results with the basic and other ABCs. As documented in the experimental results, the proposed algorithm exhibits good optimization performance and can improve both the accuracy and convergence speed of the algorithm.

artificial bee colony algorithm; high-dimension chaotic system; fitness evaluation; search tactics; optimization algorithm; evolutionary algorithm; convergence analysis; accuracy analysis; intelligent algorithm

10.11992/tis.201612026

http://kns.cnki.net/kcms/detail/23.1538.TP.20170508.0922.004.html

TP18

A

1673-4785(2017)05-0684-10

中文引用格式：劉曉芳，柳培忠，駱炎民，等.一種增強局部搜索能力的改進人工蜂群算法J.智能系統學報， 2017, 12(5): 684-693.

英文引用格式：LIUXiaofang，LIUPeizhong，LUOYanmin，etal.ImprovedartificialbeecolonyalgorithmbasedonenhancedlocalsearchJ.CAAItransactionsonintelligentsystems, 2017, 12(5): 684-693.

2016-12-23. < class="emphasis_bold">網絡出版日期

日期：2017-05-08.

國家自然科學基金資助項目(61203242); 物聯網云計算平臺建設資助項目( 2013H2002); 華僑大學研究生科研創新能力培育計劃資助項目(1511322003).

柳培忠. E-mail：pzliu@hqu.edu.cn.