馬永杰，陳滿麗，陳 敏

(西北師范大學(xué)物理與電子工程學(xué)院，甘肅 蘭州 730070)

1 引言

現(xiàn)實(shí)世界中的許多優(yōu)化問題都是多屬性的，不僅具有多個(gè)目標(biāo)、多個(gè)約束條件、高維決策變量，而且這些優(yōu)化目標(biāo)、約束條件、決策變量往往隨時(shí)間變化，該類問題即為動(dòng)態(tài)多目標(biāo)優(yōu)化問題DMOPs (Dynamic Multi-objective Optimization Problems)[1]。與動(dòng)態(tài)單目標(biāo)問題不同，它需要對(duì)相互沖突的子目標(biāo)進(jìn)行折衷，因此通常有多個(gè)最優(yōu)解，即Pareto最優(yōu)解集。

近年來，研究人員在靜態(tài)多目標(biāo)算法的基礎(chǔ)上采用各種輔助策略，使其能快速地響應(yīng)環(huán)境的改變。王洪峰等[2]總結(jié)了已有研究中的環(huán)境變化后的主要響應(yīng)策略：

(1)增加種群的多樣性[3,4]。如Deb等[3]提出的DNSGA(Dynamic Non-dominated Sort Genetic Algorithm)系列算法，通過隨機(jī)引入部分個(gè)體的DNSGA-A和對(duì)其中部分個(gè)體進(jìn)行變異的DNSGA-B，即為2種適應(yīng)不同環(huán)境變化程度的動(dòng)態(tài)多目標(biāo)優(yōu)化算法。

(2)將動(dòng)態(tài)問題轉(zhuǎn)化為靜態(tài)問題[5,6]。如劉淳安等[5]利用微積分思想，對(duì)時(shí)間區(qū)間進(jìn)行劃分，將任意的動(dòng)態(tài)多目標(biāo)優(yōu)化問題轉(zhuǎn)化為靜態(tài)多目標(biāo)優(yōu)化問題來處理。

(3)多種群的方法[7,8]。如張世文等[7]提出的基于生態(tài)策略的動(dòng)態(tài)多目標(biāo)優(yōu)化算法，對(duì)精英集和非精英集采取不同的進(jìn)化策略來響應(yīng)環(huán)境的變化。

由于動(dòng)態(tài)多目標(biāo)優(yōu)化問題中環(huán)境的變化有規(guī)律可循，近年來對(duì)于歷史信息的利用受到了研究者的廣泛重視，提出了基于記憶策略[9]、基于預(yù)測(cè)策略[10 - 13]、基于動(dòng)態(tài)進(jìn)化環(huán)境模型[14]、基于其它智能算法[15]的動(dòng)態(tài)多目標(biāo)優(yōu)化算法?；谟洃浀牟呗酝ㄟ^重復(fù)利用之前搜索到的Pareto解集來快速響應(yīng)環(huán)境的變化，這對(duì)于周期性變化的環(huán)境能取得不錯(cuò)的效果，但對(duì)于環(huán)境非周期變化的問題效果不佳；基于預(yù)測(cè)的方法是當(dāng)檢測(cè)到環(huán)境發(fā)生變化時(shí)，利用歷史信息預(yù)測(cè)新的初始種群，使種群快速響應(yīng)環(huán)境的變化。

對(duì)于動(dòng)態(tài)優(yōu)化問題，其種群多樣性關(guān)系到算法的搜索能力，而種群的收斂速度關(guān)系到能否及時(shí)響應(yīng)環(huán)境的變化。若種群多樣性過快喪失，那么由于種群中個(gè)體的相似性，會(huì)使種群過早地收斂，無法得到高質(zhì)量的解集。因此，如何平衡種群的收斂速度和多樣性，是該類算法能否成功的關(guān)鍵。由于動(dòng)態(tài)優(yōu)化問題最終得到的是Pareto最優(yōu)解集，因此如何抽取有效的歷史信息，并準(zhǔn)確預(yù)測(cè)下一時(shí)刻的初始種群便成為預(yù)測(cè)策略的難點(diǎn)。為此，本文提出一種基于Pareto解集分段預(yù)測(cè)策略的動(dòng)態(tài)多目標(biāo)進(jìn)化算法，通過所獲得的歷史信息對(duì)新環(huán)境下的種群進(jìn)行分段預(yù)測(cè)，并在預(yù)測(cè)解集的周圍自適應(yīng)地產(chǎn)生隨機(jī)個(gè)體，進(jìn)一步提高預(yù)測(cè)的準(zhǔn)確性。

