SFL算法的流程圖和算法

摘 要：本文主要介紹SFL算法的流程圖和算法，并總結(jié)出SFL算法的易于理解、參數(shù)較少、收斂速度較快、尋優(yōu)能力強(qiáng)、易于實(shí)現(xiàn)等優(yōu)點(diǎn)。

關(guān)鍵詞：SFL； 算法； 參數(shù)； 優(yōu)點(diǎn)

中圖分類號(hào)：M774 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-3315(2011)3-176-001

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

一、SFL的編碼和參數(shù)

1．frog的編碼

在SFL算法中，frog的編碼決定了解的形式和結(jié)果。和傳統(tǒng)的GA算法相比，SFL算法最突出的特點(diǎn)是frog可以使用實(shí)值進(jìn)行編碼，frog的每一個(gè)基因都可以使用實(shí)值，減少了二進(jìn)制轉(zhuǎn)換時(shí)間。

2．SFL算法中的參數(shù)

2.1種群規(guī)模：種群中青蛙的個(gè)數(shù)，即解的個(gè)數(shù)。

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

2.3最大步長(zhǎng)：當(dāng)更新族群中的frog時(shí)，需要設(shè)定最大的更新步長(zhǎng)，避免更新過(guò)快，找不到最優(yōu)解。步長(zhǎng)的設(shè)定決定了frog的局部搜索能力，步長(zhǎng)越小，局部搜索能力越強(qiáng)，但時(shí)間也越長(zhǎng)。

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

二、SFL算法流程圖和算法

在SFL算法執(zhí)行過(guò)程中，當(dāng)群體中的frog的適應(yīng)度函數(shù)達(dá)到優(yōu)化要求時(shí)，程序挑出、結(jié)束，否則繼續(xù)執(zhí)行算法，直到有可行解的出現(xiàn)。在SFL算法執(zhí)行過(guò)程中使用了分組融合的概念，每次根據(jù)適應(yīng)度值的不同，對(duì)整個(gè)群體進(jìn)行分組，分組后進(jìn)行組內(nèi)更新，即每組中適應(yīng)度函數(shù)最差的frog。經(jīng)過(guò)若干次迭代后，合并所有組內(nèi)的染色體，判斷終止條件（有沒(méi)有frog的適應(yīng)度值達(dá)到設(shè)定條件），如不滿足，則進(jìn)行下一次迭代，如果滿足，挑出程序。SFL算法流程圖，如下圖所示：

基本SFL算法如下：

算法分組后會(huì)更新組內(nèi)適應(yīng)度值最差的個(gè)體(Xw)，它的更新策略如下：

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

Xw新的位置=Xw當(dāng)前位置+Di，-Dmax≤Di≤Dmax，Dmax表示最大更新步長(zhǎng)。（2）

三、SFL算法的優(yōu)缺點(diǎn)

SFL算法優(yōu)點(diǎn)：

1．較少的參數(shù)

相對(duì)于其它算法，參數(shù)較少。

2．計(jì)算速度快

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

3．全局搜索

由于SFL算法執(zhí)行中采用分組策略，每組進(jìn)行局部搜索，多組進(jìn)行全局搜索，并在執(zhí)行一定次數(shù)的局部搜索后，進(jìn)行全局的融合，再次分組，實(shí)現(xiàn)組間的信息交互，達(dá)到快速全局搜索的目的。

4．每次迭代過(guò)程中，所有的frog均可以多次選擇參與進(jìn)化

SFL算法缺點(diǎn)：和GA算法類似，SFL算法也存在著諸多進(jìn)化算法的缺點(diǎn)，即算法執(zhí)行過(guò)程中含有參數(shù)，算法時(shí)間復(fù)雜度較高，最優(yōu)解不唯一等。

綜上所述，SFL算法是一種尋優(yōu)能力很強(qiáng)的算法，能夠快速求解優(yōu)化問(wèn)題，避免了傳統(tǒng)進(jìn)化算法易陷入局部最優(yōu)解的問(wèn)題。

參考文獻(xiàn)：

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