混合蛙跳算法研究綜述

黃世賢 何曉曦 劉一明

（成都信息工程大學(xué)軟件工程學(xué)院 四川省成都市 610225）

基于對(duì)自然界一系列獨(dú)特規(guī)律的發(fā)現(xiàn)，尤其是對(duì)自然界各種動(dòng)物群體的行為進(jìn)行研究，人們發(fā)現(xiàn)了各種仿生算法。這些仿生算法通用性強(qiáng)，原理簡(jiǎn)單，實(shí)現(xiàn)方便，最重要的是能有效解決各種傳統(tǒng)方法不易解決的復(fù)雜的組合優(yōu)化問(wèn)題，它能通過(guò)多次迭代自我適應(yīng)，學(xué)習(xí)和發(fā)展，最后得到一個(gè)復(fù)雜問(wèn)題的最優(yōu)解或非常靠近最優(yōu)解。

群智能算法作為一種近些年開(kāi)始興起的演化計(jì)算機(jī)技術(shù)，備受許多研究者的關(guān)注，它通過(guò)個(gè)體與個(gè)體，個(gè)體與環(huán)境交互，遵從簡(jiǎn)單的規(guī)則，最終表征出全局上的智能性[1]。通過(guò)對(duì)自然界中魚(yú)群，鳥(niǎo)群，細(xì)菌群，蟻群等的研究，蟻群算法，魚(yú)群算法，粒子群算法等應(yīng)運(yùn)而生[2]。而基于對(duì)蛙群的研究，混合蛙跳算法SFLA (Shuラed Frog Leaping Algorithm) 于2003年由Eusuあ等[3,4]提出。該算法結(jié)合了模因算法MA (Memetic Algorithm)和粒子群優(yōu)化PSO (Particle Swarm Optimization) 算法兩者的優(yōu)點(diǎn)，混合蛙跳算法是一種求解離散優(yōu)化問(wèn)題的元啟發(fā)式算法。SFLA 是一個(gè)基于群體的合作搜索算法，該算法在局部搜索中是通過(guò)從一個(gè)個(gè)體感染另一個(gè)的形式，在概念上與粒子群算法相似。全局搜索中運(yùn)用洗牌策略允許在局部搜索之間交換信息，以向全局最優(yōu)移動(dòng)。

1 混合蛙跳算法

1.1 基本原理

舉一個(gè)例子：給定一片濕地，濕地中生活著一群青蛙，濕地里離散的分布著許多石頭，濕地里每只青蛙都通過(guò)跳躍不同的石頭去到食物較多的地方，每只青蛙個(gè)體直接進(jìn)行信息交換，以最優(yōu)秀的青蛙為基準(zhǔn)，每只青蛙的位置都作為一個(gè)解。

濕地的青蛙群體被分為不同的子群體，每個(gè)子群體有著自己的文化，執(zhí)行局部搜索策略。在子群體中的每個(gè)個(gè)體有著自己的文化，并且影響著其他個(gè)體，也受其他個(gè)體的影響，并隨著子群體的進(jìn)化而進(jìn)化。當(dāng)子群體進(jìn)化到一定階段以后，各個(gè)子群體之間再進(jìn)行思想的交流（全局信息交換）實(shí)現(xiàn)子群體間的混合運(yùn)算，一直到所設(shè)置的條件滿足為止。

1.2 算法模型

混合蛙跳算法SFLA (Shuラed Frog Leaping Algorithm)是模擬青蛙在尋食的過(guò)程當(dāng)中,青蛙群體通過(guò)按子群分類(lèi)進(jìn)行信息交換的進(jìn)展,將全局搜索與子群局部搜索相結(jié)合,使算法朝著全局最優(yōu)解的方向進(jìn)化。

1.2.1 全局搜索

Step1：設(shè)置SFLA 參數(shù)，青蛙群體總數(shù)F，族群數(shù)量m，每個(gè)族群的青蛙數(shù)n，最大迭代次數(shù)N，最大、最小步長(zhǎng)Smax、Smin。

Step2：隨機(jī)生成F 只青蛙并計(jì)算各個(gè)蛙的適應(yīng)值。

