基于新評價指標(biāo)自適應(yīng)預(yù)測的動態(tài)多目標(biāo)優(yōu)化算法

李二超，張生輝

基于新評價指標(biāo)自適應(yīng)預(yù)測的動態(tài)多目標(biāo)優(yōu)化算法

李二超*，張生輝

（蘭州理工大學(xué) 電氣工程與信息工程學(xué)院，蘭州 730050）（ ? 通信作者電子郵箱lecstarr@163.com）

現(xiàn)實生活中的多目標(biāo)優(yōu)化問題（MOP）大多為動態(tài)多目標(biāo)優(yōu)化問題（DMOP），此類問題的目標(biāo)函數(shù)、約束條件和決策變量都可能隨時間的變化而發(fā)生改變，這需要算法在環(huán)境變化后快速適應(yīng)新的環(huán)境，且在保證Pareto解集多樣性的同時快速收斂到新的Pareto前沿。針對此問題，提出一種基于新評價指標(biāo)自適應(yīng)預(yù)測的動態(tài)多目標(biāo)優(yōu)化算法（NEI-APDMOA）。首先，在種群非支配排序過程中提出一種優(yōu)于擁擠度的新評價指標(biāo)，并分階段平衡收斂快速性和種群多樣性，使種群的收斂過程更加合理；其次，提出一種可判斷環(huán)境變化強(qiáng)弱的因子，為預(yù)測階段提供有價值信息，并引導(dǎo)種群更好地適應(yīng)環(huán)境變化；最后，根據(jù)環(huán)境變化因子匹配3種更加合理的預(yù)測策略，使種群快速響應(yīng)環(huán)境變化。將NEI-APDMOA與DNSGA-Ⅱ-A（Dynamic Non-dominated Sorting Genetic Algorithm-Ⅱ-A）、DNSGA-Ⅱ-B（Dynamic Non-dominated Sorting Genetic Algorithm-Ⅱ-B）和PPS（Population Prediction Strategy）算法在9個標(biāo)準(zhǔn)動態(tài)測試函數(shù)上進(jìn)行對比。實驗結(jié)果表明，NEI-APDMOA分別在9、4和8個測試函數(shù)上取得了最優(yōu)的平均反世代距離（IGD）值、平均間距（SP）值和平均世代距離（GD）值，可以更快地響應(yīng)環(huán)境變化。

動態(tài)多目標(biāo)優(yōu)化；進(jìn)化算法；評價指標(biāo)；非支配排序；預(yù)測策略

0 引言

很多問題都可以抽象化為具有多個相互沖突目標(biāo)的多目標(biāo)優(yōu)化問題（Multi-objective Optimization Problem，MOP）［1］，現(xiàn)實生活中多目標(biāo)優(yōu)化問題本質(zhì)上是動態(tài)的，動態(tài)多目標(biāo)優(yōu)化問題（Dynamic Multi-objective Optimization Problem， DMOP）［2］的目標(biāo)函數(shù)、約束條件和決策變量都會隨時間（環(huán)境）動態(tài)變化，它的最優(yōu)解集也會隨時間（環(huán)境）而動態(tài)變化。解決DMOP要求算法在環(huán)境變化后最大限度地跟蹤近似Pareto最優(yōu)解集（Pareto optimal Solution set， PS）和Pareto前沿（Pareto optimal Front， PF），而不是僅求解單一的最優(yōu)值或 Pareto最優(yōu)解。因此，動態(tài)多目標(biāo)優(yōu)化算法需要在傳統(tǒng)靜態(tài)多目標(biāo)算法上作出調(diào)整和改進(jìn)。

近年來，在提高自主進(jìn)化能力從而更好地尋找最優(yōu)解和解決動態(tài)優(yōu)化問題中種群快速適應(yīng)環(huán)境能力方面，研究者們提出了許多適應(yīng)DMOP的動態(tài)多目標(biāo)優(yōu)化算法［3-7］，一些學(xué)者將記憶策略和預(yù)測策略引入動態(tài)多目標(biāo)優(yōu)化算法解決此類問題。記憶策略利用先前搜索的最優(yōu)解加快收斂進(jìn)程，提高收斂速度。Sahmoud等［8］提出一種包含搜索種群和主種群的算法，搜索種群隨環(huán)境變化重新初始化，并更新非支配記憶池，在記憶池和主種群中選擇初始種群。Jiang等［9］結(jié)合記憶策略和流形遷移學(xué)習(xí)方法，提出基于流形的動態(tài)多目標(biāo)優(yōu)化算法，根據(jù)歷史信息建立流形空間的遷移模型，生成新環(huán)境下的初始種群。預(yù)測策略在每次環(huán)境變化后指導(dǎo)種群進(jìn)化，為種群進(jìn)化提供引導(dǎo)方向，預(yù)測種群快速響應(yīng)新變化。Cao等［10］提出了一種基于支持向量回歸（Support Vector Regression， SVR）的方法生成新環(huán)境的初始種群，每個子問題都可以在不同的環(huán)境中獲得它相應(yīng)的解，以形成時間序列。Rong等［11］根據(jù)問題特性變化類型提出一種多模型預(yù)測方法，對平移、旋轉(zhuǎn)和復(fù)合三類問題變化針對性響應(yīng)。Wang等［12］提出一種灰色預(yù)測模型預(yù)測新環(huán)境下初始種群，有效提高了種群收斂性，但算法過于依賴預(yù)測模型和數(shù)據(jù)?；跈C(jī)器學(xué)習(xí)策略對新環(huán)境下種群初始化，與融合多種變化響應(yīng)的混合策略發(fā)揮協(xié)同效應(yīng)，為解決動態(tài)多目標(biāo)問題提供新的思路。Zhao等［13］提出一種新的知識學(xué)習(xí)策略，通過學(xué)習(xí)先前搜索經(jīng)驗提高收斂速度。Gong等［14］提出基于區(qū)間相似度的動態(tài)多目標(biāo)進(jìn)化框架，結(jié)合隨機(jī)突變策略、決策變量分解策略和環(huán)境變化強(qiáng)度預(yù)測策略，有效提高算法跟蹤新環(huán)境的PF。Feng等［15］通過結(jié)合深度學(xué)習(xí)的自動編碼技術(shù)和預(yù)測策略重新初始化新種群。Zhang等［16］選取使用線性預(yù)測策略、收縮策略和抽樣策略生成種群的非支配個體作為新環(huán)境下的初始種群，有效提高算法收斂速度。

