王 林，萬小雨,萬建超

(1.華中科技大學(xué)管理學(xué)院,湖北 武漢 430074;2.普天信息技術(shù)有限公司，北京 100080)

1 引言

蛙跳算法SFLA(Shuffled Frog Leaping Algorithm)是由Muzaffar和Kevin在2003年提出的，他們通過模擬青蛙種群的自然覓食過程設(shè)計出的一種群智能優(yōu)化算法，并將其成功運(yùn)用于地下水資源管理問題[1]?；旌贤芴惴ㄊ且环N基于群體協(xié)同搜索的算法，它融合了模因算法MA(Memetic Algorithm)和微粒群算法PSO(Partical Swarm Optimization)的優(yōu)點(diǎn)，將基因進(jìn)化和種群進(jìn)化有效集成在一起。

蛙跳算法的原理簡單、控制參數(shù)少，具有柔性的結(jié)構(gòu)框架和較強(qiáng)的全局信息共享能力等優(yōu)點(diǎn)，已被成功運(yùn)用于多種自然科學(xué)以及工程領(lǐng)域的復(fù)雜優(yōu)化問題[2-4]。蛙跳算法自提出以后，眾多學(xué)者對其進(jìn)行理論改進(jìn)和應(yīng)用推廣。如許方等人[5]提出一種SFLA與K均值相結(jié)合的聚類算法，抑制了早熟收斂問題；趙鵬軍等人[6]在SFLA產(chǎn)生初始種群時采用對立學(xué)習(xí)策略提高了解的質(zhì)量，并結(jié)合差分進(jìn)化算法提高了種群的多樣性；Roy等人[7]將遺傳算法的交叉算子運(yùn)用到最差青蛙個體向最好青蛙個體跳動的過程中，產(chǎn)生兩個實驗個體，提高了種群迭代效率；Zhu等人[8]讓所有青蛙個體在每一次更迭中進(jìn)行跳動，并利用三因素方差分析方法對SFLA的控制參數(shù)進(jìn)行分析，設(shè)計出一種自適應(yīng)的SFLA，實驗結(jié)果說明改進(jìn)后的SFLA收斂精度有所提高，但是收斂時間增長；Luo等人[9]采用多種策略產(chǎn)生新個體，并加入一種改進(jìn)的克隆選擇過程，提高了產(chǎn)生的新個體的質(zhì)量，以及增加了種群的多樣性；肖文顯等人[10]將蛙跳算法的組內(nèi)尋優(yōu)思想嵌入和聲算法中，設(shè)計了一種和聲蛙跳算法，實現(xiàn)了兩種算法的耦合動態(tài)搜索。

但是，標(biāo)準(zhǔn)蛙跳算法和現(xiàn)有的改進(jìn)蛙跳算法的搜索時間長，存在個體之間信息交流不足、容易陷入局部最優(yōu)等問題。針對這些問題，本文提出一種改進(jìn)的蛙跳算法，加入實驗個體選擇機(jī)制，增加局部搜索中青蛙個體改進(jìn)個數(shù)，并將差分進(jìn)化算法的交叉算子和變異算子運(yùn)用到青蛙個體跳動策略中，增加個體之間的交流。實驗結(jié)果表明本文所設(shè)計的選擇差分混合蛙跳算法提高了蛙跳算法的性能，該算法與其它三種改進(jìn)的群智能優(yōu)化算法相比，具有更好的有效性和穩(wěn)定性。

2 標(biāo)準(zhǔn)蛙跳算法與缺點(diǎn)分析

2.1 蛙跳算法基本原理

SFLA的基本思想是：在一個水池中有一群青蛙尋找食物，每一只青蛙都有自己尋找食物的路徑信息，青蛙通過不斷跳動改變自己與食物之間的距離；青蛙個體按照適應(yīng)度大小分為m組，每個青蛙個體攜帶自己的路徑信息，組內(nèi)進(jìn)行信息交換，最優(yōu)青蛙個體指導(dǎo)組內(nèi)局部搜索方向，按式(1)～式(3)更新組內(nèi)當(dāng)代最差個體，重復(fù)這個過程直到滿足組內(nèi)搜索終止條件，具體操作如下：

