高维多目标优化算法研究综述

过晓芳

（1.西安工业大学理学院，陕西 西安 710032；2.西安电子科技大学计算机学院，陕西 西安 710071）

0 引言

近年来，多目标优化问题的研究成果已广泛应用于自动控制、生产调度、网络交通、集成电路设计、化学工程和环境工程、数据库和芯片设计、核能和机械设计等众多领域。随着研究问题的复杂度越来越高，优化目标的个数也不仅仅局限于2到3个，有时往往会达到4个或者甚至更多[1]。一般意义上，当多目标优化问题的优化目标个数达到3个以上时，我们将此类多目标优化问题称为高维多目标优化问题[2]（Many-Objective Optimization，简称 MAP）。

进化算法作为一种基于种群的智能搜索方法，目前已经能够成功地求解具有2、3个目标的多目标优化问题。然而，当遇到目标数目增至4个或4个以上的高维多目标优化问题时，基于Pareto支配排序的多目标进化算法在搜索能力、计算成本和可视化方面都遇到了很大的挑战。因此，高维多目标优化问题的进化算法研究成为进化算法领域的一个难点和热点问题。

由于高维多目标优化问题的复杂性，目前对于此类问题的算法研究尚处于起步阶段，首先分析高维多目标优化问题研究存在的困难，然后对当前所提出的高维多目标进化算法进行分类概述，接下来重点总结了可降维的高维多目标优化问题的几类目标缩减进化算法，最后给出了未来研究的方向。

1 高维多目标优化问题的基本概念

定义1(多目标优化问题和高维多目标优化问题)

高维多目标优化问题是建立在多目标优化问题的基础上的。不失一般性，多目标优化问题（Multi-Objective Optimization，简称MOP）可表述[3]为：

其 x=（x1，x2，…xn）T∈X⊆Rn中是 n 维决策空间的决策向量，y=（y1，y2，…ym）T∈Y⊆Rm是 m 维目标空间的目标向量，目标函数 F（x）定义了m 个由决策空间到目标空间的映射函数，gi（x）≤0（i=1，2，…，k）是 k个约束条件。若k=0，则该多目标优化问题是一个无约束的多目标优化问题。当式(1)优化的目标数目高维过3个时，该多目标优化问题被称为高维多目标优化问题。

通常，对于单目标优化问题，其全局最优解就是目标函数达到最优值的解，但是对于多目标优化问题来说，往往这些目标 f1（x），…fm（x）的最优函数值之间会相互冲突，不能同时达到最优值。这里，为了平衡多个相互冲突的目标，采用Pareto最优解来定义多目标优化问题的最优解。

定义2(可行解与可行域)

对于一个 x=（x1，x2，…xn）T∈X⊆Rn，如果 x 满足式(1)中所有的约束条件 gi（x）≤0（i=1，2，…，k），则 x 为一个可行解。 由决策空间 X 中所有可行解构成的集合称为可行域，记为Ω={x|x∈X∧gi（x）≤0（i=1，2，…，k）}。

定义3(Pareto支配)

对于可行域Ω中的两个向量xA，xB，xA支配xB当且仅当满足

定义4(Pareto最优解或非支配解)

一个解x*∈Ω被称为Pareto最优解当且仅当在可行域Ω中x*不会被其他解x所Pareto支配，其中，≺表示解之间的支配关系。即

定义5(Pareto最优解集)

Pareto最优解集(Pareto Set，简称PS)是决策空间中所有Pareto最优解集合。即

定义6(Pareto最优前沿)

Pareto最优解集中所有Pareto最优解在目标空间中的像构成了Pareto最优前沿(Pareto Front,简称PF)。

多目标优化问题通常有非常多或者无穷多个Pareto最优解，但是要找到所有的Pareto最优解往往是不太可能的，因此，希望找到尽可能多的Pareto最优解以便为决策者提供更多的选择。在利用进化算法求解多目标优化问题的过程中，进化算法使用适应度函数引导群体向Pareto最优前沿收敛，在设计算法时需要考虑下面两个方面：一是算法的收敛性，即希望算法的求解过程是一个不断逼近Pareto最优解集的过程；二是算法的分布性，即要求所求出的Pareto最优解集中的非支配解尽可能均匀且宽广的分布在目标函数空间中。

2 高维多目标优化问题研究难点

Hughes通过实验表明基于Pareto排序多目标进化算法 (如NSGAII，SPEA2等)在具有较少目标(2个或3个)时非常有效，但是，随着多目标优化问题目标数目的不断增多，目前经典的求解一般多目标优化问题的多目标进化算法的搜索性能将大大下降，从而导致求出的近似Pareto最优解集的收敛性能急剧下降。对于此类问题的研究难点在于：

1）经典的多目标进化算法通常利用传统的Pareto支配关系对个体进行适应度赋值，但是随着目标个数的不断增多，非支配个体在种群中所占比例将迅速上升，甚至种群中大部分个体都变为非支配解，因此，基于Pareto支配的个体排序策略会使种群中的大部分个体具有相同的排序值而导致选择操作无法挑选出优良个体，从而使得进化算法搜索能力下降。

2）随着目标数目的不断增多，覆盖Pareto Front最优解的数量随着目标个数呈指数级增长，这将导致无法求出完整的PF前沿[4-5]。

3）对于高维多目标优化问题来说，当Pareto前沿面的维数多于3个时，我们就无法在空间中将其表示出来，这给决策者带来了诸多不便，因此，可视化也是高维多目标优化的一个难点问题。目前，研究者们相继提出了用决策图、测地线图、并行坐标图等方法来可视化问题的Pareto前沿面。

3 高维多目标进化算法分类

