（计算机科学与技术专业论文）多目标进化算法中精英种群构建和子代个体产生的研究.pdf

i 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：! 塞逢导师签名：辇尘坠竖日期：兰! 丝笙至星f d 目签名：盔生 导师签名：踅垒坠竖日期：兰竺笙垒望l d 日 i 摘要 摘要 多目标进化算法是将进化计算的技术应用于多目标优化领域而形成的一类 智能计算方法。该算法一次运行可以得到一组折中解，具有较高的效率，而且能 够有效的避免陷入局部最优，因此逐渐成为解决多目标优化问题的一种重要方 法，在工程实践和科学研究中得到了广泛的应用。 精英种群的构建和子代个体的产生，是多目标进化算法的两个关键部分，围 绕这两个方面，科研人员进行了深入的研究，取得了大量的学术成果。本文在国 内外现有研究成果的基础上，针对当前多目标进化算法研究中的一些不足，完成 了如下3 方面的工作： ( 1 ) 针对常用测试问题中存在的缺陷提出了修改方案，避免了原有测试问 题在定义域边界取得最优解的问题，另外，使部分测试问题的分量间存在关联， 增加了问题的难度，从而可以更好地考察算法的搜索能力。 ( 2 ) 针对现有算法在精英种群构建方面的不足，本文提出了基于空间网格 的精英种群构建策略，该策略先选出当前种群中的非支配个体，再利用设定了边 长的空间网格对这些非支配个体进一步筛选，以获得较好的多样性。这种策略的 优势在于：( i ) 仅保留当前种群中的非支配个体，减少了选择过程中的时间开销： ( i i ) 借助给定边长的空间网格对非支配个体进行筛选，限制了个体间的拥挤程 度，有利于保持种群的多样性；( i i i ) 子代种群全部由当前种群中的非支配个体 产生，使得质量优秀的个体有更多的机会产生子代个体，这有利于提高种群的进 化效率。将新的精英种群构造策略与传统的子代个体产生方法相结合，得到了基 于空间网格的多目标进化算法。实验结果表明，新算法能够在较短的时间内，获 得优于一些经典算法的求解效果，从而验证了新策略的有效性。 ( 3 ) 针对子代个体产生方面的不足，本文提出了分量强调机制，把单个分 量看作是造成个体间差异的基本单位，在交叉、变异中，对单个分量逐个进行计 算，并结合( 1 + 1 ) 进化策略，保证了质量较好的单个分量能够以较大的概率得到 保留。论文根据分量强调机制设计了一对交叉变异算子，并将这对算子与经典的 精英种群构建策略结合，得到了一个新的多目标进化算法。实验结果表明，新算 法的搜索能力明显好于目前成功的算法，从而验证了分量强调机制对于算法搜索 性能提高的作用。 关键词多目标进化算法；构建精英种群；精英机制；分量强调机制；进化策略 北京工业大学工学硕士学位论文 d e a l i n gw i mt h em o p s ，a n di sw i d e l yu s e di j le n g i n e e r i n gd e s i g na n ds c i e n t i f i ci e s e a r c h t h et 、v om o s ! i m p o r ts e c t i o n so fm o e a a r et h ee l i t ep o p u l a t i o nc o n s t r u c t i o na n d t h eo 凰p r i n gg e n e r a t i o n ，a n dal o to fr e s e a r c hf i n d i n g sh a sb e e na c q u i r e df o rt l l e 铆o a s p e c t s - a 金e rs t u d y i n gb o t ha d v a n t a g e sa 1 1 df a u l t so ft h e s ef i n d i n g s ，t m sd i s s e 眦i o n m a i n l ya c h i e v e st h ef o l l o w i n gt a s k s ： ( 1 ) t bg e tr i do ft l es h o r t c o m i n g so ft h ev v i d e l yu s e dt e s tp r o b l e m s ，w ep r o p o s e s o m e 蚰p r o v e m e n ta c t i o n s ，w i l i c he n h 锄c et h ea b i l i t ) ro ft h et e s tp r o b l e m sf o rc h e c k i n gt h ea l g o r i t l l i i l s c o m p u t a t i o np e r f b r m a n c e s ( 2 ) t bs o l v et h ed r a w b a c bo ft h et r a d i t i o n a la l g o r i t h mi nt h ee l i t ep o p u l a t i o n c o n s t r u c t l o n ，w ep i o p o s ean e ws t r a t e g yb a s e do ns p a c eg r i d s t h es t r a t e g ys e l e c t sa l l t 1 1 en o n d o m i n a t e ds 0 1 u t i o n s ；a n e n ) l 脚d si tm a k e sa 血n h e rs e l e c t i o nw h i c he m p l o y s 也ef i x e d 鲥dt om a i n t a i nt h ed i v e r s i t yo ft l l ee v o l u t i o n a r y p 叩u l a t i o n ，n l ea d v a n t a g e s o f 。t h en e w s t r a t e g ya r e ：( i ) i to m yp r e s e r v e sm en o n d o m i n a t e ds o l u t i o i l s ，a n dt h et i m e c o s ti nt 1 1 es e l e c t i o nh a sb e e n r e d u c e d ；( i i ) t h ef i x e ds p a c eg f i di sa b l et or e s t r a i n tm e c r o w d i n gd i s t a n c eb e t w e e ns o l u t i o n sw h i c hi sg o o df o rt h ed i v e r s i t yo fe v o l u t i o n a r y p o p u l a t i o n ；( i i i ) t 1 1 eo 扫s p r i n ga r e 甜1g e n e r a t e db yt h en o n d o m i n a t e ds o l u t i o n s ，a n d t h ep o s s i b i l i t yo fo b t a i n i n gb e t t e rm d i v i d u a l si sm c r e a s e d t h ec o m b i n a t i o no ft l l e n e we l l t ep o p u l a t i o nc o n s t m c t i o na i l dat r a d i t i o n a lo 仃s 州n gg e n e r a t i o nm e t h o dm a k e s an e wm o e a ，a n dt h ee x p e r i m e n tr e s u l t ss h o wm a tn l en e w a l g o r i t h mo u t p e 墒咖s t h r e eo m e rs u c c e s s 如lm o e a s ，w i l i c hp r o v e sm e p o s i t i v ei n n u e n c eo ft l l en e wk i n do f e l i t ep o p u l a t i o nc o n s t r u c t i o n ( 3 ) t os 晚n g t h e nm es e a r c ha b i l i t yo ft h ea l g o r i t h m s ，w ed e s i 印t h ec o m p o n e n t e m p h a s i z i n gm e c h 砌s m ，w 1 1 i c hv i e wt h es i n g l ec o m p o n e n t2 l st h eb a s i cf a c t o rw m c h m a k e sas o l u t i o nd i a e r e n tf r o mt h eo t h e r s i i lt h en e w m e t l l o d ，ap a r e n ts o l u t i o nw i l l i i j 北京工q e 大学工学硕士学位论文 g e n e r a t em u c hm o r eo 凰研n gt h a nt h o s ei nt h et r a d i t i o n a lm e t h o d s ，a n dt h e ( 1 + 1 ) e v o l u t i o n a 巧s t r a t e g ya s s u r e st h a tt h eb e t t e rc o m p o n e n t sw i l lb ep r e s e r v e dd u r i n g 也e e v o l u t i o n t h ec o m b i n a t i o no ft 1 1 i sm e c h a n i s ma n dat r a d i t i o n a le l i t ep o p u l a t i o nc o n s t n j c t i o nm a k e san e wm o e a ，a n dt h ee x p e r i m e n tr e s u l t ss h o wt h a tt h en e w a l g o r i t h mo u t p e 面咖sb e t t e rt h a no t h e rc l a s s i c a lm o e a s ，w m c hp r o v e s 也a tt h ec o m p o n e n te m p h a l s i z em e c h a n i s mc a ne n h a n c et h es e a r c ha b i l i t v k e yw o r d sm o e a ；e l i t ep o p u l a t i o nc o n s t r u c t i o n ；e l i t e m e c h a n i s m ；c o m p o n e n t e m p h a s i z i n gm e c h a n i s m ；e v o i u t i o n a 叮s t r a t e g y i v 目录 目录 摘要i a b s t r a c t i i i 第l 章绪论一1 1 1 课题的研究背景与意义1 1 2 多目标进化算法的研究现状和方法分析2 1 2 1 精英种群构建方法2 1 2 2 子代个体的产生一5 1 3 课题的主要研究内容7 1 4 本文的组织结构。7 第2 章多目标进化算法概述9 2 1 多目标优化问题的定义9 2 2 多目标进化算法的框架10 2 3 多目标进化算法的评价指标ll 2 4 本章小结1 2 第3 章测试问题集的分析与修正1 5 3 1z d t 系列的测试问题1 5 3 2d t l z 测试问题集1 7 3 3 测试问题的缺陷及其修正1 9 3 4 本章小结2 2 第4 章基于空间网格的精英种群构建策略2 3 4 1 基本思想2 3 4 2 算法描述2 4 4 2 1 一种快速构建非支配集的方法2 4 4 2 2 基于空间网格的非支配集筛选2 6 4 2 3 基于空间网格的多目标进化算法( g s e a ) 2 7 4 3 实验结果与分析2 8 4 3 1 实验设计2 8 4 3 2 实验结果与分析2 9 4 4 本章小结3 3 北京i 业大学工学硕七学位论文 第5 章基于分量强调机制的子代个体产生策略3 5 5 1 基本思想3 5 5 2 算法描述3 6 5 2 1 基于分量强调机制的交叉算子3 6 5 f 2 2 基于分量强调机制的变异算子3 7 5 2 3 分量强调机制的多目标进化算法( c e g a ) 3 8 5 3 实验结果与分析4 0 5 3 1 实验设计4 0 5 3 2 实验结果与分析4 1 5 4 本章小结4 6 结论4 7 参考文献4 9 攻读硕士学位期间所发表的学术论文5 3 致 谢5 5 第l 章绪论 第1 章绪论 1 1 课题的研究背景与意义 在工程与科研实践中，优化问题是普遍存在的，对于这些优化问题，仅有1 个目标函数的，称为单目标优化问题( s i n g l eo b j e c t i v eo p t i m i z a t i o np r o b l e i i l s ，简称 s o p s ) ，而目标函数多于1 个，并且需要同时优化的，称为多目标优化问题 ( m u l t i o b j e c t i v eo p t i l l l i z a t i o np r o b l e m s ，简称m o p s ) 。由于现实世界中的具体问题 往往涉及多个相关的参考指标，各个指标需要同时优化，所以多目标优化问题在 实际应用中十分重要。对于一个多目标优化问题，其目标函数之间可能存在冲突， 这使得一个解对于某个目标来说是最优的，而对于其他某些目标可能不是最优， 因此，一般以一组折中解作为优化结果，在概念上称这种折中解集为p a r e t o 最优 解集或者非支配集( n o n d o m i n a t e ds e t ) 。 多目标问题的困难之处在于，需要求得非支配解集，而不像单目标问题那样 只需要求出一个解。虽然，通过对各个目标赋予一定权重的方法，可以把多目标 问题转化为单目标问题，但是，这种方法每次只能得到1 个解，效率太低，而且 权重值不易设定，因此这种方法很难获得良好的求解效果【2 j 。而进化算法 ( e v o l u t i o n a 珂a l g o r i t h m ，e a ) 作为一类模拟生物选择与自然进化的随机算法，具 有适应性强，效率高，能避免局部最优等特点【3 ，4 1 ，为多目标问题的求解提供一 种新的思路。自从19 8 5 年多目标进化算法( 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 ) 提出以来，经过2 0 多年的发展，多目标进化算法逐渐显现出它的 优势，尤其是近几年，国际上涌现出了一批有代表性的算法【5 。15 1 ，这些研究成果 的出现，为多目标进化算法的研究提供了更广阔的发展前景。 一个典型的多目标进化算法主要由两个部分组成：( 1 ) 对当前种群进行筛选， 构建精英种群。( 2 ) 利用当前得到的精英种群，产生子代个体。前一个部分制定 了一种保留良好个体的规则，利用这个规则指明了种群的进化方向。这种规则的 制定需要同时考虑种群的收敛性( c o n v e r g e n c e ) 和多样性( d i v e r s 时) 【2 j ，而且 通常情况下，精英种群的构建是算法中消耗时间较多的部分【3 j ，因此，一种快速 的筛选策略有助于提高算法的时间性能；而后一个部分，利用已经得到的精英种 群，借助进化算子( 例如交叉算子和变异算子) ，通过在决策空间【2 ，4 j 中进行随机 搜索，可以获得更好的个体，所以，一个优秀的进化算子是保证算法获得良好求 解结果和提高算法收敛性能的关键。总之，精英种群的构建策略和子代个体的产 在精英种群的构建中，难点就在于，以尽可能小的时间代价同时保证算法的收敛 性和多样性。围绕这个难点，经过长时间的探索，科研人员设计出了一系列有代 表性的算法。 ( 1 ) n s g a 和n s g a i i 基于g o l d b e r g 提出的非支配排序的思想【1 7 】，d e b 等人提出了n s g a 算法【3 1 。 非支配排序的基本思想是：把当前种群的全部个体根据他们相互间的p a r e t o 支配 情况分成不同等级，其中非支配解为第l 级，除去第1 等级后，剩下的全部个体 中的非支配解为第2 级，再除去第2 级后，剩下的全部个体中的非支配解为第3 级，依次类推，直到所有个体都分配到了相应的等级。n s g a 算法利用了非支配 排序的思想，该思想实际上是根据个体间的支配关系将当前种群分成不同层次， 2 层次数小的个体，这样就保证了种群进化的收敛性，当同一层次中的个体进行比 较时，使用共享适应度值的方法对同一层次中的个体赋予一定适应度值，该适应 度值反映了种群进化对多样性的要求，使得有利于保持多样性的个体能够以较大 的概率被保留下来。n s g a 算法根据这种对种群的划分，按照一定的比例选出用 于产生子代个体的种群( 即，精英种群) 。在每一次迭代过程中，n s g a 算法的 时间复杂度为d ( 朋妒) ，其中，m 是目标个数，是种群规模。n s g a 算法的缺 点是，时间复杂度较高，而且需要设定共享参数。 针对n s g a 算法的缺点，2 0 0 2 年d e b 等人提出了改进版本n s g a i i 【5 j ，该 算法取得了很大成功【2 ，3 1 。相对于n s g a 而言，n s g a i i 的优点体现在：( 1 ) 提 出了一种快速非支配排序的方法，使得时间复杂度由驮删) 降低为烈删z ) ；( 2 ) 为了保持种群的多样性，提出了拥挤距离的概念，并以拥挤距离的比较取代了 n s g a 中适应度值共享的方法，避免了参数的设定；( 3 ) 引入了精英保留机制p j ， 使子代个体与其父个体共同竞争以确定产生下一代个体的机会，从而有利于保持 优良个体，增强种群的进化水平。 ( 2 ) s p e a 和s p e a 2 1 9 9 9 年z i t z l e r 和t l l i e l e 提出了s p e a 【6 】算法。在该算法中，个体的适应度又 被称为p a r e t o 强度，非支配集中的个体适应度定义为其所支配的个体总数在群体 中所占的比重，其他个体的适应度定义为支配它的个体总数加1 ，约定适应度低 的个体对应较高的选择概率。除了进化种群外，还设置了一个保存当前非支配个 体的外部种群，当外部种群个体数目超过约定值时，则用聚类技术来删减个体， 确定最终得到保留的个体。当需要产生子代个体时，利用锦标赛选择，从进化群 体和外部种群中选择个体，再进行交叉和变异操作。该算法的时间效率较低，复 杂度达到d ( j ) b 一。 针对s p e a 的缺点，z i t z l e r 和1 1 1 i e l e 于2 0 0 1 年提出了s p e a 2 算法l 1 0 j ，在适 应度值分配、个体分布性的评估策略和非支配解集的更新三个方面进行了改进。 在s p e a 2 中，个体的适应度函数为以力= r ( d + d ( d ，其中，r ( f ) 同时考虑到个 体f 在外部种群和进化种群中的个体支配信息，d ( f ) 是由个体f 到它的第j | 个邻 近个体的距离决定的拥挤度度量。在构造新种群时，首先进行环境选择，然后进 行交配选择。在进行环境选择时，先选择适应度小于1 的个体进入外部种群，当 这些个体数目小于外部种群规定的规模时，再选择进化种群中适应度较低的个体 进行填充；当这些个体的数目大于外部种群规定的规模时，则运用环境选择进行 删减。在交配选择中，运用锦标赛机制选择个体。由于s p e a 2 引入了基于近邻 3 北京工业大学工学硕士学位论文 规则的环境选择，简化了s p e a 中基于聚类的外部种群更新方法。所以，尽管其 计算复杂度仍为伙3 ) ，但是，基于近邻规则的环境选择得出的解集的多样性比 原有算法有很大提高。 ( 3 ) p a e s ，p e s a 和p e s a p a e s 采用( 1 + 1 ) 进化策略【1 1 】对当前一个解进行变异操作，然后对变异后的 个体进行评价，比较它与变异前个体的支配关系，保留较好的个体。该算法的另 一个经典之处在于，引进了空间网格的机制来保持种群的多样性。具体方法为， 每一个个体分配一个格子。该算法的时间复杂度为d 他) ，其中为进化种群 的规模，札为外部种群的规模。随后，该算法所提出的空间网格被许多后继的多 目标进化算法采用。如c o n l e 等人基于这种空间网格的思想提出了p e s a 【1 2 】，该 算法设置了一个内部种群和一个外部种群，在算法运行中内部种群的非支配个体 并入到外部种群中，当一个新个体进入外部种群时，同时要在外部种群中淘汰一 个个体，具体的方法是在外部种群中寻找拥挤系数最大的个体，并将其删除，如 果同时存在多个个体具有相同的拥挤系数，则随机删除一个。其中，个体的拥挤 系数是指，该个体所对应的网格中所聚集个体的数目。2 0 0 1 年c o m e 等人对p e s a 做了进一步改进，并称其为p e s a i i 算法【1 引，该算法提出了基于区域选择的概念， 与基于个体选择的p e s a 相比，新算法用网格选择代替个体选择，从而提高了算 法的效率。 ( 4 ) m o e a 受到利用空间网格保持种群多样性的启发，2 0 0 2 年，l a u m 跚s 和d e b 等学 者对传统的p a r e t o 支配进行了修改，提出了支配的概念【1 8 】，并以此为依据设计 了m o e a 算法。支配借助空间网格保持种群的多样性。算法根据预先设定了 大小的网格对目标空间进行划分，在算法的运行中，保证每个网格中至多只有1 个解个体，从而避免了非支配个体的聚集。m o e a 算法实际上是利用支配取 代了传统的p a r e t o 支配关系，加强了筛选力度，因而在时间性能和解集的分布效 果方面体现出较大的优势。另外，m o e a 算法中还提出了稳态策略，该策略是 指每当新产生子代个体后，就用这个新个体与当前种群中全部个体进行比较，通 过这种比较，一方面对当前种群进行更新，另一方面确定新产生的子个体是否得 到保留。这种稳态策略能够保证比当前种群中个体差的子代个体不会得到保留， 从而可以避免种群进化中出现“倒退”现象，提高了种群的进化效率。大量的实验 数据表明，m o e a 与以往的多目标进化算法相比，无论在算法的时间性能还是 求解质量都具有比较明显的优势19 1 。但是，支配容易造成解集在靠近p a r e t o 边界处的个体的丢失，尤其是对一些p a r e t o 曲面有特殊形状的多目标问题，这种 缺点更加明显1 1 9 j 。 4 第1 章绪论 总之，围绕如何有效的对当前种群进行筛选，国内外学者设计出很多性能优 良的算法。概括起来，这些算法主要有两个方面的特点：( 1 ) p a r e t o 支配关系是 保证收敛性的基础，所有选择策略都体现了个体间p a r e t o 支配关系的比较，只有 在这种比较中占优的个体才会得到保留；( 2 ) 种群多样性维护的策略多种多样， 各个算法的重要区别一般就体现在如何保持种群的多样性，而多样性的维护并没 有一个十分明确的最好的方法，这也使得各个算法各有特色，难分伯仲。实际上， 种群的多样性是一个与种群相关的概念，单一个体不能体现多样性，这就要求在 对单个个体进行选择时，要把这个个体放到整个种群中来考虑，而不会像比较个 体间支配关系那样，只需要两个个体进行比较，因此，当选择一个个体时，理论 上需要把这个个体与整个种群比较，才能真正明确该个体对种群多样性的影响， 而这样做必然要付出较大的时间代价。为了降低时间消耗，多数算法实质上是用 单个个体与它附近的若干个体进行比较，从而保证局部具有较好的分布效果，但 是，这仅仅是以局部近似代替整体的做法，不能在绝对意义上保证种群的多样性。 所以，在多样性维护中，如何处理好“局部”和“整体”关系是解决问题的关键。 1 2 2 子代个体的产生 多目标进化算法本质上是一个随机搜索算法，子代个体的产生机制决定了算 法的搜索性能。在实际的算法中，一般使用进化算子，例如交叉算子、变异算子 来产生子代个体，这些进化算子便是子代个体产生机制的具体体现。一般来说， 一个先进的子代个体产生机制能够使得算法有更强的搜索性能，可以帮助算法快 速准确地收敛到最优解【2 0 ，2 1 1 。在子代个体的产生机制的研究中，国内外学者取得 了大量的学术成果。下面简要总结一下在产生子代个体方面出现的重要方法。 ( 1 ) 模拟二元交叉算子和多项式变异算子 在进化算法中，较早出现的编码方式一般采用o 1 编码，但是，随着研究的 深入，人们意识到实数编码更加方便，于是实数编码方式逐渐成为主流。模拟二 元交叉算子( s i m u l a t e db i 彻r yc r o s s o v e r ，s b x ) 和多项式变异算子( p o l y n o i l l i a l m m 纰i o n ) 是目前应用广泛的基于实数编码的进化算子。该算子由d e b 等人于1 9 9 4 年提出【2 0 】，其做法是，所设定的参数1 1 。和t h n ，按照一定的概率模型由输入的实 数计算出结果。这两个算子本质上规定了某个概率模型，在算法开始前，先设定 相应的两个参数，然后，算法执行中，把输入的实数带入概率模型，就可以算出 输出结果。这两个算子的输入实际上是决策向量的单个分量，即，当利用这对算 子时，是对个体的刀个分量逐一进行计算，再将新得到的分量组成一个新的决策 向量( 新个体) 。 北京工业大学工学硕士学位论文 ( 2 ) g d e 3 算法 g d e 3 【2 2 j 算法实际上是一种微分进化算法( d i 疏r e n t i a l e v o l u t i o 彻r y 舢g o r i t l 1 1 ) ，该算法在产生子代个体时，并不使用传统的变异算子，仅仅将输入的决 策向量，代入某个线性函数，就计算出输出个体。具体地，g d e 3 算法，先在当 前精英种群中随机挑选3 个个体，然后带入计算公式，就得到了一个新个体。 g d e 3 算法计算简便高效，但是，该算法对于决策变量中分量存在非线性关联的 问题，往往不易解决【2 引。 ( 3 ) 分布估计算法 分布估计算法是进化算法和统计学习的结合，通过统计学习的手段建立决策 空间内个体分布的概率模型，然后对概率模型随机采样产生新的群体，如此反复 进行，从而实现种群的进化2 3 彩】，将分布估计算法引入多目标进化算法是一种全 新的思路。2 0 0 8 年，z h a n gq i n g 如等人提出建立基于正态模型的多目标分布估 计算法( ar e g u l a r i t ym o d e l b a s e dm u l t i o b i e c t i v ee s t 曲a t i o no fd i s t r i b u t i o na 1 g o r i t h m ，刚m e d a ) 【2 3 】，该算法首先建立一个正态概率模型，然后利用在种群 更新的过程中反映的统计规律，不断更新这一模型，使得种群逐渐逼近最优解。 分布估计算法能够利用种群进化过程中的信息，提高种群的进化效率，并且能够 结合机器学习和概率统计中的相关技术，是一种先进的子代个体产生机制。但是， 这种子代个体的产生方式，需要在每次迭代中修正概率模型，增加了时间消耗， 因此，一种设计简单而高效的概率模型，是分布估计算法设计的关键四】。 总之，对于子代个体的产生机制主要包含三种方法：( 1 ) 输入决策向量的分 量，输出新的分量，然后将，1 个分量( 以是决策向量的维) 组成一个新个体；( 2 ) 输入决策向量，直接根据输入，计算出新的决策向量；( 3 ) 根据种群进化过程中 暗含的某种规律，即利用种群的信息产生新个体。从模型的角度考虑，每一个产 生子代个体的机制，实际上就定义了一种概率模型，随着算法的运行，这个概率 模型的输出结果的随机性将越来越小，最终使得算法收敛到决策空间的一个局 部，这个局部就是算法的计算结果。简言之，算法由随机性最大的初始状态开始， 最终由随机性较小的状态结束。这里暗含了一个问题，进化算法的一个优势就在 于它的随机性，这种随机性可以很大程度地避免算法收敛到局部最优，而算法的 最终结果是达到某种随机性较小的状态，即，随着算法的运行，这种随机性将逐 渐减弱，这就有可能使得算法收敛到局部最优。也就是说，如果一种策略能够使 随机性减小的速度较快，那么，一方面它有助于提高算法的收敛效率，另一方面， 它容易导致算法陷入局部最优。所以，在设计子代个体的产生机制时，如何把握 这种随机性减小的速度，是设计进化算子的关键。 6 1 3 课题的主要研究内容 综上，多目标进化算法的两个关键部分是精英种群的构建和子代个体的产 生，针对现有研究在这两个方面的不足，本文提出了相应的新方法。 ( 1 ) 在精英种群构建方面，提出了一种基于空间网格的筛选策略。该策略 先从当前种群中选出非支配个体，然后，利用设定边长的空间网格对这些非支配 个体进一步筛选，得到最终的精英种群。这种精英种群构建策略把对收敛性和多 样性的要求分成两个步骤，分别进行处理。筛选过程仅保留种群中的非支配个体， 降低了计算量，并且，能够保证子代个体全部由当前的非支配个体产生，从而有 利于得到质量更好的子代个体。在多样性的维护方面，通过使每个网格中至多保 留1 个个体避免了个体间的拥挤，有利于种群多样性的保持。实验表明，基于新 策略的算法经典算法相比，能够更高效的收敛到最优前沿，而且具有更好的多样 性。 ( 2 ) 在产生子代个体方面，提出了分量强调机制。该机制将个体的分量看 作影响个体质量的基本单位，当产生子代个体时，对父个体的分量逐一进行计算， 每一个仅与父个体有一个分量不同的子个体都能参与到竞争过程中，从而保证了 质量较好的单个分量在种群的进化过程中能够以更高的概率保留，提高了种群的 进化效率。基于分量强调机制，本文设计了相应的交叉和变异算子，并将这对算 子与一个经典的精英种群构建策略结合，提出了一个新的多目标进化算法。实验 结果显示，无论决策向量中的分量是否存在关联，分量强调机制都能显著地提高 算法的搜索能力。 1 4 本文的组织结构 第1 章：绪论。介绍了多目标进化算法的相关背景，并详细讨论分析了国内 外研究现状，最后说明了论文的研究内容。 第2 章：介绍了多目标进化算法的相关概念，给出评价算法求解结果的常用 指标和计算公式。 第3 章：给出了检验多目标进化算法性能的常用测试问题集，说明它们的相 关性质和最优前沿，然后，分析这些测试问题存在的不足，并给出相应的修正方 法。 第4 章：提出了基于空间网格的精英种群构建策略。该策略把精英种群的构 建分为两个步骤，先选出当前种群中的非支配个体，再利用给定边长的空间网格， 对非支配个体进一步筛选，得到最终的精英种群。将新策略与传统的进化算子结 7 8 一个目标函数。为了便于表述，先给出与多目标问题相关的一些重要概念【3 1 扔】。 定义2 1 ( 多目标优化问题) 不失一般性，一个具有，z 个决策变量，m 个目 标函数的多目标优化问题可以描述为： im i ny = ，( x ) = ( z ( x ) ，以( z ) ，0 ( x ) ) 1 1 j ， g ( x ) o ( f = l ，2 ，g ) ；办，( 工) = o ( = 1 ，2 ，p ) ( 2 1 ) 其中沪0 i ，而) x c 为刀维决策向量，彳为刀维决策空间，尸l ，脚) y c r m 为m 维目标向量，】，为m 维的目标空间目标函数撒) 定义了m 个由决策空间向 目标空间的映射关系；舒o ( 卢1 ，2 ，g ) 定义了g 个不等式约束：码= o ( ，= 1 ，2 ，护) 定义了p 个等式约束。 定义2 2 ( 可行解) 对于某个z z 如果x 满足( 2 一1 ) 中的约束条件，则称x 为可行解。 定义2 3 ( 可行解集合) x 中的所有可行解组成的集合称为可行解集合，记为 掾且雄丘 定义2 4 ( p a r e t o 占优，或称p a r e t o 支配) 假设砀和砌是多目标优化问题的 两个可行解，当且仅当 1 ，z ，尬，胞) 彳魄) 人 l ，z ，胸：z 也) z 魄)( 2 2 ) 称与妇相比，动是p a r e t o 占优的( 也称为拗支配x b ) ，记作张一 施。 在多目标进化算法中，经常遇到决策空间和目标空间这两个概念，其中，决 策空间就是指目标函数的定义域，而目标空间是指目标函数的值域。当涉及到 p a r e t o 支配的比较时，一般是将参与比较的个体映射到目标空间，然后再进行相 应目标值的比较，从而得出相互间的p a u r e t o 支配关系，由p a r e t o 支配的定义可以 看出，每进行一次p a r e t o 支配关系的比较，需要对这两个个体的全部m 个目标 值进行比较，因此2 个个体的每一次p a r e t 0 支配关系比较的时间复杂度为d ( 蚴， 其中m 为目标的个数。 9 ( 2 - 3 ) t o 最优解的集合，定 ( 2 5 ) 多目标进化算法可以简单理解为，将进化算法应用到多目标优化问题中，因 此多目标进化算法在框架上与一般的进化算法没有本质的区别。一般地，可以将 多目标优化算法的框架描述如下： 由算法2 1 可以看出，每次迭代过程中都要构建精英种群，然后根据选择得 到的精英种群，通过进化算子产生子代个体，进入下一次循环。因此，精英种群 的构建和子代个体的产生是多目标进化算法的两个核心部分，这两个部分共同决 定了算法的时间性能和求解效果。 另外，对于一个多目标进化算法，一般规定最大迭代次数g 作为算法的终止 条件l l j 。假设一个算法每次迭代的时间复杂度是d ( f ( 必) ) ，最大迭代次数是g ， 那么这个算法的总的时间复杂度可以表示为d ( g m 必加) ，即一个多目标进化算 法的时间性能是由每次迭代的时间消耗和所需要的最大迭代次数决定的。 1 0 第2 章多目标进化算法概述 2 3 多目标进化算法的评价指标 如前所述，多目标问题的求解结果一般是一组相互之间无优劣关系的解的集 合，而且一方面要求所得解个体到理论最优前沿的距离尽可能小，另一方面要求 解个体能较均匀地沿着理论前沿分布。这2 个要求，分别对应解的收敛性 ( c o n v e r g e n c e ) 和多样性( d i v e r s 时) 【4 2 1 。可见，收敛性和多样性是算法求解结 果的两个关键指标，一个算法的求解性能需要同时考虑这两个指标。 ( 1 ) 收敛性的评价指标 对算法的收敛性进行评价时，经常使用的评价指标有g d 指标和指标。 其中，g d 指标( g e n e r a t i o n a ld i s t a n c e ，g di n d e x ) 是、v e l m l m z e n 和l a m o n t 在1 9 9 8 年提出的【3 1 ，该指标代表了算法所得到的近似p a r e t o 前沿与真实最优前 沿的接近程度，它定义为： 1i l g d ( 爿) = r 刍i 1 1 1 i n ( 0 q p i i ) ，口i 么，p 尸 ( 2 6 ) 其中，p 串是对真实p a r e t o 前沿均匀采样的点集，彳是算法所得到的近似p a r e t o 前沿，显然，该指标的数值越低，说明求解结果的收敛性越好。在使用g d 指标 计算收敛性时，需要先明确测试问题的理论最优前沿，并在上均匀 地取若干个点得到尸宰，然后才能够计算出g d 的数值。然而，有些时候理论最 优前沿不易获得，这样就不方便使用g d 指标。 2 0 0 0 年，z i t z l e r 提出了c s 指标( t w os e tc o v e r a g e ，c si n d e x ) 【3 】，该指标没 有计算g d 指标的那些限制，它用来直接比较两个算法的收敛性的优劣。四指 标实际上是计算参与比较的两个种群尸l 和n 之间的相互覆盖程度，计算公式为： 田( 暑：选堕坠# 型型 ( 2 - 7 ) l 2 i 如果尸i 中的所有个体都支配或等于岛中的个体，那么似尸l ，尸2 ) = 1 ，反之则等 于零。一般情况下，在使用四指标比较两个种群p l ，戌的收敛性时，需要同时 计算c 双p l ，戌) 和瞅p 2 ，p 1 ) 这两个数值。虽然傩评价指标不再需要预先知道 测试问题的最优解，但是该评价方法仅能用于比较算法结果的收敛性，无法知道 算法所得结果与真实最优前沿的近似程度。 ( 2 ) 多样性的评价指标。 多目标问题的评价方法中，多样性的评价指标的设计是一个十分重要而又非 常困难的问题。目前常用的方法有s p a c i i l g 指标【3 】，么指标【5 1 和佑d 指标圆。 s c h o t t 于1 9 9 5 年提出s p a c i n g 指标用来评价种群在目标空间中的分布情况， 地说明算法的求解效果( 这一点，对于目标数是2 和3 的问题往往能够做到，但 是目标数超过3 的测试问题，只能用评价指标进行量化的比较) 。在本文的实验 中，根据需要选用上面介绍的评价方法，另外，还通过对某些问题给出求解结果 在目标空间中的散点图，用以直观地比较。 2 4 本章小结 本章首先给出多目标优化问题的定义，并分析了求解多目标问题的特殊性， 然后描述多目标进化算法的框架，指出了算法中的两个重要部分，最后介绍评价 1 2 第2 章多目标进化算法概述 多目标进化算法性能的常用指标以及对其量化的常用方法。 1 4 第3 章测试问题集的分析与修正 第3 章测试问题集的分析与修正 多目标进化算法的性能比较，一般是让参与比较的算法在一组相同的测试问 题上进行运算，然后根据运行时间和求解结果对算法的性能进行评估和比较。为 了能够更好的考察算法的性能，很多学者深入研究了大量的多目标优化问题，在 此基础上设计了许多优秀的测试问题集，为多目标进化算法间的客观比较提供了 公认的测试集。这里先给出几个有代表性的测试问题，说明它们的相关性质和最 优前沿，然后，分析这些测试问题存在的不足，并给出相应的修正方法。 3 1z d t 系列的测试问题 z d t 是z i t z l e r 等人设计的一类十分常用的测试问题集【2 6 ，2 7 1 ，该类测试问题 的目标数全部是2 ，并且最优解和最优前沿都较容易表达。另外，该类测试问题 的决策变量个数以可以是任意的，一般通过控制甩的数值改变问题的难度。本文 主要参考了z d t l ，2 ，3 ，6 这4 个测试问题，下面分别对其进行简单介绍。 ( 1 ) 测试问题z d t l 的解析式为： 工( x ) = x - ，以( x ) 2g (