（计算机应用技术专业论文）多目标优化的遗传算法研究.pdf

摘要 摘要 科学研究和工程实践中许多优化问题都可归结为一个多目标优化问题，多目标优化作为 最优化领域的一个重要的研究方向有其广泛的应用领域，研究求解其有效算法具有重大的科 学意义和应用价值。 本文的主要工作如下： 目标加权遗传算法求解多目标优化问题，是把所有目标聚合成一个带参数的 目标函数。在多目标优化的评价指标体系中，属性权重的确定具有举足轻重的地 位。因此如何科学、合理地确定属性权重，关系到多目标优化结果的可靠性与正 确性。首先着重介绍了加权求和遗传算法，通过结合均匀设计创建初始种群，并 对其各目标函数规范化，建立新的适应度函数，提出了一种动态分配权值的方案， 设计了一个基于新的权重分配策略的多目标遗传算法( n w m o g a ) 求解多目标优 化问题。 其次，遗传算法可以同时进行多点搜索，但是这样搜索到的非支配解有时分 布是不均匀的。为了搜索到分布比较均匀的非支配解，结合均匀设计的思想，设 计了一个基于均匀设计方法的多目标优化遗传算法( b u m o g a ) ，该算法能够找到 非支配前沿的稀疏区域，对稀疏区域进行搜索，使搜索到的非支配解分布更加均 匀，引入了均匀杂交算子和单点复合交叉算子两种杂交算子，弥补了模拟二进制 交叉算子搜索能力弱的缺陷，并给出了算法的收敛性证明，通过仿真验证了该算 法的有效性。 关键词：多目标优化遗传算法均匀设计加权求和 a b s t r a c t a b s t r a c t m a n yo p t i m i z a t i o np r o b l e m si ns c i e n t i f i cr e s e a r c ha n de n g i n e e r i n gp r a c t i c ec a n b em o d e l e da 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 m s t h u s ，m u l t i o b j e c t i v e o p t i m i z a t i o np r o b l e m s ( m o p ) h a v eaw i d er a n g eo fa p p l i c a t i o n s ，a n dd e s i g n i n g e f f e c t i v ea l g o r i t h m sf o rt h e mi so fn o to n l yt h eg r e a ti m p o r t a n c ei ns c i e n t i f i cr e s e a r c h , b u ta l s ot h eg r e a tv a l u ei na p p l i c a t i o n s t h em a i nw o r k si nt h i st h e s i sa r ea sf o l l o w s ： w e i g h t e dg e n e t i ca l g o r i t h m sf o rm u l t io 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 sa t t e m p t t oa g g r e g a t ea l lt h eo b j e c t i v e si n t oo n eo b j e c t i v ef u n c t i o nw i t hp a r a m e t e r s i th a sg r e a t i m p o r t a n c et od e t e r m i n et h ew e i g h t si nt h em u l t i o b j e c t i v eo p t i m i z a t i o ne v a l u a t i o n i n d e xs y s t e m s ot h er e l i a b i l i t ya n dv a l i d i t yo ft h em u l t i - o b j e c t i v eo p t i m i z a t i o nr e s u l t s a r er e l a t e dt ow h e t h e rt h ea t t r i b u t ew e i g h t sa r ed e t e r m i n e d s c i e n t i f i c a l l ya n d r e a s o n a b l y f i r s t ，f o c u s e so nt h ew e i g h t e ds l a mg e n e t i ca l g o r i t h m ，t h ei n i t i a lp o p u l a t i o n a r eg e n e r a t e db yau n i f o r md e s i g nm e t h o d , a n da f t e rt h eo b j e c t i v e sa r en o r m a l i z e d ，t h e f i t n e s sf u n c t i o ni sd e f i n e db yw e i g h t e ds u mo ft h en o r m a l i z e do b j e c t i v e s ，w h e r et h e w e i g h t sa r ed y n a m i c a l l yd e f i n e d b a s e do nt h e s e ，an e wm u l t i - o b j e c t i v eg e n e t i c a l g o r i t h mc a l l e dn w m o g a i sp r o p o s e df o rm 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 s e c o n d ，g e n e t i ca l g o r i t h m sc a l lc o n d u c ts e v e r a lr e s e a r c h e ss i m u l t a n e o u s l y ，b u t t h es e a r c h e sf o rt h en o n - d o m i n a t e ds o l u t i o na r en o ta l w a y su n i f o r m t os e a r c hf o r m o r eu n i f o r md i s t r i b u t i o no fn o n - d o m i n a t e ds o l u t i o n s ，an e wg e n e t i ca l g o r i t h mf o r 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 sb a s e do nu n i f o r md e s i g nc a l l e db u m o g ai s p r o p o s e dc o m b i n e dw i t hu n i f o r md e s i g n t h ea l g o r i t h mc a nf m dt h es p a r s ea r e a so f n o n - d o m i n a t e df r o n t i e r , a n d e x p l o r e t h e s p a r s e a r e aw h i c hc a nm a k et h e n o n - d o m i n a t e ds o l u t i o n sm o r eu n i f o r m t h ei n t r o d u c t i o n so fu n i f o r mc r o s s o v e r o p e r a t o ra n ds i n g l ep o i n tc r o s s o v e rc o m p l e xo p e r a t o rm a k eu pt h ed e f e c t so fw e a k s e a r c hc a p a b i l i t i e so fs i m u l a t e db i n a r yc r o s s o v e ro p e r a t o r t h eg l o b a lc o n v e r g e n c eo f t h ea l g o r i t h mi sp r o v e d ，a n de f f e c t i v e n e s so ft h ea l g o r i t h mi sd e m o n s t r a t e db yt h e s i m u l a t i o n s k e yw o r 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 ng e n e t i ca l g o r i t h mu n i f o r md e s i g n w e i g h t e ds u m 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学分和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：墨! ：鹭日期盘望! 堡! ! ! 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。( 保密的 论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名： e t 期盘丝：堡：! 里 日期丛! ! ：曼f 翌 第一章绪论 第一章绪论 本章首先引入了多目标概念，介绍了多目标优化问题的产生背景和发展现状， 提出了传统的多目标优化算法和多目标遗传算法。接着介绍了多目标优化进化算 法的发展概况，论文的研究背景及意义，最后给出本文的内容提要和章节安排。 1 1 引言 多目标最优化是- - f - j 迅速发展起来的学科，是最优化的一个重要分支，它主 要研究在某种意义下多个数值目标的同时最优化问题1 1 】，吸引了不少学者的关注。 在现实生活中，人类改造自然的方案规划与设计过程在总体上都反映了“最大化 效益，最小化成本”，这一基本优化原则，在合作对策问题中如何求解最优策略以 获得共赢目标，在非合作对策问题中如何使自己的利益实现最大化，使对方的受 益最小化，以及控制工程中的稳、准、快等时域指标与稳定域度、系统带宽等频 域特性的综合问题等实际上都是多目标的优化问题，因此多目标优化问题在现实 世界中随处可见。虽然经典的方法很好地解决了一部分优化问题，但是对于多目 标优化问题( 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 ：m o p ) 却没有高效实用的解决 方法，然而许多起源于实际复杂系统的设计、建模和规划问题，如工业制造、资 本运算、城市运输、森林管理、水库设计、新城市的布局和美化、能量分配等等， 几乎每个重要的现实生活中的决策问题都要在考虑不同约束的同时优化若干个目 标，而且这些问题所涉及的多个目标并不是独立存在的，往往是耦合在一起且处 于相互竞争的状态，每个目标都有不同的量纲和物理意义，它们的复杂性和竞争 性使得对其优化变得十分困难。因此对多目标优化问题的研究具有很重要的现实 意义，已经成为一个引人注目的研究领域。 在现实生活实际应用中，解决实际优化问题时，如果仅考虑一个目标，我们 称之为单目标优化问题( s i n g l e o b j e c t i v eo p t i m i z a t i o n p r b o l e m ，s o p ) ，否则，称之 为多目标优化问题( m u l t i o b j e c t i v eo p t i m z i a t i o n p b o r l e m ，m o p ) 。多目标优化是最 优化领域的一个重要的研究方向，因为科学研究和工程实践中许多优化问题都可 归结为一个多目标优化问题。多目标优化问题起源于许多实际复杂系统的设计、 建模和规划。这些系统所在的领域包括工业制造、城市运输、资本预算、水库管 理、能量分配、后勤补给、网络通信等等，可以说多目标优化问题无处不有、无 处不在。 2 多目标优化的遗传算法研究 1 2 多e l 标优化的发展和现状 多目标最优化的思想萌芽于1 7 7 2 年，当时f r a n k l i n 就提出了多目标矛盾如何协 调的问题【2 】。1 8 9 6 年，经济学家v p a r e t o 首先在经济平衡的研究中提出多目标最优 化问题，引进了被称为p a r e t o 最优的概念【3 】。1 9 4 7 年，数学家j v o n n e u m a n 和 o m o r g e n s t e m 在对策论的著作中提及多目标决策问题，从对策论角度奠定了经济 行为理论的基础，引起人们对于多目标最优化研究的重视。1 9 5 1 年，数理经济学 家t c k o o p m a n s 弓l 入有效解的定义并得到某些基本结果，为多目标最优化学科奠 定了初步的基础。与此同时，k u l m 等人给出了向量极值问题有效解的必要条件。 1 9 5 3 年a r r o w 等人又提出了有效点的概念。至此，多目标优化逐渐受到人们的关注。 从2 0 世纪5 0 年代末至l j 6 0 年代末，c h a m e ，k a r l i n ，z a d e h ，k l i n g c r ，p o l a k ，k c e n e y 和o e o f f r i o n 等人先后做出了较有影响的工作，出现了加权和法、目标规划法、s 一约 束法等基于权重的多目标传统优化方法，期间多目标优化方法和理论的研究引人 注目。 近些年来，随着进化算法( e v o l u t i o n a r yc o m p u t a t i o n ) 技术和群智能( s w a r m i n t e l l i g e n c e ) 方法的兴起以及在科研和实践中的广泛应用，多目标优化技术的发展 更为迅猛，已成为当前的一个热门的研究领域。同时涌现了很多关于多目标进化 算法方面的会议，目前进化算法的研究已成为近年来信息科学、人工智能与计算 机科学领域两大研究热点之一。 国内对于多目标遗传算法的设计与理论研究也呈现出方兴未艾的局面。在算 法设计方面，王宇平【4 8 】等分别将正交设计、均匀设计与遗传算法相结合给出了求 解多目标优化的新方法。关世华【4 9 】等介绍了一种基于s 约束方法的增广l a g r a n g i a n 多目标协同化算法。公茂果【3 8 】等对当前多目标优化研究趋势的归纳，并提出自己 对多目标优化进一步发展的看法。郑金华等【5 0 l 论证了可以用快速排序的方法对进 化群体中的个体进行分类，同时探讨了用聚类方法来保持群体的多样性。 1 3 论文的研究背景 2 0 世纪8 0 年代以来，以遗传算法为代表的智能优化方法的蓬勃发展，使得 多目标优化方法经历了一个从确定性搜索到随机搜索、从本质上仍是单目标优化 的目标组合法到基于p a r e t o 向量优化的过程，形成了一个崭新领域，引起了众多 学者的浓厚兴趣。随着科学技术的迅猛发展，现代系统的规模增大，约束条件增 多，非线性严重，使得搜索空间异常复杂，优化问题的复杂化对多目标优化方法 的性能提出了更高的要求，同时也给多目标优化方法的研究带来了巨大的挑战。 如何在求解复杂系统时仍能可靠地找到p a r e t o 最优解，提高算法的搜索效率，有 效地维持群体多样性，正逐渐成为研究者关注的焦点。近年来，随着生命科学、 第一章绪论 仿生学以及人工智能理论与工程科学的相互渗透和相互促进，一些新的智能优化 方法，如粒子群算法、蚁群算法、免疫算法等正在逐步兴起，为多目标优化技术 的发展开辟了新的研究领域。这些算法都有其各自不同的特征。如果能结合这些 特征、发挥它们各自的优势，合理地构建多目标优化方法，将对多目标优化技术 的发展起到巨大的推动作用。由上一节的综述可以发现，目前智能优化算法种类 较多，新的优化技术不断兴起。然而，每一种方法都有其各自的优势，都有其相 应的适用范围。在求解复杂系统时，如果能够根据实际需求，采用合理的策略将 多种算法混合，充分发挥其各自的优势，使单一的优化方法互相取长补短，将会 产生更好的优化性能。 1 4 本文的主要工作及安排 近年来，多目标优化遗传算法由于其优越的性能而备受关注，已经成为进化 计算界研究的热点。本文对多目标优化的发展状况和现状、基本理论、基本概念、 基本框架等做了简单扼要的介绍。在此基础上，深入研究了多目标优化问题的性 质，并建立了简化的数学模型，主要进行了以下工作： ( 1 ) 着重介绍了加权求和遗传算法，通过结合均匀设计创建初始种群，并对 其各目标函数规范化，建立新的适应度函数，并提出了一种动态分配权值的方案， 设计了一个基于新的权重分配策略的多目标遗传算法( n w m o g a ) 求解多目标优 化问题。 ( 2 ) 设计了一个基于均匀设计方法的多目标优化遗传算法( b u m o g a ) ，并 给出了算法的收敛性证明，通过仿真验证了该算法的有效性。 本文章节安排如下： 第一章：简要介绍多目标优化问题的引入及多目标优化的发展现状和研究背 景。 第二章：先介绍了多目标优化问题的数学模型和基本概念，其次介绍了传统 的优化算法和常用的遗传算法，并比较了两者的不同之处。 第三章：在对加权求和遗传算法的基础上，提出了一种动态分配权值的方案， 设计了一个基于新的权重分配策略的多目标遗传算法( n w m o g a ) 求解多目标优化 问题。 第四章：设计了基于均匀设计方法的多目标优化遗传算法( b u m o g a ) ，并且 证明了算法的收敛性，用测试函数来验证了算法的有效性，并对结果进行了分析。 最后对全文进行了总结，给出了文章的不足之处以及进一步需要研究的工作。 第二章多目标优化问题 第二章多目标优化问题 2 1 多目标优化问题的定义和数学模型 2 1 1 多目标最优化问题的数学模型 多目标优化问题( 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 ) ，又称多准则 优化问题( m u l t i c r i t e r i ao p t i m i z a t i o np r o b l e m ) ，多性能优化问题( m u l t i p e r f o r m a n c e o p t i m i z a t i o np r o b l e m ) 或向量优化问题( v e c t o ro p t i m i z a t i o np r o b l e m ) 。 一般的多目标优化问题( m o p ) 由- - 组目标函数和相关的一些约束组成，可作如 下数学描述： m i nf ( x ) = ( 彳( x ) ，五( x ) ，厶( x ” ( 2 1 ) 彳e q x qcr ” s ，g ，( x ) 0i = 1 ，2 ，p 其中，x = ( 五，而，矗) r 是r ”空间的n 维向量，称x 所在的空间d 为问题的决策 空间，z ( x ) ，f = 1 ，2 ，所为问题子目标函数，它们之间是相互冲突的，即不q 使石( x ) ，以( 工) ，厶( x ) 在x 处同时取最小值，m 维向量“( x ) ，石( x ) ，厶( x ) ) 所在的空间称为问题的目标空间，g ，( x ) 0 ，i - 1 ，2 ，p 为约束函数。 最大化与最小化问题可以相互转化，因此没做特殊说明，本文都以最小化多 目标为研究对象。 2 1 2p a r e t o 解集的概念 多目标优化问题的本质是在很多情况下，各个子目标之间可能是相互冲突的， 一个子目标的改善有可能引起另一个子目标性能的降低，也就是说，要使多个子 目标同时达到最优是不可能的，而且只能在他们中间进行协调和折衷处理，使各 个子目标函数尽可能达到最优。法国经济学家v p a r e t o ( 1 8 4 8 1 9 2 3 ) 最早研究了经济 学领域内的多目标优化问题，并提出了p a r e t o 解集。 由于多目标优化问题中各个目标之间是相互冲突的，最优解不可能是单一的 解，而是一个解集，所以称之为p a r e t o 解集( 也称非劣解集) 。 首先介绍相关概念： 定义2 1 ( 决策空间上的可行集) 集d = x l 吕( x ) so ，x 彤，f = 1 ，2 ，p 称为m o p 在决策空间上的可行集 6 多目标优化的遗传算法研究 ( f e a s i b l es e ti nd e c i s i o ns p a c e ) 。 定义2 2 ( 目标空间上的可行集) 集f = ( 石，左9 oe0 9 厶) r ”l z = z ( x ) ，i = 1 ，2 ，m ，x d ) 称为m o p 在目标空间 上的可行集( f e a s i b l es e ti no b j e c t i v es p a c e ) 。 定义2 3 设“= ( ，u 2 ，u r n ) r , v = ( m ，v 2 ，) r r ”，若哆且影( 1 ，2 ，肌) 使u ， 为目标空间中的p a r e t o 最优解。 定义2 5 多目标优化问题( 2 1 ) 所有的p a r e t o 最优解构成的集合为p a r e t o 最优 解集，记为e ( f ，q ) ，称 f ( x ) ：x e ( f ，q ) ) 为有效界面( 见图2 1 ) 。 定义2 6 设x q 若不q ，使得z ( x ) 为弱有效界面( 见图2 2 ) 由以上定义可知，多目标优化问题的p a r e t o 最优解仅仅是可以接受的“不坏 的解，并且通常一个多目标问题大多会具有很多个p a r e t o 最优解。在实际应用问 题中，必须根据对问题的了解程度和决策人员的个人偏好，从p a r e t o 最优解集合 中挑选一个或一些解作为多目标优化问题的最优解。 图2 1 对于两个目标函数的目标空间中有效界面的图形 第二章多目标优化问题 7 f 2 图2 2 对于两个目标函数的目标空间中弱有效界面的图形 2 1 3p a r e t o 最优解集的评价准则 对于有两个目标的优化问题，非劣解集在目标空间上为连续或分散的曲线， 称之为非劣前沿曲线。图2 3 所表示的即为非劣前沿曲线。 图2 3 非劣前沿曲线 由于多目标优化问题的结果并不是唯一确定的，所以对其非劣解集质量评价 是比较困难的。一般来说，一个比较理想的非劣解集应包括以下几个方面【4 】： 1 ) 、获得的非劣解集与真实非劣解集的距离应尽可能小。 2 ) 、获得的非劣解集应均匀分布。 3 ) 、获得非劣解集应具有良好的扩展性，即非劣前沿的端点应尽可能接近单 目标极值。 为了方便对多目标优化问题非劣解集质量进行评价，在随后的研究中，人们试 图采用明确的数学表达式来定量化以上3 个衡量标准。通常使用以下四个度量方 法对算法的性能进行评价： 8 多目标优化的遗传算法研究 1 u 度量1 4 1 , 4 刀 设种群在第t 代获取的可行解个体写，墨，h t 分别对应目标空间中的解向量 是硝，“：t9e 9 t ，对于每一个解向量“地= 1 ，2 ，) ，利用在目标向量空间m 中如 何获得一个解的最邻近解的方法，若在目标空间m 中获得每一个解向量与它最邻 近的解向量之间的距离彼此相等，就称解向量嘶，“：t ，t 在目标空间是均匀分布 的。在此定义上，对于确定的解向量z ( 江1 ，2 ，n ) ，设“：是在m 中确定的与杉最 邻近的解，定义彰= t x 五= x = ( _ ，x 2 ，) f 弩t 嚣2 ，i = 1 ，2 9 00 0 9 n 墨= 缸= ( x l ，吒) 阿t 瓦5 ，江1 ，2 ，卅) 即x = x lux ，u ux ，。参数s 可以设为2 ，2 2 ，2 3 等。首先，按照最大范围的 变量，将解空间沿着这个变量方向划分为两个相等的子空间，再将这两个子空间 按同样的方式划分为四个子空间，重复以上步骤l o g ；次，就可以将解空间划分为s 个子空间。对任一个小n 维矩形域子空间x ，我们设为4 7 ( 群，彰，彰) 和 b ，( 瓦，b ，配) 为此矩形域的顶点，使用均匀设计思想，可得到若干个点，构成 初始种群。 例：考虑有三维子空间 彳( 后) ，b ( 七) 】= 【( 4 ( 七) ，a 2 ( 七) ，4 ( 七) ) ，( 骂( 七) ，b 2 ( 尼) ，b ( 七) ) 】， 把个体维数看成均匀设计的因素数，即有3 个因素，取水平数q = 5 。 令届：鱼堡攀，破：兰型攀，以：鱼壁攀，即在4 ( 尼) 到 1 4 4 。 4 b , ( k ) y _ l ；- j ，4 ( 七) 到垦( 七) 之间，a 3 ( 七) 到马( 七) 之间分别插入3 个分点，把它们均 分成4 等分，共5 个分点，则有： 4 ( 七) ，4 ( k ) + d i ，4 ( 后) + 2 面，4 ( 后) + 3 4 ，4 ( k ) + 4 4 = 蜀( 忌) 4 ( 七) ，4 ( 尼) + 畋，- 4 ( 后) + 2 畋，4 ( 后) + 3 吐，4 ( 七) + 4 如= 垦( 七) 4 ( 七) ，4 ( 七) + 以，4 ( 七) + 2 如，4 ( 后) + 3 以，4 ( 七) + 4 4 = 马( 七) 把这3 组数分别看做均匀设计中上述3 个因素的5 个水平数。 根据式3 1 求出均匀设计矩阵 2 3 u ( 3 ，5 ) = i4 5 1 3 5 54 2 3 42 11 ( 3 5 ) 由均匀设计，可以得出在 彳( 七) ，b ( 七) 】内均匀分布的5 个点分别为： ( 4 ( 后) + 4 ，4 ( j ) + 2 破，马( j ) ) ，( a l ( k ) + 2 4 ，垦( 七) ，4 ( 七) + 3 弓) ， ( 4 ( 尼) + 3 吐，4 ( 七) + 破，4 ( 七) + 2 以) ，( 墨( 七) ，4 ( k ) + 3 d 2 ，鸣( 后) + 喀) ， ( 4 ( 七) ，4 ( 七) ，4 ( 七) ) 。 第三章基于新的权重分配策略的多目标遗传算法 因此我们可以利用均匀设计方法在搜索空间上产生一些分布均匀的个体。 3 3 适应度函数设计 定理3 1 【3 6 】设xc r “，厂( x ) = ( 彳( x ) ，厶( x ) ) 在x 上有定义，向量目标函数 f ( x ) 在集合x 上的有效解集和弱有效解集分别记为e ( f ，x ) ，玩( ，x ) 。 若有g ( x ) = ( g l ) ，9 2 0 ) ，g 。( x ) ) 其中g 。x ) = - w i z o ) ，i - 1 ，2 ，m 并且每一w i 关于对应的z ( x ) 都是严格递增的，e ( g ，x ) ，已( g ，x ) 分别表示向量目标函数g ( x ) 在集合x 上的有效解集和弱有效解集，则 1 ) e ( g ，x ) e ( f ，x ) 2 ) e 。( g ，x ) e w ( 厂，x ) 定理3 2 设x 互r ”，z ：x 专r ( i = 1 , 2 ，七) ，f ( x ) = ( 石( x ) ， 0 ) ，厶( x ) ) ，向 量目标函数f ( x ) 在集合x 上的有效解集和弱有效解集分别记为 e 0 f ，x 、) ，e 。0 f ，x 、) o 对v c 。r ，c ， 0 ，令g ，( x ) = c f z ( x ) ，( f = 1 ，2 ，k ) ，g ( x ) = ( g l ( x ) ，9 2 ( x ) ，g 。( x ) ) ， e ( g ，x x e 。 ，x ) 分别表示向量目标函数g g ) 在集合x 上的有效解集和弱有效解 集，则 e ( g ，x ) = e ( f ，x ) ，e ( g ，x ) = 玩( 厂，x ) 在多目标优化的进化算法中，适应度函数通常定义为 f ( x ) = w z ( x ) ( 3 - 6 ) 其中，嵋o ，i = 1 ，2 ，册，且w j = l 。 t = l 在此我们把各目标函数规范化【4 8 l ，设x 1x 2 ，x 即为当第t 代的种群，令 曩( f ) = m a x i f , ( x 1 ) i ，i f , ( x 2 ) | ，i z 即) i ，i = 1 ，2 ，所，则z g ) 可被规范化为新的目 标函数 晶g ) = 需，川 ( 3 - 7 ) 显然- 1 岛( 功1 ，i = 1 , 2 ，m 。 对如下多目标优化问题 r a i ng ( x ) = m i n g , ( x ) ，9 2 ( x ) ，g 。( x ) ( 3 8 ) 多目标优化的遗传算法研究 x x r “ 由定理3 1 和定理3 2 很容易能得出( 2 1 ) 式和( 3 8 ) 式的有效解存在以下关系： x e ( f ，x ) c x e ( g ，r ) ；x e 0 ( ，x ) c 今x e w ( g ，x ) ( 3 9 ) 则新的适应度函数可重新定义为： g ( x ) = m g 。( x ) i = 1 其中，w f o ，i = 1 , 2 ，m ， 肘 且y 嵋= 1 。 r 一 j = l ( 3 1 0 ) 对于双目标优化问题，将规范化后的问题 m i n g , ( x ) ，9 2 ( x ) x x r ” 进行模型转换转化为三角加权求和问题： m i i l g ( x ) 2 罴蜀( x ) + ：石吾而s i n o ( x ) p 【o ，三】 ( 3 1 1 ) 然后通过变化0 值，求出一组p a r e t o 最优解。 如图3 1 示 图3 1 g t 设射线与有效界面的交点为g ( x j ) ，则_ e ( g ，x ) 。对于一个日值，只能求出 一个p a r e t o 解。如果想找到尽可能多的p a r e t o 解，那么需要不同的0 值。 3 4 权向量确定的思想设计 对于转换之后的双目标优化模型，可以看出要求出不同的p a r e t o 最优解，需 要不同的9 值，所以关键在于权向量0 值的取值，本文采用动态随机分配的方式来 第三章基于新的权重分配策略的多目标遗传算法 取0 值。 确定一个初始岛值，令o o = 号，a 为随机生成的随机数，要求h l ，则随机 生成七个口值，求的每一次的嘭= 0 0 ( 1 + a ) ，j = l ，2 ，后，这样可以通过尼个不同 的角度巳，_ r 0 0 三，求得一组p a r e l t o 最优解。 3 5 算子设计 3 5 1 杂交算子 按照适应度g g ) 的大小，用赌轮选择算子从初始种群昂o ) 中选出n ( 为偶数) 个父母点进行杂交，设父母点集合为p ，则 i = 1 , 3 ，n - 1( 3 一1 0 ) 其中，为【o ，1 】之间的随机数，x ，x “1 p ，舅。，z “1 e ( f ) ，丑( r ) 为杂交后的后代 集合。 3 5 2 变异算子 为了提高遗传算法的局部搜索能力，我们采用自适应变异算子和均匀变异两 种方式进行变异： 1 非均匀变异算子 设x = ( 而，x ：，黾) ，为种群e o ) 中的一个父体，j = 1 ，2 ，疗，x ，是 x ( x 尸。( ，) ) 的第，个坐标；a j x ， 岛，口，和屯分别是搜索空间中点的第歹个坐标 的下界和上界；i ，是i ( f ) ) 的第，个坐标，p 2 ( t ) 是第一步变异后代的集合；， 为介于【0 ，1 】之间的随机数；t 为最大遗传代数；r 为当前遗传代数；r ( o ，1 ) 表示产生 0 或者l 的随机数。则有： 弓= x j + ( 屯一乃) ，。 弓= x j 一( b i 口j ) 。， f r ( 0 ，1 ) = 0 ( 3 1 2 ) fr ( 0 ，1 ) = 1 非均匀变异是把参与变异的分量做了一随机扰动，这个扰动在进化初期变化 范围相对较大，但随着进化代数的增加，扰动的变化逐渐的减小。 2 高斯变异算子 x - ( x 1 ，x 2 ，魏) ，为种群毋( ，) 中的一个要进行变异的父体，x j x ( x 尸。( ，) ) + “ x 呵 卜一+ 一 0 卜 + ，卜 ，i 、 邓 ，： + r ，j【 、，一z，一丁 多目标优化的遗传算法研究 的第个坐标，确定刀个服从均值为0 、方差是o t 的正态分布的随机变量n ( o ，a ，) j = l ，2 ，万，章，是旱( 寻b o ) ) ，p 3 ( t ) 是第二步变异后代的集合。则有： i ，= x ，+ n ( 0 ，a ，) j = 1 , 2 ，万 ( 3 1 3 ) 由正态分布的特性可知，高斯变异是对个体的附近区域进行重点搜索。 3 5 3 选择算子 采用精英保留选择算子，具体操作如下：从集合p o ) u 暑o ) u ) u b ( f ) 中选 择最好的m 个个体作为下一代的种群p p + 1 ) 。 3 6 算法n w m o g a 的思想设计 算法步骤如下： s t e p l ：初始化，确定q 值，按照上述初始种群产生的方法在搜索空间中均匀产 生m 个点，构成初始种群e ( t ) ，其中t = 0 ，m 的大小由q 值决定。 s t e p 2 ：从p o ) 中按照赌轮选择算子选出个点作为父母点，设父母点集合为。 s t e p 3 ：对集合尸执行上述杂交算子，得只( f ) 。 s t e p 4 ：对p l ( t ) 执行上述变异算子，分别得最( f ) 和p 3 ( t ) 。 s t e p 5 ：采用精英保留选择算子，从集合p ( t ) 1 jp l ( t ) u 最( f ) ub ( f ) 中选择最好的 m 个个体作为下一代的种群p ( t + 1 ) 。 s t e p 6 ：若达到最大进化代数r ，满足终止条件，则停。否则令r = t + l 转s t e p 2 。 3 7 数值实验 3 7 1 测试函数及测试环境 本节选取了2 个测试函数，采用的是n s g a i i 中的测试函数z d t l ， z d t 4 。 函数具体形式表述如下： 例l ： z d t l ： 石( x ) = 而 厶( x ) = g ( x ) 【1 一妊厕】， g ( x ) = 1 + 9 ( x , ) ( n - 1 ) z = 2 其中，l = 3 0 ，0 薯1 ，i = 1 ，2 ，3 0 ； 第三章基于新的权重分配策略的多目标遗传算法 例2 ： z d t 4 ： 石( x ) = 而 石( x ) = g ( x ) 1 一面丽】 g ( x ) = 1 + 1 0 ( n - 1 ) + 瞎- 1 0 c o s ( 4 z r x , ) i = 2 其中刀= 1 0 ，0 五5 1 ，- 5 x i 5 ，i = 2 ，1 0 ； 3 7 2 仿真结果分析 在m a t l a br 2 0 0 9 a 环境下对上述函数进行测试，参数选择如下：种群规模 2 0 0 ；交叉概率0 9 ；变异概率0 0 7 ；z d t l ，z d t 4 最大进化代数3 0 0 ；k = 3 0 0 ； 对每个函数独立运行3 0 次，记录其中次典型运行所得的非支配解集，将其绘制 成目标空间中的非支配前沿面。 图3 1 算法n w m o g a 对z d t l 一次运行后的结果 多目标优化的遗传算法研究 图3 2 算法n w m o g a 对z d t 4 一次运行后的结果 图3 1 、图3 2 是算法n w m o g a 对上述不同函数所求得的非支配前沿。由实 验结果非支配前沿界面图可以看出，改进后的算法求得解分布相对比较均匀并且 分布范围广。并且求得解的数量有了增加，收敛性增强，逼近效果明显。 3 8 算法性能的评价方式 本节采用以下两种度量方式对算法性能进行评价。 1 s 度量 解越趋于均匀分布，相应的间距评价函数s 的值越小；当该指标值为0 时，表 明我们得到的非支配解在目标空间是等间距分布的。 2 m 度量( 宽广性度量) m 值越大，说明解集的范围越宽广。 表3 1 、表3 2 为算法n w m o g a 对测试函数z d t l 和z d t 4 运行3 0 次后得到 的最好数据分析后的结果。 表3 1 算法n w m o g a 关于测试函数的s 度量 n 、m m o g a s 度量 b e s tm e a nw o r