協同進化混合蛙跳算法*

戴月明，張明明，王 艷

(江南大學物聯網工程學院，江蘇 無錫 214122)

1 引言

混合蛙跳算法SFLA(Shuffled Frog Leaping Algorithm)于2003年由Eusuff等[1,2]提出。該算法結合了模因算法MA(Memetic Algorithm)和粒子群優化PSO(Particle Swarm Optimization)算法兩者的優點，具有結構簡單、參數設置少、運算速度快、全局尋優能力強、易于實現等特點，正成為智能計算領域的研究熱點。

但是，相關研究表明，混合蛙跳算法在進化后期收斂速度慢，易陷入局部極值，求解精度低。為此，眾多學者對其進行了大量的研究與改進。文獻[3]通過反向學習策略生成初始種群以及對局部搜索策略引入比例因子兩個階段來進行改進，有效地提高了蛙跳算法的性能；文獻[4]改進了蛙跳算法的局部搜索跳躍規則，同時引入協作與柯西變異策略代替隨機更新，一定程度上提高了算法的收斂速度與精度；文獻[5]提出一種新的更新策略，對子群內每一個青蛙都進行更新，并固定全局混合迭代時間間隔，實驗結果表明改進的算法尋優精度高、收斂速度快；文獻[6]通過結合量子進化算法的理論，提出量子二進制混合蛙跳算法，具有收斂速度快、全局搜索能力強、穩定性好等優點；文獻[7]提出了雙加速因子的搜索策略，同時對子群最差蛙以及子群最優蛙進行更新，進一步提高了算法的收斂速度。

以上文獻對混合蛙跳算法的不同改進方法雖在一定程度上提高了算法的收斂速度和精度，但效果并不是很理想，這些改進并沒有充分考慮到更優青蛙更可能存在于最優青蛙附近空間以及子群之間的交互學習和精英群體的自主學習進化能力。因此，本文提出了一種協同進化混合蛙跳算法CSFLA(Coevolutionary Shuffled Frog Leaping Algorithm)。該算法在子群內最差個體更新策略中引入子群青蛙平均值，并充分利用最優個體的優秀基因對最優個體附近空間進行有效探索。同時，結合交互學習策略，每個子群內少量較差的個體向鄰近子群的最優個體進行交互學習，利于信息共享，增加種群的多樣性，提高算法解的質量，加快尋優速度。為避免陷入局部極值，在全局迭代過程中采取精英群自學習進化機制，以進一步精細搜索精英個體空間獲得更優解，引領種群逃出局部最優，提高算法性能。最后，通過仿真實驗驗證了新算法的有效性。

2 混合蛙跳算法

由文獻[8]可知，基本混合蛙跳算法SFLA(Shuffled Frog Leaping Algorithm)是一種基于群體智能的生物進化算法，模擬青蛙按族群劃分進行覓食的過程，是一種結合了確定性方法和隨機性方法的進化計算方法。SFLA的基本思想是[1]：隨機生成F只青蛙組成初始種群體P=(P1,P2,…,PF)，D維解空間中的第i只青蛙表示為Pi=(Pi1,Pi2,…,PiD)。生成初始群體之后，首先將種群內的青蛙個體按適應值f(Pi)進行降序排列，并記錄蛙群中具有最優適應值的全局最優青蛙為Pg。然后將蛙群分成m個子群，每個子群包含n只青蛙，滿足關系F=m*n。第1只青蛙進入第1個子群，第2只青蛙進入第2個子群，…，第m只青蛙進入第m個子群，第m+1個青蛙又進入第1個子群，第m+2只青蛙進入第2個子群，以此類推，直到F只青蛙劃分完畢。

局部搜索：每個子群中具有最好適應值的最優青蛙個體和最差適應值的最差青蛙個體分別記為Pb和Pw。然后對每個子群進行局部搜索,即對子群中的Pw循環進行局部搜索操作。其更新策略為：

ds=rand(0,1)*(Pb-Pw)

(1)

(2)

其中：ds代表移動步長，rand(0,1)為[0,1]內的隨機數；dmax為其移動的最大步長。

