王萬良，陳忠馗，吳菲，王錚，俞夢嬌

(浙江工業(yè)大學 計算機科學與技術學院，浙江 杭州 310023)

在實際生活中，存在許多具有多個目標的優(yōu)化問題，并且這些目標之間是互相沖突的，此類問題被稱為多目標優(yōu)化問題(multi-objective optimization problems,MOPs)[1].實際生活中環(huán)境是不斷發(fā)生變化的，如果MOPs 的目標函數(shù)、約束和參數(shù)會隨著環(huán)境變化而改變，MOPs 則轉化為動態(tài)多目標優(yōu)化問題(dynamic multi-objective optimization problems,DMOPs).在處理復雜的DMOPs 時，傳統(tǒng)的多目標優(yōu)化算法(multi-objective optimization algorithms,MOAs)[2-7]明顯具有局限性.隨著環(huán)境的變化，Pareto 最優(yōu)解集 (Pareto-optimal set，PS)[8]和Pareto 前沿 (Pareto-optimal front，PF)不斷發(fā)生變化，傳統(tǒng)的MOAs 會在環(huán)境變化中逐漸喪失種群的多樣性，種群在某一時刻陷入局部收斂而不再隨環(huán)境發(fā)生變化.因此，需要動態(tài)多目標優(yōu)化算法(dynamic multi-object optimization algorithms,DMOAs)[9-14]及時地響應環(huán)境變化，從而追蹤到變化后的PS 和PF.

近年來，DMOAs 不斷被提出，并應用于各個領域，例如：調度[15]、機械設計[16]、資源管理[17]、路徑規(guī)劃[18]等.為了解決DMOPs,研究大致可以劃分為3 大模塊：環(huán)境變化檢測[19-20]、環(huán)境變化應答機制[9-14,21-22]、靜態(tài)多目標優(yōu)化算法[2-7].其中靜態(tài)多目標優(yōu)化算法大多是為了提高收斂速度，例如：NSGA-II[5]、RM-MEDA[6]、MOEA/D[7]等.環(huán)境變化檢測用于檢測環(huán)境的變化，為后面設計應答機制提供指導，而變化應答機制是解決DMOPs 的重要研究目標.變化應答機制大多利用多樣性引入機制[21]、預測機制[9-14]、記憶機制[22]等方式來響應環(huán)境的變化.其中預測機制對周期性問題和非周期性問題均有不錯的效果，該機制通過利用歷史信息或者其他方法來預測環(huán)境變化后的最優(yōu)解，如果預測足夠準確，那么預測機制對DMOPs 非常有效.Zhou 等[10]提出種群預測策略(population prediction strategy,PPS),該策略應對DMOPs 較有效，但由于在早期階段缺乏歷史信息的積累，前期效果較差.Zou 等[11]提出基于中心點和Knee 點的預測策略(prediction strategy based on center points and knee points,CKPS),該策略將Knee 點引入預測種群，可以更加準確地追蹤PF,但后期效果不夠理想.Li 等[12]提出基于特殊點的預測策略(predictive strategy based on special points,SPPS)，利用Knee點、近邊緣點、近中心點等特殊點快速地跟蹤PF，該策略進一步提高了種群的多樣性，但種群中心點的預測缺乏反饋校正，預測的準確性還有待進一步提高.Rong 等[13]提出多向預測策略(multidirectional strategy,MDP),該策略利用先前環(huán)境中多個代表性解所確定的多個方向來預測PS 在決策空間中的位置，從而提高了解決DMOPs 的性能.Chen 等[14]提出結合混合預測和突變策略的變化響應機制(change response mechanism by combining mixed prediction strategy and mutation strategy,HPPCM)，混合預測策略協(xié)調基于中心點的預測和基于引導個體的預測，而突變策略可以處理不可預測的環(huán)境變化，從而快速適應各種環(huán)境變化.

