噪聲環境下基于蒲豐距離的依概率多峰優化算法

王 霞 王耀民 施心陵 高 蓮 李 鵬

實際優化問題往往存在著多個全局最優解及其他有價值的局部最優解,我們不僅需要找到全局最優解,還需要找到局部最優解進行輔助決策,這類優化問題稱為多峰搜索(Multi-peak searching)或多峰優化(Multimodal optimization) 問題[1].此外,實際優化問題總是受到各種隨機噪聲的影響.在噪聲環境下求解多峰優化問題不僅要求算法能在噪聲干擾下尋找真實的極值點位置,而且希望算法能提供備選的多個優化方案.噪聲的分布往往符合一定的概率關系,因此噪聲環境下的多峰優化問題是一個依概率求解極值點的問題.其中包含的噪聲環境下的尋優問題[2](Noisy optimization)和多峰優化問題在科學和工程領域中有理論和實際意義.噪聲優化算法的研究可以為機器人[3?5]、智能控制與決策[6?9]、信號識別與測量[10?11]、智能制造[12]等存在噪聲干擾的工程優化問題提供優化解決方案.

在噪聲優化算法的依概率問題研究方面,一些學者研究了噪聲優化算法的概率模型,如Nakama[13]和李軍華等[14]研究了噪聲環境下遺傳算法的 Markov模型.Ma 等[15]使用Markov 模型分析了噪聲對生物地理優化算法(Biogeography-based optimization,BBO)的影響.Beyer 等[16]對自適應進化策略(Self-adaptive evolution strategy,ES)的魯棒優化模型進行了穩態分析.但是算法求解優化結果的依概率關系尚無相關研究.也有一些學者在研究中涉及到了優化算法的依概率問題,但都是針對無噪聲環境下的優化算法,例如蟻群優化算法[17](Ant colony optimization,ACO)基于信息素指導依概率為子代個體構建解,從而將信息素的分布理解為一種特殊的概率分布.李寶磊等[18]證明了所提出的多元優化算法以概率1 收斂于全局最優解.董易等[19]證明了所提出的斐波那契樹優化算法以概率1 收斂于全局最優解.針對噪聲環境下多峰優化算法的依概率問題尚缺乏相關研究.對于噪聲優化算法的依概率特性研究非常重要,它可以評估算法搜索優化問題全部極值點的能力,衡量算法的優化效率,同時為算法性能的改進和提升指明方向.

在噪聲環境下多極值點尋優問題的研究方面,元啟發式算法作為解決確定性優化問題的一種主流方法,其在噪聲環境中的優化性能受到了越來越多的關注.李軍華、黎明等[14,20?22]分析了噪聲對遺傳算法的影響以及正態隨機噪聲對適應度評價的影響機理,提出了多次評價一次采樣的動態適應度評價方法.許多學者通過將假設檢驗(Hypothesis test,HT)、最優計算量分配(Optimal computing budget allocation,OCBA)技術、反向學習法、自動學習機(Learning automata,LAs)、重采樣、聚類算法、加權搜索中心等多種策略引入粒子群優化算法(Particle swarm optimization,PSO)中[23?29],以提高算法的魯棒性.這些優化算法能夠在噪聲環境中找到接近全局最優的極值點,但都沒有求解其他極值點.在多峰優化問題的研究中,許多多峰函數優化算法[1,30?31]能搜索到多峰函數的多個極值點.但大部分算法只針對確定性環境,并未考慮噪聲環境下的多峰優化問題.Jamil 等[32]對蝙蝠算法(Bat algorithm)進行了改進,使其適用于無噪聲環境和有噪聲環境,將其應用到多峰函數優化問題中,可以找到多峰函數的多個全局極值點.然而遺憾的是,文中并未討論多個局部極值點的情況,且極值點的坐標并未明確給出.盡可能多的搜索局部極值點能為生產實際提供更多樣化的優化方案.此外,為了提供明確的優化方案,實驗結果應給出極值點的適應度值和對應的解,以便為實際應用提供明確的決策變量[33].

蒲豐投針問題是一個幾何概率問題.它是法國科學家蒲豐(Buffon)在1777 年的論著 《或然性算術試驗》 中提出的.蒲豐投針原理反映了幾何概率的特征及處理方法,衍生出了蒙特卡洛(Monte-Carlo)方法.其概率規律在探礦、近似計算中得到廣泛應用,但在優化算法中的應用尚無相關研究.在噪聲環境中通過隨機方式探索多峰函數的極值點與蒲豐投針問題具有相似的概率解釋.本文將蒲豐推導得到的定概率原理應用于噪聲環境下的多極值點尋優問題,從概率的角度出發,提出了噪聲環境下基于蒲豐距離的依概率多峰優化算法(Probabilistic multimodal optimization algorithm based on the Button distance,PMB),推導證明了蒲豐距離和極值分辨度共同依概率決定算法的峰值檢測率.依據蒲豐距離劃分全局搜索空間,并在局部范圍內利用改進的斐波那契法進行局部尋優,針對多維函數,采取多級劃分策略,從而提高求解精度和算法效率.通過算法依概率收斂特性實驗,驗證了PMB算法在噪聲環境下能夠依固定概率找到多個極值點;通過設置不同的噪聲強度與蒲豐距離進行實驗,分析了噪聲強度與蒲豐距離對算法求解結果的影響;通過對比噪聲環境下的改進蝙蝠算法,表明了PMB 算法具有很好的多極值點尋優特性和定位精準性;通過對比PSO 算法在多維函數上的表現,證明了PMB 算法在噪聲環境下對多維函數尋優的有效性.

第1 節對噪聲環境下的多峰優化問題進行數學描述,并說明評價指標.第2 節詳細描述了本文提出的PMB算法的基本原理和理論推導.第3 節是論文的仿真實驗與結果分析,用以驗證算法的有效性.第4 節給出結論和將來的研究方向.

1 問題描述及評價指標

1.1 問題描述

在受到加性噪聲干擾的情況下,多峰函數的適應度值可描述為:

