（应用数学专业论文）多目标最优化进化算法.pdf

摘要 摘要 进化算法已成功应用于工程优化、经济管理、科学技术等诸多领域，进化算 法作为处理复杂的函数最优化、全局最优化和多目标最优化问题的一种有效算法， 正日益受到人们的重视。本文对带约束和不带约束的多目标最优化问题进行了研 究，提出两种新的进化算法，并给出了一种解点均匀性度量方法。 对复杂多目标最优化问题，往往存在有效界面上一部分区域的点容易求而另 些部分很难求出的情况。为求出有效界面上均匀分布的有效解，构造了动态的杂 交变异概率，自适应调节杂交、变异个体的数量和杂交变异算子，结合均匀设计 的带权重极大极小策略，得到了一种新的多目标进化算法。通过对已有测试函数 的数值实验和与m o e a d 和n s g a i i 算法数值结果的比较，表明了算法的有效 性。 为了减少进化算法的计算量和提高算法的搜索效率，通过把多目标优化问题 的决策空间分为若干个小区域，使进化算子在各个小区域中的个体之间进行运算， 不同小区域中的个体之间的信息交流通过产生的后代重新划分到这些小区域中进 行，提出了基于分区域搜索的多目标进化算法。由于算法使用分区域搜索，其在 每一代的计算复杂度比n s g a i i 和m s e a 都要小；而使用带权重的极大极小策 略作为适应值，有利于引导算法趋向在有效界面上均匀分布的解。同时提出了一 种处理约束的简单技术，使无约束多目标进化算法可直接用于求解约束多目标问 题。通过测试复杂的多目标优化问题，表明了算法的高效性。 此外，为了更好的度量解点均匀性问题，对已有的多目标进化算法的均匀性 度量做了相应的分析，特别是对高维多目标优化问题解的度量进行了讨论，提出 了一种基于角度和距离相结合的均匀性度量方法，该方法将目标空间中的点做球 面坐标变换求出其对应的角度，然后根据角度来找出分布在其周围不同象限的点， 并通过计算空间欧式距离来度量该点在空问中分布的均匀性。实验结果表明，该 方法能很好的评价目标函数解集的分布情况。 关键词：进化算法；多目标最优化；约束最优化；极大极小策略；均匀设计 广东t 业人学硕l j 学位论文 a b s t r a c t e v o l u t i o n a r ya l g o r i t h mh a s b e e n s u c c e s s f u l l ya p p l i e d i nm a n yf i e l d so f e n g i n e e r i n go p t i m i z a t i o n ，e c o n o m i c s ，m a n a g e m e n t ，s c i e n c e a n d t e c h n o l o g y e v o l u t i o n a r ya l g o r i t h m sa r eo n eo ft h ee f f e c t i v ea l g o r i t h m sf o rh a r do p t i m i z a t i o n ， g l o b a lo p t i m i z a t i o na n dm u l t i o b je c t i v eo p t i m i z a t i o np r o b l e m s ，w h i c ha r ea t t r a c t e d i n c r e a s i n ga t t e n t i o n t h i sp a p e rs t u d i e se v o l u t i o n a r ya l g o r i t h m s f o rc o n s t r a i n e d m u l t i - o b je c t i v eo p t i m i z a t i o na n du n c o n s t r a i n e dm u l t i o b je c t i v eo p t i m i z a t i o n ，p u t f o r w a r dt w on e we v o l u t i o n a r ya l g o r i t h m sa n dp r o p o s e sau n if o r m i t ym e a s u r e m e n tf o r s o l u t i o n s t or e d u c et h ec o m p u t a t i o nc o m p l e x i t yo fe v o l u t i o n a r ya l g o r i t h ma n di m p r o v e t h ee f f i c i e n c yo fs e a r c ha m o u n to fc a l c u l a t i o n ，b yd i v i d i n gt h em u l t i o b j e c t i v e o p t i m i z a t i o no ft h ed e c i s i o ns p a c ei n t os e v e r a ls m a l lr e g i o n s ，t h i sp a p e rp r o p o s e s m u l t i - o b je c t i v eo p t i m i z a t i o na l g o r i t h mb a s e do ns u b r e g i o n a ls e a r c h ，w h i c hm a k e s i n d i v i d u a l si ns a m er e g i o no p e r a t ee a c ho t h e rb ye v o l u t i o n a r yo p e r a t o ra n dt h e i n f o r m a t i o nb e t w e e nt h ei n d i v i d u a l so fd i f f e r e n tr e g i o n se x c h a n g et h r o u g ht h e i r o f f s p r i n gr e d i v i d e di n t or e g i o n sa g a i n s i n c et h ep r o p o s e da l g o r i t h mu t i l i z e st h e s u b - r e g i o n a ls e a r c h ，t h ec o m p u t a t i o n a lc o m p l e x i t ya te a c hg e n e r a t i o ni sl o w e rt h a n t h en s g a i ia n dm s e a t h ep r o p o s e da l g o r i t h mm a k e su s eo ft h em a x - m i ns t r a t e g y w i t hd e t e r m i n e d w e i g h t a sf i t n e s s f u n c t i o n s ，w h i c hm a k ei ta p p r o a c he v e n l y d i s t r i b u t e ds o l u t i o ni np a r e t of r o n t t h i sp a p e rp r e s e n t sak i n do fe a s yt e c h n o l o g y d e a l i n gw i t ht h ec o n s t r a i n t ，w h i c hm a k e st h ep r o p o s e da l g o r i t h ms o l v e du n c o n s t r a i n e d m u l t i o b j e c t i v ep r o b l e m sc a na l s ob e u s e dt o s o l v ec o n s t r a i n e dm u l t i o b j e c t i v e p r o b l e m s t h en u m e r i c a lr e s u l t s ，w i t ht h ec o m p l e xt e s t i n gi n s t a n c e s ，s h o wt h eh i g h e f f e c t i v e l yo ft h ea l g o r i t h m i nc o m p l i c a t 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 n ，i to f t e nh a p p e n st h a tp o i n t si np a r t r e g i o no fp a r e t of r o n ta r ee a s yt og e t ，b u ti no t h e r sa r ed i f f i c u l t t oo b t a i ne v e n l y d is t r i b u t e d p a r e t o o p t i m a ls o l u t i o n ，w e c o n s t r u c t d y n a m i c a l c r o s s o v e ra n dm u t a t i o n a b s t r a c t p r o b a b i l i t yw h i c hc a ns e l f - a d a p t i v e l ya d j u s tt h en u m b e ro fi n d i v i d u a l se n g a g e di n c r o s s o v e ra n dm u t a t i o n ，c o m b i n ew i t ht h ef i t n e s sf u n c t i o nc o n s t r u c t e db yw e i g h t e d m i n m a xs t r a t e g yi nw h i c ht h ew e i g h ti su n if o r m l yd e s i g n e d ，t op r e s e n tan e w m u l t i o b je c t i v ee v o l u t i o n a r ya l g o r i t h m t oe v a l u a t et h ep e r f o r m a n c eo f o u ra l g o r i t h m ， w ec o m p a r et h en u m e r i c a lr e s u l t so fo u ra l g o r i t h mw i t ht h em o e a d d ea n d n s g a i i d e ，t h ec o m p a r i s o ns h o w st h a to u ra l g o r i t h mi sv e r ye f f i c i e n t f u r t h e r ，i no r d e rt om e a s u r et h eu n i f o r m i t yo fs o l u t i o n s ，t h i sp a p e rh a sm a d ea n c o r r e s p o n d i n ga n a l y s i s o nt h ee x i s t 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 ya l g o r i t h m ， e s p e c i a l l y t h eh i g hd i m e n s i o n a lm u l t i - o b j e c t i v eo p t i m i z a t i o ns o u l u t i o n sh a sb e e n r e v i e w e d ，p r o p o s e sam o e au n i f o r m i t ym e a s u r e m e n tb a s e do ng e n e r a l i z e ds p h e r i c a l t r a n s f o r m a t i o n ，w h i c hm a p p e dt h es p a c ep o i n t so n t oas p h e r i c a ls p a c eb yt r a n s f o r m i n g t h ec o o r d i n a t et og e tt h ec o r r e s p o n d i n gp o l a ra n g l e ，a n dt h e nf i n do u tt h ep o i n t s d i s t r i b u t i n g i nd i f f e r e n tq u a d r a n ta r o u n da c c o r d i n gt ot h e p o l a ra n g l e ，f i n a l l y m e a s u r et h eu n i f o r m i t yo ft h ep o i n t si nt h es p a c ed i s t r i b u t i o nb yc a l c u l a t i n gt h es p a c e e u c l i d e a nd i s t a n c e t h ee x p e r i m e n t ss h o wt h a tt h i sa l g o r i t h mc a nw e l le v a l u a t et h e d i s t r i b u t i n go ft h ep a r e t os e t k e yw o r d s ：e v o l u t i o n a r ya l g o r i t h m ；m u l t i o b je c t i v eo p t i m i z a t i o n ；c o n s t r a i n e d o p t i m i z a t i o n ；m a x m i ns t r a t e g y ；u n i f o r md e s i g n 广东t 业人学彤ji j 学化论文 独立性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导小进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 指导教师签字：钗1 砥鹣 论文作者签字：摭l 亏 妒7 年 l f 月引日 第一章绪论 第一章绪论弟一早珀t 匕 1 1 进化计算的产生与发展 达尔文的进化学说揭示了物种的多样化是自然选择和进化的结果，现代分子 生物学的发展也为这一学说提供了直接的证据，正是在自然界的启示下，一些学 者希望通过模拟生物界的生物进化过程来解决实际中的某些复杂的问题，从而导 致了进化算法的产生。 进化计算的研究起源于2 0 世纪5 0 年代末，成熟于8 0 年代，它包含了三大主 流板块：遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 、进化策略( e v o l u t i o ns t r a t e g y ， 简称e s ) 和进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，简称e p ) ，这三中算法分别 从不同的层面和角度来模拟生物的进化规律，从而达到解决实际问题的目的。 遗传算法是模拟达尔文的遗传和优胜劣汰的生物进化过程的计算模型，是一 种通过模拟自然进化过程搜索最优解的方法。遗传算法一词最先是由b a g l e y 提出 的，它在1 9 6 7 年发表的关于遗传算法应用方面的第一篇论文中首次使用了遗传算 法这个名称【l 】，直到1 9 7 5 年，美国m i c h i g a n 大学的j h o n h h o l l a n d 在总结了自 己的研究成果后发表了在遗传算法领域具有里程碑意义的著作a d a p t a t i o ni n n a t u r a la n da r t i f i c i a ls y s t e m s ) ) 【z 】，遗传算法这一名称才逐渐被人们所知。h o l l a n d 不仅展示将自然界的进化过程应用到人工系统，而且提出了遗传算法的基本理论： 模式定理( s c h e m at h e o r e m ) 和隐含并行性( i m p l i c i tp a r a l l e l i s m ) 原理，为遗传 算法的发展奠定了理论基础。 在遗传算法的发展过程中，1 9 7 5 年，d ej o n g 在其博士论文“a na n a l y s i so f t h e b e h a v i o ro fac l a s so fg e n e t i ca d a p t i v es y s t e m s 3 】”进行了大量的函数优化方面的 数值试验，并对遗传算法的性能做了大量的分析，给出了衡量遗传算法性能的在 线指标和离线指标。1 9 8 3 年，h o l l a n d 的学生g o l d b e r g 将遗传算法成功应用到管 道系统的优化和机器学习问题【4 1 ，引起人们对遗传算法的广泛关注。1 9 8 9 年， g o l d b e r g 出版了g e n e t i ca l g o r i t h m s i n s e a r c h ，o p t i m i z a t i o n a n dm a c h i n e l e a r n i n g ) ) 【4 】这一专著，全面系统的介绍了遗传算法的原理及其应用，奠定了遗传 广东t 业人学硕i j 学位论文 算法的科学基础。1 9 9 1 年，d a v i s 编辑出版了h a n d b o o ko f g e n e t i ca l g o r i t h m s ) ) 1 5 j 一书，介绍了遗传算法原理，给出了遗传算法在科学计算、工程技术及社会经 济方面的大量应用实例，对有效应用遗传算法起到重要的指导作用。为了克服遗 传算法在表达方面的局限性，k o z a 将遗传算法应用于计算机程序的优化设计及自 动生成，提出了遗传规划( g e n e t i cp r o g r a m m i n g ，简称g p ) 这一新概念。1 9 9 2 年，k o z a 出版了专著g e n e t i cp r o g r a m m i n g ：o nt h ep r o g r a m m i n go fc o m p u t e r sb y m e a n so fn a t u r a ls e l e c t i o n ) ) 6 1 ，该书全面介绍了遗传规划的原理及应用实例。同 年，他又出版了专著( ( g e n e t i cp r o g r a m m i n gi i ：a u t o m a t i cd i s c o v e r yo fr e u s a b l e p r o g r a m s ) ) 7 1 ，进一步阐明遗传规划的实质，其被视为遗传算法的奠基人。 进化策略是由r e c h e n b e r gi 和s c h w e f e lh p t8 】在1 9 6 5 年独立提出的。当时他 们在柏林工业大学进行风洞实验，由于设计描述物体形状的参数难以用传统的数 学方法进行优化，因此他们尝试用生物变异的方式来随机的改变参数值，最终获 得了较好的结果。早期进化策略的种群中只包含一个个体，且仅仅使用变异操作。 后来s c h w e f e lh 一p 在文献f8 ，9 】中系统推广了r e c e n b e r g 的原始进化策略，建立了 更先进的进化策略。 进化规划是由f o g e l l l 0 1 在2 0 世纪6 0 年代提出的。f o g e l 将仿真进化方法用于 由相互竞争的算法所构成的种群，在一系列研究中探索了进化规划的可能性，目 的是发展人工智能。从1 9 7 6 年到1 9 8 5 年，在进化规划方面的研究仅有少量的工 作。l9 8 5 年以来，进化规划方向也成了研究热点，它在相当广泛领域都有潜在应 用。最近该项技术被用到许多组合优化问题上。与使用有限状态机不同，所使用 的表示依赖于所考虑的问题，以及构造用与维持个父母体与后代之间密切联系的 变异运算。此程序已经应用到路径规划问题、神经网络设计问题、自动控制问题、 博弈问题、一般函数优化问题。 1 2 进化算法的研究意义 随着科技的发展，人类可以利用计算机来解决许多过去无法想象的问题，2 1 世纪，人类更加依赖计算机来解决实际问题，可是很多复杂的实际问题利用经典 的数学方法无法求解，例如图像识别、人工智能模拟、非线性优化等等，特别是 高度非线性的优化问题，用常规的方法无法得到令人满意的结果，许多学者认识 第一章绪论 到要解决这类问题，需要一种具有自组织、自适应能力的大规模并行算法。自然 界中的生物与周围的生存环境相互协调，表现出了复杂的行为。生物进化从简单 到复杂，从低等到高等，呈现出一种进步的发展趋势。这种模拟生物或自然现象 就成为了一种研究方向，并为计算机解决上述复杂问题带来了希望。 从2 0 世纪8 0 年代以来，有关学者提出了不少多目标进化算法 2 1 1 ，在8 0 年代中期开始解决多目标问题，一些已经成功应用到工程实践，形成了一个热门 的研究领域。用进化算法求解函数最优化问题之所以受到广泛的关注，是因为该 算法具有内在的并行性、广泛的通用性、高度的稳健性和简捷性以及全局性。 1 3 进化计算描述 生物的进化过程包含繁殖、变异、竞争、选择这四个要素，模拟生物进化的 过程，进化算法包含新个体的产生和选择，分别表现在个体的杂交、变异、适应 值估计和选择，下面从这几个方面对已有的进化算法进行说明。 1 3 1 杂交算子的设计 1 3 1 1 算术杂交【2 2 - 2 3 】 假设杂交的父代为x = ( x 。，x ：，x 。) ，y = ( 乃，y ：，y 。) ，产生的子代为 u = ( u i ，“2 ，u 。) ，= ( k ，1 ，2 ，。) ， 有： u f = a i x i + ( 1 - a f ) y f ，坼= a i y f + ( 1 - a f ) x f ， i = 1 ，2 ，刀，其中a i 为【o ，1 】内的随机数，且a i , n ，随机独立产生。由此可知算术杂 交的子代甜，v 位于父代x ，y 形成的超立方体内。 1 3 1 2 单纯形杂交 为了提高进化算法的局部搜索能力，r e n d e r s 和b e r s i n i t 2 4 】把单纯形算法思想 用于构造杂交算子。设有七( 尼 2 ) 个父体x 1 ，x 2 , o o ，x 参与杂交，选出最好的个体x 6 和最差的个体x ”，计算除个体工”以外的父体的质心x = 一量。芒三， 其中 p = 协1 ，x 2 ，x ；计算最差点的反射点j ”= x + o 。一x ”) ，然后比较函数值f ( x 6 ) 、 广东t 业人学硕i 学位论文 f ( x ”) 和f ( x ”) ，最后可确定杂交产生的子代。详见文献 2 2 】。 j o h ny e n 和b o g j ul e e l 2 5 1 推广了上述杂交算子，在单纯形杂交算子中进入随 机变量，令x ”= x + 口( 工。一x ”) ，其中口为 o ，2 】上服从三角分布的随机变量，如果 f ( x “) 比f ( x ”) 差，则令x ”= x 一( z 一x ”) ，其中是。，上的服从三角分布的随 机变量。 1 3 1 3 启发式杂交 借鉴“爬山 的思想， w r i g h t t 2 6 】提出了启发式的杂交方式。假定杂交的父 体为z i ，石7 ，并假定x 的适应值较好，令杂交后的个体为x 。= 工7 + a ( x 一x ) ，其中 口是闭区间【o ，l 】上的随机数。在算法初期，该算法能朝着适应值好的方向趋近， 在后期，算法具有一定的局部搜索作用。 1 3 2 变异算子的设计 1 3 2 1 高斯变异 高斯变异算子比较常用，最初在进化策略【8 ，9 1 中使用。假定进行变异的个体为 x = ( 工：，x ：i ，x ：) ，确定刀个服从n ( o ，盯，) ( = 1 , 2 ，疗) 的随机变量，令变异后的子代 为x “= ( 石? ，x ；，工：) 的分量x ；= z ；+ ( o ，仃_ ，) ，( _ ，= l ，2 ，”) ，e h 正态分布的特性可知 高斯变异只要是对变异个体的附近区域进行重点搜索。 1 3 2 2 均匀变异1 2 7 1 假定变异的个体为x = ( x l ，x ：i ，x ：) ，随机选择一个分量( 1 歹 刀) 进行变异， 且分量x ；的上限为a j 下限为b i ，令该变量变异后的值为x ；= 口，+ 口( 一口，) ，其中 口是【o ，l 】上服从均匀分布的随机数，则变异后的子代x 。= ( x ，x ：，矗i ) 。 1 3 2 3 非均匀变异【2 7 2 9 1 非均匀变异是对均匀变异算子的改进，均匀变异的某个分量是在确定范围内 均匀随机取值，无法在局部范围内重点搜索，为了改进这一性能，m i c h a l e w i e zz 把变异的分量作了随机扰动，在进化算法的初期该扰动变化范围较大，随着进化 4 第一章绪论 代数的增加扰动变化范围逐渐减小。在上述均匀变异中，杉为 ，f x + a ( t ，x t 日 ) ， i f r 0 5 x j2 1 x ，一a ( t ，b k x ) ， i fr o 5 其中，为【o ，1 】上服从均匀分布的随机数，这里t 为进化的当前代数，函数( f ，y ) 为 区域【o ，y 】内的一个值，且随着f 的增大，h ( t ，j ，) 波动的趋近于o m i c h a l e w i e z ，l o g a m 和s w a m i n a t h a n 在文献【2 7 1 中使用了函数( f ，y ) = y a ( 1 一去) 声，其中口为闭区间 o ，1 】上 的随机数，r 为最大进化代数，为一个确定非均匀性程度的参数。当工：取其定 义区间的左右端点时，称其变异为边界变异，边界变异是均匀变异的一种特殊情 溯。 1 3 2 4 自适应性变异 潘正君、康立山等1 3 0 1 把模拟退火的思想引入到构造变异算子中，在非均匀性 变异算子的基础上提出了自适应性变异算子，假定工7 = ( x ：，工：i 9o ，x ：) 为解空间的一 个个体，适应值为f ( x ) ，f 为所求问题的最大适应值的一个粗略上限或取当前群 体中的最大适应值，定义丁：1 一婴为该个体的变异温度。个体x ，的变异方式类 p 似非均匀变异算子，只是把其中的进化代数t 改为r ，即：a ( t ，y ) = y ( 1 一，p ) 。 自适应性变异算子对适应值较好的解在其较小的范围内搜索，而对较差的解 搜索领域较大。详见文献 3 0 】。 1 3 3 个体的选择策略 进化算法的适应度赋值策略分成三种：基于集合的策略、基于准则的策略、 和基于p a r e t o 优胜关系的策略。它们的解释说明如图1 1 所示。 广东t 业入学硕f j 学位论文 a )b )c ) 图1 1m o e a s 的三种适应度赋值策略【3 1 】 f i g u r e1 1 t h r e ea s s i g n m e n ts t r a t e g yo fm o e a sf i t n e s sv a l u e s 另外为了保持种群在进化过程中的多样性，在选择的过程中结合了种群的密 度信息，当个体在其邻居范围内所占的密度越高，被选择复制的机会越小。进 化算法中使用的多样性保持策略可根据统计概率密度函数的估计方法加以分 类成，内核方法、最近领域方法和矩形图方法( 如图1 2 所示) ，在这些策略 中通过设置排挤因子、小生境参数等等来保持种群的多样性。内核方法是通过 计算每个个体计算至其他个体f 的距离d ；，通过内核函数k 的映射后求和计算 出罗k ( a ，) 值。用该累加值代表个体的密度估计。在进化计算中适应度共享方 法就是此类方法的一种最典型的体现；最近领域方法是用给定点到其临近点的 最近距离来估计其在领域内的密度，通常估计器作为距离的一种逆转函数；矩 形图方法采用一个网格来定义空间上的领居关系，个体的密度是通过统计同一 个网格内的个体数目来确定的，网格可以是固定的，也可根据当前种群进行自 适应调整，详见文献 3 1 】。 内核方法最近邻域方法矩阵图方法 图1 2 多样性保持策略分类【3 1 】 f i g u r el 一2t h ec l a s s i f i c a t i o no fd i v e r s i t ym a i n t e n a n c es t r a t e g y 6 第一章绪论 1 4 本论文的研究重点和章节安排 本文共分为三章，用进化算法研究了单目标最优化、多目标最优化、带约束 的单目标最优化、约束多目标最优化、二层多目标最优化，提出了新算法。具体 安排如下： 第一章介绍了进化算法的意义、产生和发展现状，进化算法常用的进化算子 的设计，评述了在进化算法中起重要作用的个体的选择策略，并给出了具体的图 示说明。 第二章通过均匀设计权重、自适应调节杂交、变异概率的机制和结合模拟退 火思想，提出了解决全局最优化问题的新的进化算法，并用该算法对大量的测试 函数进行了数值仿真和同m o e a d d e 、n s g a i i d e 算法进行了比较。 第三章通过把多目标优化问题的决策空间分为若干个小区域来减少进化算法 的计算量和提高算法的搜索效率，提出了基于分区域搜索的多目标进化算法。并 对复杂的带约束和不带约束的多目标优化问题进行了仿真。 第四章对已有的均匀性度量做了分析提出了一种基于角度和距离相结合的均 匀性度量方法，并对三组不同的解点进行了度量。 最后，对全文的工作进行了总结。 7 广东t 业人学硕l j 学f 证论文 第二章基于极大极小策略和动态杂交变异概率的多目 2 。1 引言 标进化算法 进化算法处理多目标最优化的有效性，越来越受到有关学者的重视。文献 【“，1 2 基于带权重极大极小的策略提出了能有效保持种群多样性的多目标进化 算法，在文献 1 4 ，1 6 】中，把目标函数的权重和作为适应值函数的进化算法也受到 了关注。上述这些算法，包括最近出现的著名的多目标进化算法【1 3 , 1 5 , 1 7 , 1 8 】，都是以 固定的概率进行杂交、变异运算，这对复杂的多目标最优化问题( 如：有效界面 上一部分区域的点对应的有效解很难得到，而有些有效解和容易求出) 算法的搜 索效率就不会很高。这时在难得到有效解的区域增加杂交、变异的概率，在易得 到有效解的区域减少相应的概率，就可望提高算法的搜索能力。 本文就是基于这个思想，提出了基于动态的杂交、变异概率的多目标进化算 法，在算法中建议了一种自适应调节杂交、变异概率的机制和带有模拟退火思想 的杂交、变异算子；提出了一种三个目标的确定适应值函数权重的选取方式，这 样的权重取值有利于得到在有效界面上分布均匀的有效解。 2 2 研究问题及相关结论 在科学技术领域中，常常会遇到大量的多目标最优化问题，这类问题的数学 模型为： m i n m ) = ( z ( x ) ，厶( 砒，l ( 工) ) ( 2 1 ) 【 j x r ” 其中，x 是决策变量，f ( x ) 是目标向量，且各个目标通常是相互冲突的，x 是 r ”中的超矩形域，表示决策空问。与只有一个目标函数的单目标规划不同，多目 第- 二章桀f 极人极小策略车n 动态杂交变异概率的多u 标进化算泫 标最优化通常考虑使它的向量目标函数在某种意义下为非劣的有效解或弱有效 解。 定义1 设i x ，若不jx x ，使得对vf 有z ( 石) z ( i ) ，且了i 。，使 ( 工) o ，( f = 1 ，2 ，k ) 关于g ，为严格增函数，同理可得e ( f ，柳互e ( g ，的， e 。( ，x ) e 。( g ，x ) 。故有：e ( g ，x ) = e u ，e 。( g ，x ) = e 。( 厂，x ) 。 设( 2 1 ) 式的带权极大极小化问题为： 卿燃石( x ) j ( 2 2 ) 我们有如下定理： 定理4 设x r ”，厂：x 专r m ，( j ) = ( z ( x ) ，厶( x ) ，厶( x ) ) ，e ( f ，x ) 、 e 。( ，x ) 分别表示( 2 1 ) 式的有效解集和弱有效解集。若isx 和权重 0 ， i j f = l ，2 ，肌) 使得w l z ( i ) = w 2 ( i ) = = w m 厶( 孑) ，则有： 1 i e 。( 厂，x ) 的充要条件是卿懋i m 石( x ) 。懋i m z ( i ) ) j e l s l s 2 若舅e ( f ，x ) ，则m i n = ) ；当| z x ，舅i 使得, m a x w j f ( x ) m a x w , f , ( y ) - j j i m 卿燃 w z ( z ) ) 2 恶蛩 嵋，( i ) 时，必有厂( z ) = 厂( 孑) 。 证明：( 1 ) 必要性( 反证法) ：假设3 x ，x ，使得燃 w f ：o - ) 器娶 z ( i ) 。 有已知条件得出罂x z ( 墨) ) z ( 孑) ，( i = 1 , 2 ，m ) ，根据假设条件知对一切的f 都有罂婪 ，( 五) 3 ) 维目标空间： 1 当目标空间为二维的情形时，如图2 1 所示，过原点作n 条射线，把圆心 在原点单位圆周在第一象限的部分均分为+ 1 份，其中记第i 条射线与单位元的 交点为4 ( c 。s q ，s i n 谚) ( b2 夏寿，f = 1 ，2 ，) 。令w i - - ( 嵋，以) ，其中 一2 磊，以= 五，汪l 2 ，代入( 2 5 ) 式可得到一组适应值函数。 图2 1 当m = 2 时权重的选取方法 f i g u r e2 一lt h ec h o o s i n go ft h ew e i g h t sw h e nm = 2 2 当目标空间为三维的情形时，把圆心位于原点的单位球面在第一卦限的部 分，用如下办法找到均匀分布的个点：用k 个顶点在原点顶角分别为 广东t 业人学顺卜孚化论义 b ，2 瓦老，f = 1 ，2 ，k 的圆锥与球面交出k 条曲线，在每条曲线上求出相邻两 点弧长为1 i 鲁的所有点，如下图2 2 所示弧b c 上第，个点4 的坐标为 2 ( k + 1 1 。 ( s i n 皖c o s 纺，s i n o ks i n 伤，c o s o k ) ， 其中纺。i 靠， 相应的权重向量为 w l = ( 叫，嵋，嵋) ，i = 1 , 2 ，。 以= 壶o s c仇 图2 - 2 当m = 3 时权重的选取方法 f i g u r e2 - 2t h ec h o o s i n go ft h ew e i g h t sw h e nm = 3 ( 2 6 ) 3 当目标空间为聊( 所 3 ) 维的情形时，令盯= 芴丢万，其中k 由种群的规模 和维数m 决定，对于设计的任一权重w ( f = 1 , 2 9 q 9 n ) ，其对应的角度 秒7 = ( q ，色妒，气“一。) ，且有： 1 2 一纺 一吩画画 一傩 一口一，i 一只 一晚 一n n 一- 一 一一 = = 幔 第：章堆_ i 二 及人极小策略和动态杂交变异概半的多t 1 标进化算法 由此可计算出相应的权重w =