多目标优化算法综述
高鹏
（华北电力大学，电气与电子工程学院，北京，102206）
Overview Of Multi-objective Optimization Algorithms
Gao peng
(College of Electric and Electronic Engineering,North China Electric Power University,
Beijing,102206)
Abstract: Background of Multi-objective optimization algorithms is summarized in this paper. Then mathematical description to the problem of Multi-objective optimization is discussed. The advantages and disadvantages of traditional algorithm for multi-objective optimization problem are compared and classifications of the algorithms are discussed. Moreover, Multi-objective evolutionary algorithms are analyzed, such as NSGA、PAES、SPEA; At last, the clonal selection algorithms based on immune principle is analyzed and some important research areas of Multi-objective optimization are addressed.
Keywords: multi-objective optimization, evolutionary algorithms, artificial immune algorithms, Pareto non-dominance
摘要：文章通过阐述多目标优化算法的研究背景,给出多目标优化问题的数学描述，并对多目标优化算法进行分类，分析传统算法的特征和不足之处。在此基础上引入多目标优化问题的进化算法，包括NSGA、PAES、SPEA等。最后介绍基于免疫原理的克隆选择优化算法，并对多目优化算法的研究趋势作了展望和预测。
的其它目标如环境污染等方面的损失。航天器总
体设计中的有效载荷、射程、推力等指标参数的综合是一个典型的多目标的优化问题；控制工程中控制系统的稳、准、快等时域指标与稳定域度、系统带宽等频域特性的综合问题也是一个多目标工程优化设计问题；此外社会发展与国民经济的中长远发展计划的优化与决策问题也是多目标问题。一般说来，科学与工程实践中的许多优化问题大都是多目标的优化与决策问题。 典型的多目标问题求解思路是对多目标问题进行数学建模，将其抽象为数值函数的优化问题。我们知道当该函数在连续、可求导、低阶的简单情况下可解析地求出其最优解，但由于问题种类繁多，影响因素复杂，这些函数通常会显示出不同的数学特征，如是否连续，是否有凸性质等，所以大部分情况下需要通过数值计算的方法进行近似优化计算。尽管我们对函数优化问题已进行多年研究，但至今尚无一种能处理各种不同的复杂函数，又具有良好求解结果的数值计算方法。特别是当问题规模较大时，优化计算的搜索空间也随之急剧扩大，要严格地求出其最优解几乎成为不可能。所以需要研究出一种能够在可接受时间和可接受的精度范围内，求出数值函数近似最优解的方法或通用算法已成为必须。 本文首先阐述多目标进化算法的研究背景,给出多目标优化问题的数学描述；然后,分析传统多目标算法的特征并指出其不足,包括加权法、目标规划法。并在此基础上进一步介了多目标优化的进化算法，包括NSGA、PAES、SPEA等，
关键词：多目标优化,进化算法,免疫算法,Pareto非劣最优
1.引言
人类改造自然的方案规划与设计过程总体上反映了最大化效益、最小化成本这一基本优化原则。最大化效益、最小化成本本质上是一个多目标的优化问题。效益可能包括多种效益，如经济效益、政治效益与社会效益等；成本或损失也可能包括生产成本与非生产成本，或与此相关联
并逐一比较其特点。最后文章介绍基于免疫原理的克隆选择优化算法，给出算法总体框图，并对多目优化算法的研究趋势作了展望和预测。
2. 多目标优化
多目标最优化(Multi-objective optimization problem，Mop)也称为多标准优化,多绩效或向量(vector)优化问题。它的最早出现，应追溯到1772年的Franklin提出的多目标矛盾如何协调的问题，国际上一般认为多目标最优问题最早由经济学家V.pareto在1896年提出。
Pareto最优是指资源分配的一种状态，在不使任何人境况变坏的情况下，而不可能再使某些人的处境变好。Pareto改进是指一种变化，在没有使任何人境况变坏的前提下，使得至少一个人变得更好。一方面，帕累托最优是指没有进行Pareto改进的余地的状态；另一方面，Pareto改进是达到Pareto最优的路径和方法。
多标准优化的数学描述如下：
Min f(x)=[f1(x),f2(x),...fk(x)]
s..t gi(x)=0,i=1,2L,h x∈Rn
其中，fi(x)(1≤i≤k)为目标函数，
gi(x)(i=1,2,Lh)是约束条件，问题具有n个决
策变量，k个目标函数和h种约束。当只有单个目标时,最优解就是在给定约束条件下使目标函数值最大的解,当多个目标要同时最优时,最优解就是Pareto最优集。
如下几个基本概念:
（1） Pareto支配。解x01
0支配x1(xpx)当
且仅当
fi(x0)≤fi(x1),∀i=1,2,L,k;
fi(x0)
（2）Pareto最优或Pareto非劣最优。如果解x0是Pareto最优的解且仅当∃x1:x1px0. （3）Pareto最优解集。所有Pareto最优解的集合：
P0s={x|∃x1px0.}
（4）Pareto前沿或均衡面。所有Pareto最优解对应的目标函数值所形成的区域，表示为：
Pf={f(x)=(f1(x),f2(x),Lfk(x))|x∈ps} 3. 多目标优化算法分类
对于多目标优化问题，从数学的角度讲，Pareto最优解集中的所有解都为可接受的解，不同解之间并无任何差异，然而人们往往需要一个最终的解来指导实际工作。从Pareto最优解集中选择某一个解的过程称为决策。
从不同的角度出发，多目标优化方法可以有多种分类方法。依赖于优化和决策这两个过程是如何组合的，多目标优化方法可以被分为四类: 1，在搜索前决策：多目标优化的目标被合成一个单目标问题，它隐式的包含决策者的喜好信息。
2.在决策前搜索:在没有任何喜好信息的情况下进行优化。搜索过程的结果是候选解的集合(理想的是Pareto最优解集)，然后由决策者最终做出选择。
3.在搜索的过程中进行决策：在交互优化的过程中，决策者给出一些喜好信息。在优化过程的每一步，求得一些折中方案，在此基础上决策者给出更深层的喜好信息以导向更深层的搜索。 4.没有明显的偏好信息:不明显属于上述类型的方法。
第一类方法的优点显而易见，较为成熟的单目标优化算法都可以被无需改变地使用，缺点也很明显，决策者在问题求解初期很可能也没有相应的领域知识或合适的手段来指导将多目标合成为单目
标；第二类方法排除了决策者的喜好信息无指导地进行搜索，但这无疑会增加搜索空间的复杂度和算法设计的难度；第三类算法需要设计相应的策略在解的搜索过程中加入适当的决策者的指导信息，需要决策者和搜索系统长时间交互，但最有可能找到满意的解。 3.1 传统方法
简要介绍两种传统典型的算法:加权方法和目标规划算法。
加权法：
该方法将各个目标函数线性组合成一个所谓的费用函数，从而将多目标问题简单地转化为单目标问题:
fi(x)≥zi。接着，超过目标水平的值∂i被最小化。
针对权重的方法，需要做的是将偏移变量最小化，于是多目标优化问题被转化为求解如下问题:
min ∑wiδi
i=1
k
st.
fi(x)+δi≥zi
i=1,2Lk
δi≥0 i=1,2Lk
x∈S
maxf(x)=w1⋅f1(x)+w2⋅f2(x)+L+wi⋅fk(x)
st. x∈Xf
wi≥0是权值，为了不失一般性，满足
对于基于权重的目标规划，如果目标水平就是Pareto参考点，或偏移变量均为正，则可以保证得到的解为Pareto解。该方法很容易理解，并且决策者也很容易决策。但是权重参数仍然很难正确设置，并且没有什么实际的物理意义。 3.2多目标演化法
现代启发式算法和传统算法相比有很多不可比拟的优点，对于多目标优化问题而言，现代启发式算法的优势更加突出。首先，像遗传算法、粒子群算法、克隆选择算法等群体搜索算法同时搜索可能的解，从而在一次运行中就可以得到Pareto解集，传统算法却往往要多次运行；第二，现代启发式算法对所求问题的Pareto阵面的形状和连续性并不敏感。上述两点在现实问题的模型中往往经常遇到，因此，该类算法更有现实意义。
下面主要讨论几种有典型代表的相关算法：NSGA、PAES、SPEA和NSGA-II以及克隆选择算法。 2.2.1 NSGA
∑w=1。在不同权值组合下求解这个单目标优化
i
问题就可以求得一个解集。如果所求问题具有凸性，那么理论上，采用该方法反复迭代就能得到一个完全的多目标非劣解或Pareto解集；然而，如果该问题不满足凸型，将不能确保能够最终得到完整的Pareto解集。
该算法有几个明显的缺点:一方面，权重参数的很小改变能够引起所求目标向量的较显著的变化；另一方面，不同权重参数的显著改变有可能得到相似的解向量，使解的多样性差。另外，权重集合的均匀分布一般不会产生一个均匀分布的Pareto解集。
目标规划法
该方法中，决策者首先对每个目标函数提出预定的目标水平zi(i=1,2Lk)，并根据目标水平得到偏移变量。每个目标函数联合其目标水平构成目标（goal）。对于最大化问题，目标的形式为
NSGA是由Srimivas和Deb在1994年提出
的,发表在IEEE的“Evolutionary Computation”
杂志上。NSGA基于Goldberg的建议对个体分类,形成多个层次。在选择操作之前,个体基于非劣最优进行排序:所有非劣的个体分为一类,并引进决策向量空间的共享函数法,保持种群的多样性。然
[4]
后,忽略这些已经分类的个体,考虑另一层非劣的个体；这个过程一直持续,直到将所有个体分类。由于在第一个Pareto前沿中的个体有最大的适应度,因此它们被复制的机会更多。NSGA的优点是优化目标个数任选,非劣最优解分布均匀,允许存在多个不同等效解;缺点是由于Pareto排序要重复多次,计算效率较低,计算复杂度高，共享参数要预先确定。 3.2.2 PAES
PAES由Joshua D. Knoweles和David W. Cone
于2000年提出[5]
。PAES由1+1策略和历史档案组成,后者记录了以前找到的那些非劣解。这个集合用作参考集合,以便每个变异的个体与之比较,在PAES中被称作精英保留策略。它的基本思想是首先把目标欧氏空间划分成大小相同的盒子,将归档中的每个个体放置在该划分好的盒中。算法的计算复杂度为O(aMN),其中a为档案长度,M为目标数目,N为种群大小。 3.2.3 SPEA
该算法是Eckart Zitzler于1999年提出的
(Strength Pareto Evolutionary Algorithm)[3]
。借助外部种群实现精英保留策略。在每一代,将非劣个体复制到外部种群,然后计算外部种群中每个个体的强度。这个强度值与支配个体的染色体数目成比例,类似于MOGA中的排序值。在SPEA中,当前种群个体的适应度值是按照外部种群中支配它的非劣解的强度之和计算的,适应度值的计算同时考虑了接近真正Pareto前沿的程度和解的分布。SPEA使用基于距离的小生境半径和Pareto支配,确保解沿着Pareto前沿分布,但其效率依赖于外部种群非劣解的多少。事实上,由于外部种群非劣解参与到了SPEA的选择过程中,若其规模太大,就会减小选择压力,放慢收敛速度。作者采用了聚类技巧删除其中的个体,从而使其大小限制在一定的门限之内。 然而,SPEA也有其不足之处,具体表现是:在选择压力非常低时,SPEA几乎变成随机搜索；SPEA使用聚类删除外部种群个体,有可能丢失外部种群中的非劣解。2001年Zitzler提出了SPEA的改进版本SPEA2,主要改进包括: （1）使用了一种改进的适应值赋值策略，它将每一个个体都考虑进
来，无论它支配多少个个体或被多少个个体支配。（2）使用了最近邻居点方法，它能够更精确的指导搜索的进行。（3）使用了一种新的归档方法，它能够保留边界解。 3.2.4 NSGA-II
Srinivas和Deb基于个体的多层次分类提出了
NSGA(non-dominated sort ing genetic algorithm)[1]
。这种算法是基于不断的对个体进行分类的。在选择完成之前 (使用的是基于随机余数比例选择:stochastic remainder proportionate selection)，群体根据其统治性被分类。所有不被统治(no-dominated)的个体被分成一类，同时被赋予带有一种伪适应度值，这个值与群体尺寸成比例。为了保持群体的多样性，被分类后的个体根据它们的伪适应度值进行共享，然后将这组个体从群体中被移走。接下来考虑另一类不受支配的个体(比如:将群体中剩余的个体重新按照以上提到的方式进行分类)。这一过程要在一直进行到群体中的所有个体都被分类为止。
最先被分类的个体会产生一个最大的适应度值，因此它们就会比群体中的其它个体获得更多被复制的机会。这样就能不断地对non-dominated区域进行搜索，从而导致群体最终朝这一区域的收敛。部分共享会有助于在这一区域上分配群体。 3.2.5 克隆选择算法
克隆选择原理的基本思想是只有那些能够识别抗原的细胞才进行扩增，只有这些细胞才能被选择并保留下来，而那些不能识别抗原的细胞则不选择，也不进行扩增。骨髓中微小的“休眠”的B细胞每一个都载有一个不同的抗体类型。这些细胞载有对于抗原特异的受体，扩增分化成浆细胞和记忆细胞。
Castro基于免疫系统的克隆选择理论提出了克
隆选择算法[2]
,这是一种模拟免疫系统的学习过程
的进化算法。克隆选择算法[6]
的基本流程如图1所示。
图1克隆选择算法图
克隆选择方法具有较好的优化性能，它作为一种崭新的优化方法逐渐引起了人们的注意，不过由于起步较晚，其应用研究的深度和广度还有待于进一步加强。
4. 多目标优化算法的发展与展望
多目标优化算法的研究已开展十多年,到现在
为止已经提出多种多目标进化算法。近些年，基于免疫系统的多目标优化算法逐渐成为研究的热点。免疫算法作为一种新兴的仿生算法,具备如全局优化、鲁棒性好、易于并行处理、智能度高等许多特有的优点。随着研究得不断深入，出现了许多优秀的多目标免疫算法，与传统的进化算法相比，免疫算法还具有如下的优点：
1. 在记忆单元基础上运行，确保算法快速收敛于全局最优解。
2. 算法评价标准是计算亲和性抗体-抗原的亲和度以及抗体-抗体亲和度，反映了真实的免疫系统的多样性。
3. 算法通过促进或抑制抗体的产生，体现了免疫反应的自我调节功能，保证了个体的多样性。 随着人工免疫系统的建立和完善，各种免疫算法在多目标优化上的应用日臻成熟，它势必会成为促进优化技术迅速发展的主要因素之一。
5.结语
通过上述分析和阐述，各种多目标优化算法具有一些相同的特性，包括精英保留策略、种群多样性、个体适应度的赋值等。在研究多目标问题时,掌握它们的共性,可以更好的对原有算法进行改进。而掌握各种算法的不同特点则可以了解其长处与不足,为进一步研究提供理论基础。近几年进化
计算的迅速发展为多目标优化问题的解决提供新的视野和活力，它不依赖于问题的具体领域，不要求目标函数有明确的解析表达式，对问题的种类有很强的鲁棒性，所以已广泛应用于组合优化、生产调度、机器人、人工生命、生物计算等许多学科。
6.参考文献
[1] Kalyanmoy Deb，Samir Agrawal，Amrit Pratab and
T.Meyarivan. A Fast Elitist Non-Dominated Sorting Genetie Aigorithm: NSGA-II.KanGALrePort200001，Indian Institute of Technology，KanPur，India，2000
[2] L.N.de Casrto，Fenrando J，V.Zuben，learning and Optimization Using the Clonal Selection Principle. IEEE Trans on Evolutionary Computation，2002，6 (3):239-251. [3] Zitzler E, Thiele L. Multi-objective Optimization Using Evolutionary Algorithms-A Comparative Study. In: Eiben A E, ed.Parallel Problem Solving from Nature V, Amsterdam, September 1998. 292~301
[4] Srinivas N, Deb K. Multiobjective Optimization Using Non-dominated Sorting in Genetic Algorithms. Evolutionary Computation, 1994,2(3):221~248
[5] Knowles J D, Corne D W. Approximating the Non-dominated Front Using the Pareto Archived Evolution Strategy. Evolutionary Computation, 2000, 8(2):149~172 [6] 谢克明 郭红波等. 人工免疫算法及应用. 计算机工程与应用. 2005.20
多目标优化算法综述
作者：作者单位：
高鹏
华北电力大学,电气与电子工程学院,北京,102206
本文读者也读过(3条)
1. 许婧祺 多目标优化算法研究综述[期刊论文]-科技信息2010(32)
2. 赵亮.雎刚.吕剑虹.ZHAO Liang.JU Gang.L(U) Jian-hong 一种改进的遗传多目标优化算法及其应用[期刊论文]-中国电机工程学报2008,28(2)
3. 刘楠楠 基于进化算法的多目标优化算法及应用研究[学位论文]2010
引用本文格式：高鹏 多目标优化算法综述[会议论文] 2007