式中,fσ(x) 是受到噪聲干擾后的函數值,f(x) 是未受噪聲干擾的函數值.設 R 為實數集,S?R 稱為搜索空間,即變量的可行解范圍,x=(x1,x2,···,xd)∈S為d維實變量.xi ∈[ai,bi],i=1,2,···,d,其中ai和bi分別是第i維變量的取值上邊界和下邊界.由于高斯型噪聲在自然和工程系統中普遍存在[34],因此考慮ξ為服從高斯分布的隨機變量,ξ～N(μ,σ2) ,噪聲的強度由方差σ2決定.以極小值優化為例,設x?∈S,若存在δ>0 為任意獨立的無窮小值,使得

則稱x?為f(x) 在S上的局部最優解,f(x?) 為局部最優值.噪聲環境下多峰函數優化問題可描述為:在一定強度的噪聲干擾下,根據受噪聲干擾的函數值fσ(x) ,盡可能多的定位f(x) 的多個極值點,即找到f(x) 的多個最優值及其最優解.

為全文描述方便,給出極值深井和極值分辨度的定義:

假設d維函數f(x) 包含m個極小值點(m ≥1),其中第i個極小值點為Mi(xMi,f(xMi)),其中,xMi=(xMi1,xMi2,···xMid) .在第k維坐標上,與Mi左右相鄰的兩個極大值點分別為Bk(xB,f(xB))和Ck(xC,f(xC)) .Bk和Ck的第k維坐標分別為xBk和xCk.

定義 1.在第k維坐標上,由Bk(xB,f(xB)) 和Ck(xC,f(xC)) 及函數f(x) 在該維平面上投影的曲線所確定的范圍形如開口向上的深井,稱此范圍為該極值點在第k維坐標平面上的極值深井.

定義 2.Bk(xB,f(xB)) 和Ck(xC,f(xC)) 的第k維坐標之差的絕對值記為λMi_k=|xBk ?xCk|,稱為極小值點Mi在第k維坐標平面上的極值深井的井口寬度.λMi=min1

稱為該函數的極值分辨度.

以一維函數為例,如圖1 所示,極值點M1的極值 分辨 度λM1小 于極值 點M2的極 值 分辨度λM2.當決策變量受到外界不確定因素產生的噪聲影響時,函數適應度值總是不可避免地產生波動,如果產生的波動較小,則認為解的抗噪聲性能較強,如果目標函數波動的很厲害則說明解的抗噪聲性能較差.從圖1 可以看出點M1和M2都是函數的局部極小值點,其函數適應度值相差不大.假設決策變量受到干擾產生相同程度偏移,點M2的適應度值的變化將比點M1的變化更小,從而點M2的抗噪聲性能優于點M1.

圖1 極值分辨度Fig.1 Extreme value resolution

從上面的例子和分析可以看出,極值分辨度越低,即該極值點所在深井的井口寬度越小,則該極值點的抗噪聲性能越差.工程應用時要根據實際要求的誤差允許范圍確定極值分辨度.例如,誤差允許范圍是0.05,若極值分辨度小于0.05,通過優化算法將找出井口寬度小于0.05 的極值點,這樣的點在受到噪聲干擾時,若決策變量的偏移量達到0.05,雖然沒有超過誤差允許范圍,但適應度值已經由極小值偏移到了極大值,偏移程度較嚴重,極有可能對工程設計造成不良后果.因此,選取的極值分辨度需大于誤差允許范圍.

1.2 評價指標

優化問題是工程領域普遍存在且需要解決的問題[35],涉及到的研究領域繁多,除了優化方法的依概率問題、噪聲優化問題和多峰優化問題,還包括全局優化問題[36?37]、局部收斂精度提高問題[37]、高維優化問題[38]、算法收斂速度問題[39]、多目標優化問題[40?41]、多目標魯棒優化問題[42]等.針對不同的研究領域,都有相應的評價指標.本文主要研究噪聲環境下的多峰優化問題,在這類問題的優化求解中,不僅要盡可能多地求出優化問題的全局極值點和局部極值點,而且要求出每個極值點的d維變量取值,因此定義噪聲環境下的峰值檢測率、峰值誤差和定位誤差,并將它們作為評價噪聲環境下算法性能的指標.

定義 3.假設d維函數f(x) 包含m個極值點(m ≥1) ,算法求得m?個極值點,則

稱為算法求解極值點的峰值檢測率.

稱為該算法求解極值點的峰值誤差.

稱為該算法求解極值點的定位誤差.

2 噪聲環境下基于蒲豐距離的依概率多峰優化算法

2.1 算法基本原理

在噪聲環境下的多峰優化求解問題中,噪聲干擾使得函數波形發生波動,由此引入若干局部極值點,如圖2 中的實心點.噪聲環境下多峰優化的目的是要找到函數的真實極值點位置,即圖2 中的空心點.為此,可以根據工程需求對搜索空間進行合理均勻劃分,在劃分的多個局部區域內進行單極值點搜索,從而保留下多個極值點,最后利用合適的同峰判別方法區分異峰極值點,合并同峰極值點.

圖2 函數波形與極值點Fig.2 Function waveform and extremum points

在此過程中,需要解決兩個問題:1)劃分搜索空間的依據;2)局部區域搜索時如何盡可能地避開實心點(噪聲引起的局部最優)的干擾.

本文從概率的角度出發,將蒲豐投針問題中的幾何概率規律引入解空間劃分問題,提出了噪聲環境下基于蒲豐距離的依概率多峰優化算法.首先基于蒲豐投針原理提出蒲豐距離,推導并證明了蒲豐距離與峰值檢測率的關系.在此基礎上,依據蒲豐距離對全局區域進行探索,得到多個探索點.在多個探索點之間進行局部尋優,可以保留下多個極值點.其次,在局部尋優階段,為減小算法陷入噪聲引起的局部最優的發生概率,利用區域伸縮準則改進斐波那契法,提高了算法在真實最優解鄰域附近的收斂能力,削弱了噪聲的影響.

2.2 蒲豐投針原理與蒲豐距離

18 世紀,法國數學家蒲豐(Buffon,1707～1788)提出的 “投針問題”,記載于蒲豐1777 年出版的著作中:“在平面上畫有一組間距為a的平行線,將一根長度為l(l ≤a) 的針任意擲在這個平面上,求此針與平行線中任一條相交的概率.”如圖3所示.蒲豐最早設計了投針試驗.這一方法的步驟是:

圖3 蒲豐投針實驗設計圖Fig.3 Experimental design of Buffon needles

1) 在白紙上畫數條間距為a的平行線.

2) 取長度為l(l ≤a) 的針,隨機地向畫有平行直線的紙上擲n次,觀察針與直線相交的次數.

3)計算針與直線相交的概率.

由于向桌面投針是隨機的,所以用二維隨機變量 (X,Φ) 來確定它在桌上的具體位置.設X表示針的中點到平行線的距離,Φ 表示針與平行線的夾角,則當X

則針與直線相交的概率為

若對多峰函數的求解空間進行等間隔采樣,每對相鄰的采樣點可以確定一個局部范圍.若采樣間隔設置合理,使得在此局部范圍內函數只包含唯一一個局部極值點,則在此范圍內進行單極值尋優即可找出函數的局部極值點.通過采樣得到的多對相鄰采樣點,可以找到函數的多個局部極值點.為實現等間隔采樣,將求解域在每一維上以固定長度劃分,劃分的等間隔平行線與函數的若干個交點即為采樣點,相鄰采樣點在第k(1

定理 1.設a為采樣平行線間距,以函數的極值分辨度為固定針長l,若 2a ≥l ≥a,則針同時與兩條平行線相交的概率為

若l≤a,則針同時與兩條平行線相交的概率為P2=0 .

證明.以二維平面為例,用二維隨機變量(X,Φ)來確定針在平面上的具體位置.設X表示針的端點到平行線的距離,如圖4 所示.X在 ( 0,a) 范圍內服從均勻分布,由此可以寫出X的概率密度函數

圖4 式(9)證明示意圖Fig.4 Diagram to prove (9)

Φ表示針與平行線的夾角,根據極值分辨度的定義,可知針與平行線始終為垂直方向,Φ =π/2,故當 0

若l≤a,則針同時與兩條平行線相交的概率為P2=0 .

定理 2.設a為采樣平行線間距,以函數的極值分辨度為固定針長l,若 2a ≥l ≥a,則針只與一條平行線相交的概率為

若l≤a,則針只與一條平行線相交的概率為

若l≥2a,則針只與一條平行線相交的概率為P5=0.

證明.以二維平面為例,用二維隨機變量(X,Φ)來確定針在平面上的具體位置.設X表示針的端點到平行線的距離,在 ( 0,a) 范圍內服從均勻分布,由此可以寫出X的概率密度函數為式(10)所示.Φ 表示針與平行線的夾角,因此根據極值分辨度的定義,可知針與平行線始終為垂直方向,Φ =π/2 .若2a ≥l ≥a,當l?a

若l≤a,當 0

若l≥2a,則針與一條平行線相交的概率為P5=0. □

定理 3.在噪聲環境下,對于由兩條平行線確定的局部范圍內的極值點,若針同時與兩條平行線相交,則找到該極值點的概率為P6=1?Pξ,若針只與其中一條平行線相交,則找到該極值點的概率為P7=1?Pγ ?Pξ.

證明.根據算法的基本原理和極值分辨度的定義,若針同時與兩條平行線相交,說明由兩條平行線確定的兩個采樣點包含在局部極值點所在的深井范圍內,即兩個采樣點確定的范圍內只包含唯一一個極值點,在此局部范圍內進行單極值點尋優,無噪聲環境下算法將以概率1 找到該極值點,在噪聲環境下,該區域內將出現若干噪聲引起的極值點,若以概率Pξ出現函數值低于該極值點函數值的點,則算法將保留函數值更低的點,故找到該極值點的概率為P6=1?Pξ.

若針只與一條平行線相交,則在三條平行線確定的范圍內,除去此針長l的確定的范圍,其余(2a ?l) 的范圍內,若以概率Pγ出現函數值更低的極值點,或以概率Pξ出現函數值更低的噪聲波動點,則算法將留取函數值更低的點,故P7=1?Pγ ?Pξ.

綜上可得如下推論:

推論 1.設a為采樣平行線間距,稱為蒲豐距離,以函數的極值分辨度為固定針長l,若2a ≥l ≥a,則算法找到極值分辨度最小的極值點的概率為

若l

以一維函數為例,圖5 (a)和5 (b)所示分別是2a ≥l ≥a和l

圖5 蒲豐距離與針長的關系示意圖Fig.5 Diagram of the relationship between Buffon distance and needle length

對比式(16)和(17)可以看出,在函數的極值分辨度l既定的情況下,蒲豐距離a越小,算法找到所有極值點的概率也就越大,反之則遺漏的極值點將會越多.然而,a取值過小則會帶來數據量急劇增加,延長了算法的運算時間,因此,要根據工程需要來設定a的值,例如,當a=(1/2)l時,算法找到極值分辨度最小的極值點的概率為 1?Pξ,僅受噪聲引起的局部極值點的影響,若在無噪聲環境下,則此概率為1,即當蒲豐距離為針長的一半時,算法以概率1 找到極值分辨度最小的極值點,這一結論與采樣定理相符.

推論 2.設a為采樣平行線間距,以函數的極值分辨度為固定針長l.對于全局極值點,由于Pγ=0,故

對比式(16)與(18)以及(17)與(19)可知,算法找到全局極值點的概率大于找到局部極值點的概率,因此算法具有較好的全局極值點優化性能.

2.3 改進的斐波那契法

對于無約束優化問題,斐波那契法是求解一維單峰函數的最優策略[43].將斐波那契法的變量維數從一維擴展到多維,可以解決多維函數優化問題[43].斐波那契策略通過按比例壓縮搜索區間令區間內的試探點不斷逼近最優解.斐波那契法中需要用到斐波那契數列,其通項遞推公式為:

斐波那契數列中相鄰兩項之比形成的數列收斂于黃金分割數[44],即

PMB 算法在進行局部搜索時,為使算法能夠跳出噪聲引入的局部最優,算法的搜索范圍不能只局限于初始的局部范圍,而應適當擴展,探索周圍鄰域內是否有更優點.如有更優點,則搜索區域應該適當擴展,向更優點偏移.可以利用試探點引導區域向優化點方向移動.同時,為使算法收斂,搜索區域還需進行壓縮.隨著迭代次數的增加,區域最終將收斂于可接受的精度范圍內.為此提出區域伸縮準則,定義如下:

對于由任意兩點A(xA,f(xA))和B(xB,f(xB))確定的區域邊界,若f(xA)

點C(xC,f(xC)) 用來試探新擴展的區域中是否存在更優的點,然后再以比例β對區間進行壓縮,壓縮率β根據對擴展點C(xC,f(xC)) 的試探情況進行設置.若f(xA)>f(xB) ,則選取點B(xB,f(xB))為中心,做類似擴展和壓縮操作.

利用區域伸縮準則改進斐波那契法,得到算法步驟如下:

步驟 1.選定初始區間 [a1,b1] 及求解精度ε>0,令k=1 ,若f(a1)>f(b1) 轉步驟2,否則轉步驟3;

步驟 2.計算

若f(μk)

步驟 3.計算

若f(λk)

步驟 4.置

若|bk+1?ak+1|≤ε,轉步驟7,否則令k=k+1,轉步驟2;

步驟 5.置

若|bk+1?ak+1|≤ε,轉步驟7,否則令k=k+1,轉步驟2;

步驟 6.置

若|bk+1?ak+1|≤ε,轉步驟7,否則令k=k+1,轉步驟2;

步驟 7.停止計算,取極小值點的坐標為1/2|bk+1?ak+1|.

由算法執行步驟可以看出,初始搜索區間由[a1,b1]界定,但后續的搜索范圍并不僅僅局限于[a1,b1],而是向周圍鄰域進行了適當的擴展,探索周圍是否還存在更優的點.雖然每次都對區間進行了擴展,但是每次計算結束時都根據探索的結果對區間進行壓縮,根據選取的擴展點不同,第k次計算后的區域壓縮率為β1或β2,

由斐波那契數列的特點,可知

可見,算法的搜索區間在逐漸縮小,最后可以收斂到設定的精度范圍內.

為了對比改進前的斐波那契法與改進后的斐波那契法,以受噪聲干擾的一維函數為例,圖6 的9個子圖展示了改進的斐波那契法的區域伸縮過程,圖7 的4 個子圖展示了改進前的斐波那契法的區域收縮過程.其中實線波形是受噪聲干擾的函數波形,點‘·’ 表示區域邊界點ai和bi,點‘?’代表試探點λi和μi.圖6(a)表示局部搜索的初始區間由[a1,b1]=[2.6700,3.0300] 確定.由于f(a1)>f(b1),根據式(24)可以得到式(33):

由于f(μ1)

通過比較圖6 中的 9 個子圖,我們可以觀察到改進后的斐波那契法的搜索區間可以擴展到具有更優解的鄰域,而不是初始時的局部范圍.而從圖6可以看到,傳統的斐波那契法的搜索區間始終限制在初始的局部范圍內.此外,從圖7 中可以看出,斐波那契法在第4 次迭代時區間長度就壓縮到了0.0758,而改進后的斐波那契法在第7 次迭代時區間長度才壓縮到0.0704,說明引入了區域伸縮準則的斐波那契法每次迭代都遵循先擴展再壓縮的規則,因此區域壓縮和算法收斂的速度比改進前的斐波那契法下降了,但是改進后的算法可以搜索到初始區間附近鄰域范圍內的極小值點,提高了算法在函數真實最優解鄰域附近的收斂能力,避免其陷入噪聲引入的局部最優.

圖6 改進的斐波那契法的區域伸縮過程Fig.6 The process of regional scaling of the improved Fibonacci method

圖7 斐波那契法的區域收縮過程Fig.7 The process of regional shrink of the Fibonacci method

2.4 PMB 算法流程

步驟 1.初始化設置.根據實際需求的極值分辨度確定蒲豐距離a和求解精度ε.

步驟 2.在全局范圍內以蒲豐距離a進行等間隔采樣,得到采樣點集合S={A1,A2,···,Ak}.

步驟 3.以采樣點集合S中的相鄰點作為初始區間的兩個端點,在局部范圍內利用區域伸縮的斐波那契法進行單極值點尋優,可以得到k?1 個極值點{E1,E2,···,Ek?1}.

步驟 4.利用改進型插點法[45]對得到的極值點進行同峰判斷.

步驟 5.利用歸并方法[1]將同峰的極值點進行合并,并取這些點中的最大(最小)值最為最終解.

2.5 PMB 算法的多級劃分策略

為了提高PMB 算法的求解精度,同時也為了提高算法在多維函數上的優化效率,可以采用多級劃分策略.對于N級劃分策略,首先依據蒲豐距離對全局區域進行劃分,得到多個探索點,在多個探索點之間進行局部尋優,可以保留下第一級的多個極值點.對第一級的極值點的極值大小進行比較后,選取一定數量的較優極值點,對它們所在的區域仍然依據蒲豐距離進行下一級劃分,得到多個探索點,在多個探索點之間再進行局部尋優,從而得到第二級的多個極值點.依此類推,直到劃分到第N級.對第N級得到的極值點,利用改進型插點法[45]進行同峰判斷,再利用歸并方法[1]將同峰的極值點進行合并,并取這些點中的最大(最小)值最為最終解.

以圖8 (a)所示的二維平面為例,首先在每一維上進行等距離劃分,可以得到若干交點,即為第一級的采樣點,如圖8 (a)中的實心交點所示.每一維上劃分的間隔距離可以相同,也可以不同,一般情況下設置為每一維上的劃分間隔都是相同的,特殊情況除外.如圖8 (a)所示,雖然兩個維度上的范圍尺度不同,但不影響對它們進行等距離的劃分.然后每個實心交點與其相鄰的點之間進行局部尋優,得到若干第一級極值點.以圖8 (a)中點A為例,它將分別與點B、C、D、E之間進行局部尋優.在第二級劃分時,若選中了A和D局部尋優得到的極值點,則將對A和D兩點所在的公共區域進行第二級劃分,得到第二級的采樣點,如圖8 (b)所示.可以證明,若n維變量空間的每一維劃分為m段區間,則在每一維上可以得到m+1 個采樣點.所有采樣點經局部尋優后將得到m×(m+1)×2(2×n?3)個極值點.以三維變量空間為例,假設每一維的長度域為[?100,100],第一級若取蒲豐距離a1=5,則每一維可得到m1=40 段區間和41 個采樣點.所有采樣點經局部尋優后將得到m1×(m1+1)×2(2×n?3)=40×41×23=13120個第一級極值點.從第一級極值點中選出部分較優極值點,對它們所在的區域依據蒲豐距離a2=0.1 進行下一級劃分,對于其中一個子區域而言,其每一維的長度域為5,按照a2=0.1 劃分,每一維可以得到m2=50 段區間和51 個采樣點,從而每個區間可以得到m2×(m2+1)×2(2×n?3)=50×51×23=20400個第二級極值點,之后執行類似操作,直到達到指定的劃分等級.

圖8 PMB 算法的多級劃分策略Fig.8 The multilevel partition strategy of PMB algorithm

從上述過程可以看出,初始時每一維的長度域為200,經過第一級劃分后,每一維的長度域為5,經過第二級劃分后,每一維的長度域為0.1,若第二級只選取1 個最優區域進行劃分,則需要局部尋優的次數為13120+20400=33520.若不采取多級劃分策略,直接對初始時長度域以a2=0.1的蒲豐距離進行劃分,則m=2000,需要局部尋優的次數為m×(m+1)×2(2×n?3)=2000×2001×23=32016000.可見采取多級劃分策略可以省去很多計算時間,這在多維函數的優化問題上優勢更為明顯.此外,多級劃分策略不僅在同級區域內橫向可并行執行,不同級區域也可縱向并行執行,計算過程不會相互干涉.

3 實驗仿真與分析

3.1 實驗設計與測試函數

為了驗證本文所提出的PMB 算法的尋優結果與蒲豐距離之間的依概率關系,研究噪聲和蒲豐距離對PMB 算法尋優結果的影響,驗證PMB 算法在噪聲環境下的多極值點尋優能力,以及研究PMB算法在噪聲環境下對多維函數尋優的有效性,本文選用兩組基準測試函數研究PMB 算法的上述性能.第一組測試函數來自文獻[1]和文獻[32],如表1所示.這6 個測試函數都是多峰函數,不僅有一到多個全局極值點,還有若干局部極值點,其中,除f2,f3和f4只有唯一一個全局極值點,其他函數均有多個全局極值點.第二組測試函數是文獻[46]中給出的CEC2013 推薦基準函數,如表2 所示.其中,f1～f5是單峰函數,f6～f20是多峰函數,f21～f28是組合函數.CEC2013 被視為黑盒問題,并且不允許使用問題的顯式方程[46].

表1 測試函數集1 (TF1)Table 1 Test function set 1 (TF1)

表2 測試函數集2 (TF2) (維度為5)Table 2 Test function set 2 (TF2) (Dimension is 5)

3.2 PMB 算法依概率收斂特性驗證

通過第3.2 節的理論推導可知,PMB 算法的尋優結果與蒲豐距離之間存在依概率關系.當蒲豐距離a與針長l滿足 2a ≥l ≥a時,算法找到極值分辨度最小的極值點的概率滿足式(16),當l≤a時,概率關系滿足式(17).為了驗證上述依概率關系,在本節實驗中分別取兩種不同的蒲豐距離l≤a和2a ≥l ≥a,觀察PMB 算法的尋優結果并進行討論.為了確定針長,參考文獻[1]所得到的結果及本文定義2 可知,TF1 中的f1的極值分辨度大約為0.38,即針長l≈0.38 .分別取蒲豐距離a=0.5 (即l≤a)和a=0.2 (即 2a ≥l ≥a) 兩種情況,求解精度ε=0.01,驗證本文所提PMB 算法在無噪聲環境和不同噪聲環境下對TF1 中的f1中的所有極值點求解結果的依概率特性.

參照文獻[32]中的噪聲環境設置參數,分別取噪聲方差σ2=0.01 和σ2=0.05,重復獨立 實驗50 次、100 次和200 次,PMB 算法求得的優化數值結果列于表3 中.表中σ2表示噪聲方差,a表示蒲豐距離,Num_mean 表示算法平均搜索到的極值點數,Num_min 和Num_max 分別表示算法在重復實驗中搜索到的極值點個數的最小值和最大值,η_mean 表示平均峰值檢測率,η_global 表示全局極值點檢測率.從表3 中可以看出:

表3 針對TF1 中的 f1 取不同蒲豐距離時PMB 算法在不同噪聲環境下的優化結果Table 3 Optimization results of PMB algorithm for f1 of TF1 in different noise environments with different Buffon distances

當蒲豐距離a=0.2 時,即滿足2a ≥l ≥a時,可得出如下結論:

1)在σ2=0.01 和σ2=0.05 的噪聲環境下,重復獨立實驗50 次、100 次和200 次,PMB 算法都能找到所有極值點,η_mean 為100 %以上.重復獨立實驗中算法每次最少都能確保找到全部36 個極值點.

