動态多目标優化（2019年）《Hybrid of memory and prediction strategies for dynamic multiobjective optimization》

記憶和預測政策相結合的動态多目标優化政策

文章目錄

• 記憶和預測政策相結合的動态多目标優化政策
• • 摘要(Abstract)
  • Introduction引言
  • • 1、定義動态多目标問題（DMOP）
    • 2、支配關系、PS、PF的定義
    • 3、據PS、PF的不同劃分４類DMOP
    • 4、目前DEMOEAs的主流政策和局限性
    • 5、本文提出的算法所具優勢
  • Related work相關工作部分
  • • 1、環境檢測
    • • 1）一些專門檢測個體的重新評估。
      • 2）通過檢測種群資料資訊來确定算法行為。
    • 2、環境響應
    • • 1）加速收斂的環境響應技術
      • • a）預測政策隻對具有預測性的動态變化有效。
        • b)記憶政策對于具有周期性的動态變化有效。
        • c)其他加快收斂性的政策。
      • 2）提高多樣性的環境響應技術
    • 3、靜态多目标優化
  • Proposed algorithm算法提出部分
  • • MOEA/D-HMPS的整體架構
    • • 1）環境檢測
      • 2）識别變化類型
      • 3）記憶政策
      • 4）環境響應
      • 5）基本的多目标進化算法
  • 結語

摘要(Abstract)

本文提出的DMOEA主要包括記憶與預測相結合的政策（HMPS)與基于分解的多目标進化算法(MOEA/D)，最終合成的算法（MOEA/D-HMPS）能夠通過檢測環境的變化、确定檢測到的目前環境變化與曆史變化的相似性，并基于此進一步确定響應政策。如果檢測到的變化與以往任何一次曆史變化都不相同，則基于前兩個連續的種群中心的差異性預測将用于在新環境中重定位種群個體。否則，若檢測到的變化與之前任何一次變化相同，則采用基于記憶的響應政策來預測種群個體的位置。兩種響應機制都現有解的一部分同随機産生的解混合在一起，用于避免由于急劇或不規則變化引起的預測誤差的影響。MOEA / D-HMPS已經針對14個基準問題進行了測試，并與最新的DMOEA進行了比較。 實驗結果證明了MOEA / D-HMPS在解決各種DMOP方面的效率。

Introduction引言

1、定義動态多目标問題（DMOP）

m i n      F ( x , t ) = ( f 1 ( x , t ) , ⋯   , f m t ( x , t ) ) T s . t .      g i ( x , t ) ≤ 0 , i = 1 , 2 , ⋯   , p h j ( x , t ) , j = 1 , 2 , ⋯   , p x ∈ Ω x ,      t ∈ Ω t        ( 1 ) \begin{array}{cc} min\;\;F(x,t)=(f_1(x,t),\cdots,f_{m_t}(x,t))^T \\ s.t.\;\; g_i(x,t) \leq 0,i=1,2,\cdots,p \\ h_j(x,t),j=1,2,\cdots,p \\ x \in \Omega_x,\;\;t\in \Omega_t \end{array}\;\;\;(1) minF(x,t)=(f1​(x,t),⋯,fmt​​(x,t))Ts.t.gi​(x,t)≤0,i=1,2,⋯,phj​(x,t),j=1,2,⋯,px∈Ωx​,t∈Ωt​​(1)

x=( x 1 , x 2 , . . . x n t x_1,x_2,...x_{n_t} x1​,x2​,...xnt​​)代表 n t n_t nt​維的決策變量向量，t代表離散的時間執行個體， m t m_t mt​t代表有多少個目标。 n t n_t nt​和 m t m_t mt​的值都會随時間變化。F(x,t)代表目标空間向量；p和q分别是不等式限制和等式限制的個數；其中 g i g_i gi​(x,t)代表第i個不等式限制； h j h_j hj​(x,t)代表第j個等式限制。 Ω x ∈ R n t \Omega_x \in R^{n_t} Ωx​∈Rnt​ 代表可行的決策空間; Ω t \Omega_t Ωt​代表可行的時間空間;

2、支配關系、PS、PF的定義

假設x、y都是候選解,我們定義t時刻,x支配y為：當且僅當在任意一維目标i上,都有 f i ( x , t ) ≤ f i ( y , t ) f_i(x,t) \leq f_i(y,t) fi​(x,t)≤fi​(y,t),并且存在某一維目标j使得符号化表示t時刻x支 f i ( x , t ) < f i ( y , t ) f_i(x,t) < f_i(y,t) fi​(x,t)<fi​(y,t)配y為 x ≺ t y x\prec_ty x≺t​y;如果解 x ∗ x^* x∗不受任何其他解的支配，我們稱之為非支配解，并且是pareto最優解，t所有pareto最優解構成的解集符号化表示為 P S t PS_t PSt​，表達式如下：

