胥 楓，張桂珠，趙 芳，吳德龍

(江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇 無(wú)錫 214122)

1 概述

混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)是模擬青蛙覓食過(guò)程中群體信息共享和交流機(jī)制而產(chǎn)生的一種群智能算法，是一種全新的啟發(fā)式群體智能進(jìn)化算法。該算法由Eusuff 和Lansey 在2003 年首次提出，并成功解決了管道網(wǎng)絡(luò)擴(kuò)充中管道尺寸的最小化問(wèn)題［1］。

混合蛙跳與其他群智能算法相比，具有概念簡(jiǎn)單、參數(shù)少、計(jì)算速度快、全局尋優(yōu)能力強(qiáng)、易于實(shí)現(xiàn)等特點(diǎn)［2］，近年來(lái)已經(jīng)被成功應(yīng)用于多個(gè)領(lǐng)域。但混合蛙跳算法也存在著對(duì)初始值敏感、早熟收斂以及求解精度差等缺點(diǎn)［3］，為此許多學(xué)者對(duì)其進(jìn)行改進(jìn)，將該算法與其他群智能算法相結(jié)合以提高算法的性能，如與差分進(jìn)化(Differential Evolution，DE)算法［4］、量子粒子群優(yōu)化(Quantum-behaved Particle Swarm Optimization，OPSO)算 法［5］、模 擬 退 火(Simulated Annealing，SA)算法［6］等結(jié)合，都取得了不錯(cuò)的效果?；旌贤芴惴ǖ男阅芨倪M(jìn)已成為目前研究的熱點(diǎn)問(wèn)題。

粒子群優(yōu)化(Particle Swarm Optimization，PSO)算法是1995 年由Kennedy 和Eberhart 提出的群智能算法［7］，是一種全局優(yōu)化算法，能在較短的時(shí)間內(nèi)求得高質(zhì)量的解。文獻(xiàn)［8］提出一種PSO 算法產(chǎn)生滿足約束條件的初始解的方法，可用于各種算法初始解的產(chǎn)生。差分進(jìn)化算法［9］最初由Store 和Price 于1995 年提出，該算法通過(guò)變異、雜交、選擇操作來(lái)更新隨機(jī)產(chǎn)生的初始種群，經(jīng)過(guò)逐步迭代、不斷進(jìn)化，可實(shí)現(xiàn)全局最優(yōu)解的搜索，具有較強(qiáng)的全局尋優(yōu)能力，種群多樣性好，但在算法的初期收斂速度較慢。

本文在借鑒前人研究成果的基礎(chǔ)之上，提出一種自適應(yīng)交替的差分混合蛙跳算法ADE-SFLA。將SFLA 算法與DE、PSO 這2 種算法相結(jié)合，利用PSO算法在短時(shí)間內(nèi)生成一組高質(zhì)量的初始解;并在搜索策略中，提出一種改進(jìn)選擇機(jī)制，交替使用SFLA和DE 這2 種算法，利用2 種算法搜索原理的不同，在算法輪替中相互擾動(dòng)以豐富粒子多樣性，并且繼承了2 種算法各自的優(yōu)勢(shì)，使算法前期具有較快的收斂速度，后期進(jìn)行更精確的局部搜索，以提高算法的性能。

2 混合蛙跳算法

2.1 初始化

隨機(jī)生成N 只青蛙組成初始化群體F={X1，X2，…，Xn}，第k 只青蛙表示問(wèn)題的解為Xk={xk1，xk2，…，xkl}，其中，l 表示變量的個(gè)數(shù)，即解空間的維數(shù)。

2.2 分組算子

將所有青蛙按照它們的初始適應(yīng)度值進(jìn)行降序排序，并分別放入各個(gè)模因組中。具體分組方法如下:將N 只青蛙青蛙按適應(yīng)度值降序排列，并把種群分為m 個(gè)模因組，第1 只青蛙進(jìn)入第1 個(gè)模因組，第2只青蛙進(jìn)入第2 個(gè)模因組，……，第m 只青蛙進(jìn)入第m 個(gè)模因組;然后第m+1 只青蛙進(jìn)入到第1 個(gè)模因組，第m +2 只青蛙進(jìn)入到第2 個(gè)模因組，直到所有青蛙分配完畢。在每個(gè)模因組中用Fb和Fw分別表示模因組中位置最好和最差的青蛙，用Fg表示整個(gè)種群中位置最好的青蛙。

