（检测技术与自动化装置专业论文）微粒群算法及其在锅炉汽包水位控制系统中的应用.pdf

摘要 摘要 微粒群优化算法是t t l d r e b e r b a r t 和d r k e n n e d y 于1 9 9 5 年提出的一 种基于群智能的随机优化算法，是演化计算领域的一个新的分支。因 其原理简单、参数少、收敛速度较快，所需领域知识少等优点，自提 出以来已经受到国内外研究者的高度重视并被广泛应用于许多领域。 本论文在分析标准微粒群算法基本原理的基础上，就如何改进算 法性能以及拓展算法的应用领域进行了深入的研究。本文主要的研究 成果与贡献如下： 1 在简要回顾了群智能算法研究现状及优缺点的基础上详细分 析了微粒群算法的原理、流程和优缺点等相关内容，最后综述了算法 在各领域的应用。 2 总结了对算法进行改进的四种思路，并简要介绍了已有的几种 重要改进算法，在此基础上，针对算法存在的缺点，提出了一种改进 方案，并且通过数值仿真实验，说明了改进算法的有效性和可行性。 3 在简要介绍了p i d 控制器原理及其常规参数整定方法、锅炉汽 包水位的动态特性及三种常规水位p i d 控制系统的基础上将微粒群算 法及其改进算法用来整定水位三冲量控制系统中的主、吾i j p i d 控制器， 并将结果与常规整定方法进行比较，仿真实验表明，基于改进算法的 水位控制系统效果最好，基于微粒群算法的控制系统效果也优于常规 控制系统。 关键词：微粒群算法；水位控制系统；p i d 控制器；参数整定 a b s t r a c t a b s tr a c t 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 co p t i m i z a t i o n a l g o r i t h mb a s e do ns w a r mi n t e l l i g e n c ea n da ne v o l u t i o n a r yc o m p u t a t i o n t e c h n i q u ed e v e l o p e db yd r e b e r b a r ta n dd r k e n n e d yi n 19 9 5 p s oi s s i m p l ei nc o n c e p t ，f e wi np a r a m e t e r s ，a n de a s yi ni m p l e m e n t a t i o n ，s oi t h a sa t t r a c t e dal o to fa t t e n t i o n sf r o mr e s e a r c h e r sa r o u n dt h ew o r l da n d f o u n da p p l i c a t i o n si nm a n ya r e a ss i n c ei t si n t r o d u c t i o n b a s e do nt h es t u d yo fb a s i cp r i n c i p l eo fp s o ，t h et h e s i sm a k e sa t h o r o u g hr e s e a r c ho nh o w t oi m p r o v et h ep e r f o r m a n c eo fp s oa l g o r i t h m a n dt oe x p a n dt h e a p p l i c a t i o n a r e a s t h em a i na c h i e v e m e n t sa n d c o n t r i b u t i o n so ft h i st h e s i sa r el i s t e da sf o l l o w i n g ： 1 a n a l y z et h ep r i n c i p l e 、p r o c e s s 、a d v a n t a g e sa n dd i s a d v a n t a g e s a n do t h e rc o n t e n t sr e l a t e do fp s oo nt h eb a s i so fs y n t h e s i z i n gt h er e s e a r c h p r o g r e s sa n da d v a n t a g e sa n dd i s a d v a n t a g e so fs w a r mi n t e l l i g e n c e ，t h e n s u m m a r i z et h ea p p l i c a t i o n so fp s oi nv a r i o u sf i e l d s 2 f o c u so nt h el a c ko ft h ea l g o r i t h ma n db a s e do ns u m m a r i z i n g f o u rm o d i f i e di d e a so fp s oa n dt h ei n t r o d u c t i o n so fs e v e r a li m p o r t a n t i m p r o v e da l g o r i t h m s ，a ni m p r o v e m e n tp r o g r a mi sp r o p o s e d n u m e r i c a l s i m u l a t i o ns h o w st 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 ft h ei m p r o v e d a l g o r i t h m 3 b a s e do nt h ei n t r o d u c t i o n so ft h ep r i n c i p l eo fp i dc o n t r o l l e ra n d i t sc o n v e n t i o n a lp a r a m e t e r st u n i n gm e t h o d s ，t h ed y n a m i cc h a r a c t e r i s t i c s o fb o i l e rd r u mw a t e rl e v e la n dt h et h r e ek i n d so fc o n v e n t i o n a lw a t e rl e v e l c o n t r o ls y s t e m s ，t h ep s oa n di t si m p r o v e da l g o r i t h ma r eu s e dt or e g u l a t e t h ep a r a m e t e r so ft h em a i na n dt h ev i c ep i dc o n t r o l l e r s o ft h e t h r e e e l e m e n tw a t e rl e v e lc o n t r o ls y s t e m c o m p a r e dw i t ht h ec o n v e n t i o n a l t u n i n gm e t h o d ，s i m u l m i o nr e s u l t ss h o w st h a tt h ee f f e c to f t h ew a t e rl e v e l i i i 武汉工程大学硕士学位论文 c o n t r o ls y s t e mb a s e do nt h ei m p r o v e da l g o r i t h mi st h eb e s to ft h et h r e e a n dt h a to ft h ew a t e rl e v e lc o n t r o ls y s t e mb a s e do np s oi sb e t t e rt h a nt h e c o n v e n t i o n a lc o n t r o ls y s t e mt o o 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 ，w a t e rl e v e lc o n t r o ls y s t e m ，p i d c o n t r o l l e r ；p a r a m e t e rt u n i n g i v 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外， 本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对 本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：塌争 如口g 年易月宇日 学位论文版权使用授权书 本学位论文作者完全了解我院有关保留、使用学位论文的规定， 即：我院有权保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅。本人授权武汉工程大学研究生处可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存和汇编本学位论文。 本论文属于 保密o ， 在年解密后适用本授权书。 不保密。 ( 请在以上方框内打“4 ) 学位论文作者签名：季狰指导教师签名：叫中功 2 们名年6 月9 日? 一占年月j 1 7 日 第1 章绪论 1 1 引言 第1 章绪论 优化问题是长期以来人们一直在研究和探讨的问题。早在1 7 世纪，英 国n e w t o n 禾l ：l 德国l e i b n i t z 发明的微积分就包含了优化的内容。法国的数学家 c a u c h y 贝j 首次采用最速梯度下降法解决无约束优化问题，后来又针对约束 优化问题提出t i a g m n g e 乘数法口一。关于优化问题的研究，随着历史的发 展而不断的得到发展。但是，任何科学的进步都会受到历史条件的限制， 直n - - 十世纪四十年代，由于科学技术的迅速发展，特别是高速数字计算 机目益广泛的应用，使优化问题的研究不仅成为一种迫切需要，而且有了 求解的有力工具，形成了一门新的学科。但是随着人类生存空间的扩大， 以及认识世界和改造世界范围的拓宽，一些常规的方法如牛顿法、共轭梯 度法、模式搜索法、单纯形法、r o s e n b r o c k 法和p o w e l l 法已经无法处理人们 所遇到的复杂问题，因此高效的优化算法成为科学工作者的研究目标之一。 一些科学家把目光投向了大自然，他们发现自然界中的一些生物的行 为呈现群体的特征，例如蜜蜂采蜜、筑巢、蚂蚁觅食等，可以用简单的几 条规则将这种群体行为在计算机里进行建模动物学家 r e y n o l d s 认为动物 以群落形式生存觅食时一般遵守三个规则酗1 ： 1 ) 分隔规则：尽量避免与临近伙伴过于拥挤； 2 ) 对准规则：尽量与临近伙伴的平均方向一致，向目的运动； 3 ) 内聚规则：尽量朝临近伙伴的中心移动。 仔细分析，这三条规则实际上可以归纳为两类信息：一是个体信息，它 对应于分隔原则，即个体根据自身当前状态进行决策；二是群体信息，它 对应于对准规则和内聚规则，即个体根据群体( 伙伴) 信息进行决策。从整 体来看，整个过程中每个个体利用了个体和群体两种信息进行觅食搜索。 在此基础上，引出了科学家们对群集智能优化算法的探讨。群集智能 优化算法是通过r e y n o l d s 模型模拟了整个群体的运动，使得算法的迭代搜 武汉工程大学硕士学位论文 索过程成为一个不断地利用个体极值和群体极值来修正进行寻优搜索的过 程，实现了个体与群体的信息交互与相互协作。个体极值具有一定的随机 性，在一定的程度匕保持了搜索方向的多样性，避免了过早地收敛而陷于 局部最优；群体极值从整体e 把握了寻优的方向，从而保证算法的收敛性。 典型的群集智能优化算法有蚁群算法、微粒群算法以及人工鱼群算法，为 解决优化问题提供了新思维。 1 2 群智能( s t ：s w a r mir r t e lii g e n c e ) 算法的研究现状 1 2 1 蚁群算法( a c a - a n tc o l o n ya i g o ri t h m ) 蚁群算法是受到自然界中真实的蚁群集体觅食行为的研究成果的启发 而提出的基于种群的模拟进化算法，属于随机搜索算法，由意大利学者 m d o f i g o 等人【锕首先提出来，他们称之为蚁群算法，算法的基本原理主 要包括三个方面： ( 1 ) 蚂蚁的记忆。一只蚂蚁搜索过的路径在下次搜索时就不会被选择， 这在蚁群算法中通过建立t a b u ( 禁忌) 列表来模拟； ( 2 ) 蚂蚁利用信息素( p h e r o m o n e ) 进行相互通信。蚂蚁在所选择的路径 上会释放一种叫做信息素的物质，当同伴进行路径选择时，会根据路径上 的信息素进行选择，这样信息素就成为蚂蚁之间进行通讯的媒介； ( 3 ) 蚂蚁的集群活动。通过一只蚂蚁的运动很难到达食物源，但整个 蚁群进行搜索就完全不同。当某些路径e 通过的蚂蚁越来越多时，在路径 上留下的信息素数量也越来越多，导致信息素强度增大，蚂蚁选择该路径 的概率随之增加，从而进一步增加该路径的信息素强度，而某些路径上通 过的蚂蚁较少时，路径上的信息素就会随时间的推移而蒸发。因此，模拟 这种现象从而利用群体智能建立的路径选择机制，使蚁群算法的搜索向最 优解推进。 基本的蚁群算法模型由以下三个公式组成： 2 第1 章绪论 f 驴o + 1 ) = p * r 妒( 刀) + a r ；0 - 2 ) k = l 叫2 轰 ( 1 3 ) 式中，聊为蚂蚁总数；嚣为迭代次数；i 为蚂蚁所在位置；j 为蚂蚁可以到 达的位置；彳为蚂蚁可以到达位置的集合。巩为启发性信息，通常为由位 置i 到的路径的能见度( v i s i b i l i t y ) ，即l 如；f 为目标函数；为由f 到j 的 路径的信息素强度( 础e n s i 妫；a t ：为蚂蚁露在从位置i 到的路径上留下的单 位长度轨迹信息素数量；口为路径权值；为启发性信息的权值；p 为路 径上信息素数量的蒸发系数；q 为信息素质量系数；露为蚂蚁后从位置i 移 动到位置，的转移概率。 蚁群算法自提出以来就逐渐成为学者关注的研究方向之一，并已成功 应用到许多领域。该算法最初被用于解决旅行商问题。自从在著名的旅行 商问题和工件排序问题上取得成效以来，已经陆续渗透到其它领域中，如 图着色问题、二次分配问题、大规模集成电路设计、通讯网络中的路由问 题以及负载平衡问题、车辆调度问题、数据聚类问题、武器攻击目标分配 和优化问题、区域性无线电频率自动分配问题等。国内的研究是从1 9 9 8 年 末开始的，主要是在上海、北京、东北少数几个学校和研究所开展了研究 工作，主要围绕旅行商及其相关问题的试验仿真，少数设计网络通讯的路 由选择、负载平衡、电力系统的故障检测以及蚁群算法在连续系统中的应 用，如函数逼近等方面应用的尝试。 1 2 2 微粒群算法( p s 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 ) 是继蚁群算法后又一种新型的模拟自然生物的进 化算法，它的迭代过程和遗传算法类似，但没有引入变异和交叉算子这两 个定义，同时它也不同于蚁群算法，需要通过信息素这种物质来判断最佳 3 武汉工程大学硕士学位论文 路径。微粒群算法是对鸟鱼类栖息、觅食的过程成功的用计算机模拟，从 它们生活规律中衍生出来的一种仿身算法，影响f 电f 门规律的因素只包括： 自身经验和群体协作。 微粒群算法起初人们只是用来解决一些简单的线性问题，后来人们把 它尝试着用于优化问题的求解中，发现微粒群算法相对于传统的优化方法 有很大的优势。首先在优化目标函数形式上没有太严格的要求，甚至可以 把很多传统优化方法无法表达的问题描述为目标函数，同时对目标函数的 设置比较灵活，使算法应用更为广泛；其次，由于算法自身的特性，很好 的平衡了全局和局部的收敛问题，避免的局部收敛的问题；同时，它也借 鉴了遗传算法中“适者生存 ，但不同的是它始终朝好的方向发展，不会 把比较好的解破坏掉，保证了算法的快速性。 p s o 算法最早应用于训练人工神经网络，k e n n e d y 和e b e r h a a 成功地 将算法应用于分类x o r 问题的神经网络训练。随后，微粒群算法被广泛 地应用于函数优化、约束优化、模式分类、参数优化、组合优化、模糊系 统控制、机器人路径规划、信号处理、模式识别、旅行商问题、车间调度 等工程领域。此外，算法在多目标优化、自动目标检测、生物信号识别、 决策调度、系统辨识，以及游戏训练等方面也取得了一定的成果。总之， p s o 算法的应用十分广泛，它有着较好的发展前景，值得做进一步的研究。 1 2 3 人工鱼群算法( a f a ：a r t i f i e i a lf i s h - s w a r ma l g o ri t h m ) 人工鱼群算法是李小磊等在对动物群体智能行为研究的基础上提出的 一种新型仿生优化算法同。与传统人工智能系统的白上而下的设计思路相 比，该算法采用了自下而上的设计方法。所以，首先应着重构造鱼群自治 体的模型，具体模型描述如8 】： ( 1 ) 觅食行为：平时我们会看到鱼在水中游来游去，这般可视为一种 随机移动。当鱼群发现食物时，会向着食物逐渐增多的方向快速游去。 ( 2 ) 聚群行为：鱼在游动过程中为了保证群体的生存和躲避危害而形成 了一种生活习性会自然地聚集成群。 ( 3 ) 追尾行为：在鱼群的游动过程中，当其中一条或几条发现食物时， 4 第1 章绪论 其临近的伙伴会尾随其后快速到达食物点。 ( 4 ) 约束行为：在寻优过程中，由于群聚行为、随机行为等操作的作用， 容易使人工鱼的状态变得不可行，此时就需要加入相应的约束对其进行归 整化，使它们由无效状态或不可行状态转变为可行的。 ( 5 ) 公告板：公告板用来记录最优人工鱼的状态。各人工鱼在寻优过程 中，每次行动完毕就比较自身状态与公告板的状态，若自身状态优于公告 板状态，就将公告板状态改写为自身状态，这样公告板记录下的就是历史 最优状态。 ( 6 ) 移动策略：根据所要解决问题的性质，对人工鱼当前所处的环境进 行评价，从而选择一种合适的行为策略。 综上所述，有了底层的人工鱼模型，算法的展开就在一群人工鱼的自 主活动中开始了，每条人工鱼按照自己的规则游动，所求问题的满意解就 显示在公告板上。最终，人工鱼集结在几个局部极值的周围，且值较优的 极值区域周围一般能集结较多人工鱼。 不过，人工鱼群算法由于诞生时间不长且是在仿真基础上，其性能及 理论基础还有待继续研究。目前已有学者将其应用于组合优化、神经网络 训练、p i d 控制器参数整定、约束优化、电力系统负荷预测、参数估计、 数字滤波器设计、多目标优化等问题，并且取得了良好的效果。 1 3 群智能算法的优缺点 群智能算法是一种概率搜索算法，与大多数基于梯度应用优化算法及 传统的演化算法相比，其特点和优点如下【9 】： ( 1 ) 它是类不确定的优化算法，其不确定性体现了自然界生物的生 理机制，并且在求解某些问题时优于确定性算法； ( 2 ) 它是类概率型的全局最优搜索算法，一方面它能在可行解空间 进行全方位的搜索；另一方面，在优质解附近，在一定程度上它也能进行 更精细的搜索； ( 3 ) 它采用完全分布式控制来实现个体与个体和个体与环境的交互作 5 武汉工程大学硕士学位论文 用，具有良好的自组织| 生； ( 4 ) 算法中个体之间的交流方式是非直接的，各个体通过对环境的感 知( 感觉能力) 来进行合作，确保了系统具有更好的可扩展| 生和安全l 生； ( 5 ) 算法没有集中控制的约束，系统具有更好的鲁棒性，不会因为个 别个体的故障而影响整个问题的求解； ( 6 ) 由于系统中单个个体的能力十分简单，只需要最小智能，这样每 个个体的执行时间较短，实现起来比较方便，具有简单性。 由于群智能的理论依据是源于对生物群落社会性的模拟，因此其相关 数学分析还比较薄弱，这就导致了现有研究还存在些缺点【9 】： ( 1 ) 群智能算法的数学理论基础相对薄弱，缺乏具备普遍意义的理论 性分析，算法中涉及的各种参数设置一直没有确切的理论依据，通常都是 按照经验型方法确定，对具体问题和应用环境的依赖| 生比较大； ( 2 ) 同其它的自适应问题处理方法一样，群智能也不具备绝对的可信 性，当处理突发事件时，系统的反应可能是不可测的，这在一定程度上增 加了其应用风险； ( 3 ) 群智能与其它各种智能方法和先进技术的融合还不够。 已有的群智理论和应用研究证明群智能方法是一种能够有效解决大多 数优化问题的新方法，更重要的是，群智能潜在的并行性和分式特点为处 理大量的以数据库形式存在的数据提供了技术证明。无论是从理论研究还 是应用研究的角度分析，群智能理论及应用研究都是具有重要学术意义和 现实价值的。本文主要针对微粒群优化算法这一群智能算法展开研究。 1 4 本文的主要工作 本文的主要工作是在对微粒群算法的原理、流程、参数设置、优缺点 等相关内容的分析与介绍的基础上，提出对算法的一种改进方案，并且将 标准微粒群算法和改进算法应用在锅炉汽包水位控制系统中，以期取得优 于常规水位控制系统的效果，拓展微粒群算法的应用领域。 本文的组织如下： 6 第1 章绪论 第一章：简要回顾了三种群智能算法：蚁群算法、微粒群算法和人工 鱼群算法的研究现状，并且总结了群智能算法的优缺点。 第二章：详细分析了微粒群算法的原理、参数设置、流程等相关内容， 并将微粒群算法与其它进化算法进行比较，体现其优缺点，最后综述了算 法在各领域的应用。 第三章：总结了对算法进行改进的四种思路，并简要介绍了已有的几 种重要改进算法，在此基础上，针对算法存在的缺点，提出了对算法的一 种改进方案，并目通过数值仿真实验，说明了改进算法的有效性和可行性。 第四章：简要介绍了p i d 控制器原理及其常规参数整定方法，分析了锅 炉汽包水位的动态特性，并且简要介绍了三种常规水位p i d 控制系统。 第五章：将微粒群算法及其改进算法用来整定水位三冲量控制系统中 的主、吾1 p i d 控制器，并将结果与常规整定方法进行比较，仿真实验表明， 基于改进算法的水位控制系统效果最好，基于微粒群算法的控制系统效果 也优于常规控制系统。 第六章：总结与展望。 7 第2 章微粒群算法概述 2 1 引言 第2 章微粒群算法概述 人工生命技术的发展，使人们能很好的用计算机根据自然界中群体生 物的生活习性构造模型，比如鱼类，鸟类的群体生活。虽然每个个体的行 为规则非常的简单，但把他们作为一个群体来研究其行为相当复杂。 r e y n o l d s 采用计算机动画对这种复杂的行为进行了模拟，最后他提出了群 体行为中个体应遵循的三条基本原则嘲： ( 1 阶体飞行是不会相撞，他们总会飞离最近的个体； ( 2 冷体均朝一个目标飞行； ( 3 阶体习惯往群中心靠拢。 后来r e y n o l d s 在研究人类决策过程中发现，人们在决策事隋发展时会 听取同伴的意见，同时再根据自己的自身经验作出最后的决策。也就是说 人们采用了两条重要的信息，一是同伴的经验，二是自己个人的经验。 r e y n o l d s 因此得出了微粒群算法的基本概念。 微粒群算法是美国社会心理学家k e n n e d v 和工程师既i e m 砸于1 9 9 5 共同 提出的u 引，其思想主要是利用生物学蔚r a n kh e p p n e r 的模型，对鸟类群体 生活特性进行研究而启发得到。f r a n kh e p p n e r 的模型中，开始时每只鸟都 没有特定目标进行飞行，直到有一只鸟发现了栖息地，当发现期望栖息地 比鸟群目前所在位置具有较大的适应值时，每一只鸟都将离开群体而飞向 期望栖息地，随后就自然地形成了鸟群。同时，一只鸟离开群体飞向栖息 地，鸟群中的其它鸟也会跟随飞行，发现了栖息地后会降落，这样驱使更 多的鸟向栖息地靠拢，直到整个鸟群迁徙到栖息地。 k 印n 。d y 和e b e n l a n 对鸟类的这种飞行方式进行研究，即一只鸟能带领 整个鸟群飞向比较好的栖息地，增加鸟群寻找到栖息地的可能性。随后结 合社会认知观点：人类习惯与周围同类型人比较，并向成功者学习，模仿 他们的行为。提出了如下问题：一是鸟类个体怎样保持个性即在飞行过程 9 武汉工程大学硕士学位论文 中不与其它鸟相撞，而又可以向先找到栖息地的鸟学习；二是如何保证所 有鸟都是降落在找到的最优栖息地，而不是另外的栖息地，使得鸟群不至 于太分散。 k 朗n 。d 娇陀b e 血艄的解决了上述问题，提出了微粒群算法。 2 2 1 算法的原理 自然界中各种生物体均具有一定的群体行为。设想这样一个场景：一 群鸟在随机搜寻食物，在这个区域只有一块食物，所有的鸟都不知道食物 在哪里，但是它们知道当前的位置离食物还有多远。那么找到食物的最优 策略是什么呢? 最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 p s o 算法就是从这种生物种群行为特性中得到启发并用于求解优化问题。 p s o 算法是通过个体问的协作与竞争来实现复杂空间中最优解的搜 索。在p s o 算法中，先产生初始种群，即在可行解空间中随机初始化一群 粒子，每个粒子都是优化问题的一个可行解，并由目标函数为之确定一个 适应值( f i t n e s sv a l u e ) ，每个粒子在解空间中运动，并由一个速度决定其方向 和距离。通常粒子将追随当前的最优粒子而移动，经迭代搜索最后得到最 优解。在每一代中，粒子将跟踪两个极值，一个是粒子本身迄今找到的最 优解p b e s t ，另一个为全种群迄今找到的最优解g b e s t 。 用数学语言可将上述过程描述为：在一个刀维的搜索空间中，由m 个 粒子组成的种群x = “，x i ，。 ，其中第i 个粒子位置为 x i = ( x 订，一：，) r ，其速度为u = ( v n ，v 加，) r 。它的个体极值为 p ，= ( p n ，p ，p 抽) 7 ，种群的全局极f f t y 9 p g = ( p g l ，p ，p 朋) r 。按追随当前 最优粒子的原理，粒子蕾将按( 2 - 1 ) 、( 2 - 2 ) 式改变速度和位置n 阳。 v i d ( t + 1 ) = wv i a ( t ) + m r a n d 0ip i d ( t ) 一x i a ( t ) i + c z r a n d ( ) lp i a ( t ) 一x i a ( t ) 1 ) 6 d ( t + 1 ) = ( f ) + e d ( t + 1 ) 1 0 ( 2 - 1 ) ( 2 2 ) 第2 章微粒群算法概述 其中：w 为惯性权重( i n e r t i aw e i g h t ) ，f 表示微粒第t 代，e l 和c ：为加速 常数，通常在 o2 取值r a n d 0 和r a n d o 为两个随机函数，取值范围为 0 1 。此外，f i d 被限制在一定范围内，即f i d - - v m a xv m a x 。从社会学 角度来分析式( 2 1 ) ，式( 2 一1 ) 写成v = 1 ，+ p + g 。 ，= w v i d 记j 乙微粒先 前速度，w 用于调节速度变化的快慢。 p = c l r a n d olp 玉一( f ) i ( 微粒当前位置与自身最优位置之间的距离) 为 “认知( c o g n i t i o n ) 部分，即微粒对自身的思考，通过自己的经验来判 断当前的飞行。g = c 2 r a n d ol 鼢( f ) 一x i z ( t ) l ( 微粒当前位置与群体最优位置 之间的距离) 为“社会( s o c i a l ) ”部分，即微粒间的信息共享与相互合作， 根据其它微粒的经验来判断当前的飞行。微粒群算法成功的模拟了人类社 会对信息认知的过程，在这个过程中，个体要有自己的想法，但同时要结 合同伴们对信息的认识，当个体发现同伴有了比较好的认识时，就应该作 出适度调整，即学习别人的成功经验。式( 2 2 ) 中，微粒位置的改变是当 前位置向量与更新后速度向量的叠加。v i d ( t + 1 ) 可以看作为位移步长。另 外，粒子在不断根据速度调整自己的位置时，还要受到最大速度的限 制。当v i 超过时将被限定为v i 嫩。 2 2 2 算法的参数设置 微粒群算法作为一种优化算法，我们必须考虑算法的收敛速度、全局 与局部收敛、算法复杂度等问题，这些问题与算法的参数选择紧密相关。 下面是r , s o 算法中一些参数的作用及其设置经验。 1 )惯性权重 惯性权重w 是用来控制粒子以前速度对当前速度的影响，它将影响粒 子的全局和局部搜索能力。较大的w 值有利于全局搜索，较d xw 有利于局 部搜索。选择个合适的w 可以平衡全局和局搜索能力，这样可以以最少 的叠代次数找到最优解。对p s o 全局和局部之搜索能力的平衡主要被惯性 权重控制，在 1 1 中说明这种情况，实验发现p s o 的惯性权重在 o 9 ，1 2 之间平均来说有比较好的性能。还发现每次惯性权重从1 4 减少到0 要比用 固定的好。这是因为开始较大的惯性权重可以找型jl t ：较好的范围，后来小 武汉工程大学硕士学位论文 的权重有较好的局部搜索能力。 另外在 1 2 中分析了惯性权重和最大速度对p s o 性能的影响，发现最 大速度v 懈较小时权重近似为l 是个好的选择。当最大速度比较大时权重为 o 8 是个比较好的选择。 2 ) 收缩因子 为了使算法在迭代初期能探索到较大的解空间，后期能在较好的区域 进行搜索以加快收敛速度，提出了w 的调整策略u 副。但这种方法只是线l 生的 调整w 值。因而，s i l i ，y 提出了一种模糊白适应动态调整w 的方法。1 4 i 。此算 法的缺点是求解许多复杂的非线性优化问题比较困难。鉴于此，研究者提 出了一种带收缩因子的微粒群算法u 副，其数学表达式为 砌( 川) - z w 妇( f ) + e n r a n d o p 甜( f ) 必】+ c 2 删o 【助( f ) 一肠( f ) b ( 2 3 ) 式中：z = 广每i 为收缩因子； 巾= c 。+ c 2 ， 巾 4 。 1 2 一伊一缈2 4 伊i 实验证明收缩因子的引入改善了算法的收敛速度u 副，同时指出两种算 法之间的联系，带收缩因子的p s o 可以看作为带惯性权重j s o 的一种特例。 3 )加速常数 c 。、c 2 用来控制粒子自身的记忆和同伴的记忆之间相对影响。合适的选 择可以提高算法速度、避免局部极小。在 17 ，1 8 中作者认为c ，= c 产2 是好的 选择，但实验也说明c 。= c 2 = 0 5 也能得到好的结果。在 1 9 中介绍c 。比c ：选的 应大一些，但c 。- i - c ：4 较好。 4 )最大速度 一般来说，v 一的选择不应超过粒子宽度范围，如果嗽大，粒子可 能飞过最优解的位置；如果太小，可能降低粒子的全局搜索能力。 5 )群体规模和粒子维度 群体规模【i l 一般来说不用取得太大，几十个粒子就足够用了，当然一些 特殊问题可取得更多。如对多目标优化等比较难的问题，或者某些特定的 问题，粒子数可以取到1 0 0 2 0 0 个。粒子的维度，这是由优化问题所决定 的，也就是解空间的维度。 6 )适应度函数 1 2 第2 章微粒群算法概述 适应度函数的选取方法有很多，也没有统一明确的选取标准，对于简 单的线性优化问题，可以直接以求解的目标函数作为适应度函数，这种方 法简单直观，但对于某些在函数值上分布相差很大的函数，此时得到的适 应度可能不利于体现种群的平均性能，影响算法性能；在求解复杂的控制 问题时，我们可以选择超调量、上升时间、允许最小误差等作为适应度函 数。 7 )算法终止条件 与遗传算法相似，p s o 算法的终止条件一般可以设置为达到最大迭代次 数或者满足一定的误差准则。 2 2 3 算法的流程 微粒群算法流程如下图1 所示： 武汉工程大学硕士学位论文 图2 - 1 微粒群算法流程图 1 4 第2 章微粒群算法概述 ( 1 ) i n i t i a l ：将微粒群做初始化，以随机的方式求出每一粒子的初 始位置与速度。 ( 2 ) e v a l u a t i o n ：依据适应度函数计算出其适应度值以作为判断每 一粒子的好坏。 ( 3 ) f i n dt h ep b e s t ：找出每一粒子到目前为止的搜寻过程中最佳 解，这个最佳解我们将称为个体最优( p b e s t ) 。 ( 4 ) f i n dt h eg b e s t ：找出所有粒子到目前为止所搜寻到的整体最佳 解，此最佳解我们称为全局最优( g b e s t ) 。 ( 5 ) u p d a t et h ev e l o c i t y ：依据式( 2 1 ) 与式( 2 - 2 ) 更新每一粒子的速度 与位置。 ( 6 ) 回到步骤2 继续执行，直到获得个令人满意的结果或符合终止条 件为止。 2 2 4 全局模型与局部模型 k e n n e d y 等人在观察鸟群觅食的过程中注意到，通常飞鸟并不一定看 到鸟群中其他所有飞鸟的位置和动向，往往只是看到相邻的飞鸟的位置和 动向。因此他在研究微粒群算法时，同时开发了两种模型：全局模型和局 部模型 2 0 1 。在全局模型中，每个粒子的轨迹受微粒群中所有粒子的所有的 经验和意识的影响；而在局部模型中，粒子的轨迹只受自身的认知和邻近 的粒子状态的影响，而不是被所有微粒的状态影响。前者速度快不过有时 会陷入局部最优，后者收敛速度慢一点不过很难陷入局部最优。 局部模型本身存在着两种不同的方式。一种方式是由两个微粒空间位 置决定“邻居”，它们的远近用微粒间距离来度量；另一种方式是编号方法， 微粒群中的微粒在搜索之前就被编以不同的号码，例如l 号与最后个微 粒和2 号相邻，2 号微粒则与l 号、3 号相邻，形成环状拓扑社会结构。根 据社会学家的研究，这两种邻域的概念都是有社会背景的。对于第一种方 式，在每次迭代之后都需要计算每个微粒与其他微粒间的距离来确定邻居 中包括哪些微粒，这导致算法的复杂度增强，算法运行效率降低。而第二 种方式由于事先对微粒进行了编号，因而在迭代中微粒的邻域不会改变。 1 5 武汉工程大学硕士学位论文 这导致在搜索过程中，当前微粒与指定的“邻居 微粒迅速聚集，而整个 微粒群就被分成几个小块，表面上看似乎是增大了搜索的范围，实际上则 大大降彳氐了收燃。 p s o 算法可以快速收敛到最优解附近，但是缺乏局部区域精细搜索能 力，使得算法在搜索后期随迭代次数的增加解的改进甚微。在实际应用中， 可以先用全局p s o 找到大致的结果，再用局部p s o 进行搜索。 2 3 已有的几种重要改进算法 2 3 1 自适应微粒群算法 文耐3 8 】研究了惯性因子对优化性能的影响，发现较大的值有利于跳 出局部极小点，而较小的值有利于算法收敛。因此提出了自适应调整 的策略，即随着迭代的进行，线| 生地减小的值。这种方法的进一步发展 是用模糊规则动态地修改的倒t 3 9 1 ，即构造一个2 输入、1 输出的模糊推 理机来动态地修改陨性因子c o 。模糊推理机的两个输入分别是当前c a ) 值、 规范化的当前最好性能演化( t h en o r m a l i z e dc u r r e n tb e s tp e r f o r m a n c e e v a l u a t i o n ，n c b p e ) ；而输出是( i ) 的增量。c b p e 是p s o 算法迄今为止发 现的最好候选解的性能测度。c b p e 可以有不同的定义方法，但是一般 c b p e 可以定义为最好候选解的适应值。n c b p e 用下式计算： n c b p e 芦( c b p e - - c b p e m 缸) ( c b p e m 醒- - c b p e n i n ) ( 3 3 ) 其中c b p e 一和c b p e n _ 血l 是c b p e 可能的上下限。 模糊推理机的输入、输出的论域定义为3 个模糊集合：l o w n ， m e d i u m ，h i g h ，相应的模糊隶属度函数分别是l e t t t r i a n g l e ，t r i a n g l e ， r i g h t t r i a n g l e 。模糊推理机定义了9 条规则进行模糊推理，决定当前的增 三l 里。 这类自适应p s o 算法对许多问题都能取得满意的结果。通过自适应 调整全局系数，兼顾搜索效率和搜索精度，是一类有效的算法。但是对许 多复杂的非线性优化问题，试图通过自适应调整一个全局系数提高搜索精 度的余地是有限的。 1 6 第2 章微粒群算法概述 2 3 2 离散二进制模型 基本的p s o 算法是在连续域中搜索个数值函数的最小值的有力工 具。k e n n e d y 和删4 0 x f f 此做了扩展，提出了种离散二进制p s o 算 法。而c l 讹- 4 l 】推广了这一工作，研究了离散版的p s o 算法，并将其应用 于旅行商问题的求解，取得了较好的结果。 离散二进制p s o 算法和基本p s o 算法的主要区别在于运动方程的差 别，离散二进制p s o 算法的运动方程为： = 、) l 眦r h c l 啪d ( 脚一) + c e r a n d ( p g d 一) 【i d ) ( 3 - 4 ) i f p i a s i g ( v i d ) t h e n ) 嘞尸1 ；e l s ex 蝴- - 0 ( 3 - 5 ) 其中：s 辔( ) = 再百击了丽是s i g m o i d 函数，【0 ，1 】是随机矢量心 的第n 维分量，粒子的位置只有( o ，1 ) 两种状态。 离散p s o 算法扩展了基本p s o 算法的应用领域，尤其是让人看到了 在类组合优化问题中的应用前景。 2 3 3 协同微粒群算法 协同p s o 算法乎】的基本思想是用k 个相互独立的微粒群分别在d 维 的目标搜索空间中的不同维度方向上进行搜索。 具体做法是：选定划分因子( s p l i tf a c t o r ) k 和微粒群的粒子数m ，将输入 的d 维向量( 粒子的位置及速度向量) 划分到k 个微粒群。前d m o d k 个微 粒群，其粒子的位置及速度向量都是d k 维的；而后k 一( d m o d k ) 个微 粒群，其粒子的位置及速度向量也是d k 维的。在每一步迭代中，这k 个 的微粒群相互独立地进行状态更新，微粒群之间不共享信息。计算适应值 时，将每个微粒群中最优粒子的位置向量拼接起来，组成d 维向量并代入 适应函数计算适应值。例如，考虑有2 4 个自变量的优化问题，即d = 2 4 。 如果选取m = 1 0 ，k = 5 ，那么每个粒子的位置及速度向量的维数就是d k = - 5 。 这种协同p s o 算法有明显的“启动延迟”( s t a r t - u pd e l a y ) 现象，在迭代 初期，适应值下降缓慢，换言之，收敛速度慢。文献【4 3 】的实验结果显示微 粒群数目越大，收敛越慢。不过这种协同p s o 算法因为实际上采用的是局 1 7 武汉工程大学硕士学位论文 部学习策略，因此比基本的p s o 算法更易跳出局部极小点，达到较高的收 敛精度。 生物免疫系统是由器官、细胞和分子组成的一个复杂系统，它是除神 经系统外，机体能特异的识别“非己和“自己 的刺激，对之做出精确 的应答、并保留记忆反应的功能系统。受到这些特性的启发，高鹰和谢胜 利m 给出了免疫微粒群优化模型。 免疫微粒群优化模型是将免疫系统的免疫信息处理机制( 多样| 生、免疫 自我调节、免疫记忆等) 引入到微粒群优化算法中而形成的。这种优化模型 结合了微粒群优化算法具有的全局搜索能力、实现简单和免疫系统的免疫 信息处理机制，从而避免了微粒群优化算法易于陷入局部极值点的缺点， 提高了进化后期算法的收敛速度和精度。 2 4 与其它进化算法的 匕较 1 相同点 微粒群算法与其他进化算法有许多相似之处： ( 1 ) 都是仿生算法：p s o 和其它进化算法一样，都是总结自然界中生物 生活规律而提出的优化算法； ( 2 ) 算法流程：p s o 和遗传算法等进化算法都引入了“群体 这个概念， 用来表示一组解空间中的个体集合； ( 3 ) 选择机制：在优化的过程，都是根据评价度函数来选择粒子以后 的发展，而且算法都是朝适应值好的方向发展； ( 4 ) 全局寻优：作为进化优化方法，目的都是在全局寻求最优解； ( 5 ) 隐含并行性：搜索过程都是从问题解的一个集合开始的，而不是 从单个个体开始，从而减小了陷入局部极小的可能性； ( 6 ) 在算法操作过程中，都要考虑到算法陷入局部最优等早熟问题。 2 不同点 第2 章微粒群算法概述 同时，微粒群算法也呈现出一些其他进化算法所不具有的特性： ( 1 ) 微粒群引入“社会意识”。在微粒群算法中，微粒的最优位置共 享，其它微粒根据这一信息调整自己的飞行方向。在其他算法中，如遗传 算法，染色体之间相互共享信息，使得整个种群都向最优区域移动。 ( 2 ) 记忆功能。微粒群算法会记忆全局最好适应值位置和微粒个体曾 到过的最好位置，而对于进化遗传算法，会通过交叉破坏掉好的种群。 ( 3 ) 微粒群算法同时将粒子的位置和速度模型化，给出固定的进化方 程。 ( 4 ) p s 0 算法相对于遗传算法，没有交叉和变异操作，粒子只是通过内 部速度进行更新，因此原理更简单、参数更少、实现更容易。 2 5 微粒群算法的应用 p s o