趙付青,陳自豪

(1.蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院,甘肅 蘭州　730050;

2.西北工業(yè)大學(xué) 現(xiàn)代設(shè)計(jì)與集制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,陜西 西安　710072)

?

基于自適應(yīng)變異因子策略的混合蛙跳算法

趙付青1,2,陳自豪1

(1.蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院,甘肅 蘭州730050;

2.西北工業(yè)大學(xué) 現(xiàn)代設(shè)計(jì)與集制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,陜西 西安710072)

摘要由于基本混合蛙跳算法在對(duì)問題的優(yōu)化求解中存在著收斂速度慢、優(yōu)化精度低且容易陷入局部最優(yōu)等問題,因此提出了一種新的混合蛙跳算法。對(duì)基本混合蛙跳算法的組內(nèi)更新策略進(jìn)行重新設(shè)計(jì),引入自適應(yīng)變異因子來控制青蛙的移動(dòng)步長(zhǎng)；在算法中將改進(jìn)的粒子群優(yōu)化算法有機(jī)地嵌入其中,這樣算法在搜索過程中就增加了發(fā)現(xiàn)新解的概率,維持了種群的多樣性,從而使算法不易陷入局部最優(yōu)。通過對(duì)標(biāo)準(zhǔn)函數(shù)進(jìn)行優(yōu)化測(cè)試,結(jié)果證明其具有良好的優(yōu)化性能。

關(guān)鍵詞混合蛙跳算法；自適應(yīng)變異因子；移動(dòng)步長(zhǎng)；粒子群優(yōu)化算法

混合蛙跳算法(SFLA,shuffled frog leaping algorithm)是2003年由Eusuff和Lansey提出的一種基于群體智能的生物進(jìn)化算法[1]。它具有參數(shù)少、概念簡(jiǎn)單、計(jì)算速度快、全局尋優(yōu)能力強(qiáng)及易于實(shí)現(xiàn)等特點(diǎn)。目前該算法在改進(jìn)和應(yīng)用方面都得到了相應(yīng)提高,并且利用它解決了許多實(shí)際優(yōu)化問題,如函數(shù)優(yōu)化、水資源網(wǎng)絡(luò)分配問題、成品油管網(wǎng)優(yōu)化設(shè)計(jì)、車間調(diào)度問題、旅行商問題等[2-4]。然而它還是存在著許多缺點(diǎn),如收斂速度較慢、優(yōu)化精度相對(duì)低、易陷入局部最優(yōu)等,尤其在解決高維函數(shù)問題時(shí),這些缺點(diǎn)表現(xiàn)的更明顯,從而算法的效率非常低。因此改進(jìn)基本混合蛙跳算法,提高算法性能就變得非常急切。目前,研究者們用不同的方法對(duì)算法的各個(gè)過程進(jìn)行改進(jìn)。文獻(xiàn)[5-10]中介紹了國(guó)內(nèi)和國(guó)外學(xué)者們對(duì)基本混合算法進(jìn)行的改進(jìn),確實(shí)提高了算法的優(yōu)化性能。但是現(xiàn)有的混合蛙跳算法的優(yōu)化性能依舊比較低,所以需要對(duì)其進(jìn)行進(jìn)一步的改進(jìn)和研究。

我們重新設(shè)計(jì)了混合蛙跳算法的組內(nèi)更新策略,引入自適應(yīng)變異因子來動(dòng)態(tài)控制青蛙移動(dòng)步長(zhǎng),并將粒子群優(yōu)化算法有機(jī)地嵌入其中,從而增加算法發(fā)現(xiàn)新解的概率,提高了解的多樣性,避免算法陷入局部最優(yōu),提高了算法的優(yōu)化性能。

1混合蛙跳算法

1.1算法描述

