（计算机应用技术专业论文）粒子群算法的硬件实现及性能分析.pdf

摘要 摘要 量子粒子群算法( q u a n t u m b e h a v e dp 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 ，q 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 na l g o r i t h m ，p s o ) 的基础上改进而来，是一种 有效的全局优化搜索算法，它比较好地改进了p s o 算法的自身缺陷，提高了全局优化搜 索效率。 在现代的科研诸多领域中人们对算法的速度要求越来越高，所以有更多的算法被用 硬件实现来增加实时性。f p g a ( f i e l d p r o g r a m m a b l e g a t e a r r a y ) 较之以前的c p l d 、p a l 有很多优点，用它作为硬件平台，弥补了传统a s i c 灵活性不足的缺点。 本文首先介绍了粒子群算法的基本原理，研究了q p s o 算法的粒子间的特性，另外 本实验选择f p g a 作为硬件平台，结合了f p g a 的硬件架构和q p s o 的特性对算法进行硬 件结构设计。在结构设计当中加入了并行流水技术，这是在f p g a 开发中的一个优点， 从而进一步提高了算法的运行效率。在实验中，通过对不同的函数进行实验比较，同时 使用不同的硬件方式串行和并行来实现，从多个方面来比较算法的运行效率并做了 相应的分析。通过实验表明，硬件实现的o p s o 算法的运行效率显著提高。 为了能更好地说明硬件实现该算法的运行效果，本文也做了在相同条件下的q p s o 算法在m a t l a b 中的实现，然后比较它们的运行效果。通过采用硬件并行和流水技术， 大大缩短了算法的运算时间，仿真结果表明硬件化o p s o 算法的运算时间甚至达到原 m a l l a b 中运算时间的0 0 3 2 。 最后，在程序综合、实现、配置成功后，分别采用j t a g 和主串两种模式下载到x i l i n x 公司的s p a r t a n - 3x c 3 s 4 0 0 型号f p g a 开发板中，并且运行成功，测试结果与仿真结果 相同。 关键词：量子粒子群算法，硬件实现，并行流水，可编程逻辑器件，v e r il o gh d l ， a b s t r a c t q u a n t u m b e h a v e dp 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 ( q p s o ) i s an e w i m p r o v e d a r i t h m e t i co fp 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 ( p s o ) ，w h i c hi se f f e c t i v ea n do p t i m i z e d ， i ta m e l i o r a t e s 也eb u go fp s op r e f e r a b l y ，i m p r o v e st h es e a r c he f f i c i e n c y i nt h em o d e ms c i e n c er e s e a r c hf i e l d s ，p e o p l ea l w a y sw a n tt og e tm o r ea n dm o r es p e e do f a l g o r i t h m s ol o t so fa l g o r i t h m si m p l e m e n t e db yh a r d w a r et oi n c r e a s er e a lt i m e f p g a ( f i e l d p r o g r a m m a b l e g a t e a r r a y ) h a v em a n ya d v a n t a g e sc o m p a r ew i t hc p l d o rp a l ，u s ef p g aa s t h eh a r d w a r ef l a tr o o f , m a k eu pf o rb a d a g i l i t yo f a s i c t h i sp a p e ri n t r o d u c e st h ef u n d a m e n t a lo fp s of i r s t ，r e s e a r c h e st h ep a r t i c l es p e c i a l i t yo f q p s o ，b e s i d e s ，t h eh a r d w a r ef l a tr o o fi sf p g a ，s oa f t e ri n t r o d u c i n gt h eh a r d w a r ef r a m eo f f p g a ，a n dc o m b i n i n gw i t hs p e c i a l i t yo fq p s ot od e s i g nt h eh a r d w a r ef r a m e ，u s i n gt h e p i p e l i n i n gt e c h n o l o g yw h i c hi sas t r o n g p o i n t o ff p g ad e v e l o p i n g ，a n dt h e ni m p r o v i n gt h er u n e f f i c i e n c yg r e a t l y i nt l l el a b ，f r o mt h ed i f f e r e n tf u n c t i o n s c o m p a r i n ga n dt w od i f f e r e n t h a r d w a r ei m p l e m e n tm o d e - - s t r a n da n dp a r a l l e la n dm a k es o m er e l e v a n ta n a l y s i s ，t h e r e b y , w e c a l lg e tt 1 1 ea l g o r i t h m slu l le f f i c i e n c yf r o mm a n yw a y s d u r i n gt h ei m p l e m e n t i n go fs y s t e m c o d e s ，u s e dt h eh a r d w a r ed e s c r i p t i o nl a n g u a g e - v e r i l o gh d l ，w h i c hi sv e r yp o p u l a r c u r r e n t l y , a f t e ri m p l e m e n to fc o d e s ，f r o mt h er e s u l to fr u n n i n gi nm o d e l s i m w ec a nf i n dt h e r e s u l ti sr i g h ta n dt h ee f f i c i e n c yi m p r o v e dg r e a t l y i no r d e rt op r o v et h ee f f e c to ft h i sa l g o r i t h mi m p l e m e n to nh a r d w a r e ，t h i sp a p e ra l s o m a k e so u tt h eq p s oo nm a t l a bi nt h es a m ec o n d i t i o n s ，f r o mt h er e s u l to fc o m p a r ep r o v i n g t h a te f f e c ti sg o o d w i t ht h ep i p e l i n et e c h n o l o g ys h o r t e n st h er u n t i m ee n o r m o u s l y 。r h e s i m u l a t er e s u l ti n d i c a t e st h a tr u n t i m eo ff p g a b a s e dq p s oa c h i e v e sa b o u t0 0 3 2p e r c e n to f r u n t i m eo nm a t l a b a tl a s t ，a f t e rs y n t h e s i s ，i m p l e m e n ta n dc o n f i g u r es u c c e s s f u l l y ，d o w n l o a dt h es p a r t a n - 3 x c 3s 4 0 0f p g aw h i c hp r o d u c e si nx i l xc o m p a n yu s i n gj t a ga n dm a s t e rs e r i a lm o d e s a n dr u ns u c c e s s f u l l y , t h er e s u l ti sa ss a m ea ss i m u l a t i o n k e y w o r d s ：q p s o ，h a r d w a r ei m p l e m e n t ，p i p e l i n i n gt e c h n o l o g y , p l d ，v e r i l o gh d l i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南 大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规定： 江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文， 并且本人电子文档的内容和纸质论文的内容相一致 保密的学位论文在解密后也遵守此规定 签名： 导师签名：2ij 陂 日 期：珥! 显华 第一章绪论 第一章绪论 1 1 硬件加速的现状与趋势 硬件加速是指利用硬件模块来替代软件算法以充分利用硬件所固有的快速特性。从 软件的角度看，与硬件加速模块接口就跟调用一个函数一样。 当设计者试图从算法中获得最佳性能但软件方法已无计可施时，可以尝试通过硬件 软件重新划分来进行加速。f p g a 一一( f i e l dp r o g r a m m a b l eg a t ea r r a y ) 易于实现软 件模块和硬件模块的相互交换，且不必改变处理器或进行板级变动。低成本可编程逻辑 在嵌入式系统中应用得越来越普遍，这为系统设计者提供了一个无需对处理器或架构进 行大的改动即可获得更高性能的可选方案。可编程逻辑可将计算密集型功能转换为硬件 加速功能。从软件的角度看，这只是简单地将一个函数调用做进一个定制的硬件模块中， 但运行速度要比通过软件平台实现的快得多。 使用可编程器件( p l d ) 来进行硬件加速是人们越来越多的选择，作为一种2 0 世 纪7 0 年代才发展起来的新技术产品，尽管其发展历程很短，但由于其具有静态可重复 编程、动态在系统重构和设计方便的特点，到目前已得到了广泛的应用。但由于技术发 展和用户需求的提高，也要求p l d 无论在结构、工艺、集成度方面，还是在功能、速 度和灵活性方面都要有较大的提高和改进。但是在飞速发展的信息化时代，数字化、智 能化设计已经变得愈来愈普及，产品的更新换代不断加快，传统的单一功能的集成电路 设计技术已经无法满足性能日益提高的整机系统的要求。而f p g a 是一种可编程逻辑器 件一( f i e l dp r o g r a m m a b l eg a t ea r r a y ) 。它是在p a l 、g a l 等逻辑器件的基础上发展起 来的，相比于它们，f p g a 的规模更大，同时具有多种自身的特性。使用f p g a 作为硬 件加速平台，突破了传统的定义，由单纯和简单的门电路向着更灵活、更高性能、更低 成本、平台化、可定制等系统级解决方案的方向发展。 目前已经有很多常用的算法在尝试使用硬件来实现，而且都获得了非常好的效果， 如w i l l i a mn c h e i t o n ，m o h a m m e db e n a i s s a 的“f a s te l l i p t i cc u r v ec r y p t o g r a p h yo nf p g a 2 1 ， ( 椭圆曲线密码加密算法的硬件f p g a 实现) ，该论文中使用了并行流水架构和改进的 一并行乘法器来实现椭圆曲线密码加密算法，从而更加提高了运行效率。文中通过使用改 进的乘法器进行算法设计，极大地提高了运行效率，还在不同的硬件平台上做了运行时 间和资源消耗的对比。在国内也有相似的研究，如在文献【3 】中，作者研究了并行遗传算 法的f p g a 硬件实现，该论文中提出基于f p g a 的并行遗传算法的硬件实现系统，从硬 件实现角度提高遗传算法的收敛速度。硬件系统划分4 个子系统，每个子系统同步而单 独地运行一个群体大小为m 的简单遗传算法，在简单遗传算法每代结束时，总控制器 从4 个子系统中选取1 个最佳个体，然后复制到与其物理相邻的2 个子系统中，实现子 系统之间的信息交换。每个子系统采用5 段流水线处理技术。实验数据表明，由f p g a 硬件实现的并行遗传算法同由软件实现的遗传算法相比，收敛速度大幅度提高，约2 个 数量级。在文献【4 】中，用f p g a 实现了s o m 神经网络算法，该文提出了一种实现该算 江南大学硕士学位论文 法的高并行体系结构并给出了该体系结构中关键模块的具体实现电路，通过并行实现的 硬件加速来提高算法的效率。粒子群算法在国内外的研究中都占有很重要的地位，很多 学者和研究人员都尝试尽可能地改进粒子群算法的性能，但都以改进算法的本身性能为 主，若能以硬件来实现该算法，像上述文献中所提到的那样，用硬件的方式来提高算法 的运行效率，将进一步促进粒子群算法在各个领域中的应用。 对于f p g a 的应用，国内外都发展的很快，尤其在国外，基于其优异的性能，已经 将f p g a 应用到了高科技领域中。作为美国国家航空航天局( n a s a ) 哈勃望远镜的下 一代后继设备，韦伯空间望远镜( t h ej a m e sw 色b bs p a c et e l e s c o p e ，j w s t ) 基于 n il a b v i e wf p g a 技术，顺利通过了2 0 1 3 年发射前的重要测试关卡。j w s t 的一个重 要元素是近红外线声谱仪( n e a r i n f r a r e ds p e c t r o g r a p h ，n i r s p e c ) ，该装置具备了超过 2 5 0 ，0 0 0 个微型快门来帮助人们更好地观察成千上万的遥远星系，以更好地认识宇宙起 源。这些微型快门实际上是微电机系统装置( m i c r o e l e c t r o m e c h a n i c a ls y s t e m ，m e m s ) ，其 作用类似于照相机的快门，是用于控制曝光量的。n a s a 戈达德空间飞行中心 ( n a s ag o d d a r ds p a c ef l i g h tc e n t e r ) 的工程师在实验室里成功地运用l a b v i e wf p g a 来 控制和测试这些微型快门。 1 2 嵌入式系统的发展趋势 嵌入式系统起源于微型机时代，但很快就进入到独立发展的单片机时代。在这个时 代，以电子技术应用工程师为主体，实现传统电子系统的智能化，而计算机专业队伍并 没有真正进入单片机应用领域，虽然如此，但随着后p c 时代的到来，网络、通信技术 得以发展。同时，嵌入式系统软件、硬件技术有了很大的提升，为计算机专业人员介入 嵌入系统应用开辟了广阔的天地。以信息家电为代表的互联网时代嵌入式产品，不仅为 嵌入式市场展现了美好前景，注入了新的生命；同时也对嵌入式系统技术，特别是软件 技术提出了新的挑战。这主要包括：支持日趋增长的功能密度、灵活的网络连接，以及 轻便的移动应用和多媒体的信息处理。因此，未来的嵌入式系统会体现出以下趋势p 1 。 第一，由于片上系统( s o c ，s y s t e mo nc h i p ) 具有集成度高、体积小、功耗低、 结构简单、可靠性高等特点，极大地满足各行业的要求，因此，s o c 将是嵌入式系统硬 件的主流发展趋势。 第二，连网成为嵌入式系统发展的必然趋势。为适应嵌入式分布处理结构和应用上 网需求，面向2 1 世纪的嵌入式统要求配备标准的一种或多种网络通信接口。 第三，嵌入式系统要嵌入到小型电子设备中，实现小尺寸、微功耗和低成本。为满 足这些特性，要求嵌入式主品设计者相应降低处理器的性能，限制内存容量和复用接口 芯片。 第四，嵌入式系统要提供精巧的多媒体人机界面。嵌入式设备之所以为亿万用户乐 于接受，重要原因之一是它们与使用者之间的亲和力、自然的人机交互界面，使其能与 用户方便、简单的使用。 2 第一章绪论 作为嵌入式系统的主要形式的s o c 来说，是将大规模的数字逻辑和嵌入式处理器整 合在单个芯片上，集合模拟部件，形成模数混合、软件硬件结合的完整的控制和处理片 上系统。但是要实现s o c ，需要相对较长的开发周期和高昂的开发费用，并且涉及到大 量集成电路后端设计和微电子技术的专门知识，存在着十分困难的门槛，美国a l t e r a 公 司2 0 0 0 年提出的s o p c ( s y s t e mo np r o g r a m m a b l ec h i p ，片上可编程系统) 技术则提供了 另一种有效的解决方案，即用大规模可编程器件的f p g a 来实现s o c 的功能。s p o c 是s o c 发展的新阶段，代表了当今电子设计的发展方向。 随着百万门级的f p g a 芯片、功能复杂的i p 核、可重构的嵌入式处理器核以及各种 功能强大的开发工具的出现，s o p c 已成为一种普遍流行且易于实现的设计方法。用f p g a 来实现s o p c 的方式一般有如下几种： 1 、基于f p g a 嵌入i p ( i n t e l l e c t u a lp r o p e r t y ) 硬核的s o p c 系统。比如有含有 a r m 的3 2 位知识产权处理器核的器件；x i l i n x 的v i r t e x - l lp r o 系列中则植入了i b m p o w e p c 4 0 5 处理器。 2 、基于f p g a 嵌入i p 软核的s o p c 系统。由于硬核的结构不能改变，功能也相对固 定，无法裁减硬件资源，但是软核嵌入式系统处理器就可以有效地克服上述不利因素。 如x i l i n x 的p i c o b l a z e 等软核处理器。 3 、基于h a r d c o p y 技术的s o p c 系统。h a r d c o p y 就是利用原有的f p g a 开发工具，将 成功实现于f p g a 器件上的s o p c 系统通过特定的技术直接向a s i c 转化，从而克服传统 a s i c 设计中普遍存在的问题。 1 3 处理系统实时性介绍 从在指定时间内完成任务的严重程度划分，实时系统1 可以分为“硬实时系统和 “软”实时系统。“硬 实时系统包括比如航天器控制、核反应堆控制、化学电力工厂 控制等等，对这类系统来说，如果在指定时间内无法完成既定任务，将有可能导致严重 后果：“软 实时系统包括多媒体编解码器、实时媒体传输系统等，这类系统如果在指 定时间内无法完成既定任务，会引起性能的下降或信息的丢失，但是不会造成严重的后 果嗍。 随着后p c 时代以及网络、通信技术时代的到来，信息化不断加强，大量的计算机 专业人员进入了嵌入式应用领域；然而，有大量的嵌入式系统应用是以单片机的形式， 应用在传统的电子技术领域中。因此，以计算机领域人员为主体的，远离对象系统的嵌 入式系统的计算机工程应用模式，和以电子技术领域人员为主体，与对象系统紧耦合的 电子技术应用模式产生了概念上的碰撞。以前的“嵌入式系统概念是其一，而今“嵌 入式系统的实时性 又是一个现在人们不断关注的焦点。 任何一个电子系统都可看成是个激励一响应系统。每个特定的电子系统都有一个 从激励输入到响应输出的时间，即激励一响应周期t ，它表现为系统的响应能力。如果系 统的响应能力t 能满足嵌入对象所规定的响应时间t a 要求，即t t a ，这个系统便是实 3 江南大学硕士学位论文 时的电子系统。应用于不同对象的系统有不同的实时性，它是根据用户或生产的需要来 设计的，每个系统都有自己的实时性，只是有些系统的实时性太差，我们就并不把它们 看成是真正的实时系统。按不同的激励一响应时间t 的特点，可以将电子系统分为经典 电子系统、通用计算机系统与嵌入式系统，来讨论不同类型的电子应用系统不同的实时 性特点。 1 、经典电子系统：不含计算机的纯电子电路系统，例如，测量放大器、电子计数 器、温度指示器( 由a d c 、译码器、l e d 显示器构成) 等，电路的动态特性决定了系统响 应能力t 的大小。经典电子系统是一个激励一响应系统，从激励到响应的时间完全取决 于电子在电路中的运动过程，因而，它具有极短的、相对固定不变的，从激励到响应的 时间周期t 。在大多数经典电子应用系统中，由电路的动态特性决定了t 值的大小。一 般情况下，应用系统的t 远小于嵌入对象系统的响应( t a ) 要求，因此，在经典电子应 用领域中，应用工程师的头脑中没有“实时性”名词的概念，而对一些极快速响应要求 的应用系统，如振动测量系统，它的实时性要求常常反映为电路系统的“频率响应 要 求。 2 、通用计算机系统：是一个人机交互的激励一运行一响应系统。它的激励一响应时 间t 表现为电路系统的激励一响应时间t c 与软件运行时间t s ，而电路系统的激励一响应 时间与软件运行时间相比为高阶小量，因而软件运行时间形成了t 的主要成份， t = t c + t s t s 。由于通用计算机系统只使用在人机交互环境中，对象( 人) 提出的响应 时间t a 要求，只是一个期望值( 尽量快) ，而这种欲望一方面表现为永无止尽，另一方 面又表现出现实的可容忍性。因此，通用计算机系统是一个非实时的电子系统，而快速 性成为通用计算机系统发展的永恒主题。 3 、 嵌入式系统：由于计算机的嵌入，嵌入式系统也是一个激励一运行一响应的电子 系统。但是，它与嵌入对象交互，与嵌入对象的事件过程相关，在与嵌入对象体系交互 时，要满足事件交互过程的响应要求。这种嵌入系统可以使用f p g a 等纯硬件解决方案， 能对实时多任务有很强的支持能力，能完成多任务并且有较短的中断响应时间，但是在 嵌入式应用系统的具体设计中，必须考虑系统中每一个任务运行时，能否满足t s t a 的要求，这就是嵌入式系统的实时性问题。 综上所述，经典电子系统应用中，没有显示出实时性的概念，是因为电子系统的激 励一响应时间t 极短，绝大多数电子系统都能满足t t a 要求；通用计算机系统应用中， 没有实时性概念，是因为t a 只有期望要求；而嵌入式系统应用中，必须考虑实时性问 题，是因为软件运行的时间耗费t s ，会使系统的激励一响应时间t 巨额增加，而不能满 足嵌入对象系统提出的响应时间t a 要求，凸现了嵌入式系统的实时性问题。 1 4 课题的来源目的与意义 粒子群算法( p s o ) 阻1 是一种新的进化算法，但其本身存在缺陷，人们在它的基 础上研究出了许多优化的算法，q p s o 1 1 ，1 2 3 就是一种结合量子理论的新的粒子群算法， 4 第章绪论 它改进了粒子群算法的全局优化能力。虽然算法是越来越完善了，但是通过软件获得的 算法速度却不能满足人们的需求，如q p s o 这种基于随机搜索的优化算法，当遇到大规 模的问题时，速度瓶颈会显得尤为突出。针对此问题，在前面的工作n 3 1 中，本研究组已 经采用串行方式实现了q p s o 的硬件加速，取得了较好的效果，本文采用提高硬件并行 计算能力的手段，进一步提高q p s o 算法的运算速度。 在科研和日常生活的诸多领域中经常需要用到一些优化算法，影响优化算法实用性 的一个重要因素是其运算速度，为了提高算法的运算速度，越来越多的算法被用硬件来 实现，f p g a 拥有开发周期短、可编程能力强、设计灵活等多种优点，常被用来作为算法 硬件实现的平台，所以，对粒子群算法的硬件加速的研究有重要意义。 1 5 本论文研究的方法与内容 本论文的研究方法是首先根据q p s o 算法的特性和硬件平台f p g a 的特点来进行系统 设计，在设计的过程中采用并行流水技术来对算法进行改进，再用硬件描述语言v e r i l o g h d l u 怕。分别实现并行q p s o 和串行q p s o ，将它们的运行结果进行比较。另外还与在软件 中( m a t l a b ) 引的运行结果比较，从而在不同方面来得出并行硬件实现的o p s o 算法的最 后效果。最后还要经过对系统编码的综合、实现、下载等过程最终在f p g a 开发板上的 成功运行。 本论文的研究内容主要包括以下几点：1 ) 研究粒子群算法，包括q p s o 算法的研究， 分析其适合使用f p g a 实现的特性。2 ) 结合q p s o 算法的粒子特性和f p g a 的硬件特点， 提出了它的硬件实现的架构，使用整个群体的分群并行方式来设计。3 ) 算法编码的实 现。对算法进行模块划分，采用了硬件描述语言和自顶向下的数字系统设计方法来实现 算法描述，在仿真工具m o d e l s i m 上运行查看结果。4 ) 在m a t l a b 中实现在相同条件下 q p s o 算法，与硬件实现的q p s o 算法进行比较，通过设计的几种不同的函数和不同的硬 件实现方式等方面进行比较分析，检验其功能并讨论相关数据。5 ) 综合、实现、下载、 运行。最后本实验使用x i l i n x 公司的开发板，根据本开发板的特性和程序的要求，通 过专用集成工具i s e 将程序下载到开发板中。 5 江南大学硕士学位论文 第二章粒子群算法介绍 2 1 粒子群算法 1 、p s o 算法介绍 群体智能( s w a r mi n t e l l i g e n c e ，s i ) 的概念源于对蜜蜂、蚂蚁、大雁等群居生物 群体行为的观察和研究。通常将这样一种模拟群居性生物中的集体智能行为的智能计算 或优化方法称为群体智能。严格地讲，群体智能是一种在自然界生物群体所表现出的智 能现象启发下提出的人工智能模式，是对简单生物群体的智能涌现现象的具体模式研 究，即“简单智能的主体通过合作表现出复杂智能行为的特性 。目前，对群体智能的 研究尚处于初级阶段，但是它越来越受到国际智能计算研究领域学者的关注，逐渐成为 一个新的重要的研究方向。 粒子群算法也是一种群体智能算法，受鸟群运动模型的影响，美国社会心理学博士 j a m e sk e n n e d y 和电子工程学博士r u s s e l le b e r 2 h a r t 于1 9 9 5 年提出了粒子群算法。粒 子群算法是一种演化计算技术，该算法中将鸟群运动模型中的栖息地类比于所求问题解 空间中可能解的位置，通过个体间的信息传递，导引整个群体向可能解的方向移动，在 求解过程中逐步增加发现较好解的可能性。与进化算法相比，p s o 保留了基于种群的全 局搜索策略，但其采用的速度、位移模型操作简单，避免了复杂的遗传操作，是一种更 高效的随机搜索算法n7 1 9 1 。 经典粒子群算法的基本思想是模拟鸟类群体行为，即源于对鸟群捕食行为的研究， 一群鸟在随机搜寻食物，如果这个区域里只有一块食物，那么找到食物的最简单有效的 策略就是搜寻目前离食物最近的鸟的周围区域。p s o 算法就是从这种模型中得到启示而 产生的，并用于解决优化问题，这就构成了p s o 的一个基本概念。该算法由于运算速度 快，局部搜索能力强，参数设置简单，近些年已收到学术界的广泛重视，现在其应用领 域已扩展到多目标优化、数据分类、数据聚类、模式识别、路由计算、生物系统建模、 流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，但该算法的 全局搜索能力不强，易于陷入局部最优解。 经典粒子群算法和其他的进化算法相似，也采用“群体”与“进化”的概念，同样 是根据个体即粒子( p a r t i c l e ) 的适应度大小进行操作。所不同的是，粒子群算法不像 遗传算法那样有复杂的遗传和交叉操作，也不像其他进化算法那样对个体使用进化算 子，而是将每个个体看作是在n 维搜索空间中的一个无重量无体积的粒子，并在搜索空 间中以一定的速度和方向飞行。该飞行速度是根据个体的飞行经验和群体的飞行经验来 进行动态地调整，将按照下面方向进行调整n 引： ( 1 ) 至今发现的每个粒子的最优位置。 ( 2 ) 粒子群的最优位置。 每个粒子包含以下信息： 置= g 儿，t 2 ，) 表示粒子f 的当前位置； 6 第二苹糙子群算法介缁 k = o n ，加) 表示粒子f 的当前飞行速度； 只= 0 n ，p m ，p 册) 表示粒子f 所经历过的具有最好适应度值的位置，称为 个体f 所经历的最佳位置( 又称局部最优点) 。 设f ( x ) 为需要最大化的目标函数，也就是要求取此目标函数的最大值，则粒子f 目 前的个体局部最优位置由下式确定： 州，= 艘+ 。雾嚣裂秽淼 亿， 其中厂( 置o + 1 ) ) 是根据目标函数得出的粒子f 的当前适应值。 设群体中的粒子数为s ，群体中所有粒子所经历过的最佳位置( r ) ，称为全局最佳 位置。也就是所有粒子个体最优值的最大值，则： 最( f ) r o ) ，异o ) ，b ( f ) ) i 厂( 名( f ) ) = m a x 扩( b ( ，”，厂( 置( f ) ) ，厂( b ( f ) ) ) ( 2 2 ) k e n n e d y 和e b e r h a r t 最早提出的p s o 算法的进化方程如下： 吻o + 1 ) = 屹o ) + c 1 木掌心 一嘞 ) + c 2 宰饧0 ) 木吧o ) 一( f ) ) ( 2 3 ) 勤o + 1 ) = 南( f ) + v o ( t + 1 ) ( 2 4 ) 其中下标“f 表示第f 个粒子，下标“j f 表示的是粒子f 的第维分量，t 表示 第f 代，学习因子q ，c ：为非负常数，q 用来调节粒子向本身最好位置飞行的步长，c ：用 来调节粒子向群体最好位置飞行的步长，通常c 。，c ：在【o ，2 】间取值。，l ，( f ) ，r 2 ，( f ) 是两个 介于【0 ，1 】之间的服从均匀分布的随机数，即：r u ( f ) u ( o ，1 ) ，r 2 ( f ) u ( o ，1 ) 。为了减少 在优化过程中，粒子飞出搜索空间的可能性，以) 通常限定在一定的范围内，即 【v 孟心双】。1 ，曲、，。缸是根据具体问题而人为设定的，同时人们也会根据具体问题， 限定搜索空间x ，【x m i n ) x 。瓠】。迭代终止条件根据具体问题一般选为最大迭代次数或粒 子群搜索到的最优位置满足于预先设定的精度。一般来讲，将经典粒子群算法的形式表 述如下： 巧( f + 1 ) = 形( f ) + qx ( p ( t ) 一x ，( f ) ) + c 2 r 2 ( 名( f ) 一x ，o ) ) ( 2 5 ) x ，o + 1 ) = x ，( r ) + 杉( f + 1 ) ( 2 6 ) 经典粒子群算法的算法流程如下： 1 ) 、依照如下初始化过程，对粒子群的随机位置和速度进行初始设定。 、设定群体规模，即粒子数为。 、对任意f ，随机产生在【x 。面，x 。戡】内服从均匀分布的。 、对任意f ，j f ，随机产生在 1 ，血，v 。瓤】内服从均匀分布的1 ，玎。 、对任意f 初始化局部最优位置为：只= 。 、初始化全局最优位置名为：f ( p g ) = m a x v ( x 。) ，f ( x ：) ，f ( x ) ) 。 2 ) 、根据目标函数，计算每个粒子的适应度值。 3 ) 、对于每个粒子，将其适应度值与其本身所经历过的最好位置只的适应度值进行 江南大学硕士学位论文 比较，如果更好，则将现在x 的位置作为新的只。 4 ) 、对每个粒子，将其经过的最好位置只的适应度值与群体的最好位置的适应度值 比较，如果更好，则将p 的位置作为新的全局最优值只。 5 ) 、根据等式( 2 5 ) 、( 2 6 ) 对粒子的速度和位置进行更替。 如未达到结束条件，通常为足够好的适应值或是达到一个预设的最大迭代代数，则 返回步骤2 ) 。 2 、其它改进的粒子群算法1 1 ) 、惯性权重( i n e r t i aw e i g h t ) 法 微粒群算法是一种局部搜索效率高的搜索算法，收敛快，特别是在算法的早期，但 也存在着精度较低，易发散等缺点。若加速系数、最大速度等参数太大，粒子群可能错 过最优解，算法不能收敛；而在收敛的情况下，由于所有的粒子都同时向最优解的方向 飞去，所以粒子趋向同一化，这样就使算法容易陷入局部最优解，即算法收敛到一定精 度时，无法继续优化，因此很多学者都致力于提高p s o 算法的性能。 y s h i 和e b e r h a r t 4 5 1 在1 9 9 8 年对微粒群算法引入了惯性权重w ( f ) ，并提出了在进化 过程中线性调整惯性权重的方法，来平衡全局和局部搜索的性能，该方程已被学者们称 为标准p s o 算法，其方程形式如下： k o + 1 ) = 以f ) 奉v ：f ( f ) + c l 木( f ) 幸( 弓( f ) 一嘞o ) ) + c 2 * r 2 j ( t ) 木( 乞( f ) 一x o ( t ) ) r 27 3 x u ( t + 1 ) 。( ，) + 吩( h 1 ) ( 2 8 ) 这里w 是惯性权重，c l 和c ：加速常数，r l , j ( ) ，r 2 ，j ( t ) u ( o ，1 ) ，并且七= 1 ，m 。 速度的计算以下面三个基值为基础：( 1 ) 其第一部分_ 为微粒先前的速度。( 2 ) 第二部分p b e s t j a , ( ) 为“认知”部分，因为它仅考虑了微粒自身的经验，是局部最优位 置。( 3 ) 第三部分g b e s t 【f ) 是“社会”部分，表示微粒间的社会信息共享，是全局最优 位置。 2 ) 、选择( s e l e c t i o n ) 法 a n g e l i n e 提出的混和p s o 主要应用p s o 的基本机制以及演化计算所采用的自然选 择机制。由于p s o 搜索过程依赖p b e s t 和g b e s t ，所以搜索区域有可能被他们限制住了。 自然选择机制的引入将会逐渐减弱其影响。测试结果显示，虽然在大多数测试函数中选 择法取得了比基本p s o 更好的效果，却在g r i e w a n k 函数上得到了较差的结果。因此该 法提高了p s o 的局部搜索能力，但同时削弱了全局搜索能力。 3 ) 、领域拓手b ( n e i g h b o r h o o dt o p o l o g i e s ) 法 p s o 算法中的每个粒子的左右两边的粒子都是它的邻居，实际上这是应用了环形拓 扑。k e n n e d y 测试了如图2 1 所示的几种邻域拓扑结构。 8 第二章粒子群算法介绍 妨 环形拓扑b 融机化的环形拓扑 躲躲 c 轮形拓并 麓机化的轮彤拓扑 图2 - 1 两种可能的邻域拓扑图形 f i g 2 1ad i a g r a m m a t i cr e p r e s e n t a t i o no f t w op o s s i b l en e i g h b o r h o o dt o p o l o g i e s 结果表明，拓扑非常影响算法的性能，且最佳的拓扑形式因问题而定。如对有很多 局部最优的函数，轮形拓扑邻域算法能得到最好的结果，k e i l i l e d y 推测，这是由于较慢 的信息流动；而对于单峰函数，星形拓扑邻域算法可以产生较好的结果，因为它有较快 的信息流动( 这里的拓扑都是在粒子序号空间下的拓扑) 。 4 ) 、社会趋同( s o c i a ls t e r e o t y p i n g ) 法 k e 彻e y 提出了混和空间邻域和环形拓扑方法的另一个p s o 算法版本，称为社会趋 同法。因为生活中人们往往是试图追随一个群体的共同观点，而不是群体中某个人的立 场。将该思想应用到p s o 中，即不用每个粒子的经验而是用它所属空间聚类的共同经 验来更新自己。 5 ) 、序列生境技术( s n t ，s e q u e n t i a ln i c h et e c h n i q u e ) 法 b e a s l e y 等提出的最初使用在遗传算法中的序列生境技术可以系统地访问每一个全 局极值。其思想是在找到每一个极值后，都用下降函数来自适应地改变适应值函数， 如此算法就不会再回到该极值。虽然将s n t 引入p s o 会带来诸如参数选择、引入更多 局部极值等问题，但是该法能够枚举所有全局极值，在多目标优化问题上还是很有意义 的。 6 ) 、函数延 申( f u n c t i o ns t r e t c h i n g ) 法 为了减小定位所有全局极值的花费，p a r s o p o u l o s 等将自适应改变目标函数方法应用 到了p s o 中。他提出一个两步的转化过程来改变目标函数，以防止p s o 返回已经找到 的局部极值。该方法能跳出局部最优，有效定位全局最优点，有助于p s o 稳定地收敛， 虽然增加了计算量，p s o 的成功率却有明显的提高。但该方法不能枚举全部最优。 7 ) 、其它改进法 同时为了避免微粒群算法存在的过早收敛问题，j r i g h t 提出了一种保证种群多样性 的微粒群算法( a t t r a c t i v ea n dr e p u l s i v ep a r t i c l es w a r mo p t i m i z e r ) 该算法引入“吸引 和“扩散两个算子，动态的调整全局和局部的搜索能力，从而提高算法的效率。f v a n 9 江南大学硕士学位论文 d e nb e r g h 提出了具有局部收敛性能的改进粒子群算法g c p s o ( g u a r a n t e e dc o n v e r g e n c e p a r t i c l es w a r mo p t i m i z e r ) 。彭喜元等在研究论文中提出了一种将p s o 与模拟退火算法 相结合的p s o s a 算法性能分析过程中发现的初始参数依赖性问题和算法搜索能力问 题。通过模拟退火算法赋予搜索过程一种时变且最终趋于零的概率突跳性，有效地降 低了陷入局部极小的概率，从而获取更佳的近似最优解。 2 2 量子粒子群算法( q p s o ) 基于量子行为的q p s o 乜1 2 2 1 算法是在经典的粒子群算法( p s o 算法) 的基础上改进形 成的，它主要是结合了量子理论行为来改进的，提高了算法的全局优化性能，它与前面 所说的p s o 算法的思想相近，主要的区别是它们的进化公式不同，如下面介绍。 在q p s o 中，粒子群的进化公式如下： m 6 甜f ( f + - ) = 万1 善m 只( d = ( 吉善只。( f ) ，万1 善m 只：( f ) ，吉善( r ) ( 2 9 ) 尸弓o + 1 ) = f o ( t + 1 ) x p q ( t ) + ( 1 一f j ( t + 1 ) ) x 乃( f ) ( 2 1 0 ) ) 2 o + 1 ) 枷册雄+ 1 ) a ( t + 1 ) 咖协t j ( t “) 一x v ( t ) l x l n 赢q 1 1 ) 其中：厶( f + 1 ) = r a d f o ，u qo + 1 ) = r a d f o ；函数r a d f o 产生一个 o ，1 之间服从均匀 分布的随机数，r a n d ( t + 1 ) 以一定的概率分别取一1 和1 ，一般的方法是： r 口甩d o + - ，= ：翥羹：朋r a 矽d f o o o 。茎 c 2 1 2 ， m 表示粒子总数，d 表示粒子的维数，只( f ) 表示第t 次迭代时第i 个粒子的当前最 佳位置，只( f ) 表示第，次迭代时的全局最佳位置，这里m b e s t ( t + 1 ) 是粒子群中所有粒子 第，次迭代时当前最佳位置p b e s t ( t ) 的中间位置，r e , ( f + 1 ) 为粒子个体最优值只( f ) 和群 体全局最优值只( f ) 之间的随机点。口( f ) 为q p s o 的收缩扩张系数，它是q p s o 收敛的一个重