Step1設(shè)置算法參數(shù)，包括組內(nèi)進(jìn)化代數(shù)Ne、種群總進(jìn)化代數(shù)maxgen、子種群數(shù)量m、組內(nèi)個體數(shù)n、種群規(guī)模popsize=m×n、最大跳動步長Smax。

Step2隨機(jī)生產(chǎn)初始種群pop，種群中第i個個體表示為Xi=(Xi1,Xi2,Xi3,…,Xid)，其中d是求解問題的維度，Xi∈[lb,ub]。計算初始種群中每個個體的適應(yīng)度，并按升序排列，找出初始種群最優(yōu)個體gx。

Step3將種群分為m組，每組n只青蛙。分組規(guī)則是，排序后的個體，將第1、第1+m、第1+2m、…、第popsize-m+1個個體放入第一組，將第2、第2+m、第2+2m、…、第popsize-m+2個個體放入第二組，以此類推。分組后找出組內(nèi)最優(yōu)個體pb和最差個體pw。

Step4組內(nèi)進(jìn)行局部搜索操作。按照式(1)～式(3)對pw進(jìn)行更新，具體操作如下。

①采取組內(nèi)最優(yōu)更新策略。組內(nèi)最差個體pw向組內(nèi)最優(yōu)個體pb方向跳動更新。通過式(1)計算跳動步長S，如果Sj<-Smax，則Sj=-Smax；如果Sj>Smax，則Sj=Smax。然后通過式(2)對pw進(jìn)行更新操作，如果tempjub, 則tempj=ub。計算temp的適應(yīng)度值，如果temp的適應(yīng)度小于pw,則pw=temp進(jìn)入Step 5，否則繼續(xù)進(jìn)行操作②。

S=rand[0,1]×(pb-pw),S∈[-Smax,Smax]

(1)

temp=pw+S,tempj∈[lb,ub]

(2)

②采取全局最優(yōu)更新策略。組內(nèi)最差個體pw向全局最優(yōu)個體gx方向跳動更新。通過式(3)計算跳動步長S，如果Sj<-Smax，則Sj=-Smax；如果Sj>Smax，則Sj=Smax。然后通過式(2)對pw進(jìn)行更新操作，如果tempjub,則tempj=ub。計算temp的適應(yīng)度值，如果temp的適應(yīng)度小于pw,則pw=temp進(jìn)入Step 5，否則繼續(xù)進(jìn)行操作③。

S=rand[0,1]×(gx-pw),S∈[-Smax,Smax]

(3)

③隨機(jī)生成新個體更新策略。隨機(jī)生產(chǎn)一個新個體替代pw,進(jìn)入Step 5。

Step5對組內(nèi)個體重新計算適應(yīng)度，并找出更新后的pb和pw。判斷是否滿足組內(nèi)更新終止條件，若滿足，則進(jìn)行Step 6，否則進(jìn)行Step 4。

Step6混合洗牌，將完成局部搜索的各組個體重新混合，計算個體適應(yīng)度，并按照適應(yīng)度大小重新排序，找出此時的gx。判斷是否滿足全局搜索終止條件，若滿足，則進(jìn)行Step 7，否則進(jìn)行Step 3。

Step7輸出最佳個體gx和對應(yīng)的適應(yīng)度值，則為找出的最優(yōu)解。

標(biāo)準(zhǔn)蛙跳算法的流程如圖1所示。

Figure 1 Flowchart of SFLA圖1 標(biāo)準(zhǔn)蛙跳算法流程圖

2.2 標(biāo)準(zhǔn)蛙跳算法的局限性

(1)標(biāo)準(zhǔn)SFLA和其它智能優(yōu)化算法一樣，沒有參數(shù)設(shè)置的最優(yōu)組合，而是根據(jù)不同的具體問題產(chǎn)生差異，并沒有指導(dǎo)性的原則，僅能通過大量的實驗得到。參數(shù)設(shè)置沒有通用性，算法的穩(wěn)定性不高。

