基于密度和記憶的動態(tài)多目標(biāo)優(yōu)化算法

王曉冬，栗三一

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

1 引言

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

為了解決這個問題，研究人員提出了兩類種群初始化方法：基于預(yù)測的方法和基于記憶的方法?；陬A(yù)測的動態(tài)多目標(biāo)優(yōu)化算法(DMOAs)在環(huán)境發(fā)生變化時，根據(jù)之前獲得的帕累托解(POS)預(yù)測環(huán)境變化后的POS?；陬A(yù)測的DMOAs可以有效地解決環(huán)境變化平緩或有規(guī)律的DMOPs。然而，當(dāng)環(huán)境變化劇烈且不穩(wěn)定時，預(yù)測精度難以保證。無人駕駛過程中需要根據(jù)路況實(shí)時優(yōu)化行車路線，當(dāng)遇到復(fù)雜的路況時基于預(yù)測的方法無法有效及時的確定最優(yōu)路線。

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

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

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

1)基于記憶的種群初始化方法的一個難點(diǎn)是如何判斷環(huán)境與記憶的匹配關(guān)系。本文提出環(huán)境變量的定義并對如何設(shè)定環(huán)境變量進(jìn)行了描述，根據(jù)環(huán)境變量可以準(zhǔn)確判斷環(huán)境與記憶池中記憶的匹配關(guān)系。

2)現(xiàn)有的基于記憶的DMOA只記錄一個解或?qū)⑺蟹侵浣庾鳛橛洃?。NSGA2-DM將中心解和交界解記錄為記憶，其包含了解集的分布信息并且不占用很大的存儲空間。例如，雙目標(biāo)優(yōu)化問題一條記憶記錄三個解，三目標(biāo)優(yōu)化問題記錄四個解。

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

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

通過基準(zhǔn)測試函數(shù)驗(yàn)證MSGA2-DM算法的有效性，并將MSGA2-DM的結(jié)果與兩種基于記憶的DMOA、兩種基于預(yù)測的DMOA和兩種局部搜索NSGA2算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明NSGA2-DM算法可以根據(jù)環(huán)境變化快速跟蹤變化的帕累托前沿，當(dāng)種群初始化方法相同時，基于密度的局部搜索搜索策略結(jié)果優(yōu)于所對比局部搜索方法。

2 動態(tài)多目標(biāo)優(yōu)化問題

一個DMOP可表述如下：

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

(1)

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

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

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

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

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

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

3 NSGA2-DM的設(shè)計(jì)與分析

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

為了復(fù)用過去的信息來初始化種群，需要構(gòu)建一個記憶池來存儲具有代表性的解和相應(yīng)的環(huán)境變量值。環(huán)境變量的設(shè)置原則是：對于一個DMOP，具有相同環(huán)境變量值的系統(tǒng)可視為相同的靜態(tài)系統(tǒng)。換句話說，具有相同環(huán)境變量值的DMOP具有相同的POS和POF。

對于式(1)表示的動態(tài)多目標(biāo)優(yōu)化問題可以將環(huán)境向量設(shè)置為

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

(2)

根據(jù)環(huán)境向量可以判斷環(huán)境是否發(fā)生變化，并且可以判斷新的環(huán)境是否在記憶池中有對應(yīng)的記憶。設(shè)上一時刻的環(huán)境向量值為，當(dāng)前環(huán)境向量值為，則當(dāng)不等式(3)成立時環(huán)境發(fā)生改變。

(3)

假設(shè)環(huán)境已經(jīng)發(fā)生改變且當(dāng)前環(huán)境向量值為，記憶庫中共有條記憶，其對應(yīng)的環(huán)境向量值為(，，…，)，為與記憶庫中環(huán)境向量值的歐氏距離，若

(4)

則新環(huán)境與記憶庫中第條記憶對應(yīng)的環(huán)境相近，否則記憶池中沒有對應(yīng)新環(huán)境的記憶。

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

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

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

(5)

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

(6)

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

(7)

其中，是記憶中的解；是第個初始解；是目標(biāo)向量的維數(shù)；是決策向量的維數(shù)；是初始種群規(guī)模；是0到1之間的隨機(jī)值?；谟洃浀姆N群初始化過程如下所示(過程1)。

0) If 環(huán)境變量值發(fā)生變化.

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

2)更新現(xiàn)有記憶。

3) else

4)形成新的記憶。

5) end if

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

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

8) else

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

10) end if

11) end if

3.2 稀疏度計(jì)算

假設(shè)初始種群規(guī)模為。首先，對目標(biāo)函數(shù)值進(jìn)行歸一化處理。假設(shè)第個解的目標(biāo)向量值為()=(()，…，())，歸一化公式為

(8)

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

(9)

其中是目標(biāo)空間中與歐氏距離小于的解的個數(shù)。本文將設(shè)為01。

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

備注2：值可以介于0和1之間。但是當(dāng)值太大或太小時都不能準(zhǔn)確反映解的稀疏度?？梢宰龈嗟膶?shí)驗(yàn)來確定最合適的值。由于文章篇幅有限，本文實(shí)驗(yàn)根據(jù)經(jīng)驗(yàn)將值設(shè)置為01。

3.3 局部搜索NSGA2算法

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

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

極限優(yōu)化策略具有強(qiáng)大的微調(diào)能力。但是極限搜索的搜索范圍較小，當(dāng)非支配解遠(yuǎn)離POS時收斂速度較慢。為了提高收斂速度，NSGA2-DM同時采用隨機(jī)局部搜索策略。隨機(jī)局部搜索策略產(chǎn)生的局部解的個數(shù)為0.2N(向下舍入)。局部搜索解產(chǎn)生公式為：

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

