肖瑩瑩, 林廷宇, 李伯虎, 侯寶存,3, 施國強,3

(1.北京市復雜產(chǎn)品先進制造系統(tǒng)工程技術研究中心, 北京仿真中心, 北京 100854;2. 復雜產(chǎn)品智能制造系統(tǒng)技術國家重點實驗室, 北京電子工程總體研究所, 北京 100854;3. 航天系統(tǒng)仿真重點實驗室, 北京仿真中心, 北京 100854)

?

混合蛙跳算法自適應參數(shù)調(diào)整改進策略

肖瑩瑩1,2, 林廷宇1,2, 李伯虎2,3, 侯寶存1,2,3, 施國強1,2,3

(1.北京市復雜產(chǎn)品先進制造系統(tǒng)工程技術研究中心, 北京仿真中心, 北京 100854;2. 復雜產(chǎn)品智能制造系統(tǒng)技術國家重點實驗室, 北京電子工程總體研究所, 北京 100854;3. 航天系統(tǒng)仿真重點實驗室, 北京仿真中心, 北京 100854)

針對基本混合蛙跳算法(shuffled frog leaping algorithm, SFL)在求解高維復雜問題時的不足,本文提出一種自適應參數(shù)調(diào)整的改進策略。首先,利用變公比數(shù)列分析了SFL更新軌跡的收斂性;在此基礎上,利用系統(tǒng)穩(wěn)定性分析方法,提出在SFL更新公式中基于比例系數(shù)和適應度標準差來自適應調(diào)整更新的方法。最后,基于3組共8個標準測試函數(shù)將本文改進SFL與基本SFL和4個改進型粒子群優(yōu)化算法(particle swarm optimization,PSO)作對比,驗證了本文改進策略對各類復雜函數(shù)的高效性;同時,對比了改進SFL與基本SFL和wPSO在求解高維問題時的性能,驗證了改進SFL對高維問題求解的有效性。

混合蛙跳算法; 收斂性; 自適應參數(shù)調(diào)整; 智能計算

0　引　言

作為新興的計算智能技術,以蟻群優(yōu)化算法和粒子群優(yōu)化算法為代表的群體智能優(yōu)化技術受到了世界各國科研工作者的廣泛重視,通過對它們進行深入和細致的研究,取得了豐碩的研究成果。這種基于種群的進化算法具有隱含的并行特征,可以在單次模擬過程中得到多個解,因此非常適合求解多目標優(yōu)化問題。目前,群體智能技術在多目標優(yōu)化、數(shù)據(jù)分類、模式識別、系統(tǒng)建模、決策支持、系統(tǒng)辨識、信號處理、過程控制等方面得到廣泛應用,展現(xiàn)了群體智能技術解決優(yōu)化問題的獨特優(yōu)勢。

混合蛙跳算法(shuffled frog leaping,SFL)是由M. Eusutl和E. Lansey于2003年提出的基于群體智能的新型優(yōu)化算法[1],它結合了粒子群優(yōu)化算法(particle swarm optimization,PSO)良好的全局搜索能力和元算法Metric較強的局部搜索能力,具有實現(xiàn)簡單、適應性強、魯棒性好等優(yōu)點,是群體智能優(yōu)化技術研究與發(fā)展的重要方向,已經(jīng)應用于多項工程優(yōu)化問題[2-4]。此外,文獻[5]通過比較遺傳算法(genetic algorithm,GA)、文化基因算法(memetic algorithm,MA)、粒子群算法(particle swarm algorithm,PSO)、蟻群算法(ant colony optimization,ACO)和SFL,指出PSO在多數(shù)單模平滑/無噪聲問題上有很好的求解成功率和求解質(zhì)量,但在某些復雜奇異/多模問題上不如SFL。總的來說,PSO和SFL具有與問題無關的特性,很適合應用于復雜工程問題求解。

但和PSO算法一樣,基本SFL算法也存在早熟收斂和收斂較慢的難題[6]:隨著迭代次數(shù)的增加,個體之間變得越來越相似,容易陷入局部最優(yōu),出現(xiàn)早熟收斂。由于算法權系數(shù)變化范圍固定,無法自適應地調(diào)整搜索步長,在初始狀態(tài)尋找次優(yōu)解時速度較慢,在次優(yōu)解附近精確定位最優(yōu)解時需要很多次迭代,導致算法收斂較慢。

為提高SFL的收斂性,加快其收斂速度,國內(nèi)外學者先后做出一些改進,例如:文獻[7]將SFL與遺傳算法結合,并使用K鄰域聚類改進選擇算子,文中使用11種典型問題測試了混合算法的性能。文獻[8]通過對SFL算法收斂行為的分析,引入一種新的認知組件到每個個體中,增強個體的自主決策能力,文中使用6個benchmark問題驗證了改進算法的效率。文獻[9]受到離散SFL算法啟發(fā),通過改進蛙群的分組方法得到一種新的改進算法,通過與標準SFL的性能對比驗證了改進策略的有效性。文獻[10]通過擴展跳躍步長范圍和引入跳躍慣性分量,有效地改善了跳躍規(guī)則,但是所提出的跳躍規(guī)則缺少理論依據(jù)。