P S t = { x ∗ ∣ ∄ x ∈ Ω x , x ≺ t x ∗ } PS_t=\{x^*|\nexists x \in \Omega_x,x \prec_t x^*\} PSt​={x∗∣∄x∈Ωx​,x≺t​x∗}

相對應的目标向量解集符号化表示為 P F t PF_t PFt​，表達式如下：

P F t = { F ( x ∗ , t ) ∣ x ∈ P S t } PF_t=\{F(x^*,t)| x \in PS_t\} PFt​={F(x∗,t)∣x∈PSt​}

3、據PS、PF的不同劃分４類DMOP

​ 1）PS随時間變化，PF固定；

​ 2）PS、PF都随時間變化；

​ 3）PS固定，PF随時間變化；

4）PS、PF都固定，但問題仍随時間變化；

通常研究的焦點聚集在1）2）3）

4、目前DEMOEAs的主流政策和局限性

​ 1）基于預測的政策：專為可預測性的動态變化而設計；

​ 2）基于記憶的政策：用于處理有周期性變化的DMOPs；

​ 3）基于多樣性的政策：當發生動态變化易導緻多樣性喪失時該政策有效；

5、本文提出的算法所具優勢

​ 首先分析目前許多DMOPs既具有周期性又具有預測性。是以結合記憶和預測政策用以解決具有這兩類特征的動态多目标問題。許多現存的糅雜政策在并未判斷該政策是否适用該變化的情況下就采用了這樣相結合的響應機制，這很可能導緻曆史資訊無法得到有效的重用。

​ 而本文正是設計了這樣一種方法來辨識是否目前環境變化和以往的曆史變化相似，用以提高存儲資訊的重用效率。如果存在相似性，啟動記憶響應機制，否則啟用預測響應機制。本文設計的記憶驅動的預測政策可以用來響應相似的環境變化和加快收斂速度。并且使用這兩者的優勢在于能夠在保持種群良好分布性的情況下還追蹤到變化的PF/PS。與最新的其他動态多目标優化算法在14個基準問題上測試的效果來看，本文提出的MOEA/D-HMPS具有非常強的競争優勢。其主要優勢在于：

​ 1）一種有效檢測環境變化的固定檢測器方法。

​ 2）能夠處理相似和不相似變化的兩種響應機制。

​ 3）HMPS算法具有較好的魯棒性。原因是種群一半的個體來自 采用記憶-預測相結合政策後經排序的最優秀個體，另一半采 用輪盤賭政策決定現有個體被重用或者被随機産生的解替代

​ 4）在基于分解的多目标優化算法（MOEA/D）架構内采用HMPS算法。

Related work相關工作部分

1、環境檢測

1）一些專門檢測個體的重新評估。

​ 在每一代都重新評價這些檢測個體用以監測各個目标值的變化。這種方式很容易實作但是要求額外的評價函數并且不适應于有噪聲的環境。這種專門的探測個體包含固定的和不固定的兩類。前者在決策空間随機産生并且在每一代保持不變。而後者從現有種群中随機選擇并且每一代都有所變化。

2）通過檢測種群資料資訊來确定算法行為。

該方式通過檢測種群資料資訊和算法内在行為之間的差異性。這種方式不需要評價函數但是有可能造成錯誤的回報，進而導緻沒有發生環境變化時反應過度。

2、環境響應

​ 通過算法的表現行為将環境響應的技術分為兩類：加速收斂、提高多樣性。

1）加速收斂的環境響應技術

​ 包括基于預測的方法，用以解決具有可預測性變化的DMOPs和基于記憶的方法，針對具有周期性變化的DMOPs，這兩者都有利于加快收斂速度。

a）預測政策隻對具有預測性的動态變化有效。

