基于混合優(yōu)化策略的微分進化改進算法

基于混合優(yōu)化策略的微分進化改進算法

1基于混合優(yōu)化策略的de算法全球優(yōu)化問題通常存在于數(shù)學(xué)、科學(xué)、控制等科學(xué)研究領(lǐng)域，因此成為人們長期研究的熱點。集成智能優(yōu)化算法（ga）、模擬退火模型（sa）和微群算法（pso）為代表，為解決優(yōu)化問題提供了一種新方法。這些算法模擬了自然界的一些自然現(xiàn)象，并形成了進化過程和規(guī)則。計算機可以模仿自然的進化過程，進行優(yōu)化計算，解決科學(xué)研究中的優(yōu)化問題。1995年RainerStorn和KennethPrice提出的微分進化算法(differentialevolutionalgorithm,以下簡稱DE算法)是一種實數(shù)編碼的基于種群進化的全局優(yōu)化算法,己被證明在求優(yōu)過程中具有高效性、收斂性、魯棒性等優(yōu)點.DE算法已在濾波器設(shè)計、神經(jīng)網(wǎng)絡(luò)參數(shù)訓(xùn)練、聚類分析、機器人路徑規(guī)劃等工程領(lǐng)域得到應(yīng)用并取得了良好的效果.DE基本算法的核心思想是利用隨機偏差擾動產(chǎn)生新的中間個體.其產(chǎn)生中間個體的方式?jīng)Q定了DE算法在許多問題上都有很好的收斂表現(xiàn),但搜索速度則相對緩慢.如果優(yōu)化問題是計算成本很高即每計算一次目標函數(shù)值都需要很長時間的問題,那么過多次數(shù)的計算目標函數(shù)值就會使得算法不可行,因此減少算法收斂所需目標函數(shù)評價次數(shù)和收斂時間就具有很強的現(xiàn)實意義.最新的DE改進算法有AnyongQing提出的動態(tài)微分進化算法(簡稱DDE),其基本思想是對種群中的個體進行動態(tài)更新,而不是等所有個體都更新完畢后再以新種群替代舊種群.PaulKBergey提出了MDE算法,MDE將種群中的個體按適應(yīng)度排序,適應(yīng)度更高的個體以較大的概率被選中作為變異操作的父體.JianyongSun等將DE算法和EDA算法進行了混合,提出了DE/EDA混合算法.PKaelo等提出了DERL算法和DELB算法,其中,DERL算法主要是對參與變異操作的三個個體按適應(yīng)度值高低排序,并將適應(yīng)度最高的個體作為基點向量,DELB算法則對算法的選擇操作進行了改進,使種群中的個體在每次迭代過程中有多次的改善機會.這些改進算法都不同程度地提高了DE算法的性能.應(yīng)該說,DE算法在搜索成功率性能方面已非常出色,但在搜索速度上仍有提高的空間.在實際應(yīng)用中,DE算法可以采用不同的優(yōu)化策略,本文在對DE各優(yōu)化策略進行分析的基礎(chǔ)上提出了基于混合優(yōu)化策略的微分進化改進算法.2變異、交叉DE算法是求解有n個連續(xù)變量全局優(yōu)化問題的算法.全局優(yōu)化問題都可以轉(zhuǎn)化為求解如下的最小化問題:minf(X)(1)其中X=(x1,x2,…,xn)∈D?Rn是連續(xù)變量,目標函數(shù)f:D→R可能是不可微的.同所有的進化優(yōu)化算法一樣,DE算法也是對候選解的種群進行操作.DE利用實數(shù)值參數(shù)向量作為每一代的種群,DE的中間個體是通過把種群中兩個個體之間的加權(quán)差向量加到第三個個體上來產(chǎn)生的,這稱為“變異”;然后將中間個體的參數(shù)與當(dāng)前個體的參數(shù)按照一定規(guī)則混合來產(chǎn)生所謂的候選個體,通常稱為“交叉”;如果候選個體的目標函數(shù)值小于當(dāng)前個體的目標函數(shù)值,候選個體就在下一代中代替當(dāng)前個體,這一操作稱為“選擇”.種群中所有個體都要被作為當(dāng)前個體進行一次變異、交叉和選擇操作.這種利用隨機偏差擾動產(chǎn)生新個體的方式可以獲得一個具有非常好收斂性質(zhì)的自適應(yīng)程序.DE基本算法的流程以及變異、交叉、選擇算子的詳細描述請見參考文獻,此處不再贅述.DE算法中有三個控制參數(shù):F、CR、NP.其中F和CR影響搜索過程的魯棒性和算法的收斂速度.種群規(guī)模NP取值一般為2D～20D,且至少應(yīng)大于4.F取值范圍一般為0.4～1.0,建議初始值選為0.5.CR初始值建議選為0.5.DE算法有幾種變形,即有不同的優(yōu)化策略.為了區(qū)分不同的DE算法,通常將DE表示為:DE/x/y/z.其中x表示變異操作中的基點向量是隨機選取的還是選擇當(dāng)前種群中的最優(yōu)個體,y表示差分向量的個數(shù),z表示交叉方式,主要有指數(shù)交叉和二項式交叉兩種.一般來說,DE基本算法表示為DE/rand/1/bin,該優(yōu)化策略在實際中應(yīng)用最為廣泛.3提高算法hde3.1schaffer函數(shù)為了更清楚地了解各種優(yōu)化策略下DE算法的性能,本文利用各優(yōu)化策略對2維Schaffer函數(shù)進行了測試,并將搜索成功率、目標函數(shù)評價次數(shù)(numberoffunctionevaluations,以下簡寫為nfe)和收斂時間(t)列于表1.Schaffer函數(shù)的相關(guān)描述和DE算法的參數(shù)設(shè)置見本文第4節(jié).3.2基于混合優(yōu)化策略的微分進化改進算法由表1可見,不同的優(yōu)化策略具有不同的搜索性能.通過目標函數(shù)評價次數(shù)和收斂時間可以看出算法的搜索效率,通過成功率可以看出算法的全局收斂性能.一般來說,如果變異操作中的基點向量是隨機抽取的,則算法全局收斂性好,不易陷入局部最優(yōu),但收斂所需目標函數(shù)評價次數(shù)和收斂時間也偏大;如果變異操作的基點向量選擇了當(dāng)前種群中的最優(yōu)個體,則收斂速度相對較快,但搜索成功率則不高,較易陷入局部最優(yōu).例如DE6算法中變異操作的基點向量選擇了當(dāng)前種群中的最優(yōu)個體,使其收斂速度相對較快,但搜索成功率僅為70%.又如DE7算法中變異操作的基點向量是隨機選取的,因此其全局收斂性好,搜索成功率為100%,但其收斂速度則較DE6緩慢.如果將這兩種優(yōu)化策略進行混合,取長補短,可以預(yù)見算法的性能會有所改善,即在保證算法良好收斂性的同時,加快算法的收斂速度.基于以上思想,本文提出了基于混合優(yōu)化策略的微分進化改進算法(HybridDifferentialEvolutionAlgorithm,以下簡寫為HDE).HDE算法可以有兩種形式,分別記為HDE1、HDE2.HDE1算法的流程圖如圖1所示,即如果按照DE7優(yōu)化策略所得候選個體的適應(yīng)度相對于當(dāng)前個體沒有得到改善,則利用DE6優(yōu)化策略獲得一個新的候選個體,并重新進行選擇操作.HDE2算法則在每次迭代過程中將種群中的個體隨機地分成兩組,每組采用不同的優(yōu)化策略進行優(yōu)化,比如種群中50%個體采用DE7優(yōu)化策略獲得候選個體,另50%個體則采用DE6優(yōu)化策略獲得候選個體,選擇操作不做任何改變,本文所討論的HDE2算法即采用50%比例進行混合優(yōu)化.4hde算法的模擬體驗4.1單峰函數(shù)rastritch為了檢驗HDE算法的性能,選擇了5個常用的優(yōu)化算法測試函數(shù)對算法進行測試,它們分別是sphere函數(shù)(f1)、Rosenbrock函數(shù)(f2)、Rastrigin函數(shù)(f3)、Griewank函數(shù)(f4)和Schaffer函數(shù)(f5).這5個函數(shù)的表達式分別見式(2)～式(6),測試停止迭代條件以及2維圖形如表2所示.除了Schaffer是2維函數(shù)外,其他函數(shù)都用30維變量進行測試.5個函數(shù)中前兩個為單峰函數(shù),只有一個極小值.后三個為多峰函數(shù),有多個局部極小值,其中Rastrigin和Griewank函數(shù)有很大的曲率,可以引導(dǎo)搜索到全局極小,而Schaffer函數(shù)在全局極小附近劇烈震蕩,一般算法難以得到最優(yōu)解.f1(ˉx)=n∑i=1x2i(2)f1(xˉˉ)=∑i=1nx2i(2)f2(ˉx)=n-1∑i=1(100(xi+1-x2i)2+(xi-1)2)(3)f2(xˉˉ)=∑i=1n?1(100(xi+1?x2i)2+(xi?1)2)(3)f3(ˉx)=n∑i=1(x2i-10cos(2πxi)+10)(4)f3(xˉˉ)=∑i=1n(x2i?10cos(2πxi)+10)(4)f4(ˉx)=14000n∑i=1x2i-n∏i=1cos(xi√i)+1(5)f4(xˉˉ)=14000∑i=1nx2i?∏i=1ncos(xii√)+1(5)f5(ˉx)=0.5+sin2√x21+x22-0.5(1+0.001(x21+x22))2(6)f5(xˉˉ)=0.5+sin2x21+x22√?0.5(1+0.001(x21+x22))2(6)4.2pso算法參數(shù)設(shè)置為了使HDE算法的測試結(jié)果更具對比性,我們將HDE與DE基本算法,DE改進算法DDE以及PSO算法進行了比較.每種算法針對5個測試函數(shù)都運行20次,取其搜索成功率,并計算搜索成功情況下的nfe平均值和收斂時間(t).各算法實驗結(jié)果如表3～表7所示.在表3～表7中,DE7代表DE基本算法DE/rand/1/bin,DDE7為基于DE/rand/1/bin策略的斂時間,因此此欄空缺.本文中的所有算法對5個測試函數(shù)設(shè)置的種群數(shù)量都為60個,最大迭代次數(shù)為10000次,算法迭代10000次還沒有達到表2所列的停止條件則認為本次搜索失敗.DE算法其他參數(shù)設(shè)置為:F=0.5,CR=0.5;PSO算法參數(shù)設(shè)置如下:w=0.729;c1=c2=1.494.本文所列DE相關(guān)算法均采用C語言進行編寫,開發(fā)環(huán)境為LabWindows/CVI6.0,這是一個C語言編程環(huán)境,所用計算機為IBM-T30筆記本電腦,主頻2.0GHz,內(nèi)存256M,操作系統(tǒng)為Windows2000.從仿真數(shù)據(jù)可以看出,HDE1和HDE2算法針對5個測試函數(shù)都取得了很好的效果.HDE算法在保證搜索成功率的基礎(chǔ)上,大大降低了收斂所需目標函數(shù)評價次數(shù)和收斂時間.HDE算法對目標函數(shù)的評價次數(shù)和收斂時間與DE基本算法相比減少了50%以上.顯而易見,HDE算法不僅優(yōu)于DE基本算法,總體上也優(yōu)于DDE算法和PSO算法.本文所討論的HDE1算法為DE7優(yōu)化策略和DE6優(yōu)化策略的混合優(yōu)化,HDE2算法則將種群中的個體隨機的分成兩組,一組采用DE7優(yōu)化策略,另一組則采用DE6優(yōu)化策略.在實際應(yīng)用中,可以根據(jù)實際需要,采用不同的優(yōu)化策略組合,或采用不同的比例進行混合優(yōu)化.例如利用HDE2算法針對f5函數(shù)尋優(yōu)時,如果種群中80%個體采用DE7優(yōu)化策略,其