（信号与信息处理专业论文）基于改进粒子群算法的多目标优化研究.pdf

基于改进粒子群算法的多目标优化研究 摘要 在科学研究与工程实践中存在大量的多目标优化问题，所涉及的领域包括城市运 输、城市布局、能量分配、资本预算等，因此研究解决多目标优化问题的有效算法具有 重大的科学意义和应用价值。由于各目标的改善之问相互冲突，问题的最优解并不唯一， 不存在一个解的所有目标都好于其它的解，这就给解决多目标优化问题带来了一定的难 度。尽管运筹学领域里出现了很多的多目标优化问题解决方法，但问题本身的复杂性使 得高效的优化算法仍然是多目标优化领域的需要。 粒子群算法是近年来发展起来的一种非线性函数优化方法，是模拟鸟群捕食行为的 一种群体智能算法，由于其具有简单、收敛速度快、可调参数少等优点，近年来被频繁 用于解决多目标优化问题。本文在分析了多目标优化理论和粒子群优化算法理论的基础 上，重点研究了求解多目标优化问题的粒子群优化算法的原理。研究内容主要包括： 首先介绍了研究改进粒子群算法和多目标优化问题的目的和意义以及多目标优化 算法的发展过程和研究现状。然后对多目标优化的基本理论、粒子群优化算法的基本原 理进行了分析。为了改善粒子群算法极易收敛到局部最优的不足，提高粒子群算法的收 敛性，在比较了常用的几种变异算子的基础上，提出了一种多尺度变异粒子群算法。算 法采用大小不同尺度的高斯变异机制提高搜索效率。在算法搜索的前期阶段，通过大尺 度变异算子能够完成最好解区域的大致定位，随着迭代次数变异尺度也逐渐减小，最终 在算法搜索的后期阶段，由小尺度变异算子实现对最优解附近区域的深度开采。同时给 出了算法收敛原理。针对多目标优化问题采用新的速度更新公式来维持解的分布性，并 利用拥挤距离排序的方法对外部存储器中的最优粒子进行维护和更新。 最后选取4 个典型b e n c h m a r k 函数优化问题，并同其他带变异操作的p s o 算法进行比 较，仿真结果表明，该算法不仅具有更快的收敛速度，且全局解搜索能力有显著提高。 针对多目标优化问题，选取4 个典型的二维多目标优化函数问题和两个三维的多目标优 化函数问题对算法进行了测试，并同其他算法进行比较，仿真结果表明该算法具有更佳 的优化性能。 关键字：多目标优化；粒子群；多尺度；变异 a bs t r a c t 1 1 1 e r ea r eal o to fm u l t i - o b j e c t i v e o p t i m i z a t i o np r o b l e m si ns c i e n t i f i cr e s e a r c ha n d e n 9 1 n e e r l n gp r a c t i c e t h ef i e l d si n v 0 1 v e c i t yt r a n s p o n a t i o n 、 u r b a nl a y o u t s 、 e n e r g v d l s t r l b u t l o n 、 c 印i t a lo p e r a t i o na n ds o o n t h u s ， d e s i g n i n ge 虢c t i v ea l g o r i t h m sf o r m u l t i o b je c t i v eo p t i m i z a t i o np r o b l e m si sn o to n l yt h eg r e a ti m p o r t a n c ei ns c i e n t i f i cr e s e a r c h ， b u ta l s ot h eg r e a tv a l u ei na p p l i c a t i o n s a st h ei m p l e m e n to f t h eo b je c t i v e so r e nc o n n i c tw i t h e a c ho t h e r ，n ou n i q u eb e s ts o l u t i o nm a y e x i s t ，n os o l u t i o ni ss u p e r i o rt oo t h e rs 0 1 u t i o n sw h e n c o n s i d e r i n ga 1 1t h eo b j e c t i v e s ，s oi tb r i n g ss o m ed i 仟i c u l t i e st os o l v et h em u l t i o b i e c t i v e o p t l m l z a t l o np r o b l e m s d e s p i t et h ec o n s i d e r a b l ed i v e r s i t ) ，o ft e c h n i q u e s d e v e l o p e di nt h e o p e r a t i o n sr e s e a r c hn e l dt ot a c k l et h e s ep r o b l e m s ，t h e i ri n t r i n s i c c o m p l e x i t yc a l l sf o r h i g h - e f b c i e n c ya p p r o a c h e s p a r t i c l es w a 肿 o p t i m i z a t i o na l g o r i t h m( p s o ) i san o n l i n e a r 向n c t i o n o p t i m i z a t i o n t e c 上1 1 1 1 q u eo 士r e c e n td e v e l o p m e n ta n das w a n ni n t e n i g e n c ea l g o r i t h mt os i m u l a t et h eb e h a v i o r o fb i r d s p r e d a t i o nw h i c hi s 行e q u e n t l yu s e dt o s 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 m s b e c a u s eo fi t ss i m p l i c i 吼f a s tc o n v e 唱e n c ea 1 1 d l e s sp a r a m e t e r s b a s e do nt h et h e o r vo f m u l t 卜o b j e c t eo p t i m i z a t i o na n dp s 0 t h ep a p e rf o c u s e so nt h ep r i n c i p l eo fp s 0w h i c hi s u s e dt os o l v i n gm 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 em a i nc o n t e n t si n c l u d e ： 1 r s t l yt h ep a p e ri n t r o d u c e st h ep u 印o s ea n ds i g n i f i c a n c eo fs t u d y i n gm o d i f i e dp s oa n d 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 sa 1 1 d d e v e l o p m e n tp r o c e s sa 1 1 dr e s e a r c hs t a t u so f m u l t l o b j e c t i v eo p t i m i z a t i o n a l g o r i t h m t h e nt h e a n a l y s i s o nt h eb a s i ct h e o r vo f m u l t 卜o b 9 e c t i v eo p t i m i z a t i o np r o b l e m sa n dt h eb a s i cp r i n c i p l e so fp s 0i sg i v e n i no r d e rt o c o n q u e rp a r t l c i es w a 姗o p t i m i z a t i o na l g o r i t h me a s i l y c o n v e 曜e t oal o c a lo p t i m u ma n d i m p r o v ep s 0 sc o n v e 玛e n c ep e r f o m l a n c e ，a r e rc o m p a r i n gs e v e r a lo p e m t o r sw h i c ha r ei n c o m m o nu s e ，ap a r t l c l e s w a 册o p t i m i z a t i o na l g o r i t h mb a s e do nm u l t i s c a l es e l f 二a d a d t i v e e s c a p e1 sp r o p o s e dmt h i sp a p e r t h es p e c i a lm u l t i s c a l eg a u s s i a nm u t a t i o no p e r a t o r sa r e i n t r o d u c e dt om a k ep 叭i c l e s e x p l o r et h es e a r c hs p a c em o r ee 硒c i e n t ly t h el a r g e s c a l e m u t a t l o no p e r a t o r sc a nb eu t i l i z e dt oq u i c k l yl o c a l i z et h e9 1 0 b a lo p t i m i z e ds p a c ea tt h e e a r l y e v o j u t l o n ，t h e nt h en o v e ls t r a t e g yp r o d u c e sas c a l em u t a t i o no p e r a t o rw h i c hg r a d u a l l yr e d u c e d a c c o r d i n gt ot h ec h a n g eo ft h ef i t n e s sv a l u e ，t h es m a l l s c a l em u t a t i o no p e r a t o r s c a n1 m p j e m e n t 1 0 c a la c c u r a t em i n i m as o l u t i o ns e a r c ha tt h e1 a t ee v o l u t i o n c o n v e r g e n c ep r l n c l p l e 1 sg l v e na c t h es a m et i m e t h e ni no r d e rt 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 m s ，an e w v e l o c i t y u p d a t ee q u a t i o ni su s e dt om a i n t a i nt h ed i s t r i b u t i o no ft h es o l u t i o n s t h ea l g o r i t h mm a i n t a i n s t h ea r c h i v e do p t i m a ls o l u t i o n sb a s e do nc r o w d i n gd i s t a n c es o r t i n gt e c l l n l q u e t h ec o m p a r i s o no ft h ep e r f d r r n a n c e o ft h e p r o p o s e da p p r o a c h w i t ho t h e rp s o a l g o r i t h m sw i t hm u t a t i o ne s c a p eo nf o u rt y p i c a lb e n c h m a 出如n c t i o n si se x p e r i m e n t e d t h e e x d e r i m e n t a lr e s u l t ss h o wt h ep r o p o s e dm e t h o dc a n n o to n l ye a e c t i v e l ys o l v et h ep r e m a t u r e c o n v e r g e n c ep r o b l e m ，b u ta l s os i g n i 6 c a n t i ys p e e du pt h ec o n v e r g e n c e t h e ni no r d e r t os o l v e m u l t i o b i e c t i v eo p t i m i z a t i o np r o b l e m s ，c o m p a r i s o n o ft h ep e r f o m a n c eo ft h ep r o p o s e d a p p r o a c hw i t ht h eo t h e ra l g o r i t h m so n 矗v et y p i c a lt w oo b j e c t i v e f u n c t i o n sa n dt w ot 1 1 r e e o b je c t i v en m c t i o n sa r ee x p e r i m e n t e d t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep r o p o s e d a p p r o a c hh a sb e t t e rp e r f o m a n c e k e y w o r d ：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 ；p s o ；m u l t i 。s c a l e ；m u t a t i o n 第l 章绪论 1 1 课题研究的目的和意义 第1 章绪论 在工程实践的各个方面和科学研究的各个领域普遍存在着最优化问题，所谓最优化 问题就是从所有符合要求的候选方案中选出一个最合理的最优方案，寻找最优方案所采 用的方法称为最优化方法。当一个最优化问题只包含一个待优化目标方程时，称这样的 多目标优化问题为单目标优化问题。然而在现实生活中，经常存在在某个特定的区域范 围内使多个目标都尽可能达到决策者满意的问题。比如在设计一款产品时，不仅要考虑 其体积大小，与此同时还需要考虑它的质量、制造成本等因素。改善一个目标有可能会 造成另一个目标的恶化。例如如果增大产品的体积可能会增加其制造成本，降低制造成 本又可能引起其质量的变差。所以就不得不在各目标之间争取平衡。这对于决策者而言， 找到的就不是一个单一的解，而是满足条件的，成员彼此之间无法比较优劣的一个解的 集合，我们把这个解集叫做p a r e t o 最优解集或非支配解集。p a r e t o 最优解集的存在标志 了多目标优化问题与单目标优化问题之间最根本的不同。可以这样理解，p a u r e t o 最优解 是指不会出现这样情况的解：存在至少一个比其它解方案更优的目标，同时其它目标又 不劣于别的解方案。对所有目标来说，p a r e t o 最优解集里的解成员间无法比较各自优劣 性，理由是不会出现一些目标得到优化的同时其它目标又不恶化的情况。由于很多的实 际问题都可以建模成多目标优化问题，并且多目标优化领域中一些悬而未决的问题仍亟 待解决。因此，多目标优化相关问题的研究成为了一个十分有意义的课题。 进化算法是一种启发式搜索算法，它的出现为多目标优化问题的研究提供了新的思 路。从上世纪8 0 年代起进化多目标优化逐渐成为多目标优化领域一个比较热门的研究 方向，至今已经被成功应用于多目标优化领域。以遗传算法作为代表的进化算法的优势 在于它可以处理较大范围的决策空间。算法在决策空间每进化一次就可以得到许多有效 解；另外，对均衡面的连续性和形状不敏感使进化算法具有良好的逼近不连续均衡面的 能力。 但是，进化算法也存在一定的缺陷，如容易陷入局部最优值和计算量过大问题，对 于某些较复杂的问题，编解码操作较为繁琐。群体智能方法作为一种基于迭代的智能计 算方法，能够用来处理大多数最优化问题。其应用领域已包括聚类分析、多目标优化、 模式识别、数据分类及信号与信息处理等许多方面。 哈尔滨工程大学硕士学位论文 k e i l i l e d y 和e b e r h a r t 在1 9 9 5 年提出一类新的优化算法一粒子群优化算法( p s o ) ， 这种新算法启发于鸟类、虫、鱼群等物种的群体捕食行为。由于其简单有效，随后得到 了广泛的关注。粒子群算法作为一种新兴的智能优化算法，吸取了其他算法思想的一些 精华，比如遗传算法( g e n e t i c a l g o r i t h m ，g a ) 的迭代思想。采用了g a 为问题初始化 一组随机解的基本思路，然后通过迭代方式来寻求最优值。 当然，p s o 与g a 也有着本质的区别：p s 0 思想的核心是使群体中的粒子在解空 间中以一定的原则飞行，以搜索最优解；而g a 的核心思想是利用染色体的交叉 ( c r o s s o v e r ) 和变异( m u t a t i o n ) 操作，寻找最优解；p s 0 在复杂度、易实现性和参数 个数上都比g a 有着明显的优势，这也使得它在各个领域都得到了越来越广泛的关注， 并在函数优化、神经网络训练以及模糊系统控制等多个应用领域都已经得到了广泛的应 用。 不可忽视的是，p s 0 作为一种出现时间不长的比较新的算法，还存在着理论基础研 究不足的缺点，并没有真正的形成较为完善的理论体系，应用范围也没有得到足够的拓 展，例如现在p s 0 算法大多是针对于单个目标的优化算法，不符合实际的优化问题基 本都是多目标优化的事实。虽然现在也有一些针对p s 0 运用在多目标优化方面的研究， 但是，往往只是针对二维空间的问题，而一旦p s o 算法应用到相对复杂的高维问题上 时，早熟收敛的问题几乎难以避免，所以如何对p s o 算法进行改进以用于多目标优化， 是p s o 算法的一个研究趋势。 1 2 多目标优化算法的发展与研究现状 作为优化领域的一个重要研究方向，多年来多目标优化问题经过了国内外很多学者 的不断研究，现已经出现了众多的优秀研究成果。 1 2 1 古典的多目标优化方法 古典多目标优化方法的原理是用正系数把各子目标函数合成为一个单目标函数，系 数的取值由决策者进行设置或者由优化方法本身来自适应调整。典型的古典多目标优化 方法有线性加权和法、目标规划法2 1 、约束法【3 】等。古典方法的优点是简单易行，但 由于多目标优化问题的目标函数有可能是非线性、不连续或不可微的，需要事先掌握充 足的关于待优化问题的先验知识。另外，彼此之间独立的求解方式和对于权重值或目标 排列的次序较敏感的性质会导致无法共享信息，而延长算法的运算时间。因此，古典方 法对于相对较复杂的多目标优化问题往往行不通。 第1 草绪论 1 2 2 基于进化算法的多目标优化方法 进化算法( e v o l u t i o n a r ya l g o r i t m ，e a ) 是一种模仿生物自然选择和进化过程的随 机搜索算法，进化算法适于用来处理多目标优化问题的理由在于：一、进化算法采用基 于种群的搜索机制能实现搜索的全面性和多样性，重组操作能够共享各个解彼此问的相 似信息，进行一次进化行为能搜索到许多p a r e t o 最优解。二、进化算法不需要引用许多 的数学相关信息，能处理针对所有形式的目标函数。 早在1 9 6 7 年，r o s e n b e r g 【4 】就提出了将进化搜索机制引入到多目标优化领域，但该 想法并未得到真正实施。直到1 9 8 5 年，s c h a f f e r 提出了向量评估遗传算法( v e g a ) p j ， 这对于采用进化算法处理多目标优化问题具有重要的启发性和指导性意义。1 9 9 0 年以 后，研究者们先后提出的各种多目标进化算法慢慢引起了学术界的广泛关注，如f o n s e c a 和f l e m i n g 提出的多目标遗传算法( m o g a ) 【6 】、d e b 和s r i n i v a s 提出的非劣排序遗传 算法( n s g a ) 【7 】、h o m 和n a f p l i o t i s 提出的小生境p a r e t o 遗传算法( n p g a ) 例等经典 的多目标进化算法。这些算法为采用进化算法解决多目标优化问题奠定了基石，因此被 视为第一代多目标进化算法，它们的显著特点是基于p a l r e t o 支配的个体选择方式和基于 适应度共享的种群多样性保持机制。 从1 9 9 4 年到2 0 0 2 年期间，多目标进化算法的研究开始真正引起了广大学者们的重 视，相关理论成果的数量也随之迅速增加。学者们开始考虑将精英保留策略结合到进化 算法，第二代多目标进化算法也相继被提了出来，具有代表性的研究成果有1 9 9 9 年 z i t z l e r 提出的强度p a r e t o 进化算法( s p e a ) 及其在2 0 0 1 年提出的该算法的改进算法 s p e a i i 2 0 0 0 年k n o w l e s 和c o m e 提出的p a r e t o 存档进化策略( p a e s ) 以及其改 进算法p e s a 和p e s a i i 【l o 】；d e b 等人于2 0 0 2 年对n s g a 算法进行改进，提出了非常 具有代表性的n s g a i i 】算法。精英保留策略作为设计的基本步骤被应用到第二代多 目标进化算法中，一些其他更有效的策略也被提了出来，如采用聚类的方法、拥挤度距 离的方法、空间超网格划分的方法等，使算法的搜索效率也得到了大大改善。 从2 0 0 3 年至今，多目标进化算法先后结合了某些其它的想法和策略，使得多目标 进化算法的研究展现了新的特点，以期获得性能更好和效率更高的算法，这些策略主要 包括协同进化策略、混合策略、量子进化策略、并行策略等；如崔逊学【1 2 1 等人提出通过 加入偏好到各目标之间的方法来设计多目标调和遗传算法；石川【1 3 】等人为了降低运算代 价，在解之间没有采用冗余比较，提出了一种快速多目标进化算法；公茂果，焦李成【1 4 】 等人对多目标进化算法进行了综述；d e b 【b 】等人提出了s 支配的概念并结合进化计算来 h 合尔滨r 程大学硕卜学位论文 求解多目标优化问题。 1 2 3 基于粒子群算法的多目标优化方法 粒子群优化算法( p a r t i c l es w a n l l0 1 ) t i m i z a t i o n ，p s 0 ) 【1 6 是19 9 5 年由e b e r h a n 和 k e n n e d y 共同提出的一种群体智能算法，该算法思想源自于对鸟群捕食过程的研究。粒 子依据对附近环境的适应程度定位到位置更优的区域。每个粒子以某一速度在搜索空间 自由飞行，该速度依据粒子总结自身飞行经验和种群中其它粒子的飞行经验进行动态调 整。p s 0 算法也是基于种群的搜索算法，同样适用于求解多目标优化问题，此外，粒子 自身的记忆能力、彼此间共享信息和互相合作的能力使得学者们尝试通过设计多目标粒 子群优化算法来解决多目标进化算法收敛慢，易陷入局部极值的问题。相对于进化算法 而言，p s o 算法在多目标优化领域的应用研究发展比较晚，2 0 0 4 年，c o e l l oc o e l l o 等人 提出的多目标粒子群算法【1 7j 具有里程碑意义，由此用p s o 算法处理m o p 变成了新的关 注问题。至今比较具有代表性的多目标粒子群算法有：r a y 【1 8 】等在解决多目标优化问题 的过程中结合了p a r e t o 最优的策略和进化计算的想法，并运用拥挤度距离的机制来保持 解的多样性；h u 【1 9 】等人提出了动态邻居的多目标粒子群算法，同时算法采取了字典序 的方法，每次只选择其中一个目标函数来优化；张利彪 2 0 】等人改进了p s 0 算法的全局 最优位置和个体最优位置的选择方式；f i e l d s e n d 和s i n g h 【2 l 】使用“支配树”的方法来保 存搜索过程中的非占优个体，并对粒子的速度进行“扰动”；m e n g 【2 2 1 等人通过协同进化 算子，变异算子及新的选择方式来指导整个迭代过程，提出一种协同进化的多目标粒子 群优化算法；m o s t a 曲i n 和t e i c h 【2 3 】采用“s i g m a 方法来获得粒子的局部最优位置，从 而改善多目标粒子群算法的收敛速度，同时对决策变量使用“扰动”算子；f i e l d s e n d 【2 4 j 采 用外部种群集合大小不固定的办法，把局部搜索算子定义成进化种群与外部种群间的相 互作用，同时引入扰动算子来维持种群多样性。多目标粒子群算法继承了传统粒子群算 法收敛速度快、参数易调节的优点，并且改善了多目标进化算法易陷入局部极值解、收 敛速度慢的不足，因此近年来成为了很多学者广泛研究的对象。 1 3 论文的主要工作和安排 本文针对粒子群算法在解决多目标优化问题上的不足提出了一些新的想法，在对多 目标优化问题的发展过程、研究现状、基本概念、理论知识及基本框架介绍以后，在对 现有的多目标优化算法进行分析的基础上，进行了创新。本文内容被组织成五章，每章 主要内容大致如下： 4 第1 章绪论 第l 章绪论叙述了课题研究的目的及意义，简要的介绍了粒子群算法的应用范 围，回顾了处理多目标优化问题的古典方法，把基于进化算法与粒子群算法在多目标优 化领域的发展过程作为重点进行了介绍，最后对论文各章节内容进行了安排。 第2 章多目标优化问题的基本知识简要介绍了多目标优化问题的定义、数学模 型及多目标优化算法的设计目标，同时介绍了多目标优化算法的个体选择策略和多样性 保持策略，分析了多目标优化算法的各种性能度量指标。 第3 章粒子群优化算法的介绍介绍了标准连续型粒子群算法和离散型粒子群算 法的基本原理及流程，并给出了粒子群算法的收敛域分析以及粒子群算法的时间复杂度 分析。 第4 章改进的粒子群算法首先对粒子群算法中常见的几种变异算子进行了简单 介绍，然后给出了多尺度变异算子的设计方法，针对多目标优化问题采用新的个体最优 值与全局最优值的更新方式以及速度的更新方式，然后总结了多尺度变异算法解决多目 标问题的流程，最后分析了算法的收敛原理。 第5 章实验结果及分析选取了4 个b e n c h m a r k 优化函数，对本文算法和基于其它 变异策略的改进粒子群算法进行结果对比，仿真表明本文算法具有吏佳的优化性能。针 对多目标优化问题，本文选取4 个z d t 测试问题和2 个d t l z 测试问题进行了实验并 与其它算法进行对比，结果表明了本文算法的性能具有一定优越性。 最后对全文工作进行了总结，指出了研究的不足之处，并对未来的研究前景进行了 展望。 5 哈尔滨工程大学硕十学位论文 第2 章多目标优化基础 科学研究和工程实践中经常会碰到许多问题可以建模为多目标优化问题，与只包含 个目标函数的单目标优化问题不同，多目标优化问题存在着多个相互冲突的优化目 标，某一个目标的改良可能引起其它目标的恶化，因此如何获取多目标优化问题的最优 解，一直是研究人员关注的焦点问题。为此，怎样设计一个有效的多目标优化算法成为 了多目标优化领域的主要问题。同时，如何评价一个多目标优化算法的优劣程度，即对 于多日标优化算法的性能度量也成为了多目标优化问题的重点研究内容。 2 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 ，m o p ) 又称多属性、多准 则、多指标优化问题。通常情况下，一个m o p 的组成包括：决策变量 个，目标函数m 个和约束条件尼个，具体可描述为： m i n y = 厂( x ) = ( 彳( x ) ，艿( x ) ，厶( x ) ) s t 力( x ) = ( 啊( x ) ，鸭( x ) ，( 石) ) o ( 2 - 1 ) 其中，x = ( _ ，x ：，) x 代表决策向量，y = ( y 。，y ：，y 。，) 】，代表目标向量，x 代表 ，z 维决策空间，y 代表所维目标空间。目标函数厂= ( 石，六，工，) 代表x 到y 的映射函 数，力( x ) = ( ( x ) ，( x ) ，吃( x ) ) 代表足个约束条件。在此之上，给出下面几个定义。 定义2 1 ( 可行解) ：称一个满足式( 2 1 ) 中约束条件办( x ) = ( ( x ) ，鸭( x ) ，k ( x ) ) o 的 决策变量x x 为可行解。 定义2 2 ( 可行解集) ：在决策空间x 中，称由所有的可行解x 构成的集合为可行解 集，记作( ，x ) 。 定义2 3 ( p a r e t o 支配) ：对于可行解集。中的任意两个可行解口，6 ，称a 支配6 ， 当且仅当式( 2 2 ) 成立，记作口 - 6 。 v f ( 1 ，2 ，m ) ： ) ( 6 ) 八 影( 1 ，2 ，m ) ：乃( 口) - 。6 。 v f ( 1 ，2 ，竹) ：，( 口) 一s ，( 6 ) ) 八 影( 1 ，2 ，m ) ：乃( 日) 一s ， - x ( 2 4 ) 定义2 6 ( p a r e t o 最优解集) ：称由所有p a r e t o 最优解构成的集合为p a r e t o 最优解集， 定义如式( 2 5 ) ： p = ( x _ 1 j x x 。：x x )( 2 5 ) 定义2 7 ( p a r e t o 最优前端) ：称p a r e t o 最优解集中所有解的目标向量值构成的集合 为p a r e t o 最优前端，定义如式( 2 6 ) ： b = 厂( x ) = ( i ( x ) ，以( x ) ，( x ) ) x p ) ( 2 - 6 ) 以两个目标函数优化问题为例，考虑目标函数最小化情况，图2 1 体现了非支配解 与支配解在目标空间的分布情况。 f 2 f 1 图2 1p a r e t o 支配关系 图2 1 中，实线部分表示p a r e t o 最优前端，实心点a ，b 位于在p a r e t o 最优前端上， 它们都是最优解，是非支配的，阴影部分为a ，b 两点在目标空间上的支配范围；空心 点c ，d ，e 位于搜索空间内，但不位于p a r e t o 最优前端上，它们不是最优解，是被支 配的，即劣于p a r e t o 最优前端上的最优解。 多目标优化问题本身的复杂程度比单目标优化问题高很多，需要同时优化多个目 标。由于改良一个目标可能导致其他目标变差，因而在各优化目标之间要加以权衡。这 使得多目标优化问题的解并不唯一，而是一组对于决策者来说各优化目标的性能指标都 比较满意的p a r e t o 最优解的集合。 7 哈尔滨： 程大学硕士学位论文 2 2 多目标优化算法的设计目标 进化算法的兴起为处理多目标优化问题开辟了新的思路。与多目标进化算法及其它 多目标优化方法相比，尽管多目标粒子群算法在收敛速度和保持解多样性方面取得了良 好的效果，但是由于多目标优化问题自身的复杂性，所以仍然有必要设计一些高效的策 略用来更好地解决多目标优化问题中的一些难点。一般说来，多目标优化算法的设计应 该尽可能满足以下几个方面： ( 1 ) 搜索到的非劣解应最大限度地逼近p a r e t o 最优前端； ( 2 ) 搜索到的非劣解应尽最大可能在p a r e t o 最优前端均匀地分布； ( 3 ) 搜索算法需要保证一个较快的收敛速度。 同时满足以上四个方面对于任何一个解决多目标优化问题的算法而言都是一个难 题。尽管国内外许多文献中提出的有效的多目标优化算法为解决此问题带来了希望，但 问题依然远远没有得到解决，尤其是当问题存在无穷多个p a r e t o 最优解，并且这些解在 目标空间呈现出非凸、分段、不连续以及分布不均匀的情况时，已有的多目标优化算法 在保持最优解集的收敛性、均匀性以及宽广性等方面难以达到理想的效果。因此，在设 计一个多目标粒子群算法时必须要考虑以下两个关键性问题： ( 1 )怎样才能确保粒子逐渐向p a r e t o 最优前端的位置移动； ( 2 ) 怎样才能使算法不陷入局部最优，同时获得分布均匀和扩展良好的p a r e t o 最优前端。 以上两个关键问题的核心是如何在保证算法具有较好收敛能力的同时，还具有较强 的搜索能力。 2 3 多目标优化算法的关键理论 目前，处理多目标优化问题的算法大致归类为以下几种：传统的多目标优化方法、 多目标进化算法、多目标粒子群算法、多目标免疫算法等。虽然传统的多目标优化方法 简单易行，但需要对待优化的问题有充足的先验知识。另外，相互独立的优化过程使得 彼此之间信息无法共享，从而延长算法的计算时间，因此一般不依赖传统方法解决多目 标优化问题。以进化算法为代表的群体智能优化算法为解决多目标优化问题提供了一种 新途径。同时，与多目标智能优化算法相关的一些关键理论也成为国内外学者关注的重 点问题。 8 第2 蕈多目朽：优化基础 2 3 1 适应度函数的选取 单目标优化问题中，适应度函数往往与目标函数相同，但多目标优化问题的适应度 赋值必须考虑多个待优化目标函数，没有固定的适应度函数形式，需要学者们自行定义 它。因此，多目标优化算法的适应度赋值和单目标情况下的操作方式有着很大的不同。 按照现有的研究成果，可以将多目标优化算法的适应度赋值方式分为三种：基于聚合的 方式、基于目标函数的方式以及基于p a r e t o 支配关系的方式。 基于聚合的方式建立于传统方法的基础之上，如常见的进化加权法。将多个目标函 数按不同权重组合成一个单目标函数，权重值随着进化代数有规律的变化，个体的适应 度值采用确定的加权组合。 与将每个目标整组为一个目标的标量值不同，基于目标函数的方式是在搜索过程中 阶段置换所选的目标。例如k u r s a w e 提出在选择阶段以一定概率系数对各目标进行取 舍，此概率值可以由用户指定或者随机设定。这种适应度赋值方式的缺陷在于进化结果 容易趋向于某些极端边界解。 基于p a r e t o 支配关系的适应度赋值方式，起初是由g 0 1 d b e r g 吲提出的，之后多数是 在此基础上进行改进。其赋值过程为：种群中所有非支配个体的级别设为l ，将它们从 种群中暂时移除，从剩下的个体中再选出所有非支配个体，再把级别设为2 ，同样从种 群中暂时移除，如此循环直到所有个体均赋值完毕。个体的等级值即为其自身的适应度 值。基于p a r e t o 支配关系的适应度赋值方式已经被大多数学者们使用，比如s p e a 和 s p e a 2 等一些方法采用计算支配级别的方式，即统计种群中支配此个体的所有其它个体 数目之和，依此来确定每个个体的适应度值。这种适应度赋值方式操作简单，原理也一 目了然。需要注意的是适应度值与种群规模相关。 2 3 2 最优个体选择策略 对于单目标优化问题，判断一个解质量的好坏只要依据其目标函数值的大小。而多 目标优化问题解之间的优劣排序比较困难，相互不支配的个体之间彼此不具备可比性。 当用来保存非支配个体的外部存储器集合中的个体数量过多时，为了节约内存资源，只 能放弃其中一部分非支配个体。因此一个恰当的保持解多样性的最优个体选择策略也是 影响算法性能的关键原因。目前比较典型的多样性保持策略包括聚类策略【2 6 】、拥挤度距 离策略及超网格划分策略。 ( 1 ) 聚类策略 这类裁剪外部粒子群解集的方法是借鉴了多目标进化算法中的技术，其基本原理是 9 哈尔滨j 程大学硕十学位论文 每一次算法进化后，将整个外部粒子群解集中的所有非支配解进行聚类，当类别数超出 一定数量时将相聚最近的2 个类别合并，取合并以后的中心点作为新类的聚类中心。采 用聚类技术对非劣解集进行裁剪的步骤如下： 1 初始化由外部粒子群中的非劣解组成的聚类集d ，每个非劣解对应一个聚类； 2 若i d l ，跳到第5 步，否则，继续第3 步。为外部粒子群解集的最大规模； 3 根据公式( 2 1 0 ) 计算两两聚类彼此间的距离，皿和d 2 d ，m 一，2 | l 代表两个体 在目标空间上的欧氏距离。 d 。南 磊胁卜7 ：| i ( 2 j o ) 4 确定彼此间距离最小的两个聚类d 1 和以d ，然后更新聚类集 d = d q ，砬 u d 1ud 2 ，转步骤2 ； 5 确定各聚类的聚类中心。一般情况下，选择在同一类别里与其它个体间平均距 离最小的个体作为聚类的中心； ( 2 ) 拥挤度距离策略 拥挤度距离方法起初出现在n s g ai i 算法中，它描述了一个最优解的周围分布的其 他最优解的疏密程度。对于每个待优化目标函数，将p a r e t o 最优解集中的所有非支配解 按照此目标函数值大小进行排序，对每个解坼，计算由解坼一。与诈+ 。所形成的长方体的 平均边长，托的拥挤度距离就是相对于所有待优化目标函数的平均边长的和。具体计算 方法如式( 2 1 1 ) ： 张咖躺 d ( 坼) = 噍( 砟) ( 2 1 1 ) 其中，( _ ) 、( x ，) 表示对于第g 个目标函数离( 矗) 最近的两个点( 即 ( x ，) 厶( 坼) ( x ，) ，g = 1 ，2 ，朋) ，m a x ( ) 、m i n ( ) 分别表示所有p a r e t o 最优解 在第g 个目标函数上的最大值和最小值。当( k ) = m a ) 【( ) 或m i n ( ) 或者 m a x ( 五) = m i n ( ) 时( 即矗为边界解或者唯一解时) ，吒( ) = o 。 以两目标函数优化问题为例，一个p a r e t o 最优解的拥挤度距离如图2 2 所示。 图中实心点表示该多目标优化问题当前进化代数下的所有p a r e t o 最优解，k 的拥 挤度距离d ( 诈) = 4 ( 坼) + 破( 坼) ，即为以离最近的两个最优解的连线为对角线，在 目标空间形成的长方体的两个边长之和。 1 0 第2 章多目标优化基础 当外部粒子群中所有p a r e t o 最优解的拥挤度距离确定了之后，将这些最优解根据拥 挤度距离值进行降序排列。拥挤度距离越小的解将被赋予越大的概率从外部粒子群中移 除，如果拥挤度距离值最小的解不只一个时，则随机选择其中一个最优解将其从外部粒 子群移除，然后再判断外部粒子群的容量是否超出最大值，若超出，继续移除剩余最优 解中拥挤度距离最小的个体，反复循环直到外部粒子群解集的容量达到规定值为止。 f 2 tl 图2 2 两目标函数优化问题的个体拥挤度距离表示 ( 3 ) 超网格划分策略 超网格划分策略的基本原理是：将低维目标空间分割成许多的网格，如果是多维目 标空间，就分割成很多的超立方体。在算法进化的过程中，外部粒子群中的个体会不断 发生变化，算法自行动态调整网格尺寸，对外部粒子群中的个体重新定位，以保证每个 个体都落于某个网格之中。对于有聊个目标函数的多目标优化问题而言，超网格划分策 略的具体实现过程如下： 第f 个目标函数能取得的最小值和最大值分别为i n i n ( ) 和m a ) ( ( z ) ，给定一个向量 s = s 。，s ：，s 。 ，s ，表示第f 个目标函数上的网格宽度，将搜索空间分割成 兀( m a x ( ) 一m i n ( z ) ) 他，个超网格，通过辨识向量6 = ( 6 1 ，6 2 ，玩，) 来确定个体位于哪 个超网格内，辨识向量的计算如公式( 2 1 2 ) ： ( x ) = i ( ( ( x ) 一n l i n ( ) ) s ，i g = 1 ，2 ，m( 2 1 2 ) 以两目标函数优化问题为例，超网格划分法如图2 3 所示。 虚线构成的每个网格由网格宽度向量s = s 。，s ： 分割而成。其中个体1 的辨识向量e 和个体2 、3 的辨识向量b ，根据式( 2 1 2 ) 计算得到。阴影部分表示个体1 的p a r e t o 支配 哈尔滨工程火学硕士学位论文 范围，灰色部分表示个体1 的s 支配范围，个体4 不受个体1p a r e t o 支配，但却被个体 1s 支配，因而从外部粒子群中移除个体4 。个体2 和个体3 的辨识向量相同，且相互 间无支配关系，这时分别计算个体2 和个体3 与它们的辨识向量b 间的欧式距离，保 留具有较小欧式距离的个体2 ，移除欧式距离较大的个体3 ，保