此外，檢測環(huán)境變化和變化程度是動態(tài)多目標(biāo)優(yōu)化算法設(shè)計中重要環(huán)節(jié)之一。許多有效算法環(huán)境檢測機(jī)制十分簡單，大多都采用重新評價個體的方式判斷環(huán)境是否發(fā)生改變，并通過嵌套合理的數(shù)學(xué)模型設(shè)計動態(tài)響應(yīng)機(jī)制。Sahmoud等［17］提出了一系列新的變化檢測機(jī)制，一種是檢測種群個體是否發(fā)生變化，另一種則是在搜索空間中產(chǎn)生一些新個體檢測環(huán)境是否發(fā)生變化。Richter［18］提出通過判斷當(dāng)前代目標(biāo)解集和新一代目標(biāo)解集是否具有不同分布的方法，以判斷環(huán)境是否發(fā)生變化。Jiang等［19］提出一種穩(wěn)態(tài)檢測方法，將所有個體隨機(jī)排列后重評估，通過重評估差異證明環(huán)境變化與否。

以上方法保持了種群的分布性，對新環(huán)境下的種群具有良好的跟蹤環(huán)境能力；然而，在種群收斂時不能保持很好的收斂速度，并且在解決環(huán)境變化時具有一定的盲目性，不能為新環(huán)境下種群提供正確引導(dǎo)。因此，提高種群自主進(jìn)化能力并在環(huán)境發(fā)生變化后快速跟蹤環(huán)境，幫助算法對新變化作出快速響應(yīng)成為提高算法收斂速度和收斂性的研究重點。

基于上述問題，綜合考慮算法跟蹤環(huán)境變化能力、收斂快速性等問題，提出一種基于新評價指標(biāo)的自適應(yīng)預(yù)測動態(tài)多目標(biāo)優(yōu)化算法（Adaptive Prediction Dynamic Multi-objective Optimization Algorithm based on New Evaluation Index， NEI-APDMOA）。與現(xiàn)有其他算法相比，該算法具有以下特點：

1）引入一種新的非支配排序指標(biāo)，平衡種群多樣性和收斂快速性，解決解集分布不均等問題，有效提高種群自主進(jìn)化能力，加快算法收斂。

2）提出一種判斷動態(tài)環(huán)境變化強(qiáng)弱的算子，判斷環(huán)境變化前后線性相關(guān)性，為算法跟蹤環(huán)境變化提供依據(jù)。

3）設(shè)計自適應(yīng)響應(yīng)機(jī)制，根據(jù)環(huán)境變化強(qiáng)弱選擇相應(yīng)的響應(yīng)機(jī)制生成新環(huán)境下預(yù)測種群，提高環(huán)境變化跟蹤能力。

本文采用5個FDA系列［20］、2個DMOP系列［21］和2個DTLZ系列［22］涵蓋3類動態(tài)多目標(biāo)問題的標(biāo)準(zhǔn)測試集，將本文算法與DNSGA-Ⅱ-A（Dynamic Non-dominated Sorting Genetic Algorithm-Ⅱ-A）［6］、DNSGA-Ⅱ-B（Dynamic Non-dominated Sorting Genetic Algorithm-Ⅱ-B）［6］、PPS（Population Prediction Strategy）算法［23］對比。實驗結(jié)果表明，NEI-APDMOA能更好地平衡種群進(jìn)化時多樣性和收斂性，保持更快的收斂速度，具有更好的動態(tài)環(huán)境跟蹤能力，更加合理地響應(yīng)環(huán)境變化。

1 問題描述

DMOP是以最小化多目標(biāo)優(yōu)化問題為研究對象，數(shù)學(xué)定義一個具有維決策變量、個目標(biāo)函數(shù)的DMOP可以描述為：

隨著環(huán)境的變化，根據(jù)PS和PF的變化情況［24］，動態(tài)多目標(biāo)優(yōu)化問題可分為以下4類：

第1類問題 PS隨時間變化，PF不隨時間變化。

第2類問題 PS不隨時間變化，PF隨時間變化。

第3類問題 PS和PF都隨時間變化。

第4類問題 PS和PF都不隨時間變化。

2 相關(guān)工作

2.1　動態(tài)多目標(biāo)優(yōu)化算法框架

