（计算机软件与理论专业论文）改进微粒群算法在多目标优化问题中的应用.pdf

山东师范大学硕士学位论文 改进微粒群算法在多目标优化问题中的应用 摘要 在现代科学研究中，多目标优化是优化问题的主要研究领域之一，现实世界中的问题 大多具有多目标特征，通常不易处理。因此，解决多目标优化问题是一个非常有实际意义 和科研价值的课题。过去在运筹学、决策学等学科涌现了很多方法，用于求解多目标优化 问题。随着现代科学的发展，各学科之间的相互渗透，新的交叉学科、思维方式、计算方 法的产生，都为多目标优化技术的研究和发展注入了活力，提供了更广阔的研究空间。 随着计算智能技术的发展，在2 0 世纪8 0 年代中期进化算法开始应用于解决多目标优 化问题。目前涌现出了很多种多目标进化算法，比如s p e a 、p e s a 、n p g a 等，利用进化算 法求解多目标优化问题逐渐成为一个热点和重要研究领域。它突破了古典运筹学中多目标 优化方法的局限性，并具有区别于传统单目标进化算法的特征，在工业工程、科学和国防 军事中具有很高的应用价值。 微粒群算法是2 0 世纪9 0 年代提出的一种基于群体智能理论的优化算法，通过群体中 粒子间的合作与竞争产生的群体智能指导优化搜索。这种新算法启发于鸟类、虫、鱼群等 物种的群体捕食行为。由于其简单有效，随后得到了广泛的关注，同时其在解决单目标优 化问题时表现出来的良好特性也非常适合求解多目标优化问题。 本文主要研究了群体智能中的微粒群优化算法，并将其应用于多目标优化领域。主要 工作有以下几个方面： 1 简要介绍了微粒群算法和多目标优化的理论基础 主要介绍了微粒群算法的基本概念、算法的基本流程及其发展；多目标优化的基本理 论与常见的古典求解方法，最后对多目标进化算法的关键理论进行了探讨，并给出了几种 常见的多目标进化算法。 2 提出一种基于动态概率变异的c a u c h y 微粒群优化 针对微粒群算法的不足，通过求解0 1 背包问题，验证了f u z z yp s 0 算法的性能。借 鉴g a u s s i a ns w a r m 和f u z z yp s 0 的基本思想，提出了c a u c h y 微粒群优化算法，并引入遗 传算法中的变异操作，形成了动态概率变异c a u c h y 微粒群优化算法，实验表明改进算法 优于传统算法。 3 提出一种多微粒群协同进化模型 借鉴群体智能中协同进化的思想和遗传算法的基本理论，提出了一种多微粒群协同进 化算法，通过实验对算法的有效性进行了验证。并结合群体进化算法的一般特征，改进了 该算法，提出了一种多群协同进化模型，给出了模型的一般框架。 4 改进了p a r e t o 解集构造方法片予以证明，实现了改进p s 0 在m o k p 中的求解 本文最后在擂台赛法则基础上改进了p a r e t o 解集的构造方法，利用改进的微粒群算 山东师范大学硕士学位论文 法，实现了多目标优化中多背包问题的求解。算法模拟程序利用v c + + n e t2 0 0 5 在w i n d o w s x p 平台上丌发完成，分别对三种测试样本进行验证，测试结果比较满意。 关键词：微粒群优化；多目标优化；多背包问题；p a r e t o ；多目标进化算法 分类号：t p 3 0 l 山东师范人学硕十学位论文 t h em o d i f i e dp s o a l g o r i t h ma n di t sa p p l i c a t i o ni nm u l t i o b je c t i v e o p t i m i z a t i o np r o b l e m a b s t r a c t 1 1 1m o d e ms c ie n t i f i c r e s e a r c h ，m u l t i o b je c t i v eo p t i m i z a t i o ni s o n eo ft h em o s ti m p o r t a n t r e s e a r c ha r e a si no p t i m i z a t i o np r o b l e ma n dm o s tp r o b l e m si nr e a l w o r l da r ec h a r a c t e r i z e db y m u l t i o b j e c t i v e ，s oi ti su s u a l l yi l o te a s yt oh a l l d l et 1 1 e m t h e r e f o r e ，s 0 1 v i n gm 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 mi sat o p i cw k c hh a sp r a c t i c a ls i g n i f i c a i l c ea n ds c i e n t i 丘cr e s e a r c hv a l u e f o h n e d y ，m e r ew e r em a n ym e m o d sw h i c hb e l o n gt o 叩e r a t i o n a lr e s e a r c h 觚dd e c i s i o nm a k i n g t os o l v em 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 w i t ht h ed e v e l o p m e n to fm o d e ms c i e n c ea n d t e c l l l l 0 1 0 9 ya n dp e n e t r a t i o no fd i f r e r e n ts u b j e c t s ，a 1 1 dm ea p p e a r a n c eo fn e wc r o s ss u b j e c t s ，n e w t l l i l l l 【i i l gw a y sa n dn e wc o l n p u t a t i o nm e t h o d se n e r 百z e t h e s t u d y a 1 1 d d e v e l o p m e n to f m u l t i o b j e c t i v eo p t i m i z a t i o nt e c l l l l 0 1 0 9 ya i l do f f e rm o r es p a c ef o rs t l l d y w i mt h ed e v e l o p m e n to ft h ec o m p u t a t i o n a li n t e l l i g e n c et e c h n o l o g y ，t h ee v 0 1 u t i o na l g o r i t l l m w a sa p p l i e dt o s 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 mi nt h e 面d d l e1 9 8 0 s a n dm a n y 舢l t i o b j e c t i v ee v o l u t i o na l g o 打t l l m sh a v ee m e r g e di nl a r g en u m b e r s ，s u c ha ss p e a 、p e s a 、 n p g aa i l ds oo n m a k i n gu s eo fe v 0 1 u t i o na l g o r i t l u nt os 0 1 v em u l t i o b je c t i v ep r o b l e m sh a v e 黟a d u a l l yb e c o m eah o ti s s u ea n dm em o s ti m p o r t a n tr e s e a r c ha r e a i tb r e a k st h el i m i t a t i o no f m u l t i o b je c t i v eo p t i m i z a t i o ni nt h eo p e r a t i o n a lr e s e a r c ha n dp o s s e s s e st h ec h a r a c t e r i s t i c sw 1 1 i c h d i s t i n g u i s hi t s e l f 矗o mt h et r a d i t i o n a ls i n g l eo b je c t i v ee v 0 1 u t i o na l g o r i m ma n dh a s 黟e a tp r a c t i c a l v a l u ei ni n d u s t r i a le n g i n e e 血g ，s c i e n c ea 1 1 dn a t i o n a ld e f e n s em i l i t a 丐 p a n i c l es w a r mo p t i m i z a t i o nw a sa no p t i m i z a t i o na l g o r i t w h j c hw a s p r o p o s e do nt h eb a s i s o fs w a r mi n t e l l i g e n c ei nt h e19 9 0 sa n di td i r e c t st 1 1 e o p t i m i z a t i o ns e a r c hb yt h es w a r m i n t e l l i g e n c ew h i c hw a sp r o d u c e db yt h ec o o p e m t i o na n dm ec o m p e t i t i o no ft h es w a r mp a n i c l e s a n dt 1 1 i sn e wa l g o r i t h mw a s i n s p i r e db yt h es w a mf o o d h m l t i n gb e h a v i o ro f b i r d s ，i n s e c t s 勰d f i s h 伊o u p s b e c a u s eo f i t ss i m p l i c i t ya n de 伍c i e n c y ，i ti 删 1 1 e d i a t e l yd r e we x t e n s i v ea t t e n t i o n 姐d a tt h es a m et i m ei t sa d v a n t a g e sw h i c hw a ss h o w e dw h e ns 0 1 v i n gt 1 1 es i n 9 1 eo b je c t i v ep r o b l e m w a s q u i t ea p p l i c a b l ef o rs o l v i n gm u l t i o b j e c t i v ep r o b l e m s t h et h e s i sf o c u s e so nt h es t u d yo fp a n i c l es w a mo p t i i l l i z a t i o na l g o r i t h ni nt h es w 蛐 i n t e l l i g e n c ea n df u n h e r 印p l i e si tt ot h em u l t i o b j e c t i v ef i e l d t h em a i nw o r k sa r ea sf o l l o w s ： 1 t h eb r i e fi n t r o d u c t i o no ft h e o r yb a s i so fp a r t i c i es w a n no p t i m i z a t i o na n dm 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 t h eb r i e fi n t m d u c t i o no ft h ec o n c 印t s ，t h eb a s i cp r o c e d u r ea n dt l l ed e v e l o p m e n to fp a r t i c l e s w a n no p t i m i z a t i o n ；l eb a s i ct h e o r yo 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 n dc o m m o nc l a s s i c a l 山东师范大学硕士学位论文 a l g o r i t 王1 i i l s ，a n dt h ee x p l o r a t i o no ft h ek e yt h e o r i e so fm u l t i o b je c t i v ee v o l u t i o na l g o t 王1 1 1 1 sa n d p r e s e n t a t i o no fs o m ec o m m o nm u l t i o b j e c t i v ee v o l u t i o na l g o r i t h m s 2 p r o p o s eac a u c h yp a n i c l es w a r mo p t i m i z a t i o nb a s e do nd y l l a i 】面cp r o b a b i l i t ym u t a t i o n i nv i e wo ft h ed i s a d v a n t a g e so fp a n i c l es w a mo p t i m i z a t i o n ，t 1 1 r o u 曲t h eo 1 k n 印s a c k p r o b l e m ，也ep e r f o m l a n c eo ff u z z yp s 0w a sv e r i f i e d u s i n gm eb a u s i ct h o u g h t so fg a u s s i a i l s w a 册缸1 df u z z yp s o ，c a u c h yp a n i c l es w 锄o p t i m 娩a t i o nw a sp r o p o s e da n d 向r t h e rt h e m u t a t i o no p e r a t i o no fg e n e t i ca l g o r i t h mw a si n t r o d u c e da n df o n n e dd y l l 锄i c p r o b a b i l i t y m u t a t i o nc a u c h yp a n i c l es w 锄0 p t i i n i z a t i o na l g o r i t l l i l l t h ee x p e r i m e n t sp r d v e dt h a ti m p r o v e d a l g o r i t h mw a s b e t t e rt h a nt h et r a d i t i o n a la l g o r i t h m 3 t h ep r o p o s i t i o no fam o d e lo fm u l t i p s oc o e v o l u t i o n d r a w i n g1 e s s o n sf r o mm ec o e v 0 1 u t i o nt h o u 酿t so fs w 狮i n t e l l i g e n c ea 1 1 dt h eb a s i cm e o r yo f g e n e t i ca l g o r i t h i n ，强a l g o r i 恤no fm u l t i p s oc o e v o l u t i o nw a sp r o p o s e d 孤dv e d f i e db y e x p e r i m e m s t h i sa l g o n m mw a si m p r o v e db yc o m b i n i n gt h ec o m m o nc h a r a c t e r i s t i c so fs w 锄 e v o l u t i o na l g o r i t h m sa n dp r o p o s e dam o d e lo fm u l t i p s oc o e v 0 1 u t i o na n dt h em a i ns t l l j c t u r eo f t h em o d e lw a s p r e s e n t e d 4 r h ei i l l p r o v e m e n ta n dp r 0 v i n go ft h ec o n s t l l j c t i n gm 砒o do fp a r e t 0 ，t h er e a l i z a t i o no f i m p r o v i i l gp s o i ns 0 1 v i n gm u l t i o b j e c tk n a p s a c kp r o b l e m a tt h ee n do ft h i st h e s i s ，t h ec o n s t r u c t i n gm e t h o do fp a r e t ow a si m p r o v e do nm eb a s i so f 心e n a sp r i n c i p l ea n dt h es a l v a t i o no fm u l t i k n 印s a c kp r o b l e mo fm u l t i o b j e c t i v e 叩t i m 五a t i o n w a sr e a l i z e dt h r o u g ht h ei m p r o v e dp s o 、t h em o d e lp r o 黟锄w a sd e v e l o p e da n dc o m p l e t e do n t h ep l a t f o m lo fw i n d o w sx pw i t hv c + + n e t2 0 0 5 n 聆ee x a m i n a t i o ns a m p l e sw e r et e s t i 矗e d a 1 1 ds a t i s f a c t o r yr e s u l t sw a s p r o d u c e d k e y w o r d s ：p s 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 n ；m o k p ；p a r e t o ；m o e a c l a s s i 矗c a t i o h ：t p 3 0 1 l v 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得( 注：如没有其他需要特别声 明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：委，l痔 学位论文版权使用授权书 导师签字： 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权擞 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：壶，l办 签字日期：2 0 0 9 年歹月弓。日 导师签字 签字日期：2 0 0g 年j 月如日 山东师范大学硕十学位论文 第一章绪论 本章首先介绍了计算智能的研究背景及前沿，其次阐述多目标优化的发展现状，最后 介绍了本文的内容和主要工作。 1 1 计算智能 生命在长期进化过程中，积累了很多新奇的功能，人类很早就从中得到启发而改造自 己的工具，如史书中记载“见蓬转而做车辑”，传说鲁班被茅苇划破，而发明了锯。后来， 人们开始有意识地进行这方面的研究，这就是“仿生学”。仿生学顾名思义就是模仿生物 的某些功能的学问。仿生学的例子很多，如模仿海豚皮而构造的“海豚皮游泳衣”、科学 家研究鲸鱼的皮肤时，发现其上有沟漕的结构，于是有个科学家就依照鲸鱼皮构造，造成 一个薄膜蒙在飞机的表面，实验表明可节约能源3 ，若全国的飞机都蒙上这样的表面，每 年可节约几十亿。又如有科学家研究蜘蛛，发现蜘蛛的腿上没有肌肉，有脚的动物会走， 主要是靠肌肉的收缩，现在蜘蛛没有肌肉为什么会走路? 研究发现蜘蛛不是靠肌肉的收缩 进行走路的，而是靠其中的“液压”的结构进行走路，据此人们发明了液压步行机。总之， 从自然界得到启迪，模仿其结构进行发明创造，这就是仿生学，也是我们向自然界学习的 一个方面。另一方面，我们还可以从自然规律中得到启迪，利用其原理进行设计( 包括设 计算法) ，这就是计算智能的思想。 计算智能，也称为“软计算( s o f tc o m p u t i n g ) ”，是当代人工智能的重要组成部分， 它是2 0 世纪9 0 年代初期在向传统的人工智能挑战过程中提出的研究模拟人类的思维或生 物的自适应、自组织能力，以实现计算技术的智能性的一门新学科。1 9 9 2 年，b e z d e k 瞳1 在a p p r o x i 腿t er e a s o n i n g 学报上首次给出了计算智能的定义；1 9 9 4 年，i e e e 神经网 络委员会在0 r l a n d o 召开了i e e e 首次国际计算智能大会( w o r l dc o n f e r e n c eo n c o m p u t a t i o n a li n t e l l i g e n c e ) 。这次会议首次将进化计算、人工神经网络和模糊系统这 三个领域合并在一起，形成了“计算智能”这个统一的技术范畴。计算智能是从模拟自然 界生物体系和人类智能现象发展而来，用计算机模拟和再现人类的某些智能行为，并用于 改造自然的工程实践的一种新型人工智能研究领域。 目前，计算智能的技术主要有进化计算、人工神经网络、模糊逻辑、混沌系统( c h a o t i c s y s t e m s ) 、概率推理( p r o b a b i l i s t i cr e a s o n i n g ) 等t4 l 。计算智能的最大特点就是不需 要建立问题本身精确的数学模型，适合于解决那些因为难以建立有效的形式化模型而用传 统人工智能技术又难以有效解决甚至无法解决的问题。计算智能的积极意义在于促进基于 计算和基于物理符号相结合的各种智能理论、模型和方法的综合集成，以利于发展功能更 强大，能解决更复杂系统的智能行为晦。需要指出的是计算智能不是主要研究单项技术， 而是研究如何将上述几种技术集成起来，优势互补，并应用来解决实际问题。 山东师范火学硕士学位论文 1 1 1 进化计算 进化计算( e v 0 1 u t i o n a r yc o m p u t a t i o n ，e c ) 是在2 0 世纪9 0 年代初被提出的，它是一 种借鉴生物界自然选择和进化机制发展起来的高度并行、随机、自适应搜索算法，是模拟 生物进化过程中“优胜劣汰”的自然选择机制和遗传信息的传递规律的算法的总称。简而 言之，它使用了群体搜索技术，将种群代表一组问题解，通过对当前种群施加一系列规定 的操作，从而产生新一代种群，并逐步使种群进化到包含近似最优解的状态。 进化计算主要有：遗传算法( g e n e t i ca 1 9 0 r i t h m s ，g a ) 、遗传编程( g e n e t i c p r o g r a m m i n g ，g p ) 、进化规划( e v 0 1 u t i o n a r yp r o g r a 舳i n g ，e p ) 和进化策略( e v 0 1 u t i o n s t r a t e g i e s ，e s ) 等。这几种算法是彼此独立发展起来的，各自有不同的侧重点，不同的 生物进化背景，各自强调了生物进化过程中的不同特性。各个算法都有自己的优缺点，研 究它们的优越性，并融合成新的进化算法，可以促进进化计算更广泛的应用。目前，进化 计算已成为继人工智能领域中专家系统、人工神经网络之后的又一个受人青睐的新学科。 在美国、德国、英国和法国等发达国家，进化计算己成功地应用到机械、化工、建筑、自 动控制和计算机工程等领域，着重解决结构性优化、非线性优化和并行计算等复杂问题。 进化计算的研究与应用，无论是研究队伍的规模，还是发表的论文数量，都有了很大 发展，已经得到了国际学术界的广泛认可。1 9 8 5 年，在美国的p i t t s b u r g h 召开了第一届 遗传算法国际会议。在会议期间，国际遗传算法学会( i n t e r n a t i o n a ls o c i e t yo fg e n e t i c a l g o r i t h m s ) 也宣告成立。自此，来自不同学科和工程应用领域的各国学者在遗传算法方 面有了交流、探讨的国际论坛。此外，以遗传编程、进化策略或进化编程为主题的研讨会 也频繁召开。 1 9 9 4 年，i e e e 神经网络委员会主持召丌了第一届进化计算国际会议，并成立了i e e e 进化计算委员会，此会每3 年与i e e e 神经网络国际会议、i e e e 模糊系统国际会议在同一 地点先后连续举行，共同称为i e e e 计算智能c i 国际会议，并分别出版i e e et r a n s a c t i o n s o ne v 0 1 u t i o n a r y c o m p u t a t i o n ， i e e et r a n s a c t i d n so nn e u r a ln e t w o r k s和i e e e t r a n s a c t i o n so nf u z z ys e t s 学术期刊阳 引。另外，进化计算的国际期刊e v 0 1 u t i o n a r y c o m p u t a t i o n 也于1 9 9 3 年诞生。以遗传算法为主的进化计算的研究内容也在其他学术期刊 中出版了专辑隋叫，同时在m a c h i n el e a r n i n g ，c o m p l e xs y s t e m s ，a r t i f i c i a li n t e l l i g e n c e 等重要国际期刊上也经常见到u 2 1 。 除了期刊、会议外，进化计算的一些软件也形成了商业化的产品n3 j 。根据系统开发和 设计目标的不同，这些软件程序通常可以分为三类：面向应用的系统、面向算法的系统和 工具包系统，如表1 1 所示。国内自2 0 世纪9 0 年代以来对进化计算也进行了广泛的研究 n 钔。特别是将进化计算的原理应用在不同的工程领域，取得了令人瞩目的成就，对进化计 算的理论基础研究也取得了很多优秀成果n 5 。 2 山东师范大学硕士学位论文 面向应用的系统 面向算法的系统 j 。 具包系统 专门算法算法库教学系统通用系统 e v o l v e r e s c a p a d e e m g ag a o t o m e g a g a g ag a l i bw o r k b e n c h e n g i n e e r p c b e a 9 1 e g a u c s d1 i b g a c o m p u t e r a n ts g a m e g e n e r a t o rm g a p g a p a c k g a m u s i cm i c r o g a x p e r t r u l e g e n e s i s o o g as g a s p l i c e r g e n a s 穸s g e n i t o rd o u g a l p a g a s u s 1 1 2 群体智能 表1 1 进化计算的软件产品及分类 在自然界中存在很多动物群集的行为，例如大雁在飞行时自动排成一字形或人字形； 蚂蚁群可以一起往蚁穴搬运路上遇到的食物，它们协同工作，建起坚固、漂亮的巢穴，一 起抵御危险，抚养后代。所有这些群集的动物中存在着能迅速适应环境变化的十分灵活的 系统，这些系统是分散的和自主管理的，具有很强的抗击能力。群体中的每个个体都遵守 一定的行为准则，当它们按照这些准则相互作用时就会表现出复杂行为。这种现象揭示了 简单智能的主体通过合作可以表现出复杂智能行为的特性。通过对其行为的模拟，产生了 一系列解决复杂优化问题的新思路和方法，用于解决组合优化问题和其它一些实际应用问 题的新方法相继产生。受群居性生物的寻食、打扫巢穴等行为的启发而设计的算法成功地 解决了组合优化、网络通信和机器人等领域的实际问题。 自然界中的动物群集是一组相互依赖的通过间接或直接交互实现透信的a g e n t 的集 合，被称为群体( s w a r m ) 。群体表现出来的智能行为被称为群体智能( s w a r mi n t e l l i g e n c e ) 。 1 9 8 6 年，c r a i gr e y n 0 1 d s 提出一个仿真生物群体行为的模型b o i d n6 l 。这是一个人工鸟系统， 其中每只人工鸟被称为一个b 6 i d ，它有三种行为：分离、列队及聚集，并且能够感知周围 一定范围内其它b o i d 的飞行信息。b o i d 根据该信息，结合其自身当前的飞行状态，并在那 三条简单行为规则的指导下做出下一步的飞行决策。r e y n 0 1 d s 用计算机动画的形式展现了 该系统的行为，每个b o i d 能够在快相撞时自动分开，遇到障碍物分开后又重新合拢，这实 际上就是一种群体智能模型。尽管这一模型出现在1 9 8 6 年，但是群体智能( s w a r m i n t e l l i g e n c e ) 概念被正式提出的时间并不长。一个显著的标志是1 9 9 9 年由牛津大学出版 社出版的eb o n a b e a u 和md o r i g o 等人编写的一本专著群体智能：从自然到人工系统 ( s w a r m 【n t e l l i g e n c e ：f r o mn a t u r a lt oa r t i f i c i a ls y s t e m ) 。 目前，对群体智能的研究还处于初级阶段，但是它越来越受到国际智能计算研究领域 学者的关注，逐渐成为一个新的重要的研究方向，并且已初见成果。2 0 0 3 年，在印第安那 州召开的i e e e 国际会议上，首次发起了对群体智能的系列研究。2 0 0 5 年，进行了第二次关 于群体智能的i e e e 国际会议，物理学家、工程师、计算机科学家、生物学家、经济学家、 山东师范大学硕士学位论文 生态学者等在广义群体智能的定义下，展示和讨论了他们在各自领域中使用群体智能取得 的成果，以及群体智能在这个新兴领域中的发展潜力和趋势。 群体智能主要有两种算法，分别是蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ，托o ) 和 微粒群优化算法( p a r t i c l es w a r m0 p t i m i z a t i o n ，p s o ) 。 1 1 3 微粒群算法 微粒群优化( p s 0 ) 算法最早是由k e n n e d y 和e b e r h a r t n 钉于1 9 9 5 年提出的，是一种基于种 群寻优的启发式搜索算法。它的基本概念源于对鸟群群体行为的研究。在微粒群优化算法 中，每个微粒代表待求解问题的一个潜在解。每个微粒都可获得其邻域内其它微粒个体的 信息，并可根据该信息以及简单的位置和速度更新规则，改变自身的状态量，以便更好地 适应环境。随着这一过程的反复进行，微粒群最终能够找到问题的近似最优解。由于微粒 群优化算法概念简单，易于实现，并且具有较好的寻优特性，因此它在短期内得到迅速发 展，目前己在许多领域中得到应用，如电力系统优化、t s p 问题求解、神经网络训练、交 通事故探测、模型优化等。 p s 0 算法自提出以来，得到了优化领域的普遍关注。在算法的改进方面，首先由k e n n e d y 和e b e r h a r t 在1 9 9 7 年将基本微粒群算法应用于二进制编码，提出的二进制p s o 算法n 引，主 要用于解决工程中的组合优化问题。为了更好地提高算法的收敛性能，s h i 等人引入了惯 性权重wu 驯，通过控制w 的取值大小，可以调节p s o 算法的全局和局部寻优能力。 e b e r h a r t 堙仉2 等人根据试验提出了一种随时间线性递减w ( l i n e a rd e c r e a s ei n e r t i a w e i g h t ，l d w ) 的方案以获得较好的全局寻优性能。c 1 e r c 心羽于1 9 9 9 年在进化方程中引入收缩 因子以保证算法的收敛性，算法对微粒的最大速度没有限制。但是，后来研究发现设定最 大速度限制可以提高算法的性能。有关学者已通过代数方法对此方法进行了详细的算法分 析，并给出了参数选择的指导性建议。 1 9 9 9 年，a n g e l i n e 瞳3 3 借鉴遗传算法中的自然选择机制，提出了一种杂交微粒群算法， 测试函数试验结果表明：在大多数情况下测试性能优于标准p s o 算法，对于某些测试函数 效果不甚理想，原因在于算法提高了p s 0 算法的局部搜索能力，但同时削弱了全局搜索能 力。l o v b j e r g 比4 1 等人进一步将进化计算机制应用于p s 0 算法，研究结果表明繁殖操作降低 了单峰值函数的收敛率，但是在拥有多个局部最小值的函数中情况恰恰相反。 保持种群多样性对于种群进化是十分有利的，对于大多数进化算法而言，保持种群的 多样性可以避免早熟收敛，从而更加有利于全局搜索。为了保证进化过程中群体中微粒的 多样性，s u g a n t h a n 在标准p s 0 算法中引入空间邻域概念_ 引，提出了基于粒子空间位置的划 分方案。应用改进的邻域规则，且采用l d w 策略的p s o 在绝大多数测试中都取得了更优良的 效果：k e n n e d y 通过对几种拓扑结构的测试乜引，引入邻域拓扑的概念来调整邻域的动态选 择，同时引入社会信念将空间邻域与邻域拓扑中的环拓扑相结合以增加邻域间的信息交 流，提高群体的多样性。l o v b j e r g 等人于2 0 0 1 年将遗传算法中的子群体概念引入p s 0 算法 4 山东师范人学硕十学位论文 中，同时引入繁殖算子以进行子群体的信息交流。 在p s 0 算法的行为分析和收敛性分析方面，很多学者进行了大量的研究工作。首先是 采用代数方法对几种典型的p s 0 算法的运行轨迹进行了分析心7 1 ，给出了保证算法收敛的参 数选择范围。在收敛性方面，f r a n sv a nd e nb e r 曲引入s 0 1 i s 和w e t s 关于随机性算法的收 敛准则，证明了标准p s 0 算法不能收敛于全局最优解，甚至于局部最优解；并证明了保证 收敛的p s 0 算法能够收敛于局部最优解，而不能保证收敛于全局最优解旺引。 在p s o 算法的应用方面，p s 0 算法最早应用于人工神经网络的训练方法。k e n n e d y 和 e b e r h a r t 成功地将p s o 算法应用于分类x 0 r 问题的神经网络训练。随后，p s o 算法在函数优 化、约束优化、极大极小问题、多目标优化等问题中均得到了成功的应用。但是p s 0 算法 做为一种新兴的群体智能算法，还存在很多有待改进和发展的地方。根据国内外关于微粒 群算法研究的相关文献及进化领域的发展趋势分析，微粒群算法的改进，微粒群算法与其 他进化算法的结合，以及将微粒群算法应用于新的领域等将是未来主要的研究方向。 1 2 多目标优化 在国民经济各部门和科学技术的各个领域中普遍存在着最优化问题，最优化问题就是 从所有可能的方案中选择出最合理的达到最优目标的方案，即最优方案，搜索最优方案的 方法就是最优化方法。当一个优化问题模型只包含一个目标方程时，我们称之为单目标优 化。然而在实际应用中，人们经常遇到需要使多个目标在给定可行区域上尽可能最优的决 策问题。例如在设计一种新型产品时，我们既要考虑它的使用性能，又要考虑制造成本， 同时还要考虑产品的可制造性、可维护性和可靠性等。这些设计目标的改善可能相互抵触， 譬如好的可维护性会引起可靠性的降低，因而必须在这些设计目标之间进行折衷。这种多 个目标在给定区域上的最优化问题就是多目标优化问题( m u l t i o b j e c t i v e0 p t i m i z a t i o n p r o h l e m ，m o p ) 。目标分为总目标和子目标，这里所谓的多目标优化是对多个子目标同时实 、施最优化。多目标优化问题虱2 州可以简要定义为：寻找一组既满足约束条件又使总目标函 数最优化的决策变量的取值，其中组成总目标函数的元素是子目标函数。这些子目标函数 构成性能评价标准的数学描述，这类性能指标一般是相互冲突的。因此，术语“优化”实 际上是寻找一个解，使得对于决策者而言所有的子目标函数的性能指标都是可以接受的较 好的解方案。 多目标优化对科学家和工程师来说是一个非常有实际意义和科研价值的课题，不仅因 为大多数现实问题具备多目标的特征，而且还由于该领域仍有一些悬而未决的问题有待解 决。一般来说，在科学研究和工程实践中许多优化问题都与多目标优化相关。多目标优化 问题中各目标之间通过决策变量相互制约，对其中一个目标性能的优化必须以其他目标作 为代价，而且各目标的度量单位又往往不一致，因此很难客观地评价多目标优化问题解的 优劣性。与单目标优化问题本质的区别是，多目标优化问题的解方案不是唯一的，而是存 在一个最优解集合，即p a r e t o 最优解集或非劣解集。所i 胃p a r e t o 最优解就是不存在比这个 解方案至少一个目标更好而其他目标不低劣的更好的解，也就是不可能优化其中部分目标 山东师范大学硕七学位论文 而使其他目标不劣化。p a r e t o 最优解集里的元素就所有目标而言，彼此之间不可进行性能 优劣比较。因此，对多目标优化问题的求解是科学家们在解决实际应用问题中遇到的一个 挑战。 过去的几十年间在运筹学界涌现了许多种相关方法来处理多目标优化问题，大多数方 法沿袭了一条固定模式的技术解决路线，即使用对策权衡原理对各个子目标的相对重要性 进行折衷后，再组成一个单目标来处理。常见的古典方法有加权法、约束法、目标规划法 和极大极小法等叭。但是，古典方法普遍存在的一个关键问题就是获得p a r e t o 最优解集合 必须经过多次优化过程，由于各次优化过程相对独立，往往得到的结果很不一致，令决策 者很难有效地决策，而且要花费巨额时间。 进化算法作为一种多目标优化方法已经崭露头角。它的优点在于可以处理大规模的搜 索空间、在单轮优化期间可以产生多个均衡解，能够有效地克服古典方法的局限性。进化 算法具有求解多目标优化问题的优点，早在1 9 6 7 年r o s e n b e r g 在其博士学位论文中曾提到 可以采用遗传搜索的方式来求解多目标优化问题。直到1 9 8 5 年s c h a f f e r 才提出了第一个多 目标进化算法( 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 1 9 0 r i t h m s ，m 0 队s ) 即v e g a 3 。多目标进 化算法的研究经过1 9 8 5 年一1 9 9 4 年的停滞期，到了2 0 世纪9 0 年代中期，m o e a s 开始真正引起 人们的兴趣，相关的论文数量急剧增加，在人工生命和进化计算学科中m o e a s 成为一个相 当热门的研究领域。2 0 0 1 年3 月在瑞士的苏黎世大学召开了国际上第一次进化多准则优化 的会议；2 0 0 1 年5 月在韩国汉城召开的国际进化计算大会上开始出现专门的多目标进化算 法会议专题。多目标进化算法在国内外的许多应用案例和所掀起的研究热潮已成为事实。 微粒群算法由于简单有效，迅速得到了广泛的关注，将p s 0 算法应用于多目标优化问 题是一个很有意义的研究方向。目前，解决多目标优化问题的多目标微粒群算法的研究刚 刚处于起步阶段，现在主要是将多目标进化算法中已经实现的且比较有效的优化策略直接 应用于微粒群算法来实现多目标优化求解。c o e l l o 和l e c h u g a 口2 1 在非劣最优概念的基础上 应用了一个“容器”来记录己找到的非支配向量，并用这些解来指导其他粒子的飞行。 p a r s o p o u l o s 和v r a h a t i s 应用了权重聚合的方法；h u 和e b e r h a r t 。引应用了动态邻近的p s 0 算法来求解多目标问题；s m o s t a g h