針對上述不足，本研究提出基于個體預測的動態(tài)多目標優(yōu)化算法，其主要貢獻如下.1) 提出參考點聯(lián)系算法，引入該算法篩選的特殊點，并通過新的特殊點預測策略快速地響應環(huán)境變化.2) 提出針對種群中心點預測的反饋校正機制，對種群中心點預測非支配解集的預測步長進行反饋校正，使預測更加準確.3) 提出混合多樣性維持機制，引入拉丁超立方抽樣和精度可控的突變策略分別生成的隨機個體，以提高種群的多樣性，避免種群陷入局部收斂.

1 相關工作

1.1 動態(tài)多目標優(yōu)化相關概念

DMOPs 定義[23]如下：

式中：F(x,t) 為m維的目標向量，x=[x1,x2,···,xn]T為n維的決策變量，定義域為Ω,g(x,t) 和h(x,t) 分別為不等式約束以及等式約束，t表示時間變量.

式中：τ 為迭代數(shù)，nt為環(huán)境變化程度，τt為變化頻率.

定義1.如果x1和x2在時間t滿足以下條件：

則x1可以支配x2，記作x1?x2.

定義2.在t時刻，如果不存在個體x′∈Ω 支配個體x，則x為問題(1)(式（1）) 在t時刻的一個Pareto 最優(yōu)解，P St為問題(1)在t時刻所有Pareto最優(yōu)解的集合.定義如下：

定義3.在t時刻，PSt在目標空間的映射被稱為 PFt：

根據(jù)PF 和PS 動態(tài)變化的不同組合，確定4 種不同類型的DMOPs，如表1 所示.

表1 4 種不同類型的DMOPsTab.1 Four different types of DMOPs

1.2 RM-MEDA

RM-MEDA[6]是改進后的分布估計算法，可以在一定的光滑性假設下，即在Karush-Kuhn-Tucker假設下，導出連續(xù)MOP 的PS,在決策空間中能夠形成分段連續(xù)的m-1 維流形.RM-MEDA 不是直接使用種群中的局部信息生成新的種群，而是充分利用當前種群提供的全局信息，因此RM-MEDA具有更強的啟發(fā)式優(yōu)化能力.RM-MEDA 的流程圖如圖1 所示.

圖1 RM-MEDA 流程圖Fig.1 Flow chart of RM-MEDA

1.3 參考點

參考點常常被用來解決多目標優(yōu)化問題上的收斂性和多樣性問題，在Das 等[24]所提方法的基礎上，Deb 等[25-26]提出基于參考點的多目標優(yōu)化算法(NSGA-III),利用預定義的參考點對選擇個體的方法進行改進，以維持種群之間的多樣性，后續(xù)將NSGA-III 擴展到求解一般約束多目標優(yōu)化問題.本研究的參考點采用Das 等[24]的方法設計，所設計的參考點在超平面上均勻分布.假設M個參考點的集合為R={r1,···,ri,···,rM}，生成參考點ri：

式中：i=1,2,···,M,j=1,2,···,m,M為參考點的數(shù)量，H為每個目標上劃分的數(shù)目，m為目標函數(shù)的個數(shù).

在Das 等[24]的方法中，參考點數(shù)量M的表達式為

通常，參考點的數(shù)量與種群的大小一致，本研究根據(jù)種群中非支配解集的大小設置參考點的數(shù)量.

2 基于個體預測的動態(tài)多目標算法

2.1 特殊點集

追蹤PS 和PF 一直是解決動態(tài)多目標優(yōu)化問題的熱點，本研究提出參考點聯(lián)系算法，利用該算法篩選的特殊點來追蹤PF，從而實現(xiàn)更快的收斂.