目前動態(tài)多目標(biāo)優(yōu)化算法大多都是基于靜態(tài)多目標(biāo)優(yōu)化算法基礎(chǔ)上改進(jìn)，當(dāng)環(huán)境沒有發(fā)生改變時，將動態(tài)多目標(biāo)優(yōu)化問題以時間維度分割成多個靜態(tài)多目標(biāo)優(yōu)化問題，并優(yōu)化求解。在靜態(tài)算法基礎(chǔ)上增加環(huán)境變化檢測機(jī)制和響應(yīng)機(jī)制，實時檢測當(dāng)前時刻問題與上一時刻問題的數(shù)學(xué)模型映射關(guān)系。環(huán)境變化響應(yīng)機(jī)制是設(shè)計動態(tài)多目標(biāo)優(yōu)化算法的關(guān)鍵，當(dāng)檢測到環(huán)境發(fā)生改變時，變化響應(yīng)機(jī)制直接影響環(huán)境變化后種群的優(yōu)劣，好的響應(yīng)機(jī)制可以保證種群在新環(huán)境下的多樣性和收斂的快速性。

動態(tài)多目標(biāo)優(yōu)化算法主要框架由3部分組成：靜態(tài)多目標(biāo)優(yōu)化算法、環(huán)境變化檢測機(jī)制和環(huán)境變化響應(yīng)機(jī)制，算法的主框架流程如圖1所示。

圖1　動態(tài)多目標(biāo)優(yōu)化算法流程

2.2　熵權(quán)TOPSIS評分

TOPSIS（Technique for Order Preference by Similarity to an Ideal Solution）理論模型［25］是一種多目標(biāo)決策算法，基本原理是通過計算評價樣本與正理想解和負(fù)理想解的距離排序，正理想解和負(fù)理想解分別是各評價指標(biāo)中的最優(yōu)值和最劣值，該數(shù)學(xué)模型通過對理想解的逼近實現(xiàn)多指標(biāo)成分綜合分析，如圖2所示。

圖2　正理想點和負(fù)理想點

熵權(quán)法根據(jù)各指標(biāo)信息含量賦予權(quán)重系數(shù)，更準(zhǔn)確地進(jìn)行目標(biāo)綜合評價。對采集的原始數(shù)據(jù)建立評估矩陣如下：

在進(jìn)行數(shù)據(jù)處理的過程中，為使原始狀態(tài)矩陣中的數(shù)據(jù)具有可行性，需對原始評估矩陣的評估數(shù)據(jù)進(jìn)行正向化和逆向化處理。如果數(shù)據(jù)中有逆向指標(biāo)，此時需要使用從數(shù)據(jù)處理到生成變量的“逆向化”功能處理，讓數(shù)據(jù)變成正向指標(biāo)。針對數(shù)據(jù)越大越優(yōu)型指標(biāo)和數(shù)據(jù)越小越優(yōu)型指標(biāo)分別進(jìn)行正向化（式（3））和逆向化（式（4））處理：

將處理后的正向指標(biāo)進(jìn)行標(biāo)準(zhǔn)、歸一化處理，將所有數(shù)據(jù)歸至0到1之間，解決數(shù)據(jù)量綱化問題，最終得到矩陣：

3 NEI?APDMOA

3.1　非支配排序度量指標(biāo)

多目標(biāo)優(yōu)化算法的目的就是協(xié)調(diào)各個目標(biāo)函數(shù)之間的關(guān)系，找出使得各個目標(biāo)函數(shù)都盡可能達(dá)到較大（或者較?。┑暮瘮?shù)值的最優(yōu)解集。Deb等［6］提出了非支配排序遺傳算法（Non-dominated Sorting Genetic Algorithm-Ⅱ， NSGA-Ⅱ），該算法引入擁擠度和擁擠度比較算子，將擁擠度作為種群個體之間的比較準(zhǔn)則，使得準(zhǔn)Pareto域中的種群個體均勻擴(kuò)展到整個Pareto域，保證種群的多樣性。NSGA-Ⅱ簡單有效，已成為多目標(biāo)優(yōu)化問題中的基本算法之一。然而，在種群進(jìn)行快速非支配排序時，只考慮擁擠度不能很好地平衡多目標(biāo)算法下種群的多樣性和收斂性；在高維目標(biāo)選擇中，擁擠度不能作為唯一的非支配排序指標(biāo)，否則將導(dǎo)致解在非支配層上分布不均勻，使算法陷入局部最優(yōu)。

為使算法在尋優(yōu)過程中同時兼顧種群多樣性和收斂快速性，本文引入新的非支配排序度量指標(biāo)，根據(jù)種群進(jìn)化過程動態(tài)調(diào)整算法的全局搜索和局部開發(fā)能力，提高多目標(biāo)算法收斂性的同時，也提高算法優(yōu)化效率和非支配解集的質(zhì)量。

算法1 新度量指標(biāo)排序法。

輸入 前一時刻的非支配種群；

輸出 更新的種群new。

計算前一時刻非支配種群各指標(biāo)熵值，得到指標(biāo)權(quán)重矩陣

將前一時刻的非支配種群與指標(biāo)權(quán)重結(jié)合，得到加權(quán)標(biāo)準(zhǔn)化矩陣

初始化正、負(fù)理想解后計算出種群的正、負(fù)理想解集

計算種群的熵權(quán)TOPSIS評分

返回更新的種群new

3.2　環(huán)境檢測機(jī)制

