引入混合蛙跳搜索策略的人工蜂群粒子群算法

任 聰，葛洪偉，楊金龍，袁運浩

江南大學 物聯(lián)網工程學院，江蘇 無錫 214122

1 引言

Kennedy和Eberhart[1]于1995年提出了模擬鳥類覓食行為的粒子群優(yōu)化算法（PSO），該算法是繼遺傳算法、蟻群算法之后，被提出的一種基于群體智能的新型優(yōu)化算法。由于PSO算法能夠解決大量非線性、多峰等復雜的優(yōu)化問題，且具有易于實現(xiàn)、參數(shù)較少、并行等優(yōu)點，因此，在科學和工程領域得到了廣泛的應用。近些年來，國內外的許多學者致力于粒子群優(yōu)化算法的研究，在算法性能改進和應用上取得了許多重要的成果。Shi和Eberhart[2]引入了慣性權重來提高算法的收斂速度。Jiao等人提出了在PSO中引入動態(tài)慣性權重的方法，用于提高算法的收斂速度[3]。Bergh和Engelbreeht[4]提出了一種協(xié)作粒子群優(yōu)化算法，該算法通過不同種群之間的協(xié)作提高收斂精度。Jiang和Etorre[5]將混沌的方法引入到PSO中來避免早熟現(xiàn)象；Fan和 Zahara[6]提出了一種混合單純形的粒子群優(yōu)化算法，用于加快算法的收斂速度。文獻[7]提出了在小生鏡粒子群的最優(yōu)值附近定向地產生粒子來提高算法的探索能力；文獻[8]中引入人工蜂群搜索策略來解決粒子群算法易于陷入局部最優(yōu)的問題。這些算法雖然在一定程度上提高了PSO算法的性能，但在收斂速度和避免早熟方面很難達到平衡，特別是在處理多峰函數(shù)優(yōu)化問題時，收斂速度慢且易于陷入局部最優(yōu)。

針對標準PSO在解決多峰問題時，易陷入局部最優(yōu)解和算法收斂速度慢的問題，本文提出了一種引入人工蜂群和混合蛙跳搜索策略的粒子群算法（Artificial Bee Colony&Shuffled Frog Leaping Particle Swarm Optimization，ABCSFL-PSO）。首先，使用人工蜂群搜索策略來避免算法陷入局部最優(yōu)，再使用蛙跳算法中更新最差適應度粒子的方法，加快算法的收斂速度，提高算法的搜索精度。實驗結果表明，本文提出的算法能夠顯著提高粒子群算法的優(yōu)化能力和運算速度。

2 標準PSO算法

標準PSO算法通過模擬鳥群飛行中的覓食行為，把鳥類個體看作隨機的粒子，通過局部和全局最優(yōu)來引導粒子飛向最優(yōu)解。設在D維空間中，有N個粒子，每個粒子的位置xi=[xi1,xi2,…,xiD]，速度為vi=[vi1,vi2,…,viD]，其中，i=1,2,…,N，并設第i個粒子搜索到的歷史最優(yōu)位置為pi，整個粒子群搜索到的最優(yōu)位置為pg，則粒子的位置和速度更新公式分別為：

其中，w為慣性權值，c1和c2是學習參數(shù)，r1和r2為[0,1]之間的隨機數(shù)。

3 引入蛙跳搜索策略的人工蜂群粒子群算法

3.1 人工蜂群搜索策略

Karaboga[9]在2006年提出了一種新的群體智能優(yōu)化算法——人工蜂群優(yōu)化算法（Artificial Bee Colony，ABC）。ABC主要通過模擬蜂群的采蜜行為來實現(xiàn)對求解問題的優(yōu)化，它在解決多峰問題時具有優(yōu)秀的探索能力，其探索能力主要通過式（3）函數(shù)實現(xiàn)：

3.2 混合蛙跳局部搜索策略