參考點聯(lián)系算法是將預定義的參考點與非支配個體關聯(lián)起來.參考點與原點連接作為該參考點的參考向量，計算每個參考向量與非支配個體的距離，參考點與離其參考向量最近的非支配個體關聯(lián).由于參考點是均勻分布在超平面上的，若有非支配個體關聯(lián)較少的參考點或沒有關聯(lián)參考點，說明附近有其他非支配個體與其競爭，則這些個體不具備較好的多樣性；反之，關聯(lián)較多參考點的非支配個體具有較好的多樣性.如圖2所示，非支配個體A關聯(lián)了3 個參考點，其多樣性優(yōu)于關聯(lián)2 個參考點的B、C、D以及關聯(lián)1 個參考點的E，而F、G作為邊界點則直接加入到特殊點集中.

圖2 非支配個體與參考點關聯(lián)示意圖Fig.2 Schematic diagram of association between non-dominant individuals and reference points

根據(jù)非支配個體關聯(lián)參考點的數(shù)量，從多到少依次選擇 num1個非支配個體加入特殊點集中.為了給篩選提供便利，預定義參考點的數(shù)量大于非支配解集的總數(shù).參考點聯(lián)系算法的具體步驟見算法1.

算法1 參考點聯(lián)系算法

1）將種群分層，選擇第1 層的個體為非支配個體.

2）根據(jù)非支配解集的大小，采用式(6)的方法設計參考點集R.

3）計算每個參考向量與非支配個體的距離，參考點與離其參考向量最近的非支配個體關聯(lián).

4）根據(jù)非支配個體關聯(lián)參考點的數(shù)量，從多到少依次排列，按照順序選擇 n um1個非支配個體加入特殊點集.

除了以上篩選的點和邊界點以外，本研究還采用文獻[11]中的方法，選擇Knee 點加入特殊點集，Knee 點是指在PF 上具有最大邊際效用的點，在Knee 點附近，一個目標上有一個較小的改進，將會伴隨著至少一個目標的嚴重退化.參考點聯(lián)系算法在篩選過程中會避免出現(xiàn)和Knee 點重合的情況，且當實際篩選點的數(shù)量少于 n um1時，從非支配解集中隨機選擇個體補齊.

選擇參考點聯(lián)系算法篩選的點、邊界點和Knee 點作為特殊點代表整個PF,而對特殊點集的預測能快速地響應環(huán)境變化，加快種群的收斂.采用文獻[27]、[28] 的方法，提出特殊點預測策略，在圖3 中，通過例子來說明該特殊點預測策略的思想.首先計算t時刻特殊點集的最小值點mint和最大值點maxt:

圖3 特殊點預測策略示意圖Fig.3 Schematic diagram of special points prediction strategy

根據(jù)t時刻的mint和maxt以及可以預測出t+1 時刻的最小值點mint+1和最大值點maxt+1，mint+1和maxt+1則組成了t+1 時刻的決策空間：

利用特殊點預測出t+1 時刻最小值點和最大值點組成的決策空間，然后進一步預測t+1 時刻的特殊點集.它不是一個準確的預測，因此增加了一個高斯擾動，若為t時刻的一個特殊點，則預測的公式為

算法2 特殊點預測策略

輸入：特殊點集 specialt,特殊點集的大小Ns.

輸出：預測的t+1特殊點集 pops.

1）根據(jù)式(8)計算t時刻和t-1 時刻特殊點集的最小值點mint和mint-1以及最大值點maxt和maxt-1.

2）根據(jù)式(9)計算t時刻最小值點和最大值點第i維的運動方向

3）根據(jù)式(10)預測t+1時刻的最小值點mint+1和最大值點maxt+1.

4）根據(jù)式(11)預測t+1 時刻的特殊點集.

2.2 種群中心點預測的反饋校正機制

種群中心點的預測方法[9-11]被廣泛應用到種群的預測中，該預測方法通常被用來預測非支配個體，但由于缺乏誤差反饋和校正機制，預測的準確性還有待進一步提高，因此，本研究采用了針對該預測方法的反饋校正機制[29]來彌補這一缺陷.

