混沌搜索策略的改進人工蜂群算法

彭曉華, 劉利強

(1.遼寧工程技術大學 基礎教學部，遼寧 葫蘆島 125105； 2.遼寧工程技術大學 電氣與控制工程學院，遼寧 葫蘆島 125105)

?

混沌搜索策略的改進人工蜂群算法

彭曉華1, 劉利強2

(1.遼寧工程技術大學 基礎教學部，遼寧 葫蘆島 125105； 2.遼寧工程技術大學 電氣與控制工程學院，遼寧 葫蘆島 125105)

摘要：針對人工蜂群算法的蜂群缺乏多樣性、全局和局部搜索能力差及收斂速度較慢，提出一種基于混沌搜索策略的改進人工蜂群算法。該算法通過載波映射，由混沌-決策變量的變換，產生新的鄰域點，為采蜜蜂和被招募的觀察蜂提供了更廣闊的搜索空間和更優質的位置蜜源，增強蜂群多樣性；同時，引進偵查蜂局部蜜源搜索較好地解決了算法易陷入局部極小的問題，改善了人工蜂群算法的收斂性能。最后由6個標準測試函數的仿真驗證，得到基于混沌搜索策略的人工蜂群算法性能明顯優于標準人工蜂群算法。

關鍵詞：人工蜂群算法；混沌搜索策略；載波映射；局部蜜源搜索；蜂群多樣性；混沌-決策變量；收斂性能；仿真實驗

中文引用格式：彭曉華， 劉利強. 混沌搜索策略的改進人工蜂群算法[J]. 智能系統學報， 2015, 10(6): 927-933.

人工蜂群算法(artificial bee colony algorithm，ABCA)是一種模擬自然界中蜜蜂按照不同分工而共同尋找優質蜜源的智能方法。1995年Seeley首次闡述了有關蜜蜂群體行為的自組織模型。2005年D.Karaboga建立了具有完整協同動作的人工蜂群算法模型，而且通過非線性的函數優化實驗驗證了人工蜂群算法比一般啟發式優化算法具有更強的穩定性和可靠性。2006年D.Karaboga等又將ABC理論應用到限制性數值優化問題、神經網絡訓練、數字濾波器設計等，并取得了較好的測試效果。在文獻[1-2]中，Dervis Karaboga等通過對多種智能優化算法的定量對比驗證，得出在迭代誤差曲線對比中，人工蜂群算法要比其他智能優化算法在曲線大部分階段上具有更好的優化性能，至少有著相似的性能。人工蜂群算法和其他智能優化算法類似，算法本身也存在自身的優化缺陷，從全局搜索能力表現出的搜索速度緩慢或搜索暫時性的停滯現象，在局部搜索能力存在易陷入局部極小值問題，特別是對于人工蜂群算法，存在一個對于該算法優化性能特別重要的影響因素，即蜂群的多樣性。多樣性降低，會使蜜蜂行為中漏掉一定的搜索區域，直接導致算法陷入局部最優，進而會影響全局搜索能力，收斂速度會受到極大影響。同時，蜂群群體的具體行為也會存在一些問題，比如：蜂群的不同選擇方式和進化策略都會使得算法在處理一些具體優化問題時存在易陷入早熟收斂或收斂速度慢等問題。文獻[6]結合了Markov的性質和隨機搜索算法的收斂準則，證明了ABC算法具備全局收斂的性質，并提出一種搜索效率更高的局部搜索代替原來的隨機解的設想；文獻[7]分別從蜂群初始化、鄰域搜索及跟隨蜂行為這3個角度對人工蜂群算法進行了改進優化，有效地平衡了全局搜索和局部搜索，算法的性能也得到了提高；文獻[8]充分考慮以粒子群算法為代表的智能優化算法普遍存在的算法局限性的問題，針對不同的缺陷提出改進策略，通過將多種改進策略進行融合，通過自適應學習機制選出恰當的策略來解決不同形態的復雜問題。