一個優(yōu)秀的環(huán)境檢測機(jī)制不僅需要判斷環(huán)境變化的劇烈程度，即決策空間到目標(biāo)空間映射發(fā)生變化的劇烈程度，還需要判斷環(huán)境變化的規(guī)律，將當(dāng)下環(huán)境變化規(guī)律與響應(yīng)機(jī)制相契合，為響應(yīng)機(jī)制提供更合理、有效的指導(dǎo)。

算法針對性選擇部分代表性解，并利用這些解檢測環(huán)境是否發(fā)生改變，若發(fā)生改變，則利用這些解判斷環(huán)境變化關(guān)聯(lián)程度。假設(shè)環(huán)境在t時刻到t+1時刻發(fā)生改變，通過DNSGA-Ⅱ算法在t時刻所選擇個體集合的目標(biāo)函數(shù)所處目標(biāo)空間位置為實心點，t+1時刻此集合的目標(biāo)函數(shù)所處目標(biāo)空間位置為空心點，同一解集在不同時刻下的關(guān)聯(lián)程度如圖3所示。

圖4　參考直線示意圖

算法2 環(huán)境變化檢測機(jī)制。

利用環(huán)境參考直線公式計算種群、+1的截距矩陣、

3.3　環(huán)境響應(yīng)機(jī)制

3.3.1隨機(jī)初始化

當(dāng)環(huán)境發(fā)生劇烈變化時，種群在新環(huán)境中的移動和進(jìn)化方向存在很大差異，繼續(xù)沿用之前環(huán)境的響應(yīng)機(jī)制會使種群不能及時適應(yīng)新環(huán)境的特點，不能快速追蹤環(huán)境變化。對新環(huán)境支配種群隨機(jī)初始化可以保證種群有良好的多樣性，避免陷入局部最優(yōu)，保證新環(huán)境下種群的收斂性。本文算法對種群中一定數(shù)量的支配種群個體隨機(jī)初始化，非支配種群個體保留上一時刻狀態(tài)，在新環(huán)境變化后作出響應(yīng)，保證種群多樣性和新環(huán)境下收斂速度。

算法3 隨機(jī)初始化策略。

輸入 當(dāng)前時刻種群，種群大??；

輸出 隨機(jī)初始化預(yù)測種群random。

選擇/10數(shù)量的最優(yōu)個體best

隨機(jī)生成9×/10數(shù)量的個體random

合并best與random種群個體組成預(yù)測種群random

返回預(yù)測種群random

圖5　支配種群個體的隨機(jī)初始化

3.3.2質(zhì)心移動軌跡預(yù)測

圖6　不同時刻種群輪廓質(zhì)心

算法4 質(zhì)心軌跡移動策略。

輸入 當(dāng)前時刻種群，歷史質(zhì)心存檔history，歷史輪廓存檔history；

輸出 質(zhì)心軌跡移動預(yù)測種群move。

計算當(dāng)前種群的質(zhì)心和輪廓，更新歷史質(zhì)心存檔history與歷史輪廓存檔history

計算預(yù)測種群質(zhì)心

計算預(yù)測種群輪廓

生成并返回質(zhì)心移動預(yù)測種群move

3.3.3慣性隨機(jī)預(yù)測

算法5 慣性隨機(jī)預(yù)測。

輸入 當(dāng)前種群，前一時刻種群-1，種群大??；

輸出 慣性隨機(jī)預(yù)測種群inertia。

計算環(huán)境變化前后種群時間序列

根據(jù)式（23）計算生成當(dāng)前種群預(yù)測點p

預(yù)測點鄰域通過高斯擾動產(chǎn)生新預(yù)測點集new

合并預(yù)測點p和新預(yù)測點集new組成預(yù)測點集predict

預(yù)測點集predict中選擇個的預(yù)測種群inertia

返回慣性隨機(jī)預(yù)測種群inertia

3.4　NEI-APDMOA詳細(xì)描述

NEI-APDMOA旨在檢測到環(huán)境變化時，實時追蹤環(huán)境變化強(qiáng)弱，以算法最快速度響應(yīng)環(huán)境變化，平衡種群分布性和收斂性，使種群更好地適應(yīng)新環(huán)境。NEI-APDMOA的詳細(xì)描述如算法6所示。

算法6 NEI-APDMOA。

初始化 種群大小，隨機(jī)產(chǎn)生規(guī)模為的初始種群，進(jìn)化代數(shù)，進(jìn)化總代數(shù)，交叉概率c，變異概率m

for=1 todo

環(huán)境變化不存在線性關(guān)系，啟用算法3

生成預(yù)測種群；

環(huán)境變化存在弱相關(guān)關(guān)系，啟用算法4

生成預(yù)測種群；

環(huán)境變化存在強(qiáng)線性關(guān)系，啟用算法5

生成預(yù)測種群；

end if

輸出預(yù)測種群并作為當(dāng)前初始種群

end if

種群以交叉概率c，變異概率m交叉變異生成子代種群G

for=1 todo

啟用算法1計算子代個體新評價指標(biāo)V

end for

end for

3.5　計算復(fù)雜度分析

4 測試問題及評價指標(biāo)

4.1　測試問題

為了驗證本文算法的有效性，選取FDA1～FDA5［20］、DMOP1、DMOP2［21］、DTLZ1和DTLZ2［22］涵蓋3類動態(tài)多目標(biāo)問題的標(biāo)準(zhǔn)測試集進(jìn)行仿真實驗。其中：FDA1和FDA4屬于第1類問題（真實PS位置隨時間變化，真實PF位置不隨時間變化）；DMOP1屬于第2類問題（真實PS位置不隨時間變化，真實PF位置隨時間變化）；FDA2、FDA3、FDA5和DMOP2屬于第3類問題（真實PS位置和PF位置都隨時間變化）；DTLZ1和DTLZ2的Pareto前沿面都是高維曲面。