這些改進策略有些缺乏理論支撐,無法適用于求解所有類型的問題;有些在做算法比較時使用的測試問題較為簡單(維數(shù)較低/單模問題),無法反映求解真實多目標高維問題的效率。因此,本文后續(xù)部分著重以SFL的收斂性理論分析為基礎,給出合理的改進策略,并使用豐富的測試函數(shù)與目前流行的算法做對比,保證改進策略在求解后續(xù)復雜問題時依然有效。

1　基本混合蛙跳算法

基本SFL算法原理[1]如下圖1所示。

步驟 1初始化算法條件,包括種群大小P、種群個數(shù)M和步長;

步驟 2隨機產(chǎn)生包含P只青蛙的群體,并計算每只青蛙的適應度;

步驟 3迭代搜索開始:將整個蛙群根據(jù)適應度大小排序后劃分成M個族群,并對每個族群執(zhí)行it次局部搜索以更新本族群的最差解(記為Xw) (具體流程如圖1中所示A-B)。

步驟 4所有族群完成局部搜索后,將所有青蛙混合在一起重新分組,當次迭代結束;

步驟 5判斷當前結果是否滿足收斂條件,若不滿足則重新排序并劃分族群執(zhí)行上述局部搜索過程,若滿足則算法結束。

步驟3局部搜索是SFL算法的核心,其核心思想是根據(jù)組內(nèi)的最優(yōu)解Xb和群體最優(yōu)解Xg來更新最差解Xw。標準SFL算法的第k次迭代的更新策略具體描述如下:

(1)

(2)

(3)

圖1　基本SFL算法流程圖

由上述算法的基本流程可知,SFL算法是一種通過不斷迭代利用多個個體在搜索空間中尋找最優(yōu)解的隨機群體優(yōu)化算法。決定SFL算法求解效率的核心是局部搜索的更新策略,為了保證在有限次迭代中找到滿足收斂精度的解,算法必須在逐步收斂的前提下擴大解的隨機性,保持盡可能多地遍歷整個搜索空間,避免“早熟”,提高收斂精度和全局搜索能力。同時,若無限制的提高隨機性,則算法會陷入無規(guī)則的嘗試中,浪費大量計算時間,降低了算法的收斂速度。因此,收斂速度和收斂精度的平衡是保證SFL能夠適用于應用問題要解決的重要方面,下面將詳細分析SFL算法的收斂性,以得到平衡精度和速度的改進策略。

2　收斂性分析

為便于分析,假設Xb=Xg,且為了分析新解的可變軌跡,將式(1)～(3)擴展描述為

第k次迭代:

(4)

第k+1次迭代:

(5)

由式(4)和(5)得

(6)

記ΔXk+1=Xk+1-Xk,式(6)整理為

(7)

則有

(8)

結論 2SFL算法的收斂速度和精度與系數(shù)α，β和l有關。根據(jù)l合理的調(diào)節(jié)α，β,可以在保證算法按概率收斂的前提下,具有更快的收斂速度,使算法具有更強的全局搜索能力和全局/局部平衡能力。

假設α是α∈[αmin,αmax]范圍的隨機數(shù),β是β∈[βmin,βmax]范圍的隨機數(shù),那么q=(α+βl)可以劃分為2個區(qū)域:

(9)

式中,{q|0<|q|<1}是保證數(shù)列收斂的區(qū)間;{q||q|≥1}是數(shù)列不收斂的區(qū)間,用于增強解的隨機性避免早熟。因此系數(shù)α、β和l決定了q落入收斂區(qū)間0<|q|<1的概率,即

(10)

l值是迭代中間量,在概率表達式P=f(α,β|l)中屬于先驗知識,討論中可假設為常數(shù),則P只與α和β有關,即P=f(α,β)。因此可以通過調(diào)節(jié)α和β來平衡收斂速度和精度,使得當P很大時,算法沿較強的收斂軌跡運動;P減小時,跳出局部最優(yōu)解的能力加強。

綜上所述,在迭代過程中,根據(jù)群體的狀態(tài)和中間量l合理設置α和β的隨機區(qū)間,以自適應的改變公比q的取值范圍,可以擴大全局搜索能力,保證算法具有較快的收斂速度和較高的收斂精度。

3　改進策略

本節(jié)將從控制理論中的系統(tǒng)穩(wěn)定性分析理論出發(fā),定量給出SFL搜索性能與α和β的取值范圍區(qū)間的關系分析,得到α和β的取值范圍確定準則。為便于表述,最差解的更新公式可表示為

