一種單種群混合蛙跳算法

王聯國，龔亞星

(1.甘肅農業大學信息科學技術學院，甘肅 蘭州 730070；2.甘肅農業大學工學院，甘肅 蘭州 730070)

一種單種群混合蛙跳算法

王聯國1,2，龔亞星2

(1.甘肅農業大學信息科學技術學院，甘肅 蘭州 730070；2.甘肅農業大學工學院，甘肅 蘭州 730070)

針對SFLA算法運行速度較慢、在優化部分函數問題時精度不高和易陷入局部最優的缺點，提出了一種單種群混合蛙跳算法SPSFLA。該算法采用單個種群，無需對整個種群進行排序，每個個體通過向群體最優個體和群體中心位置學習進行更新。如果當前個體學習沒有進步，則對群體最優個體進行變異，并用變異的結果替代當前個體，加快了算法的運行速度和收斂速度，提高了優化精度。仿真實驗結果表明，該算法具有更好的優化性能。

群體智能；混合蛙跳算法；單種群；加速因子；聚群行為

1 引言

混合蛙跳算法SFLA(Shuffled Frog Leaping Algorithm)是2003年由Eusuff M和Lansey K E提出的一種基于群體智能的生物進化算法[1]，在水資源網絡分配問題、函數優化、成品油管網優化、組合優化、圖像處理、多用戶檢測、電力系統優化等方面得到了初步應用，并取得了良好的效果。但是，SFLA具有運行速度較慢、求解部分函數優化問題時不夠理想的缺陷，因此，很多學者對其進行了改進。文獻[2]借鑒差分進化算法DE中DEb1版本的優點，將SFLA與DE有機融合，提出一種蛙跳和差分進化混合算法，有效克服了SFLA容易早熟的缺陷；文獻[3]在SFLA深度搜索方向上融合極值動力學優化，對SFLA進行了改進，拓展了算法搜索空間，能夠幫助算法跳出局部極值，增強了其全局搜索能力；文獻[4]通過對SFLA局部更新策略以及全局信息交流策略的改進，提出了一種能高效求解背包問題的新算法；文獻[5]在SFLA中引入自適應因子，提高了個體向局部最優或全局最優個體學習的能力，加快了算法的收斂速度；文獻[6]將微粒群算法和SFLA相融合，在蛙群和微粒群兩群體獨立進化過程中，設計了一種兩群之間的信息替換策略以及一種相互協作方式，并適時對其所有個體最好位置進行隨機擾動，實驗表明新算法性能優越；文獻[7]改進了SFLA算法的子群個體優化方式，并提出了最優引導概率和次優引導概率，提高了算法性能；文獻[8]提出了一種新的移動距離更新方式對SFLA進行改進，該方式根據新解的適應度高低，決定是否將某分量上一次移動的距離引入本次移動的距離，增強了算法的尋優性能；文獻[9]把生物學中的吸引排斥思想引入到混合蛙跳算法中，修正了其更新策略，提高了算法的收斂速度，有效地避免了SFLA早熟收斂的問題，改善了算法對復雜問題的搜索效率。

然而，以上文獻對算法的不同改進方法都采用基本SFLA中將種群劃分為多個子群的多種群進化模式，雖然多種群能使算法在多個方向進行進化，使其不易陷入局部最優，但是在種群間進行全局信息交流時，不斷地排序和劃分子群的操作，增加了算法實現的復雜度，耗費大量時間。因此，本文提出一種單種群混合蛙跳算法SPSFLA(Single Population Shuffled Frog Leaping Algorithm)，該算法采用單個種群，無需對整個種群進行排序，每個個體向群體最優個體學習，如果沒有進步，則向群體中心位置學習，如果仍然沒有進步，則對群體最優個體進行變異，并用變異的結果替代當前個體，從而加快了算法的運行速度和收斂速度，提高了優化精度。此外，通過仿真實驗驗證了新算法的有效性。

2 單種群混合蛙跳算法

2.1 基本思想

基本混合蛙跳算法采用多個子群，對子群內最差個體通過更新策略進行進化，在進化過程中需要對整個種群進行排序并分組，在每個子群中求子群極值個體和最差個體，計算量大，運行速度較慢。

