黃懿, 梁放馳, 范成禮, 宋占福

(1.空軍工程大學(xué) 基礎(chǔ)部, 陜西 西安 710051; 2.空軍工程大學(xué) 防空反導(dǎo)學(xué)院, 陜西 西安 710051)

粒子群優(yōu)化算法(PSO)是一種群體性智能搜索算法[1-3],由Kenney于1995年提出,并因?qū)崿F(xiàn)容易、精度高、收斂快等優(yōu)點(diǎn)成為國(guó)內(nèi)外研究的熱點(diǎn)。但PSO算法在求解高維多峰問題時(shí)容易出現(xiàn)“早熟”現(xiàn)象,不能完全保證求得全局最優(yōu)[4]。針對(duì)此問題,國(guó)內(nèi)外學(xué)者提出了許多改進(jìn)策略[5-15],如調(diào)整參數(shù)、精英選擇和混合算法等,或在前人的基礎(chǔ)上增加優(yōu)化因子。文獻(xiàn)[7-9]通過動(dòng)態(tài)和自適應(yīng)控制慣性權(quán)重提高算法的搜索和挖掘能力,但其搜索范圍不一定能夠覆蓋整個(gè)空間,依然存在出現(xiàn)局部最優(yōu)的情況。文獻(xiàn)[10]提出了一種無慣性的自適應(yīng)精英變異策略,加快了算法的收斂過程,擴(kuò)大了種群搜索范圍,但在高維問題求解上還需進(jìn)一步實(shí)驗(yàn)驗(yàn)證。文獻(xiàn)[11]根據(jù)個(gè)體與全局最優(yōu)粒子間的距離分別對(duì)慣性系數(shù)ω、學(xué)習(xí)因子c1和c2求導(dǎo),給出了3種參數(shù)的確定性變化方向,達(dá)到參數(shù)自適應(yīng)控制的目的,但對(duì)局部最優(yōu)分散在整個(gè)搜索空間,并且與全局最優(yōu)相距很遠(yuǎn)的復(fù)雜問題求解能力不強(qiáng)。文獻(xiàn)[12]在自適應(yīng)調(diào)整慣性權(quán)重的量子粒子群優(yōu)化算法基礎(chǔ)上,對(duì)粒子位置進(jìn)行了周期性變異,提高了全局搜索精度,但全局判據(jù)僅作為判斷優(yōu)化結(jié)果全局性的依據(jù),不會(huì)擴(kuò)大算法搜索范圍。文獻(xiàn)[13]為解決粒子種群多樣性和收斂性的矛盾,引入了動(dòng)態(tài)劃分多種群重構(gòu)粒子作為引導(dǎo)因子,對(duì)執(zhí)行階段的最優(yōu)個(gè)體實(shí)施混合變異,對(duì)時(shí)變概率實(shí)施反向?qū)W習(xí)或鄰域擾動(dòng)策略,提高算法的開發(fā)與勘探能力,但頻繁使用該策略反而會(huì)降低部分函數(shù)的求解精度。文獻(xiàn)[14]在前人基礎(chǔ)上,提出了一種自適應(yīng)局部搜索啟動(dòng)策略,提高了算法的收斂速度和精度,但其全局搜索能力有待驗(yàn)證。文獻(xiàn)[15-16]分別將混沌云和單純形與基本粒子群算法相結(jié)合,以提高算法的全局搜索能力,多用于多模態(tài)復(fù)雜問題求解,對(duì)目標(biāo)函數(shù)求解問題需要進(jìn)一步驗(yàn)證。文獻(xiàn)[17]提出粒子速度或位置小概率隨機(jī)變異與自適應(yīng)逃逸策略相結(jié)合,但求解高維多峰等復(fù)雜問題時(shí),其收斂速度較慢,需要迭代2 000次以上,才能求出最優(yōu)值。針對(duì)多模態(tài)優(yōu)化問題,文獻(xiàn)[18]通過構(gòu)建集成代理輔助模型,解決了區(qū)間多模態(tài)粒子群優(yōu)化計(jì)算代價(jià)高昂?jiǎn)栴},但對(duì)多目標(biāo)多模態(tài)的適用性仍需進(jìn)一步驗(yàn)證?？傊?以上算法的改進(jìn)大多采取參數(shù)選擇或參數(shù)自適應(yīng)控制策略,或混合其他算法,針對(duì)高維復(fù)雜問題的求解能力略顯不足,不能從根本上克服“早熟”的固有弊端。

