基于線性權重最優支配的高維多目標優化算法

朱占磊,李 征,趙瑞蓮

(北京化工大學 信息科學與技術學院,北京 100029) (*通信作者電子郵箱lizheng@mail.buct.edu.cn)

基于線性權重最優支配的高維多目標優化算法

朱占磊,李 征*,趙瑞蓮

(北京化工大學 信息科學與技術學院,北京 100029) (*通信作者電子郵箱lizheng@mail.buct.edu.cn)

在高維多目標優化問題中，Pareto支配關系存在非支配解隨優化目標數增加呈指數級增長和種群選擇壓力下降等問題。針對這些問題，基于線性權重聚合函數和支配關系兩種比較多目標解方法的思想，提出一種線性權重最優支配關系(LWM-dominance)，并理論證明了LWM非支配解集是Pareto非支配解集的子集，同時保留了種群中重要的角解。進一步地，基于LWM支配關系，實現了一個高維多目標進化優化算法，基于該算法的實驗驗證了LWM支配關系的性質。在隨機解空間中的實驗結果表明LWM支配關系適用于5～15個目標的高維多目標優化問題，通過DTLZ1～DTLZ7高維多目標優化問題進化過程中LWM非支配解集與Pareto非支配解集規模的對比實驗，結果表明優化目標數為10和15時非支配解的比例平均下降了約17%。

進化優化算法；高維多目標優化；線性權重函數；支配關系；Pareto前沿

0 引言

多目標優化問題普遍存在并已被廣泛研究。實際工程中的優化問題往往會涉及3個以上的優化目標,甚至會多達10～15個目標[1],這些問題被稱為高維多目標優化問題(Many-objective Optimization Problems, MaOP)[2]。

進化多目標優化算法是解決多目標優化問題最有效的方法之一,其中廣泛使用的NSGA-II(Non-dominated Sorting Genetic Algorithm II)[3]可以有效的解決2～3個目標的多目標優化問題。但在高維多目標優化問題中,隨著目標個數增加,基于Pareto支配關系最優解的選擇壓力被削弱,造成解集中非支配個體的比例呈指數上升[4],算法性能急劇下降。因此,在高維多目標優化問題中,需要研究一種新的支配關系來提高區分解集中個體優劣的能力,增強最優解的選擇壓力,從而減小解集中非支配解的占比,提升算法性能。

在高維多目標優化問題的研究中,解的比較方法可分為兩類[5]:

1)基于聚合函數的方法,即把多目標優化問題的目標向量通過聚合函數映射為一個實數值,進而比較這個實數值來確定解的優劣關系。線性加權函數是最常用的聚合函數[6-8]。但存在以下問題:首先,權重向量在線性加權函數中具有重要作用,權重的選取會影響優化算法在進化過程的搜索方向;其次,權重向量通常需要在進化算法執行前由領域專家依據經驗確定[9],并且在進化算法執行過程中通常是不變的,難以動態調整進化過程中的搜索方向[10]。最后,線性權重聚合函數的方法需要優化目標為同一量綱或者可以轉化為同一量綱,具有一定的局限性。

2)基于支配關系的方法,即通過一種支配關系來權衡解的優劣。此類方法最終的結果通常是一個解集合,需要領域專家通過更高層次的領域經驗和知識來進一步選取最終解。

在解決高維多目標優化問題的方法中,基于聚合函數的方法計算簡單,但由于目標數量的增加,進一步加劇了權重向量的確定難度,難以保證結果的準確;使用基于支配關系的方法求解,目前廣泛使用的Pareto支配關系,其最優解的選擇能力隨優化問題目標數的增加而急劇下降。如何改進Pareto支配關系是近年來高維多目標優化算法的研究熱點之一[11]。文獻[12]提出了γ-cons支配關系,這是Pareto支配關系的一種泛化,是Pareto支配關系的一般形式；但是實際計算過程中錐形的夾角需要人工確定。文獻[13]使用線性權重作為Pareto支配關系之外的第二選擇標準；但是它只考慮了有限的k種固定權重,只是幫助Pareto區分解集的一種次要手段。本文綜合聚合函數和支配關系的方法提出了一種線性權重最優支配關系(Linear Weighted Minimal/Maximal dominance， LWM-dominance),核心思想是考慮在線性加權聚合函數方法中,不同的權重向量會影響到解的優劣關系,若存在權重向量,使得某個解對應目標向量的聚合函數值在解集中是最優的,相對于其他解更有被保留下來的必要。這類解通常是在某個目標上達到了當前的最優值,或者各個目標上取值相對不會太差。

