（计算机应用技术专业论文）并行进化算法的研究与应用.pdf

摘要 摘要 本文的目的是研究一种新的并行进化算法及其应用。群体智能算法是一种进化类算法，是解决 优化问题特别是复杂系统优化问题的有效手段。而q p s o 是一种新的、具有全局收敛性群体智能算 法并且许多实际麻h 证明，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 简称 p s o ) 和遗传算法( g e n e t i ca l g o r i t h m ) 。因此，本文的研究内容对丁| 群体智能和并行化的发展具有一 定的学术意义和应用价值。 本文在研究了遗传算法、粒子群优化算法和具有量子行为的粒子群算法及其并行化研究现状的 基础上，受遗传算法并行化的启发，对粒子群优化算法和具有量子行为的粒子群算法提出并实现了 新的并行化策略。主要思想是引入岛域模犁和交换算子的概念，在机群环境f ，基于这两种优化算 法在求解的过群中，相互之间通过迁移算于米达到相互之间交换信息的目的，使得整个群体的多样 性得到保持从而提高了算法的全局搜索能力。 住并行删试中，由丁通信时间过k 会引起通信的瓶颈问题本文对相互通信的时间进行了改 进，相互通信的周 i i i 按指数递减地序列进行，文中主要是以一些常见的基准函数的并行实现为例 详细描述了算法设计思想和程序实现过程，提供了大颦的测试结果，并与相应串行算法在相同计算 环境r 的测试结果做出比较，以及不同并行实现之间的比较。测试结果表明，无论是在优化算法的 搜索能力还是在运行的时间上。本文的并行方案相对于串行算法以及现有的并行策略都具有一定的 优势，提供了解决复杂优化问题的一种有力手段。本文将p p s o 算法片j 于个在多阶段投资组合优 化系统中进行决策的决策制定过程目标函数是最夫化个人经济效益或最人化周期结束时个人财富。 通过比较按删望同报平标准方筹铍不同的目标函数所优化的投资组合的性能来指导验证。 关键词：并行：粒子群优化算法：量子化；多阶段随机优化 江南人学硕f 。学位论义 a b s t r a c t i n t h i sp a p e ran o v e lc l a s so fp a r a l l e l e v o l u t i o n a r yc o m p u t a t i o nt e c h n i q u e - s w a r mi n t e l l i g e n c e a l g o r i t h ma n da p p l i c a t i o ni sd i s c u s s e d ，a m o n gw h i c ht h eq 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 n ( q p s o ) a l g o r i t h mi sar e c e n t l yp r o p o s e da p p r o a c ha n di sav a r i a n to f o r i g i n a lp 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 ) q p s oi sg l o b a lc o n v e r g e n ta n dw i l lb eap r o m i s i n gs o l v e rf o rc o m p l e xo p t i m i z a t i o np r o b l e m ， w h i c hi ss h o w nb ys o m ep r e v i o u sw o r k t h u s ，t h er e s e a r c ho ft h i sp a p e rw i l lb eo fs o m e w h a ts i g n i f i c a n c e i ne v o l u t i o n a r yc o m p u t a t i o na r e aa n dp a r a l l e la r e a o nt h eb a s eo fg e n e t i ca l g o r i t h m ，p a r t i c l e $ w a r n la l g o r i t h m ，q u a n t u m b e h a v e dp a r t i c l es w a l t na l g o r i t h m a n ds o m eo t h e rp a r a l l e la l g o r i t h m ，w ep u tf o r w a r dan e w p a r a l l e lm e t h o do np a r t i c l es w a h r la l g o r i t h ma n d q u a n t u m - b e h a v e dp a r t i c l es w a r ma l g o r i t h mb yt h ei n f l u e n c eo ft h ei m p l e m e n to fg e n e t i ca l g o r i t h m t h e m a i ni d e ai si n t r o d u c i n gt h ec o n c e p t so fi s l a n dm o d e la n dc h a n 百n ga r i t h m e t i co p e r a t o r s i nt h ec l u s t e r e n v i r o n m e n t ，t h eo p t i m a la l g o r i t h mi n c r e a s i n gg l o b a ls e a r c h i n ga b i l i t yb ym a i n t a i n i n gd i v e r s i t y - u s i n g c h a n g i n ga r i t h m e t i co p e r a t o r st oc o m m u n i c a t ew i t he a c ho t h e r d u et ot h e l o n gt i m e f o rc o m m u n i c a t i o n ，b o t t l e n e c kw i l l a p p e a ro np a r a l l e l t e s t s w ea m e n d c o m m u n i c a t i o nb yr e d u c i n gt h ec o m m u n i c a t i o nc y c l ea c c o r d i n gt od e s c e n d i n gn u m e r a la r r a y w es e t e x a m p l e sb ys o m eb a s i ct e s t i n gc a s et od e s c r i b et h ed e s i g ni d e aa n dt h ei m p l e m e n tp r o c e s sa n dw ep r o v i d e m a n yt e s t i n gr e s u l t sa n dc o m p a r i s o nw i t ho t h e rs e r i a la n dp a r a l l e lr e s u l t s t h er e s u l t si n d i c a t et h a tb o t h s e a r c h i n ga b i l i t ya n dr u n n i n gt i m ea r eb e t t e ra n di t sau s e f u lm e a n sf o rs o l v i n gc o m p l e xo p t i m i z a t i o n p r o b l e m s i nt h i sp a p e r , w ep r e s e n tad e c i s i o n - m a k i n gp r o c e s st h a ti n c o r p o r a t e sp a r a l l e l p a r t i c l es w a r m o p t i m i z a t i o n ( p p s o ) a l g o r i t h mi n t om u l t i - s t a g ep o r t f o l i oo p t i m i z a t i o ns y s t e m t h eo b j e c t i v ef u n c t i o ni s t om a x i m i z eo n e se c o n o m i cu t i l i t yo re n d o f p e r i o dw e a l t h e x p e r i m e n t sa r cc o n d u c t e dt oc o m p a r e p e r f o r m a n c eo ft h ep o r t f o l i o so p t i m i z e db yd i f f e r e n to b j e c t i v ef u n c t i o n si nt e l t u so fe x p e c t e dr e t u ma n d s m n d a r dd e r i v a l i o n k e y w o r d s ：p a r a l l e l ；p a r t i c l es w a r m o p t i m i z a t i o n ；q u a n t u m ；m u l t i s t a g e s t o c h a s t i c o p t i m i z a t i o n i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名： 日期：岬年6 月；日 关于论文使用授权的说明 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 签名：墨毖导师签名：( ! 皇! 坚 日期：a - 7 年j 月；日 第一章 绪论 1 1 课题背景 第一章绪论 人苗的n p 难解问题比如：函数优化、结构优化、神经网络训练、模糊系统控制、模式分类、- r = 厂布图、时序安排等问题以及其它的应用领域中的一些n p 难解问题都需要用到优化，在解决这些 问题的过程中经常会遇到两个棘手问题：一是，大规模的问题常常需要大量的计算，这样就要。1 i 用 较k 的时间资源，二是，由于存在较多的局部虽优解，所求的解常常会落入某个局部最优解。这样 就需要寻找一个易于得到全局虽优解的优化算法。 诸如大气预报和地震分析等富有挑战性的应用己逐渐成为并行计一算机发展的强人的、主要的 推动力“1 。创建和使用并行计算机的主要原因是因为并行计算是解决单处理器速度瓶颁的最好方法 之一。 在实际应用中，人们经常需要比串行计算机所能提供的能力更强的计算能力。克服这种限制的 一种方法是增加处理器和其他部件的运算速度，以使他们能提供应用所需的更强大的计算能力”。 然而计算机单机技术的发展受着诸如光速与物理尺寸的限制，正是这种计算机单机技术发展的有限 性与科学j 。榉计算的无限性之间的矛盾决定了计算机发展必然走上多机并行的道路。由丁| 采用人规 模的升行，使得计算机的计算速度大人提高，反过来，科学技术需要求解的课题规模越人、问题越 复杂，并行的渐力越人，这也要求高性能计算走并行的道路。 1 2 课题内容 鉴丁以上课题背景，本文总结研究了现在比较常用的和较新出现的优化算法的性能比如二进 制遗传算法，十进制遗传算法，粒子群优化算法( p s o ) ，簟化粒子群算法( q p s o ) 等研究了现 有的实现其并行化的方法，提出了新的并行策略，期望得剑更好的结果：在相同处理器时间内得到 更高质龉的解或者得剑相同质餐的解需要更少的处理器时间。针对不带约束的优化问题利带约束 的优化问题的一些基准函数进行测试，并对其实验结果进行详细分析比较，以讨论各种优化算法并 行化策略对相应串行算法的作_ j 效果。最后对多阶段投资组合进行优化，并对其试验结果进行分析 比较。 1 3 课题意义 遗传算法，粒子群优化算法，姑化粒子群优化算法白提出以来，在国内外都有一定的研究，对 - 二进制遗传算法的研究及并行化已经有了很深的研究及麻用，但是对十进制遗传算法和另外两种算 法的并行化研究却很少尤其是对量化粒子群优化算法的并行化研究还未出现。本文除了促进优化 算法本身的发展外，更重要的意义在于提供了解决大多数组合优化问题的一种手段。因为n p h a r d 类问题一直以来都是很难求解的，在计算机问世之前，对较大规模的问题可以说根本不可能得剑确 定的晟女r 解，尽管有了计算机并且其性能极速发展但对丁实际问题对计算能力的需求来说，目前 仍显滞后。从这方面讲本文对其它算法的并行研究又具有实际意义。 具体剑本文所介纠的算法的并行化的研究，本文讨论的重点在于如何获得更好的晟优解以及 提高求解的速度。提出了不同的并行方案来横向纵向比较不同算法所得剑的结果。 垩堕查兰堡! ：兰竺堡皇 1 4 本文的组织结构 本文在第二部分介绑了并行的基础知识，第三章介绍了遗传算法，粒子群优化算法，苗化粒子 群优化算法的原理，讨论了各种算法的改进及性能比较并对研究现状进行了对比：第四章阐述本文 提出的并行策略及其实现；第五章对实验结果做出详细分析并得出绪论。 2 第一二章并行算法基础 第二章并行算法基础 2 1 并行算法的一般概念 在数值建模和优化计算解等许多领域中，常需要对大量数据进行多次重复计算来得剑有效结果。 并且要求计算必须在合理时间内完成，例如数值气象预报、太空中大体运动预测、虚拟现实等问题， 这些麻川对计算速度的需要总是在不断的增长。即使是在现代的高端处理器上，求解这些人规模 复杂1 程问题依然需要人鼍的计算时间。提高计算速度的一种方法是 j 多个处理器协同求解一个问 题，可以是带有多个处理器的计算机或是以某种方式互连的若干台独立计算机1 4 j 。并行计算因为能 够充分地缩减人规模l ：程问题求解的时间需求得到广。泛应用，比如遗传算法i ，1 ( g e n e t i ca l g o r i t h m ， g a ) 、模拟退火( s m u l a t e da n n e a l i n g ，s a ) 等优化方法都已被成功并行化并应_ j 剑了复杂问题的优 化上。 除了加速对问题求解之外，多计算机多处理机的使用可以在给定时间内计算更多的求解点，从 而获得更精确的解。 2 2 并行性 传统的计算机是串行结构的，每时刻只能按一条命令指令对一个数据进行操作，事实上这种结 构限制了运算速度。从6 0 年代起，并行处理技术开始引入计算机的结构设计中，以改进系统结构。 所谓并行处理就是把一个传统串行处理的任务分解开来，并将其分配给多个处理器同时处理，即在 同一时间间隔内增加计算机的操作数量。为并行处理所设计的计算机称为并行计算机l “。 2 2 1 并行算法的性能评价 并行算法的三个评价如卜p j ： 1 并行算法的成本c 定义为并行算法的运算时间t ( n ) 与所需处理机数目p ( n ) 的乘积，即： c e n j = t e n ) p f m 如果在数革级上等丁| 串行算法最坏情况f 解决相同问题所需执行步数，则称该并行算法成本为 最优的。 2 加述比s 口m j 对丁一个求解问题，令五p 为最快的串行算法在最坏情况f 的运算时间，印似是求解此问题的 某一并行算法在最坏情况f 的运算时间则此算法的加速比定义为 s p ，刖= t s c n ) f p r n ) 可以看出，：跏倒p 例，当印例= p 时称具有此加速比的并行算法为最优的并行算法。 3 并行算法的效率勋r ， 并行算法的效率可定义为加速比与处理器数目的比，即 ；n j = 印o n ；p n p ，它反映了在执行算法时处理机的利_ 【 j 情况，由于，= s p r n ) p n p ，故d 印倒 e 1 。若一个并行算法的兑化翠等丁，则说明住执行算法的过程中每台处理机都得剑了充分的利川。 不过一般情况f ，要达剑e p 例= ，是不可能的。 江南人学颂 + 学位论史 2 2 2 并行编程模型 并行编稃模型共有以f 几种”： 隐式编科模型：这种编稃模犁相对显式编程模璎而言，程序员不片j 显式的说明并行性，由编译器、 运行支持系统对程序进行并行化。现在比较流行的有以一f ) l 种形式：并行化编译器、自动并行化、川 户指导和运行时间并行化。这种模型突出要解决的问题是数据依赖和控制依赖。并行化编译技术是 一个日趋活跃的研究课题，但是目前由丁这种技术还不成熟，其性能让研究者火望。 日前最重要的并行编样模刑是数据并行和消息传递，数据并行编程模型的编程级别比较高，编 拌相对简单，但它仅适_ 丁数据并行问题；该模型适用于s i m d 方式，主要思想是将一组数据颁布 剑多个计算机1 ，点上，在。竹点计算机并行执行相同的指令或程序。另外有一个全局的存储空间和数 据结构进行并行操作。消息传递编程模型的编程级别相对较低，但消息传递编样模型可以有更广泛 的戍川范隔。是指在各个计算机节点并行执行，消息通过计算机网络进行传递，主要是指令数据、 同步信号、中断信号等。现在流行消息传递模型编程j ：具有m p i 、p v m 等。 共享变量模型：共享变苗模型和数据并行模型类似，都具有单地址空间。同时义和消息传递模剐 类似，冈为它是多线拌和异步的。由丁i 数据驻留在单一共享地址空间中，冈此不需要对数据加以显 式分配，通信通过读写共享变量实现但是同步必须是显式的。 2 3m p i 的语言绑定 由y - m p i 是一个库而不是一门语言，因此对m p i 的使用必须和特定的语言结合起米进行， f o r t r a n 是科学与l ：样计算的领域语言，而c 义是目前使h j 最广泛的系统和麻川科序开发的语言 之一，闪此对f o r t r a n 平c 的支持是必须的1 6 , 7 1 。 4 第三章几种进化算法 3 1 优化问题 第三章几种进化算法 为了使系统达到最优的目标所提出的各种求解方法称为最优化方法。晟优化方法是在第一次世 界人战前后在军事领域中对导弹、雷达控制的研究中逐渐发展起来的。它对促进运筹学、管理科 学、控制论和系统十程等新兴学科的发展起到了重要的作片j i j 。在经济管理学上就是在一定人力、 物力和财力资源条件b ，使经济效果( 如产值、利润等) 达到最大，并使投入的人力和物力达剑以最 小的系统科学方法。 最优化在运筹学和管理科学中起着核心作用。最优化通常是极大或极小某个多变量的函数并满 足一些等式或不等式约束。最优化技术对社会的影响日益增加，应用的种类和数茸快速增加，丝毫 没有减缓的趋势。 近儿年来，随着计算机的发展，一些过去无法解决的复杂优化问题已经能够通过计算机来求得 近似解所以，计算机求解优化问题的方法研究也就显得越来越重要了。 求解晟优化问题的优化方法有各种形式。针对相同的优化问题，不同的优化方法具有不同的优 化特性。有些优化方法可以快速求解剑局部晟优解，有些优化方法具有很好的全局最优解，有些优 化方法可以快速有效的得到全局最优解。求解最优化问题的理想情况是快速有效的得到全局最优解。 由丁对蛀优化问题的性质和最优化方法认识的不足，这种情况只能在有限的条件f 实现。对于复杂 函数最优化问题，一般很难找到收敛性好且全局最优的优化方法。工程优化应用的人多数问题，都 需要先对其进行数学建模，即向数学问题转化，然后对函数进行优化j ：程优化所建立的数学函数， 往往是带有多种约束条件的复杂函数，而且人都是既不连续、也不可微的隐函数对丁这些复杂函数 来说，川常规的数学方法很难或根本无法处理常_ 【 j 的优化方法有线性规划法、前线性规划法、动态 规划法、极人值法甾。 3 1 1 无约束优化 无约束优化针对的是没有任何约束前提f 的极大或极小化某个函数的问题。一般，无约束优化 问题可h 】如r 数学公式描述i ： m i nf ( x ) s tx q 其中，厂是值函数可行域q 是e ”的子集就可行域而方言，当口= e ”时，问题是完全无约束 的。 虽然绝人多数实际优化问题都有必须满足的约束，但无约束优化问题的研究是约束问题的基础。 3 1 2 约束优化 人多数实际的优化问题往往都是带有约束条件的 成f 面的1 | 线性规划问题： m i n f ( x 1 ； x c s c r j 服从丁- f 面的线性或1 e 线性约束： 般而言，一个有约束的优化问题可以描述 ( 3 1 ) 江南人学硕j j 学位论j 。警扛l ，2 研 ( 32 ) i h ，( 工) = o ；，= 1 , 2 ，k 其中f ( x ) 是一个目标函数，s 是可行区域的解r 是整个寻找空间，g ，( z ) 和h ，( x ) 分别是约束 不等式和i 约束等式，公式( 3 2 ) 中的约束函数是非限制性的，因为一个g ，( x ) 0 形式的不等式约束也 可以埘- g ，( z ) - ( p ( f ) ) r ，、 群体中的微粒数为n ，群体中所有微粒所经历过的最佳位置p g ( t ) ，称为全局虽佳位置。则： 只( f ) p o ( t ) ，b ( ，) ，b ( ，) i ，( 只( r ) ) = m a x t 厂( 昂( ，) ) ，( 鼻( ，) ) ，( b ( ，) ) ) 1 0 苎三皇! ! 登丝些竺鲨 ( 3 5 ) k e n n e d y 和e b e r h a r t 最早提出的p s o 算法的进化方程如下： 峋( f + 1 ) = v f ( f + 1 ) + c - ，( d 4 喝( f ) 一3 咯( f ) ) + c 2 + ( f ) ( 巴( f ) 一x p ( f ” ( 36 ) x p ( t + 1 ) = 工 ( t ) + v _ ( f + 1 ) f ，7 、 其中：f 标“z ”表示第2 个微粒，下标“，”表示的是微粒i 的第j 维分晕，t 表示第t 代 学习网子。l ，。2 为非负常数，。l 用来调节微粒向本身晟好位置b 行的步长，。2 用来调1 i 微粒向群体 最好位置e 行的步长，通常q ，c z 在【o ，2 】间取值。，( ) ，( f ) 是两个介于【o ，1 】之间的服从均匀分 布的随机数，即：( ) u ( 0 ，n ，( r ) u ( o ，n 。为了减少在优化过程中，微粒e 出搜索空间的 可能性，”【。) 通常限定在一定的范围内，即峋【盂，】。v 一、v m “是根据具体问题而人为设 定的，同时人仃j 也会根据具体问题，限定搜索空间x 口【z m ，5 一】。迭代终i r 条什根据具体问题一 股选山最人迭代次数或粒子群搜索剑的展优位置满足于预先设定的精度。为了方便起见，我们将经 典微粒群算法的形式表述如卜_ ”“： k ( ，+ 1 ) 2 ( f ) + c 1 。( p ( f ) 一x ( f ) ) + c 2 。r 2 。( 尸g ( f ) 一x ，( f ) ) ：( 3 8 ) x ，( f + 1 ) = x ( t ) + 一( t + 1 ) f r9 1 经典微粒群算法的算法流拌如下： 步骤一、依照如f 初始化过程对微粒群的随机位置和速度进行初始设定。 、设定群体规模，即粒子数为n 。 、对任意f ”，随机产生在【。一，x j 内服从均匀分布的l 。 、对任意f ”，随机产生在【”一，”一j 内服从均匀分布的”。 、对任意f 初始化局部最优位置为：只2z 。 、初始化全局最优位置0 为：f ( p g ) 2 m a x f f ( x - ) ，f ( x ：) ，f ( x w ) 。 步骤二、根据目标函数计算每个微粒的适麻度值。 步骤二、对丁每个微粒，将其适麻度值与其本身所经历过的最好位置尸的适应度值进行比较，如更 好，则将现在x 的位置作为新的p 。 步骤四、对每个微粒，将其经过的最好位置只的适应度值与群体的最好位置的适应度值比较，如果 更好，则将p 的位置作为新的名。 步骤五、根据等式( 3 6 ) 、( 3 7 ) 对微粒的速度和位置进行更替。 如为达剑结束条件，则返同步骤步骤_ 二。算法的终j p 条件是：迭代次数满足一定的要求、最优 值在一定的迭代次数中不再发生变化、最优值达到所要求的精度，在本文中，我们采_ l f 迭代次数满 足一定的要求作为结粜条件。 3 3 3 两种基本的进化模型 在基本的p s o 算法中，根据直接相互作用的微粒群定义可构造p s o 算法的两种不同版本也就是 说，可以通过定义全局最好微粒( 位置) 或局部最好微粒( 位置) 构造具有不同行为的p s o 算法。 ( ，g b e s t 模喇( 仝局最好模型) g b e s t 模掣以牺牲算法的鲁棒性为代价提高算法的收敛速度，基本p s o 算法就是典型的该模删的 体现。在该模掣中，整个算法以该微粒( 全局虽好的微粒) 为吸引子，将所有微粒拉向它，使所有 的微粒最终收敛于该位置。如果在进化过程中，该全局最优解得不剑更新，则微粒群将出现类似丁 遗传算法甲熟的现象。 、l b e s t 模型( 局部最好模型) 1 1 坚里查兰堡! ：兰些堡皇 为了防止g b e s t 模型可能出现早熟现象，l b e s t 模型采川多个吸引子代替g b e s t 模型中的单一 吸引子。首先将为粒子群分解为若干个子群，在每个粒子群中保留其局部最好微粒p ( n ，称为局 部最好的位置或邻域晟好位置。假设每一个粒子在大小为，的邻域内定义一个集合 j v ，2 p b e s t 一，p b e s 一，p b e s t f + ) ，从f 中选出最好的，将其位置代替标准p s o 算法公式中 的g b e s t ，其他与全局版p s o 相同。实验表明，局部虽好模型的p s o 比全局最好模型的收敛慢，但 不容易陷入局部最优解。 3 3 4 改进的微粒群算法 止如先前所述，公式( 1 3 ) 由三部分组成：第一部分是粒子先前的速度项，即，u ，第一二部分和 第二部分是导致粒子速度变化的两项，即q 。，l 。( 尸( ，) ) 一j ，( ，) ) 和c 2 。吃。( 丘( ，) 一x ( f ”。 一方面，公式( 3 8 ) 如果没有后两项，粒子将保持在相同的方向上以当前的速度“飞翔”至f 一 个点直至达剑边界值。这样的p s o 将不能找到一个可接受的解，除非这样的e 行轨迹是一种合理的 方案，而这在现实中是非常少见的“1 。 另一方面，如果公式( 3 8 ) 没有第一项，那么“飞翔”粒子的速度仅仅取决丁粒子的当前位置 币它们最好的历史位置。速度自身是没有记忆性的。假设在开始的时候，粒子，止好是整体最盘f 所在 的点，那么粒子粥以速度为0 “e 翔”这将保持粒子此次的位置不变，直剑出现新的一个晟妤点替 代粒子，。同时，每一个粒子将向自身虽好点和整体最好点的质心方向“e 翔”。冈此可以想像在没 有第一项情况r 的p s o 搜索过程，其搜索空间将在迭代中逐渐衰退，这类似丁局部搜索算法。只有当 全局最立，点包含在初始搜索空间内的时候，才有可能找到满意解。这样，最终解在很人_ f ! f ! 度上要依 赖丁| 初始化种群。这也说明了在没有第一项内容的情况f ，p s o 算法更多的显现的是局部搜索能力。 从兄一层意思米说，第一项内容使得粒子有一种扩展搜索空间的能力，即开拓能力( e x p l o r e a b i l i t y ) ，是一种全局搜索能力的表现。 在各类题的解决中，局部搜索和全局搜索都起着重要作_ h j 。对丁某一类优化问题的具体解决 中，我们应该权衡局部搜索和全局搜索的贡献“。y s h i 和e b e r h a r t 在1 9 9 8 年对微粒群算法引入了 惯性权重m “，并提出了在进化过稃中线性调整惯性权重的方法，以起到权衡全局搜索和局部搜索 能力。惯性权重冈子w 可以是个整数，也可以是以时间为变量的线性或非线性止整数。该方样已铍学 者们称为标准p s o 算法，这样公式( 3 8 ) ( 3 9 ) 就变为： o - i - 1 ) 2 h f ) + k o + 1 ) + c l + ，( f ) + ( 弓o ) 一x p ( f ) ) + c 2 + ( 巴( f ) 一( f ) ) ：( 3 8 ) j 。( ，+ 1 ) = 工，( f ) + v 。o4 - 1 ) ： ( 3 9 ) 当惯性权重w uj 2 1 时，式( 1 5 ) 与式( t 1 ) 相同，从而表明代惯性权重的微粒群算法是基本 微粒群算法的扩展，建议w 【f j 的取值范围为e o ，1 4 ，但实验结果表明当w 【，j 取 o 8 ，1 2 时，算法 收敛速度更快，而当w 【，j 1 2 时，算法则较多的陷入局部极值。惯性权重叭，) 表明微粒的原先的 速度能在多大的程度上得剑保留较大的w u j 值有较好的全局搜索能力，而较小的w 【f ) 则由较柱的 局部搜索能力。因此，随着迭代次数的增加，线性的减小惯性权重u ，就可以使得微粒群算法在 初期具有较强的全局收敛能力，而在晚期具有较强的局部收敛能力。当惯性权重眦j 满足： w ( ，) = 脚一( 所一n ) 面面t ( 3 1 2 ) 即w ( r ) 随着迭代线性地从川递减到甩( 通常m 2 1 2 ，月2 0 4 ) 时，从几个测试函数的测试结果米 看效果很好。等式( 3 1 2 ) 中的m a x _ c i r c l e t i m e s 为最人截j p 代数，对于惯性权重叭，) 来说，由 丁| 不同的问题，其每一代所需的比例关系并不相同，这样线性的递减关系并不是对所有的问题都 第三章几种进化算法 会最佳。义有学者提出了基丁：模糊系统的惯性权重的动态调整”。 3 3 5 改进的微粒群算法与遗传算法的比较 p s o 算法和其它的进化计算技术基木上是一样首先是初始化群，然后迭代求解。人多数进化 计算技术都是_ i j 同样的过程： 1 种群随机初始化： 2 对种群内的每一个个体计算适应度值( ( f i t n e s sv a l u e ) ； 3 种群根据适应值进行复制； 4 如果终r 条件满足的话，就停j p ，否则转步骤2 。 我们可以石到p s o 和g a 有很多共同之处。首先，微粒群算法与遗传算法相同，均使_ i j “群体” d 概念，h j 丁j 表示解空间中的一组个体集合。如果将微粒所经过的自身的最好位置。，看作是群体的组 成部分，则微粒群的每一代进化早现出弱化形式的“选择”机制。b a n a c h 提出的具有全局收敛性的 压缩映射遗传算法( c o n t r a c t m a p p i n g g e n e t i c a l g o r i t h m , 简称c m g a ) 就提出如果某一代种群的平均 适值相对于上一代没得剑增长，则不直接进入下一代，而是反复进行遗传操作，直到平均的适值得 剑增k ，才进入f 一代。显然，两者具有相类似的机制。其次，式( 3 8 ) 和( 3 1 0 ) 所描述的速度 进化方程与实数编码的遗传算法的算术交义算子相类似，通常，算术交义算子有两个父代个体的线 性组合成生两个子代个体，而在速度进化方程 即式( 3 8 ) 中，如果不考虑巧( f ) 项，则可将+ d 看 作是两个父代，即尸( r ) 和足( ) 的交义运算结果。从另一个角度，如果考虑( f ) 项，速度进化方 程也可以看什是一种变异算子，其变异的强度，取决于两个父代，即只( ，) 和0 ( f ) 间的距离。如果 我仃j 将微粒群算法的进化迭代理解为一个自适应的过程，则微粒新的位置( ，+ 1 ) 是在原先的位置 “ 根据速度，j v “7 动态调整的结果，它他同时保留和利用位置和速度信息，而遗传算法仅保 留和利川位置信息。所以微粒群算法的局部搜索能力强丁遗传算法，而遗传算法的全局搜索能力强 丁微粒群算法。两者作为进化计算的两个分支，在优化领域都有广泛的麻州前景。而且都使川适应 值米评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解。 但p s o 算法作一种进化计算技术，在编码方式上p s o 算法比g a 的算法简单 2 6 2 7 】，可以直接 根据被优化问题的进行实数编码。p s o 算法对于种群的初始化并不像g a 那样敏感，因为整个群体 并不是均匀移动的，而是每个粒子分别根据自己和同伴的经验来调整，这也使得p s o 在许多情况h 要比g a 更快的找剑最优解。另外p s o 算法中粒子可以记住先前的最好位置的。 3 4 基于量子行为的微粒群算法( q p s 0 ) 3 4 1 基于量子行为的微粒群算法简介 基丁量子行为的q p s o 算法是在经典的微粒群算法( p s o 算法) 的基础上改进形成它士要是结 合了量子物理的思想修改了p s o 的“进化”方法( 即更新粒子位置的方法) 在更新粒子位置时重点 考虑各个粒子的当前局部最优位置信息和全局最优位置信息具体方法见f 面“基丁姑子行为的微 粒群算法的运算过程”的描述 2 s 2 9 1 。 江南人学硕l 学位论文 _ _ - _ _ _ _ _ _ _ _ _ - _ _ _ _ _ - - _ _ _ _ _ _ _ _ _ - - _ _ _ _ _ _ _ _ _ _ - - _ _ _ _ - _ _ _ - _ _ _ _ _ _ _ _ - _ _ _ - _ _ _ _ _ _ _ - 3 4 2 基于量子行为的微粒群算法的运算过程 在q p s o 中粒子群按照f 面的二个公式移动位置 2 8 】： m 。州( r + ，) = 面1 萎m 只( ，) = ( - - 未z 差p 一) ，面1 各mf ：( 铣，面1 善m ( f ) ( f + 1 ) = f j ( t + 1 ) 乞( f ) + ( 1 一f j ( t + 1 ) ) x 巴( ，) ( 3 1 4 ) 也”1 ) 2 粥”1 ) + r 碱“) 砸“m 胁舭1 ) - x , j ( t ) i l n 赢) ( 3 1 5 ) 其中：l ( t + 1 ) = r a d f o ，“。( f + 1 ) = r a d f o ；数r a d f o 产生一个 o ，l 】之间服从均匀分布 的随机数，r a n d ( t + 1 ) 以一定的概率分别取一1 和l ，我们的方法是： r口一do+，=：1：量：radfo i n ( x ) 是x 的以1 0 为底的对数，m 表示粒子总数，d 表示粒子的维数，p ( r ) 表示第f 次迭代时第i 个 粒子的当前最佳位置，e ( f ) 表示第，次迭代时的全局最佳位置，这里m b e s t ( t + 1 ) 是粒子群中所有 粒子第f 次迭代时当前虽佳位置p 6 p 5 ，( ，) 的中间位置，p 只( f + 1 ) 为p ( ，) 和最( f ) 之间的随机点。 a ( t ) 为q p s o 的收缩扩张系数，它是q p s o 收敛的一个重要的参数，a ( t ) 的取值视情况而定，可以l 司定 不变，可以按照一定的方式动态变化。一般按照下式取值： “，) 钏_ ( m - n ) 。志 臼1 7 ) 即：a ( t ) 随着迭代线性地从m 递减剑n ，通常m = l , n = o 5 ，( 3 1 7 ) 式中m a x t i m e s 是迭代的最人 次数。 o p s o 的算法流程为： 步骤一、初始化：随机初始化m 个粒子的初始位置x ( ，并令各个粒子的当前 晟住位置为：p ( 0 ) = x ，( 0 ) ，令全局最佳位置为 名( 0 ) = m a x x l ( o ) ，x 2 ( o ) ，x ，( o ) ) ( 3 1 8 ) 步骤_ 二、根据目标幽数f ( x ) 计算公式计算粒子的目标函数值： 步骤二、按 ! r 式更新每个粒子的新局部最优位置p o + 1 ) 假设我们是是人化目标函数，( x ) ： 1 4 第三章几种进化算法 即圳= 般+ 毒甏黎瑟缴， 步骤四、按照r 式更新全局最优何置e a t + 1 ) 最( ，+ 1 ) = m a x p i ( t + 1 ) ，p 2 ( t + 1 ) ，。一，( f + 1 ) ( 3 2 0 ) 步骤五、根据公式( 3 1 3 ) 计算m b e s t ( t + 1 1 步骤人、根据公式( 3 1 4 ) 计算每个粒子随机点p p o + 1 ) 步骤七、根据公式( 3 1 5 ) 更新每个粒子的新位置，( f + 1 ) ； 重复执行步骤二至步骤七，直到满足算法终止条件( 算法终止条件一般取迭代次数达到一定的 值m a x t i m e s ) 。 3 4 3 基于量子行为的微粒群算法和经典微粒群算法的比较 q p s o 算法与传统的p s o 算法相比具有如f 优点： ( 1 ) 、参数个数少，q p s o 算法只有参数d ( f ) 的最人值m 和最小值n 需要根据具体问题进行调整 而p s o 算法需要根据具体问题进行调整参数：c l ，c 2 和a ( t ) 的最大值m 和最小值n ，这样就人大 地降低了程序参数的调整难度。 ( 2 ) 、它能够较好地收敛丁= 全局最优点，不易于陷入局部最优点，具有较强的全局搜索能力和局 部搜索能力，算法一开始的全局搜索能力强，而局部搜索能力相对较弱，随着迭代，其全局搜索能 力相对减弱，而局部搜索能力相对增强。 ( 3 ) 、鲁棒性好，即：q p s o 算法的稳定性明显优于己开发的各种p s o 算法。 ( d ) 、收敛速度快。q p s o 算法能够很快地收敛于全局最优点。 江南人学硕 。学位论文 第四章进化算法的并行化实现及其应用 4 1 进化算法的并行策略 对并行优化算法的研究主要我们主要从两个方面进行研究： 一、实现方案 伴随着优化算法的不断发展，并行优化算法及其实现的研究也变得十分重要。一般来说，优化算 法中目标函数的计算最费时间，所以如何提高优化算法的运行速度显得尤为突出。由丁我们所研究 的优化算法具有内在并行机制，其并行处理是很自然的解决途径。 目前并行优化算法的实现方案大致可分为三类： ( 1 ) 全局犁一主从式模型( m a s t e r - s l a v em o d e l ) 并行系统分为一个主处理器和若干个从处理器。 土处理器监控整个种群，及全局统计操作p o j ；各个从处理器接受来自主处理器的个体进行优化，并 计算适廊度，再把计算结果传给土处理器。 ( 2 ) 独立刑一粗粒度模r 弘( c o a r s e g r a i n e dm o d e l ) 将种群分成若干个子群并分配给各自对应的处 理器，每个处理器不仅独立计算适应度，而且独立进行各种优化操作，还要定期地相互传送适麻度 展好的个体，从而加快满足终止条件的要求。 ( 3 ) 分散硝细粒度模帮( f i n e g r a i n e dm o d e l ) 为种群中的每一个个体分配一个处理器，每个处 理器进行适麻度的计算，优化操作在相邻的个体或单独的个体中进行。 啊二、迁移策略 迁移( m i g r a t i o n ) 是白行遗传算法后引入的一个新的算子它是指进化过拌中子群体间交换个体的 过程，一般的迁移方法是将子群体中最好的个体发给其它的子群体，通过迁移可以加快较好个体在 群体中的传播，提高收敛速度和解的精度p “。与单种群相比只需要较少的个体评价计算j ：作昔。冈 此，即使是采_ 【 j 单一处理器的计算机上以串行方式( 伪并行) 实现并行算法也能产生较好的结果。因 此迁移算子的采用，使并行算法更适合丁二全局寻优并且计算茸较小。以基丁| 粗粒度模型的并行算 法为例，其迁移策略可分为以f 两种： ( 1 ) 一传多每个处理器对应有若干个相邻处理器，每个处理器产生新一代个体后，都将自己最好 的一个个体传送给其所有相邻处理器，并且接受来白相邻处理器的最好的个体将这些个体与自己 的个体同时考虑，淘汰适应度筹的个体。 ( 2 ) 一传一每个处理器都将自己晟好的个体仅传给与之相邻的一个处理器，同时增加两个参数： 一是s e n dr a t e 决定处理器之间通讯的频率，如s e n d - r a t e = 3 时表示当进化或迭代次数是3 的倍数时， 各处理器之间相互传送个体；二二是s e n db e s t 决定每次传送给最好个体的数目，如s e n db e s t = 5 时表 示每个处理器把晟好的前5 个个