2)σ2=0.01 時算法最多能找到37 個極值點,σ2=0.05 算法最多能找到38 至40 個極值點,且σ2=0.05 時的η_mean 略高于σ2=0.01 時的η_mean,出現了η_mean 的值超出100 %的情況.這是由于噪聲的干擾引入了眾多的局部極值,使得算法找到的極值點數超出了原函數的極值點數.可以看出,隨著噪聲強度的增大,這種干擾越明顯,噪聲引入的局部極值點數越多.

3)在σ2=0.01 和σ2=0.05 的噪聲環境下,重復獨立實驗50 次、100 次和200 次,PMB 算法都能找到所有全局極值點,η_global 都能達到100 %.

當蒲豐距離a=0.5 時,即滿足l≤a時,有如下結論:

1)在σ2=0.01 的噪聲環境下,重復獨立實驗50 次、100 次和200 次,PMB 算法的η_mean 都是82 %左右.

2)在σ2=0.05 的噪聲環境下,重復獨立實驗50 次、100 次和200 次,PMB 算法的η_mean 都為88 %左右.

3)由于噪聲干擾會引入局部極值點,因此當噪聲強度增強時,PMB 算法的η_mean 有所增加.

4)在σ2=0.01 和σ2=0.05 的噪聲環境下,重復獨立實驗50 次、100 次和200 次,PMB 算法都能找到所有全局極值點,η_global 都能達到100 %.