人工蜂群算法是依賴位置信息最終搜索到最優蜜源，所以鄰域搜索就顯得格外重要。目前人工蜂群算法的改進方法大多是從收斂速度的角度出發，從全局搜索角度來看，極有可能漏掉一部分的鄰域搜索范圍，而這種鄰域搜索的局限性會直接導致蜂群多樣性降低，容易陷入局部極值，針對特殊優化問題時，有可能得不出全局最優解。所以，提出一種基于混沌搜索策略的改進人工蜂群算法，引入混沌搜索的思想，通過載波方式將混沌變量的值映射到優化變量的取值范圍內，產生局部最優解的新增鄰域點[5,9]，從而增強種群的多樣性，提高全局搜索能力，使其免于陷人局部最優而獲得全局最優解。

1人工蜂群算法

人工蜂群算法搜索蜜源過程中，蜜蜂按照不同的分工可分為采蜜蜂、觀察蜂和偵查蜂3種，采蜜蜂通過不斷探索，保持最優質蜜源，觀察蜂及時補充優質蜜源對應蜜蜂的數目，偵察蜂在蜂群鄰域尋找新蜜源。整個蜂群搜索過程并不是單一地各司其職地進行，而是3種蜂種在密切的相互聯系及轉化中完成的，并且各個蜂種之間通過蜜蜂獨特的交流方式，即找到蜜源的蜂種依靠在指定區域跳搖擺舞向別的蜂種發送自己攜帶蜜源的信息，同時，通過所攜帶蜜源量的多少決定該蜂種跳搖擺舞的時間長短，蜜源花蜜量的多少可以看成是適應度的大小，所以觀察蜂看到別的蜂種所跳搖擺舞的時間越長，說明該蜂種的適應度值越大，所帶蜜源花蜜量就越多，反之亦然。當觀察蜂被招募后轉化為采蜜蜂，便開始執行采蜜蜂的行為，當采蜜蜂放棄原來蜜源而轉化為偵查蜂后，便開始在蜂群鄰域尋找新蜜源。不斷地估算比較適應值的大小而進行不同蜂種之間的轉化合作，蜂群才能在鄰域范圍不斷地刷新蜂蜜含量較高的新蜜源，即找到最優解。

為了更好地展示蜜蜂覓食的行為特征，用圖1來展示整個算法搜索過程[1-2]，其中觀察蜂行為(UF)，被招募為采蜜蜂采蜜行為(EF1)，原采蜜蜂采蜜行為(EF2)，S線為偵察蜂尋找蜂巢附近的蜜源行為，R線為被招募的觀察蜂尋找蜜源行為。

圖1　人工蜂群算法的基本原理Fig.1　The basic principle of artificial swarm algorithm

圖1完整地描述了3種蜂種協同合作、共同尋找最優蜜源的原理，人工蜂群算法的基本步驟如下[3-4]：

1)初始化參數。設置蜂群規模NP，采蜜蜂Ne，觀察蜂Nu，蜜源個數NP/2，蜜源維數D，鄰域搜索空間S，迭代次數K，蜜蜂停留閾值Limit，采蜜蜂種群記為X=[X1X2…XNe]，其中Xi∈S(i≤Ne)是Ne個個體，X(0)代表初始采蜜蜂種群，X(n)代表第n代采蜜蜂種群。

2)對于n=0時刻，隨機生成Ns個可行解(X1,X2，…,XNe)，具體隨機產生的可行解Xi為

(1)

式中：j取值于{1,2,…,D}，為D維解向量的某個分量。分別計算各向量的適應度值，并將排名前一半的作為初始的采蜜蜂種群X(0)，初始標志向量trail(i)=0，記錄采蜜蜂停留同一蜜源的搜索次數。

3) 設置初始迭代次數iter=0，對于第n步的采蜜蜂Xi(n)，在當前位置向量附近鄰域進行搜索新的位置，搜索公式為

(2)

式中：j取值于{1,2,…,D}，k取值于{1,2,…,Ne}，且k≠i。k，j均為[-1,1]的隨機數。

4)根據最優適應度選擇原則，既要保留最優位置蜜源，又要使蜂群搜索方向向著蜜源含量高升的方向迭代。故當采蜜蜂在蜂巢鄰域范圍第2次找到新蜜源時，記此時位置向量為new_Xi，而上一次所找到的蜜源位置向量為Xi，則記2次蜜源搜索中，適應度值較大的位置蜜源為Ts，其概率分布為