SFLA是一種新型的后啟發(fā)式群體智能進(jìn)化算法。它的實(shí)現(xiàn)機(jī)理是通過模擬現(xiàn)實(shí)自然環(huán)境中青蛙群體在覓食過程中所體現(xiàn)的信息交互和協(xié)同合作行為,來完成對(duì)問題的求解過程。采用模因分組方法把種群分成若干個(gè)子種群,每個(gè)子種群稱為模因分組,種群中青蛙被定義為問題解。模因組中的每個(gè)青蛙都有努力靠近目標(biāo)的想法,具有對(duì)食物源遠(yuǎn)近的判斷能力,并隨著模因分組的進(jìn)化而進(jìn)化。在模因組的每一次進(jìn)化過程中,找到組內(nèi)位置最差和最好的青蛙。組內(nèi)最差青蛙要按照一定更新策略來進(jìn)行位置調(diào)整。對(duì)每個(gè)模因組進(jìn)行一定次數(shù)的模因進(jìn)化后,把所有模因分組重新混合成新的群體,實(shí)現(xiàn)各個(gè)模因組交流與共享彼此間的信息,算法一直執(zhí)行到種群預(yù)定的進(jìn)化次數(shù)才結(jié)束。

SFLA中信息傳遞是通過種群分類來實(shí)現(xiàn)的,它相間進(jìn)行局部進(jìn)化和重新混合過程,有效地將全局信息交互和局部搜索相結(jié)合,具有很強(qiáng)的全局搜索能力。

1.2算法數(shù)學(xué)模型

混合蛙跳算法首先隨機(jī)初始化P個(gè)解來組成青蛙的初始種群,例如解決d維的優(yōu)化問題時(shí),可以把第i個(gè)解記作Xi=(xi1,xi2,…,xid),適應(yīng)度值可記作Y=f(Xi),Y是目標(biāo)函數(shù)值。根據(jù)適應(yīng)度將P只青蛙按從大到小排列,然后對(duì)種群進(jìn)行分組,把它分為n個(gè)模因組,每組有s個(gè)青蛙(解)。把第一只青蛙分配到第一個(gè)模因組,第二只青蛙分配到第二個(gè)模因組,直到第n只青蛙分配到第n個(gè)模因組；接著把第n+1只青蛙分配到第1個(gè)模因組,第n+2只青蛙分配到第2個(gè)模因組,依次類推,直到所有解分配完畢。模因組中最差青蛙記為Xw,最好青蛙記為Xb,整個(gè)種群中位置最好的青蛙則記為Xg,其中Xb=(xb1,xb2,…,xbd),Xw=(xw1,xw2,…,xwd),Xg=(xg1,xg2,…,xgd)。在模因組中執(zhí)行局部搜索,適應(yīng)度值最差的青蛙得到更新,其公式如下:

ΔX=rand()×(Xb-Xw),

(1)

newXw=Xw+ΔX,ΔXmax≥ΔX≥-ΔXmax

(2)

其中:newXw為最差解Xw更新后的新解,newXw=(newxw1,newxw2,…,newxwd);ΔX為青蛙的最大移動(dòng)步長(zhǎng);rand()表示0～1之間的隨機(jī)數(shù)。計(jì)算新解,如果得到了更優(yōu)的解,則用newxw取代Xw,否則則用Xg代替式(1)中的Xb,重新計(jì)算新解。如果產(chǎn)生新解的適應(yīng)度值還沒被改善,那么就隨機(jī)生成新解。重復(fù)執(zhí)行以上更新過程對(duì)模因組進(jìn)行模因進(jìn)化,當(dāng)達(dá)到設(shè)定的迭代次數(shù)后模因進(jìn)化結(jié)束,重新混合所有模因組成新的種群,再對(duì)新種群按照上面分配原則重新劃分模因組,然后繼續(xù)對(duì)每個(gè)模因組進(jìn)行模因進(jìn)化。如此反復(fù),直到滿足終止條件。

1.3算法流程

