王聯(lián)國，龔亞星

(1.甘肅農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，甘肅 蘭州 730070；2.甘肅農(nóng)業(yè)大學(xué)工學(xué)院，甘肅 蘭州 730070)

一種單種群混合蛙跳算法

王聯(lián)國1,2，龔亞星2

(1.甘肅農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，甘肅 蘭州 730070；2.甘肅農(nóng)業(yè)大學(xué)工學(xué)院，甘肅 蘭州 730070)

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

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

1 引言

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

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

2 單種群混合蛙跳算法

2.1 基本思想

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

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

2.2 更新策略

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

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

(1)

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

(2)

(3)

2.3 算法流程

算法流程如下：

Step 1 隨機產(chǎn)生種群規(guī)模為F只青蛙的種群，設(shè)置迭代次數(shù)、學(xué)習(xí)因子等參數(shù)；

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

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

Step 4 計算每只青蛙個體的適應(yīng)度，更新全局最優(yōu)個體Xg；

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

Step 6 終止條件是否滿足？如果滿足，結(jié)束迭代，輸出最優(yōu)解Xg，否則轉(zhuǎn)向Step 3。

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

2.4 時間復(fù)雜度分析

SPSFLA在實現(xiàn)的過程中，有以下幾個主要操作：

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

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

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

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

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

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

具有較小的時間復(fù)雜度。

3 仿真實驗

3.1 實驗設(shè)計

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

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

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

Table 1 Parameters of test functions

3.2 實驗結(jié)果及分析

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

Table 2 Experimental results of three algorithms

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

[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].計算機工程與應(yīng)用,2011,47(18):4-8.

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

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

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

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

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

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

龔亞星(1990-),女,甘肅西和人，碩士生,研究方向為計算智能，農(nóng)業(yè)電氣化與自動化。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

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

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

TP18

A

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

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

通信地址：730070 甘肅省蘭州市安寧區(qū)甘肅農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院

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