首先須構建一個代表個體，將t時刻非支配解集的中心點Ct作為代表個體：

式中：PSt為t時刻種群的非支配解集，xt為非支配個體.

然后對代表個體進行預測：

式中：Ct+1為預測的t+1 時刻非支配解集的中心點；Pt=Ct-Ct-1表示初始預測的步長和方向，Ct-1為t-1 時刻非支配解集的中心點.

如圖4 所示，基于Ct+1，在預測步長的范圍內，沿初始預測的正負方向對最優(yōu)變量均勻采樣，生成 2N個搜索個體S={s1,···,si,···,s2N}：

圖4 決策空間變量的步長探索Fig.4 Step size exploration of decision space variables

最后對這組搜索個體S={s1,···,si,···,s2N} 和Ct+1進行評估，將非支配個體存儲到外部存檔A中，A={a1,···,ai,···,a|A|},在A中隨機選擇一個非支配個體ai.非支配個體ai優(yōu)于Ct+1,其對應的預測步長也優(yōu)于初始預測的步長，因此初始預測步長可以通過Ct+1和ai之間的向量差 Δ進行修正：

最優(yōu)變量的選擇，根據(jù)非支配解集中每個維度決策變量的標準差決定，選擇標準差較小的變量作為最優(yōu)變量.根據(jù)文獻[29]、[30]中單一最優(yōu)變量的定義，如果一個決策變量是單一最優(yōu)的，那么所有解在該決策變量上的值是相同，因此本研究選擇非支配解集中標準差較小的變量作為最優(yōu)變量.反饋校正機制的具體步驟如算法3 所示.

算法3 反饋校正機制

輸入：非支配解集PSt

輸出：校正后的預測步長Pt

1）根據(jù)式(12)計算t-1時刻和t時刻非支配解集的中心點Ct-1和Ct,Ct作為代表個體.

2）根據(jù)式(13)對Ct進行預測，得到預測的t+1 時刻非支配解集的中心點Ct+1.

3）計算非支配解集中每個維度決策變量的標準差，選擇標準差較小的變量為最優(yōu)變量Vstd.

4）根據(jù)式(14)生成 2N個搜索個體S={s1,···,si,···,s2N}.

5）重新評估Ct+1和搜索個體S={s1,···,si,···,s2N}，并將非支配個體存儲到A中.

6）對于j∈Vstd，利用式(15)對Pt進行校正.

根據(jù)校正后的預測步長對非支配個體進行預的非支配個體，分別對非支配個體進行小、中、大3 種步長的預測[31]:

測.為了使預測的非支配個體更接近t+1 時刻真實式中：xt+1表示t+1 時刻的非支配個體；rs 為沿移動方向的移動步長，使用3 種不同的值(0.5,1.0,1.5)表示，分別代表非支配個體小、中、大3 種步長的預測，其中，小步長和大步長的預測作用在同一非支配解集，各預測一半的非支配個體，3 種步長預測后的種群共同構成了t+1 時刻的非支配解集.

2.3 混合多樣性維持機制

在動態(tài)環(huán)境中，保持多樣性是非常重要的，本研究提出混合多樣性維持機制，通過拉丁超立方抽樣[32]在式(8)～(10)預測的t+1 時刻的決策空間和t時刻特殊點的最小值點和最大值點組成的決策空間中分別生成N1個隨機個體.除此之外，在Zhang 等[33]提出的精度可控突變算子的基礎上，提出精度可控的突變策略，對非支配解集進行突變，生成隨機個體.所提出的精度可控突變算子表達式如下：

式中：Δβ=Δα+1/10Random(q)×Gaussian(0,std),其中Δα=1/10Random(q)×Random(9)，std 為非支配解集中每個維度決策變量的標準差；i=0,1,···,n；xi為x的第i維決策變量；為x′突變的第i維決策變量.

精度可控的突變策略的具體步驟如算法4 所示.

算法4 精度可控的突變策略