綜上可知:

1)在相同的噪聲環境下,PMB 算法的平均峰值檢測率是一個固定概率,取決于算法的蒲豐距離a.對于TF1 中的f1,當 2a ≥l ≥a時,平均峰值檢測率可達到100 %,當l≤a時,平均峰值檢測率約為80 %以上.這一結果映證了推論1,即算法依固定概率找到函數的多個極值點.

2)在不同噪聲環境下取不同蒲豐距離時,PMB算法都能找到TF1 中的f1的所有全局極值點.這一結果映證了推論2,即算法找到全局極值點的概率高于找到局部極值點的概率.表明PMB 算法具有較好的全局極值點優化性能.

3)噪聲強度對峰值檢測率有一定程度的影響.由于噪聲干擾會引入局部極值點,因此當噪聲強度增強時,PMB 算法的平均峰值檢測率也會有所增加,其中包含了少數幾個噪聲引入的局部極值點.

3.3 噪聲強度與蒲豐距離對PMB 算法尋優結果的影響

首先定量分析噪聲強度和蒲豐距離對PMB 算法求解結果的影響.分別取a=0.2 和a=0.5,求解精度ε=0.01 ,參照文獻[32],分別設置σ2=0.01和σ2=0.05,PMB 算法對TF1 中的f1的一次尋優結果分別繪于圖9～圖14 中,其中,圖11～圖14的(a) 圖呈現的是算法在同峰判斷前找到的極值點,(b)圖呈現的是算法經同峰判斷后確定的極值點.