4.2　性能指標(biāo)

為了能夠全面地評價算法的性能表現(xiàn)，本文采用3種廣泛使用的評價指標(biāo)。

1）反世代距離（Inverted Generational Distance， IGD）［23］。

2）世代距離（Generational Distance， GD）［23］。

5 實驗與結(jié)果分析

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

表1　不同度量權(quán)重時的平均IGD、SP值

圖7　平均IGD值隨環(huán)境檢測閾值的變化曲線

5.2　實驗結(jié)果與分析

根據(jù)測試函數(shù)問題的PS和PF的變化情況進(jìn)行分類并將本文算法（NEI-APDMOA）與NSGA-Ⅱ-A［6］、NSGA-Ⅱ-B［6］和PPS算法［23］進(jìn)行對比，在仿真實驗后分別計算各算法在測試函數(shù)上的平均IGD、平均SP和平均GD這3種評價指標(biāo)值，對比情況如表2～4所示，其中：性能“+”“-”和“～”分別表示根據(jù)顯著性水平為0.05的Wilcoxon秩和檢驗結(jié)果，對應(yīng)算法得到的指標(biāo)值結(jié)果比NEI-APDMOA較好、較差和相似，各表中最后一行標(biāo)出了NEI-APDMOA與其他算法對比結(jié)果的統(tǒng)計數(shù)據(jù)。

平均IGD評價標(biāo)準(zhǔn)結(jié)果如表2所示，NEI-APDMOA較其余3種對比算法有較大優(yōu)勢。相較于DNSGA-Ⅱ-A，本文算法有6個測試函數(shù)的平均IGD數(shù)據(jù)表現(xiàn)出色，有3個測試函數(shù)結(jié)果相似；相較于DNSGA-Ⅱ-B，有7個測試函數(shù)NEI-APDMOA表現(xiàn)出色，有2個測試函數(shù)結(jié)果相似；相較于PPS算法，NEI-APDMOA在全部測試函數(shù)中的表現(xiàn)都要出色。通過對比可知，NEI-APDMOA比3種對比算法有更優(yōu)性能，這主要歸功于引入新評價指標(biāo)分階段平衡收斂速度和種群多樣性，其次有針對性的環(huán)境響應(yīng)策略也有一定性能提升貢獻(xiàn)。

平均SP評價標(biāo)準(zhǔn)結(jié)果如表3所示，相較于DNSGA-Ⅱ-A，NEI-APDMOA有2個測試函數(shù)的平均SP數(shù)據(jù)表現(xiàn)出色，有4個測試函數(shù)結(jié)果相似，有3個測試函數(shù)結(jié)果不如DNSGA-Ⅱ-A；相較于DNSGA-Ⅱ-B，NEI-APDMOA有2個測試函數(shù)表現(xiàn)出色，有5個測試函數(shù)結(jié)果相似，另有2個測試函數(shù)較差；相較于PPS算法，NEI-APDMOA有2個測試函數(shù)表現(xiàn)出色，有3個測試函數(shù)結(jié)果相似，有4個測試函數(shù)表現(xiàn)不如PPS算法。通過對比綜合分析，NEI-APDMOA在新環(huán)境下的對新初始種群的預(yù)測是導(dǎo)致在部分測試函數(shù)上性能略差的主要原因，但NEI-APDMOA整體的收斂性都優(yōu)于其他3種算法，能夠適應(yīng)環(huán)境變化并快速追蹤Pareto前沿面。

平均GD評價標(biāo)準(zhǔn)比較結(jié)果如表4所示。相較于DNSGA-Ⅱ-A，NEI-APDMOA有7個測試函數(shù)的平均GD數(shù)據(jù)表現(xiàn)出色，有1個測試函數(shù)結(jié)果相似，1個不如比較算法；相較于DNSGA-Ⅱ-B，有7個測試函數(shù)NEI-APDMOA表現(xiàn)出色，有1個測試函數(shù)結(jié)果相似，另有1個測試函數(shù)較差；相較于PPS算法，NEI-APDMOA有7個測試函數(shù)表現(xiàn)出色，有2個測試函數(shù)結(jié)果相似。

通過對比可知，NEI-APDMOA分別在9、4、8個測試函數(shù)上取得了最優(yōu)的平均IGD值、平均SP值和平均GD值，相較于對比算法有更好的動態(tài)多目標(biāo)優(yōu)化性能。

為了直觀展示各算法在不同環(huán)境中的綜合性能，跟蹤每個算法在不同類型測試問題上的IGD值演變曲線如圖8所示，具體分析對比如下。

1）動態(tài)測試函數(shù)FDA1作為第1類問題代表，PS隨時間變化，PF不隨時間變化。在動態(tài)測試問題FDA1中，NEI-APDMOA在一開始就具有良好的收斂性，且全局收斂效果明顯優(yōu)于其他對比算法，說明本文算法獲得的解集更加接近真實的Pareto前沿。但是種群在環(huán)境變化前后波動較大，經(jīng)分析是由于算法在自適應(yīng)預(yù)測機(jī)制中生成的預(yù)測種群為保持多樣性所導(dǎo)致，算法經(jīng)過幾代進(jìn)化后立即收斂，展現(xiàn)出算法能更好適應(yīng)新環(huán)境的能力。NEI-APDMOA可以更快速地適應(yīng)第1類問題環(huán)境的變化，提高了算法在環(huán)境變化后的尋優(yōu)能力，更快速地收斂至理想Pareto前沿。