單種群混合蛙跳算法采用單個種群，無需對整個種群進行排序，每個個體向群體最優個體學習，如果沒有進步，則向群體中心位置學習，如果仍然沒有進步，則對群體最優個體進行變異，并用變異的結果替代當前個體，因此加快了算法的運行速度和收斂速度。

2.2 更新策略

設青蛙種群規模為F，第i只青蛙的狀態向量Xi=(xi1，xi2，…，xin)，n表示變量的維數，青蛙當前所在位置的適應度表示為Y=f(Xi)，其中Y為目標函數值。整個種群迄今為止找到的全局最好適應度的個體表示為Xg=(xg1，xg2，…，xgn) 。整個種群的中心位置為Xc=(xc1，xc2，…，xcn) 。個體i按式(1)向全局最優個體Xg學習，如果得到的新個體newXi=(newxi1，newxi2，…，newxin)優于原來的Xi，則用newXi取代Xi。如果沒有改進，則按式(2)向群體中心位置Xc學習，如果得到的新個體newXi優于原來的Xi，則用newXi取代Xi。如果仍然沒有改進，則按式(3)隨機產生一個新的個體取代原來的Xi。

newxij=xij+rand()×C×(xgj-xij)

(1)

newxij=xij+rand()×C×(xcj-xij)

(2)

(3)

2.3 算法流程

算法流程如下：

Step 1 隨機產生種群規模為F只青蛙的種群，設置迭代次數、學習因子等參數；

Step 2 對每只青蛙個體，計算其適應度，找出全局最優個體Xg，計算群體中心位置Xc；

Step 3 對每只青蛙個體按照更新策略更新位置；

Step 4 計算每只青蛙個體的適應度，更新全局最優個體Xg；

Step 5 計算群體中心位置Xc；

Step 6 終止條件是否滿足？如果滿足，結束迭代，輸出最優解Xg，否則轉向Step 3。

當種群規模較大時，為了提高計算群體中心位置Xc的速度，按隨機抽樣方式選取M個個體，計算M個個體的中心位置，并用其代替群體中心位置Xc。

2.4 時間復雜度分析

SPSFLA在實現的過程中，有以下幾個主要操作：

(1)初始化F個個體，每個個體是D維，其時間復雜度為O(D·F)；

(2)對F個個體計算適應度值，適應度函數的復雜度一般都是O(D)，所以其時間復雜度為O(D·F)；

(3)在一次迭代中，對已經計算出的F個個體的適應度值進行統計，找出全局最優個體，其時間復雜度為O(F)，并計算群體中心位置，其時間復雜度為O(D·F)；

(4)在一次迭代中，需要對F個個體的每一維進行更新，故其時間復雜度為O(D·F)；

(5)在一次迭代后，判斷中止條件，時間復雜度為O(1)。

設最大迭代次數為Itmax，當Itmax足夠大時，低次冪影響可忽略不計，因此SPSFLA的時間復雜度為O(Itmax·D·F)。而在基本SFLA中，對F個個體按照適應度值進行降序排列的操作，時間復雜度為O(D·F·F)，系為其最大時間復雜度，若設其混合迭代次數為Itmax，則SFLA的時間復雜度為O(Itmax·D·F2)。這說明，SPSFLA較之SFLA

具有較小的時間復雜度。

3 仿真實驗

3.1 實驗設計

本文分別用SFLA、文獻[9]提出的ISFLA以及SPSFLA求八個基準測試函數的最小值，進行對比實驗，以評價改進算法的優化性能。

實驗中，各算法的參數設置如下：對于SPSFLA，種群規模F=200，學習因子C=2。對于SFLA和ISFLA，種群規模仍為200只青蛙，但要將其分為20個子群，每個子群含10只青蛙，子群內更新迭代次數為10，步長Dmax=Xmax/5(Xmax為搜索范圍的最大值)，最大迭代次數均設為500。由于SFLA和ISFLA總的迭代次數為20個子群×每個子群10次迭代×500次迭代=100000，SPSFLA總的迭代次數為200個個體×每個個體1次迭代×500次迭代=100000，三種算法總的迭代次數相同，因此具有可比性。八個測試函數及其實驗的相關參數見表1。