混合蛙跳算法SFLA（Shuffled Frog Leaping Algorithm）是由Eusuff和Lansey[10]于2003年提出的一種基于群體智能的優(yōu)化算法。該算法具有較好的全局探索能力和較快的收斂速度，而且魯棒性強等優(yōu)點。

混合蛙跳算法搜索是通過如下公式每次更新適應度最差的粒子：

其中，i∈{1 ,2,…,N} ，Di為移動步長，Xb和Xw分別是種群中適應度最優(yōu)的粒子位置和適應度最差的粒子位置，rand為[0 ,1]之間的隨機數(shù)。

通過公式可以看出混合蛙跳算法（SFLA）是通過在全局最優(yōu)粒子值引導下更新最差粒子值來搜索最優(yōu)解。

3.3 ABCSFL-PSO算法

3.3.1 算法思想

由于人工蜂群搜索策略能夠有效地避免陷入局部最優(yōu)，而混合蛙跳算法通過更新最差適應度粒子來搜索最優(yōu)解。受這兩種搜索機制的啟發(fā)，本文將人工蜂群和混合蛙跳算法的搜索策略結合，綜合混合蛙跳算法在加速收斂和人工蜂群算法在避免局部最優(yōu)方面的優(yōu)勢，提出了ABCSFL-PSO算法。

3.3.2 算法步驟

ABCSFL-PSO算法是采用文獻[11]和文獻[12]提出的混沌和反學習的方法進行初始化的，目的在于加快收斂速度和提高精度。算法步驟如下：

步驟1初始化參數(shù)，用混沌和反學習方法初始化粒子。

步驟2對每個粒子利用標準粒子群算法的公式（1）和（2）更新粒子速度和位置。

步驟3利用人工蜂群的局部搜索策略的公式（3）在全局最優(yōu)解附近搜索新的解。

步驟4利用公式（4）和（5）計算適應度最差的Z個粒子，如果更新后粒子適應度改善則更新粒子位置，否則不更新粒子位置。

步驟5如果滿足要求，則算法執(zhí)行結束，并輸出最優(yōu)值；否則，轉至步驟2繼續(xù)執(zhí)行。

3.3.3 算法偽代碼

偽代碼如下所示：

其中，K和M為固定值，p為最優(yōu)值的位置，pg為全局最優(yōu)粒子位置，vi為粒子速度，pi為第i個粒子的局部最優(yōu)位置，xw為適應度最差的粒子位置。

4 仿真實驗及結果分析

4.1 測試函數(shù)

為了證明ABCSFL-PSO算法的有效性，本文對文獻[13]中的12個標準測試函數(shù)進行仿真實驗。其中，Sphere函數(shù)和Rosenbrock函數(shù)是單峰函數(shù)，其他的均為多峰函數(shù)。表1為這12個標準測試函數(shù)的維數(shù)、搜索范圍和最優(yōu)解。

表1 測試函數(shù)的維數(shù)、搜索空間和最優(yōu)值

4.2 實驗及結果分析

為了檢驗本文所提出算法的有效性，將本文算法與文獻[8]提出的PSOSW算法以及標準粒子群算法（BPSO）作比較。實驗中，慣性權重w采用線性遞減策略，最大值為0.9最小值為0，種群大小為30，維度D=50，K=300最大迭代次數(shù)為150 000次，采用Matlab2008a軟件進行仿真實驗。表2為3個算法在12個測試函數(shù)上進行50次獨立實驗并求平均值的結果，其中，平均適應度表示算法的尋優(yōu)能力，標準方差表示算法的穩(wěn)定性。通過實驗結果可以得出，在平均適應度指標中，除f7外，其余的測試函數(shù)ABCSFL-PSO算法的搜索精度都高于其他對比算法，特別是在f1,f2,f5,f6這4個測試函數(shù)上搜索精度明顯高于對比算法；在標準方差指標中，本文算法穩(wěn)定性明顯高于對比算法，特別是在f1表現(xiàn)的尤為明顯。

