基于密度和記憶的動態多目標優化算法

王曉冬，栗三一

(1. 鄭州科技學院，河南鄭州450064； 2. 鄭州輕工業大學，河南鄭州450002)

1 引言

很多實際的多目標優化問題(MOPs)會隨著時間發生變化，稱之為動態多目標優化問題(DMOPs)。對于隨環境變化較慢的MOPs，人們往往在環境變化時隨機重新初始化種群，并用靜態多目標優化算法求解。然而，對于無人駕駛的路徑規劃過程中，由于環境因素變化迅速，靜態多目標優化算法無法快速追蹤帕累托前沿，很難求得高質量的解，從而制約了該技術的應用。

為了解決這個問題，研究人員提出了兩類種群初始化方法：基于預測的方法和基于記憶的方法。基于預測的動態多目標優化算法(DMOAs)在環境發生變化時，根據之前獲得的帕累托解(POS)預測環境變化后的POS。基于預測的DMOAs可以有效地解決環境變化平緩或有規律的DMOPs。然而，當環境變化劇烈且不穩定時，預測精度難以保證。無人駕駛過程中需要根據路況實時優化行車路線，當遇到復雜的路況時基于預測的方法無法有效及時的確定最優路線。

與基于預測的DMOAs相比，基于記憶的DMOAs不受環境變化劇烈程度的影響。基于記憶的種群初始化方法建立一個記憶池存儲之前獲得的解，利用記憶池中的解指導新環境下的種群初始化。在算法運行一段時間，記憶庫豐富之后，基于記憶的DMOAs有令人滿意的效果，在無人駕駛過程中，當遇到相似的路況時可以根據歷史經驗提供較合理的備選路線，從而快速確定最優路線。但該方法容易導致解喪失多樣性。

當環境變化間隔很長時，可以采用局部搜索策略來解決DMOAs中解的多樣性丟失問題。局部搜索機制可以有效地增加種群多樣性，避免陷入局部最優，但在局部搜索過程中需要大量的計算。因此，當DMOPs的環境變化較快時，現有局部搜索策略效果并不理想。

為了減少局部搜索過程的計算量，本文提出了一種基于密度的局部搜索策略，并將其應用于基于記憶的DMOA中，稱為基于密度和記憶的NSGA2算法(NSGA2-DM)。NSGA2-DM建立了一個記憶池來存儲代表性的解和相應的環境信息。當遇到相似或相同的環境時，將根據記憶池生成初始種群。在遺傳過程中，NSGA2-DM用目標空間中每個解的密度來評價每個非支配解的稀疏度，并將稀疏度最小的非支配解定義為稀疏解。在每個遺傳過程中，NSGA2-DM只在稀疏解的周圍進行局部搜索。NSGA2-DM同時采用極限優化局部搜索策略和隨機局部搜索策略，提高了解的質量和收斂速度。算法的最終目標是在快速變化的環境中獲得多樣性良好和質量高的非支配解。本文的主要技術貢獻可歸納如下：

1)基于記憶的種群初始化方法的一個難點是如何判斷環境與記憶的匹配關系。本文提出環境變量的定義并對如何設定環境變量進行了描述，根據環境變量可以準確判斷環境與記憶池中記憶的匹配關系。

2)現有的基于記憶的DMOA只記錄一個解或將所有非支配解作為記憶。NSGA2-DM將中心解和交界解記錄為記憶，其包含了解集的分布信息并且不占用很大的存儲空間。例如，雙目標優化問題一條記憶記錄三個解，三目標優化問題記錄四個解。

3) NSGA2-DM每代都在稀疏解周圍進行局部搜索。當非支配解不均勻分布時，該策略使解均勻分布。當解分布均勻時，交界解的稀疏度最小，這意味著NSGA2-DM將圍繞交界解進行搜索，以擴大解的范圍。因此，NSGA2-DM可以保證解的多樣性。

4)現有的局部搜索策略都是圍繞所有解進行搜索，并且每一代都會產生大量的局部解，導致計算量大。NSGA2-DM只圍繞稀疏解進行搜索，因此計算量小于其它局部搜索策略。

通過基準測試函數驗證MSGA2-DM算法的有效性，并將MSGA2-DM的結果與兩種基于記憶的DMOA、兩種基于預測的DMOA和兩種局部搜索NSGA2算法進行比較，實驗結果表明NSGA2-DM算法可以根據環境變化快速跟蹤變化的帕累托前沿，當種群初始化方法相同時，基于密度的局部搜索搜索策略結果優于所對比局部搜索方法。

2 動態多目標優化問題

一個DMOP可表述如下：

=(，，…，)，≤≤，=1，2，…，

(1)

其中=0，1，2，…∈表示瞬時時間；(，)∈為維目標向量，由個時變目標函數組成；∈為維決策向量；和分別是第個決策變量的下限和上限；()為目標函數中的時變參數，為目標函數中時變參數的個數，一旦時間變量固定，則()為常數。DMOP基本上可以分為四類：

第一類：帕累托最優解集(POS)和帕累托最優前沿(POF)都保持不變。

第二類：POS和POF均隨時間變化。