P{Ts(Xi,new_Xi)=new_Xi}=

(3)

5)當許多個采蜜蜂將所采蜜源信息帶到舞蹈區共享給觀察蜂時，觀察蜂將會做出2個動作行為：首先，觀察蜂根據概率式(4)選擇符合自身條件的采蜜蜂，轉化為采蜜蜂；其次，通過式(4)中適應度值公式在蜂群鄰域進行初次蜜源的搜索。不同觀察蜂被招募為對應采蜜蜂的概率為

(4)

式中：Ts1表示隨機映射。

6)對比多次搜索到的新蜜源位置，生成最優蜜源位置向量集(x1,x2,…,xd)，d為現有采蜜蜂個數，同時得出，到目前為止更新的最優適應度Best_Fitness。

7)在蜜源搜索中，不斷地用標志向量trail(i)記錄著同一采蜜蜂對同一蜜源位置的搜索次數，當trail(i)>Limit且不滿足式(3)時，即說明該鄰域范圍位置蜜源含蜜量整體偏低，若再在此地搜索蜜源，會嚴重影響蜜源質量及搜索速度，故須將此類采蜜蜂重新規定初始蜜源位置。即

(5)

8)如果滿足停止準則，則停止計算并輸出最優適應度值Best_Fitness，迭代次數iter=iter+1，相應的參數(x1,x2,…,xD)，否則轉向第3)步。

2基于混沌搜索策略的改進人工蜂群算法

針對人工蜂群算法(ABC)尋優過程中缺乏多樣性，收斂速度較慢，易陷入局部最優等缺陷，引入混沌搜索策略的改進人工蜂群算法(improvedartificialbeecolonyalgorithmofchaossearchingstrategy，CSABCA)，采用混沌搜索策略細化人工蜂群算法中采蜜蜂和觀察蜂的搜索空間，在迭代進化中產生局部最優解的新增鄰域點，從而加速了偵查蜂的搜索，使得蜂群以最快速度找到最優蜜源。

混沌搜索的基本思想[5]是根據式(6)

(6)

產生混沌序列，然后通過載波方式將混沌變量的值映射到優化變量的取值范圍。式(6)中，n∈[1,Nmax]，d∈[1,D]，μ是混沌狀態的控制參數，當μ=4時，Logistic方程為完全混沌狀態。它的數學描述過程為：當有采蜜蜂轉變為偵查蜂時，產生一個D維隨機向量y0=[y0,1y0,2…],y0∈[0,1]，y0為迭代初始值，通過Logistic方程開始迭代，得到序列yn,d。同時，根據式(6)產生的局部最優解的新增鄰域點，按照載波方式將混沌變量放大后應用在待進行蜜源搜索的單個變量fi,d上，可得新個體

(7)

對于目標函數minf(x)，目標變量為X=[x1x2…xd]T，完整的基于混沌搜索策略的人工蜂群算法(CSABC)實現步驟如下：

1)按照操作1)進行，記最大混沌迭代次數為Cmax。

2)利用混沌序列初始蜂群生成數值都在(0,1)的NP個互異D維向量y0，通過式(7)的載波方式將y0映射到原解空間鄰域范圍內，產生決策變量。

(8)

4)按照操作2)~6)進行。

6)若trail(i)>Limit時，進行7)，然后第i個采蜜蜂舍棄蜜源轉變為偵查蜂，偵查蜂在混沌區域范圍內搜索鄰域蜜源y″n,d。

7)記錄到目前為止的所有蜜蜂尋找的最優蜜源，更新iter=iter+1，判斷是否達到最大混沌迭代次數，如果是，結束混沌搜索，找到最優解，否則，返回到 2)。CSABC算法的基本流程圖[14]如圖2。

圖2　CSABC算法流程圖Fig.2　CSABC algorithm flow chart

3CSABC算法仿真

3.1 標準測試函數