輸入：非支配解集 PSt，x為PSt中的非支配個體

輸出：隨機解pop2

該策略對非支配解集突變生成隨機個體，為了保證突變的隨機個體仍具有較好的收斂性，只對非最優(yōu)變量進行突變，變量r隨機取1 或2，使突變可以生成均勻擴散的隨機個體.Δβ 和 Δα 都用于控制變量的精度，Δβ 在 Δα 基礎上增加了精度可控的高斯分布，在擴大了搜索范圍的同時也可以通過比 Δα 更小的步長在決策空間中局部搜索最優(yōu)解，理論上，本研究提出的精度可控的突變策略所突變的隨機個體，具有更好的多樣性和更均勻的分布.

2.4 IPS 算法詳細描述

IPS 是在動態(tài)多目標進化算法的框架下進行的.IPS 在環(huán)境變化后產(chǎn)生新的初始種群，使新的種群能夠對環(huán)境變化快速響應并追蹤其變化的PF.算法5 是對IPS 的詳細描述，IPS 的流程圖如圖5 所示.

圖5 IPS 流程圖Fig.5 Flow chart of IPS

算法5 IPS 算法

初始化：時間變量t:=0,初始化種群 pop,迭代次數(shù)計數(shù)器gt:=0,算法總進化代數(shù)gmax.

1）檢測環(huán)境變化，如果環(huán)境沒有發(fā)生變化，轉步驟10）；否則，轉步驟2）.

2）根據(jù)算法1 得到參考點聯(lián)系算法篩選的點，和Knee 點、邊界點一起作為特殊點.

3）利用式(8)～(10)預測t+1 時刻最小值點和最大值點組成的決策空間，并利用式(11)預測t+1 時刻的特殊點集 pops.

4）計算非支配解集的中心點Ct.

5）利用式(14)～(15)對式(13)的預測步長進行反饋校正，并利用校正的預測步長預測t+1 時刻的非支配解集 popNon-dom.

6）對式(8)～(10)計算的t時刻決策空間和預測的t+1時刻決策空間進行拉丁超立方抽樣生成隨機解 pop1.

7）根據(jù)算法4 對t時刻非支配解集突變生成隨機解pop2.

8）得到新種群popt+1=pops+popNon-dom+pop1+pop2.

9）對popt+1執(zhí)行RM-RMAD 中的環(huán)境選擇算法.

10）用RM-RMAD 對種群進行優(yōu)化.

11）如果gt＞gmax,則輸出 popt并終止；否則gt:=gt+1，轉步驟1）.

3 測試問題及評價指標

3.1 測試問題

采用幾種常見的動態(tài)多目標測試問題，包括FDA 系列[23]和DMOP 系列[34]以及F5～F10 系列問題[6].其中，F(xiàn)DA 和DMOP 系列問題的決策變量之間是線性相關的，而F5～F10 系列問題的決策變量之間是非線性相關的.F9～F10 是更難收斂的測試問題，例如，F(xiàn)9 的Pareto 前沿在大部分時間內發(fā)生平穩(wěn)變化，但偶爾會出現(xiàn)較大的環(huán)境變化，這會降低算法的收斂速度.在所有的測試問題中，F(xiàn)DA4 和F8 是三目標測試問題，其他是兩目標測試問題.

3.2 性能指標

采用修正的反向代距離(modified inverted generational distance,MIGD)[11-12]和修正的超體積差(modified hypervolume difference,MHVD) 作為DMOAs 的性能評價指標，衡量算法在收斂性和多樣性方面的性能.

反向代距離 (inverted generational distance,IGD)[35]被廣泛應用到衡量算法的收斂性和多樣性，IGD 指標的定義如下：

IGD 評價的是標準PF 和算法所得PF 的接近程度以及算法所得PF 中個體的分布性，MIGD 是IGD 的修改版本，它被定義為運行期間某些時間步長內的IGD 平均值：

