多目標優(yōu)化算法標準測試函數(shù)尋優(yōu)研究

栗方

摘要：多目標優(yōu)化問題在各種領域中日益展現(xiàn)出舉足輕重的地位。該文對6種多目標優(yōu)化算法進行了測試，選擇了四種不同性質的測試函數(shù)，安排了12組實驗，從實驗數(shù)據(jù)可以得出，NSGA-III算法在多目標優(yōu)化問題中具有很好的尋優(yōu)效果，IBEA算法在單目標優(yōu)化問題或者是多目標問題中需要觀測單個變量時能起到很好的尋優(yōu)效果，CMAES算法在高值域多目標優(yōu)化中能起到很好的優(yōu)化作用。

關鍵詞：多目標優(yōu)化算法;多目標標準測試函數(shù);智能優(yōu)化算法;多目標優(yōu)化評價指標;多目標優(yōu)化性能測試

中圖分類號：TP301.6? ? ? 文獻標識碼：A

文章編號：1009-3044（2020）23-0203-04

Abstract： Multi-objective optimization problems play an increasingly important role in various fields. In this paper， six kinds of multi-objective optimization algorithms are tested， four kinds of test functions with different properties are selected， and 12 groups of experiments are arranged. From the experimental data， it can be concluded that NSGA-III algorithm has a good optimization effect in multi-objective optimization problems， and IBEA algorithm can play a good optimization effect when single-objective optimization problems or multi-objective problems need to observe a single variable. CMAES algorithm can play a good role in high-range multi-objective optimization.

Key words： multi-objective optimization algorithm; multi-objective standard test function; intelligent optimization algorithm; multi-objective optimization evaluation index; multi-objective optimization performance test

1 背景

多目標計算問題在日常生活中很常見，不管是在科學探索還是實際的工程應用當中，多目標優(yōu)化算法都是很重要的。不僅因為多目標優(yōu)化算法需要同時對多個目標進行優(yōu)化，多目標優(yōu)化的最優(yōu)解還是一組解集，如何選出符合決策者偏好的解也是需要注意的問題[1]。常用的多目標算法有NSGA-II、NSGA-III、CMAES、IBEA、MOEAD等，每種算法都有各自的適應條件，本文會通過設計的實驗優(yōu)化對比出6種算法的優(yōu)劣性及適應空間。在多目標優(yōu)化算法的發(fā)展過程中，形成了多種標準測試函數(shù)，這些測試問題由于其容易將優(yōu)化問題上升為多維而被廣泛采用。常用的標準測試函數(shù)有SCH、DEB、ZDT1、ZDT2、DTLZ2、DTLZ3、WFG3、WFG7等，這些測試函數(shù)各有其特點。在優(yōu)化性能的評比中，通常采用以下3種方法，只考慮收斂性指標、只考慮多樣性指標、綜合考慮收斂性和多樣性指標。本文圍繞多目標優(yōu)化問題，基于Platypus實驗平臺，設計了6種多目標優(yōu)化算法在3種不同適應度值下的標準測試問題中優(yōu)化效果分析實驗[2]，通過實驗數(shù)據(jù)分析出6種算法的優(yōu)劣性，以便在處理優(yōu)化問題時選擇適合問題的優(yōu)化算法。

2 多目標優(yōu)化算法

2.1 NSGA-II和NSGA-III算法

帶精英策略的非支配排序遺傳算法（NSGA-II）是迄今為止最優(yōu)秀的多目標進化遺傳算法之一，該算法解決了第一代優(yōu)化算法中如何將進化算法與多目標優(yōu)化問題有機結合起來的問題，采用了基于聚類、精英保留機制、空間超格、擁擠距離等機制。該算法面臨的主要問題是如何處理高維多目標優(yōu)化以及效率問題[3]。該算法的邏輯圖如圖1所示。

是否滿足終止條件取決于人為設定或迭代次數(shù)限定，但最優(yōu)值不會變化，迭代次數(shù)要盡可能多次，因為在迭代次數(shù)太少的情況下，不能確定出現(xiàn)的解為最優(yōu)解。在NSGA-II遺傳算法中，擁擠度計算是確保種群多樣性的一個重要部分[4]，偽代碼表示為：

