基于分解的多目标优化算法研究与分析

弓佳明，章腾浩，许丽娟

（广州华商学院数据科学学院，广州 511300）

0 引言

时代造就了科技水平的提高，人类文明的不断推进。无论是在医学、金融，还是交通等方面都出现了许多优化问题。为此，研究人员研究了一种模拟自然进化算法（EA）的随机搜索算法，由于这类算法在科研领域有很强的适配性，该算法被广泛用于解决非常复杂的非线性结构。然而现实中的优化问题通常是拥有多个属性且相互联系的，例如：一个国家想要强大，经济实力和国防力量是支撑。国家的经济发展与其军事国防发展间的优化关系。国家发展好了，那么经济就会对其军事力量提供更好的资金支持；反过来，只有武器力量强大了才能在世界上站稳脚跟，更好地发展经济。其两者是相互促进，密不可分的。同时，这两者又是相互矛盾的，倘若过度投资国防不发展经济，就会头重脚轻，到最后国防资金供给不足；反之亦然，落后就要挨打，处于水深火热之中的经济更加燃不起火苗。所以，关键在于衡量这两者之间的投入比例使其达到最优解。

为了实现总目标的最优化，研究者们往往需要对彼此矛盾的影响因子进行综合考虑，于是便衍生了多目标进化算法。MOEA 的种类有许多，本文只研究基于分解的多目标优化算法（MOEA/D）。根据多目标演化算法将多目标问题（MOPS）转化为一些单个体，之后利用小个体的邻近子问题的关系进一步重复更新迭代［1］。由于分解成一个个小目标，这使得该方法在处理相关联系的信息就不会进入极端的局部最优，而这些个体目标所组成的结果最终会接近最优解边界（PF），即一组Pareto最优解集。

1 基于分解策略的多目标优化算法概述

1.1 多目标优化问题（MOP）

在解决多目标优化问题时，有些问题是难以解决的。这是因为多目标优化问题（MOPs）不同于单目标优化（SOPs），在最优解上多目标优化问题具有多个最优解。那么接下来的问题即是，对于这些最优解集哪些才是解决问题所需要的，如何构造这些最优解集？为了解决这些问题，研究者们给出了这样的描述。

对于一个具有m个目标，n维决策变量的MOPs，其数学模型［2］为

其中x=(x1,…,xm)∈Ω 被称为m维决策向量，为一组个体。在目标进化中优化函数向量minF(x)=(f1(x),f2(x),…,fk(x))T，k是目标函数的个数。在多目标优化问题中，对于不同的子目标函数可能会有不同的最优解。总结起来归为三类情况：①最大化所有子目标函数；②最小化所有子目标函数；③最小化部分子目标函数，最大化其他子目标函数。

1.2 Pareto最优解和最优边界

Pareto 最优解：多目标的最优解通常被称为Pareto最优解。它是由经济学领域的专家为提高经济上的效率问题和收入方面的分配方法而研究得到的，是属于资源分配的“乌托邦”，在进行分拨的过程中整体趋势向着好的方向发展，并不会存在一个由于其他的优化而恶化，这就是帕累托最优化。

Pareto 最优边界：在目标空间中，多目标的最优解集就是目标函数的切点。它们总是落在搜索区域的边界上。如图1所示。A、B、C、D、E和F所在曲线便是最优解边界，而这些实心点所组成的集合即为Pareto最优解集，其余点便不属于该集内。

图1 最优边界

1.3 分解策略

分解策略是用传统数学规划解决多目标优化问题的一个基本思路。在给定权重偏好或者参考点信息的情况下，分解法通过线性或者非线性方法将原MOPS中的各个目标聚合得到一个个单目标优化问题，并且使单目标优化方法求出一个Pareto 最优解［3］。为了得到整个PF 的逼近，Zhang等［4］在2008年提出了基于分解的多目标优化算法，该算法在科研领域得到了广泛使用，成为目前最具影响力的MOEA/D之一。

1.4 基于分解策略的多目标优化算法的分解方法

权重聚合方法（Weighted Sum Approach）［4］是一种常用的线性多目标聚合方法，其目标函数的聚合形式定义为

如式（2），x∈Ω为决策向量，λ=(λ1,λ2,…,λm)为权重向量，满足λi≥0,i=1,2,…,m且=1如图2 所示，绿色为等值线，红色为权重向量，等值线与方向向量垂直。当最小化问题的PF 为凸状时，单个最优等值线会与PF 相交于一个切点。该类聚合方法所得到的结果能够较好符合贴近PF 的要求，这使得研究者们遇到高维度的空间难题时用该类方法解决好这一复杂问题。