算法的性能評估采用如下方法：固定進化迭代次數，評估其收斂速度、精度、穩定性和達到目標精度的成功率，其中，成功率=達到目標精度的運行次數/總實驗次數。各算法的最終測試結果采用獨立運行30次后的平均值。

Table 1 Parameters of test functions

3.2 實驗結果及分析

表2為30次實驗所得的三個算法的平均值、標準差、成功率以及平均運行時間?？梢钥闯?，除了f4函數外，SPSFLA對于其余七個函數的平均最優值、標準差均好于SFLA和ISFLA，尤其對于f3函數，SPSFLA找到了其全局最優值0；對于f4函數，雖然SPSFLA的平均最優值及標準差略遜于ISFLA，但要比SFLA好得多。這說明SPSFLA的求解精度較高，穩定性好。成功率方面，SPSFLA對于除f4函數以外的其它七個函數均能達到100%，尤其對于f1、f5、f8函數在其余兩種算法都為0%的成功率時，SPSFLA表現出了更強的尋優能力及穩定性。此外，SPSFLA算法運行的平均時間都要遠少于SFLA和ISFLA。綜上所述，總體上，SPSFLA求解精度高、穩定性好、運行速度快。

Table 2 Experimental results of three algorithms

圖1～圖8是函數f1～f8采用三種算法運行30次后得到的平均極值的進化曲線，在圖1～圖7中，縱坐標用函數平均極值的常用對數表示，在圖8中，因f8函數的極值為負，縱坐標直接用函數的平均極值表示，各圖中橫坐標均為迭代次數。當函數值為0時，則對函數值均加上10-5作為截止值。從圖中可以看出，對所有八個函數而言，SPSFLA總能最先收斂，除了對f4函數的最終收斂值略差于ISFLA，對其它函數，SPSFLA總是收斂于更好的解，這說明，SPSFLA收斂速度較快且優化精度較高。

Figure 1 Average evolutionary curve of f1圖1 圖1 函數f1平均極值的進化曲線

Figure 2 Average evolutionary curve of f2圖2 函數f2平均極值的進化曲線

Figure 3 Average evolutionary curve of f3圖3 函數f3平均極值的進化曲線

Figure 4 Average evolutionary curve of f4圖4 函數f4平均極值的進化曲線

Figure 5 Average evolutionary curve of f5圖5 函數f5平均極值的進化曲線

Figure 6 Average evolutionary curve of f6圖6 函數f6平均極值的進化曲線

Figure 7 Average evolutionary curve of f7圖7 函數f7平均極值的進化曲線

Figure 8 Average evolutionary curve of f8圖8 函數f8平均極值的進化曲線

4 結束語

針對SFLA算法運行速度慢、對部分函數優化精度不高等問題，提出了一種單種群混合蛙跳算法，該算法采用單個種群，結合人工魚群算法中的聚群行為思想，對群體極值進行變異并替代隨機算子，加快了算法的運行速度和收斂速度，提高了算法的優化精度。仿真實驗結果表明，該算法具有更好的優化性能。

[1] Eusuff M, Lansey K E. Optimization of water distribution network design using the shuffled frog leaping algorithm[J]. Water Resources Planning and Management,2003,129 (3):210-225.

[2] He Bing, Che Lin-xian, Liu Chu-sheng. Novel hybrid shuffled frog leaping and differential evolution algorithm[J]. Computer Engineering and Applications,2011,47(18):4-8. (in Chinese)

[3] Luo Jian-ping, Chen Min-rong. Study on trajactory and convergence analysis of shuffled frog leaping algorithm and its improved algorithm[J]. Signal Processing, 2010,26(9):1428-1433. (in Chinese)

[4] Li Z F, Zhou Y, Cheng P. An improved shuffled frog leaping algorithm for knapsack problem[J]. Advances in Intelligent and Soft Computing,2012(169):299-303.

