（机械制造及其自动化专业论文）带约束的多目标进化算法及其应用研究.pdf

l 41 1 1 1 1 l m m 吣叭叭帆帆帆 。 下o2 n 6 10 3 一 c i a s s i f i e dl n d e x ：t p l8 s e c u r i t yc l a s s i f i c a t i o n ： u d c ： 许 s e c u r i t yp e r i o d ： d i s s e r t a t i o nf o rt h em a s t e r sd e g r e e r e s e a r c ho nc o n s t r a i n e d m u l t i o b j e c t i v ee v o l u t i o n a r y a l g o r i t h ma n di t sa p p l i c a t i o n c a n d i d a t e ： s u p e r v i s o r ： s p e c i a l i t y ： 一 r e s e ar c bf i e l d ： u n i v e r s i t y ： s u b m i s s i o nd a t e ： l ip e n g p r o f y ug u o y a n e n g i n e e r i n g d i g i t a ld e s i g na n dm a n u f a c t u r et e c h n o l o g y g u a n g d o n go c e a nu n i v e r s i t y a p r i l2 0 1 0 广东海洋大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得 的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承 担。 作者签名：苍鹂2 。f 。年6 月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权广东海洋大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：李 导师签名：1 翁l 乱 2 0 0 每 2 0m 年 月7 日 6 月1 3e t 带约 车间调度问题对企业提高资源利用率、节约成本、提高运行效率起着关键作用。 但车间调度问题是一个多目标优化问题，且这些目标之间往往是相互冲突的，传统的 解决方法是将多目标优化问题通过一定的处理转化为单目标优化问题，这种处理方法 每次实验只能得到单一的最优解。为了得到多个可行较优解，就需要进行多次重复实 验，这大大降低了优化效率。因此，研究一种高效的、可解决多目标的、带约束的优 化算法来解决诸如车间调度这类实际生产问题，具有重要的理论与实践意义。 差分进化( d i f f e r e n t i a le v o l u t i o n ，d e ) 算法是一种高效的、解决连续优化问题 的进化算法，本文对如何利用d e 算法解决当前工程实际中最常见的多目标约束优化 问题作了深入研究。研究内容主要从以下两方面进行：一是研究如何提高d e 算法在 解决多目标约束优化问题的算法效率；二是研究d e 算法在车间调度优化中的应用。 第一部分的研究内容为： ( 1 ) 研究了如何将解决单目标、无约束优化问题的标准d e 算法用于解决多目 标约束优化问题。在对标准d e 算法分析研究的基础上，提出了一种基于双群体搜索 机制的改进d e 算法来解决多目标约束优化问题，采用了两个不同种群分别保存可行 个体与不可行个体的双群体约束处理策略，利用基于p a r e t o 的分类排序多目标优化技 术来完成对进化个体解的评价。并通过混池群体初始化、自适应交叉和变异操作来提 高d e 算法的性能。用三个标准b e n c h m a r k 函数对其进行测试，验证了其解决低维多 目标约束优化问题的有效性； ( 2 ) 针对标准d e 算法在解决多目标优化问题时其多样性与收敛性之问的平衡 维持难题，提出了基于自适应动态变异和非支配解二次变异的改进d e 算法。用六个 标准测试函数对其进行测试，验证了其性能优于非支配排序遗传算法和标准d e 算法； ( 3 ) 针对标准d e 算法在求解多目标优化问题时非支配解数目过少、易陷入局 部最优的不足，提出了一种结合分阶段二次变异和混沌理论的改进d e 算法来解决多 目标约束优化问题。用典型测试问题对其进行测试，验证了所提算法能在全局搜索性 能和局部搜索性能之间维持较好平衡。 第二部分的研究内容为： ( 1 ) 研究了如何用d e 算法来解决多目标流水车问调度问题。主要工作是对标 准d e 算法进行了改进，使d e 算法的应用范围从解决连续优化问题扩展到离敝优化 问题，构建了适合求解多目标流水车间调度问题的离散d e 算法，用经典调度模型的 标准测试问题集对其进行测试，验证了算法的有效性； ( 2 ) 研究了如何用d e 算法来解决更为复杂的多目标作业车阳j 调度问题。主要 工作是对标准d e 算法进行改进，构建了适合求解多目标作业车间调度问题的离散 d e 算法，并采用1 0 个作业车间调度的标准测试问题对其进行测试，验证了算法的有 效性。 最后，对全文进行了总结，并对后续工作作了讨论。 关键词：约束优化问题，多目标优化，差分进化算法，二次变异，车问调度 a b s t r a c t j o bs h o ps c h e d u l i n gp r o b l e mp l a y sa k e yr o l ei ne n h a n c i n gr e s o u r c eu t i l i z a t i o nr a t e ， r e d u c i n gc o s ta n da d v a n c i n go p e r a t i n ge f f i c i e n c yf o re n t e r p r i s e b u tj o bs h o ps c h e d u l i n g p r o b l e mi sam 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 ，a n dt h e s eo b j e c t i v e so f t e nc o n f l i c tw i t h e a c ho t h e r f o rt h ec l a s s i c a lm e t h o 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 np r o b l e mi su s u a l l y t r a n s f o r m e di n t oas 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 m ，s oe a c ht e s tc a no n l yo b t a i n sa o p t i m a ls o l u t i o n i no r d e rt oa c q u i r em o r ef e a s i b l es u b o p t i m a ls o l u t i o n s ，e x p e r i m e n tn e e d s t ob er e p e a t e do v e ra n do v e ra g a i n ，i tg r e a t l yr e d u c e st h eo p t i m i z i n ge f f i c i e n c y t h e r e f o r e ， r e s e a r c ho na ne f f i c i e n tc o n s t r a i n e do p t i m i z a t i o na l g o r i t h mt h a tc a ns o l v em u l t i - o b j e c t i v e p r o b l e m ，s u c h a st h ea c t u a l p r o d u c t i o np r o b l e m - j o bs h o ps c h e d u l i n g ，i s o f g r e a t s i g n i f i c a n c eb o t ho nt h e o r ya n dp r a c t i c e d i f f e r e n t i a le v o l u t i o n ( d e ) a l g o r i t h mi sav e r ye f f i c i e n te v o l u t i o n a r ya l g o r i t h mt h a ti s u s e dt os o l v ec o n t i n u o u so p t i m i z a t i o np r o b l e m i nt h i sp a p e r , h o wt ou s ed ea l g o r i t h mt o s o l v em u l t i - o b j e c t i v ec o n s t r a i n e do p t i m i z a t i o np r o b l e mi sd i s c u s s e d ，w h i c ho f t e na p p e a r s i nt h ec u r r e n tp r a c t i c ee n g i n e e r i n g t h ec o n t e n to ft h ep a p e ri sm a d eo ft h ef o l l o w i n gt w o a s p e c t s ，o n si sh o wt oe n h a n c et h ee f f i c i e n c yo fd ea l g o r i t h mw h i c hi su s e dt os o l v e m u l t i - o b j e c t i v ec o n s t r a i n e do p t i m i z a t i o np r o b l e m ，t h eo t h e ri sr e s e a r c ho nt h ea p p l i c a t i o n o fi m p r o v e dd ea l g o r i t h mi nj o bs h o ps c h e d u l i n gp r o b l e m t h ec o n t e n t so ft h ef i r s ts e c t i o na r ea sf o l l o w s ： ( 1 ) h o wt os o l v em u l t i o b j e c t i v ec o n s t r a i n e do p t i m i z a t i o np r o b l e mb yd ea l g o r i t h m i ss t u d i e di nd e t a i l t h r o u g ha n a l y z i n ga n ds t u d y i n go ft h es t a n d a r dd e a l g o r i t h m ，w h i c hi s u s e dt os o l v et h ep r o b l e mo fu n c o n s t r a i n e do p t i m i z a t i o na n ds i n g l eo b j e c t i v e b a s e do n d o u b l ep o p u l a t i o n ss e a r c h i n gs c h e m e ，a ni m p r o v e dd if f e r e n t i a le v o l u t i o n a l g o r i t h mi s p r o p o s e df o rm u l t i - o b j e c t i v ec o n s t r a i n e do p t i m i z a t i o np r o b l e m t w od i f f e r e n tp o p u l a t i o n s a r ea d o p t e df o rh a n d l i n gc o n s t r a i n t si no p t i m i z a t i o np r o c e s s ，o n ei sf o rf e a s i b l es o l u t i o n s ， a n dt h eo t h e ri sf o ri n f e a s i b l es o l u t i o n s t oe v a l u a t ee v o l u t i o n a r yi n d i v i d u a l ，p a r e t o b a s e d s o r t e dr a n k i n gm u l t i - o b j e c t i v et e c h n o l o g yi sa d o p t e d i na d d i t i o n ，i no r d e rt oi m p r o v et h e a l g o r i t h mp e r f o r m a n c e ，p o p u l a t i o nc h a o t i ci n i t i a l i z a t i o n ，a d a p t i v ec r o s s o v e ra n dm u t a t i o n a r ea d o p t e da tt h es a m et i m e t h r o u g he x p e r i m e n t so nt h r e eb e n c h m a r kf u n c t i o n sw i t h c o n s t r a i n t sa n dm u l t i - o b j e c t i v e s ，i ts h o w st h a tt h ep r o p o s e da l g o r i t h mi se f f e c t i v ef o r s o l v i n gm u l t i o b j e c t i v ec o n s t r a i n e do p t i m i z a t i o np r o b l e mo fl o wd i m e n s i o n ( 2 ) i no r d e rt ok e e pb a l a n c eb e t w e e nd i v e r s i t y a n dc o n v e r g e n c eo fd if f e r e n t i a l e v o l u t i o na l g o r i t h mi ns o l v i n gm 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 ，a ni m p r o v e dd e b a s e do na d a p t i v ed y n a m i cm u t a t i o na n ds e c o n dm u t a t i o no fn o n - d o m i n a n c es o l u t i o nw a s p r o p o s e d t h r o u g he x p e r i m e n t s o ns i xb e n c h m a r kf u n c t i o n s w i t hc o n s t r a i n t sa n d m u l t i o b j e c t i v e s ，i ts h o w st h a t t h ep r o p o s e da l g o r i t h mi ss u p e r i o rt on o n - d o m i n a t e d s o r t i n gg e n e t i ca l g o r i t h mi ia n ds t a n d a r dd ea l g o r i t h mi np e r f o r m a n c e ( 3 ) t oa v o i ds h o r t c o m i n g sw h e nt h es t a n d a r dd ea l g o r i t h mi s u s e dt os o l v 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 ，s u c ha st h en u m b e ro fn o n - d o m i n a t e ds o l u t i o no b t a i n e d i st o os m a l la n dt h ea l g o r i t h mi se a s i l yt r a p p e di n t ol o c a lo p t i m u m ，a na d v a n c e d d i f f e r e n t i a le v o l u t i o na l g o r i t h mc o m b i n gg r a d i n gs e c o n dm u t a t i o na n dc h a o t i ct h e o r yi s p r e s e n t e d t os o l v e m u l t i o b j e c t i v e c o n s t r a i n e d o p t i m i z a t i o np r o b l e m b e n c h m a r k s f u n c t i o n sa r et e s t e d ，s i m u l a t i o nr e s u l t ss h o wt h i sa l g o r i t h mh a sb e t t e rc o n v e r g e n c ea n d d i s t r i b u t i o np r o p e r t y t h ec o n t e n t so ft h es e c o n ds e c t i o na r ea sf o l l o w s ： ( 1 ) m u l t i o b j e c t i v ef l o ws h o ps c h e d u l i n gp r o b l e m ( f s s p ) b a s e do nd ea l g o r i t h mi s s t u d i e d t h em a i nt a s ki st om o d i f yo p e r a t o r so fs t a n d a r dd ea l g o r i t h ma n de x t e n di t s a p p l i c a t i o nf r o mc o n t i n u o u so p t i m i z a t i o np r o b l e m t od i s c r e t eo p t i m i z a t i o np r o b l e m d i s c r e t ed ea l g o r i t h mw h i c hi ss u i t a b l ef o rs o l v i n gm u l t i - o b j e c t i v ef s s pi sc o n s t r u c t e d e x p e r i m e n t so ns t a n d a r dt e s t i n gp r o b l e m s e to fc l a s s i cs c h e d u l i n gm o d e la r em a d e ， s i m u l a t i o nr e s u l t si n d i c a t et h a tt h ep r o p o s e da l g o r i t h mi se f f e c t i v e ( 2 ) h o wt ou s ed ea l g o r i t h mt os o l v em o r ec o m p l i c a t e dm u l t i o b j e c t i v ej o b 。s h o p s c h e d u l i n gp r o b l e m ( j s p ) i ss t u d i e d t h em a i nw o r ki st om o d i f ys t a n d a r dd ea l g o r i t h m a n dc o n s t r u c td i s c r e t ed ea l g o r i t h mi no r d e rt os o l v em u l t i - o b j e c t i v ej s ee x p e r i m e n t so n t e ns t a n d a r dt e s t i n gp r o b l e mo fj s pa r em a d e ，s i m u l a t i o n r e s u l t sd e m o n s t r a t e st h e e f f e c t i v e n e s so ft h ep r o p o s e da l g o r i t h m f i n a l l y , s u m m a r yo ft h ew h o l ep a p e ri sg i v e na n d t h ef u t u r ew o r ki sd i s c u s s e d k e yw o r d s ：c o n s t r a i n e do p t i m i z a t i o np r o b l e m ， e v o l u t i o na l g o r i t h m ，g r a d i n gs e c o n dm u t a t i o n ， i v 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 ，d i f f e r e n t i a l j o bs h o ps c h e d u l i n g 2 2 3 2 算法改进的基本思想10 2 3 3 算法改进的关键技术1 0 2 4 数值仿真实验与分析1 2 2 4 1 算法流程l2 2 4 2 测试函数13 2 4 3 算法性能评价标准13 2 4 4 与n s g a i i 算法的性能对比1 4 2 4 5 与其它改进算法的性能对比l5 2 4 6 算法收敛性分析。l6 2 5 本章小结17 3 基于自适应动态变异和非支配解二次变异的差分进化算法18 3 1 弓i 言一l8 3 2 算法改进的基本方法18 3 3 算法改进的关键技术l9 3 4 数值仿真实验与分析。2 1 3 4 1 算法流程2l 3 4 2 测试函数2 2 3 4 3 算法性能评价标准2 2 3 4 4 实验结果与分析2 2 3 4 5 算法的进一步验证2 4 3 5 本章小结2 6 4 分阶段二次变异的多目标混沌差分进化算法2 7 4 1i ；i 言2 7 4 2 混沌理论及其在差分进化算法中的应用简介2 7 4 2 1 混沌理论简介2 7 4 2 2 混沌理论在差分进化算法的应用2 8 4 3 多目标差分进化算法2 9 4 4 基于分阶段非支配解二次变异的混沌多目标差分进化算法3 0 4 5 数值仿真实验与分析3l 4 5 1 算法流程31 4 5 2 测试函数3 2 4 5 3 算法性能评价标准一3 2 4 5 4 实验结果与分析3 2 4 6 本章小结3 3 5 基于改进差分进化算法优化的多目标流水车间调度3 5 5 1 引言3 5 5 2 问题描述及数学模型3 5 5 2 1 问题描述3 5 5 2 2 数学模型3 6 5 3 基于差分进化算法的多目标p f s p 求解3 7 5 4 算法实现步骤4 0 5 5 实例仿真及结果4 0 5 6 本章小结4 2 6 基于改进差分进化算法优化的多目标作业车间调度4 3 6 1 引言一4 3 6 2 问题描述及数学模型4 4 6 2 1 问题描述4 4 6 2 2 数学模型4 4 6 3 基于差分进化算法的多目标j s p 求解4 5 6 4 算法实现步骤4 9 6 5 实例仿真及结果4 9 6 6 本章小结5 0 7 总结与讨论5 2 参考文献5 4 攻读硕士学位期i 廿j 发表的学术论文5 9 致谢6 0 作者简历61 导师简介6 2 广东海洋大学硕士学位论文 1 前言 1 1 研究目的和意义 随着科学技术和社会生产力水平的不断发展，企业之间的竞争同趋激烈，这使企 业对管理和生产过程都提出了更高的要求，企业必须全面缩短交货期、减小成本、提 高企业的质量和服务来响应市场。车间调度是决定企业生产能力的关键因素，它是制 造业提高资源利用率，节约成本，提高运行效率的关键环节之一，并且是整个先进生 产制造系统实现管理技术，运筹技术，优化技术，自动化与计算机技术发展的核心。 而目f j 我国企业的车l 刈调度工作大部分靠车间管理人员的经验来安排。由于车间 调度中工件、加工机器、搬运系统和库场之间相互影响、相互作用，每个工件要考虑 其加工时间、准备时间、操作顺序和交货期等因素，且加工过程中有很多随机和不确 定性因素，因而相当复杂，已被证明是一个n p 难题乜1 。传统的基于管理人员经验的。 调度方式存在着时间长、效率低、动态响应差等缺点，难以根据市场的快速变化有效、 有组织地利用本企业的现有资源。因此，以计算机技术为基础的调度方法和系统研究 成为国内外关注的热点，并已出现了多种不同的基于计算机技术的调度方法，与传统 的手工调度相比，它们改善了调度方案，降低了生产成本，提高了企业生产效益和资 源利用率。但是，车间调度作为一个多目标优化问题，存在着时阳j 最小化、利益最大 化、成品率最大化、机械损耗最小化等多个相互冲突的目标。对此，传统的多目标优 化方法通过将多目标优化问题转化为单目标优化问题来解决，这种处理方法每次实验 只能得到单一的最优解。为了得到车i 日j 调度问题的多个可行较优解，就需进行多次重 复实验，这大大降低了优化效率。因此，研究一种高效的优化算法来解决车间调度问 题就成为当务之急，它能有效促进我国企业生产管理的现代化，提高我国企业的竞争 力，对其进行研究既具有重要的理论意义，也有很强的实践意义。 对车间调度这类生产问题的研究方法最初集中在整数规划、实验仿真和简单的规 划等方法上，用这些方法很难得到理想的调度结果，也难以解决复杂的大规模车间调 度问题。”。目前对车间调度问题的研究方法总结起来可以分为经典调度理论和智能调 度理论。经典调度理论主要有调度规则、多项式算法、解析法等。这些算法都存在 一定的局限性，如调度规则不具备一般性、推广性；多项式算法只能以特定的调度问 题为研究对象，针对某特定领域，到目前为止，主要是单机和简单的并行多机问题； 解析法对大规模问题提取模型困难，运算量大，算法难以实现。 近年来，许多智能技术被应用于车间调度问题，比较具有代表性的有：人工神经 带约束的多目标进化算法及其戍用研究 网络、遗传算法、粒子群算法、蚂蚁算法、禁忌搜索算法、模拟退火算法等。这些技 术的应用使车间调度理论取得了重大进展，同时也是当前车问调度理论的研究热点。 但由于实际车间调度问题同时受到资源、成本、交货期等多个因素的制约，如何将不 同的智能算法与实际问题结合来解决复杂的车间调度问题，以获得更好的性能还有待 于更进一步的研究。 d e 算法是一种高效的、解决连续优化问题的进化算法，但由于标准d e 主是用 来解决无约束、单目标的优化问题，而当前现实工程领域中存在的大多是多目标约束 优化问题。因此，在标准d e 算法基础上对其进行研究和改进，使其能解决带约束的 多目标优化问题，并进一步将其推广到车间调度这类离散、多目标约束优化问题，更 加符合实际工程需要。 本文的丰要目的是研究一种可解决多目标、约束优化问题的有效优化算法来解决 诸如车间调度这类实际生产问题。以标准d e 算法为基础，首先研究如何利用d e 算 法柬解决多目标约束优化问题；其次对如何提高d e 算法在解决多目标约束优化问题 的算法效率进行了研究；最后，对d e 算法在两种不同类型的车间调度问题中的应用 进行了研究。 1 2 国内外研究现状 1 2 1 多目标约束优化问题的进化算法研究现状 多目标优化| u j 题由于其在科学研究和工程实践中的普遍存在性及求解复杂性，促 使很多科研t 作者都为之付出了艰辛的努力。早在1 7 7 2 年，f r a n k l i n 就提m 了多h 标问题其目标冲突如何协调的问题n 1 。1 8 9 6 年，p a r e t o 第一次从数学的角度提出了多 目标最优决策问题，并引入p a r e t o 最优解的概念埔1 ，与此同时，k u h n 盯1 等人给出了向 量极值问题有效解的必要条件，至此，多目标优化问题彳逐渐受到人们的关注。 多目标优化方法的发展可以分为两个阶段。第一个阶段为从2 0 世纪5 0 年代木到 9 0 年代初，即传统的多目标优化方法时期。这一时期的主要特点是通过各种方式将 多目标优化问题转化为单目标优化问题，然后再用单目标优化方法来求解；第二阶段 为从2 0 世纪9 0 年代中期至今，即多目标进化算法时期。这一时期的主要特点则是通 过寻求各种进化算法来直接求解多目标优化问题。 进化算法通过模拟自然界的生物进化过程来解决实际问题，起源于达尔文的生物 进化论和孟德尔的遗传学 兑理论m 1 。目前进化算法阳3 的研究主要有遗传算法( g e n e t i c a l g o r i t h m ，g a ) 、进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 、进化策略( e v o l u t i o n a r y s t r a t e g y ，e s ) 和遗传编程( g e n e t i cp r o g r a m m i n g ，g p ) 等。基于进化算法的多目标优化 方法主要用到的就是遗传算法，概括起来可分为两种：即非基于p a r e t o 的多目标进化 算法( 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 ，m o e a ) 和基于p a r e t o 的多目标进化算 2 广东海洋大学硕士学位论文 法。前者典型的代表有聚集函数法( a g g r e g a t i o nf u n c t i o n ，a f ) 和向量评估遗传算法 ( 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 ) ：后者则以基于分类排序的p a r e t o 遗传 算法( n o n d o m i n a t e ds o r t i n gg e n e t i c a l g o r i t h mi i ，n s g a i i ) 和精英策略( e l i t i s t ) 的 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 ya l g o r i t h m2 ，s p e a 2 ) 等为代表。具 体如下： ( 1 ) 聚集函数法( a f ) ：a f 是最早用于求解多目标优化问题的进化算法盯1 。在遗 传算法中，每一个目标都有相应的目标函数值及适应度值。聚集函数法则对每个目标 赋予不同的权值，并对多个目标进行线性组合，将其转化为单目标，然后再使用遗传 算法对其优化求解。这种算法的优点是运行效率高，但缺点也很明显，各目标权重确 定困难，主观性随意性较大，且算法对参数的改变表现非常灵敏1 。 ( 2 ) 向量评估遗传算法( v e g a ) ：v e g a 由s c h a f f e r 在其1 9 8 4 年的博士论文 中n 纠提出。v e g a 对简单进化算法( s i m p l ee v o l u t i o n a r ya l g o r i t h m s ，s g a ) 进行扩充， 提出向量形式的适应度计算方法，从而可以对多个目标向量进行处理，即v e g a 。该 算法的主要优点是简单，且提高了种群的多样性，但由于没有采用p a r e t o 选择机制， 算法容易收敛于局部最优解。 ( 3 ) 基于p a r e t o 排序的多目标遗传算法( m u l t i o b j e c t i v eg e n e t i ca l g o r i t h m ， m o g a ) ：m o g a 由f o n s e c a 和f l e m i n g 3 1 于1 9 9 3 年提出。在m o g a 中，种群中的 个体根据当时种群中支配它的个体数来排序，并采用共享函数和小生境( n i c h e ) 技术 来实现种群的多样化。m o g a 的主要优点是运行效率较高且实现相对容易，不足是 需人为确定小生境的大小，对共享参数的选择过于依赖。 ( 4 ) 基于小生境的小组决胜遗传算法( n i c h e dp a r e t og e n e t i ca l g o r i t h m ，n p g a ) ： n p g a 由h o r n 和n a f p l i o t i s 在1 9 9 3 年提出1 。n p g a 采用基于p a r e t o 支配关系的锦 标赛选择( t o u r n a m e n ts e l e c t i o n ) ) 6 j l $ 1 j ，部分种群选取非劣最优解，并使用小生境技术实 现共享来维持种群的多样性。n p g a 的主要优点在于运行效率高，能获得较好的p a r e t o 自i 沿，不足是共享参数及锦标赛规模的选择没有一个通用法则，需人为确定，并且在 实际应用中很复杂。 ( 5 ) 基于分类排序的p a r e t o 遗传算法( 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 ) ：n s g a 由s r i n i v a s 和d e b 州于1 9 9 3 年提出。它是基于种群中个体的等级按 层次来分类排序的。该算法效率高，能够得到分和均匀的非劣最优解，但计算复杂度 高，无精英保留策略，且共享参数需人为预先给定。基于这些不足，d e b 等1 人于 2 0 0 0 年又提出了改进版的n s g a ，即带精英保留策略的n s g a i i 。n s g a i i 克服了 n s g a 的缺陷，降低了计算复杂度，且在低维优化问题上表现得非常好。 ( 6 ) 基于精英策略( e l i t i s t ) 的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 ) ：z i t z l e r 和t h i e l e 【l 刚于1 9 9 9 年提出了s p e a 。它是在进化过程中同 时保留两个群体：主群体和外部非劣群体，其中外部非劣群体是用来保存和更新算法 带约束的多目标进化算法及其应用研究 在进化过程中所找到的非劣个体。该算法继承了以往所有多目标进化算法的优点，能 够获得分布均匀的非劣最优解集，特别是在高维问题上，这一点尤为明显。但由于采 用聚类过程来保持群体多样性，时间耗费大，运行效率不高。因此，z i t z l e r 等训人于 2 0 0 1 年提出了s p e a 2 ，实现了对s p e a 的改进，其性能比s p e a 有了较大的改进。 近年来，随着m o e a 成为国际学术界跨学科研究的热点，许多新的算法被应用 到m o e a 中，这些新算法的引入为多目标进化算法的进一步发展提供了新的思路。 差分进化( d i f f e r e n t i a le v o l u t i o n ，d e ) 算法心羽就是其中一种，它由s t o r n 和p r i c e 等学 者于1 9 9 5 年首先提出，其最初的设想是用于解决切比雪夫多项式问题。由于算法结 构简单、可控参数少、鲁棒性强等特点，一经提出就得到了很多学者的重视，短期内 发展很快，并在许多领域得到了广泛应用。在1 9 9 6 年举行的第一届围际i e e e 进化 优化竞赛上，d e 算法被证明是最快的进化算法。虽然d e 算法收敛速度快，但与遗 传算法一样，仍存在早熟现象，特别是当优化高维问题时早熟现象更为严重心3 1 。针对 这种现象，国内外学者从不同方面对标准d e 算法进行了改进。 文献 2 4 ，2 5 从操作算子方面对d e 算法进行改进，提出一种具有自适应操作算 子的d e 算法，对标准函数测试结果表明改进后的算法能有效避免早熟收敛，显著提 高算法的全局搜索能力；文献 2 6 ，2 7 从算法结构方面进行改进，在d e 算法中加入 迁移操作，当种群的分散度低于一定的阈值时，利用迁移操作在最优个体附近区域重 新产生新个体，并替换旧个体，提高了科，群多样性；文献 2 8 ，2 9 从种群数目方面进 行改进，提出多种群并行进化策略。该策略通过在多种群并行进化过程中进行种群问 个体迁移，实现信息共享，增强全局搜索能力；文献 3 0 ，3 1 从与其它进化算法结合 方面进行改进，利