王俊徐建中徐雷

基于討論機(jī)制的混合蛙跳算法?

王俊徐建中徐雷

（南京理工大學(xué)南京210094）

針對(duì)混合蛙跳算法易陷入局部最優(yōu)的情況，提出一種基于討論機(jī)制的混合蛙跳算法。改進(jìn)算法在原混合蛙跳算法基礎(chǔ)上加入了討論機(jī)制，并根據(jù)迭代次數(shù)動(dòng)態(tài)調(diào)整討論次數(shù)，增加算法后期變異性，避免陷入局部最優(yōu)。論文選擇了3個(gè)常用的測(cè)試函數(shù)進(jìn)行測(cè)試，與基本蛙跳算法比較，在計(jì)算精度和求解成功率上均有很大的提高。

混合蛙跳算法；討論機(jī)制；動(dòng)態(tài)調(diào)整；計(jì)算精度；成功率

Class NumberTP301.6

1引言

混合蛙跳算法（Shuffled Frog Leaping Algo?rithm）是一種高效的智能算法，由于算法的簡(jiǎn)單、易實(shí)現(xiàn)等特點(diǎn)而被廣泛使用。為了提高算法的性能，國(guó)外［1～11］和國(guó)內(nèi)學(xué)者［12～18］做了很多研究。Hu等［10］在基礎(chǔ)的混合蛙跳算法中加入了記憶因子，通過(guò)因子的自適應(yīng)變化，提高了算法的成功率。Wang等［11］在基礎(chǔ)混合蛙跳算法中，加入了一種自適應(yīng)模糊變異策略，有效地提高了算法的精度。張等［12］將模擬退火和免疫接種思想引入到混合蛙跳算法中，有效地克服了局部極值，提高了算法的收斂速度和準(zhǔn)確度。劉等［13］引入共享因子的思想，將其分為全局共享因子和局部共享因子，該算法在單峰值和多峰值函數(shù)優(yōu)化問(wèn)題上具有較高的收斂速度和精度。本文不修改原算法的內(nèi)部搜索策略，而是增加了一個(gè)討論機(jī)制，在內(nèi)部更新完之后，每隔一定代數(shù)就進(jìn)行一次討論，并且隨著代數(shù)增加，逐漸增加討論頻率。仿真結(jié)果表明，本文算法在求解精度和正確率方面都取得較好效果，有效地提升了算法的性能。

2混合蛙跳算法

混合蛙跳算法是受自然界中青蛙覓食啟發(fā)而產(chǎn)生的進(jìn)化算法。其思想是：一組青蛙分組去尋找食物，每組都有自己的文化，每個(gè)青蛙都往離食物近的青蛙移動(dòng)，并且互相交流，按照這個(gè)思想每組執(zhí)行局部搜索，當(dāng)執(zhí)行一段時(shí)間局部搜索后各組會(huì)進(jìn)行交流，持續(xù)這個(gè)過(guò)程直到條件滿(mǎn)足為止，混合蛙跳算法主要包括三個(gè)過(guò)程：子群劃分，內(nèi)部搜索和全局交換。

1）子群劃分

設(shè)種群內(nèi)有N個(gè)個(gè)體，將其分成k組，每組的個(gè)體數(shù)為N/k，用Xi=(xi1，xi2，…，xiD)表示第i個(gè)個(gè)體，D表示個(gè)體的維數(shù)。對(duì)于初始種群S=(X1，X2，…，XN)，按適應(yīng)度升序排列后，將第一個(gè)個(gè)體放入第一個(gè)子群，第二個(gè)個(gè)體放入第二個(gè)子群，…，第k個(gè)放入k組，第k+1，k+2，等依次放入第一組，第二組。依次重復(fù)直到所有個(gè)體都被分入組中。

2）子群內(nèi)部搜索

設(shè)Xb為每組中適應(yīng)度最好的個(gè)體，Xw為每組中適應(yīng)度最差的個(gè)體，Xg為所有個(gè)體中適應(yīng)度最好的個(gè)體。對(duì)每組進(jìn)行內(nèi)部搜索，即更新最差個(gè)體，更新公式如式（1）所示

其中，Xw′為產(chǎn)生的新的個(gè)體，r是隨機(jī)數(shù)，取值為0～1，如果新產(chǎn)生的個(gè)體比原來(lái)的Xw好，就替代原來(lái)的個(gè)體。如果適應(yīng)度上沒(méi)有改進(jìn)則采用式（2）進(jìn)行更新。