步驟1隨機(jī)生成包含P個(gè)解的初始種群P=N×S,青蛙的最大移動(dòng)步長(zhǎng)設(shè)為ΔXmax,子種群間最大混合迭代次數(shù)設(shè)為G,子種群內(nèi)迭代次數(shù)設(shè)為T;

步驟2計(jì)算種群中每個(gè)解的適應(yīng)度值,并用Xg表示全局最優(yōu)解；

步驟3按照適應(yīng)度值對(duì)種群中P個(gè)解進(jìn)行降序排列,然后把種群劃分為N個(gè)子種群,每個(gè)子種群體中含有S個(gè)解;

步驟4根據(jù)適應(yīng)度值找到每個(gè)子種群中的最差解和最優(yōu)解,將它們分別記作Xw和Xb,以及當(dāng)前種群的最優(yōu)解Xg,利用更新策略,對(duì)子種群的最差解Xw進(jìn)行更新;

步驟5判斷是否達(dá)到子群內(nèi)的最大迭代次數(shù),如果沒有就轉(zhuǎn)到步驟4,否則重新混合所有子種群,構(gòu)造下一代種群;

步驟6判斷終止條件。群間迭代如果達(dá)到終止條件就結(jié)束,算法結(jié)束并輸出最優(yōu)解Xg;否則轉(zhuǎn)向步驟2。

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

2.1引入自適應(yīng)變異因子

引入自適應(yīng)變異因子主要是對(duì)青蛙的移動(dòng)步長(zhǎng)進(jìn)行動(dòng)態(tài)調(diào)整。因?yàn)樵谒惴ㄟM(jìn)化的初期階段應(yīng)加大移動(dòng)步長(zhǎng),擴(kuò)大搜索范圍,使青蛙快速向更好的方向跳動(dòng),從而加快算法的收斂速度。但是在進(jìn)化的后期應(yīng)該減小青蛙的移動(dòng)步長(zhǎng),縮小搜尋空間,讓算法進(jìn)行深度局部搜索,避免跳出最好解。同時(shí)組內(nèi)青蛙的平均值比最優(yōu)青蛙更能代表組內(nèi)青蛙所處的位置,因此用組內(nèi)平均值代替最優(yōu)解來對(duì)最差解進(jìn)行更新。在基本算法中更新最差解時(shí),最差青蛙的移動(dòng)起點(diǎn)總是從自身出發(fā),這樣產(chǎn)生的解還保留了最差青蛙部分壞的信息,容易產(chǎn)生一些劣質(zhì)解,影響算法的收斂速度。文獻(xiàn)[10]中提到了青蛙個(gè)體對(duì)自己的歷史最優(yōu)解存在記憶功能,因此采用以從組內(nèi)最優(yōu)青蛙和最差青蛙的歷史最優(yōu)解之間的隨機(jī)點(diǎn)出發(fā)和從自身出發(fā)的隨機(jī)混合方式來更新最差青蛙,這樣不僅能提高解的質(zhì)量,而且還增加種群多樣性。具體的更新策略為

(3)

其中:Δx代表青蛙的移動(dòng)步長(zhǎng);Δxmax是Δx的最大值;r1、r2和r3是0~1之間的隨機(jī)數(shù);Xa代表青蛙組內(nèi)的平均值;Xw和 Xb分別是組內(nèi)的最優(yōu)和最差解;Xh是最差青蛙的歷史最優(yōu)值;K是自適應(yīng)變異算子,它的值是隨著進(jìn)化的過程呈線性遞減的;Ke和Ks分別是K取值的最小值和最大值。

2.2嵌入粒子群優(yōu)化算法

粒子群優(yōu)化(PSO,particleswarmoptimization)算法是一種有效的全局尋優(yōu)算法,目前它已經(jīng)被廣泛應(yīng)用于數(shù)值的優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、數(shù)據(jù)挖掘等應(yīng)用領(lǐng)域。在PSO中,可以用三元組(Xi,Vi,Pi)來表示i粒子,其中Xi=(xi1,xi2,…,xid)T為其目前位置;Vi=(vi1,vi2,…,vid)T為其目前速度;Pi=(pi1,pi2,…,pid)T為其經(jīng)過的最優(yōu)位置；又設(shè)全局最優(yōu)位置Pg=(pg1,pg2,…,pgd)T∈S ,則i粒子的速度進(jìn)化公式為