第三類：POS改變，POF不變。

第四類：POS保持不變，但POF發生變化。

第一類可以作為靜態MOPs求解，后三種類型由于目標的變化增大了優化難度，因此主要研究后三種類型的DMOPs。DMOAs的目標是跟蹤動態的POS(POF)。

3 NSGA2-DM的設計與分析

3.1 基于記憶的種群初始化(MPI)

為了復用過去的信息來初始化種群，需要構建一個記憶池來存儲具有代表性的解和相應的環境變量值。環境變量的設置原則是：對于一個DMOP，具有相同環境變量值的系統可視為相同的靜態系統。換句話說，具有相同環境變量值的DMOP具有相同的POS和POF。

對于式(1)表示的動態多目標優化問題可以將環境向量設置為

=(()，()…，())

(2)

根據環境向量可以判斷環境是否發生變化，并且可以判斷新的環境是否在記憶池中有對應的記憶。設上一時刻的環境向量值為，當前環境向量值為，則當不等式(3)成立時環境發生改變。

(3)

假設環境已經發生改變且當前環境向量值為，記憶庫中共有條記憶，其對應的環境向量值為(，，…，)，為與記憶庫中環境向量值的歐氏距離，若

(4)

則新環境與記憶庫中第條記憶對應的環境相近，否則記憶池中沒有對應新環境的記憶。

若環境發生了改變，變化前環境變量若在記憶池中有對應的記憶則更新該記憶，否則生成新的記憶。每條記憶中包含中心解、交界解和對應的環境變量值。中心解是所有非支配解的平均值，交界解至少在一個目標變量上具有最大值。

記錄記憶后，如果新的環境變量值與記憶池中的記憶不一致，則隨機初始化種群。否則，將對應記憶中的解加入初始種群，初始種群中其余解隨機初始化，初始化方法為：

=(，1，，2，…，，) (=1，…，+1)

(5)

=(，1…，，，…，，)=1，2，…，(--1)

(6)

，=(-)+=1，2，…，

(7)

其中，是記憶中的解；是第個初始解；是目標向量的維數；是決策向量的維數；是初始種群規模；是0到1之間的隨機值。基于記憶的種群初始化過程如下所示(過程1)。

0) If 環境變量值發生變化.

1) If 前一時刻的環境變量值與記憶池中的一條記憶相匹配.

2)更新現有記憶。

3) else

4)形成新的記憶。

5) end if

6) If 新環境變量值與記憶池中的一條記憶相匹配.

7)將記憶中的解加入初始種群，根據等式(2)得到其它解.

8) else

9)隨機生成所有初始解。

10) end if

11) end if

3.2 稀疏度計算

假設初始種群規模為。首先，對目標函數值進行歸一化處理。假設第個解的目標向量值為()=(()，…，())，歸一化公式為

(8)

其中min和max分別是第個目標變量的最小值和最大值。則的稀疏度計算公式為

(9)

其中是目標空間中與歐氏距離小于的解的個數。本文將設為01。

備注1：不需要計算()與所有其它目標向量之間的歐幾里德距離。只有當所有個目標方向上的距離都小于01，才需要計算其與()的歐氏距離。

備注2：值可以介于0和1之間。但是當值太大或太小時都不能準確反映解的稀疏度。可以做更多的實驗來確定最合適的值。由于文章篇幅有限，本文實驗根據經驗將值設置為01。

3.3 局部搜索NSGA2算法

NSGA2-DM將稀疏度最小的解設置為稀疏解。然后圍繞稀疏解進行局部搜索。當非支配解分布不均勻時，該策略提高解的均勻性。當解分布均勻時，它會圍繞交界解進行搜索，以擴大解的范圍(因為當解分布均勻時，交界點上的解密度更稀疏)。因此，這一策略可以保證種群的多樣性。

NSGA2-DM同時采用極限優化局部搜索策略和隨機搜索策略生成局部解。在極限優化階段，每一個生成的局部解只有一個決策變量值與稀疏解不同，在靠近帕累托前沿時可以有效提高解的精度。

極限優化策略具有強大的微調能力。但是極限搜索的搜索范圍較小，當非支配解遠離POS時收斂速度較慢。為了提高收斂速度，NSGA2-DM同時采用隨機局部搜索策略。隨機局部搜索策略產生的局部解的個數為0.2N(向下舍入)。局部搜索解產生公式為：

(=1，2，…，「02?)

(10)

′=+(-)

(=1，2，…，)(-02<<02)

(11)

其中是介于-02和02之間的隨機值。為了保持種群的多樣性，隨機生成01個解。本部分生成解的總數為+「03?。

3.4 NSGA2-DM的主要過程

根據實際問題設置參數：種群規模；環境變化后最大迭代次數；決策變量個數；決策變量下界與上界=(，，…，)，=(，，…，)；目標函數個數；形狀參數；交叉率；變異率；交叉參數；變異參數；環境變量；環境變化閾值；環境檢測周期。2-的主要過程如下所示(過程2)。

步驟1：如果到環境檢測周期則計算環境變量值。如果滿足式(3)，則環境發生改變，轉至步驟2，否則環境未發生改變，轉至步驟3。