基于以上分析,根據(jù)粒子群在空間中的搜索和分布特點(diǎn),通過增加隨機(jī)變異和感知因子,改進(jìn)粒子群的速度和位置更新策略,提出帶隨機(jī)變異因子和感知因子的粒子群優(yōu)化算法(PSORMP),擴(kuò)大粒子在空間中的搜索范圍,有效解決了粒子群因搜索范圍不足或粒子過于聚集而陷入局部最優(yōu)問題。通過典型函數(shù)測(cè)試、算法對(duì)比實(shí)驗(yàn)、參數(shù)影響分析等仿真實(shí)驗(yàn),驗(yàn)證了PSORMP算法具有很強(qiáng)的快速收斂、全局搜索與精確挖掘能力。

1 基本PSO算法

設(shè)一個(gè)D維空間中,由N個(gè)初始搜索粒子組成一個(gè)群落,則第k代第i個(gè)粒子的D維向量表示為

(1)

第k代第i個(gè)粒子的飛行速度為

(2)

截至k代,第i個(gè)粒子經(jīng)歷的最優(yōu)位置稱為個(gè)體最優(yōu),記為

(3)

截至k代,整個(gè)粒子群經(jīng)歷的最優(yōu)位置稱為全局最優(yōu),記為

(4)

由此,基本PSO算法粒子的速度和位置更新公式為

(5)

式中:c1和c2為學(xué)習(xí)因子;r1和r2為[0,1]范圍內(nèi)的隨機(jī)數(shù)。

針對(duì)慣性系數(shù)ω,采用非線性遞減權(quán)重策略

(6)

式中:f表示粒子實(shí)時(shí)的目標(biāo)函數(shù)值;favg和fmin分別表示當(dāng)前粒子群的平均值和最小目標(biāo)值[19]。

由基本PSO算法的迭代公式可以發(fā)現(xiàn),粒子的尋優(yōu)方向由粒子群的自身歷史最優(yōu)位置和全局最優(yōu)位置所決定,因此,如果全局最優(yōu)位置是解空間的局部最優(yōu)位置,就很容易導(dǎo)致粒子群陷入局部收斂。許多高維空間求解問題都是復(fù)雜多峰函數(shù),如果算法跳出局部最優(yōu)的能力不足,這些峰值很容易吸引粒子群發(fā)生“早熟”現(xiàn)象,算法的可靠性和穩(wěn)定性難以保證。

2 PSORMP算法

為了使算法更具跳出局部最優(yōu)能力,根據(jù)粒子群的運(yùn)動(dòng)特性,提出帶隨機(jī)變異及感知因子的PSO算法,改變粒子的速度和位置更新策略,以提高全局搜索與挖掘能力。

2.1 帶隨機(jī)變異因子的速度更新策略

為擴(kuò)大粒子的搜索范圍,避免粒子群受初始種群的限制,在速度更新公式中增加一個(gè)基于粒子自身鄰域、個(gè)體最優(yōu)和全局最優(yōu)的隨機(jī)變異因子,以提高粒子的運(yùn)動(dòng)能力,更新的速度公式為

(9)

(10)

式中:r4為[-0.5,0.5]的隨機(jī)數(shù)(由函數(shù)測(cè)試得出,具體見本文3.3節(jié));xmax為最大可行變異區(qū)間,這里同自變量的取值范圍。

(11)

(12)

最后,進(jìn)行負(fù)理想點(diǎn)映射,得映射點(diǎn)xR