vij(t+1)=wvij(t)+c1r1(pij(t)-xij(t))+

c2r2(pgj(t)-xij(t)),

1≤i≤s,1≤j≤d

(4)

其中:r1,r2表示(0,1)之間的隨機(jī)生成數(shù),w代表慣性權(quán)重;c1與c2代表加速正常數(shù)。文獻(xiàn)[9]中提出了一種帶有遞減擾動(dòng)項(xiàng)的改進(jìn)粒子群算法(DDPSO),由于SFLA和DDPSO在搜索機(jī)制方面具有各自的優(yōu)點(diǎn),把它們相結(jié)合可以提高算法搜索新解的能力,同時(shí)也擴(kuò)大算法的搜索空間,使其不易陷入局部最優(yōu)。改進(jìn)混合蛙跳算法表述如下:

初始化種群及參數(shù):種群大小為P,子種群個(gè)數(shù)為S ,子種群內(nèi)最大迭代次數(shù)為N,種群間混合迭代次數(shù)為 G。

Fori=1∶G

If mod(I,R)~=0

用組內(nèi)更新策略改進(jìn)的SFLA進(jìn)行搜索

Else

用DDPSO算法進(jìn)行搜索

End

End

其中R為算法交替的控制參數(shù),mod( )代表取余函數(shù),SFLA和DDPSO相結(jié)合維持了種群的多樣性,提高了整個(gè)算法的性能。

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

3.1實(shí)驗(yàn)設(shè)計(jì)

為驗(yàn)證改進(jìn)SFLA的優(yōu)化性能,采用如表1所列的Sphere,Rosenbrock,Rastrigin,Griewank,Ackley和Schaffer’s f6等標(biāo)準(zhǔn)測(cè)試函數(shù)對(duì)SFLA和ISFLA進(jìn)行仿真實(shí)驗(yàn)比較。實(shí)驗(yàn)代碼用MATLAB實(shí)現(xiàn),電腦用個(gè)人PC機(jī),操作系統(tǒng)是Windows 7,CPU為Core i3,內(nèi)存是2 G。6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的3D圖見圖1。

參數(shù)設(shè)置:P=300,N=10,S=30,T=20,G=500,TS=8,Te=4,R=10,其他需要的參數(shù)配置和文獻(xiàn)[9]中一致?；維FLA和改進(jìn)SFLA兩個(gè)算法的相關(guān)參數(shù)相同,它們分別對(duì)6個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行30次。

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

改進(jìn)SFLA和基本SFLA的實(shí)驗(yàn)對(duì)比結(jié)果見表2。從表2的實(shí)驗(yàn)結(jié)果可以明顯看出,ISFLA的優(yōu)化結(jié)果要比SFLA的好,而且ISFLA 的標(biāo)準(zhǔn)差要小于SFLA,表明ISFLA的穩(wěn)定性也要好于SFLA。ISFLA采用自適應(yīng)變異因子,動(dòng)態(tài)地控制青蛙移動(dòng)步長(zhǎng),從而平衡了算法的開發(fā)與探索,提高了其收斂速度；同時(shí)把SFLA和DDPSO相結(jié)合,利用它們各自的尋優(yōu)特性,增強(qiáng)了整個(gè)算法的優(yōu)化性能。ISFLA不容易陷入局部最優(yōu),有很強(qiáng)的全局尋優(yōu)能力,而且其魯棒性很強(qiáng)。

表1　6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)

圖1　6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的3D圖Fig.1　3D diagram of six standard test functions

