（计算机应用技术专业论文）粒子群优化算法及其在神经网络中的应用.pdf

大连理工大学硕士学位论文 摘要 自上世纪8 0 年代以来，智能优化算法( 如人工神经网络、混沌算法、遗传算法等) 通过模拟或揭示某些自然现象和过程而发展起来，为优化理论提供了新的思路和手段， 并在科学、经济以及工程领域得到了广泛应用。粒子群优化算法是一种基于种群搜索策 略的自适应随机算法。作为智能优化算法中的一种，它可用于求解大部分的优化问题， 并在工程实践中表现出巨大潜力，现已广泛应用于神经网络、模糊系统控制、模式识别 等多个领域。 本文对粒子群算法的收敛性进行分析，阐述了过早收敛问题的产生原因，并对此给 出了生存密度粒子群( s d p s o ) 与速度变异粒子群( v m p s o ) 两种改进型算法。s d p s o 以 自然界和物理界的基本原理为导向，通过提高种群多样性的方法使算法获得持续搜索能 力。实验结果表明，该算法能有效克服过早收敛问题，并有助于增大种群跳出局部极值 的几率。v m p s o 对粒子每一维上的速度进行操作，从而将在高维度空间上的搜索转化 为在每一维上分别进行搜索。实验结果显示，对于3 0 维g r i e w a n k 和r a g 匝g m 多模态函 数，v m p s o 均已找到全局最优值0 ，而且对于所有被测函数，其整体性能指标均超出 基本p s o 多个数量级。此外，v m p s o 对高维度函数的优化效果更加明显。 本文将s d p s o 与v i v i p s o 算法作为学习算法用于神经网络训练，使用三组标准分 类数据集进行测试，并与其它几种经典学习算法进行比较，结果表明：基于s d p $ o 与 v m p s o 算法的感知机网络在分类准确率上明显优于梯度算法、b p 算法以及遗传算 法。本文给出了一套用神经网络进行人脑认知状态分类的解决方案，并使用基于改进粒 子群算法的感知机网络建立并训练了一个认知状态分类器，实现对汉语拼音与汉字字形 这两种汉语认知状态的分类。该方案不只局限于认知状态分类，通过适当扩展可用于求 解其它分类问题。 关键词：粒子群优化算法；生存密度；速度变异；神经网络；认知状态分类 塾王壁垡堂鎏垦基垄! ! 丝堕鱼主箜窒旦 p a r t i c l es w a r m o p t i m i z a t i o na n d i t sa p p l i c a t i o ni nn e u r a ln e t w o r k f r o mt h e1 9 8 0 s ，i n t e l l i g e n to p t i m i z a t i o n a l g o r i t h ms u c h a sn e u r a ln e t w o r k , g a , c h a o sh a s b e e nd e v e l o p e dt h r o u g ht h es i m u l a t i o no fn a t u r a n ds o c i a lp r o c e s sa n di t p r e s e n t san e w a p p r o a c hf o ro p t i m i z a t i o nm e t h o d s p a r t i c l es w v a r n lo p t i m i z a t i o ni sap o p u l a t i o n - b a s e d , s e l f - a d a p t i v es e a r c ho p t i m i z a t i o nt e c h n i q u e a sak i n do fi n t e l l i g e n ta l g o r i t h m , i tc a nb eu s e dt 0 s o l v ev a r i o u so p t k n i z a t i o np r o b l e m sa n ds h o w sg r e a tp o t e n t i a li np r a c t i c e 。n o w , i th a sb e e n w i d e l ya p p l i e d i nm a n yo t h e r 棚= e a s s u c h 如a r t i f i c i a ln e u r a ln e t w o r ka n d f u z z ys y s t e m e n n t r 0 1 1 1 l i st h e s i sp r e s e n t sa n a n a l y s i so f t h ec o n v e r g e n c eb e h a v i o ro f t h ep s 0 ，a n dd i gi n t ot h e p r e m a t u r ec o n v e r g e n c ep r o b l e m i no r d e rt oo v e r c o m et h i sp r o b l e m , t w om o d i f i e dp s o - s d p s oa n dv 口s oa r cp r o p o s e d s d p s o , m o t i v a t e db yn a t u a n dp h y s i c sp r i n c i p l e s , c a l l m a i n t a i na h i 【g l ll e v e lo fd i v e r s i t ys oa st oo b t a i nt h ea b i l i t yo fc o n t i n u o u s l ys e a r c h i n g t h e r e s u l t so fe x p e r i m e n t a ls i m u l a t i o n ss h o wt h a ts d p s oc a nn o to i l 坶o v e r c o m 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 me f f e c t i v e l y ，b u t a l s oi n c r e a s et h e p r o b a b i l i t yf o rt h es w a r mt o j m n p o u to f t h el o c a lm i n i m u m v m p s oa d j u s t st h ev e l o c i t yo ft h ep a r t i c l eb yd i m e n s i o n , w h i c hc a n f a c i l i t a t e h i g h - d i m e n s i o ns p a c es 髑l r c h i n g t h ee x p e r i m e n t a l r e s u l t ss h o wt h a tf o r3 0 毋 g r i e w a n ka n d r a s t r i g i nf u n c t i o n st h ea l g o r i t h mc a n e v e nf i n dt h e g l o b a lo p t i m u m - z e o f o r a l lt e s t i n gf u n c t i o n si nt h i se x p e r 皿e n t , v m p s o o u t p e r f o r mp s o al o t t h et w om o d i f i e da l g o r i t h m sa r ea p p l i e dt ot h et a s ko f 位d n i n gt w o q a y e rp e r c c p t r o nf o r t h r e eb e n c h m a r kc l a s s i f i c a t i o np r o b l e m sa n d c o m p a r e dw i t ho t h e rl e a r n i n ga l g o r i t h m ss u c ha s b p g da n dg a 1 1 圮e x p e r i m e n t a lr e s u l t si l l u s t r a t et h ee f f i c i e n c y t h et h e s i sa l s op r e s e n t sa s o l u t i o no f c r e a t i n gc o g n i t i v es t a t e sc l a s s i f i e ru s i n gp s o - b a s e d p e r e e p l r o n n e t w o r k ac l a s s i f i e r i sb e i n ge s t a b l i s h e da n dt r a i n e da c c o r d m gt ot h es o l u t i o nt od i s l i n g u i s hb e t w e e nt w oc h i n e s e c o g n i t i v es t a t e s ：c h i n e s ec h a r a c t e ra n dp i n y i nr e a d i n g t l l i ss o l u t i o nc a na l s ob ea p p l i e dt o s o l v ev a r i o u sc l a s s i f i c a t i o n p r o b l e m s k e y w o r d s ：p a r t i c l es w a r m o p t i m i z a t i o n ；s u r v i v a ld e n s i t y ；v e l o c i t ym u t a t i o n ；n e u r a l n e t w o r k ；c o g n i t i v es t a t e sc l a s s i f i c a t i o n ，i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：查j 荭日期：丝旦皇：! ：； 大连理，r 人学硕十学位论文 引言 1 课题意义 优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。作为一 个重要的科学分支，它一直受到人们的广泛重视，并在科学、经济以及工程领域发挥着 极为重要的作用。优化算法研究对改进算法性能、拓宽算法应用领域、完善算法体系同 样具有重要作用。因此，优化理论与算法研究是一个同时具有理论意义和应用价值的重 要课题。自上世纪8 0 年代以来，一些新颖的优化算法，如人工神经网络、混沌、遗传 算法、进化规划、模拟退火等通过模拟或揭示某些自然现象或过程而得到发展。这些 算法独特的优点和机制为解决复杂问题提供了新的思路和手段，并在诸多领域得到了成 功应用。由于其构造的直观性与自然机理，通常被称作智能优化算法。 粒子群优化算法是智能优化算法的一种，源于对乌群觅食过程中的迁徙和聚集的 模拟。它收敛速度快、易实现并且仅有少量参数需要调整，因而一经提出就成为智能优 化与进化计算领域的一个新的研究热点，目前已经被广泛应用于目标函数优化、神经网 络训练、模糊控制系统等许多领域。总的来说，粒子群优化算法与其它进化算法一样， 可以解决几乎所有的优化问题，或者是可以转换为优化问题进行求解的问题。其中最具 应用前景的领域包括多目标问题的优化、系统设计、分类、模式识别、生物系统建模、 规划、信号处理、决策和模拟等。目前，在模糊控制器的设计、车间任务调度、实时机 器人路径规划、图像分割、e e g 信号模拟、语音识别、烧伤诊断咀及探测移动目标等 方面已经有成功应用的先例。 2 理论背景 粒子群优化算法的理论背景是“人工生命”。人工生命是来研究具有某些生命基本 特征的人工系统，其中一个重要部分是利用生物技术来研究计算问题，现在已经有很多 源于生物现象的计算技巧。例如，人工神经网络是简化的大脑模型遗传算法是模拟 基因进化过程的。而粒子群优化算法的诞生则来源于另一种生物一社会系统。更确切的 是，是由简单个体组成的群落与环境以及个体之间的互动行为， 也可称作”群智能”。 群居个体以集体的力量进行觅食、御敌，单个个体只能完成简单的任务，而由单个 个体组成的群体却能完成复杂的任务，这种群体所表现出来的“智能”，就称之为群体 智能。而从群居昆虫互相合作进行工作中得到启迪，研究其中的原理，并以此原理来设 计新的求解问题的算法被称为群智算法( s w a r mi n t e l l i g e n c e ，s i ) 1 。这些模拟系统利用 局部信息从而可能产生不可预测的群体行为。例如f l o y s 和b o i d s ，他们都用来模拟鱼群 粒子群优化算法及其在神经网络中的应_ l ! f j 和鸟群的运动规律，主要用于计算机视觉和计算机辅助设计。在计算智能领域主要有两 种基于群智能的算法，一种是蚁群算法，它是对蚂蚁群落食物采集过程的模拟，已经成 功运用在很多离散优化问题上。粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ) 也是 群智算法中的一种，最初出j i mk e n n e d y 于1 9 9 5 年提出并成功的用于函数优化，后来 又进行了有效的拓展，它是对鸟群觅食过程中的迁徙和聚集的模拟 2 。 3 本文工作 本文主要对粒子群优化算法及其在神经网络中的应用这两方面进行研究。 本文的工作主要有以下四个方面： ( 1 ) 对粒子群算法进行了全面的介绍，剖析了算法的全局与邻域两种模式、总结了算 法改进的三种途径，阐明了过早收敛问题的产生原因，从实验和数学两种角度对算法收 敛性进行分析，从而为算法改进提供了理论支持。 ( 2 ) 针对原算法中存在的过早收敛和易陷入局部极值问题，给出两种改进型粒子群算 法，并通过仿真实验与基本算法进行了对比分析。 ( 3 ) 针对神经网络的传统学习算法的收敛速度慢、泛化能力弱等缺点，将改进粒子群 算法作为学习算法用于神经网络训练，并使用标准分类问题对其进行测试。 ( 4 ) 建立了一套完整的使用神经网络进行认知状态分类的方案；针对蹦r j 脑数据维 度过高的问题，给出两种可行的特征抽取方法：使用基于改进型粒子群算法的神经网络 建立认知状态分类器，用于人脑认知状态分类。 4 组织结构 本文共分五章前言部分介绍了粒子群优化算法的理论背景及应用价值，阐明了对 粒子群算法进行研究的目的和意义。 第一章介绍了粒子群优化算法的基本原理和具体应用，对全局和邻域两种模式进行 了分析，讨论了改进粒子群算法的三种途径，并与其它进化算法进行了比较。 第二章给出了粒子群算法收敛性的实验和数学分析，并对算法收敛性进行证明。 篼三章给出了两种基本粒子群的改进算法，使用标准b e n c h m a r k 函数优化问题对它 们进行测试，并对实验结果进行详细的讨论与分析。 第四章首先简要地介绍神经网络的基本原理，接着将两种改进的粒子群算法应用到 二层感知机神经网络的训练中，通过三组b e n c h m a r k 分类数掘集对其进行测试。并将测 试结果与其它几种学习算法进行了性能对比分析。最后使用基于改进粒子群算法的神经 网络建立了认知状态分类器，对汉语拼音与汉字字形实验中的两种认知状态进行分类。 结论部分总结全文，指出文章中存在的一些问题，并对今后的工作进行了展望。 2 1 粒子群优化算法概述 粒子群优化算法是由k e 皿e d y 和e b e r h a r t 等于1 9 9 5 年提出的一种基于种群搜索的 自适应进化计算技术【l 】。算法最初受到飞鸟和鱼类集群活动的规律性启发。利用群体智 能建立了一个简化模型，用组织社会行为代替了进化算法的自然选择机制，通过种群间 个体协作来实现对问题最优解的搜索。 1 1 基本粒子群算法 1 1 1 基本原理 粒子群优化算法来自予对鸟群的捕食行为的模拟。设想这样一个场景：一群鸟在随 机搜索食物，在这个区域里只有一块食物，所有的鸟都不知道食物在那里，但是它们知 道当前的位置离食物还有多远，那么找到食物的最优镱略是什么呢? 最简单有效的就是 搜寻目前离食物最近的鸟的周围区域。p s 0 从这种模型中得到启示并用于解决优化问 题。 在p s o 模型中，每个优化问题的解都是搜索空间中一个“粒子”的状态。每个粒子 都有一个由被优化函数决定的适应值( 矗n 螂sv a l u e ) ，同时还有一个速度决定它们的飞行 的方向和距离。粒子根据自身及同伴的飞行经验进行动态调整，也可以说是通过跟踪两 个位置来更新自身。一个是粒子本身所找到的最优解p b e s t ，即个体最好位置；另一个 是燕个种群当前找到的最优解g b e s t ，即全局最好位置。 p s o 算法运行过程中。随机产生一个初始种群并赋予每个粒子一个随机速度，并根 据公式( 1 1 ) 和( i 2 ) 来更新粒子的速度和位置。 r i d o + 1 ) = w 年v 时o ) + c 6 v i ( p 时o ) 一z 时o ”+ c 2 妒2 + ( p 蚪( ，) 劫( r ) ) x t d o + 1 ) = ( 0 + 甜o + 1 ) ( 1 1 ) ( 1 2 ) 其中，v i d 是粒子的速度，w 是惯性因子，c l 、c 2 为学习因子，仍、仍是介于( 0 ，1 ) 之 间的随机数，x i d 是粒子当前位置，肋代表粒子当前最好位置，p g d 代表种群当前最好位 置，也就是全局最优。 公式( 1 1 ) 中的第一部分称为动量部分，表示粒子对当前自身运动状态的信任，并为 粒子提供了一个必要动量，使其依据自身速度进行惯性运动。第二部分称为认知部分， 代表了粒子自身的思考行为，鼓励其飞向自身曾经发现的摄佳位置。第三部分称为社会 3 一 一 垫量壁垡些蔓鲨墨基奎塑丝婴垫主些堕旦 部分，表示粒子间的信息共享与相互合作，它引导粒子飞向粒子群的最佳位置。这三个 部分之间的相互平衡和制约决定了算法的主要性能。惯性因子w 即是粒子上一次的速度 对本次飞行速度的影响因子，它主要用于平衡粒子群的全局搜索能力和局部搜索能力。 有研究表明w 对优化性能的影响很大，较大的w 值有利于跳出局部极小点，而较小的 w 值有利于算法收敛 4 1 。p s o 算法的这些观点某种程度上可以通过心理学加以解释：在 寻求一致的认知过程中，个体往往记住它们的信念，同时考虑同伴们的信念；当个体察觉 同伴的信念较好时，它将根据同伴的信念进行适应性地调整。 1 1 2 算法流程 p s o 算法运行时首先初始化一群粒子( 种群规模为p ) ，包括随机位置和速度：并根 据适应函数计算每个粒子的适应度；接着，将每个粒子的适应值与自身经历过的最好位 置p b c s t 作比较。如果较好，则将当前位置作为自身最好位置p b e s t ；将每个粒子的适应 值与种群所经历的最好位置g b e s t 作比较，如果较好，则作为种群最好位置g l m s t ；最后 根据公式( 1 1 ) 和( 1 2 ) 更新粒子的速度和位置，并继续计算下一个粒子。图1 1 给出了算 法的具体流程。 1 1 3 参数设霹 基本p s o 算法包含以下参数：种群规模p ，粒子维度d 。粒子活动范围x ，惯性权重w ， 学习因子c 1 和c 2 ，最大速度v m a x ，最大迭代次数m a x l t e r a t i o n 。 ( 1 ) p ：种群中的粒子总数，通常设为1 0 - 4 0 闯的一个值。 ( 2 ) d ：由具体优化问题决定。就是问题解空间的维度。 ( 3 ) x ：粒子的活动范围，由优化问题决定。每一维可是设定不同的范围。 ( 4 ) v m a x ：最大速度。决定粒子在一个循环中最大的移动距离。通常设定为粒子活动 范围的宽度，例如，对于粒子( x 1 ，x 2 ，x 3 ) ，x l 属于卜1 0 ，】o ，那么v m a x 的大小就 是2 0 。如果v m a x 太高，粒子可能会飞过较好解，从而丧失局部搜索能力；如果v m a x 太 小，粒子不能在局部区间之外进行足够的探索，导致陷入局部极值。 ( 5 ) 权重因子w ：使粒子保持运动惯性，使其有扩展搜索空间的趋势。有能力探索新 的区域。w 一般取小于或等于1 4 的定值，也可设计为在迭代中随时间线性减少。 ( 6 ) 学习因子：c 1 和c 2 代表将每个粒子推向p b e s t 和g b e s t 位置的统计加速项的 权重。较低值允许粒子在被拉回之前可以在目标区域外徘徊，而较高值则导致粒子突然 的冲向或越过目标区域。一般取c l 等于c 2 ，并且范围在0 和4 之间。 ( 7 ) 最大迭代次数：算法的终止条件，该值由具体的问题确定。 一4 一 大连理工大学硕士学位论文 厂、 随机扔始化粒子 的位俺羽j 速度 ，号lj ，- l 对侮个粒了l 1 2 ) 则会导致算法很难收 敛 9 】。一些学者还对惯性因子和v m a x 闯的交互关系进行了研究。这样，当v m a x 增加时， 可通过减小w 来达到平衡搜索，而w 的减小可使得所需的迭代次数变小。从这个意义上 看，可以将v m a x 固定为粒子每维的变化范围，只对w 进行调节。通过实验进一步发现， 线形变化的惯性因子有助于提高整个算法的性能。这是因为这种设置有助于在前期获得 较高的探索能力以搜索到较大范围，而在后期则有较高的开发能力以加快收敛速度。为 此可将w 设为随时间线性减小。例如由1 4 到0 。由0 9 到0 4 ，由0 9 5 到0 2 等。值得 注意的是，惯性因子与模拟退火算法中的温度参数很相像。模拟退火算法中一个重要过 程是使用温度进度表来调节系统温度，温度越高，算法跳出局部极值搜索到其他空间的 概率就越大。因此具有自适应特性的惯性因子也可以看作是模拟退火算法中的温度进度 表。s h i 和e b e r h a r t 提出一个模糊系统来调节w ，该系统包括9 条规则，有两个输入和一 个输出，每个输入和输出定义了3 个模糊集 1 0 3 。一个输入为当前代的全局最好适应值， 另一个为当前的w ：输出为w 的变化，结果显示该方法能大为提高平均适应值。 此外c l e r e 引入了收缩因子k 来确保算法的收敛性【1 l 】，从而达至提高局部收敛 速度的目的。该方法不单单调节速度更新方程中的某个参数，而是针对w 、e l 和c 2 进 行整体调节，以此来提高收敛速度。基本p s o 中的c 1 与c 2 实际上等价于公式( 1 6 ) 中的 k e l 与k ，c 2 而k 本身则可以看作受c l 和c 2 限制的w 。修改后的速度更新方程如 下： ( ，+ 1 ) = k + ( ( ，) + c i 妒i + ( p “( r ) 一( ，) ) + c 2 仍+ ( p 州( ，) 一( r ) ) ) ( 1 6 ) 肛屏一瓜而l “7 其中o = c 1 + c 2 且m 4 。 8 大连理工大学硕士学位论文 a n g e l i n e 借鉴了遗传算法中选择操作用来提高收敛到局部极值的速度【1 2 】，但却损 失了大范围搜索能力，从而导致无法搜索到全局最优。l 0 v b j e r g 在a n g e l i n e 的基础上引 入了遗传算法中的复制和再结合操作来提高算法的性能。 1 3 3 提高种群多样性 目前，p s o 算法作为一种新的随机搜索算法，仍旧存在着早熟收敛和收敛速度慢这 两个难题，并且具有种群多样性随代数增加下降过快，有可能不收敛到全局最优解等缺 点。为了避免早熟收敛。一些研究者提出了通过控制种群多样性来提高算法性能的方 法。一方面通过解决粒子间的冲突和聚集问题 1 3 1 、分析粒子和种群最优位置的距离 【1 4 】、通过增加环境检测和响应、种群随机多代初始化等思想【1 5 】，给出了不同策略来 增强种群多样性，使算法不至于过早陷入局部极小。另一方面，通过引入遗传算法的 “变异”操作来增强全局搜索性能也是一种十分有效的方式。而临域模型也有助来提高 粒子群的种群多样性。 文献【1 6 】【1 7 】深入分析了不同均值和方差的高斯变异操作对增强算法性能的影响。 文献【1 8 】通过对粒子速度或位置引入了一个小概率随机变异操作来增强种群多样性 ( d p s o ，d i s s i p a t i v ep s o ) ，使算法能有效地进行全局搜索，但是过大的变异率在增加 种群多样性的同时也将会导致群体发生混乱，使种群不能进行精确地局部搜索，减缓了 算法的收敛速度。它的公式描述如下； i f ( r 3 c v ) t h e n r i d 2r 4 + u c m ( 1 3 ) 其中b 一为相互独立的均匀分布在【0 ，l 】的随机变量，c v 用来控制速度的变异率， g i l 是一个常量用来控制变异幅度的大小。 l o v b j e r g 提出了一种改善种群多样性的途径一自组织临界点控制( s o c p s o ，s e l f - o r g a n i z e dc r i t i c a l i t yv s o ) b g 。算法对每个粒子增加了当前临界值属性，如果两个粒子闯 的距离小于预定阈值则增加彼此的临界值，当个体临界值超过系统全局极限值时，则需 重新分配其在搜索空间中的位置，以达到控制种群多样性的目的值得注意的是， s o c p s o 对于p b c s t 的重新初始化给出了两种基本方法：一种是使粒子忘记p b c s t 并重 新赋予一个新值；一种是给其一个小的推动力使其偏离p b e s t 。在具体实验中可以发现 第一种方法能有效地加快算法的收敛速度。 r a t n a w e e r a 在自组织算法的基础上给出了一种变异操作随时间变化的自适应层次 p s o 算法( h p s o ，s e l f - o r g a n i z i n gh i e r a r c h i c a l p s o ) 来进一步提高搜索性能【2 0 】，并给 9 粒子群优化算法及其在神经网络中的应用 出了适合变异操作的自适应参数选择方式，但是h p s o 算法消除了速度公式中的惯性部 分，其发生变异条件是粒子速度为零，使其不能快速、有效地逃出局部极小点。虽然这 些研究工作已经给出了提高p s o 算法全局搜索能力的方法，但是它们很难在提高搜索 速度和保持种群多样性之间达到平衡。而h p s o 在引入变异操作同时，消除了速度的惯 性部分，给出了新的参数自适应方法、速度公式和变异- g d 牛如下： v l , t ( t + 1 ) = c 1 x 妒l ( p 肼o ) 一x 埘( f ) ) + c 2x 仍x ( 翰( f ) 一x 讨( f ) ) i f ( v i d = 们t h e nr i d ；r 6 + r 5 + v ( 1 9 ) ( 1 1 0 ) 其中v 是重新初始化的速度；r 。为均匀分布在 0 ，1 的随机变量；r 6 为一随机变 量，当随机数小于0 5 时为1 ，大于0 5 时为一1 。 以上这些改进通常降低了算法的局部收敛速度，但却能获得了更好的优化结果，这 在多模态和较复杂问题的优化中体现的尤为明显。 1 4 与其他进化算法的比较 粒子群算法与其他进化算法有许多相似之处。首先，粒子群算法和其它进化算法相 同，都使用“种群”概念，用于表示一组解空间中的个体集合。两者都随机初始化种 群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系 统都不是保证一定找到最优解。如果将粒子所持有的最好位置也看作种群的组成部分， 则粒子群的每一步迭代都可以看作是一种弱化的选择机制。在( + a ) 进化策略算法 中，子代与父代竞争，若子代具有更好的适应值，则子代将替换父代，而p s o 算法的 进化方程式也具有与次类似的机制，其唯一的差别在于，粒子群算法只有当粒子的当前 位置与所经历的最好位置相比具有更好的适应值时，其粒子所经历的最好位置才会唯一 地被该粒子当前的位置所替代。可见，p s o 算法中也隐藏着一定形式的“选择”机制。 在遗传算法中存在着交叉( c r o s s o v e r ) 和变异( m u t a t i o n ) 操作，粒子群算法中虽然在表 面上不具备这样的操作，但在本质上却有相通之处。粒子群算法的速度更新方程与实数 编码的遗传算法的算术交叉算子很类似。通常，算术交叉算子由两个父代个体的线性组 合产生两个子代个体；而在p s o 算法的速度更新方程中，如果不考虑第一项，也就是 带惯性权重的速度项。就可以将方程理解成由两个父代个体产生一个子代个体的算术交 叉运算。从另一个角度上看，同样不考虑第一项，速度更新方程也可以看作是一个变异 算子，其变异的强度大小取决于个体最好位置和全局最好位置之间的距离，可以把个体 1 0 大连理工大学硕士学位论文 最好位置和全局最好位置看作父代，变异就可以看作是由两个父代到子代的变异。至于 前面略去的惯性速度项，也可以理解为一种变异的形式，其变异的大小与速度相乘的惯 性因子相关，惯性因子越接近l ，则变异强度越小；越远离1 ，则变异强度越大。通常 在进化算法的分析中，人们习惯于将每一步进化迭代理解为用新个体代替旧个体的过 程。 与遗传算法等其他进化算法比较，p s o 的具有独特的信息共享机制。在遗传算法 中，染色体互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动。在 p s o 中，只有自身最优和全局最优提供信息给其他的粒子，这是单向的信息流动。整 个搜索更新过程是跟随当前最优解的过程。与遗传算法比较，所有的粒子很可能更快的 收敛于最优解。p s o 算法与其他进化算法另个重要不同点在于它在进化过程中同时 保留和利用位置与速度信息，而其它进化算法仅保留和利用位置信息。 从以上分析中看，基本p s o 算法与其他进化算法有相似之处，但同时也具备其它 算法不具备的特性，特别的是，p s o 算法同时将粒子的位置与速度模型化。并给出了它 们的进化方程。 1 5 具体应用 当前，p s o 算法已得到广泛应用，本节将简要介绍一些具体的应用实例。p s o 最 直接的应用或许就是多元函数的优化问题，包括带约束的优化问题。如果所讨论的函数 受到严重的噪音干扰而呈现非常不规则的形状，同时所求的不一定是精确的最优值，则 p s o 算法能得到很好的应用。比如在半导体器件综合方面，需要在给定的搜索空间内根 据所希望的器件特性来得到符合要求的设计参数，而所能利用的器件模拟器通常得到的 特性空间是高度非线形的。有人用p s o 替换g a 进行了计算，发现p s o 能比g a 更快 地找到较高质量的设计参数。 另外，还有一种更广泛的应用：简单而有效地演化的人工神经网络，不仅用于演化 网络的权重，而且包括优化神经网络的结构。作为一个演化神经网络的例子，p s o 算法 已应用于分析人的颤抖。对人颤抖的诊断，包括帕金森( p a r k i n s o n ) 病和原发性颤抖，是 一个非常具有挑战性的领域。p s o 已成功地应用于演化个用来快速和准确地辨别普通 个体和有颤抖个体的神经网络，而网络的输入则为从一个活动变化记录系统中获得的归 一化的移动振幅。另一个应用例子是使用p s o 对一个电气设备的功率反馈积电压进行 控制。这里采用一种二进制与实数混合的p s o 算法来决定对连续和离散的控制变量的 控制策略，以得到稳定的电压。 粒子群优化算法及其在神经网络中的应用 此外，p s o 还在动态问题中得到应用。一般而言，p s o 与其他演化算法一样，能 用于求解大多数优化问题。在这些领域中。最具潜力的有系统设计、多目标优化、分 类、模式识别、信号处理、机器人技术应用、决策制定、模拟和证明等。例子包括模糊 控制器设计、工作调度、实时机器人路径设计和图像分割等。 1 2 一查鲨堡：! ；丛堂堡堂笪笙奎 2 粒子群算法收敛性分析 2 1 实验分析 对于基本粒子群算法的速度更新方程，如果没有第1 部分，即w = o ，则速度只取决于 粒子当前位置和其历史最好位露p b e s t 和g b e s t 。在算法运行中，假设一个粒子位于当 前全局最好位置，由于不受惯性因素的影响，它将保持静止。在这种情况下，粒子群将收 缩到当前的全局最好位置，导致大面积搜索能力的丧失。如果去掉第2 部分即c l = o ，在 粒子间的相互作用下，它将具有比基本p s o 更快的收敛速度，但对于多模态函数等较复杂 问题，则很容易陷入局部极值。如果没有第3 部分，即c 2 = 0 ，粒子间就丧失了沟通的纽 带，导致个体间没有交互，各自在搜索空问中搜索，因而得到解的几率非常小。 有实验表明在算法运行的开始阶段收敛速度极快，运动轨迹呈正弦波摆动，但到了 一定程度速度就开始减漫甚至停滞 2 1 。般来说，当所有粒子速度均为o ，这时即可 认定算法已经收敛。在对复杂的单模态和多模态函数的多组测试实验中可以发现，基本 p s o 算法中的绝大多数粒子迭代一千次后速度与。已非常接近( 通常可达到e 一7 ) ，这时 算法实际上已经停滞，而此时通常与己知的全局极值有很大差距，甚至连局部极值也难 以达到。 现在将注意力集中到种群最优粒子上。在当前时刻，促使最优粒子移动的“动力” 是速度方程中的惯性部分，因为最优粒子的当前位置与该粒子最好位置及种群的最好位 置相同。经过这一时刻，最优粒子在惯性的作用下继续移动，一种可能性是种群找到了 一个新的全局最优位鬣( 其他的粒子有可能成为最优粒子) ；另一种可能是种群并未找 到更好的位置( 实验发现这种情况在迭代中后期更可能发生) ，特别是最优位置在一段 时间内没有