xR=xC+α(xC-xF)

(13)

式中,α為負(fù)理想點(diǎn)映射系數(shù),一般取α=1.3～0.5遞減。

圖1 為負(fù)理想點(diǎn)時(shí)粒子運(yùn)動(dòng)過程

圖2 為負(fù)理想點(diǎn)時(shí)粒子運(yùn)動(dòng)過程

2.2 帶感知因子的位置更新策略

針對(duì)算法容易陷入局部最優(yōu)的不足,本文提出一種帶感知因子的位置更新修正策略,使種群粒子盡可能分散于整個(gè)搜索空間,提升全局搜索能力。其主要思想為:粒子自身虛擬感知與其他粒子之間的距離,粒子間的距離小于平均距離的粒子,該部分粒子自身觸發(fā)感知排斥,將自身與其他粒子的距離控制在平均距離之外,從而保持跳出局部搜索。如圖3所示,黃色點(diǎn)代表個(gè)體最優(yōu)粒子,紅色點(diǎn)代表全局最優(yōu)粒子,若粒子群出現(xiàn)圖3a)表示的情況,個(gè)體最優(yōu)附近粒子群數(shù)量比全局最優(yōu)數(shù)量多,且距離較近,容易使結(jié)果陷入局部最優(yōu)。此時(shí),局部緊密粒子存在斥力,觸發(fā)感知排斥,而經(jīng)過感知因子調(diào)整后,粒子群空間分布如圖3b)所示,從而防止陷入局部最優(yōu)。

圖3 感知因子對(duì)粒子群修正示意圖

為更好地理解該策略,引入以下2個(gè)定義。

定義1各維度粒子間的距離定義為

(14)

定義2則各維度的平均距離定義為

(15)

(16)

為簡(jiǎn)化計(jì)算過程和保證種群收斂,令慣性權(quán)重系數(shù)ω3的遞減策略與慣性權(quán)重系數(shù)ω1相同,采取非線性遞減的方式,以達(dá)到后期的局部挖掘能力。

2.3 PSORMP算法步驟

根據(jù)基本粒子群算法求解過程,結(jié)合帶隨機(jī)變異粒子的速度更新策略和帶感知因子的位置更新策略,PSORMP算法的尋優(yōu)步驟為

step1 輸入初始化PSORMP算法參數(shù),設(shè)置初始種群規(guī)模N,粒子維數(shù)D,最大迭代次數(shù)Tmax,學(xué)習(xí)因子c1,c2,粒子速度閾值vmin,vmax和粒子各維閾值xmin,xmax;

step2 計(jì)算并記錄粒子群的位置和速度;

step3 計(jì)算粒子的適應(yīng)度值;

step4.1 利用隨機(jī)變異粒子的速度更新策略進(jìn)行速度更新;

step4.2 利用感知因子的位置更新策略進(jìn)行位置更新;

step6 判斷是否滿足終止條件t=Tmax,若滿足,則轉(zhuǎn)至step7,若不滿足,則轉(zhuǎn)至step4;

3 實(shí)驗(yàn)與結(jié)果分析

3.1 算法的選擇與比較

為驗(yàn)證算法的有效性和優(yōu)越性,本文選取5種算法進(jìn)行對(duì)比,分別是基本PSO算法和4個(gè)基于PSO算法的改進(jìn)算法,即PSOPC[20]、RPSO[21]、NPSO[22]和RFRPSO[23],其中,①PSOPC算法:為避免生物群在信息共享時(shí)存在自私行為導(dǎo)致形成被動(dòng)群體,從而無法獲得全局最優(yōu),提出在粒子群中加入一個(gè)被動(dòng)群模型,提高算法粒子運(yùn)動(dòng)活力。②RPSO算法:排斥PSO算法利用在粒子間設(shè)置幾種排斥機(jī)制,使種群粒子從被認(rèn)為個(gè)體最佳的位置移開,從而促使粒子探索空間中的新區(qū)域,并在后期切換原有探索模式,達(dá)到跳出局部最優(yōu)的可能。③NPSO算法:負(fù)粒子優(yōu)化算法的優(yōu)化策略是在原有粒子群優(yōu)化算法的基礎(chǔ)上,采取將粒子遠(yuǎn)離個(gè)體和群體負(fù)理想解的理念,來達(dá)到尋優(yōu)目的。④RFRPSO算法:帶反向預(yù)測(cè)與斥力因子的PSO算法,其優(yōu)化策略為降低粒子在運(yùn)動(dòng)過程中的惰性,引入反向預(yù)測(cè)因子以改變粒子速度更新方式,為使粒子分散于搜索空間,引入帶斥力的位置修正策略。以上算法的速度更新公式如表1所示。