如果新個體Pn優于原個體Pw，則取代Pw；如果沒有得到改進，則用全局最優個體Pg代替Pb，代入式(1)～式(2)重新生成新個體，若優于Pw則取代Pw，否則隨機生成一個新個體取代Pw。重復以上更新操作直到子群最大迭代數。

全局信息交換：當所有子群的局部搜索完成后，進行全局信息交換，將所有子群中的青蛙重新混合成一個新的蛙群，并再次排序和劃分子群，然后每個子群再進行局部搜索。如此反復，直到滿足相應的結束條件(收斂到指定精度或達到全局最大進化代數)。

3 協同進化混合蛙跳算法

協同進化混合蛙跳算法(CSFLA)針對基本SFLA存在收斂速度緩慢、收斂精度低、青蛙子群局部信息和青蛙種群全局信息交流不全面等缺點進行了優化。本文通過引入子群青蛙平均值，并充分利用最優個體的優秀基因對子群內最差青蛙個體更新方式進行改進；同時考慮到子群之間的交互學習有利于信息共享，對子群內較差的青蛙個體采取交互學習策略，以提高解的質量，加快算法尋優速度；最后，在全局迭代過程中采取精英群自學習進化機制，以獲得更優解，避免陷入局部最優，提升算法的全局尋優能力。

3.1 局部位置更新算子

傳統混合蛙跳算法只對子群內最差青蛙個體Pw進行更新，局部搜索為一個線性搜索，使得生成的新個體Pn總是沿直線方向向Pb或Pg靠近[9]，限制了搜索區域，進化后期種群多樣性明顯下降，易陷入局部最優，從而影響算法的求解精度和收斂速度。

本文充分利用子群最優個體和全局最優個體的優秀基因，深入搜索最優青蛙附近空間以獲得更優青蛙。同時考慮到全組青蛙的更新現狀對下一步進化具有重要的影響，組內最優個體代表了組內青蛙所處的最好位置，對整個子群起到重要的引領作用；組內所有青蛙的平均值在一定程度上反映了子群的整體水平。因此，對傳統混合蛙跳算法的組內更新策略進行了重新設計，本文從最優青蛙位置出發，利用最優青蛙與最差青蛙以及組內所有青蛙的平均值與最差青蛙的隨機差值為步長基數，調整更新步長，最后采用隨機雙向的更新方式。雙向隨機查找更優青蛙，以此擴大解空間的搜索范圍，從而提高了局部搜索的效率。

在進行組內搜索時，首先計算組內青蛙的平均值Pa。對子群內最差青蛙的更新策略進行改進，定義如下：

ds=r*(r*(Pb-Pw)+(1-r)*(Pa-Pw))

(3)

Pn=Pb±ds

(4)

其中r代表[0,1]內的隨機數。

根據子群最優個體Pb對Pw進行更新操作，若所得出的新個體Pn優于子群內最差青蛙個體Pw，則對其進行取代；若得出的結果沒有改進，那么用種群的最優個體Pg代替Pb，代入式(3)～式(4)重新進行更新操作，若優于Pw則用新個體取代Pw；否則雙向隨機生成一個新個體取代Pw。

3.2 交互學習策略

啟發于人類社會不同群體間可以交互學習的特點[10]，依據生物學上同物種間信息的交互共享有利于物種生存的原理，個體與其近鄰同伴之間進行頻繁的信息交互，可以擴大個體的感知范圍，提高個體感知信息的速度和準確率，成員間的信息交互有利于個體進化[11]。

因此，在算法進行局部搜索時，對子群內較差的青蛙個體采取交互學習策略進行更新，對子群內部少量(例如3個)適應值較差的青蛙個體，利用全局最優個體Pg與所在子群的最優個體Pb之間的隨機點為起點，以保持當前迭代全局最優個體以及所在子群的優秀基因。每一只較差青蛙個體向鄰近子群的最優個體進行交互學習，獲取其他子群的優質元素，整體提升整個種群的質量。通過此交互學習策略產生的新個體，若優于原個體則對其進行取代，否則保持不變，定義式如下：

Po=r*Pg+(1-r)*Pb

(5)

(6)

Pn=Po+△Pmi

(7)

