王啟翔 許峰

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

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

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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

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

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

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

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

1 NSGA-III算法

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

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

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

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

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

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

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

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

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

2 信息反饋NSGA-III算法

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

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

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

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

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

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

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

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

步驟2 種群更新。

（1）對(duì)父代種群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ù)參考點(diǎn)和小生境技術(shù)，產(chǎn)生下一代父種群Pt+1。

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

4 數(shù)值實(shí)驗(yàn)與算法性能評(píng)測(cè)

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

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

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

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

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

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

5 結(jié)論

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

參考文獻(xiàn)：

[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].計(jì)算機(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.