測(cè)試函數(shù)基本SFLA最優(yōu)值平均值標(biāo)準(zhǔn)差改進(jìn)SFLA最優(yōu)值平均值標(biāo)準(zhǔn)差理論最優(yōu)值f11.241e-51.837e-31.564e-31.846e-93.548e-81.172e-80f22.736e+19.645e+16.076e+11.008e+11.862e+11.584e+10f31.718e+08.945e+05.236e+01.254e+07.789e+04.831e+00f43.364e-18.075e-16.183e-13.047e-33.142e-24.164e-20f52.885e-36.885e-25.574e-23.468e-57.557e-45.632e-40f65.036e+05.988e+05.652e+02.975e+04.633e+04.138e+00

為了驗(yàn)證改進(jìn)SFLA的收斂性能,上述6個(gè)測(cè)試函數(shù)采用兩種算法運(yùn)行30次后求得的平均適應(yīng)度進(jìn)化曲線見圖2,圖2中迭代進(jìn)化代數(shù)G由橫坐標(biāo)表示,每一代的平均最優(yōu)適應(yīng)值由縱坐標(biāo)表示。

圖2　6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的平均進(jìn)化曲線Fig.2　The average evolutionary curve of six standard test functions

從圖2可以明顯看出,ISFLA的收斂速度比基本 SFLA的快,在算法進(jìn)化初始階段就能快速收斂到理論最優(yōu)解附近,然后向理論最優(yōu)解不斷地靠近,收斂性能非常好。比較算法對(duì)被測(cè)函數(shù)的求解精度,表3列出了它們的目標(biāo)收斂精度,維數(shù)設(shè)置為30,對(duì)ISFLA算法獨(dú)立運(yùn)行30次,實(shí)驗(yàn)結(jié)果由表4所列。

通過表4中的結(jié)果可以得知,在指定的目標(biāo)收斂精度下對(duì)以上6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行優(yōu)化,ISFLA的成功率很高,一般都能達(dá)到 90%以上,而SFLA算法的成功率相對(duì)比較低,大部分都很難達(dá)到指定的精度,因此可以說明ISFLA算法在求解優(yōu)化問題中有較高的成功率。

表3　6個(gè)測(cè)試函數(shù)的目標(biāo)收斂精度

表4　改進(jìn)SFLA和基本SFLA的平均迭代次數(shù)對(duì)比

綜上所述,我們提出的改進(jìn)算法克服了基本混合蛙跳算法的一些缺點(diǎn),提高了算法的收斂速度和尋優(yōu)精度,同時(shí)算法也不易陷入局部最優(yōu),提高了算法的優(yōu)化性能。

4結(jié)論

在基本混合蛙跳算法的基礎(chǔ)上,在其組內(nèi)更新策略中引入自適應(yīng)變異因子,對(duì)青蛙的移動(dòng)步長(zhǎng)進(jìn)行有效地動(dòng)態(tài)調(diào)整。在對(duì)最差解更新策略中采用以從最優(yōu)解和最差解的歷史最優(yōu)值之間隨機(jī)點(diǎn)出發(fā)和從自身出發(fā)混合進(jìn)行的模式,提高了解的質(zhì)量,從而加快了算法的收斂速度。在全局信息交換過程中將粒子群優(yōu)化算法有機(jī)地嵌入其中,增加了在搜索過程中發(fā)現(xiàn)新解的概率,提高了解的多樣性,使算法不易陷入局部最優(yōu)。最后通過仿真實(shí)驗(yàn)表明改進(jìn)算法的性能更好,今后要對(duì)改進(jìn)算法在實(shí)際應(yīng)用方面進(jìn)行研究。

參考文獻(xiàn):

[1]Eusuff M M,Lansey K E.Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm[J].Journal of Water Resources Planning and Management,2003,129(3):210-225.

[2]Poli R,Kennedy J,Blackwell T.Particle Swarm Optimization[J].Swarm Intelligence,2007,1(1):33-57.

