偏好MOEA/D算法的研究与实现

万旭光+毛樟根

摘 要： 在科研和工程实践中存在着很多需要同时优化的两个或多个相互冲突的多目标优化问题。多数情况下，人们使用多目标优化是为了寻求某一特定方向的Pareto解，但传统的优化方法只能得出分散的全部解集，不利于辅助决策。为此，提出一种带偏好的多目标优化算法（即偏好MOEA/D算法），该算法的核心思想是将一个多目标优化问题分解成多个单目标优化问题并同时优化，在子问题通过相邻子问题信息优化的过程中加入使用者偏好，最终得到方向明确的Pareto解集。经仿真验证，该算法具有突出的求解性能，便于辅助决策，且有较高的有效性和可拓展性。

关键词： 多目标优化； MOEA/D算法； Pareto解； 信息优化； 辅助决策； 权向量

中图分类号： TN911.1?34 文献标识码： A 文章编号： 1004?373X（2018）01?0133?06

Abstract： The multi?objective problem that two or more objectives conflicted with each other should be optimized exists in scientific research and engineering practice. The multi?objective optimization is usually used to get the Pareto solution in a certain direction， but the traditional optimization method can only get the dispersive whole solution set and isn′t conducive to the assistant decision. A preference?based multi?objective optimization algorithm （preference MOEA/D algorithm） is proposed. The core thought of this algorithm is to decompose a multi?objective optimization problem into several single?objective optimization problems， and optimize the single?objective optimization problems. The user preference is added into the sub problem in the information optimization process of the adjacent sub problem to get the Pareto solution set with explicit direction. The simulation results show that the proposed algorithm has outstanding solving performance， high efficiency and strong expansibility， and is convenient for assistant decision?making.

Keywords： multi?objective optimization； MOEA/D algorithm； Pareto solution； information optimization； assistant decision?making； weight vector

0 引 言

在科学技术、经济管理和工程设计等领域的实践中，常会遇到要求多个目标在指定方向上或限定区域内进行最优化处理的问题，也就是多目标优化问题（Multi?objective Optimization Problems，MOPs）[1]。

在单目标优化中最优解通常是惟一确定的，而多目标优化问题所研究的多个目标经常是相互矛盾，相互冲突的，因此没有单一的全局最优解，而是一系列互不支配的解，称为Pareto解或非支配解集，通常均匀分布在解空间内[2]。

而在实际问题的应用中，决策者往往只对目标空间的某一区域感兴趣，因此，这就需要在这一特定区域能够得到比较稠密的Pareto解。本文优化了MOEA/D算法，在该算法的基础上加入偏好关系模型，改善了传统算法解集均匀分布的缺点，成功使解集向使用者偏好方向聚集，所得解集对解决问题更有针对性，辅助决策的意义更强，效果更好。

1 偏好MOEA/D算法的描述

1.1 算法的提出

目前有很多求解多目标优化的算法，如强度Pareto遗传算法（SPEA，SPEA?Ⅱ）、Pareto存档进化算法（PAES）[3]、非劣排序遗传算法（NSGA，NSGA?Ⅱ）[4]等，这些算法的核心目的是在尽量少的计算量的情况下，寻求较均匀的Pareto近似解。

本文要改进的是最近提出的MOEA/D算法，运用在第一象限均匀地分配权向量的方法将多目标优化问题分解成一系列单目标优化问题，每个子问题又有其邻域子问题，为了构造一个新解，每个子问题需要组合其邻域子问题的当前解的信息，同时每个新产生的解不仅要更新自身的解还要更新其邻域子问题的解[5]。选择该方法作為优化对象的原因是：该算法原理简单，易于与具体问题结合并且容易与本文提出的偏好模型相结合，是一种简单有效的进化算法。

目前对MOEA/D算法的改进和优化多集中于算法本身的功能上，很少有将偏好考虑其中的。算法本身在进行优化时，是对全目标空间进行寻优的，这样最终得到的Pareto解也是均匀分布的。若在算法寻优的过程中加入使用者的个人偏好，使寻优方向向偏好方向靠拢并最终保持一致，便可在使用者所需要的区域内产生特定需求的Pareto解。endprint

采用先验方法来处理偏好问题，在算法开始之前，由用户提供一个目标空间的偏好区域，该偏好区域首先用权向量[λi]代表用户偏好的方向，然后用偏好比率范围来表示偏好区域的大小。在算法的运行过程中，通过权向量不断调整达到Pareto解集不断收敛到偏好区域的目的。

