




已阅读5页,还剩92页未读, 继续免费阅读
(计算机软件与理论专业论文)个性化微粒群算法研究.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
中文摘要 微粒群算法是一种模拟鸟群飞行、鱼群游动等生物群体社会行为的群体随机优 化算法,由于它结构简单、运算速度较快,己广泛应用于许多领域。论文从智能体 ( a g e n t ) 观点出发,提出了个性化微粒群算法框架,并将其应用于参数选择及结 构优化。 标准微粒群算法仅利用了微粒的记忆性,没有考虑微粒的其它特性。这一局限 使得微粒群算法与其生物学背景之间存在较大差异,从而影响了算法的计算效率。 有鉴于此,论文将算法中的微粒视为具有记忆能力、通讯能力、响应能力、协作能 力及自学习能力的智能体( a g e n t ) 粒子,提出了个性化微粒群算法框架。该算法 在标准微粒群算法的基础上,利用多智能体之间的相互竞争、相互协作,使微粒能 更好地适应周围环境,从而更加符合算法的生物学背景。 参数选择是微粒群算法研究的一个重要内容,与已有的参数选择策略不同,个 性化的参数选择策略需要充分利用各微粒的通讯、响应、协作及自学习能力,从而 导致不同微粒在同一代中参数具有不同的值。论文以各微粒对环境适应能力的优劣 为基础,提出了线性化的性能评价指标作为微粒的自学习能力,并根据协作能力动 态调整全局搜索能力与局部搜索能力之间的比例。基于该思想,论文成功提出了惯 性权重、认知系数及社会系数的个性化选择策略,仿真结果表明这些策略能有效地 提高算法的计算效率。 对于微粒群算法的另一个重要研究内容一结构优化,论文根据较优位置附近存 在全局极值点的概率较大这一原则,初步探讨了个性化的微粒群算法结构实现方 式。由于个性化惯性权重策略具有较高的选择压,容易陷入局部极值点。因此,论 文引入一种特殊的结构以限制局部搜索能力,强化其全局搜索能力,从而有效地避 免了过早收敛现象的发生。然而,该策略的全局搜索性能仍然较弱,为此,论文进 一步提出了一种发散的进化方式。仿真结果表明该算法能有效提高种群多样性。 关键词:微粒群算法;惯性权重;认知系数;社会系数;算法结构 s t u d i e so ni n d i v i d u a lp a r t i c l es w a r mo p t i m i z a t i o n x i n g ju a nc a i ( c o m p u t e r s o f t w a r ea n dt h e o r y ) d i r e c t e db yp r o f y i n gt a n a n dj i a n c h a oz e n g 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 sap o p u l a t i o n - b a s e d s t o c h a s t i c o p t i m i z a t i o na l g o r i t h ms i m u l a t e dw i t hs o c i a lb e h a v i o ra m o n g a n i m a ls o c i e t y s u c ha sb i r df l o c k i n ga n df i s hs c h o o l i n g d u et oi t ss i m p l ei m p l e m e n t a t i o n a n df a s tc o n v e r g e n ts p e e d ,p s oh a sb e e na p p l i e di n t om a n ya r e a s i nt h i s a r t i c l e ,an e wi n d i v i d u a lp s o m o d e li si n t r o d u c e df r o mt h ea g e n tv i e w p o i n t , a n da p p l i e di n t op a r a m e t e rs e l e c t i o na n ds t r u c t u r eo p t i m i z a t i o n i nt h es t a n d a r dp a r t i c l es w a r mo p t i m i z a t i o n , o n l yt h em e m o r yo fe a c h p a r t i c l ei su s e dw h i l eo t h e rc h a r a c t e r sa r eo m i t t e d t h i sl i m i t a t i o nm a k e s l a r g ed i f f e r e n c e sb e t w e e np s o a n di t sc o r r e s p o n d i n gb i o l o g i c a lm o d e l ,a n d a f f e c t st h ee f f c i e n c ys i g n i f i c a n t l y t h e r e f o r e ,t h i sa r t i c l ep r o p o s e sa n i n d i v i d u a lp a r t i c l es w a r mo p t i m i z a t i o nm o d e l ,w h i l ee a c hp a r t i c l ei sv i e w e d a sa na g e n tw i t hm e m o r y , c o m m u n i c a t i o n ,r e s p o n s i b i l i t y , c o o p e r a t i o na n d s e l f - l e a r n i n ga b i l i t y t h ei n c o r p o r a t e di n t e r a c t i o ns u c ha sc o o p e r a t i o na n d c o m p e t i t i o nm a k e st h i sn e wm o d e li sm o r ef i tf o rb i o l o g i c a lb a c k g r o u n d t h a ns t a n d a r dp s 0 p a r a m e t e rs e l e c t i o ni sa ni m p o r t a n tr e s e a r c ht o p i ci np s ol i t e r a t u r e s d i f f e r e n tf r o mp u b l i s h e ds t r a t e g i e s ,f o re a c hp a r t i c l e ,i n d i v i d u a lp a r a m e t e r s e l e c t i o ns t r a t e g yu t i l i z e si t si n f o r m a t i o na n da d v i s e sad i f f e r e n tv a l u e b a s e do nt h ef i t n e s sc a p a b i l i t yo fe a c hp a r t i c l e ,i nt h i sa r t i c l e ,al i n e a r p e r f o r m a n c ei n d e xi sd e s i g n e dt os i m u l a t et h es e l f - l e a r n i n ga b i l i t y , a n de a c h p a r t i c l ed y n a m i c a l l ya d j u s t s t h er a t i ob e t w e e ng l o b a la n dl o c a ls e a r c h c a p a b i l i t i e sw i t hc o o p e r a t i v er u l e s s i m u l a t i o nr e s u l t ss h o wt h ep r o p o s e d i n d i v i d u a ls t r a t e g i e ss u c ha si n e r t i aw e i g h t ,c o g n i t i v ec o e f f i c i e n ta n ds o c i a l c o e f f i c i e n ta r ee f f e c t i v e a sa n o t h e ri m p o r t a n tr e s e a r c ht o p i c ,t h i sa r t i c l e d i s c u s s e st w od l 付e r e n t i n d i v i d u a ls t m c t u r eo p t i m i z a t i o nm a n n e r s b e c a u s eo ft h eh i g h s e l e c t l o n p r e s s u r ew i 曲 i n d i v i d u a l i n e r t i aw e i g h t s e l e c t i o ns t r a t e g y , as p e c l a l s t m c t u r ei sd e s i g n e dt oe n l a r g e t h eg l o b a ls e a r c hc a p a b i l i t y , a s w e l la s s h o 舳t h el o c a ls e a r c hc a p a b i l i t y h o w e v e r , t h ee x p l o r a t i o n o ft h i sm a n n e r iss t i l lw e a k t h e r e f o r e ,an e wr e p u l s i v eu p d a t em a n n e r i su s e dt om 吡e r i m p r o v et h ee x p l o r a t i o nc a p a b i l i t y s i m u l a t i o n r e s u l t ss h o wi tc a n1 m p r o v e t h ep o p u l a t i o nd i v e r s i t ys i g n i f i c a n t l y 1 研w 。r d s :p a r t i c l e s w a r mo p t i m i z a t i o n ;i n e r t i a w e i 出;c 。9 1 1 i t i v e c o e m c i e n t ;s o c i a lc o e f f i c i e n t ;a l g o r i t h m s t r u c t u r e m 承诺书 承诺书 本人郑重声明:所呈交的学位论文,是在导师指 导下独立完成的,学位论文的知识产权属于太原科技 大学。如果今后以其他单位名义发表与在读期间学位 论文相关的内容,将承担法律责任。除文中已经注明 引用的文献资料外,本学位论文不包括任何其他个人 或集体已经发表或撰写过的成果。 学位毪文仟者( 签章) 荣曼磺 2 0 簖年扯月侈日 第一章引言 第一章引言 1 1 优化问题 在现实生活中,经常会遇到在有限的资源( 如人力、原材料、资金等) 情况下, 如何合理进行安排使其效益达到最大;或者对给定的任务,如何统筹安排现有的资 源,完成给定的任务而使花费最小,这就是现实社会中的优化问题。 所谓的优化问题【l 】,是指在满足一定的约束条件下,对一组确定的参数函数, 使一些优化的度量得到满足,即达到某些度量指标的最大或者最小。优化问题涉及 到社会的各个领域,对社会的发展显得非常重要。其一般形式可写为: g l o b a lr a i 。nd ( x ) ( 1 1 ) s t g j ( x ) = 0 ,= 1 ,2 ,m ; ( 1 2 ) g i ( z ) 0 ,7 = m 。+ 1 ,m ( 1 3 ) 其中x 是解空间,f ( x ) 和g ,( z ) ( ,= 1 ,2 ,m ) 是定义在x 上的实值函数,分别称为 目标函数和约束函数,x r “,托为变量个数,m s ,m 为非负整数且m 。sm 。记s 为x 中满足式( 1 2 ) 和式( 1 3 ) 的所有点的集合,称之为可行域。当m = 0 且x 是一个 r “空间上的紧的超立方体时,问题( 1 1 ) ( 1 3 ) 称为无约束全局优化问题。本文讨论 的问题就属于无约束全局优化问题。为下文叙述方便,这里将无约束全局优化问题 写为: m i 、n ,f ( x ) ( 1 4 ) 其中, x = 【a 1 ,b l l x a 2 ,b 2 】【n 。,b 。】 ( 1 5 ) 求解问题( 1 1 ) ( 1 3 ) 就是要找到x 上的可行域内使得目标函数值达到最小的点, 即全局极小点。相对而言,局部极小点仅在其“周围”以某个长度为半径的邻域内 是最小的,并不能保证在整个x 上是最小的,因为通常x 内不只一个局部极小点。 一般情况下,局部优化算法不能有效地求解全局优化问题( 1 1 ) 一( 1 3 ) ,除非问题只有 一个局部极小点。 全局优化问题通常被认为是优化问题中最难以求解的一类。这一方面是由于在 可行域s 内一般会有很多局部极小点,却只有一个或很少几个是全局极小点。此外, 在实际问题中,随着问题维数的增加,局部极小点的数量还会急剧增多,这就会使 问题的精确求解变得十分困难。另一方面,局部优化问题可以用梯度是否为零来判 个性化微粒群算法研究 定算法是否找到局部极小点,而对于全局优化问题则不存在这样一个通用的准则来 判断算法是否达到全局极小点。这样就常常会使算法陷入某一个局部极值点,而不 能准确有效地跳出当前点转到下一个更好的局部极小点,这不但可能造成大量的重 复计算,而且使得算法终止准则的提出变得十分困难。 为了使系统达到最优目标而提出的各种求解方法称为优化方法。优化问题的求 解一般有确定的优化方法和随机的优化方法。确定的优化方法有n e w t o n r a p h s o n 法、共轭梯度法、f l e t c h e r - r e e v e s 法、p o l a r - r i b i e r e 法、d a v i d o n f l e t c h e r p o w e r 法、 b r o y d e n f l e t c h e r - g o l d f a r b s h a n n 方法等。所有这些确定优化算法均对目标函数有一 定的解析性质要求,如n e w t o n - r a p h s o n 法要求目标函数连续可微,同时要求其一 阶导数连续。然而,随着科学技术及工程应用的发展,提出了许多具有非线性、高 维、不连续等特点的优化问题,这些问题一般难以用传统的确定性算法解决。为了 求解这些问题,学者们提出了随机优化方法。常见的随机优化方法主要有 m o n t e c a r l o 算法、进化算法【2 1 ( 遗传算法【3 】、进化策略f 4 】、进化规划5 1 ) 、模拟退火 算法【6 1 、禁忌算法【7 1 、群智能算法【8 】等。在此,我们仅对其中几个较为典型的优化算 法作一简单介绍。 1 1 1 遗传算法 遗传算法1 3 1 是模拟遗传选择和自然淘汰的生物进化过程的计算模型,遗传算法 最早是由美国m i c h i g a n 大学的j h o l l a n d 博士提出的,已广泛应用于计算机科学、 优化调度、运输问题和组合优化等领域。遗传算法的操作对象是一组二进制串,即 种群。每一个二进制串称为染色体或个体,每个染色体或个体都对应于问题的一个 解。从初始种群出发,采用基于适应值比例的选择策略在当前种群中选择个体,并 使用交叉和变异来产生下一代种群,如此一代一代进化下去,直至满足期望的终止 条件。 1 1 2 模拟退火算法 模拟退火算法【6 j 来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却, 加温时,固体内部粒子随温度升高变为无序状,内能增大,而徐徐冷却时粒子渐趋 有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。根据 m e t r o p o l i s 准则,粒子在温度t 时趋于平衡的概率为e - d e 灯,其中,e 为温度丁时的 内能,丝为其改变量,k 为b o l t z m a n n 常数。用固体退火模拟组合优化问题,将内 能模拟为目标函数值,温度演化成控制参数,即得到求解组合优化问题的模拟退火 算法:由初始解和控制参数瓦开始,对当前解重复“产生新解一计算目标函数值 2 第一章引言 一接受或舍弃”的迭代,并逐步衰减温度丁的值,算法终止时的当前解即为所得的 近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程,退火过程 由冷却进度表( c o o l i n gs c h e d u l e ) 控制。 1 1 3 禁忌搜索算法 禁忌搜索f j 7 】的思想最早由g l o v e r 提出,它是对局部领域搜索的一种扩展,是一 种全局逐步寻优算法。禁忌搜索算法( t a b us e a r c h ,t s ) 通过引入一个灵活的存储 结构和相应的禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良 状态,进而保证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算 法,t s 是又一种搜索特点不同的m e t a - h e u r i s t i c 算法。迄今为止,t s 算法在组合 优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功,近年 来又在函数全局优化方面得到较多的研究,并大有发展趋势。 1 2 群体智能算法 1 2 1 群智能 群智能这个概念来自对蜜蜂和蚂蚁的观察。每只蜜蜂和蚂蚁的智能并不高,看 起来并没有集中的指挥,但它们却能够协同工作,建起坚固、漂亮的巢穴,集中食 物、扶养后代,依靠群体的能力,发挥了超出个体的智能,这样一种从群居性生物 中产生出来的集体行为被称为群体智能0 1 。 通过对群居性昆虫的模拟,一系列启发于群智能的用于解决计算机传统问题和 实际应用问题的新方法也相继产生。这些研究就是群智能的研究。群智能( s w a r m i n t e l l i g e n e e ) 中的群体( s w a r m ) 指的是“一组相互之间可以进行直接通信或者间 接通信的主体,这组主体通过合作进行分布问题求解”。而所谓群智能指的是“简 单智能的主体通过合作表现处复杂智能行为的特点”。 1 2 2 常见的群智能算法 基于群居性昆虫群体和其它动物群体的集体行为,一些学者提出了相应的群体 智能算法,其中常见的群体智能算法主要有下面几种: ( 1 ) 蚁群算法 蚁群算法 n l ( 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 年在他的博士论文中引入,其灵感 来源于蚂蚁在寻找食物过程中发现路径的行为。 蚂蚁在寻找食物的过程中不断的释放一种化学物质一信息素,因而,信息素多 3 个性化微粒群算法研究 的地方经过的蚂蚁也会多。假设有两条路从窝通向食物,开始的时候,走这两条路 的蚂蚁数量同样多( 或者较长的路上蚂蚁多,这无关紧要) 。当蚂蚁沿着一条路到 达终点以后会马上返回来,这样,短的路上的蚂蚁来回一次的时间就短,这也意味 着重复的频率就快,因而在单位时间里走过的蚂蚁数目就多,洒下的信息素自然也 会多,自然会有更多的蚂蚁被吸引过来,从而洒下更多的信息素;而长的路正 相反。因此,越来越多的蚂蚁聚集到较短的路径上来,最短的路径就近似找到了。 ( 2 ) 人工鱼群算法 在一片水域中,鱼往往能自行或尾随其它鱼找到营养物质多的地方,因而鱼生 存数目最多的地方一般就是本水域中营养物质最丰富的地方。人工鱼群算法【1 2 】是根 据这一特点,通过构造人工鱼来模仿鱼群的觅食、聚群及追尾行为,从而实现寻优过 程。该算法模拟了鱼的几种典型行为:觅食行为:一般情况下鱼在水中随机游动, 当发现食物时,则会向食物逐渐增多的方向快速游去;聚群行为:鱼在游动过程中为 了保证自身的生存和躲避危害会自然地聚集成群,鱼聚群时所遵守的规则有三条: ( a ) 分隔规则尽量避免与临近伙伴过于拥挤;( b ) 对准规则尽量与临近伙伴的 平均方向一致;( c ) 内聚规则尽量朝临近伙伴的中心移动;追尾行为:当鱼群中的 一条或几条鱼发现食物时,其临近的伙伴会尾随其快速到达食物点。 ( 3 ) 微粒群算法 标准微粒群算法n 3 4 3 ( s t a n d a r dp 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 ) 是在 1 9 9 5 年由美国社会心理学家j a m e sk e n n e d y 和电气工程师r u s s e lle b e r h a r t 共同 提出的,有关标准微粒群算法的内容将在下一节进行详细介绍。 1 3 微粒群算法 所谓微粒群算法,实际上是一种模拟鸟群飞行、鱼群游动等群体行为的随机优 化算法。该算法体现这样一种简单朴素的智能思想:鸟类使用简单的规则来确定自 己的飞行方向和速度,试图停落在鸟群中而不致相互碰撞。这种思想产生的微粒群 算法与其它进化类优化算法相类似,也采用“群体”和“进化的概念,同样也是 依据个体( 微粒) 的适应值大小进行操作。所不同的是,微粒群算法不像其它进化 算法那样对于个体使用进化算子,而是将每个个体看作是在咒维搜索空间中的一个 没有重量和体积的微粒,并在搜索空间中以一定的速度飞行,该飞行速度由个体的 飞行经验和群体的飞行经验进行动态调整。 4 第一章引言 1 3 1 标准微粒群算法 本论文将讨论如下的数值优化模型: m i n f ( x ) ,x 【x 血,x 姐。】”gr ” ( 1 6 ) 设 x f = ( zf 1 ,zf 2 ,xf 。) 为微粒,的当前位置; k = ( v j l ,移2 ,v ,。) 为微粒- 的当前飞行速度; 0 = ( p j l , p 2 ,p j 。) 为微粒所经历的最优位置,也就是微粒_ 所经历过的具 有最优适应值的位置,称为个体历史最优位置。对于最小化问题,目标函数值越小, 对应的适应值越优。 设群体中的微粒数为s ,群体中所有微粒所经历过的最优位置为p g ( t ) ,称为全 局历史最优位置。 有了以上定义,标准微粒群算法的进化方程可描述为: v j k ( f + 1 ) = w v j k ( t ) + c l r x ( p j k ( f ) 一z 弦( f ) ) + c 2 r 2 ( p g k ( f ) 一x 业( f ) ) x j k ( t + 1 ) = ( f ) + v i k ( f + 1 ) ( 1 7 ) ( 1 8 ) 其中:下标“k ”表示微粒的第k 维,“f ”表示微粒j ,t 表示第t 代,w 为惯性权 重,介于0 ,1 之间,认知系数g 与社会系数c ,称为加速度常数,通常在0 2 间取 值,_ ( ,( 0 ,1 ) ,r 2 - u ( o ,1 ) 为两个相互独立的随机数。 从上述微粒进化方程可以看出,烈,用于调节自身惯性所占的比重,g 调节微粒 飞向自身最优位置方向的步长,c ,调节微粒向群体历史最优位置飞行的步长。为了 减少在进化过程中,微粒离开搜索空间的可能性,v 证通常限定于一定范围内,即 v f k 卜,秒一1 。如果问题的搜索空间限定在 一x 蛐,x 一】内,则可设定 = k xz 。,0 1 七1 0 。 标准微粒群算法的初始化过程为: ( 1 ) 设定群体规模; ( 2 ) 对任意微粒- 的任意维k 的位置分量z 灰在卜x 懈,x 一】内服从均匀分布产生; ( 3 ) 对任意微粒,的任意维k 的速度分量z ,m 在卜1 ,一,k 内服从均匀分布产生; ( 4 ) 个体历史最优位置p ( 0 ) 取各微粒初始位置,群体最优位置只( o ) 为适应值最优 的微粒所对应的位置。 1 3 2 标准微粒群算法流程 ( 1 ) 种群初始化:按照上述初始化过程选择,并置进化代数f 为o ; 5 个性化微粒群算法研究 ( 2 ) 参数初始化:设置惯性权重1 4 、认知系数q 、社会系数c :及最大速度上限v 一; ( 3 ) 由式( 1 7 ) 计算微粒下一代的速度; ( 4 ) 调整各微粒的速度; ( 5 )由式( 1 8 ) 计算微粒下一代的位置; ( 6 )更新个体历史最优位置及群体历史最优位置; ( 7 ) 若结束条件满足,输出得到的最优位置;否则,转步骤3 。 1 3 3 社会行为分析 标准微粒群算法的速度进化公式( 1 7 ) 可以分成三个部分【1 5 】: v 庸 + 1 ) = 互+ 乃+ 正 ( 1 9 ) 其中,五= w v j k ( f ) ,l = c l r l ( p j k ( f ) 一x j k ( f ) ) ,l = c 2 r 2 ( p g k ( f ) 一x j k ( f ) ) 。 第一部分表示微粒先前速度所起的惯性作用,若速度进化方程仅保留这部分, 此时,微粒将会保持速度不变,沿该方向一直“飞”下去直至到达边界。因而,在 这种情形下,微粒很难搜索到较优解。 第二部分为个体的“认知 部分,因为它仅考虑了微粒自身的经验,表示微粒 本身的思考。如果标准微粒群算法的速度进化方程仅包含认知部分,由于不同的微 粒间缺乏信息交流,且没有社会信息共享,则一个规模为聊的群体等价于运行了m 次单个微粒的微粒群算法,降低了得到最优解的概率。 第三部分为“社会”部分,表示微粒间的社会信息共享。若速度进化方程中仅 包含社会部分,则微粒缺乏个体的认识能力。此时,虽然微粒在相互作用下,有能 力到达新的搜索空间,但对于复杂问题,容易陷入局部最优点。因此,标准微粒群 算法的速度进化方程由认识和社会两部分组成。虽然目前的一些研究表吲1 6 】,对于 某些问题,模型的社会部分比认识部分更重要,但两部分的相对重要性还没有从理 论上给出结论。 若速度的进化方程仅保留第二、三部分,由于微粒的速度将取决于其历史最优 位置与群体的历史最优位置,从而导致速度的无记忆性,即先前速度的影响为0 。 假设在开始时,微粒,处于群体的历史最优位置,则它将停止进化直到群体发现更 优的位置,而其它微粒将收敛于群体的历史最优位置。因此,若群体在收敛时没有 发现更优的位置,则整个群体的搜索区域将会收缩到当前历史最优位置附近,从而 表明此进化方程具有很强的局部搜索能力。 6 第一章引言 由于标准微粒群算法具有一定的全局搜索能力,因此,微粒速度进化方程的第 一项正用于保证算法具有一定的全局搜索能力,而与五两项则用于保证微粒群算 法具有局部搜索能力。 1 3 4 与其它进化算法的比较 微粒群算法与其它进化算法有许多共同之处。首先,微粒群算法和其它的进化 算法相同,均使用“群体”概念,用于表示一组解空间中的个体集合。如果将微粒 所经历的最优位黄p ,( ,) 看作是群体的组成部分,则微粒群的每一步进化都呈现出 弱化形式的“选择”机制。在( p + a ) 进化策略算法中,子代与父代竞争,若子代具 有更好的适应值,则用来替换父代,而p s o 算法的个体历史最优位置的更新方程具 有与此相类似的机制,其唯一的差别在于,只有当微粒的当前位置与所经历的最好 位置p ,( r ) 相比具有更好的适应值时,其微粒所经历的最好位置( 父代) 才会唯一 地被该微粒的当前位置( 子代) 所替换。总之,p s o 算法隐喻着一定形式的“选择” 机制。 其次,式( o 7 ) 所描述的速度进化方程与实数编码遗传算法的算术交叉算子相类 似,通常,算术交叉算子由两个父代个体的线性组合产生两个子代个体,而在p s o 算法的速度进化方程中,假如不考虑互项,就可以将该方程理解为由两个父代个体 产生一个子代个体的算术交叉运算。从另一个角度,在不考虑t i 项的情况下,速度 进化方程也可以看作是一个变异算子,其变异的强度( 大小) 取决于两个父代微粒 间的距离,即代表个体最好位置和全局最好位置的两个微粒的距离。至于z 项,也 可以理解为一种变异的形式,其变异的大小与微粒在前代进化中的位置相关。 通常在进化类算法的分析中,人们习惯将每一步进化迭代理解为用新个体( 即 子代) 代替旧个体( 即父代) 的过程。这里,如果我们将p s o 算法的进化迭代理解 为一个自适应过程,则微粒的位置x 以) 就不是被新的微粒所代替,而是根据速度向 量 v j ( ,) 进行自适应变化。这样,p s o 算法与其它进化类算法的最大不同点在于:p s o 算法在进化过程中同时保留和利用位置与速度( 即位置的变化程度) 信息,而其它 进化类算法仅保留和利用位置的信息。 另外,如果将位置进化方程看作一个变异算子,则p s o 算法与进化规划很相似。 所不同之处在于:在每一代,p s o 算法中的每个微粒只朝一些根据群体的经验认为 是好的方向飞行,而在进化规划中可通过一个随机函数变异到任何方向。也就是说, p s o 算法执行一种有“意识( c o n s c i o u s ) 的变异。从理论上讲,进化规划具有更 多的机会在优化点附近进行开发,而p s o 则有更多的机会更快地飞到更好解的区 7 个性化微粒群算法研究 域。 由以上分析可以看出,基本p s o 算法也呈现出一些其它进化类算法所不具有的 特性,特别是,p s o 算法同时将微粒的位置与速度模型化,给出一组显式的进化方 程,是其不同于其它进化类算法的最显著之处,也是该算法所呈现出许多优良特性 的关键点。 1 3 5 微粒群算法的研究背景和现状 微粒群算法【1 3 ,1 4 ,1 7 ,1 8 1 是在1 9 9 5 年由美国社会心理学家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 共同提出的,其基本思想是受他们早期对鸟类群体行为研究结 果的启发,并利用了生物学家f r a n kh e p p n e r 的生物群体模型【1 9 】。 基本微粒群算法的速度进化方程可以分成三个部分1 1 5 j :微粒先前的速度、表示 微粒本身思考的“认知”部分及表示微粒间社会信息共享的“社会 部分。基本的 微粒群算法可分为两种基本进化模型:全局模型( g b e s t 模型) 及局部模型( l b e s t 模型) 。g b e s t 模型以牺牲算法的鲁棒性为代价提高算法的收敛速度【2 0 1 ,但易发生过 早收敛现象。为此,l b e s t 模型采用多吸引子代替g b e s t 模型的单一吸引子。虽然收 敛速度低于g b e s t 模型,但收敛的全局最优性明显改善。 为了保证进化过程中群体微粒的多样性,p n s u g a n t h a n 2 1 】在标准微粒群算法中 引入了空间邻域的概念,并随着进化动态的改变选择阀值。j k e n n e d y 2 2 】引入拓扑邻 域的概念来调整邻域的动态选择,同时引入社会信念以增加邻域间的信息交流。x l i 提出了邻域的自适应调整方案2 3 1 。j r i g e t l 2 4 1 通过引入“吸引和扩散”两个算子, 动态调整“勘探 与“开发”比例,从而能更好地提高算法效率。为了保证种群多 样性,t h e n d t l a s s 2 5 1 提出了一种微粒群算法的优化方案。t 2 g y e n 2 6 1 在微粒群算法中 引入了动态种群策略,从而有效地提高了算法的计算效率。此外,还有通过增加变 异算子提高多样性的策吲2 7 , 2 8 】。 为了提高算法计算效率,y s h i 等【2 9 】引入了惯性权重,实验结果表明,惯性权 重从0 9 线性递减到0 4 时,效果较好【3 0 】。一般认为较大的惯性权重具有较好的全 局收敛能力,而较小的惯性权重则具有较强的局部收敛能力,但文献 3 1 的分析却 指出随着迭代次数的增加,惯性权重应不断增加。为了提高惯性权重的协调能力, y s h i 提出了基于模糊系统的惯性权重动态调整策略1 32 。,但是隶属度函数却难以选 择。通过引入平均速度信息统计量,k y a s u d a 3 3 提出了一种自适应的微粒群算法, 对惯性系数进行调节。彭宇等【3 4 】利用方差分析方法,给出了惯性权重较优的选择范 围。此外,在m c l e r c 【3 5 】的研究中,提出了收缩因子的概念,并给出一种参数选择 8 第一章引言 的方法,以确保算法收敛。文献 3 6 】提出了提高算法速度的几个加速算子,王俊伟 等提出了带有梯度加速的微粒群算法。基于生物学分析,赫然等引入了群体的 逃逸行为。 在一般微粒群算法中,微粒历史最好位置的确定相当于隐含的选择机制,因此, p j a n g e l i n e 3 吼引入了具有明显选择机制的改进微粒群算法。m l o v b j e r g t 4 0 1 提出了杂 交微粒群算法,微粒群中的微粒被赋予一个杂交概率,这个杂交概率是用户确定的, 与微粒的适应值无关。w z h a n g 4 1 l 通过增加微分进化算子,构造了一种混合微粒群 算法。f w a n g 等通过引入单纯形方法,构造了一个特殊的混合微粒群算法【4 2 】,还 有利用混沌搜索【4 3 】及与模拟退火算法阻1 构成的混合微粒群算法,这些算法都能有 效的提高微粒群算法的局部搜索能力。通过修改速度进化方程,a r a m a w e e r a 4 5 】提 出了不含微粒先前速度信息的改进微粒群算法,该算法由于不含原有的速度信息, 能有效提高算法的全局搜索能力。 c k m o n s o n 4 6 通过借鉴k a l m a n 滤波形式,提出了一种新卡尔曼微粒群算法, 能很好的提高算法的性能。类似地,j s u n 等提出了量子微粒群算法【4 7 】,该算法通 过引入吸引子的概念,有效提高了算法的计算效率。借助于贝叶斯统计网络,c k m o n s o n 4 8 提出了贝叶斯网络微粒群算法,该算法利用贝叶斯网络分析获得的信息, 能有效提高信息的利用率。 在微粒群算法的行为分析和收敛性分析方面,首先由e o z c a n 和c k m o h a n 采 用代数方法对几种典型的微粒群算法的运行轨迹进行了分析,给出了保证收敛性的 参数选择范围 4 9 , 5 0 】。m c l e r c 5 1 】针对微粒群算法的简化模型,分别采用代数方法、解 析分析和状态空间模型对微粒群算法的运行轨迹进行了分析。最近,j i a n g 等【5 2 。5 4 1 将微粒群算法中每个微粒运行轨迹视为一个随机过程,得到了较为深入的结果,但 仍无法直接应用于参数选择。 f s o l i s 和r w e t s 5 5 】对随机优化算法提出了其全局收敛需满足的条件,f r a n sv a n d e nb e r g h l l 6 j 利用该条件对标准微粒群算法的全局收敛性和局部收敛性进行了分 析,指出标准微粒群算法不能保证全局或局部收敛。提出了具有局部收敛性能的改 进微粒群算法【5 6 】,证明了该算法不具有全局收敛性能。文献 5 7 】中考虑了该算法在 不同邻域结构中的表现。i c t r e l e a 5 8 】通过分析微粒群算法的收敛性,给出了参数的 选择方式。 李衍达院士【5 9 】在研究生物系统的自组织现象时,发现生物系统在演化过程中采 取倾向于聚集中心的偏好性策略,这使得生物能更快、更好地产生对环境的适应性。 9 个性化微粒群算法研究 实际上,标准微粒群算法实际上是以微粒自身最好位置与群体最好位置的随机加权 平均为聚集中心,以倾向于聚集中心的定向搜索策略为聚集行为,以惯性方式为聚 集方式的一种群体智能算法。针对聚集中心的确定问题,崔志华等【6 0 l 提出了从群体 历史最好位置及个体最好位置构成的动态圆及椭圆内随机选择聚集中心的算法,该 算法能有效控制该聚集中心与群体的聚集中心的误差。针对聚集行为的仿真,曾建 潮等1 6 1 - 6 3 】提出了随机微粒群算法,该算法将群体最好的个体位置重新随机产生,体 现了算法的定向搜索与随机搜索策略的结合。崔志华等l 6 4 j 将速度与位置等同对待, 利用二者同时对空间进行搜索。针对聚集方式的模拟,提出了带控制器的微粒群算 法【6 锄9 1 ,该算法将进化方程作为控制对象,引入积分控制器及p i d 控制器,可以得 到振荡环节,对典型优化问题的仿真实验均取得了优于标准微粒群算法的结果,并 初步建立了标准微粒群算法、标准微粒群算法、带收缩因子的微粒群算法、随机微 粒群算法以及带控制器的微粒群算法的统一模型【70 。上述带控制器的微粒群算法相 当于一种开环控制,在此基础上,介婧等【7 1 j 提出了一种利用多样性的反馈控制的自 组织微粒群算法。然而,这三部分仅是生物系统的某个层面,整体论认为整体并不 等同于部分之和,因此,如何才能将其有效、合理地统一在一个模型中才是更为重 要的问题。从这个角度出发,曾建潮等在对诸如鸟群、鱼群等群体的相关生物学模 型进行分析的基础上,提出了一种广义微粒群算法统一模型【72 ,该方程从微粒需要 满足的收敛性、随机性、平衡性、方向性等条件出发,将聚集中心、聚集行为以及 聚集方式有机地统一起来,从而为高效的微粒群算法设计提供了一条可行途径。进 而,胡建秀等【_ 7 3 】给出了一种广义微粒群算法的具体实现形式。 二进制编码作为一种比较重要的编码形式,首先由j k e n n e d y 和r c e b e r h a r t 在1 9 9 7 年将标准微粒群算法应用于二进制编码【7 4 1 ,并作了大量数值研究【7 5 1 。 h y o s h i d a t 7 6 】在1 9 9 9 年、y f u k u y a m a 7 7 1 在2 0 0 1 年分别提出了混合编码的微粒群算 法。李炳宇掣7 8 】提出了求解约束优化问题的混合微粒群算法。为了将微粒群算法应 用于组合优化问题,k e w a n g 给出微粒群算法的位置与速度的类似定义l _ 7 9 j 。 在动态环境优化方面,h u 和e b e r h a r t 通过计算环境变化前后群体历史最优位 置p 。的适应值是否相等来检测环境是否发生了变化【8 0 】。每进化一次,重新计算p , 的适应值。c a r l i s l e 和d o z i e r 选择一个固定微粒或随机的多个微粒【8 1 】,这些微粒被 称为“s e n t r y ”,每次进化之前重新计算s e l l d y ”的适应值并与之前的适应值进行比 较,若不相等,说明环境发生了变化,否则环境没有变化。e s q u i v e l 基于进化算法 的概念提出环境发生变化后,微粒以概率己。动态突变的混合p s o 算法【8 2 】。微粒的 1 0 第一章引言 每一维坐标独立以概率巴。进行突变,坐标值可以由另外一个随机产生的值来代替。 c u i 和h a r d i n 重新定义了环境变化后微粒的适应值【8 3 1 ,微粒个体适应值和全局适应 值随着时间以蒸发常量不断减少,每次进化后将蒸发后的适应值与进化前的适应值 进行比较,选取最优的作为薪的个体最优适应值。以多样性为判据,胡静等瞰j 提出 了一种反馈控制的改进微粒群算法用于求解动态环境问题。 神经元网络训练方面,e n g e l b r e c h t 等蚓利用p s o 来训练神经元网络;j u a n g 8 6 】 将遗传算法与p s o 相结合来设计递归模糊神经元网络:m e s s e r s c h m i d t 等1 87 j 利用基 于p s o 的神经元网络来预测t i c t a c t o eg a m e 树叶节点的状态。应用结果都显示利 用p s o 设计神经元网络是一种快速、高效并具有潜力的方法。 在图像处理方面, k i n 船】应用k e n n e d y 等的离散p s o 方法解决多边形近似问题, 有效提高了多边形近似效果;p a r s o p o u l o s 等【8 9 j 利用p s o 对用于放射治疗的模糊认 知图的模型参数进行优化;c a o r s i 等1 9 0 利用基于p s o 的微波图像法来确定电磁散射 体的绝缘特性;w a c h o w i a k 等【9 l 】利用结合局部搜索的混合p s o 算法对生物医学图 像进行配准。 在调度问题方面,l i u 等 9 2 , 9 3 将标准微粒群算法扩展到离散生产调度问题,提 出了针对典型流水线调度问题的一种有效混合p s o 算法。在此基础上,结合特定问 题信息,提出了解决零等待流水线调度、带有限缓冲区的流水线调度、多目标流水 线调度和加工时间随机分布的流水线调度等一系列复杂问题的混合p s o 算法。 t a s g e t i r e n 等【9 4 】则提出置换f l o w s h o p 问题的基于可变邻域搜索的微粒群算法。 1 4 本文主要完成的工作 通过将标准微粒群算法中的微粒拓展为智能体,提出了个性化微粒群算法框 架,并通过微粒在每一代中的表现不同,赋予它自己独特的参数或结构控制。本文 的研究内容主要有: 第二章详细介绍了个性化微粒群算法框架,并从生物学角度论证了该想法的可 行性。在此基础上提出了个性化的惯性权重设计策略。为了提高种群多样性,分别 利用混沌策略与变
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 财务考试题及答案
- 中级英语写作知到智慧树答案
- 汽车维修工中级模拟习题(附参考答案)
- 成人护理学皮肤、运动、神经系统测试题(附答案)
- 药品注册管理办法试题(附答案)
- 化工总控工职业技能鉴定模拟练习题含答案
- 中学化学习题研究知到智慧树答案
- 2025年外墙清洗与外墙玻璃清洁服务合同范本
- 2025年二手车出口业务代理合同样本
- 2025版智慧城市建设招标投标服务合同
- 2023年高考作文备考之广东重点中学六校四联“鲁侯养鸟”分析
- 半导体制造工艺基础之扩散工艺培训课件
- 溶剂油MSDS危险化学品安全技术说明书
- 检验标本的采集与运送课件
- 济南版生物七年级下册课程纲要
- 福建升辉鞋业有限公司年加工EVA鞋底385万双、TPR鞋底65万双、PVC鞋底60万双项目环评报告表
- 胸腺瘤诊断治疗指南
- 班主任到场签到表
- 视网膜静脉阻塞.LM
- 海底捞-A级门店管理制度
- 《陶行知教育名篇》读书笔记(课堂PPT)
评论
0/150
提交评论