（计算机应用技术专业论文）多目标演化算法及在优化问题中的应用.pdf

摘要 解决现实世界中的许多问题会遇到两种类型的难度；i ) 多个相互冲突 的目标，i i ) 高维复杂的搜索空间。就第一点而言，与单目标优化不同的是 多个相互竞争目标的优化结果是得到一组可行解，一般被称作p a r e t o 最优 解集。由于缺少喜好信息，在折中解中找不到一个解比另一个解更好。就 第二点而言，若使用精确的方法解决多目标优化问题，搜索空闯太大而且 很复杂。因此，需要设计高效的优化策略来解决这两个问题。 演化算法所具有的几个特征很适合解决这类问题，相对于经典的优化 方法而言，演化算法更受欢迎。实际上，自从1 9 8 5 年以来，研究者们已经 提出了许多基于演化计算的多目标优化算法，这些算法能够在一次独立的 运行中同时搜索到多个p a r e t o 最优解。s p e a 2 算法就是其中一种优秀的算 法。s p e a 2 算法是一种新的使用了精英机制的多目标优化演化算法，它采用 了细粒度赋值策略和密度估计技术，整个算法可以快速收敛到p a r e t o 最优 解，并且可以获得很好的分布性和延展性。 遗传算法( g a s ) 是一类基于自然选择和遗传学原理的有效搜索方法， 虽然g a s 通常能在合理的时间内找到问题的满意解，但随着求解问题的复 杂性及难度的增加，提高g a s 的运行速度便显得尤为突出。g a s 具有天然的 并行性，非常适合于在大规模并行计算机上实现，把串行g a s 中的单一群体 分成多个子群体，各子群体之问相互交换信息的粗粒度并行是将g a s 并行 化的最直接方式。 本文结合s p e a 2 算法，设计了一个有效的并行增强p a r e t o 多目标演化 算法( p s p m e a ) 。该算法同时采用了全局并行模型和粗粒度并行岛模型。 在岛模型中，首先将整个群体划分成若干个子群体，在每个子群体中执行遗 传算法的各步骤，并每隔一定的代数交换各子群中的精英个体：在每个子 群体中，个体的评价和遗传操作使用多线程程序设计，各操作是并发进行的， 这是全局并行模型。在演化过程的最后阶段，就能够找到最优个体。在做了 这两种方式的并行化以后不仅可以获得更好的计算性能，在p a r e t o 最优解集 的优化效果上有更显着的改进。 通过连续测试问题和组合测试问题的实验数据对比与分析，精英机制， 群体规模以及子群个体迁移都是影响p s p m e a 算法的关键因素。实验的结 果也表明了p s p m e a 算法是一个高效的并行多目标优化演化算法。 关键宇：遗传算法，多目标优化，并行遗传算法，精英机制，多种群 a b s t r a c t m 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 ：i ) 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 di i ) ah i g h l yc o m p l e xs e a r c hs p a c e o nt h e o n eh a n d ，i n s t e a do fas i n g l eo p t i m a ls 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 t o 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 f p 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 e b 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 d t o o c o m p l e xt o b es o l v e d b 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 n s 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 l lb o t hd i m c u l t i e 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 e f o rt h i sk i n d o fp r o b l e ma n dm a k et 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 e o p t i m i z a t i o n m e t h o d s i n f a c t ， v a r i o u se v o l u t i o n a r y a p p r o a c h e s t 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 nh a v eb e e np r o p o s e ds i n c e 19 8 5 ，c a p a b l eo f s e a r c h i n gf o rm u l t i p l e p a r e t oo p t i m a ls o l u t i o n s c o n c u r r e n t l y i nas i n g l e s i m u l a t i o nr u n s p e a 2i so n eo f t h ea r to f t h ed a t ea l g o r i t h m s t h ea l g o r i t h mi s 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 n e v o l u t i o n a r ya l g o r i t h mu s i n ge l i t i s m ，i n w h i c hf i n e g r a i n e df i t n e s sa s s i g n m e n ts t r a t e g y , ad e n s i t ye s t i m a t i o nt e c h n i q u e ， a n da ne n h a n c e da r c h i v et r u n c a t i o nm e t h o da r eu s e d t h ea l g o r i t h mc a n c o n v e r g et o t h ep a r e t oo p t i m a ls o l u t i o n sr a p i d l ya n dt h en o n d o m i n a t e d s o l u t i o n sg a i nb e t t e rd i s t r i b u t i o na n ds p r e a d g e n e t i ca l g o r i t h mi sac l a s so fe f f e c t i v ea l g o r i t h m sb a s e do nn a t u r a l s e l e c t i o na n dp r i n c i p l eo fg e n e t i c s t h o u g hg a scanf i n dt h ec o m p r o m i s e s o l u t i o n si nl i m i t e dt i m e ，i m p r o v i n gt h es p e e do fg ai sa ni m p o r t a n ti s s u ew h e n t h ep r o b l e mi sm o r ec o m p l e xa n dd i f f i c u l t g ap o s e si m p l i c i tp a r a l l e l i s ma n di s s u i t a b l ef o ri m p l e m e n t a t i o no nl a r g es c a l ep a r a l l e lc o m p u t e r s d i v i d i n gt h e w h o l ep o p u l a t i o ni n t os u b - p o p u l a t i o n sa n dc o a r s e g r a i n e di s l a n dm o d e lo f e x c h a n g i n gi n f o r m a t i o na m o n gs u b p o p u l a t i o n sa r et h em o s td i r e c tp a r a l l e l m e t h o d q ap a r a l l e l s t r e n g t h p a r e t o 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 ( p s p m e a ) i sp r o p o s e d p s p m e ai sap a r a l l e lc o m p u t i n gm o d e ld e s i g n e df o r s o l v i n gp a r e t o - b a s 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 np r o b l e m sb yu s i n ga n e v o l u t i o n a r yp r o c e d u r e i nt h i sp r o c e d u r e ，b o t hg l o b a lp a r a l l e l i z a t i o na n di s l a n d p a r a l l e le v o l u t i o n a r ya l g o r i t h mm o d e l sa r eu s e d e a c hs u b - p o p u l a t i o ne v o l v e s s e p a r a t e l yw i t hd i f f e r e n tc r o s s o v e ra n dm u t a t i o np r o b a b i l i t y , b u tt h e ye x c h a n g e i n d i v i d u a l si nt h ee l i t i s ta r c h i v e i ne a c h s u b - p o p u l a t i o n ，b r e e d i n ga n d e v a l u a t i o na r ei m p l e m e n t e du s i n gm u l t i t h r e a d e dm e c h a n i s m t h eb e n c h m a r k p r o b l e m sn u m e r i c a le x p e r i m e n tr e s u l t sd e m o n s t r a t et h a tt h ep r o p o s e dm e t h o d c a nr a p i d l yc o n v e r g et ot h ep a r e t oo p t i m a lf r o n ta n ds p r e a dw i d e l ya l o n gt h e f r o n t u s i n gt h ec o n t i n u o u st e s tp r o b l e m sa n d t h ec o m b i n a t i o n a lt e s tp r o b l e m sw e c o m p a r et h et w oa l g o r i t h m s ：p s p m e aa n ds p e a 2 e l i t i s m ，s i z eo ft h e p o p u l a t i o n a n de x c h a n g i n ga m o n g s u b p o p u l a t i o n sa r e t h ek e yi s s u e si n p s p m e a t h er e s u l t sa l s os h o wt h ep s p m e ai sa p r o m i s i n gp a r a l l e l 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 k e yw 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 t i v e o p t i m i z a t i o n ，p a r a l l e l g e n e t i ca l g o r i t h m ，e l i t i s m ，m u l t i s u b p o p u l a t i o n 1 v 1 1 问题的提出 第一章引言 人类改造自然的方案规划与设计过程总体上反映了最大化效益、最小 化成本这一基本优化原则。最大化效益、最小化成本实质上是一个多目标 的优化问题( m o p ) 。效益可能包括多种效益，如经济效益、政治效益与社 会效益等：成本或损失也可能包括生产成本与非生产成本，或与此相关联 的其它目标如环境污染等方面损失。航天器总体设计中的有效载荷、射程、 推力等指标参数的综合是一个典型的多目标的优化问题。控制工程中控制 系统的稳、准、快等时域指标与稳定域度、系统带宽等频域特性的综合问 题也是一个多目标工程优化设计问题。此外还有社会发展与国民经济的中 长远发展计划的优化与决策问题等。一般说来，科学与工程实践中的许多优 化问题大都是多目标的优化与决策问题。 传统的多目标优化方法往往将其转化为各目标之加权和，然后采用单 目标的优化技术。但是，这样做存在几大缺点：a 不同性质的目标之间单位 不致，不易作比较；b 各目标加权值的分配带有较大的主观性；c 优化目 标仅为各目标的加权和，优化过程中各目标的优度进展不可操作；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 最优概念对解进行评估。因此，p a r e t o 最优概念虽然提出来已百 年有余，但却仍无传统算法意义上的相关算法。基于种群操作的演化算法可 以隐并行地搜索解空间的多个解，并能利用不同解之间的相似性来提高其 武汉理上人学硕士学位论文 并发求解问题效率，如果与p a r e t o 最优概念相结合，有可能产生真正基于 p a 似。最优概念的多目标优化的演化算法，实现对非劣最优解集的搜索。 1 。2 本文研究内容 本文基于s p e a 2 算法，设计了一个有效的并行p a r e t o 多目标优化演化算 法框架。该框架同时采用了全局并行模型和粗粒度并行岛模型。在岛模型 中，首先将整个群体划分成若干个子群体，每个子群体并不是完全独立的进 行演化，而是每隔一定的代数，子群体之间相互交换外部集合中的个体，以保 证各予群体中个体的多样性；在每个子群体中，个体的评价和遗传操作是并 发进行的。这是全局并行模型。在演化过程的最后阶段，就能够找到最好的个 体，即最优解。在做了这两种方式的并行化以后对于获得p a r e t o 最优解有很 明显的改善。 在基于j a v a 的e c j ( aj a v a b a s e de v o l u t i o n a r yc o m p u t a t i o na n dg e n e t i c p r o g r a m m i n gr e s e a r c hs y s t e m ) 平台上实现了该并行算法框架，并给出了这 个并行多目标优化演化算法的具体实现方法。 1 3 本文的组织 本文后续章节组织如下：第二章介绍了什幺是多目标优化问题，以及 相关的基本概念和术语，演化算法作为一种现代优化算法也进行了介绍。 第三章介绍了如何使用演化算法进行多目标问题求解，在此对s p e a 和 s p e a 2 算法进行了详细讨论。第四章是全文的重点，首先给出了基于s p e a 2 算法的并行增强p a r e t o 多目标演化算法框架，然后根据不同的并行演化算法 策略，详细讨论了单机上模拟并行算法实现步骤，并给出了基于e c j 平台的 具体实现方案。第五章给出了评价多目标优化演化算法性能的度量方法， 通过一些标准测试函数上的实验数据对比，讨论了算法的优缺点和适用范 围。第六章对该研究工作进行了总结，提出了对进一步研究工作的设想。 武汉理工大学硕士学位论文 第二章多目标优化 一般说来，科学研究与工程实践中许多优化问题大都是多目标优化问 题。多目标优化问题中各目标之间通过决策变量相互制约，对其中一个目标 优化必须以其它目标作为代价，而且各目标的单位又往往不一致因此很难 客观地评价多目标问题解的优劣性。与单目标优化问题的本质区别在于，多 目标优化问题的解不是唯一的，而是存在一个最优解集合，集合中元素称为 p a r e t o 最优或非劣最优。所谓p a r e t o 最优就是，不存在比其中至少个目标好 而其它1 7 1 标不劣的更好的解，也就是不可能通过优化其中部分目标而其它目 标不至劣化。p a r e t o 最优解集中的元素就所有目标而言是彼此不可比较的。 在本章中，首先给出了多目标优化的原则和一些基本概念，然后是对 近似p a r e t o 最优解集的一些传统方法的讨论，尤其是它们的潜在缺点。最后， 演化算法作为一种现代优化方法被提了出来，它拥有的潜在特性特别适合 这一类问题。 2 1 多目标优化 2 。1 。1 基本概念和术语 多目标优化问题是一类很普遍的问题。举个例子，考虑移动电话，汽 车中复杂的硬件软件系统的设计问题，通常，我们要求系统的开销要最小 化，而系统性能要最大化。依赖于这类应用，其它目标例如：可靠性，能 源消耗有时候显得更重要一些。这些问题可以被显示的定义为单独的优化 问题，或是公式化为约束，也就是说系统的大小不能够超过给定的维数。 正式的，我们做如下定义。 d e f 1 ( 多目标优化问题) 一个通常的多目标问题包括一个含有仃个参 数( 自变量) 的集合，个k 个目标函数的集合，一个m 个约束的集合。 目标函数和约束都是自变量的函数。优化的目标是： m a x i m i z e ：y = f ( x ) = ( z 0 ) ， “) ，五( x ) ) s u b j e c t t o ：p ( x ) = ( 8 i ( x ) ，e 2 ( x ) ，口3 ( x ) ) 0 w h e r ex = ( x i , x 2 ，x 。) x ，y = ( y l ，y 2 ，y i ) y 一1 武汉理工大学硕士学位论文 x 是自变量向量，y 是目标向量，x 是自变量空间，y 是目标空问。 约束e ( x ) 0 确定了可行解集。 d e f 2 ( n 7 行集) 可行集x 定义为自变量向量x 的集合，满足约束8 ( z ) ： r = 工x ie ( x ) o 肖，的相也就是，在目标空间的可行区域，被称作： y ，= f ( x ，) = u 。， ，( x ) ) o - 为了不失一般性这里我们考虑的是最大化问题，对于最小化或是混 合的最大最小问题有着相似的定义。 再考虑上面的例子，假设两个目标函数一个是性能p e r f o 珊a i l c e ( ，：) ， 另一个是开销的倒数c h e a p n e s s ( 五) ，这两者都需要在尺寸大小约束( e ，) 下被最大化。那幺一种最优设计可能是能够达到最优性能而开销又最小并 且没有违反尺寸大小约束的设计方案。如果这样一个解存在，我们实际上 要解决一个单目标优化问题。对于任意一个目标的最优解对另个目标也 要是最优的。然而，相应于不同目标函数的单独优化却是大不相同的，这 正是多目标优化问题困难所在。因为这多个目标是相互冲突的并且不能够 被同时优化。相反，我们必须找到满意的折中解。在我们这个例子中， p e r f o n n a n c e 和c h e a p n e s s 是两个相互冲突的目标：高性能的体系结构潜在的 会增加j 干销，而廉价的体系结构通常只能提供较低的性能。依赖于市场需 求，一个中间解( 中间性能，中间开销) 可能是合适的折中解。显然，对 于多目标优化问题，最优的概念需要重新定义。 在单目标优化问题中，按照目标函数可行集是全序的：对于两个解 订，b x ，或者f ( a ) f ( b ) 或f ( b ) f ( a ) 。求解的目标是找到函数，的最大 值所对应的解。然而，当考虑几个目标的时候，情况又发生了变化：一般 而言，不是全序而是偏序的，这一点可以用图1 左边的图解释。由b 点所 代表的解要优于由c 点所代表的解：因为它表示更高的性能和更低的开销。 如果仅仅是在一个目标上进行优化那是很容易的事情，例如c 点和d 点，尽 管开销相等，c 点比d 点有更好的性能。为了在数学上表达这种状况，大小 关系= ， 与单目标问题类似的，也被扩展到多目标向量的方式。 d e f 3 对于任意两个目标向量“和v “2 ”i fv i 1 , 2 ，k ：“，= v ， 武汉理工大学硕士学位论文 “2v i fv i 1 , 2 ，尼) ：u ，v ， “ v i f v 甜v s 和 c ，c d ，b d 。然而 当我们比较b 和e 时，我们不能说哪一个更优，因为丑! e ，倒 b 。尽管与 点e 关联的解更廉价，但是它的性能要比由b 点所表示的解的性能更高。因 此，在多目标优化问题中，按照关系，自变量向量a ，b 有三种可能的关系： f ( a ) 厂( 6 ) ，f ( b ) f ( a ) ，厂( 口) ! f ( b ) a ，( 6 ) ! f ( a ) 。在这里，我们使用下 面的符号和术语来区分不同的情况： d e f 4 ( p a r e t od o m i n a n c e ) 对于任意两个自变量向量a 和b 仃 b ( a d o m i n a t e s b ) i f ，( 日) 厂( 6 ) a b ( a w e a k l y d o m i n a t e s b ) i ff ( a ) f ( b ) a b ( ai si n d i f f e r e n tt ob ) i f ，( 口) ! ，( 6 ) ，( 6 ) ! ，( 口) 基于p a r e t o 大小的概念，我们引出了多目标优化问题的最优标准。仍然 参考图1 1 ，在b ，c ，d ，e 之间a 点是唯一的：它相应的自变量向量a 没有被任 何其它的自变量向量所支配。这也就意味着在某种意义上a 是最优的，在 任何一个目标上它都不能继续得到优化而并没有引起任何其它任何一维目 标上的劣化。这些解被称为p a r e t o 最优解，有时也称作非劣最优解。 d e f 5 ( p a r e t o o p t i m a l h y ) 一个自变量向量x x ，考虑x ，的一个子集爿 如果1 3 a e a ：口 x ，x 被称作是p a r e t o 最优的。 在图l l 中白色的点表示p a r e t o 最优解。它们彼此不同。这点与单目 标问题是大不相同的：它没有一个单独的最优解而是一个最优折中解的集 武汉理j 二人学硕士学位论文 合。在这些解中，没有一个解比另一个更好，除非加入一些喜好信息( 例 如目标的排序) 。 p a r e t o 最优解的全体被称作p a r e t o 最优解集；相应的目标向量构成了 p a r e t o 最优阵面。 d e f 6 ( n o n d o m i n a t e ds e t sa n df r o n t s ) 设a x r 函数p ( a ) 给出了集合 a 未被支配解集，目标向量，( p o ) ) 是对应于集合一的未被支配阵面。集合 x ，= p ( x j ) 被称作p a r e t o 最优解集，集合= f ( x ，) 被称作p a r e t o 最优阵 面。 p a r e t o 最优解集构成了全局最优解。然而，与单目标优化问题一样也存 在局部最优，在某个邻域范围内，多个局部最优解构成了未被支配解集。 这个概念是与d e b 所提出的全局和局部p a r e t o 最优相对应的。 d e f 7 考虑一个自变量向量集合a x ， 集合一被称为一个局部p a r e t o 最优解集： 女口果v a a ：i x x ，：x a a i ix d0 0 集合a 被称作是全局最优解集； 血口果v a a ：! x ，：x a 局部最优和全局最优的区别可以用图2 解释。虚线构成了一个全局 p a r e t o 最优阵面，而实线构成了局部p a r e t o 最优阵面。与后者相关的自变量 就局部而言是互不支配的，因为与a 点相关联的解支配它们中的任何一个。 最后，一个全局的p a r e t o 最优解集不一定包含所有的p a r e t o 最优解并且每一 个p a r e t o 最优解集也是一个局部p a r e t o 最优集。 武汉理：i ：人学硕士学位论文 2 1 2 搜索和决策 图2 - 2 在解决一个多目标优化问题的时候，有两个重要的问题：搜索和决策。 第一个方面指的是优化过程，在这个过程中，可行解集被求解出来称作p a r e t o 最优解集。就单目标优化而言，大并且复杂的搜索空间使得搜索困难，并且 不能使用精确的优化方法例如线性规划。第二个方面强调的是从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 最优解集。这个过程独立于所用的优 化算法。 这一类技术中最有代表性的是加权方法，约束方法，目标规划，最小最 大方法。下面我们主要讨沦前两种方法。 2 2 1 加权方法 最开始的多目标优化方法是将多个目标线性组合从而转化成一个单目 标优化问题： m a x i m i z e ：y = 厂( x ) = w i - z ( x ) + w 2 厶( x ) + + w k - 五( x ) s u b j e c t t ox 乇x j 是权值，为了不失一般性，满足y w j = 1 。在不同权值组合下求解这 个单目标优化问题就可以求得一个解集。 使用一个确定的优化算法，并且所有的权值都为正的条件下，这个方法 可以得至o p a r e t o 最优解。假设一个可行自变量向量口在给定的权值组合下最 大化函数厂，但它并不是p a r e t o 最优解。有一个解向量b 支配辟，为了不失一 般性_ ( 6 ) z ( ) 并且，( 6 ) f x a ) ，i = 2 ，k 。因此f ( b ) f ( a ) ，而这与f ( a ) 是最大值相矛盾的。 这种方法的主要缺点是对于非凸折中p a r e t o 阵面，它不能找到所有的 武汉理工人学硕士学位论文 p a r e t o 最优解。这可以用图1 - 3 解释。对于固定的权值w l w 最大化函数 y = w 1 z ( x ) + w 2 ( z ) 。变形得到 ( x ) = 一旦z ( x ) + 上，在日标空间它 ”2 实际上是一条斜率为一_ ! ! = l 截距为y 的直线。从图形上而言，优化的过程对 w 2w 2 应于向上移动这条直线直到没有可行的目标向量在它之上并且至少有一个 可行的目标向量( 在这里是4 点和d 点) 。点b 和c 从未最大化函数厂。如 果斜率增加，d 点获得更大的函数值f ( 上面的虚线) ；如果斜率减少，一点 比b 点和d 点有更大大的函数值( 下面的虚线) 。 2 2 2 约束方法 这种方法对于凸的p a r e t o 最优阵面，它将k 个目标中的k 一1 个目标转换 成约束。剩下的目标可以任意选择，这样就转化成一个单目标优化问题。 m a x i m i z ey = f ( x ) = ( x ) s u b j e c t t oe 。( 功= z ( x ) 占，( 1 f 七，i h ) x x 在图l 一3 的右侧，约束方法能够获得与折中阵面非凸部分相关联的解。 假设h = 1 并且s ，；r ( 实线) ，考虑扩展约束集的情况下使得由a 点所表示 的解不可行，而b 点所表示的自变量向量在余下的解中最大化了厂。图1 3 也给出了使用这种方法所带来的问题。如果没有恰当的选取下界( f ，= r ) ， 所获得的新的可行集可能为空，也就是说对于这个单目标优化问题找不到一 个解。为了避免这种状况，占。的取值需要事先知道。 武汉理工大学硕士学位论文 2 2 3 经典方法的讨论 传统方法更具吸引力的主要原因是研究得较为深入的一些单目标优化 算法可以使用。对于一些规模较大的问题，几乎没有一个多目标优化方法可 以使用。与此相对应的是：在单目标优化问题中有许多启发式方法能够处理 这种问题，例如随机搜索算法，随机局部搜索算法，模拟退火算法，禁忌搜 索算法等等。 一 一些方法例如：加权方法可能对于p a r e t o 最优阵面的形状很敏感。需要 某一个问题领域的知识而又往往不容易获得。d e b 提到了使用这些方法的潜 在问题，也就是说这些方法的使用是受约束的。而且经典的方法通常要求 多次运行算法获得p a r e t o 最优解集的近似解集。当每次独立运行的时候，由 于不能相互协调而这又可能引起很高的计算开销。而这又依赖于不同的应 用。 近些年来，演化算法逐渐替代了经典的方法：1 ) 它能够搜索较大的空 间并且2 ) 在一次单独的运行中可以得到多个折中解。而且使用演化算法也 比较容易实现。 2 3 演化计算 2 3 i 演化计算 自从电子计算机出现以来，生物模拟便构成了计算机科学的一个组成 部分。其目的一是试图建立一种人工模拟环境，以便使用计算机进行仿真 以更好地了解人类自己和人类的生存空间；另一目的则是从研究生物系统 出发，探索产生基本认知行为的微观机理然后设计成具有生物智能的机器 或模拟系统以解决复杂问题。如神经网络、细胞自动机和演化计算都是从 不同角度模拟生物系统而发展起来的研究方向。演化计算最初具有三大分 支：遗传算法( g e n e t i c ba l g o r i t h m ，简称g a ) 、演化规划( e v o l u t i o n a r y p m g r a m m i n g ，简称e p ) 和演化策略( e v o l u t i o ns t r a t e g y , 简称e s ) 。2 0 世纪9 0 年代初，在遗传算法的基础上又发展了一个分支：遗传程序设计( g e n e t i c p r o g r a m m i n g ，简称g p ) 。虽然它们在算法实现方面具有一些细微差别，但都 具有一个共同的特点，即都是借助生物演化的思想和原理来解决实际问题。 武汉理工大学硕士学位论文 下面我们只对本文中用到的遗传算法( g a ) 进行讨论。 2 3 2 遗传算法的基本内容 1 ) 遗传算法的基本思想 遗传算法是从代表问题可能潜在解集的一个种群开始的，而一个种群则 由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征 的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现 是某种基因组合，它决定了个体的性状的外部表现。因此，在一开始需要实 现从表现型到基因型的映像即编码工作。初代种群产生之后，按照适者生存 和优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问 题中个体的适应度大小挑选个体，并借助于自然遗传学的遗传算子进行组合 交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化 一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解 码，可以作为问题近似最优解。 2 ) 遗传算法的特点 遗传算法不同于传统的搜索和优化方法，其主要的特点在于：白组织、 自适应和自学习性。应用遗传算法求解问题时，在编码方案、适应度函数及 遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索。遗传算 法的这种自组织、自适应特征，使它同时具有能根据环境变化来自动发现环 境的特性和规律的能力。自然选择消除了算法设计过程中的一个最大障碍， 即需要事先描述问题的全部特点，并要说明针对问题的不同特点算法应采取 的措施。因此，利用遗传算法的方法，我们可以解决那些复杂的非结构化问 题。 遗传算法的本质并行性。遗传算法按并行方式搜索一个种群数目的点， 而不是单点。它的并行性表现在两个方面，一是遗传算法是内在并行的，即 算法本身非常适合大规模的问题。它适合在目前所有的并行机或分布式系统 上进行并行处理，而且对并行效率没有太大影响。二是遗传算法的内含并行 性。由于遗传算法采用种群的方式组织搜索，因而可同时搜索解空间内的多 个区域，并相互交流信息。 遗传算法不需要求导或其它辅助知识，只需要影响搜索方向的目标函数 和相应的适应度函数。遗传算法强调概率转换规则，而不是确定的转换规则。 武汉理工大学硕士学位论文 遗传算法可以直接地应用。 遗传算法对给定问题，可以产生许多的潜在解，最终选择可以由使用者 确定。 3 ) 遗传算法基本步骤 ( 1 ) 初始化群体 初始群体中的个体一般是随机产生的。在不具有关于问题解空间的先验 知识的情况下，很难判定最优解的数量及其在可行解空间中的分布状况。因 此我们往往采用在问题解空间均匀采样，随机生成一定数目的个体，然后从 中挑出较好的个体构成初始群体。另外，对于带约束域的问题，还需要判定 随机初始化个体是否在可行区域范围内。 ( 2 ) 终止循环的条件 关于g a 迭代过程如何终止，一般采用设定最大代数的方法。该方法简 单但不准确。 遗传算法包括了三个基本操作：选择、交叉和变异。 ( 3 ) 选择 选择即从当前群体适应值高的个体以生成交配池的过程。目前，主要有 适应值比例选择、b o l t z m a n n 选择、排序选择、联赛选择等形式。 ( 3 1 ) 适应值比例选择 适应值比例选择是最基本的选择方法，其中每个个体被选择的期望 数量与其适应值和群体平均适应值的比例有关，通常采用轮盘赌方式实现。 这种方式首先计算每个个体的适应值，然后计算出此适应值在群体适应值总 和中所占的比例，表示该个体在选择过程中的概率。 对于给定的规模为珂的群体p = 缸，q ，泠体口，芒p 的适应值为厂b ，) ，其 选择概率为 小) = 茄， l - l 该式决定后代种群中个体的概率分布。经过选择操作生成用于繁殖的交 配池，其中父代种群个体生存的期望数目为： p 0 ，) = 聆p 。b ，l ，= l “2 一，九 1 2 武汉理工大学硕士学位论文 当群体中个体适应值的差异非常大时，最佳个体与最差个体被选择的概 率之比也将按指数增长。最佳个体在下一代的生存机会将显着增加，而最差 个体的生存机会将被剥夺。 ( 3 2 ) b 0 1 t z l n a n r l 选择 在群体进化过程中，不同阶段需要不同的选择压力。早期选择压力较小， 我们希望较差的个体也有一定的生存机会，使得群体保持较高的多样性：后 期阶段选择压力较大，我们希望g a 缩小搜索邻域，加快当前最优解改善的 速度。个体选择概率为 型 n ( n 小斋， - ，= l 2 - n e 7 其中，t o 是退火温度。t 随着迭代进行逐渐缩小，选择压力将随之升 高。 【3 3 ) 排序选择 排序选择方式是将群体中个体按其适应值由大到小的顺序排成一个序 列，然后将事先设计好的序列概率分配给每个个体。排序选择与个体的适应 值无直接关系，仅仅与个体之间的适应值相对大小有关。由于排序选择概率 比较容易控制，所以在实际计算过程中经常采用，特别是适用于动态调整选 择概率，根据进化效果适时改变群体选择压力。 ( 3 4 ) 联赛选择 联赛选择的基本思想是从当前群体中随机选择一定数量的个体，将其中 适应值最大的个体保存到下一代。反复执行该过程，直到下一代个体数量达 到预定的群体规模。联赛规模用g 表示，也称为g 联赛选择，般取q = 2 。 为了将联赛选择与排序选择进行对比分析，设q = 2 ，个体选择概率为 驴吉b 一，+ 1 ) 2 - o 一疗】= 吉n + z o 一州= 去( 2 一等一丢) 在应用g a 求解实际问题时，为了动态控制群体选择压力，往往采用排 序选择算子或联赛选择算子，并通过调节参数 叩，q ，使得g a 能够克服模式 欺骗性或者避免陷于局部极值点。 ( 3 ，5 ) 精英选择 武汉理t 大学硕士学位论文 从g a 的整个选择策略来说，精英选择是群体收敛到优化问题的最优解 的一种基本保障。如果下一代群体的最佳个体适应值小于当前群体最佳个 体的适应值，则将当前群体最佳个体或者适应值大于下一代最佳个体适应 值的多个个体直接复制到下一代，随机替代或替代最差的下一代群体中的 相应数量的个体。 ( 3 6 ) 稳态选择 在稳态选择操作中，仅有少量个体按适应值比例选择方法被选择，通过 遗传操作生成新的个体。新的个体放回群体中时，随机替代等量的旧个体， 或者替代等量的最差的旧个体。 ( 3 ，7 ) ( ，z - 口+ a 选择 ，五) 选择是从规模为的种群中选取多个通过重组和变异生成 丑【 ) 个后代然后再从这些后代中选取个最优后代作为新的一代种 群。而1 + 选择是从这些后代与其父体共+ 五个选择个最优的后代。 ( 4 ) 交叉 交叉操作是进化算法中遗传算法具备的原始的独有特征。g a 交叉算子 是模仿自然界有性繁殖的基因重组过程，其作用在于将原有的优良基因遗 传给下一代个体，并生成包含更复杂基因结构的新个体。交叉操作一般分 为以下几个步骤： 从交配池中随机取出要交配的一对个体： 根据位串长度l ，对要交配的一对个体，随机选择 1 ，l l 】中个或多 个的整数k 做为交叉位置。 根据交叉概率儿( 0 。l ，； i d 2 。x 1 2 a 2 j 。瓴x _ - ，) i 。 在这里