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

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

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

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

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

第1 節(jié)對噪聲環(huán)境下的多峰優(yōu)化問題進(jìn)行數(shù)學(xué)描述,并說明評價指標(biāo).第2 節(jié)詳細(xì)描述了本文提出的PMB算法的基本原理和理論推導(dǎo).第3 節(jié)是論文的仿真實驗與結(jié)果分析,用以驗證算法的有效性.第4 節(jié)給出結(jié)論和將來的研究方向.

1 問題描述及評價指標(biāo)

1.1 問題描述

在受到加性噪聲干擾的情況下,多峰函數(shù)的適應(yīng)度值可描述為:

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

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

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

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

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

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

稱為該函數(shù)的極值分辨度.

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

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

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

1.2 評價指標(biāo)

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

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

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

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

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

2 噪聲環(huán)境下基于蒲豐距離的依概率多峰優(yōu)化算法

2.1 算法基本原理

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

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

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

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

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

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

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

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

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

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

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

則針與直線相交的概率為

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

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

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

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

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

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

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

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

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

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

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

若l≤a,當(dāng) 0

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

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

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

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

綜上可得如下推論:

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

若l

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

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

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

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

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

2.3 改進(jìn)的斐波那契法

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

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

PMB 算法在進(jìn)行局部搜索時,為使算法能夠跳出噪聲引入的局部最優(yōu),算法的搜索范圍不能只局限于初始的局部范圍,而應(yīng)適當(dāng)擴(kuò)展,探索周圍鄰域內(nèi)是否有更優(yōu)點.如有更優(yōu)點,則搜索區(qū)域應(yīng)該適當(dāng)擴(kuò)展,向更優(yōu)點偏移.可以利用試探點引導(dǎo)區(qū)域向優(yōu)化點方向移動.同時,為使算法收斂,搜索區(qū)域還需進(jìn)行壓縮.隨著迭代次數(shù)的增加,區(qū)域最終將收斂于可接受的精度范圍內(nèi).為此提出區(qū)域伸縮準(zhǔn)則,定義如下:

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

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

利用區(qū)域伸縮準(zhǔn)則改進(jìn)斐波那契法,得到算法步驟如下:

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

步驟 2.計算

若f(μk)

步驟 3.計算

若f(λk)

步驟 4.置

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

步驟 5.置

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

步驟 6.置

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

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

由算法執(zhí)行步驟可以看出,初始搜索區(qū)間由[a1,b1]界定,但后續(xù)的搜索范圍并不僅僅局限于[a1,b1],而是向周圍鄰域進(jìn)行了適當(dāng)?shù)臄U(kuò)展,探索周圍是否還存在更優(yōu)的點.雖然每次都對區(qū)間進(jìn)行了擴(kuò)展,但是每次計算結(jié)束時都根據(jù)探索的結(jié)果對區(qū)間進(jìn)行壓縮,根據(jù)選取的擴(kuò)展點不同,第k次計算后的區(qū)域壓縮率為β1或β2,

由斐波那契數(shù)列的特點,可知

可見,算法的搜索區(qū)間在逐漸縮小,最后可以收斂到設(shè)定的精度范圍內(nèi).

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

由于f(μ1)

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

圖6 改進(jìn)的斐波那契法的區(qū)域伸縮過程Fig.6 The process of regional scaling of the improved Fibonacci method

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

2.4 PMB 算法流程

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

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

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

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

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

2.5 PMB 算法的多級劃分策略

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

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

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

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

3 實驗仿真與分析

3.1 實驗設(shè)計與測試函數(shù)

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

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

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

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

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

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

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

當(dāng)蒲豐距離a=0.2 時,即滿足2a ≥l ≥a時,可得出如下結(jié)論:

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

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

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

當(dāng)蒲豐距離a=0.5 時,即滿足l≤a時,有如下結(jié)論:

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

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

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

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

綜上可知:

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

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

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

3.3 噪聲強(qiáng)度與蒲豐距離對PMB 算法尋優(yōu)結(jié)果的影響

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

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

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

圖9 a =0.2 時無噪聲環(huán)境下PMB 算法對TF1 中的f1的尋優(yōu)結(jié)果Fig.9 Optimization results for f1 of TF1 by PMB algorithm in noiseless environment with a =0.2

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

表4 a =0.2 時PMB 算法針對TF1 中的 f1 在不同噪聲環(huán)境下的全局極值點優(yōu)化數(shù)值結(jié)果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 在不同噪聲環(huán)境下的全局極值點優(yōu)化數(shù)值結(jié)果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 中可以看到,算法求解的定位誤差和峰值誤差同時受到蒲豐距離與噪聲強(qiáng)度的影響.在蒲豐距離相同的情況下,隨著噪聲強(qiáng)度的增加,全局極值點的峰值誤差Pf和定位誤差Pl也隨之增加.在噪聲強(qiáng)度相同的情況下,蒲豐距離越小,全局極值點的定位誤差Pl越小,定位精度越好.

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

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

表6 P-MQHOA[1]算法與 a =0.2 時的PMB 算法針對TF1 中的 f1 在不同環(huán)境下的所有極值點求解結(jié)果對比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 中可以看出,隨著噪聲強(qiáng)度的增加,各個極值點的定位誤差都隨之增加.綜上可知:

圖10 a =0.5 時無噪聲環(huán)境下PMB 算法對TF1 中的f1的尋優(yōu)結(jié)果Fig.10 Optimization results for f 1 of TF1 by PMB algorithm in noiseless environment with a =0.5

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

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

3.4 PMB 算法在不同噪聲環(huán)境下的多極值點尋優(yōu)能力

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

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

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

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

表7 PMB 算法對TF1 中的 f 2～f6 在不同噪聲環(huán)境下的全局極值點優(yōu)化數(shù)值結(jié)果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的尋優(yōu)結(jié)果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的尋優(yōu)結(jié)果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 算法在不同噪聲環(huán)境下對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 更高,但是在噪聲環(huán)境下衡量算法的優(yōu)化性能應(yīng)該更關(guān)注算法的定位誤差指標(biāo).在無噪聲環(huán)境下,衡量算法的尋優(yōu)性能往往通過考察算法求得的全局極值點的適應(yīng)度值與真實適應(yīng)度值的誤差來得到,例如,函數(shù)f2在無噪聲情況下的全局極值點是?176.1375 (?1.3068,?1.4248),如果算法找到的極值點的適應(yīng)度值近似為 ?176.1375,則通常認(rèn)為算法已經(jīng)找到了全局極值點,同時也證明了算法的全局優(yōu)化性能較好.而在噪聲環(huán)境下,點 (?1.3068,?1.4248)處的函數(shù)值將發(fā)生變化,偏離原來的函數(shù)值 ?176.1375,因此,衡量算法在噪聲環(huán)境下優(yōu)化求解性能的指標(biāo)不應(yīng)是找到函數(shù)值為 ?176.1375 的點,這樣的點極有可能已經(jīng)不是原函數(shù)的全局極值點,算法優(yōu)化求解的目的應(yīng)該是力圖找到(?1.3068,?1.4248)這個點,因為它才是原函數(shù)的全局極值點位置.因此,在噪聲環(huán)境下,求解極值點的坐標(biāo)顯得尤為重要,它是判斷算法是否能夠找到全局極值點的有力依據(jù),而定位誤差則反映了算法定位全局極值點的精確度.

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

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

表8 PMB 算法對TF1 中 f 2～f4 在不同噪聲環(huán)境下得到的全局極值點的定位誤差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 在不同噪聲環(huán)境下的全局極值點優(yōu)化數(shù)值結(jié)果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 算法在不同噪聲環(huán)境下求解TF1 中f2～f5得到的全局極值點的定位誤差均小于IBA算法得到的結(jié)果.即PMB 算法在不同噪聲環(huán)境下對TF1 中f2～f5的全局極值點定位比IBA 算法更為精確.

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

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

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

1) PMB 算法在噪聲環(huán)境下可以一次性得到極值點的適應(yīng)度值和對應(yīng)坐標(biāo),可以為生產(chǎn)實際提供明確的決策變量.

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

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

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

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

1) 無噪聲環(huán)境下的比較

PMB 算法和 PSO 算法在無噪聲環(huán)境下對TF2 測試函數(shù)進(jìn)行尋優(yōu),獲得的優(yōu)化結(jié)果列于表10中,其中t是完成一次實驗的時間.

從表10 中可以得出以下結(jié)論:

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

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

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

2)σ2=0.01 的噪聲環(huán)境下比較

PMB 算法和 PSO 算法在σ2=0.01 的噪聲環(huán)境下對TF2 測試函數(shù)進(jìn)行尋優(yōu),獲得的優(yōu)化結(jié)果分別列于表11 和表12 中.

對比表11 和表12 中可以得出以下結(jié)論:

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

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

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

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

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

3) 多極值點尋優(yōu)結(jié)果

PMB 算法可以在噪聲環(huán)境中實現(xiàn)多極值點優(yōu)化.對于多峰函數(shù)f6,f7,f8,f16,f19和f20,PMB 算法得到的多個極值點的數(shù)值結(jié)果列于表13中.由于篇幅有限,每個函數(shù)只列出 5 個極值點的數(shù)值結(jié)果.

從表13 中可以看出,PMB 算法可以在無噪聲環(huán)境和噪聲環(huán)境中找到多峰函數(shù)的多個極值點,說明PMB 算法可以在噪聲環(huán)境中實現(xiàn)多維、多峰函數(shù)的多極值點優(yōu)化.

表13 PMB 算法對TF2 中部分函數(shù)在無噪聲環(huán)境和 σ2 =0.01 的噪聲環(huán)境下的多極值點優(yōu)化結(jié)果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 中部分函數(shù)在無噪聲環(huán)境和 σ2 =0.01 的噪聲環(huán)境下的多極值點優(yōu)化結(jié)果 (續(xù)表)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 算法可以在無噪聲和噪聲環(huán)境中準(zhǔn)確定位測試函數(shù)的真正全局極值點,反映了PMB 算法良好的穩(wěn)定性和抗噪性能.PSO 算法在無噪聲環(huán)境中容易陷入局部最優(yōu),而在噪聲環(huán)境中容易陷入由噪聲引起的局部最優(yōu).因此,PSO 算法的穩(wěn)定性和抗噪性能較差.

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

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

4 結(jié)論

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