2.3 局部位置更新算子

在模因組中的每一次進(jìn)化過(guò)程中，對(duì)最差青蛙Fw位置進(jìn)行調(diào)整，具體調(diào)整方法如下:

青蛙的移動(dòng)距離為:

更新最差青蛙的位置:

其中，rand()是0～1 之間的隨機(jī)數(shù);Dmax是允許青蛙移動(dòng)的最大距離。

在位置調(diào)整過(guò)程中，如果最差青蛙經(jīng)過(guò)上述過(guò)程能夠產(chǎn)生一個(gè)較好的位置，就用新位置的青蛙取代原來(lái)位置的青蛙，即更新最差青蛙Fw;否則用Fg代替Fb。

重復(fù)上述過(guò)程，即用下式更新最差青蛙位置:

如果上述方法不能產(chǎn)生位置更好的青蛙或在調(diào)整過(guò)程中青蛙的移動(dòng)距離超過(guò)了最大移動(dòng)距離，那么就隨機(jī)產(chǎn)生一個(gè)新解取代原來(lái)最差的青蛙Fw。按照這種方法，每個(gè)模因組內(nèi)部經(jīng)過(guò)一定次數(shù)的進(jìn)化，對(duì)最差青蛙位置進(jìn)行調(diào)整和更新。

2.4 全局更新算子

全局更新算子有助于收集各模因組內(nèi)搜索的局部信息，通過(guò)模因組中信息在全局中的共享，獲得新的搜索全局最優(yōu)解的方向。當(dāng)所有模因組經(jīng)過(guò)組內(nèi)最大迭代次數(shù)后，將各模因組中青蛙混合在一起，再將所有青蛙個(gè)體按適應(yīng)度降序排列后，重新分組，這樣使得青蛙個(gè)體的模因信息得到充分的傳遞，然后繼續(xù)進(jìn)行局部搜索，如此反復(fù)直至達(dá)到最大全局迭代次數(shù)或者滿足收斂條件，算法停止。

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

3.1 初始種群的產(chǎn)生

群智能算法都有一個(gè)普遍的特點(diǎn):對(duì)初始值敏感，混合蛙跳算法也不例外?；旌贤芴惴ǖ某跏冀馐请S機(jī)產(chǎn)生的，如果產(chǎn)生的隨機(jī)解普遍適應(yīng)度值不夠理想，可能會(huì)影響算法的全局尋優(yōu)性能，容易收斂到局部最優(yōu)解。因此，必須對(duì)初始產(chǎn)生的青蛙種群進(jìn)行優(yōu)化。

理想的初始解應(yīng)該有較好的適應(yīng)度值，初始種群有較好的多樣性。本文利用粒子群算法來(lái)產(chǎn)生初始解，粒子群算法的具體步驟見(jiàn)文獻(xiàn)［10］。定義產(chǎn)生初始解的約束條件有3 個(gè):粒子每維的分量落在指定的區(qū)間內(nèi)，粒子的適應(yīng)度值達(dá)到預(yù)定值，粒子的多樣性達(dá)到規(guī)定要求。定義粒子群的初始群體L={X1，X2，…，Xk，…，Xn}，n 表示群體中粒子的個(gè)數(shù)，第k個(gè)粒子問(wèn)題的解為Xk={xk1，xk2，…，xkl，…，xkd}，d 為解空間的維數(shù)。因此，本文提出初始解產(chǎn)生的數(shù)學(xué)算子為:

其中，a 和b 分別為搜索區(qū)間的下界與上界;fitness(X)是適應(yīng)度函數(shù);dfitness為適應(yīng)度值閾值;ddiversity為多樣性閾值;diversity(X)是多樣性度量表達(dá)式中的xij表示第i個(gè)粒子的第j 維分量。

