基于 Holt 差分預測校正的動態多目標優化算法

摘 要：

為高效追蹤動態多目標優化問題中隨時間或環境變化而不斷演變的Pareto前沿，提出了一種新的基于環境感知與預測校正的動態多目標優化算法（HD-DMOEA）。該算法包含三個主要策略：首先使用Wilcoxon符號秩檢驗對環境變化進行檢測，并提出一種新的環境感知算子對環境變化強度進行判定。其次，構建Holt差分預測校正模型預測種群個體在下一個時間窗的位置，并在預測過程中根據參考點進行預測校正，以提高模型預測精度，加快算法尋優速度。另外，提出了一種新的變異方法，該方法根據環境變化強度引入不同的變異個體，以維持種群多樣性，從而降低種群陷入局部最優的概率。為驗證HD-DMOEA的有效性，將HD-DMOEA與五種最先進的預測算法分別在測試集FDA和dMOP上進行實驗對比分析，實驗結果表明，HD-DMOEA在搜索過程中能有效動態平衡種群的多樣性和收斂性，實現對Pareto 前沿的持續高效追蹤，并且優于其他五種對比算法。

關鍵詞：動態多目標優化；預測校正；環境感知；參考點

中圖分類號：TP301.6"" 文獻標志碼：A""" 文章編號：1001-3695（2024）12-023-3701-09

doi： 10.19734/j.issn.1001-3695.2024.04.0124

Dynamic multi-objective optimization algorithm based on Holt’s differential prediction correction

Liu Zhilin1， Kang Lanlan1，2， Dong Wenyong3

（1.School of Information Engineering， Jiangxi University of Science amp; Technology， Ganzhou Jiangxi 341000， China; 2.School of Information Engineering， Gannan University of Science amp; Technology， Ganzhou Jiangxi 341000， China; 3.School of Computing， Wuhan University， Wuhan 430072， China）

Abstract：

To efficiently track the evolving Pareto frontier in dynamic multi-objective optimization problems over time or environment， this paper proposed a new dynamic multi-objective optimization algorithm， called HD-DMOEA， based on environment sen-sing and prediction correction. This algorithm incorporated three main strategies. Firstly， it employed the Wilcoxon signed rank test to detect environmental changes and introduced a new environment sensing operator to determine the intensity of these changes. Secondly， it constructed the Holt differential prediction correction model to predict the positions of population individuals in the next time window， making corrections based on a reference point during the prediction process to enhance prediction accuracy and accele-rate the search speed of the algorithm. Then， it introduced a new mutation method that injected different mutated individuals based on the intensity of environmental changes to maintain population diversity， thus reducing the likelihood of the population falling into local optima. To verify HD-DMOEA’s effectiveness， researchers conducted comparative analysis between HD-DMOEA and five advanced prediction algorithms on the FDA and dMOP test sets. The results demonstrate that HD-DMOEA effectively and dynamically balances the diversity and convergence of populations during the search process， continuously tracking the Pareto frontier and outperforming the other five comparative algorithms.

Key words：dynamic multi-objective optimization; prediction correction; environment perception; reference points

0 引言

多目標優化問題（multi-objective optimization problem，MOP）［1］是一類在工業生產和科學研究中都廣泛關注的問題，該問題存在多個目標需要優化，但這些目標通常是相互沖突的。在現實生活中，此類問題往往會隨著時間或環境的變化而變化，這種時變性問題統稱為動態多目標優化問題（dynamic multi-objective optimization problem，DMOP），例如：機械設計［2］、資源調度問題［3～5］、廢水處理［6］等。在動態環境中，多目標優化問題的目標函數和約束條件都可能會隨著時間的變化而變化，從而導致傳統優化方法無法適應［7］。為了能在動態多變的環境下快速追蹤到變化后的Pareto前沿，大量科研人員采用進化算法解決DMOP，這類算法被稱之為動態多目標進化算法（dynamic multi-objective evolutionary algorithm，DMOEA）。為應對不斷變化的外部環境，DMOEA往往需要通過環境變化檢測策略對環境進行有效檢測，并通過環境變化響應機制保持對Pareto前沿的持續追蹤。當前，DMOEA的研究主要聚焦于以下三點：如何設計環境變化檢測機制、如何設計環境變化響應策略、如何實現靜態快速尋優［8，9］。

現有的環境變化檢測機制大致分為三種：a）隨機選取種群中部分個體作為檢測點，通過觀測檢測點在不同時間窗內適應度值的變化情況來判斷環境是否發生變化［10，11］；b）對時間窗內的種群個體適應度進行排序，根據排序結果依次重新評估相鄰時間窗種群個體適應度，如果發現當前評估個體的適應度不同，則判定環境發生了變化，且無須對后續剩余個體進行評估［12］；c）根據相鄰兩個時間窗的種群適應度的概率分布情況判定環境是否發生變化［13］。方法a）需要選擇能代表整個種群運動趨勢的個體作為檢測點進行評估，但這種個體難以選取。方法b）僅依賴于相鄰時間窗內個體適應度的差異來判斷環境是否發生變化。然而，個體適應度的差異可能受到噪聲或隨機性的影響，從而導致誤判環境變化或遺漏實際的環境變化［14］?；谇皟煞N方法的局限性，本文將采用方法c），利用種群個體的全局信息，提出新的環境變化檢測方法。

環境變化響應機制根據環境變化檢測結果作出響應。常見的環境變化響應機制主要包括：隨機再初始化［15］、基于記憶的再初始化［16～18］、基于預測的再初始化［19～21］等。隨機再初始化方法是一種研究早期應對環境變化的響應機制，但因其在檢測到環境變化后每次都要對整個種群重新尋優，計算資源消耗過高。因此，為提高優化效率，研究人員借助歷史信息，采取基于記憶的再初始化方法對種群進行部分初始化，從而幫助算法快速跟蹤變化后的最優解。但是，這種方法的效果往往受到歷史信息準確性的影響，導致算法陷入局部最優。為避免這一現象，目前多采用一種基于預測的再初始化方法，該方法可根據歷史環境信息尋求變化規律，預測未來環境變化情況，從而通過積極響應環境變化的方式提高動態環境下對Pareto前沿的持續跟蹤效率。常用的預測方法有：線性預測模型、自回歸模型等，此類方法多適用于短期預測，且其過程較為復雜［22］。本文關注到，霍爾特（Holt）預測模型和差分預測模型是一類模型簡單且可通過實時調整模型參數應對不同環境變化的預測方法，因此，本文首次將Holt差分預測模型用于環境變化響應中，同時，基于不同時間窗下的若干靜態多目標優化問題的思考，視其為一個整體，借助MOEA/D［23］的分解思想，提出了一種新的基于Holt差分預測校正的動態多目標優化算法。該算法主要創新點如下：

a）使用變點檢測中的Wilcoxon符號秩檢驗方法對動態環境變化進行檢測，并提出環境感知算子，對環境變化強度進行判定。同時，提出一種新的環境感知雙變異的方法作用于種群，以維持種群多樣性。

b）首次將Holt預測模型用于種群個體的預測，創新性地提出Holt差分預測校正模型，對種群個體在下一個時間窗的位置進行預測，并根據參考點校正預測值，以達到提高算法預測精度的目的。

1 相關工作

1.1 DMOP的定義

不失一般性，以最小化優化問題表示DMOP，該表達為

min f（x，t）=（f1（x，t），f2（x，t），…， fm（x，t））

s.t. x∈∏ni［ai，bi］={x=（x1，x2，…，xn）|ailt;lt;xlt;lt;bi}

i=1，2，…，n（1）

其中： f（x，t）包含m個目標函數fi（x，t），i=1，2，…，m，它隨著時間t的變化而改變；x=（x1，x2，…，xn）為n維決策變量；∏ni［ai，bi］是種群搜索空間，下文統一稱為Ω；ai和bi表示決策變量x在i維上的邊界。

定義1 Pareto支配。如果u，v∈Ω，滿足u支配v（uv），當且僅當fi（u）≤fi（v），i={1，2，…，m}，且j∈{1，2，…，m}，使得fj（u）lt;fj（v）。

定義2 Pareto最優解集（PS）。假設決策變量x′∈Ω，在任意t時刻內，x′嚴格優于任意x，則x′被稱為目標函數在時刻t的Pareto最優解。在t時刻的所有Pareto最優解所構成的集合被定義為Pareto最優解集PS，PS（t）表達如式（2）所示。

PS（t）={x′∈Ω|x∈Ω，x′x}（2）

定義3 Pareto前沿（PF）。在t時刻，Pareto解集在相應目標空間中的映射被稱為Pareto前沿，PF（t）表達如式（3）所示。

PF（t）={f（x，t）|x∈PS（t）}（3）

1.2 基于分解多目標優化算法

基于分解多目標優化算法包含多種分解方法，本文采用切比雪夫TCH（Tchebycheff）作為分解方法。設w1，…，wN是一組均勻分布的權重向量，一個多目標優化問題可分解為N個單目標子問題，第j個子問題為

minimize g（x|wj，z*）=maxi∈{1，…，m}wi|fi（x）－z*i|（4）

當前時間窗內每個目標的最小值構成參考點z*=（z*1，…，z*m）T，即z*i=min{fi（x），x∈Ω}（i=1，2，…，m），在MOEA/D中，每個子問題都對應一個權重向量wj，每個子問題的鄰域由其最近的幾個權重向量組成，這些最近的權重向量被稱為wj的鄰域。因此，第j個子問題的鄰域包含了所有具有來自wj鄰域的權重向量的子問題。每個子問題的鄰域由與其權重向量最接近的一組子問題組成，這些子問題與該權重向量的鄰域中的其他子問題具有相似的目標優化方向。

受差分進化思想的啟發，文獻［24］對MOEA/D進行改進，引入了交叉、差分變異，用于加快種群尋優速度。其中，差分變異公式如式（5）所示。

wi（g）=xr1（g）+F·（xr2（g）－xr3（g）） （5）

其中：xr1（g）、xr2（g）、xr3（g）為當前種群中3個隨機個體；F是縮放因子，用于調節該算法中種群個體變異的幅度。

1.3 預測策略

目前大部分基于預測方法主要是根據種群在歷史時間窗的信息去學習種群某些特定的行為特征，并建立模型，用于預測種群未來變化趨勢。例如：自回歸模型（AR）、移動平均模型（MA）等，自回歸模型的基本形式可以表示為

Xt=c+φ1Xt－1+φ2Xt－2+…+φpXt－p+εt（6）

其中：Xt是在時間點t的觀測值；c是常數項；φ1，φ2，…，φp是模型參數，表示各滯后項的系數；p是模型的階數；εt是時間點t的誤差項。

一個q階移動平均模型可以表示為

Xt=μ+εt+θ1εt－1+θ2εt－2+…+θqεt－q（7）

其中：μ是時間序列的均值；θ1，θ2，…，θq是模型參數；q是模型階數。其他參數與式（6）相同。

Wang等人［25］提出了一種結合了四種預測模型的集成方法，其中兩種為自回歸模型（如式（6）所示），當檢測到環境發生變化時，該方法會選擇隨機重新初始化種群。但是這種基于自回歸模型的集成方法，由于集成方法數量多，所以可能會間接地影響算法的預測效果及增加時間成本。Karasu等人［26］提出了一種基于平均距離的線性預測模型，以解決一類具有平移 Pareto 最優解的動態多目標優化問題。除此之外，Zhou等人［27］提出一種基于種群預測的優化算法 （population prediction strategy， PPS），該算法在種群的中心點構造好了時間序列，并且同時結合 PF的總體分布特性，但該算法要求環境的變化需具有周期性或者變化前后具有一定程度的相似性，所以該方法限制了算法的自適應性的能力。

隨著越來越多的預測策略被提出，眾多學者致力于研究更簡單但不失預測精度的預測模型。因此，本文提出一種新的Holt預測模型對種群個體進行預測，以實現種群對環境變化的快速響應，同時，提出一種新的校正機制或補償機制對預測值進行修正，以提高不同環境變化強度下對個體的預測精度。如何準確預測、減少預測誤差、動態地校正預測值是本文所要研究的重點內容之一。

2 算法設計

本文提出基于環境感知與預測校正的動態多目標優化算法。該算法以MOEA/D為基本框架，采用威爾科克森符號秩檢驗（Wilcoxon signed rank test）對環境變化進行檢測，并提出新的環境感知算子對環境變化強度進行判定；為保持環境變化下種群的多樣性，提出環境感知雙變異策略對種群個體進行變異；為提高種群尋優速度，構建Holt差分預測校正模型來預測種群個體在下一個時間窗的位置，同時模型根據參考點對預測值進行校正，校正后的預測值與原個體共同參與到下次的迭代進化中，以實現種群對變化環境快速響應的目的。

算法1 HD-DMOEA整體框架

輸入：一個動態多目標問題、一個迭代終止標準、N（種群個體數量）、W（鄰域大小）、W1，…，WN（N個權重向量）。

輸出：Pnew（新種群）。

for i=1 to N

取xi最近的一組權重向量B（i）={i1，…，is}

end for

while 不滿足迭代終止標準

使用算法2進行環境檢測；

使用算法3預測校正得到新種群P′；

Pnew=P′；

end while

2.1 環境檢測機制

2.1.1 Wilcoxon符號秩檢驗

在動態多目標優化中，種群個體適應度會隨著環境的變化或者種群的迭代優化產生差異性變化。由于Wilcoxon符號秩檢驗不僅適用于大樣本數據檢測，而且適用于檢測同一組數據在兩個不同時間點內是否存在差異，所以本文采用變點檢測中的Wilcoxon符號秩檢驗作為環境變化檢測方法對動態環境進行檢測。

Wilcoxon符號秩檢驗的詳細步驟如下［28］：

a）假設檢驗：

（a）零假設（H0）：兩個相關樣本的差異中位數為零，即兩個樣本沒有顯著差異。

（b）備擇假設（H1）：兩個相關樣本的差異中位數不為零，即兩個樣本存在顯著差異。

b）收集兩個樣本數據，并計算它們之間的差異值。

c）將差異值取絕對值之后排序。

d）賦予秩次：為排序后的差異值分配秩次。

e）計算秩和：分別計算正秩次的秩和（稱為W+）和負秩次的秩和（稱為W－），計算方法如式（8）（9）所示。

f）計算檢驗統計量：將較小的秩次和作為檢驗統計量。如果樣本量較大（通常大于50），則可以使用正態分布的近似方法來計算檢驗統計量的p值，計算方法如式（10）所示。不失一般性，p值用于衡量觀察到的數據與零假設的一致性，較小的p值表明觀察到的數據在零假設下是不太可能的，從而拒絕零假設。

g）判斷顯著性：將檢驗統計量與顯著性水平進行比較。如果p值小于顯著性水平（通常為0.05），則拒絕零假設，認為兩個樣本之間存在顯著差異。

如果用R+j表示|xj|在絕對值樣本中的秩，則正秩次總和（正秩次是指差異值大于零的樣本對應的秩次之和）計算方法如式（8）所示。

W+=∑nj=1R+jI（xjgt;0）（8）

負秩次總和（負秩次是指差異值小于零的樣本對應的秩次之和）計算方法如式（9）所示。

W－=∑nj=1R－jI（xjlt;0）（9）

其中：n為樣本個數；I（xjgt;0）是一個指示函數，如果xjgt;0則該函數值為1，否則為0；相反，I（xjlt;0）表示xjlt;0則該函數值為1，否則為0。

本文使用正態分布的近似方法來計算檢驗統計量的p值，其計算方法如式（10）所示。

Z=W+－n（n+1）/4n（n+1）（2n+1）/24～N（0，1）（10）

根據計算得到的Z值，使用標準正態分布的累積分布函數（CDF）來計算p值，計算方法如式（11）所示，p值是Z值對應的雙側概率。

φ（z）=∫z－∞12πe－x2/2dx（11）

假設現在所檢測的是一個雙目標問題，首先需要創建一個窗口滑動模型，該模型的數據流創建、檢測的操作流程如圖1所示。假設算法在T時刻完成了第 i 次迭代，則先檢測的是綠色虛線框內的兩個綠色實線窗口（參見電子版），這兩個窗口分別表示算法在T時刻得到的兩個目標的種群適應度，檢測完之后算法繼續迭代，當來到時間窗T+1時，執行第二次檢測，也就是圖1中的橙色虛線框內的兩個橙色實線窗口（同上），如果是三目標及三目標以上的測試集，則依次對應增加數據流即可。

2.1.2 環境感知算子

近年來，由Liu等人［29］提出的一種評價環境變化強度的策略備受學者關注，該策略利用當前種群和歷史種群之間的目標值偏差來估計環境變化，其具體表達如式（12）所示。

Fmean=1N∑mj=1 ∑Ni=1（fj（xi，t））2（12）

其中：Fmean表示在t時刻的種群均方差；N是種群數量；m是函數f（x，t）的目標數量； fj（xi，t）是第i個種群個體在t時刻的第j個目標的適應度值。同時，為判定環境變化強度，文獻［29］給出了一個變化強度閾值Ieva（t），其計算方法如式（13）所示。

Ieva（t）=Fmeancur－FminFmax－Fmeancur（13）

其中：Fmeancur表示當前窗口種群個體的均方差；Fmax和Fmin分別表示歷史窗口中種群個體的最大均方差和最小均方差。

此外，本文提出一種新的環境感知算子Iepo，其表達式為

Iepo=exp（－1/（nt+τt））（14）

其中：nt為環境變化強度；τt為環境變化頻率。當Iepolt;Ieva（t）時，視環境的變化是溫和的，即種群個體的可控程度大于環境變化強度，反之，當Iepo≥Ieva（t）時，視環境的變化是劇烈的，即種群個體的可控程度小于環境感知算子。

2.1.3 環境感知雙變異

當環境發生變化時，依環境變化強度的不同，計算新個體引入比例ratio（t）（如式（15）所示）以獲得種群變異的個體數量Nnew（如式（16）所示）：

ratio（t）=min{Ieva（t），1}" Iepolt;Ieva（t）

Iepo Iepo≥Ieva（t） （15）

Nnew=N×ratio（t）（16）

當環境變化強度為溫和時，選取Nnew個種群個體進行第一階段的交叉變異，產生新個體與原種群剩余的N－Nnew個種群個體共同進入下一代的進化搜索中，從而加速逼近PF。圖2顯示的是環境變化為溫和情況下，新時間窗開始時雙目標空間中新種群分布的示例。當環境變化強度為劇烈時，將離參考點z*最近的Nnew個種群個體進行第一階段的交叉變異，并隨機初始化剩余種群個體，因為在劇烈的環境變化中，隨機生成的新個體可以加快種群尋優的速度。圖3顯示的是環境變化劇烈情況下，新時間窗開始時雙目標空間中新種群分布的示例。

圖2 假設N=6，舊解與預測解的比例

Fig.2 Assuming N=6， the ratio of old to predicted solutions

圖3 假設Nnew=3，則選出三個最接近Z*的解，其余的進行初始化

Fig.3 Assuming Nnew=3， the three closest solutions to Z* are selected and the rest solutions are initialized

假設在以前的時間窗中獲得的一系列個體解記為{P1，P2，…，PK}，時間窗數量記為K，將兩個時間窗的種群個體使用Wilcoxon符號秩檢驗進行檢測，如果檢測到環境發生變化，使用環境感知算子進行環境變化強度的判定，根據環境的變化程度自適應地選取交叉變異個體參與下一輪的進化。

算法2 環境檢測機制

輸入：PT，PT+1（對應兩個時間窗的個體解）、N（種群個體數量）、P（當前的種群）、z*（當前的參考點）、τT（環境變化頻率）、Iepo（環境感知算子）。

輸出：P′（更新的種群）、z′（更新的參考點）。

for i=1 to N

if i%τT=1

對PT、PT+1進行Wilcoxon符號秩檢驗；

分別計算Fmean和Ieva（t）；

if Ieva（t）gt;Iepo

Nnew=N×min（Ieva（t），1）；

選擇種群中離參考點最近的Nnew/2個個體進行交叉變異；

else

Nnew=N×Iepo；

選擇種群中離參考點最近的Nnew個種群個體進行交叉變異，剩余個體重新進行隨機生成；

end if

end if

end for

2.2 預測校正機制

2.2.1 Pareto三元解

算法在當前種群內選取三個指定個體作為當前時間窗內的Pareto三元解（式中統稱為Triad），它們分別是：精英解、平衡解和多樣性解。

精英解——當前時間窗離參考點z*最近的個體，代表當前PF中的最優解。

平衡解——既未嚴格靠近參考點z*，也不顯著偏離，維持在一個相對適中的距離范圍內，代表在算法優化中的一種平衡。

多樣性解——距離參考點z*最遠的個體，代表了在PF上的一個極端，它有助于為算法的迭代優化提供多樣性和全面性。圖4展示了Pareto三元解與參考點的相對位置關系。Holt差分預測校正模型通過對Pareto三元解在下一個時間窗位置的預測和校正來實現對整個種群的預測和校正。本文假設種群所有個體在不同時間窗上的移動趨勢與Pareto三元解的移動趨勢是一致的。雖然這種假設可能會引入一定程度的誤差，但鑒于預測的種群個體新位置僅作為種群下一步搜索過程的起點，這部分誤差在可接受范圍內。

2.2.2 Pareto三元Holt預測模型

該預測模型旨在通過歷史時間窗Pareto三元解的位置來估計Pareto三元解在當前時間窗T結束時的移動趨勢ΔXT，從而估計種群的其他個體在時間窗T+1上所處的位置。為防止產生誤導，本文根據時間窗設置了一個滑動窗口模型，Pareto三元解會根據時間窗的變化而改變，具體模型如下：

Triadt+T=at+bt·T（17）

at=2S（1）t－S（2）tbt=a1－a（2S（1）t－S（2）t）（18）

S（1）t=a·Triadt+（1－a）S（1）t－1（19）

S（2）t=a·S（1）t+（1－a）S（2）t－1（20）

ΔXT=TriadT+1－TriadT（21）

式（17）是計算Pareto三元解在時間窗t+T 上的位置，at和bt是兩個參數變量。S（1）t表示在t時間窗內的一次指數平滑值，S（2）t表示在t時間窗時的二次指數平滑值。a是記憶衰減因子，其取值為［0，1］，a值越大，模型對歷史數據“遺忘”的就越快，因此，當種群在歷史時間窗的位置波動相對平穩時，可取較大的a；當種群在歷史時間窗的位置波動較大時，應取較小的a。在本文中，當環境感知算子檢測到環境變化是溫和的，則a取較大值；若檢測到環境變化是劇烈的，則a取較小值。

圖5展示了種群所有解在不同時間窗的運動，當得到Pareto三元解在時間窗T上的運動趨勢ΔXT后，在時間窗T+1上的種群其他個體的位置如式（22）所示。

鑒于種群歷史時間窗口的數量存在限制，這類基于個體的Holt預測方法的準確度尚有提升空間，因此，本文進一步提出了一個預測校正機制以增強模型的預測精度。

XT+1i=XTi+ΔXT" i=1，2，…，N（22）

2.2.3 Pareto三元二階差分模型

通過2.2.2節三元Holt預測模型，獲得相鄰時間窗內種群預測值，采用二階差分思想［30］，對式（22）進行二階差分處理，具體改進如式（23）（24）所示。

ΔX1T=TriadT－TriadT－1（23）

ΔX2T=ΔX1T+（ΔX1T－（TriadT－1－TriadT－2））（24）

在現實中，各種各樣的優化問題可能會以不同的方式發生變化，例如隨機變化、非線性變化等［31］。為簡化模型的處理過程，使之能夠在復雜多變的動態環境中應用，新模型將Pareto三元解在不同時間窗上的運動視為在一系列間隔時間內以相同加速度進行的運動，此時T+1時間窗內種群個體預測位置由式（25）獲得。

XT+1i=XTi+ΔX2T" i=1，2，…，N（25）

三元Holt預測模型和Pareto三元二階差分模型在獲得預測個體位置后，衡量預測個體與參考點的距離進行擇優選取的過程被稱為Holt差分預測校正。圖6展示了預測校正過程。預測校正機制的偽代碼在算法3中給出。

算法3 預測校正機制

輸入：TriadT，TriadT－1，TriadT－2（三個時間窗的Pareto三元解）、N（種群個體數量）、PT={XTi}（當前的種群）、z*（當前的參考點）、a（記憶衰減因子）、T（環境變化計數器）。

輸出： P′（更新的種群）、Z′（更新的參考點）、T（環境變化計數器）。

for i=1 to N

if T=2

使用Holt模型預測XT+1i；

else if T≥3

分別使用Holt模型和差分模型預測校正XT+1i；

擇優選取N個個體形成新的種群P′；

end if

end for

3 實驗設計與結果分析

本章通過對比仿真實驗驗證了HD-DMOEA算法解決DMOP的綜合性能，給出了實驗所使用的測試集與算法性能評價指標、對比算法及實驗參數設置、實驗結果與分析、環境變化檢測有效性分析等。為確保實驗公平性，所有實驗均在MATLABR2021a上進行。

3.1 測試函數與性能指標

本文實驗采用7個標準動態多目標測試函數，分別是4個FDA函數（FDA1～FDA4）、3個dMOP函數（dMOP1～dMOP3），按照不同特征，所有測試函數如表1所示，其中n表示決策空間，m表示優化目標個數。

在每個測試函數中設定一個時間參數t，其數學表達式為

t=1ntτ/τt（26）

其中：nt表示是環境變化強度；τ表示迭代次數；τt表示環境變化頻率。

本文采用平均反世代距離（MIGD）對DMOEA的收斂性和多樣性進行評價［32］，其具體定義如式（27）所示。

MIGD=1|T|∑t∈TIGD（P*t，Pt）（27）

其中：T是一組運行時的離散時間點；|T|是T的基數；P*t表示真實前沿；Pt表示算法得到的一組近似前沿的解。IGD被稱之為反世代距離，通過度量靜態環境中種群逼近真實PF的程度來評價算法的收斂性與多樣性，MIGD在IGD的基礎上加上時間序列，即算法在多個時間窗內IGD值的平均值。反世代距離（IGD）具體指標定義如式（28）所示。

IGD（P*t，Pt）=∑v∈PFtd（v，Pt）|P*t|（28）

其中：d（v，Pt）表示個體v到Pt之間的最小歐氏距離；|P*t|表示真實前沿中解的個數。

3.2 算法性能對比及其參數設置

3.2.1 對比算法

本文選取目前先進的五種基于預測模型的算法與HD-DMOEA進行比較，這五種先進算法分別是：基于個體遷移學習方法IT-DMOEA［33］、基于膝點的遷移學習方法KT-DMOEA［34］、基于混合預測策略與改進社會學習優化算法HPS-DMOP［35］、穩態世代進化算法SGEA［36］和多向預測策略MDP［37］。

3.2.2 參數設置

所有算法當m為2時，種群個數N設置為100，當m為3時，N設置為200。在HD-DMOEA中將交叉概率CR設置為0.5，縮放因子F設置為0.5，鄰域大小w設置為20，突變概率PM設置為1/n（其中n為決策變量數目）。為保證公平性，本文將所有算法的相同參數設置相同，其余特殊參數按原論文設置，同時，對比算法隨機抽取20%的種群個體進行重新評估，以此來評定該時間窗環境是否發生變化。每次運行的總代數固定為30×τt，這樣可以保證在每次實驗中至少發生30次環境變化。

為了探索環境變化頻率τt和環境變化強度nt的影響，本文采用多種參數不同的搭配。其中τt取值為20，nt分別取值為5、10、20。

3.3 實驗結果與分析

將本文HD-DMOEA分別與五種對比算法進行實驗比較，表2、3記錄六種算法的MIGD在30次實驗中的均值和標準差，最好的實驗結果加粗顯示標注（表中“+/－/～”分別表示該結果與HD-DMOEA相比好于、差于、相似）。為了更直觀地進行比較，圖8展示了每種算法在30個時間段的MIGD值趨勢。

從表2、3中不難看出，HD-DMOEA在測試集類型Ⅱ這種環境多變的情況下，與其他對比算法相比依舊能保持較明顯的優勢。眾所周知，FDA1、FDA2、FDA3和dMOP3測試函數分別包含了不同類型環境變化的DMOP：FDA1的PS隨時間呈現正弦趨勢但PF保持不變；FDA2的PF形狀隨時間從“凸”變為“非凸”；dMOP3中PF的變化具有隨機性，這種隨機性的變化對預測性算法是一種挑戰；而FDA3是由環境變化導致的PF偏移。HD-DMOEA、HPS-DMOP和SGEA在FDA3上均表現良好，在dMOP1測試函數中，HPS-DMOP在一組實驗中表現最佳，而HD-DMOEA在其余測試函數中均表現出最優異的性能，實驗結果表明HD-DMOEA具有良好的魯棒性。

3.4 環境變化檢測有效性分析

由表1可知FDA2、FDA3以及dMOP1和dMOP2都是屬于類型Ⅱ的測試問題，即PF會隨著時間的變化而改變，這類測試函數可用于檢驗環境變化檢測方法是否有效。因此本文將Wilcoxon符號秩檢驗在該類型測試函數上檢測到的前20個時間窗的變點分別展示于圖7（a）～（d），存在變點即可說明種群在該時間窗發生環境變化。

當實驗中存在一個目標在時間窗T與時間窗T+1上的目標函數值經過Wilcoxon符號秩檢驗方法得到的p值小于設定的閾值（threshold，通常設置為0.05）［29］，即可說明種群在該時間窗的環境發生變化。如圖所示，圖7中包含三條線，藍線代表種群第一個累積目標函數值，綠線代表種群第二個累積目標函數值、紅色虛線代表閾值（參加電子版）。當任意一個目標的p值小于閾值時，變點將以紅點的形式標注于圖中，由于FDA3的PF是發生偏移的，所以在該測試問題上檢測到的環境變化也比較明顯，并且每發生一次環境變化都會被檢測到。而其余測試問題雖然會存在一個目標超過閾值的情況，但Wilcoxon符號秩檢驗方法規定，只要任意一個目標的p值小于閾值，就判定環境發生變化，由圖7可知屬于類型Ⅱ的測試問題中發生的環境變化都能被有效檢測到。因此， Wilcoxon符號秩檢驗用于檢測環境變化是一種非常有效的手段。

3.5 MIGD對比分析

圖8（a）～（f）展示的是當環境變化強度nt=20，環境變化頻率τt=20時，六種算法在部分FDA測試集以及dMOP測試集上得到的MIGD值。根據圖8所示，在FDA2測試函數中，HPS-DMOP與HD-DMOEA的MIGD穩定性最好，兩者都具有較好的性能；在FDA3測試函數中，SGEA和HPS-DMOP的MIGD穩定性都要高于HD-DMOEA，其中，HPS-DMOP的MIGD穩定性最好，這可能是由于它自身具有改進的社會學習算法，具有快速穩定的追蹤能力，所以在PF發生平移時，能夠繼續保持穩定；在FDA4測試函數中，所有算法都表現出不穩定性，HD-DMOEA相對而言MIGD是最穩定的，因此HD-DMOEA在具有三個目標的測試函數下，其性能相對較好；在dMOP1測試函數中，HPS-DMOP與HD-DMOEA的MIGD穩定性最好，但其余算法也有較好的穩定性，只有MDP的MIGD穩定性稍差，可能是由于MDP沒有獲得足夠的個體來預測PF的變化類型；在dMOP2測試函數中HD-DMOEA的MIGD穩定性最好，除了MDP，其余算法都在部分運行時能夠超過HD-DMOEA和HPS-DMOP，但總體而言沒有兩者穩定；在dMOP3測試函數中，HD-DMOEA的MIGD最穩定。綜上所述，HD-DMOEA在這些測試集中的MIGD最穩定，算法魯棒性最強。

如表2和3所示，HD-DMOEA在不同的nt、τt組合中，在所有測試問題上的MIGD值的標準差都是遠遠小于其余算法。當MIGD的標準差較小時，意味著在算法在多次運行中，得到的解集質量較為一致，不會出現較大波動，即表示在不同的運行條件和隨機因素下依然能夠保持較好的性能，進一步驗證了算法的穩定性和魯棒性。

為了更直觀地評估六種算法的性能，本文使用Friedman檢驗用于檢測不同算法在多個測試集上的性能是否存在顯著性差異，隨后使用Nemenyi后續檢驗，使用該檢驗是為了確定哪些算法對之間的性能差異是顯著的，因為Nemenyi后續檢驗可以利用其CD差值進行多重算法的比較，CD差值的計算方法為

CD=qαK（K+1）6N（29）

其中：qα的取值是由表4決定；K表示對比算法的個數；N表示測試函數的個數。本文對比算法有6個，因此qα取值為2.85。

圖9（a）～（f）展示了六種算法在τt=20，nt=5、10、20時的平均排名以及CD差值圖。圖9（a）～（c）展示的是算法的平均排名，圖中HD-DMOEA的平均排名數值最低，即表示該算法基本在所有測試集中排名最前。圖9（d）～（f）展示的是六種算法的CD差值圖，坐標軸上的數字越小，代表性能越好，即算法的均值列秩越小越好。由圖9可知，在nt=5，τt=20時，HD-DMOEA的算法性能最好，并且遠超其余算法，在nt=10，τt=20時，HD-DMOEA的算法性能依舊最好，在nt=20，τt=20時，HD-DMOEA的表現穩定且超過其他算法，此時HPS-DMOP表現也比之前更佳。根據Friedman檢驗與Nemenyi 后續檢驗的結果，本文認為HD-DMOEA的算法性能要優于其他算法，并且該算法能夠在不同的環境下一直保持性能最佳，具有良好的魯棒性和穩定性。

3.6 參數敏感性分析及消融實驗

3.6.1 參數敏感性分析

參數a是Pareto三元Holt預測模型的重要組成部分，它能根據環境感知算子快速調整算法響應狀態，使得算法能一直維持不錯的性能。本文通過選取不同的a，分別做了幾組對比實驗。當檢測到環境變化強度為劇烈時（a1=0.7，0.8，0.9）、環境變化強度為溫和時（a2=0.3，0.2，0.1），分別選取5個有代表性的測試函數，含有變化的以及不變化的PF的測試函數，表5給出了HD-DMOEA變體的實驗結果。5個測試函數中體現算法性能的MIGD最佳值以加粗顯示。據表5所示，在15個不同組合的測試函數中，HD-DMOEA算法獲得了12個性能最佳結果。HD-DMOEA-Ⅰ算法獲得了2個性能最佳結果，HD-DMOEA-Ⅱ算法獲得了1個性能最佳結果。結果表明，HD-DMOEA算法的性能優于其他兩種變體算法。

通過比較HD-DMOEA和HD-DMOEA變體的實驗結果，當a1=0.8，a2=0.2時，15個不同參數搭配測試函數的MIGD值最小。由此可見，HD-DMOEA的記憶衰減因子最佳搭配方案為a1=0.8，a2=0.2。

3.6.2 消融實驗

本文提出的HD-DMOEA的環境變化響應策略有預測校正策略和環境感知雙變異策略兩個組成成分。本文將預測校正策略中的差分預測模型單獨使用，命名為HD-DMOEA1。將Holt預測模型單獨使用，命名為HD-DMOEA2。兩者分別進行預測，根據實驗結果判斷預測校正策略是否有效。為了進一步驗證環境感知雙變異策略的有效性，本文將雙變異改為單變異，命名為HD-DMOEA3。由表6可知，對比HD-DMOEA和HD-DMOEA1以及HD-DMOEA2，算法單獨使用差分預測模型和Holt預測模型的效果都不如預測校正策略，因此，本文認為預測校正策略具有有效性。根據HD-DMOEA和HD-DMOEA3的結果可知，雖然在部分測試中，雙變異策略的效果不是很好，但對于如FDA3這種PF平移變化的情況，需要增加種群的多樣性才會有更好的效果?？傮w來說HD-DMOEA優于HD-DMOEA3，因此，環境感知雙變異策略也具有有效性。

4 結束語

本文提出了一種新型的環境檢測方法與預測校正模型相結合的算法，通過靈敏地檢測環境變化使種群能及時對環境變化作出響應；構建Holt差分預測校正模型，實現動態變化下對PF的快速準確追蹤，并使用環境感知雙變異策略根據環境變化強度自適應地選擇個體進行變異，以此維持種群多樣性。此外，本文提出的Pareto三元解能夠更加客觀地描述種群的運動趨勢。HD-DMOEA在上述各種類型測試函數上表現出良好的收斂性與多樣性，并具有較好的魯棒性。同時采取消融實驗以及參數敏感性分析驗證了該方法可以有效地提高算法的動態優化性能。

為取得多目標問題上更加理想的效果，在后續實驗中，將針對此類問題進一步展開研究。在未來的工作中，針對如邊緣計算資源調度等實際問題，研究重心將放在尋找一組在不同的時間段內表現較為良好的可接受優化解，而并非執著于尋找每個時間段中表現最佳的優化解，從而減少不必要的時間、能耗等成本。

參考文獻：

［1］Tavakkoli M R， Hoseina A， Tanhaeean M， et al. Multi-objective boxing match algorithm for multi-objective optimization problems ［J］. Expert Systems with Applications， 2024， 239： 122394.

［2］Sohani A， Dehnavi A， Sayyaadi H， et al. The real-time dynamic multi-objective optimization of a building integrated photovoltaic thermal （BIPV/T） system enhanced by phase change materials ［J］. Journal of Energy Storage， 2022， 46： 103777.

［3］Liu Zhifeng， Li Lingling， Liu Yuwei， et al. Dynamic economic emission dispatch considering renewable energy generation： a novel multi-objective optimization approach ［J］. Energy， 2021， 235： 121407.

［4］唐湘黔， 錢淑渠， 武慧虹. 混雜免疫多目標優化算法及對動態經濟環境調度問題優化 ［J］. 計算機應用研究， 2023， 40（9）： 2720-2728. （Tang Xiangqian， Qian Shuqu， Wu Huihong. Hybrid immune multi-objective optimization algorithm for dynamic emission economic dispatch ［J］. Application Research of Computers， 2023， 40（9）： 2720-2728.）

［5］Qiao Kangjia， Chen Zhaolin， Qu Boyang， et al. A dual-population evolutionary algorithm based on dynamic constraint processing and resources allocation for constrained multi-objective optimization problems ［J］. Expert Systems with Applications， 2024， 238： 121707.

［6］Niu Guoqiang， Li Xiaoyong， Wan Xin， et al. Dynamic optimization of wastewater treatment process based on novel multi-objective ant lion optimization and deep learning algorithm ［J］. Journal of Clea-ner Production， 2022， 345： 131140.

［7］Zheng Jinhua， Zhou Fei， Zou Juan， et al. A dynamic multi-objective optimization based on a hybrid of pivot points prediction and diversity strategies ［J］. Swarm and Evolutionary Computation， 2023， 78： 101284.

［8］Liang Zhengping， Zheng Shunxiang， Zhu Zexuan， et al. Hybrid of memory and prediction strategies for dynamic multi-objective optimization ［J］. Information Sciences， 2019， 485： 200-218.

［9］Wang Zitong， Pei Yan， Li Jianqiang. A survey on search strategy of evolutionary multi-objective optimization algorithms ［J］. Applied Sciences， 2023， 13（7）： 4643.

［10］Li Jianxia， Liu Ruochen， Wang Ruinan. A change type-based self-adaptive response strategy for dynamic multi-objective optimization ［J］. Knowledge-Based Systems， 2022， 243： 108447.

［11］Wu Yan， Jin Yaochu， Liu Xiaoxiong. A directed search strategy for evolutionary dynamic multi-objective optimization ［J］. Soft Computing， 2015， 19（11）： 3221-3235.

［12］Jiang Shouyong， Yang Shengxiang. A steady-state and generational evolutionary algorithm for dynamic multi-objective optimization ［J］. IEEE Trans on Evolutionary Computation， 2017， 21（1）： 65-82.

［13］Ma Xuemin， Yang Jingming， Sun Hao， et al. Double-space environmental change detection and response strategy for dynamic multi-objective optimize problem ［J］. Swarm and Evolutionary Computation， 2024， 85： 101468.

［14］馬永杰， 陳敏， 龔影， 等. 動態多目標優化進化算法研究進展 ［J］. 自動化學報， 2020， 46（11）： 2302-2318. （Ma Yongjie， Chen Min， Gong Ying， et al. Research progress of dynamic multi-objective optimization evolutionary algorithm ［J］. Acta Automatica Sinica， 2020， 46（11）： 2302-2318.）

［15］Chen Renzhi， Li Ke， Yao Xin. Dynamic multi-objective optimization with a changing number of objectives ［J］. IEEE Trans on Evolutionary Computation， 2018， 22（1）： 157-171.

［16］Zhang Junxi， Qu Shiru， Zhang Zhiteng， et al. An acceleration-based prediction strategy for dynamic multi-objective optimization ［J］. Soft Computing， 2024， 28（2）： 1215-1228.

［17］Peng Hu， Xiong Jianpeng， Pi Chen， et al. A dynamic multi-objective optimization evolutionary algorithm with adaptive boosting ［J］. Swarm and Evolutionary Computation， 2024， 89： 101621.

［18］Raghul S， Jeyakumar G. A hybrid multi-population reinitialization strategy to tackle dynamic optimization problems ［J］. IEEE Access， 2023， 11： 114270-114282.

［19］Wang Fengxia， Huang Min， Yang Shengxiang， et al. Penalty and prediction methods for dynamic constrained multi-objective optimization ［J］. Swarm and Evolutionary Computation， 2023， 80： 101317.

［20］Yang Cuili， Wang Danlei， Tang Jian， et al. Multi-reservoir ESN-based prediction strategy for dynamic multi-objective optimization ［J］. Information Sciences， 2024， 652： 119495.

［21］Liang Zhengping， Zou Ya， Zheng Shunxiang， et al. A feedback-based prediction strategy for dynamic multi-objective evolutionary optimization ［J］. Expert Systems with Applications， 2021， 172： 114594.

［22］Cao Leilei， Xu Lihong， Goodman E D， et al. Decomposition-based evolutionary dynamic multi-objective optimization using a difference model ［J］. Applied Soft Computing， 2019， 76： 473-490.

［23］Zhang Qingfu， Li Hui. MOEA/D： a multi-objective evolutionary algorithm based on decomposition ［J］. IEEE Trans on Evolutionary Computation， 2007， 11（6）： 712-731.

［24］Tanabe R， Ishibuchi H. Review and analysis of three components of differential evolution mutation operator in MOEA/D-DE ［J］. Soft Computing， 2019， 23（23）： 12843-12857.

［25］Wang Feng， Li Yixuan， Liao Fanshu， et al. An ensemble learning based prediction strategy for dynamic multi-objective optimization ［J］. Applied Soft Computing， 2020， 96： 106592.

［26］Karasu S， Altan A， Bekiros S， et al. A new forecasting model with wrapper-based feature selection approach using multi-objective optimization technique for chaotic crude oil time series ［J］. Energy， 2020， 212： 118750.

［27］Zhou Aimin， Jin Yaochu， Zhang Qingfu. A population prediction strategy for evolutionary dynamic multi-objective optimization ［J］. IEEE Trans on Cybernetics， 2014， 44（1）： 40-53.

［28］Sapl1olu K， Gülü Y S. Combination of Wilcoxon test and scatter diagram for trend analysis of hydrological data ［J］. Journal of Hydrology， 2022， 612： 128132.

［29］Liu Ruochen， Yang Ping， Liu Jiangdi. A dynamic multi-objective optimization evolutionary algorithm for complex environmental changes ［J］. Knowledge-Based Systems， 2021， 216： 106612.

［30］Sabir Z， Raja M A Z， Wahab H A， et al. Integrated neuro-evolution heuristic with sequential quadratic programming for second-order prediction differential models ［J］. Numerical Methods for Partial Differential Equations， 2024， 40（1）： e22692.

［31］Azzouz R， Bechikh S， Said L B， et al. Handling time-varying constraints and objectives in dynamic evolutionary multi-objective optimization ［J］. Swarm and Evolutionary Computation， 2018， 39： 222-248.

［32］Zhang Qingyang， Yang Shengxiang， Jiang Shouyong， et al. Novel prediction strategies for dynamic multi-objective optimization ［J］. IEEE Trans on Evolutionary Computation， 2020， 24（2）： 260-274.

［33］Jiang Min， Wang Zhenzhong， Guo Shihui， et al. Individual-based transfer learning for dynamic multi-objective optimization ［J］. IEEE Trans on Cybernetics， 2021， 51（10）： 4968-4981.

［34］Jiang Min， Wang Zhenzhong， Hong Haokai， et al. Knee point-based imbalanced transfer learning for dynamic multi-objective optimization ［J］. IEEE Trans on Evolutionary Computation， 2021， 25（1）： 117-129.

［35］張杰， 馬菲菲， 鄭禾丹， 等. 基于混合預測策略與改進社會學習優化算法的動態多目標優化方法 ［J］. 計算機應用研究， 2023， 40（4）： 1101-1107， 1118. （Zhang Jie， Ma Feifei， Zheng Hedan， et al. Dynamic multi-objective optimization method based on hybrid prediction strategy and improved social learning optimization algorithm ［J］. Application Research of Computers， 2023， 40（4）： 1101-1107， 1118.）

［36］Luo Wenjian， Sun Juan， Bu Chenyang， et al. Species-based particle swarm optimizer enhanced by memory for dynamic optimization ［J］. Applied Soft Computing， 2016， 47： 130-140.

［37］Khan M W， Salhi A. A decomposition-based hybrid multi-objective evolutionary algorithm with dynamic resource allocation ［J］. Applied Soft Computing， 2012， 12（9）： 2765-2780.