2）動態(tài)測試函數(shù)DMOP1作為第2類問題代表，PS不隨時間發(fā)生改變，PF隨時間發(fā)生改變，DMOP1最優(yōu)PF呈現(xiàn)凸顯至凹型的變化。NEI-APDMOA在大多數(shù)代數(shù)中顯示出比其他比較算法更低IGD值，表明NEI-APDMOA產(chǎn)生的解集更加接近真實Pareto前沿，NEI-APDMOA在前沿變化的情況下仍然具有最好的追蹤能力。分析可得，NEI-APDMOA更加適應(yīng)新環(huán)境并快速地收斂至理想Pareto前沿，相較于其他3種算法可以更好地適用于第2類問題。

3）動態(tài)測試函數(shù)FDA3和DMOP2屬于第3類問題，PS和PF都隨時間變化。對于此類問題，NEI-APDMOA在大部分時間IGD值較小且曲線平穩(wěn)，說明本文算法有效平衡了收斂速度和種群多樣性，環(huán)境變化后響應(yīng)速度更快，算法更加穩(wěn)定。得益于NEI-APDMOA根據(jù)環(huán)境變化強(qiáng)弱選擇相應(yīng)的響應(yīng)機(jī)制，有效降低環(huán)境變化后的種群波動，通過有效判斷環(huán)境變化因子，為選擇合理的響應(yīng)機(jī)制提供有效信息。綜合對比分析可知，NEI-APDMOA可以更快更準(zhǔn)確地響應(yīng)此類型的環(huán)境變化，表現(xiàn)出較為穩(wěn)定的收斂性和分布性，相較于其余3種算法更加適用于PF和PS都隨時間變化的第3類問題。

4）動態(tài)測試函數(shù)DTLZ1和DTLZ2作為高維問題代表，Pareto前沿面都是高維的。對于此類問題，NEI-APDMOA在環(huán)境變化初始階段收斂性優(yōu)于其余3種算法，可以以較快速度收斂至理想解集，經(jīng)過進(jìn)化收斂性與其他算法相差不大。對比分析可知，NEI-APDMOA通過使用提出的新指標(biāo)更加合理地進(jìn)行非支配排序，更好地解決高維動態(tài)多目標(biāo)問題。

為更好地展現(xiàn)NEI-APDMOA在不同時刻產(chǎn)生的Pareto解在Pareto前沿上的分布，圖9～10給出DMOP1和DTLZ2不同類型測試函數(shù)的前沿分布情況。其中，DMOP1測試函數(shù)繪出同一環(huán)境下不同進(jìn)化階段的前沿分布情況，DTLZ2測試函數(shù)繪出不同環(huán)境下的前沿分布情況。

表2　四種算法的平均IGD值統(tǒng)計

表3　四種算法的平均SP值統(tǒng)計

表4　四種算法的平均GD值統(tǒng)計

如圖9所示，在同一環(huán)境進(jìn)化初期選擇最優(yōu)個體時，NEI-APDMOA由于引入新評價指標(biāo)，選擇全局性最優(yōu)個體權(quán)重較大，側(cè)重于全局搜索，較DNSGA-Ⅱ-A有更快收斂速度；當(dāng)進(jìn)化處于后期時，隨著選擇全局性最優(yōu)個體權(quán)重下降，算法從初期側(cè)重于全局尋優(yōu)變?yōu)閭?cè)重于局部尋優(yōu)，增加種群多樣性，所得Pareto解增多，分布較DNSGA-Ⅱ-A均勻，更加接近測試函數(shù)理想Pareto前沿。

DTLZ2問題如圖10所示，NEI-APDMOA在第1次環(huán)境變化時較PPS算法有較快的收斂速度；由于本文算法根據(jù)環(huán)境變化類型選擇響應(yīng)機(jī)制，當(dāng)?shù)?次環(huán)境變化時，大部分個體收斂趨勢較好，但種群分布性依然欠佳；隨著種群進(jìn)化，在第9次環(huán)境變化時，種群的分布性得到改善，NEI-APDMOA較對比算法PPS更加快速適應(yīng)新環(huán)境。

圖8　不同算法在6個測試函數(shù)上的IGD值演變曲線

圖9　DMOP1在同一環(huán)境下不同階段的解集分布

通過對比4個算法在不同動態(tài)類型測試函數(shù)上的平均IGD、平均SP和平均GD這3種評價指標(biāo)，并分析4個算法的平均IGD值演變曲線和不同環(huán)境變化種群前沿分布可知，NEI-APDMOA可以很好地處理不同類型和維度的動態(tài)問題，在環(huán)境變化中加快收斂速度的同時兼顧種群的多樣性和分布性，更好地適用于解決不同類型的動態(tài)優(yōu)化問題。

圖10　DTLZ2在不同環(huán)境下的解集分布

6 結(jié)語

