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

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

一種單種群混合蛙跳算法

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

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

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

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

1 引言

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

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

2 單種群混合蛙跳算法

2.1 基本思想

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

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

2.2 更新策略

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

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

(1)

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

(2)

(3)

2.3 算法流程

算法流程如下：

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

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

Step 3 對(duì)每只青蛙個(gè)體按照更新策略更新位置；

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

Step 5 計(jì)算群體中心位置Xc；

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

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)計(jì)

本文分別用SFLA、文獻(xiàn)[9]提出的ISFLA以及SPSFLA求八個(gè)基準(zhǔn)測(cè)試函數(shù)的最小值，進(jìn)行對(duì)比實(shí)驗(yàn)，以評(píng)價(jià)改進(jìn)算法的優(yōu)化性能。

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

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

Table 1 Parameters of test functions

3.2 實(shí)驗(yàn)結(jié)果及分析

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

Table 2 Experimental results of three algorithms

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

針對(duì)SFLA算法運(yùn)行速度慢、對(duì)部分函數(shù)優(yōu)化精度不高等問(wèn)題，提出了一種單種群混合蛙跳算法，該算法采用單個(gè)種群，結(jié)合人工魚(yú)群算法中的聚群行為思想，對(duì)群體極值進(jìn)行變異并替代隨機(jī)算子，加快了算法的運(yùn)行速度和收斂速度，提高了算法的優(yōu)化精度。仿真實(shí)驗(yàn)結(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)

附中文參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

TP18

A

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

王聯(lián)國(guó)(1968-),男,甘肅臨夏人，博士，教授，研究方向?yàn)橹悄苄畔⑻幚?。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