​ 可以通過學習曆史的環境變化來預測新的最優解的位置，進而最優解能夠快速收斂到新的PS上。典型的有Hatzakis 和 Wallace提出的FPS（向前回報預測政策），該算法存儲了現有PF的邊界點，在一個時間序列的邊界點的基礎上，FPS使用自回歸模型預測新的邊界點的位置并且追蹤到新的PF。周愛民等人提出的PPS（種群預測政策）把PS分成中心點和形狀兩部分。基于一系列的存儲中心點，PPS采用一個單變量的自回歸模型來預測下一個中心點，通過利用之前的形狀(manifolds）來估計下一個形狀（manifold）。吳等人提出的DDS（方向搜尋政策）用前兩個時刻PS的中心點的移動方向預測新的最優解的位置。

​ Muruganantham 等人提出了一種基于預測的政策,即采用一種線性離散時間卡爾曼濾波用來估計新環境中最優解的位置,生成的算法MOEA / D-KF顯示出良好的能力，可以将個體重新定位到更接近新PS的位置，并具有非常不錯的性能。江 和楊聖祥出的穩态世代進化算法(SGEA)表明,當檢測到環境變化時，SGEA能夠組合現有的曆史最優解和從新環境中收集的最差解，用以重定位最優解。

b)記憶政策對于具有周期性的動态變化有效。

​ 通過重用已有的最有解或者新種群中的其他最優解來獲得較快的收斂性。基于記憶的政策可以顯式或隐式地實作。顯式的記憶政策中，當環境變化發生時，現有的最有解被重新引進到重新初始化的種群中。而隐式的記憶政策中，為了産生新環境中的個體使用了備援表現。

​ 比如，王等人提出了兩個記憶方案，其中先前的最優解被存儲在歸檔集中，環境發生變化時，第一個方案從歸檔集中随機挑選個體并引進到種群中。第二個方案也從歸檔集中随機挑選個體，但在他們并入新種群中之前會先用高斯局部搜尋做一些調整。

​ Koo等人提出了一種新的選擇性記憶技術來存儲之前的歸檔集中的幾何質心和質心方差。當環境發生變化時，選擇擁擠距離較小的記憶方案來産生新環境中的個體。彭舟等人提出了能夠更有效重用曆史解的新的預測和記憶政策（PMS），PMS主張在每個時刻都把非支配個體存儲到一個記憶池中，變化來臨時，記憶池中存儲的個體被重新評價後，将非支配個體選入新種群中。

c)其他加快收斂性的政策。

​ 比如Sen等人使用逆模組化方法在決策空間中生成個體，這有助于将搜尋引向有希望的領域。 江等人提出了一種新的算法架構，将轉移學習和傳統的MOEA（Tr-DMOEA）解決DMOP。 Tr-DMOEA通過使用基于曆史經驗的轉移學習技術來重新初始化有效種群，以促進進化過程。

2）提高多樣性的環境響應技術

​ 某些DMOPs的動态變化會導緻種群喪失多樣性，這時需要引進或者保持種群的多樣性。比較經典的有Deb等人提出的動态版本的非支配排遺傳算法（DNSGA-II），通常會用變異的解或者随機産生的解來替代種群中的一部分個體以提高環境變化發生後種群多樣性。Goh和Tan等人将競争性和協同性組合起來提出了一種新的動态協同進化算法（dCOEA),dCOEA采用一種競争機制将随機産生的解并入競争池中以提高種群多樣性。

​ 阮幹等人提出一種有效的多樣性保持政策（DMS）來提高解決動态多目标問題的MOEA的多樣性。根據決策空間每一維目标的曆史最大最小值的移動方向，DMS估計新環境下決策變量空間每一維目标的邊界，然後在估計的區域随機産生個體。

​ 盡管這些基于多樣性的政策能有效彌補環境變化發生後出現多樣性喪失的情況，但過度的引進多樣性有可能對種群收斂帶來負面影響，甚至導緻算法進化停滞。

​ 而本文提出的DMOEA融合了記憶與預測相結合的政策(HMPS)與基于分解的多目标進化算法架構(MOEA/D)，最終合成的算法（MOEA/D-HMPS）能夠通過檢測環境的變化、确定檢測到的目前環境變化與曆史變化的相似性，并基于此進一步确定響應政策。如果檢測到的變化與以往任何一次曆史變化都不相同，則基于前兩個連續的種群中心的差異性預測将用于在新環境中重定位種群個體。否則，若檢測到的變化與之前任何一次變化相同，則采用基于記憶的響應政策來預測種群個體的位置。兩種響應機制都現有解的一部分同随機産生的解混合在一起，用于避免由于急劇或不規則變化引起的預測誤差的影響。MOEA / D-HMPS已經針對14個基準問題進行了測試，并與最新的DMOEA進行了比較。 實驗結果證明了MOEA / D-HMPS在解決各種DMOP方面的效率。

3、靜态多目标優化

