基于线性权重最优支配的高维多目标优化算法

朱占磊,李 征,赵瑞莲

(北京化工大学 信息科学与技术学院,北京 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个目标的高维多目标优化问题的结论。基于DTLZ1～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*。可行域S中所有的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非支配解集的规模。总体上,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.