（应用数学专业论文）基于参考点的演化多目标优化算法及性能评价研究.pdf

摘要 自2 0 世纪印年代初以来多目标优化问题就受到研究人员越来越多的关注 近些年对演化算法的研究，表明了这种方法比传统的搜索和优化方法更加有效。 演化多目标优化( e m o ) 算法被广泛地应用在各种问题中，在决策和优化领域 都引起了研究者极大的重视 本文对当前流行的演化多目标优化算法的基础和不同实现方法中的基本思 想进行了综合分析和归纳。阐明当前多目标优化领域的薄弱环节：带有偏好信 息的高维多目标优化演化算法和多目标优化算法性能的度量以此为基础确定 了本文的研究方法和目标具体的工作和创新点如下： 1 、通过在n s g a - 1 算法中加入新构造的变异算子和偏好算子，提出了基于 参考点的演化算法( 简称m r n s g a - 算法) ，来实现高维多目标优化问题的求 解。本文还对算法的时间复杂度和性能进行综合分析，数值实验验证了算法的 有效性。 2 、评价多目标优化算法的性能方法包括测试函数和度量准则两个基本要 素，针对标准双目标优化测试问题，系统的分析构造多目标优化测试函数的方 法，从理论上证明了构造方法的有效性。对常用的评价多目标优化算法的三个 度量准则做了综合分析，提出了评价偏好集的三个新度量准则，即r e r 、r s p 和r g d 。 最后对本文提出的算法和评价准则做出了总结，并对将来在多目标优化领 域的一些可能的发展方向进行了预测。 关键字：演化多目标优化，参考点，偏好集，测试函数，度量准则 a b s t r a c t r e s e a r c h e r sh a v em o r ea n d m o r e p a i d a t t e n t i o nt ot h e 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 np r o b l e m sf r o m1 9 6 0 s w e c a nc o n c l u d et h a te m o m e t h o d o l o g i e sm a y p r o v i d ea na d v a n t a g eo v e rt h e i rc l a s s i c a lc o u n t e r p a r t s , s u c h a sc l a s s i c a lr e s e a r c ha n d o p t i m a lm e t h o d st h r o u g ht h er e s e a r c ho ne v o l u t i o n a r ya l g o r i t h m sr e c e n t l y e m o a l g o r i t h m sh a v eb e e na p p l i e dt ov a r i o n sp r o b l e m sa n da t t a c h e di m p o r t a n c et ot h e r e s e a r c h e r si nd e c i s i o na n do p t i m a lf i e l d s 仳p a p e ra n a l y z e st h ef o u n d a t i o n so ft h ec u r r e n tp o p u l a rm o e a sa n dt h eb a s i c i d e ao fv a r i o u sm e t h o d so fm o e a si ng e n e r a l d e m o n s t r a t i n gt h ew e a kl o c a t i o no f m u l t i - o b j e c t i v eo p t i m i z a t i o nf i e l di sh i g h - d i m e n s i o ne v o l u t i o n a r ym u l t i - o b j e c t i v e o p t i m i z a t i o na l g o r i t h m s w i t h p r e f e r e n c e i n f o r m a t i o na n dt h em e a s u r eo ft h e p e d o r m a n c eo fm u l t i - o b j e c t i v eo p t i m i z a t i o na l g o r i t h m s ，s ot h a tw ea s c e r t a i nt h e r e s e a r c hm e t h o da n dg o a lo ft h i sp a p e r t h ew o r ka n dc r e a t i v ep o i mo ft h i sp a p e ra r c d e s c r i b e da sf o l l o w s ： 1 、p r e s e n t i n gt h e r e f e r e n c ep o 缸b a s e de v o l u t i o n a r y a l g o r i t h m ( n a m e l y m r - n s g a - i ia l g o r i t h m ) h i g h - d i m e n s i o nm 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 s a r es o l v e db yn s g a - i ia l g o r i t h mw i t ht h en e wm u t a t i o no p e r a t o ra n dp r e f e r e n c e o p e r a t o r t i m ec o m p l e x i t ya n dt h ep e f f o r m a n c oo ft h ea l g o r i t h ma r ea n a l y z e di n g e n e r a l t h ee f f e c t i v e n e s so ft h ea l g o r i t h mi st e s t e db yt h eu s eo fh i g h - d i m e n s i o nt e s t f u n c t i o n s 2 、t h em e a s u r eo ft h ep e r f o r m a n c eo fm u l t i - o b j e c t i v eo p t i m i z a t i o na l g o r i t h m s i n c l u d e st e s tf u n c t i o n sa n dm e t r i c s a n a l y z i n gt h ec o n s t r u c t i o nm e t h o d so f m u l t i - o b j e c t i v eo p t i m i z a t i o nt e s tf u n c t i o n s p r o v i n gt h ee f f e c to ft h ec o n s t r u c t i o n m e t h o d si n t h e o r y a n a l y z i n gt h r e em e t r i c su s e d i nm e a s u r i n gp e r f o r m a n c eo f m u l t i - o b j e c t i v eo p t i m i z a t i o na l g o r i t h m s w ep r e s e n t i n gt h r e en e wm e t r i c sr e r 、r s p a n dr g dt om e a s u r i n gt h eo b t a i n e dp r e f e r r e ds e t s 。 a tl a s t , t h ea l g o r i t h ma n dp e r f o r m a n c em e t r i c sa r ec o n c l u d ea n ds o m eo ft h e m o s tp r o m i s i n gf u t u r ep a t h so fr e s e a r c hi nm u l t i - o b j e c t i v eo p t i m i z a t i o na r e aa r ca l s o a d d r e s s e d k e y w o r d s ：e v o l u t i o n a r ym u l t i - o b j e c t i v eo p t i m i z a t i o n , r e f e r e n c ep o i n t s , p r e f e r e n c e s e t , t e s tf u n c t i o n s , m e t r i c s 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意 签名：啦日期：兰焉二垡。 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权 保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) i t 期：甚型：! ! ：f 武汉理工大学硕士学位论文 1 1 研究背景与意义 第1 章引言 自2 0 世纪6 0 年代初以来多目标优化( m u l t i o b j e c t i v eo p t i m i z a t i o n ) 问题就 受到研究人员越来越多的关注在多目标优化问题中，多个且标函数需要同时 进行优化由于目标之间无法比较和矛盾等现象，导致不一定存在在所有目标 上都是最优的解某个解可能在一个目标上是最优的但在另一个上是最差的。 因此，多目标问题通常存在一个解的集合，它们之间不能简单地进行比较好坏 对这种解来说，不可能使得在任何目标函数上的改进不损害至少一个其他目标 函数，这种解称作非支配解( n o n d o m i n a t e ds o l u t i o n s ) 和p a r e t o 最优解( p a 北t o o p t i m a ls o l u t i o n s ) 。 多目标优化的原则与单目标优化是不同的。在单目标优化中，我们的目的 是找到最好的解，这个解对应目标函数的最小值或最大值。而在多目标优化中， 由于目标之间是相互冲突的，所以通常不存在一个单一的最优解最终得到的 会是一组妥协解，即p a r c t 0 最优解因为在没有更进一步的考虑的前提下，这 些解中的任何一个都不能认为比其他的解更好，多目标优化的基本任务之一就 是找到尽可能多的p a r e t o 最优解一旦找到了这些解，通常需要从其他方面考 虑并做出决策，从它们中选择一个作为闯题的最终解决方案。当前多目标优化 算法的主要焦点集中在第一个任务，即找到p a f c l n 最优集或接近p a ”协最优集 的解集，并使得p a r e t o 前沿尽可能分布均匀 过去1 5 年里，演化多目标优化算法充分证实了它们在寻找有良好的收敛性 和分布性的p a 托t 0 最优解时的有效性由于研究工作的进展和源代码的开放性， e m o 过程被广泛的应用在各种问题中，在决策和优化领域都引起了研究者极大 的重视。 然而，最近的研究发现：e m o 方法在处理拥有大量数日的多目标优化问题 时，面临着极大的困难。表现在：( 1 ) 4 个或者更多个多目标问题空间的可视化 是一个难点，它限制了e m o 方法找到整个p a r e t o 最优集，( 2 ) 对于目标数目很 大的问题，一个个体总数较少的种群无法产生足够的选择压力使所有的非支配 武汉理工大学硕士学位论文 解朝p a r e l o 最优区域发展，( 3 ) 为了获得p a r e t o 解的多样性，所需的种群中个 体的数目与目标的数目成指数倍增长 尽管使用大种群或者更好的可视化技术可以解决拥有4 个目标( 或4 个左 右) 的优化问题，但是如果目标数日增如到l o 个或者更多，e m o 方法并不容易 找到具有广泛代表性的整个p a r e t o 前沿。如果我们从决策者的实际需要出发， 将焦点集中在他她将所关心的那些区域，那么e m o 方法可以找到带有偏好信 息的范围较小的p a 阳t o 解集。 传统的交互式多目标优化方法需要决策者提供一个参考方向、参考点或其 他线索，根据得到的线索将多目标转化为一个单目标优化问题，最终得到的是 一个单解，因为决策者提供的线索( 加权向量、参考方向、参考点) 仅仅是粗 略，模糊的信息，一个单解( 尽管对于给定的线索来说是最优的) 并不能提供 给决策者所关心的区域附近的解的特性。实际上，决策者希望根据他她提供的 信息，得到一个他所感兴趣的那些区域的一个较小范围的p 姗t o 最优解集，并 从中做出选择，如果能同时找到他关心的多个区域信息，那么决策者能够做出 个更有效的最终决定。 ， 1 2 国内外研究现状 自1 9 6 0 年以来，人们对于模拟生物以及由此开发的针对复杂优化问题的有 效算法产生了浓厚兴趣当前在该领域中常常引用的术语就是演化计算 ( e v o l u t i o n a r yc o m p u t a t i o n ) 它包含以下一些主要算法：遗传算法( g e n e t i c a l g o r i t h m s ) ，演化策略( e v o l u t i o ns t r a t e g i e s ) ，演化规划( e v o l u t i o n a r yp r o g r a m m i n g ) 和遗传程序设计( g e n e t i cp r o g r a m m i n g ) 当然还存在若干将上述算法的各种特 点加以结合而形成的混合算法。 。 作为强有力且应用广泛的随机搜索和优化方法，遗传算法可能是当今影响 最广泛的演化计算方法之一 在过去的几年中，将遗传算法应用于多目标优化问题成为研究热点，这种 算法通常称作演化多目标优化( e v o l u t i o n a r ym u l t i o b j e c t i v eo p t i m i z a t i o n ) 或遗传 多目标优化( g e n e t i c m u l t i o b j e c t i v c o p t i m i z a t i o n ) 遗传算法的基本特点是多方向 和全局搜索，带有潜在解的种群因此能够一代一代地维持下来。从种群到种群 的方法对于搜索p a r e t o 解来说是有益的。 2 武汉理工大学硕士学位论文 优化处理的是具有多个变量且通常需要服从等式和( 或) 不等式约束的最 小化或最大化函数的问题。在运筹学、管理科学和工程设计中，优化问题处于 非常重要的地位许多工业工程的设计问题非常复杂而困难，以至于难以采用 传统优化方法进行求解 许多现实世界的工程设计问题或决策问题设计到同时优化多个目标多目 标优化的原则有别于单目标优化 在处理多目标优化问题时，传统的搜索和优化方法并不十分有效，这是因 为( 1 ) 它们不能在单次运行中找到多个解，必须经过多次的运行才能找到期望 的p a r c t o 最优解集，( 2 ) 它们不能产生多个不同的p a r e t o 最优解，( 3 ) 它们不 能有效处理具有离散变量和多个最优解的问题。 1 2 1 用演化算法解决多目标优化问题 近些年对演化搜索算法的研究，表明了这种方法比其他的方法更加有效 因为它们在搜索中使用了种群，能在单次运行中找到多个p a r e t o 最优解。在演 化算法中加入的多样性维持机制能够使找到的解具有广泛的差异性 s c h a f f e r 了解到遗传算法在求解多目标优化问题潜力的基础上，于1 9 8 5 年 提出了向量评价遗传算法( v e c t o re v a l u a t e dg e n e t i c a l g o r i t h m , v e g a ) i 埘，它将 简单遗传算法扩展为能够包容不可比较的多个目标的算法，实际上就是在遗传 算法的基础上对选择操作进行了改进。 基于封套p 眦t o 选择算法( p a r e t oe n v e l o p e - b a s e ds e l e c t i o na l g o r i t h m , r e s a ) 由c o r 酩c ta 1 提出闭，采用显型空间( p h e n o t y p es p a c e ) ( 也就是且标函数空闯) 的超栅格分割( h y p c 吁- g r i dd i v i s i o n ) 维持种群的多样性( d i v e r s i t y ) 它的选择机 制基于拥挤度量( c r o w d i n gm e a s u r e ) ，同样使用了前面提到的超栅格，它决定什 么样的解能加入到外部种群中因此，在p e s a 中，外部种群在算法中的角色非 常重要，它不仅确定维持多样性的机制，而且被用于选择的执行 p e s a 有一个改进的版本，称之为p e s a - i i ，该算法除了选择机制( 基于区 域) 与p e s a 不同，其它的做法都是相同的在基于区域的选择机制中，选择的 单位是一个超盒子( h y p e r b o x ) 而不是一个个体1 2 l l ，这个过程使用任何传统的选 择技术选择一个超盒子，然后随机的选择这个盒子中的一个个体，这个改进版 本的主要动因是减少传统的m o e a s ( 即那些基于p a r e t o 排序的算法) 的计算费 用。 3 武汉理工大学硕士学位论文 小生境p m e t o 遗传算法( n i c h e d p a m t o g e n e t i c a l g o r i t h m ，n p g a ) 2 2 1 于1 9 9 4 年由j e f f r e y h o r n 等人提出，它的选择机制采用p a r e t o 支配竞争( p a r e t o d o m i n a t i o n t o u r n a m e n t s ) 方法 与n p g a 的锦标赛选择不一样的是，n p g a 2 仅使用p a r e t o 等级决定锦标赛 的胜利者，个体的等级由它的支配度( d e g r e eo fd o m i n a t i o n ) 决定n p g a 2 被 成功用于地下水补给系统的设计 力度p a r e t o 演化算法( s t r e n g t hp a r e t oe v o l u t i o n a r y a l g o r i t h m ，s p e a ) 俐于 1 9 9 9 年由e c k a r t z i t z l e r 和l o t h a r t h i e l e 提出，s p e a 2 中的档案更新算子与s p e a 有两个方面不同：( 1 ) 档案中的个体数目是恒定不变的；( 2 ) 截断( t r u n c a t i o n ) 方法防止边界解被移除。 s p e a 2 与s p e a 相比主要的不同之处在于：( 1 ) 改进了适应值的分配策略， 考虑了每个个体能被多少个体支配以及它能支配多少个体；( 2 ) 包含了最近邻 域密度估计技术，引导搜索过程更加准确；( 3 ) 一种新的档案截断方法保存了 边界解。 非支配分类遗传算法( n o n - d o m i n a t e ds o r t i n gg e n e t i ca l g o r i t h m ，n s g a ) 于 1 9 9 4 年由n s r i n i v a s 和k a l y a n m o yd e b 提出【卅。该算法基于一个非支配分类过 程，非支配分类过程的一个突出特点是等级选择方法( r a n k i n g s e l e c t i o n m e t h o d ) ， 在选择以前，种群根据个体的非支配性进行掉序。所有的非支配个体从当前种 群中首先被识别出来，然后，假定这些个体组成第一非支配前沿，它们被分配 一个较大的哑适应值然后，这些非支配个体被暂时忽略，对剩下的种群以相 同的方式得到第二非支配前沿。这个过程直到整个种群被分成若干个前沿 n s g a 有一个改进版本n s g a - h 2 5 1 ，考虑到n s g a 算法的三个方面的缺 点；( 1 ) 时间复杂度为o ( m n 3 1 ，其中m 是目标的数目，是种群的大小；( 2 ) 非精英方法；( 3 ) 需要确定共享参数。n s g a - i i 算法力图克服上述问题，它能 将时间复杂度降低到o ( m n 2 ) ，结合父代和子代种群选出( 根据适应值和分布性) 最好的个解产生交配池 p a r e t o 档案演化策略( p a r e t o a r c h i v c de v o l u t i o ns t r a t e g y , p a e s ) 算法于2 0 0 0 年由k n o w l e s 提出闭它始于一个单一的染色体( 当前解) ，然后产生该染色体 的副本并对这个副本进行变异，与当前解进行评价比较后确定新的候选解和决 定是否将这个变异的副本放入档案中 演化多目标优化的研究者都在努力研究新的算法，也在疑惑什么样的算法 4 武汉理工大学硕士学位论文 能成为第三代演化多目标优化算法。重点似乎集中在算法的效率 2 7 , 2 s 1 和空阃数据 结构，目的是为了提高外部种群的效率和存储能力 2 9 , 3 e l 。 1 2 2 解决多目标优化问题的新方法 这些年研究者在演化多目标优化上已经进行了大量的研究，却很少将研究 扩展到基于种群的其他启发式方法。近几年，有些研究者又提出了一些超启发 式算法，如人工免疫系统1 3 1 , 3 2 1 ，蚊群优化1 3 3 3 4 ) ，粒子群优化1 3 5 洲 2 0 0 4 年，c o e l l o 在粒子群优化中加入了p a r e t o 支配的概念，目的是在处理 多目标优化问题时加入启发式的策略该算法采用了一个外部粒子集引导其他 粒子的飞行，并加入了一个独特的变异算子以增强算法搜索的能力2 0 0 5 年， c o e l l o 使用人工免疫系统解决多目标优化问题( 包括不含约束条件的和含约柬条 件的问题) ，使用p a r e t o 支配和可行性的概念确定可以被克隆的解，并采用了两 种变异方式：均匀变异和非均匀变异。通过标准的测试函数和度量准则，粒子 群优化和人工免疫系统的方法与流行的演化多目标优化算法的比较中，均显示 了它们的有效性 文化算法由r o b e r tg r e y n o l d s 提出，它被誉为基于遗传和自然选择机制的 演化算法的补充构件，基于社会学提出的理论建立文化演化的模型它是一种 能使得搜索更加有效的技术，包含在演化过程中获得的域知识。 1 2 3 演化多目标优化的应用 当前，演化多目标优化的应用可以粗略的分成三类 3 1 ：工程、工业和科学。 应用最为广泛的可以说是工程领域，因为很多工程问题已经被适宜的数学模型 描述出来，这点非常易于使用演化算法它们中的典型例子有：电子工程、水 力工程、结构工程、航空工程、机器人、控制、通信、土木工程、交通工程。 工业上的应用是演化多目标优化的第二个应用领域。代表例子有：设计和制造 业、调度、管理演化多目标优化在科学领域的应用也非常广泛，包括：化学、 物理、医学、计算机科学 研究演化多目标优化算法的现实应用对许多领域的问题都做出了极大的贡 献( 毫无疑问，因为大多数现实世界的阀题在本质上都是多目标的) 5 武汉理工大学硕士学位论文 1 3 本文所作的工作 本文主要做了以下几方面的工作： 第1 章引言：阐述了多目标优化问题的研究现状及当前流行的解决方法， 包括演化算法，超启发式算法等，指出目前该领域面临的主要困难和挑战，点 明论文的研究方向为求解带有偏好信息的高维多目标优化问题。 第2 章演化多目标优化算法：对当前流行的演化多目标优化算法的基础和 不同实现方法中的基本思想进行了综合分析 第3 章基于参考点的多目标优化算法：综合阐述了传统解决带有偏好信息 的多目标优化闯题的思想和算法，系统地描述了基于参考点并加入新变异算子 和偏好算子的n s g a - 算法( 简称m r - n s g a - i i 算法) 的思想和详细流程。将 m r - n s g a - i i 算法应用在双目标、五目标和十目标的标准测试问题上，三个数值 实验均证实了该算法的有效性。并对m r n s g a - i i 算法的计算时间复杂度进行 了分析。 第4 章多目标优化算法性能度量：提出评价演化多目标优化算法性能包括 两个基本要素；测试函数和度量准则。概括介绍了构造多目标优化测试函数的 方法，从数学推导的角度证明了标准双目标优化测试问题的p a r e t o 前沿的确切 位置。对常用的评价多目标优化算法的三个度量准则做了综合分析，在此基础 上提出三个准则评价基于参考点的优化算法得到的偏好集，分别是r e r 、r s p 和r g d 第5 章结论：对本文进行了归纳。概括了本文的主要工作和创新点，提出 了下一步研究工作和研究方向。 6 武汉理工大学硕士学位论文 第2 章演化多目标优化算法 2 。1 多目标优化的基本概念 最优化处理的是在一堆可能的选择中搜索对于某些目标来说是最优解的问 题如果仅考虑一个目标，就成为单目标优化问题，这种问题在过去的5 0 年中 已经得到了深入的研究如果存在的目标超过一个并需要同时处理，就成为多 目标优化问题多目标优化问题起源于许多实际复杂系统的设计、规划和建模 问题，这些系统所在的领域包括工业制造、城市运输，资本预算、森林管理、 水库管理、新城市的布局和美化、能量分配等等。几乎每个重要的现实生活中 的决策问题都需要在考虑不同约束的同时处理若干相互冲突的目标，这些问题 大大增加了问题的复杂程度。自2 0 世纪6 0 年代早期以来，多目标优化问题吸 引了越来越多不同背景研究人员的注意力。许多学者对多目标优化问题做出了 重要贡献。其中p a r e t o 可能是本领域公认的开创者之一遗传算法作为解决多 目标优化问题的新方法受到了相当的关注。 不失一般性，多目标优化( m u l t i o b j e c t i v eo p t i m i z a t i o n s ) 问题可以表述为下 面的形式： m n 口。一 ( 张z ：- ，2 ( 劲，g ) ( 2 - - 1 ) 5 0 g j ) o , i - 1 ，2 ，m ( 2 2 ) 其中孑r 。是带有一个决策变量的向量， ) ，2 仃) ，无 ) 是鼋个目标函 数，g ；侈) 是m 个不等式约束函数，由它们形成了可行解区域。通常在决策空间 中用s 来表示可行区域，如下所示： s - i 露。l g i ( i ) o ，f l 2 , ，栅 ( 2 - - 3 ) 当目标函数的个数较少的时候，可以在决策空间和目标空间中用图形来表 示多目标优化问题s 用来表示决策空间( d e c i s i o ns p a c e ) 中的可行区域，z 用 来表示目标空间( o b j e c t i v es p a c e ) 的可行区域 z 一仁r 9 肛l 一 g ) z ：- ，2 g ) op l , 0 - ，f ) i 耐( 2 - - 4 ) 其中三尺- 是带有鼋个耳标函数的向量 7 武汉理工大学硕士学位论文 2 1 1 非支配解 多目标优化问题与单目标优化问题的差异非常大。在有单个目标时，人们 寻找最好的解，这个解比其他所有的解都要好在有多个目标时，由于存在目 标之间的无法比较和冲突现象，不一定有在所有目标上都是最优的解一个解 可能在某个目标上是最好的，但在其他目标上是最差的因此在有多个目标时， 通常存在一系列无法简单进行相互比较的解。这种解称作非支配解 ( n o n d o m i n a t c ds o l u t i o n s ) 或p a r e t o 最优解( p a r c t oo p t i m a ls o l u t i o n s ) ，它们的特 点是：无法在改进任何目标函数的同时不削弱至少一个其他目标函数。对于一 个给定的目标空间z 中的非支配解，它在决策空间中的原象点称作有效的 ( e f f i c i e n t ) 或非劣的( n o n i n f e r i o r ) s 中的一点是有效的当且仅当它的象在z 中 是非支配的 对给定点z oe z ，它是非支配的( n o n d o m i n a t c d ) 当且仅当不存在其他点 z e z ，使得对于最小化情况有： 缸缸”对于某些j 他2 ，办 ( 2 5 ) z ，墨毛” 对于所有其他f _ k( 2 6 ) 如果对于z o 存在其他点z 满足上式，则z o 点称作目标空间中的支配点( d o m i n a t e d p o i n t ) 。 对给定点i oe s ，它是有效的( e f f i c i e n t ) 当且仅当不存在其他点j s ，使 得对于最小化情况有： ，i ) ，l ( j o ) 对于某些七仉2 ，q ( 2 7 ) 正 ) g o ) 对于所有其他，- k ( 2 - - 8 ) 如果对于i o 存在其他点i 满足上式，则妒点在目标空间中是无效的( i n e f f i c i e n t ) 决策空间中的某点是有效的当且仅当它的象是目标空间中的非支配点。 在目标空间中有一个特殊点叫做理想点( i d e a lp o i n t ) ，用 z - 0 l ，z 2 ，) 来表示，其中气。- m i l l 何准s ，k - 1 , 2 , ，口。点z 称作 理想点因为通常该点无法达到。对于每个目标来说，寻找气是可能的但寻找 一个能够同时最小化每个 ) ，k - 1 , 2 , ，q 的点z 通常是非常复杂甚至根本不 存在的。 8 武汉理工大学硕士学位论文 2 1 2 偏好结构 多目标问题解的基本特征之一是存在一组无法相互进行比较的有效解 ( e f f i c i e n ts o l u t i o n s ) 在实际的决策情况中，通常需要从非支配解中选择一个作 为给定问题的最终解。然而，如果不提供对于不同目标附加的偏好信息，很可 能无法从解中进行选择。因此，如何从这些可选的非支配解中做出最后的选择 本质上依赖于个人主观的偏好。从概念上讲，偏好( p r e f e r e n c e ) 是通过采用某 人对目标的价值判断来对有效集合中无法进行比较的解给出排序( o r d e r ) 偏好 反映了某人根据对问题事先掌握的知识对所有目标进行的折中或者对某个目标 进行的强调。给定了偏好结构我们就可以将非支配集中可选的解进行排序，然 后获得最终解，这就是通常决策过程的结果这个最终解称作最优妥协解( b e s t c o m p r o m i s e ds o l u t i o n ) 一 偏好通常由二元关系来表示二元关系( b i n a r yr e l a t i o n ) 就是一组有序对 对于一组给定对h 和，可能且仅可能发生下面的一种关烈4 l ： 1 ，h 比v 好，或对h 的偏好大于v ，用h 卜v 来表示 2 、h 比p 差，或对h 的偏好小于 ，用h 0 算术杂交定义为两个向量( 染色体) 的组合如下： - 瓴+ 也毛 - 坼：+ 九毛 ( 2 1 3 ) ( 2 1 4 ) ( 2 1 5 ) 武汉理工大学硕士学位论文 著名的n s g a - i i 算法采用的就是这种杂交方式，其中 和如的计算如下： o 5 ( 1 + 幻) ( 2 - - 1 6 ) 九一o 5 ( 1 一, q ) ( 2 一1 7 ) l2 r a n d ( 1 ) 者a r a n d ( 1 ) 0 5 叼。 ，1与 ( 2 1 8 ) i ( _ 矧删( 1 ) 0 5 其中m u - 2 0 为杂交分布指数。 变异算子在染色体中产生随机变化，通常被用作次要的算子。 在n s g a - i i 算法中，采用的变异方式为； j - i + d e l t a( 2 1 9 ) d e l t a - ：删君阳勰：慧c220)1 7 i 一r a n d ( 1 ) ；：虿 r a r 如l 印土u ， 其中m l , m - 2 0 为变异分布指数。 2 2 4 选择 选择将遗传搜索引导到搜索空间中有前途的区域中在过去的2 0 年中提出 的、验证并比较了许多选择方法通常采用的选择方法如下： i 、轮盘赌选择( r o u l e t t ew h e e ls e l e c t i o n ) 2 、( f + a ) 选择( ( p + a ) s e l e c t i o n ) 3 、竞争选择( t o u r n a m e n ts e l e c t i o n ) 4 、稳态复制( s t e a d y - s t a t er e p r o d u c t i o n ) 5 、排序与比例变换 6 、共享( s h a r i n g ) h o l l a n d 提出的轮盘赌选择是最知名的选择方式嘲，其基本的原理是根据每 个染色体适应值的比例来确定个体的选择概率或生存概率，特点就是随机采样 过程。与比例选择不同，b a c k 提出了似+ a ) 选择。该方法为确定性选择过程， 从父代和子代中选取最好的染色体嗍 g o l d b c r g ，k o r b 和d e b 提出的竞争选择( t o u r n a m e n ts e l e c t i o n ) 同时包含随 机和确定性的特征i “该方法随机选择一些染色体并从中选出最好的来进行繁 殖选取的染色体数量称作竞争规模( t o u r n a m e n ts i z e ) 常用的竞争规模为2 ， 武汉理工大学硕士学位论文 这种情况被称作二进制竞争( b i n a r yt o u r n a m e n t ) 由o o l d b e r g 和r i c h a r d s o n 针对多峰函数优化提出的共享方法【1 4 l 可以用来维 持种群多样性共享函数就是一种用予根据个体在某个距离内与其他个体相邻 的程度来确定该个体适应值下降多少的方法由于适应值的下降，在拥挤的峰 周围的个体的复制概率受到抑制，而其他个体则易于产生后代 2 3 演化多目标优化 在过去的2 0 年中，演化算法( 特别是遗传算法) 作为多目标优化问题的新 求解方法受到了相当程度的关注，这就诞生了演化或遗传多目标优化这个主 题已经由f o n s e c a 和f l e m i n 9 1 4 2 1 ，i i 响【4 3 l 、t a m a k i 、k i t a 和k o b a y a s h i 进行了综 述。本节将简要描述多目标优化演化算法不同实现方法中的一些基本思想。某 些有代表性的方法将在后续几节中进行详细介绍 2 3 1 适应值分配机制 遗传算法本质上是一种求解的超策略当采用遗传算法来求解给定的问题 时，有必要对其主要组成部分( 比如编码方式、重组算子、适应值分配、选择、 约束处理等等) 进行改进使其获得对给定问题更有效的实现。由于多目标优化 问题是约束和组合优化问题的自然扩展，过去2 0 年里在用遗传算法求解约束优 化问题和组合优化问题中开发的许多实用方法和技巧都可以方便地应用于多目 标优化问题中因此，当考虑如何将遗传算法应用于多目标优化问题时，我们 仅需考虑与问题相关的一些特殊情况。 用遗传算法求解多目标优化问题中出现的一个特殊情况就是如何根据多个 目标来确定个体的适应值。适应值分配机制在过去的1 0 年中得到了广泛的研究， 已经提出并测试了若干种方法。这些方法可以粗略地分类如下： 1 、向量评价方法 2 、权重和方法 3 、基于p a r e t o 方法 4 、妥协方法 5 、耳标规划方法 根据偏好信息与适应值函数结合程序的不同，这些方法包括从给定全部偏 1 4 武汉理工大学硕士学位论文 好信息( 当直接组合目标函数或将其进行捧序时) 到不给任何偏好信息( 当采 用基于p a r e t o 的方法时) 另外的一个显著特点是可以先给出一个租略的偏好， 随着进化搜索的进程来对偏好进行持续的细化偏好的持续细化类似于多目标 优化中经常使用的交互式过程，在这种过程中决策者在每次迭代过程中修改偏 好。细化机制的独特之处在于偏好是随着进化搜索的过程由某种适应性改善机 制来逐渐改善的，而不是由决策者在每次迭代过程中进行干预当然交互式过 程也可以结合进遗传搜索来指导偏好细化。 2 3 2 适应值共享和种群多样性 适应值共享( f i t n e s ss h a r i n g ) 是维持种群多样性的一种技术首先需要区分 下面两类共享技术：( 1 ) 多峰函数中的共享( s h a r i n gi nm u l t i m o d a lf u n c t i o n s ) ， ( 2 ) 沿着p a r e t o 边界的共享( s h a r i n ga l o n gt h ep a r e t of i o n t i e r ) 。适应值共享由 g o l d b e r g 和r i c h a r d s o n 针对多峰函数优化提出m 。后来共享方法在遗传多目标 优化中进行扩展，目的是沿着非支配解边界维持种群。 遗传算法用于求解多峰函数的一个问题是，由于选择过程中随机误差的作 用，有限的种群最终收敛到一个最优解上。这种现象称作遗传漂移( g e n e t i c d r i f t ) 共享技术的目的就是防止遗传漂移并促进均匀采样。换句话说，就是在搜索空 间的不同峰中分布种群，每个峰根据其高度的比例得到种群中一部分个体为 了达到这个目的，就产生了适应值降低( f i t n e s s d e g r a d a t i o n ) 的概念如果某个 峰有太多的个体，该峰中所有个体的适应值都将降低以减小其复制能力。 共享函数( s h a r i n gf u n c t i o n ) 是根据某个体周围的拥挤程度来确定其个体适 应值降低程度的方法两个个体之间距离的度量可以在两个不同的空间中定义， 于是产生两种类型的适应值共享：基因型共享( g e n o t y p i cs h a r i n g ) 和表现型共 享( p h e n o t y p i es h a r i n g ) ，基因型共享中两个个体之间的距离在编码空间度量； 表现型共享中距离在解码空间度量。d e b 的工作指出，一般来说，表现型共享比 基因型共享要好l 叫 在遗传多目标优化中，共享方法可以分为下面两类：( 1 ) 目标空间中的共 享( s h a r i n go nt h eo b j e c t i v es p a c e ) ，( 2 ) 解空间中共享( s h a r i n go nt h es o l u t i o n s p a c e ) 目标空间中的共享试图得到整个p a r e t o 集合上的均匀采样：解空间中的 共享试图在允许的解集中进行均匀采样目标空间中的采样由f o n s e c a 和 f l 咖i n g i 埘提出在多峰函数优化中，共享在解空间中进行通常需要关于有限 武汉理工大学硕士学位论文 峰数量的先验知识和解空间中小生境均匀分布的假设对于收敛来说，许多个 体根据局部最优解适应值的比例被保留在局部最优解上与此相反，在多目标 优化中情况则不同。不再存在任何局部峰。p a r e t o 边界上的点都是同等优秀的 我们更为关心维持一组全局非支配解，最好它们能够在全局折中表面( g l o b a l t r a d e - o f f s u r f a c e ) 上均匀地相互隔开并且有代表性采用捧序方法会迫使搜索唯 一地集中于全局最优解上通过在目标值域的非支配个体上，而不是决策变量 域上实现适应值共享，可以期望能够实现在全局折中表面上非支配个体的均匀 分布。 解空间中的共享由s r i n i v a s 和d e b 提出旧。其主要关注点是沿着p a r e t o 边界 ( p a r e l of r o n t i e r ) 的多样性可能不对应着解空间中的多样性，而解空间中的多样 性对于决策者来说很重要通过根据下式计算两个个体之间的共享函数来实现 共享： 眦，一 ：- 一目2 【u 其中略是两个个体之间的表现型距离，而口是两个个体成为同一小生境成员 所允许的最大表现型距离。 如果希望种群在多个最优区域中分布，交配限制( m a t i n gr e s t r i c t i o n ) 就成 为另一个值得考虑的问题。交配限制假设相邻的个体在几何上是相似的，因此 它们的交配可以形成稳定的小生境在多峰优化中很容易理解；不同局部峰所 在的区域一般具有非常不同的遗传表示因此交配