多目標優化算法標準測試函數尋優研究

栗方

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

關鍵詞：多目標優化算法;多目標標準測試函數;智能優化算法;多目標優化評價指標;多目標優化性能測試

中圖分類號：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 背景

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

2 多目標優化算法

2.1 NSGA-II和NSGA-III算法

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

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

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

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

2.2 MOEAD算法

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

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

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

3）依次對每個子問題進行優化;

4）更新端點和鄰居;

5）判斷停止條件。

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

2.3 IBEA算法

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

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

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

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

4） 終止條件判斷;

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

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

3多目標優化標準測試函數及評價指標

3.1多目標優化標準測試函數

3.1.1 DTLZ2測試函數

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

3.1.2 WFG測試函數

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

3.2多目標優化性能評價指標

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

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]為解集中非支配邊界上兩個連續向量的歐氏距離，[d]是平均距離。該目標方法比較適用于二維目標空間，在超多目標情況下不理想。

4多目標優化性能測試實驗設計

4.1實驗平臺搭建

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

4.2實驗具體內容設置

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

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

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

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

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

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

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

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

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

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

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

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

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

5多目標優化性能測試實驗結果分析

5.1進行12組實驗結果展示

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

5.2 對DTLZ2測試函數結果的分析

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

5.3對WFG3測試函數結果的分析

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

5.4對WFG7測試函數結果的分析

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

5.5對WFG2測試函數結果的分析

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

6 結論

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

參考文獻：

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

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

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

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

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

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

[7] 朱永勝，王杰，瞿博陽，等.含風電場的多目標動態環境經濟調度[J].電網技術，2015，39（5）：1315-1322.

[8] 王經卓，樊紀山.空間數據關聯的多目標粒子群優化算法[J].控制與決策，2015，30（7）：1291-1297.

【通聯編輯：謝媛媛】