算法的基本思想:在給定區(qū)間范圍內(nèi)隨機(jī)產(chǎn)生一組值作為粒子群算法的初始解，然后按照粒子群的粒子速度、位置更新公式更新粒子的速度和位置，每次計(jì)算H(L)時(shí)判斷H(L)是否小于等于1，并且判斷f(Xi)≤0，i=1，2，…，n 和d(Xj)≤0，j=1，2，…，n 是否都成立，若都成立，則記下該粒子的位置作為改進(jìn)算法的一個(gè)初始解，并且重新在給定的區(qū)間范圍內(nèi)產(chǎn)生一新粒子以替換該粒子。重復(fù)上述過(guò)程，最終能找到滿足約束條件的N 個(gè)位置作為改進(jìn)算法的初始解。

3.2 改進(jìn)的搜索策略

基于優(yōu)勢(shì)互補(bǔ)的思想，本文提出一種自適應(yīng)交替的差分混合蛙跳算法。相對(duì)于差分進(jìn)化算法，混合蛙跳算法在進(jìn)化初期有較快的收斂速度，但在進(jìn)化后期由于粒子的趨同性，導(dǎo)致粒子喪失多樣性，易發(fā)生早熟收斂;相對(duì)于混合蛙跳算法，差分進(jìn)化算法在進(jìn)化初期的收斂速度較慢，但在進(jìn)化的后期收斂速度較快，而且粒子多樣性較好，為了結(jié)合兩者的優(yōu)勢(shì)，需要一個(gè)合理的選擇機(jī)制在搜索過(guò)程中交替使用這2 種算法。文獻(xiàn)［4］提出了一種選擇機(jī)制，類似于轉(zhuǎn)盤(pán)機(jī)制:

其中，i 是當(dāng)前算法的迭代次數(shù);R 是一個(gè)固定常數(shù)。在這種選擇機(jī)制下，算法每進(jìn)行R -1 次SFLA 全局迭代搜索后就進(jìn)行一次DE 迭代搜索，相當(dāng)于是給SFLA 搜索進(jìn)行了一次DE 擾動(dòng)，但是這種選擇機(jī)制并沒(méi)有真正結(jié)合SFLA 和DE 這2 種算法的優(yōu)勢(shì)，只是在原來(lái)SFLA 算法的基礎(chǔ)上多了DE 擾動(dòng)。為此，本文提出一種改進(jìn)的選擇機(jī)制:

其中，i 是當(dāng)前算法的迭代次數(shù);rand 是0～1 之間的隨機(jī)數(shù);Tmax是算法最大迭代次數(shù);0.8/(1 +e-4i/Tmax)是根據(jù)當(dāng)前迭代次數(shù)產(chǎn)生0～1 的小數(shù)，前期產(chǎn)生數(shù)較小，后期產(chǎn)生的數(shù)較大。這個(gè)選擇機(jī)制的作用:通過(guò)比較rand 和0.8/(1 +e-4i/Tmax)的大小，讓算法前期以較大的概率進(jìn)行SFLA 搜索，并以小概率隨機(jī)地進(jìn)行DE 擾動(dòng);后期以較大概率進(jìn)行DE 搜索，并以小概率進(jìn)行SFLA 擾動(dòng)。這樣不但能豐富粒子的多樣性，而且繼承了2 種算法在進(jìn)化初期和后期的優(yōu)秀性能，使算法在前期有較快的收斂速度，后期能夠進(jìn)行更精確的局部搜索。

改進(jìn)算法ADE-SFLA 的步驟如下:

(1)初始化算法參數(shù)，包括種群的數(shù)量N，模因組數(shù)量M，組內(nèi)迭代次數(shù)It，全局最大迭代次數(shù)Tmax等參數(shù)。

(2)用PSO 算法優(yōu)化初始產(chǎn)生的種群，獲得高質(zhì)量的初始解。

(3)進(jìn)行迭代過(guò)程:

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

4.1 實(shí)驗(yàn)平臺(tái)測(cè)試函數(shù)的介紹與參數(shù)的設(shè)置