如果新個(gè)體適應(yīng)度上還是沒(méi)有改進(jìn)就隨機(jī)產(chǎn)生一個(gè)個(gè)體替換Xw。

3）全局信息交換

當(dāng)所有子群更新完成之后，重新進(jìn)行子群劃分。并進(jìn)行內(nèi)部搜索，反復(fù)執(zhí)行此過(guò)程直到滿(mǎn)足終止條件或者達(dá)到進(jìn)化代數(shù)為止。

3算法改進(jìn)

3.1討論機(jī)制

混合蛙跳算法由于后期變異性差，因此很容易陷入局部最優(yōu)情況。本文在每進(jìn)化m代后，在原有的組內(nèi)搜索結(jié)束后進(jìn)行討論。

其中，G EN為總進(jìn)化代數(shù)，igen為當(dāng)前進(jìn)化代數(shù)，mb和mt是兩個(gè)常量，實(shí)驗(yàn)中取值為1和7，可以看出，隨著進(jìn)化代數(shù)的增加m逐漸減小，以此來(lái)增加算法后期的變異性，避免陷入局部最優(yōu)，具體為

1）隨機(jī)選擇一個(gè)組，并將組中最優(yōu)個(gè)體加上一個(gè)隨機(jī)變化生成新個(gè)體：

2）隨機(jī)選擇一個(gè)組，并隨機(jī)選擇一個(gè)個(gè)體加上隨機(jī)變化生成新個(gè)體：

3）隨機(jī)選擇一個(gè)組，并隨機(jī)選擇兩個(gè)個(gè)體融合產(chǎn)生新個(gè)體。

其中n(μ，σ)為高斯函數(shù)，μ為均值，σ為方差，實(shí)驗(yàn)中取值0和1，ξ為步長(zhǎng)，其取值計(jì)算公式為

其中，κ控制函數(shù)坡度，實(shí)驗(yàn)中取值為25，通過(guò)p1，p2來(lái)確定選擇哪種方案，具體為：隨機(jī)產(chǎn)生一個(gè)0～1之間的數(shù)τ1，當(dāng)τ1＜p1選擇方案1，當(dāng)τ1＞p1再產(chǎn)生一個(gè)隨機(jī)數(shù)τ2，當(dāng)τ2＜p2選擇方案2，當(dāng)τ2＞p2選擇方案3。將新產(chǎn)生的個(gè)體與組內(nèi)最差個(gè)體比較，如果優(yōu)于組內(nèi)最差個(gè)體比較，則替換。

3.2改進(jìn)后的算法流程

設(shè)種群內(nèi)有N個(gè)個(gè)體，將其分成k組，每組的最大內(nèi)部搜索次數(shù)為P，最大進(jìn)化代數(shù)為GEN，適應(yīng)度函數(shù)為f（x）。本文提出的基于討論機(jī)制的混合蛙跳算法流程表示為

4仿真實(shí)驗(yàn)

4.1實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證算法的性能，將本文算法（Discussion Mechanism Based Shuffled Frog Leaping Algorithm，DMSFLA）與基本的混合蛙跳算法（SFLA），張等改進(jìn)算法（Improved Shuffled Frog Leaping Algorithm，ISFLA）做對(duì)比，選擇三個(gè)典型的函數(shù)進(jìn)行測(cè)試。分別為

1）Sphere函數(shù)

2）Rastrigin函數(shù)

3）Ackley函數(shù)

實(shí)驗(yàn)參數(shù)設(shè)置為：GEN=400，種群個(gè)數(shù)N=100，分組數(shù)k=10，子群內(nèi)部搜索次數(shù)P=10。P1=P2= 0.5。實(shí)驗(yàn)從算法求解精度和算法求解成功率進(jìn)行對(duì)比。

4.2實(shí)驗(yàn)結(jié)果及分析

1）算法求解精度對(duì)比

針對(duì)每一函數(shù)獨(dú)立進(jìn)行100次實(shí)驗(yàn)，表1～3分別給出了實(shí)驗(yàn)結(jié)果。

表1 Sphere函數(shù)在不同維數(shù)下的平均適應(yīng)度

表2 Rastrigin函數(shù)在不同維數(shù)下的平均適應(yīng)度