2 問題描述

動(dòng)態(tài)多目標(biāo)優(yōu)化問題一般描述為：

minF(x,t)=(f1(x,t),f2(x,t),…,fm(x,t))

(1)

s.t.g(x,t)≤0,h(x,t)=0,x∈[L,V]

(2)

其中，t為時(shí)間變量，x=(x1,x2,…,xn)是n維變量，L=(l1,l2,…,ln),V=(v1,v2,…,vn)是搜索空間的上下邊界，g(x,t)和h(x,t)分別為不等式約束和等式約束，有m個(gè)目標(biāo)函數(shù)f(x,t)并隨時(shí)間變化。

設(shè)x和y為種群中任意2個(gè)不同的個(gè)體，若滿足對(duì)所有的子目標(biāo)均有x不比y差，即fk(x,t)≤fk(y,t)，k=1,2,…,m，且至少存在一個(gè)子目標(biāo)使x比y好，即?j∈{1,2,…,m}，使fj(x,t)

根據(jù)Pareto最優(yōu)解集和Pareto最優(yōu)前沿隨時(shí)間變化的情況，DMOPs可以分為以下4類[1]：

(1)Pareto最優(yōu)解集隨時(shí)間變化而Pareto最優(yōu)前沿不隨時(shí)間變化；

(2)Pareto最優(yōu)解集不隨時(shí)間變化而Pareto最優(yōu)前沿隨時(shí)間變化；

(3)Pareto最優(yōu)解集和Pareto最優(yōu)前沿都隨時(shí)間變化；

(4)Pareto最優(yōu)解集和Pareto最優(yōu)前沿都不隨時(shí)間變化。

3 分段預(yù)測(cè)算法

種群的收斂速度和多樣性的維持是算法能否快速適應(yīng)動(dòng)態(tài)環(huán)境的關(guān)鍵。研究者的大量實(shí)驗(yàn)表明，利用種群進(jìn)化的歷史信息對(duì)最優(yōu)解的潛在區(qū)域進(jìn)行預(yù)測(cè)，對(duì)于提高種群收斂速度能取得令人滿意的效果。分段預(yù)測(cè)策略相當(dāng)于將種群分為多種群，進(jìn)而通過多種群維持種群多樣性。文獻(xiàn)[16]的研究表明，多種群策略把種群劃分成多個(gè)子種群，一部分用于進(jìn)一步開發(fā)，跟蹤當(dāng)前的極值點(diǎn)，另一部分繼續(xù)探索整個(gè)空間，尋找新的極值點(diǎn)，從而提升算法的搜索效率。通過多種群維持種群多樣性的方式有助于探索有前景的搜索區(qū)域。

因此，本文提出了一種基于Pareto解集分段預(yù)測(cè)策略的動(dòng)態(tài)多目標(biāo)優(yōu)化算法，該算法的預(yù)測(cè)機(jī)制發(fā)生在種群進(jìn)化的整個(gè)過程中。當(dāng)環(huán)境未發(fā)生變化的時(shí)候，通過預(yù)測(cè)策略插入若干引導(dǎo)個(gè)體，加快種群收斂速度；當(dāng)環(huán)境發(fā)生變化的時(shí)候，由于多目標(biāo)優(yōu)化問題的特殊屬性，得到了多個(gè)最優(yōu)解，所以只需要抽取能反映Pareto最優(yōu)前沿分布的特征點(diǎn)并進(jìn)行預(yù)測(cè)。此外，為了進(jìn)一步提高預(yù)測(cè)的準(zhǔn)確性，采用分段預(yù)測(cè)策略，即在檢測(cè)到環(huán)境發(fā)生變化后，將上一時(shí)刻所得到的Pareto解集按照任意一個(gè)子目標(biāo)函數(shù)的函數(shù)值fj(x,t)進(jìn)行排序，并按照函數(shù)值fj(x,t)的大小將Pareto解集均勻地分為3段；然后分別計(jì)算每一段Pareto解集中心點(diǎn)的移動(dòng)方向，對(duì)每一段子集進(jìn)行系統(tǒng)抽樣得到Pareto前沿面的特征點(diǎn)；最后利用線性模型結(jié)合每個(gè)子集中心點(diǎn)移動(dòng)方向分段預(yù)測(cè)下一代種群；同時(shí)，在預(yù)測(cè)的解集周圍自適應(yīng)地產(chǎn)生若干隨機(jī)個(gè)體，以保持種群的多樣性。