式中：T為運行中的一組時間離散點集合.

MIGD 是綜合的評價指標，可以評價算法在收斂性和分布性方面的性能，其值越小，說明算法的性能越好.

超體積差 (hypervolume difference,HVD)[36]測量的是標準PF 和算法所得PF 之間的超體積差，HVD 的評價指標如下：

式中：HV(S) 表示集合S的超體積.

MHVD 是對HVD 的修改版本，它被定義為運行期間某些時間步長內的HVD 平均值，其表達式如下：

4 實驗結果與分析

4.1 參數(shù)設置

選擇4 種策略與本研究所提的IPS 進行對比.4 種策略分別為種群預測策略(PPS)[10]、基于中心點和拐點的預測策略(CKPS)[11]、基于特殊點的預測策略(SPPS)[12]和結合混合預測和突變策略的變化響應機制(HPPCM)[14].5 種策略均采用RMMDEA[6]對問題優(yōu)化.

對每個問題獨立實驗20 次，每次實驗都會產(chǎn)生100 次環(huán)境變化，環(huán)境的變化程度nt=10,環(huán)境變化頻率 τt=25,每次運行的總進化代數(shù)為2 500，種群大小設置為100，決策空間的維度n=20，在AR(p)模型中，參數(shù)p=3，歷史信息序列長度設置為23.各個策略特定的參數(shù)設置如下.

1) CKPS 的Knee 點個數(shù)為9.

2) SPPS 在種群中心點預測非支配集的過程中將高斯擾動d=0.1.

3) HPPCM 中自主演化的代數(shù) Δt=2.

4) IPS 中參考點聯(lián)系算法篩選的特殊點個數(shù)num1=9，最優(yōu)變量個數(shù)為2，搜索個體總數(shù) 2N=18，N1=25，q=2.

環(huán)境變化檢測則通過選擇種群中5%的個體來檢測環(huán)境變化，目標值不匹配表明環(huán)境發(fā)生了改變.

4.2 性能評價的統(tǒng)計結果對比

在動態(tài)環(huán)境中，須討論不同策略在不同時期的性能，因此，將100 次環(huán)境變化分為3 個階段：第1 階段包括前20 次環(huán)境變化；第2 階段包括中間40 次環(huán)境變化；第3 階段包括最后40 次環(huán)境變化.MIGD 和MHVD 的平均值和標準差如表2～5 所示.表中，粗體表示最佳值.采用Wilcoxon 秩和檢驗[37]在0.05 顯著性水平上比較不同結果之間的顯著性.

表2 5 種策略在FDA 和DMOP 上的MIGD 指標Tab.2 MIGD indicators for five strategies on FDA and DMOP

4.2.1 FDA 和DMOP 問題上的實驗結果分析 如表2 所示為在FDA 和DMOP 系列問題上比較5 種策略的MIGD 指標，總階段代表所有的環(huán)境變化.可以看出，1) 在總階段和第1 階段，IPS 有5 個MIGD 指標是最優(yōu)的，HPPCM 有2 個MIGD指標是最優(yōu)的.2) 在第2 階段，IPS 有3 個MIGD 指標是最優(yōu)的，HPPCM 有4 個MIGD 指標是最優(yōu)的.3) 在第3 階段，IPS 有2 個MIGD 指標是最優(yōu)的，PPS 和HPPCM 有3 個MIGD 指標是最優(yōu)的.

出現(xiàn)這樣實驗結果的原因如下.IPS 不需要經(jīng)驗的積累，其參考點聯(lián)系算法篩選的特殊點可以加速種群的收斂，因此，在第1 階段IPS 表現(xiàn)出了更好的性能.PPS 隨著經(jīng)驗的積累，在后2 個階段的某些測試問題上的MIGD 指標優(yōu)于IPS 的.HPPCM 的混合預測機制注重收斂，可以快速地響應環(huán)境變化，因此在FDA 和DMOP 系列問題上也有較好的表現(xiàn).對于3 個目標的測試問題，IPS 整體的性能要好于其他4 種策略，說明IPS 在高維動態(tài)多目標問題上有著更好的表現(xiàn).

