肖瑩瑩, 林廷宇, 李伯虎, 侯寶存,3, 施國(guó)強(qiáng),3

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

?

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

肖瑩瑩1,2, 林廷宇1,2, 李伯虎2,3, 侯寶存1,2,3, 施國(guó)強(qiáng)1,2,3

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

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

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

0　引　言

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

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

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

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

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

1　基本混合蛙跳算法

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

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

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

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

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

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

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

(1)

(2)

(3)

圖1　基本SFL算法流程圖

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

2　收斂性分析

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

第k次迭代:

(4)

第k+1次迭代:

(5)

由式(4)和(5)得

(6)

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

(7)

則有

(8)

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

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

(9)

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

(10)

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

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

3　改進(jìn)策略

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

(11)

(12)

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

(13)

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

(14)

(15)

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

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

圖2　不同α的階躍響應(yīng)

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

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

圖3　當(dāng)l>0時(shí)最差解的變化區(qū)域

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

(16)

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

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

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

(19)

圖4　不同β的階躍響應(yīng)

圖5　當(dāng)l=0時(shí)最差解的變化區(qū)域

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

(17)

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

(18)

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

圖6　不同Δ取值的極點(diǎn)位置

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

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

圖7　當(dāng)l<0時(shí)最差解的變化區(qū)域

圖8　不同Δ條件下的階躍響應(yīng)

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

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

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

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

3.2適應(yīng)度標(biāo)準(zhǔn)差的作用

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

(20)

(21)

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

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

(22)

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

(23)

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

3.3基于比例系數(shù)和適應(yīng)度標(biāo)準(zhǔn)差的調(diào)節(jié)策略

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

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

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

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

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

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

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

4　性能測(cè)試

4.1不同特性的標(biāo)準(zhǔn)測(cè)試集

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

表2　標(biāo)準(zhǔn)測(cè)試函數(shù)

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

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

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

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

算法測(cè)試函數(shù)評(píng)價(jià)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結(jié)果可以得到以下結(jié)論:

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

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

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

總之,從三組不同特性的測(cè)試函數(shù)結(jié)果可以看出,MSFL在求解成功率、收斂速度、收斂精度上比其他5種算法好,證明本文改進(jìn)策略是有效的。但同時(shí)也要注意,MSFL的計(jì)算時(shí)間是最長(zhǎng)的,這主要是因?yàn)樵诰植克阉髦屑尤肓藦?fù)雜的最差解更新邏輯。但在實(shí)際問(wèn)題求解中,使用更高性能的計(jì)算設(shè)備或?qū)?shí)時(shí)性要求不高的場(chǎng)合,MSFL具有很高的應(yīng)用價(jià)值。

4.2低維/高維特性對(duì)比

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

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

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

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

分析表5中結(jié)果可得以下結(jié)論:

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

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

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

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

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

圖11　D=100測(cè)試結(jié)果

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

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

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

5　小　結(jié)

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

[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ìn)混合蛙跳算法求解旅行商問(wèn)題[J].通信學(xué)報(bào), 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ìn)[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 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)絡(luò)優(yōu)先出版日期：2016-06-19。

國(guó)家高技術(shù)研究發(fā)展計(jì)劃(863計(jì)劃)(2015AA042101)資助課題

TP 391

A

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

肖瑩瑩(1987-),女,博士研究生,主要研究方向?yàn)橹悄苤圃?、智能?yōu)化算法。

E-mail: xiaoyingying504@126.com

林廷宇(1984-),男,博士,主要研究方向?yàn)橹悄苤圃?、云制造、網(wǎng)絡(luò)化建模與仿真系統(tǒng)。

E-mail:lintingyu2003@sina.com

李伯虎(1938-),男,中國(guó)工程院院士,博士研究生導(dǎo)師,主要研究方向?yàn)榫W(wǎng)絡(luò)化建模與仿真系統(tǒng)、虛擬樣機(jī)工程、網(wǎng)格化、智能化、服務(wù)化制造系統(tǒng)。

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

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

E-mail:houbaocun@sina.com

施國(guó)強(qiáng)(1978-),男,高級(jí)工程師,博士，主要研究方向?yàn)榫W(wǎng)絡(luò)化建模與仿真系統(tǒng)、虛擬樣機(jī)工程、網(wǎng)格化、智能化、服務(wù)化制造系統(tǒng)。

E-mail:sunnyqiang737@163.com

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