(11)

(12)

則由式(11)～式(12)得到

(13)

該方程可以看作是系統(tǒng)的差分方程表達形式,利用Z變換原理,得到系統(tǒng)傳遞函數(shù)

(14)

(15)

3.1比例系數(shù)l的作用

比例系數(shù)l代表了本次迭代中,最差解的變化速率與(局部/全局)最優(yōu)解的變化速率之間的關系,是表征系統(tǒng)隨機性的重要特征。因此，根據(jù)l取值范圍,更新策略分析如下:

圖2　不同α的階躍響應

當0<α<1,階躍響應是逐步收斂的,并且α越大,收斂速度越快;當α=1,階躍響應是完全收斂的,最差解直接跳到最優(yōu)解位置;當1<α<2,階躍響應是逐步收斂的,并且α越小,收斂速度越快;當α≥2,階躍響應是發(fā)散的,并且α越大,發(fā)散速度越快。

圖2所示不同α的階躍響應結果進一步驗證了當β=1且α∈(0,2),最差解Xw將在有限迭代次數(shù)內(nèi)收斂到最優(yōu)解Xb,且當α越靠近0或2,收斂速度就越慢。因此,可將α的取值范圍設置為α∈(1-Δ,1+Δ),則Δ∈(0,1),且Δ越小,收斂速度越快。同時,為了保持算法具有一定的隨機性,避免陷入某個局部解無法突破,可以將β擴展成(0.95,1.05)的隨機數(shù),以增強算法的全局搜索能力。此時,最差解Xw的變化區(qū)域是圍繞著最優(yōu)解Xb的一個狹長四邊形(如圖3所示)。

圖3　當l>0時最差解的變化區(qū)域

總之,當l>0時,α和β可以使用公式(16)生成,即

(16)

此時,新解的變化區(qū)域面積為S=0.1×2Δ=0.2Δ。

圖4所示不同β的階躍響應結果進一步驗證了當α=1 且β∈(0,2),最差解Xw將在有限迭代次數(shù)內(nèi)收斂到最優(yōu)解Xb,且當β越靠近0或2,收斂速度就越慢。因此,可將β的取值范圍設置為β∈(1-Δ,1+Δ),則Δ∈(0,1),且Δ越小,收斂速度越快。同時,為了保持算法具有一定的隨機性,避免陷入某個局部解無法突破,可以將α擴展成(0.95,1.05)的隨機數(shù),以增強算法的全局搜索能力。此時,最差解Xw的變化區(qū)域是圍繞著D=(Xb-Xw)或D=(Xg-Xw)的狹長四邊形(見圖5)。

總之,當l<0時,α和β可以使用式(19)生成,即

(19)

圖4　不同β的階躍響應

圖5　當l=0時最差解的變化區(qū)域

總之,當l=0時,α和β可以使用式(17)生成,即

(17)

此時,新解的變化區(qū)域面積為S=0.1×2Δ=0.2Δ。

(18)

為求解上述不等式,圖6給出了不同Δ取值下極點位置隨β的變化曲線。從圖中看出,不論Δ如何取值,只要β∈(Δ,2-Δ),則可滿足極點位于單位圓內(nèi)的要求(紅線所示區(qū)域)。

圖6　不同Δ取值的極點位置

此時,新解變化區(qū)域是與Δ相關的平行四邊形(見圖7),面積為S=2Δ×(2-2Δ)=4Δ-4Δ2,S∈(0,1)。Δ越小,該四邊形越是朝著縱向方向壓縮,變成圍繞D=(Xb-Xw)或D=(Xg-Xw)的狹長四邊形;反之,該四邊形越是朝著橫向方向壓縮,變成圍繞最優(yōu)解的狹長四邊形。當Δ=0.5時,面積最大且為等邊四邊形。

因此,隨機產(chǎn)生Δ,并使用公式(19)生成α和β可以保證算法保持一定的隨機性且收斂。為了進一步明確Δ的取值對系統(tǒng)響應的影響,圖8給出了不同Δ條件下的階躍響應曲線。

圖7　當l<0時最差解的變化區(qū)域

圖8　不同Δ條件下的階躍響應

如上圖8所示,每行代表某個Δ隨機產(chǎn)生的3組α和β的系統(tǒng)階躍響應,包括Δ=0.1,Δ=0.5和Δ=0.9 3種情況。從圖中9個響應曲線發(fā)現(xiàn),所有響應曲線均在有限步長內(nèi)收斂。同時,收斂速度是隨機的,如圖最大為25步。因此,進一步驗證了使用公式(19)隨機產(chǎn)生α和β可以平衡全局搜索能力和局部搜索效率。

總之,從比例系數(shù)的3種情況階躍響應分析可以得到如下結論:

(1) 使用不同方法產(chǎn)生系數(shù)α和β決定了最差解的進化特性,從而影響了整個群體的行為特征,例如保持更大的隨機性以增強全局搜索能力,或加速收斂速度保持收斂效率。

(2) 基于比例系數(shù)l的取值,合理調(diào)節(jié)Δ,并基于式(16)、式(17)、式(19)隨機生成α和β可以平衡算法的全局收斂能力和局部搜索效率。Δ的調(diào)節(jié)方法將在下節(jié)詳細論述。

3.2適應度標準差的作用

如上所述,本文改進策略的基本原則是在每次局部搜索的迭代中,根據(jù)l取值自適應選擇不同的系數(shù)取值范圍來更新最差解,即

(20)

(21)

這種改進策略可以保證算法在有限步長內(nèi)收斂,并保持一定的隨機性,很好的平衡了全局搜索能力和收斂效率。但同時應該注意到,上述方法中Δ是一定范圍變化的隨機數(shù),而收斂步長與Δ的取值有關,造成階躍響應的收斂步長與算法當前狀態(tài)無關,無法根據(jù)群體的聚集程度和最優(yōu)解的更新頻率等自適應地擴大/縮小步長,因此無法加快收斂速度。

為自適應調(diào)整Δ以加快收斂速度,本節(jié)引入全局最優(yōu)解序列Xg(k)在當前迭代附近時間窗子序列標準差stdJi來度量算法的當前狀態(tài),作為調(diào)整Δ的依據(jù)。stdJi是反映Xg(k)離散程度的統(tǒng)計值,可預測全局最優(yōu)解的更新頻率。當Xg(k)變化緩慢(或幾次迭代均未更新)時應增強隨機性使得新解具有突破當前位置的能力,來避免陷入局部最優(yōu);反之,應保持一定的隨機性來跟隨最優(yōu)解,在其附近探索新解。

(22)

式中,Ji是全局最優(yōu)解在第i-th迭代的適應度值。所以,當stdJi較小時,Xg(k)變化緩慢;當stdJi較大時,Xg(k)變化較快。因此,使用stdJi調(diào)節(jié)Δ的取值方法如下式(23)所示。

(23)

總之,根據(jù)迭代過程中的stdJi,實現(xiàn)自適應調(diào)節(jié)Δ,是本文加快收斂速度的策略。

3.3基于比例系數(shù)和適應度標準差的調(diào)節(jié)策略

綜上所述,本文改進策略可以總結為一種根據(jù)比例系數(shù)l和適應度標準差stdJi來自適應調(diào)整更新系數(shù)α和β的技術。詳細的系數(shù)產(chǎn)生策略如表1所示。

表1給出了根據(jù)比例系數(shù)l和適應度標準差stdJi選擇最差解Xw更新公式的系數(shù)α和β及Δ的具體方法。直觀上看,對每行l(wèi)<0情況下Xw的可變范圍要大于l>0,意味著無論標準差stdJi是多少,都需要減小隨機性來確保最差解能在最優(yōu)解附近區(qū)域搜索。在每一列,stdJi越小,Δ的取值范圍越大,意味著需要增強隨機性來確保最差解能在更大區(qū)域搜索,使得算法具有跳出當前最優(yōu)解的能力,避免陷入局部最優(yōu)。

為了進一步驗證本文改進策略對收斂特性的影響,下圖9給出了不同l和Δ條件下的系統(tǒng)階躍效應。

表1　自適應系數(shù)調(diào)整策略

圖9　不同l和Δ條件下的系統(tǒng)階躍效應

圖9所示階躍響應驗證了本節(jié)所論述的觀點。當l>0時,從階躍響應可以看出,系統(tǒng)在1～2步內(nèi)快速穩(wěn)定收斂;當l<0時,則需要1～7步才能收斂。由此說明l<0時的系統(tǒng)隨機性保持的很好,達到穩(wěn)定所需的步長是隨機的;而l>0在一定隨機性下將以更快的速度收斂。

總之,比例系數(shù)l和適應度標準差stdJi是兩個重要的指標,分別對算法的收斂性和收斂速度產(chǎn)生影響。本文提出的改進策略是一種動態(tài)平衡新解可變范圍和收斂速度的方法。當?shù)^程中,群體聚集度高容易陷入局部最優(yōu)時,通過調(diào)節(jié)Δ增大系統(tǒng)的隨機性;反之,應該更加關注最優(yōu)解附近區(qū)域避免不必要的嘗試,以此來提高收斂速度。

4　性能測試

4.1不同特性的標準測試集