表1 算法速度更新公式比較

3.2 測(cè)試函數(shù)的選擇與參數(shù)設(shè)置

為驗(yàn)證算法的穩(wěn)定性和可行性,本文通過求解7個(gè)具有代表性的標(biāo)準(zhǔn)基準(zhǔn)函數(shù)的最小值問題來驗(yàn)證算法,主要包括Sphere、Quartic、Rosenbrock、Griewank、Ackley、Rastrigrin和Schwefel。其中,Sphere函數(shù)除了全局極小值外,還具有D(維度)個(gè)局部極小值,對(duì)高維粒子求解困難;Quartic函數(shù)是存在隨機(jī)干擾的單峰函數(shù),對(duì)算法驗(yàn)證極具代表性;Rosenbrock函數(shù)的全局最優(yōu)位于一個(gè)狹窄的拋物線谷中,雖然山谷容易找到,但很難收斂到最小值,是很難求解極小值的典型二次函數(shù);Griewank函數(shù)具有很多局部極小值,可驗(yàn)證算法跳出局部最優(yōu)能力;Ackley函數(shù)在二維形式中,呈現(xiàn)出外部平坦,中心下沉的一個(gè)深坑狀態(tài),并具有眾多的局部極小值,對(duì)容易產(chǎn)生“早熟”現(xiàn)象的算法求解帶來了很大困難;Rastrigrin函數(shù)為復(fù)雜多峰函數(shù),在求解過程中很容易陷入全局最優(yōu)附近的局部極小點(diǎn);如圖4所示,Schwefel函數(shù)具有均勻隨機(jī)性,其局部最優(yōu)分散在整個(gè)搜索空間,并且與全局最優(yōu)相距很遠(yuǎn),欺騙性強(qiáng),算法必須擁有很強(qiáng)的全局搜索能力才能得到全局最優(yōu)。實(shí)驗(yàn)過程中測(cè)試函數(shù)的相關(guān)信息如表2所示。

圖4 Schwefel函數(shù)的二維圖像

表2 測(cè)試函數(shù)及參數(shù)設(shè)置

實(shí)驗(yàn)過程中,設(shè)置初始粒子群規(guī)模N=200,最大迭代次數(shù)Tmax=1 000,慣性權(quán)重系數(shù)ωmax=0.9,ωmin=0.5,維數(shù)D=30,學(xué)習(xí)因子c1=c2=2,可接受誤差為0.1。實(shí)驗(yàn)環(huán)境為:AMD Ryzen 7 4800H with Radeon Graphics 2.90 GHz,RAM 16.0GB,Windows10操作系統(tǒng),MATLAB2019a。比較算法的參數(shù)根據(jù)文獻(xiàn)[19-23]的最佳參數(shù)而定,如表3所示。

表3 對(duì)比算法的參數(shù)設(shè)置

3.3 測(cè)試結(jié)果及分析