LWM支配關系借鑒并融合了聚合函數和支配關系兩種解比較的方法,具有以下優點:LWM支配關系借鑒了線性加權聚合函數的思想,但不需要計算聚合函數中具體的權重向量,只用本文算法驗證其存在性即可。在支配關系方面,Pareto定義的是一種解和解的支配關系,而LWM支配關系定義的是一種解和解集之間的支配關系。在高維多目標問題的優化算法中,LWM支配關系可以替換現有的Pareto支配關系。

本文首先給出LWM支配關系的定義,然后提出并證明了LWM支配關系的兩個重要性質；同時本文在NSGA-II算法中框架中融合了LWM支配關系,實現了一個高維多目標進化優化算法。通過隨機解空間中兩種支配關系的非支配解占比的研究,得出LWM支配關系適用于5～15個目標的高維多目標優化問題的結論?；贒TLZ1～DTLZ7高維多目標優化問題的實驗結果表明本文提出的高維多目標進化優化算法在進化過程中非支配解的占比要低于Pareto支配關系,LWM支配關系對NSGA-II算法得到的非支配解集有很好的約減效果。

1 LWM支配關系定義及推論

不失一般性,本文中考慮的優化問題均為最小化優化,即對于每個優化的子目標越小越好。形式化的表述為:

minf(x)=(f1(x),f2(x),…,fm(x))

(1)

s.t.x∈S?Rn

其中:x是n維實數空間中的決策向量；S是可行域;fi(x)為優化問題的第i(i=1,2,…,m)個目標函數；m為目標函數的個數。在問題1(式(1))描述的基礎上,給出以下兩個定義：

定義1 Pareto支配。解xA,xB∈S,若xA稱為Pareto支配xB,當且僅當對于?i=1,2,…,m均有fi(xA)≤fi(xB),同時?i使得fi(xA)lt;fi(xB)。

定義2 Pareto非支配解。解x*∈S被稱為Pareto非支配解(也稱作最優解),當且僅當S中不存在其他解支配x*?？尚杏騍中所有的Pareto非支配解組成Pareto非支配解集(最優解集),而非支配解集對應的目標向量組成的曲面稱為Pareto前沿面(Pareto Front, PF)。

下面給出LWM支配關系和LWM非支配解的定義。

定義3 LWM支配。解x∈X被稱為LWM支配解集X,當且僅當存在某個向量w=(w1,w2,…,wm)∈Rm+使得w(f(x))T取得最小,即對于?x′∈X且x′≠x均有w(f(x))Tlt;w(f(x′))T。同時,類似地,解x也被稱為LWM非支配解(最優解)。解集X中的所有LWM非支配解組成LWM非支配解集,LWM非支配解集對應的目標向量組成的曲面稱為LWM前沿面(LWM Front, LWMF)。

本文接下來將給出LWM支配關系的兩個推論以及相應的證明。

推論1 LWM非支配解也是Pareto非支配解,也就是LWM非支配解集是Pareto非支配解集的子集。

證明 根據Pareto支配關系的定義,某個解支配其他解,當且僅當這個解在所有的目標上均不大于另一個解,同時兩個解的目標向量不能完全相等,也就至少在某些子目標要小。接下來使用反證法來證明推論1。

推論1的逆命題為:至少存在一個解是LWM非支配解,但是它不是Pareto非支配解,也就是存在某個解支配它。