图2 权重逼近

权重聚合方法也有其缺点，那就是当最小化问题的Pareto前沿面为凹状时，所有最优解位于Pareto面的边缘地带。这是因为Pareto 面中间凹下去那部分的解会与其他的解“格格不入”，形成了较大的差值比较，从而降低了最终结果的精确度，即相比Pareto 面的边缘具有更大的函数值。所以权重聚合方法并不能很好地解决Pareto面为凹状的情况。

基于惩罚的边界交叉方法（Boundary Inter⁃sectionApproach）［5］是于2007 年被提出的基于方向的分解法，其定义如下：

边界交叉有一个缺点就是必须处理等式约束，为此引入了惩罚参数θ，数学描述见公式（3），λ和z*分别是权重向量和参考点，l1是F(x)投影点到参考点的距离，其中θ>0是预设参数，用来处理等式约束。

切比雪夫分解法（Tchebycheff Approach）是一种非线性的多目标聚合方法［6］，其聚合函数定义如下：

其中z*为目标函数f（x）的最小值，将其定义z*=min{fi(x)|x∈Ω}；λ定义与上述的权重聚合的λ定义一致。

2 切比雪夫分解法

2.1 切比雪夫分解法概述

切比雪夫分解法无论是解决Pareto凸状问题还是凹状问题都具有良好的适配性，一定程度上解决了权重聚合方法不能适应凹状问题的缺点。其数学描述如公式（4）所示，=1，其中z*为理想点，同时也为目标函数的最小值；w为权重向量，x∈Ω 为决策向量，T为权重向量，其中满足wi≥0,i=1,2,…,m。

如图3 所示，坐标轴是两个目标函数f1和f2。首先根据定义式分别计算w1*|f1(x)-z1|和w2*|f2(x)-z2|，把计算出来的最大值保留。保留的这个数值越大，说明在这个目标函数上它离点z*越远。若w1*|f1(x)-z1|较大，逐渐改变自变量x，使得这个值离点z*越来越近，直到达到PF 上对应的点为止。这个过程其实就是求函数gtche=w1*|f1(x)-z1|的最小值。若这个较大的定义式达到了它的最小值，那么w2方向的式子也就相应地达到它的最小值。其他的权重向量都是采用这种方式不断地进行更新迭代，直至获得Pareto最优解集。

图3 切比雪夫方法

这种方法类似于物理上力的分解平行四边形法则和Pareto最优解思想的结合。通过对一个权重向量上任意点基于目标函数进行分解，将其分解成两个方向，当其中较大的那个函数通过改变x的值达到最小值时，相应的另外的函数也就达到了理想值［7］。从原来的状态到另一种状态的变化过程中，在原有情况下没有使其变坏的前提下，使得其中的某一项变得更好。此时该函数已达到Pareto边界的逼近，即最优解。

2.2 基于切比雪夫分解法的MOEA/D算法框架

与其他的MOEA算法不一样的是，MOEA/D算法是属于比较开放的算法类型，它会在分解的基础上在附近选择一个父个体，通过穿插变异得到一个新的子个体，且这一个体经过一定的运算法则更新附近种群。其基本思想——通过将整体分为一个个小个体，这些子问题之间存在的相邻联系，相互协作做到同时优化这些子问题，最终满足无限接近于PF。

基于分解的MOEA/D 算法框架最大的特点便是分解与合作。要了解基于切比雪夫分解法的MOEA/D 算法框架首先要定义其数据结构。根据其定义式所需，其数据结构定义如下：

（1）首先定义关于切比雪夫分解法所需的权重向量集合{w1,w2,…,wi}和理想点z；

（2）对于每个子问题分配一个个体，然后将这些个体集合{x1,x2,…,xi}组合成一个进化种群Q；

（3）用于存储逼近Pareto 边界最优解的精英种群EQ；

MOEA/D的算法流程如图4所示。

图4 MOEA/D算法流程图

初始化：在进行初始化的时候需设EQ=Ø；确定每个权重wi的k个相邻的权重向量{w1,…,wk}，同时计算初始化种群的目标向量（通过计算权重向量之间的欧几里得距离来计算子问题的邻域关系）；初始化理想点z*。

更新：更新操作是对原来的个体进行交叉变异，即从邻域中随机挑选两个个体进行基因重组，从而产生新的个体（其中在邻域中修正约束解时，邻域的大小和替换个体的次数将会影响到这个种群的多样性与收敛性），如此往复使其逐步逼近Pareto边界。