3.1 Pareto解集中特征點(diǎn)的抽取

環(huán)境發(fā)生變化后，對(duì)Pareto解集進(jìn)行預(yù)測(cè)的基礎(chǔ)是使用大量的歷史數(shù)據(jù)，然而，多目標(biāo)優(yōu)化問題得到的是Pareto最優(yōu)解集，為了降低計(jì)算復(fù)雜度，需要抽取一些特征點(diǎn)近似描述Pareto最優(yōu)前沿，那么如何抽取Pareto最優(yōu)前沿中的特征點(diǎn)呢？彭星光等[17]提出了基于超塊的Pareto解的選取方法，武燕等[18]提出了通過應(yīng)用K-means求質(zhì)心的方法抽取特征點(diǎn)，都取得了一定的效果，但也都相對(duì)較復(fù)雜?；诔瑝K的抽取方法依賴于區(qū)間分度參數(shù)的取值，還需要計(jì)算Pareto解與超塊頂端點(diǎn)的距離，計(jì)算復(fù)雜度較大；基于聚類求質(zhì)心的方法，初始聚類中心的選擇對(duì)聚類結(jié)果的影響很大且在K-means算法中K是事先給定的，這個(gè)K值是非常難以估計(jì)的，大多數(shù)情況下事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個(gè)類別才最合適。

基于以上分析，本文在目標(biāo)空間利用系統(tǒng)抽樣的方法抽取Pareto解集中的特征點(diǎn)。先將種群中的個(gè)體按目標(biāo)函數(shù)fj(x,t)由小到大排列，并確定抽樣間距k，然后在1～k隨機(jī)選取一個(gè)整數(shù)i，以它作為起始單元的編號(hào)，逐個(gè)抽取樣本單元，直至抽取到Pareto解的目標(biāo)函數(shù)值fj(x,t)最大時(shí)為止。此外，為了確保抽取的解集更加寬廣，保留邊界點(diǎn)作為描述Pareto前沿的特征點(diǎn)。系統(tǒng)抽樣實(shí)施起來相對(duì)簡(jiǎn)單且只有一個(gè)初始個(gè)體需要隨機(jī)抽取，很容易得到一個(gè)在整個(gè)種群中分布均勻的子集。

3.2 種群移動(dòng)方向的計(jì)算

李智勇等[19]提出了將Pareto解集分為PS圖像的中心點(diǎn)和除中心點(diǎn)以外的所有點(diǎn)所形成的曲線。t時(shí)刻種群中心點(diǎn)定義為：

(3)

因此，為了更精確地描述種群Pareto解集的移動(dòng)方向，本文將種群中心點(diǎn)修改為：

(4)

然而，Pareto解集在其目標(biāo)函數(shù)空間中的表現(xiàn)形式并非是線性的，所以僅僅利用一個(gè)方向無法準(zhǔn)確詮釋整個(gè)種群的進(jìn)化方向。因此，本文提出了在目標(biāo)空間中進(jìn)行分段預(yù)測(cè)的算法。

(5)

最后，對(duì)每段Pareto子集進(jìn)行系統(tǒng)抽樣得到Pareto前沿面的特征點(diǎn)，利用線性模型結(jié)合式(5)中所計(jì)算出的子集中心點(diǎn)移動(dòng)方向分段預(yù)測(cè)下一代種群。