交互學習策略使得青蛙個體學習的方向具有了多樣性，為算法擺脫局部最優提供了新的額外動力。同時，可以減少算法尋優過程的盲目性，加快算法的尋優速度。

3.3 精英群自學習進化機制

自然界的生物不斷調整自身狀態來適應環境[12]。針對目前蛙跳算法研究中忽視個體能動性，尤其是種群中精英群體的自主學習進化能力，提出了精英群自學習進化機制。在全局迭代中種群的多個精英個體組成單獨的精英群進行主動的自我學習和調整，在精英個體空間進行小鄰域精細搜索，將搜索到的更優解返回當前迭代種群，每一代個體都能比上一代個體更好地適應環境，從而最終必然更加逼近最優個體，進而指導算法改善下一步的進化方向，進一步提高算法的全局尋優能力，減少陷入局部最優的危險。

精英群自學習進化機制的第1 步是精英個體的選擇。根據多精英比單精英更能夠引導群體學習的社會現象，在蛙跳算法的全局信息交換階段，將個體按適應值進行排序，選取當前種群最好的m個精英個體組成一個精英群，引入雙向隨機變異算子，通過對“精英”個體攜帶的信息進行多次多角度的隨機擾動變異操作進行自學習進化，既保留了精英個體的優秀基因，又在其周圍鄰域空間進行更深入的精細探索以產生更優秀的新個體，通過在精英群空間多角度雙向隨機探索，使算法具備了一定的自主學習能力，有利于算法跳出局部最優解的束縛進行全局搜索。精英自學習方程為：

△Pij=ξrands()ij*Pij

(8)

(9)

其中,Pij是個體Pi第j維數；rands()ij為對應Pij的-1到1的隨機數，使得對種群的精英個體Pi的每一維度進行雙向隨機變異擾動；ξ為變異參數。

如果式(8)和式(9)產生一個更優解則取代原精英個體，否則對式(8)精英個體的隨機擾動進行反序雙向探索，再利用公式(9)獲得更優解，如果還是不能找到更優解，則保持原精英個體不變，以避免產生的種群個體劣化。式(8)和式(9)是在精英個體Pi的基礎上增加了雙向隨機變異因子，增加了新個體的隨機性，既具有隨機搜索的作用，又優于隨機搜索，因為它利用了勝者的信息。精英群自學習進化機制增強了算法逃離局部最優的能力，能夠正確導向算法的進化，指引種群有效搜索，加速收斂。

3.4 協同進化混合蛙跳算法的算法流程

綜上所述，本文提出的協同進化混合蛙跳算法CSFLA的基本流程如下：

步驟1初始化種群及相關參數，選取合適的青蛙總數F，每個青蛙個體的維度為D，子群數m，子群內個體數n，子群內迭代數Ne，種群總進化代數MAXGEN，精英變異參數ξ。

步驟2計算每個個體的適應度，根據適應度將F個個體降序排列，選取適應度值最好的m個精英個體組成精英群，在全局迭代中對精英群根據式(8)和式(9)采取精英群進化機制進行多次多角度的迭代進化，以產生更優個體取代原個體，指導整個種群向更好的方向進化。

步驟3重新計算每個個體的適應度，根據適應度將F個個體降序排列，記錄整個種群的最優候選解為Pg并劃分成m個子群。

步驟4對每個子群依次進行局部搜索，局部深度搜索策略如下：

(1)確定子群內最優青蛙個體Pb，最差的青蛙個體Pw，整個種群的最優青蛙個體Pg，根據式(3)和式(4)生成新個體Pn對子群內最差的青蛙個體Pw進行更新，并且若新個體位置優于Pb，則更新子群內最優青蛙個體Pb的位置；若新個體位置同時又優于Pg，則更新全局最優個體Pg的位置。

(2)交互學習策略，對子群內部少量較差的青蛙個體根據式(5)～式(7)向鄰近子群的最優個體進行交互學習，產生1個新個體，若優于原個體，則對其進行取代，否則保持不變，并且若變異生成的新個體位置優于Pb，則更新子群內最優青蛙個體Pb的位置；若變異生成的新個體位置又優于Pg，則同時更新全局最優個體Pg的位置。