圖11 σ2 =0.05,a =0.5 時PMB 算法對TF1 中的f1的尋優結果Fig.11 Optimization results for f1 of TF1 by PMB algorithm in noise environment with σ2 =0.05 and a=0.5

從圖9～圖14 中可以看出,算法求得的極值點個數受蒲豐距離的影響較為明顯.蒲豐距離越小,PMB 算法找到的極值點越多,a=0.2 時可以找到全部極值點,a=0.5 時,PMB 算法不能找到全部極值點,個別局部極值點會被遺漏,但仍然可以找到所有全局極值點.

圖9 a =0.2 時無噪聲環境下PMB 算法對TF1 中的f1的尋優結果Fig.9 Optimization results for f1 of TF1 by PMB algorithm in noiseless environment with a =0.2

為進行定性分析,以全局極值點為例,將PMB算法求解TF1 中的f1得到的全局極值點的數值結果分別列于表4 和表5 中.

表4 a =0.2 時PMB 算法針對TF1 中的 f1 在不同噪聲環境下的全局極值點優化數值結果Table 4 Numerical results of global extremum points for f1 of TF1 searched by PMB algorithm with a =0.2 under different noise environments

表5 a =0.5 時PMB 算法針對TF1 中的 f1 在不同噪聲環境下的全局極值點優化數值結果Table 5 Numerical results of global extremum points for f1 of TF1 searched by PMB algorithm with a =0.5 under different noise environments

從表4 和表5 中可以看到,算法求解的定位誤差和峰值誤差同時受到蒲豐距離與噪聲強度的影響.在蒲豐距離相同的情況下,隨著噪聲強度的增加,全局極值點的峰值誤差Pf和定位誤差Pl也隨之增加.在噪聲強度相同的情況下,蒲豐距離越小,全局極值點的定位誤差Pl越小,定位精度越好.

除了全局極值點,PMB 算法還能求得多個局部極值點.取a=0.2,PMB 算法在σ2=0.01 和σ2=0.09 的噪聲環境中的100 次獨立重復實驗結果列于表6 中.

從表6 中可以看出,當a=0.2 時PMB 算法可以找到TF1 中的f1的全部極值點.對比文獻[1]的數值結果,可以驗證PMB 算法在噪聲環境下定位所有極值點的正確性.依據文獻[1]的數值結果計算得到PMB 算法定位每個極值點的定位誤差,繪于圖15 中.

表6 P-MQHOA[1]算法與 a =0.2 時的PMB 算法針對TF1 中的 f1 在不同環境下的所有極值點求解結果對比Table 6 Comparison of total-extremum points for f1 of TF1 searched by P-MQHOA[1] algorithm and PMB algorithm with a =0.2 under different noise environments

從圖15 中可以看出,隨著噪聲強度的增加,各個極值點的定位誤差都隨之增加.綜上可知:

圖10 a =0.5 時無噪聲環境下PMB 算法對TF1 中的f1的尋優結果Fig.10 Optimization results for f 1 of TF1 by PMB algorithm in noiseless environment with a =0.5

1)蒲豐距離的大小會對PMB 算法找到極值點的個數以及求解極值點的定位精度產生主要影響.蒲豐距離越小,算法的全極值點尋優性能就越好,遺漏的極值點越少,峰值檢測率越高,同時定位準確度越高.

2)噪聲強度也會對PMB 算法的峰值檢測率和求解極值點的定位精度產生影響.噪聲強度的增加使得極值點的峰值誤差Pf和定位誤差Pl都隨之增加,同時會引入更多的局部最優,使得峰值檢測率增加.

3.4 PMB 算法在不同噪聲環境下的多極值點尋優能力

本節實驗選用文獻[32]中的5 個測試函數,即表1 中TF1 函數f2～f6,檢驗本文所提PMB 算法在不同噪聲環境下對不同函數的多極值點尋優能力,并與文獻[32]提出的改進蝙蝠算法(Improved bat algorithm,IBA)進行對比分析.

圖12 σ2 =0.01,a =0.5 時PMB 算法對TF1 中的f1的尋優結果Fig.12 Optimization results for f1 of TF1 by PMB algorithm in noise environment with σ2 =0.01 and a=0.5

