（检测技术与自动化装置专业论文）改进微粒群算法及在优化中的应用.pdf

摘要 摘要 优化技术指的是在满足一定约束条件下，通过找寻一组参数值，能够 使目标函数值取到最小或最大。伴随着人类认识与改造世界能力的不断 扩大，我们日益迫切要求高效的优化技术和智能计算的出现。微粒群优 化算法是一种基于群智能的随机优化算法，算法具有原理简单、参数少、 收敛速度快、所需知识领域较少等优点，故该算法自提出以来便获得很 大发展，而且被成功应用到众多领域。微粒群算法的优点的是有较强的 全局搜索能力，但缺点是易陷入局部极值。本文主要研究的是对微粒群 算法的改进与应用，并进行了仿真研究。研究内容如下所述： 1 、阐述了微粒群算法有关背景知识，介绍了此算法产生的基础。然 后讨论了微粒群算法的基本原理和算法的流程。目前微粒群算法存在许 多参数依赖经验法确定的问题，而且参数的不同选择可能会直接影响算 法的收敛性，甚至会导致算法不收敛。针对微粒群算法这一问题，本文 对微粒群算法的参数选择进行了研究实验，给出了选择参数的基本方法。 2 、总结了研究者提出几种重要改进算法，在分析前改进算法基础上， 针对算法存在的缺点，本文尝试提出了一种改进方案，然后用于无约束 函数和约束函数优化算例，实验结果说明了改进算法的有效性和可行性。 3 、简要介绍了p i d 控制器的原理，并将提出的改进算法用于工业p i d 控制器的参数优化，以一个工业上常用的二阶时滞传递函数为模型，通 过m a t l a b 仿真证明了该改进算法的可行性和优越性。 4 、将微粒群算法这一新兴算法应用到i p 网络的服务质量( q o s ) 路 由优化的实例中，在满足服务质量的要求的同时又使所选路径费用最小 为优化指标，对网络的进行仿真，通过仿真实验表明，此算法具有确实 具有良好的效果。 关键词：优化算法；微粒群算法；p i d 控制器参数优化；服务质量路由 a b s t r a c t o p t i m i z a t i o nt e c h n o l o g yi sb a s e do nm a t h e m a t i c s w h i c hc a ns o l v e v a r i o u sc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s o p t i m i z a t i o nm e t h o di st o l o o kf o ras e to fp a r a m e t e r si n d e f i n i t er e s t r i c t i o nw i t ht h ea i mo f m a x i m i z i n g o r m i n i m i z i n g t h e o b j e c t i v e f u n c t i o n w i t h p e o p l e s c o g n i t i o na n dt r a n s f o r m a t i o nw o r l da b i l i t ye n l a r g e dd a yb yd a y ，p e o p l e n e e d i n t e l l i g e n c eo p t i m i z a t i o n a n d h i g h p e r f o r m a n c eo p t i m i z i n g t e c h n o l o g yu r g e n t l y 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 ) i sas t o c h a s t i c o p t i m i z a t i o na l g o r i t h mw h i c hi s b a s e do ns w a r mi n t e l l i g e n c ea n da n e v o l u t i o n a r yc o m p u t a t i o nt e c h n i q u e i ti se a s yt ob ei m p l e m e n t e da n d i t s c o n c e p ti s i th a sa c h i e v e dg r e a td e v e l o p m e n ti ns e v e r a ly e a r sa n dh a s b e e ns u c c e s s f u l l yu s e dt os o m ef i e l d sa f t e rb e i n gp r e s e n t e d p a r t i c l e s w a r mo p t i m i z a t i o na l g o r i t h mh a sas t r o n ga b i l i t yt oa c h i e v et h em o s t o p t i m i s t i cr e s u l t m e a n w h i l ei t h a sad i s a d v a n t a g es of a ra si t sl o c a l m i n i m u mi sc o n c e r n e d i m p r o v e m e n ta n da p p l i c a t i o no fp a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h ma r em a i n l yd i s c u s s e di nt h i sd i s s e r t a t i o n i nt h i s a r t i c l et h em a jo ri n n o v a t i o n sa r ea sf o l l o w s ： 1 d i s c u s st h ef o u n d a t i o na n dt h eb a c k g r o u n dk n o w l e d g eo fp s o i ta l s oh a sd i s c u s s e dt h ep r i n c i p l e sa n dd e v e l o p m e n t o fp s oa n d i n t r o d u c e dt h ep r o c e e d i n go ft h ea l g o r i t h m s i n c e t h e r eh a s m a n y p a r a m e t e r sb a s e do nt h ee x p e r i e n c ef o c u so n t h ea t t e m p tr e s e a r c h ，a n dc h o o s e t h ed i f f e r e n tp a r a m e t e r sw h i c hc a nd i r e c t l ya f f e c tt h ea l g o r i t h mr e s u l t so ft h e r e s e a r c h s oi t sr e s t r a i n e df e a t u r e sa r eb a d t h ed i s s e r t a t i o nh a sm a d ea n a t t e m p tr e s e a r c ho nt h ep a r t i c l es w a r mo p t i m i z a t i o nf r o mt h ea s p e c to ft h e p a r a m e t e r s s e l e c t i o n u n d e rt h i sb a c k g r o u n d 2 s u m m a r i z e ds e v e r a lm o d i f i e di d e a so fp s oa n do nt h eb a s eo ft h e l a c ko ft h ea l g o r i t h mp r o p o s e da ni m p r o v e m e n tp r o g r a m u n c o n s t r a i n e d f u n c t i o no p t i m i z a t i o na n dc o n s t r a i n e df u n c t i o no p t i m i z a t i o np r o b l e m s s h o wt h ee f f e c t i v e n e s sa n df e a s i b i l i t yo fi m p r o v e da l g o r i t h m 3 i n t r o d u c e dt h ep r i n c i p l eo fp i dc o n t r o l l e ra n dt h e i m p r o v e d a l g o r i t h mi sa p p l i e dt ot h ep i dc o n t r o l l e rp a r a m e t e ro p t i m i z a t i o n t a k ea t i m e - d e l a yt r a n s f e rf u n c t i o nt h a ti sc o m m o n l yu s e di n i n d u s t r y a s a m o d e la n dt h ei m p r o v e da l g o r i t h mi so fb e t t e rs u p e r i o r i t yt h r o u 曲t h e m a t l a bs i m u l a t i o n 4 t h eb a s i cp s o a l g o r i t h mi sa p p l i e dt ot h ei pn e t w o r k sq u a l i t yo f s e r v i c e ( o o s ) r o u t i n g t om e e tt h eq o sr e s t r i c t i o ni st h et a r g e to ft h e o p t i m i z a t i o n ，a tt h es a m et i m et h es e l e c t e d r o u t i n g s c o s tm u s tb e m i n i m u m t h es i m u l a t i o nr e s u l to nan e t w o r ks h o w st h a t t h ep s o a l g o r i t h mi sb e t t e r k e y w o r d s ：o p t i m i z a t i o na l g o r i t h m ；p a r t i c l es w a r mo p t i m i z a t i o n ；t h e p a r a m e t e ro p t i m i z a t i o no fp i d c o n t r o l l e r ；q u a l i t yo fs e r v i c er o u t i n g i i i 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研 究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识 到本声明的法律结果由本人承担。 学位论文作者签名：劐葺 z 咖7 年f 月以日 l 学位论文版权使用授权书 本学位论文作者完全了解我院有关保留、使用学位论文的规定，即： 我院有权保留并向国家有关部门或机构送交论文的复印件和电子版，允 许论文被查阅。本人授权武汉工程大学研究生处可以将本学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存和汇编本学位论文。 保密o ，在年解密后适用本授权书。 本论文属于 不保密吼 ( 请在以上方框内打“4 ) 学位论文作者签名：谢专 训气年r 月巩日 指导教师签名：蝴婶矽 1 如粕 第1 章绪论 1 1 研究背景 第1 章绪论 最优化问题是人们长期探讨的在很多方案找寻最优的一个课题，1 7 世 纪，英国科学家n e w t o n 和德国l e i b n i t z 创造了微积分，b e r n o u l l i 、 e u l e r 、l a g r a n g e 和w e i r s t r a s s 完善微积分，法国数学家c a u c h y 首次研 究了函数随着哪个方向下降最快的问题，这被称为最速梯度下降法，用 此方法来解决无约束问题n 2 1 。随着时间慢慢发展人们深入开展研究优化 问题。二十世纪中期优化技术的发展成为迫切需要同时也出现了求解的 有力工具。因此，优化理论和及其算法迅速发展起来，形成一门新的学 科。现在已经出现了有动态规划、线性规划、整数规划、非线性规划、 几何规划、动态规划、随机规划、网络流这些分科，这些优化技术应用 到许多工程领域的包括系统控制方面和人工智能方面等。 上面所提到的经典优化算法通常是按在某一区域内搜索的方法为基 础并且全部是通过迭代来提高问题域中唯一的候选解，这些算法决定了 它们解决一般的小规模并且非常清楚定义的问题还是比较有效的。但在 解决实际工程问题的过程中人们对这些算法的解得精确程度或者说是消 耗的时间不满意，认清楚这一点后，人们就开始追求一些能够用于大规 模的并且具有智能特征的算法。自从二十世纪八十年代以来，出现了一 些很新颖的优化算法，如混沌口。5 1 、人工神经网络( a n n ) 。9 1 、遗传算法 ( g a ) 1 0 - 1 2 、进化规划( e p ) n 轧1 4 、模拟退火( s a ) n 5 1 们、禁忌搜索( t s ) n 7 1 引，这些算法它们的思想和内容包括很多方面，比如物理的、数学的、 生物进化的。在优化领域中，我们把这些算法叫做智能优化算法 ( i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ) 1 9 j 。 本文所研究的微粒群算法( 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 ) 是k e n n e d y 和e b e r h a r t 发明的另一种智能优化算法n 引。这个微粒群算法 从出现就引起学者关注，并且很多人热衷研究，而且微粒群算法在众多 的方面被成功应用。缺陷是p s o 的发展很短暂，需要我们来解决一些问 题。首先，p s o 在求解优化维度比较高，问题比较复杂的时候，就会出现 武汉t 程大学硕十学位论文 早早向最好的地方聚拢的问题。其次，p s o 在向最好地方靠拢的速度太慢 了。我们还发现了大多数微粒群算法解决带有一定限制的优化问题有难 度。发现这些问题我就对微粒群算法再次研究，提出相应的改进，并将 改进算法用于新的优化问题。 。 1 2 最优化问题 1 2 1 最优化问题分类2 0 3 最优化问题依据决策变量不同分为带有一定的约束的优化问题与没 有一定约束的优化问题。如果说是对象是连续状态的的话就是函数优化 问题，如果对象是离散状态的话就是组合优化问题。 ( 1 ) 无约束最优化与约束最优化 最优化问题的一般形式可表示为 m i n 厂( x ) ( 卜1 ) stxx 其中，x r ”是决策变量，f ( x ) 被称为目标函数，xcr ”被称为可行域 或者约束集。而且如果x ：r ”，最优化问题就可以表示没有约束的最优化 问题。 约束最优化问题一般形式表示为 m i n 厂o ) j j ( x ) = 0 ，i e e ， ( 1 2 ) e ( x ) 0 ，i e i ， 式子中e 表示约束是等式的指标集合；，约束是不等式的指标集合； c(x)是约束函数。j 如果目标函数是线性函数和约束函数均也是线性函数的话，那不就是 线性规划问题。那显而易见的是目标函数和约束函数如果有一个x 的不是 线性的函数时，那肯定就是非线性规划问题。 ( 2 ) 函数优化与组合优化 函数优化描述：令s 为r ”上的定义域。厂：s r 是维数为刀实数函数， 所谓要求出厂在s 域上全面的最好的解，就是要找到一个k ；。e s 并且能够 第1 章绪论 使得函数值在定义域里面是所有范围里面的最好的。即可以表示为 v x e s ：厂( l 。) e f ( x ) 。由于我们碰到的许多工程问题都有一些限制条件， 所以说有对有限制条件的函数进行优化，我们一直都比较关注这类对象。 组合优化描述：所有的状态我们都可以求出一个解，我们把所有的解 用这样q 。“，s ：，s o 的一个空间来表示，把墨代入到每一个函数里面就 可以求得一个值的集合用c ( ) 表示，在这个里面找到最好的解s ，使得 v t q ，c ( s ) 一r a i n c ( s f ) 。 ( 3 ) 局部优化和全局优化瞳 局部优化算法从一个给定的初始点开始，依据一定的方法找寻下一个 更好的解，使得目标函数的值得到改变，搜寻直到满足某种停止准则。 目标函数我们都希望解析。如果我们碰到了一些限制的条件不是相通的、 目标函数离散的问题，那这些问题用解析确定性方法求解难。 1 2 2 无免费午餐( n f l ) 在研究最优化理论的漫长过程中，w o l p e r t 和m a c r e a d y 的论文提出 并且严格证明了一个无免费午餐定理，简称n f l 乜副。该定理只是在有范围 内的搜索空间中定义的，对没有限制范围的搜索地方里的结论我们不清 楚。有一点我们知道用计算机实现的搜索算法必是在一定范围内的搜索 空间内实施的，所以该定理肯定对现存的所有算法都适用。 n f l 定理只是说的是对所有函数集，所有的最优化算法都是相同一样 的。但是对于一个特定的函数集，结论也不可能成立，这些函数更多表 现出的是随意性。然而，在我们所在的现实生活中大多数的函数通常有 一定的结构，并且的是有简单的描述，这些类型的函数便形成了所有函 数集内的相当数量的子集。这些考虑都使得n f l 发展增强版本来对更小 的函数子集进行研究。 1 3 进化计算 进化算法的两个特点我们说是： 群体中个体之间的互相交换资料。 一是整个群体共同的搜索策略，一是 以下两个方面体现了它们的优越性， 武汉工程大学硕七学位论文 首先，在搜索过程中，进化算法都不容易把某一区域内的最好地方当作 整体的最好地方，第二，进化算法的特点在于它们用于巨量并行机还是 比较适合的；第三，进化算法能够准确迅速地解决非常困难的问题；基 于以上的优越性，进化算法已经被我们广泛应用到最优化问题。 1 3 1 遗传算法 遗传算法是模拟自然遗传学机理和生物进化理论而形成的一种全局 并行的、随机搜索方法瞳3 f 。遗传算法具有强鲁棒性，并具有收敛到全局 最优的能力。1 9 7 5 年，j o h nh o l l a n d 首次在自然界和人工系统的适应 性一书中全面、系统地对遗传算法作了描述，标志着该算法的问世， h o l l a n d 本人也被视为遗传算法的创始人。遗传算法是一种基于自然选择 和遗传进化的搜索算法，它将生物进化过程中适者生存规则与群体内部 染色体的随机信息交换机制相结合。遗传算法通过正确的编码机制和适 应度函数的选择来操作称为染色体的二进制串( 1 或o ) ，每个二进制串 表示搜索空间的一个点。它模仿生物遗传及进化的步骤，在所求解的问 题空间上进行全局的、并行的、随机的搜索优化，朝全局最优方向收敛。 遗传算法的基本步骤： ( 1 ) 随机产生初始种群，一定数目的个体，每个个体表示为染色体 单基因编码。 ( 2 ) 计算个体适应度，并判断是否符合优化准则，若符合，输出最 佳个体及其代表的最优解，并结束计算，否则转向第三步。 ( 3 ) 依据适应度选择再生个体，适应度高的个体被选中的概率高， 适应度低的可能被淘汰。 ( 4 ) 依照一定的交叉概率和交叉方法，生成新的个体。 ( 5 ) 按照一定的变异概率和变异方法，生成新的个体。 ( 6 ) 由交叉和变异产生新的一代种群并返回第二步进行循环。 遗传算法的流程图如下： 第1 章绪论 1 3 2 进化规划 图1 1 遗传算法的流程图 进化规划是由美国人l j f o g e l 等人提出。其智能行为就是要其具 有能预见到现在处于什么状态的环境中，并按照给定的目标作出适当响 应的能力。这种计算方法是依据环境中将要出现的下一个符号及预先定 义好的目标来确定的。进化规划根据被正确预测的符号数来计算适应函 数值。演化规划中常用有限态自动机( 简称f s m ) 来表示这样的策略。 l j f o g e l 等一些人借用进化的思想对一群f s m 进行演化然后得到了好的 新的f s m 。随后他们在数据论断、模式识别和控制系统的设计等问题当中 采用了这种方法，效果良好。 1 3 3 进化策略 进化策略是在欧洲独立于遗传算法和进化规划而发展起来的一种进 化算法瞳4 l 。1 9 6 3 年，在利用流体工程研究所的风洞做实验时德国大学的 两名学生i 1 e c h e n b e r 和h p s c h w e f e l 提出了一种进化策略思想的依据 是按自然突变和自然选择的生物进化思想。很久之前进化方法的群体里 武汉t 程大学硕士学位论文 面只有一个个体而且也只使用变异的操作。每一次变异结束后，这个个 体就将会和它的父体进行比较，哪个更优就把哪个作为下一代新的个体， 这种思想就是( 1 + 1 ) 进化策略。 ( 1 + 1 ) 进化策略存在的问题就是难以以集中的方式向最好的位置靠拢， 而且找到最好位置的效率也低。想解决这些问题可以增加群体里面单个 个体的数目，这样就是( + 1 ) 进化策略，这个时候群体里面的单个个体的 数量是，但只是随意会出现一个变异个体。想更一步提高效率，后来又 产生了( + a ) 和( 肛，a ) 进化策略，( + a ) 进化策略是群体内的肛个个产生a 个后下一代；而( ，a ) 思想就是对新的a ( ) 个个体之间做一下比较，然 后在其中选择个最好的。 1 4 群智能算法简介 群智能算法( s w a r mi n t e l l i g e n c e ，s i ) 指的是“没有智能的主题通 过合作的形式表现出智能行为的特性”。在没有集中控制且不提供全局 模型的前提下，群智能算法为寻找复杂的分布式问题求解方案提供了基 础2 5 2 6 3 。 蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 和微粒群优化算法 ( 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 ) 是我们知道的群智能领域两种 主要算法。前一个讨论蚂蚁食物采集，应用离散优化问题。后一个发展 成为一种很好的优化工具。群智能算法所根据的是按照一定的概率的搜 索算法，尽管要采用很多的评估函数，但也有如下优点：( 1 ) 算法用起 来容易。( 2 ) 群智能算法系统鲁棒性强；( 3 ) 群智能算法可以保证系统 的扩展性；( 4 ) 群智能使多处理器被利用充分；( 5 ) 定义连不连续群智 不作要求； 现有的群智能理论和应用方法研究可以表明的是该方法解决大多数 全局的优化没问题，是新方法，研究有学术意义同时也有现实价值。本 文主要研究微粒群优化算法的改进和应用，下一节将对微粒群算法作总 体概述。 第1 章绪论 1 5 微粒群算法 微粒群优化( p a r t i c l es w a r mo p t i m i z e r ，p s 0 ) 算法和遗传算法是 一样的优化工具。系统首先进行初始化，然后得到一组随机的解，最后 便通过不停的寻优过程找到最好的。但是微粒群算法只是粒子在区域内 跟着最好的粒子飞行，不需要遗传算法中的相互交叉与变换算子。 微粒群算法的研究大致可以分为五个部分心7 i ：算法、拓扑结构、参数、 与其他进化技术的融合以及应用。 起初人们知识不够丰富的时候就利用它解决简单的一些线性问题，后 来人们拓宽知识面后就想办法求优化问题，在这个里面就发现微粒群算 比传统方法更好的地方。第一，微粒群算法可以描述目标函数，传统优 化方法做不到，同时可以比较灵活地设定目的函数，使算法被广泛地应 用；第二，算法自己有比较好的特性，依据这个特性把全局和局部收敛 进行平衡。第三，算法可以与其他的进化算法融合。那么有些学者把一 些算子，比如说选择算子、变异算子等加入p s 0 算法，选择算子有这种 作用，能够把最好的粒子直接性地复制到下一代，这样就能确保最好的 粒子。交叉算子有这样的作用使一对一对的粒子之间相互交换各自的信 息资料，然后都具有向新的区域飞行的能力。另一种想法是把p s 0 中的 速度思想加到进化规划中，加快了进化规划算法的速度，从而来进行指 导变异操作。 因为微粒群算法具有不少优点，所以被成功应用到很多的领域。一般 来说，别的算法应用不好的地方，p s 0 算法都能成功应用。 1 6 本文研究的主要内容 本文讨论的是微粒群算法的基本原理、流程、参数设置及分析；总结 前人提出的一些主流的改进算法的优缺点，并在此基础上自己尝试大胆 提出对算法的一种改进方案，通过无约束和约束函数算例验证了改进算 法的可行性。同时将改进算法用于优化工业p i d 参数，也得到了平稳的 阶跃响应曲线；最后提出将基本p s 0 算法用于i p 网路的服务质量( q o s ) 武汉工程人学硕士学位论文 路由优化实例中，取得良好的效果。 本文的结构组织如下： 第一章：简单介绍了最优化问题及其分类、进化算法、群智能算法和 微粒群算法。 第二章：详细分析了微粒群算法的原理、参数设置、流程等相关内容， 并研究了微粒群算法参数的变化调整及向最好地方聚拢的性能，通过实 验方法变化地调整算法参数，使算法把全局收敛和收敛速度进行平衡。 第三章：总结了目前一些主流的微粒群算法的改进方法，在此基础上， 针对算法存在的缺点，自己大胆的提出了对算法的一种改进方案。 第四章：将改进算法用于函数优化中，通过没有约束和带有一定约束 函数算例验证了改进算法用起来有效。 第五章：简要地把p i d 控制器的原理介绍了一下，然后就提出的改进 方案用于求得工业p i d 的三个参数中，用一个工业上常用的二阶时滞传 递函数为模型，求得最好的值，体现了改进方案的优越性。 第六章：将基本的微粒群算法应用于i p 网络的服务质量( q o s ) 路由 优化的实例中，对网络的仿真实验表明，在满足q o s 要求的同时又把路 径费作为优化指标使其最优，此算法具有良好的效果。 第七章：对本文研究的总结与展望。 第2 章微粒群算法基本原理及参数分析 第2 章微粒群算法基本原理及参数分析 2 1 引言 微粒群算法是源于鸟群和鱼群群体运动行为的研究一种新的分支，与 基于达尔文“适者生存，优胜劣汰”进化思想的遗传算法不太一样，基 于个体间的相互帮助，微粒群优化算法来寻找最好的解。文献 2 8 引用 了生物社会学家e 0 w i l s o n 关于生物群体的一段话，“至少是在理论范 围内，一个生物群体中的一员可以从这个群体中所有其他成员以前在寻 找食物过程中积累的优势可能变成决定性的，这将超过群体中个体相互 之间抢夺食物进行竞争而带来的劣势 。这段话的意思是说生物群体中 个体一起分享资料促进进化，这也正是微粒群优化算法的基本思想。 2 2 基本微粒群算法 自然界中每一种生物都有它们自己的群体行为，通过慢慢发现它们的 群体行为，然后把它们的群体行为放在计算机上。一般来说，群体行为 可以由几条简单的规则进行建模。每一个个体的行为我们觉得比较简单， 但是整个群体的行为就复杂。r e y n o l d s 用b o i d 表示该个体，在计算机仿 真中找到如下三条简单的原则眩引： ( 1 ) 个体飞离最近的个体，以防撞到一起 ( 2 ) 个体共同朝一个目标飞 ( 3 ) 个体朝着群体的中心飞 2 2 1 算法基本原理 s h iy 和e b e r h a r t 对k e n n e d y 的基本p s 0 模型进行了系统的改进， 是目前大多研究者使用的模型。假定在一个d 维空间进行搜索，第i 个微 粒所在的地方我们可以表示为一个d 维向量，表示为置：( x 五：，) ， 微粒的飞行的快慢大小同样也是一个d 维向量，表示为形：( v f l ，v l2 一，v , d ) ， 只= ( 只。，易：，砌) 是第i 个微粒的最好的地方( 即适应值最好) ，记为p b e s t ， 您= ( p g 。，p ，p g d ) 是整个群体中所有微粒都经过的最好的地方，记为 武汉- t 程大学硕十学位论文 g b e s t ，这个可以作为一种共同的资料给其他的粒子作借鉴。注意到公式 中的上标表示迭代的次数，微粒根据下列公式来更新自己的速度和位置 1 1 ： i 箩1 = f o x v k d + c 1 x r a n d o x ( p , d 一一k d ) + c 2 x r a n d o x ( p g d 一) ( 2 一1 ) 嚣1 = + 略1 ( 2 2 ) 其中，d ：1 , 2 ，d ；i ；1 , 2 ，n ；k ；1 , 2 ，；k 表示迭代次数；n 为种群 大小；q 和乞是两个正常数，称为自身认识( c o g n i t i o n ) 参数和社会认 识( s o c i a l ) 参数；r a n d 0 是【o ，1 】之间的随机数；为惯量( i n e r t i a w e i g h t ) 。 想求这个问题，厂( x ) ；+ z + ，我们就把微粒直接编成这样一种形 式( 彳+ + ) ，而适应度函数就是厂( x ) 。然后我们就可以利用前面讨论的 过程慢慢地去找到最好的解，这个寻找最好的解的过程我们就叫它为迭 代的过程。如果到达了最多的飞行次数，或者找到最好的地方与实际上 最好的位置之间的间距的最小的时候，就停止。 公式( 2 - 1 ) 我们可以看出这个式子有三个部分，这三个部分的组合 就可以求出微粒i 的新的飞行的快慢大小：微粒i 刚刚之前的飞行快慢， 微粒i 现在所在的地方与它本来最好的地方之间的间隔，微粒i 现在所在 的地方与这一群粒子最好的地方之间的间距。公式( 2 - 2 ) 我们可以看出 有两部分就能够计算出微粒i 新的所处的地方的方位。我们可以通过式 ( 2 - 2 ) 的计算出微粒i 等会要到的地方。如果我们要是从社会学的角度 来看公式( 2 - 1 ) ，其中的第二部分( 微粒i 现在所在位置与这一群粒子最 好的位置之间的间距) 是自我认识的部分心9 l ，表示的是微粒的一切行为 都依靠自己的认识了解；第三部分( 微粒i 现在所在的位置与这一群粒子 最好的位置之间的间距) 是认识社会能力的部分，表示的是微粒的一切 行为依靠的是这一群粒子中另外的微粒在社会上获得的资料部分，这完 全体现出的微粒都来对知识进行加工和合作。这个过程我觉得很像人类 的决策，微粒想找到最好的地方第一要自身了解第二要借鉴同伴粒子获 得的一些资料，正好人类也是把自己的认识加上从外界得到的一些信息 来决定自己的行为。 第2 章微粒群算法基本原理及参数分析 2 2 2p s o 算法的基本流程 图2 1 基本微粒群算法流程图 2 3 微粒群算法参数分析 2 3 1 参数设置 p s o 算法的参数主要包括：惯性权重函数，权重因子g ，c 2 ，最大迭 代次数i t e r 一，群体规模，微粒的长度d ，微粒的坐标范围等最大速度 圪。 惯量：通常权重函数由下式来确定： ；t o m “一0 3 m _ a x _ - - 0 3 m i n i t e ，- 武汉工程大学硕十学位论文 饥h 分别表示c o 的最大值和最小值：i t e r 表示的是当前进行的多 少次，f f p _ 。，表示的是最终到结束时进行了多少次。通常这个函数对于 p s o 算法会不会发散起到了关键性的作用。粒子以前飞行的快慢会对粒子 现在飞行的快慢产生一定的影响，那我们就来调整的大小，来控制好这 种影响。如果大的话就导致速度y 小，那么这样对于粒子找到更好的地 方是比较有利的。所以我们在迭代刚刚开始的时候就让c o ：。一在慢 慢搜索的时候就线性地减小，最后就会达到：。；。的时候。这样粒子在 开始飞行的时候可以飞到很多地方，飞行的范围宽广，找到好的地方的 几率更高，然后粒子在搜索接近尾声的时候就慢慢地都集中较好的地方 进行更为精确的搜索，这时候飞行的比较快，通过研究可以表明，让随 着飞行次数的变多，让在1 4 到0 之间慢慢减小，这样飞行就可以取得 较好的效果0 | 。 加速度常数因子q ，c ：，即学习系数：调整的是微粒的自己认识自己 的部分与社会( 群体) 获得一些资料在它们的飞行中起到一定作用的部 分。如果而且g ；0 ，那么粒子没有自己认识自己的部分，只能到社会上 获得一些经验口0 i ，这样的话粒子飞到最好的地方的速度可能较快，但是 毕竟我们要解决一些较难的问题，这时就可能把错误的把某一局部找到 的最好的地方作为全面的最好的地方。如果而且厶。0 ，则微粒无法从它 们的伙伴中得到一些资料，只有自己认识自己的部分心9 | ，因为个体间没 有进行交流，一个有个的粒子的群体仅仅只是等于每个粒子单独地飞， 这样的话要找到最好的地方几率比较小。我们把c 1 和c ：通常取2 ，不过在 某些其他文献中也有其他的取值，但是一般q = 岛并且范围在0 和4 之间。 微粒的空间有几维d 这是我们想求的问题决定的，就是问题解的长 度。群体规模的种群大小：一般取2 0 - 4 0 ，对于大部分的问题，1 0 个 微粒的话我们觉得结果已经足够好，我们觉得这个问题比较难或者是特 定类别的问题时候就把微粒数取到1 0 0 或2 0 0 。微粒的坐标范围：由优化 问题决定，每一维可以设定不同的范围。结束要求：最大的飞行次数和 最好位置与实际最好位置间的差别要求小，这个终止条件由具体的问题 确定。最大速度圪a x 决定微粒在一个循环中最大的移动速度，通常设定 第2 章微粒群算法基本原理及参数分析 为微粒的范围宽度，例如上面的例子里，微粒“，吒，毛) 属于卜1 0 ，1 0 ，那么 大小就是2 0 。 2 3 2 参数分析实验 ( 1 ) 分析惯性权重对算法收敛速度和稳定性的影响。：1 2 是对粒 子飞行速度的约束，在搜索过程中，我们希望微粒在前期具有运行的能 力，后期具有一定的发现最好地方的能力。 选择y 。s i n ( x ) ，我们用它来进行实验，求一p f ，p 门的最小值。种群规模 朋。2 0 ，加速度常数q ：乞；1 4 ，最大进化代数乙。，。9 0 ，适应度函数 ( x ) ：s i n ( x ) ，图2 1 - 2 4 为不同时粒子的寻优轨迹图。 图2 1 = 1 2 时微粒寻优轨迹图 图2 1 的实验结果我们可以看出微粒在整体的区域内找到的最好的位 置是6 = 7 8 8 3 9 7 ，把这个最好的位置的数值代入到函数中求出函数的最小 值为；- 0 9 9 9 9 。，这个时候我们从图可以看出粒子在运行了1 8 次后 就慢慢聚拢，达到稳定，同时可以从图中看出，粒子在飞行了6 5 次以后 就开始往各处飞行，导致发散。同时在最好地方搜索的这个过程中，粒 子最终无法搜索到函数的最小值k 以。一1 。 武汉工程大学硕士学位论文 一 - _k ：o ：1k 。一 01 02 03 04 05 0印7 0即9 0 进化代数i 图2 2 = 0 9 时微粒寻优轨迹图 图2 2 的实验结果我们可以看出微粒在整体的区域内找到的最好的位 置是g = - i 5 7 0 8 ，把这个最好的位置的数值代入到函数中求出函数的最小 值为= 一1 0 ，这个时候我们从图可以看出粒子在找寻y 8 7 次是就慢慢 聚拢，达到稳定。 - 。 一i “ - 01 02 03 04 05 0印7 0即9 0 进化代数i 图2 3 = 0 4 时微粒寻优轨迹图 8 ， 2 4 6 8 2 2 m 0 1 1 之 删掣宅巾樊 3 2 1 0 1 2 3 州犁髻巾樊 第2 章微粒群算法基本原理及参数分析 删 趔 窖 h 樊 图2 4 ( = 0 9 0 4 ) 动态变化时时微粒寻优轨迹图 图2 3 的实验结果我们可以看出微粒在整体的区域内找到的最好的 位置是g 一1 5 7 0 8 ，把这个最好的地方的值代入到函数中求出函数的值为 y m m ；一1 0 ，这个时候我们从图可以看出粒子在找了3 3 次是就慢慢聚拢， 达到稳定，粒子在搜索刚刚开始的时候主要在 - 3 - i 之间飞行。 图2 4 的实验结果可以看出微粒在整体的区域内找到的最好的地方是 g = 一1 5 7 0 8 ，我们把这个最好地方值代入到函数中求出函数的的最小值是 ，一一1 0 ，这时我们可以看出粒子找寻了4 9 次是就慢慢聚拢，达到稳定。 实验结论：保持其他参数保持不变，如果我们把值取得过大，可能 无法找到最好的地方，那么反之我们把值取得值太小时，粒子可以很快 就找到最好的地方，但与此同时就过早就找到了最好地方，飞行的时间 不长，飞行的地方也不多。因此对就有一定要求，在刚刚开始飞行的时 候，把0 3 取得较大值，那么粒子可以在更大范围的地方搜索，在飞行慢慢 要结束的时候，就把6 0 取得较大值，就使粒子以最短的时间找到最好位置。 ( 2 ) 以上述测试函数为例，实验分析加速度常数q 和岛固定和动态变 化时的寻优过程。同时保持惯性权重因子；0 9 0 4 线性递减。图2 5 ， 图2 6 分别为加速度常数不变和变化调整时的微粒运动轨迹。 武汉工程人学硕士学位论文 翻 趔 鏊 融 勰 , - o o o t o 。- * 01 02 0 3 0 4 05 0即7 口 8 口 9 口 进化代数i 图2 5 加速度常数不变时微粒寻优过程图 - ： ， ， - 一 t - 一* - t - - t ； ：、 亍。 j d a y , ： o “i 。叫1 ： ： t ： j ， i o ： ： i i ， ， i 一4 r 4 f 4o 。t 。- - li i lii 图2 6 加速度常数动态调整时微粒寻优过程图 实验结果表明：自身认识的部分c 。取较大值时粒子找到最好位置的 时间过长，但是可以在更宽一点的领域里搜寻，对于比较简单的优化问 题，在搜寻范围是一定的时候，对社会获得资料的部分c ：进行变化的调 整有利于粒子在短时间聚拢，这样算法的效率增加，如果想求一些很多 0 5 ， 5 2 5 3 5 m 1 之 。 删掣譬巾鞯 第2 章微粒群算法基本原理及参数分析 目标值但不连续的问题，在后期对加速度常数进行变化地调整，使粒子 在运行初期在很宽的范围内飞行，在飞行的后期以很短的时间聚拢。 ( 3 ) 种群规模和最大进化代i t e r 一门选取实验测试函数： s p h e r e 函数： f o ( x ) 一罗x ? r o s e n b r o c k 函数： 舒 石( x ) = ( 1 0 0 ( x “l x f ) 2 + ( x f 一1 ) 2 ) r a s t r i g r i n 函数： 六 ) = 罗( x ? 一l o c o s ( 2 a x ，) + 1 0 ) g r i e w a n k 函数： 六m 志善# 一i ：i c o s ( 砉) “ s c h a f f e r 函数： 六( x ) 一。5 一面( s i n 而4 x 丽2 + y 研2 ) 2 _ 0 5 测试重点：保持惯性权重、加速度常数、变量x 允许变动范围不变， 在此基础上设定最优全局值，记录各函数在不同种群规模下( 1 5 、3 0 、 6 0 ) 到达目标值需要的迭代次数。最大迭代次数限定为i 0 0 0 。 武汉工程大学硕士学位论文 表2 1 微粒群算法迭代次数表 函数名种群数目 目标值迭代次数 $ p h e r e 15 - 1 0 0 ，1 0 0 8 o o l8 3 7 3 04 5 2 6 03 0 6 r o s en b r o c k15 - 3 0 ，3 0 。 1o o5 2 4 3 03 8 3 6 02 8 4 r a s tr i g r i n15 一5 1 2 ，5 1 2 。 lo o2 9 2 3 017 4 6 011 9 g r ie w a n k15 - 6 0 0 ，6 0 0 。 o 16 0 8 3 03 6 1 6 02 8 0 s c h a f f e r 15 - 1 0 0 ，1 0 0 ” l o - s13 8 3 0 12 0 6 09 1 由表2 - 1 发现，微粒种群数目与迭代次数成反比，而且是如果种群数 目较多的话算法寻优的成功率较高。但