不失一般性,假設解x是LWM支配關系下的非支配解,但是它又被解x′在Pareto支配關系下支配。根據定義1可以得出fi(x′)≤fi(x)(i=1,2,…,m),因此,對于?w∈Rm+滿足w(f(x′))T≤w(f(x))T。同時,由于x是一個是LWM支配關系下的非支配解,根據定義3可知?w∈Rm+使得w(f(x))Tlt;w(f(x′))T,顯然這兩個不等式之間是矛盾的。

LWM非支配解集是Pareto非支配解集的一個子集,雖然理論上兩個集合存在相等的可能性,但是實驗數據表明LWM支配關系可以有效地約減Pareto非支配解集的規模。

推論2 如果一個解在某個目標取得最優,那么這個解為LWM非支配解。

證明 假設該解為x,可以構造一個權重向量w=(w1,w2,…,wm),滿足如下性質:

其中:ε是一個足夠小的正實數。此權重向量w可使w(f(x))T最小,保證了w的存在性。也就證明了含有最優子目標的解為LWM支配關系下的非支配解。

含有最優子目標的解在多目標優化問題中是比較重要的,也被稱為角解[14-15],而LWM支配關系保證了角解會被保留下來。

2 基于LWM支配關系的高維多目標優化算法

本章給出了基于LWM支配關系的優化算法,算法框架基本同NSGA-II一致,主要區別是使用LWM支配關系替換了Pareto支配關系。算法的框架如下。

算法1 基于LWM支配關系的高維多目標優化算法。

輸入 種群大小N、種群最大迭代次數T。

輸出 LWM非支配解集合LWMF。

步驟1 初始化進化種群P0,種群的規模為N,并令種群迭代次數t=0。

步驟2 對于第t次迭代的種群Pt實施交叉、變異操作,獲得臨時的子代種群Qt。

步驟3 把Pt和Qt合并得到種群Rt=Pt∪Qt,對Rt使用LWM支配關系進行非支配排序,并得到前N個個體構成子代種群Pt+1。

步驟4 判斷是否滿足進化的終止條件：如果滿足,輸出種群的非支配解；否則,t增加1,轉到步驟2。

基于LWM支配關系的非支配排序過程如下:第i次遍歷種群時,對于每個解,判斷其是否為LWM非支配解。如果是,則加入Fi,其中Fi為第i層非支配解集,遍歷結束之后對當前種群去除Fi之后得到的新種群進行同樣的遍歷操作,同時i增加1,直到種群中的解個數變為1或者0。

通過推論1可以得出,LWM非支配解集是Pareto非支配解集的一個子集。在本文中求解一個解集的LWM非支配解集是通過把它轉化為一個線性規劃問題來解決的。

s.t.w(f(x))Tlt;w(f(x′))T； ?x′∈X,x′≠x

(2)

wigt;0;i=1,2,…,m

線性規劃問題2(式(2))通常會出現三種情況:1)沒有可行解,這種情況顯然對應解x不是LWM非支配解。2)存在無界解,此時wi均大于0,且某個wi可以任意大,因此對應解x是LWM非支配解。3)存在最優解,理論上存在最優解w,解x符合LWM非支配解的定義,因此是LWM非支配解,但實際上由于計算精度誤差的問題,有可能得到的wi均為接近0的小數,此時實際上x不是LWM非支配解。因此需要判斷得到的s的值,大于某個閾值s才能認為是一個LWM非支配解。

3 實驗與驗證

本文在jMetal[16]開源多目標優化框架的基礎上實現了基于LWM支配關系的多目標優化算法,并通過實驗比較在高維多目標優化問題中,LWM支配關系與Pareto支配關系的優劣，具體包括兩種支配關系在種群進化過程中非支配解個數的對比,以及LWM支配關系對Pareto非支配解集約減能力的驗證。