3.3 預(yù)測(cè)點(diǎn)集

Zhou等[20]對(duì)比了二次回歸模型(Quadratic Regression Model)、反向傳播模型(Backpropagation Network Model)以及線性模型(Linear Model)在雙目標(biāo)測(cè)試函數(shù)上算法的反向代距離IGD(Inverted Generational Distance)值，其仿真實(shí)驗(yàn)表明，在動(dòng)態(tài)環(huán)境中，線性模型比非線性模型更適合預(yù)測(cè)解集。劉若辰等[21]設(shè)計(jì)的基于預(yù)測(cè)策略的動(dòng)態(tài)多目標(biāo)免疫優(yōu)化算法，其實(shí)驗(yàn)已經(jīng)證明基于線性預(yù)測(cè)機(jī)制，不僅算法的復(fù)雜度低，且在動(dòng)態(tài)環(huán)境中得到的解集對(duì)IGD的跟蹤能力得到極大的增強(qiáng)。因此，為了降低預(yù)測(cè)的復(fù)雜度，本文選用線性模型進(jìn)行預(yù)測(cè)[17,21]。

(6)

當(dāng)環(huán)境未發(fā)生變化時(shí)，在每一代種群中插入若干引導(dǎo)個(gè)體，加快收斂速度。引導(dǎo)個(gè)體由式(7)產(chǎn)生：

xiter+1=xiter+diter

(7)

其中,iter為種群進(jìn)化代數(shù)，diter為種群連續(xù)2代進(jìn)化方向，可由式(8)計(jì)算獲得：

diter=citer-citer-1

(8)

其中

(9)

PSiter為種群進(jìn)化到第iter代得到的最優(yōu)解集。

(10)

其中，random(a,b)函數(shù)返回一個(gè)a～b的隨機(jī)數(shù)。li和vi分別是變量x第i維xi的最小值和最大值，i=1,2,…,n。

所要優(yōu)化的問題越復(fù)雜，種群就越不容易收斂到最優(yōu)解集；在相同的迭代次數(shù)下，問題越復(fù)雜時(shí)，得到的Pareto解集越少；動(dòng)態(tài)優(yōu)化問題收斂的難易程度不同，迭代得到的Pareto解集數(shù)量也不同，那么所抽取得到的特征點(diǎn)的數(shù)目也隨之變化。因此，本文設(shè)計(jì)了自適應(yīng)的多樣性保持策略。種群進(jìn)化過程中，種群規(guī)模保持不變。通過預(yù)測(cè)特征點(diǎn)產(chǎn)生的下一時(shí)刻解集越多，隨機(jī)產(chǎn)生的用來維持種群多樣性的個(gè)體就越少。此處，隨機(jī)產(chǎn)生的個(gè)體由上一時(shí)刻種群經(jīng)高斯變異產(chǎn)生，即:

xt+1=gaussand(xt,δ)

(11)

其中,xt為預(yù)測(cè)點(diǎn)，gaussand(xt,δ)產(chǎn)生以xt為均值、δ為方差的高斯隨機(jī)數(shù)，δ用來控制鄰域的大小。

為了保持種群規(guī)模，采用自適應(yīng)的多樣性保持策略，上一時(shí)刻種群經(jīng)高斯變異產(chǎn)生新的隨機(jī)個(gè)體。如果目標(biāo)函數(shù)越難收斂，得到的最優(yōu)解集越少，那么隨機(jī)產(chǎn)生的個(gè)體就越多；目標(biāo)函數(shù)越容易收斂，得到的最優(yōu)解集越多，隨機(jī)產(chǎn)生的個(gè)體就越少。

本文算法的偽代碼如算法1所示。

算法1基于Pareto解集分段預(yù)測(cè)策略的多目標(biāo)進(jìn)化算法

if環(huán)境未變化then

插入引導(dǎo)個(gè)體xiter+1=xiter+diter

else

邊界檢測(cè);

if種群規(guī)模減少then

高斯變異隨機(jī)生成新個(gè)體xt+1=gaussand(xt,δ)

endif

endif

