李敏楠 劉 升

1 引言

Eusuff等［1～2］于 2003 年提出了混合蛙跳算法（SFLA），該算法結合了粒子群算法和模因算法的特性，因此具有全局尋優(yōu)能力強，計算速度快等優(yōu)點。但算法在進行局部搜索時，每次組內迭代時個體都要重新根據(jù)初始蛙跳規(guī)則對最差個體進行更新，因此這種更新存在不確定性，導致算法在對復雜函數(shù)進行優(yōu)化求解時，易出現(xiàn)收斂速度慢、精度低等問題。

文獻［3］采用一種新的搜索策略，根據(jù)個體的差異性自主選擇不同的位置更新方式，加快算法收斂速度，提高了種群的多樣性。文獻［4］為了加速算法收斂，避免陷入局部最優(yōu)，對蛙跳更新規(guī)則進行改進，并對最差個體進行混沌擾動，結果證明有效。文獻［5］基于比例系數(shù)和適應度標準差來自適應調整更新，改進了SFLA對高維問題求解的有效性。文獻［6］在算法局部搜索策略中，對子群內最差個體的更新融入了服從正態(tài)分布的變異擾動，擴大了搜索空間，增加了種群的多樣性。文獻［7］結合貪婪算法與模擬退火算法，對算法在局部搜索時是否陷入局部最優(yōu)進行判斷，繼而選擇相應策略進行位置更新。在算法的應用研究方面，許多學者也對該算法進行了相應改進后，用于實際問題的優(yōu)化當中，如云資源調度、車間布局優(yōu)化以及產品裝配序列等研究中，也為蛙跳算法的改進提供了諸多思路［8～12］。為了提高SFLA的收斂精度，提高算法的優(yōu)化性能，本文在標準SFLA中引入同步策略因子，提出一種基于自適應同步因子的混合蛙跳算法（Adaptive Synchronized Factor Shuffled Frog Leaping Algorithm，AS_SFLA），利用同步因子改進青蛙個體的局部搜索策略，更新蛙跳規(guī)則，控制最優(yōu)個體對最差個體的引導程度，提高了算法的收斂精度和優(yōu)化能力。

2 標準混合蛙跳算法

標準蛙跳算法包含確定性和隨機性方法。其基本思想是［1］：隨機生成NI只青蛙個體組成初始種群體P=｛X1，X2，…，XNI｝，S維解空間中的第i只青蛙表示為 Xi=［xi1，xi2，…，xiS］。種群經初始化后，對種群內的青蛙個體按目標函數(shù)值大小的升序排列，并記錄種群中具有最優(yōu)值的個體為Xg，之后將全部個體分成m個模因組，每個模因組包含n只青蛙，滿足關系N=m×n。其中：第1只蛙～第m只蛙分別分入第1模因組～第m模因組，第m+1只蛙再次歸類至第1組，依次類推。設Mk為第k個模因組的個體集合，其分配規(guī)則如式（1）：

每一組中的最優(yōu)個體和最差個休分別記為Xb和Xw，而整個種群的全局最優(yōu)個體表示為Xg，然后對m個模因組展開局部迭代搜索，即對模因組中的最差個體Xw進行循環(huán)迭代更新操作。根據(jù)最初蛙跳規(guī)則，其更新方式為

式中：r為一個隨機數(shù)，且 r∈［0，1］，Dmax表示個體。

位置可以允許改變的最大值。在經過式（2）與式（4）更新后，如果產生的新個體 Xw'優(yōu)于原來的個體XW，則取代相應模因組中最差個體；如果沒有優(yōu)化，則用全局最優(yōu)個體 Xg取代 XW，按式（3）和式（4）進行局部搜索；如果仍未能優(yōu)化，則進行隨機更新，產生一個全新個體取代原來的最差個體，即XW。重復局部搜索過程J次，內部搜索迭代完成后，將全部模因組內的青蛙個體重新混合，重復排序過程和劃分模因組，再進行局部迭代，反復進行，直到迭代次數(shù)達到最大迭代次數(shù)Gmax或滿足收斂精度。全局信息交互學習并開拓局部搜索深度可以使算法能夠跳出局部極值點，不斷向全局最優(yōu)位置靠近［13］。

3 改進的混合蛙跳算法

3.1 自適應同步因子

引入同步因子后，青蛙在進行組內搜索時，會不斷地學習自身的信息來調整位置，但若同步因子固定不變，算法易陷入局部最優(yōu)，影響算法效果。因此本文引入一個動態(tài)自適應的同步因子。由于組內的其他個體會隨著組內迭代次數(shù)的增加不斷地靠近組內具有最優(yōu)位置的個體，因此個體在每次迭代中更新位置時，更新變量也不同，故利用動態(tài)的同步因子來改進蛙跳規(guī)則，可以調整個體對自身信息的學習程度，增加算法局部搜索時個體更新步長的擾動性，從而提高算法的局部搜索和全局搜索能力。綜上分析，動態(tài)同步因子根據(jù)式（5）進行調整：