從表1～3可以看出，DMSFLA在Sphere函數(shù)中有較好的表現(xiàn)，隨著維數(shù)的增加，DMSFLA求得平均最優(yōu)適應(yīng)度都比另外兩種算法小，特別是相對(duì)基本SFLA算法有較高的求解精度。在Rastrigin函數(shù)的測(cè)試中，在維數(shù)為5～20之間，有較好的表現(xiàn)。在Ackley函數(shù)中在維數(shù)為5和10時(shí)，相對(duì)于SFLA也有明顯的提升。

2）算法求解成功率對(duì)比

指定各個(gè)函數(shù)的收斂精度如表4所示，函數(shù)的維數(shù)取30，每個(gè)算法獨(dú)立100次后結(jié)果如表5所示。

表4 函數(shù)收斂精度

表5 100次實(shí)驗(yàn)結(jié)果

從表5的結(jié)果可以看出，對(duì)于3個(gè)測(cè)試函數(shù)，在指定的精度下DMSFLA都能達(dá)到較好的成功率。綜上分析，本文提出的基于討論機(jī)制的混合蛙跳算法在算法求解精度，成功率方面都有一定的提升，獲得了較滿(mǎn)意的結(jié)果。

5結(jié)語(yǔ)

本文對(duì)基本的混合蛙跳算法做了一定的改進(jìn)，通過(guò)增加討論機(jī)制，提高了算法后期的搜索能力，避免過(guò)早陷入局部最優(yōu)。實(shí)驗(yàn)對(duì)3個(gè)典型函數(shù)進(jìn)行測(cè)試，結(jié)果表明，本文提出的改進(jìn)算法有效提高了算法求解精度和準(zhǔn)確率，增強(qiáng)了算法的尋優(yōu)性能。但是，在Rastrigin函數(shù)和Ackley函數(shù)的30維數(shù)測(cè)試中，一定程度上還是會(huì)陷入局部最優(yōu)的情況，沒(méi)有達(dá)到顯著的提升，仍有改進(jìn)的空間。未來(lái)，將繼續(xù)提高算法在高維數(shù)的優(yōu)化能力。

［1］J.Zhou，E.Dutkiewicz，R.P.Liu，X.Huang，G.Fang and Y.Liu.A Modified Shuffled Frog Leaping Algorithm for PAPR Reduction in OFDM Systems［J］.in IEEE Transac?tions on Broadcasting，2015，61（4）：698-709.

［2］A.Asrari，T.Wu，S.Lotfifard.The Impacts of Distributed Energy Sources on Distribution Network Reconfiguration［J］.in IEEE Transactions on Energy Conversion，2016，31（2）：606-613.

［3］Y.Chen，J.Wen，L.Jiang，S.Cheng.Hybrid algorithm for dynamic economic dispatch with valve-pointeffects［J］.in IET Generation，Transmission&Distribution，2013，7（10）：1096-1104.

［4］M.A.Bahar，M.Shokooh-Saremi.Design of GMR-based narrow bandpass filters using improved shuffled frog leap?ing algorithm［J］.in Electronics Letters，2015，51（6）：497-499.

［5］H.M.Hasanien.Shuffled frog leaping algorithm-based static synchronous compensator for transient stability im?provement of a grid-connected wind farm［J］.in IET Re?newable Power Generation，2014，8（6）：722-730.

［6］W.Ding，J.Wang，Z.Guan，Q.Shi.Enhanced minimum attribute reduction based on quantum-inspired shuffled frog leaping algorithm［J］.in Journal of Systems Engineer?ing and Electronics，2013，24（3）：426-434.

［7］H.Huang，M.Pan，S.Gong.Estimating and calibrating the response of multiple wideband digital radio frequency memories in a hardware-in-the-loop system using shuf?fled frog leaping algorithm［J］.in IET Radar，Sonar& Navigation，2016，10（5）：827-833.

［8］M.Barati，M.M.Farsangi.Solving unitcommitment prob?lem by a binary shuffled frog leaping algorithm［J］.in IET Generation，Transmission&Distribution，2014，8（6）：1050-1060.

［9］H.M.Hasanien.Shuffled Frog Leaping Algorithm for Pho?tovoltaic Model Identification［J］.in IEEE Transactions on Sustainable Energy，2015，6（2）：509-515.

