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

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

江南大學 物聯網工程學院，江蘇 無錫 214122

1 引言

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

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

2 標準PSO算法

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

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

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

3.1 人工蜂群搜索策略

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

3.2 混合蛙跳局部搜索策略

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

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

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

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

3.3 ABCSFL-PSO算法

3.3.1 算法思想

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

3.3.2 算法步驟

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

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

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

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

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

步驟5如果滿足要求，則算法執行結束，并輸出最優值；否則，轉至步驟2繼續執行。

3.3.3 算法偽代碼

偽代碼如下所示：

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

4 仿真實驗及結果分析

4.1 測試函數

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

表1 測試函數的維數、搜索空間和最優值

4.2 實驗及結果分析

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

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

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

圖1 f1函數的收斂性比比較

圖2 f4函數的收斂性比比較

圖3 f5函數的收斂性比比較

圖4 f6函數的收斂性比比較

圖5 f8函數的收斂性比比較

圖6 f9函數的收斂性比比較

5 結束語

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

[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]高衛峰，劉三陽，焦合華，等.引入人工蜂群搜索算子的粒子群算法[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.