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

摘要 摘要 由于多目标优化技术在工程、经济、管理和军事等领域中具有重要的应用价 值，多目标优化的研究越来越受到广泛的关注和重视，它已发展成为- i - j 新兴的 学科并在应用中显示出强大的生命力。遗传算法是借鉴生物的自然选择和遗传机 制而丌发出的一种全局优化自适应概率搜索算法，它在解决复杂系统优化时的所 表现出的独特的优越性和健壮性，使其成为解决多目标优化问题的一个非常有效 的手段。 本文详细地介绍- 了多目标优化的研究现状、基本原理和具有代表性的算法以 及遗传算法的数学理论和实现技术等内容，并对多目标优化遗传算法中有待解决 的问题对进行了研究。通过对最优保存策略的研究，提出了基于p a r e t o 最优解数据 仓库的多目标优化遗传算法，该算法利用数据仓库来保存每代所产生的p a r e t o 最优 解个体，采用度量个体间的距离方式来淘汰数据仓库中相同或相似的个体，该算 法还对选择算子进行了改进，使得算法的自适应能力增强，这种新算法提高了算 法性能，改善了解集的质量，能够获得了大量的、均匀的p a r e t o 最优解；针对实际 应用中的多目标优化问题一般都含有约束条件这一情况，提出了一种基于群体分 类的复杂约束条件多目标优化遗传算法，该算法对群体多样性问题进行了重点的 研究，采用k 均值聚类分析运算来解决群体多样性问题，该算法将整个群体划分 为四个子群体，并赋予适当的适应值，从中体现最优保存策略，大量的计算机仿 真计算表明，该算法不仅能得到分布广泛的、均匀的p a r e t o 最优解，而且进化速度 快，通常只需1 0 - 4 0 代即可达到很好的优化效果。 图2 2表1参4 1 关键词：遗传算法，多目标优化，p a r e t o 最优解，聚类分析 中图分类号：t p 3 0 1 6 a b s t r a c t i nv i e wo fi m p o r t a n c eo fm u l t i o b j e c to p t i m i z a t i o ni ne n g i n e e r i n g , e c o n o m y , m a n a g e m e n t ，m i l i t a r ya n ds oo r l ，t h er e s e a r c ho nm u l t i o b j e c to p t i m i z a t i o nh a sb e e n p a i dm o r ea n e n t i o n ，i th a sd e v e l o p e di n t oan e wb r a n c ho fs c i e n c ea n dd e m o n s t r a t e d p o w e r f u lv i t a l i t y i na p p l i c a t i o n 。t h eg e n e t i ca l g o r i t h mi s ag l o b a lo p t i m i z a t i o n , a u t o - a d a p t e d ，p r o b a b i l i t ys e a r c ha l g o r i t h mw h i c hu s e st h ee x p e r i e n c eo fb i o l o g i c a l n a t u r a ls e l e c t i o na n dg e n e t i cm e c h a n i s mf o rr e f e r e n c e ，o w i n gt oi t su n i q u es u p e r i o r i t y a n dr o b u s t n e s si ns o l v i n gt h ec o m p l e xs y s t e mo p t i m i z a t i o n ，i tb e c o m e sav e r ye f f e c t i v e m e t h o di ns o l v i n gm u l t i - o b j e c to p t i m i z a t i o np r o b l e m s t h i sp a p e rd w e l l so np r e s e n ts i t u a t i o no ft h er e s e a r c h ，b a s i c p f i n c i p l c s ， r e p r e s e n t a t i v ea l g o r i t h m a b o u tt h em u l t i - o b j e c to p t i m i z a t i o n ，i ta l s o p r e s e n t s t h e m a t h e m a t i c a lt h e o r ya n di m p l e m e n t a t i o nt e c h n o l o g yo fg e n e t i ca l g o r i t h m , i ts t u d i e s s o m ep r o b l e m sw h i c hh a v en o tb e e ns o l v e di nm u l t i o b j c c to p t i m i z a t i o n g e n e t i c a l g o r i t h m 。t h r o u g hr e s e a r c ho fe l i t i s ts t r a t e g y , t h ep a p e rp r e s e n t s am u l t i - o b j e c t o p t i m i z a t i o ng e n e t i ca l g o r i t h mb a s e do l id a t aw a r e h o u s eo fp a r e t oo p t i m a ls o l u t i o n s ，t h e a l g o r i t h mp r e s e r v e st h ei n d i v i d u a l so fp a r e t oo p t i m a ls o l u t i o n sf r o me a c hg e n e r a t i o ni n t h ed a t aw a r e h o u s e ，i te l i m i n a t e st h es a e n eo rs i m i l a ri n d i v i d u a l si st h ed a t aw a r e h q n s e b ym e a s u r i n gt h ed i s t a n c eb e t w e e nt w oi n d i v i d u a l s ，n o to n l yt h en e wa l g o r i t h m e n h a n c e dt h ep e r f o r m a n c eo fa l g o r i t h m ，b u ta l s oi ti m p r o v e st h eq u a l i t yo fs o l u t i o n s ，i t c a l lo b t a i nt h em a s s i v ea n dw e l l d i s t r i b u t e dp a r e t oo p t i m a ls o l u t i o n s i nv i e wo ft h e c o n s t r a i n tc o n d i t i o ni nt h ea p p l i c a t i o no fm 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 e p a p e rp r e s e n t sam u l t i - o b i e c to p t i m i z a t i o ng e n e t i ca l g o r i t h mw i t hc o m p l i c a t ec o n s t r a i n t s b a s e do np o p u l a t i o nc l a s s i f i c a t i o n ，t h i sa l g o r i t h ml a y ss p e c i a ls t r e s so np o p u l a t i o n d i v e r s i t y , a n ds o l v e si tu s i n gk - m e a n sc l u s t e r i n ga n a l y s i s , i td i v i d e st h ep o p u l a t i o ni n t o f o u rc l a s s e s ，t h ed i f f e r e n tp o p u l a t i o na l eg i v e nt h ed i f f e r e n tf i t n e s s ，s oi tc a l le m b o d y e l i t i s ts t r a t e g y al a r g en u m b e ro fc a l c u l a t i o n su s i n gt h ec o m p u t e ri n d i c a t et h a tn o to n l y t h ea l g o r i t h mc a ng e tt h em a s s i v ea n dw e l l - d i s t r i b u t e dp a r e t oo p t i m a ls o l u t i o n s ，b u ta l s o t h ee v o l u t i o nr a t ei se x t r e m e l yq u i c k , i tc a no b t a i ne x t e n s i v ep a r e t oo p t i m a ls o l u t i o n s e a s i l yo n l y1 0 4 0g e n e r a t i o n so rs o f i g u r e2 2 t a b l e1r e f e r e n c e4 1 k e y w o r d s ：g e n e t i ca l g o r i t h m ，m u l t i - o b j e c to p t i m i z a t i o n ，p a r e t oo p t i m a ls o l u t i o n s ， c l u s t e r i n ga n a l y s i s c b c n ：t p 3 0 1 ，6 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果据我所知，除了文中特别加以标注和致谢的地方 以外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得塞邀理王太堂或其他教育机构的学位或证书而使用过 的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示谢意。 学位论文作者张茸啦呲蝣j 月日 学位论文版权使用授权书 本学位论文作者完全了解塞徼垄王太堂有保留、使用学位论文的 规定，即：研究生在校攻读学位期间论文工作的知识产权单位属于立 丝垄三太堂。学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人授权安徽理工大学可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印，缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论 文在解密后适用本授权书) 学位论文作者 导师签名： 签名： 、 1 午 蝴、签字日期： u 1 年6 月i 日 签字日期：年月f 日 1 崎 l言 引言 在工程技术、经济、管理、军事和系统工程等领域大量地存在着一类问题， 它们往往可以归结为在某种约束条件下使多个目标同时达到最优，我们称这种含 有多个目标的最优化问题为多目标优化问题。多目标优化是近年来迅速发展起来 的一门新兴学科，它主要研究的是在某种意义下多个数值目标的同时最优化闯题， 自上世纪7 0 年代以来，国内外关于多目标优化的研究越来越多，它已成为一个热 门课题而受到人们广泛的关注和重视。鉴于多目标优化在生产和生活中的重要作 用，可以预计。在不久的将来这一学科不论是在理论研究方面还是在实际应用方 面，均会得到进步的发展。 遗传算法是借鉴生物的自然选择和遗传机制而开发出的一种全局优化自适应 概率搜索算法。遗传算法具有思想简单、易于实现、算法健壮等优点，目前它已 被广泛应用于各类复杂最优化问题。 多目标优化问题是一类复杂的、难以解决的最优化问题，为此人们研究出了 多种求解方法，其中利用遗传算法来解决多目标优化问题是一个非常有效的手段。 目前具有代表性的多目标优化遗传算法有s c h a f f e r 的向量评估多目标优化遗传算 法、f o n s e 虻a 和f l e m i n g 的多目标优化遗传算法、h o r n 和n a f p l i o t i s 的基于小生境p a r c t o 遗传算法以及s f i n i v a s 和d e b 的非支配排序遗传算法等。在实际应用中，它们都有 各自的优缺点，还需要研究人员去加以改进。 本文在总结和吸收前人的研究成果之上，注重于最优保存策略和群体多样性的 研究，分别提出了基于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 最优解运算和个体间的欧氏距离运 算；在基于群体分类的复杂约束条件多目标优化遗传算法中，提出了群体分类的 概念，并利用聚类分析技术来解决群体的多样性问题。为检验这两种算法性能， 分别利用m a t l a b 编程进行了仿真实验，其结果证明了它们的正确性和有效性。这两 种算法在思想上较为新颖独特，对于今后多目标优化遗传算法的研究具有一定的 参考价值。 安徽理，i ：人学硕十论旃一章绪论 第一章绪论 1 1 多目标优化问题的发展简史 最优化问题是人们在日常生活中经常遇到的问题，很久以前，就有学者对该 问题展开研究。按照目标函数的个数可将最优化问题分为两类：单目标优化和多 目标优化，单目标优化指的是单个目标在给定区域上的最优化问题，而多目标优 化则指的是多于一个数值目标在给定区域上的最优化问题。由多目标优化的基本 概念可知，多目标优化问题的最优解与单目标优化问题的最优解有着本质的区别。 1 8 9 6 年，法国经济学家v p a r e t o 正式提出多目标优化问题，他从政治经济学的 角度，把很多不便于比较的目标归纳成多目标优化问题。他给出一种资源配置的 状态：无法改变这种状态使得某一目标得以改善，同时又不损害其它目标，这就 是被后人称之的帕累托最优状态( p a r e t oo p t i m a l i t y ) 。帕累托最优状态意味着资源配 置达到了最大效率，任一种重新配置的行为都会使它的效率降低，而无法使它的 效率更高。这一概念对多目标优化学科的形成和发展产生了重要而深远的影响。 二十世纪五十年代以来，众多学者从不同的角度对多目标优化问题进行了广泛的、 系统的研究：1 9 5 1 年，t c k o o p m a n s 从生产与分配的活动分析中提出了多目标优 化问题，并第一次提出了p a r e t o 最优解的概念；同年，h w k u h n 和a 。w t u c k e r 从数 学规划的角度，给出向量极值问题的p a r e t o 最优解的概念，并研究了这种解的充分 与必要条件；1 9 6 8 年，z 1 0 h n s e n 系统地提出了关于多目标决策模型的研究报告， 这是多目标优化这门学科走向迅速发展的一个转折点。自上世纪七十年代以来， 多目标优化的研究受到广泛关注，有关多目标优化的国际学术会议多次召开，在 理论上不断创新，在应用中硕果累累，多目标优化正式作为一个数学分支得到了 系统她研究l l 】a 1 2 多目标优化问题研究意义 由于现实世界中的大量问题都可以归结为一类在某种约束条件下使多个目标 同时达到最优的多目标优化问题，因此多目标优化问题的研究有着重要的应用价 值。解决多目标优化问题的传统方法是根据各个目标的重要性对其赋予一个权重， 将其转化为单目标优化问题来处理，但是多目标优化问题的解一般来说是一个解 集，通常情况下并不存在类似荦j 目标优化问题那样的纯“最优解”，如用传统方法 来解，得到的结果可能各不相同，因此如何科学地、台理地解决多目标优化问题 已成为一个非常重要的研究课题1 2 l 。近年来，研究多目标优化问题的专家和学者越 安徼理1 人学硕十论文第一章绪论 来越多，它己成为一个热门课题而受到人们的广泛关注。目前为止，多目标优化 在理论上和应用中都取得很多重要成果，其应用范围也越来越广泛，多目标最优 化作为一个工具在解决工程技术，经济、管理、军事和系统工程等领域众多方面 的问题越来越显示出它的强大生命力 1 3 多目标优化问题的研究方向 多目标优化问题的研究方向可归纳为四类：其一为解的概念及其性质的研究。 1 9 5 1 年，h w k u h n 和a 。w t u c k e r 首先引进一种特殊的有效解，称为k 卜真有效解。 1 9 6 8 年，a g g e o f f r i 6 n 对有效解进一步加以限制，界定一种新的解，这种新的解叫 做o r - - 真有效解。1 9 7 7 年，j b o r w e i n 借助于切锥概念引进一种真有效解，被称为b 一真有效解，1 9 7 9 年，h p b e n s o n 借助投影锥也引进一真有效解，称为卜真有效 解，1 9 8 2 年，m t h e n i g 利用闭凸锯又引进一种真有效解，称为h 一真有效解等。 其二为关于多目标规划的解法。这类问题又可分为直接算法和间接算法两种。所 谓直接算法是指像单目标优化那样，针对规划本身直接去求解，而间接算法则指 根据问题的实际背景，将多目标问题转化成单目标问题。其三为对偶问题的研究。 可以将对偶问题分成两大类：l a g r a a g e 对偶和共扼对偶，其中日本学者t a n i n o 以及 e e r o s i n g e r 采l d t l u e 的工作最为突出。第四个研究方向为不可微多目标规划的研 究。近年来国内外学者都非常重视不可微多耳标规划的研究，f h c l a r k e 、a d i o 恐 和j e a u b i n 从不同的角度出发，对非光滑函数的广义梯度进行研究，中国学者史树 中、陈光亚、汪寿阳和董加礼等从不同的侧面对不可微多目标规划进行了大量的 研究，并取得很多重要的成果【l 】o 1 4 多目标优化方法 传统的多目标优化方法的基本思想是将多目标优化问题转化为一个或一系列 的单目标优化问题，通过求解个或一系列单目标优化问题来完成多目标优化问 题的求解。常用的方法有权重系数变化法、目标规划法和约束法等。传统的多目 标优化方法存在一些局限：为了获得p a r e t o 最优解集需多次运行优化，由于各次 优化过程相互独立，往往得到的结果很不一致，这让决策者很难做出有效合理的 决策：另外有些方法对p a r e t o 最优前端的形状较为敏感，不能处理前端的凹部【，】。 鉴于传统的多目标优化方法的局限性，一些学者开始从生物学角度研究如何利用 计算机模拟生物遗传过程去解决多目标优化问题，这就是所谓的多目标优化遗传算 法。目i ； f 具有代表性的多目标优化遗传算法仃s c h a f f e r 的向量评估多目标优化遗传 2 j 芟敬理l ：久学硕十论交第一章绪论 算法、f o n s e c a 和n e m i n g 的多目标优化遗传算法、h o r n 和n a f p l i o t i s 的基于小生 境p a r e t o 遗传算法以及s r i n i v a s 和d e b 的非支配排序遗传算法等。多目标优化遗 传算法种类较多，但其理论体系尚不完善，需要迸一步去研究和探讨。本文将对 最优保存策略、群体多样性以及约束条件处理等方面做深入的研究。 1 5 论文的主要研究内容 本文首先对多目标优化基本概念和遗传算法数学理论进行了详细的介绍和分 析，为了解决群体多样性问题，本文介绍了当前研究人员较为经常使用的聚类分 析方法，并对在复杂约束条件多目标优化问题的研究中所采用的尽均值聚类方法 作重点说明。本文重点研究了以下几个问题： 针对在遗传算法的进化过程中，选择操作、交叉操作和变异操作对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 最优解产 生的破坏，而且进化速度极快，算法稳定。 针对具有复杂约束条件的多目标优化问题，本文在第六章中提出一种基于群 体分类的复杂约束条件多目标优化遗传算法，该算法利用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 最优解，而且进化速度快，通常只需1 0 4 0 代即可达到很好的优化效果。 在本文的最后进行了总结，并指出了有待进一步解决的问题。 3 安徽理i ：人学硕十论文 第二章多目标优化遗传算法 第二章多目标优化遗传算法 2 1 多目标优化问题的数学模型 在实际应用中，人们经常会遇到在多准则或多目标下设计和决策的问题。例 如证券投资问题，投资者为了能获得较高的收益，就需要选择优秀股票进行投资， 一般来说一个优秀股票具有以下特征：业绩好，市盈率较低，成长性高等，但是 通常情况下这些目标是相互冲突的，例如目前国内的钢铁行业上市公司普遍业绩 较好，市盈率也比较低，但钢铁行业不是向阳产业，公司的成长性不高；而一些 中小型公司的虽然成长性高，但业绩较差，市盈率高，因而为了能够选择出一个 优秀股票，做投资决策时就需要在这些目标之间进行某种均衡处理。这种多于一 个数值目标在给定区域上的最优化问题就称之为多目标优化。 为了解决多目标优化问题，就需要为其建立一个通用的数学模型。首先要确 定它的决策变量，一般情况下，可把决策变量看作万维欧氏空间e ”的一个点，也 即： x o i ，z 2 ，工。) e z “ 其次是目标函数，一般地可假设有p 个目标函数且部是关于决策变量的函数， 也就是： ( x ) i 【 ) ，2 g ) ，厶o ) r 最后是它的约束条件，从数学角度来看，约束条件有两种：不等式约束和等 式约束，可以把约束条件定义为册个不等式约束和k 个等式约束： g j o ) 主o , i l 2 ，m h ，0 ) 一o , y 一1 2 ，七 如果所有的目标函数都是求极小值，则多目标优化问题可描述为以下的数学 模型： r a i n f ( x ) = f l ( x ) ，2 ，l g ) i r s u b j e c t t o o f 一1 ，2 ，k g ，s q j 。坛，肌 ( 2 。1 ) z 。“，石2 ，x , ) e x c _ e 4 x ； y 当且仅当t ) y f ，v f - 1 ，2 ，以 x 乏y 当且仅当t 之y f ，v i 一1 2 ，h ，且工j y ，j ，一1 , 2 ，一，n 【定义2 2 】设x r ”是多目标优化模型的约束集，f ( x 1 月一是向量目标函 数，x ，x ，工，x 。若 o 。) t ：) ( v k l 2 ，p ) ，则称解z ，优于解工：。 ) 奠敬理i ：人学硕十论文 第二章多目标优化遗传算法 d 。) s 兀o ：) ( 讹- 1 ，2 ，p ) 并且 。) t 丘o ：) ( 亚- 1 , 2 , ，p ) ，则称解五弱优于解工：。 “，) 术l ( x ：) 且 ：) 丰 0 ，) ( v 七- 1 , 2 ，p ) ，则称解_ 无差别于解 x ：。 【定义2 3 】设x j r 4 是多目标优化模型的约束集，0 ) 月9 是向量目标函 数，工x ，并且x 比x 中的所有其他点都优越，则称z 是多目标极小化模型的 最优解。 由定义可知，多目标优化问题的最优解z 就是使向量目标函数f ( x ) 的每一个 子目标都同时达到最优点的解( 见图1 ) ，显然，在大多情况下，多目标优化问题 的最优解是不存在的。 f 0 xx 图1 多目标优化问题的最优解 f i g lt h eo p t i m a ls o l u t i o no fm u l t i - o b j e c to p t i m i z a t i o n 【定义2 4 ( p a r e t o 最优解) 设z c _ r 4 是多且标优化模型的约束集，f ( x ) e r 是向量目标函数。若z j ，并且不存在比z 更优越性的x ，则称z 是多目标极小 化模型的p a r e t o 最优解，或称非劣解( 见图2 ) 。 f l w 。 | ! e | 2 多目标优化问题的p a r e t o 晟优解 f i 9 2t h ep a r a t oo p t i m a ls o l u t i o n so fm u l t i o b j e c to p t i m i z a t i o n 6 安徽理 ：人学硕十论文 第一：章多目标优化遗传弃法 【定义2 5 1 ( 非劣集与i j i 端) 设x r ”是多目标优化模型的约束集， f ( x ) e r 是向量目标函数。a x 是多目标极小化模型的p a r e t o 最优解集，则a 称为x 的非劣集，y 一，) 称为p a r e t o 最优6 f 圭 。 图3 非劣集与最优前端 f i 9 3 n o n i n f e r i o rs c la n dt h ef r o n t 由上述定义可知1 3 】： 多目标优化问题与单目标优化问题有着本质的区别，一般来说，多目标优 化问题的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 最优解也只由这些最优解所组成，再不包含其它解。所以可以这 么说，p a r e t o 最优解是多目标优化问题的合理的解的集合。 对于实际应用问题，必须根据对问题的了解程度及决策人员的个人偏好， 从多目标优化问题的p a r e t o 最优解集合中挑选一个或多个解作为多目标优化问题 的最优解。所以求多目标优化问题的首要步骤是求出其所有的p a r e t o 最优解。 2 3 多目标优化与遗传算法 多目标优化问题是一个古老的问题，也是一个非常棘手的问题。在现实世界 中，人们更多地遇到的是多目标优化问题，为此一些专家和学者研究出了许多种 求解方法其中利用遗传算法来解决多目标优化问题是一个非常有效的手段，这 是因为： 7 安徽理l ：人学硕t 论文第一章多目际优化遗传筇法 遗传算法具有稳定性和健壮性，算法在运行过程中不易受外界环境变化的 影响，特别适合一些大型的、复杂的系统优化。 对于一些非线性的、多目标的函数优化问题以及组合优化中的n p 完全问 题等，用传统优化方法较难求解或解的质量不太理想，而遗传算法却可以方便地 得到较好的结果。 由于遗传算法是对整个群体所进行的进化运算操作，它着眼于个体的集 合，从多目标优化最优解的定义可知，多目标优化问题的p a r e t o 最优解一般也是 一个集合，所以通过遗传算法来求解多目标优化问题的p a r e t o 最优解不失为一种 有效的手段。 2 4 多目标优化遗传算法的主要任务 多目标优化问题的最优解就是其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 5 求解多目标优化问题的遗传算法 目前已经提出了多种利用遗传算法求多目标优化问题的p a r c t o 最优解的方法， 如权重系数变化法、极大极小法、向量评估法、排序选择法、共享函数法等，它 们各有各的优点，也各有各的限制。本节将对当前一些具有代表性的算法作简单 介绍和评价。 2 5 1 权重系数变化法 权重系数变化法是用于求解多目标优化问题的最早方法。其基本思想为：对 于一个多目标优化问题，若给其各个子目标函数f a x ) ( f - 1 ，2 p ) 赋予不同的权重 m a 一1 ，2 p ) ，其中各w ，的大小代表相应子目标正0 ) 在多目标优化问题中的重要 程度，则各个子目标函数的线性加权和可表示为： 8 安徽理j ：入学硕一 ：论文第章多舀f 永优化遗传葬法 h ( ，o ) ) 一w 1 ，l 仁) + w ：f d x ) + + 。丘o ) - 艺w f f a x ) ( 2 - 4 ) 其中：m 0 ( i - l 2 p ) 且满足薹m - 1 若以这个线性加权和作为多目标优化问题的评价函数，则多目标优化问题就 可转化为单目标优化问题。该算法的主要优点是思想简单、可行以及时间复杂度 低，且有利于决策人员找到他们所需的偏好解，其缺点为：在我们对问题还没有 足够多的了解时，很难给各目标函数确定的、合适的权重系数，另外该算法对p a r e t o 最优前端的形状非常敏感，不能处理前端的凹部。 2 5 2s c h a f f e r 的向量评估多目标优化遗传算法 向量评佶多目标优化遗传算法( v e c t o r e v a l u a t e d g e n e t i c a j 【g o r i t h m ，v e g a ) 的基本思想是：先将群体中的全部个体按子目标函数的数目均等地划分为一些子 群体，对每个子群体分配一个子目标函数，各个子目标函数在其相应的子群体中 独立地进行选择运算，各自选择出一些适应度较高的个体组成一个新的子群体， 然后再将所有这些新生成的子群体合并为一个完整的群体，在这个完整的群体中 进行交叉运算和变异运算，从而生成下一代完整群体，如此这样不断地进行“分 割一并列选择合并? 过程，最终可求出多目标优化问题的p a r e t o 最优解【4 l 【卯。 v e g a 是一种非p a r c t o 法求解多目标优化问题p a r e t o 最优解的算法，这种方 法很容易产生个别予目标函数的极端最优解，而要找到所有目标函数在某种程度 上较好的协调最优解却比较困难。 2 5 3 f o n s e c a 和f l e m i n g 的多目标优化遗传算法 f o n s e c a 和f l e m i n g 提出的多目标优化遗传算法( m 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 m ，m o g a ) 是最具代表性的基于p a r e t o 最优概念的多目标优化的遗传算法， 其基本思想源自于g o l d b e r g 的非支配排序概念：基于“p a r e t o 最优个体”的概念对 群体进行分类，再对群体中的各个个体进行从优到劣排序，然后依照从大到小且 满足线性关系的概率对这些个体进行选择，从而使得排在的面的个体有更多的机 会遗传到下一代群体中。如此这样经过一定代数的循环之后，最终就可求出多目 标优化问题的p a r e t o 最优解。为了评价群体中各个个体的优劣，他们采用了一种排 名方法( r a n k ) 1 6 j ：即在某一代中，某一个体的排名与该个体在当前群体中支配它 的个体数目相致。其排名的计算方法为：在t 代中，将所有不受支配的个体排名 9 安傲理l ：人学硕十论文 第二章多日标优化遗传算法 为1 ，如果个体被该代中p j ”个体所支配，则 r a n k ( x ，r ) t 1 + ( 2 - 5 ) 由于这种排名方法仅仅度量了各个个体之间的优越次序，而未度量各个个体的分 散程度，所以它易于生出很多相似的p a r c t o 最优解，而难于生成分布较为广泛的 p a r e t o 最优解。为了克服这种情况的发生，f o n s c c a 和f l e m i n g 采用了共享函数与小 生境技术来解决种群多样化问题。该方法的主要优点是运行效率高且耜对容易实 现，它的不足就是该方法受小生境大小的影响1 7 】i s l 【9 1 2 5 4 h o r n 和n a f - p l i o t i s 的基于小生境p a r e t o 遗传算法 h o r n 和n a f p l i o t i s 于1 9 9 4 年提出了一种基于小生境p a r c t o 遗传算法( t h e n i c h e d - p a r e t og e n e t i c a l g o r i t h m ，n p g a ) 。该算法在选择操作上没有采用常见的比 例选择，而是采用了一种基于p a r e t o 占优的锦标赛选择策略，并采用小生境技术来 解决种群的多样性问题。其中锦标赛共享选择方法为：从群体中随机选取两个个 体，再从群体中随机选取一个比较集，然后将两个个体分别与比较集中的个体进 行比较，如果其中的一个个体比比较集中的所有个体都优越，而另一个个体都不 比比较集中的所有个体优越，则将这个个体遗传到下一代群体中：如果未能选择 出一个个体，则利用共享函数的概念从随机选取的两个个体中选择出一个小生境 数较小的个体遗传到下一代群体中。该算法的优点是它能得到多种不同的p a r e t o 最 优解，但是由于每次进行选择操作时都需要进行大量的个体之间优越关系的评价 和比较运算，所以使得算法的搜索效率较低【1 0 1 1 1 】。 2 5 5s r i n i v 笛和d e b 的非支配排序遗传算法 s r i n i v a s 和d e b 于1 9 9 4 年提出了非支配排序遗传算法( t h en o n d o m i n a t e ds o r t i n g g e n e t i c a l g o r i t h m ，n s g a ) ，这算法更为直接地体现了g o l d b c r g 非支配排序思想。 其方法为：首先从整个群体找出所有的非劣解个体，将它们放入非支配解集中， 并为它们分配一个原始的适应度，非支配解集中的个体通过适应值共享得到个体 适应度。然后将这一部分个体取出，剩余的个体再采用相同的方法进行分类，将 找出所有的非劣解个体放入非支配解集中，所不同的是此次分配的适应度小于上 次的适应度，直到所有的个体都被分类完毕。这种方法的好处在于最前沿的个体 具有最大的适应度，被选择而遗传到下一代的可能性就越大。该算法能够获得分 布均匀的非劣最优解，但其计算复杂度较高，为o ( m n 3 ) ( m 为目标的个数，为 种群的规模) ，无精英保留策略，且共享适应值需人为预先确定，所以d e b 等人又 安徽理i ：人学硕+ 论文第二章多目标优化遗传算法 提出了带有精英保留策略的第二代n s g a ( n s g a i i ) ，n s g a i i 能够克服n s g a 的缺点，将计算复杂度降低至o ( m n ：) 1 1 2 3 3 】。 2 5 6z i t z l e r 和t h i e l c 的基于e l i t i s t 的多目标演化算法 z i t z l c r 和t h i e l e 于1 9 9 9 年提出了基于e l i t i s t 的多目标演化算法( s t r e n g t hp a r c t o e v o l u t i o n a r y a l g o r i t h m ，s p e a ) ，该算法继承了前人的研究成果，并将精英保留策 略和聚类分析技术运用至多目标优化问题中，取得了良好的优化效果。该算法在 运行过程中同时保留两个群体：主群体和外部非劣群体，其中外部非劣群体是用 来保存和更新算法运行过程中所发现的非劣个体。对于外部非劣群体中的每个个 体i 赋予一个强度值： $ 1 - - - - 焘 o ，1 ( 2 - 6 ) 其中 伪主群体的个数，珂为个体i 基于p a r e t o 在主群体中所支配的个体数，个体f 的 适应值e = 毛；对于主群体中的每个个体j ，其适应值为外部非劣群体中所有支配f 的个体的强度值之和加上1 ，即 2 1 + 艺墨 ( 2 7 ) 其中加1 是为了保证外部非劣群体中的个体适应值一定优于主群体中个体的适应 值。选择操作采用两个体锦标赛选择方法，个体来自于主群体和外部非劣群体。 为了保持群体的多样性和个体分布的均匀性，该算法使用聚类的方法来保持外部 种群的规模。实验证明使用了精英保留策略的s p e a 算法的解集质量高，能够获得 分布均匀的非劣最优解，但其计算效率不高，其计算复杂度为o ( m 。v 3 1 t 3 1 1 3 8 l 。 2 6 多目标优化遗传算法中有待解决的问题 尽管多目标优化遗传算法已成为一个热门的研究课题，但它毕竟是- - r j 新兴 的学科，其发展的时间并不长，许多理论尚需证明，许多方法有待完善，而这些 理论和方法的解决必将推动多目标优化遗传算法更快的发展，进而走向成熟。多 目标优化遗传算法中存在以下问题尚需解决： 2 6 1 最优保存策略问题 在遗传算法的运行过程中，通过对个体进行交叉、变异等遗传操作而不断地 产生出新的个体。虽然随着群体的进化过程会产生出越来越多的优良个体，但由 安敞理i 人学硕十论文第一二章多目标优化遗传算法 于选择、交叉、变异等遗传操作的随机性，它们也有可能破坏掉当前群体中适应 度最好的个体。这是我们不希望发生的，因为它会降低群体的平均适应度，并且 对遗传算法的运行效率、收敛性都有不利的影响。所以，我们希望适应度最好的 个体要尽可能地保留到下一代群体中。为达到这个目的，可以使用最优保存策略 进化模型来进行优胜劣汰操作，即当前群体中适应度最高的个体不参与交叉运算 和变异运算，而是用它来替换掉本代群体中经过交叉、变异等遗传操作后所产生 的适应度最低的个体该策略的实施可保证迄今为止所得到的最优个体不会被交 叉、变异等遗传运算所破坏，它是遗传算法收敛性的一个重要保证条件。但另一 方面，它也容易使得某个局部最优个体不易被淘汰掉反面快速扩散，从而使得算 法的全局搜索能力不强。所以该方法一般要与其他一些方法配合起来使用，方可 有良好的效果。s p e a 算法使用了最优保存策略，取得了较好的优化结果，本文第 五章中提出的基于p a r e t o 最优解数据仓库的多目标优化遗传算法在最优保存策略 方面亦做出了有益的尝试，但这一策略的引入会大大增加算法的时间和空自j 复杂 度，因此如何更好地实现最优保存策略问题是一个有待解决的热点问题1 1 4 1 1 15 1 。 2 6 2 群体多样性问题 群体多样性的维护问题对多目标优化遗传算法的性能会产生重要的影响，这 个问题解决的不好，很易导致算法早熟，从而生成极端最优解，不能获得分布均 匀的p a r c t o 最优解。目前常用的解决方法有共享函数法( 如m o g a 、n s g a 、n p g a ) 和聚类分析技术( 如s p e a ) 等，其共同点是对个体所在局部邻域的拥挤程度进行 考察，运用某种策略来降低邻域中拥挤程度高个体的选择机会，提高邻域中拥挤 程度低的个体的选择机会，从而维持群体的多样性。实验证明了这类方法对于目 标函数较少的多目标优化问题具有良好的优化效果，但是如果决策变量高维、目 标函数众多则会导致收敛慢，甚至不能收敛。因此群体多样性问题是多目标优化 遗传算法中一个尚需解决的非常重要的问题【1 6 3 。