為了測試改進混合蛙跳算法對不同問題的求解性能,本文根據(jù)文獻[11-14],選擇3組共8個標準測試函數(shù)(如表2)做對比。包括:①單模函數(shù)測試組:F1 Sphere測試收斂速度;F2 Rosenbrock評價優(yōu)化算法執(zhí)行效率;F3 Ackley函數(shù)在狹長的全局最優(yōu)點周圍擁有很多局部極值點,測試全局搜索能力;F4 Easom是一個非線性函數(shù),全局最小解分布在很窄的洞中而外圍幾乎是平面,很難找到最優(yōu)解。②多模函數(shù)測試組:F5 Rastrigrin測試種群多樣性;F6 Griewank測試收斂速度;F7 Schwefel包含很多峰值且全局最小值周圍有很平滑的區(qū)域,很難求解。③帶噪聲多模函數(shù):F8 Levy有很多局部最小點,同時含有噪聲,常用來測試多模噪聲環(huán)境下的算法搜索性能。

表2　標準測試函數(shù)

為評估改進混合蛙跳算法的性能,本文選取標準SFL和4種PSO算法做對比。① wPSO:由Shi和Ebehart R于1998年提出的時變慣性權重PSO算法[15];② cPSO:由Clerc和 Kennedy于2002年提出的帶約束因素的改進PSO算法[16];③ vPSO:由Y. Volkan于2012年提出的多頻率震動PSO算法[17];④ clPSO:由Liang于2006年提出的帶復雜自學習的PSO算法[18]。所有算法參數(shù)設置如表3所示。

對上述測試函數(shù),所有算法都獨立執(zhí)行30次。算法使用Matlab 2009b實現(xiàn),運行在Intel Core i5處理器(2.5 GHz)/4GB RAM的PC機上。表4給出了運行結果,分別從30次運行結果的最差適應度(Worst)、最好適應度(Best)、平均適應度(Mean)、成功率(Suc.)和運行時間(Time)5個方面做對比。需要注意的是,評價標準解為0的測試函數(shù)是否求解成功時,本文假設當求解精度高于10-8就認為本次運行求解成功。下圖10同時給出了不同測試函數(shù)的運行最好的一次求解結果的收斂曲線。

表3　算法的參數(shù)設置

圖10　同測試函數(shù)的收斂曲線

算法測試函數(shù)評價wPSOcPSOvPSOclPSOBasicSFLMSFLF1SphereWorst11.3143184.56112.2716e-0571.4222e-0151.4364e-53.055e-110Best0.0275450.735511.1908e-0697.4753e-0181.6565e-81.3556e-154Mean2.352931.48951.3678e-0582.3297e-0162.6292e-0061.0183e-111Suc.(%d)00100%100%0100%Time/s1.20981.14531.25144.722317.920332.1029F2RosenbrockWorst00.0390079.9104e-0168.9014e-0100.0581450Best007.7835e-0211.5306e-0142.6059e-0060Mean00.00136195.1948e-0172.5287e-0100.00627990Suc.(%d)100%86.7%100%100%0100%Time/s0.23940.210031.04573.625118.133932.4479F3AckleyWorst3.22288.6132.814317.92153.2638e-0053.5527e-015Best3.5527e-0150.02451200.171961.5737e-0090Mean0.575191.75980.3356611.34012.0342e-0062.3685e-016Suc.(%d)73.3%083.3%016.7%100%Time/s1.28751.26321.06674.204517.33930.8249F4EasomWorst-8.0683e-005-8.1102e-005-10-1-1Best-1-1-1-0.99999-1-1Mean-0.96667-0.72622-1-0.96296-1-1Suc.(%d)96.7%50%100%0100%100%Time/s0.238530.999030.445573.539217.156931.6668F5RastrigrinWorst25.869429.209816.91887.225930.34060Best2.98495.98512.9850.711042.98490Mean12.513914.10378.75693.483411.47740Suc.(%d)00000100%Time/s1.07751.13171.10544.678416.883130.6665F6GriewankWorst2.76883.17450.5516633.95180.375040Best0.278350.637480.04189610.30820.0503160Mean1.2341.67760.2683821.96680.157930Suc.(%d)00000100%Time/s1.4331.37811.38015.061617.438730.8855F7SchwefelWorst-601.0891-572.6518-620.8247-601.0886-719.5274-837.9658Best-837.9658-837.9657-837.9658-837.9657-837.9658-837.9658Mean-710.1637-691.5232-758.2083-766.6481-833.6939-837.9658Suc.(%d)13.3%06.7%063.3%100%Time/s1.2371.19451.25323.716417.370731.8599F8LevyWorst-147.2612-146.8709-166.9959-186.5909-170.5308-186.3406Best-186.7309-186.7309-186.7309-186.7309-186.7309-186.7309Mean-178.7279-179.4437-182.4145-186.7173-182.5721-185.5468Suc.(%d)46.7%40%60%36.7%40%66.7%Time/s1.01310.985471.03993.553717.051431.4902

從表4和圖10結果可以得到以下結論:

(1)對第一組單模測試集,MSFL幾乎對4個函數(shù)都有最好的性能(收斂速度快,成功次數(shù)多),其次是vPSO對這組測試函數(shù)也有較好的求解結果。另外,從圖30中F2 Rosenbrock函數(shù)的收斂曲線看出,cPSO的收斂速度是最快的,但是它在成功率上比wPSO vPSO clPSO和MSFL要差;從F3 Ackley的收斂曲線看,wPSO vPSO和MSFL都有不錯的全局搜索能力,但是MSFL是收斂速度最快的,成功率最高;F4 Easom測試函數(shù)既是單模函數(shù),又含有噪聲,wPSO vPSO BasicSFL MSFL都能以較高的成功率求解該函數(shù),但MSFL的收斂速度是最快的。因此,可以明顯看出MSFL比其他5類算法在求解單模問題時具有更好的收斂速度和精度。

(2)對第二組多模測試集,從表5中可以看出只有MSFL對3個測試函數(shù)均有效。對F5 Rastrigrin和F6 Griewank,其他5種算法幾乎都無法求解,這說明它們的保持種群分布能力和收斂速度都比MSFL差;對F7 Schwefel,MSFL和BasicSFL具有很高的求解成功率,而wPSO和vPSO雖然能在30次運算中成功求解該函數(shù),但成功率不高,cPSO和clPSO最多只能得到與標準解接近的結果。因此,可以看出BasicSFL和MSFL比4種PSO算法有更好的全局搜索能力,同時,MSFL在求解多模問題的成功率和收斂速度上是最好的。

(3)對第三組多模-帶噪聲的測試集,6種算法都能在30次運算中成功求解F8 Levy,但成功率都基本只到50%左右。雖然MSFL的成功率最高,但仍不能達到90%以上。

總之,從三組不同特性的測試函數(shù)結果可以看出,MSFL在求解成功率、收斂速度、收斂精度上比其他5種算法好,證明本文改進策略是有效的。但同時也要注意,MSFL的計算時間是最長的,這主要是因為在局部搜索中加入了復雜的最差解更新邏輯。但在實際問題求解中,使用更高性能的計算設備或對實時性要求不高的場合,MSFL具有很高的應用價值。

4.2低維/高維特性對比

上節(jié)討論的8個測試函數(shù)結果驗證了MSFL在求解單/多模帶噪聲問題的效率是最高的,但其中的測試函數(shù)維數(shù)都不高。因此,還需要進一步驗證MSFL是否在低維/高維問題中同樣有效。以下將8個測試函數(shù)中維度可擴展的F1 Sphere、F2 Rosenbrock、F5 Rastrigrin和F6 Griewank四類函數(shù)作為本節(jié)標準測試函數(shù)集,對比wPSO、BasicSFL和MSFL的性能。其中wPSO算法粒子共30個,慣性權重w∈[0,0.9]、C1=C2=2;BasicSFL/MSFL算法中,種群規(guī)模30只分為6組,且局部迭代6次。性能評估采用2組實驗對比:

(1)固定迭代精度的5維/30維函數(shù)性能測試

為了對比測試結果,分別從成功率、最差解、最好解、平均值和平均迭代次數(shù)對性能進行對比,每種算法分別用于5維和30維函數(shù)性能測試。每組測試運行100次,最大迭代次數(shù)為1 000次,統(tǒng)計結果如表5所示。

表5　固定迭代精度的5維/30維函數(shù)性能測試結果

分析表5中結果可得以下結論:

(1) 由F1測試結果可知:wPSO和MSFL對低維F1函數(shù)都具有很好的性能,可以達到預定的搜索精度(1E-32),且MSFL的成功率和平均值的精度要高于wPSO;當F1測試函數(shù)的維數(shù)增大到30時,wPSO的求解性能明顯下降(成功率為0),而MSFL則無影響,仍然可以100%得到標準解。因此,在簡單單模函數(shù)求解時,MSFL比wPSO/SFL的魯棒性好,幾乎不受維數(shù)約束。

(2) 由F2測試結果可知:求解低維F2時,wPSO和MSFL都有很好的性能;但當維數(shù)增大到30維時,wPSO的成功率迅速下降到0,此時MSFL的成功率仍然可以達到100%。對比結果說明,MSFL在求解非凸的病態(tài)單模函數(shù)時,也幾乎不受問題維數(shù)的影響。

(3) 由F5/F6測試結果可知,wPSO在低維F5問題求解時,還能在多次運算中求得標準解,但一旦問題維度提高到30維時,成功率又下降為0。而MSFL的成功率始終保持在100%。因此,MSFL在多模問題上的求解性能,也幾乎不受問題維度的影響。

(2)固定迭代次數(shù)(1 000次)的100維測試函數(shù)

第一組測試結果問題維數(shù)雖然提高到了30維,可以滿足一般工程應用的維度要求,但是對于更加復雜的問題,其求解維度優(yōu)勢會達到更高。因此,還需要分析更高維度下算法的性能,下文采用D=100的4種測試函數(shù) (有效精度范圍設置在10-64),每組測試運行10。測試結果以迭代過程中的最優(yōu)解曲線表示,如圖11所示。