​ 在每兩次環境變化之間，DMOP自然是靜态MOP。是以，魯棒性好的MOEA架構對于解決基礎MOP也是至關重要的。正常的MOEA通常直接應用于或稍加修改用以解決DMOP，例如非支配的、排序遺傳算法II（NSGA-II）、MOEA / D 和基于規則模型的多目标估計分布算法（RM-MEDA）。因為動态變化可能會降低收斂速度或導緻多樣性損失，是以在解決靜态MOP時，主幹MOEA應該能夠實作快速收斂并保持良好的分布。故DMOEA中的不同組成在解決DMOP的不同方面都起作用。故本文嘗試在MOEA / D架構内将記憶體和預測政策進行混合，以利用每個組成部分來提高DMOP的解的品質。

Proposed algorithm算法提出部分

MOEA/D-HMPS的整體架構

初始化種群P，歸檔集D存儲所有探測個體在t時刻每一維目标上的均值，歸檔集C存儲曆史時刻内種群的中心，歸檔集D和C都初始化為空，且在進化搜尋過程中由所提出的記憶政策更新。在算法１中，flag标志着目前環境變化是否與曆史環境變化相似，index代表歸檔集D和C中相似環境所在的位置索引。 F ‾ t + 1 \overline{F}_{t+1} Ft+1​記錄着t+1時刻探測個體的均值。一旦檢測到環境變化，MOEA/D-HMPS能夠通過比較 F ‾ t + 1 \overline{F}_{t+1} Ft+1​裡的值和歸檔集D裡的值來确定目前變化是否與曆史變化相似。flag,index相應地被更新，算法啟動環境響應機制，根據目前變化是否相似于曆史變化做出不同反應，生成新種群。如果沒有檢測到環境變化，則采用基本的MOEA/D-DE優化t時刻的靜态MOP。

1）環境檢測

​ 本文采用固定的探測個體方法，這些探測個體從決策空間随機産生并且在每一代保持固定的值。假設在無噪聲幹擾的情況下，每一代都重新評價探測個體的目标函數值，并與之前存儲的目标值比較，如果發生不比對則說明發生了環境變化。

2）識别變化類型

​ 一般來說，如果兩個時刻追蹤到的PS和PF相同，那就意味着這兩個動态環境是相似的，意味着下一次相似環境中可以重複利用這些最優解，因而能夠提高收斂性能。

​ 算法2中， F ‾ c \overline F_c Fc​表示目前環境下探測個體的目标值，詳細介紹了歸檔集D與 F ‾ c \overline F_c Fc​比較的函數時如何實作的。 ϵ \epsilon ϵ是預先設定的門檻值，用以判定前後變化中探測個體每一維目标上的值是否差不多一樣，進而最終傳回位置索引index和布爾值flag。

3）記憶政策

​ 記憶池中存儲非支配解或者目前種群中的最優解，并被重新用于接下來相似環境中。但這樣的政策仍有局限性，一方面這些曆史非支配解在環境變化之後可能不再是非支配解，另一方面這些存儲起來的最優解或資訊沒有得到充分且有效的重新利用。是以上文提出的識别變化類型能夠讓存儲的最優解得到更有效的重用，另外現有最優種群的中心被存儲起來，成為曆史最優資訊。

​ 存儲的曆史資訊很明顯就是兩方面： F ‾ t \overline F_t Ft​表示t時刻探測個體的目标值，用以判斷目前時刻的環境變化是否同以往的曆史變化相似，進而友善最優解的重用； C ‾ t \overline C_t Ct​代表t時刻種群的中心，一旦發現目前變化同以往變化相同，那麼存儲的種群中心就會在新環境中引導個體進化和收斂。

​ 歸檔集的存儲與更新過程用以下三張圖表示：

圖一：檢測到第一次變化時，将 F ‾ 1 \overline F_1 F1​和 C 1 C_1 C1​存儲起來；

圖二：如果檢測到第k次變化發現并未相似于之前任何一次變化，則将 F ‾ k \overline F_k Fk​和 C k C_k Ck​存儲起來：

圖三：如果檢測到第k次變化相似于之前某次變化，以第二次為例，則

用 F ‾ k \overline F_k Fk​和 C k C_k Ck​替代 F ‾ 2 \overline F_2 F2​和 C 2 C_2 C2​；

​ 這種存儲方式有兩方面的優點：簡約的存儲使得歸檔集中不存在相似變化的資訊；另外即使兩次變化極為相似，記憶池中存儲和記錄的是最新一次變化産生的資訊；而且當兩個歸檔集大小超過預設空間時，對其應用先入先出的原則，避免額外占用資源空間；

4）環境響應

