（计算机应用技术专业论文）基于并行pso的模式分类算法及其应用研究.pdf

摘要 模式分类是l ：多工程领域如自控监测、图像识别、故障诊断、物料配制、医疗诊 断等领域广泛应用的一种关键技术。经典的模式分类方法主要是基于多元统计分析方 法，近年来人工神经网络技术也逐渐成为模式分类的有效工具。这两类方法各有所长， 多元统计分析方法计算规范，有明确的概率意义，但需要有足够多的样本，并且要遵 从一定的分布；人工神经网络技术表达能力强，适用范围广，但网络设计困难，训练 费时，还存在局部极值等缺点。 用于模式分类问题的神经网络大多数采用多层前向神经网络，并且使用反向传播 算法( b p 算法) 。但b p 算法过度依赖于初始权值的选择，收敛速度缓慢且容易陷入局 部最优。b p 算法的上述缺陷使其训练的神经网络的输出具有不一致性和不可预测性， 导致模式分类的可靠性降低。遗传算法的并行搜索策略及全局优化特性使其成为同益 普遍的神经网络训练算法。通过实验证明，与b p 算法相比，遗传算法( g a 算法) 训练 的神经网络在提高分类正确率的同时可以加快训练的收敛速度。但是遗传算法复杂的 遗传操作如选择、复制、交叉、变异使神经网络的训练时间随着问题的规模及复杂程 度呈指数级增长，并且由于缺乏有效的局部区域搜索机制，算法在接近最优解时收敛 缓慢甚至出现收敛停滞现象。粒子群优化算法( p s o 算法) 是一种基于群体智能理论 的优化算法，通过种群中粒子删的合作与竞争产生的群体智能指导优化搜索。p s o 保 留了基于种群的全局搜索策略，采用的速度一位移模型操作简单，避免了复杂的遗传 操作。 随着科学计算的不断发展，问题搜索空问的不断扩大，面对越来越复杂的搜索空 i h j ，传统的进化计算的方法通常与种群规模、参数的选择、问题的复杂程度等因素有 关，当种群规模较大、参数较复杂、搜索空问增大时，在单个c p u 上运行的优化算法 通常需要很长的计算时问，甚至有时无法得到满意的结果。进化计算出于其本身的内 在的并行性，特别适合大规模的并行计算。将并行计算机的高速并行性和进化计算的 天然并行性相结合，能够有效的解决了大规模的优化问题。 本文提出了种并行粒子群优化算法p p s o ，该算法对采用m a s t e r - s l a v e 及s p m d 桀于并行p s o 的模式分类算法及e 应用研究 相结合的并行编程模式，主进程主要完成种群随机初始化、任务的分发和根据适应值 进行粒子的选择从进程主要完成粒子适应值的计算。该算法采用速度一位移搜索模 型，操作简单，计算复杂度较低，并通过惯性权重协调全局搜索结果与并行局部搜索 结果，既能以较大的概率保证最优解，克服b p 算法局部最优的缺陷，又可以提高局 部区域的收敛速度，避免g a 算法在局部区域搜索过程中的收敛停滞现象，同时提高 求解的速度。 本文将并行p s 0 算法用于优化单个多层前向神经网络和神经网络集成技术中，粒 子群中的每一个粒子的分量映射为神经网络中的一组不同权值，在曙光天潮t c 3 0 0 0 服务器上，利用m p i c h 并行环境设计实现了该并行程序，对入侵检测数据及b r e a s t c a n c e r 模式分类数据进行测试。实验结果表明，并行的p s 0 算法是有效的神经网络训 练算法，用于神经网络集成中解决模式分类问题，不仅能提高网络的泛化能力，提高 分类误差精度，而且能加快收敛的速度，具有较好的加速比。 关键词并行计算，p s o ，神经网络，模式分类，神经网络集成 i i a b s t r a c t p a t t e r nc l a s s i f i c a t i o ni sak i n do ft e c h n o l o g yu s e di nal o to fp r o j e c tf i e l d si n c l u d i n g a u t o m a t i cc o n t r o l m o n i t o r ，i m a g er e c o g n i t i o n ，t r o u b l e dd i a g n o s e ，s u p p l i e sc o m p o u n d ， m e d i c a ld i a g n o s i s ，e t c t h ec l a s s i c a lc a t e g o r i z e dm e t h o do f p a t t e r nc l a s s i f i c a t i o ni sm a i n l y t oc o u n tt h ea n a l y t i c a lm e t h o db a s e do np l u r a l i s m i nr e c e n ty e a r s ，a r t i f i c i a ln e u r a ln e t w o r k t e c h n o l o g yb e c o m e se f f e c t i v et o o lt h a tp a t t e r nc l a s s i f i e dg r a d u a l l yt o o t h e s et w ok i n d so f m e t h o d sh a v et h e i ro w ns t r o n gp o i n t s p l u r a l i s mc o u n t st h ea n a l y t i c a lm e t h o dc a l c u l a t e s n o r m a l l y ，t h e r ea r ec l e a rp r o b a b i l i t ym e a n i n g s ，b u tn e e da b u n d a n ts a m p l e s ，a n ds h o u l d c o m p l yw i t h c e r t a i nd i s t r i b u t i o n t h ea r t i f i c i a ln e u r a ln e t w o r k t e c h n o l o g y i s s t r o n gi n a b i l i t yt oe x p r e s sa n ds u i t a b l ef o re x t e n s i v er a n g e ，b u tt h en e t w o r ki sd i f f i c u l ti nd e s i g n ，i t i st i m e c o n s u m i n gt ot r a i n ，s o m ee x t r e m ev a l u ea r ed e f i c i e n t t h en e u r a ln e t w o r ku s i n gi np a t t e r nc l a s s i f i c a t i o np r o b l e m sm o s t l ya d o p tm u l t i l a y e r f e e d - f o r w a r dn e u r a ln e t w o r ka n du s et h eb a c k - p r o p a g a t i o na l g o r i t h m ( b pa l g o r i t h m ) b u t b pa l g o r i t h md e p e n d so nt h ec h o i c eo fi n i t i a lw e i g h tv a l u ee x c e s s i v e l y ，r e s t r a i nt h es p e e d s l o w l y a n da p tt of a l li n t ot h el o c a lo p t i m i z a t i o n t h ea b o v em e n t i o n e dd e f e c t so fb p a l g o r i t h mm a k et h eo u t p u to ft h en e u r a ln e t w o r ko fi t st r a i n i n gh a v ei n c o n s i s t e n c ya n d u n p r e d i c t a b i l i t y ，c a u s i n gt h ed e p e n d a b i l i t yo fp a t t e rc l a s s i f i c a t i o ni sr e d u c e d t h ep a r a l l e l s e a r c ht a c t i c sa n dg l o b a lo p t i m i z a t i o no fg e n e t i ca l g o r i t h mm a k ei tb e c o m et h e g e n e r a l n e u r a ln e t w o r kt r a i n a l g o r i t h mi n c r e a s i n g l y p r o v i n gt h r o u g ht h ee x p e r i m e n t ，c o m p a r e d w i t hb pa l g o r i t h m ，t h en e u r a ln e t w o r k t r a i n i n gb y g aa l g o r i t h mc a n i m p r o v e t h e c l a s s i f y i n gc o r r e c tr a t e a n da c c e l e r a t et h ec o n v e r g e n c eo ft r a i n i n g b u tt h e c o m p l i c a t e d h e r e d i t yo p e r a t i o n ss u c h a s s e l e c t i o n ，d u p l i c a t i o n ，c r o s s i n g ，a n dm u t a t i o nm a k en e u r a l n e t w o r kt r a i n i n gt i m ep r e s e n tw i t he x p o n e n ti n c r e a s ew i t ht h es c a l ea n dc o m p l e x i t yo ft h e p r o b l e m s i nd e f e c t o fe f f e c t i v es o m el o c a ls e a r c hm e c h a n i s m ，t h ea l g o r i t h md i s a p p e a r s l o w l yp h e n o m e n o no fc o n v e r g e n c ew h i l ec l o s i n g t ot h e o p t i m i z a t i o n v a l u e p a r t i c l e s w a r mo p t i m i z a t i o ni sak i n do fo p t i m i z a t i o na l g o r i t h mo fi n t e l l e c t u a l t h e o r yb a s e do n p o p u l a t i o n ，t h i sa l g o r i t h m s e a r c ht h e o p t i m i z a t i o n v a l u e u s i n g t h e c o o p e r a t i o n a n d c o m p e t i t i o no ft h ep a r t i c l e s p s oh a sk e p tt h eg l o b a ls e a r c ht a c t i c s ，a d o p t e dt h em o d e lo f v e l o c i t y d i s p l a c e m e n t ，a n dh a sa v o i d e dc o m p l i c a t e dh e r e d i t a r yo p e r a t i o n s w i t ht h ec o n s t a n td e v e l o p m e n to fs c i e n t i f i cc a l c u l a t i o na n dt h ec o m p l i c a t e ds e a r c h i i i 壮十并行p s o 的模式分类算法发j t 朋州究 s p a c e ，t r a d i t i o n a l e v o l u t i o n c o m p u t i n g m e t h o d s u s u a l l y h a v e s o m e t h i n g t od ow i t h p o p u l a t i o ns c a l e ，t h ec h o i c eo fp a r a m e t e r s ，t h ep r o b l e m sc o m p l e x i t y ，e t c i tt a k e sal o n g t i m et os e a r c ht h eo p t i m a lv a l u eo ni n d i v i d u a lc p uw h e nt h ec o m p u t i n gh a sal a r g es c a l e p o p u l a t i o n ，t h ec o m p l i c a t e dp a r a m e t e r sa n dl a r g es e a r c hs p a c e i ti s e v e nu n a b l et or e c e i v e t h es a t i s f a c t o r yr e s u l ts o m e t i m e s e v o l u t i o nc o m p u t i n gh a st h ei n h e r e n tp r o p e r t yo f p a r a l l e l ， e s p e c i a l l ys u i t a b l ef o rl a r g e s c a l ep a r a l l e lc o m p u t a t i o n i t i se f f e c t i v et os o l v eal a r g e - s c a l e o p t i m a lp r o b l e m t h a tt h i sp r o p e r t yo f p a r a l l e lc o m b i n e sw i t ht h eh i g hp a r a l l e lc o m p u t e r t h i s p a p e rp r o p o s e sp a r a l l e lp a r t i c l e s w a r mo p t i m i z a t i o n a l g o r i t h m ，t h ea l g o r i t h m a d o p t st h ep a r a l l e lm o d eo fm a s t e r s l a v ea n ds p m d ，t h em a i np r o c e s sf i n i s h e sr a n d o m i n i t i a l i z a t i o no fp o p u l a t i o n ，d i s t r i b u t i o no ft a s ka n ds e l e c t i o no fp a r t i c l e a c c o r d i n g t o f i t n e s se v a l u a t i o nr e s u l t ，a n dt h es l a v ep r o c e s sm a i n l yf i n i s h e st h ec a l c u l a t i o no ff i t n e s s e v a l u a t i o n so f p a r t i c l e s t h i sa l g o r i t h ma d o p t st h e m o d e lo f s p e e d d i s p l a c e m e n t ，s i m p l yt o o p e r a t e ，c a l c u l a t ec o m p l e x i t yi sr e l a t i v e l yl o w ，a n dc o o r d i n a t et h eg l o b a lo p t i m a lv a l u ea n d t h er e s u l to fp a r a l l e ll o c a l o p t i m a lv a l u eu s i n gt h e i n e r t i aw e i g h t s t h i sa l g o r i t h mc a n s e a r c ht h eo p t i m a lr e s u l tw h i tg r e a t e rp r o b a b i l i t y ，o v e r c o m et h ed e f e c t so fb p a l g o r i t h m ， a l s oc a n i m p r o v e s o m e c o n v e r g e n c es p e e d a n d p r e v e n t g aa l g o r i t h m c o n v e r g e n c e s t a g n a t i o ni n t h ec o u r s eo fs e a r c h i n gl o c a la r e a ，w h i l e i m p r o v i n gt h es p e e do fs o l v i n g p r o b l e m s p a r a l l e l p 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 u s e st o o p t i m i z es i n g l em u l t i l a y e r f e e d f o r w a r dn e u r a ln e t w o r ka n de n s e m b l eo fn e u r a ln e t w o r k ，e a c hw e i g h to fp a r t i c l e s h i n e su p o na st h ew e i g h t so fn e u r a ln e t w o r k w ed e s i g nt h ep a r a l l e l p r o g r a mu s i n gt h e m p i c he n v i r o n m e n to nd a w n i n gt c 3 0 0 0 i d sd a t aa n db r e a s tc a n c e rd a t aa r et e s t e dt h e a l g o r i t h m t h ee x p e r i m e n tr e s u l t ss h o w t h a tp a r a l l e lp s oi sa ne f f e c t i v et r a i n i n ga l g o r i t h m u s i n gi nn e u r a ln e t w o r k t h e s ep a r a l l e ln e u r a ln e t w o r ke n s e m b l ea l g o r i t h ms o l v i n gp a t t e r c l a s s i f i c a t i o np r o b l e m sn o to n l yc a ni m p r o v et h eg e n e r a l i z a t i o no fn e u r a ln e t w o r ka n dc a n i m p r o v e t h ep r e c i s i o no fc l a s s i f i e de r r o r ，b u ta l s oc a na c c e l e r a t et h ec o n v e r g e n c e s p e e d k e y w o r d sp a r a l l e lc o m p u t i n g ，p s o ，n e u r a ln e t w o r k ，p a t t e r nc l a s s i f i c a t i o n ，n e u r a l n e t w o r ke n s e m b l e 1 v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的 研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律责任由本人承担。 论文作者签名：篮! 蠹日期：地：主：玉l 关于学位论文使用授权的声明 本人完全了解济南大学有关保留、使用学位论文的规定，同意 学校保留或向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借鉴；本人授权济南大学可以将学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：趣! 盏 导师签名：日期：2 堂：s ：i f 峻 辛 一一。二一篓! 曼冬翌曼! ：苎堡坠1 1 1 课题研究的背景 第一章引言 ：i = 业、经济、医疗等领域的许多实际问题如质量控制、破产预测、图像识别、医 疗诊断等可以转化为模式分类问题求解。经典的模式分类方法主要是基于多元统计分 析方法，浚方法计算规范，有明确的概率意义，但需要有足够多的样本，并且要遵从 一定的分布【1 1 。神经网络自学习、自组织、容错以及模拟非线性关系的能力使其特别 适合解决复杂的模式分类问题。h o r n i k i 】证明采用s i g m o i d n l f i j 应函数的三层前馈神经 网络能够以任意精度模拟复杂的非线性关系，神经网络上述性能的实现依赖于对神经 网络的充分训练。因此，训练算法对于神经网络的模式分类性能有着决定性影响。 b p 算法是最普遍的神经网络训练算法。但是，r m u l h a r t | 2 】研究证明：基于梯度下 降的b p 算法依赖于初始权值的选择，收敛速度缓慢且容易陷入局部最优。b p 算法的上 述缺陷尤其是局部优化特性使其训练的神经网络的输出具有不一致性和不可预测性， 导致模式分类的可靠性降低。遗传算法的并行搜索策略及全局优化特性使其成为日益 普遍的神经网络训练算法。s e x t o n 3 1 通过实验证明，与b p 算法比较，遗传算法训练的 神经网络在提高分类f 确率的同时可以加快训练的收敛速度。但是，遗传算法复杂的 遗传操作如选择、复制、交叉、变异使神经网络的训练时间随着问题的规模及复杂程 度呈指数级增长i ”，并且由于缺乏有效的局部区域搜索机制，算法在接近最优解时收 敛缓慢甚至出现收敛停滞现象【5 1 。 粒子群优化算法( p a r t i c l es w a r m o p t i m i z e r ，p s o ) 是一种新兴的基于群体智能的 随机全局优化算法，通过种群中粒子问的合作与竞争产生的群体智能指导优化搜索 1 a l 。与进化算法比较，p s o 算法保留了基于种群的全局搜索策略，其采用的速度一位 移模型操作简单，避免了复杂的遗传操作，在非线性函数优化【6 】、电压稳定性控制1 7 1 、 动态日标优化 8 1 等实际问题取得了成功的应用。国内对粒子群优化算法的研究刚刚起 步。文献 1 2 1 1 3 5 1 综述性地介绍了粒子群优化算法及其理论发展与实际应用。文献【1 3 1 通过对算法基本模型的改进，改善了p s o 摆脱局部极值的能力，以5 个基准函数测试， 改进的算法优于基本p s o 算法以及惯性权重模型的p s o 算法。文献f 9 哿粒子群优化算 法用于同步发电机参数的辨识，实验结果显示，算法可有效地辨识同步发电机的运行 皋十并行p s o 的模式分类算法及l e 心用研究 参数，简单实用，具有较强的可行性。 随着科学计算的发展，问题搜索空间的不断扩大，面对越来越复杂的搜索空间， 采用传统的进化计算的方法在优化效率和求解的质量上都显得“力不从心”。随着高 性能计算机和高性能网络设施的出现，并行处理技术得到开益广泛的关注【4 9 1 1 5 1 】【5 4 】。 进化计算由于其本身内在的并行性，特别适合大规模的并行计算。将并行计算机的高 速并行性和进化计算的天然并行性相结合，能够促进进化计算更有效的解决大规模的 优化问题。国内外研究表明，并行进化计算方法不仅可以提高求解的速度和解的质量， 甚至可以获得超线性的加速比【4 2 】1 5 0 1 。 1 2 课题研究的目的及意义 基于种群的进化计算方法的成功与否通常与种群规模、参数的选择、问题的复杂 程度等因素有关。当种群规模较大、参数较复杂、搜索空间较大时，在单个c p u 上 运行的进化优化算法通常需要很长的计算时间，甚至有时无法得到满意的结果。 本文提出了一种并行粒子群优化算法( p a r a l l e lp a r t i c l es w a r mo p t i m i z e r ，p p s o ) ， 为解决优化大规模的工程问题提供一个新的选择。并行粒子群优化算法采用速度一位 移搜索模型，操作简单，计算复杂度较低，并通过惯性权重协调全局搜索结果与并行 局部搜索结果，既能以较大的概率保证最优解，克服b p 算法局部最优的缺陷，又可 以提高局部区域的收敛速度，避免g a 算法在局部区域搜索过程中的收敛停滞现象， 同时提高的求解的速度。 将并行p s o 算法用于优化单个多层前向神经网络及集成的神经网络，实验结果表 明，并行的p s o 算法是有效的神经网络训练算法，用于解决实际的模式分类问题，不 仅提高了分类误差精度，而且：| j 【| 快收敛的速度，具有较好的加速比。采用神经网络并 行集成技术，能提高网络的泛化能力，与单个神经网络相比，进一步提高数据分类i 别能力。 1 3 课题研究的主要内容 本课题研究的主要内容有： 1 ) 本文主要研究了并行粒子群优化算法，该算法对单个种群采用了m a s t e r s l a v e 及 2 s p m d 并行编程模式，主进程主要完成种群随机初始化、任务的分发和根据适应值进 行粒子的选择，从进程主要完成粒子适应值的计算。 2 ) 采用并行的粒子群优化算法训练单个多层前向神经网络。粒子群中的每一个粒子 的分量映射为神经网络中的一组不同权值。在曙光天潮t c 3 0 0 0 服务器上，利用 m p i c h 并行环境设计实现了该算法，主要采用m p i c h 提供的点对点通信以及群集通 信的功能实现进程问的通信，由于各个进程的计算能力相当，采用块分配方案实现任 务的分发。 3 ) 采用神经网络集成技术，通过并行的训练多个神经网络并将这些不同网络结构的 个体神经网络进行集成。其中个体神经网络，其输入神经元个数和输出神经元个数采 用相同的数目，训练和测试样本也采用相同的样本，不同的是其隐含层神经元的数目。 并行的对每个个体神经网络进行训练和测试，然后将个体神经网络进行集成，集成的 结果采用简单平均法和加权平均法。采用加权平均方法其权值的优化仍然采用并行 p s o 算法。 4 ) 针对入侵检测数据及b r e a s tc a n c e r 模式分类数据进行检测。 5 ) 分析并行算法的时间复杂度以及并行算法的加速比，研究并行算法的执行效率。 3 摧于并行p s o 的模【l = 分类算法及j 应用研究 2 1 引言 第二章串行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 ) 5 7 1 算法是由k e n n e d y 和e b e r h a r t 博士于1 9 9 5 年提出的一种随机全局优化算法。p s o 算法不是依靠个体的自然进化规 律，而是对整个生物群体的社会行为进行模拟，它最早源于对鸟群捕食行为的研究。 在生物群体中存在着个体与个体、个体与群体间的相互作用、相互影响的行为，这种 行为体现的是一种存在于生物群体中的信息共享机制。p s o 算法就是对这种社会行 为的模拟，即利用信息共享机制，使得个体间可以相互借鉴经验，从而促进整个群体 的发展。 p s o 算法和遗传算法( g e n e t i ca l g o r i t h m ，g a ) 类似，也是一种基于迭代的优化 工具，系统初始化为一组随机解，通过某种方式迭代寻找最优解。但p s o 没有g a 的 “选择”、“交叉”、“变异”算子，编码方式也较g a 简单。由于p s o 算法容易理解、 易于实现，所以p s o 算法发展很快，在函数优化、模糊系统控制、神经网络训练、 工业系统优化与控制以及其他遗传算法的应用领域得到广泛使用。目前已被“国际进 化计算会议”( i e e ei n t e r n a t i o n a lc o n f e r e n c e so ne v o l u t i o n a r yc o m p u t a t i o n ，c e c ) 列 为一个讨论的专题。 2 2p s o 算法原理 自然界中的些生物的行为特征呈现群体特征，可以用简单的几条规则将这种群 体行为( s w a r m b e h a v i o r ) 在计算机中建模，实际上就是在计算机中用简单的几条规 则来建立个体的运动模型，但是这个群体的行为可能很复杂。例如，r e y n o l d s 使用了 下列三个规则作为简单的行为规r a , j t l 4 】： 1 ) 向背离最近的同伴的方向运动； 2 ) 向目的运动； 3 1 向群体的中心运动。 这即是著名的b o i d ( b i r d o i d ) 模型。在这个群体中每个个体的运动都遵循这三 4 条规则，通过这个模型来模拟整个群体的运动。p s o 算法的基本概念也是如此。p s o 算法源于对鸟群捕食行为的研究，研究者发现鸟群在飞行过程中经常会突然改变方 向，其行为不可预测，但其整体总保持一致性，个体与个体问也保持着最适宜的距离。 通过对类似生物群体的行为的研究，发现生物群体中存在着一种社会信息共享机制， 它为群体的进化提供了一种优势，这就是p s o 算法形成的基础。 假设这样一个场景：一群鸟在随机搜索食物，在这个区域里只有一块食物，所有 的鸟都不知道食物在那早，但是他们知道当前的位置离食物还有多远，那么找到食物 的最优策略是什么呢? 最简单有效的方法就是搜寻目前离食物最近的鸟的周围区域。 p s o 算法就是从这种生物种群行为特性中得到启发并用于求解优化问题。在p s o 算法中，每个优化问题的潜在解都可以想象成d 维空间上的一个点，我们称之为“粒 子”( p a r t i c l e ) 。粒子在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经 验和同伴的飞行经验来动态调整。所有的粒子都有一个被优化的函数决定的适应值 ( f i t n e s sv a l u e ) ，粒子在飞行过程所经历过的最好位置，就是粒子本身找到的晟优解， 称为个体极值( p b e s t ) ，这个可以看作是粒子自己的飞行经验。除此之外，每个粒子 还知道目前为止整个种群中所有粒子发现的最好位置，称为全局极值( g b e s t ) ，这个 可以看作是粒子同伴的飞行经验。每个粒子都通过上述两个极值不断更新自己，从而 产生新一代群体。实际操作中通过由优化问题所决定的适应值( f i t n e s sv a l u e ) 来评价 粒子的“好坏”程度。显然，每个粒子的行为就是种群追随着当前的最优粒子在解空 间中搜索。 2 3p s o 算法的数学描述 假设在一个n 维的目标搜索空间中，有m 个粒子组成一个种群，其中第i 个粒子 表示为一个n 维的空间向量x ：= ( x ：，x l ，x ：) ，其中i = l ，2 ，3 ，m ，即第i 个粒子在n 维搜索空问中的位置是x ：。每个粒子的位置就是一个潜在的解。将x ：代入一个目标 函数f ( x ) 可以计算出其适应值f ：，根据适应值f ：的大小衡量x i 的优劣。第i 个粒子的 “飞翔”速度也是一个n 维的向量，记为v i = ( v ；，v ，v ：) ，第i 个粒子目前搜索到的 晟优位置为p ：；( p ：，p ，p ：) ，整个粒子群目前搜索到的最优位置为p l = ( 吨硝，残) 。 挂本的p s 0 算法采用下列公式【l l 】川对粒子进行操作： 基于并行p s o 的模式分类算法驶) # 应用研究 v ：“- wk v ：+ c i h ( p ：一x ：) + c 2 r 2 ( p 2 一x ：) ； ( 1 ) x ：r x ：+ v o ( 2 ) 其中w 。称为惯性因子，为非负数。c 和c ：称为学习因子，通常为2 。r 和r ：是介 于 o ，1 之间的随机数。 公式( 1 ) ( 2 ) 所表述的速度进化方程由三部分组成，第一部分是粒子先前的速 度，表示粒子目前的状态；第二部分是“认知部分”( c o g n i t i v em o d a l ) ，表示粒子本 身的思考，来源于粒子自身的经验；第三部分为“社会部分”( s o c i a lm o d a l ) ，表示 粒子间的社会信息共享，粒子通过自己的经验和同伴中最好的经验来决定下一步的运 动。三个部分共同决定了粒子的空问搜索能力，第一部分起到了平衡全局和局部搜 索的能力；第二部分使粒子有了足够强的全局搜索能力，避免局部极小；第三部分体 现了粒子间的信息共享。在这三部的共同作用下粒子才能有效的到达最好位置。 另外，粒子在不断根据速度调整自己的位置时，还要受到最大速度v 。的限制， 当v ：超过v m 。，时将被限定为v 。 迭代的终止条件根据具体问题的一般选为最大迭代次数或种群目前位置搜索到 的最优位置满足预定最小适应阈值。 2 4 p s 0 算法流程 公式( 1 ) 是根据粒子以前的速度和粒子现在位置与自己曾经最好的位置之间的 距离及当前位置和群体最好位置之间的距离三者的和，来计算粒子新的速度。粒子根 据公式( 2 ) 移动到一个新位置上。每个粒子的优劣程度根据己定义好的适应值函数 柬评价，适应值函数的选择与被解决的问题有关。下面给出p s o 算法的算法流程： 初始化粒子群，包括种群规模，每个粒子的位置x ：和速度v ：； 计算每个粒子的适应值f ：； 对每个粒子，将其的适应值f ：和个体极值p ：比较，若较好，则替换p ：； 对每个粒子，将其的适应值f ：和全局极值p ：比较，如果较好，则替换p l ； 根据公式( 1 ) 、( 2 ) 更新每个粒子的速度和位置： 如果满足结束条件退出。否则回至4 。 算法的伪代码如下： 6 f o re a c h p a r t i c l e i n i t i a l i z ep a r t i c l e e n d d o j o r e a c hp a r t i c l e c a l c u l a t e f i t n e s sv a l u e i f t h ef i t n e s sv a l u ei sb e t t e rt h a nt h eb e s tf i t n e s sv a l u e ( p b e s t ) e n d s e tc u r r e n tv a l u ea st h en e w p b e s t c h o o s et h ep a r t i c l ew i t ht h eb e s tf i t n e s sv a l u eo fa l lt h ep a r t i c l e sa st h eg b e s t f o re a c hp a r t i c l e c a l c u l a t ep a r t i c l ev e l o c i t ya c c o r d i n ge q u a t i o n ( 1 ) u p d a t ep a r t i c l ep o s i t i o na c c o r d i n ge q u a t i o n ( 2 ) e n d w h i l em a x i m u mi t e r a t i o n so rm i n i m u me r r o rc r i t e r i ai sn o ta t t a i n e d 2 5 参数设置 2 5 1 惯性权重 惯性权重w 是用来控制粒子以前速度对当前速度的影响，它将影响粒子的全局 和局部搜索能力，使粒子保持运动惯性，具有扩展搜索空间，探索新区域的能力。w 越大，粒子的飞行速度越大，粒子将以较大的步长进行全局搜索；w 较小，粒子的 飞行速度越小，粒子将趋向于精细的局部搜索。选择一个合适的w 可以平衡全局和 局部搜索能力，这样可以以最少的迭代次数找到最优解。s h i 与e b e r h a r t l l 5 1 等人经过 实验发现，当w 【0 8 ，1 2 】之间时有较好的性能。另外，在搜索过程中可以对w 进行 动态调整：在算法开始时，可以给w 赋予一较大正值，随着搜索的进行，可以线性 的使w 逐渐减小，这样可以保证在算法丌始时，每个粒子都能够以较大的速度步长 在全局范围内搜索到较好的种子；而在搜索的后期，较小的w 值则保证粒子能够在 极点周围做精细的搜索，从而使算法有较大的几率以一定精度收敛于全局最优解。 2 5 2 学习因子 c ，、c 2 用来控制粒子自身的记忆和同伴的记忆之间相对影响。c 。反映了粒子飞行 过程中所记忆的最好位置对粒子飞行速度的影响，被称为“认知系数”；c 2 则反映了 7 基于并行p s o 的模式分类算法及其应用研究 整个种群所记忆的最好位置对粒子飞行速度的影响，被称为“社会学习参数”。合适 的选择可以提高算法速度、避免局部极小。在文献【1 6 】中认为c ，= c 2 - - 2 是最好的选择， 但实验也说明了c l = c 2 = 0 5 也能得到好的结果。在文献【1 7 】中指出，经过大量的实验结 果对比，指出c 。+ c 2 一4 较好。 2 5 3 最大速度 一般来说，v 。的选择不应超过的粒子宽度范围，如果v 。太大。粒子可能飞过 最优解的位置；如果v 。太小，无论w 如何取值，算法总是趋向于局部搜索。 2 5 4 种群规模和粒子的维数 种群规模一般取2 0 4 0 个粒子，对于大部分问题1 0 个粒子就可以取得较好的效 果。当然一些特殊问题可取的更多，如对多目标优化等比较难的问题，或者某些特定 的问题，粒子数可以取到1 0 0 - 2 0 0 个。粒子的维数是由优化问题所决定的，即问题解 的长度。在并行p s o 算法中，我们根据实际求解问题的难易程度，选取种群数目为 2 0 1 0 0 粒子。 2 6 与其它进化计算的比较 p s o 算法和其它的进化计算p q p 8 】技术基本上是一致的，过程如下： 1 1 种群随机初始化； 2 1 对种群内的每一个个体计算适应值( f i t n e s s ) ； 3 、种群根据适应值进行复制； 4 1 如果终止条件满足的话，就停止，否则转步骤2 ) 。 p s o 算法和遗传算法相比，有很多共同之处【3 3 】。两者都是随机初始化种群，都 使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。p s o 算法采用 “速度一位移”模型，操作简单，没有g a 算法的“选择”、“交叉”、“变异”等遗传 操作，而是根据粒子自身的速度变化动态跟踪当前搜索情况调整其搜索策略。k e n n e d y 和e b e r h a r t 认为p s o 算法应该是介于遗传算法和进化规划间的一种算法。在编码 方式上p s o 算法也较其它的算法简单，可以直接根据被优化的问题进行实数编码。 8 g a 算法和p s o 算法的信息共享机制也是不同的。在g a 算法中，染色体之间互相共 享信息，所阻整个种群的移动是比较均匀的向最优区域移动的。在p s o 算法中，所 有粒子共享全局极值( g b e s t ) ，属于单向的信息流动，整个搜索更新过程跟随当前最 优解的搜索过程，所以整个种群的移动是不均匀的。与g a 算法相比，p s o 算法在大 多数情况下能更快的找到最优解。 2 7p s o 算法应用领域 目前已经有一些利用p s o 算法代替反向传播算法来训练神经网络的研究，研究 表明p s o 算法是一种很有潜力的神经元网络训练算法【3 2 1 。p s o 算法速度比较快而且 可以得到比较好的结果，而且没有遗传算法碰到的问题【”】。p s o 算法被用于优化b p 神经元网络的权值【。用p s o 算法进化神经网络的一个成功的例子是用于分析人的 颤抖，包括帕金