2.3 算法相关代码示例

由于进化算法相对复杂，针对采用Tcheby⁃cheff 的MOEA/D 实验方法将两个多目标测试问题进行运算举例说明，如算法1所示。

3 MOEA/D的性能评价

3.1 MOEA/D的性能评价的概述

通常在对一个多目标进化算法的性能进行评价时，总是需要有一套能客观评价MOEA/D优劣性的评价方法或者工具，同时也要选取一组较有代表性的测试来说明问题。

一般来说，衡量MOEA/D 性能的评价有两个标准。第一是MOEA/D 的效果，具体来说即是目标函数所求得的Pareto最优解的质量，而这主要取决于它的收敛结果和分布结果；第二是MOEA/D 的效率，由于多目标优化算法的复杂性影响着算法的效率，所以也要考虑硬件问题，比如电脑CPU 运算算法的时间效率问题或电脑的空间存储问题。

3.2 MOEA/D的性能评价的方法

通常采用两种方法来对MOEA/D 的性能进行评价，一种是对MOEA/D 的性能进行理论上的分析，另外一种是在实验的过程中对MOEA/D的性能进行测试和比较。一般来说，MOEA/D算法的运行效率和收敛性是可以通过理论方法来进行分析的，但是由于目前对MOEA/D 收敛性的研究还不是特别深入，相关的论证还局限于时间趋近于无穷大的状态。因此很难从理论上去判断它们哪一个更加适合。所以在现实研究中，研究者们通常采用理论分析和实验相结合的方法对一个MOEA/D算法进行综合评价。

在众多MOEA/D 性能评价的方法中又可以归类为三大类：

（1）收敛性：评价解集和真正的最优边界的逼近程度；

（2）分布性：评价解集的多样性和分布性；

（3）综合性能：综合考虑解集的收敛性和分布性。

要根据具体问题来具体分析，针对算法的相关特征选取与之适应的评价方法。

3.2.1 收敛性评价方法

（1）世代距离（Generationl Distance，GD）

世代距离表示PFknown和PFtrue之间的间隔距离，PFtrue是问题的真正最优边界，数值越大，离真正最优边界的偏差越大，相应的收敛性也越大。其定义式见式（5），其中n是PFknown中向量的个数；当p=2时，为欧氏距离。

如图5 所示，di的点距离Pareto 最优解集非常接近，结合公式可知它的收敛性比较好。但是世代距离也有缺点——那就是在一些解集分布性能不好的情况下，可能会影响到最终结果。

图5 世代距离

（2）基于距离的趋近度评价法［8］

其原理是通过计算两个解集之间的最短距离来测量算法的近似值，该距离是最优的或可参考的。距离越小，说明计算结果和真实就越接近。在估计算法的收敛程度时，这种方法需要定义一个集作为运算的参照，可以是最优解集，也可以是过去几代的非支配集。通常很难在许多优化问题上得到一组最优解，所以参考集都是选取历代非支配集并集的非支配集。

（3）C-metric解集覆盖率［9］

Zitzler 等［9］提出通过计算两个不同解集的覆盖率，然后对它们进行比较，在MOEA/D 的论文中也用到了该性能指标。其定义为：对于两个相近解集A和B，C（A,B）是B被A中至少一个解支配的解占B中解数量的比值。C（A,B）=100表示B中所有的解都被A中至少一个解支配。C（A,B）=0 表示B中没有解被A中的解支配。但是C（A,B）不一定等于1-C（B,A）。其公式为

3.2.2 对于分布性评价方法

（1）空间评价方法［10］

空间评价方法是用来评价近似解集中个体在目标空间的分布情况，其评价函数定义式如下：

其中非支配边界上两个连续向量的欧几里得距离，d是这些矢量Euclidean-distance 的平均值，PF是已知的Pareto 最优解面。在此基础上提出了一种新的多属性决策分析中关于方案排序和择优问题的综合决策模型，并给出相应的算法步骤与实现过程。最后通过一个算例说明了该方法的有效性与可行性。值得一提的是，这种评价方法只适用于二维目标空间，对于高维目标并不能很好地解决评价问题。

（2）对空间评价法的进一步优化

通过计算一个给定点到它最近邻居的距离来解决高维目标的问题［10］。改进后的指标如下：

3.2.3 对于综合性评价方法

（1）超体积指标——Hypervolume指标［7］

它可以根据超过体积的单个值来判断群解的质量，是唯一已知的符合帕累托主导概念的指标。超体积是估计近似解集收敛性和多样性的综合指标。如图6所示。