4.2.2 在F5～F10 問題上的實驗結果分析 F5～F10是決策空間變量呈非線性相關的測試問題，如表3所示，在F5～F10 系列問題上比較了這5 種策略的MHVD 指標，MHVD 和MIGD 均為綜合的評價指標，可以評價5 種策略在收斂性和分布性方面的性能.可以看出，IPS 和HPPCM 較其他3 種策略表現(xiàn)出了更好的性能.對于測試問題F5～F8,HPPCM 在第2、3 階段的MHVD 指標大多優(yōu)于IPS 的，原因如下：HPPCM 擅長追蹤具有重大變化的PS 或PF,而IPS 的反饋校正機制和特殊點預測策略可以加速種群的收斂，因此IPS 在第1 階段表現(xiàn)更好.對于復雜測試問題F9,IPS 的MHVD指標比其他4 種策略的都要好，這是因為IPS 在面對較大環(huán)境變化時仍能較快地收斂.CKPS 和SPPS 則在F10 測試問題上有著更好的表現(xiàn)，是因為其自適應的種群維持機制可以根據(jù)問題困難程度引入不同數(shù)量的個體.

表3 5 種策略在F5～F10 上的MHVD 指標Tab.3 MHVD indicators for five strategies on F5 to F10

4.2.3 不同環(huán)境變化頻率下的實驗結果分析 為了檢驗5 種策略在不同環(huán)境變化頻率下的性能，選擇6 個具有代表性的測試問題，比較5 種策略對應3 種不同 τt的MIGD 和MHVD 指標，環(huán)境變化頻率 τt分別設置為20、25 和30.如表4 所示，每種算法都有18 個MIGD 指標，其中IPS 有11 個MIGD 指標是最優(yōu)的，HPPCM 有5 個MIGD 指標是最優(yōu)的，SPPS 和CKPS 有1 個MIGD 指標是最優(yōu)的，不難看出，5 種策略中IPS 和HPPCM 最優(yōu)和次優(yōu)的MIGD 指標是最多的，說明IPS 和HPPCM 比其他3 種策略的性能更好，另一方面，隨著 τt的增加，5 種策略的性能均得到了提升，原因是較大的 τt有更多的迭代次數(shù)使種群在環(huán)境變化之前找到近似的 PS.

表4 5 種策略在部分測試問題上的MIGD 指標Tab.4 MIGD indicators of five strategies on some test questions

如表5 所示為5 種策略在6 個測試問題上對應3 種不同 τt的MHVD 指標，與表4 較為不同的是，SPPS 在DMOP1 測試問題上的3 個MHVD 指標是最優(yōu)的，原因可能是MHVD 在評價算法性能時更傾向于邊界解，而SPPS 在保留邊界解的方面做得更好.

表5 5 種策略在部分測試問題上的MHVD 指標Tab.5 MHVD indicators of five strategies on some test questions

4.3 獲得的解集分布圖對比

為了進行更加直觀的比較，選擇DMOP2、F9 這2 個具有代表性的測試問題來繪制5 種策略在不同時刻所獲得解集的分布圖，如圖6、7 所示.圖中，橫縱坐標表示所獲得解集在不同目標上的目標值，圓點表示獲得的解集，曲線表示標準PF.可以看出，對比結果與表2、3 的相同，在早期階段，IPS 所獲得的解集具有更好的收斂性和分布性，說明IPS 可以快速地響應環(huán)境變化.在后期階段，IPS 在環(huán)境多次變化后仍能較為準確地追蹤到新解，最終得到收斂性和分布性均較好的 P S，并且，IPS 所獲得的PF 和標準的PF 較接近.其他4 種策略在后期階段的表現(xiàn)也較為不錯.由圖7可以看出，IPS 在處理F9 這種復雜測試問題時也有較好的表現(xiàn).