步驟5對每個子群不斷迭代直到達到子群最大迭代數Ne從而跳出步驟4，結束局部搜索。

步驟6將各個子群重新混合構成一個新的種群，重復步驟2到步驟5,直到達到種群總進化代數MAXGEN。

CSFLA算法的偽代碼描述如下所示：

Begin

/*全局迭代中精英群自學習進化機制*/

Calculate the fitness of each individual；

select the bestmelite individuals to form the elite group；

forgg= 1 tom

forgi= 1 to 5

Updateelitesby formula (8) and formula (9)；

break；/*一旦精英進化生成更優秀的青蛙個體,則立即取代原個體,否則保持不變*/

end if

end for

end for

/*局部搜索中*/

fori= 1 tom

forj= 1 toNe

/*子群最差青蛙個體更新策略*/

UpdatePwby formula (3) and formula (4)；

iff(Pn)

Pw=Pn;/*找出更好的新個體取代Pw*/

end if

iff(Pn)

Pb=Pn； /*更新子群最優位置*/

iff(Pn)

Pg=Pn；/*更新全局最優位置*/

end if

end if

/*子群內較差青蛙個體交互學習策略*/

formi=floor(9/10*n) ton-1

Update a small number of worse frogs individual by formula (5)～formula (7)；

iff(Pnew)

Pmi=Pnew；/*取代較差個體*/

iff(Pnew)

Pb=Pnew；/*更新子群最優位置*/

iff(Pnew)

Pg=Pnew；/*更新全局最優位置*/

end if

end if

end if

end for

nextj

nexti

End for

4 仿真實驗結果及分析

4.1 實驗設置

為了驗證本文改進算法CSFLA的有效性，選取了如表1中的七個測試函數，并與混合蛙跳算法(SFLA)、文獻[13]的GSFLA(A New Updated Strategy Shuffled Frog Leaping Algorithm based on Gravitation Search Algorithm)和文獻[14]的改進混合蛙跳算法ISFLA(Improvement and Simulation for Shuffled Frog Leaping Algorithm)進行對比實驗。

以上這七個測試函數的理論最優值都是0，其中Sphere(f1)函數是簡單的單模態函數，通常被用來測試算法的進化效率。f2和f3是單峰函數，其余是復雜的多峰函數，通常有許多局部極小值點，在算法搜索過程中極易陷入局部極值而無法收斂到全局最優點。以上所選測試函數形態各異，具有很好的測試性能，可有效檢驗算法的收斂速度、全局尋優精度以及多峰尋優能力等優化性能。

性能評估采用如下方法：(1)固定全局迭代次數，評估算法的收斂速度、精度和穩定性；(2)固定收斂精度，評估算法的全局迭代次數；(3)CSFLA收斂到最優解0時全局迭代次數分析。

4.2 固定全局迭代次數的實驗結果分析

實驗參數設置如下：所有算法的青蛙種群規模F= 500，子群數m= 20，子群個體數n= 25，子群內個體迭代數Ne= 30。種群總進化代數MAXGEN= 250，青蛙個體解的維度D= 30，為了確保測試的準確性減小偶然性，本文采用多次測試取平均值的方法，設置重復運行次數t= 30并統計相關結果，取30 次的最優適應度值、平均適應度值和標準差作為參照指標進行對比。實驗結果如表2所示。為了更直觀地比較各種算法的尋優性能，圖1中給出了每種算法所對應的測試函數適應度的進化曲線。

Table 1 Definition of the test functions

Table 2 Experimental results of the test functions