選擇壓力體現的是支配關系區分支配解和非支配解的能力,可以通過種群中非支配解的個數來評價。為了確定LWM支配關系適用的優化問題的目標數范圍,實驗首先在隨機解空間中對比了兩種支配關系非支配解的個數,之后選取了7個廣泛用于多目標優化算法性能比較的多目標優化問題DTLZ1～DTLZ7[17],它們的決策變量和目標維數是可以擴展的。為了防止實驗結果受進化算法隨機性的影響,所有實驗均獨立運行10次,并計算運行結果的平均值。實驗是在Intel CORE i7 CPU和8 GB RAM的PC上完成的。

3.1 LWM支配關系適用優化目標數范圍的研究

為了確定LWM支配關系適用的優化問題目標數范圍,在隨機解空間進行了模擬實驗,通過在m維空間中進行均勻采樣模擬隨機解空間對應的目標向量,然后對比其中LWM非支配解個數和Pareto非支配解個數隨著優化問題目標數增多的變化情況。

實驗在目標數取值2～20的范圍內,對于每個目標數取值,均隨機生成1 000個實數向量來表示優化問題的種群對應在解空間的目標向量,然后分別計算出隨機種群中Pareto非支配解和LWM非支配解的個數。得到的結果如圖1所示?？梢钥闯鲈趦灮瘑栴}的目標函數在區間[5,15]時,LWM支配關系對Pareto支配關系的約減效果比較明顯。

圖1 隨機種群中兩種支配關系非支配解個數對比

3.2 LWM支配關系和Pareto支配關系選擇壓力的比較

實驗通過對在DTLZ1～DTLZ7優化問題進化過程中種群中LWM非支配解和Pareto非支配解隨著種群進化代數增加的變化情況,來分析LWM支配關系在高維多目標優化問題中是否增強了Pareto支配關系的選擇壓力。

在3.1節隨機解空間中的實驗結果表明,LWM支配關系適用于優化目標數在5～15的高維多目標優化問題,因此實驗中對DTLZ1～DTLZ7系列優化問題分別選取5、10、15和20個目標進行實驗,其自變量的個數是隨著目標數確定的,計算的公式由文獻[17]中給出。在基于LWM支配關系的優化算法和NSGA-II算法框架中,兩者的實驗參數設置一致:種群規模均為100，采用聯賽選擇，模擬二進制交叉和多項式變異,最大迭代次數均為100。實驗采用非支配解個數占比度量兩種支配關系的選擇壓力。

圖2展示了7個優化問題的種群非支配解個數的隨著進化代數增加的變化情況?？梢钥闯?1)對于DTLZ1～DTLZ7這7個優化問題,在進化初始階段LWM非支配解的比例小于Pareto支配關系的非支配解,這是因為在初始階段種群近似于隨機解集,因此和3.1節中隨機解空間中的實驗結果表現類似。2)對于這7個優化問題,優化目標數為10和15時,LWM非支配解的個數明顯小于Pareto非支配解的個數,總體相對于Pareto非支配解約減了17%；當目標數達到20時,兩者差距不再明顯。3)圖中存在有LWM非支配解的比例高出Pareto非支配解的情況,因為此時的LWM非支配解和Pareto非支配解不在同一次進化過程,這與推論1不矛盾。

3.3 LWM支配關系對Pareto非支配解的約減能力

推論1說明了LWM非支配解集是Pareto非支配解集的子集,因此LWM支配關系可以約減Pareto非支配解集的規模。

圖2 種群中非支配解個數隨著種群進化的變化曲線

實驗通過對比Pareto非支配解集中解的個數和使用LWM支配關系約減之后的個數來說明LWM支配關系的約減能力。首先,使用基于Pareto支配關系的進化優化算法得到表1中優化問題的Pareto非支配解集,然后對這些解集使用LWM支配關系進行約減。該實驗中進化優化算法的種群規模為100,獨立運行10次并記錄結果最后取平均。實驗優化問題及結果如表1所示。

表1 LWM支配關系對Pareto非支配解集的約減效果

