浅析多目标优化问题

张淑艳 段鹏松 邹卫琴

（1.郑州大学 软件技术学院，河南 郑州 450000；2.江西理工大学 软件学院，江西 南昌 330000）

多目标优化问题MOPs(Multi objective Optimization Problems)是工程实践和科学研究中的主要问题形式之一，广泛存在于优化控制、机械设计、数据挖掘、移动网络规划和逻辑电路设计等问题中。MOPs有多个目标，且各目标相互冲突。对于MOPs，通常存在一个折衷的解集(即Pareto最优解集)，解集中的各个解在多目标之间进行权衡。获取具有良好收敛性及分布性的解集是求解MOPs的关键。

1 问题定义

最小化MOPs的一般描述如下：

min F（x）＝（f1（x），f2（x），…，fm（x））

其中解x＝（x1，x2，…，xn）∈Ω为在决策空间Ω中的n维决策向量，f1（x），f2（x），…，fm（x）为 m 个相互冲突的目标函数。 对于解 x1，x2∈Ω，x1支配 x2（记作 x1≻x2），当且仅当∀i∈（1，2，…，m）使得 fi（x1）≤fi（x2），且∃i∈｛1，2，…，m｝，使得 fi（x1）≤fi（x2）。解 x*∈Ω 为 Pareto 最优解，当且仅当不存在解x∈Ω，使得x≻x*。Pareto最优解的集合称为Pareto 最优解集（记作 P*），P*＝｛x*∈Ω｜﹁∃x∈Ω：x≻x*｝。 Pareto 最优解集P*在目标空间的映射称为真实Pareto前沿面 （记作PF*），PF*＝｛F（x*）＝（f1（x*），f2（x*），…，fm（x*））｜x*∈P*｝。若 x1≻x2，则称 x2为支配解。解集P'被称为非支配解集，当且仅当P'中不含支配解。

2 多目标优化算法

目前，大量算法用于求解MOPs。通常，可以将求解MOPs的算法分为两类。

第一类算法，将MOPs转化为单目标优化问题。算法为每个目标设置权值，通过加权的方式将多目标转化为单目标。经过改变权值大小，多次求解MOPs可以得到多个最优解，构成非支配解集[1]。

第二类算法，直接求解MOPs。这类算法主要依靠进化算法。进化算法这种面向种群的全局搜索法，对于直接得到非支配解集是非常有效的。基于进化算法的多目标优化算法被称为多目标进化算法。根据其特性，多目标进化算法可以划分为两代[2]。

（1）第一代算法：以适应度共享机制为分布性策略，并利用Pareto支配关系设计适应度函数。代表算法如下。VEGA将种群划分为若干子种群，每个子种群相对于一个目标进行优化，最终将子种群合并。MOGA根据解的支配关系，为每个解分配等级，算法按照等级为解设置适应度函数。NSGA采用非支配排序的思想为每个解分配虚拟适应度值，在进化过程中，算法根据虚拟适应度值采用比例选择法选择下一代。NPGA根据支配关系采用锦标赛选择法，当解的支配关系相同时，算法使用小生境技术选择最优的解进入下一代。

（2）第二代算法：以精英解保留机制为特征，并提出了多种较好的分布性策略。代表算法如下。NSGA－II降低了非支配排序的复杂度，并提出了基于拥挤距离的分布性策略。SPEA2提出了新的适应度分配策略和基于环境选择的分布性策略。PESA－II根据网络超格选择个体并使用了基于拥挤系数的分布性策略。

近年来，在求解MOPs上，新的算法框架也在不断提出。粒子群算法、分布估计算法、分解算法等已被逐渐用于求解MOPs。

3 评估方法

求解MOPs通常得到一个非支配解集，而解集的评估相对于单个解的评估更加复杂。目前存在多种方法评估非支配解集的质量。通常，对非支配解集的评估分为两个方面[3]。一方面，是收敛性，即评估非支配解集在目标空间与真实Pareto前沿面的趋近程度。常用方法有错误率、覆盖率、世代距离、高维空间及其比率、基于聚集距离的趋近度评价方法等；另一方面，是分布性，即评估非支配解集在目标空间分布的广度和均匀度，常用方法有空间评价方法、基于个体信息的评价方法、网格分布评价方法、个体空间的分布度评价方法、基于聚类的评价函数等。

4 测试用例

算法性能的评估需要客观的测试用例。Schaffer、Kursawe和Deb分别在1985年、1991年和1999年提出了较简单的两目标优化测试用例SCH、KUR和DEB。Zitzler、Deb和Thiele在2000年提出了6个两目标优化测试用例 ZDT1～ZDT6。 Deb、Thiele、Laumanns和 Zitzler在2002年提出了 7个多目标优化测试用例 DTLZ1～DTLZ7，DTLZ1～DTLZ7的决策变量和目标数可以扩展到任何数目[4]。上述测试用例均无约束，其Pareto最优解集和真实Pareto前沿面可在(http://www.cs.cinvestav.mx/～emoobook/)下载。 Liu在 2008年为 CEC2009提出了 23个更加复杂的测试用例 CF1～CF10、R2－DTLZ2、R3－DTLZ3、WFG1 和CF1～CF10。其中CF1～CF7为7个无约束两目标优化测试用例，CF8～CF10 为 3 个无约束三目标优化测试用例，R2－DTLZ2、R3－DTLZ3、WFG1为3个无约束五目标优化测试用例，CF1～CF7为7个带约束两目标优化测试用例，CF8～CF10为3个带约束三目标优化测试用例。CEC2009的测试用例的问题描述、Pareto最优解集和真实Pareto前沿面 可 在 网 站 (http://dces.essex.ac.uk/staff/qzhang/moeacompetition09.htm)下载。

5 挑战和困难

由于MOPs与现实应用的密切相关性，MOPs面临许多研究课题：

（1）现有大部分求解MOPs的算法都基于进化算法，新的算法框架亟待提出。

（2）对多目标优化算法的评估需要能够客观反映算法优劣的评估方法和一组测试用例。评估方法和测试用例的选择和设计，是一个研究的关键问题。

（3）现有多目标优化算法各有其优缺点，某个算法对求解一个问题是有效的，而对求解另一个问题可能是无效的。那么如何使各算法的优缺点互补也是一个尚待研究的问题。

6 结论

MOPs在工程实践和科学研究中是非常重要的。本文通过对MOPs的问题定义、多目标优化算法、评估方法、测试用例四个方面对MOPs的相关问题进行阐述，最后分析了求解MOPs的挑战和困难。

［1］P.Hajela and C.Y.Lin.Genetic search strategies in multicriterion optimal design[J].Structural and Multidisciplinary Optimization,1992,4(2):99－107.

［2］Coello Coello,C.A.Evolutionary Multi－Objective Optimization:A Historical View of the Field[J].IEEE Computational Intelligence Magazine,2006,1(1):28－36.

［3］郑金华.多目标进化算法及其应用[M].北京：科学出版社，2007.

［4］公茂果,焦李成,杨咚咚,马文萍.进化多目标优化算法研究[J].软件学报,2009,20(2):271－289.