Step3：按適應(yīng)值大小進(jìn)行降序排序并記錄最好解Px，并且將蛙群分成多個(gè)族群。把F 個(gè)蛙分配到m 個(gè)族群中去，每個(gè)族群包含n 個(gè)蛙。

Step4：每個(gè)族群執(zhí)行族群局部搜索。

Step5：將各個(gè)族群進(jìn)行混合，然后將各個(gè)族群中的蛙重新進(jìn)行排序和族群劃分并記錄全局最好解Px。

Step6：檢查收斂。如果收斂條件滿足，停止。否則，返回到步驟3。

1.2.2 局部搜索

Step4-1：設(shè)im=0，im 是當(dāng)前族群編號(hào)；設(shè)iN=0，iN 是當(dāng)前進(jìn)化次數(shù)。

Step4-2：從當(dāng)前族群青蛙數(shù)n 個(gè)中選取q 個(gè)可能成為最佳的青蛙構(gòu)成子群，將子群中青蛙按適應(yīng)度進(jìn)行降序排列，記錄最佳位置和最差位置Pb，Pw，然后im=im+1。

Step4-3：改善子群中最差青蛙的位置，然后iN=iN+1。

其中下標(biāo)j 表示第j 次更新，Dj表示最差解的更新步長(zhǎng)，Pj'表示最差解更新后的解。

Step4-4：如果最差青蛙的新位置比原來(lái)的好，則使用新位置替換原來(lái)的，如果比原來(lái)的差，則用全局最優(yōu)Px 替換局部最優(yōu)Pb 并計(jì)算新的適應(yīng)值，計(jì)算后如果新的位置更優(yōu)，則使用新位置，如果新位置沒(méi)有舊位置好，在可行域中隨機(jī)生成一只新的青蛙取代最差的青蛙并計(jì)算適應(yīng)值。

Step4-5：重新計(jì)算本子群的最優(yōu)個(gè)體Pb 和最差個(gè)體Pw。如果iN＜LS(最大進(jìn)化數(shù))，則轉(zhuǎn)到步驟4-3。如果im＜m，則轉(zhuǎn)到步驟4-2，否則轉(zhuǎn)到全局搜索過(guò)程的步驟5。

2 混合蛙跳算法的研究與改進(jìn)

雖然混合蛙跳算法在很多優(yōu)化問(wèn)題上表現(xiàn)出較好的性能，但是它仍然存在一些不足，它的算法后期收斂速度慢，優(yōu)化精度不夠高，容易陷入局部最優(yōu)，不同參數(shù)的選擇對(duì)它的表現(xiàn)有很大影響。針對(duì)這些問(wèn)題，許多研究人員從不同的方向?qū)FLA 算法進(jìn)行了改進(jìn)，我將其分為參數(shù)優(yōu)化類(lèi)改進(jìn)和混合優(yōu)化類(lèi)改進(jìn)。

2.1 參數(shù)優(yōu)化

為提高算法的尋優(yōu)收斂性能，文獻(xiàn)[5]對(duì)算法迭代尋優(yōu)過(guò)程中子種群最差解得更新公式進(jìn)行改進(jìn)，提出自適應(yīng)動(dòng)態(tài)局部搜索機(jī)制，如下：

隨著全局迭代次數(shù)由大變小，算法迭代初始，較大的權(quán)重系數(shù)有利于算法的全局搜索，隨著算法接近尾聲，變小的權(quán)重系數(shù)加快了個(gè)體的局部搜索力度，能夠發(fā)現(xiàn)更多的精英個(gè)體。該更新機(jī)制有利于引導(dǎo)個(gè)體向著全局最優(yōu)解方向探索，加快全局收斂。

