王啟翔 許峰

摘? 要：為了提高NSGA-III算法求解大規(guī)模高維多目標(biāo)優(yōu)化問題的能力，提出了一種基于自適應(yīng)信息反饋機制的改進NSGA-III算法，其基本思想是：根據(jù)信息反饋原理，將當(dāng)前代第k個個體與用NSGA-III算法求得的第i個個體加權(quán)平均后作為下一代第i個個體。k的選取有指定和隨機兩種方式，可以根據(jù)目標(biāo)函數(shù)的梯度自適應(yīng)地選擇。采用大規(guī)模高維測試函數(shù)對新算法進行了性能測試，并與相關(guān)算法的結(jié)果進行了比較。

關(guān)鍵詞：高維多目標(biāo)優(yōu)化;NSGA-III;信息反饋;自適應(yīng);目標(biāo)函數(shù)梯度

中圖分類號：TP312 文獻標(biāo)志碼：A 文章編號：2095-2945（2020）30-0020-04

Abstract： In order to improve the ability of NSGA-III to solve large-scale many-objective optimization problems， an improved NSGA-III based on adaptive information feedback mechanism is proposed. Its basic idea is： according to the principle of information feedback， the weighted average of the kth individual in current generation and the ith individual obtained by NSGA-III is taken as the ith individual in next generation. There are two ways to select k： named and random， which can be adaptively selected according to the gradient of the objective function. The performance of new algorithm is tested by the large-scale many-objective test function， and the results are compared with those of related algorithms.

Keywords： large-scale many-objective optimization; NSGA-III; information feedback; adaptive; objective function gradient

通常，有兩個或三個目標(biāo)的優(yōu)化問題稱為多目標(biāo)優(yōu)化問題（Multi-objective Optimization Problems，MOP），而有四個或更多目標(biāo)的問題稱為高維多目標(biāo)優(yōu)化問題（Many-objective Optimization Problems，MaOP）。多目標(biāo)進化算法（Multi-objective Evolutionary Algorithm，MOEA）已被公認為求解MOP最有效的優(yōu)化算法，但被用于求解MaOP時性能往往會有不同程度的下降。

MOEA主要分為兩大類：一類是基于精英選擇的多目標(biāo)進化算法;另一類是基于多目標(biāo)分解的多目標(biāo)進化算法?；诰⑦x擇的多目標(biāo)進化算法中最具代表性的算法是NSGA類算法。1994年，K.Deb提出了基于非支配排序的NSGA[1];2002年，K.Deb將精英選擇引入NSGA算法，提出了NSGA-II[2];2014年，K.Deb又在NSGA-II中引入?yún)⒖键c，提出了NSGA-III[3]。

2017年，Bi[4]提出了一種基于小生境的改進NSGA-III;2018年，M. Carvalho[5]系統(tǒng)研究了NSGA-III中的參考點對算法性能的影響;2020年，Gu[6]提出了一種基于信息反饋的改進NSGA-III。

本文在文獻[6]的基礎(chǔ)上，提出了一種在算法中同時采用這兩種選擇方式的算法，基本思路是根據(jù)目標(biāo)函數(shù)的梯度自適應(yīng)再選擇這兩種方式。采用標(biāo)準測試函數(shù)對改進算法進行了性能測試，并與NSGA-III及文獻[6]中算法的結(jié)果進行了比較。

1 NSGA-III算法

NSGA-III是在NSGA-II基礎(chǔ)上發(fā)展起來的，基本步驟如下[3]：

步驟1 初始化參考點和種群（種群規(guī)模為N）。參考點根據(jù)Das和Dennis的方法[7]進行預(yù)設(shè)置。

步驟2 對父代種群Pt，通過選擇、交叉、變異產(chǎn)生子種群Qt。

步驟3 混合Pt和Qt得到一個新種群Rt，即Rt=Pt∪Qt，其規(guī)模為2N。對Rt進行非支配排序，將其劃分為不同的非支配解集（F1，F(xiàn)2，...，F(xiàn)l，...，F(xiàn)w）。

步驟4 產(chǎn)生一個新解集St，其方法是：從F1開始，每次移動一個非支配解集到St，直到首次出現(xiàn)|St|≥N，其中|St|為St中解的個數(shù)。假設(shè)Fl是首次滿足|St|≥N的解集，則

步驟5 從St中選擇解產(chǎn)生下一代父種群Pt+1。若|St|=N，則St直接被視為Pt+1。否則，首先將St＼Fl放入Pt+1，然后再從Fl中根據(jù)選擇機制選取其余解。

在NSGA-III中，解的選擇是基于參考點?；趨⒖键c的選擇方法如下：