圖11　D=100測試結果

由圖11所示100維求解結果可以看出:MSFL對高維Sphere函數(shù)仍然有效,能夠在第600次迭代時找到滿足收斂精度的解,其他兩類

算法均失效;SFL、MSFL、wPSO 3種方法對高維Rosenbrock函數(shù)都無能為力,但MSFL在收斂速度和精度上還是優(yōu)于其他兩類算法;MSFL對高維Rastrigrin函數(shù)是有效的,只是需要花費更多迭代次數(shù)(800次左右)才能找到滿足精度的解,其他兩類算法均失敗;MSFL對高維Griewank函數(shù)是有效的,需要大概400次迭代找到滿足精度的解,其他兩類算法均失敗。因此,MSFL在處理更高維復雜問題時仍具有很強的優(yōu)勢,收斂速度和精度比其他2種算法都好。

總之,通過對不同特性標準函數(shù)測試集的求解結果對比,以及相同函數(shù)低維/高維/更高維時的求解性能對比,驗證了本文所提出的MSFL具有很好的全局搜索能力和搜索效率,收斂精度和收斂速度能夠在迭代中保持平衡,適用于線性/非線性、單模/多模、低維/高維等多種問題的求解,可以作為本文模型求解器的核心算法。

5　小　結

本文研究了一類新型群體智能算法的收斂性及其改進策略。文中首先分析了基本SFL的計算步驟,從而找到影響算法收斂精度和速度的關鍵步驟是局部迭代的更新過程。然后,分析了算法收斂性的影響要素:將更新公式變形整理成數(shù)列形式,使用等比數(shù)列的性質(zhì)證明了收斂性與系數(shù)α和β的取值范圍相關;進一步將更新公式整理成系統(tǒng)傳遞函數(shù)形式,使用數(shù)字信號處理的穩(wěn)定性原理分析了不同α和β的取值方法和調(diào)節(jié)方法對系統(tǒng)階躍響應穩(wěn)定性的影響。在此基礎上提出一種基于比例系數(shù)和適應度標準差的自適應調(diào)節(jié)策略用于算法改進。最后,使用不同特性的3組共計8種標準測試函數(shù)做對比,并對其中4種函數(shù)在低維/高維/更高維情況下的測試性能做對比,驗證了本文改進策略在改進算法收斂精度和收斂速度的有效性,為復雜問題的求解提供了有效的求解算法支撐。

[1] Eusuff M M, Lansey K E. Optimization of water distribution network design using the shuffled frog leaping algorithm[J].JournalofWaterResourcesPlanningandManagement, 2003, 129(3): 210-225.

[2] Emad E, Tarek H, Donald G. A modified shuffled frog-leaping optimization algorithm: applications to project management[J].StructureandInfrastructureEngineering, 2007, 3(1): 53-60.

[3] Bhattacharjee K K, Sarmah S P. Shuffled frog leaping algorithm and its application to 0/1 knapsack problem[J].AppliedSoftComputing, 2014, 19(19): 252-263.

[4] Luo X H, Yang Y, Li X. Modified shuffled frog-leaping algorithm to solve traveling salesman problem[J].JournalonCommunications, 2009, 30(7):130-135.(羅雪輝,楊燁,李霞. 改進混合蛙跳算法求解旅行商問題[J].通信學報, 2009, 30(7): 130-135.)

[5] Elbeltagi E, Hegazy T, Grierson D. Comparison among five evolutionary-based optimization algorithms[J].AdvancedEngineeringInformatics, 2005, 19(1): 43-53.

[6] Xiao Y Y, Chai X D, Li B H, et al. Convergence analysis of shuffled frog leaping algorithm and its modified algorithm[J].JournalofHuazhongUniversityofScienceandTechnology(NatureScienceEdition),2012,40(7):15-18.(肖瑩瑩,柴旭東, 李伯虎, 等. 混合蛙跳算法的收斂性分析及其改進[J].華中科技大學學報(自然科學版), 2012, 40(7): 15-18.)

[7] Yang C S, Chuang L Y, Ke C H, et.al. A combination of shuffled frog-leaping algorithm and genetic algorithm for gene selection[J].JournalofAdvancedComputationalIntelligenceandIntelligentInformatics, 2008, 12(3): 218-226.

[8] Zhang X, Hu X, Cui G, et al. An improved shuffled frog leaping algorithm with cognitive behavior[C]∥Proc.ofthe7thIEEEWorldCongressonIntelligentControlandAutomation, 2008: 6197-6202.

[9] Zhen Z, Wang D, Liu Y. Improved shuffled frog leaping algorithm for continuous optimization problem[C]∥Proc.oftheIEEECongressonEvolutionaryComputation, 2009: 2992-2995.