1.2 算法的数学描述

MOEA/D的数学描述为：

[（MOP）minF（x）=f1（x），f2（x），…，fq（x）s.t. x∈Ω Ω?Rn] （1）

式中：[Ω]是变量空间；[F（x）]为向量值函数，[F（x）∈Rq；]min表示向量极小化，即向量目标[F（x）=][f1（x）， f2（x），…， fq（x）]中的各个子目标函数都尽可能极小化。

大多数情况下，多目标优化问题（MOP）的最优Pareto解位于目标空间边界。图1给出了一个二目标最小化目标函数，[xa]和[xb]点分别为问题的两个Pareto最优解，当从[xa]点移动到[xb]点时，在函数[f2]上的性能变优，在[f1]上的性能却变差。[xb]点Pareto支配[xc]点。

文献[6]提出复杂的局部偏好关系模型，该模型中，需要决策者给出起始点、终止点、无差别阈值向量、否决阈值向量，规避了仅为每个单目标分配0或1的某个权重，即全部否定或全部肯定的决策辅助情况。

本算法的提出受到了局部偏好关系模型的启发，但是本算法只需要用户给出偏好方向上的权向量和偏好比率范围（如图2所示），简化了偏好关系模型的复杂度。偏好方向權向量选定以0点为向量起始点，终止点选取起始点后的任何点，这里采用最大值作为终止点，限定偏好权向量只有一个，偏好比率范围用以限定偏好区间，假设Pareto前沿为1，那么偏好区间以偏好方向为基点占Pareto前沿长度的比率作为偏好范围比率（即偏好比率范围为0～1以内的任意值），偏好比率越大则代表偏好范围越大。

1.3 算法框架

目前有许多方法可以将一个多目标优化问题分解为一系列单目标优化问题，本文所采用的分解方法是Tchebycheff分解法[7]。

Tchebycheff分解方法：将多目标问题分解后，其中一个单目标优化问题可以表示成如下形式：

[Minimize gtexλ，z*=Max1≤i≤mλifi（x）-z*is.t. x∈Ω] （2）

式中：[λ1，λ2，…，λN]是一套均匀分布的权重向量，其中[λi≥0，i=1，2，…，m，]并且[i=1mλi=1]。这里[z*=（z*1，z*2，…，z*m）T]是一个参考点，也就是说，对每一个[i=1，2，…，m，]存在[z*=minfi（x）x∈Ω3]对式（1）中每一个Pareto占优解[x*]存在一个权值向量[λ]使得[x*]是式（2）的最优解；而且每一个式（2）的最优解都是式（1）的Pareto占优解，所以能够通过解一系列由Tchebycheff分解方法定义的不同权向量的单目标优化问题来获得不同的Pareto占优解。

以下是基于偏好的MOEA/D算法的主要流程：

输入：

1.多目标优化问题（MOP）

2.终止条件

3.N：MOEA/D分解过程中所考虑子问题的数目

4.均匀分布的N个权重向量：[λ1，λ2，…，λN]

5.T：权重向量的个数

输出：EP（外部种群）

Step1初始化：

1.1 令Pareto解集 EP=[?；]

1.2 计算任何两个向量间的欧氏距离，然后对每个权重用与其距离最近的T个权重组成其相邻集合；即对每一个i=1，2，…N，有[B（i）={i1，i2，…，iT}]，其中[λi1，λi2，…，λiT]就是[λi]的T个最近的权重向量；

1.3 随机或根据集体问题产生一个初始化种群[x1，x2，…，xN，]并计算[FVi=F（xi）]；

1.4 根据具体问题设置初始化，令[z=（z1，z2，…，zm）T]。

Step2 更新：对每个i=1，2，…，N，做如下操作：

2.1 繁殖：从[B（i）]中随机选择两个序号[k，l，]然后对[xk]和[xl]进行遗传操作，产生一个新的解[y；]

2.2 更新改进：根据具体问题对接进行调整/修补，由[y]变成[y；]

