（应用数学专业论文）基于随机微粒群算法的改进算法研究.pdf

，；-_1 。 l ： ，_ 。一”，謦。墟蘑笈 摘要 基于随机微粒群算法的改进算法研究 摘要 微粒群算法( 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 ) 在前人工作的基础上将随机微粒群算法和协同进化结合在一起寻求一种更有 效的算法。 ( 2 ) 把微粒群算法和传统优化算法( 如信赖域算法、共轭梯度法、最速下降法等) 相结合尝试寻找更有效的优化算法。 论文的研究内容主要包括以下几个部分： 第一章是绪论，主要介绍了微粒群算法的历史和现状，本文的创新和突破，以及本 文的现实意义。 第二章在多种群协同进化和随机微粒群算法基础上，提出了一种改进的多种群随机 微粒群算法，将各个子种群独立地按照随机微粒群进化，周期性的更新共享信息。 第三章在随机微粒群算法和函数梯度信息基础上，提出了基于梯度的随机微粒群算 法。数值计算表明算法对于求解连续可微函数的全局优化问题是非常有效的。 第四章提出一种基于协同进化的单纯形随机微粒群算法。该算法采用多个优化种 群，分别在奇数种群和偶数种群并行运行随机微粒群法和单纯形法，周期性更新相邻种 群最优信息。通过优化两个典型的测试函数验证了算法的有效性。 关键词：随机微粒群算法；协同进化；共轭梯度法；最速下降法；单纯形法。 基丁随机微粒群算法的改进算法研究 i i a b s t r a c t t h ei m p r o v e m e n ta l g o r i t h mb a s i e ds t o c h a s t i cp a r t i c l es w a r m o p t i m i z a t i o n 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 n ( p s o ) i sar a n d o mo p t i m i z a t i o n a l g o r i t h m t h eb a s i ci d e a o fp s oc o m e sf r o mt h er e s e a r c ho ft h e b e h a v i o ro fb i r d sf i n dh a b i t a t s i n c et h ea l g o r i t h mh a sb e e np r o p o s e d ， b e c a u s eo fi t se a s yi m p l e m e n t a t i o n ，f a s tc o n v e r g e n c e ，a n dt h en e e dt o a d j u s tl e s sp a r a m e t e r s ，a t t r a c t e d w i d ea t t e n t i o nf r o mm a n ys c h o l a r s t h ef o l l o w i n gt w op r o b l e m sh a v eb e e nc h o s e na st h em a i ng o a li nt h e d i s s e r t a t i o n ( 1 ) c o n s t r u c taf e wa l g o r i t h m sb a s e do ns p s oa n dc o o p e r a t i v e e v o l u t i o n a r y ( 2 ) d e v e l o pam i x e ds e a r c hm e t h o db yc o m b i n i n gs p s o w i t ho t h e r o p t i m i z a t i o na l g o r i t h m s t h ec o n t e n to ft h i sp a p e ri so r g a n i z e di n t of o u rc h a p t e r s i n c h a p t e ri ，w e i n t r o d u c et h eh i s t o r ya n ds t a t u sa b o u tp a r t i c l e s w a r mo p t i m i z a t i o n ，t h ec r e a t i v i t i e sa n dt h ep r a c t i c a li m p o r t a n c eo f t h i s p a p e l i nc h a p t e ri i ，am o d i f i e dc o o p e r a t i v es t o c h a s t i cp a r t i c l es w a r m o p t i m i z a t i o n ( c s p s o ) ，i sp r e s e n t e db a s e do nt h ea n a l y s i s o ft h es p s o a n dt h ec o o p e r a t i v ee v o l u t i o n a r yp s ow i t hm u l t i p o p u l a t i o n s t h ew h o l e g r o u p i sd i v i d e di n t os e v e r a ls u b g r o u p s e v e r ys u b g r o u p e v o l v e d i n d e p e n d e n t l ya n du p d a t e ds h a r i n gi n f o r m a t i o np e r i o d i c a l l y i nc h a p t e ri i i ，t h es t o c h a s t i cp a r t i c l es w a r mo p t i m i z a t i o nb a s i e dt h e g r a d i e n tm e t h o d ，i sp r e s e n t e db a s e do nt h ea n a l y s i so f t h es p s oa n dt h e g r a d i e n to ft h ec o n t i n u o u s d i f f e r e n t i a l f u n c t i o n n u m e r i c a le x p e r i m e n t s h a v ep r o v e dt h a tt h i sh y b r i da l g o r i t h mi sv e r yr e a s o n a b l e i nc h a p t e ri v , ac o o p e r a t i v es i m p l e xm e t h o d - s t o c h a s t i cp a r t i c l e s w a r mo p t i m i z a t i o n ( s m s p s o ) i sp r o p o s e d ，t h ec o n c e p t i o n o f i l l 基丁随机微粒群算法的改进算法研究 m u l t i p o p u l a t i o n si sa d o p t e di nt h i sm e t h o d ，w h e r es p s oa n ds mr u no n o d dp o p u l a t i o n sa n de v e np o p u l a t i o n s ，r e s p e c t i v e l y e x p e r i m e n t a lr e s u l t s o no p t i m i z a t i o nt w ob e n c h m a r kf u n c t i o n sd e m o n s t r a t ei t su s e f u l n e s s k e yw o r d s ：s t o c h a s t i cp a r t i c l es w a r mo p t i m i z a t i o n ；c o o p e r a t i v e e v o l u t i o n a r y ；c o n ju g a t eg r a d i e n tm e t h o d ；s t e e p e s td e s c e n ta l g o r i t h m ； s i m p l e xm e t h o d ； i v 目录 目录 第1 章绪论1 1 1 基本微粒群算法1 1 2 改进的微粒算法2 1 2 1 增加惯性权重和收敛因子：2 1 2 2 与进化计算技巧有机结合2 1 2 3 基于领域算子及拓扑结构的改进3 1 2 4 构造新的微粒组织或群结构3 1 2 5 改进或使用新的位置速度更新公式4 1 2 6 离散二进制p s o 算法5 1 2 7 其他优化方法。一5 1 3p s o 的应用5 1 3 1 神经网络训练5 1 3 2 函数优化5 1 3 3 其他领域的应用6 1 4 微粒群算法发展趋势6 1 4 1 算法的理论研究一6 1 4 2 算法的改进研究6 1 4 3 应用领域的拓展6 1 5 本文将做的工作6 第2 章一种基于协同进化的随机微粒群算法9 2 1 引言一9 2 2 算法的建立一l o 2 2 1 多种群协同进化1 0 2 2 2 随机微粒群算法1o 2 2 3 协同随机微粒群算法10 2 3 算法的有效性和收敛性分析1 2 2 3 1 测试函数1 2 2 3 2 实验方法1 2 2 3 3 实验结果1 2 2 3 4 实验数据分析1 3 2 3 5 收敛性分析1 4 2 3 6 结论1 4 第3 章基于梯度的随机微粒群算法1 5 3 1 引言15 v 基丁随机微粒群算法的改进算法研究 3 2 算法：1 5 3 2 1 共轭梯度算法15 3 2 2 最速下降算法1 6 3 2 3 基于共轭梯度算法的随机微粒群算法1 6 3 2 4 基于最速下降的随机微粒群算法1 7 3 2 5 数值试验1 7 3 2 5 1 实验方法1 7 3 2 5 2 实验结果1 7 3 2 5 3 实验数据分析1 8 3 2 5 4 收敛性分析1 8 3 2 5 5 结论1 8 第4 章一种协同进化的单纯形随机微粒群算法2 l 4 1 引言2 1 4 2 算法2l 4 2 1 单纯形法( s m ) 2 1 4 2 2 协同进化的单纯形随机微粒群算法2 2 4 3 数值试验2 3 4 3 1 测试函数2 3 4 3 2 实验方法2 3 4 3 3 实验结果2 3 4 3 4 收敛性分析2 5 4 3 5 结论2 5 总结与展望2 7 参考文献2 9 蜀【 谢3 5 硕士期间发表文章目录3 7 v l 第1 章绪论 第l 章绪论 最优化，也称为数学规划。它属于应用数学的范畴，同时也是运筹学的一 个重要分支，在工程技术、物理系统、经济管理、交通运输，特别是“优化设计” 等诸多领域得到广泛的应用，成为一门十分活跃的学科。最优化思想与方法于 上个世纪3 0 年代末4 0 年代初开始形成一门独立的学科。 优化算法有很多，经典算法包括：线性规划，动态规划等；改进型局部搜 索算法包括爬山法，最速下降法等。 上世纪9 0 年代初丌始出现群体智能算法的研究。其基本思想是模拟自然界 生物的群体行为来构造随机优化算法。典型的算法有蚁群算法和微粒群算法等。 1 1 基本微粒群算法 微粒群算法( p a r t i c l es w a l mo p t i m i z a t i o n ，简称p s o ) 是j a m e sk e n n e d y 和 r u s s e l le b e r h a r t 于1 9 9 5 年提出的，借鉴了鸟群或鱼群捕食过程的社会行为。算 法将群体中的成员描述为空间内一个没有质量、没有体积的“微粒”，所有微粒通 过一个适应函数来确定其在空间中的适应度。进化初期，每个微粒的位置和速度 都被随机初始化，微粒在飞行过程中相互合作，根据自身和同伴的运动状态及 时调整自己的速度和位置，以便在适应值较好的位置降落。 基本微粒群算法的进化方程为： v o + 1 ) = w v ( r ) + q o ) ( b o ) 一薯o ) ) - i - c 2 r 2 ( t ) ( p g ( t ) 一0 ) ) ( 1 1 ) x j ( t + 1 ) = 薯o ) + v o + 1 ) ( 1 2 ) 其中p i 表示第i 个微粒所经历过的最好位置，p g 表示所有微粒所经历过的最 好位置，e l ，c 2 为常数，r l ，r 2 【o ，1 】为均匀分布的随机数。 这种多个初始点开始的并行随机搜索方法，由于其易于实现、计算机量小、 收敛速度快、且需要调整的参数少，引起了诸多学者的广泛关注，并被广泛应 用于函数优化、神经网络、图像处理等方面。其中函数优化问题是p s o 最直接 的应用，包括多元函数优化、带约束优化问题。大量事实表明微粒群优化算法 比遗传算法在处理一些典型函数优化问题时更具有优势。因为许多实际问题都 可以归结为函数优化问题，所以微粒群优化算法具有很好的应用前景。尽管已 出现了许多改进的p s o ，但是由于实际问题的多样性和复杂性，这些已有算法 还是不能满足实际工作的需要。所以研究新的改进的实用的更好的p s o 用来解 决实际问题是一项很有意义的工作，也是当前许多学者探讨、研究的热点领域。 基丁随机微粒群算法的改进算法研究 1 2 改进的微粒算法 目前国内外研究主要改进算法的以下几方面： 1 2 1 增加惯性权重和收敛因子 p s o 算法的惯性权重可以平衡算法的全局搜索和局部搜索能力，所以控制 算法的参数显得尤为重要。于是，1 9 9 8 年s h iye b e r h a r tr 【2 】引入了惯性权因子 来调整了速度的更新公式，为了进一步提高算法的性能，该文还提出了自适应 调整c o 的策略，即随着迭代的进行，线性减小的值，这样算法更好的控制探 索与开发。由于p s o 搜索过程是一个非线性的复杂过程，让惯性权重线性调整 并不能正确反映搜索过程，后来s h iye b e r h a r tr f 3 】又先后提出了一种用模糊规 则动态调整的方法和带收敛因子的p s o ，这种方法在处理单峰函数时效果不 错。但此方法需要对各种搜索情况建立模糊规则，并且搜索时需要不断查找模 糊规则库，因此一定程度上增加了算法的复杂度、降低了算法效率。文献【4 】提 出了一种带收敛因子的p s o ，实验证明此微粒群算法比惯性权重的p s o 有更快 的收敛速度。 1 2 2 与进化计算技巧有机结合 1 9 9 8 年a n g e l i n ep e t e rj 【5 】在p s o 算法中结合了进化计算中锦标赛选择方法 的思想。该混合算法根据每个微粒的适应度将整个群体排序，然后将群体中当前 位置和速度最好的一半保留，最差的一半淘汰，过程中并不改变微粒的个体极 值。这样就保留了这一半相对较优位置的微粒用于下一代位置更新。通过实验 表明，算法的搜索能力因选择方法的引入增强。2 0 0 1 年l o v b j e r gm ，r a s m u s s e nt k ，k r i n kt t 6 j 提出了基于繁殖和子种群的杂交p s o 算法模型。该算法在繁殖过程 中将适应度用繁殖概率来替换，每次迭代时，依据繁殖概率在微粒群中选取 定数量的微粒随机两两进行繁殖，用产生出来的数目相同的后代微粒代替父代微 粒，这样种群微粒数目保持不变，后代微粒的位置由父母位置的算术“交叉”得到， 后代的速度向量由父母向量之和归一化后得到。此外，该算法还通过引入子种群 来维持算法的多样性。实验结果显示，该算法的收敛速度比较快，搜索精度也相 对比较高，对一些非线性优化问题可以取得较好效果，但因为引用的待调整参 数较多，导致仿真的次数增多，工作量加大。2 0 0 3 年n a t s u k ih i g a s h i ，h i t o s h ii b a 。7 】 提出将进化计算中的高斯变异算子与p s o 杂交的思想。2 0 0 4 年高鹰、谢胜利【8 】 提出了一种基于模拟退火的粒子群优化算法。2 0 0 7 年夏桂梅、曾建潮 9 1 进一步 提出了基于锦标赛选择遗传算法的随机p s o 算法。该算法对s p s o 进化中产生 2 第1 章绪论 的停止的微粒，用锦标赛选择机制下的g a 所产生的最优个体来代替。通过实验 表明了算法的有效性。 1 2 3 基于领域算子及拓扑结构的改进 1 9 9 9 年k e n n e d yj 【i o 对p s o 中邻域算子的研究发现：邻域算子通过保持微 粒群的多样性可以改进p s o 的性能使其避免过早收敛。19 9 9 年s u g a n t h a npn u l j 引入一个可变的邻域算子来改进标准p s o 的性能。刚开始优化时一个微粒以它 本身作为它的邻域。迭代后期邻域逐渐变大，扩张到所有微粒。这样p s o 算法 中的全局极值g b e s 。逐渐被一个局部邻域逐渐增加的局部极值p b e s 。所代替。与此同 时在最后阶段不断调整p s o 算法中惯性权重的大小，以使优化更好进行。结合 空间邻域和环状拓扑结构，2 0 0 0 年k e n n e d yj 【1 2 j 提出了具有社会模式的聚类分析 p s o 。该算法构造了族结构，每一个族以微粒群体中的一些微粒作为中心，合并 吸收离他较近的周围的n 个微粒，然后用这每个簇的中心位置替代个体的历史 最优位置和全局的历史最优位置。这种算法的特点是如果个体被他们自己的簇 中心所吸引则可明显改善p s o 的性能，但是若个体被相邻的簇中心所吸引时效 果则变差。2 0 0 3 年h ux ，e b e r h a r tr t l 3 j 提出一种能解决多目标优化问题的基于 动态邻域的微粒群优化算法( d n p s o ) ，利用扩展存储区存储全局p a r e t o 最优解 这种技巧缩短了算法的计算时间，是一种有效的多目标优化技术。2 0 0 3 年p e e re s 【1 4 】等用不同的邻域拓扑来研究保证收敛p s o ( g c p s o ) 的性能。2 0 0 7 年夏小翔、 曾建潮、高慧敏【1 5 】将小生境技术引入到p s o 中，提出了基于元胞自动机领域的 小生境微粒群算法。 1 2 4 构造新的微粒组织或群结构 2 0 0 1 年fv a nd e nb e r g h t l 6 】提出一种协同微粒群优化算法( c p s o ) 。该算法的 思想是将每个粒子分为k 部分数，刚开始的每一步迭代中，这n 个微粒群相互 独立地进行状态更新，计算适应值时，将微粒群之间信息共享即把每部分中最 好微粒的位置向量拼接起来，形成一个完整的解向量。这种局部学习的策略使 该算法容易跳出局部极值并且有较高的收敛精度。 2 0 0 2 年b u t h a i n a ha 【1 7 】提出了多相微粒群优化算法( m p p s o ) 。该算法将整个 群分为两组，这两组的搜索目标不相同，一组以全局最好为搜索目标，另一组 以局部最好为搜索目标，两组目标共同使微粒朝着适应值得到改善的方向进行。 该算法与基本p s o 相比增加了搜索的多样性和搜索的广泛性。 2 0 0 5 年薛明志、左秀会等f l8 1 提出了正交微粒群算法( o p s o ) 。其主要思想是 3 基于随机微粒群算法的改进算法研究 利用子空间分割方法来产生证交初始化微粒群，以便微粒能够均匀分布在整个 解空间上。 2 0 0 6 年滕居特、陈国初等1 1 9 1 提出了分段式微粒群算法( m s p s o ) 。该算法区 别于协同进化的地方是将所要搜索的区域分成若干段，首先搜索出每区段的最 优位置，然后将各区段的最优位置组成一微粒群，然后搜索该微粒群的全局最 优位置。实验证明，该算法具有更快的搜索速度和更好的优化性能。 2 0 0 6 年夏桂梅、曾建潮【2 0 j 提出了双群体随机微粒群算法。该方法采用两个 群体同时进化，一个群体在进化过程中所出现的停止微粒由另一群体的微粒来 代替，文中提出了三种产生新微粒的方法，并对三种方法进行了效果比对。 2 0 0 8 年都延丽、吴庆宪、姜长生、周耐2 l j 提出了协同随机微粒群优化的神 经网络预测建模，针对一类难以精确建立数学模型的非线性控制系统，提出了 协同随机微粒群优化c s p s o 的神经网络预测建模方法。c s p s o 在协同微粒群算 法c p s o 执行之后引入随机微粒群优化s p s o 的思想，促使c p s o 摆脱了伪最小 值现象，并且保证其以概率l 收敛于全局最优值。 1 2 5 改进或使用新的位置速度更新公式 2 0 0 4 年曾建潮、崔志华【2 2 l 提出了一种利用停止微粒改进算法全局搜索能力 的保证全局收敛的随机微粒群算法( s p s o ) 。 2 0 0 5 年陈国初、俞金寿1 2 3 j 提出了两群替代微粒群优化算法( t s s p s o ) 。该方 法将微粒分成飞行方向不同的两分群，其中一分群微粒朝着最优微粒飞行，另 一分群微粒朝着相反方向飞行。算法对每分群的每一代微粒、其第d 维( 1 9 9 ) 速度和位置的迭代方程进行了修正。每分群微粒在本分群历史最优微粒的指导 下朝着全群的历史最优微粒飞行。仿真实验证明，该算法可以有效地搜索到全局 最优解，优化效率和优化性能比基本p s o 算法均有明显的提高。 2 0 0 6 年黄建江、须文波等【2 4 】提出一种量子行为的微粒群优化算法( q p s o ) 。 2 0 0 7 年廖京、申群太f 2 5 】提出了差分演化p s o ( d e p s o ) 。 2 0 0 7 年姜海明、谢康、王亚非【2 6 】提出按概率突跳改进的p s o 。该算法引入 了一个新参数重新设置了粒子的速度进化公式，粒子飞行时会以一定的概率改 变飞行的距离和方向，该算法在合理地新参数的选取下对高维复杂函数的优化 效果较为突出。 2 0 0 7 年胡建秀、曾建潮1 27 】从控制角度分析了p s o 的进化方程，通过引入二阶 振荡进化方程来调节p s o 的全局和局部搜索能力，实验结果表明这种增加了群 4 第l 章绪论 体的多样性的算法容易跳出局部最优，显着加快算法的收敛速度。 1 2 6 离散二进制p s o 算法 针对基本p s o 在组合优化问题上的缺陷，k e n n e d y 和e b e r h a r t 【2 8 】发展了离 散二进制p s o 。 1 2 7 其他优化方法 文献 2 9 】提出了针对当前微粒群体中的最优微粒进行混沌寻优，并利用寻优 结果随机替换微粒群中的某一个微粒的混沌优化p s o 算法( c p s o ) 算法。文献 【3 0 根据耗散结构的自组织性，提出了通过附加噪声持续为微粒群引入负熵，从 而使群体不断进化的耗散微粒群优化算法( d p s o ) 。文献【3 l 】提出了通过引入“活 性因数”及使用分布式系统响应方式提高其适应性的适应复杂动态环境的改进的 自适应微粒群算法( i a p s o ) 。 1 3p s o 的应用 微粒群算法这种新兴的基于群体智能的随机优化算法，同模拟退火、蚁群算 法等其他智能算法相比，其最具优势的特征是易于实现，拥有较强的全局优化能 力，而且算法处理不同问题需要调整的参数少。 1 3 1 神经网络训练 p s o 在神经网络训练方面发挥了很大的潜力，它在训练网络的权重、进化网 络的结构方面都游刃有余，但是计算并不复杂。事实表明利用p s o 训练神经网 络是一种快速、高效的方法。文献 3 2 】研究如何训练积单元神经网络，并利用微粒 群算法来预测噪声环境的混沌时间序列；文献【3 3 】研究医用方面的p s o 的神经 网络应用，主要是分析人的颤抖这个医疗方面；文献【3 4 】在对建筑结构的损伤位 置和损伤程度进行识别的p s o 的优化神经网络方面进行了应用研究。通过引入 各层问的连接权值，对神经网络进行训练。 1 3 2 函数优化 函数优化问题是p s o 最直接的应用，在常见的多元函数优化、带约束优化 问题等方面效果尤其显著。大量研究结果表明，对于一些典型函数优化问题微粒 群算法比遗传算法优化效果更好。此外，p s o 还被成功应用于各种复杂的优化问 题，如动态优化问题、多目标优化问题等。例如，文献【3 5 】将p s o 应用于分布规 划通信基站；文献【3 6 】研究微粒群算法在设计模糊控制器领域的作用；文献 3 7 】 研究如何利用微粒群算法更好求解j o b s h o p 车间调度问题；文献 3 8 用离散p s o 求解t s p 问题，试验表明优化效果较好。 5 基丁随机微粒群算法的改进算法研究 1 3 3 其他领域的应用 微粒群算法除了应用于神经网络和函数优化方面外，还被广泛应用于电力系 统 3 9 1 、机械设计 4 0 1 、生物工程 4 1 1 、化学工程【4 2 】、经济 4 3 】、图像处理【4 4 】 等领域，并且也都取得了一定的成果。 1 4 微粒群算法发展趋势 p s o 是一种新兴的基于群体智能的进化算法。目前还处于研究初期，和遗传 算法相比，尚缺乏坚实的应用基础，系统的分析方法和良好的理论基础，如果想 真正发挥微粒群算法的优越性，深入分析算法的科学性和合理性，还有许多问 题仍需我们进一步探讨和深入，大致归纳如下： 1 4 1 算法的理论研究 与p s o 相应的相对鲜明的社会特性基础相比，其数学基础显得相对薄弱， 缺乏深刻且具有普遍意义的理论分析。如何利用有效的数学工具对算法的收敛 性、收敛速度估计、计算的复杂性、鲁棒性，以及预防陷入局部最优和参数设 置影响等进行分析将是今后的研究热点之一。 1 4 2 算法的改进研究 现实生活的实际问题是多种多样、纷繁复杂的，所以尽管许多改进形式的 p s o 已经出现，但仍然不能满足实际生活的需要。如何将p s o 算法与其他演化 技术的相结合，扬长避短，构造出有特色又有实用价值的混合算法是当前科技 工作者应该致力研究的一个非常重要的方面。 1 4 3 应用领域的拓展 虽然p s o 在函数优化及神经网络的训练等领域已经取得了一定的成绩，但 是微粒群算法仍然是一种很年轻的算法，在更多领域的应用还处于研究阶段， 因此，进一步开拓p s o 算法的新的应用领域也是一项值得继续摸索研究的新内 容。 1 5 本文将做的工作 本课题将在以下两个方面展开研究： ( 1 ) 在前人工作的基础上将随机微粒群算法和协同进化结合在一起寻求 种更有效的算法。不论标准微粒群还是随机微粒群每一代均更新信息，即更新 个体的历史最好位置和群体的历史最好位置。这样当前所搜索到的最好位置就 没有被充分利用，假使粒子位置一旦陷入局部最好值，算法将无法继续进化。 6 第1 章绪论 另一方面群体中的每一个微粒都代表可行解空间中的一个完整的解向量，每一 步更新都是在一个n 维向量上进行的。那就有可能被优化向量的某些分量靠近 了较优值，而另一些分量却远离了较优的值。尤其对于高维向量，这种现象较难 避免，也势必会削弱算法的全局收敛性能。可以假设，如果不再是每隔一代就更 新信息，而是粒子每独立地进化到一定代数，周期性地更新全局最好值，这样 既可以充分利用己搜索到的历史最好位置进行搜索，也利用周期性的共享全局 最好位置搜索到最好值，以此改善s p s o 算法的收敛性。基于上述思想，提出了 多种群协同进化的s p s o 算法。 ( 2 ) 把微粒群算法和传统优化算法( 如信赖域算法、共轭梯度法、最速下 降法等) 相结合尝试寻找更有效的优化算法。 对连续可微函数的优化问题，传统数值优化方法( 如最速下降法、n e w t o n 法和共轭梯度法等) 有相对较快的收敛速度，计算精度高，在实际函数优化问题 求解中得到广泛应用。但传统数值优化方法求得的是局部最优解。 微粒群算法实现全局并行搜索，搜索空间大，易于寻找到最优解或者准确解 所在的区域，所以具有计算时间相对较少、能以较大概率求解到全局最优解、 具有较强的鲁棒性。可是由于微粒群算法局部搜索能力比较差，导致在搜索工程 中易出现“早熟收敛”现象，进化后期收敛慢精度较差。考虑把粒子群算法的全局 收敛性和传统数值优化法的快速收敛性以及精度高等特点结合起来，提出新的 智能混合算法。 7 基丁随机微粒群算法的改进算法研究 8 第2 章一种基于协同进化的随机微粒群算法 第2 章一种基于协同进化的随机微粒群算法 本章在多种群协同进化和随机微粒群算法基础上，提出了一种改进的多种 群随机微粒群算法，将各个子种群度独立的按照随机微粒群去进化，周期性的 更新共享信息。其中采用了两种不同的更新策略，并对这两种不同的方法进行 详细的分析和比较。实验表明：合理调整更新周期能提高算法的收敛性。 2 1 引言 微粒群算法( 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 ) 是j a m e sk e n n e d y 和 r u s s e l le b e r h a r t 于1 9 9 5 年提出的【，它模拟的是鸟群或鱼群寻找栖息地、觅食 过程的社会行为。微粒群算法简单、易于实现、收敛速度快且需要调整的参数 少，自该算法提出以来引起了诸多学者的广泛关注，并在整数规划、神经网络、 图像处理等方面得到了成功应用。在最近很短的几年时间里该算法便获得了很 大的发展，算法的改进种类众多。随着2 0 世纪9 0 年代协同进化被引入计算科 学领域，有一些学者开始研究多种群协同进化，他们通过构造新的微粒组织或 群结构来提高算法收敛率，通过采用不同的协同策略提高算法性能。其中文献 4 5 】 提出了一种基于两个p s o 协同进化的求解极大极小值的算法。文献 4 6 1 根据微 粒群算法的特点，借鉴递阶编码的思想，构造了一种具有种群内个体微粒自由 运动特征分量与种群运动特征分量分层递阶进化的特征的基于多种群协同进化 的微粒群算法，并将其应用于径向基神经网络设计。文献 4 7 】引入了种群和移民 的思想，提出了一种基于多种群的并行p s o 算法。文献【4 8 】将种群分为主群和 若干个子群体，子群体迭代结束后将信息反馈给主群，主群依次最好微粒进化 后再将结果反馈回子群体。还有一些学者从算法的收敛性方面对微粒群算法进 行研究、改进，使其在全局收敛性方面有所改善。其中文献 2 2 1 给出了一种保证 全局收敛的随机微粒群算法( s t o c h a s t i cp a r t i c l es w a r mo p t i m i z a t i o n ) s p s o 。 为了进一步提高随机微粒群算法的性能，本文基于多种群协同进化提出协 同进化的随机微粒群算法。协同进化算法是指两个以上相关联的物种的同时进 化，分为竞争协同进化和合作协同进化，本文首先介绍了计算科学领域里的多 种群协同进化和随机微粒群算法的概念，然后给出了我们提出的一种基于多种 群协同进化的随机微粒群算法的描述。即把整个粒子群划分为若干个子种群， 各个子种群首先独立的用随机微粒群算法进化，然后再采用不同的更新策略周 期性地根据共享信息进行更新，以此来寻求函数的最优解。实验结果表明：采 9 基丁随机微粒群算法的改进算法研究 用随机微粒群算法的子种群选用合适的更新周期可以显著提高优化函数的收敛 速度和最优性。 2 2 算法的建立 2 2 1 多种群协同进化 多种群协同进化改变传统的用一个种群在解空问中搜索最优解的方式，它 直接将群体中的个体划分为若干子群体，每一子群体代表解空间中的一个子区 域( 子空间) ，其中的每一个体均代表问题一个解。所有予群体并行进行局部搜索， 所搜索到的优良个体将在不同子群体间进行迁移，作为共享信息用来指导进化 的进行，从而有效提高算法的全局收敛率。协同进化算法中最常见的协同模型 是“孤岛模型”与“邻域模型”。 2 2 2 随机微粒群算法 保证全局收敛的随机微粒群算法其基本思想是利用停止进化的微粒来改善 全局搜索能力，即在基本微粒群进化方程中( 1 ) 式中令w = o 使其先前速度项去掉， 这样使得速度本身失去记忆性，与基本p s o 算法相比，该进化方程使得全局搜 索能力减弱，局部搜索能力加强。但这样也使得在进化的每一代中至少有一个 微粒由于处于微粒群的历史最好位置而停止进化，然后在搜索空间中重新随机 产生新的微粒以代替停止微粒的进一步进化。这样大大增强了全局搜索能力。 2 2 3 协同随机微粒群算法 不论标准还是随机p s o ，每一代均按照进化方程更新个体的历史最好位置 和群体的历史最好位置。这就可能导致当前所搜索到的最好位置没有被充分利 用，假使粒子位置一旦陷入局部最好值，算法将停止进化。另一方面群体中的 每一个微粒都代表可行解空间中的一个完整的解向量，每一步更新都是在一个n 维向量上进行的。那就有可能被优化向量的某些分量靠近了较优值，而另一些分 量却远离了较优的值。尤其对于高维向量，这种现象较难避免，也势必会削弱算法 的全局收敛性能。可以设想，如果粒子独立地进化到一定代数再周期性地更新 全局最好值，不再是每隔一代就更新信息，这样就不仅能在已搜索到的历史最 好位置的引导下进行搜索，也可以向周期性的共享到的全局最好位置处飞行， 如此进化应该可以改善随机微粒群算法的收敛性能。本文按照如上假设，提出 了多种群协同进化的随机微粒群算法。将整个种群划分为若干个子种群，各个 子种群独立地用随机微粒群进化，在达到一定的周期时更新全局最好位置。这 样，各个子种群的粒子既能充分地按照子种群内部的寻优方向不断地飞行，又 l o 第2 章一种基于协同进化的随机微粒群算法 能周期性地利用共享到的全局最好位置加快粒子找到最好值。同时，分解为多 个子种群有保持种群的多样性的优势，从而有可能改善随机微粒群算法的早熟 现象。 本文提出两种不同的协同进化s p s o 算法，一种是本质是“孤岛模型”的 c e s p s 0 1 ，一种是基于“邻域模型”的c e s p s 0 2 。 首先将整个种群的m 个粒子划分为n 个子种群，这样每个子种群有 q = i n t ( m n ) ( q i ) 个粒子，其中i n t o 为取整函数。如果m 不能被n 整除，则将剩 余的粒子随机进行分配。 c e s p s 0 1 ：对于分解下的n 个子种群，初始化使它们都有相同的初始最好 位置及对应的最好值。然后让这n 个子种群各自不断的独立地用s p s o 算法更 新本种群内各个粒子的位置和速度。当进化到第r 代( r 为更新周期) 将n 个子种 群的当前最好值( p 9 0 ( i = l ，2 ，3 ，”n ) 做比较，得出其中的最好值作为当前的全局最 好值( p o ) 。各个子种群共享该全局最好值继续进化。依次循环，每隔r 代更新 共享一次全局最优值，满足精度要求或达到最大进化代数时退出。 在算法c e s p s 0 1 中，各个子种群既充分利用自身搜索到最好位置，不迷失 方向，又可以在达到周期时，按照共享到的全局最好值p g 的引导使本种群的所 有粒子向函数的最好位置靠拢。当r = i 时，其实质就是随机微粒群算法。算法 c e s p s 0 1 中，要等到所有的子种群全部达到周期时，才可以进行比较得出此时 的全局最好值然后共享此最好值。而下面介绍的算法c e s p s 0 2 是按照另外一种 方式更新共享信息。 c e s p s 0 2 ：各子种群顺次进化。首先第一个子种群独立的使用s p s o 算法 不断更新本子种群内粒子的速度和位置。当进化到第r 代时( r 为更新周期) 我们 将第一个子种群的全局极值点p g l 直接赋给第二个子种群，第二个种群根据随机 微粒群算法的进化方程更新本群内微粒时采用p 。i 作为它的全局极值点这样 依次类推，种群i 达到更新周期r 代时，便用上一个种群的p g i 引导它的进化， 而它进化之后的全局极值点再引导i + 1 个种群进化，最后一个子种群将p g 。传回 给第一个子种群。在每次各个子种群得出该种群内的当前最好位置，传递给下 一个相邻的子种群的同时需要判断p g i ( i = l ，2 ，3 ，n ) 是否满足精度，若果满足则终 止程序，否则继续进化，直到满足退出条件。 ， 在算法c e p s 0 2 中，由于各个种群是顺次进化，每隔r 代相邻的两个子种 群之间进行信息交换。由于每个子种群进化时都采用的上一个子种群传递下来 基丁随机微粒群算法的改进算法研究 的信息，所以是一种串行搜索方式。 2 3 算法的有效性和收敛性分析 实例仿真： 实验中设置总种群数目为3 0 ，设定5 个子种群。验证算法对于3 个标准测 试函数的优化效果。为了避免s p s o 算法的随机性对优化结果的影响，我们选取 各个函数5 0 次运算的平均值。 2 3 1 测试函数 ( 1 ) a c k l e y 函数 厂_。 胁) = - 2 0 e x p ( n 2 善# ) _ e x p ( 1 玎p s ( 2 e r x , ) ) + 2 0 + 卜3 眍x ig o 在x ，= o ( i = 1 ，z ) 时达到全局极小点。 ( 2 ) g r i e w a n k 函数 左( 功= 窆x 2 4 0 0 0 一n c o s ( 薯圻) + l 一1 0 0 ，d o = 一g o ，k ：= 0 ； 步2 若l i i i 鱼，则停止。得问题的解。否则转步3 ； 步3 由线性搜索确定步长c l k ； 步4 令x k + 1 = x k + 毗d k ； 步5 由3 3 式计算b k ，并求d k + l = g k + i + p k + l d k ，k ：_ k + l 转步2 。 3 2 2 最速下降算法 步1 取初始点x o r n ，精度 0 ，k ：= 0 ； 步2 若i i 舭i ig ，则停止。得问题的解。否则d k = 一g k 转步3 ； 步3 由线性搜索确定步长0 【k ； 步4 令x k + l = ) ( k 托k d k ，k ：- k + 1 ，转步2 。 3 2 3 基于共轭梯度算法的随机微粒群算法 对于优化问题m i n f 【x