（计算机应用技术专业论文）群体智能算法可并行性分析及其软件硬件协同设计.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 n a l g o r i t h m ，p s o ) 的基础上改进而来，同时在此基础上提出了 基于粒子间相互协作的量子粒子群改进算法( c o o p e r a t i v eq u a n t u m - b e h a v e dp 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 m , c q p s o ) 。它们都是一种有效的全局优化搜索算法，相对于 p s o 算法而言，具有收敛速度快，收敛性能好的优点，但是由于q p s o 同p s o 算法一 样的是，它也把粒子作为一个整体来进行更新，因此q p s o 算法同样具有着维数限制的 缺点。通过把一个具有复杂高维的粒子分解为多个一维的子个体进行优化，使用协作方 法的c q p s o 算法能够很好的克服这一缺点。 目前，f p g a 技术日趋成熟。它不再仅是用于a s i c 的快速原型，而且还可以直接用 作s o p c ( s y s t e mo nap r o g r a m m a b l ec h i p ) 器件。f p g a 技术发展迅速，应用广泛。基于 b p 在线学习、c m a c 估计与控制、r b f 特征辨识等多种神经网络已在f p g a 器件 中实现并得到应用。在神经网络学习方面，p s o ( p a n i c l es w a r mo p t i m i z a t i o n ) 作为一种 新的优化算法正在引起人们的重视。就从改善算法性能来说，目前己应用到嵌入式工程 领域，如系统识别，控制参数优化，电力优化，f p g a 的布局和布线优化，和机器人控 制设计。， 本文并行性角度出发，分析了量子行为的粒子群q p s o 算法和粒子间相互协作的 c q p s o 算法结构的可并行性，并结合f p g a 技术可并行处理信息的特点，说明了在并 行运算模式下粒子的收敛性能。在x i l i n xi s e l o 1 中编程实现，在综合可配置后，采用主 串模式下载到f p g a 板中，得到的相关数据与在软件仿真中得到的数据相同。 关键词：量子粒子群算法( 协作性量子粒子群算法) ，可并行性分析，收敛速度， 收敛精度，并行硬件设计 a b s t r 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 na l g o r i t h ma sak i n do fs w a r l l li n t e l l i g e n c ea l g o r i t h m ，i s f r o mg r o u p so fb i r da n df i s hm o v e m e n tb e h a v i o r i t sm a i nf e a t u r ei ss i m p l ei np r i n c i p l e ：，f e w p a r a m e t e r sa n db e t t e rc o n v e r g e n c es p e e d t h ea l g o r i t h mi nf u n c t i o no p t i m i z a t i o n ，n e u r a l n e t w o r k , c o m b i n a t o r i a lo p t i m i z a t i o n , r o b o tp a t h # a r m i n gh a sb e e nw i d e l yu s e d a p p l i c a t i o n s b u th e r ei n t r o d u c e st h a tt h eq u a n t u mp a r t i c l es w a r mo p t i m i z a t i o n ( q p s o ) i s b a s e do nt h ep 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 d t h m a tt h es a m et i m e ，an e wh y b r i dq p s o a l g o r i t h mw i mc o o p e r a t i v em e t h o d ( c q p s o ) i sm e n t i o n d t h e ya r ea ne f f i c i e n ts e a r c h a l g o r i t h mf o rg l o b a lo p t i m i z a t i o n ，i nt e r m sr e l a t i v et ot h ep s oa l g o r i t h m ，w h i c hh a v eb e e n a d v a n t a g e so ff a s tc o n v e r g e n c ea n dt h eg o o dc o n v e r g e n c ep e r f o r m a n c e h o w e v e r , d u et ot h e s a m eq p s o 谢mp s oa l g o r i t h m , t l l e ya r ea l s ob a s e do nt h ep a r t i c l ea saw h o l et ob eu p d a t e d , h e n c eq p s oa l g o r i t h ma l s oh a st h ed i s a d v a n t a g eo fl i m i t e dd i m e n s i o n s b yc o m b i n i n ga h i g h - d i m e n s i o n a lp a r t i c l e s 、j l ，i mc o m p l e xd e c o m p o s e i n t o m u l t i p l e o n e d i m e n s i o n a l s u b - o p t i m i z a t i o no fi n d i v i d u a l s ，t h eu s eo fc o l l a b o r a t i v ea p p r o a c h e sc q p s oa l g o r i t h mc a l l o v e r c o m et h i ss h o r t c o m i n g c u r r e n t l y , f p g at e c h n o l o g yh a sm a t u r e d i tj sn ol o n g e rj u s tf o rr a p i da s i cp r o t o t y p i n g ， b u ta l s oc a nb eu s e da ss o p c ( s y s t e mo n ap r o g r a m m a b l ec h i p ) d e v i c e s f p g at e c h n o l o g yi s d e v e l o p i n gr a p i d l ya n dw i d e l yu s e d b p - b a s e do n l i n el e a r n i n g ，c m a ce s t i m a t i o na n dc o n t r o l ， r b ff e a t u r er e c o g n i t i o na n do t h e rn e u r a ln e t w o r kh a sb e e ni m p l e m e n t e da n da p p l i e di nt h e f p g ad e v i c e , i nt h en e u r a ln e t w o r kl e a r n i n g ，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 ) a l g o r i t h m a san e wo n ea r o u s e dp e o p l e i sa t t e n t i o n f r o mt h ei m p r o v e dp e r f o r m a n c eo ft h ea l g o r i t h m ，i th a sb e e na p p l i e dt ot h ee m b e d d e d e n g i n e e r i n gf i e l d s ，s u c ha ss y s t e mi d e n t i f i c a t i o n ，c o n t r o lp a r a m e t e r so p t i m i z a t i o n , p o w e r o p t i m i z a t i o n , f p g ap l a c e m e n ta n dr o u t i n go p t i m i z a t i o n ，a n dr o b o tc o n t r o ld e s i g nr e c e n t l y n l i sa r t i c l ei sf r o mt h ep a r a l l e l i s mp o i n to fv i e w ，a n a l y z e dt h es t r u c t u r ea b o u tt h e q u a n t u m - b e h a v e dp s oa l g o r i t h mq p s o a n dh e n c ean e wh y b r i dq p s oa l g o r i t h m 、7 l ，i t l l c o o p e r a t i v em e t h o db e t w e e np a r t i c l e sc q p s o ，w h o s e s t r u c t u r ec a nb ep a r a l l e l i s m t h e n c o m b i n gw i 也f p g at e c h n o l o g yc h a r a c t e r sw h i c hc a nb ep a r a l l e lp r o c e s s i n go fi n f o r m a t i o n , i n d i c a t e dt h ec o n v e r g e n c eo fp a r t i c l e sp e r f o r m a n c ei np a r a l l e lo p e r a t i o nm o d e p r o g r a m m i n g i nt h ex i l i n xi s e10 1 ，w h e nc a nb ec o n f i g u r e di ni n t e g r a t e d ，u s i n gt h em a i ns t r i n gp a t t e r n d o w n l o a dt of p g ab o a r d t h ed a t ao b t a i n e di nt h es o f t w a r ei st h es a n l e 嬲t h ed a t ao b t a i n e d i 1 1f p g a k e y w o r d s ：q p s o ( c q p s o ) ；p a r a l l e la n a l y s i s ；c o n v e r g e n c es p e e d ；c o n v e r g e n c ea c c u r a c y ； d e s i g no f p a r a l l e lh a r d w a r e i i 目录 目录 摘| 娶一i a b s t r a c t 。： 第一章绪论1 1 1 课题背景1 1 1 1 并行性运算的发展与趋势1 1 1 2 优化算法的并行性分析及其实现3 1 1 3 嵌入式微处理器的发展4 1 2 课题的目的与意义5 1 - 3 课题的主要内容与组织结构6 1 4 本章小结6 第二章粒子群算法的收敛性分析及其并行性分析：7 2 1 粒子群算法的介绍及其收敛性分析7 2 1 1 粒子群算法及其改进算法的介绍7 2 1 2 粒子群算法的收敛性分析1 3 2 2 粒子群算法的应用1 5 2 3 量子粒子群算法及其改进算法简单介绍- 一1 6 2 3 1 量子粒子群算法16 2 3 2 基于粒子间协作的量子粒子群算法1 7 2 4 量子粒子群算法的并行性分析1 8 2 5 量子粒子群算法的应用1 9 2 6 本章小结1 9 第三章软硬件协同设计2 0 3 1 算法并行逻辑设计模型与软件环境介绍2 0 3 1 1x i l i n xi s e l 0 1 介绍【4 2 】2 0 3 1 2m o d e l s i m 仿真器介绍【4 3 1 2 7 3 1 3v e d l o g 语言介绍】3 0 3 1 4 算法并行逻辑设计思路。3 2 3 2 算法的硬件并行设计3 3 3 2 1 基于f p g a 硬件平台的介绍【4 5 1 i 3 3 3 2 2 并行算法架构中主要的控制模块设计3 4 3 2 3 其他一些计算模块的设计。4 3 3 2 4q p s o c q p s o 算法的硬件设计思路一4 5 3 2 5h c l 6 4 驱动数码管模块一4 7 3 3 系统综合仿真、烧写实验4 8 3 4 本章小结4 9 目录 第四章算法的f p g a 实现及其实验数据分析一5 0 4 1 前言一5 0 4 2 算法的硬件加载与配置f 4 7 】5 0 4 3 数据分析5 4 4 3 1 基于m a t l a b 软件下实验数据与f p g a 并发设计试验下数据的分析5 4 4 3 2 粒子的收敛精度分析5 6 4 4 本章小结一5 6 第五章结论与展望一5 7 致谢5 8 参考文献一5 9 附录：作者在攻读硕士学位期间发表的论文一6 3 i i 第一章绪论 第一章绪论 1 1 课题背景 1 1 1 并行性运算的发展与趋势 并行计算( p a r a l l e lc o m p u t i n g ) 是指把多个处理器与方法和步骤结合起来，解决问 题，其具体实施是把一个给定的问题首先分解成若干独立的子问题，尽可能降低，然后 用它在同一时间用多台计算机解决，并最终获得原问题的解。这是为了提高计算机系统 的计算速度和处理能力的有效手段。它的基本思想是使用多个处理器来协调并解决同一 问题，这些问题被分解成若干个部分，每个部分由一个独立的处理器执行运算。并行计 算系统的设计，具有多个处理器的组合，也可以以某种方式互连的计算机构成一个独立 的计算机簇号。 并行计算引起了人们的广泛注意，那是因为现在的系统对实时性要求，更加依赖于 高精度的数据处理运算。所以，比较经典且常用的串行计算往往难以满足系统实时性的 需求，从而得借助于并行机用并行算法处理。 2 0 世纪4 0 年代，计算机开始慢慢发展起来，它的发展历程可以分为两个黄金时代： 串行计算时代、并行计算时代。狭义上的理解，串行计算是指在一台计算机上，这台计 算机上只具有单个中央处理单元( c p u ) ，所执行的软件写操作。c p u 逐个调用自身的 内部指令解决问题，这在时间上只能一个一个调用。但是由于器件的物理条件限制，单 一的处理器满足不了快速计算的应用，所以使用一个以上的处理器联合起来求解问题就 变得越来越重要了；其次，在大型和复杂的科学工程计算中，需要很强的精度，所以网 格计算被强调，同时引入网格运算需要大量的计算，这就需要并行机来实施。最后，对 于那些要求极高的实时应用中的问题，传统的串行处理在实时性的需要上还是比较困难 的，必须借助于并行机上用并行算法求解。科学家们在此基础上提出了并行计算的概念， 并行计算是在串行计算的基础上发展而来的，它努力仿真自然世界中的事务状态：一个 序列中众多同时发生的、复杂且相关的事件。 并行计算要求计算资源应包括一台配有多处理机( 并行处理) 的计算机、一个与网 络相连的计算机专有编号，或者两者结合使用。并行计算的主要目的是快速解决大型且 复杂的计算问题。此外还包括：利用非本地资源，节约成本，使用多个“廉价计算资 源取代大型计算机，同时克服单个计算机上存在的存储器限制。 并行计算机是由一组处理单元组成的。这组处理单元通过相互之间的通信与协作， 以更快的速度共同完成一项大规模的计算任务。因此，并行计算机的两个最主要的组成 部分是计算节点和节点间的通信与协作机制。并行计算机体系结构的发展也主要体现在 计算节点性能的提高以及节点间通信技术的改进两方面。 并行计算，是相对于串行计算来说的，所谓并行计算分为时间上的并行和空间上的 并行。时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的 执行计算。通常用来计算如下几个问题： 江南大学硕士学位论文 第一，将工作分离成离散部分，有助于同时解决； 第二，随时并及时地执行多个程序指令； 第三，多计算资源下解决问题的耗时要少于单个计算资源下的耗时。 并行算法可以分为数值并行算法和非数值并行算法【l 】：关于数值并行算法，它是基 于代数关系运算的，主要包括矩阵运算、方程组的求解和数字信号处理等。而非数值并 行算法是基于比较关系运算的符号处理问题，主要包括图论问题、数据库操作和组合优1 化等。 这些年来，随着半导体器件工艺水平的提高，计算技术和通信网络的迅速发展， 2 c p u 或4 c p u 的高档机已随处可见，而大学和研究所的各专业实验室中，自行用多台 p c 机搭建的机群系统也越来越多。随着现今并行机的普及，并行机的用户要求学习和 使用并行算法也甚为迫切，这就给我们研究并行算法带来新的机遇，它将使并行算法的 研究产生一个新的飞跃。与此同时，近几年来由于硬件技术的飞速发展，使得拥有成千 上万个c p u 的高端并行机相继研制成功。如何充分有效地利用如此巨量的c p u ，成为 并行算法研究面对的一个极富挑战性的问题。 目前研究的并行算法的研究主要分为以下几种类型：并行计算模型、并行算法设计 技术等 并行计算模型是指从不同并行计算机体系结构中抽象出来的、供并行算法设计者使 用的一种抽象的并行机。任何模型均必须提供为数不多的、能反映并行机计算特性的且 可以定量计算出或实际测量出的一组参数，并按照模型所定义的计算行为构造成本函 数，以此进行算法的复杂度分析。常用的并行计算模型有共享存储的模型 2 1 ，包括共享 存储的s i m d 同步p r a m t 3 】模型和共享存储的m i m d 异步a p r a m 模型；分布式存储 模型，包括分布存储的m i m d 大同步b s p 4 模型和异步l o g p 5 模型等【6 】；此外，对于松 散耦合的并行系统( 如基于局域网连接的p c 机群等) ，也提出了异构非独占使用方式的 分时计算模型。 并行算法设计技术 7 1 尽管理论上不是很成熟，具有很强的随机性和技巧性，但也不 是不能归纳出规律。这些年来，对并行算法改进许多，做了许多理论研究，已经总结出 了一些通用、基础的的并行算法设计技术。细分后有两个：划分法和随机法。 并行计算发展的新趋势，刀片服务器和云计算技术。刀片服务器是指在标准高度的 机架式机箱内可插装多个卡式的服务器单元，实现高可用和高密度。每块“刀片实际 上就是一块系统主板。它们可以通过板载硬盘启动自己的操作系统，类似于一个个独立 的服务器。在这种状态下，每块母板运行自己的系统，服务于指定的不同用户群，相互 之间没有关联。不过，管理员可以使用系统软件将这些母板集合成一个服务器集群。集 群里所有的母板都可以连接起来提供高速的网络环境，并同时共享资源，为相同的用户。 群服务。在集群中插入新的“刀片 ，就可以提高整体性能。而由于每块“刀片 都是 热插拔的，所以，系统可以轻松地进行替换，并且将维护时间减少到最小。 刀片服务器在设计上具有许多优点，比如说低功耗、空间小、单机售价低等特点， 在这基础上它还继承发扬了传统服务器的所具有的一些功能，比如热插拔和冗余电源 2 一一 第一章绪论 等，满足了密集计算环境对服务器性能的需求。其他的，在某些产品中还可以通过内置 的负载均衡技术，有效地提高服务器的稳定性和核心网络性能。 云计算技术是网格计算、分布式计算、并行计算、效用计算、网络存储、虚 拟化、负载均衡等传统计算机技术和网络技术发展融合的产物。它旨在通过网络 把多个成本相对较低的计算实体整合成一个具有强大计算能力的完美系统，并借 助s 从sa a s 、i a a ss p 等先进的商业模式把这强大的计算能力分布到终端用 户手中。云计算的一个核心理念就是通过不断提高“云”的处理能力，进而减少用户 终端的处理负担，最终使用户终端简化成一个单纯的输入输出设备，并能按需享 受“云”的强大计算处理能力。 1 1 2 优化算法的并行性分析及其实现 优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于 并行处理的算法。这种算法具有严密的理论论证，理论上可以在一定时间内找到最优解 或者是近似最优解。常用的智能优化算法有遗传算法( g a ) 、模拟退火算法( s a ) 、禁忌 搜索算法( t s ) 、粒子群算法( p s o ) 、蚁群算法( a c o ) 、m e m e t i c 算法等等。它们都 具有一些共同特点，初始化一个共同解，按照某一种算法机制进行迭代，以一定的概率 在整个求解空间中找到最优解，从而完成迭代。在迭代过程中，算法把搜索空间扩展到 整个问题空间，从而达到全局优化性能。这里给出遗传算法和蚁群算法的并行分析及其 蚁群算法的f p g a 实现。 蚁群算法( a n tc o l o n yo p t i m i z a t i o n , a c o ) ，又称蚂蚁算法，是一种用来在图中寻找优 化路径的机率型算法。它由m a r c od o r i g o 于1 9 9 2 年在他的博士论文中提出，其灵感来 源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究 表明该算法具有许多优良的性质针对p i d 控制器参数优化设计问题，将蚁群算法设计的 结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟 进化优化方法的有效性和应用价值。蚁群算法是一种求解组合最优化问题的新型通用启 发式方法，该方法具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点。通 过建立适当的数学模型，基于故障过电流的配电网故障定位变为一种非线性全局寻优问 题。 关于蚁群算法，m d o r i g o 等人先后提出a s , a c s 两个版本，之后，他们把a s 嗍、 a c s l 9 1 纳入统一的框架称之为蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n , a c o ) 1 0 1 。蚁群 算法的可并行性也是源于算法本身机理，从a c s 算法机理出发【l ，每只蚂蚁沿着城市 周游一周的过程是完全独立的选择下一个城市的概率计算、修改局部信息等因素完全可 以独立进行。基于这种并行性完全可以将m 只蚂蚁在m 个独立的并行处理机上进行并 行搜索。这种并行处理可以在以全局为中心的并行机上进行，也可以小规模专用局域网 实现。 从算法的可并行角度出发，进行理论分析，并结合嵌入式微处理器技术进行试验分 析是论证算法可并行性的一种有效方法。这就是说明并不是所有的优化算法都可以并 行，所以本课题的研究才有意义。 3 江南大学硕士学位论文 遗传算法作为群智能算法的一种，它表现出了良好的的算法可并行性。遗传算法是 借鉴生物界的自然选择法则建立起来的一种非导数优化计算方法，具有适应能力强，应 用范围广的优点同时也具有收敛速度慢的缺点，因此，许多学者提出了提高遗传算法收 敛速度的方法这些方法一般基于以下几个方面：( 1 ) 混合遗传算法，组合基于导数的优 化计算方法、模拟退火等算法；( 2 ) 并行遗传算法；( 3 ) 自适应遗传算；这些都是从 理论角度提高了算法的收敛速度，但是这些速度的提高还是不够的，所以再结合硬件技 术的并发性处理，会大大提高算法的收敛速度。 于是基于f p g a 的并行遗传算法的硬件实现系统被提出【1 4 1 ，从硬件实现角度提高 遗传算法的收敛速度，用遗传算法标准测试函数测试该硬件系统，实验数据表明，由 f p g a 硬件实现的并行遗传算法同由软件实现的遗传算法相比，收敛速度大幅度提高， 约2 个数量级。关于并行遗传算法的硬件实现，它采用了分解并行方法。这种方法是指 根据算法的特性，将一群体等分成若干子群体，每个子群体在各自的子系统上独立运行 简单遗传算法，每次迭代结束后，按照算法迭代机制交换一次数据，再接着迭代，直到 迭代一定次数后退出系统。试验验证了该算法的可并行性及其在硬件上实现的可行性。 1 1 3 嵌入式微处理器的发展 嵌入式系统( e m b e d d e ds y s t e m ) 是以应用为中心，以计算机技术为基础，并且软硬件 可定制，适用于各种应用场合，对功能、可靠性、成本、体积、功耗有严格要求的专用 计算机系统。它一般由嵌入式微处理器、外围硬件设备、嵌入式操作系统以及用户的应 用程序等四个部分组成，用于实现对其他设备的控制、监视或管理等功能。嵌入式系 统几乎包括了生活中的所有电器设备，如掌上p d a 、移动计算设备、电视机项盒、手 机上网、数字电视、多媒体、汽车、微波炉、数字相机、家庭自动化系统、电梯、空调、 安全系统、自动售货机、蜂窝式电话、消费电子设备、工业自动化仪表与医疗仪器等。 嵌入式微处理器较有代表性的有四种。l 、在8 0 3 l 上发展出了m c s 5 1 系列单片机 系统。2 、d s p 芯片，也称数字信号处理器，是一种具有特殊结构的微处理器。3 、a r m ( a d v a n c e dr i s cm a c h i n e s ) ，是高性能、廉价、耗能低的r i s c 处理器，同时在技术上 面非常成熟，随时可以找到更新的嵌入式编译环境。4 、f p g a ( f i e l d - p r o g r a m m a b l eg a t e a r r a y ) ，即现场可编程门阵列，它是在正、g a l 、c p l d 等可编程器件的基础上进一 步发展的产物。它是作为专用集成电路( a s i c ) 领域中的一种半定制电路而出现的，既 解决了定制电路的不足，又克服了原有可编程器件门电路数有限的缺点。 嵌入式系统的出现最初是基于单片机的。7 0 年代单片机的出现，使得汽车、家电、 工业机器、通信装置以及成千上万种产品可以通过内嵌电子装置来获得更佳的使用性 能：更容易使用、更快、更便宜。这些装置已经初步具备了嵌入式的应用特点，但是这 时的应用只是使用八位的芯片，执行一些单线程的程序，还谈不上“系统 的概念。 m c s 5 1 系列单片机系统使单片机得到了广泛的应用，随着工业控制领域要求的提高， 开始出现了1 6 位单片机，但因为性价比不理想并未得到很广泛的应用。9 0 年代后随着 消费电子产品大发展，单片机技术得到了巨大提高。随着i n t e li 9 6 0 系列特别是后来 的a r m 系列的广泛应用，3 2 位单片机迅速取代1 6 位单片机的高端地位，并且进入主 4 第一章绪论 流市场。而传统的8 位单片机的性能也得到了飞速提高，处理能力比起8 0 年代提高了 数百倍。 在信号处理、图像处理、仪器、声音语言、控制等领域d s p 数字信号处理器应用 比较广泛，d s p 芯片的内部采用程序和数据分开的哈佛结构，具有专门的硬件乘法器， 广泛采用流水线操作，提供特殊的d s p 指令，可以用来快速的实现各种数字信号处理 算法。d s p 具有大规模集成性、稳定性好、精度高、可编程性、高速性能、可嵌入性、 接口和集成方便等特点，但是它的成本较高、高频时钟的高频干扰、功率消耗较大等缺 点。 a r m ( a d v a n c e dr i s cm a c h i n e s ) ，是一个公司的名字，同时也是对一类微处理器 的统称。a r m 处理器有三大特点：耗电少功能强、1 6 位3 2 位双指令集和众多合作伙 伴。a r m 应用软件的开发工具根据功能的不同，分别有编译软件、汇编软件、链接软 件、调试软件、嵌入式实时操作系统、函数库、评估板、j t a g 仿真器、在线仿真器等， 目前世界上约有四十多家公司提供以上不同类别的产品。用户选用a r m 处理器开发嵌 入式系统时，选择合适的开发工具可以加快开发进度，节省开发成本。因此一套含有编 辑软件、编译软件、汇编软件、链接软件、调试软件、工程管理及函数库的集成开发环 境( i d e ) 一般来说是必不可少的，至于嵌入式实时操作系统、评估板等其他开发工具 则可以根据应用软件规模和开发计划选用。使用集成开发环境开发基于a r m 的应用软 件，包括编辑、编译、汇编、链接等工作全部在p c 机上即可完成，调试工作则需要配 合其他的模块或产品方可完成。 目前，以硬件描述语( v e r i l o g 或v 霸r d l ) 完成的电路设计，可通过一个简单、快速检 测并烧写至f p g a ，进行布局布线，这是现代集成电路设计的主流技术。但是f p g a 具 有许多与传统微处理器不同的特点：l 、采用a s i c 电路设计，用户不需要投片生产，就 能得到合适的芯片。2 、f p g a 可以定做其他全定制或半定制a s i c 电路样片。3 、f p g a 内部有丰富的触发器和i o 引脚。4 、采用f p g a 的a s i c 电路设计，具有开发周期最短， 开发成本低，风险小。5 、f p g a 技术采用高速c h m o s 工艺，可以与c h m o s 、1 凡电 平兼容。可以说，f p g a 芯片是小批量系统提高系统集成度，高可靠性中的佼佼者。 1 2 课题的目的与意义 粒子群算法同遗传算法、蚁群算法机理一样都有较强的并行性，但是p s o 是根据自 己的速度来决定搜索，没有遗传算法的明显的交叉和变异并且不需要梯度信息，只需要目 标的取值，具有很强的通用性。p s o 收敛速度较快，尤其是在算法的早期，但也存在 着不够精确，容易发散等缺点。如果加速系数、最大速度等参数太大，粒子群有可能达 不到最优解，从而粒子群不能收敛到正确位置。相反在收敛的情况下，由于所有的粒子都 能收敛到最优解，所以粒子趋向同一化( 丧失了多样性) 。在这种情况下，群体在后期的迭 代过程中，收敛速度变慢较明显，群体的优化能力下降，所能达到的精度也比遗传算法低。 所以很多学者都致力于改进粒子群算法的性能。 目前，对于算法性能的改进主要从收敛速度方向提出：l 、惯性权重法。2 、模糊惯 性权重法。3 、压宿因子法。4 、选择法。5 、繁殖法。6 、领域拓扑法。7 、社会趋同法。 5 江南大学硕士学位论文 这些方面的改进，主要集中在对算法迭代式的改进，或者是对算法参数的优化、优化函 数的形状。 ， 1 3 课题的主要内容与组织结构 针对本课题组提出的q u a t u m b e h a v e dp s o ( q p s o ) ，在已作算法串行固化到f p g a 的基础上，从算法的并行性出发，重新分配子系统，把算法并行化架构固化到f p g a 中。 接着考虑到全局粒子的收敛性能问题，把提出的基于粒子间协作的改进算法c q p s o 并 行化架构也固化到f p g a 中，在基于标准测试函数的基础上，观察粒子的收敛性能。本 文的主要内容归纳如下： 1 、首先对粒子群算法进行简单介绍，接着阐述基于粒子间协作的粒子群算法，从 算法的可并行性角度出发，观察粒子在标准测试函数及两种算法并行架构的条件下，粒 子的全局收敛性能及局部收敛性能。 2 、鉴于硬件实现算法的困难性，如何对算法并行设计及成功固化到f p g a 中，得 到的实验数据是否与己被得到验证的实验数据相同，都是待验证的问题。 所以本文主要从如下几章展开： 第一章介绍本课题的研究背景，并且阐述接下来所要做的工作。 第二章对粒子群算法收敛性及其并行性进行分析，结合已做好的理论分析和待阐述 的问题进行了系统的理论分析。 第三章从软硬件协同设计的思路出发，简单介绍上位机编码环境，着重阐述算法的 并行逻辑实现及硬件架构设计。接着对所要用到的f p g a 开发平台进行了介绍。 第四章主要介绍并行算法成功固化到f p g a 中，对实验数据进行对比分析得出结 论。 第五章总结全文，并对进一步研究作出展望。 1 4 本章小结 这里介绍了下并行运算的理论研究、发展及趋势，并接着在其基础上简单介绍了下 并行运算的应用。为了引入本课题将要讨论的问题，叙述了算法并行设计思路及已成功 实现的一些算法并行设计。算法并行的实现需要借助于一些硬件平台，如a r m 微处理、 f p g a c p l d 等，所以简单介绍了一下嵌入式微处理器的发展。最后，给出了本论文的 主要内容与组织结构。 6 第二章粒子群算法的收敛性分析及其并行性分析 第二章粒子群算法的收敛性分析及其并行性分析 2 1 粒子群算法的介绍及其收敛性分析 2 1 1 粒子群算法及其改进算法的介绍 在微粒群算法的基本概念中，其中之一简单的描述过程是，关于个体学习和文化传 递的基本概念。比如，人们在决策的过程中要使用两类重要信息：一是自身的经验；二 是其他人的经验。微粒群算法是在1 9 9 5 年，由美国社会心理学家j a m e s k e n n e d y 和电气 工程师r u s s e l l e b e r h a r t 共同提出的，思想来源于他们早期对许多鸟类的群体行为进行建 模与仿真研究结果得到的启发。鸟类在迁徙的过程中，使用一些简单的规则确定自己的 方向与飞行速度，这些鸟类在飞行的过程中，都不愿脱离鸟群或与自己的同伴相撞，如 果因为一只鸟飞离了鸟群，转而飞向栖息地时，这将会使周围的其他鸟也随他飞向栖息 地。于是，这将驱使更多的鸟落在栖息地，直到整个鸟都落在栖息地。这与寻求一个特 定的问题的解很类似，于是k e n n e d y 和e b e r h a x t 对基本概念进行了修正，即如何保证微 粒群着落的最佳方案是其群体的最优解，这体现在两个方面，即信念的社会性和智能性。 信念具有社会性，具体表现在个体不断地向它周围的成功者学习，和周围的其他同类进 行比较，并且模仿其优秀者的行为。于是，在这种推理下，使用一种算法将这种思想实 现。k e n n e d y 和e b e r h a r 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 ) 。 1 粒子群算法原理阐述【1 5 l 微粒群算法与其他进化类算法相比较，有其类似之处，“群体 与“进化”的概念 在微粒群算法中也得到了采用，粒子群位置的更新由个体的位置更新所决定。唯一有一 点不同的是，在n 维搜索空间中，粒子群算法把每一个粒子都看成一个个体，他们都是 没有重量和体积的微粒。他们在该搜索空间中自身都有一定的速度，并且其飞行速度都 是由个体和群体的飞行经验进行动态更新。 设粒子f 的当前位置为x ，= 瓴，x a )，当前的飞行速度为=“，m：，)，当前- 粒子的最好位置为a = ( 办，只：，以) ，在选取下一时刻的函数最优值时，要想适应值选 取的越好，取决于目标函数值选取的情况。目标函数值设为厂( x ) ，且添加下列约束条 件使得在每次位置的更新中更新粒子的最好位置： 驸驴 瑞鬣踹缆2 分 池l ， 设群体里有s 个微粒，且群体中所有微粒经过每次的更新后，最好位置为p p ( f ) ，称为全 局最好值。则 p g ( f ) 瓴似最( f l ，只( f 刈厂眩= m i n b , - ( e o o ) ) ，厂亿( f 强，厂仉o ) ) ) 7 江南大学硕士学位论文 有了上述定义，基本微粒群算法的进化方程可描述为： ( ，+ 1 ) = ( f ) + q 翮而 ( 砌一( f ) ) + 乞陀峨( 砌一嘞( f ) ) h o + 1 ) = ( f ) + ( ，+ 1 ) ( 2 2 ) ( 2 3 ) 其中，下标“d 表示微粒的第d 维：“f 表示微粒f ；f 表示第，代；c 、c ，为加 速常数，通常取值o 2 ，r a n d 。- v ( o ，1 ) ，r a n d 2 - v ( o ，1 ) 为两个相互独立的随机常数。 【- v 。，v 。】，其中，程是用户设定速度的上限。如果问题的搜索空间限定在 卜x 一，x 一】内，则可设定v 。残= k x m a x ，0 1 k 1 0 。 2 粒子群算法流程 ( 1 ) 依照初始化过程，初始化整个粒子群的随机位置和速度； ( 2 ) 计算出粒子群中各个粒子的适应值； ( 3 ) 将粒子群中每个粒子的适应值与所经历过的最好位置只的值按照式( 2 1 ) 进行 比较，满足条件的作为当前的最好位置； ( 4 ) 将粒子群中每个粒子的适应值与所经历过的最好位置只的值按照式( 2 1 ) 进行 比较，满足条件的作为当前的最好位置； ( 5 ) 按照式( 2 2 ) 和( 2 3 ) 对粒子的速度和位置进行进化； ( 6 ) 通常约束条件为足够好的适应值或达到一个预设最大的迭代次数，否则返回步骤 ( 2 ) 继续迭代。 3 粒子群算法的社会行为分析 在式( 2 2 ) 中，它描述了一个速度进化的方程，包含两部分，分别为粒子先前的 速度和粒子的“认知 部分，这里只考虑了粒子自身的经验，即粒子本身的思考。在基 本粒子群算法的速度进化方程中，如果仅包含认知部分，即 ( t + 1 ) = ( t ) + q r a n d l 木( 办- x 埘( t ) ) + c 2 r a n d 2 ( 砌一( f ) ) 则其性能就会变得较差。这主要是因为不同的粒子间没有信息交流，即不共享社会信息， 而彼此之间又不相交互，规模很大的群体因为这等同于运行了单个的个体微粒，所以得 到最优解的概率不高，而且收敛速度也明显降低。 ， 在速度进