(2)標(biāo)準(zhǔn)SFLA的跳動步長始終保持固定值。進(jìn)化最初最大步長太小，降低收斂速度；進(jìn)化進(jìn)入尾聲時，最大步長又太大，減弱局部搜索能力。

(3)標(biāo)準(zhǔn)SFLA在局部搜索的時候，采用三種更新策略，除了隨機(jī)更新策略，另兩種策略都是通過最差值向最優(yōu)值方向進(jìn)行跳動，更新方式過于單調(diào)，造成組內(nèi)個體過分單一，種群多樣性不強(qiáng)，容易陷入局部最優(yōu)。并且在個體更新的過程中，忽略了同組內(nèi)其它個體，以及種群中其它個體的信息交流，可能會錯過很多優(yōu)秀的基因組合。

針對以上問題，本文提出一種選擇差分混合蛙跳算法，通過與差分進(jìn)化算法混合，并加入選擇機(jī)制和資源池操作，提高蛙跳算法的性能。

3 選擇差分混合蛙跳算法(SDSFLA)

3.1 SDSFLA改進(jìn)思路

SDSFLA(Selected Differential Shuffled Frog Leaping Algorithm)主要是對組內(nèi)局部搜索進(jìn)行改進(jìn)：增加一種選擇機(jī)制提高實驗個體的質(zhì)量；利用差分進(jìn)化算法的交叉算子、變異算子，增加個體與個體之間的信息交流；引入資源池操作，增加種群多樣性。SDSFLA的改進(jìn)思路如下：

(1)標(biāo)準(zhǔn)蛙跳算法中，每一次組內(nèi)更新只對最差個體進(jìn)行一次更新操作之后，就重新排序，效率很低。在SDSFLA中，我們對組內(nèi)第n-2、n-1、n個組內(nèi)最差的三個個體進(jìn)行更新操作，提高更新效率。

(2)組內(nèi)三種更新策略產(chǎn)生新個體，策略①維持標(biāo)準(zhǔn)蛙跳算法更新策略不變，策略②和策略③分別引入差分進(jìn)化算法的兩種變異算子。三種策略中，對于跳動更新后的實驗個體，引入差分進(jìn)化算法中的交叉操作，產(chǎn)生本次更新最終的實驗個體。

(3)SDSFLA的三種策略分別產(chǎn)生三種實驗個體，選擇最優(yōu)的實驗個體與原個體比較，這種操作有利于算法自適應(yīng)地選擇更好的個體進(jìn)入下一代。采用多種策略產(chǎn)生多個實驗個體，選擇最優(yōu)的，這種選擇機(jī)制有助于增強(qiáng)算法的通用性。

(4)建立變異算子F和交叉算子CR的資源池，SDSFLA三種策略對個體進(jìn)行更新時，隨機(jī)選擇F和CR的組合，增加種群多樣性。本文根據(jù)Lu等人[11]提到的F、CR組合，選擇了五組F、CR值,分別是[1，0.1],[1，0.9],[1，0.1],[0.8，0.2],[0.5，0.9],[0.5，0.3]。

3.2 SDSFLA局部搜索的執(zhí)行流程

Step1找出組內(nèi)最差的三個個體分別執(zhí)行Step 2到Step 4。

Step2對要進(jìn)行更新的個體local(i,:)，根據(jù)以下三個策略分別進(jìn)行更新操作，產(chǎn)生相對應(yīng)的三個實驗個體temp1、temp2、temp3，策略中F和CR的值是隨機(jī)從[F，CR]資源池中選取出來的。

策略①：組內(nèi)個體local(i,:)向組內(nèi)最優(yōu)個體pb方向跳動更新。組內(nèi)個體local(i,:)通過式(4)計算跳動步長S，如果Sj<-Smax，則Sj=-Smax；如果Sj>Smax，則Sj=Smax。然后通過式(5)對local(i,:)進(jìn)行更新操作，如果temp1jub，則temp1j=ub。對temp1j進(jìn)行交叉操作，如果rand

