（计算机科学与技术专业论文）面向多目标优化的群智能算法研究.pdf

面向多目标优化的群钭能算法研究 摘要 针对连续型变量与离散型变量的多目标优化问题，分别提出基于蹲 弈策略的多目标粒子群优化算法和面向旅行商问题( t s p ) 的协同进化粒 子群优化算法。围绕群智能算法的优化原理与多目标优化问题的求解模 型，论文的主要研究成果概括为： ( 1 ) 根据博弈论的思想，提出一种基于博弈策略的多目标粒子群优 化算法，将目标函数看作智能体引领个体往各自有利的方向搜索，它们 根据自身的效应函数制定不同的搜索策略。从理论上分析了基于博弈策 略的多目标粒子群优化算法的收敛性质，通过多个基准测试算例，对算 法的性能进行验证，结果表明算法是有效的。 ( 2 ) 基于协同进化的思想，提出了一种面向t s p 问题的协同进化粒 子群算法( n e p s o ) ，结合一种适合t s p 问题与粒子群算法的特殊编码 方案，在此基础上新定义了两个粒子间的位置“加法”运算，替换原来 的速度方程，以实现粒子间的信息交换，然后增加一个变异算子，用来 保持种群的多样性，防止早熟收敛。 ( 3 ) 进一步改进n e p s o 算法的性能，基于蚁群算法的局部信息素 更新原理和模拟退火算法的扰动算子组成新的变异算子，在算法的收敛 速度和保持种群多样性上取得平衡，提升了算法的性能。 ( 4 ) 针对多目标t s p 问题的优化模型，综合上述算法并做相应的优 化调整，应用到多目标t s p 问题的优化求解中，引进归档集，保存当前 搜索到的p a r e t o 最优解，通过仿真实验对算法进行验证。 粒子群算法作为一种新兴的进化优化方法，能够大大减轻复杂的大 规模多目标优化问题的计算负担，本文的研究工作对研究多目标粒子群 优化算法，拓展粒子群算法的应用领域，特别是实际工程优化中存在的 离散变量多目标优化问题具有重要的理论意义与实际意义。 关键词：粒子群优化；蚁群算法；t s p 问题；多目标优化；博弈策略 i i 硕l ：学位论文 a bs t r a c t t h i st h e s i sp r o p o s e sam u l t i - o b j e c t i v e p a r t i c l es w a r mo p t i m i z a t i o n a l g o r i t h m b a s e do n g a m es t r a t e g i e s f b rc o n t i n u o u s 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 np r o b l e m ，a n dac o e v o l u t i o n a r yp a r t i c l es w a r mo p t i m i z a t i o n a l g o r i t h mf o rm u l t i o b j e c t i v et r a v e l i n gs a l e s m a np r o b l e m ( m o t s p ) w i t h d i s c r e t ev a r i a b l e s f o c u s i n go nt h es w a r mi n t e l l i g e n ta l g o r i t h m sf o rs o l v i n g 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 s ，t h em a i na c h i e v e m e n t so ft h i st h e s i s c a nb es u m m a r i z e da sf b ll o w s ： ( 1 ) an o v e lm u l t i - o b j e c t i v ep a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m i n s p i r e df r o mg a m es t r a t e g i e s ( g m o p s o ) h a sb e e np r o p o s e d ，w h e r et h o s e o p t i m i z e do b j e c t i v e sa r el o o k e da ss o m ei n d e p e n d e n ta g e n t sw h i c ht e n dt o o p t i m i z eo w no b j e c t i v ef i l n c t i o n t h e r e f b r e ，am u l t i - p l a y e rg a m em o d e li s a d o p t e d i n t o t h em u l t i - o b j e c t i v e p a r t i c l e s w a r m a l g o r i t h m ， w h e r e a p p r o p r i a t eg a m es t r a t e g i e sc o u l db r i n gb e t t e rm 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 e r f b r m a n c e i nt h e a l g o r i t h m ， n o v e lb a r g a i n s t r a t e g ya m o n gm u l t i p l e a g e n t s a n dn o n d o mi n a t e ds o l u t i o n s i m p r o v i n go p t i m i z a t i o np e r f 6 r m a n c e b ys e v e r a ls i m u l a t i o ne x p e r i m e n t sa n d b e n c h m a r kf h n c t i o n s a r c h i v em e t h o da r e d e s i g n e d f b r m o r e o v e r ，t h ea l g o r i t h mi sv a li d a t e d i t sp e r f o r m a n c ei st e s t e db yd i f f e r e n t ( 2 ) i n s p i r e df r o mt h ec o - e v o l u t i o n a r y ，an e wh y b r i dp a r t i c l es w a r m e v o l u t i o n a r ya i g o r i t h mf o rs o l v i n gt s pi sp r o p o s e d t h ea l g o r i t h ma d o p t s a ne f f e c t i v ec o d es c h e m aa n dd e f i n e san e wa d d i t i o no p e r a t i o no ft h e p a r t i c l e sp o s i t i o ni no r d e rt oe x c h a n g ei n f b r m a t i o na m o n gt h ep a r t i c l e s h e r eam u t a t i o no p e r a t o ri sd e s i g n e dt ok e e pt h ep o p u l a t i o n sd i v e r s i t y ( 3 ) i no r d e rt ok e e pab a l a n c eb e t w e e ne n h a n c i n gc o n v e r g e n c es p e e d a n di m p r o v i n gs p e c i e sd i v e r s i t y ，an e wm u t a t i o no p e r a t o ri sd e s i g n e d ，w h i c h c o n s i s to fl o c a lp h e r o m o n eu p d a t i n gt h e o r yi na n tc o l o n ya l g o r i t h ma n d d i s t u r b a n c eo p e r a t o ri ns i m u l a t e da n n e a “n ga l g o r i t h m n e wa l g o r i t h mh a sa b e t t e rp e r f o r m a n c et h a nt h ea b o v ea l g o r i t h m ( 4 ) an e wa l g o r i t h mi sd e s i g n e df o rs o l v i n gm u l t i - o b j e c t i v et s pt h a ti s p r e v a l e n te x i s t e di nr e a il i f e ，w h i c ha d o p t sn e wa r c h i v i n gm e c h a n i s mb y i m p r o v i n gt h ea b o v ea l g o r i t h m t h ep e r f o r m a n c eo fa l g o r i t h mi sv a l i d a t e d t h r o u g has e r i e so fs i m u l a t i o ne x p e r i m e n t s i i i p s oi san e we v o l u t i o n a r yo p t i m i z a t i o nm e t h o d ，w h i c hc o u l dr e d u c e c o m p u t a t i o n a lb u r d e no fl a r g e s c a l 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 t h ea c h i e v e m e n t s6 ft h i st h e s i sh a v ei m p o r t a n tt h e o r e t i ca n dr e a i i s t i c s i g n i f i c a n c ei nr e s e a r c h i n 套m u i t io b j e c t i v ep a r t i c l e s w a r mo p t i m i z a t i o n ， e s p e c i a l l y i nr e a l i s t i c e n g i n e e r i n go p t i m i z a t i o np r o b l e m w i t hd i s c r e t e v a r i a b l e s k e yw o r d s ：p a r t i c l es w a r mo p t i m i z a t i o n ；a n tc o l o n ya l g o r i t h m ；t r a v e l i n g s a l e s m a n p r o b l e 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 ；g a m e s t r a t e g y i v 硕上学化论文 插图索引 图1 1 多目标优化的发展历程4 图2 1p s o 借助群居生物寻优原理图8 图2 2 粒子群算法流程图1 0 图2 3 蚁群路径搜索原理l l 图3 1 目标空间的p a r e t o 最优解和最优前沿1 8 图3 2 优化与决策的系统构成图l9 图3 3 从决策的观点对多目标优化方法分类2 0 图4 1 测试函数三上的p a r e t o 最优解3 3 图4 2 测试函数四上的p a r e t o 最优解3 3 图4 3 算法在测试函数五上比较3 4 图4 4 算法在测试函数六上比较3 4 图5 1n e p s o 算法流程3 8 图5 2n e p s o 与文献【4 8 】中算法的迭代曲线比较4 l 图5 3 改进的算法流程4 3 图5 4 三个算法运行l0 0 次的迭代曲线图4 4 图5 5 种群大小为5 0 的曲线图4 5 图5 6 种群大小为2 0 的曲线图4 5 图5 7 新算法在u l y s s e s 2 2 上迭代曲线图4 6 图6 1 求解多目标t s p 的算法流程图4 8 图6 2 各算法求得的p a r e t o 最优解分布情况5 0 图6 3 城市数目为2 0 的测试结果5l 图6 4 城市数目为3 0 的测试结果51 图6 5 城市数目为5 0 的测试结果5 2 v i i 面向多目标优化的群钾能贸法研究 附表索引 表4 1 本文算法与m o p s o 的参数设置3 0 表4 2 不同算法的解分布情况比较3 2 表4 3 不同算法的覆盖指标c 的比较3 2 表5 1 口和取不同值时收敛代数统计3 9 表5 2 实验参数设置4 0 表5 3 两种算法的搜索效率比较4 0 表5 4 三个算法运算l0 0 次的收敛比率和运算时间4 3 表5 5 算法参数设置4 4 表5 6 种群大小为5 0 的实验结果4 5 表5 7 种群大小为2 0 的实验结果4 6 表5 8u l y s s e s 2 2 问题上的统计结果4 6 表6 1 各算法找到的p a r e t o 最优解4 9 表6 2 各算法在覆盖指标c 上的比较4 9 表6 3 实验二的参数设置5 l v i i i 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行 研究所取得的研究成果。除了文中特别加以标注引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本 文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本人完全意识到本声明的法律后果由本人承担。 作者签名：劫】舷织日期：岬年s 月辞日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权湖南大学可以将本学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印 或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在j 解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打”) 作者签名： 导师签名： 剖枷囊 矽切 日期：抄叼年 日期：跏毋年 岁月印日 月4 日 硕上学位论文 1 1 研究背景与意义 第1 章绪论 多目标优化问题起源于许多实际复杂系统的设计、建模和规划，几 乎每个重要的现实生活中的决策问题都要在考虑不同约束中同时处理若 干相互冲突的目标，这些问题大大增加了问题的复杂程度。 传统的多目标优化方法是将各个子目标聚合成一个带正系数的单个 目标函数，系数由决策者决定，或者由优化方法自适应调整。为了获取 近似的p a r e t o 最优集，一些优化方法使用不同的系数来实施动态优化。 常见的古典方法有加权法、约束法、数学规划法等等，但是这些方法在 某些特殊条件下会表现出一定的局限性，包括： ( 1 ) 一些古典方法如加权法在求解多目标优化问题时，对p a r e t o 最 优前端的形状比较敏感，不能很好的处理前端的凹部。 ( 2 ) 求解问题所需的与应用相关的启发式知识经常不能获得，导致 无法正常实施优化。 ( 3 ) 古典方法共同存在的一个关键问题就是获得p a r e t o 最优解集合 必须运行多次优化过程，由于各次优化过程相互独立，往往得到的结果 不一致，令决策者很难有效的决策，而且要花费巨额时间。 近年来研究的较多的进化算法( 以遗传算法为主) 的优点在于可以 同时处理大规模的搜索空间，能够有效的克服古典方法的局限性。首先， 它能同时处理一组解，每运行一次算法就能获得多个有效解；其次，进 化算法对均衡面的形状和连续性不敏感，能很好地逼近非凸性或者不连 续的均衡曲线和曲面。通常利用进化算法求解m o p 的优化目的和希望达 到的目标包括以下几点。 ( 1 ) 进化结果的非劣前端与p a r e t o 前端的距离最短。 ( 2 ) 进化结果的分布性能好，通常希望其呈现均匀分布。 ( 3 ) 获得非劣前端的范围最大，即非劣解的目标空间覆盖每个子目 标尽可能广阔的范围。 另外一方面，进化算法存在收敛速度慢和容易陷入局部最优的不足。 普通的遗传算法在处理某些复杂问题时计算量过大，编码和解码问题较 为复杂，对有些问题难以找到最优解。作为基于迭代的优化方法，群智 能理论是一种全新的智能计算方法。事实上，群智能方法能够被用于解 面向多 标优化的群智能算法研究 决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已 扩展到多目标优化、数据分类、数据聚类、模式识别、电信q o s 管理、 生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真 和系统辫识等方面。作为群智能算法的优秀代表，粒子群优化算法 ( p a r t i c l es w a r mo p t i m i z a l i o n ，p s 0 ) 作为随机搜索方法之一，通常情况 下具有比普通进化算法更好的收敛效率、更少的c p u 运算时间、可直接 用实数编码、易于实现等一系列优点。随着进化算法在多目标优化领域 研究中的深入，如何将p s o 引入到多目标优化中也逐渐被人们所重视， 并且已经有了一些研究成果，进一步深入研究多目标粒子群优化算法具 有重要的理论意义和现实意义，可以预见，未来两三年将是多目标粒子 群优化算法研究的蓬勃发展期。 1 2 多目标优化的发展历程与研究现状 早在l7 7 2 年，f r a n k i i n 就提出了多目标问题矛盾如何协调的问题1 1 1 。 l8 9 6 年p a r e t o 首次从数学角度提出了多目标最优决策问题，并引入了 p a f e t o 最优解的概念。l9 51 年，k o o p m a n s 在生产和分配问题中提出有效 向量的概念1 2 j ，与此同时，k u h n 等人给出了向量极值问题有效解的必要 条件【3j 。至此，多目标优化逐渐受到人们的关注。从2 0 世纪5 0 年代末 到9 0 年代初，c h a r n e s ，z a d e h ，c r e o f r i o n ，s t e u e r 等人先后做出了卓有 成效的工作，出现了加权和法、目标规划法、约束法等基于权重的多目 标优化方法，在此期间多目标优化方法和理论得到更广泛的研究。近十 年来，随着进化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 技术和群智能( s w a r m i n t e l l i g e n c e ) 方法的兴起以及在科研和实践中的广泛应用，多目标优化 技术的发展更为迅猛，应用这些技术和方法求解多目标优化问题成为当 前一个热门的研究领域。 目前多目标进化算法的研究主要集中在以下几个方面：其一，使算 法的搜索向着p a r e t o 最优解集移动；其二，保持解在p a r e t o 解的界面或 者其附近均匀分布：其三，对于约束函数的处理。r o s e n b e r g 在他的博士 论文中最早提出可以将进化方法应用到多目标优化领域【4 】，但事实上文 中并没有给出真正的多目标进化算法( m u l t i o b i e c t i v ee v o l u t i o n a r y o p t i m i z a t i o n ，m o e a ) ，而是将多目标问题重新描述成单目标优化问题进 行求解；综述m o e a 的发展历程，大致可以分为两个阶段，第一阶段的 算法都比较简易，研究方向更趋向于“能用”一一即能用进化算法来描 述多目标优化问题，如向量聚合遗传算法( v e c t o ra g g r e g a t i n gg e n e t i c a l g o r i t h m ，v e g a ) 【引、n i c h e d 感应技术的遗传算法( n i c h e d p a r e t o 2 硕士学化论文 g e n e t i ca i g o r i t h m ， n p g a ) 1 6 j 、多目标遗传算法( m u l t i o b ；e c t i v eg e n e t i c a l g o r i t h m ，m o g a ) 【7 】等，而在第二个阶段，研究者们的兴趣逐渐从简 易能用转移到算法本身的效率上来，正是这个时期，进化算法在多目标 优化领域产生了深远的影响，如z i t z l e r 与t h i e l e 提出强化p a r e t o 进化算 法( s t r e n g t hp a r e t oe v o l u t i o n a r ya l g o r i t h m ，s p e a ) ，发表于国际权威 期刊i e e et r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n ，被大量研究者引 用。d e b 等人改进其前一版本的基于非支配排序的遗传算法 ( n o n d o m i n a t e ds o r t i n gg e n e t i ca l g o r i t h m ，n s g a ) 提出效率更高的 n s g a i i 【9 1 ，对第一版的改进是根据产生的各种非劣前端，采用更好的归 档策略，从而减少算法运行的整体时间，该文同样发表于i e e e t r a n s a c t i o n so ne v o l u t i o n a r yc o m p u t a t i o n ，成为该领域绝大多数研究者 的引用对象。z i t z i e r 对s p e a 做了改进提出了新的s p e a 2 【1 0 】，文献【l ll 比较系统的介绍了很多产生过重要影响的多目标进化算法，并对2 0 0 6 年 以前的文章进行了归类总结。最近三年，相继有人提出基于量子遗传算 法的多目标优化方法【12 1 ，免疫克隆多目标算法【1 引，多目标蚁群算法【1 4 】， 多目标粒子群优化算法等【”一 。国内学者对多目标进化算法也做了深入 的研究，崔逊学等人提出利用不同准则之间引入偏好来解决该问题，并 设计了多目标调和遗传算法【1 8 】，该作者于2 0 0 6 年出版了多目标进化算法 的专著【1 9 】，石川，李清勇，史忠植通过消除解之间的冗余比较以减少计 算代价，提出了一种快速的多目标进化算法【2 0 1 ，文献【l8 ，2 0 】发表于国内 权威期刊软件学报，该刊于2 0 0 9 年2 月份出版了公茂果，焦李成， 杨咚咚等的最新多目标进化算法综述文章【2 1 】 作为群智能算法的优秀代表，粒子群优化算法在单目标优化中取得 的巨大的成功，学者们开始通过设计多目标粒子群算法来解决多目标进 化算法的收敛速度慢，易于陷入局部最优解的问题。当前，多目标粒子 群算法的研究处于起步阶段，研究的主要工作是模仿多目标演化算法的 策略设计新的多目标粒子群算法，并将两类算法进行比较和分析。据文 献【2 2 】所述，m o o r e 和c h a p m a n 在一篇未公开发表的文稿中第一次提出 用粒子群算法解决多目标优化问题，目前来看，主要多目标粒子群优化 算法有以下几类：p a r s o p o u l o s 和v r a h a t i s 提出的加权方法【2 3 】( 类似于 v e g a ) ，h u 和e b e r h a r t 的字典排序方法( 类似于文献【2 4 】中介绍的字典 排序多目标进化算法) ，文献【2 5 】中提出的子群体方法也具有一定的代表 性，大部分研究者从p a r e t o 方法出发来研究多目标粒子群优化算法【2 6 28 1 ， 另外还有一些学者提出了求解多目标优化问题的混合算法1 2 引。 关于国内学者对多目标粒子群算法的研究动态，论文对最近几年发 3 面向多目标优化的群智能算法研究 表的相关文献数目做了一个调查，在维普资讯中文科技期刊数据库中， 检索到以“多目标”+ “粒子群”为标题或者关键字的论文分布情况如下： 截止到2 0 0 8 年收录到数据库中的文献一共l l8 篇，2 0 0 3 年至2 0 0 6 年的 论文数目为3 2 篇，其中2 0 0 3 年1 篇，2 0 0 4 年2 篇，2 0 0 5 年7 篇，2 0 0 6 年2 2 篇。而2 0 0 7 年与2 0 0 8 年两年的文献数目将近前四年所有文献之和 的3 倍，达到8 6 篇，可见国内对多目标粒子群优化算法的研究呈现出快 速上升的趋势。 总结多目标优化算法的发展历程，可以用图1 1 来概括： 图1 1 多目标优化的发展历程 4 硕上学位论文 1 3 主要研究内容与文章结构 1 3 1 主要研究内容 本文主要研究群体智能的基本原理，介绍多目标问题的发展历程与 优化方法的改进。目前，粒子群优化算法在智能计算领域内已经成为了 一个研究热点，越来越多的基于微粒群模型的算法被相继提出。本文基 于博弈论的思想，提出了一种基于博弈策略的多目标粒子群优化算法； 在拓展传统p s o 模型方面，也做了一些工作；在应用领域，分别提出了 解决单目标和多目标旅行商售货问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 的协同进化粒子群算法。本文的主要研究工作和成果包括： 1 通过理论分析和实验仿真，研究粒子群优化算法的基本原理和性能， 参数的优化以及一些新的基于群智能算法的计算模型，如基于量子编 码的粒子群优化算法、基于量子d e l t a 势阱和量子振荡器的粒子群优 化算法，根据算法原理，编程实现这些算法，比较各种算法在解决实 际问题中的性能，从中选取适合于扩展到求解多目标优化问题的算法 模型。 2 根据博弈论的思想，提出一种基于博弈策略的多目标粒子群优化算法， 将目标函数看作智能体引领个体往各自有利的方向搜索，它们根据自 身的效应函数制定不同的搜索策略。从理论上分析算法的收敛性质， 通过仿真实验对该算法与n s g a i l 、m o p s o 做了一个在靠近真实 p a r e t o 前沿的程度和分布的均匀度上的比较，结果表明算法是有效的。 3 提出了一种面向t s p 问题的协同进化粒子群算法，结合一种适合t s p 问题与粒子群算法的特殊编码方案，在此基础上新定义了两个粒子间 的位置“协同加法”运算，替换原来的速度方程，以实现粒子间信息 交换，然后增加一个变异算子，用来保持种群多样性，防止早熟收敛。 4 为了在收敛速度和保持种群多样性上取得平衡，对上述算法做了进一 步的优化，利用蚁群算法的局部信息素更新原理和模拟退火算法的扰 动算子组成新的变异算子，并对相关参数做了一些优化调整，从整体 来说，改进后的算法性能有较大提升。 5 针对多目标t s p 问题的优化模型，基于上述算法做一些改进，将其应 用到多目标t s p 问题的优化求解中，引进归档集，保存当前搜索到的 p a r e t o 最优解，通过仿真实验对算法进行验证。 5 面向多目标优化的群钾能算法研究 1 3 2 本文的工作安排 本文章节组织如下： 第一章：绪论，概述多目标优化问题及研究背景，国内外研究情况， 介绍论文研究内容以及组织结构。 第二章：群智能算法与粒子群优化，介绍群智能的基本理论和核心 概念，分析介绍了当前常用的几种典型的粒子群算法，并根据对国内外 关于粒子群算法研究的相关文献发展趋势，给出算法的改进方向和应用 领域。 第三章：多目标优化及粒子群算法求解模型，对多目标优化的数学 模型和基本概念做了简要描述，对各类多目标优化算法进行分类，总结 和概括多目标粒子群优化算法的几种不同模型。 第四章：首先介绍量子p s o 的基本模型，并根据博弈论的思想，提 出一种新的基于博弈策略的多目标粒子群算法，详细分析了博弈模型的 建立过程，并从理论上证明算法的收敛性质，最后通过多个基准校验函 数仿真实验，验证算法的有效性。 第五章：研究和分析粒子群算法在组合优化方面的一些研究成果， 提出一种新的解决t s p 问题的粒子群算法，并通过仿真实验验证两种不 同变异策略对算法性能的影响，与参考文献中的算法做详细的对比分析。 第六章：提出一种解决多目标t s p 问题的粒子群优化算法，对算法 性能做了详细的测试。 最后，对研究工作进行总结，并提出下一步工作的展望。 6 硕上学位论文 2 1 引言 第2 章群智能算法与粒子群优化 为了解决复杂搜索与优化问题，各种进化方法与非进化方法被相继 提出，在这些方法中，出现了一类比较特殊的基于进化计算与群集智能 ( s w a r mi n t e l l i g e n c e ) 的方法，如粒子群优化算法、蚁群优化算法等， 它们的主要优势在于能非常方便的应用到待解决的特殊优化问题中，易 于编解码，并且可以在更高维空间中进行搜索，而性能上不会有太大的 变化f 30 1 。 本章主要介绍群智能算法的基本原理，描述两种典型的群智能算法， 粒子群优化算法和蚁群算法，以及粒子群优化算法的实现流程，重点研 究粒子群算法的改进方向与应用领域。 2 2 群体智能 作为群体智能的优秀代表，粒子群算法和蚁群算法具有很多共同点， 它们的模型都来自学者们对自然界中的群居生物的研究。群居生物以集 体的力量，进行觅食、御敌、筑巢，这种由于个体之间以及个体与环境 之间交互而使群体所表现出来的智能，就称之为群智能，如蜜蜂采蜜、 筑巢、蚂蚁觅食等。人们从群居生物的互相协作中，得到启迪，研究其 中的原理，以此原理设计出群智能算法。群智能理论的基本原理是以生 物社会系统( b i o l o g ys o c i a ls y s t e m ) 为依托的，也就是由简单个体组成 的群落与环境以及个体之间的互动行为。这种生物社会性的模拟系统利 用局部信息相互协作产生难以估量的群体智能行为。作为基于迭代的优 化方法，群智能算法是一种全新的进化计算方法，事实上，群智能方法 能够被用于解决大多数优化问题或者能够转化为优化求解的问题。现在 其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电 信q o s 管理、生物系统建模、流程规划、信号处理、机器人控制、决策 支持以及仿真和系统辩识等方面1 3 。群智能理论和方法为解决这类应用 问题提供了新的途径。 2 2 1 粒子群优化算法 粒子群优化( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 算法是近年发展起 7 来的一种新必智能i f 算方法，又称为微粒群优化算法、群智能优化算法 等- 最先由美国的心理学家j a m e sk e n n e d y 和电气j 程师r us s e l le b e r h ar t 共同提h ”，其基本思想是受他们早期对鸟类群体行为研究结果的启发， 并利用了生物学家f r a n kh e p p n e r 的生物群体模型。其主要特点是群体搜 索策略和模拟社会的特性，它由系列功能简单的个体按一定规则相互 协作，最终在宏观上表现出具有寻优能力的智能行为。通常情况下具有 比普通进化算法更好的收敛效率、更少的c p u 运算时间、可直接用实数 编码、易于实现等一系列优点。 粮于群算法与其它进化类算法相似，也采用“群体”与“进化”的 概念，同样也是依据个体( 粒子) 的适应值大小进行操作。所不同的是， 粒子群算法不像其它进化算法那样对于个体使用进化算子，而是将每个 个体看作是在一维搜索空间中的个没有重量和体积的微粒，并在搜索 窄间中以 定的速度飞行。该飞行速度由个体的飞行经验和群体的飞行 经验进行动态调整。p s 0 的原理如图2l 所示，每一个粒子根据自身历史 最优位置( p c r s o n a lb e s t ，自身经验) 与群体盛优位置( g l o b a j b e s t ，社会 经验) 调整自己的当前位置，最终向全局最优( b e s ts o l u t i o n ) 靠近。 图21p s 0 借助群居生物寻优原理图 在粒子群优化算法中，每个可能产生的解表述为群体中的一个微 粒，它们都具有自己的位置向量和速度向量，其中每个粒子所处的伉置 都表示问题的个潜在解，记作x 。粒子通过不断调整自己的位置x 来 搜索新解。每个粒子都能记住自己搜索到的最好解，记作p ，以及整个 群体经历过的最好位置，即日前搜索到的全局最优解，记作，。锥个粒 子都有一个速度记作r ，设 x ，= ( x m z m，z 。) 为微粒f 的当前位置： r ，= ( v v 一，v ，) 为微粒，的当前e 行速度； 8 硕上学位论文 只= ( p mp f 2 ，p m ) 为微粒f 所经历的最好位置。对于最小化问题， 目标函数值越小，对应的适应值越好。 o + 1 ) = 缈o ) + 叩i 朋聆以) ( 匕( f ) 一如( f ” + 阳蒯( ) ( ( f ) 一如( f ) ) “7 其中n d 表示第f 个粒子第d 维上的速度，为粒子保持上一速度的惯性权 重，叩，叩2 为调节尸f d 和以d 相对重要性的参数，口刀d ( ) 为随机数生成函数。 这样，可以得到粒子的下一位置： j 乙o + 1 ) = j 乙o ) + p + 1 ) ( 2 2 ) 以及一个由目标函数决定的适应度，所有微粒在搜索空间中以一定的速 度飞行，通过追随当前搜索到的最优值来寻找全局最优。 基本微粒群算法的流程为： 第一步，依照初始化过程，对微粒群的随机位置和速度进行初始设 定； 第二步，计算每个微粒的适应值； 第三步，对于每个微粒，将其适应值与所经历过的最好位置p 6 p j ，t 的适应值进行比较，若较好，则将其作为当前的最好位置； 第四步，对每个微粒，将其适应值与全局所经历的最好位置的适应 值9 6 p j f 进行比较，若较好，则将其作为当前的全局最好位置； 第五步，根据方程( 2 1 ) ( 2 2 ) 对微粒的速度和位置进行进化； 第六步，如未达到结束条件通常为足够好的适应值或达到一个预设 最大代数( m a xg e n ) ，则返回第二步。 其流程图如图2 2 所示。 9 而向多 j 杯优化的群智能算法研究 初始化种群、位置向量x 、速度向 量v 、p b e s t 和g b e s t ，设置k = o 2 2 2 蚁群优化算法 图2 2 粒子群算法流程图 作为与遗传算法同属一类的通用型随机优化方法，蚁群算法不需要 任何先验知识，最初只是随机地选择搜索路径，随着对解空间的“了解”， 搜索变得有规律，并逐渐逼近直至最终达到全局最优解。蚁群算法对搜 索空间的“了解”机制主要包括三个方面【3 3 1 ( 1 ) 蚂蚁的记忆，一只蚂蚁搜索过的路径在下次搜索时就不会再被选 l o 硕士学化论文 择，由此在蚁群算法中建立t a b u ( 禁忌) 列表来进行模拟； ( 2 ) 蚂蚁利用信息素( p h e r o m o n e ) 进行相互通信，蚂蚁在所选择的 路径上会释放一种叫做信息素的物质，当同伴进行路径选择时，会根据 路径上的信息素进行选择，这样信息素就成为蚂蚁之间进行通讯的媒介； ( 3 ) 蚂蚁的集群活动，通过一只蚂蚁的运动很难到达食物源，但整个 蚁群进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，在路 径上留下的信息素数量也越来越多，导致信息素强度增大，蚂蚁选择该 路径的概率随之增加，从而进一步增加该路径的信息素强度，而某些路 径上通过的蚂蚁较少时，路径上的信息素就会随时间的推移而蒸发。因 此，模拟这种现象即可利用群体智能建立路径选择机制，使蚁群算法的 搜索向最优解推进。 蚁群算法所利用的搜索机制呈现出一种自催化或正反馈的特征，因 此，可将蚁群算法模型理解成增强型学习系统。图2 3 说明了蚂蚁群体 的路径搜索原理和机制。 图2 3 蚁群路径搜索原理 假定障碍物的周围有两条道路可从蚁巢到达食物，即( 蚁巢一a b d 食物) 和( 蚁巢a c d 食物) ，路径的长度分别为4 和6 。每只蚂蚁在单 位时间内移动一个单位长的距离，并在走过的路径上遗留一个单位的信 息素。开始时所有道路上未留有任何信息素，假设在f = o 时刻，有2 0 只蚂蚁从蚁巢出发移动到a 。它们以相同概率选择左侧或右侧的路径， 冈此有l0 只蚂蚁走左侧，lo 只走右侧。在f = 4 时刻，第一批找到食物 的蚂蚁将返回，在f = 5 时刻，两批蚂蚁将在d 点相遇，此时b d 上的信 息素数量与c d 上的相同，因为各有l0 只蚂蚁选择了相应的道路。从而 有5 只返回的蚂蚁将选择d b 而另5 只选择d c 。在f = 9 时刻，前5 只 而向多 j 杯优化的群智能算法研究 蚂蚁又返回a 并且再次进行往左还是往右的选择。这时，a b 上的信息素 数量是2 0 而a c 上是i5 ，因此将有较多的蚂蚁选择往左，从而增加了该 路径的信息素数量。随着这种过程的不断进行，两条路径上的信息素数 量的差距将越来越大，直到绝大多数蚂蚁都选择了最短的路径，正是由 于一条路要比另一条道路短，因此，在相同的时间区间内，短的路线会 有更多的机会被选中。 基本的蚁群算法模型由下面三个公式描述： r an 9 譬2 葫 3 ， 厶一。u l u _ ，e 爿 乃0 + 1 ) = p 勺( ，z ) + 力 ( 2 4 ) = 弋争 如果，( 七，l ) = l ( 2 5 ) 厶厶 公式( 2 3 ) 、( 2 4 ) 和( 2 5 ) 中：坍为蚂蚁个数，刀为迭代次数，f 为蚂蚁所在位置，j 为蚂蚁可以到达的位置，彳为蚂蚁可以到达位置的集 合，珂玎为启发性信息，这里为由f 到_ ，的路径的能见度，即l d u ，三七为 目标函数，这里为两点间欧式距离，q 由f 到j f 的路径的信息素强度，露 为蚂蚁七由，到，的路径上留下的信息素数量，口为路径权，为启发性 信息的权，户为路径上信息素数量的蒸发系数，q 为信息素质量系数，_ p 为蚂蚁七从位置，移动到位置的转移概率，( 七，) 是表示蚂蚁七是否从 位置，移动到位置，如果是则为l ，否则为0 。 目前，除了业已得到公认的遗传算法、模拟退火算法、禁忌搜索算 法等计算智能算法外，新加入这个行列的蚁群算法已开始崭露头角，为 困难的组合优化问题提供了新颖且有竞争力的求解方法。 2 3 粒子群算法的改进与应用 2 3 1 粒子群算法的改进 粒子群优化算法自提出以来，吸引了众多学科的研究人员的目光， 这期间，大量针对如何改进粒子群算法的论文被相继提出，第一类表现 为对p s o 参数的调整与优化；第二类改进方法主要是就如何提高算法的 全局寻优能力，防止早熟收敛而引进保持种群多样性的操作；第三类方 法是基于新的计算模型，如量子粒子群优化算法，采用量子计算模型， 仍然利用基本p s o 种群，个体经验和群体经验实现进化；第四类方法是 1 2 硕1 ：学位论文 与其他智能算法结合，与遗传算法中的选择、变异等操作相结合，使其 更加具备进化算法的特征，提高全局寻优能力，还有混合模拟退火粒子 群算法、基于克隆免疫的混合粒子群算法等；其它的改进方向主要是为 了拓展p s o 的应用领域而做的努力，如将原本只适合于在连续解空间求 解的方法拓展到离散空间、整数空问等。 ( 1 ) 参数优化，p s o 算法与其它智能计算方法的一个显著区别就是 所需调整的参数很少，但是这些关键参数的设置对算法的精度和效率却 存在显著影响。文献【3 4 】针对算法中的种群规模、迭代次数和粒子速度的 选择方法进行了详细分析，利用统计实验方法对约束优化问题的求解论 证了这三个参数对算法性能的基本影响，并给出了具有一定通用性的三 种参数选择原则，在文献【35 】中y s h u i 和r e b e r h a r t 首次提出了惯性 权重的概念，并