4 仿真實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證本文算法對(duì)于解決動(dòng)態(tài)多目標(biāo)優(yōu)化問題的有效性，選取了FDA系列和DMOP系列測(cè)試函數(shù)對(duì)算法進(jìn)行測(cè)試，并與著名的DNSGA系列算法進(jìn)行比較。

4.1 測(cè)試函數(shù)

動(dòng)態(tài)多目標(biāo)優(yōu)化問題主要分為4類，本文主要研究前3種類型的動(dòng)態(tài)變化，因此選用測(cè)試函數(shù)FDA1、FDA2、FDA3、FDA4、DMOP1、DMOP2。其中FDA1、FDA4屬于第1類問題，F(xiàn)DA2、DMOP1屬于第2類問題，F(xiàn)DA3、DMOP2屬于第3類問題，能夠較全面地測(cè)試本文算法的性能。

4.2 性能指標(biāo)

動(dòng)態(tài)多目標(biāo)優(yōu)化算法的目標(biāo)是在動(dòng)態(tài)環(huán)境下盡可能地收斂到Pareto最優(yōu)前沿PFt，同時(shí)需要保持解集多樣性[13]。本文采用反向代距離IGD和收斂指標(biāo)CM(Convergence Metric)作為評(píng)測(cè)指標(biāo)。IGD是評(píng)價(jià)算法收斂速度和種群多樣性性能的綜合評(píng)價(jià)指標(biāo)。理想的IGD值為0，IGD值越小，代表算法收斂速度越快，同時(shí)種群多樣性越好。IGD的計(jì)算方式如下所示：

(12)

(13)

其中，PFt是t時(shí)刻真實(shí)的Pareto最優(yōu)前沿中一組均勻分布的解集，Pt是t時(shí)刻種群進(jìn)化得到的解集，fj(v,t),fj(u,t)為個(gè)體v和u的第j個(gè)目標(biāo)值，d是v與u之間的最小歐氏距離。

為了進(jìn)一步測(cè)試DMOEA的性能，Zhou等人[20]提出了一種改進(jìn)的IGD評(píng)估指標(biāo)MIGD(Modified Inverted Generational Distance):

(14)

其中,T為一組離散的時(shí)間點(diǎn)。

CM是評(píng)價(jià)算法所得解集的收斂性的評(píng)價(jià)指標(biāo),表示該組近似Pareto最優(yōu)解與真實(shí)Pareto最優(yōu)前沿之間的距離。其值越小表示收斂能力越強(qiáng)。

若P*=(p1,p2,…,p3,…,p|P*|)是真正的Pareto最優(yōu)前沿上的參考或目標(biāo)點(diǎn)集合，A=(a1,a2,a3,…,a|A|)是算法獲得的最終近似Pareto最優(yōu)集，則ai∈A與P*的最小歸一化歐氏距離為：

i=1,2,…,|A|;j=1,2,…,|P*|}

(15)

(16)

4.3 參數(shù)設(shè)置

將本文算法與DNSGA算法進(jìn)行對(duì)比，都采用非劣排序遺傳算法NSGA-Ⅱ作為框架。其中，種群規(guī)模為100*20，交叉概率為0.9，變異概率為0.1，交叉和變異的分布指數(shù)均為20。DNSGA算法在環(huán)境變化后隨機(jī)產(chǎn)生20個(gè)個(gè)體。測(cè)試函數(shù)環(huán)境變化的幅度τT=10，環(huán)境變化頻率nT=30，即算法運(yùn)行30代環(huán)境變化一次。算法運(yùn)行360代，共經(jīng)歷12個(gè)環(huán)境。對(duì)于每個(gè)測(cè)試問題2種算法獨(dú)立運(yùn)行50次。此外，本文算法中，當(dāng)環(huán)境未發(fā)生變化時(shí)，在每一代種群中插入5個(gè)預(yù)測(cè)得到的引導(dǎo)個(gè)體，加快種群的收斂速度；當(dāng)環(huán)境發(fā)生變化時(shí)，抽取Pareto最優(yōu)解集特征點(diǎn)的抽樣間距k設(shè)置為3，產(chǎn)生自適應(yīng)隨機(jī)個(gè)體的方差δ設(shè)為0.35[18]。