S=F×(pb-local(i,:)),S∈[-Smax,Smax]

(4)

temp1=(local(i,:))+S,tepm1j∈[lb,ub]

(5)

策略②：組內(nèi)個體local(i,:)通過式(6)計算跳動步長S，X1、X2是在組內(nèi)隨機(jī)選擇的兩個互不相同的個體，如果Sj<-Smax，則Sj=-Smax；如果Sj>Smax，則Sj=Smax。然后通過式(7)對local(i,:)進(jìn)行更新操作，如果temp2jub，則temp2j=ub。對temp2j進(jìn)行交叉操作，如果rand

S=F×(local(X1,:)-local(X2,:)),

S∈[-Smax,Smax]

(6)

temp2=gx+S,temp2j∈[lb,ub]

(7)

策略③ ：組內(nèi)個體local(i,:)通過式(8)計算跳動步長S，X1、X2、X3是在組內(nèi)隨機(jī)選擇的三個互不相同的個體，如果Sj<-Smax，則Sj=-Smax；如果Sj>Smax，則Sj=Smax。然后通過式(9)對local(i,:)進(jìn)行更新操作，如果temp3jub，則temp3j=ub。對temp3j進(jìn)行交叉操作，如果rand

S=F×(local(X1,:)-local(X2,:)),

S∈[-Smax,Smax]

(8)

temp3=(local(X3,:))+S,temp3j∈[lb,ub]

(9)

Step3將得出的三個實驗個體temp1、temp2、temp3的適應(yīng)度值進(jìn)行比較，選擇出適應(yīng)度最優(yōu)的個體作為最終的實驗個體temp。

Step4將最終實驗個體temp的適應(yīng)度值與local(i,:)的適應(yīng)度值進(jìn)行比較，如果最終實驗個體temp的適應(yīng)度值優(yōu)于local(i,:)的，則local(i,:)=temp，否則local(i,:)=local(i,:)。

Step5對組內(nèi)個體重新計算適應(yīng)度值，并且排序。判斷是否滿足組內(nèi)更新終止條件，若滿足，則退出組內(nèi)局部搜索，否則轉(zhuǎn)Step 1。

4 SDSFLA性能測試

4.1 測試函數(shù)介紹

為檢驗SDSFLA的性能，本文選取了16個被廣泛運(yùn)用的標(biāo)準(zhǔn)測試函數(shù)[12,13]，包括8個單峰函數(shù)和8個復(fù)雜多峰函數(shù)。所選取的測試函數(shù)具備不同的特征，如對稱、多極值、非線性、可分離或不可分離等。16個測試函數(shù)的具體描述如表1所示。

Table 1 Test functions

16個測試函數(shù)中F3理論最優(yōu)值為-1，F(xiàn)16理論最優(yōu)值為1-n，其它函數(shù)理論最優(yōu)值均為0。

4.2 測試結(jié)果

本文將所提出的SDSFLA與ADE(Adaptive DE)[14]、CMSFLA(Centroid Mutated-SFLA)[15]、EPSDE(Ensemble of mutation strategies and control Parameters with the DE)[16]三種智能優(yōu)化算法進(jìn)行比較。其中CMSFLA和ADE算法都是2015年剛發(fā)表的改進(jìn)SFLA和改進(jìn)DE算法，而EPSDE算法是在其他文獻(xiàn)中經(jīng)常被用來做比較的算法之一，所以本文將提出的SDSFLA與這三種算法進(jìn)行比較。

最大進(jìn)化代數(shù)maxgen設(shè)置為500，種群規(guī)模為50，本文提出的SDSFLA的分組數(shù)為10，局部搜索代數(shù)為10，函數(shù)維度分別設(shè)置為30和50，每種算法對每個函數(shù)獨(dú)立運(yùn)行20遍，運(yùn)算結(jié)果的平均值和標(biāo)準(zhǔn)差如表2和表3所示。