步驟2：根據過程1更新記憶并初始化種群。假設初始種群為={，，…，}，其中=(1，2，…，)，=1，2，…，。

步驟3：計算中各解的適應度值和擁擠距離(與原2相同，本文不介紹具體過程)。所有非支配解記為種群。

步驟4：根據原2中的交叉和突變策略生成子代。

步驟5：根據式(9)計算種群中所有解的稀疏度。將稀疏度最小的解設置為稀疏解。

步驟6：局部搜索生成+「03?個解，形成種群。

步驟7：將，和合并形成種群。基于非支配排序和擁擠距離排序從中選擇個個體。該個個體形成種群并設置=。

步驟8：如果達到環境檢測周期則轉到步驟1。否則，如果達到最大迭代次數，轉到步驟9。否則，重復步驟7。

步驟9：中的非支配解是目前為止找到的最佳解，等待達到環境檢測周期再次進行計算。

4 測試問題和性能指標

4.1 測試問題

本文所用的測試問題為標準測試問題dMOP1、dMOP2、FDA1、FDA4和FDA5。dMOP1和dMOP2是雙目標動態優化問題。dMOP1的POS固定不變而POF隨時間變化；dMOP2的POS和POF均隨時間變化。FDA1是POS隨時間變化而POF固定的雙目標動態優化問題；FDA4是POS變化而POF固定的三目標優化問題；FDA5是POS和POF都隨時間變化的三目標優化問題。所有問題的決策變量個數為20，決策變量的取值范圍為0到1，變化幅度參數=10。

4.2 性能指標

Helbig等總結了一些動態多目標優化算法的評價指標。首先介紹靜態多目標優化的反向世代距離(IGD)指標，然后將其擴展到動態問題上形成平均IGD指標(MIGD)。

假設*是一組在POF中均勻分布的Pareto最優解。是POF附近的一組解。IGD定義為

(12)

MIGD被定義為DMOP在一段時間中的IGD平均值，計算公式如下

(13)

其中是一組連續的時間點，||是中時間點的個數。

在本文實驗中，從雙目標問題和三目標問題的POF上分別選取1000點和2500點作為P。

5 實驗結果及分析

5.1 參數設置

問題和算法參數設置如下：

1)雙目標問題系統每10秒更改一次，三目標問題系統每30秒更改一次，即雙目標問題的t值每10秒增加1，三目標問題的t值每30秒增加1。所有實驗的環境檢測周期t設定為10秒。

2)所有問題的初始種群規模設定為100。

3)環境變化后最大迭代次數Imax設為雙目標問題30次，三目標問題50次。

4)所有實驗中交叉率設置為90%，突變率設置為1/n；交叉參數和變異參數均設置為20。

5)所有實驗的環境變量設置為環境變量設置為=sin(05π+π2)。所有實驗的環境變化閾值設定為001。

6)當≥100時，算法停止。

5.2 不同動態優化算法的結果對比

本實驗將所提出的基于密度的局部搜索算法與不同的種群初始化方法相結合來解決基準問題。比較的算法包括：①文獻[5]中提出的MPI方法(表示為A1)；②文獻[6]中提出的MPI方法(表示為A2)；③文獻[7]中提出的基于預測的種群初始化方法(PPI)(表示為A3)；④文獻[8]中提出的PPI方法(表示為A4)。當環境變化時，A1方法記錄上一時刻的一部分特征解，其余解隨機生成。A2方法只是在記憶中記錄一個中心解。A3和A4建立了兩種預測模型來預測環境變化時的解。

連續20次實驗的MIGD統計結果見表1。結果顯示，NSGA2-DM的性能優于A1，這意味著所提出的MPI方法比只在一個記憶中記錄一個解的MPI方法包含更多有用的信息。對于dMOP1問題，A4達到最低的MIGD值，而在40

實驗結果表明，與PPI算法相比，本文提出的種群初始化方法在記憶池完備的情況下可以達到更好的結果。但在算法運行初期，記憶池中的記憶很少，無法有效指導種群初始化，這是基于記憶的初始化方法的一個不足，可以將PPI與MPI進行優勢互補解決這個問題。

5.3 不同局部搜索策略之間的對比

為了驗證所提出的基于密度的局部搜索算法的有效性，將本文提出的MPI方法與不同的局部搜索策略相結合來解決一些基準問題。比較的進化算法包括NSGA2、NSGA2-MOEA和NSGA2-els。

連續20次實驗的MIGD統計結果見表2。由表2可知，當0

實驗結果表明，當環境變化比較快時，本文提出的基于密度的局部搜索策略的性能優于所對比的局部搜索策略。這些所對比的局部搜索策略性能較差的主要原因是它們的計算量太大，沒有足夠的時間來獲得較好的解。所以本文提出的NSGA2-DM算法適用于環境變化較快的動態多目標優化問題，而當環境變化緩慢時則適合采用計算量大但精度高的算法。

表1 基準測試問題中各算法MIGD指標的統計結果

表2 準測試問題中不同局部搜索策略的MIGD統計結果