注:PF為Pareto非支配解的個數；LWMF為LWM支配關系約減后解的個數。

對比表1中的PF和LWMF可以看出:1)因為優化目標數取值為10,進化算法結束之后,大小為100的種群中絕大部分都是Pareto非支配解,這也驗證了隨著目標數增多,在高維多目標優化問題的解種群中非支配解占比高的問題；2)LWM支配關系對Pareto非支配解集有明顯的約減效果,可以顯著地減小Pareto非支配解集的規模?？傮w上,LWMF相對于Pareto非支配解集約減了20.64%。實驗驗證了前文的推論1,即LWM非支配解是Pareto非支配解的子集。

3.4 討論與分析

3.1節和3.2節的實驗分別驗證了本文提出的LWM支配關系可以提高高維多目標優化問題在進化過程中種群的選擇壓力,以及LWM支配關系可以有效約減Pareto非支配解集的規模。LWM支配關系雖然借鑒了線性聚合函數方法的思想,但是LWM非支配解的判定只需要確定權重的存在性,因此避免了線性聚合函數方法中確定權重向量參數的問題,這或許也避免了線性權重聚合函數方法需要轉化為同一量綱的問題。

由于LWM支配關系在判定LWM非支配解的過程中需要求解線性規劃問題2,引入了額外的計算,因此相對于使用Pareto支配關系的NSGA-II算法花費了更多的時間,算法效率有所下降。

4 結語

高維多目標優化問題是目前演化計算領域的研究熱點之一,需要提出新的支配關系以解決目前廣泛使用的Pareto支配關系在高維多目標優化問題中非支配解隨目標數的增加呈指數級增長等問題。

本文提出了一種線性權重最優支配關系(LWM-dominance)的新型支配關系來解決傳統的Pareto支配關系在高維多目標優化問題中面臨的選擇壓力問題。本文證明了LWM非支配解集是Pareto非支配解集的一個子集,同時保留了解集中比較重要的角解。最后本文在NSGA-II算法框架的基礎上實現了一個高維多目標進化優化算法。

實驗結果表明:LWM支配關系適用于5～15個目標的高維多目標優化問題;基于LWM支配關系的高維多目標進化優化算法在進化過程中非支配解的比例要低于基于Pareto支配關系的非支配解的比例;LWM支配關系可以對Pareto非支配解集進行約減,并具有良好的約減效果。

References)

[1] DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 577-601.

[2] ISHIBUCHI H, TSUKAMOTO N, NOJIMA Y. Evolutionary many-objective optimization: a short review[C]// CEC 2008: Proceedings of the 2008 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2008: 2419-2426.

[3] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

[4] GARZA-FABRE M, PULIDO G T, COELLO C A C. Ranking methods for many-objective optimization[C]// MICAI 2009: Proceedings of the 2009 Mexican International Conference on Artificial Intelligence. Berlin: Springer, 2009: 633-645.

[5] DEB K. Multi-objective optimization using evolutionary algorithms[M]. New York: John Wiley amp; Sons, 2001: 47-75.

[6] STEHR G, GRAEB H, ANTREICH K. Performance trade-off analysis of analog circuits by normal-boundary intersection[C]// Proceedings of the 40th Annual Design Automation Conference. New York: ACM, 2003: 958-963.

[7] KLAMROTH K, J?RGEN T. Constrained optimization using multiple objective programming[J]. Journal of Global Optimization, 2007, 37(3): 325-355.

[8] HUGHES E J. Multiple single objective Pareto sampling[C]// CEC 2003: Proceedings of the 2003 Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2003: 2678-2684.

[9] LI B, LI J, TANG K, et al. Many-objective evolutionary algorithms: a survey[J]. ACM Computing Surveys, 2015, 48(1): 13.

[10] KUNG H T, LUCCIO F, PREPARATA F P. On finding the maxima of a set of vectors[J]. Journal of the ACM, 1975, 22(4): 469-476.