式中：ω為同步因子，ωmax，ωmin分別為同步因子的取值范圍邊界值，j為組內當前迭代次數(shù)，J表示組內最大迭代次數(shù)。

3.2 改進的混合蛙跳算法

3.2.1 算法描述

混合蛙跳算法（SFLA）具有尋優(yōu)精度不高、算法收斂速度較慢等不足，因此在優(yōu)化復雜函數(shù)問題時效果相對較差。產生這種效果是由于種群多樣性隨著種群的進化不斷降低，從而使算法易陷入早熟收斂和局部最優(yōu)。造成這一問題的原因是蛙跳算法的局部更新策略有待改進，因此本文根據(jù)上面兩個公式對蛙跳規(guī)則進行改進，使算法能夠跳出局部最優(yōu)點，向全局最優(yōu)方向搜索，引入同步因子后的局部與全局蛙跳規(guī)則如式（6）與式（7）所示：

式中：D表示相對當前上次更新時的距離向量，D'L與D'G分別表示本次局部更新與全局更新時的距離向量，ω表示自適應同步因子。

3.2.2 算法流程

本文提出的AS_SFLA算法流程如下：

Step 1：參數(shù)初始化中包含全部個體NI只青蛙，個體搜索維度S，種群分組數(shù)m，每組中有青蛙個體n只，即NI=m×n。個體在改變位置時能夠允許的最大變量為Dmax，組內迭代次數(shù)為J，全局最大迭代次數(shù)為Gmax。

Step 2：種群初始化。參數(shù)進行初始化設定后，隨機生成NI只青蛙個體作為初始種群P=｛X1（t），…，Xi（t），…，XNI（t）｝，i=1，2，…，NI，t為迭代計數(shù)器。其中Xi（t）就作為目標函數(shù)中的自變量來計算每個青蛙個體的適應度值，即Fi（t）=F（Xi（t））；計算出每個個體的目標函數(shù)值后，對所有適應度值按數(shù)值大小的升序排列，同時以Ui（t）=｛Xi（t），F(xiàn)i（t）｝的形式記錄下來，并記錄當前種群全局最優(yōu)個體為X1（t）=U1（t）。

Step 3：種群分組。將按升序排列后的個體按式（1）分配到m個組別中M1（t），…，Mk（t），…，Mm（t），k=1，2，…，m，同時也記錄下每個組別中的最優(yōu)青蛙與最差青蛙，即Xbk（t）和Xwk（t）。

Step 4：組內迭代搜索。對當前種群的每一組進行組內迭代搜索，對當前組別中的最差個體Xkw（t）展開局部搜索。其更新原理仍同基本蛙跳算法，但其更新方式則是按照式（5）、式（6）與式（7）。若此更新后，結果仍未優(yōu)化，則隨機產生一個全新的個體作為當前組內最差個體，計算目標函數(shù)值；重新上述局部搜索次數(shù)J次，最后可以得到一個進化后的種群分組M1（t）'，M2（t）'，…，Mm（t）'。

Step 5：個體重新混合。將進化后的所有分組中的青蛙個體重新混合。重新計算當前種群個體的目標函數(shù)值，并再次按升序重新排列，記錄更新后的種群最優(yōu)個體為Xg（t+1）。

Step 6：算法終止判定。當?shù)嫈?shù)器t=t+1＜J時，跳轉至Step 3；否則，輸出當前最優(yōu)青蛙個體。

4 仿真實驗

4.1 Benchmark函數(shù)

為了驗證AS_SFLA的性能，文中應用SFLA和AS_SFLA分別對所選測試函數(shù)進行優(yōu)化測試，另外利用文獻［14］中的數(shù)據(jù)在9個函數(shù)中選取了其中的5個函數(shù)對SFLA、ISFLA1［14］和 AS_SFLA 進行了數(shù)據(jù)比較。測試平臺為Matlab R2014a和Windows7，處理器為 Intel Core i5，機器主頻 3.00GHz，內存4.00GB。本文選擇了9個Benchmark函數(shù)進行仿真實驗，其中包括3個單峰函數(shù)和5個多峰函數(shù)，最后測試了一個二維函數(shù)。具體函數(shù)如下：

4.2 實驗結果與分析

4.2.1 參數(shù)設置

本文采用SFLA和AS_SFLA進行對比，為了提高實驗的可比性和準確性，設置相同參數(shù)，具體如下：青蛙總數(shù)NI=450只，模因分組數(shù)m=30，每組包含青蛙個體n=15只，組內迭代次數(shù)J=30次，全局總迭代次數(shù)Gmax=1000次，個體維度S=15，同步因子上下限分別取2.5和1，即ωmax=2.5，ωmin=1。