目前的高维多目标优化问题按照Pareto前沿的实际维数可以分为以下两类。一类问题是高维多目标优化问题真正的Pareto前沿所含的目标个数要小于目标空间的个数，也就是说，存在着原始目标集合的一个子集能生成与原始目标集合相同的Pareto前沿，具有该性质的原始目标集合的最小元素子集称为非冗余目标集，而原始目标集合中去掉非冗余目标集的剩余目标称为冗余目标，此类问题称为含有冗余的高维多目标优化问题，求解此类问题的方法就是利用目标缩减技术删除这些冗余目标，从而确定构造Pareto最优前沿所需的最少目标数目，以此来达到使问题得到简化的目标。与此类问题相对的是一类不含冗余目标的高维多目标优化问题，其分类结构图如1所示。

对于不含冗余目标的高维多目标优化问题来说，非支配个体在种群中所占比例随着目标个数的增加迅速上升，利用传统的Pareto支配关系大大削弱了算法进行排序与选择的效果，导致进化算法搜索能力下降。所以，处理此类问题的方法大致分为三种：一是采用松驰的Pareto排序方式对传统的Pareto排序方式进行修改，从而增强算法对非支配个体的排序和选择能力，进一步改善算法的收敛性能；二是采用聚合或分解的方法将多目标优化问题整合成单目标优化问题求解。三是基于评价指标的方法：基于评价指标的高维多目标进化算法(Indicator-based Evolutionary Algorithm简称IBEA)的基本思想是利用评价非支配解集优劣的某些指标作为评价个体优劣的度量方式并进行适应度赋值，从而将原始的高维多目标问题转化为以优化该指标为目标的单目标优化问题。直接应用一些评价指标代替Pareto支配关系以指导进化算法的搜索过程。

4 含有冗余目标的高维多目标优化问题的目标缩减算法

求解含有冗余目标的高维多目标优化问题的方法就是利用目标缩减技术寻找并删除冗余目标，从而确定构造Pareto最优前沿所需的最少目标数目。处理含有冗余目标的高维多目标优化问题的方法大致分为两种：一种是基于目标之间相互关系的目标缩减方法，另一种是基于保持个体间Pareto支配关系的目标缩减方法。下面介绍两类算法的基本思想。

（1）基于目标之间相互关系的目标缩减方法

此方法首先利用多目标进化算法获得的非支配解集合作为样本数据来分析目标之间的相互关系，然后通过分析目标间相关性的强弱来寻找冗余目标。2005年，Deb等提出了基于主成分分析法的高维多目标问题的目标缩减方法（PCA-NSGAII）。该算法将进化算法NSGAII和删除冗余目标的过程相结合，目标间的相关性是通过分析非支配集的相关系数来得到的，并由此生成目标集合中两两目标间的相互关系矩阵，然后通过分析相互关系矩阵的特征值和特征向量来提取互不相关冲突目标来表示原始目标集合，从而达到目标缩减的目的。Jaimes等提出了基于无监督特征选择技术的目标缩减方法来求解高维多目标优化问题。在该方法中，原始目标集按照目标间的相互关系矩阵划分成若干个均匀的分区。算法将目标间的冲突关系类比于点之间的距离，两个目标间的冲突性越强，则它们在目标空间中对应的两点之间的距离越远。算法要寻找的冗余目标是在联系最紧密的分区中寻找的。

（2）基于保持个体间Pareto支配关系的目标缩减方法

Brockhoff等研究了一种基于Pareto支配关系的目标缩减方法，该方法认为如果某个目标的存在与否对非支配解集中个体之间的Pareto支配关系没有影响或影响很小，则可以将其视为冗余目标删除。他们在其文献中定义了目标集合间相互冲突的定义，并提出了两种目标缩减算法δ－MOSS和k－MOSS，使得在一定误差允许下保留非支配解集中个体间的非支配关系。

另外，HK Singh提出了一种新的基于Pareto支配关系的目标缩减方法，(Pareto Corner Search Evolutionary Algorithm and Objective Reduction简称PCSEA)，该算法将一些具有代表性的处于边界区域的非支配解作为辨识冗余目标的样本点集，并通过逐个删除每个目标能否保持样本集中解的非支配性来辨识冗余目标。

高维多目标优化问题的求解算法是科学研究和工程实践领域的一个非常重要的研究课题，同时亦是目前进化算法领域的一个研究热点问题之一。但是由于问题求解复杂，当前的研究成果还较少，还有待进一步研究和探讨。今后，对于高维多目标优化问题的求解算法的进一步研究可以从以下几个方面展开：

1）引入新的非支配个体的评价机制。在高维多目标优化问题中，基于Pareto支配关系的个体排序策略由于缺乏选择压力而无法将位于不同区域的非支配个体区分开来，所以如何设计新的非支配个体的评价机制对这些个体进行比较和排序，既能保证搜索能力不受目标个数增加的影响，又能得到Pareto最优解。

2）探索新的目标缩减算法。为了减轻高维目标所带来的高额的计算成本，目标缩减技术仍然是当前求解高维多目标优化问题的一个重要方向。

3）多种策略融合。在高维多目标优化问题的求解过程中，将基于分解的技术和新的个体适应度赋值策略相结合，既能有效的增加个体在选择操作中的选择压力，又能在进化过程中更好地维持种群的多样性。

［1］Purshouse R C,Fleming P J.Evolutionary many objective optimization：An exploratory analysis[C]//Proc of 2003 IEEE Congress on Evolutionary Computation.Canberra：IEEE Service Center,2003：2066-2073.

［2］孔维健.高维多目标进化算法研究综述[J].控制与决策,2010,25(3)：321-326.

［3］公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究[J].软件学报,2009,2(20)：271-289.