為驗證基于混沌搜索策略的人工蜂群算法的性能，選用6 個標準測試函數Sphere、Rosenbrock、Rastrigrin、Griewank、Ackley和Schwefel進行性能測試[15-17]。Sphere是一個基本單峰優化函數，只有全局極值，用于測試算法尋優精度和收斂速度；Rosenbrock是非凸、病態單峰函數，有局部極小值，用于測試算法的收斂速度和執行效率；Rastrigrin、Griewank、Ackley和Schwefel都是復雜的非線性多峰函數，有許多局部極值點，用于測試算法的全局搜索能力、跳出局部極值并避免早熟的能力[5,10,20]。6個標準測試函數的表達式、搜索空間及最優解見表1。

3.2實驗仿真分析

采用CSABC與ABC 2種算法的對比仿真實驗進行性能測試。在ABC算法中，設定初始參數：蜂群規模NP=100，蜜源個數為50，D=100，Ne=20，Nu=10，Ns=40，搜索次數極限Limit=100，最大迭代次數為2 000；在CSABC算法中，混沌狀態的控制參數μ=4，為混沌映射半徑Ri,d為函數自變量定義域的3/10，調節系數σ=0.25，其余參數均與ABC相同。圖3～圖8是為標準人工蜂群算法(ABC)與本文提出的基于混沌搜索策略的改進人工蜂群算法(CSABCA)對6個標準測試函數的優化過程中，蜂群尋優對比曲線。

表1　標準測試函數

圖3　Sphere函數尋優對比曲線Fig.3　Sphere of function optimization curve

圖4　Rosenbrock函數尋優對比曲線Fig.4　Rosenbrock of function optimization curve

圖5　Rastrigin函數尋優對比曲線Fig.5　Rastrigin of function optimization curve

圖6　Griewank函數尋優對比曲線Fig.6　Griewank of function optimization curve

圖7　Ackley函數尋優對比曲線Fig.7　Ackley of function optimization curve

圖8　Schwefel函數尋優對比曲線Fig.8　Schwefe of function optimization curve

函數算法均值標準差最優值SphereABC5.34516×10-113.55671×10-124.85461×10-12CSABC1.23503×10-166.12312×10-171.92924×10-16RosenbrockABC25.69789413.1001223.28459CSABC0.5411870.5560730.330645RastrigrinABC9.05027×10-91.59532×10-86.25471×10-7CSABC6.20541×10-131.07481×10-120GriewankABC3.71686×10-64.70565×10-69.04417×10-7CSABC2.22828×10-103.82682×10-106.64705×10-10AckleyABC1.5099×10-80.78904×10-81.80593×10-8CSABC1.74675×10-144.10232×10-152.22045×10-14SchwefelABC-19.69520.958708-16.1453CSABC-34.84020.671552-34.4944

通過圖3～圖8測試驗證，可以看出，在取維數為100，蜂群規模為100的情況下，CSABC算法無論在收斂速度方面、收斂精度還是尋找全局最優值方面，都明顯要優于ABC算法，它可以有效地避免陷入局部極值而加速收斂。測試結果參數見表2。

由表2可以看出，6個測試函數中，CSABC算法的最優值，均值及標準差均優于ABC算法。將本文CSABC算法與根據文獻[11]中的改進算法IABC，文獻[12]中的算法SFABC，文獻[13]中的算法LRABC，再次進行尋優測試進而驗證本文算法的有效性，取最大混沌搜索次數Cmax=40，取標準測試函數Rosenbrock 和Griewank分別測試運行40次，設算法精度為10-25，進行對比驗證，見表3。

表3不同改進人工蜂群算法優化結果

Table 3Different improved artificial colony algorithms optimization results

函數算法均值標準差平均時間Rosen-brockIABC4.95867×10-17.66847×10-125.1755SFABC6.4712003.85270026.6514LRABC1.35918×10-18.74717×10-224.1843CSABC5.2657×10-26.38326×10-317.5548Grie-wankIABC0031.0128SFABC2.5457×10-157.78426×10-1622.8748LRABC0027.8934CSABC0018.2354

由表3中多種改進人工蜂群算法的對比測試可得到，對測試函數Griewank、IABC、SFABC和CSABC算法均達到最優值，而對Rosenbrock測試函數中，CSABC算法在均值、標準差及平均運行時間上均優于IABC、SFABC和LRABC算法，從而進一步驗證了CSABC算法的優越性。

