（计算机应用技术专业论文）εdominance多目标演化算法在优化问题中的应用研究.pdf

武汉理工大学硕士学位论文 中文摘要 在现实生活中，人们遇到的大多数优化问题是多目标优化问题，而且这些目 标之间大多数是相互冲突的。在优化过程中所获得的解集就称为p a r e t o 优化解 集。大多数的多目标优化算法是用来寻找p a r e t o 近似优化解集。算法所获得的 解不但要分布均匀，而且还要尽量地接近p a r e t o 优化阵面。但是目前存在的多 数优化算法在这方面却存在着一定缺陷。比如有些算法可能花费大量的时间获 得分布均匀的优化解；有些算法虽然时间短些，但获得的优解分布不是很均匀。 在这篇论文中提出一种快速稳定的多目标演化算法( i - m o e a ) ，同时又改进了 目前一种比较好的算法n s g a i i 算法。i m o e a 算法是基于d e b 在2 0 0 2 年提出 的e d o m i n a n c e 的概念，算法还应用了精英策略、归档更新、超网格分割法和 g 向量支配策略。精英策略是目前公认的一种保持个体多样性的有效策略。归档 更新策略分为在线归档和离线归档，算法中应用了在线归档。本文中提出的超 网格分割法和g 向量支配策略是用来解决个体多样性的问题。网格分割方法是 将目标空间分割成许多超网格，同时保证每一个超网格只能被一个非支配的个 体所占用，这样做的目的是便于个体之间的e 支配关系的比较，可以解决维持 解的多样性的问题。g 向量支配策略用来选择非支配的精英个体，可以保证选出 的精英最具有代表性，从而很好地解决个体的多样性问题。用p a r e t o 支配和e 支配来选择非支配个体，选择出具有代表性的精英个体，这样就可以减少候选 解的p a r e t o 优化区域。归档的大小没有预先设值，而是根据协调参数 和e 的 乘积而定，这样能缩短归档的更新时间，且能获得理想的p a r e t o 优化解，从而 减少了整个算法的计算时间。从模拟实验的结果来看，该算法具有很好的通用 性，且算法的效率也很高。 在改进的n s g a i i 算法( i n a s g i i 算法) 中，首先分析了n s g a i i 算法所存 在的缺陷，即在保持解的多样性方面存在着缺陷。于是用s p e a 2 中的c l u s t e r i n g 方法来代替n s g a i i 算法中c r o w d i n g 方法。从测试结果看，i n s g a i i 算法获 得解分布比n s g a i i 算法所获得解均匀些；而i m o e a 算法无论是在无约束的两 个目标、有约束限制的两个目标还是三个目标上的测试，获得优化解都比较理 想。从模拟结果上看，这两种算法都取得了良好的效果。 关键字：多目标优化，p a m t o 优化解，演化算法，e 支配，超网格 武汉理t 大学硕十学位论文 a b s t r a c t m a n yr e a l w o r l do p t i m i z a t i o np r o b l e m s c o n s i s to fs e v e r a l c o n f l i c t i n g o b j e c t i v e s ，t h es o l u t i o n so fw h i c h a r ec a l l e dt h ep a r e t o o p t i m a ls e t d u r i n gt h el a s t d e c a d e ，m o s te v o l u t i o n a r ya l g o r i t h m sh a v eb e e nu t i l i z e dt of i n da na p p r o x i m a t i o n o ft h ep a r e t o o p t i m a ls e t h o w e v e r , t h ea p p r o x i m a t i o ns e tm u s tp o s s e s ss o l u t i o n s w i t hh i g h e rc o n v e r g e n c et o w a r d st h ep a r e t o o p t i m a ls e ta n db e t t e rd i v e r s i t y m a n y s t u d i e sh a v eu s e dd i f f e r e n tw a y so fe v o l u t i o n a r ya l g o r i t h m st oa p p r o a c ht h e p a r e t o - o p t i m a lf r o n tw i t haw i d ed i v e r s i t ya m o n gt h es o l u t i o n s h o w e v e r , m o s t m u l t i o b j e c t i v ee 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 ) a r ee i t h e rg o o df o ra c h i e v i n ga w e l l - d i s t r i b u t e ds o l u t i o n sa tt h ee x p e n s eo fal a r g ec o m p u t a t i o n a l l ye f f o r to r c o m p u t a t i o n a l l yf a s t a tt h ee x p e n s eo fa c h i v i n gan o t s o g o o dd i s t r i b u t i o no f s o l u t i o n s t h es u b j e c to ft h i st h e s i si st op r o p o s eaf a s ta n ds t e a d ym o e a ( i m o e a ) ，a n d i m p r o v et h ee x i s t i n gm o e a s ( n a g a - l l 、t h ei - m o e aa l g o r i t h mi sb a s e do n e d o m i n a n c ec o n c e p tw h i c hp r o p o s e db yd e b t h ea l g o r i t h mu s e se l i t i s t s t r a t e g y a n da r c h i v eu p d a t es t r a t e g y , a n dh y p e r 一班d sd i v i s i o nm e a s u r ea n dgv e c t o r d o m i n a n c es t r a t e g yt oo b t a i np a r e t oa p p r o x i m a t i v eo p t i m a ls o l u t i o n s t h ee l i t i s t s t r a t e g yi sr e g a r d e da sa ne f f e c t i v em e t h o dt om a i n t a i nt h ed i v e r s i t yo ft h eo p t i m a l s o l u t i o n s t h ea r c h i v eu p d a t es t r a t e g yi n c l u d e so n l i n ea r c h i v ea n do f f - l i n ea r c h i v e t h eo n - l i n ea r c h i v ei su s e di nt h ea l g o r i t h m 。t h eh y p e rg r i dd i v i s i o na n dgv e c t o r d o m i n a n c ew h i c ha r ep r o p o s e di nt h et h e s i sa r ea d o p t e dt os o l v et h ed i v e r s i t yo f s o l u t i o n s t h es e a r c hs p a c ei sd i v i d e di n t oan u m b e ro fg r i d sa n dt h ed i v e r s i t yi s m a i n t a i n e db ye n s u r i n gt h a tag r i dc a l lb eo c c u p i e db yo n l yo n es o l u t i o n t h e m o t i v ee n s u r e st h a tn ot w oo b t a i n e ds o l u t i o n sa r ew i t h i nt h es a m eev a l u ef r o m e a c ho t h e ri nt h eo b j e c t i v e t h egv e c t o rd o m i n a n c ei si n t r o d u c e di nt h es e l e c t i o n o fn o n d o m i n a n c es o l u t i o n s i tc a n p i c ko u t t h em o s t r e p r e s e n t a t i v e e l i t i s t i n d i v i d u a l s a n y m o e a sn e e dn o t p r e s e r v e a l ln o n - d o m i n a t e ds o l u t i o n s c o m p e l e t e l y s o t h ea l g o r i t h mu s e sp a r e t o - d o m i n n a c ea n d d o m i n a n c et o c o n t r o lt h es e l e c t i o no fn o n d o m i n a t e ds o l u t i o n s t h es i z eo ft h ea r c h i v ei sn o t 1 i t 武汉理7 1 大学硕士学位论文 f i x e do nan u m b e r a n d d e t e r m i n et h es i z eo fa r c h i v e s ot l l ea l g o r i t h mc a n n o to n l yr e d u c ec o m p u t a t i o n a lt i m e ，b u ta l s oo b t a i np e r f e c tp a r e t on o n - d o m i n a t e d s o l u t i o n s f i n d i n gag o o dd i s t r i b u t i o no fs o l u t i o n sn e a rt h ep a r e t o - o p t i m a lf r o n ti n as m a l lc o m p u t a t i o n a lt i m ej sa ni m p o r t a n tg o a lf o rm u t i o b j e c t i v ee ar e s e a r c h e r s a n dp r a c t i t i o n e r s t h ei - m o e aa l g o r i t h mc a ns l o v et h ep r o b l e mc o m m e n d a b l y t h e s i m u l a t i v ee x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a tt h ea l g o r i t h mh a sb e t t e ru n i v e r s a l p e r f o r m a n c ea n dc o m p u t a t i o n a le f f i c i e n c y i ni - n s g a - i ia l g o r i t h m w ea n a l y z et h el i t i m i t a t i o no ft h en s g a i ia l g o r i t h m f i r s t l y t h e nt h ec l u s t e r i n gm e t h o dw h i c hu s e di ns p e a 2r e p l a c e st h ec r o w d i n g m e t h o ds t r a i 曲t i y t h ep e r f o r m a n c eo ft h et w oa l g o r i t h m sr e p r e s e n t sg o o dr e s u l t s o nc o n v e r g e n c ea n dd i v i s i t yb yt w op e r f o r m a n c em e t r i c s t h e o p t i m i z a t i o n s o l u t i o n so f1 - n s g a - i ia l g o r i t h md i s t r i b u t em o r es l i c kt h a nt h a to fn s g a - 1 1 a l g o r i t h m ，a n dt h ei - m o e aa l g o r i t h mh a so p t i m i z a t i o ns o l u t i o n sd i s t r i b u t i n g p e r f e c t l y , w h i c ho p t i m i z e st w oo b j e c t i v e sw i t h o u tc o n s t r a i n t so rw i t hc o n s t r a i n t s a n dt h r e eo b j e c t i v e s t h ee x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h et w oa l g o r i t h m sh a v e b e t e re f f e c t k e yw o r d 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 ，p a r e t o o p t i m a ls o l u t i o n s ，e v o l u t i o n a r y a l g o r i t h m s ，一d o m i n a t e ，h y p e rg r i d s i v 此页若属实请申请人及导师签名。 独创性声明 y 8 6 0 3 3 3 本人声明，所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得武汉理工大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意。 研究生签名：蕉包出日期鲤：墨：签 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅； 学校可以公布论文的全部内容，可以采用影印、缩印或其他复制 手段保存论文。 ( 保密的论文在解密后应遵守此规定) 研究生签名：鸯阻导师签名：勤邀日期 注：请将此声明装订在论文的目录前。 谢a 夏l 譬 武汉理t 大学硕十学位论文 1 1 问题的提出 第1 章绪论 最优化处理问题是在一堆可能的选择中搜索出对于某些目标来说是最优解 的问题。如果仅考虑一个目标，就成为单目标优化问题，这种问题在过去5 0 年 中已经得到了深入的研究。如果存在的目标超过一个并且需要同时处理的话， 就称为多目标优化问题“1 。一般来说，科学与工程实践中的许多优化问题大都 是多目标优化与决策问题。比如许多实际复杂系统的设计、建模和规划问题， 这些系统所在的领域包括工业制造、城市运输、资本预算、森林管理、水库管 理、新城市的布局和美化、能量分配、网络设计与施工等等。多目标优化问题 中各个目标之间通过决策变量相互制约o “，对其中一个目标优化往往以其它目 标的劣化作为代价，而各个目标的单位又往往不一致，因此很难客观地评价多 目标问题的优劣性。如何在最短时间内获得稳定的结果是人们最关心的问题。 处理这些优化问题是一件很困难的事情，这是由于人们所涉及到的目标大多都 是互相冲突且有较高的复杂度。人们总是希望在处理这些问题时，得到最理想 的答案。为了在这些多目标之间得到最优的结果，需要在这些目标之间进行折 中处理。在求解折中解的过程中就会涉及到优化。随着目标数量的增加和应用 的目的不同，问题优化处理的困难度也随之上升。因此解决好多目标优化问题 具有非常重要的现实意义。 1 2 国内外研究状况 在1 7 7 2 年f r a n k l i n 提出的多目标之间的冲突如何协调是多目标优化问题的 雏形，而国际上一般认为多目标最优化问题最早是由法国经济学家v p a r e t o 在 1 8 9 6 年提出的”3 。从此以后关于这方面的研究工作从未间断过“1 ：1 9 4 4 年 v o n n e u m a n n 和j m o r g c n s t e r n 从对策论的角度，提出多个决策者且彼此又相互 矛盾的多目标决策问题；1 9 5 1 年，t c k o o p m a n n 第一次提出了p a r c t o 最优解的 概念；同年h w k u h n 和a w t t u c k e r 从数学规划的角度给出了向量极值问题 的p a r e t o 最优解概念；1 9 5 3 年，a x r o n 等人对凸集提出了有效点的概念；1 9 6 3 年，l a z a d e h 又从控制论的角度提出多目标控制问题；l e o n i dh u r w i c z 于6 0 武汉理工大学硕士学位论文 年代推广了k u h n 和t u c k e r 的拓扑向量空间的结论从纯数学的角度巩固了多目 标最优化：1 9 6 8 年，z j o h n s e n 系统地提出了多目标优化问题的研究报告，这是 多目标最优化这门学科发展的一个转折点。到目前为止，已有超过3 0 个数值计 算技术用于解决该类问题。基于传统数学规划原理的多目标优化方法在实际工 程优化问题中往往会表现出一定的脆弱性。理论上说，p a r e t o 解的概念应该有助 于改变这种情况。所谓的p a r e t o 最优解，就是在任何一个目标上都不能继续得 到优化同时还不能引起在其他目标上的劣化，因此也被称为非劣最优解。也就 是说，多目标优化决策问题不存在唯一的全局最优解，而是多个最优解的集合。 该集合中的元素就所有目标而言是不可比较的。p a r e t o 最优概念是建立在集合论 的基础上多目标解的一种向量评估方式。但是，由于当时问题的解决方法仍为 传统的数学方法，而数学规划与模拟退火算法是以单点搜索为特征的串行算法， 所以很难利用p a r e t o 最优概念对多目标的解评估。 演化算法的产生为上述问题的解决提供了一个新思路。演化算法搜索解的一 个最大特点是一个群体搜索算法。它可以解决了上述传统的多目标优化算法的 并行化困难的问题，有效的利用f a r e t o 最优解，也就变更加合理。演化算法对 p a r e t o 解集的形状、连续性并不敏感，而它们却是实际工程中经常遇到的，且用 传统数学方法是很难解决的问题。1 9 6 7 年r o s e n b e r g 在其博士论文中曾提出可 用遗传的搜索算法来解决多目标优化问题；1 9 8 5 年s c h a f f e r 的v e g a 算法是其 第一个实现9 3 。但是直到9 0 年代，演化多目标算法才逐渐成为一个众多学者研 究的热点，并相继提出了不同的多目标演化算法。特别是在1 9 9 4 1 9 9 9 年，多 目标演化算法的文献发表数量几乎是1 9 8 5 年一1 9 9 4 年的3 倍还多1 9 1 0 例如，1 9 9 3 年，f o r t s c c a 和f l e m i n g 提出了m o g a 算法 1 0 rs r i n i v a s 和d e b 提出了n s g a 算法1 ，h o r n 和n a f p l i o t i s 也提出了n p g a 算法“”。m o g a 算法对种群每一个 个体的排序是基于p a r e t o 最优化概念的，并采用一种基于排序数的适应值赋值 方法、小生境技术和受限杂交技术来提高种群多样性，防止种群过早的收敛。 m o g a 算法的主要优点是算法执行相对容易且效率高，缺点是算法易受小生境 大小影响，但值得一提的是f o n s e c a 和f l e m i n g 已经从理论上解决了小生境大小 的计算问题。n s g a 算法是基于对多目标解群体进行逐层分类的方法，每代选 种配对之前先按解个体的非劣性进行排序，并引进基于决策向量空间的共享函 数法，优点是优化目标个数任选，非劣最优解分布均匀，允许存在多个不同等 效解。缺点是计算效率低，未采用精英保留策略，需要特别指定共享半径o 。 武汉理工大学硕卜学位论文 研究表明“”，精英策略可以明显改善遗传算法的收敛性，同时可以避免丢失进 化过程中取得的最优解。最近，d e b 与p r a t a p 等“”通过引进一种快速非支配排 序和新的多样性保持方法，提出了第1 i 代n s g a ，简称n s g a 一1 1 它可服了n s g a 的缺点。因为该算法的非劣最优解选择的是基于种群的部分而非全体，因此其 优点是能很快找到一些好的非劣最优解域，并能维持一个较长的种群更新期。 缺点是除需要设置共享参数外，还需要选择一个适当的锦标赛规模，限制了该 算法的实际应用效果。z i t z l e r 和n i e l e 提出了一种采用精英保留策略的多目标 优化算法s p e a “”，每代维持一个用来保存从初始种群开始业已发现的非劣解 的外部种群，外部种群参与所有遗传操作。k n o w l e s 与c o m e 提出一种类似 1 + 1 e s 的演化策略的多目标演化算法，也就是p a e s 1 5 1 只采用一个亲本与 一个子代个体，算法维持一个用来保存就发现的非劣解的归档。此外，还有一 些基于决策者预期目标的目标向量方法，如目标规划“i t 目标实现“”以及最 小最大方法“”等，其优点是计算效率高，缺点是各优化指标的预期目标难以确 定，而且对非凸搜索空间不适用“”。 我们实验室研究的主要是在熊盛武教授和刘冠蓉教授的带领下，许多师兄在 这方面的研究也取得了优秀的结果。李锋。”在他的硕士论文中设计了一个有效 的并行增强p a r e t o 多目标演化算法，同时采用了全局并行模型和粗粒度并行岛 模型。在岛模型中，首先将整个群体划分成若干个子群体，在每个子群体中执行遗 传算法的各步骤，并每隔一定的代数交换子群中的精英个体：在每个子群体中， 个体的评价和遗传操作使用多线程程序设计，各操作是并发进行的，这是全局并 行模型。在演化过程的最后阶段，就能够找到最优个体。在做了这两种方式的并 行化以后不仅可以获得更好的计算性能，在p a r e t o 最优解集的优化效果上有更显 著的改进。刘麟 6 1 在他的硕士论文中提出了两种改进粒子群算法，在第一种改进 的粒子群算法中添加了动态栅格技术，第二种改进的粒子群p s o 的消息传递机 制，同时使用s 距离归档技术和环境选择策略。他们都取得了良好的成果。 1 3 本文研究的内容 多目标优化中一个重要的问题就是如何能在短时间内获得分布均匀的 p a r e t o 优化阵面。在过去的几十年中有些算法不是花费大量的计算时间来获得具 有较好分布的解集，就是在短时间内而不能获得具有较好分布的解集。例如 武汉理l ：人学硕士学位论文 s p e a 2 算法获得解的分布比n s g a - i i 算法获得解的分布均匀，但是前者花费的 计算时间比后者多得多。本文就是在这种情况下，提出以一种稳定快速的 i - m o e a 算法，在此算法中使用了一d o m i n a n c e 协、p a r e t o d o m i n a n c e 、归档更 新策略、超网格分割方法和g 向量支配策略。在非支配个体的选择过程中使用 了两种支配关系。超网格分割法将目标空间分割成许多网格，用欧氏距离来控 制网格中个体的数目，每一个个体仅能占用一个网格，这样便于应用e 支配来 选择非支配的个体，同时可以解决多样性问题。归档的大小没有预先设定值， 面是根据调整参数e 和 的乘积变化。算法中还用了精英策略和g 向量支配策 略。由于使用了e 支配，可以减缩归档更新的时间，因此这个算法更具有实际 应用的价值。在本文中同时还将n s g a - i i 算法在保持解的多样性方面的缺陷进 行了改进。 1 4 本文的组织结构 第2 章介绍了与p a r e t o 支配相关的一些概念和一些常用的术语，同时还将改 进算法中用的与e p a r e t o 支配相关的知识进行了介绍，最后介绍多目标演化算 法中个体的适应度的分配机制和保持种群的多样性过程中采用的策略，还指出 目前存在算法所存在的缺陷。本文的重点在第3 章和第4 章，在第3 章中详细 介绍了两种的多目标算法。第一种改进的算法是基于n s g a - i i 算法，主要改进 n s g a i i 算法保持解的多样性方面性的缺陷；第二种算法主要使用了 n o n d o m i n a n c e 的有关技术；同时调整参数e 和 可以来改变归档中个体的多 少，这样可以使决策者选择所需的优化解，第二个算法是本文的研究重点。第4 章是模拟试验，通过优化函数来验证算法的性能。最后进行总结，并提出以后 研究的设想。 武汉理工人学硕士学位沦文 第2 章多目标优化及算法 多目标最优化是这样的一种问题：在一定约束限制下，希望使得多个目标同 时都能达到最优。在现实生活中，很多问题都要求多个目标最好，或者是妥协 最好。比如买车，价格要便宜，又要最省油，还要性能最好。但是一般来说， 多个目标同时达到最优的情况是不存在的。多目标优化首先要解决的一个问题 就是解的存在性问题。这种问题涉及到很深的数学理论。其次还要解决怎样来 求解的问题。如果问题没有最优解，那么应用相应的数学方法就可以判别出来， 这个问题不是本文的研究内容。如果问题有解，又怎么来求得这些解。特别地， 当问题有无限多个解，又该如何选择它们。这正是多目标优化算法所要解决的 主要问题。而在这一章中将介绍与多目优化相关的一些概念和术语。 2 1 多目标优化的概念 当人们考虑到一个优化问题时，最终目的就是获得最好解，也就是最优解。 优化问题通常包括最大化问题和最小化问题，最大化可以转化为最小化进行求 解。这里仅考虑最小化的形式。在优化过程中经常会遇到全局优化和局部优化 的概念，下面分别给出它们的定义： d e f 2 - 1 ( 全局优化) 假设s 为一个搜索空间，x f s 为可行域，f 为适应 值函数。优化问题就是寻找i x ，使得对于任何i x ，满足f ( i ) z f ( i ) 。 这里，x 为全局最优解。 d e f 2 - 2 ( 局部优化) 首先定义两个解的距离度量：d i s t ：x x x r 。则对于 x s 。x 的邻域可定义为： n ( x ) 一 y e x l d i s t ( x ，y ) a 如果有f ( i ) z f ( i ) ，且对于所有的一x 2 n ( 王) ，则一个解；x 被称为局 部最优解。 当同时有多个目标需要同时优化时，人们就会用到多目标优化方法。如图 2 一l 所示： 武汉理 大学硕十学位论文 图2 1 ( a ) 为2 一目标优化问题( b ) 为目标空间 现在考虑方程n ( x ) 和f 2 ( x ) ，可以从图2 - 1 中看出这两个方程的最小值分别 为f 1 ( o ) 和f 2 ( 1 ) ，也就是x = 0 和x = l 时，f l ( x ) 和f 2 ( x ) 取得最小值。现在，如果想 同时使n ( x ) 和f 2 ( x ) 取得最小值，那么就没有单个最小值。当x = o 不是使f 2 ( x ) 取得最小值，则x = l 不是使f l ( x ) 取得最小值，在这种情况下，要是n f x ) 和f 2 ( x ) 同时获取最小值时，则x 的取值范围应为【0 , 1 】，也称为优化解集。实际上，在 多目标优化中所获得的优化解是成倍增加的，这是因为为了在互相冲突的目标 中进行折中所造成的。因此，在这些解当中无法判断谁比谁好。 d e f 2 - 3 ( 多目标优化问题) ：多目标优化问题是由许多需要同时最大化或最 小化的方程组成： m i n i m i z ey f ( x ) t f 1 ( x ) ，f 2 ( x ) ，f 。( x ) ) s u b j e c tt o c ( x ) 一( e l ( x ) ，e 2 ( x ) ，e k ( x ) ) s0 包含m ( = 2 ) 个需要同时最小化且相互冲突的目标函数f i ：r “一职。决策向量 ( 也称为参数) x 一( x ，x ，x ) 7e scr 1 。s 表示决策变量可行域。可行域是由约 束函数e ( x ) 来决定。通常用z c r “来表示目标可行域。z 中的元素称为目标向 量，它们构成目标函数值f ( x ) 一( f l ( x ) ，f 2 ( x ) ，f m ( x ) ) d e f 2 - 4 ( 可行域) ：用s 来表示决策空间中的可行域，用z 来表示目标空 间的可行域，x 为自变量空间，则这两者的表达式为： s t i x x ie ( x ) s o ： z = z r 4 iz l = f l ( x ) ，z 2 - - f 2 ( x ) ，z q = f q ( x ) ，x s ) 武汉理工大学硕士学位论文 2 1 1 多目标优化中的基本概念和术语 1 ) 基本概念 d e - f 2 - 1 1 ( 可行解) 可行解x = 定义为自变量的集合，满足约束： x 7 = x x l e ( x ) o 1 在所有目标中决策向量x 1 不比差x 2 ，f i ( x ，) f i ( x ：) v i = l 2 m ， 2 至少在一个目标中决策向量x ，的确比x ，好些，或者至少在一个目标中 f a x l ) 岛：那么就说f j 支配着g 。，记为 ft g 。 d e f 2 - 3 2 ：( e a p p r o x i m a t ep a r e t os e t ) 假定f c _ r 一是个向量的集合，且 o ；如果对于任何一个向量g f 至少要被一个向量f e 所支配，那么就 说集合e 是f 的一个- a p p r o x i m a t ep a r e t os e t 。即满足如下条件： v g e f ：| f es u c h t h a t f g 记为：e ( f ) 。 d e f 2 - 3 3 ：( 一p a r e t os e t ) 假定f r + 一是一个向量的集合， 0 e f ； 如果f 满足如下两个条件： 1 e 是f 的个一a p p r o x i m a t e p a r e t os e t ，即e e ( f ) ； 2 e 仅包含f 的p a r e t o 点，即f f + ： 那么f 就是f 的一个p a r e t os e t 。 一个e - p a r e t os e t e 不仅支配着f 中所有的向量，而且还是唯一构成f 的 p a r e t o 优化向量的集合。以上的定义可以用图2 4 进行说明： 图2 4e 近似p a r e t o 集合和ep a r e t o 集合 鹜 茵 武汉理一l i 大学硕士学位论文 2 2 多目标演化算法 演化算法有g a ( g e n e t i ca l g o r i t h m ) 遗传算法、e p ( e v o l u t i o n a r yp r o g r a m m i n g ) 演化规划、e s ( e v o l u t i o n a r ys t r a t e g y ) 演化策略和g p ( g e n e t i cp r o g r a m m i n g ) 遗传程 序设计组成。这里仅用到遗传算法g a ，g a 是基于种群迭代搜索的方法，且能 在单独运行过程中搜索出系列潜在的解，因而，适合解决多目标优化问题。 当把g a 应用到多目标优化问题中的时候主要解决下面的两个问题： 1 为了指引搜索p a r e t o 最优解集的方向进行，如何正确的进行适应值分配 和选择。 2 为了防止早熟( 过早收敛) 并且要获得较好的分布性和扩展性的非劣最优 解集，如何维持群体的多样性。 由于g a 内含的并行性，它拥有在次单独的模拟运行中寻找多个p a r e t o 最优 解的潜在能力。然而对于许多复杂的应用，想要得到所有的非劣最优解是不可 能的。因此，一个多目标优化问题可以重新描述为： 1 所得的非支配阵面至l j p a r e t o 最优阵面的距离应该最小； 2 解的分布应该理想( 大多数情况下是均匀分布的) ； 3 所获得的非支配阵面的扩展区域应该最大。 2 2 1 适应值函数的选择和分配机制 用演化算法求解多目标优化问题中出现的一个特殊情况就是如何根据多个 目标来确定个体的适应值。每个个体的适应值是通过适应函数来计算。适应函 数是评价候选解的一种方法。这一步对于选择过程来说是十分重要的。而约束 条件也是在这一步中通过惩罚函数来惩罚那些不适合的候选解。通过惩罚函数 来调整不适合种群中个体个数，但是允许一部分不适合解留在种群中以便于影 响最终的解。适应值是评估个体好坏的一种度量，是进行自然选择的唯一依据。 适应值与最优解的距离直接有关，e a s 只能通过适应值的评估与问题相联系。 适应值分配机制在过去的2 0 年中得到广泛的研究，已经提出并测试了若干 种方法。这主要介绍基于p a r e t o 适应值分配机制“3 ：p a r e t o 排序( p a r e t or a n k i n 9 1 和p a r e t o 竞争俾a r e t ot o u r a m e n t ) 。 1 ) p a r e t o 排序法 武汉理工大学硕十学位论文 p a r e t o 基于排序的适应值分配方法首先由g o l d b e r g 提出“”，目的是使所有 p a r e t o 个体得到相同的复制概率。种群是根据非支配个体进行排序。排序的过程 如下：对当前种群的非支配个体分配次序1 ，并将其从竞争中移去；然后从当前 种群中选出非支配个体并对其分配次序2 。该过程持续到种群中所有个体都分配 到次序后结束。图3 - 1 ( a ) 用一个简单实例说明改过程。 ( a ) g o l d b e r g 提出的排序方法( b ) f o n s e e a 和f l e m i n g 提出的排序方法 图3 一lp a r e t o 排序法 排序选择很直截了当：( 1 ) 从最好到最差对种群进行排序：( 2 ) 根据排序对个 体分配选择概率。设m 表示排序后种群中第k 个个体的选择概率，则线性排序 方法采用式3 1 ： p k q - ( k - 1 ) r 3 一l 其中参数q 是最好个体的选择概率；设q o 是最差个体的选择概率，k 是种群中 最后一个次序的值。参数r 可以用式3 - 2 确定： r 。旦二生3 2 k 一1 中等个体的适应值则根据其次序的比例从q 降低到q o ，将q o 设为0 提供了最大 的选择压力。f o n s e c a 和f l e m i n g 提供了存在少许不同的p a r e t o 排序方法1 4 0 。当 前种群中所有非支配个体分配次序1 ，任何其他个体所分配的次序数等于支配该 个体的数量加1 。这种方法可以用图3 - 1 ( b ) 进行说明。如果次序相同，顺序随机 选取。适应值是根据种群中最好到最差个体进行线形或非线性插值的结果来分 配，具有相同次序个体的适应值一样。 3 - - - k ，。h一 2 一 一 -二一 2 一 一 一 一 1一101珥；：；一 一 一 1。+。_。l-一 ，一一。+。一。一一 一。一一。一一 一 ： ： 一 !r#；丁-|tlr0r-ll，kl 武汉理t 大学硕士学位论文 2 ) p a r e t o 竞争法 p a r e t o 竞争方法由h o r n n a f p l i o t i s 和g o l d b e r g 提出。这种方法从种群中 随机选出两个候选个体。同时还从种群中随机选出一组比较个体集。然后每个 候选个体与比较集中的每个个体进行比较。可能产生两种结果：第一种，如果 一个候选个体被比较集支配，而另一个不被支配，则非支配后选个体被选出来 进行复制；第二种；如果两个候选个体都被比较集支配或都支配比较集，则采 用共享方法来选择优胜者。 共享方法根据个体的小生境数来确定个体适应值的降低程度。h o r n 等人提 出了种新的共享方法，该方法不根据小生境数进行适应值任何形式的降低， 而是将具有较小生境数的个体选为优胜者。小生境数是通过求候选个体周围一 定距离内种群中个体的数量来确定。 图3 2 说明了这种共享方法在两个非支配个体问的工作过程。这是一个最 大化第1 个目标并最小化第2 个目标的实例。两个候选个体均在p a r e t o 解集中， 因此不被比较集支配。从p a r e t o 解的观点出发，两个候选个体之间没有偏好。 如果维持种群多样性，很显然最好选择具有较小小生境的个体。在该实例中就 是候选个体2 。 候选2 的小生境 图3 2h o r n 提出的共享方法 由于非支配性是将候选个体和从种群中随机选出的比较集进行比较来确 定，该算法成功与否就取决于比较集的规模这个参数。如果这个参数太小，该 过程仅选出种群中少许非支配个体。如果这个参数太大，则可能发生早熟收敛。 武汉理r 大学硕士学位论文 2 2 2 种群的多样性 为了在一次单独的优化运行中找到近似p a r e t o 最优解集，演化算子在多维空 间上进行搜索，应该找到多个不同的解。因此，对于一个多目标优化演化算法， 维持群体的多样性是至关重要的。由于选择压力，选择噪音和算子副作用使得 遗传算法经常丢失一些解，这样就造成遗传算法会收敛到一个单解。选择压力 是按照时间定义的，它指的是当选择发生的时候，整个群体被最优个体填满的 时间。选择噪音指的是选择机制的变化，而算子副作用与杂交和变异算子所引 起的破坏作用相关。为了克服这些缺点，已经提出了一些方法。下面将介绍在 多目标优化演化算法中经常使用的方法。 1 ) 适应值共享 适应值共享【4 3 】是维持种群多样性的一种技术，目的是沿着非支配解的边界 来维持种群的多样性。遗传算法用于求解多峰函数的一个问题就是由于选择过 程随机误差的作用，有限的种群最终会收敛到一个最优解上，这种现象称作遗 传漂移( g e n e t i cd r i f t