本文利用威爾科克森秩和檢驗(Wilcoxon’s rank sum test)，在統(tǒng)計顯著性為0.05的條件下，分析判斷統(tǒng)計結(jié)果，將本文提出的SDSFLA的測試結(jié)果分別與ADE、CMSFLA、EPSDE的測試結(jié)果比較，30維和50維的比較結(jié)果如表4和表5所示(其中√、×、≈代表算法結(jié)果差于、優(yōu)于、等于SDSFLA)。

圖2～圖5分別是較復(fù)雜的多峰函數(shù)F11、F12、F13、F14的優(yōu)化過程對比圖。

分析可知，針對這16個測試函數(shù)，SDSFLA明顯優(yōu)于其它三種算法。分析表3和表5的結(jié)果，30維函數(shù)中，SDSFLA與其他算法比較，11個優(yōu)于ADE和CMSFLA，13個優(yōu)于EPSDE，僅分別有1個、2個相比較差；50維函數(shù)中，SDSFLA與其他算法相比，12個優(yōu)于ADE、11個優(yōu)于CMSFLA，12個優(yōu)于EPSDE，僅分別有1個、2個、2個結(jié)果相比較差。對于少數(shù)幾個測試函數(shù)，雖然SDSFLA的運(yùn)行結(jié)果稍差于其它算法，但是對于這幾個測試函數(shù)，SDSFLA同樣也收斂到了比較理想結(jié)果。

對于F1、F2、F4、F5、F6、F7、F9、F11這八個函數(shù)，SDSFLA的運(yùn)算結(jié)果遠(yuǎn)遠(yuǎn)優(yōu)于其它三種算法。分析圖2～圖5，在有限的搜索代數(shù)內(nèi)，SDSFLA可以較快收斂到理想值。另外，通過分析標(biāo)準(zhǔn)差的結(jié)果，SDSFLA運(yùn)行結(jié)果的波動性小，證明SDSFLA的穩(wěn)定性較好。

Table 2 Experimental results of 30 variables

Table 3 Experimental results of 50 variables

Table 4 Comparison results based onWilcoxon’s rank sum test of 30 variables

Table 5 Comparison results based onWilcoxon’s rank sum test of 50 variables

Figure 2 Convergence results for F11圖2 F11收斂結(jié)果對比圖

Figure 4 Convergence results for F13圖4 F13收斂結(jié)果對比圖

Figure 5 Convergence results for F14圖5 F14收斂結(jié)果對比圖

5 結(jié)束語

本文將差分進(jìn)化算法中產(chǎn)生新個體的策略與標(biāo)準(zhǔn)混合蛙跳算法結(jié)合，設(shè)計出一種SDAFLA，主要貢獻(xiàn)如下：為解決混合蛙跳算法個體間信息交流不充分的問題，結(jié)合差分算法的變異算子和交叉算子，采用三種改進(jìn)策略產(chǎn)生新個體，加強(qiáng)局部搜索過程中個體與個體之間的信息交換；實驗個體選擇機(jī)制，能選擇更優(yōu)秀的新個體，加快收斂速度；引入資源池隨機(jī)選擇操作，增加了種群的多樣性。測試函數(shù)結(jié)果表明，SDSFLA是一種有效的智能優(yōu)化算法。

本文將三種改進(jìn)策略作為一個組合，并在資源池中隨機(jī)選擇F、CR兩種控制參數(shù)的值，理論上加強(qiáng)了種群的多樣性，提高了產(chǎn)生的實驗個體的優(yōu)秀率。未來可以利用本文提出的SDSFLA的框架，改進(jìn)新個體產(chǎn)生策略的組合，以及資源池內(nèi)控制參數(shù)的組合，加強(qiáng)SDSFLA解決更復(fù)雜更高維度的目標(biāo)函數(shù)的能力，并用CEC2005中的測試函數(shù)進(jìn)行測試，將結(jié)果與近年IEEE Transactions系列期刊論文中提出的新算法的測試結(jié)果進(jìn)行比較，進(jìn)一步驗證SDSFLA的有效性和穩(wěn)定性。

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