將每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行100次,記錄每個(gè)算法的成功率(S,在規(guī)定的可接受誤差范圍內(nèi),成功求解的次數(shù)與總運(yùn)行次數(shù)的比值)、平均最優(yōu)值(Bm,每種算法對(duì)每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行100次后得到的平均最優(yōu)值,此結(jié)果能衡量算法的穩(wěn)定性)、最終適應(yīng)值(Bf,表示每種算法對(duì)每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行100次后得到的最優(yōu)適應(yīng)值,此結(jié)果可以衡量算法的求解精度)、平均運(yùn)行時(shí)間(Tm每個(gè)算法對(duì)測(cè)試函數(shù)獨(dú)立運(yùn)行100次的平均運(yùn)行時(shí)間)和Adjusted p-value(P,表示本文算法與其他算法對(duì)比的顯著性差異水平),如表4～10所示,除Adjusted p-value外,最優(yōu)值用粗體顯示,次優(yōu)值用斜體顯示。各類對(duì)比算法對(duì)7個(gè)測(cè)試函數(shù)的收斂過程如圖5所示。

圖5 測(cè)試函數(shù)收斂曲線圖

表4 函數(shù)f1測(cè)試結(jié)果對(duì)比

表6 函數(shù)f3測(cè)試結(jié)果對(duì)比

表7 函數(shù)f4測(cè)試結(jié)果對(duì)比

表8 函數(shù)f5測(cè)試結(jié)果對(duì)比

表9 函數(shù)f6測(cè)試結(jié)果對(duì)比

表10 函數(shù)f7測(cè)試結(jié)果對(duì)比

表4～10的實(shí)驗(yàn)結(jié)果表明:在求解成功率上,PSORMP算法取得5個(gè)最高值,2個(gè)次高值,平均成功率為97%,明顯高于其他算法;在平均最優(yōu)值上,PSORMP算法得到6個(gè)平均最優(yōu)結(jié)果和1個(gè)平均次優(yōu)結(jié)果,PSO、RPSO、RFRPSO 3種算法共得到3個(gè)平均最優(yōu)結(jié)果和6個(gè)次優(yōu)平均結(jié)果,驗(yàn)證了本文算法的尋優(yōu)能力;在最終適應(yīng)值上,PSORMP算法得到6個(gè)最優(yōu)結(jié)果和1個(gè)次優(yōu)結(jié)果,PSO、RPSO、RFRPSO 3種算法共得到5個(gè)最優(yōu)結(jié)果和6個(gè)次優(yōu)結(jié)果,驗(yàn)證了本文算法的求解精度;在平均運(yùn)行時(shí)間上,PSORMP算法得到5個(gè)最優(yōu)結(jié)果,2個(gè)次優(yōu)結(jié)果;根據(jù)Adjusted p-value,僅在函數(shù)f3～f5測(cè)試結(jié)果中,與RFRPSO算法的對(duì)比結(jié)果為P>0.05,即沒有顯著差別,其他測(cè)試結(jié)果顯示本文算法顯著優(yōu)于其他算法,驗(yàn)證了本文算法的優(yōu)越性和穩(wěn)定性。從算法的求解精度看,本文算法針對(duì)f1,f4～f7共5個(gè)函數(shù)求得理想的全局最優(yōu),對(duì)f2,f3函數(shù)求得最優(yōu)值與理想值非常接近,并優(yōu)于其他算法。分析其主要原因在于依托增加隨機(jī)變異因子和粒子感知因子后,使粒子群在種群空間中的多樣性和聚集性達(dá)到了合理分配,從而能夠有效求解高維復(fù)雜多峰函數(shù),特別是對(duì)函數(shù)f1,f4～f7,取得了理想全局最優(yōu)解,并且在成功率和穩(wěn)定性上也優(yōu)于其他算法,表現(xiàn)了算法較強(qiáng)的魯棒性。