4.4 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)中，對(duì)2種算法運(yùn)行后的每個(gè)環(huán)境所得的近似最優(yōu)解集和最優(yōu)前沿面進(jìn)行記錄，并選擇其中6個(gè)不同環(huán)境的解集進(jìn)行繪制。為了方便描述，記本文算法為BPDMOP。圖1為BPDMOP和DNSGA算法對(duì)于6種測(cè)試函數(shù)在不同環(huán)境中求解得到的Pareto解集。由于多目標(biāo)優(yōu)化算法的隨機(jī)性，所以每次運(yùn)行多目標(biāo)優(yōu)化算法的效果都可能不同，即使對(duì)同一個(gè)問題進(jìn)行優(yōu)化，每次優(yōu)化結(jié)果都可能存在著差異。因此，衡量實(shí)驗(yàn)效果優(yōu)劣的指標(biāo)必然是一個(gè)統(tǒng)計(jì)指標(biāo)。圖2和圖3分別給出了BPDMOP和DNSGA算法獨(dú)立運(yùn)行50次、在12個(gè)不同的環(huán)境下測(cè)試函數(shù)所得到的IGD值和CM值。不同環(huán)境下算法獨(dú)立運(yùn)行50次的IGD和CM性能指標(biāo)的均值如表1所示，其中加粗字體表示IGD均值和CM均值較小，說明對(duì)應(yīng)算法具有較好的收斂性和多樣性。

4.4.1 與DNSGA算法的性能比較

圖1a、圖1c、圖1e、圖1g、圖1i、圖1k分別是BPDMOP算法在FDA1、FDA2、FDA3、FDA4、DMOP1、DMOP2測(cè)試函數(shù)上得到的在不同環(huán)境下的最優(yōu)前沿分布圖，圖1b、圖1d、圖1f、圖1h、圖1j、圖1l分別是算法DNSGA在FDA1、FDA2、FDA3、FDA4、DMOP1、DMOP2測(cè)試函數(shù)上得到的在不同環(huán)境下的最優(yōu)前沿分布圖,F1和F2分別為函數(shù)值。從圖1中可以看出，隨著迭代次數(shù)的增加，2種算法在FDA1、FDA2、DMOP1上都能收斂到最優(yōu)前沿，但對(duì)于FDA3、FDA4、DMOP2函數(shù)DNSGA算法幾乎得不到最優(yōu)解集。

對(duì)于第1類問題，隨著時(shí)間的變化，Pareto最優(yōu)解集發(fā)生變化，而Pareto最優(yōu)前沿不變。從圖1中可以看出，BPDMOP算法在第3個(gè)環(huán)境時(shí)就收斂到了最優(yōu)解集，而且隨著環(huán)境的變化，Pareto前沿逐漸接近理想Pareto前沿面，這是因?yàn)锽PDMOP算法在環(huán)境變化后引入預(yù)測(cè)點(diǎn)集，從而使得算法能夠快速搜索到Pareto最優(yōu)解集的可能區(qū)域。而DNSGA算法對(duì)于FDA1函數(shù)，幾乎在第8個(gè)環(huán)境時(shí)才收斂到最優(yōu)解集，對(duì)于FDA4幾乎收斂不到最優(yōu)前沿，這是因?yàn)镈NSGA算法雖然引入了若干隨機(jī)個(gè)體，擴(kuò)大了搜索空間，但是收斂所需時(shí)間較長(zhǎng)，影響了算法的優(yōu)化效果。如表2所示，對(duì)于FDA1和FDA4函數(shù)BPDMOP算法的IGD均值和CM均值都小于DNSGA算法的。