NSGA-III算法在原有的NSGA-II算法框架基礎上，增添了下面結構：① 假設有一個規(guī)模為N的種群A，用選擇、重組、變異遺傳算子對種群A進行操作，得到一個規(guī)模為N的種群B，再將種群A和種群B混合，得到一個規(guī)模為2N的種群C;②對種群C進行非支配排序;③對目標函數(shù)進行標量化操作，方便下一步關聯(lián)參考點，見公式（1）;④尋找極值點，此時需要用到ASF函數(shù)，見公式（2）;⑤遍歷每個函數(shù)，找到ASF數(shù)值最小的個體，根據(jù)這些點的具體函數(shù)值，計算出相對應坐標軸上的截距[ai]，得到[ai]和[zi]后，按照公式（3）進行歸一化運算。

之后對計算出的參考點進行遞歸處理，篩選子代并刪除參考點尋優(yōu)。

2.2 MOEAD算法

MOEAD（基于分解的多目標優(yōu)化算法）將一個多目標優(yōu)化問題分解為若干個標量優(yōu)化子問題，并同時對其進行優(yōu)化，每個子問題都通過使用來自它的幾個相鄰子問題的信息來優(yōu)化的，能夠大大提高處理處理高緯度目標函數(shù)時的效率[5]，算法流程如下：

1）初始化設置，包括目標函數(shù)、終止條件、鄰居個數(shù)等;

2）分解目標問題，明確子問題及鄰居;

3）依次對每個子問題進行優(yōu)化;

4）更新端點和鄰居;

5）判斷停止條件。

通過算法流程可以看出，MOEAD是一種將多目標問題分解為一系列的單目標問題的方法，在處理高緯度問題時降低了問題維度。

2.3 IBEA算法

IBEA（基于指標的多目標選擇）采用對指標的優(yōu)劣性判斷來優(yōu)化目標問題，算法流程如下：

1）產(chǎn)生初始種群P，種群大小為α，當前迭代此時m=0;

2） 適應度計算，根據(jù)如下公式計算P里個體的使用度，例如[x1]（k為比例縮放因子）;

3） 對每一代P，進行迭代篩選，直到種群大小為a;

4） 終止條件判斷;