為了檢驗(yàn)改進(jìn)算法的性能，設(shè)計(jì)實(shí)驗(yàn)環(huán)境在軟件平臺(tái)Matlab 上。

測(cè)試對(duì)象為6 個(gè)經(jīng)典的連續(xù)函數(shù)，f1:Sphere 簡(jiǎn)單的單峰函數(shù);f2:Rosenbrock 簡(jiǎn)單的多峰函數(shù);f3:Rastrigin 復(fù)雜的多峰函數(shù);f4:Griewank 復(fù)雜的多峰函數(shù)，f5:Ackely 復(fù)雜的多峰函數(shù);f6:Schafferf7 復(fù)雜的多峰函數(shù)。

這些函數(shù)的理論全局最優(yōu)解都為0。6 個(gè)函數(shù)表達(dá)式如下所示:

算法參數(shù)的設(shè)置:全局最大迭代次數(shù)為500 次，變量的維數(shù)n 為30。SFLA 算法的青蛙數(shù)量為200 個(gè)，模因組數(shù)為20 個(gè)，組內(nèi)最大迭代次數(shù)為10 次［12］;DE 算法的縮放因子F 設(shè)置為0.5，交叉概率C 為0.3;PSO 算法的種群大小為20，慣性權(quán)重為0.9，認(rèn)知權(quán)重c1和c2都設(shè)置為2.0，產(chǎn)生200 個(gè)初始解。將ADE-SFLA 算法與文獻(xiàn)［4］改進(jìn)的算法(簡(jiǎn)記為DE-SFLA)、SFLA、DE 算法進(jìn)行對(duì)比實(shí)驗(yàn)。

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

為了消除隨機(jī)性對(duì)算法運(yùn)行結(jié)果的影響，每個(gè)測(cè)試函數(shù)都分別獨(dú)立運(yùn)行30 次，4 種算法對(duì)6 個(gè)測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果如表1 所示。

表1 固定迭代次數(shù)收斂的實(shí)驗(yàn)結(jié)果

表1 的數(shù)據(jù)顯示，ADE-SFLA 的最優(yōu)解、平均最優(yōu)解都優(yōu)于基本的SFLA 和DE，也優(yōu)于趙鵬軍等人的改進(jìn)算法DE-SFLA，說(shuō)明算法后期更夠進(jìn)行更精確的局部搜索，使得求解精度得到有效的提高，標(biāo)準(zhǔn)差也較小，表明ADE-SFLA 穩(wěn)定性更好。在運(yùn)行時(shí)間上，記錄了ADE-SFLA 分別采用PSO 生成初始解的運(yùn)行時(shí)間和算法全局迭代運(yùn)行時(shí)間，雖然生成初始解花費(fèi)了一點(diǎn)時(shí)間，但有了高質(zhì)量的初始解，使ADE-SFLA 進(jìn)入迭代后的速度明顯快于DE-SFLA的速度。

圖1～圖6 為4 種算法分別對(duì)6 個(gè)函數(shù)搜索最優(yōu)解的進(jìn)化曲線。可見(jiàn)，ADE-SFLA 的初始解要優(yōu)于DE-SFLA、SFLA 以及DE，普遍適應(yīng)度值較優(yōu)、多樣性較好的初始解有利于算法的全局搜索，不易陷入局部極值。ADE-SFLA 的收斂速度及收斂精度也優(yōu)于與之比較的3 個(gè)算法，表明本文提出的選擇機(jī)制能夠繼承SFLA 和DE 各自的優(yōu)勢(shì)，算法前期有較快的尋優(yōu)速度，后期使粒子保持良好的多樣性，進(jìn)行更精確的局部搜索，無(wú)論面對(duì)簡(jiǎn)單的單峰函數(shù)還是復(fù)雜的多峰函數(shù)都有較好的收斂性能。進(jìn)一步論證了本文改進(jìn)算法是可靠、有效的優(yōu)化算法。

圖1 各算法對(duì)Sphere 函數(shù)的尋優(yōu)進(jìn)化曲線

