基于自適應變異因子策略的混合蛙跳算法

趙付青,陳自豪

(1.蘭州理工大學 計算機與通信學院,甘肅 蘭州　730050;

2.西北工業(yè)大學 現代設計與集制造技術教育部重點實驗室,陜西 西安　710072)

?

基于自適應變異因子策略的混合蛙跳算法

趙付青1,2,陳自豪1

(1.蘭州理工大學 計算機與通信學院,甘肅 蘭州730050;

2.西北工業(yè)大學 現代設計與集制造技術教育部重點實驗室,陜西 西安710072)

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

關鍵詞混合蛙跳算法；自適應變異因子；移動步長；粒子群優(yōu)化算法

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

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

1混合蛙跳算法

1.1算法描述

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

SFLA中信息傳遞是通過種群分類來實現的,它相間進行局部進化和重新混合過程,有效地將全局信息交互和局部搜索相結合,具有很強的全局搜索能力。

1.2算法數學模型

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

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

(1)

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

(2)

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

1.3算法流程

步驟1隨機生成包含P個解的初始種群P=N×S,青蛙的最大移動步長設為ΔXmax,子種群間最大混合迭代次數設為G,子種群內迭代次數設為T;

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

步驟3按照適應度值對種群中P個解進行降序排列,然后把種群劃分為N個子種群,每個子種群體中含有S個解;

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

步驟5判斷是否達到子群內的最大迭代次數,如果沒有就轉到步驟4,否則重新混合所有子種群,構造下一代種群;

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

2改進的混合蛙跳算法

2.1引入自適應變異因子

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

(3)

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

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

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

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)之間的隨機生成數,w代表慣性權重;c1與c2代表加速正常數。文獻[9]中提出了一種帶有遞減擾動項的改進粒子群算法(DDPSO),由于SFLA和DDPSO在搜索機制方面具有各自的優(yōu)點,把它們相結合可以提高算法搜索新解的能力,同時也擴大算法的搜索空間,使其不易陷入局部最優(yōu)。改進混合蛙跳算法表述如下:

初始化種群及參數:種群大小為P,子種群個數為S ,子種群內最大迭代次數為N,種群間混合迭代次數為 G。

Fori=1∶G

If mod(I,R)~=0

用組內更新策略改進的SFLA進行搜索

Else

用DDPSO算法進行搜索

End

End

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

3實驗方法與結果分析

3.1實驗設計

為驗證改進SFLA的優(yōu)化性能,采用如表1所列的Sphere,Rosenbrock,Rastrigin,Griewank,Ackley和Schaffer’s f6等標準測試函數對SFLA和ISFLA進行仿真實驗比較。實驗代碼用MATLAB實現,電腦用個人PC機,操作系統是Windows 7,CPU為Core i3,內存是2 G。6個標準測試函數的3D圖見圖1。

參數設置:P=300,N=10,S=30,T=20,G=500,TS=8,Te=4,R=10,其他需要的參數配置和文獻[9]中一致?；維FLA和改進SFLA兩個算法的相關參數相同,它們分別對6個測試函數獨立運行30次。

3.2實驗結果與分析

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

表1　6個標準測試函數

圖1　6個標準測試函數的3D圖Fig.1　3D diagram of six standard test functions

測試函數基本SFLA最優(yōu)值平均值標準差改進SFLA最優(yōu)值平均值標準差理論最優(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

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

圖2　6個標準測試函數的平均進化曲線Fig.2　The average evolutionary curve of six standard test functions

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

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

表3　6個測試函數的目標收斂精度

表4　改進SFLA和基本SFLA的平均迭代次數對比

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

4結論

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

參考文獻:

[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]趙付青,唐建新,張秋余.一種帶有遞減擾動項的粒子群優(yōu)化算法[J].蘭州理工大學學報,2011,37(6):88-93.

[10]代永強,王聯國.帶記憶功能的混合蛙跳算法[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

中圖分類號:TP391

文獻標志碼:A

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

作者簡介:趙付青(1977-),男,甘肅酒泉人,博士,教授,研究方向為復雜系統、計算智能.E-mail:7673385510@qq.com.

基金項目:國家自然科學基金(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.[趙付青,陳自豪.基于自適應變異因子策略的混合蛙跳算法[J].甘肅科學學報,2016,28(1):6-11.]