SFL算法的流程圖和算法

摘 要：本文主要介紹SFL算法的流程圖和算法，并總結出SFL算法的易于理解、參數較少、收斂速度較快、尋優能力強、易于實現等優點。

關鍵詞：SFL； 算法； 參數； 優點

中圖分類號：M774 文獻標識碼：A 文章編號：1006-3315(2011)3-176-001

混合蛙跳算法（Shuffled Frog Leaping Algorithm， SFLA）是2000年由Eusuff等人提出的一種基于群體智能的后啟發式計算技術。SFL作為一種生物進化算法， 它結合了基因進化的模因演算法(Memetic Algorithm)和群體行為的粒子群算法( Particle Swarm Optimization)兩者的優點，具有概念易于理解、參數較少(比PSO算法更少的參數)、收斂速度快、全局尋優能力強、易于實現等優點。

一、SFL的編碼和參數

1．frog的編碼

在SFL算法中，frog的編碼決定了解的形式和結果。和傳統的GA算法相比，SFL算法最突出的特點是frog可以使用實值進行編碼，frog的每一個基因都可以使用實值，減少了二進制轉換時間。

2．SFL算法中的參數

2.1種群規模：種群中青蛙的個數，即解的個數。

2.2族群個數：族群個數決定了SFL算法的搜尋范圍，族群個數越多，搜索范圍越廣，利于可行解的全局搜索。

2.3最大步長：當更新族群中的frog時，需要設定最大的更新步長，避免更新過快，找不到最優解。步長的設定決定了frog的局部搜索能力，步長越小，局部搜索能力越強，但時間也越長。

2.4閾值：用于控制算法挑出的參數。通常是殘差、精度等數值。

二、SFL算法流程圖和算法

在SFL算法執行過程中，當群體中的frog的適應度函數達到優化要求時，程序挑出、結束，否則繼續執行算法，直到有可行解的出現。在SFL算法執行過程中使用了分組融合的概念，每次根據適應度值的不同，對整個群體進行分組，分組后進行組內更新，即每組中適應度函數最差的frog。經過若干次迭代后，合并所有組內的染色體，判斷終止條件（有沒有frog的適應度值達到設定條件），如不滿足，則進行下一次迭代，如果滿足，挑出程序。SFL算法流程圖，如下圖所示：

基本SFL算法如下：

算法分組后會更新組內適應度值最差的個體(Xw)，它的更新策略如下：

Xw位置的改變量（Di）=rand( )×（Xb-Xw），rand( )∈(0，1)（1）；

Xw新的位置=Xw當前位置+Di，-Dmax≤Di≤Dmax，Dmax表示最大更新步長。（2）

三、SFL算法的優缺點

SFL算法優點：

1．較少的參數

相對于其它算法，參數較少。

2．計算速度快

由于在SFL算法中采用了分組策略，每一組frog可以搜尋一個方向，并由一直帶頭frog指引方向（更新策略1），使得算法執行過程中能在局部快速找到最優解。

3．全局搜索

由于SFL算法執行中采用分組策略，每組進行局部搜索，多組進行全局搜索，并在執行一定次數的局部搜索后，進行全局的融合，再次分組，實現組間的信息交互，達到快速全局搜索的目的。

4．每次迭代過程中，所有的frog均可以多次選擇參與進化

SFL算法缺點：和GA算法類似，SFL算法也存在著諸多進化算法的缺點，即算法執行過程中含有參數，算法時間復雜度較高，最優解不唯一等。

綜上所述，SFL算法是一種尋優能力很強的算法，能夠快速求解優化問題，避免了傳統進化算法易陷入局部最優解的問題。

參考文獻：

[1]E. Emad， H. Tarek， G. Donald. Comparison among five evolutionary-based optimizationalgorithms. Advanced Engineering Informatics， 2005， 19: 43–53.

[2]Wilson， D.L. Asymptotic properties of nearest neighbor rules using edited data. IEEE Transactions on Systems， Man， and Cybernetics， 1972， SMC-2(3):408–421.

[3]Fabrizio Angiulli. Fast Nearest Neighbor Condensation for Large Data Sets Classification. IEEE Transactions on Knowledge and Data Engineering， Nov 2007， Vol 19， No. 11. pp. 1450-1464.