基于模糊閾值補償的混合蛙跳算法

劉立群，王聯國，火久元，韓俊英，劉成忠

(1. 甘肅農業大學信息科學技術學院，蘭州 730 070；2. 蘭州交通大學電子與信息工程學院，蘭州 73007 0)

基于模糊閾值補償的混合蛙跳算法

劉立群1，王聯國1，火久元2，韓俊英1，劉成忠1

(1. 甘肅農業大學信息科學技術學院，蘭州 730 070；2. 蘭州交通大學電子與信息工程學院，蘭州 73007 0)

針對混合蛙跳算法(SFLA)求解復雜問題時收斂速度慢、優化精度低的缺點，提出一種基于模糊閾值補償的混合蛙跳算法(FTCSFLA)。在SFLA的基礎上，采用模糊分組方法對青蛙分組并改進局部搜索的擾動策略。在族群中定義模糊隸屬度、隸屬度閾值和補償系數，利用鄰域青蛙之間的分布程度衡量某一青蛙的模糊隸屬度。在一次局部搜索中，對族群最差個體按模糊隸屬度和隸屬度閾值關系給出2種更新方法，設置相應的補償系數。實驗結果表明，隸屬度閾值為0.9的FTCSFLA其收斂精度、速度均優于SFLA和隸屬度閾值為0.5的FTCSFLA，當隸屬度閾值取值在(0.5,0.9]之間時，FTCSFLA的性能達到最優。

混合蛙跳算法；模糊隸屬度；隸屬度閾值；補償系數；模糊分組；擾動策略；優化性能

1 概述

混合蛙跳算法(Shuffled Frog Leaping Algorithm, SFLA)是模擬青蛙覓食過程中信息共享和交流特點提出的群體智能算法[1-2]，已經成功應用于許多領域。近年來學者們對SFLA優化性能做了諸多改進：文獻[3]引入閾值選擇策略，通過對不滿足閾值條件的個體分量不予更新的策略減小了個體空間差異。文獻[4]引入遺傳算子增加對局部極值的擾動并借鑒粒子群優化算法中粒子飛行經驗對青蛙移動策略進行優化。但是SFLA對于求解復雜問題依然存在收斂速度慢、優化精度低的缺點。這主要是由SFLA的分組方式以及局部更新策略引起的。首先，SFLA在局部搜索前，各青蛙是被逐一循環分配給各個族群的。這種循環分配存在固定性，全局最優個體所在分組更新后得到新的全局最優個體的次數最多，導致該分組尋優能力強于其他分組，一旦該分組陷入局部最優，則整個群體很難跳出局部極值[5]，容易陷入早熟。其次，在局部搜索中，最差個體通過與最優個體的差異進行更新，而這種更新存在隨機性，缺乏一定的尋優指導性。這些因素很大程度上影響了SFLA的收斂速度和優化精度。

文獻[6-7]將模糊理論引入支持向量機(Support Vector Machine, SVM)中，通過對每個輸入樣本增加一個模糊隸屬度，對含有噪聲或野值的樣本賦予較小權值，有效提高了SVM分類準確率及計算效率。目前，已有學者將模糊理論與SFLA結合研究：文獻[8]在SFLA基礎上利用模糊控制器的模糊語言變量及控制規則得出模糊控制表，改進后算法在尋優精度、收斂速度上均有大幅提高；文獻[9]將SFLA應用于模糊C均值算法，克服了算法易陷入局部極小的缺陷，提高了算法尋優能力。

為克服SFLA固定循環分配方式容易引起早熟現象的缺陷，并改善局部搜索中的隨機性更新，本文將模糊分類思想[6-7]引入SFLA，并借鑒文獻[3]固定閾值選擇思想，在族群中定義模糊隸屬度，設置隸屬度閾值對最差個體更新進行適度控制，提出一種新的基于模糊閾值補償的混合蛙跳算法(Shuffled Fro g L eaping Algorithm Based on Fu zzy Threshold Compensation, FTCSFLA)。

2 SFLA算法

隨機生成P=N×M只青蛙組成的初始群體，第i只青蛙個體記為xi=(xi1,xi2,…,xis)，其中，s為個體維數；M為族群數；N為族群內青蛙個數。對每個青蛙個體計算適應度f(xi)，并按f(xi)降序排序，再逐一循環分配給M個族群。對每個族群中f( xi)最差的個體x( k)w按式(1)進行局部搜索：