參照文獻[32] 的噪聲環境設置,分別在σ2=0.01、σ2=0.05、σ2=0.07 和σ2=0.09 的噪聲環境中利用PMB 算法對TF1 函數f2～f6進行優化求解,重復獨立實驗100 次,求解精度ε=0.01,優化數值結果列于表7 中.表中Mean 表示100 次重復獨立實驗得到的全局極值點的適應度平均值,MAPE 表示適應度平均值相對百分比誤差.

從表7 中看到,全局極值點的適應度值受噪聲的影響非常明顯,隨著噪聲強度的增加,MAPE 隨之增大.從TF1 中f2的尋優結果上可以看到,本文所提出的PMB 算法可以得到比IBA 算法更低的MAPE,而在其他函數上,PMB 算法的MAPE 高于IBA 算法,但依然呈現出平均相對百分比誤差隨著噪聲強度的增加而增大的規律.

表7 PMB 算法對TF1 中的 f 2～f6 在不同噪聲環境下的全局極值點優化數值結果Table 7 Numerical results of global extremum points for function f 2～f6 of TF1searched by PMB algorithm under different noise environments

圖13 σ2 =0.05,a =0.2 時PMB 算法對TF1 中的f1的尋優結果Fig.13 Optimization results for f1 of TF1 by PMB algorithm in noise environment with σ2 =0.05 and a=0.2

圖14 σ2 =0.01,a =0.2 時PMB 算法對TF1 中的f1的尋優結果Fig.14 Optimization results for f1 of TF1 by PMB algorithm in noise environment with σ2 =0.01 and a=0.2

圖15 a =0.2,PMB 算法在不同噪聲環境下對TF1 中的 f1 求解所有極值點的定位誤差Fig.15 Positioning errors of total-extremum points for f1 of TF1 searched by PMB algorithm with a =0.2 under different noise environments

盡管在TF1 中f3～f6上PMB 算法得到的MAPE 更高,但是在噪聲環境下衡量算法的優化性能應該更關注算法的定位誤差指標.在無噪聲環境下,衡量算法的尋優性能往往通過考察算法求得的全局極值點的適應度值與真實適應度值的誤差來得到,例如,函數f2在無噪聲情況下的全局極值點是?176.1375 (?1.3068,?1.4248),如果算法找到的極值點的適應度值近似為 ?176.1375,則通常認為算法已經找到了全局極值點,同時也證明了算法的全局優化性能較好.而在噪聲環境下,點 (?1.3068,?1.4248)處的函數值將發生變化,偏離原來的函數值 ?176.1375,因此,衡量算法在噪聲環境下優化求解性能的指標不應是找到函數值為 ?176.1375 的點,這樣的點極有可能已經不是原函數的全局極值點,算法優化求解的目的應該是力圖找到(?1.3068,?1.4248)這個點,因為它才是原函數的全局極值點位置.因此,在噪聲環境下,求解極值點的坐標顯得尤為重要,它是判斷算法是否能夠找到全局極值點的有力依據,而定位誤差則反映了算法定位全局極值點的精確度.

PMB 算法在不同噪聲環境下求解TF1 中f2～f5得到的全局極值點的定位誤差分別列于表8和表9 中.

從表8 和表9 中可以看到,PMB 算法求出了每個極值點對應的坐標值,明確了全局極值點的位置,可以直觀地與無噪聲時的真實極值點位置做對比,從而證明PMB 算法在噪聲環境下定位全局極值點的準確性.而文獻[32]只給出了IBA 算法求解全局極值點的Pl結果,并未給出具體的坐標值.

表8 PMB 算法對TF1 中 f 2～f4 在不同噪聲環境下得到的全局極值點的定位誤差Table 8 Positioning errors of global extremum points for function f 2～f4 of TF1 searched by PMB algorithm under different noise environments

表9 PMB 算法對TF1 中的 f 5～f6 在不同噪聲環境下的全局極值點優化數值結果Table 9 Numerical results of global extremum points for function f 5～f6 of TF1searched by PMB algorithm under different noise environments

同時,對比兩種算法得到的Pl值可以看到,除了4 個極值點(f2在σ2=0.09 時、f4在σ2=0.01和σ2=0.05 時、f6的第3 個極值點在σ2=0.09時)外,PMB 算法在不同噪聲環境下求解TF1 中f2～f5得到的全局極值點的定位誤差均小于IBA算法得到的結果.即PMB 算法在不同噪聲環境下對TF1 中f2～f5的全局極值點定位比IBA 算法更為精確.

此外,文獻[32]的IBA 算法只給出了TF1 中f2～f5的全局極值點求解結果,對其他局部極值點并未討論.而PMB 算法運行一次即可得到全部極值點和多個局部極值點.以TF1 中f2為例,取蒲豐距離a=1 時,PMB 算法運行一次得到的優化結果如圖16 所示.

從圖16 中可以看出,TF1 的f2是一個多峰函數,其在σ2=0.05 的噪聲環境下出現了無窮多的噪聲峰值點,PMB 算法有效的找到了它的1 個全局極值點及170 個局部極值點.綜上可知:

圖16 a =1,σ2 =0.05,PMB 算法對TF1 中f2的尋優結果Fig.16 Optimization results for f2 of TF1 by PMB algorithm in noise environment with σ2 =0.05 and a=1

1) PMB 算法在噪聲環境下可以一次性得到極值點的適應度值和對應坐標,可以為生產實際提供明確的決策變量.

2) PMB 算法求解的極值點位置精度總體高于IBA 算法.

3) PMB 算法不僅能夠求得噪聲環境下的全局極值點位置,還能得到多個局部極值點的位置,為生產實際提供更多的備選方案.

3.5 PMB 算法在CEC2013 測試函數上與PSO算法的對比

本節實驗選用文獻[46]中給出的CEC2013 推薦基準函數,即表2 中的函數f1～f28,檢驗PMB算法在噪聲環境下對多維函數尋優的有效性,并與PSO 算法進行對比分析.為了檢驗PMB 算法和PSO 算法在噪聲環境中尋優的準確性,首先給出了無噪聲環境下的優化結果,然后與噪聲環境下的優化結果進行了比較.實驗中改進的斐波那契法的求解精度ε設置為1 × 10?5,針對CEC2013 的5 維測試函數采用5 級劃分策略.

1) 無噪聲環境下的比較