[10] Huynh T H. A modified shuffled frog leaping algorithm for optimal tuning of multivariable PID controllers[C]∥Proc.oftheIEEEInternationalConferenceonIndustrialTechnology, 2008: 1-6.

[11] Ping D A, Fang W H. Adaptive particle swarm optimization algorithm with dynamically changing inertia weight[J].Control&Decision, 2008, 23(11): 1253-1257.

[12] Chen W N, Zhang J, Lin Y, et al. Particle swarm optimization with an aging leader and challengers[J].IEEETrans.onEvolutionaryComputation, 2013, 17(2): 241-258.

[13] Mehrabian A R, Lucas C. A novel numerical optimization algorithm inspired from weed colonization[J].EcologicalInformatics, 2006, 1(4): 355-366

[14] Hao G, Hao L W, Bo X W. A global convergence algorithm of particle swarm optimization and its convergence analysis[J].Control&Decision, 2009, 24(2): 196-201.

[15] Shi Y, Eberhart R. A modified particle swarm optimizer[C]∥Proc.oftheIEEEInternationalConferenceonEvolutionaryComputation, 1998: 69-73.

[16] Clerc M, Kennedy J. The particle swarm-explosion, stability, and convergence in a multidimensional complex space[J].IEEETrans.onEvolutionaryComputation, 2002, 6(1): 58-73.

[17] Pehlivanoglu Y V. A new particle swarm optimization method enhanced with a periodic mutation strategy and neural networks[J].IEEETrans.onEvolutionaryComputation,2013,17(3):436-452.

[18] Liang J J, Qin A K, Suganthan P N, et al. Comprehensive learning particle swarm optimizer for global optimization of multimodal functions[J].IEEETrans.onEvolutionaryComputation, 2006, 10(3): 281-295.

Improvement strategy of adaptive parameter adjustment for shuffled frog leaping algorithm

XIAO Ying-ying1,2, LIN Ting-yu1,2, LI Bo-hu2,3, HOU Bao-cun1,2,3, SHI Guo-qiang1,2,3

(1. Beijing Complex Product Advanced Manufacturing Engineering Research Center, Beijing Simulation Center, Beijing 100854; 2. State Key Laboratory of Intelligent Manufacturing System Technology,Beijing Institute of Electronic System Engineering, Beijing 100854; 3. Science and Technology on Space System Simulation Laboratory, Beijing Simulation Center, Beijing 100854)

An improvement strategy of adaptive parameter adjustment is proposed to improve the efficiency of the shuffled frog leaping algorithm (SFL) in solving high dimensional complex problems. First of all, the convergence feature of the SFL is analyzed based on the theory of geometrical sequence. Then, an improvement strategy of adaptive parameter adjustment based on proportional coefficient and fitness standard deviation is proposed to the update the formula. Finally, based on three groups of eight criteria functions, the performance of the modified SFL with basic SFL and four modified particle swarm optimization (PSO) is compared, and the results verify the high-efficiency of the improvement strategy for various complex functions. Meanwhile, the performance of the modified SFL with basic SFL and wPSO on solving high dimension problems is compared, and the results verify the validity of the modified SFL.

shuffled frog leaping (SFL) algorithm; convergence feature; adaptive parameter adjustment; intelligent computing

2016-02-22；

2016-03-28；網(wǎng)絡優(yōu)先出版日期：2016-06-19。

國家高技術研究發(fā)展計劃(863計劃)(2015AA042101)資助課題

TP 391

A

10.3969/j.issn.1001-506X.2016.08.34

肖瑩瑩(1987-),女,博士研究生,主要研究方向為智能制造、智能優(yōu)化算法。

E-mail: xiaoyingying504@126.com

林廷宇(1984-),男,博士,主要研究方向為智能制造、云制造、網(wǎng)絡化建模與仿真系統(tǒng)。

E-mail:lintingyu2003@sina.com

李伯虎(1938-),男,中國工程院院士,博士研究生導師,主要研究方向為網(wǎng)絡化建模與仿真系統(tǒng)、虛擬樣機工程、網(wǎng)格化、智能化、服務化制造系統(tǒng)。

E-mail: bohuli@moon.bjnet.edu.cn

侯寶存(1979-),男,研究員,博士，主要研究方向為網(wǎng)絡化建模與仿真系統(tǒng)、虛擬樣機工程、網(wǎng)格化、智能化、服務化制造系統(tǒng)。

E-mail:houbaocun@sina.com

施國強(1978-),男,高級工程師,博士，主要研究方向為網(wǎng)絡化建模與仿真系統(tǒng)、虛擬樣機工程、網(wǎng)格化、智能化、服務化制造系統(tǒng)。

E-mail:sunnyqiang737@163.com

網(wǎng)絡優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160619.1132.010.html