基于模糊閾值補(bǔ)償?shù)幕旌贤芴惴?/h1>
2014-08-05 04:27:58劉立群王聯(lián)國(guó)火久元韓俊英劉成忠
計(jì)算機(jī)工程 2014年5期
劉立群，王聯(lián)國(guó)，火久元，韓俊英，劉成忠
(1. 甘肅農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，蘭州 730 070；2. 蘭州交通大學(xué)電子與信息工程學(xué)院，蘭州 73007 0)
基于模糊閾值補(bǔ)償?shù)幕旌贤芴惴?/p>
劉立群1，王聯(lián)國(guó)1，火久元2，韓俊英1，劉成忠1
(1. 甘肅農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，蘭州 730 070；2. 蘭州交通大學(xué)電子與信息工程學(xué)院，蘭州 73007 0)
針對(duì)混合蛙跳算法(SFLA)求解復(fù)雜問(wèn)題時(shí)收斂速度慢、優(yōu)化精度低的缺點(diǎn)，提出一種基于模糊閾值補(bǔ)償?shù)幕旌贤芴惴?FTCSFLA)。在SFLA的基礎(chǔ)上，采用模糊分組方法對(duì)青蛙分組并改進(jìn)局部搜索的擾動(dòng)策略。在族群中定義模糊隸屬度、隸屬度閾值和補(bǔ)償系數(shù)，利用鄰域青蛙之間的分布程度衡量某一青蛙的模糊隸屬度。在一次局部搜索中，對(duì)族群最差個(gè)體按模糊隸屬度和隸屬度閾值關(guān)系給出2種更新方法，設(shè)置相應(yīng)的補(bǔ)償系數(shù)。實(shí)驗(yàn)結(jié)果表明，隸屬度閾值為0.9的FTCSFLA其收斂精度、速度均優(yōu)于SFLA和隸屬度閾值為0.5的FTCSFLA，當(dāng)隸屬度閾值取值在(0.5,0.9]之間時(shí)，F(xiàn)TCSFLA的性能達(dá)到最優(yōu)。
混合蛙跳算法；模糊隸屬度；隸屬度閾值；補(bǔ)償系數(shù)；模糊分組；擾動(dòng)策略；優(yōu)化性能
1 概述
混合蛙跳算法(Shuffled Frog Leaping Algorithm, SFLA)是模擬青蛙覓食過(guò)程中信息共享和交流特點(diǎn)提出的群體智能算法[1-2]，已經(jīng)成功應(yīng)用于許多領(lǐng)域。近年來(lái)學(xué)者們對(duì)SFLA優(yōu)化性能做了諸多改進(jìn)：文獻(xiàn)[3]引入閾值選擇策略，通過(guò)對(duì)不滿足閾值條件的個(gè)體分量不予更新的策略減小了個(gè)體空間差異。文獻(xiàn)[4]引入遺傳算子增加對(duì)局部極值的擾動(dòng)并借鑒粒子群優(yōu)化算法中粒子飛行經(jīng)驗(yàn)對(duì)青蛙移動(dòng)策略進(jìn)行優(yōu)化。但是SFLA對(duì)于求解復(fù)雜問(wèn)題依然存在收斂速度慢、優(yōu)化精度低的缺點(diǎn)。這主要是由SFLA的分組方式以及局部更新策略引起的。首先，SFLA在局部搜索前，各青蛙是被逐一循環(huán)分配給各個(gè)族群的。這種循環(huán)分配存在固定性，全局最優(yōu)個(gè)體所在分組更新后得到新的全局最優(yōu)個(gè)體的次數(shù)最多，導(dǎo)致該分組尋優(yōu)能力強(qiáng)于其他分組，一旦該分組陷入局部最優(yōu)，則整個(gè)群體很難跳出局部極值[5]，容易陷入早熟。其次，在局部搜索中，最差個(gè)體通過(guò)與最優(yōu)個(gè)體的差異進(jìn)行更新，而這種更新存在隨機(jī)性，缺乏一定的尋優(yōu)指導(dǎo)性。這些因素很大程度上影響了SFLA的收斂速度和優(yōu)化精度。
文獻(xiàn)[6-7]將模糊理論引入支持向量機(jī)(Support Vector Machine, SVM)中，通過(guò)對(duì)每個(gè)輸入樣本增加一個(gè)模糊隸屬度，對(duì)含有噪聲或野值的樣本賦予較小權(quán)值，有效提高了SVM分類準(zhǔn)確率及計(jì)算效率。目前，已有學(xué)者將模糊理論與SFLA結(jié)合研究：文獻(xiàn)[8]在SFLA基礎(chǔ)上利用模糊控制器的模糊語(yǔ)言變量及控制規(guī)則得出模糊控制表，改進(jìn)后算法在尋優(yōu)精度、收斂速度上均有大幅提高；文獻(xiàn)[9]將SFLA應(yīng)用于模糊C均值算法，克服了算法易陷入局部極小的缺陷，提高了算法尋優(yōu)能力。
為克服SFLA固定循環(huán)分配方式容易引起早熟現(xiàn)象的缺陷，并改善局部搜索中的隨機(jī)性更新，本文將模糊分類思想[6-7]引入SFLA，并借鑒文獻(xiàn)[3]固定閾值選擇思想，在族群中定義模糊隸屬度，設(shè)置隸屬度閾值對(duì)最差個(gè)體更新進(jìn)行適度控制，提出一種新的基于模糊閾值補(bǔ)償?shù)幕旌贤芴惴?Shuffled Fro g L eaping Algorithm Based on Fu zzy Threshold Compensation, FTCSFLA)。
2 SFLA算法
隨機(jī)生成P=N×M只青蛙組成的初始群體，第i只青蛙個(gè)體記為xi=(xi1,xi2,…,xis)，其中，s為個(gè)體維數(shù)；M為族群數(shù)；N為族群內(nèi)青蛙個(gè)數(shù)。對(duì)每個(gè)青蛙個(gè)體計(jì)算適應(yīng)度f(wàn)(xi)，并按f(xi)降序排序，再逐一循環(huán)分配給M個(gè)族群。對(duì)每個(gè)族群中f( xi)最差的個(gè)體x( k)w按式(1)進(jìn)行局部搜索：
在式(1)～式(3)中，x( k)w,new和x( k)w,old分別表示族群k中最差個(gè)體更新的新舊值；x( k)b表示族群k中局部最優(yōu)個(gè)體；x( g)b表示青蛙群體的全局最優(yōu)個(gè)體；xnew表示定義域內(nèi)隨機(jī)產(chǎn)生的一個(gè)新個(gè)體。對(duì)各族群重復(fù)局部搜索，直至族群k的局部進(jìn)化次數(shù)T1為止，將所有族群的P個(gè)青蛙個(gè)體重新混合進(jìn)行全局信息交換，并按適應(yīng)度重新排序和劃分族群，再對(duì)各族群局部迭代，如此反復(fù)迭代直至滿足問(wèn)題終止條件或達(dá)到全局進(jìn)化次數(shù)T2為止。
3 FTCSFLA算法
3.1 模糊閾值補(bǔ)償?shù)乃枷?/p>
SFLA局部搜索前的循環(huán)分配方式會(huì)導(dǎo)致全局最優(yōu)個(gè)體所在分組尋優(yōu)能力強(qiáng)于其他分組，易使算法陷入早熟。此外，在一次局部搜索中，式(1)、式(2)中最優(yōu)個(gè)體對(duì)最差個(gè)體的差異擾動(dòng)rand(0,1)是[0,1]間隨機(jī)數(shù)[10]，存在很大的隨機(jī)性，沒(méi)有體現(xiàn)出更好的尋優(yōu)指導(dǎo)性。針對(duì)以上缺陷，本文引入模糊閾值補(bǔ)償思想，對(duì)每個(gè)青蛙進(jìn)行模糊分組，在各分組族群中定義模糊隸屬度，設(shè)置隸屬度閾值，并對(duì)局部搜索中最差個(gè)體的更新設(shè)置補(bǔ)償系數(shù)。以動(dòng)態(tài)模糊的方式調(diào)整最差個(gè)體的更新程度，以避免局部早熟，達(dá)到全局最優(yōu)。
3.1.1 模糊隸屬度
定義1(模糊隸屬度) 每個(gè)青蛙i(i=1,2,…,N)屬于某族群k(k=1,2,…,M)的模糊隸屬度記為s(k)i,0＜s(k)i＜1。在一次局部搜索中，每個(gè)族群k中f(xi)最差個(gè)體x(k)w對(duì)應(yīng)的模糊隸屬度記為s(k)w。其中，s(k)i表示第i個(gè)青蛙隸屬于第k個(gè)族群的程度。隸屬度越大，它隸屬于族群k的可能性越大。因此，族群k是由s(k)i大于某個(gè)值的多個(gè)青蛙組成的。
3.1.2 模糊隸屬度的確定
在生成的P=N×M個(gè)青蛙初始群體中，對(duì)第k(k= 1,2,…,M)個(gè)族群隨機(jī)選擇N個(gè)青蛙作為鄰域青蛙，利用鄰域青蛙之間的分布程度衡量某一青蛙的模糊隸屬度，并采用歐氏距離度量?jī)汕嗤荛g距離。則鄰域青蛙內(nèi)第i(i= 1,2,…,N)個(gè)青蛙x(k)i的模糊隸屬度通過(guò)下式確定：
3.1.3 隸屬度閾值
定義2(隸屬度閾值) 某青蛙i隸屬于某族群k的隸屬程度由其s(k)i是否大于某一隸屬度閾值表示，該隸屬度閾值記為s0,0＜s0＜1。
如果s( k)i≥s0，表示青蛙i隸屬于族群k的程度大，認(rèn)為青蛙i隸屬于族群k。否則，表示隸屬于族群k的程度小，認(rèn)為青蛙i不隸屬于族群k。
在一次局部搜索中，對(duì)族群k定義如下：
如果按式(6)更新仍無(wú)法提高尋優(yōu)指導(dǎo)性，則使用式(7)進(jìn)行局部搜索：
擾動(dòng)策略1如果青蛙i隸屬于某族群k，即s( k)i≥s0，則該族群最差個(gè)體x( k)w按式(6)局部最優(yōu)個(gè)體x( k)b進(jìn)行差異擾動(dòng)。否則，按式(7)全局最優(yōu)個(gè)體x( g)b進(jìn)行差異擾動(dòng)。
證明：如果s( k)i≥s0，也即s( k)w≥s0時(shí)，說(shuō)明最差個(gè)體x( k)w隸屬于族群k，因此，使用式(6)局部最優(yōu)個(gè)體x( k)b進(jìn)行差異擾動(dòng)體現(xiàn)了局部尋優(yōu)指導(dǎo)能力。下面分2種情況證明擾動(dòng)策略1后半部分：第1種情況：如果s( k)i＜s0，也即s( k)w＜s0時(shí)，那么最差個(gè)體x( k)w不屬于族群k，局部最優(yōu)個(gè)體x( k)b已無(wú)法提高尋優(yōu)性能，使用式(7)全局最優(yōu)個(gè)體x( g)b進(jìn)行差異擾動(dòng)體現(xiàn)了全局尋優(yōu)指導(dǎo)能力。式(7)中1-s( k)w表示不屬于族群k的最差個(gè)體對(duì)應(yīng)的模糊隸屬度。第2種情況：如果s( k)i≥s0，也即s( k)w≥s0時(shí)，若按式(6)對(duì)x( k)w更新后，如果仍有f( x( k)w,new)≥f( x( k)w,old)，說(shuō)明式(6)用局部最優(yōu)個(gè)體進(jìn)行差異擾動(dòng)無(wú)法找到最優(yōu)值，因此，應(yīng)按第1種情況最差個(gè)體x( k)w不隸屬于族群k對(duì)待。證畢。
擾動(dòng)策略1利用模糊隸屬度及隸屬度閾值之間關(guān)系對(duì)青蛙群體模糊分組，克服了SFLA固定循環(huán)分配方式易引起早熟的缺陷；同時(shí)，在一次局部搜索中，分別利用局部最優(yōu)個(gè)體x( k)b、全局最優(yōu)個(gè)體x( g)b對(duì)x( k)w的尋優(yōu)進(jìn)行指導(dǎo)，避免了式(1)、式(2)隨機(jī)性更新的缺陷。
3.1.4 補(bǔ)償系數(shù)
定義3(補(bǔ)償系數(shù)) 為統(tǒng)一表示式(6)、式(7)最優(yōu)個(gè)體對(duì)最差個(gè)體的尋優(yōu)指導(dǎo)能力，對(duì)每個(gè)族群k定義補(bǔ)償系數(shù)，記為m( k),m( k)∈{0,1}。
其中，1-m( k)表示使用局部最優(yōu)個(gè)體差異擾動(dòng)仍無(wú)法達(dá)到最優(yōu)時(shí)，全局最優(yōu)個(gè)體對(duì)差異擾動(dòng)的尋優(yōu)補(bǔ)償能力。
綜上，在一次局部搜索中，F(xiàn)TCSFLA將按擾動(dòng)策略2進(jìn)行最差個(gè)體更新。
3.2 算法步驟
FTCSFLA是引入模糊隸屬度、隸屬度閾值及補(bǔ)償系數(shù)等概念，并將模糊閾值補(bǔ)償?shù)乃枷霊?yīng)用于SFLA，算法的具體步驟如下：
Step1隨機(jī)生成P=N×M只青蛙的初始群體，記為XP={xi|xi=(xi1,xi2,…,xis),i=1,2,…,P}，其中，s為個(gè)體維數(shù)；M為族群數(shù)；N為族群內(nèi)青蛙個(gè)數(shù)。
Step2設(shè)置隸屬度閾值s0，并令初始補(bǔ)償系數(shù)m( k)為1，對(duì)每個(gè)青蛙個(gè)體計(jì)算適應(yīng)度f(wàn)( xi)，并按式(4)計(jì)算第k( k=1,2,…,M)個(gè)族群的第i( i=1,2,…,N )個(gè)青蛙x( k)i的模糊隸屬度s( k)i，將P個(gè)青蛙模糊分組到M個(gè)族群中。
Step3對(duì)族群k中f(xi)最差的個(gè)體x( k)w進(jìn)行局部搜索：
Step3.1按f( xi)降序排序，確定x( k)w、x( k)b、x( g)b及x( k)w對(duì)應(yīng)的s( k)w。
Step3.2根據(jù)擾動(dòng)策略2對(duì)x( k)w進(jìn)行更新，計(jì)算x( k)w,new。
Step4判斷各族群局部進(jìn)化次數(shù)是否達(dá)到T1，若未達(dá)到，轉(zhuǎn)至Step3。否則，判斷青蛙族群全局進(jìn)化次數(shù)是否達(dá)到T2或x( g)b是否達(dá)到收斂精度，若未達(dá)到，轉(zhuǎn)至Step2進(jìn)行全局信息交換，否則，算法停止，輸出x( g)b。
3.3 算法效率分析
FTCSFLA算法的改進(jìn)主要是在SFLA基礎(chǔ)上引入了模糊隸屬度、隸屬度閾值及補(bǔ)償系數(shù)，算法效率的改進(jìn)體現(xiàn)在以下3點(diǎn)：
(1)Step2中計(jì)算s( k)i并模糊分組，計(jì)算只在外層循環(huán)中增加T2×M×N次操作時(shí)間。
(2)Step3.1對(duì)每個(gè)族群按f( xi)降序排序，排序由原來(lái)的外層循環(huán)T2次改變?yōu)閮?nèi)層循環(huán)T1×M次。
(3)Step3.2中根據(jù)改進(jìn)的局部搜索策略更新x( k)w。增加了比較s( k)w≥s0和s( k)w＜s0的2T1次。
SFLA算法的時(shí)間復(fù)雜度是O( T1×T2×M×s+T2)，空間復(fù)雜度是O( M×N×s)。而FTCSFLA算法的時(shí)間復(fù)雜度是O( T1×T2×M×s+T2×M×N+T1×M+2T1)，空間復(fù)雜度是O( M×N×s+M×N +2)。由于T1＜＜T2，因此FTCSFLA與SFLA的效率是同數(shù)量級(jí)的，并未增加大的運(yùn)算開(kāi)銷和空間。
4 實(shí)驗(yàn)及結(jié)果分析
實(shí)驗(yàn)采用Sphere、Rastrigrin、Griewank和Ackley[11-12]4個(gè)測(cè)試函數(shù)作為青蛙個(gè)體適應(yīng)度，分別對(duì)SFLA和FTCSFLA算法進(jìn)行極小值尋優(yōu)性能測(cè)試，并對(duì)FTCSFLA算法的隸屬度閾值s0設(shè)置不同取值進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)參數(shù)設(shè)置如下：青蛙群體規(guī)模P=200，族群數(shù)M=20，族群內(nèi)青蛙個(gè)數(shù)N=10，各測(cè)試函數(shù)對(duì)應(yīng)青蛙個(gè)體維數(shù)s=30，T1=10，T2=500。設(shè)置s0=0.9和s0=0.5，分別對(duì)應(yīng)算法FTCSFLA0.9和FTCSFLA0.5。實(shí)驗(yàn)所用計(jì)算機(jī)處理器為Intel Core2，主頻為2.0 GHz，內(nèi)存為2.0 GB，測(cè)試平臺(tái)是VC++6.0。最終測(cè)試結(jié)果采用獨(dú)立運(yùn)行30次后的平均值。
算法性能評(píng)價(jià)采用如下方法：(1)固定全局進(jìn)化次數(shù)，評(píng)價(jià)算法收斂精度和速度；(2)固定收斂精度，評(píng)價(jià)算法達(dá)到該精度所需的全局進(jìn)化次數(shù)；(3)不同的隸屬度閾值對(duì)應(yīng)的FTCSFLA之間優(yōu)化性能比較。
4.1 固定全局進(jìn)化次數(shù)的收斂精度和速度分析
各算法收斂精度比較如表1所示，4個(gè)測(cè)試函數(shù)在固定全局進(jìn)化次數(shù)條件下函數(shù)平均最優(yōu)值進(jìn)化曲線比較如圖1～圖4所示，其中，fitness代表適應(yīng)度。
表1 固定全局進(jìn)化次數(shù)結(jié)果比較
圖1 Sph ere函數(shù)平均最優(yōu)值進(jìn)化曲線比較
圖2 R astrigrin函數(shù)平均最優(yōu)值進(jìn)化曲線比較
圖3 G riewank函數(shù)平均最優(yōu)值進(jìn)化曲線比較
圖 4 A ckley函數(shù)平均最優(yōu)值進(jìn)化曲線比較
可以看出，本文算法各項(xiàng)數(shù)值上均優(yōu)于SFLA，進(jìn)化曲線也表明其收斂速度均優(yōu)于SFLA。對(duì)單峰值Sphere函數(shù)，F(xiàn)TCSFLA0.9和FTCSFLA0.5均達(dá)到了理論極小值0，圖1顯示，F(xiàn)TCSFLA0.9進(jìn)化到184次時(shí)就達(dá)到了極小值，F(xiàn)TCSFLA0.5進(jìn)化到205次時(shí)也達(dá)到了極小值。由于這2個(gè)算法的收斂速度很快，因此在圖1中只顯示了達(dá)到極小值之前的進(jìn)化曲線，此后沒(méi)有再顯示進(jìn)化曲線表示算法已經(jīng)收斂為極小值。對(duì)多峰值Rastrigrin、Griewank和Ackley函數(shù)，因隸屬度閾值s0的調(diào)節(jié)，使得青蛙隸屬于不同族群的程度發(fā)生了變化，F(xiàn)TCSFLA0.9和FTCSFLA0.5的收斂精度有上下浮動(dòng)，從進(jìn)化曲線表明隸屬度閾值s0取值范圍在(0.5, 0.9]之間FTCSFLA收斂精度和收斂速度最為理想。
4.2 固定收斂精度的全局進(jìn)化次數(shù)分析
4個(gè)測(cè)試函數(shù)目標(biāo)精度和各函數(shù)達(dá)到目標(biāo)精度時(shí)的平均進(jìn)化次數(shù)見(jiàn)表2[11-12]。實(shí)驗(yàn)結(jié)果表明，F(xiàn)TCSFLA0.9達(dá)到目標(biāo)精度的次數(shù)明顯少于SFLA和FTCSFLA0.5。
表2 固定收斂精度結(jié)果比較
以上2個(gè)不同角度的對(duì)比結(jié)果表明，F(xiàn)TCSFLA0.9收斂精度、速度均優(yōu)于SFLA和FTCSFLA0.5，并且FTCSFLA在隸屬度閾值取值范圍在(0.5,0.9]之間時(shí)其收斂精度和速度為最優(yōu)。
5 結(jié)束語(yǔ)
本文提出一種基于模糊閾值補(bǔ)償?shù)幕旌贤芴惴?，引入模糊閾值補(bǔ)償思想，對(duì)青蛙模糊分組，在族群中定義了模糊隸屬度、隸屬度閾值和補(bǔ)償系數(shù)等概念。在局部搜索中，設(shè)置隸屬度閾值，根據(jù)模糊隸屬度和隸屬度閾值關(guān)系，給出了2種最差個(gè)體的更新方法，并設(shè)置補(bǔ)償系數(shù)統(tǒng)一表達(dá)了2種更新方法。該算法以動(dòng)態(tài)模糊的方式調(diào)整最差個(gè)體的更新程度，避免了局部早熟。實(shí)驗(yàn)結(jié)果表明，該算法在單峰值和多峰值函數(shù)尋優(yōu)問(wèn)題上均具有較高的收斂速度和精度，改進(jìn)了SFLA的優(yōu)化性能。未來(lái)將進(jìn)一步研究動(dòng)態(tài)隸屬度閾值對(duì)算法性能的影響。
[1] Eusuff M M, Lansey K E. O ptimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm[J]. Journal of Water Sourc es Planning an d M anagement, 2003, 129(3): 210-225.
[2] Eusuff M M, Lansey K E, Pasha F. Shuffled Frog Leaping Algorithm: A Memetic Meta-heuristic for Discrete O ptimization[J]. Engineering Optimization, 2006, 38(2): 129-154.
[3] 李英海, 周建中, 楊俊杰, 等. 一種基于閾值選擇策略的改進(jìn)混合蛙跳算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2 007, 43(35): 19-21.
[4] 歐 陽(yáng), 孫元姝. 基于改進(jìn)混合蛙跳算法的網(wǎng)格任務(wù)調(diào)度策略[J]. 計(jì)算機(jī)工程, 2011, 37(21): 146-148.
[5] 代永強(qiáng), 王聯(lián)國(guó). 帶記憶功能的混合蛙跳算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2011, 32(9): 3170-3173.
[6] L in Chunfu, Wang Shengde. Fuzzy Support Vector Machines[J]. IEEE Transcations on Neural Networks, 2002, 13(2): 464-471.
[7] Huang Hanpang, Liu Y H. Fuzzy Support Vector Machines for Pattern Recognition and Data Mining[J]. International Journal of Fuzzy Systems, 2002, 4(3): 826-835.
[8] 葛 宇, 王學(xué)平, 梁 靜. 改進(jìn)的混合蛙跳算法[J]. 計(jì)算機(jī)應(yīng)用, 2012, 32(1): 234-237.
[9] 趙小強(qiáng), 劉悅婷. 基于選擇和變異機(jī)制的蛙跳FCM算法[J].計(jì)算機(jī)應(yīng)用研究, 2012, 29(6): 2068-2071.
[10] 王 輝. 一種帶共享因子的人工蜂群算法[J]. 計(jì)算機(jī)工程, 2011, 37(22): 139-142.
[11] 王 凌. 智能優(yōu)化算法及其應(yīng)用[M]. 北京: 清華大學(xué)出版社, 2001.
[12] Engelbrecht A P. F undamentals of Computational Swarm Intelligence[M]. 譚 營(yíng), 譯. 北京: 清華大學(xué)出版社, 2009.
編輯 金胡考
Shuffled Frog Leaping Algorithm Based on Fuzzy Threshold Compensation
LIU Li-qun1, WANG Lian-guo1, HUO Jiu-yuan2, HAN Jun-ying1, LIU Cheng-zhong1
(1. College of Information Science and Technology, Gansu Agricultural University, Lanzhou 730070, China; 2. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)
To solve the problem of slow convergence speed and low optimization precision of Shuffled Frog Leaping Algorithm (SFLA) in solving complex problems, a Shuffled Frog Leaping Algorithm Based on Fuzzy Threshold Compensation(FTCSFLA) is proposed. The fuzzy grouping idea is introduced to divide different frogs into fuzzy groups, and disturbance strategy in a local search is improved based on the basic SFLA. Each fuzzy group is defined with a total membership threshold and a total compensation coefficient, and each frog is defined with a fuzzy membership, which is scaled with the distribution degree of neighborhood frogs. In a local search, the worst individual is updated by two methods in each group, which is partitioned ac cording to the relation between fuzzy membership and membership threshold. In t wo methods, a com pensation coefficient is set to gi ve a u nify expression. Experimental results show th at the con vergence precision and speed of FTCSFLA which membership threshold is 0.9 is better than SFLA and FTCSFLA which membership threshold is 0.5. The evolution curve shows that the convergence precision and speed of FTCSFLA is the optimum when its membership threshold is between (0.5, 0.9].
Shuffled Frog Leaping Algorithm(SFLA); fuzzy membership; membership threshold; compensation coef ficient; fuzzy grouping; disturbance strategy; optimization performance
10.3969/j.issn.1000-3428.2014.05.035
國(guó)家自然科學(xué)基金資助項(xiàng)目(61063028)；中國(guó)博士后科學(xué)基金資助項(xiàng)目(2013M542398)；甘肅省高等學(xué)校研究生導(dǎo)師科研基金資助項(xiàng)目(1202-04, 1 102-05)；甘肅省教育廳信息化戰(zhàn)略研究基金資助項(xiàng)目(2011-02)；甘肅省自然科學(xué)研究計(jì)劃基金資助項(xiàng)目(1308RJZA214, 1208RJZA133)；甘肅農(nóng)業(yè)大學(xué)盛彤笙科技創(chuàng)新基金資助項(xiàng)目(GSAU-STS-1322)；蘭州交通大學(xué)青年科學(xué)基金資助項(xiàng)目(2013032)。
劉立群(1982－)，女，講師、碩士，主研方向：群體智能算法，數(shù)據(jù)庫(kù)技術(shù)；王聯(lián)國(guó)，教授、博士；火久元，副教授、博士；韓俊英，副教授、碩士；劉成忠，副教授、博士研究生。
2013-03-04
2013-05-27E-mail：llqhjy@126.com
1000-3428(2014)05-0168-05
A
TP18
猜你喜歡
Cahn-Hilliard-Brinkman系統(tǒng)的全局吸引子數(shù)學(xué)物理學(xué)報(bào)(2022年4期)2022-08-22 04:07:12 “三層七法”：提高初中生三級(jí)蛙跳能力的實(shí)踐研究體育教學(xué)(2022年4期)2022-05-05 21:26:58 量子Navier-Stokes方程弱解的全局存在性數(shù)學(xué)物理學(xué)報(bào)(2022年2期)2022-04-26 14:08:04 論《白牙》中流散族群內(nèi)部的文化沖突英美文學(xué)研究論叢(2021年2期)2021-02-16 00:37:30 新興族群的自白時(shí)代郵刊(2019年24期)2019-12-17 11:49:30 漢德森 領(lǐng)跑年輕族群保健品市場(chǎng)知識(shí)經(jīng)濟(jì)·中國(guó)直銷(2018年9期)2018-09-28 03:15:26 落子山東，意在全局金橋(2018年4期)2018-09-26 02:24:54 高句麗族群共同體的早期演進(jìn)東北史地(學(xué)問(wèn))(2017年1期)2017-06-15 20:27:19 中娃娃畫(huà)報(bào)(2016年5期)2016-08-03 19:25:40 新思路：牽一發(fā)動(dòng)全局中國(guó)衛(wèi)生(2014年5期)2014-11-10 02:11:26
劉立群，王聯(lián)國(guó)，火久元，韓俊英，劉成忠
(1. 甘肅農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，蘭州 730 070；2. 蘭州交通大學(xué)電子與信息工程學(xué)院，蘭州 73007 0)
基于模糊閾值補(bǔ)償?shù)幕旌贤芴惴?/p>
劉立群1，王聯(lián)國(guó)1，火久元2，韓俊英1，劉成忠1
(1. 甘肅農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，蘭州 730 070；2. 蘭州交通大學(xué)電子與信息工程學(xué)院，蘭州 73007 0)
針對(duì)混合蛙跳算法(SFLA)求解復(fù)雜問(wèn)題時(shí)收斂速度慢、優(yōu)化精度低的缺點(diǎn)，提出一種基于模糊閾值補(bǔ)償?shù)幕旌贤芴惴?FTCSFLA)。在SFLA的基礎(chǔ)上，采用模糊分組方法對(duì)青蛙分組并改進(jìn)局部搜索的擾動(dòng)策略。在族群中定義模糊隸屬度、隸屬度閾值和補(bǔ)償系數(shù)，利用鄰域青蛙之間的分布程度衡量某一青蛙的模糊隸屬度。在一次局部搜索中，對(duì)族群最差個(gè)體按模糊隸屬度和隸屬度閾值關(guān)系給出2種更新方法，設(shè)置相應(yīng)的補(bǔ)償系數(shù)。實(shí)驗(yàn)結(jié)果表明，隸屬度閾值為0.9的FTCSFLA其收斂精度、速度均優(yōu)于SFLA和隸屬度閾值為0.5的FTCSFLA，當(dāng)隸屬度閾值取值在(0.5,0.9]之間時(shí)，F(xiàn)TCSFLA的性能達(dá)到最優(yōu)。
混合蛙跳算法；模糊隸屬度；隸屬度閾值；補(bǔ)償系數(shù)；模糊分組；擾動(dòng)策略；優(yōu)化性能
1 概述
混合蛙跳算法(Shuffled Frog Leaping Algorithm, SFLA)是模擬青蛙覓食過(guò)程中信息共享和交流特點(diǎn)提出的群體智能算法[1-2]，已經(jīng)成功應(yīng)用于許多領(lǐng)域。近年來(lái)學(xué)者們對(duì)SFLA優(yōu)化性能做了諸多改進(jìn)：文獻(xiàn)[3]引入閾值選擇策略，通過(guò)對(duì)不滿足閾值條件的個(gè)體分量不予更新的策略減小了個(gè)體空間差異。文獻(xiàn)[4]引入遺傳算子增加對(duì)局部極值的擾動(dòng)并借鑒粒子群優(yōu)化算法中粒子飛行經(jīng)驗(yàn)對(duì)青蛙移動(dòng)策略進(jìn)行優(yōu)化。但是SFLA對(duì)于求解復(fù)雜問(wèn)題依然存在收斂速度慢、優(yōu)化精度低的缺點(diǎn)。這主要是由SFLA的分組方式以及局部更新策略引起的。首先，SFLA在局部搜索前，各青蛙是被逐一循環(huán)分配給各個(gè)族群的。這種循環(huán)分配存在固定性，全局最優(yōu)個(gè)體所在分組更新后得到新的全局最優(yōu)個(gè)體的次數(shù)最多，導(dǎo)致該分組尋優(yōu)能力強(qiáng)于其他分組，一旦該分組陷入局部最優(yōu)，則整個(gè)群體很難跳出局部極值[5]，容易陷入早熟。其次，在局部搜索中，最差個(gè)體通過(guò)與最優(yōu)個(gè)體的差異進(jìn)行更新，而這種更新存在隨機(jī)性，缺乏一定的尋優(yōu)指導(dǎo)性。這些因素很大程度上影響了SFLA的收斂速度和優(yōu)化精度。
文獻(xiàn)[6-7]將模糊理論引入支持向量機(jī)(Support Vector Machine, SVM)中，通過(guò)對(duì)每個(gè)輸入樣本增加一個(gè)模糊隸屬度，對(duì)含有噪聲或野值的樣本賦予較小權(quán)值，有效提高了SVM分類準(zhǔn)確率及計(jì)算效率。目前，已有學(xué)者將模糊理論與SFLA結(jié)合研究：文獻(xiàn)[8]在SFLA基礎(chǔ)上利用模糊控制器的模糊語(yǔ)言變量及控制規(guī)則得出模糊控制表，改進(jìn)后算法在尋優(yōu)精度、收斂速度上均有大幅提高；文獻(xiàn)[9]將SFLA應(yīng)用于模糊C均值算法，克服了算法易陷入局部極小的缺陷，提高了算法尋優(yōu)能力。
為克服SFLA固定循環(huán)分配方式容易引起早熟現(xiàn)象的缺陷，并改善局部搜索中的隨機(jī)性更新，本文將模糊分類思想[6-7]引入SFLA，并借鑒文獻(xiàn)[3]固定閾值選擇思想，在族群中定義模糊隸屬度，設(shè)置隸屬度閾值對(duì)最差個(gè)體更新進(jìn)行適度控制，提出一種新的基于模糊閾值補(bǔ)償?shù)幕旌贤芴惴?Shuffled Fro g L eaping Algorithm Based on Fu zzy Threshold Compensation, FTCSFLA)。
2 SFLA算法
隨機(jī)生成P=N×M只青蛙組成的初始群體，第i只青蛙個(gè)體記為xi=(xi1,xi2,…,xis)，其中，s為個(gè)體維數(shù)；M為族群數(shù)；N為族群內(nèi)青蛙個(gè)數(shù)。對(duì)每個(gè)青蛙個(gè)體計(jì)算適應(yīng)度f(wàn)(xi)，并按f(xi)降序排序，再逐一循環(huán)分配給M個(gè)族群。對(duì)每個(gè)族群中f( xi)最差的個(gè)體x( k)w按式(1)進(jìn)行局部搜索：
在式(1)～式(3)中，x( k)w,new和x( k)w,old分別表示族群k中最差個(gè)體更新的新舊值；x( k)b表示族群k中局部最優(yōu)個(gè)體；x( g)b表示青蛙群體的全局最優(yōu)個(gè)體；xnew表示定義域內(nèi)隨機(jī)產(chǎn)生的一個(gè)新個(gè)體。對(duì)各族群重復(fù)局部搜索，直至族群k的局部進(jìn)化次數(shù)T1為止，將所有族群的P個(gè)青蛙個(gè)體重新混合進(jìn)行全局信息交換，并按適應(yīng)度重新排序和劃分族群，再對(duì)各族群局部迭代，如此反復(fù)迭代直至滿足問(wèn)題終止條件或達(dá)到全局進(jìn)化次數(shù)T2為止。
3 FTCSFLA算法
3.1 模糊閾值補(bǔ)償?shù)乃枷?/p>
SFLA局部搜索前的循環(huán)分配方式會(huì)導(dǎo)致全局最優(yōu)個(gè)體所在分組尋優(yōu)能力強(qiáng)于其他分組，易使算法陷入早熟。此外，在一次局部搜索中，式(1)、式(2)中最優(yōu)個(gè)體對(duì)最差個(gè)體的差異擾動(dòng)rand(0,1)是[0,1]間隨機(jī)數(shù)[10]，存在很大的隨機(jī)性，沒(méi)有體現(xiàn)出更好的尋優(yōu)指導(dǎo)性。針對(duì)以上缺陷，本文引入模糊閾值補(bǔ)償思想，對(duì)每個(gè)青蛙進(jìn)行模糊分組，在各分組族群中定義模糊隸屬度，設(shè)置隸屬度閾值，并對(duì)局部搜索中最差個(gè)體的更新設(shè)置補(bǔ)償系數(shù)。以動(dòng)態(tài)模糊的方式調(diào)整最差個(gè)體的更新程度，以避免局部早熟，達(dá)到全局最優(yōu)。
3.1.1 模糊隸屬度
定義1(模糊隸屬度) 每個(gè)青蛙i(i=1,2,…,N)屬于某族群k(k=1,2,…,M)的模糊隸屬度記為s(k)i,0＜s(k)i＜1。在一次局部搜索中，每個(gè)族群k中f(xi)最差個(gè)體x(k)w對(duì)應(yīng)的模糊隸屬度記為s(k)w。其中，s(k)i表示第i個(gè)青蛙隸屬于第k個(gè)族群的程度。隸屬度越大，它隸屬于族群k的可能性越大。因此，族群k是由s(k)i大于某個(gè)值的多個(gè)青蛙組成的。
3.1.2 模糊隸屬度的確定
在生成的P=N×M個(gè)青蛙初始群體中，對(duì)第k(k= 1,2,…,M)個(gè)族群隨機(jī)選擇N個(gè)青蛙作為鄰域青蛙，利用鄰域青蛙之間的分布程度衡量某一青蛙的模糊隸屬度，并采用歐氏距離度量?jī)汕嗤荛g距離。則鄰域青蛙內(nèi)第i(i= 1,2,…,N)個(gè)青蛙x(k)i的模糊隸屬度通過(guò)下式確定：
3.1.3 隸屬度閾值
定義2(隸屬度閾值) 某青蛙i隸屬于某族群k的隸屬程度由其s(k)i是否大于某一隸屬度閾值表示，該隸屬度閾值記為s0,0＜s0＜1。
如果s( k)i≥s0，表示青蛙i隸屬于族群k的程度大，認(rèn)為青蛙i隸屬于族群k。否則，表示隸屬于族群k的程度小，認(rèn)為青蛙i不隸屬于族群k。
在一次局部搜索中，對(duì)族群k定義如下：
如果按式(6)更新仍無(wú)法提高尋優(yōu)指導(dǎo)性，則使用式(7)進(jìn)行局部搜索：
擾動(dòng)策略1如果青蛙i隸屬于某族群k，即s( k)i≥s0，則該族群最差個(gè)體x( k)w按式(6)局部最優(yōu)個(gè)體x( k)b進(jìn)行差異擾動(dòng)。否則，按式(7)全局最優(yōu)個(gè)體x( g)b進(jìn)行差異擾動(dòng)。
證明：如果s( k)i≥s0，也即s( k)w≥s0時(shí)，說(shuō)明最差個(gè)體x( k)w隸屬于族群k，因此，使用式(6)局部最優(yōu)個(gè)體x( k)b進(jìn)行差異擾動(dòng)體現(xiàn)了局部尋優(yōu)指導(dǎo)能力。下面分2種情況證明擾動(dòng)策略1后半部分：第1種情況：如果s( k)i＜s0，也即s( k)w＜s0時(shí)，那么最差個(gè)體x( k)w不屬于族群k，局部最優(yōu)個(gè)體x( k)b已無(wú)法提高尋優(yōu)性能，使用式(7)全局最優(yōu)個(gè)體x( g)b進(jìn)行差異擾動(dòng)體現(xiàn)了全局尋優(yōu)指導(dǎo)能力。式(7)中1-s( k)w表示不屬于族群k的最差個(gè)體對(duì)應(yīng)的模糊隸屬度。第2種情況：如果s( k)i≥s0，也即s( k)w≥s0時(shí)，若按式(6)對(duì)x( k)w更新后，如果仍有f( x( k)w,new)≥f( x( k)w,old)，說(shuō)明式(6)用局部最優(yōu)個(gè)體進(jìn)行差異擾動(dòng)無(wú)法找到最優(yōu)值，因此，應(yīng)按第1種情況最差個(gè)體x( k)w不隸屬于族群k對(duì)待。證畢。
擾動(dòng)策略1利用模糊隸屬度及隸屬度閾值之間關(guān)系對(duì)青蛙群體模糊分組，克服了SFLA固定循環(huán)分配方式易引起早熟的缺陷；同時(shí)，在一次局部搜索中，分別利用局部最優(yōu)個(gè)體x( k)b、全局最優(yōu)個(gè)體x( g)b對(duì)x( k)w的尋優(yōu)進(jìn)行指導(dǎo)，避免了式(1)、式(2)隨機(jī)性更新的缺陷。
3.1.4 補(bǔ)償系數(shù)
定義3(補(bǔ)償系數(shù)) 為統(tǒng)一表示式(6)、式(7)最優(yōu)個(gè)體對(duì)最差個(gè)體的尋優(yōu)指導(dǎo)能力，對(duì)每個(gè)族群k定義補(bǔ)償系數(shù)，記為m( k),m( k)∈{0,1}。
其中，1-m( k)表示使用局部最優(yōu)個(gè)體差異擾動(dòng)仍無(wú)法達(dá)到最優(yōu)時(shí)，全局最優(yōu)個(gè)體對(duì)差異擾動(dòng)的尋優(yōu)補(bǔ)償能力。
綜上，在一次局部搜索中，F(xiàn)TCSFLA將按擾動(dòng)策略2進(jìn)行最差個(gè)體更新。
3.2 算法步驟
FTCSFLA是引入模糊隸屬度、隸屬度閾值及補(bǔ)償系數(shù)等概念，并將模糊閾值補(bǔ)償?shù)乃枷霊?yīng)用于SFLA，算法的具體步驟如下：
Step1隨機(jī)生成P=N×M只青蛙的初始群體，記為XP={xi|xi=(xi1,xi2,…,xis),i=1,2,…,P}，其中，s為個(gè)體維數(shù)；M為族群數(shù)；N為族群內(nèi)青蛙個(gè)數(shù)。
Step2設(shè)置隸屬度閾值s0，并令初始補(bǔ)償系數(shù)m( k)為1，對(duì)每個(gè)青蛙個(gè)體計(jì)算適應(yīng)度f(wàn)( xi)，并按式(4)計(jì)算第k( k=1,2,…,M)個(gè)族群的第i( i=1,2,…,N )個(gè)青蛙x( k)i的模糊隸屬度s( k)i，將P個(gè)青蛙模糊分組到M個(gè)族群中。
Step3對(duì)族群k中f(xi)最差的個(gè)體x( k)w進(jìn)行局部搜索：
Step3.1按f( xi)降序排序，確定x( k)w、x( k)b、x( g)b及x( k)w對(duì)應(yīng)的s( k)w。
Step3.2根據(jù)擾動(dòng)策略2對(duì)x( k)w進(jìn)行更新，計(jì)算x( k)w,new。
Step4判斷各族群局部進(jìn)化次數(shù)是否達(dá)到T1，若未達(dá)到，轉(zhuǎn)至Step3。否則，判斷青蛙族群全局進(jìn)化次數(shù)是否達(dá)到T2或x( g)b是否達(dá)到收斂精度，若未達(dá)到，轉(zhuǎn)至Step2進(jìn)行全局信息交換，否則，算法停止，輸出x( g)b。
3.3 算法效率分析
FTCSFLA算法的改進(jìn)主要是在SFLA基礎(chǔ)上引入了模糊隸屬度、隸屬度閾值及補(bǔ)償系數(shù)，算法效率的改進(jìn)體現(xiàn)在以下3點(diǎn)：
(1)Step2中計(jì)算s( k)i并模糊分組，計(jì)算只在外層循環(huán)中增加T2×M×N次操作時(shí)間。
(2)Step3.1對(duì)每個(gè)族群按f( xi)降序排序，排序由原來(lái)的外層循環(huán)T2次改變?yōu)閮?nèi)層循環(huán)T1×M次。
(3)Step3.2中根據(jù)改進(jìn)的局部搜索策略更新x( k)w。增加了比較s( k)w≥s0和s( k)w＜s0的2T1次。
SFLA算法的時(shí)間復(fù)雜度是O( T1×T2×M×s+T2)，空間復(fù)雜度是O( M×N×s)。而FTCSFLA算法的時(shí)間復(fù)雜度是O( T1×T2×M×s+T2×M×N+T1×M+2T1)，空間復(fù)雜度是O( M×N×s+M×N +2)。由于T1＜＜T2，因此FTCSFLA與SFLA的效率是同數(shù)量級(jí)的，并未增加大的運(yùn)算開(kāi)銷和空間。
4 實(shí)驗(yàn)及結(jié)果分析
實(shí)驗(yàn)采用Sphere、Rastrigrin、Griewank和Ackley[11-12]4個(gè)測(cè)試函數(shù)作為青蛙個(gè)體適應(yīng)度，分別對(duì)SFLA和FTCSFLA算法進(jìn)行極小值尋優(yōu)性能測(cè)試，并對(duì)FTCSFLA算法的隸屬度閾值s0設(shè)置不同取值進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)參數(shù)設(shè)置如下：青蛙群體規(guī)模P=200，族群數(shù)M=20，族群內(nèi)青蛙個(gè)數(shù)N=10，各測(cè)試函數(shù)對(duì)應(yīng)青蛙個(gè)體維數(shù)s=30，T1=10，T2=500。設(shè)置s0=0.9和s0=0.5，分別對(duì)應(yīng)算法FTCSFLA0.9和FTCSFLA0.5。實(shí)驗(yàn)所用計(jì)算機(jī)處理器為Intel Core2，主頻為2.0 GHz，內(nèi)存為2.0 GB，測(cè)試平臺(tái)是VC++6.0。最終測(cè)試結(jié)果采用獨(dú)立運(yùn)行30次后的平均值。
算法性能評(píng)價(jià)采用如下方法：(1)固定全局進(jìn)化次數(shù)，評(píng)價(jià)算法收斂精度和速度；(2)固定收斂精度，評(píng)價(jià)算法達(dá)到該精度所需的全局進(jìn)化次數(shù)；(3)不同的隸屬度閾值對(duì)應(yīng)的FTCSFLA之間優(yōu)化性能比較。
4.1 固定全局進(jìn)化次數(shù)的收斂精度和速度分析
各算法收斂精度比較如表1所示，4個(gè)測(cè)試函數(shù)在固定全局進(jìn)化次數(shù)條件下函數(shù)平均最優(yōu)值進(jìn)化曲線比較如圖1～圖4所示，其中，fitness代表適應(yīng)度。
表1 固定全局進(jìn)化次數(shù)結(jié)果比較
圖1 Sph ere函數(shù)平均最優(yōu)值進(jìn)化曲線比較
圖2 R astrigrin函數(shù)平均最優(yōu)值進(jìn)化曲線比較
圖3 G riewank函數(shù)平均最優(yōu)值進(jìn)化曲線比較
圖 4 A ckley函數(shù)平均最優(yōu)值進(jìn)化曲線比較
可以看出，本文算法各項(xiàng)數(shù)值上均優(yōu)于SFLA，進(jìn)化曲線也表明其收斂速度均優(yōu)于SFLA。對(duì)單峰值Sphere函數(shù)，F(xiàn)TCSFLA0.9和FTCSFLA0.5均達(dá)到了理論極小值0，圖1顯示，F(xiàn)TCSFLA0.9進(jìn)化到184次時(shí)就達(dá)到了極小值，F(xiàn)TCSFLA0.5進(jìn)化到205次時(shí)也達(dá)到了極小值。由于這2個(gè)算法的收斂速度很快，因此在圖1中只顯示了達(dá)到極小值之前的進(jìn)化曲線，此后沒(méi)有再顯示進(jìn)化曲線表示算法已經(jīng)收斂為極小值。對(duì)多峰值Rastrigrin、Griewank和Ackley函數(shù)，因隸屬度閾值s0的調(diào)節(jié)，使得青蛙隸屬于不同族群的程度發(fā)生了變化，F(xiàn)TCSFLA0.9和FTCSFLA0.5的收斂精度有上下浮動(dòng)，從進(jìn)化曲線表明隸屬度閾值s0取值范圍在(0.5, 0.9]之間FTCSFLA收斂精度和收斂速度最為理想。
4.2 固定收斂精度的全局進(jìn)化次數(shù)分析
4個(gè)測(cè)試函數(shù)目標(biāo)精度和各函數(shù)達(dá)到目標(biāo)精度時(shí)的平均進(jìn)化次數(shù)見(jiàn)表2[11-12]。實(shí)驗(yàn)結(jié)果表明，F(xiàn)TCSFLA0.9達(dá)到目標(biāo)精度的次數(shù)明顯少于SFLA和FTCSFLA0.5。
表2 固定收斂精度結(jié)果比較
以上2個(gè)不同角度的對(duì)比結(jié)果表明，F(xiàn)TCSFLA0.9收斂精度、速度均優(yōu)于SFLA和FTCSFLA0.5，并且FTCSFLA在隸屬度閾值取值范圍在(0.5,0.9]之間時(shí)其收斂精度和速度為最優(yōu)。
5 結(jié)束語(yǔ)
本文提出一種基于模糊閾值補(bǔ)償?shù)幕旌贤芴惴?，引入模糊閾值補(bǔ)償思想，對(duì)青蛙模糊分組，在族群中定義了模糊隸屬度、隸屬度閾值和補(bǔ)償系數(shù)等概念。在局部搜索中，設(shè)置隸屬度閾值，根據(jù)模糊隸屬度和隸屬度閾值關(guān)系，給出了2種最差個(gè)體的更新方法，并設(shè)置補(bǔ)償系數(shù)統(tǒng)一表達(dá)了2種更新方法。該算法以動(dòng)態(tài)模糊的方式調(diào)整最差個(gè)體的更新程度，避免了局部早熟。實(shí)驗(yàn)結(jié)果表明，該算法在單峰值和多峰值函數(shù)尋優(yōu)問(wèn)題上均具有較高的收斂速度和精度，改進(jìn)了SFLA的優(yōu)化性能。未來(lái)將進(jìn)一步研究動(dòng)態(tài)隸屬度閾值對(duì)算法性能的影響。
[1] Eusuff M M, Lansey K E. O ptimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm[J]. Journal of Water Sourc es Planning an d M anagement, 2003, 129(3): 210-225.
[2] Eusuff M M, Lansey K E, Pasha F. Shuffled Frog Leaping Algorithm: A Memetic Meta-heuristic for Discrete O ptimization[J]. Engineering Optimization, 2006, 38(2): 129-154.
[3] 李英海, 周建中, 楊俊杰, 等. 一種基于閾值選擇策略的改進(jìn)混合蛙跳算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2 007, 43(35): 19-21.
[4] 歐 陽(yáng), 孫元姝. 基于改進(jìn)混合蛙跳算法的網(wǎng)格任務(wù)調(diào)度策略[J]. 計(jì)算機(jī)工程, 2011, 37(21): 146-148.
[5] 代永強(qiáng), 王聯(lián)國(guó). 帶記憶功能的混合蛙跳算法[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2011, 32(9): 3170-3173.
[6] L in Chunfu, Wang Shengde. Fuzzy Support Vector Machines[J]. IEEE Transcations on Neural Networks, 2002, 13(2): 464-471.
[7] Huang Hanpang, Liu Y H. Fuzzy Support Vector Machines for Pattern Recognition and Data Mining[J]. International Journal of Fuzzy Systems, 2002, 4(3): 826-835.
[8] 葛 宇, 王學(xué)平, 梁 靜. 改進(jìn)的混合蛙跳算法[J]. 計(jì)算機(jī)應(yīng)用, 2012, 32(1): 234-237.
[9] 趙小強(qiáng), 劉悅婷. 基于選擇和變異機(jī)制的蛙跳FCM算法[J].計(jì)算機(jī)應(yīng)用研究, 2012, 29(6): 2068-2071.
[10] 王 輝. 一種帶共享因子的人工蜂群算法[J]. 計(jì)算機(jī)工程, 2011, 37(22): 139-142.
[11] 王 凌. 智能優(yōu)化算法及其應(yīng)用[M]. 北京: 清華大學(xué)出版社, 2001.
[12] Engelbrecht A P. F undamentals of Computational Swarm Intelligence[M]. 譚 營(yíng), 譯. 北京: 清華大學(xué)出版社, 2009.
編輯 金胡考
Shuffled Frog Leaping Algorithm Based on Fuzzy Threshold Compensation
LIU Li-qun1, WANG Lian-guo1, HUO Jiu-yuan2, HAN Jun-ying1, LIU Cheng-zhong1
(1. College of Information Science and Technology, Gansu Agricultural University, Lanzhou 730070, China; 2. School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)
To solve the problem of slow convergence speed and low optimization precision of Shuffled Frog Leaping Algorithm (SFLA) in solving complex problems, a Shuffled Frog Leaping Algorithm Based on Fuzzy Threshold Compensation(FTCSFLA) is proposed. The fuzzy grouping idea is introduced to divide different frogs into fuzzy groups, and disturbance strategy in a local search is improved based on the basic SFLA. Each fuzzy group is defined with a total membership threshold and a total compensation coefficient, and each frog is defined with a fuzzy membership, which is scaled with the distribution degree of neighborhood frogs. In a local search, the worst individual is updated by two methods in each group, which is partitioned ac cording to the relation between fuzzy membership and membership threshold. In t wo methods, a com pensation coefficient is set to gi ve a u nify expression. Experimental results show th at the con vergence precision and speed of FTCSFLA which membership threshold is 0.9 is better than SFLA and FTCSFLA which membership threshold is 0.5. The evolution curve shows that the convergence precision and speed of FTCSFLA is the optimum when its membership threshold is between (0.5, 0.9].
Shuffled Frog Leaping Algorithm(SFLA); fuzzy membership; membership threshold; compensation coef ficient; fuzzy grouping; disturbance strategy; optimization performance
10.3969/j.issn.1000-3428.2014.05.035
國(guó)家自然科學(xué)基金資助項(xiàng)目(61063028)；中國(guó)博士后科學(xué)基金資助項(xiàng)目(2013M542398)；甘肅省高等學(xué)校研究生導(dǎo)師科研基金資助項(xiàng)目(1202-04, 1 102-05)；甘肅省教育廳信息化戰(zhàn)略研究基金資助項(xiàng)目(2011-02)；甘肅省自然科學(xué)研究計(jì)劃基金資助項(xiàng)目(1308RJZA214, 1208RJZA133)；甘肅農(nóng)業(yè)大學(xué)盛彤笙科技創(chuàng)新基金資助項(xiàng)目(GSAU-STS-1322)；蘭州交通大學(xué)青年科學(xué)基金資助項(xiàng)目(2013032)。
劉立群(1982－)，女，講師、碩士，主研方向：群體智能算法，數(shù)據(jù)庫(kù)技術(shù)；王聯(lián)國(guó)，教授、博士；火久元，副教授、博士；韓俊英，副教授、碩士；劉成忠，副教授、博士研究生。
2013-03-04
2013-05-27E-mail：llqhjy@126.com
1000-3428(2014)05-0168-05
A
TP18
猜你喜歡
數(shù)學(xué)物理學(xué)報(bào)(2022年4期)2022-08-22 04:07:12
體育教學(xué)(2022年4期)2022-05-05 21:26:58
數(shù)學(xué)物理學(xué)報(bào)(2022年2期)2022-04-26 14:08:04
英美文學(xué)研究論叢(2021年2期)2021-02-16 00:37:30
時(shí)代郵刊(2019年24期)2019-12-17 11:49:30
知識(shí)經(jīng)濟(jì)·中國(guó)直銷(2018年9期)2018-09-28 03:15:26
金橋(2018年4期)2018-09-26 02:24:54
東北史地(學(xué)問(wèn))(2017年1期)2017-06-15 20:27:19
娃娃畫(huà)報(bào)(2016年5期)2016-08-03 19:25:40
中國(guó)衛(wèi)生(2014年5期)2014-11-10 02:11:26