[11] 公茂果, 焦李成, 楊咚咚, 等. 進化多目標優化算法研究[J]. 軟件學報, 2009, 20(2): 271-289. (GONG M G, JIAO L C, YANG D D, et al. Evolutionary multi-objective optimization algorithms[J]. Journal of Software, 2009, 20(2): 271-289.)

[12] EMMERICH M, DEUTZ A, KRUISSELBRINK J, et al. Cone-based hypervolume indicators: Construction, properties, and efficient computation[C]// EMO 2013: Proceedings of the 2013 International Conference on Evolutionary Multi-Criterion Optimization. Berlin: Springer, 2013: 111-127.

[13] RACHMAWATI L, SRINIVASAN D. A multi-objective evolutionary algorithm with weighted-sum niching for convergence on knee regions[C]// Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. New York: ACM, 2006: 749-750.

[14] SINGH H K, ISAACS A, RAY T. A pareto corner search evolutionary algorithm and dimensionality reduction in many-objective optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(4): 539-556.

[15] WANG H, YAO X. Corner sort for Pareto-based many-objective optimization[J]. IEEE Transactions on Cybernetics, 2014, 44(1): 92-102.

[16] DURILLO J J, NEBRO A J. jMetal: a Java framework for multi-objective optimization[J]. Advances in Engineering Software, 2011, 42(10): 760-771.

[17] HUBAND S, HINGSTON P, BARONE L, et al. A review of multiobjective test problems and a scalable test problem toolkit[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(5): 477-506.

Many-objectiveoptimizationalgorithmbasedonlinearweightedminimal/maximaldominance

ZHU Zhanlei, LI Zheng*, ZHAO Ruilian

(CollegeofInformationScienceandTechnology,BeijingUniversityofChemicalTechnology,Beijing100029,China)

In Many-objective Optimization Problems (MaOP), the Pareto dominance has exponential increase of non-dominated solutions and the decrease of selection pressure with increasing optimization objectives. To solve these issues, a new type of dominance, namely Linear Weighted Minimal/Maximal dominance (LWM-dominance) was proposed based on the ideas of comparing multi-objective solutions by using linear weighted aggregation and Pareto dominance. It is theoretically proved that LWM non-dominated solution set is a subset of Pareto non-dominated solution set, meanwhile the important corner solutions are reserved. Furthermore, an MaOP algorithm based on LWM dominance was presented. The empirical studies proved the corollaries of the proposed LWM dominance. In detail, the experimental results in random objective space show that the LWM dominance is suitable for the MaOPs with 5-15 objectives; the experiment on comparing the number of LWM non-dominated solutions and Pareto non-dominated solutions with subjects of DTLZ1-DTLZ7 shows that the proportion of non-dominated solutions decreases by about 17% on average when the number of optimization objectives is 10 and 15.

evolutionary optimization algorithm; many-objective optimization; linear weighted function; dominant relationship; Pareto Front (PF)

2017- 04- 05;

2017- 05- 30。

國家自然科學基金資助項目(61472025,61672085)。

朱占磊(1990—),男,河南許昌人,碩士研究生,主要研究方向:進化優化算法、多目標優化; 李征(1974—),男,河北清苑人,教授,博士生導師,CCF高級會員,主要研究方向:基于搜索的軟件工程、軟件測試; 趙瑞蓮(1964—),女,山西忻州人,教授,博士生導師,CCF會員,主要研究方向:軟件測試、軟件可靠性分析。

1001- 9081(2017)10- 2823- 05

10.11772/j.issn.1001- 9081.2017.10.2823

TP18

A

This work is partially supported by the National Natural Science Foundation of China (61472025, 61672085).

ZHUZhanlei, born in 1990, M. S. candidate. His research interests include evolutionary optimization algorithm, many-objective optimization.

LIZheng, born in 1974, Ph. D., professor. His research interests include search-based software engineering, software testing.

ZHAORuilian, born in 1964, Ph. D. professor. Her research interests include software testing, software reliability analysis.