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

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

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

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

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

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

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

人工蜂群算法；高維混沌系統(tǒng)；適應(yīng)度評價；搜索策略；優(yōu)化算法；演化算法；收斂性分析；精度分析；智能算法

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

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

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

1 基本的人工蜂群算法

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

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

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

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

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

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

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

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

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

2 改進的人工蜂群算法

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

2.1 種群初始化

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

混沌是一種非線性現(xiàn)象，具有隨機性、遍歷性和有界性。在一定范圍內(nèi)，根據(jù)規(guī)則可不重復(fù)地轉(zhuǎn)變成所有狀態(tài)。B. Alatas[12]已證明混沌映射是一種可有效地在整個搜索空間搜索解的方法。目前，應(yīng)用在群智能算法上的混沌系統(tǒng)大多數(shù)為一維的，但是，一維混沌系統(tǒng)具有以下不足：1)迭代操作后產(chǎn)生單一序列；2)分布不均勻。因此，本文提出采用一種高維的混沌系統(tǒng)——洛倫茲混沌系統(tǒng)，該系統(tǒng)可產(chǎn)生3個不同的混沌迭代序列，增加了優(yōu)良序列的可選擇性，提高了序列的分布性?；煦绲蛄械纳晒饺缡?6)所示：

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

2.2 改進的適應(yīng)度評價方式

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

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

2.3 新的搜索機制

2.4 改進算法流程圖

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

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

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

3.1 測試函數(shù)

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

表1 基準函數(shù)

3.2 實驗分析

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

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

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

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

表2 實驗結(jié)果(D=30)

續(xù)表2

表3 實驗結(jié)果(D=60)

續(xù)表3

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

圖3 進化曲線(D=60)

4 結(jié)束語

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

[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]. 智能系統(tǒng)學(xué)報， 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]. 哈爾濱工程大學(xué)學(xué)報, 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]陳杰，沈艷霞，陸欣. 基于信息反饋和改進適應(yīng)度評價的人工蜂群算法[J].智能系統(tǒng)學(xué)報， 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]王志剛，王明剛. 基于符號函數(shù)的多搜索策略人工蜂群算法[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年生，碩士研究生，主要研究方向為智能優(yōu)化算法及其應(yīng)用。

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

駱炎民，男，1975年生，副教授，博士，主要研究方向為人工智能、機器學(xué)習、圖像處理、數(shù)據(jù)挖掘。主持及參與課題8項，發(fā)表學(xué)術(shù)論文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.智能系統(tǒng)學(xué)報， 2017, 12(5): 684-693.

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

2016-12-23. < class="emphasis_bold">網(wǎng)絡(luò)出版日期

日期：2017-05-08.

國家自然科學(xué)基金資助項目(61203242); 物聯(lián)網(wǎng)云計算平臺建設(shè)資助項目( 2013H2002); 華僑大學(xué)研究生科研創(chuàng)新能力培育計劃資助項目(1511322003).

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