4.2.2 結果分析

將重復運行30次所得的結果按照函數(shù)測試Best值、Worst值與Mean值來檢測算法性能，從測試結果表1與收斂曲線圖1～圖9中得知AS_SFLA的收斂速度更快，對于前3個單峰函數(shù)，AS_SFLA比基本蛙跳算法更接近最優(yōu)值，并且在收斂精度上有很大輻度的提高。在另外5個多峰函數(shù)和一個二維函數(shù)的測試結果中，AS_SFLA也體現(xiàn)了較好的收斂性和較強的尋優(yōu)能力，相比標準混合蛙跳算法，本文提出的算法在迭代過程中，隨著同步因子不斷提高，能夠更加快速地收斂從而找到全局最優(yōu)解，因此較基本算法已有了較大程度的改進。

圖1 不同算法在函數(shù)f1（x）下的收斂曲線（ln）

圖2 不同算法在函數(shù)f2（x）下的收斂曲線（ln）

圖3 不同算法在函數(shù)f3（x）下的收斂曲線（ln）

圖4 不同算法在函數(shù)f4（x）下的曲線（ln）

圖5 不同算法在函數(shù)f5（x）下的收斂曲線

圖6 不同算法在函數(shù)f6（x）下的收斂曲線

圖7 不同算法在函數(shù)f7（x）下的收斂曲線

圖8 不同算法在函數(shù)f8（x）下的收斂曲線

圖9 不同算法在函數(shù)f9（x）下的收斂曲線

表1 不同算法在9個測試函數(shù)中的尋優(yōu)結果

對于Sphere函數(shù)，AS_SFLA采用本文所用參數(shù)可以使最優(yōu)解的收斂精度達到10-49量級，對于Schwefel與Ackley函數(shù)，AS_SFLA的收斂精度也達到了10-10量級，較基本SFLA有所改進。

為了進一步證明AS_SFLA的有效性，本文采用文獻［14］中的數(shù)據(jù)以及參數(shù)，即：青蛙總數(shù)NI=200只，模因分組數(shù)m=20，每組包含青蛙個體n=10只，組內迭代次數(shù)J=10次，全局總迭代次數(shù)Gmax=500次，個體維度S=30，同步因子上下限分別取2.5和 2，即 ωmax=2.5，ωmin=2。 將 SFLA、ISFLA1［14］和AS_SFLA進行了5個Benchmark函數(shù)的實驗，并重復運行30次后，對相關數(shù)據(jù)進行比較，具體數(shù)據(jù)如表2所示。

表2 SFLA，AS_SFLA和ISFLA1的5個測試函數(shù)實驗數(shù)據(jù)

由表2可知，在采用了文獻［14］中的建議參數(shù)后，本文提出的AS_SFLA尋優(yōu)結果和收斂性依然要優(yōu)于基本算法，同時經過兩種算法與ISFLA1的相應數(shù)據(jù)進行對比后，AS_SFLA在Sphere函數(shù)、Rosenbrock函數(shù)、Griewank函數(shù)及Ackley函數(shù)中的最優(yōu)值都要優(yōu)于ISFLA1，其中對Sphere函數(shù)的測試求解精度也已達10-8。

5 結語

混合蛙跳算法基于群體協(xié)同搜索，具有一定的全局搜索能力。本文借鑒改進粒子群算法［15］的思想，在基本算法中引入自適應同步因子，更新局部搜索時的蛙跳規(guī)則，以促進算法的局部搜索深度，通過對9個基準測試函數(shù)進行仿真試驗，證明了算法具有很好的收斂精度和尋優(yōu)結果，對高維復雜函數(shù)能夠進行有效優(yōu)化，體現(xiàn)了算法的優(yōu)越性。本文由于無文獻［14］中的代碼，沒有對其進行收斂曲線的對比，并且該算法在前期迭代時獲得的函數(shù)值較大，影響了算法的穩(wěn)定性，如何能夠對這個問題加以修正和改進將是下一步的研究工作。

［1］Eusuff M M，Lansey K E.Optimization of water distribution network design using the shuffled frog leaping algorithm［J］.J of Water Resources Planning and Management，2003，129（3）：210-225.

［2］Moscato P.On evolution，search，optimization，genetic algorithms and martial arts：Towards memetic algorithms［R］.Caltech Concurrent Computation Program Report 826，California Institute of Technology，1989：16-20.

［3］趙芳，張桂珠.基于新搜索策略的混合蛙跳算法［J］.計算機應用與軟件，2015，32（8）：224-228.