在式(1)～式(3)中，x( k)w,new和x( k)w,old分別表示族群k中最差個體更新的新舊值；x( k)b表示族群k中局部最優個體；x( g)b表示青蛙群體的全局最優個體；xnew表示定義域內隨機產生的一個新個體。對各族群重復局部搜索，直至族群k的局部進化次數T1為止，將所有族群的P個青蛙個體重新混合進行全局信息交換，并按適應度重新排序和劃分族群，再對各族群局部迭代，如此反復迭代直至滿足問題終止條件或達到全局進化次數T2為止。

3 FTCSFLA算法

3.1 模糊閾值補償的思想

SFLA局部搜索前的循環分配方式會導致全局最優個體所在分組尋優能力強于其他分組，易使算法陷入早熟。此外，在一次局部搜索中，式(1)、式(2)中最優個體對最差個體的差異擾動rand(0,1)是[0,1]間隨機數[10]，存在很大的隨機性，沒有體現出更好的尋優指導性。針對以上缺陷，本文引入模糊閾值補償思想，對每個青蛙進行模糊分組，在各分組族群中定義模糊隸屬度，設置隸屬度閾值，并對局部搜索中最差個體的更新設置補償系數。以動態模糊的方式調整最差個體的更新程度，以避免局部早熟，達到全局最優。

3.1.1 模糊隸屬度

定義1(模糊隸屬度) 每個青蛙i(i=1,2,…,N)屬于某族群k(k=1,2,…,M)的模糊隸屬度記為s(k)i,0＜s(k)i＜1。在一次局部搜索中，每個族群k中f(xi)最差個體x(k)w對應的模糊隸屬度記為s(k)w。其中，s(k)i表示第i個青蛙隸屬于第k個族群的程度。隸屬度越大，它隸屬于族群k的可能性越大。因此，族群k是由s(k)i大于某個值的多個青蛙組成的。

3.1.2 模糊隸屬度的確定

在生成的P=N×M個青蛙初始群體中，對第k(k= 1,2,…,M)個族群隨機選擇N個青蛙作為鄰域青蛙，利用鄰域青蛙之間的分布程度衡量某一青蛙的模糊隸屬度，并采用歐氏距離度量兩青蛙間距離。則鄰域青蛙內第i(i= 1,2,…,N)個青蛙x(k)i的模糊隸屬度通過下式確定：

3.1.3 隸屬度閾值

定義2(隸屬度閾值) 某青蛙i隸屬于某族群k的隸屬程度由其s(k)i是否大于某一隸屬度閾值表示，該隸屬度閾值記為s0,0＜s0＜1。

如果s( k)i≥s0，表示青蛙i隸屬于族群k的程度大，認為青蛙i隸屬于族群k。否則，表示隸屬于族群k的程度小，認為青蛙i不隸屬于族群k。

在一次局部搜索中，對族群k定義如下：

如果按式(6)更新仍無法提高尋優指導性，則使用式(7)進行局部搜索：

擾動策略1如果青蛙i隸屬于某族群k，即s( k)i≥s0，則該族群最差個體x( k)w按式(6)局部最優個體x( k)b進行差異擾動。否則，按式(7)全局最優個體x( g)b進行差異擾動。

證明：如果s( k)i≥s0，也即s( k)w≥s0時，說明最差個體x( k)w隸屬于族群k，因此，使用式(6)局部最優個體x( k)b進行差異擾動體現了局部尋優指導能力。下面分2種情況證明擾動策略1后半部分：第1種情況：如果s( k)i＜s0，也即s( k)w＜s0時，那么最差個體x( k)w不屬于族群k，局部最優個體x( k)b已無法提高尋優性能，使用式(7)全局最優個體x( g)b進行差異擾動體現了全局尋優指導能力。式(7)中1-s( k)w表示不屬于族群k的最差個體對應的模糊隸屬度。第2種情況：如果s( k)i≥s0，也即s( k)w≥s0時，若按式(6)對x( k)w更新后，如果仍有f( x( k)w,new)≥f( x( k)w,old)，說明式(6)用局部最優個體進行差異擾動無法找到最優值，因此，應按第1種情況最差個體x( k)w不隸屬于族群k對待。證畢。

