一種基于選擇策略的差分混合蛙跳算法*

王 林，萬小雨,萬建超

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

1 引言

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

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

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

2 標準蛙跳算法與缺點分析

2.1 蛙跳算法基本原理

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

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

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

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

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

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

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

(1)

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

(2)

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

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

(3)

③隨機生成新個體更新策略。隨機生產一個新個體替代pw,進入Step 5。

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

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

Step7輸出最佳個體gx和對應的適應度值，則為找出的最優解。

標準蛙跳算法的流程如圖1所示。

Figure 1 Flowchart of SFLA圖1 標準蛙跳算法流程圖

2.2 標準蛙跳算法的局限性

(1)標準SFLA和其它智能優化算法一樣，沒有參數設置的最優組合，而是根據不同的具體問題產生差異，并沒有指導性的原則，僅能通過大量的實驗得到。參數設置沒有通用性，算法的穩定性不高。

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

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

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

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

3.1 SDSFLA改進思路

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

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

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

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

(4)建立變異算子F和交叉算子CR的資源池，SDSFLA三種策略對個體進行更新時，隨機選擇F和CR的組合，增加種群多樣性。本文根據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局部搜索的執行流程

Step1找出組內最差的三個個體分別執行Step 2到Step 4。

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

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

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

(4)

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

(5)

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

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

S∈[-Smax,Smax]

(6)

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

(7)

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

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

S∈[-Smax,Smax]

(8)

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

(9)

Step3將得出的三個實驗個體temp1、temp2、temp3的適應度值進行比較，選擇出適應度最優的個體作為最終的實驗個體temp。

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

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

4 SDSFLA性能測試

4.1 測試函數介紹

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

Table 1 Test functions

16個測試函數中F3理論最優值為-1，F16理論最優值為1-n，其它函數理論最優值均為0。

4.2 測試結果

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

最大進化代數maxgen設置為500，種群規模為50，本文提出的SDSFLA的分組數為10，局部搜索代數為10，函數維度分別設置為30和50，每種算法對每個函數獨立運行20遍，運算結果的平均值和標準差如表2和表3所示。

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

圖2～圖5分別是較復雜的多峰函數F11、F12、F13、F14的優化過程對比圖。

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

對于F1、F2、F4、F5、F6、F7、F9、F11這八個函數，SDSFLA的運算結果遠遠優于其它三種算法。分析圖2～圖5，在有限的搜索代數內，SDSFLA可以較快收斂到理想值。另外，通過分析標準差的結果，SDSFLA運行結果的波動性小，證明SDSFLA的穩定性較好。

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收斂結果對比圖

Figure 4 Convergence results for F13圖4 F13收斂結果對比圖

Figure 5 Convergence results for F14圖5 F14收斂結果對比圖

5 結束語

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

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

[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.

附中文參考文獻：

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

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

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

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