mops

浅析多目标优化问题

作者：张淑艳段鹏松邹卫琴

来源：《科技视界》2013年第14期

张淑艳1段鹏松1邹卫琴2

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

330000）

【摘要】本文介绍了多目标优化问题的问题定义。通过对多目标优化算法、评估方法和

测试用例的研究，分析了多目标优化问题所面临的挑战和困难。

【关键词】多目标优化问题；多目标优化算法；评估方法；测试用例

多目标优化问题MOPs(MultiobjectiveOptimizationProblems)是工程实践和科学研究

中的主要问题形式之一，广泛存在于优化控制、机械设计、数据挖掘、移动网络规划和逻辑电

路设计等问题中。MOPs有多个目标，且各目标相互冲突。对于MOPs，通常存在一个折衷的解集

(即Pareto最优解集)，解集中的各个解在多目标之间进行权衡。获取具有良好收敛性及分布性

的解集是求解MOPs的关键。

1问题定义

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

2多目标优化算法

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

第一类算法，将MOPs转化为单目标优化问题。算法为每个目标设置权值，通过加权的方式

将多目标转化为单目标。经过改变权值大小，多次求解MOPs可以得到多个最优解，构成非支配

解集[1]。

第二类算法，直接求解MOPs。这类算法主要依靠进化算法。进化算法这种面向种群的全局

搜索法，对于直接得到非支配解集是非常有效的。基于进化算法的多目标优化算法被称为多目

标进化算法。根据其特性，多目标进化算法可以划分为两代[2]。

（１）第一代算法：以适应度共享机制为分布性策略，并利用Pareto支配关系设计适应度

函数。代表算法如下。VEGA将种群划分为若干子种群，每个子种群相对于一个目标进行优化，

最终将子种群合并。MOGA根据解的支配关系，为每个解分配等级，算法按照等级为解设置适应

度函数。NSGA采用非支配排序的思想为每个解分配虚拟适应度值，在进化过程中，算法根据虚

拟适应度值采用比例选择法选择下一代。NPGA根据支配关系采用锦标赛选择法，当解的支配关

系相同时，算法使用小生境技术选择最优的解进入下一代。

（２）第二代算法：以精英解保留机制为特征，并提出了多种较好的分布性策略。代表算

法如下。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前沿面可在

(/~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前沿面可在网站

(/staff/qzhang/)下载。

5挑战和困难

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

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

（２）对多目标优化算法的评估需要能够客观反映算法优劣的评估方法和一组测试用例。

评估方法和测试用例的选择和设计，是一个研究的关键问题。

（３）现有多目标优化算法各有其优缺点，某个算法对求解一个问题是有效的，而对求解

另一个问题可能是无效的。那么如何使各算法的优缺点互补也是一个尚待研究的问题。

6结论

MOPs在工程实践和科学研究中是非常重要的。本文通过对MOPs的问题定义、多目标优化

算法、评估方法、测试用例四个方面对MOPs的相关问题进行阐述，最后分析了求解MOPs的挑

战和困难。

【参考文献】

［１］carchstrategiesinmulticriterion

optimaldesign[J].StructuralandMultidisciplinaryOptimization,1992,4(2):99-107．

［２］CoelloCoello,ionaryMulti-ObjectiveOptimization:A

HistoricalViewoftheField[J].IEEEComputationalIntelligence

Magazine,2006,1(1):28-36．

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

［４］公茂果,焦李成,杨咚咚,马文萍.进化多目标优化算法研究[J].软件学

报,2009,20(2):271－289．

［责任编辑：王静］