5） [p']為[p]的復制;

6） 用交叉變異作用在[p']上，[p]=[p']+[p]，m=m+1，轉2）。

3多目標優(yōu)化標準測試函數(shù)及評價指標

3.1多目標優(yōu)化標準測試函數(shù)

3.1.1 DTLZ2測試函數(shù)

DTLZ2可以擴展到任意多個目標，從而很好地擴展到高維多目標優(yōu)化問題，是目前采用的最多的測試算法之一[6]，公式如下：

3.1.2 WFG測試函數(shù)

WFG為變量關聯(lián)測試函數(shù)，WFG1具有平偏好的特征，WFG2具有多模非連續(xù)特征，WFG3為欺騙問題，WFG7為參數(shù)獨立測試函數(shù)，WFG9為參數(shù)獨立多模欺騙問題。本文選取WFG3和WFG7作為測試函數(shù)。

3.2多目標優(yōu)化性能評價指標

評價一個算法效率的方法，就是設置算法性能評價指標，目前主流的多目標算法性能評價指標主要有兩種。

3.2.1收斂性指標

設A和B為兩組PF近似解集，C（A，B）的定義如下面公式（6），表示B中個體至少被A中一個個體支配的占比[7]：

若[CA，B=1]，則表示B中所有個體都被A支配，證明B的收斂性比A差。

3.2.2多樣性指標

空間評價法可衡量PF近似解集中個體在目標空間中的分布情況，表達式如公式（7）所示：

其中，[PF] 代表已知的真實[PF]，[di]為解集中非支配邊界上兩個連續(xù)向量的歐氏距離，[d]是平均距離。該目標方法比較適用于二維目標空間，在超多目標情況下不理想。

4多目標優(yōu)化性能測試實驗設計

4.1實驗平臺搭建

本文基于Platypus實驗平臺，使用Pycharm2019編譯器設置了12組不同參數(shù)配置的實驗。對NSGAII、NSGAIII、IBEA、MOEAD、SPEA2、CMAES六種優(yōu)化算法在適應度值分別為500、5000、50000時分別對DTLZ2、WFG3、WFG7、WFG2四種測試問題進行優(yōu)化分析。

4.2實驗具體內容設置

詳細的12組實驗設置及安排如下。

E-1：適應度值選取500時，六種算法對DTLZ2進行優(yōu)化計算。

E-2：適應度值選取5000時，六種算法對DTLZ2進行優(yōu)化計算。

E-3：適應度值選取50000時，六種算法對DTLZ2進行優(yōu)化計算。

E-4：適應度值選取500時，六種算法對WFG3進行優(yōu)化計算。

E-5：適應度值選取5000時，六種算法對WFG3進行優(yōu)化計算。

E-6：適應度值選取50000時，六種算法對WFG3進行優(yōu)化計算。

E-7：適應度值選取500時，六種算法對WFG7進行優(yōu)化計算。

E-8：適應度值選取5000時，六種算法對WFG7進行優(yōu)化計算。

E-9：適應度值選取50000時，六種算法對WFG7進行優(yōu)化計算。

E-10：適應度值選取500時，六種算法對WFG2進行優(yōu)化計算。

E-11：適應度值選取5000時，六種算法對WFG2進行優(yōu)化計算。

E-12：適應度值選取50000時，六種算法對WFG2進行優(yōu)化計算。

5多目標優(yōu)化性能測試實驗結果分析

5.1進行12組實驗結果展示

對DTLZ2測試問題在不同適應度值下的結果展示如圖2、圖3、圖4所示;對WFG3測試問題在不同適應度值下的結果展示如圖5、圖6、圖7所示;對WFG7測試問題在不同適應度值下的結果展示如圖8、圖9、圖10所示。對WFG2測試問題如圖11、圖12、圖13所示。

5.2 對DTLZ2測試函數(shù)結果的分析

從圖2中的數(shù)據(jù)可以看出，當適應度值為500時，6種算法都不能很好地優(yōu)化出帕累托前沿面，也就是無法得出最優(yōu)值。此時NSGA-II和NSGA-III算法能得出大量的非支配解，而MODEA得到的解空間差較大，效果在6種算法中最差。 在圖3中，適應度值設置為了5000，此時NSGA-II和NSGA-III可以優(yōu)化出帕累托前沿，但相比較來說NSGA-III優(yōu)化效果最好，CMAES算法優(yōu)化出了大量非支配解，是六種算法中最好的，但是帕累托前沿面沒有NSGA-III算法體現(xiàn)的好[8]。IBEA算法在三個坐標平面上找到了帕累托前沿線，但是解空間中非支配解稀少，這證明了IBEA算法在單目標尋優(yōu)上具有很高的效率。圖4中適應度值設置為了50000，此時NSGA-III算法表現(xiàn)最優(yōu)，該算法優(yōu)化出了完美的帕累托前沿面，并且優(yōu)化得到的解在解空間中分布均勻，優(yōu)化效果遠遠高于NSGA-II算法。此時CMAES雖然優(yōu)化得解最多，但仍然無法表現(xiàn)出良好的回歸曲線。SPEA2算法優(yōu)化效果僅次于NSGA-III并優(yōu)于NSGA-II算法。IBEA算法仍是對單目標結果表現(xiàn)出優(yōu)越性。

5.3對WFG3測試函數(shù)結果的分析

如圖5所示，在適應度值為500時，CMAES算法表現(xiàn)最優(yōu)，得到了大量最優(yōu)解，解空間基本收斂，MOEAD算法表現(xiàn)最差，體現(xiàn)不出收斂性。圖6中適應度值為5000時，IBEA開始表現(xiàn)出對目標函數(shù)的適應性，已經(jīng)形成完整的收斂直線，此時另外5種算法效果基本相同。圖7中適應度值為50000時，IBEA算法求出了無偏差的最優(yōu)解，這是由于IBEA算法的特性決定的，而CMAES在低值區(qū)域表現(xiàn)較差，在高值區(qū)域優(yōu)化效果良好，證明CMAES對高值域多目標函數(shù)具有很好的適應性。此時NSGA-II和NSGA-III算法無法得到最優(yōu)收斂曲線，證明NSGA算法對WFG3這種類型的測試問題不能起到良好的優(yōu)化效果。

5.4對WFG7測試函數(shù)結果的分析

圖8中，在適應度值較小時，依然是CMAES算法表現(xiàn)最好，求得的最優(yōu)解最多，MOEAD算法表現(xiàn)最差。當適應度值增加到5000時，依然是CMAES算法最優(yōu)，SPEA2和NSGA-III優(yōu)化效果次之。在圖10中適應度值設置為50000時，NSGA-III算法最優(yōu)，IBEA算法仍然是能在單坐標平面上優(yōu)化出最優(yōu)解，此次實驗進一步證明IBEA算法在單目標優(yōu)化上能表現(xiàn)出很高的效果，NSGA-III在多目標優(yōu)化問題中優(yōu)于其他幾種算法。

5.5對WFG2測試函數(shù)結果的分析

圖11中，在適應度值為500時，無一種算法表現(xiàn)出良好的尋優(yōu)曲線，在圖12所示的結果中，適應度值被設置為了5000，此時NSGA-II、NSGA-III、CMAES、SPEA2四種優(yōu)化算法尋優(yōu)效果較好，由于IBEA算法本身特性，其優(yōu)化效果仍然是稀疏邊界，無法形成帕累托曲面，MOEAD算法依然無法表現(xiàn)出好的解。在圖13中，對應的是實驗E-12結果圖，實驗數(shù)據(jù)顯示，當適應度值設置為50000時，IBEA算法在優(yōu)化結果上表現(xiàn)得稀疏，無法形成帕累托曲面，進一步證明IBEA算法在高緯度優(yōu)化問題上優(yōu)化效果不佳，MOEAD算法優(yōu)化效果最差，得到的解雜亂無章，CMAES算法優(yōu)化效果最好，NSGA-III算法次之。此三次實驗進一步證明在對高緯度多目標優(yōu)化問題的求解中，NSGA-III算法和CMAES算法能起到很好的優(yōu)化作用，對單目標問題或者低維度問題采用IBEA算法能獲得更優(yōu)的帕累托最優(yōu)解。

6 結論

本文通過搭建Python平臺，進行了12組不同設置的實驗安排，通過對12組實驗結果的分析，對比出所選取6種算法的優(yōu)缺點，NSGA-III算法在整體上優(yōu)于NSGA-II算法，在處理多目標優(yōu)化問題上，NSGA-III算法表現(xiàn)優(yōu)越，另外5種算法都次之。通過設置的WFG3測試函數(shù)得出，在對多目標優(yōu)化問題分解方面，IBEA效果最好，證明在處理單目標問題或者需要研究多目標函數(shù)中某個單獨變量時采用IBEA算法最好。CMAES算法在三種測試問題上求解最多，但并不能形成良好的帕累托回歸曲面，在WFG3測試問題中，CMAES算法在低值區(qū)域表現(xiàn)較差，證明CMAES算法在高值域多目標優(yōu)化中能起到很好的優(yōu)化作用。在所有實驗中，MOEAD優(yōu)化效果沒有其他的五種算法好，SPEA2算法表現(xiàn)良好，但優(yōu)化效果適中。通過本次實驗得出結論，在多目標優(yōu)化算法中，NSGA-III表現(xiàn)最優(yōu)，在對單目標測試問題或者觀測多目標函數(shù)中的單個量時采用IBEA算法最好，在對大型高值多目標問題的研究上采用CMAES算法能得到較多的最優(yōu)解。

參考文獻：

[1] 胡涵，李振宇.多目標進化算法性能評價指標綜述[J].軟件導刊，2019，18（9）：1-4.

[2] 李子軒，楊國來，孫全兆，等.強沖擊載荷下永磁式電渦流阻尼器阻力特性及優(yōu)化研究[J].兵工學報，2018，39（4）：664-671.

[3] 李朝芳，茍英.基于改進NSGA-Ⅱ算法測試資源優(yōu)化配置的研究[J].科學咨詢，2017（11）：38.

[4] 戴喜妹，張軍峰，趙鵬力，等.離場航班多目標優(yōu)化排序研究[J].哈爾濱商業(yè)大學學報，2019，35（2）：241-245， 252.

[5] 徐一紅，陳青華. 基于GEP算法的煤礦瓦斯涌出量預測模型研究[J].山東師范大學學報，2015，30（2）：27-30.

[6] 吳偉麗.基于NSGA-Ⅲ的復雜成因變壓器直流偏磁控制優(yōu)化算法[J].電測與儀表，2018，55（11）：89-93.

[7] 朱永勝，王杰，瞿博陽，等.含風電場的多目標動態(tài)環(huán)境經(jīng)濟調度[J].電網(wǎng)技術，2015，39（5）：1315-1322.

[8] 王經(jīng)卓，樊紀山.空間數(shù)據(jù)關聯(lián)的多目標粒子群優(yōu)化算法[J].控制與決策，2015，30（7）：1291-1297.

【通聯(lián)編輯：謝媛媛】