圖2 各算法對(duì)Rosenbrock 函數(shù)的尋優(yōu)進(jìn)化曲線

圖3 各算法對(duì)Rastrigin 函數(shù)的尋優(yōu)進(jìn)化曲線

圖4 各算法對(duì)Griewank 函數(shù)的尋優(yōu)進(jìn)化曲線

圖5 各算法對(duì)Ackely 函數(shù)的尋優(yōu)進(jìn)化曲線

圖6 各算法對(duì)Schafferf7 函數(shù)的尋優(yōu)進(jìn)化曲線

5 結(jié)束語(yǔ)

本文提出一種改進(jìn)的混合蛙跳算法。該算法借鑒PSO 算法運(yùn)行速度較快這一特點(diǎn)，在短時(shí)間內(nèi)產(chǎn)生一組滿足約束條件的初始解，以提高初始解的質(zhì)量;根據(jù)SFLA 算法和DE 算法各自的特點(diǎn)，設(shè)計(jì)一個(gè)改進(jìn)的選擇機(jī)制，在搜索過(guò)程中自適應(yīng)地輪替使用這2 種算法，有效地結(jié)合了2 種算法各自的優(yōu)勢(shì)。仿真實(shí)驗(yàn)結(jié)果表明，ADE-SFLA 算法無(wú)論是面對(duì)簡(jiǎn)單的單峰函數(shù)還是復(fù)雜的多峰函數(shù)都有較好的收斂性能，是一種可靠的全局優(yōu)化算法。今后研究方向?yàn)?將該算法應(yīng)用到軟件測(cè)試當(dāng)中，解決軟件測(cè)試用例集的精簡(jiǎn)問(wèn)題，以提高軟件測(cè)試工作的效率。

［1］楊淑瑩，張 樺.群體智能與仿生計(jì)算:Matlab 技術(shù)實(shí)現(xiàn)［M］.北京:電子工業(yè)出版社，2012.

［2］葛 宇，王學(xué)平，梁 靜，等.自適應(yīng)混沌變異蛙跳算法［J］.計(jì)算機(jī)應(yīng)用研究，2011，28(3):945-947.

［3］趙鵬軍，劉三陽(yáng).求解復(fù)雜函數(shù)優(yōu)化問(wèn)題的混合蛙跳算法［J］.計(jì)算機(jī)應(yīng)用研究，2009，26(7):2435-2437.

［4］趙鵬軍，邵澤軍.一種新的改進(jìn)的混合蛙跳算法［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48(8):48-50.

［5］唐德玉，蔡先發(fā)，齊德昱，等.基于量子粒子群搜索策略的混合蛙跳算法［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48(29):29-33.

［6］李希婷，孫 璐，錢(qián)永亮，等.基于改進(jìn)混合蛙跳算法的SVM 分類算法［J］.信息化研究，2011，37(5):41-44.

［7］Kenndy J，Eberhart R C.Particle Swarm Optimization［C］// Proc.of IEEE Int'l Conf.on Neural Networks.Perth，Australia:［s.n.］，1995，4(2):1942-1948.

［8］Sun Chaoli，Zeng Jianchao，Pan Jengshyang.A New Method for Constrained Optimization Problems to Produce Initial Values［C］//Proc.of Chinese Control and Decision Conference.Guilin，China:［s.n.］，2009:2679-2681.

［9］Storn R，Rrice K V.Differential Evolution——A Simple and Efficient Heuristic for Global Optimization over Continuous Space［J］.Journal of Global Optimization，1997，11(4):341-359.

［10］李愛(ài)國(guó)，覃 征，鮑復(fù)民，等.粒子群優(yōu)化算法［J］.計(jì)算機(jī)工程與應(yīng)用，2002，38(21):1-3，17.

［11］程 適，史玉回.基于L1 范式的粒子群算法群體多樣性研究［J］.計(jì)算機(jī)科學(xué)，2011，38(7):190-193.

［12］劉悅婷，趙小強(qiáng).一種自適應(yīng)慣性權(quán)重的混合蛙跳算［J］.計(jì)算機(jī)工程，2012，38(12):132-135.