李敏楠 劉 升

1 引言

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

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

2 標(biāo)準(zhǔn)混合蛙跳算法

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

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

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

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

3 改進(jìn)的混合蛙跳算法

3.1 自適應(yīng)同步因子

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

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

3.2 改進(jìn)的混合蛙跳算法

3.2.1 算法描述

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

式中：D表示相對(duì)當(dāng)前上次更新時(shí)的距離向量，D'L與D'G分別表示本次局部更新與全局更新時(shí)的距離向量，ω表示自適應(yīng)同步因子。

3.2.2 算法流程

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

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

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

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

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

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

Step 6：算法終止判定。當(dāng)?shù)?jì)數(shù)器t=t+1＜J時(shí)，跳轉(zhuǎn)至Step 3；否則，輸出當(dāng)前最優(yōu)青蛙個(gè)體。

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

4.1 Benchmark函數(shù)

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

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

4.2.1 參數(shù)設(shè)置

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

4.2.2 結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

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

表2 SFLA，AS_SFLA和ISFLA1的5個(gè)測(cè)試函數(shù)實(shí)驗(yàn)數(shù)據(jù)

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

5 結(jié)語(yǔ)

混合蛙跳算法基于群體協(xié)同搜索，具有一定的全局搜索能力。本文借鑒改進(jìn)粒子群算法［15］的思想，在基本算法中引入自適應(yīng)同步因子，更新局部搜索時(shí)的蛙跳規(guī)則，以促進(jìn)算法的局部搜索深度，通過(guò)對(duì)9個(gè)基準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真試驗(yàn)，證明了算法具有很好的收斂精度和尋優(yōu)結(jié)果，對(duì)高維復(fù)雜函數(shù)能夠進(jìn)行有效優(yōu)化，體現(xiàn)了算法的優(yōu)越性。本文由于無(wú)文獻(xiàn)［14］中的代碼，沒(méi)有對(duì)其進(jìn)行收斂曲線(xiàn)的對(duì)比，并且該算法在前期迭代時(shí)獲得的函數(shù)值較大，影響了算法的穩(wěn)定性，如何能夠?qū)@個(gè)問(wèn)題加以修正和改進(jì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］.計(jì)算機(jī)應(yīng)用與軟件，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ìn)混合蛙跳算法的云計(jì)算資源調(diào)度［J］.計(jì)算機(jī)應(yīng)用與軟件，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］肖瑩瑩，林廷宇，李伯虎，等.混合蛙跳算法自適應(yīng)參數(shù)調(diào)整改進(jìn)策略［J］.系統(tǒng)工程與電子技術(shù)，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］張明明，戴月明，吳定會(huì).正態(tài)變異優(yōu)勝劣汰的混合蛙跳算法［J］.計(jì)算機(jī)應(yīng)用，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ìn)及其對(duì)旅行商問(wèn)題的求解［J］.軟件導(dǎo)刊，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］韓煒，崔喆，顧幸生.基于新型蛙跳算法的帶阻塞流水線(xiàn)調(diào)度問(wèn)題［J］.華東理工大學(xué)學(xué)報(bào)（自然科學(xué)版），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］王松，孫振忠，郭建文，等.基于混合蛙跳算法的復(fù)雜產(chǎn)品裝配序列規(guī)劃［J］.計(jì)算機(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ìn)蛙跳算法的魯棒性車(chē)間布局［J］.計(jì)算機(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ì)蛙跳算法的云資源調(diào)度方法［J］.計(jì)算機(jī)應(yīng)用研究，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］王麗萍，孫平，蔣志強(qiáng)，等.基于并行云變異蛙跳算法的梯級(jí)水庫(kù)優(yōu)化調(diào)度研究［J］.系統(tǒng)工程理論與實(shí)踐，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］劉悅婷，趙小強(qiáng).一種自適應(yīng)慣性權(quán)重的混合蛙跳算法［J］.計(jì)算機(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è)飛，張維繼，等.粒子群算法慣性權(quán)重的自適應(yīng)改進(jìn)與研究［J］.電腦知識(shí)與技術(shù)（網(wǎng)絡(luò)版），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.