表2 運行50次的平均適應值和方差

圖1～6展示了BPSO、PSOSW、ABCSFL-PSO三種算法在不同測試函數(shù)中的收斂曲線對比，以說明本文算法具有更快的收斂速度。從實驗圖可以看出，本文提出的ABCSFL-PSO算法收斂速度最快，不僅在收斂速度上具有明顯的優(yōu)勢，同時也進一步提高了搜索精度。由于篇幅有限，本文只列舉了具有代表性的6個測試函數(shù)對比圖，在其他測試函數(shù)上也具有相似的性能。

圖1 f1函數(shù)的收斂性比比較

圖2 f4函數(shù)的收斂性比比較

圖3 f5函數(shù)的收斂性比比較

圖4 f6函數(shù)的收斂性比比較

圖5 f8函數(shù)的收斂性比比較

圖6 f9函數(shù)的收斂性比比較

5 結束語

由于標準粒子群算法在尋優(yōu)時存在收斂速度慢，易于陷入局部最優(yōu)等問題，本文引入人工蜂群搜索策略和混合蛙跳算法搜索策略的粒子群算法。該算法通過人工蜂群搜索策略增強探索能力，再使用混合蛙跳算法的搜索策略加速收斂并進一步提高收斂精度。仿真實驗表明該算法在收斂速度和探索能力上具有良好的性能，能夠有效解決多峰函數(shù)問題。

[1]Kennedy J，Eberhartr C.Particle swarm optimization[C]//Proc of IEEE Int Conf on Neural Networks.Perth：IEEE Piscataway，1995：1942-1948.

[2]Shi Y H，Eberhart R C.A modified partile swarm optimizer[C]//Proceedingsofthe 1998 IEEE International Conference on Evolutionary Computation（CEC98），Anchorage，Alaska，USA，4-9 May 1998：69-73.

[3]Jiao B，Lian Z G，Gu X S.A dynamic inertia weight particle swarm optimization algorithm[J].Chaos Solitons&Fractals，2008，37（3）：698-705.

[4]Bergh F V D，Engelbreeht A P.A cooperative approaeh to partiele swarm optimization[J].IEEE Trans on Evolutionary Computation，2004，8（3）：225-239.

[5]Jiang C W，Etorre B.A hybrid method of chaotic particle swarm optimization and linear interior for reactive power optimization[J].Mathematics and Computers in Simulation，2005，68（1）：57-65.

[6]Fan S，Zahara E.Hybrid simplex search and particle swarm optimization for unconstratined optimization problems[J].European J of Operational Research，2007，181（2）：527-548.

[7]Qu B Y，Liang J J，Suganthan P N.Niching Particle swarm optimization with local search for multi-modal optimization[J].Information Sciences，2012，197：131-143.

[8]高衛(wèi)峰，劉三陽，焦合華，等.引入人工蜂群搜索算子的粒子群算法[J].控制與決策，2012，27（6）：833-838.

[9]Karaboga D，Basturk B.A powerful and efficient algorithm for numerical function optimization：Artificial bee colony（ABC）algorithm[J].J of Global Optimization，2007，39（3）：459-171.

[10]Eusuff MM，Lansey K E.Optimization of water distribution network design using shuffled frog leaping algorithm[J].Journal of Water Resources Planning and Management，2003，129（3）：10-225.

[11]Liu B，Wang L，Jin Y H，et al.Improved particle swarm optimization combined with chaos[J].Chaos，Solitons&Fractals，2005，25（2）：1261-1271.

[12]Rahnama S，Tizhoosh H R，Salama M M A.Oppositionbased differential evolution[J].IEEE Trans on Evolutionary Computation，2008，12（1）：64-79.

[13]Liang J J，Qin A K，Suganthan P N，et al.Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J].IEEE Trans on Evolutionary Computation，2006，10（3）：281-295.