(10)

′=+(-)

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

(11)

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

3.4 NSGA2-DM的主要過程

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

步驟1：如果到環(huán)境檢測周期則計(jì)算環(huán)境變量值。如果滿足式(3)，則環(huán)境發(fā)生改變，轉(zhuǎn)至步驟2，否則環(huán)境未發(fā)生改變，轉(zhuǎn)至步驟3。

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

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

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

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

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

步驟7：將，和合并形成種群?；诜侵渑判蚝蛽頂D距離排序從中選擇個個體。該個個體形成種群并設(shè)置=。

步驟8：如果達(dá)到環(huán)境檢測周期則轉(zhuǎn)到步驟1。否則，如果達(dá)到最大迭代次數(shù)，轉(zhuǎn)到步驟9。否則，重復(fù)步驟7。

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

4 測試問題和性能指標(biāo)

4.1 測試問題

本文所用的測試問題為標(biāo)準(zhǔn)測試問題dMOP1、dMOP2、FDA1、FDA4和FDA5。dMOP1和dMOP2是雙目標(biāo)動態(tài)優(yōu)化問題。dMOP1的POS固定不變而POF隨時間變化；dMOP2的POS和POF均隨時間變化。FDA1是POS隨時間變化而POF固定的雙目標(biāo)動態(tài)優(yōu)化問題；FDA4是POS變化而POF固定的三目標(biāo)優(yōu)化問題；FDA5是POS和POF都隨時間變化的三目標(biāo)優(yōu)化問題。所有問題的決策變量個數(shù)為20，決策變量的取值范圍為0到1，變化幅度參數(shù)=10。

4.2 性能指標(biāo)

Helbig等總結(jié)了一些動態(tài)多目標(biāo)優(yōu)化算法的評價指標(biāo)。首先介紹靜態(tài)多目標(biāo)優(yōu)化的反向世代距離(IGD)指標(biāo)，然后將其擴(kuò)展到動態(tài)問題上形成平均IGD指標(biāo)(MIGD)。

假設(shè)*是一組在POF中均勻分布的Pareto最優(yōu)解。是POF附近的一組解。IGD定義為

(12)

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

(13)

其中是一組連續(xù)的時間點(diǎn)，||是中時間點(diǎn)的個數(shù)。

在本文實(shí)驗(yàn)中，從雙目標(biāo)問題和三目標(biāo)問題的POF上分別選取1000點(diǎn)和2500點(diǎn)作為P。

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

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

問題和算法參數(shù)設(shè)置如下：

1)雙目標(biāo)問題系統(tǒng)每10秒更改一次，三目標(biāo)問題系統(tǒng)每30秒更改一次，即雙目標(biāo)問題的t值每10秒增加1，三目標(biāo)問題的t值每30秒增加1。所有實(shí)驗(yàn)的環(huán)境檢測周期t設(shè)定為10秒。

2)所有問題的初始種群規(guī)模設(shè)定為100。

3)環(huán)境變化后最大迭代次數(shù)Imax設(shè)為雙目標(biāo)問題30次，三目標(biāo)問題50次。

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

5)所有實(shí)驗(yàn)的環(huán)境變量設(shè)置為環(huán)境變量設(shè)置為=sin(05π+π2)。所有實(shí)驗(yàn)的環(huán)境變化閾值設(shè)定為001。

6)當(dāng)≥100時，算法停止。

5.2 不同動態(tài)優(yōu)化算法的結(jié)果對比

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

連續(xù)20次實(shí)驗(yàn)的MIGD統(tǒng)計(jì)結(jié)果見表1。結(jié)果顯示，NSGA2-DM的性能優(yōu)于A1，這意味著所提出的MPI方法比只在一個記憶中記錄一個解的MPI方法包含更多有用的信息。對于dMOP1問題，A4達(dá)到最低的MIGD值，而在40

實(shí)驗(yàn)結(jié)果表明，與PPI算法相比，本文提出的種群初始化方法在記憶池完備的情況下可以達(dá)到更好的結(jié)果。但在算法運(yùn)行初期，記憶池中的記憶很少，無法有效指導(dǎo)種群初始化，這是基于記憶的初始化方法的一個不足，可以將PPI與MPI進(jìn)行優(yōu)勢互補(bǔ)解決這個問題。

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

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

連續(xù)20次實(shí)驗(yàn)的MIGD統(tǒng)計(jì)結(jié)果見表2。由表2可知，當(dāng)0

實(shí)驗(yàn)結(jié)果表明，當(dāng)環(huán)境變化比較快時，本文提出的基于密度的局部搜索策略的性能優(yōu)于所對比的局部搜索策略。這些所對比的局部搜索策略性能較差的主要原因是它們的計(jì)算量太大，沒有足夠的時間來獲得較好的解。所以本文提出的NSGA2-DM算法適用于環(huán)境變化較快的動態(tài)多目標(biāo)優(yōu)化問題，而當(dāng)環(huán)境變化緩慢時則適合采用計(jì)算量大但精度高的算法。

表1 基準(zhǔn)測試問題中各算法MIGD指標(biāo)的統(tǒng)計(jì)結(jié)果

表2 準(zhǔn)測試問題中不同局部搜索策略的MIGD統(tǒng)計(jì)結(jié)果