[3]Niknam T,Farsani E A,Nayeripour M,etal.A New Tribe Modified Shuffled Frog Leaping Algorithm For Multi-objective Distribution Feeder Reconfiguration Considering Distributed Generator Units[J].European Transactions on Electrical Power,2012,22(3):308-333.

[4]Amiri B,Fathian M,Maroosi A.Application of Shuffled Frog Leaping Algorithm on Clustering[J].International Journal of Advanced Manufacturing Technology,2009,45(1-2):199-209.

[5]Elbeltagi E,Hegazy T,Grierson D.A Modified Shuffled Frog-leaping Optimization Algorith-m:Applications to Project Management[J].Structure and Infrastructure Engineering,2007,3(1):53-60.

[6]Khorsandi A,Alimardani A,Vahidi B,etal.Hybrid Shuffled Frog Leaping Algorithm and Nelder-Mead Simplex Search for Optimal Reactive Power Dispatch[J].IET Generation,Transmission & Distribution,2011,5(2):249-256.

[7]Roy P,Chakrabarti A.Modified Shuffled Frog Leaping Algorithm for Solving Economic Load Dispatch Problem[J].Energy and Power Engineering,2011,3(4):551.

[8]Rahimi-Vahed A,Mirzaei A H.Solving a Bi-criteria Permutation Flow-shop Problem Using Shuffled Frog-leaping Algorithm[J].Soft Computing,2008,12(5):435-452.

[9]趙付青,唐建新,張秋余.一種帶有遞減擾動(dòng)項(xiàng)的粒子群優(yōu)化算法[J].蘭州理工大學(xué)學(xué)報(bào),2011,37(6):88-93.

[10]代永強(qiáng),王聯(lián)國(guó).帶記憶功能的混合蛙跳算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2011,32(9):3 170-3 173,3 202.

Shuffled Frog-Leaping Algorithm Based on the Theory of Adaptive Mutation Factors

Zhao Fuqing1,2,Chen Zihao1

(1.SchoolofComputerandCommunication,LanzhouUniversityofTechonlogy,Lanzhou730050,China;2.KeyLaboratoryofContemporaryDesign,IntegratedManufacturingTechnology,MinistryofEducation,NorthwesternPolyTechnicalUniversity,Xi’an710072,China)

AbstractShuffled frog-leaping algorithm is an optimized solution,but its local search ability is weak,optimization accuracy is low and it is easily caught in local optimum.In this paper,a modified SFLA is proposed to overcome the disadvantages.This new algorithm reconstructs the initial SFLA by redesigning its update strategy within the group and using adaptive mutation factors to control frogs' step length.This new algorithm contains the improved particle swarm optimization as an integrated part which increases the chances of finding new solutions in the process of searching,maintains population diversity and avoids being trapped in local optimum.And an optimization test on criteria functions proved a good optimal performance of SFLA.

Key wordsShuffled frog-leaping algorithm;Adaptive mutation factors;Step length;Particle swarm optimization

中圖分類號(hào):TP391

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1004-0366(2016)01-0006-06

作者簡(jiǎn)介:趙付青(1977-),男,甘肅酒泉人,博士,教授,研究方向?yàn)閺?fù)雜系統(tǒng)、計(jì)算智能.E-mail:7673385510@qq.com.

基金項(xiàng)目:國(guó)家自然科學(xué)基金(51365030).

收稿日期:2015-03-31;修回日期:2015-05-06.

doi:10.16468/j.cnki.issn1004-0366.2016.01.002.

引用格式:Zhao Fuqing,Chen Zihao.Shuffled Frog-Leaping Algorithm Based on the Theory of Adaptive Mutation Factors[J].Journal of Gansu Sciences,2016,28(1):6-11.[趙付青,陳自豪.基于自適應(yīng)變異因子策略的混合蛙跳算法[J].甘肅科學(xué)學(xué)報(bào),2016,28(1):6-11.]