（基础数学专业论文）一种改进的粒子群优化算法.pdf

摘要 自上世纪8 0 年代以来，智能优化算法( 如人工神经网络、遗传算 法等) 通过模拟或揭示某些自然现象和过程而发展起来，为优化理论 提供了新的思路和手段。粒子群优化算法( p s 0 算法) 源于鸟群和鱼群 群体运动行为的研究，是一种基于种群搜索策略的自适应随机算法， 是进化计算领域中的一个新的分支。它的主要特点是简单、收敛速度 较快、没有很多参数需要调整，且不需要梯度信息，在工程实践中表 现出巨大潜力，现已广泛应用于函数优化、神经网络、模糊系统控制、 模式识别等多个领域。 与其他进化算法类似，粒子群算法也需要一个群体，每个个体称 之为粒子。粒子通过自身和群体的最优位置来更新其位移和速度，从 而在解空间移动。但是，粒子群优化算法仍存在易陷入局部最小、且 搜索精度不高等缺点。 本文从p s o 算法的基本原理、参数选取、边界条件、社会行为分 析、混合算法及应用、国内外研究的现状与进展等方面做了较为系统 的论述，对混沌理论，模拟退火算法和郭涛算法，都作了简单介绍。 通过对p s o 算法细致的研究，在算法的初期，引入了混沌理论，优化 初始种群；在粒子更新过程中，采用混沌变异产生子群与模拟退火两 种策略，引导粒子更新：针对粒子群算法易陷入最优的缺点，在算法 中融合郭涛算法思想，通过子空间随机产生粒子，丰富了粒子的多样 性，避免了粒子群的早熟收敛。实验结果表明，新算法不仅具有更好 的收敛精度和更快的收敛速度，而且能更有效地进行全局搜索，在求 解多峰函数最优解的问题中，也有很好的性能。 关键词：混沌、模拟退火算法、郭涛算法、粒子群算法 a b s t r a c t s i n c e 舭1 9 8 0 s ，i n t e l l i g e n to p t i l l l i z a t i o na l g 嘶恤ns u c ha sn e u r a l l l e r k ，g ah a sb e e i ld e v e l o p e d 锄肌曲t h es i 砌l 撕o no fn a t u r ea 1 1 d s o c i a lp r o c e s sa n di tp r e s e n t san e w 印p m a c hf o f0 p t i m i z 撕o nn l e t h o d s p a n i c l es w 锄叩t i i n i z a t i o i l ( p s 0 ) i si n s p i r e db ys o c i a lb e h a v i 何o f b i r d f l o c k i n g0 rf i s hs c h o o l i n g i ti sap o p u l a t i o n - b a s e d ，s e l f 咖t i v es e a r c h o p t i i i l i z a t i o nt e c h n i q u e p s oi ss i m p l ei nc o n o e p t ，f e wi l lp a 聊n e t e r s ，a | l d e a s yi ni n 巾l e 眦n t a t i o n a sal ( i n do fi n t e l l i g e i l ta l g o r i 恤：1 1 ，i tc a i lb eu s e d t 0s o l v ev 耐o u so p t i i i l i z a t i o np r o b l e 璐髓ds h o w s 印a tp o t e i l 廿a li n p r a c t i c e n o w ，i th a sb e w i d e l y 印p l i e d i n 硼m yo m e ra r e a s ，s u c h 弱 丘m c t i 叩t i m i z a t i o n ，耐i f i c i a ln e u r a ln e 觚o r k 锄d 舭掣s y s t 锄c o n 仃0 1 p s oi ss i m i l a rt og ai nt l l a tm es y s t e mi si n i t i a l i z e dw i t ha p o p u l a t i o no fr 觚d o ms o l 以o n s ， a n d她 p o t e n t i a ls o l 确o i l s ， c a l l e d p 口砒切，a r et h 饥”n o w n t l u g ht h ep r o b l 锄s p a c e e a c hp a n i c l e k e 印s 仃a c ko fi t sc o o r d i n a t e si nt h ep b l 锄s p a c ew h i c ha r e 弱s o c i a t e d w i lt h eb e s ts o l u t i o 璐i th a sa c h i e v e ds of 打锄do b t a i n e ds 0f h b ya l l y p 矾i c l e sm m ep o p u l a t i o n 1 h ea t t r a c t i v ec h a r a c t e ro fp s oc o n c 印ti s q v i t es i 瑚p l ea n de a s yt oi m p l e m e n t t h i sp a p e rm a k 璐as y s t e m a t i cd i s s e r t a t i o no nt h eb a s i cp r i n c i p l eo f p s oa l g 嘶t h m ，p a r a l n e t e r o p t i o n s ，b o u i l d a 巧c 0 n d i t i o n ， s o c i a l b 吐l a v i o ra n a l y s i s ，h y b r i da l g o r i t l l i i la n di t su s e ，a n dt h ec 1 加e n ts t a t e a 1 1 dd e v e l o p m e n to fn a t i o n a l 锄di n t e l m t i o m lr e s e a r c h i ta l s ob r i e n y i n 仃o d u c e st h ec h a o sn e o 碍，s t i 咖l a t e da m e a l i n ga l g 嘶恤玛觚d ( 沁o t a oa 1 9 耐t h m 曲t h e e x q u i s i t er e s e a r c ho fp s oa l g o r i t h i n ，i t i n 仃o d u c e sc h a o s1 1 1 e o r ya tt h eb e g i m i n go ft h ea l g 嘶t 1 1 1 1 1t 0o p t i i n i z e h t h eo r i g i n a lg r o u p s ；i tu s e st h es 缸a t e 9 1 e so 士p r o d u c m gt n en l c n e 锄d 一 1 j 1t s t i m u l a t e d 锄e a l i n gb yc h a o sv a r i a t i o nt oi n d u c tt h ep a n i c l e sr e l l o v a t i o n i nt h en l i d d l e ；i te n l b e d sg u o 切l oa l g 嘶m mt oa b t a i n 础m y0 p t i l n i z a t i o n i nm e 肌d 7 r h er e s u l to fm ee x p 嘶m e n to nd e v e l o p e da l g 耐伽nw i t hb a s e 劬c t i 叽s h o w s 1 a tt h e1 1 e wa l g 耐t 1 1 mn o to n l yp o s s e s s e sb e t t e r c o n v e r g e n tp r e c i s i o na 1 1 df a s t e rc o n v e r g e n ts p e e d ，b u ta l s om a k e sm o r e e f f e c t i v eo v e r a l ls e a r c h ，e s p e c i a l l yw h i l es 0 1 讥n gt h ep r o b l e m so f m u l t i p e a kr m c t i o n so p o t i l i z a t i o n k e yw o r d s ： c h a o t i cs t i m u l a t e da r u l e a l i n ga 1 9 0 r i m m ( 沁。切0 a l g 耐t h m p 矾i c l e ss w a r r no p t i r n i z a t i o na 1 9 耐m m i i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 8 1 i 幼加汐年f 2 月尸日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密囱。 f( 请在以上相应方框内打“ ) 作者签名：气l 目幼日期：妒扩年户月，口日 导师签名： 薯多么日期舯，二月厂日 一种改进的粒子群优化算法 1 1 课题背景 1 绪论 优化是个古老的课题，它所研究的问题是在众多方案中寻找最优 方案。长期以来，人们对优化问题进行探讨和研究。早在1 7 世纪， 英国n e w t o n 和德国l e i b n i t z 发明的微积分就蕴含了优化的内容。而 法国数学家c a u c h y 则首次采用梯度下降法解决无约束优化问题，后 来针对约束优化问题又提出了l a g r a n g e 乘数法。人们关于优化问 题的研究工作，随着历史的发展不断深入。但是，任何科学的进步都 受到历史条件的限制，直到二十世纪四十年代，由于科学技术突飞猛 进地发展，尤其是高速数字计算机日益广泛应用，使优化问题的研究 不仅成为一种迫切需要，而且有了求解的有力工具。因此，优化理论 和算法迅速发展起来，形成一门新的学科。至今已出现线性规划、整 数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许 多分支。这些优化技术在实际应用中正发挥越来越大的作用。 随着人类生存空间的扩大，以及认识世界和改造世界范围的拓 宽，常规优化方法如牛顿法、共扼梯度法、模式搜索法、单纯形法、 r o s e n b r o c k 法和p o w e l l 法已经无法处理人们所面对的复杂问题，因 此高效的优化算法成为科学工作者的研究目标之一。 二十世纪八十年代以来，一些新颖的优化算法得到了迅速发展。 人工神经网络( a n n ) 在一定程度上模拟了人脑的组织结构心1 ：遗传算 1 高校教师在职硕士学位论文 法( g a ) 借鉴了自然界优胜劣汰的进化思想1 ：蚁群优化算法( a c 0 ) 受 启发十自然界蚂蚁的寻径方式h 1 ：模拟退火( s a ) 思路源十物理学中固 体物质的退火过程晒3 ：禁忌搜索( t s ) 哺1 模拟人类有记忆过程的智力过 程。这些算法有个共同点：都是通过模拟或揭示某些自然界的现象和 过程得到发展，在优化领域，有人称之为智能优化算法( i n t e l l i 窜e n t o p t i m i z a t i o na 1 9 0 r i t h m s ) 。 本文研究的粒子群优化算法( 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 9 9 5 年由美国社会心理学家k e n n e d y 和电气工程师 e b e r h a r t 共同提出的 们，其基本思想是受他们早期对鸟类群体行为研 究结果的启发，并利用了生物学家f r a n kh e p p n e r 的生物群体模型。 p s o 与g a 有些相似之处。首先，它们都是基于群体的优化技术，亦 即搜索轨道有多条，显示出较强的并行性。其次，无需梯度信息，只 需利用目标的取值信息，具有很强的通用性。但是，p s o 比g a 更简 单、操作更方便。因而p s o 算法从诞生起，就引起了国内外学者的广 泛关注，并掀起了该方法的研究热潮，且在诸多领域得到了成功应用。 p s o 的发展历史尚短，还存在很多问题有待解决，例如参数选取、早 熟收敛、后期收敛速度慢、理论基础薄弱等。 1 2 国内外研究现状和进展 p s 0 是计算智能领域除蚁群优化算法外的另外一种群体智能算 法。它同遗传算法类似，通过个体间的协作和竞争实现全局搜索。系 统初始化为一组随机解，称之为粒子。通过粒子在搜索空间的飞行完 成寻优，在数学公式中即为迭代，它没有遗传算法的交叉以及变异算 ， 一种改进的粒子群优化算法 子，而是粒子在解空间追随最优的粒子进行搜索。 自p s 0 提出以来，由于它的计算快速性和算法本身的易实现性， 引起了国内外众多研究者们的兴趣，他们提出了各种改进的p s o 算 法。本文归纳了主要的几类改进的p s o 算法：基于参数因子的改进； 基于邻域与拓朴结构的改进；融入其他算法思想的改进：建立非数值 问题模型的改进。 1 2 1 基于参数因子的改进 1 2 1 。l 增加惯性因子的改进粒子群算法( 标准p s o 算法) 在求解实际应用的各种问题中，对算法的局部搜索能力和全局搜 索能力的比例要求不尽相同，甚至对同一个问题，在进化的不同阶段， 对它们的要求也可能是不一样的。基于这么一个事实，y u h u is h i 等 提出了带惯性因子的p s o 算法阳1 。进化方程为： k ( f + 1 ) = 彩k ( f ) + q 加刀d ( ) ( 号一五( f ) ) + 吃r 口行d ( ) ( 只一墨( f ” ( 1 一1 ) 置o + 1 ) = 誓( f ) + k o + 1 ) ( 1 2 ) 以上算式经常被学者们引用作为标准p s o 算法。其中惯性因子彩 表征粒子惯性大小：对原来速度的保持程度。y u h u is h i 在文中建议彩 的取值在 o ，1 4 。而在实验结果表明的取值在 o 8 ，1 2 之间算法收 敛速度更快一点。彩较大时，具有较强的全局收敛能力，缈较小时具 有较强的局部收敛能力，因此国有点类似于模拟退火中的温度，随着 迭代次数的增加，彩的值应该不断地减小，从而使得在算法开始初期， 要求有较强的全局搜索能力，在后期，要求有较强的局部搜索能力， 以提高算法的整体性能。y u h u is h i 在文献 9 中提出了国在o 9 到 1 高校教师在职硕士学位论文 o 4 之间线性递减的策略： 国o ) = o 9 一o 5 木f 五z 批m 6 盯 ( 1 3 ) 其中t 为当前迭代次数m a x n u m b e r 是最大迭代次数。通过对四个 b e n c h m a r k 函数的测试结果表明算法收敛性能有了明显的改进。但是， 惯性因子在进化的过程中线性递减的策略往往不能反映实际的优化 算法搜索过程，为此文献 1 0 提出了一种基于模糊系统的惯性因子动 态调整策略，取得了良好的效果。 1 2 1 2带有收缩因子的改进p s 0 算法 加速因子c 。和c ：决定了粒子本身经验信息和其他粒子的经验信息 对于粒子运行轨迹的影响，反映了粒子样之间的信息交流。设置较大 的c 。值，会使粒子过多的在局部范围内徘徊；而较大的c 。值，则又 会促使粒子过早收敛到局部最小值。为了更好地朝着最优方向移动， 文献 1 1 对于加速因子做了一些较为深入的研究，并提出了相应的改 进算法。实验结果表明改进后的算法确实加快了算法的收敛，在单峰 问题的测试中表现优异，但算法却容易陷入局部最优，并且在多峰值 函数的测试中容易产生早熟。 为了有效地控制粒子的飞行速度，使算法达到全局探测与局部 开采两者间的有效平衡，c 1 e r c 构造了引入收缩因子的p s 0 算法的模 型n 2 1 ，将p s o 速度方程改为： k ( f + 1 ) = + k ( + q ，i ( 助一嘞) + c 2 眨( p 一) ) ( 1 4 ) 式( 1 4 ) 中：k 为收缩因子，k _ 西= 王高c = c - + c z ，且 c 4 。实验结果表明k 比v 。更能有效地控制粒子速度的振动，同时也 一种改进的粒子群优化算法 增强了算法局部搜索的能力。 1 2 1 3 保证全局收敛的s p s o 算法 曾建潮等人提出了一种保证全局收敛的s p s o 算法n 朝，在标准 p s o 算法中，当国= o 时，( 卜1 ) ( 卜2 ) 描述的进化方程为 五o + 1 ) = 五( ，) + q m 刀d ( ) ( 曰一五( f ) ) + c 2 ，口万d ( ) ( 乞一五( f ) ) ( 卜5 ) 与基本p s o 算法相比，( 1 5 ) 式描述的进化方程使得全局搜索能 力减弱，而局部搜索能力加强。同时，当乃，= e = 名时，第j 个微粒 将停止进化。为了改善( 1 5 ) 式的全局搜索能力，可保留p g 作为微粒 群的历史最好位置，而在搜索空间中重新随机产生微粒j 的位置工m 。， 其它微粒i 以( 1 5 ) 式进化产生屯+ ( i j ) ，作如下改进 e = _ 川 ( 卜6 ) 只乏，馄手毵：l ， 7 ， 若名= e ，则随机产生的微粒j 处于历史最好位置，无法按( 1 5 ) 式进化，继续在搜索空间中随机产生，其它微粒在更新0 、霉后按( 1 5 ) 式进化；若名哆，且名未更新，则所有微粒均按( 1 5 ) 式进化； 若足弓，且弓已更新，即存在k j ，使得故川= 只= 弓，则微粒k 停止进化，在搜索空间中重新随机产生，其余微粒在更新只、霉后按 ( 1 5 ) 式进化。这样在进化的某些代，至少有一个微粒j 满足 = 弓= 弓，也就是说，至少有一个微粒需在搜索空间中重新随机产 生，这样就势必增强了全局搜索能力。上述算法称之为随机p s o 算 法( s p s o ) ，并证明了收敛的条件为：o q + c 2 2 。 1 2 2 基于邻域结构的改进 高校教师在职硕士学位论文 基本粒子群中的l b e s t 模型是根据粒子的下标将粒子样体分制 成若干个相邻的区域，p n s u g a n t h a n y 于1 9 9 9 年提出了一种基于 动态邻域思想的p s o 算法n 钔。其思想是在算法开始阶段，每个个体的 邻域为其自身，随着进化代数的增长，其邻域也在不断增大直至到整 个种群，该算法不论维数多少，其收敛性能均比基本p s o 算法要好。 j k e n n e d y 对于基本p s o 算法的简单邻域结构提出了几种改进 的邻域结构，如环形、随机环形、轮形、随机轮形等结构，分析了粒 子间的信息交流，对于算法速度和精度的调整起到了平衡作用，在一 定程度上提高了算法效率。 1 2 3 导入其他算法思想的改进 高鹰等n 5 3 将混沌寻优思想引入微粒群算法中，提出了混沌微粒群 算法。该算法利用混沌运动的随机性、遍历性和规律性等特性，对当 前微粒群体中的最优微粒进行混沌寻优，并利用寻优结果随机替换微 粒群中的某一个微粒。该算法实现简单，能够改善算法摆脱局部极值 点的能力，并能够提高算法的收敛速度和精度。 x i e 等n 町根据耗散结构的自组织性，将热力学中“熵 的概念引 入微粒群，提出一种耗散微粒群算法。该算法通过附加噪声持续为微 粒群引入负熵，从而使群体不断进化。从外部环境中引入负熵，使得 系统处于远离平衡态的状态，又由于群体中存在内在的非线性相互作 用，从而形成白组织耗散结构，使微粒群能够“持续进化”。 a n g e l i n e n 刀将进化规划中使用的竞赛选择方法引入微粒群算法。 该混合算法根据个体当前位置的适应度，将每个个体与其它个体进行 一种改进的粒子群优化算法 比较，然后依据比较结果对整个群体进行排序，用微粒群中较好的一 半替换群体中较差的一半，同时保留每个个体所记忆的个体最优位 置。选择方法的引入使得该混合算法具有更强的开发搜索能力，加快 了对当前较好区域的开发过程，使得收敛速度较快，但也增加了陷入 局部解的可能性。 昌振肃等n 胡将遗传算法中的变异引入微粒群算法，提出了一种新 的基于群体适应度方差自适应变异的微粒群算法。该算法在运行过程 中根据群体适应度方差以及当前最优解的大小来确定当前最佳微粒 的变异概率，变异操作增强了微粒群算法跳出局部最优解的能力。 窦全胜等人提出一种基于模拟退火的p s o 算法和有分工策略的 p s o 算法n 引。针对标准粒子群算法容易陷入局部最优的缺陷，提出将 模拟退火引入并行p s o 算法中。测试的结果表明，该算法在温度变换 相对缓慢时，能够搜索到较好的结果，而增加基木p s o 算法的迭代次 数时不能收到这样的效果。这种改进p s o 算法在解决无约束问题上具 有较强的应用价值。 此外，高尚等结合遗传算法、蚁群算法和模拟退火算法的思 想，提出用混合微粒群算法来求解著名的离散优化问题一旅行商( t s p ) 问题，所提2 4 种混合粒子群算法的效果都比较好，其中交叉策略d 和变异策略f 的混合微粒群算法的效果最好，而目简单有效。 1 2 4 建立非数值问题模型的改进 由于p s o 简单的位置和速度算式，对数值化的问题很容易表达出 来，因此处理数值化问题的各种p s o 改进算法得到了较大的发展；而 7 高校教师在职硕士学位论文 对于非数值化问题而言，不能直接用位置和速度把问题表达出来，因 此目前处理非数值化问题的p s o 算法研究相对滞后。我们认为：要使 用p s o 算法处理非数值化问题，关键是要建立与具体问题相适应的新 的p s o 算法模型，使得这个模型的位置和速度两个量以及它们的运算 可以清晰地把非数值化问题描述出来。 k a n g p i n gw a n g 等人提出一种求t s p 问题的p s o 改进算法乜。 把粒子位置直接定义t s p 问题的解，即是结点的序列，而将速度定义 为两个结点之间的交换集，并将它们之间的加法算子定义为对结点序 列( 粒子位置) 依次交换交换集( 速度) 中的交换子。文章也做出了仿真 试验：粒子个数设置为l o o ，在迭代2 0 0 0 0 次，可以求解到1 4 个城市 的最佳路径。实验结果可看出，该改进算法求解t s p 问题效果不佳。 高海兵等人提出了一种适合求解离散问题和组合优化问题的广 义的粒子群模型陇1 。该模型根据优化问题的特点设计其粒子的更新策 略，可以实现与已有方法的融合。文章以t s p 问题为例，针对遗传算 法解决该问题的成功经验，使用遗传算子作为模型的更新算子，进一 步提出基于遗传操作的粒子群优化模型，并以i n v e r o v e r 算子作为 模型中具体的遗传操作设计了基于广义模型的t s p 算法，文中做了对 广义模型p s o 算法和采用相同遗传操作的遗传算法进行了对比实验。 实验结果表明：广义模型的p s o 求解的质量和收敛稳定性均优于遗传 算法。 微粒群算法是一种新型的群体智能算法，由于其在求解复杂优 化问题方面的优势，在很多工程领域，如工程设计与优化、电力系统 矗 种改进的粒子群优化算法 领域、机器人控制和工业生产优化领域等取得了较为成功的应用。但 微粒群算法的研究还处于起步阶段，许多方法大多处于性能验证和实 验阶段，缺乏强有力的理论支持，微粒群算法在理论上的不断完善以 及应用领域的拓展等还需要更深入的探索。 1 3 本文的主要成果 在本文中，对p s o 算法作了较细致的研究，主要有以下三方面创 新： 1 ) 在粒子群算法粒子的更新过程中，当新粒子的适应值优于原 粒子的适应值时，对新粒子进行混沌变异，产生一个子群，在子群中 选取更优秀的粒子来取代原粒子。此算法命名为c - p s o 算法。 2 ) 在t p s 0 算法的基础上，引进了模拟退火思想，增加了算法 的稳定性。此算法命名为t c ? s o 算法。 3 ) 在粒子群算法粒子更新的过程中，当新粒子的适应值劣于原 粒子的适应值时，记录粒子变坏的迭代次数，当迭代次数超过某个预 设值时，引入郭涛算法的子空间搜索，利用子空间搜索的遍历性来帮 助粒子脱困。此算法命名为g 耽p s o 算法。 通过实验证明，本文的混合算法能很好地融合粒子群算法与郭涛 算法的优点，整体性能较粒子群算法和郭涛算法有了很大提高。与其 他类似优化算法比较发现，本文的混合算法性能优于现阶段大部分其 他优化算法。 9 高校教师在职硕士学位论文 1 4 本文的组织 本文共分为六章： 第一章绪论部分，对粒子群算法研究的现状和进展做了简要介 绍。 第二章较详细的介绍了标准粒子群算法。 第三章简单介绍了混沌理论，结合混沌原理对标准粒子群算法进 行了改进。在算法初始化阶段，针对算法对初始粒子的敏感依赖，利 用混沌序列选取初始粒子，再择优产生种群；在算法前期，针对粒子 群前期局部寻优能力不强的特点，在粒子接受新的较优解时，对新解 作混沌变异处理，形成一个子群，通过子群内部的竞争，选取较强的 作为粒子的更新对象。改进后，算法收敛速度明显加快。 第四章简单介绍了模拟退火算法，在第三章混沌粒子群算法的基 础上，融入了模拟退火思想，对粒子在接受坏解时作了程度上的限制； 算法的稳定性也得到了加强，避免了算法的早熟收敛。 第五章较详细地介绍了郭涛算法，并将郭涛算法与第四章所改进 的算法进行融合，得到了一种新的优化算法。 第六章对本文作了一个简要的总结，回顾了本文所取得的成果， 指出了文章的一些不足，并对以后的研究方向提出了自己的几点看 法。 1 0 一种改进的粒子群优化算法 2 粒子群算法 微粒群算法( p s o ) 是由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 算法 笙 寸o 2 1 算法原理 微粒群算法与其它进化类算法相类似，也采用“群体 与“进化 的概念，同样也是依据个体( 微粒) 的适应值大小进行操作。所不同的 是，微粒群算法不像其它进化算法那样对于个体使用进化算子，而是 将每个个体看作是在n 维搜索空间中的一个没有重量和体积的微粒， 并在搜索空间中以一定的速度飞行。该飞行速度由个体的飞行经验和 群体的飞行经验进行动态调整。 设：x i x 舭，一，x h ) 为微粒i 的当前位置； k 却n ，一，v 缸) 为微粒i 的当前飞行速度； e 劬，一，p i n ) 为微粒i 所经历的最好位置，也就是微粒i 所经历过的具有最好适应值的位置，称为个体最好位置。对于最小化 问题，目标函数值越小，对应的适应值越好。 1 1 高校教师在职硕士学位论文 为了讨论方便，设f ( x ) 为最小化的目标函数，则微粒i 的当前 最好位置由下式确定： 即爿髫觏筠蒜的 协1 ) 设群体中的微粒数为s ，群体中所有微粒所经历过的最好位置为 p g ( t ) 称为全局最好位置。则 匕( t ) r ( t ) ，e ( t ) ，- 只圳媲( 1 ) ) = 劬 矾( t ) ) ，妃( t ) ) ，媳( t ) ) ) ( 2 2 ) 有了以上定义，基本微粒群算法的进化方程可描述为： v 日( t + 1 ) 2 飞( t ) 。( t ) ( p 日( t ) 喂日( t ) ) + c z l j ( t ) ( p 舀( t ) - 飞( t ) ) x ( t + 1 ) 2 x # ( t ) + v 日”1 ) ( 2 3 ) ( 2 4 ) 其中：下标“j ”表示微粒的第j 维，“i ”表示第i 个粒子，“t ” 表示第t 代，c 。，c z 为加速常数，通常在o 一2 间取值，与口u ( o ，1 ) ， 砭口u ( 0 ，1 ) 为两个相互独立的随机函数。 从上述微粒进化方程可以看出，c 。调节微粒飞向自身最好位置方 向的步长，c ：调节微粒向全局最好位置飞行的步长。为了减少在进化 过程中，微粒离开搜索空间的可能性，v 。，通常限定于一定范围内，即 v ；， 一v v 。) 如果问题的搜索空间限定在 一x 。，x 。 内，则可设 定v 。= k x 。，o 1 k 1 o 。 基本微粒群算法的初始化过程为： 1 ) 设定群体规模n ； 2 ) 对任意i ，j ，在 - x 一，x 一】内服从均匀分布产生x t j ： 一种改进的粒子群优化算法 3 ) 对任意i ，j ，在 一v 一，v 咏】内服从均匀分布产生v t j ： 4 ) 对任意i ，设e = x ；。 2 2 算法参数 1 ) 粒子种群大小m ：粒子种群大小的选择视具体问题而定，但是一 般设置粒子数为2 0 一5 0 。其实对于大部分的问题l o 个粒子已经足够 可以取得很好的结果，不过对于比较难的问题或者特定类型的问题， 粒子数也可以取到1 0 0 或2 0 0 。 2 ) 粒子的长度n ：即是问题解空间的维数。 3 ) 粒子的最大速度v 嘲：粒子的速度在空间中的每一维上都有一个 最大速度限制值v m a x ，用来对粒子的速度进行钳制使速度控制在 【v 蛳，v 一】范围内，决定问题空间搜索的粒度。该值一般由用户自己 设定。v 傩是一个非常重要的参数。如果v 懈值太大，则粒子们也许 会飞过优秀区域：另一方面如果v 眦值太小，则粒子们可能就无法对局 部最优区域以外的区域进行充分的探测。实际上，它们可能会陷入局 部最优，而无法移动足够远的距离跳出局部最优达到空间中更佳的位 置。假设搜索空间的第d 维定义为区间【x d 峨，+ x 蛳】，则通常 。豇，o 1 k o 2 ，每一维都用相同的设置方法。 4 ) 加速常数q 、巴：分别调节向，和方向飞行的最大步长，决 定粒子个体经验和群体经验对粒子运行轨迹的影响，反映粒子群之间 的信息交流。 5 ) r a n d ( ) ：是介于 o ，1 之间的随机数。 6 ) 迭代终止条件：一般设为最大迭代次数t m a x 、计算精度占或最 3 高校教师在职硕士学位论文 优解的最大凝滞步数t 。 2 3 算法边界条件 通常工程应用中需要限制可能的实际空间。以下是几种设置边界 的方法： 1 ) 吸收墙：在某维上粒子撞上解空间的边界，令该维的速度为o ， 粒子将朝着允许的解空间运动。在此意义上，边界墙吸收了企图脱离 解空间的粒子的能量。作者采用此种方法。 2 ) 反射墙：在某维上粒子撞上解空间的边界，粒子朝着解空间反 射。 3 ) 不可见墙：允许粒子无约束运动。但是，冲出解空间的粒子将不 计算适应值。该技术仅评估在解空间内的粒子，从而节省了计算时间 且不干涉粒子的自然运动。 2 4 算法流程 1 ) 初始化粒子群：给定群体规模m ，解空间维数n ，随机产生每个粒 子的位置五、速度形。 2 ) 用适应度函数厂( x ) 分别计算每个粒子的当前适应值。 3 ) 更新个体极值：对每个粒子的适应值进行评价，即将第i 个粒子 的当前适应值厂( 墨) 与该粒子的个体极值n 的适应值进行比较，若前者 占优，则更新觑，否则保持a 不变。 4 ) 更新全局极值：从所有忍中选出最好的，作为全局极值名。 5 ) 更新速度和位置：通过公式( 2 3 ) ( 2 4 ) 来更新每个粒子的速度 1 4 一种改进的粒子群优化算法 k 和位置z 。 6 ) 检查是否满足中止条件，若满足，则退出；否则，转至步骤2 ) 。 2 5 算法时间复杂度分析 现分析2 4 节算法的步骤： 1 ) 需要对m 个粒子进行初始化，而且每个粒子又是n 维，其时间 复杂度即为o ( m ； 2 ) 对m 个粒子通过适应度函数( 基准测试函数) 计算适应值，而适 应度函数的复杂度一般都是o ，所以其时间复杂度为o ( m ； 3 ) 对m 个粒子更新个体极值，时间复杂度为o ( m ) ； 4 ) 从1 1 1 个个体极值中选出最好的那个，时间复杂度也为o ( m ) ； 5 ) 需要对每个粒子的每个维都更新速度和位置，因此其时间复杂 度为o ( m n ) ； 6 ) 判断终止条件，为常数时间。 从以上分析可以看出，2 ) 6 ) 步骤中的最大时间复杂度为o ( m 】町。 我们假设算法的迭代次数为t ( 可以是：用户设定的最大迭代次数、为 了达到计算精度所需要的迭代次数或当最优解达到最大凝滞步数t 时的迭代次数等) ，那么循环2 ) 一6 ) 后的时间复杂度为o ( t m n ) ，其大 于步骤( 1 ) 的时间复杂度o ( m n ) ，所以原始p s o 算法的时间复杂度即 为o ( t m n ) 。 2 6 社会行为分析 在( 2 3 ) 式所描述的速度进化方程中，其第一部分为微粒先前的 1 5 高校教师在职硕士学位论文 速度：其第二部分为“认知”部分，因为它仅考虑了微粒自身的经验， 表示微粒本身的思考。如果基本微粒群算法的速度进化方程仅包含认 知部分，即： v i j ( t + 1 ) 2v ( t ) + c ，l j ( t ) 0 日( t ) x 毋( t ) ) ( 2 5 ) 则其性能变差。主要原因是不同的微粒间缺乏信息交流，即没有 社会信息共享，微粒间没有交互，使得一个规模为n 的群体等价于运 行了n 个单个微粒，因而得到最优解的概率非常小。 ( 2 3 ) 式的第三部分为“社会 部分，表示微粒间的社会信息共 享。若速度进化方程中仅包含社会部分，即： v ；| j ( 什1 ) = k ( t ) + c ：岛( t ) q 面( t ) 一x ；j ( t ) ) ( 2 6 ) 则微粒没有认识能力，也就是“只有社会( s o c i a 卜o n l y ) ”的模型。 这样，微粒在相互作用下，有能力到达新的搜索空间，虽然它的收敛 速度比基本微粒群算法更快，但对于复杂问题，则容易陷入局部最优 点。 k e n n e d y 以x o r 问题的神经网络训练为例进行了仿真实验，证 明了上述结论。 总之，基本微粒群算法的速度进化方程由认识和社会两部分组 成。虽然目前的一些研究表明，对一些问题，模型的社会部分显得比 认识部分更重要，但两部分的相对重要性还没有从理论上给出结论。 2 7 两种基本进化模型 在基本p s 0 算法中，根据直接相互作用的微粒群定义可构造p s 0 算法的两种不同版本，也就是说，可以通过定义全局最好微粒( 位置) 1 一种改进的粒子群优化算法 或局部最好微粒( 位置) 构造具有不同社会行为的p s o 算法。 2 7 1g b e s t 模型( 全局最好模型) g b e s t 模型以牺牲算法的鲁棒性为代价提高算法的收敛速度，基 本p s 0 算法就是该模型的具体实现。在该模型中，整个算法以该微粒 为吸引子，将所有微粒拉向它，使所有微粒将最终收敛于该位置。这 样，如果在进化过程中，该最好解得不到有效地更新，则微粒群将出 现类似于遗传算法中的早熟现象。为了讨论方便，将p s o 的进化方程 重新表述如下： p g ( t ) p o ( t ) ，p l ( t ) ，一，p i ( t ) i 蚌( t ) 阄i n 蛾( t ) ) ，蜗( t ) ) ，一，媳( t ) ) 2 7 ) 、( t + 1 ) 2 = 、( t ) + c ( ) b i j ( t ) - x 目( t ) 】+ c z 砀( t ) b 商( t ) x i j ( t ) ) 】 ( 2 8 ) 其中，p g ( t ) 称为全局最好位置，对应于称之为全局最好微粒所处 的位置。 2 7 2l b e s t 模型( 局部最好模型) 为了防止g b e s t 模型可能出现的早熟现象，l b e s t 模型采用多吸 引子代替g b e s t 模型中的单一吸引子。首先将整个微粒群分解为若干 个子群，在每一子群中保留其局部最好微粒p i ( t ) ，称之为局部最好 位置或邻域最好位置。假设第i 个子群处于长度为l 的领域内，则 l b e s t 模型的进化方程可描述为： n t2 r 。( t ) ，气+ 。( t ) ，r 。( t ) ，( t ) ，t ( t ) ，气。( t ) p ：( t + 1 ) n il 姆”1 ) ) 锄坟a ) ，v a n i 1 7 ( 2 9 ) ( 2 1 0 ) 高校教师在职硕十学位论文 v 日( t + 1 ) ：v 日( t ) + c l ( t ) 【p 日( t ) 。x 日( t ) 】+ c 2r 2 j ( t ) p