首先找到種群St的理想點z*=（z1*，z2*，…，zm*），其中zi*是種群St中所有解中第i個目標(biāo)函數(shù)值的最小值，然后歸一化種群和參考點。此時，需要計算St中的每個解到每條參考線的垂直距離，然后用最短的距離連接解與參考點。這樣，就可以在Fl中用一種新的小生境保護方法選擇個體。生境數(shù)？籽j是種群St＼Fl中與第j個參考點相連的個體數(shù)。這種小生境技術(shù)的基本目的是提高NSGA-III的分布性，所以首先需要找到具有最小生境數(shù)？籽i的參考點i，然后確定Fl中有沒有個體與參考點i相連。如果有個體與參考點i相連，則根據(jù)？籽i的值選擇一個個體進入Pt+1。否則，這次迭代將不考慮這個參考點，而是用另外具有最小生境數(shù)的參考點重復(fù)上述操作，直到滿足|Pt+1|=N。

步驟6 若滿足終止條件，則輸出最終的解，否則重復(fù)步驟2。

2 信息反饋NSGA-III算法

大量數(shù)值實驗顯示，NSGA-III在求解大規(guī)模高維多目標(biāo)優(yōu)化問題時性能欠佳[6]。

2019年，Wang[8]提出在啟發(fā)類算法中可以引入信息反饋機制以提高算法的收斂性。據(jù)此，2020年，Zhang[9]提出了基于信息反饋機制的增強MOEA/D算法，專門用以求解大規(guī)模高維多目標(biāo)優(yōu)化問題;2020年，Gu[6]系統(tǒng)研究了在NSGA-III中如何應(yīng)用信息反饋機制以提高其求解大規(guī)模高維多目標(biāo)優(yōu)化問題的性能。

信息反饋的基本思想是：用算法求得的結(jié)果并不直接作為t+1代的結(jié)果，而是僅作為一個中間結(jié)果，將此結(jié)果與 t代中的若干結(jié)果進行加權(quán)平均后再作為t+1代的結(jié)果。根據(jù)t代結(jié)果選取個數(shù)以及選取方式的不同，信息反饋有不同的形式。考慮到算法的復(fù)雜性，t代結(jié)果選取的個數(shù)一般不超過3，而t代結(jié)果選取的方式有固定和隨機兩種，即信息反饋通常有6種形式。由于基于不同信息反饋形式的算法結(jié)構(gòu)類似，本文僅研究t代結(jié)果選取個數(shù)為1的情形。

當(dāng)t代結(jié)果選取個數(shù)為1時，信息反饋模型定義如下[6]：

其中，Xp，Xc分別表示父代和子代個體。

在進化的早、中期，當(dāng)？酌ij小于設(shè)定的閾值？著（通常取為10-2）時，意味著算法有極大的可能陷入局部最優(yōu)，此時選擇隨機方法進行信息反饋，否則選擇固定方法進行信息反饋。在進化晚期，為了防止隨機方法破壞算法的收斂性，將直接選擇固定方法。在編程時，通常設(shè)定總進化代數(shù)的后30%為進化晚期。

基于自適應(yīng)信息反饋機制的NSGA-III（NSGA-III based on adaptive information feedback， NSGA-III-AIF）的步驟如下：

步驟1 初始化。產(chǎn)生初始種群P0，參考點集？撰和初始理想點Zmin。

步驟2 種群更新。

（1）對父代種群Pt，根據(jù)NSGA-III的選擇、交叉、變異方法得到u;根據(jù)目標(biāo)函數(shù)梯度自適應(yīng)地確定信息反饋方法;代入式（1）和式（2）即得到子種群Qt。

（2）將Pt和Qt合并為Rt。

（3）按照NSGA-III中的方法，產(chǎn)生新解集St。

（4）按照NSGA-III中的方法，根據(jù)參考點和小生境技術(shù)，產(chǎn)生下一代父種群Pt+1。

步驟3 若滿足終止條件，則輸出最終的解，否則重復(fù)步驟2。

4 數(shù)值實驗與算法性能評測

衡量多目標(biāo)進化算法性能的指標(biāo)分為四類[11]，考慮到本文的改進算法主要改進的是NSGA-III的收斂性，所以選用收斂性指標(biāo)（GD）和綜合指標(biāo)（IGD）進行評測，其定義如下：

其中，O是理論Pareto最優(yōu)解集，A是算法求得的Pareto Front。在GD中，di為O中第i個個體與A中個體的最小歐幾里德距離。相反地，在IGD中，di為A中第i個個體與O中個體的最小歐幾里德距離。顯然，GD和IGD越小，表明算法取得的非支配解集逼近理論Pareto最優(yōu)解集的程度越高，即算法的收斂性越好。