文獻(xiàn)[6]提出了正態(tài)變異優(yōu)勝劣汰的混合蛙跳算法，首先在對(duì)子群內(nèi)最差的青蛙個(gè)體Pw 執(zhí)行更新策略時(shí)，引入一個(gè)服從正態(tài)分布的隨機(jī)擾動(dòng)項(xiàng)，使新個(gè)體產(chǎn)生擾動(dòng)變異，就可以使青蛙個(gè)體進(jìn)入解空間的其他區(qū)域進(jìn)行搜索，擴(kuò)大搜索范圍，從而有可能發(fā)現(xiàn)新的個(gè)體最優(yōu)位置和種群最優(yōu)位置，提高種群多樣性。其次對(duì)子群內(nèi)部少量適應(yīng)值較差的青蛙個(gè)體，在原有的青蛙個(gè)體基礎(chǔ)上每一維度引入一個(gè)服從正態(tài)分布的隨機(jī)變異擾動(dòng)，各自產(chǎn)生1 個(gè)新個(gè)體,若優(yōu)于原個(gè)體則對(duì)其進(jìn)行取代否則保持不變。最后對(duì)子群內(nèi)部少量(例如3 個(gè))適應(yīng)值較差的青蛙個(gè)體，讓它們進(jìn)行正態(tài)變異,即在原有的青蛙個(gè)體基礎(chǔ)上每一維度引入一個(gè)服從正態(tài)分布的隨機(jī)變異擾動(dòng)，各自產(chǎn)生1 個(gè)新個(gè)體，若優(yōu)于原個(gè)體則對(duì)其進(jìn)行取代否則保持不變。

為提高SFLA 的收斂性加快其收斂速度，國(guó)內(nèi)外學(xué)者先后做出一些改進(jìn)，文獻(xiàn)[7]將SFLA 與遺傳算法結(jié)合并使用KNN 和留一法(leave-one-out)交叉驗(yàn)證，文中對(duì)11 種分類(lèi)問(wèn)題進(jìn)行了比較，有效地提高了分類(lèi)問(wèn)題的精度。文獻(xiàn)[8]提出一種新的認(rèn)知組件，使每個(gè)青蛙可以根據(jù)個(gè)體的思維來(lái)調(diào)整自身位置，并采用六個(gè)基準(zhǔn)問(wèn)題驗(yàn)證了對(duì)算法有效性的提升。文獻(xiàn)[9]基于離散SFLA 算法，提出了一種新的連續(xù)空間優(yōu)化SFLA 算法，該算法根據(jù)模因一致性原則對(duì)種群進(jìn)行劃分，通過(guò)對(duì)多個(gè)多峰值連續(xù)函數(shù)進(jìn)行尋優(yōu)的仿真結(jié)果表明，改進(jìn)的SFLA 算法能有效地克服早熟收斂和收斂速度慢的問(wèn)題，獲得較高的優(yōu)化精度。文獻(xiàn)[10]提出了一種新的蛙跳規(guī)則，主要是通過(guò)模擬蛙跳的感知和動(dòng)作的不確定性來(lái)擴(kuò)展蛙跳的方向和長(zhǎng)度，這種改進(jìn)拓寬了局部搜索空間，有助于防止早熟收斂，提高了SFLA的性能。文獻(xiàn)[11]利用系統(tǒng)穩(wěn)定性分析方法,提出在SFLA 更新公式中基于比例系數(shù)和適應(yīng)度標(biāo)準(zhǔn)差來(lái)自適應(yīng)調(diào)整更新的方法，基于8個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)驗(yàn)證了該方法對(duì)高維問(wèn)題求解的有效性。文獻(xiàn)[12]通過(guò)引用精英策略保留最適應(yīng)的個(gè)體，并且引用柯西分布變異算子使算法在后期跳出局部最優(yōu)，并利用Minkowsk 距離提升了全局最優(yōu)青蛙優(yōu)化的機(jī)會(huì)，使改進(jìn)的SFLA 具有較快的收斂速度，更高的收斂精度。

2.2 混合優(yōu)化

為了改進(jìn)SFLA 易陷入局部最優(yōu)和早熟收斂的狀況，近幾年有許多結(jié)合其他方法的SFLA 改進(jìn)算法。文獻(xiàn)[13]提出基于GPU 的并行SFLA，結(jié)合CUDA 線程，有效降低算法運(yùn)行時(shí)間并提高收斂性。文獻(xiàn)[14]將粒子群算法與SFLA 融合，引進(jìn)一個(gè)全局反饋分量有效改進(jìn)蛙群更新速度和更新位置，獲得了很好的優(yōu)化性能。文獻(xiàn)[15]根據(jù)粒子群優(yōu)化和差分進(jìn)化思想，在青蛙個(gè)體進(jìn)化時(shí)，引入上一次移動(dòng)距離的權(quán)重慣性系數(shù)，有效改善子群位置更新操作，并結(jié)合KMC(傳統(tǒng)K 均值聚類(lèi))算法，獲得更強(qiáng)的尋優(yōu)能力。