圖6 5 種策略在求解DMOP2 過程中所獲得的解集Fig.6 Solution set obtained by five strategies in process of solving DMOP2

圖7 5 種策略在求解F9 過程中所獲得的解集Fig.7 Solution set obtained by five strategies in process of solving F9

5 消融實驗

5.1 參考點聯(lián)系算法篩選的特殊點對IPS 的影響

比較參考點聯(lián)系算法篩選0 個特殊點和9 個特殊點的IPS，設篩選特殊點的個數(shù)為s,s=0 的IPS 為IPS(0)，s=9 的IPS 為IPS(9)，選擇F6 和F9 作為代表問題來比較IPS(0)和IPS(9)在20 次運行中環(huán)境變化的IGD 趨勢，結果如圖8 所示.可以看出，IPS(9)整體的IGD 趨勢低于IPS(0)的，說明其性能比IPS(0)要好，原因是引入?yún)⒖键c聯(lián)系算法篩選的特殊點可以使種群更快速更準確地響應環(huán)境變化，同時維持了種群的多樣性.

圖8 IPS(0)和IPS(9)在F6 和F9 問題上運行20 次時環(huán)境變化的IGD 趨勢Fig.8 IGD trend comparison of IPS(0) and IPS(9) over number of changes for 20 runs on F6 and F9

5.2 反饋校正機制對IPS 的影響

反饋校正機制是為了解決種群中心點預測方法缺乏誤差反饋和校正機制，從而預測不夠準確的問題.為了驗證反饋校正機制對IPS 的影響，比較具有反饋校正機制和不具有反饋校正機制的IPS，設不具有反饋校正機制的IPS 為IPS(N).選擇F6 和F9 測試問題來比較IPS 和IPS(N)在20 次運行中環(huán)境變化的IGD 趨勢，結果如圖9 所示.圖中，Nc為環(huán)境變化的次數(shù).可以看出，IPS 表現(xiàn)出了比IPS(N)更好的性能.原因如下：反饋校正機制校正了預測的步長和方向，提高了預測的準確性，使種群更準確地追蹤新的最優(yōu)解，面對復雜測試問題F9,IPS 的表現(xiàn)明顯優(yōu)于IPS(N),說明反饋校正機制應對復雜問題也較有效.

圖9 IPS 和IPS(N)在F6 和F9 問題上運行20 次時環(huán)境變化的IGD 趨勢Fig.9 IGD trend comparison of IPS and IPS(N) over number of changes for 20 runs on F6 and F9

6 結語

提出基于個體預測的動態(tài)多目標優(yōu)化算法，種群中心點預測的非支配解集是預測種群的主體，采用反饋校正機制對其預測步長進行校正，從而更準確地追蹤PF,同時引入由參考點聯(lián)系算法篩選的特殊點，繼而對特殊點集的預測可以快速響應環(huán)境的變化，再由混合多樣性維持機制采用拉丁超立方抽樣和精度可控的突變策略分別產(chǎn)生一部分隨機個體以保持種群的多樣性.選擇在FDA 系列問題、DMOP 系列問題以及F5～F10 共13 個測試問題上與其他4 種算法進行比較，實驗結果表明，無論是決策空間變量線性相關的問題，還是線性無關的問題，IPS 都能快速響應環(huán)境的變化，獲得收斂性和多樣性均較好的解集.

IPS 在應對不連續(xù)問題時有待改進，這也給未來的研究指明了一定的方向，如何在后2 個階段延續(xù)第1 個階段的表現(xiàn)將是筆者未來研究工作的重點.此外，特殊點預測策略在種群尚未收斂的時候，可能會存在預測不準確的問題，而記憶策略對PS 隨時間不發(fā)生變化的問題有較好的影響，因此，將預測策略與記憶策略結合也是一項可研究的工作.