5結束語

本文主要針對人工蜂群算法，蜂群搜索速度慢甚至停滯，多樣性降低，容易陷入局部極值等諸多不足，提出了一種基于混沌搜索策略的改進人工蜂群算法。該算法引入了混沌搜索策略，通過載波方式將混沌變量的值映射到優化變量的取值范圍內，產生局部最優解的新增鄰域點，從而加快了全局搜索能力和局部搜索能力，增強了蜂群多樣性，跳出了局部極值，提高了算法收斂速度。通過6個標準測試函數的對比尋優驗證，CSABC算法具有收斂速度快，收斂精度高和較強的全局搜索能力。同時，對比了多種改進人工蜂群算法，充分驗證本文算法的有效性和優越性。

參考文獻:

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

[2]KARABOGA D, OZTURK C. A novel clustering approach: artificial bee colony (ABC) algorithm[J]. Applied Soft Computing, 2011, 11(1): 652-657.

[3]ZHU Guopu, KWONG S. Gbest-guided artificial bee colony algorithm for numerical function optimization[J]. Applied Mathematics and Computation, 2010, 217(7): 3166-3173.

[4]SZETO W Y, WU Yongzhong, HO S C. An artificial bee colony algorithm for the capacitated vehicle routing problem[J]. European Journal of Operational Research, 2011, 215(1): 126-135.

[5]羅鈞, 李研. 具有混沌搜索策略的蜂群優化算法[J]. 控制與決策, 2010, 25(12): 1913-1916.

LUO Jun, LI Yan. Artificial bee colony algorithm with chaotic-search strategy[J]. Control and Decision, 2010, 25(12): 1913-1916.

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

NING Aiping, ZHANG Xueying. Convergence analysis of artificial bee colony algorithm[J]. Control and Decision, 2013, 28(10): 1554-1558.

[7]王冰. 基于局部最優解的改進人工蜂群算法[J]. 計算機應用研究, 2014, 31(4): 1024-1026.

WANG Bing. Improved artificial bee colony algorithm based on local best solution[J]. Application Research of Computers, 2014, 31(4): 1024-1026.

[8]伍大清, 鄭建國. 基于混合策略自適應學習的并行粒子群優化算法[J]. 控制與決策, 2013, 28(7): 1087-1093.

WU Daqing, ZHENG Jianguo. Improved parallel particle swarm optimization algorithm with hybrid strategy and self-adaptive learning[J]. Control and Decision, 2013, 28(7): 1087-1093.

[9]胥小波, 鄭康鋒, 李丹, 等. 新的混沌粒子群優化算法[J]. 通信學報, 2012, 33(1): 24-30, 37.

XU Xiaobo, ZHENG Kangfeng, LI Dan, et al. New chaos-particle swarm optimization algorithm[J]. Journal on Communications, 2012, 33(1): 24-30, 37.

[10]匡芳君, 徐蔚鴻, 金忠. 自適應Tent混沌搜索的人工蜂群算法[J]. 控制理論與應用, 2014, 31(11): 1502-1509.

KUANG Fangjun, XU Weihong, JIN Zhong. Artificial bee colony algorithm based on self-adaptive tent chaos search[J]. Control Theory & Applications, 2014, 31(11): 1502-1509.

[11]王輝. 改進的蜂群算法[J]. 計算機工程與設計, 2011, 32(11): 3869-3872.

WANG Hui. Improved artificial bee colony algorithm[J]. Computer Engineering and Design, 2011, 32(11): 3869-3872.

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

WANG Hui. Artificial bee colony algorithm with sharing factor[J]. Computer Engineering, 2011, 37(22): 139-142.

[13]劉三陽, 張平, 朱明敏. 基于局部搜索的人工蜂群算法[J]. 控制與決策, 2014, 29(1): 123-128.

LIU Sanyang, ZHANG Ping, ZHU Mingmin. Artificial bee colony algorithm based on local search[J]. Control and Decision, 2014, 29(1): 123-128.

