下载文档原格式
多目标进化算法综述电子教案一、引言多目标优化问题是指在决策者有多个目标的情况下，同时寻找多个最优解的问题。
与传统的单目标优化问题相比，多目标优化问题更复杂，因为不同目标之间可能存在冲突，无法简单地将它们转化为单目标问题进行求解。
多目标进化算法（Multi-Objective Evolutionary Algorithm，MOEA）是一类应用于解决多目标优化问题的算法。
本文将对多目标进化算法进行综述。
二、多目标进化算法的基本原理多目标进化算法是一种基于自然进化的元启发式优化算法，其基本原理是模拟自然界的生物进化过程，通过不断进化来逼近多个最优解。
多目标进化算法的基本步骤包括初始化种群、适应度评估、选择操作、交叉操作和变异操作，以及终止条件判断。
在多目标进化算法中，每个解决方案用一个染色体表示，染色体上的每个基因对应一个决策变量的取值。
种群中的每个个体是一个解决方案，通过不断进化，种群中的个体分布在目标空间的帕累托前沿上，代表了多个最优解。
选择操作根据个体在目标空间的分布情况筛选出优秀的个体，交叉和变异操作则产生新的解决方案，继承和引入种群中的优秀特征。
终止条件可以是迭代次数达到一定限制或者目标空间的帕累托前沿收敛到稳定状态。
三、常见的多目标进化算法1.NSGA-II算法NSGA-II（Non-Dominated Sorting Genetic Algorithm II）是一种经典的多目标进化算法。
该算法通过非支配排序和拥挤度距离两个步骤进行个体的选择，以促进种群的多样性。
非支配排序将个体划分为不同的等级，拥塞度距离用于评估个体在目标空间中的分布情况。
2.SPEA2算法SPEA2（Strength Pareto Evolutionary Algorithm 2）是另一种经典的多目标进化算法。
该算法通过计算个体在目标空间中的适应度值来选择优秀的个体。
适应度值包括个体在被支配次数方面的评估和个体之间的拥挤度距离。
多目标进化算法性能评价指标综述多目标进化算法（MOEA）是一种用于解决多目标优化问题的进化算法。
MOEA通过维护一个个体群体的集合，通过交叉、变异等操作，逐步搜索问题的解空间，以得到一组尽可能好的近似最优解，这些解在不同的目标函数下优化结果良好且彼此之间具有一定的均衡性。
对于多目标进化算法的性能评价，主要包括以下几个方面的指标。
1. 近似最优解集合的质量这是最重要的评价指标之一，主要用于衡量算法是否能够找到一组高质量的非劣解。
在多目标优化问题中，解空间通常非常大，因此算法找到的解集可能只是非劣解的一个近似。
质量好的近似最优解集合应该尽可能接近真正的非劣解集合，并且集合中的解之间应该有较好的均衡性。
2. 支配关系的准确性多目标优化问题中的解往往是通过支配关系进行判断的。
一个解A支配另一个解B，意味着解A在所有目标函数上至少和解B一样好，且在某一个目标函数上更好。
算法找到的解集应该能够正确地判断出解之间的支配关系，并保持非劣解之间的支配关系不变。
3. 外部收敛集的覆盖度外部收敛集是算法找到的近似最优解集合，其覆盖度是衡量算法性能的重要指标之一。
覆盖度越高，说明算法找到的近似最优解集合能够尽可能覆盖真实的非劣解集合。
覆盖度的计算通常通过指标如hypervolume、inverted generational distance等进行。
4. 多样性多样性指的是找到的近似最优解集合中解之间的差异程度。
一方面，算法应该找到尽可能多样的解，以保证搜索过程能够覆盖解空间的各个方向。
解之间应该具有一定的距离，以避免近似最优解集合中过于集中在某个区域。
5. 计算效率和收敛速度算法的计算效率和收敛速度也是评价指标之一。
虽然算法能够找到高质量的近似最优解集合，但如果计算时间过长，就会限制算法的实际应用。
算法应该在保证质量的前提下，尽可能提高计算速度和效率。
多目标进化算法的性能评价指标主要包括近似最优解集合的质量、支配关系的准确性、外部收敛集的覆盖度、多样性以及计算效率和收敛速度。
第28卷第2期海南大学学报自然科学版V o l.28N o.2 2010年6月N A T U R A LS C I E N C EJ O U R N A LO FH A I N A N U N I V E R S I T Y J u n.2010 文章编号:1004-1729(2010)02-0176-07动态多目标优化进化算法研究综述刘淳安(宝鸡文理学院数学系,陕西宝鸡721013)摘 要:动态多目标优化进化算法主要研究如何利用进化计算方法求解动态多目标优化问题,其已成为进化计算领城一个新的研究课题.本文首先介绍了动态优化问题的分类,然后描述了动态多目标优化问题的基本概念、数学表述,最后在当前对动态多目标优化进化算法的基本原理、设计目标、研究现状及性能度量讨论的基础上,提出了对动态多目标优化问题需进一步研究的关键问题.关键词:动态优化;多目标优化;进化算法;性能度量中图分类号:T P18 文献标志码:A在生产调度、人工智能、组合优化、工程设计、大规模数据处理、城市运输、水库管理、网络通信、数据挖掘和资本预算等诸多优化领域,常常会遇到许多复杂的更为接近现实生活的动态和静态优化问题.动态优化问题(D y n a m i c O p t i m i z a t i o n P r o b l e m:D O P)是指其目标函数不仅与决策变量有关,而且还会随着时间(环境)动态变化,因此其最优解也会随着时间(环境)动态改变;静态优化问题(S t a t i c O p t i m i z a t i o n P r o b-l e m:S O P)是指其目标函数仅与决策变量有关,其最优解不随时间(环境)的变化而改变,在过去的几十年,人们大多致力于S O P的研究,直到近几年,D O P才引起越来越多研究者的兴趣[1-3].对于D O P,一般可将其分为动态单目标优化问题(D y n a m i c S i m p l e-o b j e c t i v e O p t i m i z a t i o nP r o b l e m:D S O P)和动态多目标优化问题(D y n a m i cM u l t i-o b j e c t i v eO p t i m i z a t i o nP r o b l e m:D M O P)两大类.目前,对D O P的研究主要集中在D S O P[4-12],对D M O P的研究成果还不多,国际上也才刚刚起步,可见到的理论很少,只有少量研究成果[13-17],而且这些成果大多数是针对时间变量取值于离散空间的D M O P设计算法,或者把一些静态多目标优化进化算法直接用于D M O P的求解.然而,对于D M O P而言,因其具有多个依赖时间(环境)的相互冲突、不可公度的目标,加之其P a r e t o最优解随时间的变化会发生改变,因此,对D M O P的优化显得比较困难,通常很难设计出一种通用的有效求解方法.20世纪60年代以来,借鉴达尔文的“物竟天择”生物进化理论及孟德尔的遗传理论,通过对生物进化中的繁殖、变异、竞争和选择4个基本形式进行模拟,使人们获得了解决复杂优化问题,特别是求解动态多目标优化问题的一类新方法———动态多目标优化进化算法(D y n a m i c M u l t i o b j e c t i v e O p t i m i z a t i o n E v o l u t i o n a r y A l g o r i t h m:D M O E A)[1,18],E A自产生以来,一直备受人们的关注,作为一种随机搜索算法,它较传统优化技术相比具有许多优势,其中算法演化的并行性、对全局优化问题的有效性和实用性以及对问题求解的稳健性是其他算法难以无法比拟的.本文主要介绍了动态多目标优化问题的基本概念、数学描述,动态多目标优化进化算法的基本原理、设计目标、研究现状、性能度量及需进一步研究的热点问题.1 D M O P基本概念及数学表述[16,17]在现实世界中,许多优化问题都是多个目标的,而且是与时间因素有关的.许多系统需要考虑动态调收稿日期:2009-10-28基金项目:陕西省自然科学基础研究计划项目(2009J M1013);陕西省教育厅科学研究计划项目(09J K329);宝鸡文理学院重点科研计划项目(Z K0840)作者简介:刘淳安,(1972-),男,陕西淳化人,宝鸡文理学院数学系副教授,博士.度问题,考虑时间间隔上各个运行状态之间的约束,即时间带来的约束,这些约束称为动态约束,面对一个复杂动态变化的系统,静态优化方法具有明显的局限性,因为在这些问题中,其研究目标是复杂变化的.将现实中这些具有多个目标、与时间因素相关的问题抽象成数学模型就是动态多目标优化问题(D y -n a m i c M u l t i o b j e c t i v e O p t i m i z a t i o n P r o b l e m s :D M O P ).不失一般性,若记V O ,V F 和W 分别是n O 维、n F 维和m W 维连续或离散的向量空间,则任何D M O P 都可以表述为以下的参数化数学形式[16,17]m i n v o ∈v Of =(f 1(v o ,v F ),f 2(v o ,v F ),…,f m (v o ,v F ))s .t .g (v o ,v F )≤0,h (v o ,v F )=0,(1)其中,g (v o ,v F )≤0和h (v o ,v F )=0分别为不等式和等式向量约束,f :V O ×V F ※W 是目标向量函数,f i (v o ,v F )(i =1,2,…,m )是m 个子目标函数.在式(1)中,变量v o 对于优化是有用的,而变量v F 是强加的参数,其与优化变量无关.目标向量函数f 和约束向量函数g 和h 都受制于时间参数约束,而且可以是非线性的.若令V 是n 维连续或离散的决策向量空间,W 是m 维连续或离散的目标向量空间,强加的参数v F 是一个取值于连续或离散实值空间T 的参数变量t ,则上述动态多目标优化问题的参数化形式可简化为[16,17]m i n v ∈Vf =(f 1(v ,t ),f 2(v ,t ),…,f m (v ,t ))s .t .g (v ,t )≤0,h (v ,t )=0,(2)其中,g (v ,t )≤0和h (v ,t )=0分别为不等式和等式向量约束,f :V ×T ※W 是目标向量函数.对于动态多目标优化问题(2),其决策空间中的P a r e t o 最优解集(记作:P s(t ))和目标空间中的P a r e t o 前沿面(记作:P F (t ))通常有以下4种可能随时间变化的情形情形1 P a r e t o 最优解集P s (t )随时间变化,而P a r e t o 前沿面P F (t )不随时间变化;情形2 P a r e t o 最优解集P s (t )和P a r e t o 前沿面P F (t )都随时间变化;情形3 P a r e t o 最优解集P s (t )不随时间变化,而P a r e t o 前沿面P F (t )随时间变化;情形4 尽管问题发生改变,但P a r e t o 最优解集P s (t )和P a r e t o 前沿面P F (t )都不随时间变化.对于优化问题(2)的P a r e t o 最优解集和目标空间中的P a r e t o 前沿面,除了上述4种情形外,在现实中,还存在另外一种情形,即当问题发生改变时,上述变化的几种类型可能在时间尺度内同时发生.然而,通常只考虑前3种类型.2 D M O E A 基本原理和设计目标对于求解动态多目标优化问题(2)的进化算法,在其设计中往往需考虑其随时间变化的强度或随时间变化的频率.一般而言,这包括2个方面:1)D M O P 随时间t 是连续缓慢变化的,即在整个时间段上D M O P 的变化非常平稳,其变化幅度保持在一个非常小的误差内;2)D M O P 随时间t 的变化出现突变,即在一个小时间段内很少变化或保持不变,但随之发生突然随机变化.一般来讲,对于静态多目标优化问题,其最优解构成一确定的P a r e t o 最优解集,而对于动态多目标优化问题(2),因目标函数及约束条件不仅依赖于决策变量而且与时间参数t 有关,故其最优解是随时间参数t 发生变化的一组P a r e t o 最优解集.另外,对实际问题而言,必须根据对问题的了解程度及决策者的偏好,从动态多目标优化问题的P a r e -t o 最优解集中挑选出所在时刻(环境)下合适的一些P a r e t o 最优解作为问题的最优解.因此,设计求解动态多目标优化问题(2)的进化算法首先需考虑以下关键问题:1)如何使算法能有效跟踪问题的随时间(环境)发生变化的P a r e t o 最优解集;2)如何使算法快速准确求得不同时刻(环境)下问题的质量较好、数量较多且分布均匀的P a r e t o 最优解.3 D M O E A 研究现状对于动态优化问题,通常将其分为动态单目标优化问题和动态多目标优化问题.目前研究最多的是177 第2期 刘淳安:动态多目标优化进化算法研究综述178海南大学学报自然科学版 2010年 求解动态单目标优化问题的进化算法,其主要分为下面3种类型,这些方法通常也被用于动态多目标优化问题的求解.1)保持种群的多样性 种群的多样性是进化算法有效探索整个可行解空间的必要条件,尤其对算法迅速适应D O P环境的改变起到非常重要的作用.如G r e f e n s t e t t e[19]提出的随机迁移进化策略,M o r r i s o n[20]提出的超变异法及L e w i s[21]提出的变量局部搜索技术等都是用来提高种群多样性的有效方法.另外, C o b b[22]把3种不同变异(固定变异率,过度变异和随机移民)方法用在动态优化问题中,并对其在动态环境中的性能进行了检验,结果表明,采用过度变异在连续缓慢变化的环境中性能最好,如果环境发生突变,随机移民进化方法性能较优.E r i k s s o n[23]提出了一种事先对进化个体进行适应度估值,然后采取对其自适应的调节来维护种群的多样性.M o r i[24]提出了借鉴一种新的变量来控制种群多样性的方法.此外,文献[25]还给出了使用一些特殊染色体来维持进化群体的多样性等.2)基于记忆的方法 对于动态优化进化算法,适时增加其存储过去获得的较好解(个体),并在需要的时候重新启动这些解并将其用于进化,这样会大大地提高算法在环境变化的情况下对问题求解的效率和搜索能力.记忆通常分为2种:利用冗余表示的隐式记忆和通过引入额外的记忆集存储较好解的显式记忆.研究者认为,基于记忆方法比较适用于具有一定规律性或周期性变化的函数,同时,冗余表示的隐式记忆方法还能增加进化模块的种类,提高群体的多样性.如R y a n[26]提出了利用额外二倍体隐式记忆方法,在该方法中,如果某种条件满足,则让基因为1;否则为0.计算机仿真表明,此方法在周期性变化的环境中优于其他方法.与此同时,H a d a d[27]提出了利用多倍体的记忆进化方法,R y a n和C o l l i n s[28]提出了基因分级结构记忆方法等.尽管上述各种隐式记忆的方法能够使进化算法间接地存储一些有效信息,但并不确定算法能否有效地使用这些信息.3)基于多种群的方法 多种群方法是指在搜索空间中的几个可行区域上布置一些子种群,并且让这些子种群搜索相应子区域上变化的最优解.从某种程度上说,多种群方法具有一种自适应记忆功能.如O p p a c h e r等[29]提出一种迁移平衡进化方法,其把整个种群分成主种群和许多小的次种群,主种群主要用于探索极值点,次种群主要用于在适值曲线上几个孤立的区域进行搜索,这种方法很好地保证了算法的探索性.U r s e m[30]提出了一种多种族进化算法来保证整个种群的多样性,在该方法中,子种群的分组是采用一种峰谷探测过程来确定.随着上述几种求解动态优化方法的不断完善,对动态多目标优化问题的研究成果也相继涌现.F a r i n a F M等人[16]提出了一种邻域搜索算法(D B M),该算法意在产生少数但具有很好分布的非劣解集.D e b K 等人[14]在N S G AⅡ基础上改进初始群体提出了动态多目标优化进化算法(D N S G A-Ⅱ),该算法采用非劣排序以及拥挤距离进行个体评价,经由最优保留,二人联赛选择、S B X交叉及P o l y n o m i a l变异等操作进行群体进化.I a s o n H等人[13]在求解动态单目标优化进化算法基础上提出了一种向前估计方法(F o r w a r d-L o o k i n g A p p r o a c h).Z h a n g Z h u-h o n g[31]提出了一种动态环境下的多目标免疫算法并把其成功地应用于温室控制;Z h o u A i-m i n等人[32]提出了一种基于种群预测的重启(P r e d i c t i o n-B a s e dP o p u l a t i o nR e-i n i t i a l i z a-t i o n)动态多目标优化进化算法.另外,许多求解静态多目标优化问题的进化算法,如N S G A-Ⅱ[33],S P E A-Ⅱ[34],M S O P S[35],O M O E A-Ⅱ[36]及求解移动峰[37-39]或带噪声[40,41]的静态多目标优化策略经过扩展和改进后也被直接应用于求解D M O P[42-44].在国内,一些基于免疫原理(I m m u n e M e c h a n i s m)和进化机理的动态多目标优化算法[45-49]也相继出现.4 D M O E A性能评价方法随着动态多目标优化进化算法的相继出现,D M O E A性能度量也是D M O P中一个值得研究的问题,下面给出几种度量D M O E A有效性的方法.1)P a r e t o最优解的收敛量[17] P a r e t o最优解的收敛量是F a r i n a M,D e b K[17]提出的用于度量D M O E A 所得到动态多目标优化问题的P a r e t o最优解的收敛量或找到问题真正P a r e t o最优解的错误率的重要指标,其定义如下e f (t )=1n p ∑n pj =1m i n i =1:n h ‖P S ,i (t )-x j(t )‖2,(3)其中,n h 为用于标记环境t 时问题的真正P a r e t o 最优解集P s (t )的采样数目,n p 为算法在环境t 求得问题的P a r e t o 最优解的数目,x j(t )(j =1,2,…,n p )为在决策空间计算的解,‖·‖2为“·”在R n上的2-范数.2)覆盖率(C o v e r a g e r a t e :C r )[31] 覆盖率C r 是张著洪教授[31]给出的用于评价2个算法在整个环境下求得问题的P a r e t o 最优解集的优劣程度.在环境t (1≤t ≤T )下,设A t k ,B t k分别是算法A 和B 在第k (1≤k ≤K )代获得的P a r e t o 最优解集,则定义C r (A ,B )=1T ·K 2∑Tt =1∑Kk =1∑Kτ=1C (A t k ,B t τ)(4)为评价2个算法A ,B 在整个环境下所得的P a r e t o 最优解集相对优劣度(覆盖率)的度量.其中,C (·,。
多目标进化算法性能评价指标综述多目标进化算法是一类用于解决多目标优化问题的进化算法。
与传统的单目标优化算法不同，多目标进化算法试图在多个目标函数之间寻找一组非支配解，即无法通过改善一个目标函数而同时改善其他目标函数的解。
基于多目标进化算法的优化方法已经在许多领域得到了广泛应用，如工程设计、车辆路径规划、机器学习等。
多目标进化算法的性能评价是在解决多目标优化问题时评估算法优劣的重要指标。
这些指标可以分为两类，一类是与解集的多样性相关的指标，另一类是与解集的收敛性相关的指标。
与解集的多样性相关的指标可以反映多目标进化算法搜索到的解的多样性和分布情况。
常见的指标包括解集的帕累托前沿覆盖率、解集的帕累托前沿距离、解集的均匀度等。
帕累托前沿覆盖率是指算法搜索到的解集中包含的真实帕累托前沿上的解的比例。
解集的帕累托前沿距离是指算法搜索到的解集中各个解与真实帕累托前沿的平均距离，可以用来评估解集的分布情况。
解集的均匀度指标可以用来评估解集中解的分布是否均匀，常见的均匀度指标包括解集的熵和解集的均匀度指标。
除了上述的指标，还有一些其他的指标可以用来评价多目标进化算法的性能，如解集的虚拟耗散度指标、解集的相对距离指标以及解集的多样性指标等。
这些指标可以综合考虑解集的多样性和收敛性，提供对多目标进化算法的全面评价。
多目标进化算法的性能评价指标涵盖了解集的多样性和收敛性两个方面，可以用来评估算法搜索过程中解集的质量和搜索效果。
在实际应用中，根据具体问题的特点和要求，选择适合的性能评价指标可以帮助研究人员更好地理解算法的优劣，并进行算法的改进和优化。
多目标进化算法性能评价指标综述多目标进化算法（Multi-Objective Evolutionary Algorithms，MOEAs）是一类用于解决多目标优化问题的算法。
在实际问题中，往往需要同时优化多个目标函数，这就需要使用多目标优化算法来寻找最优解集。
由于多目标优化问题的复杂性，需要对算法的性能进行全面评价。
本文将对多目标进化算法的性能评价指标进行综述，以期为相关领域的研究者提供参考和指导。
1. 收敛性多目标进化算法的收敛性是评价其性能的重要指标之一。
收敛性指标主要包括收敛速度和收敛准确度两个方面。
在理想情况下，算法应该能够在有限的迭代次数内找到接近于真实帕累托前沿的解集。
收敛速度指标可以通过衡量解集与真实帕累托前沿的距离来评价，收敛准确度则可以通过度量算法得到的解集是否足够接近帕累托前沿来评价。
2. 多样性多目标进化算法的多样性是指得到的解集中是否包含了足够多的种类和分布较广的解。
多样性指标主要包括均匀分布和分散度两个方面。
均匀分布指标可以通过衡量解集中解的分布是否均匀来评价，分散度指标则可以通过度量解集中解的分散程度来评价。
多样性的评价是为了确保算法能够获得全局的非劣解，而不是仅仅集中在某一区域。
3. 运行时间多目标进化算法的运行时间是指算法寻找最优解集所需的时间。
在实际问题中，算法的运行时间是一个十分重要的性能指标，因为用户往往希望算法在尽可能短的时间内给出满意的解集。
运行时间的评价需要综合考虑算法的收敛速度和解集的多样性来进行评价。
4. 鲁棒性多目标进化算法的鲁棒性是指算法对问题参数变化的适应能力。
在实际问题中，问题的参数往往会有所变化，因此算法的鲁棒性是十分重要的。
鲁棒性指标主要包括参数敏感性和问题变化适应性两个方面。
参数敏感性指标可以通过度量算法对参数变化的敏感程度来评价，问题变化适应性指标则可以通过度量算法对问题变化的适应能力来评价。
5. 可解释性多目标进化算法的可解释性是指算法得到的解集是否能够为用户提供有效的决策支持。
多目标进化算法总结多目标进化算法(MOEA, Multiple Objective Evolutionary Algorithm)是一类基于进化算法的优化方法，主要用于解决具有多个相互竞争的目标函数的问题。
MOEA通过维护一组解的种群，采用进化操作来尽可能多的帕累托最优解集。
下面对MOEA进行详细总结。
首先，MOEA的基本思想是通过模拟自然进化过程进行优化，它借鉴了进化生物学中的适应度、交叉、突变等概念。
MOEA维护了一个种群，每个个体代表一个解，种群中的个体通过进化操作进行迭代更新。
在进化过程中，MOEA通过交叉和突变操作生成新的个体，通过适应度评估来决定个体的生存能力，根据个体在不同目标函数上的性能对种群进行选择和更新。
其次，MOEA的核心是解的评估和解的选择。
MOEA采用一个适应度函数来评估解在多个目标函数上的性能。
适应度函数一般采用拥挤度或距离等概念来度量解的优劣。
拥挤度是指解在种群中的分布密度，用以保持解的多样性。
根据适应度函数的评估结果，MOEA决定哪些解会生存下来，并更新种群。
第三，MOEA有很多具体的算法实现，其中比较经典的有NSGA-II、PAES、SPEA、MOEA/D等。
NSGA-II采用非支配排序和拥挤度距离来维护种群的多样性，并通过交叉和突变操作来生成新的个体。
PAES通过局部来改进解的质量，采用网格来表示解的空间，并根据适应度函数进行迁移。
SPEA使用非支配排序和密度估计来选择解，并通过交叉和突变操作来生成新的个体。
MOEA/D通过将多目标优化问题分解为多个子问题，并通过子问题之间的协作来帕累托最优解。
此外，MOEA还面临一些挑战和改进方向。
首先，MOEA需要解决多目标函数之间的冲突，如何在多个目标之间找到均衡点是一个难题。
其次，MOEA的计算复杂度通常比单目标优化方法更高，如何提高算法的效率是一个重要问题。
此外，MOEA在处理约束问题和高维问题时也存在挑战，如何有效处理这些问题也是一个改进方向。
多目标进化算法性能评价指标综述多目标进化算法（Multi-objective Evolutionary Algorithms，MOEAs）是一类优化算法，用于解决具有多个目标函数的多目标优化问题。
MOEAs在解决多目标优化问题上具有很强的适应性和鲁棒性，并在许多领域有着广泛的应用。
为了评价MOEAs的性能，人们提出了许多指标。
这些指标可以分为两类：一类是针对解集的评价指标，另一类是针对算法的评价指标。
首先，针对解集的评价指标主要用于从集合的角度评价解集的性能。
常见的解集评价指标有：1. Pareto前沿指标：衡量解集的覆盖度和质量。
Pareto前沿是指在多目标优化问题中不可被改进的解的集合。
Pareto前沿指标包括Hypervolume、Generational Distance、Inverted Generational Distance等。
2. 支配关系指标：衡量解集中解之间支配关系的分布情况。
例如，Nondominated Sorting和Crowding Distance。
3. 散度指标：衡量解集中解的多样性。
例子有Entropy和Spacing 等。
4.非支配解比例：衡量解集中非支配解的比例。
非支配解是指在解集中不被其他解支配的解。
除了解集评价指标，人们还提出了一些用于评价MOEAs性能的算法评价指标，例如：1.收敛性：衡量算法是否能找到接近最优解集的解集。
2.多样性：衡量算法是否能提供多样性的解。
3.计算效率：衡量算法是否能在较少的计算代价下找到高质量的解集。
除了上述指标，还有一些用于评价MOEAs性能的进阶指标，例如：1.可行性：衡量解集中的解是否满足的问题的约束条件。
2.动态性：衡量算法在动态环境中的适应性。
3.可解释性：衡量算法生成的解是否易于被解释和理解。
以上只是一些常用的指标，根据具体的问题和应用场景，还可以针对性地定义其他指标来评价MOEAs性能。
综上所述，MOEAs性能的评价是一个多方面的任务，需要综合考虑解集的质量、表示多样性以及算法的计算效率等方面。
多目标进化算法性能评价指标综述多目标优化问题在现实生活和工程领域中具有重要的应用价值，其在资源配置、飞行器设计、工程设计等方面都有着广泛的应用。
多目标进化算法作为解决多目标优化问题的有效手段，一直受到学术界和工程界的关注。
对于多目标进化算法的性能评价指标，学术界存在较大的争议，无法形成统一的评价标准。
本文拟就多目标进化算法性能评价指标作一综述，以期为该领域的研究者提供参考。
一、多目标进化算法性能评价指标多目标优化问题中的性能评价指标主要包括收敛性、多样性和均衡性。
收敛性主要关注算法是否能寻找到最优解，多样性主要关注算法搜索到的解是否有广泛的分布，均衡性则主要考虑多个目标之间的平衡关系。
（一）收敛性收敛性是指算法是否能够在有限的时间内找到接近最优解的解集。
通常来说，用于评价收敛性的指标主要有收敛速度和收敛精度两个方面。
收敛速度是指算法在找到最优解的过程中所花费的时间，即算法的收敛速度越快，则算法收敛性越好；而收敛精度则是指算法所找到的解与真实最优解的误差程度，即算法的收敛精度越高，则算法收敛性越好。
（二）多样性多样性是指算法搜索到的解集是否具有广泛的分布，即解集中的解之间是否有足够的差异性。
对于多目标优化问题来说，多样性对于保证算法搜索到的解集具有全面的覆盖性和足够的可行性具有重要的意义。
多样性的评价指标主要包括最近距离、最远距离和均匀分布程度等。
（三）均衡性均衡性是指多目标之间的平衡关系，即算法所搜索到的解集中是否具有足够的多样性，同时又不失优秀解的集中度。
均衡性的评价指标主要包括超体积指标、Hypervolume Contribution Ratio 等。
近年来，虽然针对多目标进化算法的性能评价指标进行了大量的研究，但并没有形成统一的评价标准。
部分学者主张结合不同的性能评价指标，如收敛性、多样性和均衡性，以全面评价多目标进化算法的性能。
而另一部分学者则认为应该提出新的、更适用于多目标进化算法的性能评价指标，以完善对于多目标进化算法的性能评价。
多目标进化算法综述多目标进化算法综述作者：梅志伟来源：《软件导刊》2017年第06期摘要：基于种群的进化算法在一次运行中能够产生一组近似的 Pareto 最优解集，因此多目标进化算法成为处理多目标优化问题中的主流方法。
介绍了多目标优化问题中的数学模型以及相关定义，根据多目标进化算法的特点，将现有算法分为4类并分别进行阐述，同时分析了它们的优缺点。
关键词：多目标优化；进化算法；支配；分解DOIDOI：10.11907/rjdk.171169中图分类号：TP301文献标识码：A 文章编号：1672-7800（2017）006-0204-040 引言在人们的实际生活中，大多数优化问题都是多目标优化问题，广泛存在于经济管理、工程实践和科学研究等领域中。
当前，多目标优化在理论和应用方面均取得了不少进展，但是由于多目标优化问题的复杂性，因此仍存在大量挑战。
多目标优化问题中往往存在多个彼此相互冲突的目标。
与单目标优化不同，在多目标优化中，提高一个目标的性能会引起其它一个或多个目标性能的下降。
因此，多目标优化问题中不存在一个单独的最优解，而是存在一组表示各个目标间权衡和折中关系的解集，称该解集为Pareto最优解集。
Pareto最优解集在目标域的投影被称为Pareto前沿。
由于很多现实工程问题中的优化问题是NP难，传统的数学规划方法将会变得异常困难。
而具有自然界规律启发式特征的求解方法往往适合近似求解这些困难问题，这些方法被称为进化计算[1]。
进化算法基于种群的特性使其十分适合多目标优化问题的求解。
同时，进化算法还具有鲁棒性强的特点。
因此，进化算法被广泛应用在多目标优化问题的求解上。
1 多目标进化问题概述多目标优化问题同时优化多个目标，这些待优化的目标包含最大化、最小化或者两者都有的问题。
在实际处理时，为了简化问题，可以将最大化或最小化问题取反，使所有优化目标全部转化成最小化或最大化问题。
本文中将讨论最小化问题。
2 多目标进化算法一般流程生物进化是一个不断优化的过程，在不断的变化过程中增加自身的适应性。
进化计算以生物进化为启发，对一个解进行抽象编码，模拟生物进化中的基因。
进化算法以种群为基础，是一个黑盒的搜索、优化方法，进化算法不需要优化问题具备一定的前提条件，例如连续性、可微性等，且一次运行能够产生一组解。
因此，进化算法特别适合处理多目标优化问题。
生物的进化过程主要包括繁殖、变异、竞争和选择。
与之类似，一个典型的进化算法主要包含以下步骤：①初始化：生成一个初始化种群，记为P，其中包含N个个体（解），并记当前代数t=0；②适应度评价：计算每个个体x∈P的适应度值F（x）；③繁殖：从父代种群P 繁殖出后代种群Q，具体包括交叉和变异过程；④选择：使用选择算子从P∪Q中选择出N个精英个体，作为下一代的父代种群P；⑤下一代进化：增加进化代数t=t+1，如果满足终止条件，则停止算法并输出P，否则进入下一代迭代过程，即转入第2步。
一个典型的进化算法流程如图1所示。
3 多目标进化算法分类从进化算法诞生之初，由于其在多目标优化问题上的优异表现，众多研究人员提出了多种多目标进化算法。
根据算法特性不同，具体可分为以下几类：3.1 基于Pareto支配关系的多目标进化算法通过Pareto支配关系，可以对两个解进行对比，从而利用支配信息指导解集的选择。
基于Pareto支配关系的多目标进化算法一直以来都是一个热门研究方向，研究人员提出了许多算法，例如SPEA[2]、SPEA2[3]、PESA[4]、PESA-II[5]、NSGA-II[6]等。
基于Pareto支配的多目标进化算法取得了令人瞩目的成就，然而在处理超多目标优化问题时却面临许多挑战。
由于Pareto支配的特性，超多目标空间中的大部分解均为非支配关系，从而失去了选择压力。
研究人员通过改进Pareto支配关系，提出了一系列方法。
Laummans等[7]定义了一种ε支配关系，增加了一个解的支配空间；Deb等[8]根据ε支配关系，提出了ε-MOEA算法，在超多目标优化问题中取得了较好效果。
ε-MOEA算法将目标空间划分成网格，不同网格中的解使用ε支配关系进行比较，相同网格中的解则使用传统的Pareto支配关系。
2001年，Ikeda等[9]也提出了一种新的支配关系，称为α支配。
在α支配关系中，比较一个目标的同时会考虑其它目标函数值。
通过一个线性平衡函数重新计算对比时的目标值，若一个解在一个目标上显著优于另一个解，而在另一个目标上则略微处于弱势，则前者仍然能α支配后者，这样的支配关系有利于选择更好的解。
除此之外，还有多种算法建立在改进的Pareto支配关系之上，例如基于网格支配的GrEA 算法[10]、基于ε排序策略的εR-EMO算法[11]等。
3.2 基于分解的多目标进化算法将一个多目标优化问题分解为一组单目标的子问题进行求解也是一个常见的解决方法。
常见的分解方法包括加权和法、切比雪夫法以及基于惩罚值的边界交叉法[12]。
2007年，Zhang等[13]结合了上述几种分解方法提出了一种基于分解的多目标进化算法（MOEA/D），这是近年来的一个热门算法框架。
在MOEA/D算法中，通过传统的分解方法将一个多目标优化问题分解为一组单目标的子问题，然后使用进化算法同时求解这些子问题。
MOEA/D还通过权重向量之间的距离关系定义了子问题间的邻居关系。
在优化一个子问题时，通过相邻子问题间交叉变异的进化过程生成新解，并使用新解来更新当前子问题的解。
MOEA/D中还引入了一种邻居子问题间的信息共享方法，即一个新解在更新对应子问题的同时还会更新其邻居子问题。
实验表明，MOEA/D算法相较于以往的一些基于分解的算法，效果更为突出。
Li等[14]将差分进化的思想引入到MOEA/D的进化过程中，同时还限制了邻居子问题的最大更新数目，进一步提高了算法性能。
与基于Pareto支配关系的算法在超多目标优化问题中的局限不同，基于分解的算法能够直接适用于超多目标优化问题中。
针对超多目标优化问题的特性，研究人员也提出了许多改进方法。
Asafuddoula等[15]将系统抽样和自适应的ε控制技术引入到基于分解的进化算法中，在超多目标空间中生成均匀的权重向量，平衡解集的收敛性与多样性；为了解决超多目标空间选择压力过大导致的多样性丢失问题，Fabre等[16]提出了一种并行的遗传算法，将每个子问题都关联到一个子种群，通过子种群的进化实现整个种群的进化，实验结果也验证了其在多样性保持方面的优势。
3.3 基于指标的多目标进化算法多目标进化算法求得的解集可以通过许多评价指标来衡量，基于指标的多目标进化算法通过评价指标来指引算法的搜索方向，指导进化过程中新种群的选择。
Zitzler等[17]首先将评价指标引入到进化算法的选择策略中，提出一种基于评价指标的进化算法（IBEA），可以通过任意一种评价指标来对比候选解。
在IBEA中，不需要使用例如适应值共享等多样性保持策略，也不需要对整个近似Pareto最优解集进行计算，只需对比其中的部分解即可。
IH指标可以衡量一个解集的质量，IH指标值越大，表示解集质量越好。
为了能够最大化一个解集的IH指标值，Emmerich等[18]提出了一种基于S-度量选择的多目标进化算法（SMS-EMOA）。
SMS-EMOA通过IH指标的梯度信息来指导种群进化过程。
在处理低维的多目标优化问题时，SMS-EMOA求得的解集具有很好的收敛性和多样性。
但是，在面对超多目标优化问题时，SMS-EMOA的计算复杂度成指数上升，算法效果急剧下降。
其每一代进化的计算复杂度为O（Nm/2+1），其中N为种群大小，m为问题的目标个数。
Brockhoff等[19]将目标空间缩小技术与基于IH指标的方法结合起来，提出一种新的算法，通过使用不同的目标空间缩小方法提高基于IH指标的算法性能。
IH指标的计算是一个非常耗时的过程，对基于IH指标的算法有很大影响。
为了克服计算过于复杂的弊端，Bader等[20]提出了一种快速的近似计算方法，使用蒙特卡罗模拟近似计算解集的IH值，并提出了一种基于IH指标近似的多目标进化算法，在处理超多目标优化问题上取得了令人满意的成果。
通过将非支配排序和R2指标结合起来，Manriquez等[21]提出了R2-MOGA和R2-MODE 算法，在处理超多目标优化问题时有显著优势；Gomez等[22]也提出了一种基于R2指标的优化算法MOMBI，同样也取得了不错的优化效果。
3.4 混合算法在多目标进化算法中，研究人员提出了众多优化技术，不同技术均有其独特优势，例如基于Pareto支配关系的算法能够适应各种形状的Pareto前沿，但在处理超多目标优化问题时却显得不尽如人意；基于分解的算法通用性较好，但是常规的分解方法却容易导致解集多样性的丢失。
其它的优化技术也各有优缺点。
将这些技术混合起来，结合各种方法的优点来处理复杂的优化问题，也是一种非常有效的方法。
一种方法是将全局搜索与局部搜索结合起来，即多目标模因算法。
例如，在Adra等[23]的算法中，对每一代进化中求得的最优解使用局部搜索策略在目标空间进一步优化，随后将优化后的解映射到对应的决策空间并预测其具体的决策向量；在Wang等[24]的算法中，则使用局部搜索来生成子代解。
另一种广泛使用的方法是将不同方法中的搜索策略结合起来，例如将粒子群优化和进化算法结合起来[25]，在每一代中，由粒子群优化产生的解再使用进化算法进行优化。
另一方面，还可以根据进化过程的不同特性将整个进化过程划分为多个阶段，在不同阶段使用不同的搜索策略。
例如在Yang等[26]的算法中，进化过程包含3个阶段，分别侧重于被支配的解、平衡支配解和非支配解，以及着重于非支配解3个部分，结合NSGA-II算法的思想和局部增强搜索策略来实现各个阶段的进化过程。
4 结语多目标进化算法由于其基于种群的特性而成为处理多目标优化问题的一种热门方法。
本文进行了多目标优化问题的相关数学描述，简要介绍了相关理论定义。
根据多目标进化算法的特性，本文还将近年来的主流进化算法分为4类进行阐述，并分析了它们的优缺点，以更好地应用于多目标优化问题的求解。
参考文献：[1]POOLE D，MACKWORTH A，GOEBEL putational intelligence：a logical approach[M].Oxford University Press，1997.[2]ZITZLER E，THIELE L.Multiobjective evolutionary algorithms：a comparative case study and the strength Pareto approach[J].IEEE Transactions on Evolutionary Computation，1999，3（4）：257-271.[3]ZITZLER E，LAUMANNS M，THIELE L.SPEA2：improving the strength Pareto evolutionary algorithm[C].Eurogen，2001，3242（103）：95-100.[4]CORNE D W，KNOWLES J D，OATES M J.The Pareto envelope-based selection algorithm for multiobjective optimization[C].International Conference on Parallel Problem Solving from Nature.Springer Berlin Heidelberg，2000：839-848.[5]CORNE D W，JERRAM N R，KNOWLES J D，et al.PESA-II：region-based selection in evolutionary multiobjective optimization[C].Proceedings of the Genetic And Evolutionary Computation Conference （GECCO’2001），2001.[6]DEB K，PRATAP A，AGARWAL S，et al.A fast and elitist multiobjective genetic algorithm：NSGA-II[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182-197.[7]LAUMANNS M，THIELE L，DEB K，et bining convergence and diversity in evolutionary multiobjective optimization[J].Evolutionary Computation，2002，10（3）：263-282.[8]DEB K，MOHAN M，MISHRA S.Evaluating the epsilon-domination based multi-objective evolutionary algorithm for a quick computation of pareto-optimal solutions[J].Evolutionary Computation，2005，13（4）：501-525.[9]IKEDA K，KITA H，KOBAYASHI S.Failure of pareto-based MOEAs：does non-dominated really mean near to optimal？[C].Evolutionary Computation，Proceedings of the 2001 Congress on.IEEE，2001：957-962.[10]YANG S，LI M，LIU X，et al.A grid-based evolutionary algorithm for many-objective optimization[J].IEEE Transactions on Evolutionary Computation，2013，17（5）：721-736.[11]AGUIRRE H，TANAKA K.Space partitioning with adaptive ε-ranking and substitute distance assignments：a comparative study on many-objective mnk-landscapes[C].Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation.ACM，2009：547-554.[12]MIETTINEN K.Nonlinear multiobjective optimization[M].Springer Science & Business Media，2012.[13]ZHANG Q，LI H.MOEA/D：A multiobjective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation，2007，11（6）：712-731.[14]LI H，ZHANG Q.Multiobjective optimization problems with complicated Pareto sets，MOEA/D and NSGA-II[J].IEEE Transactions on Evolutionary Computation，2009，13（2）：284-302.[15]ASAFUDDOULA M，RAY T，SARKER R.A decomposition-based evolutionary algorithm for many objective optimization[J].IEEE Transactions on Evolutionary Computation，2015，19（3）：445-460.[16]GARZA-FABRE M，TOSCANO-PULIDO G，COELLO C A C，et al.Effective ranking+ speciation= many-objective optimization[C].2011 IEEE Congress of Evolutionary Computation （CEC）.IEEE，2011：2115-2122.[17]ZITZLER E，KNZLI S.Indicator-based selection in multiobjective search[C].International Conference on Parallel Problem Solving from Nature.Springer Berlin Heidelberg，2004：832-842.[18]EMMERICH M，BEUME N，NAUJOKS B.An EMO algorithm using the hypervolume measure as selection criterion[C].International Conference on Evolutionary Multi-Criterion Optimization.Springer Berlin Heidelberg，2005：62-76.[19]BROCKHOFF D，ZITZLER E.Improving hypervolume-based multiobjective evolutionary algorithms by using objective reduction methods[C].2007 IEEE Congress on Evolutionary Computation.IEEE，2007：2086-2093.[20]BADER J，ZITZLER E.HypE：an algorithm for fast hypervolume-based many-objective optimization[J].Evolutionary Computation，2011，19（1）：45-76.[21]DAZ-MANRQUEZ A，TOSCANO-PULIDO G，COELLO C A C，et al.A ranking method based on the R2 indicator for many-objective optimization[C].2013 IEEE Congress on Evolutionary Computation.IEEE，2013：1523-1530.[22]GMEZ R H，COELLO C A C.MOMBI：a new metaheuristic for many-objective optimization based on the R2 indicator[C].2013 IEEE Congress on Evolutionary Computation，2013：2488-2495.[23]ADRA S F，DODD T J，GRIFFIN I A，et al.Convergence acceleration operator for multiobjective optimization[J].IEEE Transactions on Evolutionary Computation，2009，13（4）：825-847.[24]WANG Y，CAI Z，GUO G，et al.Multiobjective optimization and hybrid evolutionary algorithm to solve constrained optimization problems[J].IEEE Transactions on Systems，Man，and Cybernetics，Part B （Cybernetics），2007，37（3）：560-575.[25]ELHOSSINI A，AREIBI S，DONY R.Strength Pareto particle swarm optimization and hybrid EA-PSO for multi-objective optimization[J].Evolutionary Computation，2010，18（1）：127-156.[26]YANG D，JIAO L，GONG M.Adaptive multi-objective optimization based on nondominated solutions[J].Computational Intelligence，2009，25（2）：84-108.（责任编辑：黄健）。