對(duì)于第2類問題，從圖1c、圖1d和圖1i、圖1j看出，2種算法對(duì)于FDA2和DMOP1函數(shù)所獲得的解集基本相似，但對(duì)于DMOP1函數(shù)2種算法在第1個(gè)環(huán)境得到的解集都不太好，導(dǎo)致DMOP1函數(shù)的IGD均值和CM均值都較大。而對(duì)于FDA2，2種算法的IGD性能指標(biāo)相差不大，且CM指標(biāo)都相對(duì)較小，如表1所示。由于第2類問題FDA2函數(shù)的特殊屬性即真實(shí)PS位置是不隨時(shí)間的改變而變化的，當(dāng)新環(huán)境到來時(shí)，繼續(xù)在上一時(shí)刻的最優(yōu)PS位置進(jìn)行搜索可能會(huì)加速種群的收斂速度。因此，通過預(yù)測(cè)機(jī)制在上一時(shí)刻最優(yōu)PS位置附近搜索新時(shí)刻的最優(yōu)解集，可能需要更多次的迭代進(jìn)化。

對(duì)于第3類問題，隨著時(shí)間的變化，Pareto最優(yōu)解集和Pareto最優(yōu)前沿均發(fā)生了變化。從圖1e、圖1f和圖1k、圖1l可以看出，不同的環(huán)境下，BPDMOP算法獲得的解集比DNSGA獲得的解集都要好，并且能近似收斂到最優(yōu)前沿，說明引入的預(yù)測(cè)機(jī)制奏效了。如表2所示，2種算法在FDA3上的CM均值比在FDA1和FDA2上的都大，說明第3類問題較第1類和第2類問題收斂更困難。綜上所述，BPDMOP在6個(gè)測(cè)試函數(shù)上得到的解集相對(duì)于DNSGA獲得的解集分布更均勻且更接近最優(yōu)解集。圖1和表1表明，本文算法引入的預(yù)測(cè)策略和自適應(yīng)多樣性保持策略是有效的，提高了算法對(duì)動(dòng)態(tài)環(huán)境的適應(yīng)能力。

4.4.2IGD性能評(píng)價(jià)

IGD表征算法獲得種群的收斂性和分布性。為比較本文算法和DNSGA算法的性能，選擇FDA1、FDA2、FDA3、FDA4、DMOP1、DMOP2 6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)，分別對(duì)2種算法運(yùn)行50次，并繪制了不同測(cè)試函數(shù)在12個(gè)環(huán)境下的IGD值對(duì)比圖。如圖2所示，對(duì)于FDA1、FDA3、FDA4、DMOP1、DMOP2函數(shù)，本文算法的IGD值都比DNSGA算法的小，且在12個(gè)不同的環(huán)境下，IGD值波動(dòng)較小，說明本文算法相對(duì)穩(wěn)定。對(duì)應(yīng)于它們的解集分布圖，本文算法所得到的解集更接近于最優(yōu)解集，且分布更均勻。但是，對(duì)于FDA2，由于FDA2函數(shù)的特殊屬性，本文算法在3個(gè)環(huán)境下的IGD值比DNSGA的大。從表1可以看出，對(duì)于DMOP1、DMOP2函數(shù)，2種算法在FDA2上的IGD均值和CM均值相對(duì)于其他測(cè)試函數(shù)都稍大一點(diǎn)，可能是DMOP系列測(cè)試函數(shù)相對(duì)于FDA系列更難收斂。

Figure 2 Comparison of IGD mean values of the two algorithms圖2 2種算法的IGD均值對(duì)比

4.4.3MIGD性能評(píng)價(jià)

為了進(jìn)一步測(cè)試算法的性能，采用MIGD指標(biāo)和PPS(Population Prediction Strategy)[20]、FPS(Feed-forward Prediction Strategy)[22]算法進(jìn)行了對(duì)比，測(cè)試函數(shù)F5～F7是Zhou等人[20]為測(cè)試PPS新提出的函數(shù)。測(cè)試結(jié)果如表2所示。

Table 2 Comparison of MIGD with PPS and FPS表2 與PPS,FPS算法的MIGD比較

從表2可以看出，PPS在F5和F6上具有明顯的優(yōu)勢(shì)，BPDMOP在傳統(tǒng)的測(cè)試函數(shù)上性能較好。

4.4.4CM性能評(píng)價(jià)