[2] Ebrahimi J,Hosseinian S H,Gharehpetian G B.Unit commitment problem solution using shuffled frog leaping algorithm[J].IEEE Transactions on Power Systems,2011,26(2):573-581.

[3] Hasanien H M.Shuffled frog leaping algorithm for photovoltaic model identification[J].IEEE Transactions on Sustainable Energy,2015,6(2):509-515.

[4] Lei De-ming,Guo Xiu-ping.A shuffled frog-leaping algorithm for hybrid flow shop scheduling with two agents [J].Expert Systems with Applications,2015,42(23):9333-9339.

[5] Xu Fang,Zhang Gui-zhu.Clustering algorithm based on modified shuffled frog leaping algorithm andK-means[J].Computer Engineering and Applications,2013,49(1):176-180.(in Chinese)

[6] Zhao Peng-jun, Shao Ze-jun.Novel improved shuffled frog leaping algorithm[J].Computer Engineering and Applications,2012,48 (8):48-50.(in Chinese)

[7] Roy P,Roy P,Chakrabarti A.Modified shuffled frog leaping algorithm with genetic algorithm crossover for solving economic load dispatch problem with valve-point effect[J].Applied Soft Computing,2013,13(11):4244-4252.

[8] Zhu G Y,Zhang W B.An improved shuffled frog-leaping algorithm to optimize component pick-and-place sequencing optimization problem [J].Expert Systems with Applications,2014,41(15):6818-6829.

[9] Luo J,Li X,Chen M R,et al.A novel hybrid shuffled frog leaping algorithm for vehicle routing problem with time windows [J].Information Sciences,2015,316(C):266-292.

[10] Xiao Wen-xian, Wang Jun-ge, Ma Xiao-qin. Harmony frog leaping algorithm and its application to complex optimization problems [J].Journal of Central China Normal University (Natural Science Edition),2016,50(2):211-215.(in Chinese)

[11] Lu X, Tang K, Sendhoff B,et al.A new self-adaptation scheme for differential evolution[J].Neurocomputing,2014,146(C):2-16.

[12] Wang L,Shi Y,Liu S.An improved fruit fly optimization algorithm and its application to joint replenishment problems [J].Expert Systems with Applications,2015,42(9):4310-4323.

[13] Ge Yu,Wang Xue-ping,Liang Jing.Adaptive chaotic mutation shuffled frog leaping algorithms [J].Application Research of Computers,2011,28(3):945-947.(in Chinese)

[14] Wang L,Zeng Y,Chen T.Back propagation neural network with adaptive differential evolution algorithm for time series forecasting [J].Expert Systems with Applications,2015,42(2):855-863.

[15] Sharma S, Sharma T K,Pant M,et al.Centroid mutation embedded shuffled frog-Leaping algorithm [J].Procedia Computer Science,2015,46:127-134.

[16] Mallipeddi R,Suganthan P N,Pan Q K,et al.Differential evolution algorithm with ensemble of parameters and mutation strategies[J].Applied Soft Computing,2011,11(2):1679-1696.

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

[5] 許方,張桂珠.一種改進(jìn)的混合蛙跳和K均值結(jié)合的聚類算法[J].計算機(jī)工程與應(yīng)用,2013,49(1):176-180.

[6] 趙鵬軍,邵澤軍.一種新的改進(jìn)的混合蛙跳算法[J].計算機(jī)工程與應(yīng)用,2012,48(8):48-50.

[10] 肖文顯,王俊閣,馬孝琴.和聲蛙跳算法在復(fù)雜優(yōu)化問題中的應(yīng)用研究[J].華中師范大學(xué)學(xué)報(自然科學(xué)版),2016,50(2):211-215.

[13] 葛宇,王學(xué)平,梁靜.自適應(yīng)混沌變異蛙跳算法[J].計算機(jī)應(yīng)用研究,2011,28(3):945-947.