​ 針對不與任何一次曆史變化相似的環境變化，采用差異性預測政策；傳統的預測方式僅僅利用前後連續時刻内的中心點做文章，而為了防止環境發生的變化無規則或者比較急劇，本文所提的MOEA/D-HMPS引進了一部分現有種群的個體和随機個體來避免可能産生的預測誤差；值得注意的是，第一次發生變化時，歸檔集D和C是空集，故此時新環境中一半的個體來自現有種群中排序最優的個體，一半的個體以随機的方式産生。

x t + 1 k = x t k + C r k − C t − 1 k + G a u s s i a n ( 0 , d ) x_{t+1}^k=x_{t}^k+C_{r}^k-C_{t-1}^k+Gaussian(0,d) xt+1k​=xtk​+Crk​−Ct−1k​+Gaussian(0,d)

其中 x t + 1 k x_{t+1}^k xt+1k​, x t k x_{t}^k xtk​, x t − 1 k x_{t-1}^k xt−1k​分别 代表t+1、t、t-1時刻種群中心個體第k維決策變量；Gaussian(0,d)表示均值為0，标準差為d的高斯擾動，其中标準差d定義如下：

d = ∣ ∣ C t − C t − 1 ∣ ∣ n d=\frac{||C_t-C_{t-1}||}{n} d=n∣∣Ct​−Ct−1​∣∣​

其中 ∥ C t − C t − 1 ∥ \|C_t-C_{t-1}\| ∥Ct​−Ct−1​∥表示 C t , C t − 1 C_t,C_{t-1} Ct​,Ct−1​之間的歐式距離；

該預測機制用圖示表示如下：

其中黑色的圓圈代表一個個體，曲線上的一系列黑色圓圈代表種群中個體的分布性，紅點代表種群的中心點，黑色實心箭頭代表前兩個時刻的種群移動方向，也是兩個中心點的向量差。藍色虛線箭頭代表預測的種群進化方向，t時刻的現有個體和種群預測的進化方向一起用以重新定位t+1時刻的最優個體。由于這種預測方法并不要求精準預測，是以加了高斯擾動增強種群的搜尋開采能力。

​ 針對檢測到的變化同過去某次環境變化相似的情況，則響應記憶機制，即在新環境中重用之前那次變化中最優解的資訊，圖示如下：

算法調用相似函數得到相似變化所在索引，重用那次變化的種群中心點 C i n d e x C_{index} Cindex​和t時刻的種群中心點 C t C_t Ct​的向量差預測種群進化方向，結合t時刻的種群個體，進而産生t+1時刻的新種群。用公式表示如下：

x t + 1 k = x t k + C i n d e x k − C t k x_{t+1}^k=x_t^k+C_{index}^k-C_t^k xt+1k​=xtk​+Cindexk​−Ctk​

有關環境響應的整體算法表示如下：

​ 首先計算t時刻種群P的中心點 C t C_t Ct​，并按找适應度值對種群 P t P_t Pt​進行排序，對于每一維目标都進行如下操作：如果該個體排在前1/2，則判斷flag是否為真，若為真，啟用預測響應機制并通過相應的公式得到新的初始化種群 P t + 1 P_{t+1} Pt+1​；若flag為假，則啟用記憶響應機制并通過此時的對應公式同樣求得 P t + 1 P_{t+1} Pt+1​。再采用輪盤賭機制，門檻值設為0.5，若随機數小于0.5，則該個體來自決策空間的随機産生，否則将重用現有個體。最終用 C t C_t Ct​替代 C t − 1 C_{t-1} Ct−1​，将 P t + 1 P_{t+1} Pt+1​作為傳回值輸出。

5）基本的多目标進化算法

​ 本文采用的是MOEA/D-DE，目前由于其解決連續MOPs時不僅收斂快而且能保持不錯的分布性，已經被廣泛用于動态多目标優化領域。MOEA / D将問題分解為多個子問題，并根據相鄰關系同時優化它們。相鄰關系的定義基于目标空間權重向量間的距離，每個個體的适應度值就是聚合函數，這裡采用經典的切比雪夫方法作為聚合方式，因為該方案既簡單，又具有很好的表現性能。

結語

​ 以上即為《Hybrid of memory and prediction strategies for dynamic multiobjective optimization》的摘要、Introduction及算法提出部分的展示。

​ 這之後10頁篇幅的内容就是實驗設計、實驗結果及讨論、總結與未來工作展望，圖表居多，測試問題及評價标準在之前的閱讀筆記中有記錄，在此不做說明。