本文通過增加隨機(jī)變異因子和感知因子,動(dòng)態(tài)調(diào)整了粒子的散布態(tài)勢(shì),擴(kuò)大了搜索空間,調(diào)整了粒子聚集時(shí)間。從函數(shù)的收斂圖像可以看出,針對(duì)函數(shù)f1～f4,各類算法均求得了最優(yōu)值,根本原因是函數(shù)f1和f2本身就是單峰函數(shù),求解最優(yōu)值相對(duì)容易,而函數(shù)f3在維度超過15維后,函數(shù)特性趨向于單峰,函數(shù)f4的全局最優(yōu)與可達(dá)到的局部最優(yōu)之間有一道狹窄的山谷,求解最優(yōu)也相對(duì)容易,但本文算法在收斂速度和求解精度上相對(duì)于其他算法更有優(yōu)勢(shì);函數(shù)f5～f7為具有大量局部最優(yōu)的復(fù)雜多峰函數(shù),在求解過程中容易陷入局部最優(yōu),但本文算法在收斂速度、求解精度上明顯由于其他算法,尤其是相對(duì)于PSO、PSOPC、RPSO、NPSO算法,在迭代500次時(shí),本文算法均收斂并取得最優(yōu)值,而其他算法還未收斂或未求解全局最優(yōu)值.由此表明,PSORMP算法具有很好的跳出局部最優(yōu)和快速求解能力。

3.4 算法參數(shù)的影響分析

圖6 不同r4取值范圍Schwefel函數(shù)收斂曲線圖

3.5 算法復(fù)雜性分析

本文引入的隨機(jī)變異因子和感知因子,是在基本粒子群算法的基礎(chǔ)上引入的速度和位置更新策略,需進(jìn)一步分析PSORMP算法的計(jì)算復(fù)雜度,以證明算法的優(yōu)越性。假設(shè)T表示最大迭代次數(shù),D表示維度,N表示初始粒子群規(guī)模。則隨機(jī)變異因子的復(fù)雜度為Cr1(N)=D×N×T,感知因子的復(fù)雜度為Cr2(N)=N×T,基本粒子群算法的復(fù)雜度為Cr3(N)=D×N×T。則PSORMP算法復(fù)雜度為Cr(N)=D×N×T+N×T+D×N×T≈D×N×T=Cr3(N)。所以,PSORMP算法與基本PSO算法的復(fù)雜度在理論上屬于同一數(shù)量級(jí)。

為進(jìn)一步驗(yàn)證上述結(jié)論,采取3.1節(jié)和3.2節(jié)的參數(shù)設(shè)置,選用基本PSO算法、PSOPC、RPSO、NPSO、RFRPSO算法及本文算法PSORMP,對(duì)7個(gè)測(cè)試函數(shù)在同一初始種群條件下,獨(dú)立運(yùn)行100次,記錄每個(gè)函數(shù)平均運(yùn)行時(shí)間Tm,系統(tǒng)運(yùn)行環(huán)境與3.2節(jié)相同,最終結(jié)果如表11所示。其中最優(yōu)值加粗表示,次優(yōu)值用斜體表示。通過給出的結(jié)果可以看出,PSORMP算法與其他算法運(yùn)行時(shí)間處于同一數(shù)量級(jí),引入的因子沒有增加計(jì)算的復(fù)雜程度。

表11 算法運(yùn)行時(shí)間對(duì)比 s

4 結(jié) 論

本文為解決高維空間中粒子群算容易產(chǎn)生早熟問題,根據(jù)粒子群在空間中的運(yùn)動(dòng)規(guī)律和散布特點(diǎn),提出了一種帶隨機(jī)變異因子和動(dòng)態(tài)感知因子的粒子群優(yōu)化算法,改進(jìn)了粒子的速度和位置更新策略,有效解決了傳統(tǒng)PSO算法在求解高維復(fù)雜多峰函數(shù)時(shí)容易陷入局部最優(yōu)問題,提高了跳出局部最優(yōu)能力和收斂速度。并通過測(cè)試函數(shù)和算法對(duì)比,驗(yàn)證了算法的有效性和優(yōu)越性,適合解決工程應(yīng)用中高維空間中的復(fù)雜函數(shù)的優(yōu)化問題。另外,算法是否適用于動(dòng)態(tài)優(yōu)化求解及可能存在的問題是未來研究的重點(diǎn)。