PMB 算法和 PSO 算法在無噪聲環境下對TF2 測試函數進行尋優,獲得的優化結果列于表10中,其中t是完成一次實驗的時間.

從表10 中可以得出以下結論:

表10 PMB 算法和PSO 算法對TF2 在無噪聲環境下得到的全局極值點Table 10 Global extremum points of TF2 obtained by PMB algorithm and PSO algorithm in noiseless environment

a)從函數值的角度來看,PMB 對 24 個測試函數得到的函數最小值更接近這些函數的全局最小值,精度高于PSO.PMB 得到的這24 個測試函數的數值結果已在表中用粗體標示出.PSO 僅在4 個函數上得到的極值比PMB 更接近函數的全局最小值,在其他24 個函數上陷入了局部最優.且PSO在單峰函數f2、多峰函數f8～f15和組合函數f21～f28上得到的極值點的適應度值偏離函數的全局最小值較大,在表中已用下劃線標示出.其中,在函數f2上的偏離值為691.6966.這說明PSO 算法很容易陷入局部最優,而PMB 算法具有很好的全局尋優性能,不容易陷入局部最優.

b)對比兩個算法運行的時間t可以看出,為了跳出局部最優和保留多個極值點,PMB 算法需要花費比PSO 算法更多的計算時間.

2)σ2=0.01 的噪聲環境下比較

PMB 算法和 PSO 算法在σ2=0.01 的噪聲環境下對TF2 測試函數進行尋優,獲得的優化結果分別列于表11 和表12 中.

對比表11 和表12 中可以得出以下結論:

表11 PSO 算法對TF2 在 σ2 =0.01 的噪聲環境下得到的全局極值點Table 11 Global extremum points of TF2 obtained by PSO algorithm in noise environment of σ2 =0.01

表12 PMB 算法對TF2 在 σ2 =0.01 的噪聲環境下得到的全局極值點Table 12 Global extremum points of TF2 obtained by PMB algorithm in noise environment of σ2 =0.01

表12 PMB 算法對TF2 在 σ2 =0.01 的噪聲環境下得到的全局極值點 (續表)Table 12 Global extremum points of TF2 obtained by PMB algorithm in noise environment of σ2 =0.01 (continued)

a) 通過比較Pl的數值結果,可以看出 PMB在25 個測試函數上得到的極值點的Pl小于PSO,這25 個數值結果已在表11 中用粗體標示出.這表明PMB 在噪聲環境和無噪聲環境下獲得的極點位置偏差很小,說明PMB 算法具有良好的穩定性和抗噪性能.然而,PSO 在噪聲環境中獲得的結果與在無噪聲環境中獲得的結果差距較大,其中在20個測試函數上的Pl值超過了10,在表11 中已經用下劃線標示出.這表明PSO 的穩定性差,這使得它易受噪聲干擾,抗噪性能較差.

b)對比兩個算法的運行時間t可以看出,在噪聲環境中,PMB 需要花費更多的時間來跳出由噪聲引起的局部最優.PSO 的收斂速度在噪聲的影響下也會減慢,但往往會收斂到噪聲引起的局部最優.

3) 多極值點尋優結果

PMB 算法可以在噪聲環境中實現多極值點優化.對于多峰函數f6,f7,f8,f16,f19和f20,PMB 算法得到的多個極值點的數值結果列于表13中.由于篇幅有限,每個函數只列出 5 個極值點的數值結果.

從表13 中可以看出,PMB 算法可以在無噪聲環境和噪聲環境中找到多峰函數的多個極值點,說明PMB 算法可以在噪聲環境中實現多維、多峰函數的多極值點優化.

表13 PMB 算法對TF2 中部分函數在無噪聲環境和 σ2 =0.01 的噪聲環境下的多極值點優化結果Table 13 Optimization results of multiple extremum points for some functions of TF2 obtained by PMB algorithm in noiseless environment and noise environment of σ2 =0.01

表13 PMB 算法對TF2 中部分函數在無噪聲環境和 σ2 =0.01 的噪聲環境下的多極值點優化結果 (續表)Table 13 Optimization results of multiple extremum points for some functions of TF2 obtained by PMB algorithm in noiseless environment and noise environment of σ2 =0.01 (continued)

綜上可知:

a) PMB 算法可以在無噪聲和噪聲環境中準確定位測試函數的真正全局極值點,反映了PMB 算法良好的穩定性和抗噪性能.PSO 算法在無噪聲環境中容易陷入局部最優,而在噪聲環境中容易陷入由噪聲引起的局部最優.因此,PSO 算法的穩定性和抗噪性能較差.

b)PSO 算法運行一次只能獲得一個極值點,而PMB 算法運行一次可以獲得多個極值點.表明PMB 算法可以在噪聲環境下找到多維、多峰函數的多個全局和局部極值點.

c)為了跳出局部最優和保留多個極值點,PMB算法需要花費比 PSO 算法更多的計算時間.PSO的收斂速度在噪聲的影響下也會減慢,但它更容易收斂到局部極值點.

4 結論

針對噪聲環境下的多極值點尋優,本文采用一種定概率的方法來解決這類隨機優化問題.從蒲豐投針的定概率原理出發,提出了噪聲環境下基于蒲豐距離的依概率多峰優化算法(PMB).理論推導證明了蒲豐距離和極值分辨度依概率影響算法的峰值檢測率.驗證了在不同的噪聲條件下,PMB 算法依概率收斂到函數的多個極值點,且算法找到全局極值點概率高于找到局部極值點的概率;驗證了蒲豐距離影響PMB 算法的全極值點尋優性能和求解極值點的定位精度,噪聲強度影響算法的峰值檢測率和定位精度;對比噪聲環境下的改進蝙蝠算法,PMB 算法具有更好的極值點定位精度和較好的多極值點尋優特性;對比PSO 算法在5 維CEC2013測試函數集上的表現,PMB 算法具有更好的多維函數尋優能力、抗噪聲性能和多極值點尋優性能.從而使得PMB 算法能在生產實際中提供更準確的決策變量和更多的優化方案.噪聲環境下的依概率優化算法的理論和應用研究剛剛起步,作者后續工作將進一步研究提高PMB 算法對高維問題的處理效率.