收斂度量CM表示算法所得近似Pareto最優(yōu)解與真實(shí)Pareto最優(yōu)前沿之間的距離。收斂度量值越小，表示收斂能力越強(qiáng)。為比較本文算法和DNSGA算法的性能，選用FDA1、FDA2、FDA3、FDA4、DMOP1、DMOP2 6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)，2種算法獨(dú)立運(yùn)行50次，記錄12個(gè)環(huán)境下的CM均值。如圖3所示，對(duì)于第1類問題，其Pareto最優(yōu)解集隨時(shí)間變化而Pareto最優(yōu)前沿不隨時(shí)間變化，本文算法的CM值都接近于0，表明本文算法對(duì)于最優(yōu)解集隨時(shí)間變化而最優(yōu)前沿不隨時(shí)間變化的這一類型問題具有獨(dú)特的優(yōu)勢(shì)。對(duì)于第2類問題，2種算法的CM值相差不大，且對(duì)于不同的環(huán)境，都相對(duì)穩(wěn)定。但是，對(duì)于DMOP1函數(shù)2種算法的CM值稍大一點(diǎn)，說明DMOP1比FDA2難收斂到最優(yōu)解集。對(duì)于第3類問題，2種算法的CM值比其他2類問題的CM值都大?？赡苁怯捎诘?類問題的最優(yōu)解集和最優(yōu)前沿都隨時(shí)間發(fā)生變化，收斂的難度較大，如表1所示。綜上可以得到，在相同的實(shí)驗(yàn)條件下，BPDMOP算法對(duì)于解決動(dòng)態(tài)問題更有效，種群收斂速度更快。

Figure 3 Comparison of CM mean values of the two algorithms圖3 2種算法的CM均值對(duì)比

5 結(jié)束語(yǔ)

針對(duì)動(dòng)態(tài)多目標(biāo)優(yōu)化問題的特點(diǎn)，本文提出了基于Pareto解集分段預(yù)測(cè)策略的動(dòng)態(tài)多目標(biāo)優(yōu)化算法BPDMOP。通過利用歷史信息進(jìn)行最優(yōu)解的預(yù)測(cè)，加快了種群的收斂速度并且提高了算法應(yīng)對(duì)環(huán)境變化的能力。對(duì)于歷史信息的提取，采用系統(tǒng)抽樣的方法確保Pareto前沿分布的多樣性，并采用分段預(yù)測(cè)，將解集分為3段進(jìn)行預(yù)測(cè)，進(jìn)一步減小預(yù)測(cè)誤差。同時(shí)，采用自適應(yīng)的多樣性保持策略，提高了算法對(duì)動(dòng)態(tài)環(huán)境的適應(yīng)能力。本文將改進(jìn)算法應(yīng)用于NSGA2算法框架上，并通過FDA1～FDA4、DMOP1和DMOP2 6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)，測(cè)試了不同環(huán)境下算法所得到的解集的收斂性和分布性，并和經(jīng)典的DNSGA算法進(jìn)行了比較。實(shí)驗(yàn)和分析結(jié)果表明，本文所提算法BPDMOP在應(yīng)對(duì)動(dòng)態(tài)多目標(biāo)優(yōu)化問題上具有一定的優(yōu)勢(shì)，能夠有效求解動(dòng)態(tài)多目標(biāo)優(yōu)化問題。

本文提出的改進(jìn)算法能有效改善種群收斂的速度和多樣性，但由于FDA系列問題的決策變量之間是線性相關(guān)的，本文的分段預(yù)測(cè)算法采用的是線性預(yù)測(cè)策略，在許多決策變量之間是非線性相關(guān)的問題上并不是很理想，無法適應(yīng)更多種類的優(yōu)化問題，這也是今后需要繼續(xù)研究的內(nèi)容。

隨著社會(huì)和科技的發(fā)展，動(dòng)態(tài)多目標(biāo)優(yōu)化必將得到更廣泛的應(yīng)用，但是由于動(dòng)態(tài)多目標(biāo)優(yōu)化問題的研究尚處于理論研究階段，如同文獻(xiàn)[23]所述，在算法應(yīng)用方面研究相對(duì)較少，因此如何結(jié)合實(shí)際生活中的動(dòng)態(tài)多目標(biāo)優(yōu)化問題來設(shè)計(jì)算法也將是未來該領(lǐng)域的研究重點(diǎn)。