李二超，張生輝

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

李二超*，張生輝

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

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

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

0 引言

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

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

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

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

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

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

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

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

本文采用5個(gè)FDA系列［20］、2個(gè)DMOP系列［21］和2個(gè)DTLZ系列［22］涵蓋3類動(dòng)態(tài)多目標(biāo)問(wèn)題的標(biāo)準(zhǔn)測(cè)試集，將本文算法與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］對(duì)比。實(shí)驗(yàn)結(jié)果表明，NEI-APDMOA能更好地平衡種群進(jìn)化時(shí)多樣性和收斂性，保持更快的收斂速度，具有更好的動(dòng)態(tài)環(huán)境跟蹤能力，更加合理地響應(yīng)環(huán)境變化。

1 問(wèn)題描述

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

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

第1類問(wèn)題 PS隨時(shí)間變化，PF不隨時(shí)間變化。

第2類問(wèn)題 PS不隨時(shí)間變化，PF隨時(shí)間變化。

第3類問(wèn)題 PS和PF都隨時(shí)間變化。

第4類問(wèn)題 PS和PF都不隨時(shí)間變化。

2 相關(guān)工作

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

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

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

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

2.2　熵權(quán)TOPSIS評(píng)分

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

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

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

在進(jìn)行數(shù)據(jù)處理的過(guò)程中，為使原始狀態(tài)矩陣中的數(shù)據(jù)具有可行性，需對(duì)原始評(píng)估矩陣的評(píng)估數(shù)據(jù)進(jìn)行正向化和逆向化處理。如果數(shù)據(jù)中有逆向指標(biāo)，此時(shí)需要使用從數(shù)據(jù)處理到生成變量的“逆向化”功能處理，讓數(shù)據(jù)變成正向指標(biāo)。針對(duì)數(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ù)量綱化問(wèn)題，最終得到矩陣：

3 NEI?APDMOA

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

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

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

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

輸入 前一時(shí)刻的非支配種群；

輸出 更新的種群new。

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

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

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

計(jì)算種群的熵權(quán)TOPSIS評(píng)分

返回更新的種群new

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

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

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

圖4　參考直線示意圖

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

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

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

3.3.1隨機(jī)初始化

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

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

輸入 當(dāng)前時(shí)刻種群，種群大?。?/p>

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

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

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

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

返回預(yù)測(cè)種群random

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

3.3.2質(zhì)心移動(dòng)軌跡預(yù)測(cè)

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

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

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

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

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

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

計(jì)算預(yù)測(cè)種群輪廓

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

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

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

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

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

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

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

預(yù)測(cè)點(diǎn)鄰域通過(guò)高斯擾動(dòng)產(chǎn)生新預(yù)測(cè)點(diǎn)集new

合并預(yù)測(cè)點(diǎn)p和新預(yù)測(cè)點(diǎn)集new組成預(yù)測(cè)點(diǎn)集predict

預(yù)測(cè)點(diǎn)集predict中選擇個(gè)的預(yù)測(cè)種群inertia

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

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

NEI-APDMOA旨在檢測(cè)到環(huán)境變化時(shí)，實(shí)時(shí)追蹤環(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ù)測(cè)種群；

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

生成預(yù)測(cè)種群；

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

生成預(yù)測(cè)種群；

end if

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

end if

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

for=1 todo

啟用算法1計(jì)算子代個(gè)體新評(píng)價(jià)指標(biāo)V

end for

end for

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

4 測(cè)試問(wèn)題及評(píng)價(jià)指標(biāo)

4.1　測(cè)試問(wèn)題

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

4.2　性能指標(biāo)

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

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

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

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

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

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

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

5.2　實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)語(yǔ)

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

[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] 劉若辰，李建霞，劉靜，等. 動(dòng)態(tài)多目標(biāo)優(yōu)化研究綜述［J］. 計(jì)算機(jī)學(xué)報(bào)， 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)計(jì)［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] 周永道，王會(huì)琦，呂王勇. 時(shí)間序列分析及應(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；

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

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

TP273

A

2022?11?21。