[5] Dai Yong-qiang, Wang Lian-guo, Shi Qiu-hong, et al. Performance analysis of improved SFLA and the application in economic dispatch of power system[J]. Power System Protection and Control, 2012,40(10):77-83. (in Chinese)

[6] Sun Hui, Long Teng, Zhao Jia. Swarm intelligence algorithm based on combination of shuffled frog leaping algorithm and particle swarm optimization[J]. Journal of Computer Applications, 2012,32(2):428-431. (in Chinese)

[7] Zhang J M, Wu C C. Improved shuffled frog leaping algorithm and its application[J]. Applied Mechanics and Materials, 2012(155/156):92-96.

[8] Zheng Shi-lian,Lou Cai-yi,Yang Xiao-niu.Cooperative spectrum sensing for congnitive radios based on a modified shuffled frog leaping algorithm[J]. Acta Physica Sinica, 2010,59(5):3611-3617. (in Chinese)

[9] Zhao Peng-jun, Liu San-yang. Shuffled frog leaping algorithm for solving complex functions[J]. Application Research of Computers, 2009,26(7):2435-2437. (in Chinese)

附中文參考文獻：

[2] 何兵,車林仙,劉初升.一種蛙跳和差分進化混合算法[J].計算機工程與應用,2011,47(18):4-8.

[3] 駱劍平,陳泯融.混合蛙跳算法及其改進算法的運動軌跡及收斂性分析[J].信號處理,2010,26(9):1428-1433.

[5] 代永強,王聯國,施秋紅,等.改進的混合蛙跳算法性能分析及其在電力系統經濟調度中的應用[J].電力系統保護與控制,2012,40(10):77-83.

[6] 孫輝,龍騰,趙嘉.基于微粒群與混合蛙跳融合的群體智能算法[J].計算機應用,2012,32(2):428-431.

[8] 鄭仕鏈,樓才義,楊小牛. 基于改進混合蛙跳算法的認知無線電協作頻譜感知[J].物理學報,2010,59(5):3611-3617.

[9] 趙鵬軍,劉三陽.求解復雜函數優化問題的混合蛙跳算法[J].計算機應用研究,2009,26(7):2435-2437.

WANG Lian-guo,born in 1968,PhD,professor,his research interest includes intelligent information processing.

龔亞星(1990-),女,甘肅西和人，碩士生,研究方向為計算智能，農業電氣化與自動化。E-mail:yaxing918@126.com

GONG Ya-xing,born in 1990,MS candidate,her research interests include computational intelligence, agricultural electrification and automation.

A single population shuffled frog leaping algorithm

WANG Lian-guo1,2，GONG Ya-xing2
(1.College of Information Science and Technology,Gansu Agricultural University,Lanzhou 730070;2.College of Engineering,Gansu Agricultural University,Lanzhou 730070,China)

Aiming at the shortcomings of shuffled frog leaping algorithm(SFLA) such as ease of trapping into local optimum, low optimization precision and slow speed when it is used to optimize some functions, a Single Population Shuffled Frog Leaping Algorithm (SPSFLA) is proposed. Without sorting the whole population, this new algorithm adopts single population. The individuals are updated by learning from the global best individual and the global middle position. If the current individual is not improved, the global best individual will be mutated and the current individual will be replaced by the new one. Those enhance the running speed, the convergence rate and the optimization precision of SPSFLA. The simulation results show that the improved algorithm has better optimization performance.

swarm intelligence;shuffled frog leaping algorithm;single population;acceleration factor;swarm behavior

2012-10-15;

2013-01-09

國家自然科學基金資助項目(61063028)；甘肅省教育信息化發展戰略研究項目(2011)

1007-130X(2014)03-0463-06

TP18

A

10.3969/j.issn.1007-130X.2014.03.015

王聯國(1968-),男,甘肅臨夏人，博士，教授，研究方向為智能信息處理。E-mail:wanglg@gsau.edu.cn

通信地址：730070 甘肅省蘭州市安寧區甘肅農業大學信息科學技術學院

Address:College of Information Science and Technology,Gansu Agricultural University,Anning District,Lanzhou 730070,Gansu,P.R.China