從表2中可以看出，無論是對于簡單單峰函數還是復雜多峰函數，CSFLA在尋優精度及算法的穩定性上都取得了極大的提高，在表1中的七個測試函數Sphere(f1)、Quadric(f2)、Hyperellipsoide(f3)、Ackley(f4)、Griewank(f5)、Rastrigrin(f6)和Schaffer(f7)中均能收斂到最優解。表2中，最優值為30次運行結果中最好的一次，平均值則是30次運行結果的平均值，CSFLA算法在七個測試函數中均能收斂到最優解0，而其他三種算法都不同程度地陷入了早熟收斂。從這兩項對比可以表明，在相同的進化迭代次數下，CSFLA相比ISFLA、GSFLA和SFLA具有更快的尋優速度、更高的收斂精度。標準差為30次獨立運行結果的標準差，CSFLA算法在七個測試函數中的標準差均是0，通過對比，也可以明顯看到，改進的CSFLA算法體現了更好的穩定性。這說明CSFLA具有較強的全局搜索能力，能夠有效擺脫局部最優，具有比其他三種算法更好的收斂速度和尋優精度，極大地提高了算法性能，具有一定的魯棒性。

Figure 1 Optimization results of the seven test functions圖1 七個測試函數的優化對比結果圖

圖1是CSFLA、ISFLA、GSFLA和SFLA在七個測試函數中的進化曲線圖，橫坐標表示種群的進化代數，縱坐標表示平均適應度值的lg對數。從圖1中也可以直觀地看出，一開始進化，CSFLA就比ISFLA、GSFLA和SFLA體現出更優秀的尋優能力。相比其他三種算法，其收斂速度更快。在進化中后期，SFLA和GSFLA均不可避免地出現早熟收斂現象，ISFLA也不可避免地在函數f1～f3中出現早熟收斂現象，而CSFLA則有效避免了這種現象，成功尋找到全局最優解，大大提高了算法的收斂精度和尋優能力。以上實驗結果表明，CSFLA在測試函數中具有更快的收斂速度和更精確的搜索精度，在函數f1、f2、f3、f4、f5、f6和f7的實驗結果中，均收斂到最優值0。因此，本文改進后的算法CSFLA無論是在收斂速度、尋優精度還是穩定性方面都得到了極大的提高，有效改善了算法的性能。

4.3 固定收斂精度的實驗結果分析

本實驗指定各測試函數收斂精度如表3所示。所有算法的青蛙種群規模F= 500，子群數m= 20，子群個體數n= 25，子群內個體迭代數Ne= 30，青蛙個體解的維度D= 30。

為了避免算法因收斂到局部最優解而無法達到指定的精度，導致程序無法結束，本實驗設置最大有效迭代次數MAXGEN= 250，如果在250次全局迭代后仍然沒有達到指定的收斂精度，就認為算法該次沒有收斂。獨立運行30次，實驗結果如表4所示。其中成功率=達到精度的實驗次數/總的實驗次數。

Table 3 Convergence accuracy of each test function

從表4可以看出，GSFLA和SFLA幾乎對所有的測試函數都很難達到指定精度，ISFLA對f1～f6函數雖然可以達到指定精度，但收斂代數上明顯高于CSFLA。本文提出的算法CSFLA對該七個函數的求解，收斂代數上明顯低于ISFLA、GSFLA和SFLA，同時成功率均達到了100%。這說明CSFLA不僅收斂速度比其他算法要快，而且具有良好的可靠性和有效性。

4.4 CSFLA收斂到最優解0時全局迭代次數實驗結果分析

從4.2節可以看出，本文所提算法CSFLA在七個測試函數中均能收斂到最優解0。所以，設計本實驗得出CSFLA收斂到最優解0時所需的最小迭代次數、最大迭代次數、平均代數以及成功率，以進一步驗證本文所提算法CSFLA收斂到全局最優解0的可靠性與有效性。參數設置均同4.2節，獨立運行30次，實驗結果如表5所示。

從表5可以看出，本文提出的算法CSFLA在250次全局迭代中均能100%收斂到七個測試函數全局最優解0，尤其對f4～f7的復雜多峰函數，尋優代數較小，尋優性能更好。本實驗再次驗證了CSFLA收斂到全局最優解0的可靠性與有效性。

Table 4 Comparison of experimental resultswith fixed convergence precision

Table 5 Experimental results of the time of global iterationwhen the CSFLA converges to the optimal solution of 0

5 結束語

