（计算机软件与理论专业论文）演化多目标优化测试问题的构造.pdf

摘要 多目标优化问题起源于许多实际复杂系统的设计、规划和建模问题，几乎 每个重要的现实生活中的决策问题都需要在考虑不同约束的同时处理若干相互 冲突的目标，这就大大增加了问题的复杂程度。自2 0 世纪6 0 年代早期以来， 多目标优化问题吸引了越来越多不同背景研究人员的注意力。 目前多目标优化领域的研究工作主要集中在如何提高多目标优化演化算法 的效率和有效性，然而，该领域的一个重要的研究方向是如何构造标准的测试 问题和度量准则以正确地评价算法的性能。大多数算法研究者对这个方面没有 引起足够的重视。 本文在广泛深入地查阅了国内外的有关文献和著作的基础上，对多目标优 化演化算法的关键操作及特点进行了分析和总结，对有关多目标优化测试问题 的构造方法进行了充分的探讨，提出现今的热点问题之一，即动态多目标优化 测试问题的构造方法。本文的主要内容如下： 1 、对多目标优化演化算法的不同实现方法中的基本思想进行了综合分析； 提出一个求解种群中的非支配集的新算法，设计了多目标优化演化算法的基本 框架。 2 、系统地阐述了如何构造双目标优化测试问题和可扩展的多目标优化测试 问题的方法；对双目标优化问题的p a r e t o 最优集和p a r e t o 前沿的确切位置从理 论上进行了证明，给出多目标优化测试问题的实例。 3 、对动态多目标优化测试问题的类型和特点进行了分析；提出将静态的多 目标优化测试问题直接转化为动态多目标优化测试问题的构造方法，并给出了 动态多目标优化测试问题的实例。 4 、动态多目标优化测试集的构造是较新的研究课题，研究的难度也相对较 大，本文还只是做了一些初步的研究工作，最后对将来在多目标优化领域的一 些可能的发展方向做出了总结和预测。 关键字：多目标优化演化算法，多目标优化测试问题，p a r e t o 最优集， p a r e t o 前沿，可扩展 a b s t r a c t m 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 ( m o p s ) o r i g i n a t e d f r o m d e s i g n ， p l a n n i n ga n dm o d e l i n go fc o m p l e xs y s t e m si nr e a l - w o r l d a l m o s te v e r yi m p o r t a n t d e c i s i o np r o b l e m si nr e a ll i f en e e dd e a lw i t hc o n f l i c t i n go b j e c t i v e sw i t hv a r i o u s c o n s t r a i n s ，w h i c hh a ss i g n i f i c a n t l ya d d e dt h ec o m p l e x i t yo ft h ep r o b l e m s f r o me a r l y 1 9 6 0 s ，m o p sa t t r a c t e ds i g n i f i c a n ta t t e n t i o no fr e s e a r c h e r si nd i f f e r e n tb a c k g r o u n d m o s to ft h ec u r r e n tr e s e a r c hc o n c e n t r a t e so ni m p r o v i n gt h ee f f i c i e n c ya n d e f f e c t i v e n e s so fm u l t i o b j e c t i v eo p t i m i z a t i o ne v o l u t i o n a r ya l g o r i t h m s ( m o s a s ) h o w e v e r ，t h ei m p o r t a n ta s p e c to ft h i sa r e ai sh o wt oc o n s t r u c tt h es t a n d a r dt e s t p r o b l e m sa n dm e t r i c s i no r d e rt of a i r l ya s s e s st h ep e r f o r m a n c eo fm o e a s u n f o r t u n a t e l y , m o s to ft h er e s e a r c h e r sh a v e n tp a i dm u c ha t t e n t i o nt ot h i si s s u e a f t e rr e a d i n gal a r g en u m b e ro fd o m e s t i ca n do v e r s e a sl i t e r a t u r e $ a n db o o k s ，w e a n a l y z ea n ds u mu pt h ek e yo p e r a t i o n s a n df e a t u r e so fm o e a s ，d i s c u s st h e c o n s t r u c t i o nm e t h o d so fm 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 tp r o b l e m s ( m o t p s ) ，a n d p r e s e n tt h ec o n s t r u c t i o nm e t h o do fd 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 nt e s t p r o b l e m s m o t p s ) w h i c hi so n eo ft h eh o tt o p i c si nc u r r e n ty e a t s t h em a i n c o n t e n t so ft h i sp a p e ra r ed e s c r i b e da sf o l l o w s ： 1 a n a l y z i n gt h eb a s i ci d e ao fv a r i o u sm e t h o d so fm o e a s i ng e n e r a l an e w a l g o r i t h mw a sp r e s e n t e df o ro b t a i n i n gn o n d o m i n a t e ds e to fap o p u l a t i o n ；t h eb a s i c f r a m e w o r ko fm o e a sw a sd e s i g n e d 2 i l l u s t r a t i n gh o wt o c o n s t r u c tt w o - o b j e c t i v eo p t i m i z a t i o nt e s tp r o b l e m s ( t o t e s ) a n ds c a l a b l em o t p s ，p r o v i n gt h ee x a c tl o c a t i o no fp a r e t oo p t i m a ls e ta n d p a r e t of r o n to fac l a s so ft o t p st h e o r e t i c a l l y , a n dt h e ng i v i n gs o m ee x a m p l e s 3 a n a l y z i n gt h et y p e sa n dc h a r a c t e r i s t i c so fd m o t p s ，p r e s e n t i n gt h em e t h o d a n de x a m p l e so fa l l o w i n gs t a t i cm o t p st ob ed i r e c t l yt r a n s f e r r e dt ot h ed m o t p s , a n dt h e ng i v i n gs o m ee x a m p l e s 4 t h ec o n s t r u c t i o fd m o t p si san e wa n dd i f f i c u l tr e s e a r c ht o p i c t h i sp a p e r d i ds o m ee l e m e n t a r yw o r kp r e s e n t l y a tl a s t ，s o m eo ft h em o s tp r o m i s i n gf u t u r ep a t h s o 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 ea l s oa d d r e s s e d k e y w o r t b ：m u l t i - o b j e c t i v eo p t i m i z a t i o ne v o l u t i o n a r ya l g o r i t h m s , 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 t e s tp r o b l e m s ，p a r e t oo p t i m a ls e t , p a r e t oo p t i m a lf m n s c a l a b l e 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名：窿鸳坠 日期：丝氇兰旦兰! 璺 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留、送交论文的复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段 保存论文。 ( 儡窟钓论之存召啐窟后应( 蔓考此规定) 警帐尸 武汉理工大学硕士学位论文 1 1 研究背景与意义 第1 章引言 最优化处理的是在一堆可能的选择中搜索对于某些目标来说是最优解的问 题。如果仅考虑一个目标，就成为单目标优化问题，这种问题在过去的5 0 年中 已经得到了深入的研究。如果存在的目标超过一个并需要同时处理，就成为多目 标优化问题i l j 。 多目标优化问题起源于许多实际复杂系统的设计、规划和建模问题，这些系 统所在的领域包括工业制造、城市运输、资本预算、森林管理、水库管理、新城 市的布局和美化、能量分配等等。几乎每个重要的现实生活中的决策问题都需要 在考虑不同约束的同时处理若干相互冲突的目标，这些问题大大增加了问题的复 杂程度l 。 例如，当设计复杂的硬件软件系统的时候，一个最优的设计是最小化费用和 能源消耗，而最大化其它性能，显然这些目标是相互冲突的。一种情况是性能高 的同时费用也高，另一种情况则是费用低，相应的能源消耗高。 自2 0 世纪6 0 年代早期以来，多目标优化问题吸引了越来越多不同背景研究 人员的注意力。许多学者对多目标优化问题做出了重要贡献。其中p a r e t o 是本领 域公认的开创者之一。 多目标优化问题需要同时处理一组不可比较而且相互冲突的目标，通常情况 下，没有一个单一的最优值，而是得到一个解集。如果我们不包含任何的偏好信 息，那么这个解集中的任何一个解不会比其它的解更优，它们就是p a r e t o 最优解。 在合理的时间里搜索p a r e t o 最优解的工具能帮助决策者做出最后的决定【2 i 。 1 2 国内外研究情况 在s c h a f f e r ( 1 9 8 4 ) 的先驱工作( 2 0 世纪8 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 ne v o l u t i o n a r ya l g o r i t h m s ，m o e a s ) 。大 部分研究m o e a s 的源动力都来自于g o l d b e r g ( 1 9 8 9 ) 的非支配遗传算法。 演化算法( e v o l u t i o n a r y a l g o r i t h m s ，e a s ) 特别适合于解决多目标优化问题。 e a s 有一个独特的性质一一基于种群的搜索方法，使得算法在单次的模拟运行中 武汉理工大学硕士学位论文 能够并行处理一组解，通过再结合( r e c o m b i n a t i o n ) 算子深度扩展这组解，最终 找到多个p a r e t o 最优解。e a s 比其它的盲目搜索策略在处理多目标优化问题时要 好，尽管这个结论需要提及“没有免费的午餐( n of r e cl u n c h ) ”的理论。到目前 为止，鲜有不是基于演化算法的多目标优化算法。 在多目标优化领域，很少有文献讨论引起m o e a s 收敛到p a r e t o 前沿和维持 种群多样性的难度的问题特性；从事构造标准测试问题的研究人员比起算法研究 者来说也相对较少，然而，测试函数正是评价算法性能的前提和基础。我们认为 一个算法的真正的有效性应该表现在将它应用在难测试问题上表现出来的性能。 测试问题的构造是多目标优化领域一个重要而特殊的研究课题，在m o e a s 的各种活动中都非常有用，比如评价一个新的m o e a 的性能，比较不同的 m o e a s ，更好地理解m o e a s 的工作机制等等。 尽管多目标优化演化算法非常实用和有效，研究者将m o e a s 的思想扩展到 动态多目标优化问题的兴趣却不浓厚。演化多目标优化文献中包含了覆盖不同难 度和不同类型的大量的静态( s t a t i c ) 测试问题，这些问题需要一个静态的优化 过程，目标是找到一组决策变量优化静止的目标函数，但是有些现实世界的应用 需要一个依赖时间的( 在线的) 函数优化，目标函数和约束或与之相关的问题参 数随着时间而发生变化。在处理这类问题时，演化多目标优化算法并不多，也缺 少能充分证实动态多目标优化演化算法( d y n a m i ce 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 n a l g o r i t h m s 。d m o e a s ) 性能的测试问题。 1 2 1 求解多目标优化问题的方法 第一个可以称之为多目标优化演化算法的是s c h a f f e r 的向量评价遗传算法 ( v e c 後) ，它的主要目的是为了解决机器学习中的问题。我们可以租略的将求 解多目标优化问题的方法分成三种【3 l ： 1 整合方法( a g g r e g a t i n ga p p r o a c h e s ) ， 2 基于种群非p a r e t o 方法( p o p u l a t i o n - b a s e dn o n - p a r e t oa p p r o a c h e s ) ， 3 基于p a r e t o 方法( p a r e t o - b a s e da p p r o a c h e s ) 。 1 2 1 1 整合方法 也许最直接的处理多目标的技术就是将所有的目标结合成一个单一的目标， 事实上，整合方法是最早的用于解决多目标优化的数学规划方法( m a t h e m a t i c a l p r o g r a m m i n gm e t h o d s ) ，这种方法的一个实例是线性加权和( 1 i n e a rs u mo f w e i g h t s ) 的形式【3 l ： i m i n 罗 g ) ( 1 - - 1 ) 2 武汉理工大学硕士学位论文 其中毋；芑0 是加权系数( w e i g h t i n gc o e f f i c i e n t s ) ，表示问题中的k 个目标函 数的相对重要性，通常假定 以( 1 - - 2 ) 整合函数可以是线性的( 如上所述) 也可以是非线性的。整合函数方法受到演化 多目标优化研究者的轻视，主要因为线性整合函数众所周知的缺陷，即不论如何 加权，都不能找到p a r e t o 最优前沿为非凸( n o n - c o n v e x ) 的部分。传统的数学规 划技术碰到类似的问题时很难或根本无法找到p a r e t o 最优区域( 举例来说，如果 存在多个p a r e t o 前沿，或不连续的，凹的p a r e t o 前沿) 。 1 2 1 2 基于种群非p a r e t o 方法 在基于种群非p a r e t o 的方法中，算法中的种群被用于拓展搜索的多样性，但 是这种方法重要的一点是：p a r e t o 支配的概念不直接包含进选择过程中。典型的 例子是s c h a f f e r 的向量评价遗传算法( v e g a ) 。其他的一些研究者对v e g a 进 行了改进或者提出了一些新的基于种群非p a r e t o 方法的算法【4 1 5 l 。这些方法并没 有在多目标优化领域中得到广泛的认可。在2 5 1 节中我们会详细的介绍v e g a 。 1 2 1 3 基于p a r e t o 方法 基于p a r e t o 方法经历了两代，第一代的特征是将p a r e t o 排序和适应值共享 及小生境策略结合使用，最具有代表性的算法有非支配分类遗传算法( n s g a ) f 6 】，小生境p a r e t o 遗传算法( n p g a ) 川，多目标遗传算法( m o g a ) 1 8 l 。 自s e h a f f e r 后，1 9 9 3 - - 9 5 年里，研究者设计了许多不同的应用在多目标优 化领域的遗传算法( f o n s e e a & f l e m i n g , 1 9 9 3 ；h o r ne ta 1 ，1 9 9 4 ；s f i n i v a s d e b , 1 9 9 5 ) 。后来，其他的研究者成功地将这些方法应用在多目标优化问题上面 ( c u n h ae ta 1 ，1 9 9 7 ；e h e a r te ta 1 ，1 9 9 3 ；m i t r ae ta 1 ，1 9 9 8 ；p a r k & m i l l e r , 1 9 9 8 ； w e i l ee ta 1 ，1 9 9 6 ) 。一些研究致力于改进遗传算法的性能( k u r s a w e ，1 9 9 0 ； l a u m a n n se ta 1 ，1 9 9 8 ；z i z l e r & t h i e l e ，1 9 9 8 ) 。f o n s e c a f l e m i n g ( 1 9 9 5 ) 和 h o m ( 1 9 9 7 ) 总结了各种不同的多目标遗传算法的实现过程。 第二代多目标优化演化算法的特征是引进了精英( e l i t i s m ) 的概念，在多目 标优化的情形下，精英通常指的是使用一个外部种群( 也叫做第二种群) 来保存 非支配个体。代表算法有z i t z l e r 和t h i e l e 的力度p a r e t 0 演化算法( s p e a ) 1 9 1 及 它的改进算法s p e a 2 1 1 0 1 ，k n o w l e s 和c o m e 的p a r e t o 档案演化策略( p a e s ) 1 1 1 】， d e b 的改进的非支配分类遗传算法( n s g a - i i ) 1 1 2 ，e r i c k s o n 的改进的小生境 p a r e t o 遗传算法( n p g a 2 ) 【1 3 】，c o r n e 的慕于封套的p a r e t o 选择算法( p e s a ) 【1 4 】及它的改进算法p e s a - i i 1 5 】。 3 武汉理工大学硕士学位论文 在z i t z l e r , d e b 和t h i e l e i t 6 1 的研究中，清楚的显示了使用精英( e l i t i s m ) 策略 能帮助多目标优化演化算法获得更好的收敛性。在现有的带精英策略的算法中， n s g a - i i 、s p e a 、p a e s 、r u d o l p h 的精英遗传算法 1 7 1 都是非常著名有效的带精 英策略的m o e a s 。 演化多目标优化的研究者都在努力研究新的算法，也在疑惑什么样的算法能 成为第三代多目标优化演化算法。重点似乎集中在算法的效率i l s , l f l 和空间数据结 构，目的是为了提高外部种群的效率和存储能力【2 0 m 1 。近几年，研究者又提出了 一些超启发式算法，如人工免疫系统【2 2 捌，蚁群优化陋, z 5 1 ，粒子群优化1 2 6 , 2 7 1 。 1 2 2 构造多目标优化测试问题的方法 提出新算法和改进现有算法的一个基本前提是：是否存在一个标准有效的方 法使得不同的m o e a s 可以直接相互比较。评价m o e a s 性能方法的一个组成部 分是需要一定的测试函数( t e s tf u n c t i o n s ) ，即基准( b e n c h m a r k ) 。 在演化多目标优化研究的早期，使用的测试函数大多是简单的无约束的单变 量的双目标优化问题，有些多目标优化演化算法研究者使用了不可扩展的测试问 题，还有些研究者使用的测试问题太复杂以至于不能可视化p a r e t o 最优前沿的确 切形状和位置。 s c h f f e r ( 1 9 8 4 ) 介绍了两个单变量的双目标优化问题( s c h l 和s c h 2 ) ，它们 被广泛地当成测试问题应用在各种算法中。k u r s a w ( 1 9 9 0 ) 的测试问题k u r 可以 扩展到任意数日的决策变量，但是不能扩展到任意数目的目标函数；有相同情况 的是f o n s e c a 和f l e m i n g ( 1 9 9 5 ) 的测试问题f o n 。v i e n n e t ( 1 9 9 6 ) 的测试问题v n t 有一个离散的p a r e t o 最优前沿，但是他仅仅设计了三个目标。p o l o n ic ta 1 ( 2 0 0 0 ) 的测试问题p o l 仅仅使用了两个决策变量，尽管这个问题的数学形式是非线性 的，但是得到的p a r e t o 最优前沿与决策变量的关系基本上是线性的。 k a l y a n m o yd e b 是演化计算和多目标优化领域的杰出贡献者。他提出的测试 函数的构造方法以及通过这些方法得到的测试函数逐渐成为了演化多目标优化 领域的研究者在评价算法性能时广泛认可和采纳的基准。概述如下： 1 9 9 9 年，d e b 分析了能引起m o e a s 收敛到p a r e t o 最优前沿和维持种群多样 性的难度的问题特性，展示了多峰函数和欺骗函数如何能引起多目标遗传算法解 决问题的难度。在此基础上，构造了可控制问题难度的多目标优化测试问题。特 别是，从单目标优化问题构造而来的多目标优化问题使得单目标优化中的难度直 接转化到多目标优化问题中。主要方法是通过改变三个函数的复杂性调解双目标 优化问题的难度。而后系统地构造了具有凸、非凸、不连续p a r e t o 最优前沿的多 目标优化问题1 2 8 1 。 4 武汉理工大学硕士学位论文 d e b 的构造方法简单易懂，并且构造出的问题能扩展到任意数目的决策变 量。在这些问题中，p a r e t o 最优前沿的确切形状和位置是知道的。尽管此类测试 问题被许多研究者广泛应用，也存在一些批评的意见，那就是在解决多目标优化 的两个基本任务中函数的特性相对独立。 2 0 0 1 年，d e b 系统地设计了决策变量和目标函数的数目均能扩展到任意数 目的多目标优化测试问题。这种构造方法的主要特点有：构造简单，可扩展到任 意数目的决策变量和目标函数，得到的p a r e t o 最优集和最优前沿的确切位置和形 状可知，对于收敛到p a r e t o 前沿和维持解的均匀分布的问题难度可以控制。目前， 从测试两个或三个目标函数的问题发展到高维问题成为演化多目标优化研究者 的新的研究焦点【捌。 约束处理是解决现实世界问题的关键部分，现今的多目标优化算法的研究者 应该把精力集中在带约束的多目标优化问题上面了。早期的文献中使用的约束处 理过程解决的都是一些简单的问题，特别是决策变量少，非线性约束也很少的问 题。当算法应用在这些问题上的时候，很难评价算法的真实特性。 在多目标优化演化算法中很少有研究专门设计用来处理约束问题的。在所有 的这些方法中，通常使用罚函数方法( p e n a l t y f u n c t i o n ) 。当使用这种方法时，所 有的约束和目标函数必须规范化。下面列举一些用于约束处理的例子： j i m e n e ze ta 1 提出了在二进制锦标赛选择中比较两个解，如果一个解可行 ( f e a s i b l e ) 而另一个解不可行，可行解被选中。如果两个解都可行，使用h o r ne t a 1 提出的小生境p a r e t o 遗传算法( n p g a ) 来确定哪个解将被选中。另一方面， 如果两个解都不可行，那么越接近约束边界的解被选中的可能性越大【3 0 l 。 r a y e ta i 提出了一个更为精心详细的约束处理技术，它分别使用目标函数和 约束对种群进行非支配分类，该算法需要大量的计算时间1 3 1 】。 d e b 定义了一个约束支配( c o n s t r a i n t d o m i n a t i o n ) 的原则1 1 2 l ，通过非支配分 类的过程从可行解中区分出不可行解。这个原则在多目标优化演化算法中使用时 不需附加任何的约束处理技术。因为这个过程的通用性，该原则能用于任何的不 带约束处理的多目标优化演化算法中。在此基础上，d e b 提出了一个带有六个参 数的可调节难度的测试问题产生器，用于获得不同难度不同类型的带约束的测试 问题1 3 2 1 。 最近，动态多目标优化已成为多目标优化领域的一个热点。在充分证实了演 化多目标优化算法应用在静态的多目标优化问题上找到多个p a r e t o 最优解的能 力之后，需要解决动态的多目标优化问题。f a r i n ae ta i 在2 0 0 4 年提出了这个问 题并构造了一组测试问题及一个基准算法。2 0 0 4 年，d e b 等人提出了构造连续 和离散动态多目标优化问题的方法，并设计了解决这类问题的一个基准算法1 3 3 1 。 武汉理工大学硕士学位论文 1 2 3 动态多目标优化演化算法 大部分演化计算的工作集中于研究静态的、目标函数不会发生变化的优化问 题。然而，现实世界的很多优化问题实际上是动态的，它需要的优化方法能够持 续适应变化的环境，并找到新的最优解。 标准的演化算法用于解决动态的优化问题时，往往收敛到一个最优值，而失 去了种群的多样性，以至于不能有效的扩展搜索空间，那么当环境发生变化的时 候就不能适应新环境。 过去几年的研究中，对动态问题提出的解决方法可以粗略地分为： 1 演化算法仍以标准的模式运行，一旦监测到环境发生了改变，再采取行 动增加种群的多样性，目的是便予找到变化了的最优僚。 当环境发生变化时，演化算法的应对措施通常有下列的几种： ( 1 ) 当监测到环境发生变化时，只是简单地将演化算法重新肩动，这种选 择是最简单地处理环境变化的方法。然而，假设问题的变化很小，那么很可能新 的最优值与旧的最优值的联系很紧密。比起重新启动演化算法，我们应该有更好 的选择，比如从旧种群向新的初始种群传递某些有益信息。 ( 2 ) 在环境发生变化后，为维持种群的多样性，使用了超变异 ( h y p e r m u t a t i o n ) l s 4 ，通过快速增大变异概率而提高整个种群的多样性。与它不 同的一个做法是变量局部搜索( v l s ) 【3 5 l ，它在监测到环境发生变化后逐步提高 变异概率。首先，应用一个很小的变异( 例如，仅变异实数的二进制编码的最后 一位) ，如果种群的适应值在预先定义的时间里没有提高，那么局部搜索的范围 通过越来越大的变异算子得以扩展。 ( 3 ) 如果环境发生变化后，影响了优化问题的遗传表示，那么简单的使用 旧的个体己经不行了，必须要使用适应环境的新个体。总的来说，重新使用变化 的( 旧) 个体在算法的收敛速度和找到新的最优解的质量上均有很大的提高【蚓。 2 演化算法在任何时候都避免收敛，希望得到一个有广泛分布的解的种群， 这样的种群更容易适应环境的变化。 在算法的运行过程中维持种群的多样性是动态演化算法成功与否的一个关 键。g r e f e n s t e t t e 3 7 1 提出在每代中随机移入( r a n d o mi m m i g r a n t s ) 个体的方法，即 种群中的一部分个体被随机产生的个体替代。与强变异相对的是，随机移入方法 仅影响部分种群。因此，这个维持多样性的过程并没有破坏正在进行的搜索过程。 a n d e r s e n 考察了遗传算法寻找移动的最优值时，在基因型空间和表现型空间 分别使用共享的不同效果。他认为算法的目的是扩展种群的多样性以找到多个峰 值，在一个变化缓慢的环境中，共享能显著提高遗传算法搜索最优值的能力。 在郾j 中提出将个体的年龄考虑到函数适应值的变化中，这种方法比没有考 6 武汉理工大学硕士学位论文 虑年龄的演化算法能够更好的维持种群的多样性，更好的适应环境。 3 演化算法使用一个存储器( m e m o r y ) 保存过去演化过程中的有用信息。 在演化算法中提供一些存储器用来记忆一( 部分的) 好的解，必要的时候可以 重新使用它们。当最优值又一次返回到以前的那个位置时，这种方法特别有效 显然，带记忆的策略特别适合于那些周期性变化的环境。 迄今为止，只有很少的文献提及不同的动态多目标优化演化算法的性能比 较，因此很难做出哪个算法更优的结论。 1 3 本文所作的工作 本文主要做了以下几方面的工作： 第1 章前言：概括地介绍了国内外对多目标优化问题的解决方法以及构造 标准测试函数的发展历程；阐述了现今的一个热点：动态多目标优化钡9 试问题和 算法的研究情况。 第2 章多目标优化演化算法：介绍了多目标优化演化算法的不同实现方法 中的一些基本思想，描述了一砦经典算法的主要思想；提出一个求解种群中的非 支配集的新算法，设计构造了多目标优化演化算法的基本框架。 第3 章多目标优化测试问题的构造：通过分析研究引起多目标演化算法收 敛到p a r e t o 最优前沿的难度的问题特性，介绍了构造双目标优化测试问题的方 法，并对该种问题的p a r e t o 最优集和p a r c t o 前沿的确切位置从理论上进行了证 明，给出通过这种方法构造的问题实例。系统地阐述了三种不同的方法用于构造 可扩展的多目标优化测试问题，给出这类问题的理论p a r e t o 集和p a r e t o 前沿的 位置及相关实例。 第4 章动态多目标优化测试问题的构造：分析了动态多目标优化测试问题 的类型和特点，提出将静态的多目标优化问题的直接转化为动态多目标优化测试 问题的构造方法，给出了它们的实例。 第5 章结论：对本文进行了归纳，概括了本文的主要工作和创新点，提出 了下一步研究工作和研究方向。 武汉理工大学硕士学位论文 第2 章多目标优化演化算法 2 1 多目标优化问题的描述及基本概念 近年来，使用启发式的优化是一个非常普遍的研究课题。优化指的是在给定 一个( 组) 限制( 或约束) 的情况下找到对于一个问题来说是最好的解。 当优化的问题是单个目标的时候，我们的目的是找到最好的解( 称之为“全 局最优”) ，或者至少是它的一个近似解。但是，在设计一个现实世界问题的优化 模型时，我们发现通常不只一个而是有几个需要同时优化的目标，这些目标往往 还是彼此冲突的。例如，当我们设计一座桥梁的时候，我们希望费用最少而安全 性最高。 这种有两个或更多个目标的问题称为“多目标优化问题”，解决这种问题需 要与那些适合解决单目标优化问题的不一样的工具。事实上，当处理多目标优化 问题时，“最优性”的概念甚至都发生了变化。 使用启发式方法处理优化问题是一个有效的方法，它获得了很多学科研究者 的认可。在众多的启发式算法中，演化算法( e v o l u t i o n a r y a l g o r i t h m s ，e a s ) 是 最普遍接受的一种算法。e a s 在单目标优化问题中的应用非常普遍，近年来，e a s 也已经成为了多目标优化领域的主流算法。 下面我们介绍与多目标优化领域相关的一些术语，当使用数学的形式定义这 些概念的时候，也提供了一些非正式的语言，目的是易于理解。 定义2 1 多目标优化问题( 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 ，m o p s ) 的形式 描述如下【3 l ： m i n i m i z e 【，l ) ，2 ) ，无 ) 】 ( 2 1 ) 满足m 个不等式约束： g j ( i ) s0 ，i 一1 ，2 ，m ( 2 2 ) p 个等式约束： h 。( i ) 一0 ，i 一1 ，2 ，p ( 2 3 ) 其中，k 是目标函数无：r “一r 的数目，称孑一【x 。，z ：，】7 为决策变量向 量( v e c t o r o f d e c i s i o n v a r i a b l e s ) ，我们希望从决策变量向量集合f 中找到满足佗 一2 ) 和( 2 3 ) ，并且在所有的目标函数上产生最优值的解簖，x ；，z ：) 的集合。 一个m o p 就是需要同时优化两个或者更多个目标的问题。在这些目标上可 能还会加上一些约束条件，值得强调的是通常情况下m o p s 的目标是互相冲突 8 武汉理工大学硕士学位论文 的。若非如此，我们只需要依次优化这些目标，那么最终获得的将是一个单一的 最优解。 绝大部分的m o p s 问题得到的优化结果并不是一个单一的解，而是一组解的 集合，这样的解在所有的目标上是平衡( t r a d c - o f f s ) 的或折中( c o m p r o m i s e s ) 的，为了产生这些平衡解，采用了最优性这个概念。 定义2 2 最优性( o p t i m a l i t y ) 3 】 最优性的概念是由f r a n c i sy s i d r oe d g e w o r t h 于1 8 8 1 年提出的，后来由 v i l f r c d op a r e t o 在1 8 9 6 年进行了推广。在多目标优化问题中，很少存在一个解能 同时使得问题中的所有目标都达到最优值。最优性( o p t i m a l i t y ) 的概念，在多 目标优化的情形下和单目标优化相比大不相同。我们通常使用的是最广泛接受的 术语：p a r e t oo p t i m a l i t y 3 9 1 。 定义2 3p a r e t o 最优( p a r e t oo p t i m a l ) 3 1 我们称决策变量i e f 是p a t e t o 最优，如果满足条件： 决策变量向量集合f 中不存在另外的一个解i ，有，i ) s f a x ) ， i - 】2 ，- - , k ，并且至少存在一个j 满足，g ) ， ) ，j 住2 ，七 。换句话说， i 是p a r e t o 最优的，那么在集合f 中不存在解i 在降低某些标准的同时不引起 其它至少一个标准的提升。 定义2 4 支配( d o m i n a t i o n ) 冽 如果同时满足下面的两个条件，解x 0 ) 称之为支配解z ( 2 ： 1 解x ( 1 ) 在所有的目标上都不比工( 2 ) 差( 算符 - 表示好) ，也 就是f ( x ( i ) ) 7 i = ， 2 ) ，其中j - , 2 , - - - , m 。 2 解x ( 1 ) 至少在一个目标上比x ( 砷好，也就是至少存在一个7 仉2 ，m ) ， 有，i o o ) 卜，7 0 ) 。 如果违背了上面任何一个条件，解x o ) 不能称之为支配解工( ”。 如果解x o ) 支配解工( ”，常记为工( 却被x o ) 支配( d o m i n a t e d ) ，或者工与工( 2 相 比是非支配( n o n - d o m i n a t e d ) 的。 定义2 5p a r e t o 最优集( p a r e t oo p t i m a ls e t ) 和p a r c t o 前沿( p a r c t of r o n t ) 1 3 p a r e t o 最优的概念使得这个集合中往往存在不止一个的鳃，而是一个解的集 合，这个集合称为p a r e t o 最优集，p a r e t o 最优集在目标空间中的映射称之为p a r e t o 最优前沿( 或简称p a r e t o 前沿) 。 2 2 问题的结构和特性 一般来说，多目标优化问题比较复杂，因此求解较困难。有关问题求解的两 9 武汉理工大学硕士学位论文 类复杂性需要明确区分：( 1 ) 问题中固有的复杂性，( 2 ) 与求解方法有关的复杂 性。传统的许多求解方法的最大缺点在于它们对权重值、目标给定的次序或效用 函数的形状非常敏感。从本质上讲，这种困难是由求解方法引起的，而不是问题 本身的困难。 通常多目标优化问题可以通过下列结构和特征来描述：( 1 ) 目标函数和决策 空间，( 2 ) 约束函数和解空间，( 3 ) 问题的规模。目标函数和约束函数可能是线 性或非线性、凸或凹或不凸不凹、可微或不可微、连续或半连续、单峰或多峰的。 因此，决策空间可能是凸或非凸、紧或非紧、连通或分离的。问题的规模由决策 变量、约束和目标的数量决定。传统方法主要被限制在带有线性函数和凸解空间 的简单情况上。这种多目标优化问题一般被转换为单目标或一系列单目标优化问 题，然后采用扩展的基于梯度或单纯形的方法来求解转换后的问题。 2 3 多目标优化演化算法的主要任务 用演化算法解决单目标优化问题是非常普遍的，近年来，在多目标优化领域 中也得到了广泛的认可和使用。从1 9 5 0 s 开始，有不少研究者开始寻求解决m o p s 的方法，当时广泛使用的是数学规划技术，然而，这类技术在处理某类m o p s 的时候会有一定的障碍，比如，当p a r e t o 前沿是凹( c o n c a v e ) 或者不连续 ( d i s c o n n e c t e d ) 时，不少方法易受p a r e t o 前沿形状的影响，而得不到这类问题 的最优前沿，还有一些方法要求目标函数和约束条件可微。此外，在使用这些方 法解决m o p s 问题时，为了产生p a r e t o 最优集中的不同元素需要运行多次( 使 用不同的初始点) 。相反的是，演化算法能同时处理一组解( 称之为种群) ，允许 算法在单次运行中获得最优集的不同元素，更重要的是，演化算法不易受p a r e t o 前沿的形状和连续性的影响。 在使用演化算法解决多目标优化问题时应该完成两个任列冽： 1 引导搜索朝p a r e t o 最优区域发展， 2 在当前的非支配前沿中维持种群的多样性( 在函数空间，参数空间，或 两者兼有) 。 因此，使用演化算法获得的p a x e t o 最优集的近似解有两个要求1 1 0 1 ：一是与 理论上最优前沿的距离应该最小化，二是产生的解的多样性应该最大化( 根据目 标函数值或者参数值) 。 通常的演化多目标优化算法的目的是找到整个p a r e t o 最优集和p a r e t o 前沿， 然而，大多数情况下，决策者并没有兴趣找到整个解集，决策过程往往带有一定 的偏好性。近两年来，一些研究者在算法中加入了用户的偏好信息，以得到更接 1 0 武汉理工大学硕士学位论文 近用户需求的解集。 为使找到的最优前沿具有鲁棒性，d e b 采用了两个不同的多目标优化过程， 目的是得到的解不易受到变量的微小变化的影响l 删。d e b 在n s g a - i i 的基础上 进行了改进，在算法中加入了偏好策略，目的是提供给决策者接近他的偏好点附 近的一组解集【4 1 1 。 2 4 演化多目标优化 在过去的2 0 年中，演化算法( 特别是遗传算法) 作为多目标优化问题的新 求解方法受到了相当程度的关注，这就诞生了演化或遗传多目标优化。这个主题 已经由f o n s e c a 和f l e m i n g 4 2 1 、h o r n 4 3 1 、t a m a k i 、k i t a 和k o b a y a s h i 进行了综述。 本节将简要描述多目标优化演化算法不同实现方法中的一些基本思想。某些有代 表性的方法将在后续几节中进行详细介绍。 2 4 1 遗传搜索的特征 遗传算法内在的特征说明了为何遗传搜索适合用于多目标优化问题。遗传算 法的基本特征