ZHAO Fang，ZHANG Guizhu.Shuffled Frog Leaping Algorithm Based on New Search Strategy［J］.Computer Applications and Software，2015，32（8）：224-228.

［4］張沫.改進混合蛙跳算法的云計算資源調度［J］.計算機應用與軟件，2015，32（4）：330-333.

ZHANG Mo.Resource Scheduling in Cloud Computaing Environment Based Shuffled Frog Leaping Algorithm［J］.Computer Applications and Software，2015，32（4）：330-333.

［5］肖瑩瑩，林廷宇，李伯虎，等.混合蛙跳算法自適應參數(shù)調整改進策略［J］.系統(tǒng)工程與電子技術，2016，38（8）：1939-1949.

XIAO Yingying，LIN Tingyu，LI Bohu，et al.Improvement strategy of adaptive patameter adjustment for shuffled frog leaping algorithm［J］.Systerms Engineering and Electronics，2016，38（8）：1939-1949.

［6］張明明，戴月明，吳定會.正態(tài)變異優(yōu)勝劣汰的混合蛙跳算法［J］.計算機應用，2016，36（6）：1583-1587.

ZHANG Mingming，DAI Yueming，WU Dinghui.Novel survial of the fittest shuffled frog leaping algorithm with normal mutation［J］.Journal of Computer Applications，2016，36（6）：1583-1587.

［7］李俊.混合蛙跳算法改進及其對旅行商問題的求解［J］.軟件導刊，2016，15（10）：41-43.

LI Jun.Improved shuffled frog leaping algorithm and the solution of traveling salesman problem ［J］.Software Guide，2016，15（10）：41-43.

［8］韓煒，崔喆，顧幸生.基于新型蛙跳算法的帶阻塞流水線調度問題［J］.華東理工大學學報（自然科學版），2014，40（1）：86-90.

HAN Wei，CUI Zhe，GU Xingsheng.Blocking Flow Shop Based on a New Frog Leaping Algorithm［J］.Journal of East China University of Science and Technology（Natural Science Edition，2014，40（1）：86-90.

［9］王松，孫振忠，郭建文，等.基于混合蛙跳算法的復雜產品裝配序列規(guī)劃［J］.計算機集成制造系統(tǒng)，2014，20（12）：2991-2999.

WANG Song，SUN Zhenzhong，GUO Jianwen，et al.Assembly sequence planning based on shuffle frog leaping algorithm［J］.Computer Integrated Manufacturing Systems，2014，20（12）：2991-2999.

［10］劉瓊，許金輝，張超勇.基于改進蛙跳算法的魯棒性車間布局［J］.計算機集成制造系統(tǒng)，2014，20（8）：1879-1886.

LIU Qiong，XU Jinhui，ZHANG Chaoyong.Robust layout of floor shop based on improved shuffle frog leaping algorithm［J］.Computer Integrated Manufacturing Systems，2014，20（8）：1879-1886.

［11］張恒巍，衛(wèi)波，王晉東，等.基于分布估計蛙跳算法的云資源調度方法［J］.計算機應用研究，2014，31（11）：3225-3228，3233.

ZHANG Hengwei，WEI Bo，WANG Jindong，et al.Cloud resource scheduling method based on estimation of distribution shuffled frog leaping algorithm［J］.Application Research of Computers，2014，31（11）：3225-3228，3233.

［12］王麗萍，孫平，蔣志強，等.基于并行云變異蛙跳算法的梯級水庫優(yōu)化調度研究［J］.系統(tǒng)工程理論與實踐，2015，35（3）：790-798.

WANG Liping，SUN Ping，JIANG Zhiqiang，et al.Study on cascade reservoirs optimal operation based on parallel normal cloud mutation shuffled frog leaping algorithm［J］.Systems Engineering-Theory&Practice，2015，35（3）：790-798.

［13］Rahimi-Vahed A，Mirzaei A H.A hybrid multi-objective shuffled frog-leaping algorithm for a mixed model assembly line sequencing problem［J］.Computers and Industrial Engineering，2007，53（4）：642-666.

［14］劉悅婷，趙小強.一種自適應慣性權重的混合蛙跳算法［J］.計算機工程，2012，38（12）：132-135.

LIU Yueting，ZHAOXiaoqiang.Adaptive Inertia Weight Shuffled Frog Leaping Algorithm［J］.Computer Engineering，2012，38（12）：132-135.

［15］邵明臣，彭業(yè)飛，張維繼，等.粒子群算法慣性權重的自適應改進與研究［J］.電腦知識與技術（網絡版），2016，16（2）：196-199.

SHAOMingchen，PENGYefei，ZHANGWeiji，et al.Particle Swarm Optimization Inertia Weight Adaptive Improve And Research［J］.Computer Knowledge and Technology，2016，16（2）：196-199.