設(shè)計動態(tài)多目標(biāo)進(jìn)化算法的核心問題就是當(dāng)環(huán)境發(fā)生變化時，及時追蹤變化的PF或PS并保持良好的分布性，本文提出一種基于新評價指標(biāo)的自適應(yīng)預(yù)測動態(tài)多目標(biāo)優(yōu)化算法（NEI-APDMOA）。NEI-APDMOA在5個FDA系列、2個DMOP系列和2個DTLZ系列涵蓋3類動態(tài)多目標(biāo)問題的標(biāo)準(zhǔn)測試集上，與3個現(xiàn)有算法作仿真對比。實驗結(jié)果表明，NEI-APDMOA在進(jìn)化過程中平衡種群多樣性和收斂性，以較快速度獲得更好的收斂性和分布性解集，快速適應(yīng)環(huán)境變化的同時有效避免陷入局部最優(yōu)，在處理不同類型和維度的動態(tài)優(yōu)化問題上優(yōu)勢明顯。此外，當(dāng)遇到部分復(fù)雜環(huán)境時，算法雖同樣可以較好預(yù)測新環(huán)境下種群，但也會出現(xiàn)較少數(shù)的個體偏離現(xiàn)象影響算法性能，故如何有效判斷新環(huán)境下預(yù)測種群是否可靠，設(shè)計一種更加合理的自適應(yīng)預(yù)測機(jī)制將是未來研究的重點。

[1] ZHOU A， QU B Y， LI H， et al. Multiobjective evolutionary algorithms： a survey of the state of the art［J］. Swarm and Evolutionary Computation， 2011， 1（1）：32-49.

[2] 劉若辰，李建霞，劉靜，等. 動態(tài)多目標(biāo)優(yōu)化研究綜述［J］. 計算機(jī)學(xué)報， 2020， 43（7）：1246-1278.（LIU R C， LI J X， LIU J， et al. A survey on dynamic multi-objective optimization［J］. Chinese Journal of Computers， 2020， 43（7）：1246-1278.）

[3] RUAN G， YU G， ZHENG J， et al. The effect of diversity maintenance on prediction in dynamic multi-objective optimization［J］. Applied Soft Computing， 2017， 58： 631-647.

[4] MURUGANANTHAM A， TAN K C， VADAKKEPAT P. Evolutionary dynamic multiobjective optimization via Kalman filter prediction［J］. IEEE Transactions on Cybernetics， 2016， 46（12）： 2862-2873.

[5] DEB K， RAO N U B， KARTHIK S. Dynamic multi-objective optimization and decision-making using modified NSGA-Ⅱ： a case study on hydro-thermal power scheduling［C］// Proceedings of the 2007 International Conference on Evolutionary Multi-Criterion Optimization， LNCS 4403. Berlin： Springer， 2007： 803-817.

[6] DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-Ⅱ［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197.

[7] AZEVEDO C R B， ARAúJO A F R. Generalized immigration schemes for dynamic evolutionary multiobjective optimization［C］// Proceedings of the 2011 IEEE Congress of Evolutionary Computation. Piscataway： IEEE， 2011： 2033-2040.

[8] SAHMOUD S， TOPCUOGLU H R. A memory-based NSGA-Ⅱ algorithm for dynamic multi-objective optimization problems［C］// Proceedings of the 2016 European Conference on the Applications of Evolutionary Computation， LNCS 9598. Cham： Springer， 2016： 296-310.

[9] JIANG M， WANG Z， QIU L， et al. A fast dynamic evolutionary multiobjective algorithm via manifold transfer learning［J］. IEEE Transactions on Cybernetics， 2021， 51（7）： 3417-3428.

[10] CAO L， XU L， GOODMAN E D， et al. Evolutionary dynamic multiobjective optimization assisted by a support vector regression predictor［J］. IEEE Transactions on Evolutionary Computation， 2020， 24（2）： 305-319.

[11] RONG M， GONG D， PEDRYCZ W， et al. A multimodel prediction method for dynamic multiobjective evolutionary optimization［J］. IEEE Transactions on Evolutionary Computation， 2020， 24（2）： 290-304.

[12] WANG C， YEN G G， JIANG M. A grey prediction-based evolutionary algorithm for dynamic multiobjective optimization［J］. Swarm and Evolutionary Computation， 2020， 56： No.100695.

[13] ZHAO Q， YAN B， SHI Y， et al. Evolutionary dynamic multiobjective optimization via learning from historical search process［J］. IEEE Transactions on Cybernetics， 2022， 52（7）： 6119-6130.

[14] GONG D， XU B， ZHANG Y， et al. A similarity-based cooperative co-evolutionary algorithm for dynamic interval multiobjective optimization problems［J］. IEEE Transactions on Evolutionary Computation， 2020， 24（1）： 142-156.

[15] FENG L， ZHOU W， LIU W， et al. Solving dynamic multiobjective problem via autoencoding evolutionary search［J］. IEEE Transactions on Cybernetics， 2022， 52（5）： 2649-2662.

[16] ZHANG Q， YANG S， JIANG S， et al. Novel prediction strategies for dynamic multiobjective optimization［J］. IEEE Transactions on Evolutionary Computation， 2020， 24（2）： 260-274.

[17] SAHMOUD S， TOPCUOGLU H R. Sensor-based change detection schemes for dynamic multi-objective optimization problems［C］// Proceedings of the 2016 IEEE Symposium Series on Computational Intelligence. Piscataway： IEEE， 2016： 1-8.

[18] RICHTER H. Detecting change in dynamic fitness landscapes［C］// Proceedings of the 2009 IEEE Congress on Evolutionary Computation. Piscataway： IEEE， 2009： 1613-1620.

