（控制科学与工程专业论文）多目标智能优化算法及其在制造系统中的应用.pdf

摘要 用新设计的启发式算法解决布局问题以最小化单元内与单元间的物流总成本。计算结果表明， 禁忌搜索和启发式算法分别提供了良好的机器单元配置、机器布局和单元布局 研究了基于禁忌搜索的多目标单元构造问题。首先根据多目标禁忌搜索( m o t s ) 自身的特 点提山了一种非劣解集的有效处理方法，它和m o e a 中的外部档案维护策略作用类似，但没 有引入个体密度值。其次，对于考虑加上顺序和加工时间的单元构造问题，利用多目标禁忌 搜索寻找最优的机器单元配置以最小化j 二件的总移动次数和单元负荷变化量。通过对5 个测试 问题的计算实验并与g u p t a 等1 4 1 提出的遗传算法比较，计算结果袭明，本文算法性能优良。晟 后，对于同时考虑加工顺序，加工时间，安装时间和单元内与单元间运输成本的单元构造问 题，设计了一种多禁忌搜索任务的并行策略，对菲劣解集中的多个解和当前解进行插入和互 换操作，提出了将上件的各j 二序分派到机器单元的方法以保证各单元闯负荷失衡量尽量小。 s h s ua n dh s u i l “1 提出的并行模拟退火( p s a ) 相比，本文算法能产生更多支配p s a 计算结果的非 劣解。 关键词：智能优化算法多目标进化算法外部档案微粒群作业车问调度模糊 调度禁忌搜索单元构造 l l 上海交通大学| 尊士论文 a b s t r a c t t h i sp a p e rm a i n l ya p p l i e se v o l u t i o n a r y ( e a ) ，p a r t i c l es w a l t uo p t i m i z a t i o n ( p s o ) a n dt a b u s e a r c h ( t s ) e t ct os o v l es o m em 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 si nm a n u f a c t u r i n gs y s t e m s t w om 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 n do n em u l t i - o b j e c t i v ep a r t i c l es w a r m o p t i m i z a t i o n ( m o p s o ) a r ef i r s tp r e s e n t e da n dt h e n ak i n do fm o e a si s a p p l i e dt oj o bs h o p s c h e d u l i n gp r o b l e m s f i n a l l y , t a b us e a r c hb a s e dm 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 sa r e p r o p o s e df o rs o m ep m b l e m so fc e l l u l a rm a n u f a c t u r i n gs y s t e m sd e s i g n t h i sp a p e rd e s i g n sc r o w d i n gm e a s u r e - b a s e dm o e a ( c m o e a ) ，i nw h i c he x t e r n a la r c h i v ei s u s e dt os t o r et h en o n d o m i n a t e ds o l u t i o n sp r o d u c e di nt h ep r o c e s so fs e a r c ha n de a c ho fa r c h i v e m e m b e ri sa s s i g n e dh i g h e rf i t n e s st h a na n ys o l u t i o n so u to fa r c h i v e f i t n e s sa s s i g n m e n tr e f l e c t st h e r e s u l to fa r c h i v em a i n t e n a n c e t h ea b o v ef e a t u r eo fc m o e ai ss e l d o mc o n s i d e r e di nt h ep a s t t h e c o m p u t a t i o n a lr e s u l t ss h o wt h a tc m o e ai sp r o v i d e dw i t hg o o dp e r f o r m a n c ef o rc o n t i n u o u s o p t i m i z a t i o n an e wa p p r o a c hh y b r i d i z i n gm o e aw i t hl o c a ls e a r c hi sp r o p o s e d t h e r ea r et w od i f f e r e n c e s b e t w e e no u ra p p r o a c ha n dm u l t i - o b j e c t i v eg e n e t i cl o c a ls e a r c hf m o g l s ) ：1 o n l ys o m ec o p i e so f e x t e r n a la r c h i v ea c ta st h ei n i t i a ls o l u t i o n so f l o c a ls e a r c ha n dt h es o l u t i o n sp r o d u c e db yl o c a ls e a r c h d o n tb e c o m et h em e m b e r so fp o p u l a t i o nu n l e s s t h e yd o m i n a t es o m eo fa r c h i v e ；w h i l em o s to f p o p u l a t i o nc a nb et h ei n i t i a ls o l u t i o n so fl o c a ls e a r c hi nm o g l s 2 t h ep r o p o s e dh y b r i da l g o r i t h m i ss u c c e s s f u l l ya p p l i e dt oc o n t i n u o u so p t i m i z a t i o na n dc o m b i n a t o r i a lo p t i m i z a t i o nw h i l em o g l s i s s e l d o mu s e dt os o l v ec o n t i n u o u sm o e p a r e t oa r c h i v em u l t i - o b j e c t i v ep s o ( p a m o p s o ) i sd e s i g n e d ，i nw h i c ht h e a r c h i v ei s m a i n t a i n e db yt h ec r o w d i n gm e a s u r e - b a s e dm e t h o da n dt h eg l o b a lb e s tp o s i t i o ni ss e l e c t e df o re a c h p a r t i c l e i nt h ep r o c e d u r eo fa r c h i v em a i n t e n a n c e a r c h i v em a i n t e n a n c ei sc o m b i n e dw i t ht h e s e l e c t i o no fg l o b a lb e s tp o s i t i o n mn e wm u t a t i o no p e r a t o ri sp r o p o s e d ，w h i c hi sj u s ta p p l i e dt os o m e m e m b e r so fa r c h i v ef o rp r o d u c i n gm o r en o n d o m i n a t e d s o l u t i o n s f i n a l l y , t h ep e r f o r m a n c e c o m p a r i s o n so fp a m o p s o w i t hd i f f e r e n ti n e r t i aw e i g h ta r ei n v e s t g a t e d t h ec o m p u t a t i o n a lr e s u l t s d e m o n s t r a t et h a tp a m o p s op o s s e s s e sg o o dp e r f o r m a n c ef o rc o n t i n u o u so p t i m i z a t i o na n dt h e i n c l u s i o no fm u t a t i o nn o to n l y i m p r o v e st h ev a r i o u sp e r f o r m a n c eo fp a m o p s ob u ta l s od i m i n i s h e s t h es e n s i t i v e n e s so fa l g o r i t h mt ot h ev a r i a t i o no fi n e r t i aw e i g h t w i t hr e s p e c tt oj o bs h o ps c h e d u l i n g ，h o wt oo b t a i nan u m b e ro fp a r e t o - o p t i m a ls c h e d u l i n gi s i l l a b s t r a c t s e l d o mi n v e s t i g a t e da n dm o s to fa l g o r i t h m sc a no n l yp r o v i d eo n eo rs e v e r a ls c h e d u l i n gp l a n s i nt h i s p a p e r , a f t e rt h en e we n c o d i n gm e t h o db a s e do np r i o r i t yr u l ei sp r o p o s e d ，c m o e ai sf i r s tu s e dt o s o l v ean u m b e ro fm u l t i o b j e c t i v ej o bs h o ps c h e d u l i n g , t h e na f t e rt h eg e n e t i ce n c o d i n gm e t h o d b a s e do n p r i o r i t y r u l ei s t r a n s p l a n t e d t of u z z y s c h e d u l i n g ，c m o e ai sa p p l i e d t os e v e r a l m u l t i - o b j e c t i v ef u z z yj o bs h o ps c h e d u l i n gp r o b l e m s a l lc o m p u t a t i o n a lr e s u l t ss h o wt h a tc m o e a c a np r o v i d em a n ye f f e c t i v es c h e d u l i n gp l a n sa n dh a ss t r o n gs e a r c hc a p a c i t yt oj o bs h o ps c h e d u l i n g w i t hr e s p e c tt oc e l l u l a rm a n u f a c t u r i n gs y s t e m sd e s i g n ，t h eh y b r i d i z a t i o no ft a b us e a r c ha n dt h e c l u s t e r i n ga l g o r i t h m sb a s e do ns i m i l a r i t yc o e f f i c i e n ti sf i r s ti n v e s t i g a t e d t h ec l u s t e r i n ga l g o r i t h m f i r s tp r o v i d e sa ni n i t i a lm a c h i n ec e l lc o n f i g u r a t i o na n dt h e nt h ei n i t i a lc o n f i g u r a t i o ni sc o n t i n u o u s l y i m p r o v e db yt a b us e a r c h t h eh y b r i da l g o r i t h mi sa p p l i e dt oan u m b e ro fc e l lf o r m a t i o np r o b l e m s w i t ha l t e m a t i v ep r o c e s sr o n t i n g sa n dc o m p u t a t i o n a lr e s u l t sd e m o n s t r a t et h a tt h eh y b r i da l g o r i t h m h a si t so w ua d v a n t a g ei nc o m p u t a t i o n a lt i m ea n ds e a r c hp e r f o r m a n c e ，t h ei n t e g r a t i o no fc e l l f o r m a t i o na n dl a y o u td e s i g ni nt h eu n i d i r e c t i o n a ll o o pm a t e r i a lh a n d l i n ge n v i r o n m e n t si st h e n c o n s i d e r e d at w o p h a s ea p p r o a c hi sp r o p o s e dt od e a lw i t ht h ei n t e g r a t i o np r o b l e m i nt h ef i r s t p h a s em a c h i n ec e l l sa r ec o n s t r u c t e du s i n gt a b us e a r c ht om i n i m i z et h e i n t e r - c e l lf l o wa n dp a r t f a m i l i e sa r ed e t e r m i n e da n da l l o c a t e dt oc o r r e s p o n d i n gc e l l st oo p t i m i z et h en u m b e ro fe x c e p t i o n a l e l e m e n t s i nt h es e c o n dp h a s el a y o u td e s i g ni sd o n eu s i n gan e wh e u r i s t i ct om i n i m i z et h ei n t r a - c e l l a n di n t e r - c e l lt r a n s p o r t a t i o nc o s t t h ec o m p u t a t i o n a lr e s u l t ss h o wt h a tt a b us e a r c ha n dh e u r i s t i c s r e s p e c t i v e l yp r o v i d eg o o dm a c h i n ec e l lc o n f i g u r a t i o n ，m a c h i n el a y o u ta n dc e l ll a y o u t t h i sp a p e rc o n s i d e r st a b us e a r c hb a s e dm u l t i - o b j e c t i v ec e l lf o r m a t i o np r o b l e m s f i r s t l y ，a n e f f e c t i v em e t h o df o rd e a l i n gw i t hn o n - d o m i n a t e ds o l u t i o ns e tj sp r e s e n t e da c c o r d i n gt ot h ef e a t u r e o fm u l t i - o b j e c t i v et a b us e a r c h ( m o t s ) t h em e t h o di ss i m i l a rw i t ha r c h i v em a i n t e n a n c eo fm o e a ； h o w e v e r ，d e n s i t yv a l u ei s n ta d o p t e d s e c o n d l y ，ak i n do fm o t si sa p p l i e d t oc e l lf o r m a t i o n c o n s i d e r i n gp r o c e s s i n gt i m ea n dp r o c e s s i n gs e q u e n c ef o rm i n i m i z i n gt h et o t a lm o v e sa n dc e l ll o a d v a r i a t i o n t h em o t si sp e r f o r m e do nf i v et e s tp r o b l e m sa n dc o m p a r e dw i t hg e n e t i ca l g o r i t h m ( g a ) p r o p o s e db yg u p t ae ta l t h er e s u l t sd e m o n s t r a t et h a tt h em o t s h a sg o o dp e r f o r m a n c e f i n a l l y ， f o rc e l lf o r m a t i o np r o b l e mc o n s i d e r i n go p e r a t i o ns e q u e n c e ，p r o c e s s i n gt i m e ，s e t u pt i m ea n d i n t r a - c e l la n di n t e r - c e l lt r a n s p o r t a t i o nc o s t ，ap a r a l l e ls t r a t e g yf o rm u l t i p l et a b us e a r c ht a s ki s d e s i g n e d ，i n s e r t i o na n ds w a po p e r a t i o na r ed o n ef o rs e v e r a ls o l u t i o n sf l o mn o n d o m i n a t e ds o l u t i o n s e ta n dt h ec u r r e n ts o l u t i o nt h em e t h o da s s i g n i n gt h eo p e r a t i o n so fp a r t si n t om a c h i n ec e l l sf o r o b t a i n i n gt h ef e w e s ti n t e r - c e l ll o a du n b a l a n c ei sa l s op r o p o s e d t h ep r o p o s e dp a r a l l e la l g o r i t h mc a n p r o d u c em o r en o n d o m i n a t e ds o l u t i o n sd o m i n a t i n gt h es o l u t i o n so fp a r a l l e ls i m u l a t e da n n e a l i n g o b t a i n e db ys ua n dh s u 1 2 0 】 上海交通大学博士论文 k e y w o r d s ：i n t e l l i g e n to p t i m i z a t i o na l g o r i t h mm u l t i - o b j e c t i v e e v o l u t i o n a r ya l g o r i t h m e x t e r n a la r c h i v e p a r t i c l es w a l n lo p t i m i z a t i o nj o bs h o ps c h e d u l i n gf u z z ys c h e d u l i n g t a b u s e a c hc e l lf o r m a t i o n v 上海交通大学学位论文答辩决议书 i 门r i 孤玎f 厂1 f 胗i 相1 2 ： ( p q k ) 跏l 沦与控制i 。刷 西夏耍网厚孺鬲潭厢酾法j 孬姹“制造系统中们壁j 9 薪碉r 琢而f 而硼厂器两砸丽_ l r徐“+ 校教2 楼篁! 蠼窟 择晰凌城会战出 丽丽币i 羽厂碱磊l r - 口 称i i 所柏i 作l 丫l 化 l i 箭汴0 箍私 i i 碡f 嘭j ：越f l 教授l f 牛尔娜1 ：人学 无 委员0 何涮森8 教授i 汛人学尢 扛人7 ： 委员l 嘏裕庚l i 教授：渐变j | 豇大学 无 必l f 伞少远0 教授0i i 海空埘人。 员0 张卫东8 教授 i _ 海交通大学 委员 i 尖智铭l l 教授| ：海交通人 尤 论文选题具 雷德明同学的博士论文结合制造系统的调度与设计， 有重要的理论意义与实用价值。 研究了多目标智能优化算法， 论文地耋萋翌日良设计了几种多目标智能优化新算法，并在基于优先规则的遗传编码新方式的 基础上，将基于密集距离的多目标进化算法应用于多目标作业车问调度和多目标模糊作业车间调 度；提出了禁忌搜索和基于相似系数的聚类算法的混合算法以解决可选加工路径的单元构造问题和 两阶段方法解决单元构造与布局设计的集成问题：提山了非劣解集的有效处理方法，并以此为基础。 研究了基于禁忌搜索的多目标制造单元设计问题。 蹩矛论文思路消嘶、层次分明、论述有据，表明作者具有坚实宽r 的理论基础和系统深入的专 业知识，具有较强的独立科研能力和创新能力。答辩过程中讲述清楚，回答问题正确，经答辩委员 会无记名投票，一致通过论文答辩，建议授予雷德明同学工学蹲士学位 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 一躲穹f 钏 日期：2 町年夕月? 日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 - 不保密口。 ( 请在以上方框内打“”) 学位敝储硌荡钐n 指唰咝! 牺黪 日期：z c 呵年f 护月，日日年1 1 , 1 弓日 ， 上海交通大学博士论文 第1 章绪论 摘要：奉章主要介绍多目标进化算法( m o e a ) 的研究进展，首先综述7m o e a 的主要研究主题，然后给 出一些基本概念，最后详细描述了2 0 年来m o e a 的研究进展。 1 1 引言 智能优化算法是通过模拟某一自然现象或过程而建立起来的，它们具有适于高度并行与 白组织、自学习、自适应等特征，为解决复杂问题提供了一种新的途径。当前，许多流行的 算法都是智能优化算法，这些算法包括进化算法( e a ) 、微粒群算法( p s o ) 、禁忌搜索f r s ) 、模 拟退火( s a 、等，其中进化算法模拟的是生物进化过程，它将问题的求解表示成染色体的适者 生存过程，通过染色体的一代代进化，最终收敛到“最适应环境”的个体，得到问题的晟优 解或满意解，该类算法主要包括遗传算法( g a ) 、进化策略( e s ) 和进化规划( e p ) 等；微粒群算法 来源于对鸟群优美而不可预测的飞行动作的模拟，微粒的e 行速度动态地随微粒自身和同伴 的历史飞行行为改变而改变；禁忌搜索是一种全局逐步优化算法，它模拟的是人类的智力过 程，它通过引入一个灵活的存储结构和相应的禁总规则来避免迂回搜索，并通过藐视原则来 赦免一些被禁忌的优良状态，以实现全局优化；而模拟退火则是基丁m e n t ec a r l o 迭代求解策 略的随机寻优算法，其出发点是固体物质的退火过程与一般组合优化问题的相似性，从某一 初温开始，随着温度的降低，结合概率突跳特性在解空间中搜索最优解，即在局部解时能概 率性地跳出并最终趋于全局最优。 本文利用e a ，p s o 和瑙处理一些多目标优化问题( m o p ) ，以获得问题的p a r e t o 最优解集， 由于进化算法( e a ) 是解抉：m o p 的有效t 具和主要手段，也是本文豹研究重点，本章将只介绍 多目标进化算法( m o e a ) 的研究进展，有关p s o 对m o p 的应用将在下一章描述。由于本文主要 利用t s 进行多目标单元构造，相关研究进展将在第5 章介绍。 从s c h a f f e r ”o l 于1 9 8 5 年首次设计r n 量估计遗传算法( v e g a ) 开始，多目标进化算法经过 1 9 8 5 1 9 9 4 的停滞期和1 9 9 4 年到现在的发展期，m o e a 受到了许多研究者的关注，特别是近几 年( 1 9 9 4 - 2 0 0 1 ) ，多目标进化算法的文献发表数量是整个停滞期的6 倍，山现了大量性能优良的 算法包括p a e s ，s p e a ，s p e a 2 ，n s g a ，n s g a - 2 ，r d g a 等。 表1 列出了2 0 年来出现的主要m o e a s 第一代算法中，非p a r e t o 方法没有直接利用p a m t o 最优的基本概念、高效且很易实现但不能产生p a r e t o 最优前端的某些部分。而p a r e t o 方法则 利用非劣排序( n o n d o m i n a t e dr a n k i n g ) 和选择使整个种群逼近p a r e t o 晟优前端。第二代算法普 遍采用外部档案或外部种群保留算法获得的非劣解，算法搜索效率得到改善。 第1 章绪论 表1 多目标进化算法分类 第一代算法第二代算法 非p a r e t o 方法p a r e l o 方法p a l e s ，m - p a e s ，p e s a ，p e s a i l 加权方法p u r e p a r e t or a n k i n gs p e a s p e a 2 v e g am o g an s g a 2 l e x i c o g r a p h i co r d e r i n gn s g a m o m g am o m o a 】j t h e - c o n s t r a i n tm e t h o dn p g an p g a 2 m i c r o g a t ：= u ( ，b 。，贮) ：f f ii n i t i l i z e 0 w h i l e t e r m i n 口t e ( a ，b ，t 1 = f a l s pd o t ：一t + 1 彳_ t r u n c a t eu p d a t e ( a - 1 , b “) ) p ：净n d a p t ( a ，b t - 1 ，p 。t 一1 1 b ? = v a r y ( s a m p l e ( e v a t u n t e ( a ，f ，p ：) ) ) e n dw h i l e 图1 上边为基于集成模型的算法框架，下边为对应的流程图，其中a 表示档案，b 为种群p ： 为第t 代的e l i t i s mi n t e n s i t y 。 和单目标进化算法( s o e a ) 不同，m o e a 必须提供( 1 ) 一组数量尽可能大的非劣解，并要求 这组解( 2 ) 逼近问题的全局p a r e t o 最优前端且( 3 ) 尽可能均匀地分布在整个全局最优前端上。大 2 上海交通大学博士论文 多数m o e a s 的设计都是围绕如何有效地实现上述三个目的，每一种算法都是实现这些目的 的特定方法的组合。l a u m a n n s 等1 7 3 1 提出了m o e a 的一种集成模型( u m n i e a ) ，如图1 所示， 根据该模型，在每一代，根据新产生的非劣解对外部档案进行升级，当档案大小即档案内能 保留的非劣解的个数超过规定值时，对档案进行修剪( t r u n c a t e ) 根据个体适应度值从外部档案 和种群中选择个体进入下一代。许多m o e a s 都是u m m e a 的变形。根据该模型，在设计m o e a 时，必须处理外部档案的升级与维护以及对个体赋予适应度值，它们对算法性能产生很大的 影响，一般情况f ，适应度赋值方法将影响算法逼近全局最优前端的程度而外部档案维护直 接决定算法的多样性性能。 选择策略对e a 性能的影响会起到举足轻重的作用，不同的选择策略导致不同的选择压 力，即下一代中父代个体的复制数目的不同分配关系，较大的选择压力使最优个体具有较高 的复制数目，加快算法收敛，但易出现过早收敛，而较小选择压力能使种群保持足够的多样 性，但收敛速度较慢。m o e a 基本上不采用基于适应度值的选择如轮盘赌，而是利用基于局 部竞争的选择，其中，在遗传算法中，用锦标赛选择，在进化策略中采用u + a 或( ，a ) 选择。 性能指标用来评价算法是否实现了要求达到的目标，在m o e a 中，一个好的指标必须能 反映算法实现上述3 个目的中一个或几个的程度，没有一个指标能同时描述3 个目的的实现程 度。目前，出现了根多指标来度量算法的求解质量，这些指标包括覆盖集合，g e n e r a t i o n a l d i s t a n c e ，收敛性指标y ，多样性指标等。为了提高算法研究与比较的效襄必须设计一些 能反映实际多目标优化问题基本特征的标准测试函数身毛这一类标准函数集合包含了多目标 问题领域的基本知识w h j t l e v 等【1 3 l l 对多目标优化问题的测试函数设计提出以下几点准则： ( 1 )测试函数必须是简单搜索策略所不易解决的 ( 2 1测试函数中应包括非线性耦合和非对称问题 ( 3 )测试函数中应包含问题规模可伸缩的问题 f 4 )一些测试函数的评估代价应具有可伸缩性 f 5 1测试函数应有规模的表达形式。 目前已积累了不少多目标测试函数，非约束测试函数有z d t l 6 d t l z i 7 等，约束测 试函数包括c t p l 7 ，o s y 等。 利s o e a 一样，m o e a 也会出现过早收敛现象，在s o e a 中，随着搜索的进行，整个种 群的绝对平均值不断增加，导致一些“探索”类个体即位于搜索空间新区域的一些适应度值 小的个体很难存活，算法无法产生新的有效个体。关于m o e a ，当种群中大多数解都为非劣 时，新解很难产生和接受，算法搜索停滞或过早收敛于局部最优集，许多研究者认为种群缺 乏多样性是产生过y - 收敛的原因，h u 等【5 ”认为过早收敛的根本原因在于算法缺乏探索新区域 的能力，种群多样性低只是过早收敛的表象。为了避免算法过早收敛，人们提出了很多有效 的方法，将e a 与局部搜索结合就是其中最有效的方法之一，m o e a 与局部搜索的混合算法 有m p a e s ，m o g l s 及其多种改进形式，每一代，种群完成遗传操作后，将局部搜索应用于 3 第1 章绪论 种群中的每个个体的拷贝，这些算法对于组合优化问题具有良好的搜索性能。 有关m o e a 的理论研究很少，只有少数作者讨论算法的收敛性并进行相应分析，人们主 要关注如何维持外部档案的多样性，这些工作包括p a e s 中的自适应格子方法、s p e a 中的聚 类分析以及n s g a - - 2 中的快速非劣排序方法等，但这些算法无法对m o p 都具有良好的收敛 性。算法的收敛性与多样性很难统一于一个算法中。m o e a 已应用于形状优化设计以及生产 调度等领域，表1 中列出的每种算法都应用于一些实际问题，但这些应用大多数都限于2 目 标问题，对3 个以及3 个以上的m o p 应用比较少见。总之，多目标进化算法已成为当前智能 计算界相当活跃的研究热点，在过去2 0 年里，很多问题得到了很好解决，有些问题包括理论 分析、进化停止准则等依然困扰着人们。 1 2 基本概念 通常在多目标优化领域广泛采用、被普遍接受的m o p 定义如下 定义1 一般m o p 由n 个决策变量，m 个目标函数和丁种约束条件组成，最优化目标如 m a x y = ，( 工) = ( 苫) ，2 ( 卫) ，l ( 工) 1 s u b j e c t t o g ，( 工) s 0i = 1 ，z t x r “ ( 1 ) 其中，j ( 置，x 2 ，x ) e x 为决策向量，y = ( y l , y ：y 。) e y 表示目标向量，x 为决 策向量形成的决策空间，y 表示目标向量形成的目标空间。 m o p 的本质在于大多数情况f 各目标是相互冲突的，某目标的改善可能引起其它目标性 能的降低，同时使多个目标均达到最佳是不可能的，只能在各目标之间进行协调权衡和折衷 处理，使所有目标函数尽可能达到晟优，最优解不再是在给定约束条件下使所有目标函数最 大的解，而是p a r e t o 晟优集。多目标优化经常会用到如下几个基本概念 定义2p a r e t o 支配，解工。支配x 1 ( 工。卜x 1 ) 当且仅当 f ( j o ) f a x l ) i = 1 2 ，m正( 工o ) l ( x 1 ) 3 i e 1 ，2 , - - 肌 p a r e t o 最优，如果解x o 是p a r e t o 最优的当且仅当一j r l ：x 1 - x o p a ”t o 最优集，f f i ：有 p a r e i 。最优解的集合只= x o | 一i x 】卜p 】 p a r e t o 均衡面，所有p a r e c 0 最优解对应的目标函数值所形成的区域p ， 昂一 ，( 工) = ( 五( 工) ，2 ( 工) ，l ( x ) ) l x s e 。 非劣解或非受支配解指一个解集内不受其中任何一个解支配的解 4 上海交通大学博士论文 外部档案或档案为解集，足算法搜索过程中产生的一些非劣解的结合 多目标优化有其完全不同于单目标优化的特点：大多数情况f ，类似单目标优化的最优 解在m o p 中是不存在的，只存在p a r e t o 最优解。m o p 的p a r e t o 最优解只是一个可接受的“不 坏”解，并且大多数m o p 的p a r e t o 最优解的个数很多，甚至是无穷大，而m o p 的最优解就 是包含所有这些p a r e t o 最优解的一个集合。因此，对于实际问题，必须根据对问题的了解程 度和决策者偏好，从大量的p a r e t o 最优解中选择一些来使用。 1 3 多目标进化算法的研究进展 下面从如下几个方面描述2 0 年来多目标进化算法的研究进展。 由于m o p 要同时处理多个目标，通常e a s 应用于多目标优化时要考虑如卜两个关键问 题，为了保证算法朝p a r e t o 最优前端方向逼近，如何对个体进行适应度赋值；为了避免算法 过早收敛和获得均匀分布且范围更广的非劣解，如何维护维护外部档案，保持群体多样性。 13 1 适应度赋值 m o e a 必须为每个个体确定适应度函数值这种适应度函数和每个目标函数的具体大小 没有直接关系，而在单目标优化中，这两个函数是直接相关的；另外，在个体保持不变的条件 下，同一个体在这一+ 代获得的适应度值和它在下一代的适应度值可能不相等，这种情况在单 目标优化时，是不可能出现的下面介绍几种常见的适应度赋值方法。 一、基丁目标函数的方法 此类m o e a s 在选择阶段不将各目标组合成一个单目标的标量适应度值，而是直接将目 标函数确定为适应度函数。例如，s c h a f f e r i ”0 1 提出一种向量评价方法，它先将种群中全部个体 按目标函数的数目均分成若干个子种群，对每个子种群分配一个目标函数，然后根据该目标 函数确定的适应度值对子种群进行独立的选择操作，最后将所有新的子种群合并成一个新的 种群。f o u r m a n l 3 6 给出了两种选择策略。第一种采用字典顺序法，即首先给各目标一个优先权， 选择过程根据目标优先权进行个体的比较，较高优先权的目标先比较，如果两个体不分胜负， 比较第2 高优先权的目标，依次进行，直到分出胜负。k u r s a w e 7 0 1 提出在选择阶段根据概率确 定各目标的排序，该概率值由用户决定或随机产生。上述方法存在的问题是进化结果 容易走向某些极端边界解，且对p a r e t o 最优前端的非凸敏感 二、加权方法 加权方法容易理解、易于实现，最近提出了若干种加权方法：固定加权法、随机加权法 和自适应加权法。固定加权法中，各目标的权值保持不变。m u r a t a 等【9 ”提出了随机加权法， 在选择过程中的每一步随机地给出权值，这样可以给所有可能地组合以平等地机会，这种方 法忽略了每代p a r e t o 解中可能获得的信息。自适应加权法中，根据当前种群中的有用信息对 权值进行适应性凋整以获得朝向正理想点的搜索压力，由于将当前种群中的有用信息用于调 5 第1 章绪论 整权值，其选择压力介于上述二者之间。 三、基于p a r c t o 支配的方法 此类m o e a s 最早使用由g o l d b e d 删提出的基于p a r e t o 支配关系来计算个体的适应度。 它的个体等级确定过程如f ：当代群体所有非劣个体的等级设为1 ，将它们暂时从群体移出， 再将剩余的群体中的非劣个体等级设为2 也暂时移出，如此循环直到所有个体都赋值，最后 将个体等级值赋为适应度值。此时，个体适应度值与群体规模有关，和其它个体有关，其它 个体会直接影响该个体的适应度值大小。后来，将密度值引入到适应度值中。 基于p a r e t o 支配的方法已被许多研究者采纳，z i t z l e r 和t h i e l e t ”1 实现了一种赋值方案， 非劣解的适应度值小于1 而劣解的适应度值大于1 ，而且支配它的个体越多，劣解的适应度值 越大。当个体之间没有p a r e t o 支配关系时，个体密度值常被用来确定适应度函数值，例如在 s p e a 2 中，个体f 的适应值f i t ( i ) = r ，4 - b ，r 为原始适应值，d i = 1 ( 2 + o ，) ，o i 为个 体i 与第k 个最相邻个体在目标空间上的距离，在p a e s 中，具有较高支配分数( d o m i n a n c e s c o r e ) 的个体被赋予较高适应度值，而对于具有相同支配分数的个体，它所在格子内的解越少， 其适应度值越高。而在n s g a i i 中，当两个点位于同一前端时，拥挤距离大者适应度值较高。 1 32 外部档案维护 外部