擾動策略1利用模糊隸屬度及隸屬度閾值之間關系對青蛙群體模糊分組，克服了SFLA固定循環分配方式易引起早熟的缺陷；同時，在一次局部搜索中，分別利用局部最優個體x( k)b、全局最優個體x( g)b對x( k)w的尋優進行指導，避免了式(1)、式(2)隨機性更新的缺陷。

3.1.4 補償系數

定義3(補償系數) 為統一表示式(6)、式(7)最優個體對最差個體的尋優指導能力，對每個族群k定義補償系數，記為m( k),m( k)∈{0,1}。

其中，1-m( k)表示使用局部最優個體差異擾動仍無法達到最優時，全局最優個體對差異擾動的尋優補償能力。

綜上，在一次局部搜索中，FTCSFLA將按擾動策略2進行最差個體更新。

3.2 算法步驟

FTCSFLA是引入模糊隸屬度、隸屬度閾值及補償系數等概念，并將模糊閾值補償的思想應用于SFLA，算法的具體步驟如下：

Step1隨機生成P=N×M只青蛙的初始群體，記為XP={xi|xi=(xi1,xi2,…,xis),i=1,2,…,P}，其中，s為個體維數；M為族群數；N為族群內青蛙個數。

Step2設置隸屬度閾值s0，并令初始補償系數m( k)為1，對每個青蛙個體計算適應度f( xi)，并按式(4)計算第k( k=1,2,…,M)個族群的第i( i=1,2,…,N )個青蛙x( k)i的模糊隸屬度s( k)i，將P個青蛙模糊分組到M個族群中。

Step3對族群k中f(xi)最差的個體x( k)w進行局部搜索：

Step3.1按f( xi)降序排序，確定x( k)w、x( k)b、x( g)b及x( k)w對應的s( k)w。

Step3.2根據擾動策略2對x( k)w進行更新，計算x( k)w,new。

Step4判斷各族群局部進化次數是否達到T1，若未達到，轉至Step3。否則，判斷青蛙族群全局進化次數是否達到T2或x( g)b是否達到收斂精度，若未達到，轉至Step2進行全局信息交換，否則，算法停止，輸出x( g)b。

3.3 算法效率分析

FTCSFLA算法的改進主要是在SFLA基礎上引入了模糊隸屬度、隸屬度閾值及補償系數，算法效率的改進體現在以下3點：

(1)Step2中計算s( k)i并模糊分組，計算只在外層循環中增加T2×M×N次操作時間。

(2)Step3.1對每個族群按f( xi)降序排序，排序由原來的外層循環T2次改變為內層循環T1×M次。

(3)Step3.2中根據改進的局部搜索策略更新x( k)w。增加了比較s( k)w≥s0和s( k)w＜s0的2T1次。

SFLA算法的時間復雜度是O( T1×T2×M×s+T2)，空間復雜度是O( M×N×s)。而FTCSFLA算法的時間復雜度是O( T1×T2×M×s+T2×M×N+T1×M+2T1)，空間復雜度是O( M×N×s+M×N +2)。由于T1＜＜T2，因此FTCSFLA與SFLA的效率是同數量級的，并未增加大的運算開銷和空間。

4 實驗及結果分析

實驗采用Sphere、Rastrigrin、Griewank和Ackley[11-12]4個測試函數作為青蛙個體適應度，分別對SFLA和FTCSFLA算法進行極小值尋優性能測試，并對FTCSFLA算法的隸屬度閾值s0設置不同取值進行對比實驗。實驗參數設置如下：青蛙群體規模P=200，族群數M=20，族群內青蛙個數N=10，各測試函數對應青蛙個體維數s=30，T1=10，T2=500。設置s0=0.9和s0=0.5，分別對應算法FTCSFLA0.9和FTCSFLA0.5。實驗所用計算機處理器為Intel Core2，主頻為2.0 GHz，內存為2.0 GB，測試平臺是VC++6.0。最終測試結果采用獨立運行30次后的平均值。

算法性能評價采用如下方法：(1)固定全局進化次數，評價算法收斂精度和速度；(2)固定收斂精度，評價算法達到該精度所需的全局進化次數；(3)不同的隸屬度閾值對應的FTCSFLA之間優化性能比較。

4.1 固定全局進化次數的收斂精度和速度分析

各算法收斂精度比較如表1所示，4個測試函數在固定全局進化次數條件下函數平均最優值進化曲線比較如圖1～圖4所示，其中，fitness代表適應度。

表1 固定全局進化次數結果比較

