（计算机软件与理论专业论文）多目标优化演化算法.pdf

摘要多目标优化演化算法专业：计算机软件与理论硕士生：李红梅指导老师：印鉴教授摘要解决现实世界中的许多问题会遇到两种类型的难度：1 ) 多个相互冲突的目标；2 ) 高维复杂的搜索空间。就第一点而言，与单目标优化不同的是多个相互竞争目标的优化结果是得到一组可行解，一般被称作p a r e t o 最优解集。由于缺少喜好信息，在折中解中找不到一个解比另一个解更好。就第二点而言，若使用精确的方法解决多目标优化问题，搜索空间太大而且很复杂。因此，需要设计高效的优化策略来解决这两个问题。演化计算来源于自然界进化过程的灵感和进化思想的观点。它的潜在并行性及自组织、自适应、自学习的智能特性对于求解多目标优化问题具有巨大的潜力。演化算法所具有的几个特征很适合解决这类问题，相对于经典的优化方法而言，演化算法更受欢迎。实际上，自从1 9 8 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 最优解；约束优化问题；适应度赋值a b s t r a c tm u l t i - o b j e c t i v eo p t i m i z a t i o na l g o r i t h mm a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r yn a m e ：l ih o n g - m e is u p e r v i s o r ：y i nj i a np r o f e s s o ra b s t i 己a c tm a n yr e a l - w o r l dp r o b l e m si n v o l v et w ot y p e so fp r o b l e md i f f i c u l t y ：1 )m u l t i p l e ，c o n f l i c t i n go b j e c t i v e sa n d2 ) ah i g h l yc o m p l e xs e a r c hs p a c e o nt h eo n eh a n d ，i n s t e a do fas i n g l eo p t i m i z a t i o ns o l u t i o nc o m p e t i n gg o a l sg i v er i s et oas e to fc o m p r o m i s es o l u t i o n s ，g e n e r a l l yd e n o t e da sp a r e t o o p t i m a l i nt h ea b s e n c eo fp r e f e r e n c ei n f o r m a t i o n ，n o n eo ft h ec o r r e s p o n d i n gt r a d e o f f sc a nb es a i dt ob eb e t t e rt h a nt h eo t h e r s o nt h eo t h e rh a n d ，t h es e a r c hs p a c ec a nb et o ol a r g ea n dt o oc o m p l e xt ob es o l v e db ye x a c tm e t h o d t h u s ，e f f i c i e n to p t i m i z a t i o ns t r a t e g i e sa r er e q u i r e dt h a ta r ea b l et od e a lw i t h b o t hh a r d n e s s e v o l u t i o n a r yc o m p u t a t i o ng e t si n s p i r a t i o n sa n di d e a sf r o mn a t u r a le v 0 1 u t i o n a r yp r o c e s s e s d u et oi t si n t r i n s i cp a r a l l e l i s m ，s e l f o r g a n i z i n g ，a d a p t a t i o na n ds e l f l e a r n i n gi n t e l l i g e n tp r o p e r t i e s ，e v o l u t i o n a r yc o m p u t a t i o nh a sl a r g ep o t e n t i a lt os o l v em u l t i o b j e c t i v e so p t i m i z a t i o ns o l u t i o n s e v o l u t i o n a r ya l g o r i t h m sp o s s e s ss e v e r a lc h a r a c t e r i s t i c st h a ta r ed e s i r a b l ef o rt h i sk i n d o fp r o b l e ma n dm a k e t h e mp r e f e r a b l et om u l t i - o b j e c t i v eo p t i m i z a t i o nm e t h o d s i nf a c t ，v a r i o u se v o l u t i o n a r ya p p r o a c h e st om u l t i o b j e c t i v eo p t i m i z a t i o nh a v eb e e np r o p o s e ds i n c e1 9 8 5 ，c a p a b l eo fs e a r c h i n gf o rm u l t i p l ep a r e t oo p t i m i z a t i o ns o l u t i o n sc o n c u r r e n t l yi nas i n g l es i m u l a t i o nr u n ，a n dt h ec u r r e n tr e s e a r c hw o r kf o c u s e so nt h ep a r e t oo p t i m a l b a s e dm 0 0e v o l u t i o n a r ya p p r o a c h e s t h ep a p e rd e f i n ea n du s ei n t e n s i v ed e g r e et om a i n t a i nag o o ds p r e a do fs o l u t i o ni nt h ep o p u l a t i o n ，a n dd e f i n et h ef i t n e s so ft h ei n d i v i d u a lt h r o u g hp a r e t os t r e n g t ha n di n t e n s i v ed e g r e e ，a n dg i v e nt h es t i rs t r a t e g y ，w h i c hr e s u l t si nan e wp o p u l a t i o ns i g n i f i c a n t l yi n d i f f e r e n tf r o mt h eo l do n ew h i l ei n h e r i t i n gt h ee v o l u t i o n a r yi n f o r m a t i o nf r o mt h eh i s t o r y ，b yt h i sw a y ，t h ep e r f o r m a n c eo ng l o b a lc o n v e r g e n c ec a nb ee n h a n c e d ，a n dp r e m a t u r ec a nb ea v o i d e ds i m u l t a n e o u s ly t e s tr e s u l t ss h o wt h a tt h en e wa p p r o a c hi sf e a s i b l ea n de f f e c t i v e s o m ed r a w b a c k s ，w h i c he x i s ti nt r a d i t i o n a lm e t h o d st os o l v es i n g l e 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 mw i t hc o n s t r a i n t s ，a r ep r e s e n t e d a n dan e wt e c h n i q u e ，w h i c ht r a n s f o r m so r i g i n a ls i n g l e 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 mw i t h c o n s t r a i n t st om 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 mw i t h o u tc o n s t r a i n t si sg i v e n t h i sm e t h o dp r o v i d e st h ed e c i s i o nm a k e r sm o r et h a no n es o l u t i o n a ne v o l u t i o n a r ym u l t i - o b j e c t i v eo p t i m i z a t i o na l g o r i t h m ( e m o a ) t os o l v et h et r a n s f o r m e dp r o b l e mi sd i s c u s s e di i i中山大学硕士学位论文a n da ni n i t i a le x p e r i m e n ti sg i v e nt o o b yu s i n gc o n s t r a i n t ss t r e n g t h ，an e wr e a l c o d e dg e n e t i ca l g o r i t h mi sp r o p o s e d t h en e wa p p r o a c hi sc o m p a r e da g a i n s to t h e re v o l u t i o n a r yo p t i m i z a t i o nt e c h n i q u e si ns e v e r a lb e n c h m a r kf u n c t i o n s t h er e s u l t so b t a i n e ds h o wt h a tt h en e wa p p r o a c hi sb e t t e rt h a ns o m eo t h e ra l g o r i t h m s m a n yp a r t so fm u l t i o b j e c t i v eo p t i m i z a t i o na l g o r i t h m sa r eu s e dt os o l v em 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 mw i t h o u tc o n s t r a i n t s b u tc o n s t r a i n e dm u l t i o b j e c t i v eo p t i m i z 8 t i o na l g o r i t h mi sv e r yl e s s 。b e c a u s ec o n s t r a i n t sd e p a r t ss e a r c hs p a c ei n t of e a s i b l ea n di n f e a s i b l et w os p a c e 。t h e ni ti sd i f f i c u l tt h a tm u l t i o b j e c t i v eo p t i m i z a t i o na l g o r i t h ms e a r c h sf o rm u l t i p l ep a r e t oo p t i m a ls o l u t i o n sc o n c u r r e n t l yi nas i n g l es i m u l a t i o nr u n t h ep a p e rd e s c r i b e sag e n e t i ca l g o r i t h mw h i c hu s e sc o n s t r a i n td o m a i np r i n c i p l ea n db a s e so n ai n d i v i d u a lr a n k i n ga p p r o a c hw i t h o u tu s i n gp e n a l t yf u n c t i o nm e t h o d s t e s tr e s u l t ss h o wt h a tt h en e wa p p r o a c hi sf e a s i b l ea n de f f e c t i v e k e y w o r d s ：e v o l u t i o n a r ya l g o r i t h m 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 a r e t o o p t i m a ls o l u t i o n s ：c o n s t r a i n e do p t i m i z a t i o n ；f i t n e s sa s s i g n m e n ti v致谢论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：棚日期：刃矿诨【1 月劢日i学位论文使用授权声明本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。保密的学位论文在解密后使用本规定。学位做作者躲如绚导师潞珈髻日期：乃产f 1 月力日日期：砷年l f 月砌日第1 章绪论1 1 引言第1 章绪论在国民经济各部门和科学技术的各个领域中普遍存在着最优化问题，最优化问题就是从所有可能的方案中选择出最合理的、达到最优目标的方案，即最优方案，搜索最优方案的方法就是最优化方法。最优化是一个古老的问题，追求最优目标一直是人类的理想，长期以来，人们对最优化问题进行不断的探讨和研究。最优化方法就是从众多可能的解决方案中选择最佳者，以达到最优目标的科学。早在1 7 世纪，英国伟大科学家n e w t o n开创了微积分时代，已经提出极值问题；后来出现l a g r a n g i a n 乘数法，1 8 4 7 年法国数学家c a n c k y 研究了函数沿什么方向下降最快的问题；1 9 4 9 年前苏联数学家k a h t o p o b n q 提出解决下料问题和运输问题这两种线性规划问题的求解方法。但是由于受到计算手段等历史条件的限制，在2 0 世纪4 0 年代以前，最优化理论还不能形成一门学科。自2 0 世纪4 0 年代以来，由于生产和科学研究突飞猛进地发展，最优化理论和方法日益受到人们的重视，特别是计算机日益广泛应用，使最优化问题的研究不仅成为一种迫切的需要，而且有了求解的有力工具，因此最优化理论和算法迅速发展起来，形成了一门新的应用数学分支学科，已经渗透到生产、管理、商业、军事、决策等各领域。至今已出现线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支，最优化理论和算法在实际应用中正在发挥着越来越重要的作用。随着生产、经济、技术的发展，工程技术、管理人才在实际工作中常常会面临这样的一类问题：在工程设计中，怎样选取参数使得设计既满足要求又能降低成本；在资源分配中，怎样的分配方案既能满足各方面的基本要求，又能获得好的经济效益；在生产计划安排中，选择怎样的计划方案才能提高产值和利润；在原料配比问题中，怎样确定各种成分的比例才能提高质量、降低成本；在城建规划中，怎样安排工厂、机关、学校、商店、医院、住宅和其他单位的合理布局，才能方便群众，有利于城市各行各业的发展。这一类问题的共同点是选出最合理、达到最优目标的方案，这就是工程优化问题。许多工程优化问题性质十分复杂，很难用传统的优化方法来求解。而且实际中山大学硕士学位论文的工程优化问题中大多数是多目标优化问题，目标之间一般都是互相冲突的。多目标与单目标优化问题的本质区别是，前者一般是一组或多组连续解的集合，而后者只是单个解或一组不连续的解，因此，得到一个解集合的近似解比得到单个解的近似解难得多。传统的多目标优化方法往往将其转化为各目标之加权和，然后采用单目标的优化技术。但是，这样做存在几大缺点：一、不同性质的目标之间单位不一致，不易作比较；二、各目标加权值的分配有较大的主观性；三、优化目标仅为各目标的加权和，优化过程中各目标的优度进展不可操作：四、各目标之间通过决策变量相互制约，往往存在相互矛盾的目标，致使加权目标函数的拓朴结构十分复杂。基于传统数学规化原理的多目标优化方法在实际工程优化问题中往往表现出一定的脆弱性，因此，有必要研究高效实用的多目标优化与决策的算法及理论。自6 0 年代以来，人们对求解这类难解问题的兴趣日益增加。一种模仿生物进化过程的、被称为“演化算法”的随机优化技术在解这类优化问题中显示出了优于传统优化算法的性能。目前，演化算法主要包括三个研究领域：遗传算法、演化规划和演化策略。其中遗传算法是迄今为止演化算法中应用最多、比较成熟、广为人知的算法。由于其在求解复杂优化问题的巨大潜力及其在工业工程领域的成功应用，这种算法受到了广泛的注意。1 2 国内外研究现状正是由于多目标问题的广泛存在性与求解的困难性，该问题一直是富有吸引力和挑战性的。研究多目标优化问题一直缺乏一种高效实用的求解方法。好在九十年代开始流行的演化计算为求解多目标优化问题提供了有力的工具。近些年来演化计算界相继提出了不同的多目标演化算法，这些算法的提出引起了众多研究机构的重视，这一方向已成为学术界研究的热点。这一方面的研究在近几年来取得的引人注目的发展与其应用于实际工程中的巨大价值已使得i e e e 进化杂志出版了多目标演化计算理论与技术的专辑。多目标最优化问题的最早出现，应追溯到1 7 7 2 年，当时f r a n k l i n 就提出了多目标矛盾如何协调的问题。但国际上一般认为多目标最优化问题最早是由法国经济学家v p a r e t o 在1 8 9 6 年提出的。当时他从政治经济学的角度，把很多不好比较的目标归纳成多目标最优化问题。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 从对策论的角度，提出多个决策者而且彼此又互相矛盾的多目标决策问题。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 t u e k e r 从数学规化的角度，给出了向量极值问题的p a r e t o 最优解的概念，并且研究了这种解的充分与必要。2第1 章绪论1 9 5 3 年，a r r o n 等人对凸集提出了有效点的概念，从此多目标规化逐渐受到了人们的关注。1 9 6 3 年，l a z a d e h 又从控制论的角度提出多目标控制问题。这期间c h a m e s 、k a r l i n 、k l i n g e r 、p o l a k 、k e e n e y 、g e o f f r i o n 等人先后都作出了较有影响的工作。1 9 6 8 年，z j o h n s e n 系统地提出了关于多目标决策问题的研究报告，这是多目标最优化这门学科开始大发展的一个转折点。多目标最优化问题从p a r e t o 正式提出到j o h n s e n 的系统总结，先后经过了六、七十年的时间。但是，传统的数学规化与模拟退火算法是以单点搜索为特征的串行算法，不可利用p a r e t o 最优概念对解进行评估。1 9 6 7 年r o s e n b e r g 在其博士论文中曾提出可用基于遗传的搜索算法来求解多目标的优化问题，但直到1 9 8 5 年才出现基于向量评估的遗传算法( v e g a ) ，这是第一个多目标演化算法( m o e a ) 。真正引起演化界重视的是1 9 9 0 年后，相继提出了不同的多目标演化算法，f o n s e g a和f l e m i n g 提出多目标遗传算法( m o o a ) ，s r i n i v a s 和d e b 提出非劣分层遗传算法( n s g a ) ，h o r n 和n a f o l i o t i s 也提出了小组决胜遗传算法( n p g a ) ，这些算法已成为多目标演化算法研究的基石。多目标演化算法已成功应用于燃气涡轮泵控制器设计、航空器机构设计及汽车发动机设计等等。当前，多目标优化演化算法作为一个优化工具在解决工程技术、经济、管理、军事和系统工程等众多方面的问题也越来越显示出它的强大生命力。1 3 本文研究的主要内容当把遗传算法应用到多目标优化问题中的时候有三个主要的问题：1 为了指引搜索向p a r e t o 最优解集的方向进行，如何正确的进行适应值赋值和选择。2 为了防止早熟( 过早收敛) 并且要获得较好的分布性和扩展性的非劣最优解集，如何维持群体的多样性。3 如何在求解过程中防止获得的p a r e t o 最优解丢失。本文定义和使用密集度来保持群体中个体的均匀分布，将个体的p a r e t o 强度值和密集度合并到个体的适应值定义中。并提出搅动策略，以提高算法对解空间的遍历性，从而较大程度上避免算法的早熟；对每次搅动得到的部分非劣解个体进行邻域搜索以加快非劣解前沿的进化。最后通过对测试函数的实验，验证了算法的可行性和有效性。这是本文研究的主要内容一。在求解约束函数优化问题时，可以将约束优化问题转换成两目标优化问题，其中一个为原问题的目标函数，另一个为违反约束条件的程度函数。本文定义了个体约束强度指标，提出一种新的多父体杂交算子，根据约束强度值设计出新的实数编码遗传算法。数值实验证实了新方法的可行性、有效性和通用性，其性能中山大学硕士学位论文优于现有的一些演化算法。这是本文研究的主要内容二。至今出现了许多成功的多目标演化算法，但是这些大部分的算法都是用来求解无约束的多目标优化问题，而处理约束问题的多目标演化算法却非常少，主要是由于约束条件将搜索空间分解成可行和不可行两个区域，使得多目标优化算法在收敛至4 真正的p a r e t o 最优区域或保持解的多样性方面存在巨大的困难。本文通过引入约束主导原理，提出一种无需采用罚函数，完全是基于个体排序的求解约束多目标优化问题的演化算法。并通过对测试函数的实验，验证了算法的可行性和有效性。这是本文研究的主要内容三。1 4 本文的组织本文研究的内容安排如下：第一章为绪论，指出实际的工程优化问题中大多数是多目标优化问题，和传统多目标优化方法存在的局限性，由此引入利用演化算法来解决多目标优化化问题的由来，并明确了本论文的研究目的和内容。第二章给出了多目标优化的一些基本概念，介绍了一些传统多目标优化方法和演化算法的基本理论。第三章首先指出了多目标搜索中的关键问题，并提出新的解决方法，通过数值实验，验证了新算法的可行性和有效性。第四章介绍了最为常见的用于求解约束优化问题的惩罚函数法，指出了它的局限性，从而把原问题转化为二目标优化问题。通过定义个体约束强度指标，设计了一种有效的多目标演化算法来求解约束优化问题，并通过数值实验证实了新算法的可行性、有效性。第五章本文通过引入约束主导原理，提出一种无需采用罚函数，完全是基于个体排序的求解约束多目标优化问题的演化算法。并通过对测试函数的实验，验证了算法的可行性和有效性。在结束语中首先对本论文进行总结，然后指出在该领域需要解决和进一步探讨的几项工作。4第2 章多目标优化第2 章多目标优化一般说来，科学研究与工程实践中许多优化问题大都是多目标优化问题( 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 n p r o b l e m ，m o p ) 。多目标优化问题中各目标之间通过决策变量相互制约，对其中一个目标优化必须以其它目标作为代价，而且各目标的单位又往往不一致，因此很难客观地评价多目标问题解的优劣性。与单目标优化问题的本质区别在于，多目标优化问题的解不是唯一的，而是存在一组非劣解( 称为p a r e t o 最优集) 。由于在p a r e t o 最优集中，解之间没有绝对优劣之分，所以要从中选择一个合适的解，还需要参照与问题相关的领域知识。不同的决策者或是同一个决策者在不同的情况下可能倾向于不同的解。因此要找到一组解供决策者选择。求解m o p 的传统方法包括加权法、理想点法、分层序列法等。这些方法的基本思想是把多目标问题转化为单目标问题，然后运用单目标优化技术求解。但这些方法在多目标转化为单目标的过程中加进了算法设计者的主观因素，使得这些方法每次运行找到的那个解，不一定是决策者满意的解。演化算法( e a ) 是一类基于种群的搜索算法，可并行搜索多个目标，在搜索过程中可以将最优解保存到下一代，这些正是求解多目标优化问题所希望的。这一特点使得e a 成为解决m o p 的很自然的选择。运行一次e a ，可能找到多个p a r e t o最优解。在本章中，首先给出了多目标优化的原则和一些基本概念，然后讨论了一些传统方法，尤其是它们的潜在缺点。最后，演化算法作为一种现代优化方法被提了出来，它拥有的潜在特性特别适合这一类问题。2 1 多目标优化2 1 1 多目标优化的一些基本概念多目标优化问题是一类很普遍的问题。举个例子，考虑移动电话，汽车中复杂的硬件软件系统的设计问题，通常，我们要求系统的开销要最小化，而系统性能要最大化。依赖于这类应用，其它目标例如：可靠性、能源消耗有时候显得更重要一些。这些问题可以被显示的定义为单独的优化问题。下面我们正式的给出它的定义。5中山大学硕士学位论文定义1 ：多目标优化问题不失一般性，考虑下列n 个自变量和m 个目标函数的多目标函数优化问题：l i i n i m i z ey = f ( x ) = ( f l ( 2 l ，x 。) 一，f - ( x l ，岛) )其中x = ( x l ，x j xc - r ”，y ：( y l 一，妯y c r ”，x 为决策( 参数) 向量，x 为决策空间，y 为目标向量，y 为目标空间。最小化与最大化问题可以互相转化，因此没作特殊说明，本文都以最小化多目标问题为研究对象。定义2 ：优劣性向量u = ( u 1 曲优于向量v f f i ( v l ，o ( 记为u 。v ) ，当且仅当v i ( 1 m ，满足u i = v 。，并且了j f l ，m 使得u l v l定义3 ：p a r e t o 最优解设a e x ，x 为x 的子集，若x 中不存在优于a 的向量，则称a 为关于子集x 的非劣解或关于子集x 的p a r e t o 最优解，若a 为关于x 的非劣解，则a 简称为非劣解或p a r e t o 最优解。定义4 ：p a r e t o 最优集对于给定的m o p f ( x ) ，p a r e t o 最优集( p ) 定义为：p = xe xi 不存在x ，e x 使得f ( x _ f ( x ) 。定义5 ：p a r e t o 前沿对于给定的m o pf ( x ) 和p a r e t o 最优集( p + ) ，p a r e t o 前沿( p p ) 定义为：p f * = u - - f ( i ) ix e p * 。可见p a r e t o 前沿是p a r e t o 最优集p 在目标函数空间中的像“p ) 。根据以上概念，可以看出，对于给定的m o p 问题，它的p a r e t o 最优集和p a r c t o前沿是确定的。而利用多目标演化算法求解多目标优化问题的目的是：求出p a r e t o最优集，提供给决策者，决策者再根据问题的其他信息和要求确定一个最终的解。从目标函数空间的角度来看，是使所求的非劣向量集尽量与p a r e t o 前沿重合。在许多测试函数中，问题的p a r c t o 前沿是已知的，用它可以检验算法的好坏，但实际问题中p a r e t o 前沿是未知的。2 1 2 搜索和决策在解决一个多目标优化问题的时候，有两个重要的问题：搜索和决策。第一个方面指的是优化过程，在这个过程中，可行解集被求解出来称作p a r e t o 最优解集。就单目标优化而言，大并且复杂的搜索空间使得搜索困难，并且不能使用精6第2 章多目标优化确的优化方法例如线性规划。第二个方面强调的是从p a r e t o 最优解集中选择合适的解。在相互冲突的目标之间做出困难的折中需要人为的决策。依赖于优化和决策这两个过程是如何组合的，多目标优化方法可以被分为三类：在搜索前决策：多目标优化的目标被合成一个单目标问题，它隐式的包含决策者的喜好信息。在决策前搜索：在没有任何喜好信息的情况下进行优化。搜索过程的结果是候选解的集合( 理想的是p a r e t o 最优解集) ，然后由决策者最终做出选择。在搜索的过程中进行决策：在交互优化的过程中，决策者给出一些喜好信息。在优化过程的每一步，求得大量的折中方案，在此基础上，决策者给出更深层的喜好信息以导向更深层的搜索。将多个优化目标组合成一个目标的方法的优点是：可以使用经典的单目标优化策略而不需要大的修改。然而，它要求更深层领域的知识，但这些知识的获取却很困难。举例而一言：在计算机工程设计领域目标是对于所求解的问题获取更深层的知识和可选的解决方案。在决策前进行搜索可以克服这个缺点，但是它排除了决策者的喜好信息，这会增加搜索空间的复杂度。第三类算法是可视化和高维多目标优化问题最优解集展示的问题。将搜索和决策结合起来是一个很有前景的方法，因为它兼有两种方法的优点。在本文中，我们所说的多目标优化方法有以下特征：1 能够搜索大并且高维复杂的空间2 能够产生确切的p a r e t o 最优解集或是它的近似解集这是在搜索的过程中进行决策的第一步，它也是多目标优化领域内更深层研究的基础。2 2 经典多目标优化算法简介目标冲突是多目标优化问题的的共同难题，即不存在这样一个解，它可以使得所有目标同时达到最优。换言之，就是说每一目标的最优解通常是不同的。p a r e t o 最优解的概念在数学中非常有用，它将各个目标之间的冲突降为最小p a r e t o 最优解可以看成是搜索空间中由来自各目标个体最优解而设置的最优解但是这样一个解或许并不能满足决策者的要求，因为他或许希望这个解能满足一些相关目标的优先权。为了实现这一目的，所有的经典方法都采取了向量目标的标量化，把向量优化问题降解为标量优化问题。使用这样的替代方法获得一个隶属于特定约束条件的折衷解。7中山大学硕士学位论文经典多目标优化方法中，通过应用某些当前已知的知识将多目标合成单目标。目标优化可以保证得到一个p a r e t o 最优解，但是结果只是单点解。在实际决策中决策者经常需要多种不同的可选方案。此外如果某些目标有噪声或者存在不连续变量空间，以上方法会变得无效。其中有些方法代价很大，因为它在矢量优化之前需要相关个体的优化知识。这些算法最根本的缺陷是对权重或者标准矢量的敏感性。在把多目标化为单目标之前决策者必须有每一目标的全局先验知识。解的获得很大程度上依赖于权矢量或者标准矢量。因此，不同的情形、不同的权矢量需要，使得同一问题需要求解很多次，现举一个简单的例子说明这一问题。现举一简单的单变量两目标问题f l 说明多目标p a r e t o 优化。v i n c e n t 和g r a n t h a m 以及后来s c h a f f e r 也以同样的目的使用这一问题。这一两目标问题如图1所示：m i n i m i z ef l - - x 2m i n i m i z ef 2 = ( x 2 ) 2图l 问题f l 的属性空间图2 问题f 1 的p a r e t o 最优解空间从图2 所示性能空间，p a r e t o 最优解明显地均匀分布于 0 ，2 】区间变量。x = 0对于f 1 是最优的但是对于f 2 来说就不是那么好；x - - 2 对于f 2 是最优的，但对f l也不是很好。区间内的任何一点都是一个上述两个函数的折衷或平衡的p a r e t o 最优解。但是比如x = 3 却不是p a r e t o 最优解，因为这一点的两个目标函数值都不比x = 2 点的目标值好。在可能的p a r e t o 最优点，在特定情况下决策者或许希望的是某一最优解，但是他还是想知其它的p a r e t o 最优解。传统的方法不能同时发现多个p a r e t o 最优解，例如给上述的所有方法赋予两目标函数相同的加权系数( o 5 ，o 5 ) 、需求标准作为个体最优值，获得的解是x = l 。第2 章多目标优化加权系数( 1 ，o ) 结果是一标量化目标f 1 ，所得解是x = o ，这对n 是最优的，但对于f 2 却不是最优的。同样，加权系数( o ，1 ) 所得解x = 2 是f 2 的最小点。【o ，2 】区间的任何点可以是一有效的折衷解，它可以由一特定的权矢量获得。于是要得到一个特定的解，决策者必须要知道相应的权矢量，这本身就是一个困难的问题。使用经典方法的另外一个问题就是某些目标经常包含不确定的因素。如果目标函数不确定，则权矢量、需求标准矢量的确定就变得更加困难。这一讨论表明传统方法不能方便适用地解决多目标优化问题。一个最实用的方法应该能同时发现p a r e t o 最优解集以便于决策者可以选取最适用于当前问题的最优方案。很多p a r e t o 最优解的知识对于后面的应用也是有用的，尤其是当前情况发生变化是需要运行新的解。因为进化算法以种群代替单个点，多目标p a r e t o 最优解可以在单次运行之后获得。下面小节中将讨论三个通用的多目标优化算法：目标加权法、距离函数法和最小最大法。2 2 1 目标加权法最开始的多目标优化方法是将多个目标线性组合从而转化成一个单目标优化问题：m a x i m i z e ：y = f ( x ) - - w 1 f l ( x ) + w 2 f 2 ( x ) + + 辄 ( x )s u b j e c tt ox x ，x 为可行域；w i 是权值，为了不失一般性，满足yw i = l 。这一方法中最优解由权系数向量w 控制。在不同权值组合下求解这个单目标优化问题就可以求得一个解集。显然改变上式中相应的权系数可以改变目标函数的优先权。从数学意义上讲，所有目标以相同的权值获得的解或许可以使目标冲突降到最小，但是实际情况要求一个满意解，简而言之，必须引入优先权的因素。在大多情况下，首先优化每一目标，进而计算最优解对应的所有的目标函数值。因此可选择出一个依赖于目标重要性的适当的权矢量。使用这一方法的优点是可以控制从而突出目标的重要性，获得的解通常都是一p a r e t o 最优解。2 2 2 距离函数法在这种方法中，通过由决策者确定的需求标准向量实现多目标函数的标量化。由多目标函数得到的单目标函数如下所示：z - 鼽功一哪l r o 如下计算得到：f fz 。( x ) = 生_ ，j = 1 ，2 ，n) i当要优化的目标优先权相同时这一方法能产生最好的折衷解。然而通常可通过引入小范围权重改变每一目标的优先权。通常这也可以引入需求标准矢量化为目标规划技术。2 2 4 惩罚函数法研究人员现在已提出多种演化算法求解约束优化问题，下面主要介绍最为常见的惩罚函数法。惩罚函数即是在目标函数中加上一个反映点是否位于约束集内的惩罚项，来构成一个广义目标函数，从而使得算法在惩罚项的作用下找到原问题的最优解。一个非线性规划问题( n l pn o n l i n e a rp r o g r a n u n i n g ) 一般可表示如下：求目标函数f 的最小化m i n i m i z ef ( x ) ，i = ( x i ，x “，) r ，这里x f c s ，s 为目标函数的搜索空间，f 为可行区域，一般地，s 为r “中的n维长方体：1 ( i ) g x 。g u ( i ) ，1 ( i ) 、u ( i ) 为常数。i = l ，n 。可行区域f 满足m 个附加的不等式和等式约束条件：g j ( x ) 9 0 ，j = l q 和h j ( x ) = 0 ，j = q + l ，ml o第2 章多目标优化对约束极小化问题，惩罚函数应具有这样的性质：对非可行点产生一个正的惩罚，而对可行点则不产生惩罚。通常惩罚函数由解到可行区域的距离来确定。如何设计惩罚函数以有效地惩罚非可行解，对问题的解决至关重要。惩罚函数一般取为个体x 到可行区域的距离的函数，通常用下面定义的厂( 石)构造罚函数：聃= 黑慧竺i ：i i - ：= = ；息mz ( x ) 表示个体x 违反约束的程度，也表示个体工到可行区域的距离aj = l2 2 4 1 静态惩罚函数静态惩罚函数是对每一约束建立一族区间及一些惩罚因子，并根据惩罚函数数值的大小确定其相应的惩罚因子。其描述如下：1 ) 每个约束，确定s 个区间k 。，口l 】，a 。，口：】，0 $ - 1 口，】，以度量惩罚函数值反映的偏离程度；2 ) 对每个约束及偏离程度，创立一个惩罚因子只，i = l ，2 ，s ，j = l ，2 m ；偏离的程度越高，惩罚因子越大。3 ) 随机生成一个初始群体，群体内的个体可以是可行解，也可以是非可行解；4 ) 演化该群体，并并使用下式计算个体的适应值：f i t n e s s ( x ) = f ( x ) + 巳疗( x )，其中巳由乃( x ) 的偏离程度确定。如j = l果( x ) g h ，q 】，则q = 巳。该方法的优点是简单、直接、易于实现。只需稍微对目标函数进行改进，便能较为有效地求解各类约束问题。只是该方法的性能在很大程度上依赖于惩罚因子只，的选取，并且需要确定的参数数目很大。对具有m 个约束的问蹶，需要确定m ( 2 s + 1 ) 个参数。即m ( s + 1 ) 个待确定区间的端点，m s 个惩罚因子。针对一个问题，要去寻求其最优的参数集可能不比约束优化问题本身简单。2 2 4 2 动态惩罚函数静态惩罚函数在算法的演化过程中是静止不变的，而由j o i n e s 和h o u c k 提出的动态惩罚函数却随算法的演化而演化。在t 演化代时，它按下式计算个体的适应1 l中山大学硕士学位论文值：f i t n e s s ( x ) = ，( x ) + ( c 矿( x )这里c 、o 、1 3 是需要调整的参数，皆为正的常数，通常取c = o 5 、n = b = 2 。当演化代数增加时，惩罚项也增加。与静态惩罚函数相比较，该方法需要很少的参数。并且，随着演化的推进，对非可行解的惩罚量将越来越大。该方法的一个弱点是惩罚因子( c r ) 4 的增大过于迅速，以致于搜索很难从局部极小中逃脱出来。有试验表明，当目标函数为二次项时，该方法能获得较好的结果。2 2 4 3 退火惩罚函数针对动态惩罚函数的缺点，m i c h a l e w i c z 等提出退火惩罚函数的策略。其描述如下：将约束分成4 类：线性方程、线性不等式、非线性方程、非线性不等式；1 ) 随机