2.3 更新[z：]对每一个j=1，2，…，m，如果[zj

2.4 更新相邻集合中的解：对每一个指数[j∈B（i）]的标号，如果有[gteyλj，z≤gtexjλj，z，]则令[xj=y]并且[FVj=F（y）]；

2.5 EP的更新：从EP中删除被[F（y）]支配的所有向量，如果在EP中没有向量支配[F（y）]那么则将[F（y）]加入EP中；

2.6 偏好权向量的调整：根据偏好信息对解进行调整，在偏好区域内在解集最稀疏的地方增加一个权向量，在偏好区域外权向量最密集的地方删除一个权向量。

Step3终止条件：如果满足终止条件那么就停止并输出EP，若不满足则转向第2步。

从上述算法框架中，可以将其分为五大主要模块：输入、初始化、更新、判断、输出，本文的算法将偏好模型加在更新部分，通过不断调整权向量使解集不断收敛于偏好区域。

MOEA/D对多目标中每个分解的子问题建立对应的评价机制，能大大减少计算复杂度，加快群体的收敛速度。同时在MOEA/D算法中融入偏好模型可以将用户的偏好信息加入算法的运行过程，经过每一代权向量的调整和筛选，使得最终结果趋近在用户的偏好区域附近。

2 算法仿真及实验结果分析

本文的算法代码是在VC++ 6.0的平台上运行，运行结束后将得出数据保存，再运用Matlab作为界面展示，结果形象并易于观察变化。

2.1 测试函数的选取

本文的主要工作是为了体现优化后的偏好MOEA/D算法的解集聚拢效果，只与传统MOEA/D算法的解集作比较，不与其他多目标优化算法作对比分析。所以测试对象选取了3个两目标函数和2个可展为高维目标的函数[8]。这些测试函数被广泛引用，能较全面地体现某多目标算法的性能。SCH是比较简单的两目标优化问题，其最优Pareto前沿是非连续的，常用于测试算法在非连续区域的稳定性；ZDT1和ZDT2问题是Zitzler等学者提出的较为复杂的两目标优化问题。它们的Pareto前沿分别是凸的和非凸的，决策变量维数均为30；DTLZ2和DTLZ3问题由Deb等学者提出，可以扩展为不同目标的多目标优化问题，为了衡量算法的扩展性能，测试了高达8目标DTLZ2和DTLZ3问题。关于这些测试函数的Pareto最优前沿可以参看Coello等学者建立的相关方面网站及文献[9]。这些测试函数的数学定义如下：

1） SCH函数，变量数：1，取值范围：[-5，10]，目标函数：

[f1（x）=-x，x≤1-2+x，14f2（x）=（x-5）2]

2） ZDT1函数，变量数：30，取值范围：[0，1]，目标函数：

[f1（x）=x1，f2（x）=g（x）1-x1g（x）g（x）=1+9i=2nxin-1]

3） ZDT2函數，变量数：30，取值范围：[0，1]，目标函数：

[f1（x）=x1f2（x）=g（x）1-x1g（x）2g（x）=1+9i=2nxin-1]

4） DTLZ2函数，变量数：30，取值范围：[0，1]，目标函数：

[f1=1+gxkcosx1π2cosx2π2…cosxk-2π2sinxk-1π2]

[?]

[fk-1（x）=1+gxkcosx1π2sinx2π2fk（x）=1+gxksinx1π2g（xk）=xi∈xkxi-0.52]

5） DTLZ3函数，变量数：[k+x-1，]取值范围：[0，1]，目标函数：

[f1=1+gxkcosx1π2cosx2π2…cosxk-2π2cosxk-1π2f2=1+gxkcosx1π2cosx2π2…cosxk-2π2sinxk-1π2 ?]

[fM-1（x）=1+gxkcosx1π2sinx2π2fM（x）=1+gxksinx1π2g（xk）=100*xk+xi∈xkxi-0.52-cos20πxi-0.5]

2.2 实验设置

本文在实验中首先测试了两目标函数问题SCH和ZDT函数系列，然后对目标维数较高的DTLZ2和DTLZ3问题[10]进行相关测试，均设计了不同的偏好方向以及偏好范围参数，具体参数设置见表1。

2.3 实验结果分析

上述函数的测试结果图如图3～图5所示。每个函数给出四个测试图，归类为一组。每组的第一张图为测试在传统MOEA/D算法无偏好情况下被测函数所获得的全部Pareto解集；第二张图给出加上偏好后的解集对比试验结果；第三张图针对偏好，选择当偏好方向相同而偏好区域不同时解集的对比结果；第四张图为偏好区域相同但偏好方向不同时的解集对比结果。

每张图中蓝色的点是偏好MOEA/D方法得到的在偏好区域内的解集，黑色的线代表标准Pareto前沿。

从图中可以清楚地看出，随设定偏好范围的增大则偏好解集范围增大，改变偏好方向则偏好解集也随之改变方向，从上述的两目标函数中可以发现，无论函数的形状如何或是否连续，偏好模型在MOEA/D算法中能够有效地使解集收敛并约束在偏好区域以内均匀分布。同时，加入偏好之后函数的解集明显收敛到了偏好区域范围内，并且在Pareto前沿上分布较均匀。随着在测试中改变偏好方向，解集明显以新的偏好方向为中心分布，在测试中改变偏好大小，偏好解集的范围也随之改变。证明了该算法能够根据使用者的决策预期引导算法朝着预先设定的偏好方向进行优化，并能调整偏好范围的大小。

为了测试函数的可扩展性，继续测试了8目标的DTLZ2和DTLZ3问题[11]，测试结果如图6，图7所示。

针对上述2个三维函数，通过改变函数的偏好方向和偏好范围，可以看出函数可以均匀分布于偏好范围内并随着偏好范围大小做出相应改变，验证了算法的可扩展性。

从以上5个测试函数中可以看出，偏好MOEA/D算法能有效地将用户的偏好信息加入算法的进化过程中，根据用户的偏好方向和偏好范围求出相应方向和范围的解集，获得更优的辅助使用者决策的效果。

3 结 论

本文优化了传统的MOEA/D算法，在原有的基础上结合偏好关系模型，产生偏好MOEA/D算法，并介绍了其算法框架，利用具有代表性的两目标函数SCH及ZDT1，ZDT2验证了其有效性，进一步使用八维函数DTLZ2和DTLZ3进行测试以验证其可扩展性。实验结果表明，新算法能够根据用户的偏好区域范围搜索相应的解集，并且具有较快的收敛速度和较好的均匀性保持能力，辅助决策的意义更强，效果更好。

参考文献

[1] PARETO V. Cours d′economies olitique [M]. Lausanne： Rouge， 1896.

[2] ZHANG Q， LI H. MOEA/D： a multiobjective evolutionary algorithm based on decomposition [J]. IEEE transactions on evolutionary computation， 2007， 6（11）： 712?731.

[3] BRANKE J， DEB K， MIETTINEN K， et al. Multiobjective optimization： interactive and evolutionary approaches [M]. New York： Springer， 2008： 405?433.

[4] MOLINA J， SANTANA L V， HERNANDEZ?DIAZ A G， et al. g?dominance： reference point based dominance for multiobjective metaheuristics [J]. European journal of operational research， 2009， 197（2）： 685?692.

[5] KIM J， HAN J， KIM Y， et al. Preference?based solution selection algorithm for evolutionary multiobjective optimization [J]. IEEE transactions on evolutionary computation， 2012， 16（1）： 20?34.

[6] JASZKIEWICZ A， SLOWINSKI R. The light beam search approach?an overview of methodology and applications [J]. European journal of operation research， 1999， 113（2）： 300?314.

[7] 肖晓伟，肖迪，林锦国，等.多目标优化问题的研究概述[J].计算机应用研究，2011，28（3）：805?808.

XIAO Xiaowei， XIAO Di， LIN Jinguo， et al. Research overview of multi target application research [J]. Computer optimization problems， 2011， 28（3）： 805?827.

[8] 丁大维.基于MOEA/D的优化技术及其在天线优化设计中的应用[D].合肥：中国科学技术大学，2015.

DING Dawei. MOEA/D based optimization technology and antenna optimization design application [D]. Hefei： University of Science & Technology China， 2015.

[9] 张冬梅，龚小胜，戴光明，等.求解复杂多目标优化问题MOEA/D?GEP算法[J].华中科技大学学报（自然科学版），2012，40（4）：33?36.

ZHANG Dongmei， GONG Victory， DAI Guangming. Solving complex multi?objective optimization problem MOEA/D?GEP algorithm [J]. Journal of Huazhong University of Science and Technology （natural science edition）， 2014， 40（4）： 33?36.

[10] 神显豪，李军，张祁.基于改进MOEA/D算法的WSN覆盖优化方法[J].计算机应用研究，2016，33（4）：1203?1206.

SHEN Xianhao， LI Jun， ZHANG Qi. WSN overlay optimization method based on improved MOEA/D algorithm [J]. Computer application research， 2016， 33（4）： 1203?1206.

[11] 胡旺，Gary G.YEN，张鑫.基于Pareto熵的多目标粒子群优化算法[J].软件学报，2014，25（5）：1025?1050.

HU Wang， YEN G G， ZHANG Xin. Multi objective particle swarm optimization algorithm based on Pareto entropy [J]. Journal of software， 2014， 25（5）： 1025?1050.endprint