（运筹学与控制论专业论文）解多目标优化问题的进化算法.pdf

摘要 在工程设计中有很多的多目标优化问题，与单目标优化问题不同，在多目标 优化问题中，往往各目标是相互冲突的，不存在使所有目标同时达到最优的解。 如何得到与p a r e t o 前沿充分接近，分布均匀且范围宽广的非支配解集是求解多目 标优化问题的关键所在。进化算法在解决多目标优化问题方面有着很多优势，研 究如何利用进化算法求解多目标优化问题已经成为一个研究热点。 本文的主要工作如下： 第一，由于初始种群的分布情况在一定程度上影响算法的搜索效率，因此本 文采用均匀设计和混沌映射相结合的方法产生出了分布较均匀、多样性较好的初 始种群；同时，结合混沌序列的性质，设计了一个新的交叉算子，由此提高了算 法的搜索性能。最后，综合以上两点思路，分别基于l o g i s t i c 映射和s i n u s o i d a l 映 射，设计了基于均匀设计和混沌映射的多目标优化进化算法u c m o e a 和 u s m o e a 。实验结果表明，本文设计的算法得到的非支配解集更加接近p a r e t o 前 沿，并且搜索到的非支配解分布较为均匀。 第二，设计了一个带有局部搜索的多目标优化进化算法l s m o e a ，该算法能 够找到非支配前沿的稀疏区域，并且基于均匀设计的思想，对稀疏区域进行搜索， 从而使搜索到的非支配解分布更加均匀，数值实验表明了算法的有效性。 关键词：多目标优化进化算法均匀设计 混沌 a b s t r a c t t h e r ea r em a n ym 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 sw h i c ho b j e e t i v e so f t e n c o n f l i c tw i t h e a c ho t h e ri nt h ee n g i n e e r i n g p r o b l e m s n os i n g l es o l u t i o nc a l lb ef o u n dt o o p t i m i z ea l lt h eo b j e c t i v e ss i m u l t a n e o u s l y t h i ss i t u a t i o ni sd i f f e r e n tf r o mt h eo n ei n s 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 t h u s ，f 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 t h ek e yi s s u ei st of i n das e to fw e l ld i s t r i b u t e da n d c l o s e t o p a r e t o o p t i m a ls o l u t i o n s a c c o r d i n gt ot h e i ra d v a n t a g e s ，e v o l u t i o n a r ya l g o r i t h m sf 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 n p r o b l e m sh a v eb e c o m eah o tr e s e a r c ht o p i c 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 ： f i r s t ，n o t et h a tt h ed i s t r i b u t i o no ft h ei n i t i a lp o p u l a t i o nd i r e c t l ya f f e c t st h es e a r c h r e s u l t so ft h ee v o l u t i o n a r ya l g o r i t h m s i nt h i st h e s i s ，u n i f o r md e s i g na n d c h a o sm a p p i n g a r ej o i n t l ye m p l o y e dt og e n e r a t et h ei n i t i a lp o p u l a t i o n t h ei n d i v i d u a l si nt h eg e n e r a t e d p o p u l a t i o na l es c a t t e r e du n i f o r m l yo v e rt h ef e a s i b l ed e c i s i o ns p a c e ，a n da l s oh a v eb e t t e r d i v e r s i t yw h i c hi sg o o df o ra na l g o r i t h mt oe x p l o r et h ed e c i s i o ns p a c e m o r e o v e r , an e w c r o s s o v e ro p e r a t o ri sd e s i g n e d ，w h i c hc a ni m p r o v et h es e a r c ha b i l i t yo f t h ep r o p o s e d a l g o r i t h m sb yu s i n gp r o p e r t yo fc h a o s b a s e do nt h e s et w os c h e m e s ，w ep r o p o s et w o m 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 o l u t i o n a r ya l g o r i t h m sn a m e du c m o e aw i t hl o g i s t i c a l m a p p i n ga n du s m o e aw i t hs i n u s o i d a lm a p p i n g t h es i m u l a t i o nr e s u l t si n d i c a t et l l a t t h en o n _ d o m i n a t e ds o l u t i o n so b t a i n e dh a v eb e t t e r q u a l i t ya n dg o o dd i s t r i b u t i o n s e c o n d , an e wm 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 o l u t i o n a r y a l g o r i t h mw i t hl o c a l s e a r c hn a m e dl s m o e ai s p r o p o s e d t h i sa l g o r i t h mc a nf i n dt h es p a r s ea r e ao ft h e n o n _ d o m i n a t e df r o n t c o n c r e t e l y , t h es e a r c hw a se s p e c i a l l yf o c u s e do nt h es p a r s ea le a u s i n gu n i f o r md e s i g nm e t h o d ，a n df i n a l l yt h en o n d o m i n a t e ds o l u t i o n sw h i c hh a v e b e e n f o u n dc a ns c a t t e ru n i f o r m l ya l o n gt h en o n d o m i n a t e df r o n t t h es i m u l a t i o nr e s u l t s i n d i c a t et h ee f f e c t i v e n e s so ft h ep r o p o s e d a l g o r i t h m k e y w 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 n e v o l u t i o n a r ya l g o r i t h m s u n i f o r md e s i g n c h a o s 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学分和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：皇! 整日期垄! ! ：圣! ! 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。( 保密的 论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名： 日期兰：! ! ：三：! ! 日期迦! ! ：i 。! ! 第一章绪论 第一章绪论 本章首先介绍了多目标优化问题的产生背景，简述了几种传统的多目标优化 算法。接着介绍了多目标优化进化算法的发展概况，论文的研究背景及意义，最 后给出本文的内容提要和章节安排。 1 1 多目标优化问题的产生背景 多目标最优化是一门迅速发展起来的学科，是最优化的一个重要分支，它主 要研究在某种意义下多个数值目标的同时最优化问题1 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 ) 却没有高效实用的解决方法，然而许 多起源于实际复杂系统的设计、建模和规划问题，如工业制造、资本运算、城市 运输、森林管理、水库设计、新城市的布局和美化、能量分配等等，几乎每个重 要的现实生活中的决策问题都要在考虑不同约束的同时优化若干个目标，而且这 些问题所涉及的多个目标并不是独立存在的，往往是耦合在一起且处于相互竞争 的状态，每个目标都有不同的量纲和物理意义，它们的复杂性和竞争性使得对其 优化变得十分困难。因此对多目标优化问题的研究具有很重要的现实意义，已经 成为一个引人注目的研究领域。 多目标优化也称为多指标优化、多准则优化或向量优化，a o s y c z k a 给出了多 目标优化的定义：寻找一个由决策变量构成的向量，使其能够满足所有的约束条 件以及由目标函数组成的向量函数，这些目标函数是对性能指标的数学描述，而 且它们之间往往是彼此冲突的。在多目标优化问题中，各目标之间通过决策变量 相互制约，对其中一个目标进行优化时必须以其它目标作为代价，而且各目标的 单位往往不一致，因此很难客观地评价多目标优化问题解的优劣性。在单目标优 化问题中，问题的最优解已具有明确的定义，但这一概念却不能推广到多目标优 化问题中，不同于单目标优化问题的最优解概念，多目标优化问题的最优解对于 某个目标来说可能是较好的，而对于其它目标来说可能是较差的，与单目标优化 问题的本质区别在于，多目标优化问题的最优解不是唯一的，而是一组最优解的 集合，称为非劣最优解集，也就是p a r e t o 最优解集。所谓p a r e t o 最优解就是，当 对所有目标函数考虑时，在搜索空间中不存在比其中至少一个目标好而其他目标 不劣的更好的解，p a r e t o 最优解集中的元素就所有目标而言是彼此不可比较的【2 】。 因为基于数学规划原理的多目标优化方法在实际优化问题中往往表现出一定的脆 2 解多目标优化问题的进化算法 弱性，所以，有必要研究求解多目标优化问题的高效算法及理论。 1 2 多目标优化方法的发展历史和研究现状 正是由于多目标优化问题的广泛存在性与求解的困难性，该问题一直是富有 吸引力与挑战性的。它的出现可以追溯到1 7 7 2 年，当时f r a n k l i n 就提出了如何来 协调多个目标矛盾的问题【3 】。但国际上一般认为多目标问题最早由法国经济学家 vp a r e t o 在1 8 9 6 年提出，当时他从政治经济学的角度出发，把很多不好比较的目 标归纳成为多目标优化问题【4 】。1 9 2 7 年数学家eh a u s d o f f 关于有序空间理论的研 究，为多目标规划的发展提供了理论工具。此后这方面的工作方兴未艾：1 9 4 4 年， v o n n e u m a n n 和j m o r g e n s t e m 从对策论的角度，提出了彼此互相矛盾的多目标决 策问题【5 1 ；1 9 5 1 年，t c k o o p m a n s 从生产与分配的活动分析中第一次提出了p a r e t o 最优解的概念。从2 0 世纪5 0 年代末到到9 0 年代初，k u h n 、c h a m e s 、z a d e h 、 g e o f f r i o n 、s t e u e r 等人先后做了许多卓有成效的工作，出现了s 约束法、加权和方 法、目标规划法等多目标优化方法，期间多目标优化理论和方法的研究一直引入 注目。 1 2 1 传统的多目标优化方法 绝大多数传统的多目标优化方法是将多个目标通过某种技术转换为一个目标 的优化问题，然后再借助数学规划工具来求解。我们先给出多目标优化问题的数 学模型，不失一般性，一个具有刀个决策变量，m 个目标变量的多目标优化问题可 表述为： lm i ny = f ( x ) = ( z ( x ) ，以( 功，厶( x ) ) s j 岛( x ) s0 ，f - l ，2 ，q( 1 1 ) i h j ( x ) = 0 ，j = l ，2 ，p 其中，工= ( 五，x 2 ，毛) xcr 行为刀维的决策矢量，x 为门维的决策空间 ( d e c i s i o ns p a c e ) ，y = ( m ，y 2 ，儿) ycr 册为m 维的目标矢量，】，为m 维的目标 空间( o b j e c t i v es p a c e ) ，g j ( x ) o f f = l ，2 ，q ) 定义了q 个不等式约束， 办，( 功= 0 ( j = 1 ，2 ，夕) 定义了p 个等式约束。 ( 1 ) 加权和方法( w e i g h t e ds u mm e t h o d ) 这种方法是由z a d e h t 6 1 和g e o f f r i o n t j 提出的，加权法将为每个目标函数分配带 有实际意义的权重，再将所有的目标函数聚合成为一个目标函数，也就是通过加 权和的方法将多个目标的优化问题转换成以下形式的一个单目标优化问题： 第一章绪论 3 m i n y = ( x ) = q z ( x ) i = 1 x x f ( 1 - 2 ) 其中权重系数鲍0 ，用来表示各个目标的相对重要程度，通常我们约定 哆= 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 最优解。此外，加权法对 于p a r e t o 前沿的形状很敏感，很难在p a r e t o 前沿的非凸部分上取得解。许多学者 又提出了若干种权重调整方法，如固定权重法，适应性权重法和随机权重法嘲等。 ( 2 ) s 一约束法( s - c o n s t r a i n e dm e t h o d ) s 约束法【9 1 是由h a i m e s 等人在1 9 7 1 年提出的，它的原理是先对多个目标中 最重要的一个进行优化，把其他目标作为约束条件考虑，模型如下： m i n f j o ) s u b j e c t t o z ( x ) q ，( 1 f m ，f ) ( 1 - 3 ) xe x f 蜀作为上界可在优化过程中取不同的值，以便搜索到多个p a r e t o 最优解，记x ， 为可行解集合。通过这种方式将多目标优化问题转换为单目标优化问题，然后通 过一般的数学规划方法或者模拟退火等方法进行求解，r i t z e l ! m 1 曾将g 约束法和遗 传算法结合起来解决多目标优化问题。这种方法比较简单。易于实施。但是求得 的解在很大程度上依赖于岛的取值。无论s ，怎么取值，一般都会或多或少的缩小 可行域的范围。 ( 3 ) 目标规划法( g o a lp r o g r a m m i n g ) 目标规划法【1 1 , 1 2 1 是c h a m e s 等人为求解多目标线性规划问题而提出的一种方 法。在使用该方法中，决策者必须根据需要求解问题的具体情况给出每个目标所 期望获得的目标值，把这些目标值作为附加的约束条件加入到原问题中。这样原 问题就转换为求目标函数值到规定目标值之间绝对偏差最小的问题，即 砌 酗( x ) 一引 s u b j e c t t o x x f 4 解多目标优化问题的进化算法 其中，霉为决策者设定的期望第f 个目标达到的目标值，记x ，为可行解集合。如 果设定的目标值在可行域内，使用这种方法肯定可以得到p a r e t o 最优解，而且具 有较高的求解效率。它的主要缺点是需要决策者事先给定各个目标函数的目标值， 而且还需要对搜索空间的形状非常了解。该方法对于目标函数为线性的优化问题 比较有效，但对于求解非线性优化问题效率不高。 ( 4 ) 极小极大法( m i n - m a xa p p r o a c h ) 极小极大法起源于博弈论法，是为求解有冲突的目标函数而设计的。该方法 的线性模型由j u t l e r 和s o l i e h 提出【1 3 l ，后由o s y c z k a 和r a o 进一步改进【堋，这种 方法是通过最小化各个目标函数值与预设目标值之间的最大偏移量来寻找问题的 最优解。 ( 5 ) 距离函数法 距离函数法 1 5 , 1 6 需要使用理想点，定义理想点如下： 定义1 1 ( 理想点) ：理想点用y = ( m ，耽，y m ) 来表示，其中 订= i n f f j ( x ) f x x ， ，f = 2 ，3 ，m( 1 5 ) 上式中点y 称为理想点( i d e a lp o i n t ) 是因为通常该点无法达到。距离函数法寻找与 理想点最近的解，根据理想点y 的定义，对于目标空间的每一个元素，我们无法 得到比理想点更好的结果。给定y y ，j ，与j ，的距离函数为： r ( y ) = 眇一y 0 ( 1 - 6 ) 其中i - y 0 是在某种特定范数意义上从y5 0y 的距离。由于范数比较清晰，因 此经常采用。对于一个给定的正数p 1 ，有： ， ；仂= i k - y l l p = 善i 一矿i p l ，p c - - 7 ， 范数的意义下的最优解就是最小 d 6 r ( y ；p ) 的点。距离函数，( 少；p ) 对于每一个 i 乃一以i 的值的重视程度相同。如果具有不同的重要性，可以指派一个权重向量 c o = ( c o 。，哆，) 来表明不同的重要程度，在这种情况下，可以使用加权乞范数 来求解： ，c y ；p ，国，= k - y l l ，翘= 善蟛i 巧一矿l p u p c - - 8 ， 1 2 2 传统多目标优化方法的局限性 从以上描述可以看出，传统方法的优点是它继承了求解单目标优化问题的机 第一章绪论 5 制。这些传统的多目标优化算法采用不同的方法将多目标优化问题转化为单目标 优化问题，然后采用解决单目标优化问题的方法来进行求解。传统的方法简单高 效，而且能够保证收敛到p a r e t o 最优解集，因此得到了广泛的使用。然而，它们 在求解多目标优化问题时也存在着一些局限性： 1 ) 所有的这些算法必须要根据问题的先验知识来选取合适的参数，不同的参 数设置会产生不同的p a r e t o 最优解。这就要求决策者事先要对问题有足够深入的 认识，才能够合适地选取参数，而这个过程往往比较困难。 2 ) 在大多数情况下，采用这些方法通常只能得到一个p a r e t o 最优解，而该解 的获取与转换过程中参数的设定有着很大的关系。为了获取更多的p a r e t o 最优解， 就得对参数多次调整、多次按照单目标优化方法来进行寻优，由于各次优化过程 是相互独立的，往往得到很不一致的结果，因此令决策者很难有效地进行决策， 而且还要耗费大量的时间。 3 ) 一些算法对p a r e t o 前沿的形状异常敏感，比如加权和方法，在处理p a r e t o 最优前端为非凸的问题时，无论参数如何调整，都无法在非凸区域找到p a r e t o 最 优解。 1 2 3 解决多目标优化问题的新方法 随着科学研究的高速发展，各个学科之间相互融合交流，产生了众多的交叉 学科。为了处理些复杂问题，例如：人工智能、图像处理、非线性优化等，人 们致力于研究一些具有自组织，自适应能力的大规模并行算法。进化算法正是根 据生物的遗传机理与自然选择的进化机理而演变出的一类智能群体算法 1 7 , i s 】。 进化算法的研究起源于2 0 世纪5 0 年代末，成熟于8 0 年代。进化算法具有四大 分支：在6 0 年代中期，受到生物界自然选择和自然遗传机制的启发，h o l l a n d 提出 了遗传算法( g e n e t i c sa l g o r i t h m ：g a ) 【1 9 2 0 1 ，r o s e n b e r g 提出了进化策略( e v o l u t i o n a r y s t r a t e g y ：e s ) 【8 】，f o g e l 等人提出了进化规划( e v o l u t i o n a r yp r o g r a m m i n g ：e p ) 【2 ，到2 0 世纪9 0 年代，在遗传算法的基础上，k o z a ：将g a 用于计算机程序及自动化生成，提 出了遗传程序设计( g e n e t i c sp r o g r a m m i n g ：g p ) 2 2 , 2 3 】，虽然这几个分支在算法实现方 面有一些细微的差别，但它们都是借鉴生物演化的思想和原理来解决实际问题的。 目前，进化算法已在经济预测、自动控制、工程优化、机器学习，模式识别等领 域得到了成功的应用【1 7 以2 5 ，2 6 1 。 进化算法的出现为解决多目标优化问题开辟了一个新的途径。进化算法因其 具有的智能性、隐并行性及表现的自适应性和自组织性等特点，实现了搜索的多 向性和全局性，又不需要许多数学上的必备条件，加之其又适应于大规模的并行 计算，可以同时搜索到问题解空间中的多个区域【1 1 , 2 6 1 。因此，进化算法为多目标 6 解多目标优化问题的进化算法 优化问题的解决提供了新的思想和新的契机。近些年来，随着研究的不断深入， 进化计算界相继提出了多种不同的多目标优化进化算法( m 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 ：m o e a ) | 2 7 2 8 ，2 9 3 0 3 1 翔, 3 3 3 4 , 3 5 , 3 6 1 。它们的提出引起了众多研究 机构的重视，这一方向已成为学术界研究的热点，近几年来取得了引人瞩目的成 就，其在实际工程中的巨大价值吸引了众多学者的关注。 总的说来，进化算法的出现为求解多目标优化问题带来了新的生机与希望， 但是由于多目标优化问题自身的特点决定了求解多目标优化问题必须注意到一些 问题，m o e a 的研究主要是两个方面：其一，如何避免未成熟收敛，即保持非支 配解集逼近p a r e t o 前沿；其二，如何获得分布均匀且范围宽广的p a r e t o 解集( 非支配 解集) ，即保持非支配解集的均匀性与多样性。然而目前所出现的算法都是比较复 杂，在对一些特殊情况往往得不出较好的结果。到目前为止，多目标优化进化算 法仍然处于不断探索和研究中。 1 3 本文的组织结构及所作的工作 近年来，多目标优化进化算法由于其优越的性能而备受关注，已经成为进化 计算界研究的热点。本文对进化算法和多目标优化的基本理论、基本概念、基本 框架、研究现状等进行了简单扼要的介绍，在此基础上，主要进行了以下工作： ( 1 ) 在n s g a i i 算法的基础上，通过结合均匀设计和混沌映射来初始化种群， 使得初始种群分布较为均匀，多样性较好。同时根据混沌序列的遍历性和伪随机 性，设计了一个可以动态调整交叉位数的交叉算子，提高了算法的搜索能力。根 据不同的混沌映射，设计了算法u c m o e a 和u s m o e a ，同时运用一些不同性质的 函数对所设计的算法进行测试，并分析了算法的性能； ( 2 ) 在均匀设计的基础上，设计了一个带有局部搜索的多目标优化进化算法 ( l s m o e a ) ，并给出算法的收敛性证明，通过仿真测试验证了该算法的有效性。 本文的内容安排如下： 第二章扼要介绍了进化算法的基本理论和多目标优化进化算法的基本概念、 基本理论、基本框架、研究现状及关键性问题。 第三章设计了基于均匀设计和混沌映射的多目标优化进化算法。通过对不同 性质函数的测试，验证了算法的有效性，并对结果进行了分析。 第四章设计了一个带有局部搜索的多目标优化进化算法，并且证明了算法的 收敛性，用测试函数来验证了算法的有效性，并对结果进行了分析。 最后对全文进行了总结，并给出了文章的不足之处以及进一步需要研究的工 作。 第二章多目标优化进化算法简介 7 第二章多目标优化进化算法简介 无论是在科学研究还是在工程应用上，多目标优化都是非常重要的研究课题。 多目标优化问题已经成为最优化的一个重要分支。多目标优化是要找到一组均衡 的解，耳p p a r e t o 最优解集，由于进化算法具有并行机制，可同时对解空间进行多点、 并行搜索，这为找到多个p a r e t o 最优解提供了可能，所以适合于求解多目标优化问 题。由于多目标优化问题有不同于单目标优化问题的优化目标，因此设计多目标 优化进化算法的目标【3 7 ，3 8 1 是： ( 1 ) 希望算法找到的非支配前沿与p a r , t o 前沿应该充分的接近； ( 2 ) 希望算法找到的非支配解集有较均匀的分布； ( 3 ) 希望算法所找到的非支配解集的分布范围尽可能的宽广，即非支配解覆盖 目标空间尽可能宽的范围； ( 4 ) 希望算法具有较快的收敛速度； 本章首先介绍了多目标优化问题的数学知识，然后陈述了进化算法的基本理 论，尤其对遗传算法做了较为详细的介绍；再对多目标优化进化算法的历史与研 究现状作了简要的说明，最后简单讨论了进化算法处理多目标优化问题要解决的 关键问题以及如何对算法进行性能评估，由此引出本文的主要研究工作。 2 1 多目标优化问题的数学描述 多目标优化问题又称为多标准优化问题。不失一般性，一个具有玎个决策变量， m 个目标变量的多目标优化问题可表述为 fm i ny = f ( x ) = ( 石( x ) ，以( x ) ，厶( x ) ) 。 s j 岛( x ) 0 ，f = 1 ，2 ，q( 2 一1 ) i h a x ) = o ，= l ，2 ，p 其中，x = ( 五，x 2 ，) xc r ”为刀维的决策矢量，x 为r 维的决策空间 ( d e c i s i o ns p a c e ) ，y = ( m ，耽，y m ) yc 尺肼为m 维的目标矢量，】，为m 维的目标 空间( o b j e c t i v es p a c e ) 。目标函数f ( x ) 定义了m 个由决策空间到目标空间的映射函 数；岛( x ) o ( i = 1 ，2 ，q ) 定义了q 个不等式约束，办，( x ) = 0 u = l ，2 ，p ) 定义了p 个等式约束。在此基础上，给出以下几个重要的定义1 3 9 1 ： 定义2 1 ( 可行解) 对于某个x x ，如果x 满足( 2 1 ) 中的约束条件蜀( x ) 0 ( 江l ，2 ，g ) 和h j ( x ) = 0 ( y = 1 ，2 ，p ) ，则称x 为可行解。 定义2 2 ( 可行解集合) 由x 中的所有的可行解组成的集合称为可行解集合，记 8解多目标优化问题的进化算法 为xf ，a x fs xo 定义2 3 ( p a r e t o 占优) 假设以，x ，是式( 2 1 ) 所示多目标优化问题的两个可 行解，则称与相比，一也是p a r e t o 占优的，当且仅当 v i = 1 ，2 ，m ，z ( 硝) z ( ) 人影= 1 ，2 ，朋，f j ( x ) - ，也称为硝支配。 定义2 4 ( p a r e t o 最优解) 一个解x x ，被称为p a r e t o 最优解，当且仅当满足如 下条件： l 孤x ，：x - x ( 2 3 ) 定义2 5 ( p a r e t o 最优解集) p a r e t o 最优解集是所有p a r e t o 最优解的集合，定义 如下： p = x j - 1 孔r ，：x x )( 2 4 ) 定义2 6 ( 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 f = f o ) = ( 彳0 ) ，a ( x ) ，厶( x ”rix p ( 2 - 5 ) 2 2 进化算法的基本理论 2 2 1 进化算法的概念和形式 进化算法1 4 0 主要包含四种典型算法：遗传算法( g e n e t i ca l g o r i t h m s ，g 舢、进 化策略( e v o l u t i o n a r ys 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 ) 、遗 传程序设计( g e n e t i cp r o g r a m m i n g ，g p ) 四种典型方法。这四种算法虽然相似，却是 彼此独立发展起来的。它们在进化的原则上是一致的，都是借助生物进化的思想 和原理来求解问题，但是在实施进化的方法上却各有特点，其中遗传算法强调染 色体的操作；进化策略强调个体上的行为变化，侧重于数值分析；进化规划强调 种群上的行为变化，其应用则介于数值分析与人工智能之间；遗传程序设计是对 算法的程序进行进化。通过近年来的研究，进化算法的各个分支之间相互借鉴， 不断融合，它们之间的差别也在不断减小。 在实际的科学计算中，进化算法具有与传统的优化方法不同的优化处理过程。 大多数典型的传统优化方法是通过计算代价函数的梯度或高阶统计值来进行优化 的，通过此类方法只能得到局部极优值，且容易受到随机干扰的影响。进化算法 借鉴进化方法以及符合达尔文“适者生存 和随机信息交换思想，消除解中的不 第二章多目标优化进化算法简介 9 适应因素，同时再利用原有解的相关知识，最终获得全局最优解。 参照自然进化的过程，称候选解为个体，候选解集为种群，每个个体代表一 个可行解，但个体并不就是决策向量，它是基于适当结构的编码形式，所有可行 向量构成个体空间。从个体空间映射到决策空间，进而得到目标空间中的信息。 进化算法是一种基于自然选择和交叉变异等生物进化机制的全局性概率搜索 算法，其求解的一般过程包括以下步骤【1 8 3 9 , 4 0 , 4 1 1 ： 1 ) 随机给定一组初始解； 2 ) 评价当前这组解的性能； 3 ) 根据2 ) 的评价结果，从当前解中选择一定数量的解作为遗传操作对象； 4 ) 对所选择的对象进行遗传操作( 交叉、变异) ，得到一组新的解； 5 ) 返回到2 ) ，对该组新的解进行评价； 6 ) 若当前解满足要求或进化达到一定的代数，计算结束，否则转向3 ) 继续进 行。 与传统的优化方法( 如下降梯度法、单纯性法、和牛顿法) 相比，进化算法具 有以下的特点： 1 ) 进化算法是对变量的编码进行操作，而非变量本身。 2 ) 进化算法的搜索过程是从一群初始点开始搜索，而不是从单一点开始搜索。 这样，提高了获得全局最优解的概率。 3 ) 进化算法使用的是目标函数的评价信息，对目标函数的性质：如可微性， 连续性几乎没有要求，具有良好的普适性。 4 ) 进化算法具有显著的隐式并行性。 5 ) 进化算法具有很强的鲁棒性。 6 ) 进化算法是一种高效的启发式搜索，而非盲目的穷举或完全随机搜索。 进化算法是一种具有自适应调节功能的寻优方法，已在众多领域内获得了较 广泛的应用，着重用于解决非线性优化、并行计算等复杂问题，其中遗传算法的 研究最为深入，应用面也最广。 2 2 2 遗传算法的基本概念 遗传算法1 4 2 j 起源于对生物系统所进行的计算机模拟研究。美国m i c h i g a n 大学 的h o l l a n d 教授及其学生受到生物模拟技术的启发，创造了一种基于生物遗传和进 化机制，适合于复杂系统优化的自适应概率优化技术遗传算法。 遗传算法模拟了自然选择和遗传中发生的复制，交叉，变异等现象。从任意 一个初始种群( p o p u l a t i o n ) 出发，通过选择、交叉和变异操作，产生了一群更适应 环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代地不断繁 l o解多目标优化问题的进化算法 衍进化，最后收敛到一群最适应环境的个体( i n d i v i d u a l ) ，求得问题的最优解。遗传 算法主要涉及有以下几个因素： ( 1 ) 遗传编码 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法的一个关键步 骤。在遗传算法执行过程中，需要对不同的具体问题进行编码，编码的好坏直接 影响到后续的遗传操作。解空间中的解数据x ，是作为遗传算法的表现型形式。从 表现型到基因型的映射称为编码，遗传算法在进行搜索之前先将解空间的解数据 表示成遗传空间的基因型串结构数据。由于遗传算法的鲁棒性，它对编码的要求 并不苛刻，但编码对遗传算法的搜索效果和效率却是非常重要的，对特定的问题 确定适合的编码是非常重要的步骤。 问题编码一般应满足以下3 个原则： 完备性( c o m p l e t e n e s s ) ：问题空间中的所有点( 候选解) 都能以遗传算法空 间中的点( 染色体) 表现。 健全性( s o u n d n e s s ) -遗传算法空间中的染色体能对应所有问题空间中的 候选解。 非冗余性( n o n - r e d u n d a n c y ) ：染色体和候选解必须一一对应。 按照遗传算法的模式定理，d e j o n g 提出了较为客观明确的编码评估原则。具 体概括为以下两条： 1 ) 有意义的积木块编码规则：即编码应当易于生成与所求问题相关的短距和 低阶的积木块； 2 ) 最小字符集编码规则：编码应采用最小字符集以使问题得到自然的表示和 描述； 其中，规则1 ) 基于模式定理和积木块假设，规则2 ) 提供了一种更为实用的编码 原则。 针对一个具体问题，如何设计一种完美的编码方案一直是遗传算法的应用难 点之一，也是遗传算法的一个重要研究方向。由于遗传算法应用的广泛性，迄今 为止人们已经设计了不同的编码方法。二进制编码方法是遗传算法中最主要的一 种编码方法，其他的编码方法还有：格雷码编码、浮点数编码、多参数级联编码、 多参数交叉编码，自适应编码等。 c ) 初始群体的生成 一定数量的个体组成了群体( p o p u l a t i o n ，也称为种群) ，群体中个体的数目称 为群体规模( p o p u l a t i o ns i z e ) 。由于遗传算法的群体性操作需要，所以在执行遗传操 作之前，必须先构造一个由若干个解组成的初始群体。由于现实工程问题的复杂 性，往往并不具有关于问题解空间的先验知识，很难确定最优解的数量及其在可 行解空间中的分布状况，所以我们往往希望在问题的解空间中均匀布点。群体规 第二章多目标优化进化算法简介 模是遗传算法的控制参数之一，其选取对遗传算法的性能有影响。一般群体规模 在几十到几百之间取值，根据问题的复杂程度不同而取值不同，问题越难，维数 越高，种群规模越大，反之则小。 ( 3 ) 适应度函数 在遗传算法中使用适应度( f i t n e s s ) 这个概念来度量群体中各个个体在优化计 算中能达到或找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就 较大；而适应度较低的个体遗传到下一代的概率相对小一些。度量个体适应度的 函数称为适应度函数( f i t n e s sf u n c t i o n ) 。适应度函数也称为评价函数，是根据目标 函数确定的，用于区分群体中个体好坏的标准，是算法演化过程的驱动力，也是 进行自然选择的唯一依据。适应度函数总是非负的，任何情况下都希望其值越大 越好，而目标函数有正有负，因此需要在目标函数和适应度函数之间进行变换。 为了变更选择压力，也需要对适应度函数进行变换。 适应度函数的设计主要应满足以下条件： 1 ) 单值、连续、非负、最大化。 2 ) 合理、一致性。要求适应度值反映对应解的优劣程度。 3 ) 计算量小。适应度函数设计应尽可能简单，这样可以减少计算时间和空间 的复杂性，降低运算成本。 4 ) 通用性强。适应度对某类具体问题，应尽可能通用，最好无需使用者改变 适应度函数中的参数。 遗传算法在选择操作时会出现以下两个称为遗传算法的欺骗问题： 1 ) 在进化的初期，通常会产生一些超常个体，若按比例选择法，这些超常个 体会因竞争力突出而控制选择过程，影响算法的全局收敛性； 2 ) 在进化的最后阶段，由于种群中个体的适应度差异较小时，继续优化的潜 能减低，可能获得某个局部最优解； 如果适应度函数设计不当，有可能造成这两种问题的出现。所以适应度函数 的设计是遗传算法设计的一个重要方面。在遗传算法中，个体遗传到下一代的群 体中的概率是由该个体的适应度来确定的。应用实践表明，如何确定适应度对遗 传算法的性能有较大的影响。有时在遗传算法运行的不同阶段，还需要对个体的 适应度进行适当的扩大和缩小。这种对适应度进行扩大或缩小变换就称为适应度 尺度变换( f i t n e s ss c a l i n gt r a n s f o r m ) 。 适应度函数的常用尺度变换算法有以下几种：线性尺度变换，乘幂尺度变换， 指数尺度变换。 ( 4 ) 标准遗传算法的操作算子【4 1 ，4 2 】 标准遗传算法的操作算子一般都包括选择( s e l e c t i o n ，或者复$ o r e p r o d u e t i o n ) 、 交叉( c r o s s o v e r ，或称杂交) 和变异( m u t a t i o n ) t m 种基本形式，它们作为自然选择过 1 2 解多目标优化问题的进化算法 程以及遗传过程发生的生殖，杂交和变异的主要载体构成了遗传算法的核心，使 得算法具有强大的搜索能力。 1 ) 选择算子 遗传算法中使用选择操作来对群体中的个体进行优胜劣汰：根据每个个体的 适应度值大小选择，适应度较高的个体被遗传到下一代群体中的概率较大；适应 度较低的个体被遗传到下一代群体中的概率较小。这样就可以使得群体中个体的 适应度值不断接近最优值。选择操作是建立在对个体适应度进行评价的基础之上。 选择操作的目的是为了避免有用遗传信息的丢失，提高全局收敛性和计算效率。 目前主要有适应度比例选择( f i t n e s s p r o p o r t i o n a ls e l e c t i o n ) 、确定性选择、排序 选择( r a n ks e l e c t i o n ) 、联赛选择( t o u r n a m e n ts e l e c t i o n ) 、精英选择( e l i t i s ts e l e c t i o n ) 、 稳态选择( s t e a d y s t a t es e l e c t i o n ) 等形式。 2 ) 杂交算子 在生物的进化过程中，两个同源染色体通过交配而重组，形成新的染色体， 从而生成新的个体和物种。模仿这个过程，遗传算法采用交叉算子来产生新的个 体：在交叉之前，先对群体中的个体配对，常用的配对策略是随机配对，即将群 体中的m 个个体依据随机方式组成i 吆i 对配对个体，其中ixi 表示不大于x 的 l l j - 一 最大整数。交叉操作是在两个个体之间进行的。常使用的杂交算子包括一点交叉 ( o n e p