［10］B.Hu，Y.Dai，Y.Su.Feature Selection for Optimized High-dimensional Biomedical Data using the Improved Shuffled Frog Leaping Algorithm［J］.in IEEE/ACM Transactions on Computational Biology and Bioinformat?ics，2014，3（99）：1-1.

［11］F.Wang，C.Geng，L.Su.Parameter identification and prediction of Jiles-Atherton model for DC-biased trans?former using improved shuffled frog leaping algorithm and leastsquare supportvector machine［J］.in IET Elec?tric Power Applications，2015，9（9）：660-669.

［12］張瀟丹，趙力，鄒采榮.一種改進(jìn)的混合蛙跳算法求解有約束優(yōu)化問(wèn)題［J］.山東大學(xué)學(xué)報(bào)（工學(xué)版），2013，43（1）：1-8.

ZHANG Xiaodan，ZHAO Li，ZHOU Cairong.An im?proved shuffled frog leaping algorithm for solving con?strained optimization problems［J］.Journal of Shandong University（Engineering Science），2013，43（1）：1-8.

［13］劉立群，王聯(lián)國(guó)，韓俊英.基于全局共享因子的混合蛙跳算法［J］.計(jì)算機(jī)工程，2013（10）：162-166.

LIU Liuqun，WANG Lianguo，HAN Junying.Shuffled Frog Leaping Algorithm Based on Global Sharing Factor［J］.Computer Engineering，2013（10）：162-166.

［14］張沈習(xí)，陳楷，龍禹.基于混合蛙跳算法的分布式風(fēng)電源規(guī)劃［J］.電力系統(tǒng)自動(dòng)化，2013，37（13）：76-82.

ZHANG Shenxi，CHEN Kai，LONG Yu.shuffled frog leaping algorithm based distributed wind power planning［J］.Automation of Electric Power Systems，2013，37（13）：76-82.

［15］馬平莉.混合蛙跳算法研究［D］.西安：西安電子科技大學(xué)，2013.

MA Pingli.Research on Shuffled Frog Leaping Algorithm［D］.Xi'an：Xidian University，2013.

［16］蘇仟.混合蛙跳算法研究與改進(jìn)［D］.西安：西安電子科技大學(xué)，2014.

SU Qian.Research and Improvement of Shuffled Frog Leaping Algorithm［D］.Xi'an：Xidian University，2013.

［17］李建軍，郁濱，陳武平.混合蛙跳算法的改進(jìn)與仿真［J］.系統(tǒng)仿真學(xué)報(bào)，2014，26（4）：755-760.

LI Jianjun，YU Bing，CHEN Wuping.Improvement and Simulation for Shuffled Frog Leaping Algorithm［J］.Jour?nalof System Simulation，2014，26（4）：755-760.

［18］施秋紅.一種改進(jìn)的混合蛙跳算法［J］.重慶理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，27（5）：78-81.

SHI Qiuhong.An Improved Shuffled Frog Leaping Algo?rithm［J］.Journal of Chongqing Institute of Technology，2013，27（5）：78-81.

Discussion Mechanism Based Shuffled Frog Leaping Algorithm

WANG Jun XU Jianzhong XU Lei
（Nanjing University of Science and Technology，Nanjing 210094）

A discussion mechanism is put forward based shuffled frog leaping algorithm in view of the situation that the shuf?fled frog leaping algorithm is easy to fall into local optimal situation.The scheme increases the variability of the algorithm，and avoids falling into local optima by adding a discussion mechanism，and the number of the discussion is adjusted dynamically.The algorithm is tested by three classical test functions，the result shows that compared with the basic shuffled frog leaping algorithm，the proposed algorithm improves the optimization capability and the success rate greatly.

shuffled frog leaping algorithm，discussion mechanism，dynamically adjusting，optimization capability，success rate

TP301.6

10.3969/j.issn.1672-9722.2017.08.001

2017年3月17日，

2017年4月21日

國(guó)家自然科學(xué)基金項(xiàng)目（編號(hào)：61301108、61671244）；中央高校基本科研基金（編號(hào)：30915011320）資助。

王俊，男，碩士研究生，研究方向：云計(jì)算。徐建中，男，碩士研究生，研究方向：通信安全。徐雷，男，副教授，研究方向：物聯(lián)網(wǎng)，下一代網(wǎng)絡(luò)技術(shù)，無(wú)線網(wǎng)絡(luò)與移動(dòng)計(jì)算技術(shù)，模式識(shí)別理論與應(yīng)用。