在09年，駱劍平等[16]率先證明青蛙族群狀態(tài)序列是齊次Markov 鏈，同時(shí)指出SFLA 滿足隨機(jī)搜索算法全局收斂的兩個(gè)條件，保證全局收斂。之后文獻(xiàn)[17]通過(guò)增加子群次優(yōu)解和次劣解的信息交互，結(jié)合2-opt 方法增加子群多樣性，有效防止算法早熟收斂。文獻(xiàn)[18]對(duì)混合蛙跳算法權(quán)重因子進(jìn)行了改進(jìn),設(shè)計(jì)了基于Pareto支配能力的SFLA 子族群劃分策略，并結(jié)合自適應(yīng)網(wǎng)格密度機(jī)制和自適應(yīng)混沌優(yōu)化技術(shù)，實(shí)現(xiàn)了多目標(biāo)優(yōu)化問(wèn)題求解。文獻(xiàn)[19]引入了全局共享因子和局部共享因子，并實(shí)驗(yàn)給出了算法效率分析，固定全局進(jìn)化次數(shù)和收斂精度后，該算法在單峰值和多峰值函數(shù)尋優(yōu)問(wèn)題上均具有較高的收斂速度和精度。

3 混合蛙跳算法的應(yīng)用

近年來(lái)，混合蛙跳算法被廣泛地應(yīng)用解決不同領(lǐng)域的實(shí)際優(yōu)化問(wèn)題，本部分對(duì)近幾年混合蛙跳算法的一些典型應(yīng)用進(jìn)行綜述。

SFLA 在文本領(lǐng)域有所建樹(shù)，許方[20]改進(jìn)了傳統(tǒng)的SFLA,并將其分別與K-means（K 均值）和FCM（模糊C 均值）結(jié)合,應(yīng)用到文本聚類(lèi)領(lǐng)域中，并且提高了Web 文本聚類(lèi)的精度。同樣在文本聚類(lèi)方面，尉建興[21]等將SFLA 與K-means 算法結(jié)合，提高了聚類(lèi)的性能。路永和等[22]在文本特征選擇優(yōu)化中應(yīng)用SFLA，降低了噪聲特征項(xiàng)對(duì)文本分類(lèi)的影響程度，取得更高的分類(lèi)準(zhǔn)確率。

SFLA 在水文方面也有所應(yīng)用，火久元等[23]提出一種基于SFLA 的水文模型參數(shù)估計(jì)方法,將該方法應(yīng)用到新安江模型的參數(shù)估計(jì)中，與基于遺傳算法的水文模型參數(shù)估計(jì)方法定量對(duì)比優(yōu)勢(shì)明顯。司存友等[24]采用SFLA 對(duì)API 模型進(jìn)行參數(shù)優(yōu)化和智能定線，有效的提高了API 模型預(yù)報(bào)精度。李恩寬等[25]運(yùn)用基于SFLA 的投影尋蹤模型對(duì)黃河流域用水效率進(jìn)行評(píng)價(jià)，為黃河流域用水效率管理與節(jié)水型社會(huì)建設(shè)提供參考資料。

針對(duì)城市電網(wǎng)問(wèn)題，儲(chǔ)琳琳等[26]提出了無(wú)功補(bǔ)償雙層優(yōu)化模型，通過(guò)SFLA 對(duì)該模型進(jìn)行求解，并應(yīng)用IEEE-33 節(jié)點(diǎn)測(cè)試有效降低網(wǎng)損，提升電壓等。仙鋒等[27]將SFLA 結(jié)合閾值選擇策略，應(yīng)用在現(xiàn)代電網(wǎng)規(guī)劃中，但沒(méi)有實(shí)驗(yàn)驗(yàn)證，只有理論。張萍等[28]通過(guò)一種結(jié)合人工魚(yú)群和SFLA 的矢量匹配法，實(shí)現(xiàn)了電壓傳輸函數(shù)的有理擬合，以實(shí)際大型電力變壓器模型開(kāi)展仿真實(shí)驗(yàn)，獲得了較好的效果，有一定的工程價(jià)值。朱芳[29]基于KPCA 與SFLA 提出一種光伏發(fā)電功率預(yù)測(cè)方法，經(jīng)算例結(jié)果表明，相比傳統(tǒng)預(yù)測(cè)模型新方法預(yù)測(cè)精度更高。