图6 超体指标

超体积值越大，该解集越好。研究者们基于上述研究结果提出了一种新的快速迭代算法：超体积迭代法。该方法通过引入两个参数来提高收敛速度。数值实验表明该算法具有较好的性能。超体积的主要优点之一是它能使解接近于单个数的最优集合，并能在一定程度上反映解在目标空间中的分布。缺点是计算过度复杂，而且参考点选取对精确度有一定的影响。

（2）反转世代距离［11］

该方法基于世代距离的逆向思考。首先，将问题转换为一个非线性规划模型，然后利用基于遗传算法（GA）的进化策略求解，这就改进了传统遗传算法收敛速度慢的缺陷。最后给出算例，说明其有效性和可行性。它表示从Pareto最优解集的个体到算法得到的非支配解集的平均距离。其定义式为

IGD值越小，说明算法的综合性能就越好。倘若分布性能不好，计算得出的IGD值相对会比较大，如果解集收敛性好并且分布也均匀，那么得到的IGD值必然很小。由此可得到的IGD指标既可以表示MOEA 的收敛性，同时也可以反映出MOEA的分布情况。

图7 反向世代距离

4 MOEA/D在现实中的应用

4.1 MOEA/D产生背景

近来，出现了许多优秀的多目标进化算法，研究者们研究这些算法的目的是希望种群尽可能地逼近PF。但是恰当地将计算资源分配到不同的前沿部位是目前为止的难点所在，所以他们通常都不能沿PF产生一组分布均匀的解，之所以这样，其主要原因是多目标优化是个复杂的问题，子目标之间又相互联系，稍有不注意优化一个目标就可能恶化其他目标，想要同一时间使所有目标达到最优是不可能的。为此，我们就需要选取一组Pareto最优解来作为结果的候选解。

为了解决这些问题，Zhang 等［4］便提出了基于分解的多目标优化算法，通过一些偏好或者规则得到这些子问题的最优解，整体趋势向优，也就是Pareto最优解集。

4.2 应用概述

在环境发展方面：联合国开发计划署的援华项目“华北水资源管理”中，对华北宏观经济水资源规划进行辅助调控，该项目是一个基于宏观经济水资源系统规划理论的大型综合性模型。包括北京、天津、河北、山东等省市，并且考虑区内国民生产总值、就业率、生物化学需氧量的排放量最小，粮食产量最大四个因素。工程和节水措施方面采用的是0～1 变量，是一个0～1 混合整数线性模型。后来史慧斌等［12］在此基础上对其用Tchebycheff 原理与求解多目标交互相结合，在切比雪夫求解构成中增加了群决策，对原有理论进行了扩展研究。

在人工智能方面：该类算法主要应用于对人工智能的路径规划问题、模糊规则、故障诊断、机械臂等。例如，机械臂的应用多出现在制造车间或者一些危险地带，解决人类难以解决的问题，但由于机械臂的操作是多约束的优化函数，与传统的算法相比，MOEA/D 在解决复杂优化问题时往往会起到“大事化小，小事化了”的奇效。

在机动车行驶路径方面：在解决行驶路径问题时，通常把服务对象称之为顾客，以满足顾客需求为服务，确定好顾客的所在地。在面对一系列位置分散的顾客点，满足一定限制条件时，通过算法分解得出最优的行车路径，使车辆达到最优满足顾客需求又使车辆数量较少。

5 结语

本文首先阐述了什么是多目标优化问题，然后介绍了多目标优化问题所需要面对的事情，那就是如何在原有状态不恶化的情况下，改变某些因素使得整体趋势变得更加符合研究者的需求，由此引出Pareto最优解的概念以及更加抽象化的Pareto 最优边界。为了达到Pareto 最优边界的逼近，Zhang 等［4］提出了MOEA/D 这一思想，将传统的数学模型引入到多目标优化算法中来，这一思想的提出掀起了研究者们对多目标进化算法的科研热潮。而分解的策略方法又详细分为了三种——权重求和方法、边界交叉方法和切比雪夫方法。

其次，本文研究了基于分解的多目标优化算法的性能评价方法。要评价多目标进化算法有两个标准，一是MOEA/D 的最终效果取得的最优解集的质量是否优秀；二是算法的效率，从数据结构的知识来说，即是时间复杂度和空间复杂度问题。MOEA/D 性能评价方法主要从收敛性、分布性、综合性能三个方面考虑。在这三个方面，本文罗列了一些研究常用的评价方式，包括世代距离法、基于距离的趋近度评价法、空间评价法、超体积指标等。