本文提出的CSFLA針對混合蛙跳算法易早熟收斂、求解精度不高的缺陷，對子群最差青蛙個體更新策略進行改進使其能夠有效避免算法陷入局部最優，交互學習策略的應用可增加子群間相互交流學習的機會，不僅有效提高了種群質量，而且加快了尋優速度。最后，在全局迭代過程中選取種群的部分精英個體組成精英群引入自學習進化機制，在精英群周圍空間進行進一步深入搜索以獲得更優的青蛙個體，引領整個種群的進化，有效地避免了算法陷入早熟收斂，大幅度提高了算法的性能。實驗仿真結果也驗證了所提算法的有效性。將改進的算法應用于實際工程中，進一步檢驗算法性能，將是下一步工作的重點。

[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] Eusuff M M,Lansey K E.Shuffled frog-leaping algorithm:A memetic meta-heuristic for discrete optimization[J].Engineering Optimization,2006,38(2):129-154.

[3] Naruka B, Sharma T K,Pant M,et al.Two-phase shuffled frog-leaping algorithm[C]∥Proc of the 3rd International Conference on Reliability,Infocom Technologies and Optimization (ICRITO)(Trends and Future Directions),2014:1-5.

[4] Wang H,Zhang K,Tu X,et al.A mnemonic shuffled frog leaping algorithm with cooperation and mutation[J].Applied Intelligence,2015,43(1):32-48.

[5] Wang L,Gong Y.A fast shuffled frog leaping algorithm[C]∥Proc of the 2013 9th International Conference on Natural Computation (ICNC),2013:369-373.

[6] Wang L,Gong Y.Quantum binary shuffled frog leaping algorithm[C]∥Proc of the 2013 3rd International Conference on Instrumentation,Measurement,Computer,Communication and Control,2013:1655-1659.

[7] Jaballah S,Rouis K,Ben Abdallah F,et al.An improved shuffled frog leaping algorithm with a fast search strategy for optimization problems[C]∥Proc of the 2014 IEEE International Conference on Intelligent Computer Communication and Processing (ICCP),2014:23-27.

[8] Cui Wen-hua, Liu Xiao-bing, Wang Wei,et al.Survey on shuffled frog leaping algorithm[J].Control and Decision,2012,27(4):481-486.(in Chinese)

[9] Li Jing-jing,Dai Yue-ming.Adaptive shuffled frog leaping algorithm adopting mixed mutation[J].Computer Engineering and Applications,2013,49(10):58-61.(in Chinese)

[10] Qin Quan-de, Li Li,Cheng Shi,et al.Interactive learning particle swarm optimization algorithm[J].CAAI Transactions on Intelligent Systems,2012,7(6):547-553.(in Chinese)

[11] Zhu Yong-fang.Information interaction and processing particle swarm optimization algorithm[D].Taiyuan:Taiyuan University of Science & Technology,2009.(in Chinese)

[12] Nie Chong, Wang Wei-ping,Zhao Wen,et al.An active learning genetic algorithm with learning operator[J].Computer Simulation,2006,23(9):168-171.(in Chinese)

[13] Sun Y H,Liu W,Xie Y S,et al.A new updated strategy shuffled frog leaping algorithm based on gravitation search algorithm[C]∥Proc of the 3rd International Conference on Material,Mechanical and Manufacturing Engineering (IC3ME 2015),2015:1432-1437.

[14] Li Jian-jun,Yu Bin,Chen Wu-ping.Improvement and simulation for shuffled frog leaping algorithm[J].Journal of System Simulation,2014,26(4):755-760.(in Chinese)

附中文參考文獻：

[8] 崔文華,劉曉冰,王偉,等.混合蛙跳算法研究綜述[J].控制與決策,2012,27(4):481-486.

[9] 李晶晶,戴月明.自適應混合變異的蛙跳算法[J].計算機工程與應用,2013,49(10):58-61.

[10] 秦全德,李麗,程適,等.交互學習的粒子群優化算法[J].智能系統學報,2012,7(6):547-553.

[11] 褚永芳.信息交互與處理微粒群算法[D].太原：太原科技大學,2009.

[12] 聶沖,王維平,趙雯,等.基于學習算子的自學習遺傳算法設計[J].計算機仿真,2006,23(9):168-171.

[14] 李建軍,郁濱,陳武平.混合蛙跳算法的改進與仿真[J].系統仿真學報,2014,26(4):755-760.