[19] JIANG S， YANG S. A steady-state and generational evolutionary algorithm for dynamic multiobjective optimization［J］. IEEE Transactions on Evolutionary Computation， 2017， 21（1）：65-82.

[20] XU B， ZHANG Y， GONG D， et al. Environment sensitivity-based cooperative co-evolutionary algorithms for dynamic multi-objective optimization［J］. IEEE/ACM Transactions on Computational Biology and Bioinformatics， 2018， 15（6）： 1877-1890.

[21] GOH C K， TAN K C. A competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization［J］. IEEE Transactions on Evolutionary Computation， 2009， 13（1）：103-127.

[22] DEB K， THIELE L， LAUMANNS M， et al. Scalable test problems for evolutionary multiobjective optimization［M］// ABRAHAM A， JAIN L， GOLDBERG R. Evolutionary Multiobjective Optimization： Theoretical Advances and Applications， AI&KP. London： Springer， 2005： 105-145.

[23] ZHOU A， JIN Y， ZHANG Q. A population prediction strategy for evolutionary dynamic multiobjective optimization［J］. IEEE Transactions on Cybernetics， 2014， 44（1）： 40-53.

[24] FARINA M， DEB K， AMATO P. Dynamic multiobjective optimization problems： test cases， approximations， and applications［J］. IEEE Transactions on Evolutionary Computation， 2004， 8（5）：425-442.

[25] DENG H， YEH C H， WILLIS R J. Inter-company comparison using modified TOPSIS with objective weights［J］. Computers and Operations Research， 2000， 27（10）：963-973.

[26] 何春雄，龍衛(wèi)江，朱鋒峰. 概率論與數(shù)理統(tǒng)計［M］. 北京：高等教育出版社， 2012：79-80.（HE C X， LONG W J， ZHU F F. Probability Theory and Mathematical Statistics［M］. Beijing： Higher Education Press， 2012：79-80.）

[27] CAO L， XU L， GOODMAN E D， et al. Decomposition-based evolutionary dynamic multiobjective optimization using a difference model［J］. Applied Soft Computing， 2019， 76： 473-490.

[28] 周永道，王會琦，呂王勇. 時間序列分析及應(yīng)用［M］. 北京：高等教育出版社， 2015：69-87.（ZHOU Y D， WANG H Q， LYU W Y. Time Series Analysis and Application［M］. Beijing： Higher Education Press， 2015：69-87.）

[29] WANG C， YEN G G， ZOU F. A novel predictive method based on key points for dynamic multi-objective optimization［J］. Expert Systems with Applications， 2022， 190： No.116127.

Dynamic multi-objective optimization algorithm based on adaptive prediction of new evaluation index

LI Erchao*， ZHANG Shenghui

（，，730050，）

Most of the Multi-objective Optimization Problems （MOP） in real life are Dynamic Multi-objective Optimization Problems （DMOP）， and the objective function， constraint conditions and decision variables of such problems may change with time， which requires the algorithm to quickly adapt to the new environment after the environment changes， and guarantee the diversity of Pareto solution sets while converging to the new Pareto frontier quickly. To solve the problem， an Adaptive Prediction Dynamic Multi-objective Optimization Algorithm based on New Evaluation Index （NEI-APDMOA） was proposed. Firstly， a new evaluation index better than crowding was proposed in the process of population non-dominated sorting， and the convergence speed and population diversity were balanced in different stages， so as to make the convergence process of population more reasonable. Secondly， a factor that can judge the strength of environmental changes was proposed， thereby providing valuable information for the prediction stage and guiding the population to better adapt to environmental changes. Finally， three more reasonable prediction strategies were matched according to environmental change factor， so that the population was able to respond to environmental changes quickly. NEI-APDMOA， DNSGA-Ⅱ-A （Dynamic Non-dominated Sorting Genetic Algorithm-Ⅱ-A）， DNSGA-Ⅱ-B （Dynamic Non-dominated Sorting Genetic Algorithm-Ⅱ-B） and PPS （Population Prediction Strategy） algorithms were compared on nine standard dynamic test functions. Experimental results show that NEI-APDMOA achieves the best average Inverted Generational Distance （IGD） value， average SPacing （SP） value and average Generational Distance （GD） value on nine， four and eight test functions respectively， and can respond to environmental changes faster.

dynamic multi-objective optimization; evolutionary algorithm; evaluation index; non-dominated sorting; prediction strategy

This work is partially supported by National Natural Science Foundation of China （62063019）， Natural Science Foundation of Gansu Province （20JR10RA152， 22JR5RA241）.

LI Erchao， born in 1980， Ph. D.， professor. His research interests include multi-objective optimization， artificial intelligence， robot control.

ZHANG Shenghui， born in 1997， M. S. candidate. His research interests include dynamic multi-objective optimization.

1001-9081（2023）10-3178-10

10.11772/j.issn.1001-9081.2022091453

2022?09?30；

2022?11?17；

國家自然科學(xué)基金資助項目（62063019）；甘肅省自然科學(xué)基金資助項目（20JR10RA152，22JR5RA241）。

李二超（1980—），男，河北保定人，教授，博士，主要研究方向：多目標(biāo)優(yōu)化、人工智能、機(jī)器人控制； 張生輝（1997—），男，甘肅武威人，碩士研究生，主要研究方向：動態(tài)多目標(biāo)優(yōu)化。

TP273

A

2022?11?21。