[14]彭泓, 丁玉成. 基于遺傳交叉因子的蝙蝠算法的改進[J]. 激光雜志, 2015, 36(2): 23-26.

PENG Hong, DING Yucheng. Improved bats algorithm optimization based on genetic hybrid genes[J]. Laser Journal, 2015, 36(2): 23-26.

[15]GAO Weifeng, LIU Sanyang. A modified artificial bee colony algorithm[J]. Computers & Operations Research, 2012, 39(3): 687-697.

[16] OMKAR S N, SENTHILNATH J, RAHUL K, et al. Artificial bee colony (ABC) for multi-objective design optimization of composite structures[J]. Applied Soft Computing, 2011, 11(1): 489-499.

[17]KARABOGA D, AKAY B. Artificial bee colony (ABC) algorithm on training artificial neural networks[C]//Proceedings of IEEE 15th Signal Processing and Communications Applications. Eskisehir: IEEE, 2007: 1-4.

[18]KARABOGA N. A new design method based on artificial bee colony algorithm for digital IIR filters[J]. Journal of the Franklin Institute, 2009, 346(4): 328-348.

[19]王瑞琪, 李珂, 張承慧. 基于混沌多目標遺傳算法的微網系統容量優化[J]. 電力系統保護與控制, 2011, 39(22): 16-22.

WANG Ruiqi, LI Ke, ZHANG Chenghui. Optimization allocation of microgrid capacity based on chaotic multi-objective genetic algorithm[J]. Power System Protection and Control, 2011, 39(22): 16-22.

[20]暴勵, 曾建潮. 一種雙種群差分蜂群算法[J]. 控制理論與應用, 2011, 28(2): 266-272.

BAO Li, ZENG Jianchao. A bi-group differential artificial bee colony algorithm[J]. Control Theory & Applications, 2011, 28(2): 266-272.

彭曉華，女,1963年生，教授，博士，主要研究方向為煤層瓦斯滲流理論研究、智能控制理論方法與應用研究。參加國家自然基金項目2項，主持和參加省教育廳科學研究基金項目各一項，主持或參加其他科研項目10余項。通過省市和學校鑒定的科研課題多項，獲科研成果10余項。發表學術論文20余篇。

劉利強，男，1988年生，碩士研究生，主要研究方向為智能檢測與故障診斷。

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20151110.1354.020.html

英文引用格式：PENG Xiaohua， LIU Liqiang. Improved artificial bee colony algorithm based on chaos searching strategy[J]. CAAI Transactions on Intelligent Systems, 2015, 10(6): 927-933.

Improved artificial bee colony algorithm

based on chaos searching strategy

PENG Xiaohua1， LIU Liqiang2

(1.Ministry of basic education, Liaoning University of engineering and Technology, Huludao 125105,China；2.College of electrical and control engineering, Liaoning University of engineering and Technology, Huludao 125105,China)

Abstract：The current artificial bee colony algorithm results in the swarm lacking diversity, and the global and local search abilities and convergence speed are slow. We propose an improved artificial bee colony algorithm based on a chaotic search strategy. We map the algorithm with the carrier using a chaos decision variable transformation, generating new neighborhood points, and recruiting bees within a broader search space and from better source locations, while enhancing swarm diversity. In addition, the investigation of a local honey bee search better solved the algorithm problem of the local minimum and improved the convergence property of the artificial bee colony algorithm. The most recent six simulation validations of the standard test functions using the proposed artificial bee colony algorithm, based on the chaotic search strategy, are significantly better than the performance results of the current artificial bee colony algorithm.

Keywords：artificial bee colony algorithm; chaotic search strategy; carrier mapping; local search nectar; the swarm diversity; chaos-decision variable; convergence performance; simulation experiment

作者簡介：

通信作者：劉利強.E-mail:2965131477@qq.com.

基金項目：國家自然科學基金資助項目(51274118)；遼寧省教育廳基金資助項目(L2012119).

收稿日期：2015-4-30. 網絡出版日期：2015-11-10.

中圖分類號：TP301.6

文獻標志碼：A

文章編號：1673-4785(2015)06-0927-07

DOI:10.11992/tis.201507032