算法基本參數(shù)設(shè)置：種群規(guī)模100，交叉概率為0.95，變異概率為0.05，進化代數(shù)為10000。其他參數(shù)均采用相應(yīng)文獻中的推薦值。測試函數(shù)選用LSMOP1～9[12]。LSMOP1～9中的目標(biāo)函數(shù)數(shù)m從3到15，具體為3，5，8，10，15。LSMOP1～9中含有幾十至上百個決策變量，屬典型的大規(guī)模高維多目標(biāo)優(yōu)化測試問題。

圖1～圖6分別給出了NSGA-III、NSGA-III-F1和NSGA-III-AIF三種算法優(yōu)化LSMOP（m=3，8，15）的GD和IGD指標(biāo)對比數(shù)據(jù)圖。其中，*， △， ○分別為NSGA-III、NSGA-III-F1和NSGA-III-AIF的指標(biāo)數(shù)據(jù)。

由于算法具有隨機性，圖中數(shù)據(jù)均為各算法獨立運行10次的平均值。

圖1～圖6顯示：（1） NSGA-III-AIF的GD和IGD指標(biāo)明顯小于NSGA-III，這表明NSGA-III-AIF在求解大規(guī)模多目標(biāo)優(yōu)化問題時收斂性較NSGA-III有明顯提高;（2） NSGA-III-AIF的GD和IGD指標(biāo)不同程度地小于NSGA-III-F1，且隨著m的增大，小于的幅度也隨之加大。這在一定程度上表明，基于自適應(yīng)信息反饋機制的NSGA-III與基于單一信息反饋機制的NSGA-III相比，的確可以進一步改善算法的收斂性。而且，問題的維數(shù)m越高，改善的程度越明顯。

5 結(jié)論

在相關(guān)工作的基礎(chǔ)上，本文提出了基于自適應(yīng)信息反饋的改進NSGA-III算法。通過對比此改進算法與NSGA-III、基于固定信息反饋的改進NSGA-III的性能指標(biāo)，驗證了改進算法在求解大規(guī)模高維多目標(biāo)優(yōu)化問題時，性能有了一定程度的提高。必須指出的是，本文的工作尚需進一步完善。比如，進化晚期的定義采用了一種人為劃定的方式;由于程序所限，僅與NSGA-III和NSGA-III-F1進行了比較。

參考文獻：

[1]N. Srinivas， K. Deb. Muilti-objective optimization using non-dominated sorting in genetic algorithms[J]. Evol. Comput.，1994，2（3）：221-248.

[2]K. Deb， S. Agrawal. A fast and elitist multi-objective genetic algorithm： NSGA-II[J]. IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.

[3]K.Deb， H. Jain. An evolutionary many-objective algorithm using reference-point-based nondominated sorting approach， Part I： Solving problems with box constraints [J].IEEE Transactions on Evolutionary Computation， 2014，18：577-601.

[4]Xiaojun Bi， Chao Wang. A niche-elimination operation based NSGA-III algorithm for many-objective optimization [J]. Applied Intelligence， 2017，48：118-141.

[5]Matheus Carvalho. Influence of reference points on a many-objective optimization algorithm [C]// Brazilian Conference on Intelligent Systems，2018，7：31-36.

[6]Zi-Min Gu， Gai-Ge Wang. Improving NSGA-III algorithms with information feedback models for large-scale many-objective optimization [J]. Future Generation Computer Systems， 2020，107：49-69.

[7]I. Das， J.E. Dennis. Normal-boundary intersection： A new method for generating the pareto surface in nonlinear multicriteria optimization problems [J]. SIAM. J. Optim.， 1998，8（3）：631-657.

[8]G. Wang， Y. Tan， Improving metaheuristic algorithms with information feedback models [J]. IEEE Trans. Cybern.， 2019，49（2）：542-555.

[9]Yin Zhang， Gai-Ge Wang， Keqin Li. Enhancing MOEA/D with information feedback models for large-scale many-objective optimization [J]. Information Sciences， 2020，522：1-16.

[10]劉雪東，許峰.基于目標(biāo)函數(shù)變化率的混合蟻群遺傳算法[J].計算機工程與應(yīng)用，2013，49（18）：41-44.

[11]S. Jiang， Y. Song， J. Zhang. Consistencies and contradictions of performance metrics in multi-objective optimization[J]. IEEE Trans. Cybern.， 2014，44（12）：2391-2404.

[12]R. Cheng， Y. Jin， M. Olhofer， B. sendhoff， Test problems for large-scale multi-objective and many-objective optimization[J]. IEEE Trans. Cybern.， 2017，47（12）：4108-4121.