圖1 Sph ere函數平均最優值進化曲線比較

圖2 R astrigrin函數平均最優值進化曲線比較

圖3 G riewank函數平均最優值進化曲線比較

圖 4 A ckley函數平均最優值進化曲線比較

可以看出，本文算法各項數值上均優于SFLA，進化曲線也表明其收斂速度均優于SFLA。對單峰值Sphere函數，FTCSFLA0.9和FTCSFLA0.5均達到了理論極小值0，圖1顯示，FTCSFLA0.9進化到184次時就達到了極小值，FTCSFLA0.5進化到205次時也達到了極小值。由于這2個算法的收斂速度很快，因此在圖1中只顯示了達到極小值之前的進化曲線，此后沒有再顯示進化曲線表示算法已經收斂為極小值。對多峰值Rastrigrin、Griewank和Ackley函數，因隸屬度閾值s0的調節，使得青蛙隸屬于不同族群的程度發生了變化，FTCSFLA0.9和FTCSFLA0.5的收斂精度有上下浮動，從進化曲線表明隸屬度閾值s0取值范圍在(0.5, 0.9]之間FTCSFLA收斂精度和收斂速度最為理想。

4.2 固定收斂精度的全局進化次數分析

4個測試函數目標精度和各函數達到目標精度時的平均進化次數見表2[11-12]。實驗結果表明，FTCSFLA0.9達到目標精度的次數明顯少于SFLA和FTCSFLA0.5。

表2 固定收斂精度結果比較

以上2個不同角度的對比結果表明，FTCSFLA0.9收斂精度、速度均優于SFLA和FTCSFLA0.5，并且FTCSFLA在隸屬度閾值取值范圍在(0.5,0.9]之間時其收斂精度和速度為最優。

5 結束語

本文提出一種基于模糊閾值補償的混合蛙跳算法，引入模糊閾值補償思想，對青蛙模糊分組，在族群中定義了模糊隸屬度、隸屬度閾值和補償系數等概念。在局部搜索中，設置隸屬度閾值，根據模糊隸屬度和隸屬度閾值關系，給出了2種最差個體的更新方法，并設置補償系數統一表達了2種更新方法。該算法以動態模糊的方式調整最差個體的更新程度，避免了局部早熟。實驗結果表明，該算法在單峰值和多峰值函數尋優問題上均具有較高的收斂速度和精度，改進了SFLA的優化性能。未來將進一步研究動態隸屬度閾值對算法性能的影響。

[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]. 計算機工程與應用, 2 007, 43(35): 19-21.

[4] 歐 陽, 孫元姝. 基于改進混合蛙跳算法的網格任務調度策略[J]. 計算機工程, 2011, 37(21): 146-148.

[5] 代永強, 王聯國. 帶記憶功能的混合蛙跳算法[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] 葛 宇, 王學平, 梁 靜. 改進的混合蛙跳算法[J]. 計算機應用, 2012, 32(1): 234-237.

[9] 趙小強, 劉悅婷. 基于選擇和變異機制的蛙跳FCM算法[J].計算機應用研究, 2012, 29(6): 2068-2071.

[10] 王 輝. 一種帶共享因子的人工蜂群算法[J]. 計算機工程, 2011, 37(22): 139-142.

[11] 王 凌. 智能優化算法及其應用[M]. 北京: 清華大學出版社, 2001.

[12] Engelbrecht A P. F undamentals of Computational Swarm Intelligence[M]. 譚 營, 譯. 北京: 清華大學出版社, 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

國家自然科學基金資助項目(61063028)；中國博士后科學基金資助項目(2013M542398)；甘肅省高等學校研究生導師科研基金資助項目(1202-04, 1 102-05)；甘肅省教育廳信息化戰略研究基金資助項目(2011-02)；甘肅省自然科學研究計劃基金資助項目(1308RJZA214, 1208RJZA133)；甘肅農業大學盛彤笙科技創新基金資助項目(GSAU-STS-1322)；蘭州交通大學青年科學基金資助項目(2013032)。

劉立群(1982－)，女，講師、碩士，主研方向：群體智能算法，數據庫技術；王聯國，教授、博士；火久元，副教授、博士；韓俊英，副教授、碩士；劉成忠，副教授、博士研究生。

2013-03-04

2013-05-27E-mail：llqhjy@126.com

1000-3428(2014)05-0168-05

A

TP18