在其他應(yīng)用方面，李波[30]在可分裂的TCRO(時(shí)間、成本，資源優(yōu)化)問(wèn)題上應(yīng)用SFLA，經(jīng)過(guò)她的案例比較，相比其他群智能算法獲得了更好的解決方案。李榮波等[31]在梯度水庫(kù)優(yōu)化調(diào)度中，應(yīng)用SFLA 結(jié)合混沌技術(shù)和全局激勵(lì)調(diào)節(jié)策略，在李仙江流域優(yōu)化調(diào)度測(cè)試中取得優(yōu)良結(jié)果。陳春朝等[32]運(yùn)用SFLA 結(jié)合人工勢(shì)場(chǎng)法，在機(jī)器人路徑規(guī)劃中有效提升規(guī)劃效率。張新明等[33]提出一種優(yōu)化的SFLA，在多閾值圖像分割中，經(jīng)過(guò)灰度和彩色圖像測(cè)試實(shí)驗(yàn)，具有良好的優(yōu)化效率。

4 總結(jié)與展望

混合蛙跳算法是一種有效的優(yōu)化算法，眾多研究者不斷推成出新，提出了大量的改進(jìn)方法和實(shí)際應(yīng)用案例。但在不斷的深入研究中，該算法依舊有許多不足和值得繼續(xù)研究的地方。

（1）混合蛙跳算法的基礎(chǔ)理論仍需要進(jìn)一步研究?？梢酝ㄟ^(guò)借鑒部分其他群智能算法的研究，進(jìn)一步挖掘算法收斂性，收斂速度方面的研究，以及如何進(jìn)一步避免早熟，進(jìn)一步優(yōu)化參數(shù)設(shè)置取得更好的結(jié)果，在局部和全局信息交換層面也可以深入研究。

（2）混合蛙跳算法本身是基于模因算法與粒子群優(yōu)化結(jié)合而來(lái)，可以考慮繼續(xù)結(jié)合其他有效的優(yōu)化技術(shù)進(jìn)行融合創(chuàng)新，比如結(jié)合模擬退火算法跳出局部最優(yōu)，可以結(jié)合蜂群和鳥(niǎo)群算法有效提高優(yōu)化精度，以及結(jié)合混度優(yōu)化策略加快算法搜索速度[34]，還有其他許多算法可以進(jìn)一步彌補(bǔ)SFLA 在不同方面的不足。

（3）雖然混合蛙跳算法近幾年在文本領(lǐng)域，水文領(lǐng)域，電網(wǎng)領(lǐng)域，圖像領(lǐng)域及車(chē)間調(diào)度等領(lǐng)域已經(jīng)有了一些應(yīng)用，但還可以繼續(xù)探索，我相信在更多的領(lǐng)域比如神經(jīng)網(wǎng)絡(luò)，語(yǔ)音情感識(shí)別，路徑規(guī)劃，信號(hào)重構(gòu)，三維定位等領(lǐng)域還可以有新的探索，在探索研究應(yīng)用的同時(shí)也會(huì)加快SFLA 的研究與發(fā)展。

本文系統(tǒng)地展示了SFLA 的基本原理和算法流程，主要介紹了近幾年SFLA 的研究進(jìn)展和應(yīng)用現(xiàn)狀，主要資料均來(lái)自與谷歌學(xué)術(shù)與知網(wǎng)，最后簡(jiǎn)單說(shuō)明了一下接下來(lái)SFLA 的研究方向和應(yīng)用領(lǐng)域，希望能為眾多接觸SFLA 的研究人員給出一點(diǎn)參考。