混合蛙跳算法研究綜述

黃世賢 何曉曦 劉一明

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

基于對自然界一系列獨特規律的發現，尤其是對自然界各種動物群體的行為進行研究，人們發現了各種仿生算法。這些仿生算法通用性強，原理簡單，實現方便，最重要的是能有效解決各種傳統方法不易解決的復雜的組合優化問題，它能通過多次迭代自我適應，學習和發展，最后得到一個復雜問題的最優解或非常靠近最優解。

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

1 混合蛙跳算法

1.1 基本原理

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

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

1.2 算法模型

混合蛙跳算法SFLA (Shuラed Frog Leaping Algorithm)是模擬青蛙在尋食的過程當中,青蛙群體通過按子群分類進行信息交換的進展,將全局搜索與子群局部搜索相結合,使算法朝著全局最優解的方向進化。

1.2.1 全局搜索

Step1：設置SFLA 參數，青蛙群體總數F，族群數量m，每個族群的青蛙數n，最大迭代次數N，最大、最小步長Smax、Smin。

Step2：隨機生成F 只青蛙并計算各個蛙的適應值。

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

Step4：每個族群執行族群局部搜索。

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

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

1.2.2 局部搜索

Step4-1：設im=0，im 是當前族群編號；設iN=0，iN 是當前進化次數。

Step4-2：從當前族群青蛙數n 個中選取q 個可能成為最佳的青蛙構成子群，將子群中青蛙按適應度進行降序排列，記錄最佳位置和最差位置Pb，Pw，然后im=im+1。

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

其中下標j 表示第j 次更新，Dj表示最差解的更新步長，Pj'表示最差解更新后的解。

Step4-4：如果最差青蛙的新位置比原來的好，則使用新位置替換原來的，如果比原來的差，則用全局最優Px 替換局部最優Pb 并計算新的適應值，計算后如果新的位置更優，則使用新位置，如果新位置沒有舊位置好，在可行域中隨機生成一只新的青蛙取代最差的青蛙并計算適應值。

Step4-5：重新計算本子群的最優個體Pb 和最差個體Pw。如果iN＜LS(最大進化數)，則轉到步驟4-3。如果im＜m，則轉到步驟4-2，否則轉到全局搜索過程的步驟5。

2 混合蛙跳算法的研究與改進

雖然混合蛙跳算法在很多優化問題上表現出較好的性能，但是它仍然存在一些不足，它的算法后期收斂速度慢，優化精度不夠高，容易陷入局部最優，不同參數的選擇對它的表現有很大影響。針對這些問題，許多研究人員從不同的方向對SFLA 算法進行了改進，我將其分為參數優化類改進和混合優化類改進。

2.1 參數優化

為提高算法的尋優收斂性能，文獻[5]對算法迭代尋優過程中子種群最差解得更新公式進行改進，提出自適應動態局部搜索機制，如下：

隨著全局迭代次數由大變小，算法迭代初始，較大的權重系數有利于算法的全局搜索，隨著算法接近尾聲，變小的權重系數加快了個體的局部搜索力度，能夠發現更多的精英個體。該更新機制有利于引導個體向著全局最優解方向探索，加快全局收斂。

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

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

2.2 混合優化

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

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

3 混合蛙跳算法的應用

近年來，混合蛙跳算法被廣泛地應用解決不同領域的實際優化問題，本部分對近幾年混合蛙跳算法的一些典型應用進行綜述。

SFLA 在文本領域有所建樹，許方[20]改進了傳統的SFLA,并將其分別與K-means（K 均值）和FCM（模糊C 均值）結合,應用到文本聚類領域中，并且提高了Web 文本聚類的精度。同樣在文本聚類方面，尉建興[21]等將SFLA 與K-means 算法結合，提高了聚類的性能。路永和等[22]在文本特征選擇優化中應用SFLA，降低了噪聲特征項對文本分類的影響程度，取得更高的分類準確率。

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

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

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

4 總結與展望

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

（1）混合蛙跳算法的基礎理論仍需要進一步研究。可以通過借鑒部分其他群智能算法的研究，進一步挖掘算法收斂性，收斂速度方面的研究，以及如何進一步避免早熟，進一步優化參數設置取得更好的結果，在局部和全局信息交換層面也可以深入研究。

（2）混合蛙跳算法本身是基于模因算法與粒子群優化結合而來，可以考慮繼續結合其他有效的優化技術進行融合創新，比如結合模擬退火算法跳出局部最優，可以結合蜂群和鳥群算法有效提高優化精度，以及結合混度優化策略加快算法搜索速度[34]，還有其他許多算法可以進一步彌補SFLA 在不同方面的不足。

（3）雖然混合蛙跳算法近幾年在文本領域，水文領域，電網領域，圖像領域及車間調度等領域已經有了一些應用，但還可以繼續探索，我相信在更多的領域比如神經網絡，語音情感識別，路徑規劃，信號重構，三維定位等領域還可以有新的探索，在探索研究應用的同時也會加快SFLA 的研究與發展。

本文系統地展示了SFLA 的基本原理和算法流程，主要介紹了近幾年SFLA 的研究進展和應用現狀，主要資料均來自與谷歌學術與知網，最后簡單說明了一下接下來SFLA 的研究方向和應用領域，希望能為眾多接觸SFLA 的研究人員給出一點參考。