（船舶与海洋结构物设计制造专业论文）多目标遗传算法及其在船舶型线优化中的应用.pdf

武汉理工大学硕士学位论文 摘要 最优化问题是一个古老的问题，追求目标的最优化一直是人类的理想。 许多工程优化问题往往性质十分复杂，很难用传统的优化方法来求解。而 且实际的工程优化问题中大多数是多目标优化问题，各子目标之间一般都存在 互相冲突的现象。多目标与单目标优化问题的本质区别是，前者一般是一组或 多组非劣解的集合，而后者只是单个解或一组不连续的解。因此，多目标优化 问题的求解变得困难。 自6 0 年代以来，人们对求解多目标优化问题的兴趣日益增加。一种模仿生 物进化过程的、被称为“进化算法( e v o l u t i o n a r y a l g o r i t h m ) 的随机优化技术应 运而生，而且在解这类优化问题中显示出了优于传统优化算法的性能。而遗传 算法( g e n e t i c a l g o r i t h m ) 是迄今为止进化算法中应用最多、比较成熟、广为人知 的算法。由于其在求解复杂优化问题的巨大潜力及其在工业工程领域的成功应 用，这种算法受到了广泛的关注。经过几十年的发展，多目标遗传算法已经日 趋成熟。 船舶的优化设计是从6 0 年代末期开始逐渐发展起来的一种有效、新的设计 方法。船舶优化设计同许多其他工程问题一样属于多目标优化问题。其中船舶 型线优化设计通常是以应用数学方法对型线进行光顺，而以船体的布置、水动 力和结构性能为目标函数。型线优化设计是一个亟待解决的复杂多目标优化问 题。 本文以多目标遗传算法为主要研究内容，将改进的遗传算法应用于求解多 目标优化问题并用于船舶优化设计是很有意义的。本文介绍了遗传算法的起源、 历程、主要研究方向、遗传算法的基本原理以及改进措施等，编制基于改进的 带精英策略的非支配排序遗传算法( n s g a i i ) 的通用多目标优化软件。本文以 高速方尾船型优化为例介绍了多目标遗传算法在船型的型线优化设计当中的应 用，找到了一种适合n p l1 0 0m o d e la 船型的数学描述方法，在此基础上，以 总阻力系数为优化目标，优化得到阻力性能优良的船舶型线。这说明多目标遗 传算法在船型优化中的应用可以大大地提高了船舶优化设计质量、缩短设计周 期。 关键字：遗传算法，多目标优化，多目标遗传算法，高速排水型方尾船，型线 优化 武汉理工大学硕士学位论文 a b s t r a c t t h eo p t i m i z a t i o np r o b l e mi sa l la n c i e n tq u e s t i o n , a n dt og e tt h eo p t i m i z a t i o n s o l u t i o n sh a sb e e nh u m a n i t y si d e a l h o w e v e r , m o s tp r o j e c to p t i m i z a t i o np r o b l e m sa r es oc o m p l e xt h a ti ti sv e r y d i f f i c u l tt os o l v et h e mw i mt h et r a d i t i o n a lo p t i m i z a t i o nm e t h o d s m o r e o v e rm o s tr e a l p r o j e c to p t i m i z a t i o nq u e s t i o n sa r et h 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 np r o b l e m sw i t h m o r et h e no n e t a r g e t sb e t w e e nw h i c ht h e r ee x i s tc o n f l i c t sm u t u a l l y t h es o l u t i o no f m u l t i o b j e c t i v e so p t i m i z a t i o np r o b l e m si sag r o u po rm a n yg r o u p so fn o n i n f e r i o r s e t , w h i l et h es i m p l et a r g e to n ea l w a y sh a so n l yo n es o l u t i o no ro n eg r o u po f n o l v - c o n t i n u a ls o l u t i o n s ，w h i c hi st h ee s s e n t i a l ，d i s t i n g u i s hb e t w e e nt h e m s oi ti s m u c hm o r ed i f f i c u l tt os o l v et h 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 np r o b l e m s s i n c et h e6 0 s ，p e o p l e si n t e r e s to ns o l v i n gt 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 n q u e s t i o n sh a si n c r e a s e dd a yb yd a y a n dak i n do fr a n d o mo p t i m i z es e a r c hm e t h o d , c a l l e de v o l u t i o n a r ya l g o r i t h m ，r e f e rt ot h ee v o l u t i o nl a wo f b i o l o g i c a lc i r c l ew a sp u t f o r w a r d i ti st e s t i f i e dt h a tt h i sl ( i n da l g o r i t h mi so fm o r ee x c e l l e n tp e r f o r m a n c eo n s o l v i n gt h eo p t i m i z a t i o np r o b l e m st h a nt h et r a d i t i o n a lo n e s a n dt h eg e n e t i c a l g o r i t h mc o n t a i n e di nt h ee v o l u t i o n a r ya l g o r i t h mi sw i d e l yk n o w na n dm o s t l yu s e d i th a sr e c e i v e dt h ew i d e s p r e a da t t e n t i o nb e c a u s eo fi t sg r e a tp o t e n t i a la p p l i c a t i o ni n t h e s o l u t i o no fc o m p l e xo p t i m i z a t i o nq u e s t i o na n da c t u a l p r o j e c to p t i m i z a t i o n p r o b l e m s a f t e rs e v e r a ld o z e n sy e a rd e v e l o p m e n t ，m u l t i o b j e c t i v eg e n e t i ca l g o r i t h m i sa l r e a d yb e i n gm a t u r ed a yb y d a y s h i p s o p t i m i z a t i o nd e s i g ni san e we f f e c t i v ed e s i g nm e t h o dw h i c hs t a r t e df r o m t h el a t e6 0 sa n dw a sd e v e l o p e dg r a d u a n y a sl i k ea so t h e ra c t u a lp r o j e c to p t i m i z a t i o n p r o b l e m s ，i ti sam u l t i - o b j e c t i v e so p t i m i z a t i o np r o n e m a n dw ea l w a y st a k eh u l l s a r r a n g e m e n t , h y d r o d y n a m i cf o r c ea n ds t r u c t u r ep e r f o r m a n c e 鹊o b j e c t i v ef u n c t i o nt og e tt h e o p t i m i z a t i o nb o d yl i n e sd e s c r i b e db ym a t h e m a t i c sm e t h o d s t h el i n eo p t i m i z a t i o nd e s i g ni st h e c o m p l e xm u l t i o b j e c t i v eo p t i m i z a t i o nq u e s t i o nw h i c hu r g e n t l yw a i t st ob es o l v e d t h i sp a p e rs t u d yo fm u l t i o b j e c t i v e g e n e t i ca l g o r i t h ma n dt h ea p p l i c a t i o ni n i i 武汉理工大学硕士学位论文 m u l t i 。o b j e c t i v e so p t i m i z a t i o np r o b l e m sa n do p t i m i z a t i o ns h i pd e s i g n i ti sg r e a t l y s i g n i f i c a t i v e t h i sp a p e r ，f i r s to fa l l ，i n t r o d u c e dt h eo r i g i no fg e n e t i ca l g o r i t h m ，t h e d e v e l o p i n gc o u r s e ，l e a d i n gr e s e a r c hd i r e c t i o n , b a s i cp r i n c i p l ea n dt h ei m p r o v e d m e a s u r e se t c a n dam u l t i o b j e c t i v eo p t i m i z a t i o ns o f t w a r eb a s eo nn s g a i iw a s d e v e l o p e d t h e n , o p t i m i z a t i o nb o d yl i n e sd e s i g no ft h eh i g hs p e e dd i s p l a c e m e n t t r a n s o ms t e ms h i pw a sr e s e a r c h e d i nt h i s p a p e r , a u t h o rf m do n em a t h e m a t i c s d e s c r i p t i o nm e t h o do fb o d yl i n e sw h i c hi ss u i t e df o rn p l10 0m o d e la ，a n dt h e n t a k et h et o t a lr e s i s t a n c ec o e f f i c i e n ta st h eo p t i m i z e dg o a l ，t h eo p t i m i z a t i o no b t a i n sa s h i pl i n e sw i mb e t t e rr e s i s t a n c ep e r f o r m a n c e t h i sp r o v e dt h a tt h ea p p l i c a t i o no f m u l t i o b j e c t i v eg e n e t i ca l g o r i t h mc a ng r e a t l ye n h a n c et h es h i pd e s i g nq u a l i t ya n d s h o r t e nt h ed e s i g nc y c l et i m e 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 eo p t i m i z a t i o n , 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 ng e n e t i ca l g o r i t h m ，h i 曲s p e e dd i s p l a c e m e n tt r a n s o m s t e r ns h i p ，l i n e so p t i m i z a t i o nd e s i g n i i i 独创性声明 本人声明，所呈交的论文是我个人在导师指导下进行的研究工作及取得的 研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教 育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意 研究生( 签名) ：壅垒亟： e t 关于论文使用授权的说明 期： t r p r o q - 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即：学校有 权保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全 部或部分内容，可以采用影印、缩印或其他复制手段保存论文 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：敝导师( 签名) ：脚蚧期：型! 笙 武汉理工大学硕士学位论文 1 1 多目标优化问题 第1 章绪论 多目标优化问题从p a r e t o 正式提出到j o h n s e n 的系统总结，先后经过了六、 七十年的时间。但是多目标优化问题的真正兴旺发达时期，并且正式作为一个 数学分支进行系统的研究，则是2 0 世纪7 0 年代以后的事情了。到现在为止， 多目标最优化不仅在理论上取得很多重要成果，而且在应用领域上也越来越显 示出它的强大生命力。多目标最优化的理论和方法，在诸如经济规划、计划管 理、金融决策、能源开发、工程设计、农业种植、卫生保健以及军事科学等领 域有着大量的应用。多目标最优化作为进行重大决策和解决实际课题的强有力 的手段和有效的工具必将在我国的经济建设中发挥重要的作用【l j 。 目前，多目标优化问题的研究主要集中在以下几个方面：有关解的概念及 其性质的研究、关于求解多目标优化问题的算法研究、关于多目标优化问题的 对偶问题的研究、关于不可微多目标优化问题的研究。 现代科学理论研究和实践中存在着大量优化问题，其中绝大多数优化问题 都涉及多个目标的优化。而且这些目标往往并不是独立存在的，它们是藕合在 一起的互相竞争的目标。它们的竞争性和复杂性使得对其优化变得困难。在多 目标优化中，由于同时考虑多个目标，要使其同时最优一般是不太可能的，于 是转为讨论多目标意义下的另一种“最优解”，即非劣最优解( 亦称有效解，p a r e t o 最优解) 。因为多目标问题中非劣解往往是一解集，每一个非劣解都具有在不同 程度上满足各目标的“优性，但实际应用中只需要一个解。因此，多目标优化 的求解须解决两个问题： ( 1 )如何求得非劣解； ( 2 )非劣解的“优性 如何鉴别，即在众多的非劣解中如何确定一个最 优的或在某种意义下“优性 程度最大的非劣解。 对问题( 1 ) 传统的多目标优化方法是将各子目标聚合为一带权系数的单目 标函数，求解此单目标函数以获得非劣解。现代则多采用遗传算法获得p a r e t o 非劣解集。而问题( 2 ) 即非劣解的评价问题，目前多采用基于偏好的方法，由决 武汉理工大学硕士学位论文 策者根据各目标之间的相对偏好关系，给出一组权系数，但这种方法使非劣解 对偏好非常敏感，而且给出客观权系数也是因难的。 另外，由于现实问题的复杂性，要想精确求得p a r e t o 最优解一般来说是不 经济、不可能的，因而目前有关多目标优化算法方面的主要工作集中在如何求 得p a r e t o 最优集的近似集。相应的，出现了一系列的随机优化技术如进化算法、 禁忌搜索算法、模拟退火算法、蚂蚁算法、微粒群算法等等。其中遗传算法是 迄今为止进化算法中应用最多、比较成熟、广为人知的算法。由于其在求解复 杂优化问题的巨大潜力及其在工业工程领域的成功应用，这种算法受到了广泛 的关注。 1 2 遗传算法的发展及其研究进展 1 2 1 遗传算法的发展历史 遗传算法( g e n e t i ca l g o r i t h m ，简称g a s ) 是受生物进化学说和遗传学说的 启发而发展起来的 2 1 。6 0 年代初，美国m i c h i g e n 大学的j o h nh o l l a n d 教授提出 在研究设计人工自适应的系统时，可以借鉴生物自然遗传的基本原理，模仿生 物自然遗传的基本方法。1 9 6 7 年，他的学生b a g e l e y 在博士论文中首次提出“遗 传算法一词。到了7 0 年代初，h o l l a n d 提出了“模式定理( s c h e m at h e o r e m ) ( 一般认为是“遗传算法的基本原理 ) ，从而奠定了遗传算法的研究理论基础。 1 9 7 5 年h o l l a n d 教授出版了他的著名专著a d a p t a t i o ni n n a t u r ea n da r t i f i c a t i o i l s y s t e m ) ) ，详细的阐述了遗传算法的理论并为其奠定了数学基础。同年，d ej o n g 完成了对遗传算法研究具有指导意义的博士论文“a na n a l y s i so fac l a s so f c e n e t i ca d a p t i v es y s t e m ，他基于模式定理做了大量严格的计算实验，给出明确 的结论；并在此基础上给出了著名的d ej o n g 五函数测试平台，定义了性能评 价标准，并以函数优化为例，对遗传算法的六种方案的性能及机理进行了详细 的实验和分析，他的工作为后续者的范例并为遗传算法以后的广泛应用奠定了 坚持的基础。1 9 8 3 年g o l d b e r g 在他的博士论文中第一次把遗传算法用于实际的 工程系统煤气管道工程优化。从此引起了各学科学者对遗传算法的广泛兴 趣，是遗传算法理论进一步完善，遗传算法的应用领域不断扩展，越来越受到 国际学术界的重视。1 9 8 5 年，在美国召开了第一届关于遗传算法及其应用的国 2 武汉理工大学硕士学位论文 际会议，并且成立了国际遗传算法学会，此后每两年举行一次。1 9 8 9 年，g o l d b e r g 出版了g e n e t i ca l g o r i t h mi ns e a r c h , o p t i m i z a t i o na n dm a c h i n el e a m i n g ) ) ，总结 了遗传算法研究的主要成果，对遗传算法及其应用做了全面而系统的论述。一 般认为，这一时期的遗传算法从古典发展到了现代阶段，该书奠定了现代遗传 算法的基础。1 9 9 1 年，d a v i s 编辑出版了( h a n d b o o ko fg a s ) ) ，其中包括了遗 传算法在科学计算、工程技术和社会生活大量的应用实例，为遗传算法的推广 和普及起到了重要的指导作用。 经过几十年的发展，取得了许多理论进步和丰硕的应用成果。2 0 世纪9 0 年代中期以来在世界范围内已经形成了进化计算的研究热潮，作为人工智能的 重要研究方向和人工生命研究的重要工具，遗传算法的研究备受关注。 近几十年来，国内许多学科及专业的学者也开始研究和应用遗传算法，并 发表了数篇较有影响的综述性文章，对国内学者进一步研究及应用遗传算法起 到了积极作用。近几年来，无论是理论研究还是应用研究，国内的学者取得了 许多成果，使我国在遗传算法研究上处于与国际同一水平线上。 1 2 2 遗传算法与传统优化方法的比较 为解决各种优化计算问题，人们提出了各种各样的优化算法，如单纯形法、 梯度法、动态规划法等。这些优化算法各有各的长处，各有各的适用范围，也 各有各的限制。都存在如寻找的是局部最优解、需要目标函数连续可微、计算 量大，搜索效率低等问题。而g a s 采用了独特的搜索技术，克服了传统搜索方 法存在的不足。 与传统搜索方法相比，g a s 具有以下特点【3 j ： 1 ) g a s 的处理对象不是参数本身，而是对参数集进行了编码的个体。此编 码的操作，使得g a s 可直接对结构对象进行操作。这一特点使得g a s 具有广泛的应用领域。 2 ) g a s 采用同时处理群体中多个个体的方法，即同时对搜索空间中的多个 解进行评估。更形象地说，g a s 使并行的爬多个峰。这一特点使g a s 具有较好的全局搜索性能，减少了陷入局部最优的风险。同时，这使 g a s 本身也十分易于并行化。 3 ) 在标准遗传算法中基本上不用搜索空间的知识和其他辅助信息，而仅用 适应度函数值来评估个体，并在此基础上进行遗传操作。需要指出的是， 3 武汉理工大学硕士学位论文 g a s 的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设 定。对适应度函数的唯一要求是非负。g a s 的这个特点使它的应用范围 大大扩展。 4 ) g a s 不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方 向。 1 3 遗传算法在多目标优化中的应用 遗传算法应用于单目标问题之后的2 0 多年以后，多目标遗传算法逐渐成为 研究热点【4 】。1 0 几年来出现了许多基于进化方法的多目标优化技术。遗传算法 的思想在多目标优化问题中的首次应用可以追溯到1 9 6 7 年，在r o s n e b e g 的研 究中提出了模拟单细胞有机物的化学遗传特性中采用多属性研究方法1 5 j 。虽然 在他的研究中最终只应用了单一属性方法，正是他的研究开创了这个领域的研 究，然而，遗传算法真正应用于多目标优化领域是在9 0 年代初期最早出现的。 遗传算法的操作需要适应度值的信息，那么，对于多目标优化问题来说最 直接的方法就是采用加权的方法将各个目标函数整合成一个单目标优化问题。 从概念上讲，权重和方法可以看作是将多目标优化中采用的方法向遗传算法进 行扩展。该方法给每个目标函数分配权重，然后将加权目标组合为单一目标函 数。事实上，在遗传算法中使用的权重和方法与在传统多目标优化算法中使用 的权重和方法在本质上有很大不同。在多目标优化中，权重和方法用来获得妥 协解。使算法运行的唯一要求是合适的权重向量，但是对于给定问题，通常很 难获得一组合适的权重。在遗传算法中，最初权重和方法用来使遗传搜索向着 p a r e t o 前沿进行。随着进化的进行，权重适应性的重新调整。因此并不一定需 要良好的权重向量来使遗传算法运行。另外，权重和方法在传统多目标优化中 的缺点也可以被遗传算法基于种群搜索和进化搜索的力量削弱。 最近提出了三种权重设置的方法：固定权重方法、随机权重方法和适应性 权重方法【6 】。固定权重方法可以看作是对传统标量化方法的模仿，而随机权重 方法和适应性权重方法用来更全面的利用遗传算法的搜索能力。m u r a t a ， i s h i b u c h i 和t a n a k a 提出了一种随机权重方法( r a n d o m w e i g h ta p p r o a c h ) 来获得目 标使p a r e t o 前沿面的可变搜索方向【7 j i 引。存在两种目标空间中有代表性的搜索 行为：固定方向搜索和多方向搜索。固定权重方法使遗传算法有向着目标空间 4 武汉理工大学硕士学位论文 中一个固定点所在的区域进行采样的趋势，而随机权重方法则使遗传算法具有 可变搜索方向，即在整个p a r e t o 前沿面上进行均匀采样的能力。但是这种方法 忽略了每代p a r e t o 解中可能获得的信息，难以找到所有目标函数在某种程度上 较好的协调解，并且由于选择过程中的每一步都随机给出权重，使其难以生成 分布较广且均匀的p a r e t o 最优解。 早期的多目标遗传算法一般都是遗传算法和一些经典的多目标优化技术的 结合产物，它们普遍效率不高、局限性大、鲁棒性差。之后出现了基于多种群 的v e g a 、基于字典序的方法、基于博弈论的方法等等，这些方法的特点是实 用性差、解的精度不高、不能保证求得最优解。 目前多目标遗传算法的研究热点是采用p a r e t o 机制的多目标优化技术，包 括：m o g a 、n s g a 、n s g a l l 、n p g a 、s p e a 等等。 m o g a 由f o n s e e a 和f l e m i n g 于19 9 3 年提t 9 ，主要思想是个体排序的序 号由当前种群中支配它的个体的数量来决定。m o g a 在多目标优化领域得到了 广泛的应用。 非支配排序遗传算法叫s g a 是由s r i n i v a s 和d e b 于1 9 9 3 年提出的。算 法是基于对个体的几层分级实现的【1 0 1 。n s g a 在现实闯题的求解中得到了广泛 的应用。但是，n s g a 本身存在许多不足之处，使得它在处理高维、多模态等 问题时，难以得到满意的结果。 2 0 0 0 年，d e b 对n s g a 算法进行改进，得到了n s g ai i 算法j ，使运算速 度和算法的鲁棒性进一步提高。为了标定分级快速非胜出排序后同级中不同元 素的适应值，也为使准p a r e t o 域中的元素能扩展到整个p a r e t o 域，并尽可能均 匀遍布，文献【1 2 】提出了拥挤距离的概念，采用拥挤距离比较算子代替需要计算 复杂的共享参数的适值共享方法。 1 4 船舶型线优化设计中的多目标优化问题 船型优化是船舶设计的传统方法之一，其中包括船体型线优化。船体型线 优化通常可以应用数学方法对型线进行光顺，但是必须以船体的布置、水动力 与结构性能的要求为目标函数。所以，实际上船体型线优化是一种多目标优化 问题。 船舶最优化设计就是寻找一个能满足所有限制条件并且使所有的设计指标 5 武汉理工大学硕士学位论文 最为先进的设计方案。最优化方法的优点是能给出最优解，求解速度也较快， 应当指出，最优化设计还需要不断完善。某些设计问题难于用单目标函数概括， 而需要用多目标函数，例如目标函数有时不应限于单位运输成本，还要考虑航 速等。而且这些目标往往并不是独立存在的，它们是藕合在一起的互相竞争的 目标。它们的竞争性和复杂性使得对其优化变得困难。在多目标优化中，由于 同时考虑多个目标，要其同时最优一般是不太可能的。本文采用改进的多目标 遗传算法求解船舶设计多目标优化模型，获得p a r e t o 非劣解集，给设计者提供 最优方案选择。 多目标最优化的理论和方法经过几十年的发展已趋成熟，将多目标最优化 的理论和方法应用到船舶优化设计各方面的应用将大大提高船舶优化设计质量 和缩短设计周期。 1 5 本文所作的工作内容 本文以多目标遗传算法为主要研究对象，找出多目标遗传算法的缺陷，基 于改进的多目标遗传算法，开发一个对求解多目标优化问题较为通用的多目标 优化软件，并对软件进行测试，软件具有较好的图形输入界面。分析船舶优化 设计中的特点和难点，将多目标优化遗传算法应用到船舶优化设计中。 本文以不同航速下总阻力系数为优化目标的高速排水型方尾船舶的型线优 化设计作为算例，介绍了多目标遗传算法在船舶型线优化设计中的应用。型线 优化设计中，研究船型的数学描述是本文的难点。本文在前人的研究基础上， 进一步研究高速排水型方尾船舶的型线描述，以水动力性能作为优化目标对型 线进行优化设计，得到阻力性能优良船型。 6 武汉理工大学硕士学位论文 第2 章多目标优化的基本概念 2 1 多目标优化的数学描述 一般的多目标优化问题由一组目标函数和相关的一些等式和不等式约束组 成，数学上可做如下描述： m i n ( x l ，x2 ，x 。) m i n f ，( xl ，x2 ，x 。) m a x fr + l ( x l ，x2 ，xn ) ( 2 1 ) m a x f 。( x 1 ，x2 ，x 。) s t g ，g ) 0 ，j = 1 ，2 h ，似= 0j = 1 ，2 g j 其中：z ( x ) ，o = 1 , 2 ，m ) 是目标函数；蜀 ) 和办，( x ) 是约束函数： x = ( z 1 ，x 2 ，x n ) r 是，z 维的设计变量； x = 刮x 月”，g ，( x ) o ，h j ( x ) = o ，扛1 ，2 ，p ，歹= 1 ，2 ，g 称为( 2 1 ) 的可 行域。在这个多目标优化问题当中有m ( m 2 ) 个目标函数( 其中，个极小化目 标，m 一，个极大化目标) 和p + q ( p ，q 0 ) 个约束( 其中p 个不等式约束和g 个 等式约束) 。 如果多目标优化问题( 2 1 ) 的目标全部是极小化目标，约束全部是不等 式约束，则得到一个标准的多目标优化模型： m i n f ( x ) = 【z ( x ) ，厶( x ) ，厶( x ) 】2 r ， s t g i s 0 。i = 1 , 2 p ； 定灿1 目标空间、可行域：设计变量x = ( 而，z ：，x n ) r 的一组确定值，对 应n 维的欧式空间r ”的一个点，而相应的厂( x ) 则可对应一个m 维的目标函数空 间尺”的一个点。即向量目标函数厂( x ) 对应的是由设计变量空间r ”到目标函数 空间r ”( 简称r 辨为目标空间) 的一个映射： 7 武汉理工大学硕士学位论文 f ：r “_ 灭4 设计变量、目标函数和约束条件是构成多目标优化问题的主要要素【1 1 【1 2 1 。 设计变量毛，x ，x 。是在工程、系统设计中可以人为控制、并能对设计结 果的性能、属性产生影响的一组参数，设计变量不同的取值对应着不同的设计 方案。一组设计变量往往用向量x = “，x 2 ，z 。) r 表示，并称作问题的一个解。 目标函数是设计结果性能指标的数学表达式，在产品或系统设计中决策者 希望能够同时最优化这些性能指标，它们是设计变量的函数。所有目标函数 石o ) ，以( 功，厶o ) 组成了多目标优化问题( 2 一1 ) 的目标函数f ( x ) 向量。 约束条件给出了设计变量必须满足的限制条件，用含有约束函数的等式或 不等式表示。满足所有约束条件的一组设计变量称为一个可行解，所有的可行 解构成了问题的可行域。 根据目标函数、约束函数和设计变量的特点，多目标优化问题可以分为几 种类型：如果多目标优化问题的所有目标函数和约束函数都是线性的，则它是 线性多目标优化问题，否则如果至少一个目标函数或约束函数是非线性，则它 是非线性多目标优化问题；如果模型中的设计变量是连续的，则它是连续多目 标优化问题，否则就是离散问题【1 2 1 。 由于在实际应用中遇到问题的大多是非线性的，而且非线性问题的解决难 度远大于线性问题，另外大多数的工程设计问题中的设计变量是连续的，所以 多目标优化主要研究如何解决连续、非线性问题。 2 2 多目标优化问题的解 在求解单目标优化问题时，人们寻找的是一个最好的解。在多目标优化问 题中，由于各个目标之间相互矛盾、相互制约，一个目标的改善可能往往是以 其它目标的损失为代价，不可能存在一个使每个目标都达到最优的解，所以多 目标优化问题的解往往是一个非劣解的集合- 呻a r e t o 解集。 在存在多个p a r e t o 最优解的情况下【1 3 1 ，如果没有关于问题的进一步的信息， 那么很难说哪个解更可取，所有的p a r e t o 最优解被认为是同等重要的。所以， 鉴于理想法，重要的是找到尽可能多的关于问题的p a r e t o 最优解。因而，可以 推论在多目标优化中有两个目标： 1 ) 找到一组尽可能接近p a r e t o 最优域的解。 8 武汉理工大学硕士学位论文 2 ) 找到一组尽可能不同的解。 第一个目标在任何优化工作中都是必须的。收敛到不接近真正的p a r e t o 最 优解集的一组解是不可取的。只有当解收敛到近似真正的最优解才能保证它们 的近似最优这一特性。 除了收敛到近似最优域，求得的解也必须稀疏地分布在p a r e t o 最优域。只 有一组多样的解，才能确保有一组在多个目标之间的好的协议解。由于多目标 进化算法需要处理两个空间决策变量空间和目标空间，所以解( 个体) 之间 的多样性能在这两个空间定义。例如，如果两个个体在决策变量空间的欧拉距 离大，那么就说它们在决策变量空间互异。同样，如果两个个体在目标空间的 欧拉距离大，那么就说它们在目标空间互异。尽管对于大多数问题，在一个空 间的多样性常常意味着在另一个空间的多样性，但是并不是对于所有问题都成 立。对于此类复杂的非线性问题，找到在要求的空间有好的多样性分布的一组 解也是一项重要的任务。 2 3 多目标优化的目标占优和p a r e t o 占优 2 3 1 占优基本概念 大多数多目标优化算法在它们的搜索中使用了占优( d o m i n a t e ) 的概念【l 引。 在这里给出占优以及相关术语的定义并介绍在有限个体组成的种群中辨识非劣 解的技巧。 定义2 2 向量序：设彳= 口，a ：，r ，b = p 。，b 2 ，屯r 是m 维欧式空间 r ”中的两个向量。 ( 1 ) 若a ，= b 艇= 1 , 2 ，聊) ，则称向量彳等于向量b ，记作a = b 。 ( 2 ) 若a ，以( f = 1 , 2 ，聊) ，则称向量彳小于等于向量曰，记作a 耋b 。 ( 3 ) 若a ，玩( f = 1 , 2 ，掰) ，并且至少有一个是严格不等式，则称向量彳小 于向量b ，即向量彳优于向量b ，记作a b 。 ( 4 ) 若a ， 6 = 1 , 2 ，聊) ，则称向量彳严格小于向量曰，记作a b 。 定义2 3 绝对最优解、非劣解：s 为多目标优化的可行域，厂( x ) 为多目标 优化的向量目标函数。 若f ( x + ) 三f ) ，锻s ，则称x 为多目标优化的绝对最优解。 9 武汉理工大学硕士学位论文 若八x ) f ( x 一) v x s ，则称x 一为多目标优化的非劣解，且g p a r e t o 最优解。 非劣解也称为有效解( e f f i c i e n ts o l u t i o n ) 、非支配解( n o n d o m i n a t e d s o l u t i o n ) ，p a r e t o 最优解( p a r e t oo p t i m a ls o l u t i o n ) 或p a r e t o 解，它是多目标优化 中一个最基本的概念。从其定义中可以看出，在可行域中找不到比非劣解更好 的解，如果要改善问题的一个目标，必须会导致其它目标的损失。 多目标优化问题的非劣解一般不止一个，由所有非劣解构成的集合称为非 劣解集( n o n - i n f e r i o rs e t ) 。所有非劣解对应的目标函数构成了多目标优化问题的 非劣最优目标域，也称为p a r e t o 前缘( p a r e t of r o n t ) ，在不引起混淆的情况下也 可以称为非劣解集。 2 3 2 用于查找一组非劣解的过程 后面的章节所介绍的多目标遗传算法要求寻找种群的非劣组。算法将种群 分成两组非劣组和劣组。从一组给定的解中寻找一组非劣解的过程在原理 上与从一组实数中寻找最小值的过程相似。下面介绍二种过程，首先介绍一种 较慢的方法，然后介绍一种更有效且更快的方法【1 3 1 【1 5 1 。 方法一：种群中的每个解f 都要与该种群中的所有其它的解进行比较，看解 f 是否劣于种群中的其它的任意一个解。如果发现解i 劣于任意一个解，那么， 解f 不可能属于非劣组。对解f 作一个标记以表明它不属于非劣组；如果没有发 现优于解f 的解，那么解f 属于非劣组。下面的步骤描述了在一组给定的种群大 小为的解尸中辨识非劣组的过程。 第一步：设解计数器i = 1 ，建一个空的非劣组p 。 第二步：对于p 中的一个不同于f 的解，将它与解f 进行比较，看它是否优 于解i 。如果是，则跳到第四步。 第三步：如果尸中还有没参与比较的解，则，= i + 1 且跳到第二步；否则， 设置p = p u f 第四步：f = i + l 。如果i n ，则跳到第二步；否则，终止且得出非劣组p 。 方法二：种群中的每一个解都要与一个部分填充的种群进行比较来实现优 劣分组。辨识非劣组的过程如图2 1 所示。图中 i 表示劣于。 很显然使用以上二种方法中的任一种所求得的非劣解都是种群中的最优 解。因此，这些解也被称作最优非劣组的解。 l o 武汉理工大学硕士学位论文 2 4 本章小结 图2 1 寻找非劣解流程图 本章简单的介绍了多目标优化问题的数学描述以及各类解的基本概念和判 别方法。给出了一种查找多目标优化问题非劣解的过程，并给出了其流程图， 这对本文后续的研究有很好的理论指导意义。 武汉理工大学硕士学位论文 第3 章遗传算法的基本理论 遗传算法的内涵哲理启迪于自然界生物从低级、简单到高级、复杂的漫长 而绝妙的进化过程，借鉴于达尔文的物竞天择，适者生存的自然遗传机理。其 本质是一种求解问题的高效并行全局搜索方法，它能在搜索过程中自动获取和 积累有关搜索空间的信息，并自适应地控制搜索过程以求得最优解。 遗传算法实际上是模拟由个体组成群体的整体学习过程，其中每个个体表 示给定问题搜索空间的一个解点。遗传算法以编码空间代替问题的参数空间， 以适应度函数为评价依据，以编码群体为进化基础，以对群体中个体位串的遗 传操作实现选择和遗传机制，建立起个迭代过程。它从任一初始化的群体出 发，通过随机选择、交叉和变异等遗传操作，使群体一代代地进化到搜索空间 中越来越好的区域，直至抵达最优点。本章将简单的介绍遗传算法的基本理论。 3 1 标准遗传算法基本理论 3 1 1 模式理论 模式定理是遗传算法的基本原理。h o l l a n d 在早期研究中提出了模式( s c h e m a ) 概念以及模式定理( s c h e m a t h e o r e m ) 驯，它是源于对自然界中广泛存在的适应过 程的理论描述框架构造，并进一步应用于人工系统( 算法) 法行为分析。h o l l a n d 认为，g a 操作虽然是直接作用于群体中的个体，实际上隐性完成了更大数量的 模式估计、评价和生成过程。模式定理从进化动力学的角度提出了能够较好地 解释遗传算法机理的一种数学工具，同时也是编码策略、遗传策略等分析的基 础。 采用字符集k = o ，1 二进制编码的位串空间表示为s 工= o ，l 卜，该空间的基 数为l s l i = 2 工。其扩展字符集k = o ，l ， ，其中木是通配符或无关符即可和。或1 匹配。扩展位串空间表示为s e = 0 ，l ，r ，该空间的基数为l s e l = 3 三，则称& 三为 s 的模式空间。显然，包含2 l 个位串的位串空间，对应于3 l 个模式位串的模式 空间。 1 2 武汉理工大学硕士学位论文 定义3 2 1 扩展位串空间s e 工= o ，l ，幸r 中的任何一个点，称为对应于位串空 间s 工= o ，1 卜的一个模式( s c h e m a ) ： h = k l 口s 工，v i ，e je = 口fj ( 3 1 ) 其中a = ( 口。，a ：，吼l h = 。，h ：，h l l q o ，l ，幸) ，i = 1 ，2 ，l ；a s l ， h s 。l 。 定义3 2 2 模式的阶( s c h e m ao r d e r ) 是指模式中所含有0 、l 确定基因位的 个数，计作d ( 日) 。 定义3 2 3 模式的定义长度( d e f i n i n gl e n g t h ) 是指模式中从左到右第一个非 “木”位和最后一位非“木位之间的距离，记作万( 日) 。 定义3 2 4 模式的维数( s c h e m ad i m e n s i o n ) 是指模式中所包含的位串的个 数，也称为模式的容量，记作d ( h ) ，d ( h ) = 2 l - - o ( 小。 定义3 2 5 令m = m ( h ，r ) 为模式日在第t 代群体中所含位串数量，模式在t 代群体中包含的个体位串为 口。，a ：，a 。 ，称为模式h 在群体中的生存数量 ( s u r v i v a l s ) 或者采样样本( s a