（计算机应用技术专业论文）基于演化算法的多目标优化方法及其应用研究.pdf

摘要现实中遇到的许多问题往往表现为由多个、可能相互冲突的目标构成的多目标优化问题。多年来多目标优化问题尽管已有许多求解方法，然而最近十几年来演化算法己逐渐发展成为解决多目标优化问题的理想方法，特别为求解大规模复杂的多目标优化问题提供了有效的研究方法，因而多目标优化问题也已经成为演化算法领域的研究热点。正因为如此，多目标优化在现实世界中正得到广泛应用：在经济学和管理中，用于求解证券投资、通货膨胀和经济增长模型中的多目标决策、运输投资等问题；在工程设计中可用于多目标选址问题、多目标指派问题、多目标设计问题、交通问题等：在网络与通讯中主要应用于网络的拓结构设计组播路由( m u l t j c a s t ) 和g e o c a s t 等问题中。随着研究和应用的深入，实际求解问题的复杂性对算法的各种性能等技术发展提出了新的挑战。因此，如何进一步提高演化算法性能，以及在多目标优化领域，如何将有关的搜索策略和多目标优化技巧进行有效的结合从而最终提高问题的求解质量，将是本文研究的关键问题，所有这些研究也将拓展演化算法及其在多目标优化领域的应用研究。本文的主要工作包括：( 1 ) 遗传算法中的种群多样性对遗传算法的收敛等性能具有重要的影响作用，本文具体分析了遗传算法的演化性能特征、遗传算法的多样性问题，以及影响遗传算法性能的一些主要因素。在此基础上分析了基于混合优化策略的演化算法，这将是改善算法性能的一个重要途径，并分析了从整体上提高算法性能的可行性及其有效机制。基于此，以类车辆路径调度问题( 冲，v 幽i c l er o u t i n gp r o b l e m s ) 为问题背景，结合2 一o p t 局部优化算法提出了g aw i t ho o p t 算法来求解冲问题，讨论了以遗传算法求解冲问题的染色体表示和有关遗传操作，并给出了算例分析。( 2 ) 为致力于多目标演化算法的求解目标，本文分析了多目标演化算法设计中所要解决的主要各种策略应用问题：适应度赋值方法、选择操作和遗传操作的设计。基于多目标混合演化算法的形成机制及其一般结构，提出了种改善收敛性能的混台多目标演化算法，将传统的局部搜索方法应用于m o e a ，即基于h 0 0 k ea n dj e e v e s 局部搜索的m o e a h m o e a ，并以算例验证其可行性、有效性和收敛性能。( 3 ) 交叉算子是演化算法特别是遗传算法( g a ) 中的重要的构成要索，其对g a 的性能影响理论上虽然还没有形成系统的分析，但基于实践和经验的认识，交叉算子对g a 性能的影响发挥着重要作用。本文分析了交叉算子在演化算中所存在的性能特征，基于演化算法中的有效交叉算子和多目标优化问题的自身特征，借助已有的运用于多目标演化算法中的策略，研究了将两种交叉算子有机地运用于多目标演化算法，提出了基于两种交叉操作相互结合的多目标演化算法( m u l t i o b j e c t i v ee v o l u t i o n a d a l g o r i t h mb a s e do nd o u b l ec r o s s o v e f s ，m o e a d c ) ，分析了算法的收敛性能、解集分布性能和计算效率，并进一步证明了它的收敛性，并通过复杂的算例验证了相关性能。( 4 ) 工程优化设计及管理决策的现实情况决定了多目标演化算法是一种较好解决问题的方法，本文通过了一个简单的机械设计的问题并结合算法m o e a d c分析了多目标演化算法在实际应用中的必要性，以及它在工程设计、管理中为决策者所带来的决策信息和产生的指导作用。并进步给出了混合交叉策略的多目标演化算法m o e a d c 在一类投资组合应用方面的案例研究，与相关研究作了比较，分析了该算法应用于工程管理方面的的可行性，以及能够为投资决策者提供较为全面的、灵活的投资选择决策。因此本研究能够为一类工程优化和管理问题的决策者或管理者在实际操作过程中提供较为具体的相关信息和更大的灵活性。关键词：多目标优化问题，演化算法，多目标演化算法，混合演化算法a b s t r a c t1 nr e a lw o r l dp r o b l e m s ，o n ei sf a c e dw i t ht h ep r o b l e m ，w h i c ho f l e ni sc o m p o s e do fm u l t i p i e ，p o s s i b l yc o m p e t i n 岛g o a l s ，w h i l eb e i n go p t i m i z e ds i m u l t a n e o u s l 弘t h a ti s ，t h ep 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 ma i t h o u g ht h e 印p r o a c h e sf o rs 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 s ( m o p s ) h a v eb e e na v a i l a b l ef o rm a n yy e a r s ，e v o l u t i o n a r y g o r i t h m s ( e a s ) h a v eb e e nd e v e l o p e dt ob ei d e a lt e c h n i q u e sf o rs 0 1 v i n gm o p s 、e s p e c i a l l yf o rv e r yl a r g es c a l eo n e st h e r e f o r em o p sa l s ob e c o m ef o c u si nt h ed o m a i no fe a st h e r e b ym u l t j o b j e c t i v eo p t i m i z a t i o n e 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 ew i d e i yu s e ds u c ha sf o l l o w si np r a c t i c e ：m u l t i o b j e c t i v ed e c i s i o n ，t r a n s p o n a t i o na n dp o r t f 0 1 i op r o b l e m sf o rs o l v i n gi n v e s t m e n ts e c u r i t i e s ，i n 丑a t i o n ，e c o n o m i cg r o 、n hi ne c o n o m i c sa n dm a n a g e m e n t ；m u 】t i 一。b j e c t j v el 。c a t i o n ，a s s j g n m e n t ，d e s i g na n dt r a f f i cp r o b l e m sl ne n g i n e e r n gd e s i g n ；m u l t i c a s ta n dg e o c a s tp r o b l e m sf o rd e s i g n i n gf r a m e w o r kt o p o l o g i c a lf r a m e w o r ki nn e t w o r ka n dc o m m u n i c a t i o nw i t ht h ed e v e l o p m e n to fr e s e a r c h e sa n da p p l i c a t i o n s ，s o m ec o m p l e xp r o b l e m si nr e a lw o r l dd e m a n de n h a n c i n gp e r f b 珊a n c eo fm o e a st h e r e f 。r et h ep r o b l e m ss u c ha sh o wt of a r t h e ri m p r o v ee a s ，a n di nm o p sh o wt oc o m b i n ee h e c t i v e l y1 0 c a ls e a r c hs t r a t e g i e sw i t ho p t i m i z a t i o nt e c h n i q u e sf o ru l t i m a t e l yi m p r o v i n gq u a l i t yo fs o l u t i o n ，s h o u l db ec e r l t i 曩1 i nt l i sw o r kt h er e s e a r c hi nt h i sw o r ke m e n d st e c h n i q u e su s e di nm o e a ss p e c 难c a l l yt h i st h e s i si sc o n c e n t r a t e do nt h ef 0 1 1 0 w i n ga r e a s1d i v e r s i t yo fp o p u l a t i o ni ng ah a sa ni m p o r t a mi m p a c to ng a sc o n v e 唱e n c ea n do t h e rp e b 珊a n c e ss o m ee v o l u t i o n a r yp r o p e n i e s ，d i v e r s i t ya n do t h e rf a c t o r s ，w h i c bi n f 】u e n c eg a sp e r f o 瑚a n c e s ，a r e 鲫叫y z e da ni m p o r t a n ta p p r o a c hf o ri m p r 。v i n ga ne a ，sp e r f o r m a n c e _ e ab a s e do nh y b r i do p t i m i z a t i o ns t r a t e g y ( h e a ) ，a n di t sf e a s i b i l i t ya n de f f 爸c t i v em e c h a n i s ma r ea n a l y z e da n dt h e ni nt h ec o n t e x to fv 曲i c l er o u t i n gp r o b l e m s ( v r p ) c o m b i n e dw i t hl o c a ls e a r c hs t r a t e g y 一2 o p t i m a 】a na l g 。r i t h mg a w i t h _ 2 一o p ti sp r o p o s e dt os 0 1 v ev r p a n dc h r o m o s o m er e p r e s e n t a t i o n ，g e n e t i co p e r a t o r sa r ed i s c u s s e de x p e r i m e n ts h o w sg a w i t h 一2 一o p ti sw e l lp e r f b r m e d皿2i nc o n t 抽u t i o nt os o l v i n gg o a lo fm o e a s ，w h e nc o n s t r u c 七i n gam o e 气s o m et e c h n i q u e sa n ds 仃a t e 画e s ，u s e di n 丘t n e s sa s s i g n m e n t ，s e l e c t i o na n dg e n e t i co p e r a t i o n s a r ea n a l y z e di nd e t a i l sb a s e do nt h em e c h a n i s mo fah y b r i dm o e a ( h m o e a ) a n di t sf r a m e ，ah m o e aw i t he n h a n c i n gc o n v e 唱e n c ep e i f o r m a n c e h j m o e 气1 8p r o p o s e d h 丁m o e ac o m b i n e sm o e a sw i t hac l a s s i c a l1 0 c a ls e a r c ht e c h n 岫u e ，h o o k ea n dj e e v e ss e a r c hm e t h o dt h ee x p e r i m e n td e m o n s t r a t e se a e c t i v e n e s s ，f e a s i b i l j ty c o n v e r g e n c ep e 怕r m a n c eo f h j m o e a3c r o s s o v e ri so fi m p o r t a n c et oe a s ，e s p e c i a l l yg a a l t h o u 曲t h e o r e t i c a l j yt h e r ei sn o ts y s t e m a t i ca n a i y s i sa b o u ti t si m p a c tt og a ，b u tf b mp r a c t i c a ia p p i i c a t i o n sa n de x p e r i e n c e s ，c r o s s o v e tp l a y sai m p o r t a n tr 0 1 ei ne v 0 1 u t i o n a r yp r o c e s so fg ar u n l l i n gs o m ep r o p e n i e sa b o u tc r o s s o v e ri ng aa r ed i s c u s s e db a s e do ne 丘 e c t i v ec r o s s o v e r si ng aa n ds p e c 访ct e c h n i q u e su s e di nt h en o t e dm o e a s ，a i la l g o r i t h mw i t hw e l lp e r f o r m a n c e s ，m o e a d c ( m u l t 沁 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 mb a s e do nd o u b l ec r o s s o v e r s ) i sp r o p o s e d w h e r et w o 虹n d so fc r o s s o v e r sa r eu s e de 矗e c t i v e l yi nam o e ai t sc o n v e r g e n c ep 刮陆r m a n c e ，s o l u t i o n sd i s t r i b u t i o na n dc o m p u t i n ge 每c i e n c ya r ea n a l y z e da n dt e s t e d ，a n db yp r o o f i ti sc o n v e 唱e n t4a c c o r d i n gt ot h ep r a c t i c a la c t i v i t i e si ne n g i n e e r i n go p t i m i z a t i o na n dm a n a g e m e n t ，m o e a sa r ew e l ls u i t a b j ef o rs 0 1 v i n ga n dr e s e a r c h i n gt h i sc i a s so fp r o b l e m sas i m p l ee n g i n e e r i n gd e s i g np r o b l e m ，c o m b i n e dw i t ht h ea l g o r i t h m ，m o e a d c ，p r o p o s e di nc h a p t e r4 ，i su s e dt od i s c u s st h ei m p o r t a n c ei np r a c t i c a la p p l i c a t i o n ，a j l dt h eu s e m li n s i 曲t sa b o u tt h er e la t i o n s h i pa m o n gd e c i s i o nv a r i a b l e sc o r e s p o n d i n gt ot h ep a r e t o o p t i m a ls o l u t i o n sa 盘e r w a r db a s e do nm o e a d c ，ac a s ea b o u tac l a s so fp o r t f 0 1 i os e l e c t i o np r o b l e m si sr e s e a r c h e dc o m p a r e dt oo t h e rr e l e v a n tr e s u l t si nl i t e r a t u r e ，t h i sm e t h o do 丘b r sm o r ec o m p r e h e n s i v ei n f o r m a t i o n ，m u c hm o r ef l e x i b i l i t yt oad e c i s i o n - m a k e ri nm a k i n gap o r t f 0 1 i os e l e c t i o n ，a j l dt h e r e f o r e ，t od e c i s i o n m a k e r so rm a n a g e r si ne n g i n e e r i n gd e s 远no p t i m i z a t i o na n dm a n a g e m e mp r o b l e m si np r a c t i c a l 叩p l i c a t i o n sk e y w o r d：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 ，e v o l u t i o n a r ya l g o t h m ，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 r n ，h y b r i de v o l u t i o n a r ya l g o r i t h mvy7 6 5 3 5 3擘短吠尊博士学位论文题目基于演化算法的多目标优化方法及其应用研究专业计算机应用技术研究方向算法设计与分析作者姓名汪祖柱届别2 0 0 5导师姓名程家兴职称教授完成时问2 0 0 5 年4 月教育部博士点基金项目( 2 0 0 4 0 3 0 5 7 0 0 2 ) 资助独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得塞邀盍堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意学位论文作者签名：i 雯翘杠c签字日期：年乒月谚日学位论文版权使用授权书本学位论文作者完全了解安徽大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借闽。本人授权安徽大学可以将学位论文的全部或部分内容编入有关数据库进行检索可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书)学位论文作者签名：厉互租立签字日期：沙町6 年么月力纩日学位论文作者毕业去向：安徽大学工作单位：安徽大学电子科学与技术学院通讯地址：合肥市肥西路3 号钠鲐每弘签字目期：钟年中月电话：0 5 5 1 5 1 0 7 3 2 4邮编：2 3 0 0 3 9名日第一章绪论现实中的很多问题通常出相互冲突的多个目标组成，单目标优化的最优解一般可明确定义，但却不能简单地定义多目标优化问题的最优解。因为多目标优化的结果并不是单个解，而是一组均衡解，即所谓的p a r e t o 最优解。8 0 年代中期人工智能的演化算法开始应用求解该问题。近十几年来涌现了许多多目标优化算法，一些已成功应用到工程实践中，因而形成了最近的一个热门研究领域。本章首先介绍多目标优化的基本概念，并回顾了求鳃多目标优化问题的古典方法及其局限性，然后概述利用演化算法的进化原理求解多目标优化问题领域的研究发展过程与一些待研究的问题，最后说明本论文的研究目的、内容及安排。1 1 多目标优化的基本概念在实际应用中，人们经常遇到在给定的区域上需要使多个目标均尽可能最佳的优化问题。例如在设计新产品时，既要考虑使产品具有较好的性能，又要考虑使其制造成本最低，同时还要考虑产品的可制造性、可靠性以及可维修性等性能，这些设计目标的改善可能相互抵触，譬如好的维修性会引起可靠性的降低，因此须在这些设计目标之间取一折中结果。还有如投资组合优化问题，一般希望所投入的资金量少，风险最少，且所获得的收益最大。这种多个的数值目标在给定的区域上的最优化问题一般就称之为多目标优化问题( m o p ，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 ) 。根据求解问题的背景不同，多目标有时也称为多准则、多属性或多指标，目标分为总目标和予目标，这里所谓的多目标优化是指对多个子目标同时实施最优化。通常在多目标优化领域广泛采用、被普遍接受的m o p 的定义如下 r i n l 9 9 2 ；d v l 2 0 0 0 ：定义1 1一般的m o p 问题的数学描述：m 抽f ( x ) = ( z ( x ) ，五( x ) ， ( x ) )j ，蓦( x ) 0 ，江1 ，2 ，m ，( 1 1 )基于演化算法的多目标优化方法及其应用研究m o p 的解是使目标函数f ( z ) 且( 五是目标函数空间，女2 1 ，七= 1 时问题对应单目标优化问题) 中的各个分量取得最小值的决策变量，其中x 是决策空间n 彤中的n 维决策变量，一个m o p 问题有珂个决策变量，m 个约束条件和个目标函数组成，目标函数可以是线性的或非线性的。m o p 的评价函数，：q 呻人( 人月。是目标函数空间) 将决策向量x 映射目标向量y = ，( x ) 。这种映射关系的例子如图1 1 所示( 其中”- 2 ，m = o ，女= 3 ) 。m o p 的本质在于大多数情况下各个子目标可能是相互冲突的，某予目标的改善可能引起其它子目标性能的降低，即同时使多个目标均达到最优解一般是不可能的，否则就不属于多目标优化研究的范畴。解决m o p 的最终目的只能是在各个子目标之间进行协调权衡和折衷处理，使各子目标函数均尽可能达到最优。因此m o p 的最优解与单目标优化问题的最优解有着本质的区别，为了正确求解m o p ，必须对其解的概念进行定义 h u y l 9 9 0 】。x 3图1 1 多目标优化的函数映射关系定义1 2 可行解集( f e a s i b l es 0 1 u t i o n ss e t ) 可行解集，定义为满足式子( 1 1 ) 的约束条件的决策向量的集合，即x f5 x q l g f ( x ) 0 ，f = l ，2 ，咒)( 1 ，2 )可行区域。所对应的目标空间可表示为：耳= f ( 爿- ) = y y = f ( x ) ，z ，( 1 3 )式( 1 3 ) 的物理意义是，对于可行解集x ，中的所有x ，经优化函数映射形成目标空间中的一个子空阳j ，该子空间的决策向量均属可行集。不失一般性，这里假设讨论的是极小化问题，对于极大化问题与上述定义类似。假设在上述产品例子中，如果在产品尺寸的约束条件晶( x ) 下有性能指标彳( x )和价格指标五( x ) ，优化的目的是要求在产品尺寸范围内，在最低成本下使产品性能最佳。如果只有一个解存在，则我们仅须求解单目标优化问题( s o p ，s i n g l e - o b j e c t i v eo p t i i i l i z a t i o np r o b l e m ) ，此时最优解对于所有指标均为最佳。但对m o p 来说各指标是相互冲突的，一个解不可能对所有指标同时达到最优，这就需要在各指标之间进行均衡处理。本例中产品性能与价格一般总是矛盾的，根据实际需求，一个适中的方案即中等的性能、中等的价格或许是一种均衡的结果。这种讨论有助于清楚地理解m o p 中最优解的概念。s o p 的可行解集完全根据单个的目标函数，( x ) 来确定优劣，即对某两个解d ，6 爿，( 可行域) ，总有，( 臼) ，( 6 ) 或者厂( 日) ，( 6 ) 成立，优化的目的在于找到使厂( x ) ( x 五，) 取极小值的解 c o h l 9 8 5 】。但对m o p 来说情况则不同，因为一般的j ，不是全序的( t o t a lo r d e r ) ，即为偏序( p a r t i a lo r d e r ) 【p a r l 8 9 6 。定义1 3优劣性( d o m i n a n c e i n f e r i o r i t v ) 。设，v 耳，称目标向量解“= ( 毪，“2 ，) 优于v = ( v 】，v 2 ，毪) ，如果v 涎 1 ，2 ，七) ，“v ， j f 1 ，2 ，女) ，“， v ，记为_ v ，记为“ _ v 。设x ，x 。，称工1 优于( d o m i n a t e ) 一2 或x 不劣( n o n d o m i n a t e d )于。，如果f ( 一1 ) f ( 一2 ) 。如图1 2 所示，其中1 、2 、3 、4 代表四个可行解，点4 表示的解优于点l 、2 、3 所表示的解，点2 、3 所表示的解均优于点1 表示的解；点2 与点3 所表示的解彼此不劣于或不优于对方。定义1 4p a r e t o 最优解( 非劣最优解，p a r e t o o p t i m a l ) 。决策变量工x ，成为x ，上的p a r e t o最优解，当且仅当不存在x 爿使得v = 厂( x ) = ( 一( x7 ) ，2 ( x ) 厶( x ) ) 优于( d o m i n a t e ) “= ，扛) = ( 一( x ) ，正“) 厶( x ) )由以上定义可知，p a r e t o 最优解的判断与所在集台的范围有关，一般情况下，基于演化算法的多目标优化方法及其应用研究t 、c 1 1 u i m 】1 i z e 图1 2m o p 目标空间中的解之间的关系则指的是整个决策空间的p a r e t o 最优解。定义1 5p a r e t o 最优解集( p a r e t 0 0 d t i m a ls c t ) 。对于给定的m o p 问题，p a r e t o 最优解集p 定义为：p + = 工x i 、| x x ，( x ) _ 厂( 工) )( 1 4 )定义1 6p a r e t o 前沿( p a r c t o f r o n t ) 对于给定的m o p 问题和p a r e t o 最优解集矿+ ，p a r e t o 前沿矽+ 定义为：+ = = 厂( x ) lz p )所以p a r e t o 前沿是导致于p a r e t o 最优解集在目标空间中的映像。如图1 3 所示，点a 、b 及c 是分布于p a r e t o 前沿的( 近似) p a r e t o 最优解，点d 、e 所在的灰色阴影区域为基于目标空间中的可行解区域，相对于点a 、b 、c ，d 和e 所表示的解为劣解( d d m i n a t e ds o l u t i o n ) 。同时点a 、b 及c 对应的p a r e t o前沿上的解应均为p a r e t o 最优解，对应的解集为p a r e t o 最优解集。另外，p a r e t o 最优解集还存在着全局最优和局部最优的概念，d e b 对此进行了相关定义f d e b l 9 9 8 1 。定义1 7 对于决策向量集4 五，( 1 ) 集合4 称为局部p a r e t o 最优集，当且仅当v 玎爿： j x 。：工 臼 i x 一日i i 占 i l ，( x ) 一f ( a ) i l o ，占 0图1 3 基于两目标的m o p 目标空间的p a r e t o 前沿及可行域( 2 ) 集合爿称为全局p a r e t o 最优集，当且仅当v 口一：t j x z 。：x _ d( 1 6 )全局和局部p a r e t o 最优概念的区分如图1 4 所示。图1 4 中点a 、b 、c 所在的曲线为全局p a r e t o 最优前沿，点d 所在的曲线段为局部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 最优集也可以看作是一个局部最优集。卵l l n l a ls e ta l l yp a ” oo p l a l5 nf 2 ( 1 m n l m i z c )图1 4 局部最优孵集和全局最优解集对上述有关定义可总结如下：( 1 ) 大多数情况下，类似于单目标优化的最优解在多目标优化问题中是不存基于演化算法的多目标优化方法及其应用研究在的，只存在p a r e t o 最优解。多目标优化问题的p a r e t o 最优解仅仅只是它的一个可以接受的非劣解或满意解，并且通常的多目标优化问题大多具有很多个p a r e t o最优解。( 2 ) 若一个多目标优化问题存在所谓的最优解，则该最优解必定是p a r e t o 最优解，并且p a r e t o 最优解也只由这些最优解组成，再不包含其它解。因此p a r e t o最优解是多目标优化问题的合理的解集合。( 3 ) 通常多目标优化问题的p a r c t o 最优解是一个集合。对于实际应用问题，必须根据对问题的了解程度和决策人员的个人偏好，从多目标优化问题的p a r e t o最优解中挑选出一个或多个解作为所求多目标优化问题的最优解。因此求解多目标优化问题的首要步骤和关键是求出所有的p a r e t o 最优解。多目标优化问题算法问题是实际中经常遇到的问题，因此人们对这个问题已经研究出了许多方法，如传统的线性加权和法、极大极小法、理想点法、逐次线性加权和法等。这些求解方法各有优点，当然也有各自应用的局限性。1 2 传统的多目标优化方法传统的多目标优化方法是将各子目标聚合成一个带权重系数的单目标函数，系数由决策者来确定，或者由优化方法来自动调整。为了获取近似p a r e t o 最优集，一些研究者采取不同的系数来实施动态优化。常见的方法有加权法【c o h l 9 78 、约束法【c o h l 9 7 8 、目标规划法【s t e l 9 8 6 和目标满意法【k o s l 9 8 4 ，下面简要介绍这些方法，这些方法也是经常使用的方法。1 2 1 加权法加权法是通过目标函数的线性聚合将m o p 转换成s o p ：m i n y = ，( x ) = m 1 z ( x ) + m 正( x ) + + 1 ，：( x )( 17 )5 r x ，o ，f = 1 ，2 ，露、o 为权值，应用时通常可正则化为w = 1 ，求解上述不同权值的优化问题后输出一组解。如果所有权重值取正值，这种方法可得到一些p a r e t o 最优解。假设一可行决6第一章绪论策向量口在给定权重组合下使，取极小值，但口不是p a r e t o 最优解；另有一个优于口的解向量6 ，使得对于f _ 1 ，2 ，女，( 6 ) sf ( d ) ，且至少存在一个- ，f厂( 6 ) 厂( 口) 。所以f ( 6 ) c ，则按照上述方法产生的个体的第一个子路径为( 2 ，4 ，6 ) ，同样按照这样的方法产生的子路径为( 1 ，l o ) 、( 9 ，8 ) 、( 5 ，3 ，7 ) ，所以最终产生的一个染色体个体为( 2 ，4 ，6 ) ， l ，1 0 ) ， 9 ，8 ) ， 5 ，3 ，7 ) ，在编程实现时，可以三维数组来表示群体中的染色体。另外，初始种群的个体数视问题规模来确定。在进行遗传操作过程中，结合了约束满足检验机制，即无论是交叉还是变异操作，每当新个体产生时，都要检验其是否满足有关约束，如容量约束，若满足，则保留，否则弃之。选择操作执行的是联赛选择( t o u m a m e ms e l ec t i o nm o d e l ) 和最佳个体保存( e l i t i s tm o d e l )相结合的方法 c w z l 9 9 6 】。( 3 )以2 一叩t 算法【l k 1 9 7 3 l 改善解在遗传算法过程中，以2 一o p t 算法对每一代中的当前解( 最好解) 继续进行改善。当前解包括若干子路径，对其中的每一条子路径应用2 一o p t 算法设当前解中的一条子路径为s r x ：葺，x 一一，x 。，各个需求点之间的直接有向路径称为边，如( x x ! ) 和( x ：，x ；) ，从第一条边开始，以遍历方式，对f 一，x 。) 帮( r ，一h ) 进行第二章演化算注2 一o p t 操作( 其中，i| ) 。在进行2 一o p t 操作时，如果新产生的路径满足约束且路径长度小于原来的长度，则将该路径作为当前路径长度，然后再进行其余遍历过程，直至该路径完成所有的2 一o p t 操作，此时对应当前路径长度的子路径将作为改善后的当前解的相应子路径。这样，当前解中的所有子路径均实施了2 一o p t 操作后，即可得到一个路径长度不大于原路径长度的当前解。对于一个由n个配送点构成的问题当中，对一个子路经执行次2 o p t 操作，至多需要的计算量为li ，因此对当前解的所有子路经都执行一次2 o p t 操作，则至多需要的计算量为口。混合优化算法( g a w i t h2 一o p t ) 的具体算法步骤见算法21 。算法2 1g a w i t h2 o 口t 的步骤f a 培。痈h m 2 1f h ep 1 o c e 幽1 e s 时g aw i l h2 一o p f s t e p l ：i = o ，p 。为空集( p i 用来保存每代中的最好解) 。s t e p 2 ：产生某代初始群体s i 。s t 印3 ：计算适应度，若满足优化准则，则转s t 印8 。s t e d 4 ：执行选择操作，i = i + 1 。s t e p 5 ：以一定的概率进行交叉操作和交异操作。s t e 口6 ：产生当前最好解。s t e p 7 ：对当前最好解进行2 一o p t 操作，将改善的当前解保存于p 。中；转s t e p3 。s t 印8 ：p 。中的最优个体即为问题的解或近似解。2 4 3 实验结果及分析实验所用的例子数据来自于著名的测试用例“枷，为了说明2 一o p t 算法对求解问题的影响，试验设计中对每一个例子均实施了两组算法，即遗传算法( g a )和结合2 一o p t 启发算法的遗传算法( g a w i t h 2 一o p t ) 。为便于比较，在每一个例子的两组试验中采取了相同的遗传算法参数。有关交叉操作和变异的三种操作的概率分别设置为：c r o s s o v e rr a t e ：o7 5 ，m u t a l i o nr a t e s ：( s w a p ：o0 5 ，i n s e 九i o n ：o1 5 ，i n v e r s i o n ：0 0 1 ) ；群体规模和演化代数分别可取为1 0 0 一2 0 0 和1 0 0 0 0 一3 0 0 0 0 ( 视问题规模来确定) 。试验以c 语言程序实现，其结果见表23 。我们讨论的g a 算基于演化算法的多目标优化方法及其应用研究法能够求解实例中的近似解，甚至最优解，如实例a 3 2 k 5 ，a 5 4 k 7 ，而对其它实例也求出了较好的近似解；从所求实例解的质量考虑，结合2 一o p t 算法的g a 算法大大提高了求解性能，所求的实例解均优于g a 算法所给出的解；对于规模较小的问题，能够求解最优解。算法在运行过程中，尽管运行的代数达到1 0 0 0 0 次以上，但通过以上的试验结果，说明文中讨论的算法的可行性。上述的仿真试验，验证了算法的有效性与可行性，说明了算法g aw i t h2 _ o p t 所具有的优化性能。该算法可以用来解决其它v 】婶问题，如变车辆数的冲问题和车辆容量约束不同的u 问题等。表23 以g a 和g a 嘶山2 一o p t 计算发现的最好解h l s t a n c e sn u m b 盯o f p o i r i t sp r c v i 0 1 l sb e s ts 0 1g ag a j t h 2 - 0 p la 3 2 k 53 27 8 47 8 47 9 4a 5 4 k 75 41 1 6 71 1 6 71 1 6 7a 6 0 k 96 01 3 5 41 3 6 01 3 5 4a 8 0 k 1 08 01 7 6 41 7 8 51 7 6 4表格说明：i n s t 强c e s ：实例名称；n u m b e ro f p o i n t s ：实例的需求点数；p r 吖i o u sb e s ts 0 1 ：对应实例目前最好解；g a ：本文的遗传算法所求最好解；g a 谢t h2 一o p t ：本文的g aw i t h2 一o p t 所求最好解2 5 小结本章在分析遗传算法的演化性能特征、遗传算法的多样性问题，以及影响遗传算法性能等的一些主要因素基础上，针对实际的心案例进行了试验分析和验证。在以演化算法求解优化问题时，应该针对具体的问题考虑所运用的问题解的表示和遗传算子，这也符合算法中的“没有免费的午餐( n o 仃e ej u n c h ) ”定理 w & m 1 9 9 7 。求解冲问题的过程中，本章考虑了个体染色体的表示，以及交叉算子和变异算子等演化策略的设计和应用。为提高演化过程的局部搜索能力，使用了局第二章演化算法部搜索算子2 一o p t ，据此本章提出了算法g a w i t h2 o p t ，从整体上提高算法的性能。基于此，以算法g a w j t h2 一o p t 求解了v 】 问题的一组案例，试验结果说明了算法g a 埘t h2 - o p t 所具有的良好的优化性能。第三章基于多目标优化的演化算法及其策略分析本章回顾了现有多目标演化算法的研究、发展现状。概述了目前一些典型的多目标演化算法设计中采用的算法技巧和策略问题。分析了多目标演化算法设计中所要解决的问题：适应度赋值方法、种群多样性维护问题、选择操作和精英策略的运用。指出了算法求解问题所面临的关键问题。基于单目标演化算法中运用混合策略的机制，分析了多目标混合演化算法的形成机制及其一般结构，提出了一种改善收敛性能的混合多目标演化算法，并以算例验证其可行性和有效性。3 1 基于演化算法的多目标优化求解多目标优化问题的一个根本目的是获得一组折衷解，即( 近似) p a r e t o最优解。在没有进一步的知识信息的前提条件下，在同一p a r e t o 前沿上不存在一个解比另一个解好，即位于同一p a r e t o 前沿上的解在某种意义上均是最优解。这是单目标优化与多目标优化之间的基本区别。尽管存在着这样的不同，人们还是要从众多的p a r e t o 最优解中最终确定个解来为他或她的实际应用服务。至于如何选择一个解或选择哪一个解应根据进一步的知识信息来作出决策。在多目标优化问题求解过程的某个阶段，决策者可以将自己的意愿或偏好加入到闯题求解的优化过程中，所以根据优化过程中使用用户偏好信息的阶段，有如下两种多目标优化问题求解方法。( 1 ) 基于偏好( p r e f e r e n c e ) 信息或先验( p 订o r i ) 信息：决策者将不同的目标函数聚合成一个数值代价函数，从而将多目标优化问题转换成单目标优化问题，如图3 ，1 所示。问题求解通过使用不同的代价函数丽不断重复迭代过程来设法发现一组折衷解。( 2 ) 基于理想( i d e a l ) 的多目标优化或后验( p o s t e r i o r i ) 信息：首先利用多目标优化方法求解问题以获得分布于大范围值域的多个折衷解或( 近似) 最优解，然后利用相关知识信息从中选择一个解。基于偏好( p r e f e r e n c e ) 信息或先验( p r i o r i ) 信息求解多目标优化问题属于经第_ 三章基于多目标优化的演化算法发其策略分析图3 1 两种多目标优化方法示例典的优化方法，其弊端在第一章的1 | 2 节中已经分析。演化算法很适合用于求解多目标优化问题，它不仅能够在一次的运行中获得多个解，更重要的是，它非常容易处理具有非连续的或非凸的p a r e t o 前沿的问题，因而极少受到p a r e t o 前沿的数学形态及其解析性能的影响。3 2 多目标演化算法概述早先1 9 6 7 年，r o s e n b e r g 在其博士学位论文中曾提到可用遗传搜索算法来求解多目标优化问题 r o s l 9 6 7 ，