(计算机软件与理论专业论文)协同微粒群算法的研究及其在图像分割中的应用.pdf_第1页
(计算机软件与理论专业论文)协同微粒群算法的研究及其在图像分割中的应用.pdf_第2页
(计算机软件与理论专业论文)协同微粒群算法的研究及其在图像分割中的应用.pdf_第3页
(计算机软件与理论专业论文)协同微粒群算法的研究及其在图像分割中的应用.pdf_第4页
(计算机软件与理论专业论文)协同微粒群算法的研究及其在图像分割中的应用.pdf_第5页
已阅读5页,还剩47页未读 继续免费阅读

(计算机软件与理论专业论文)协同微粒群算法的研究及其在图像分割中的应用.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

山东师范大学硕士学位论文 协同微粒群算法的研究及其在图像分割中的应用 摘要 微粒群算法是上个世纪9 0 年代提出的一种基于群体智能理论的优化算法,通过群体 中粒子间的合作与竞争产生的群体智能指导优化搜索。相比于进化算法,微粒群算法保留 了基于种群的全局搜索策略,采用简单的速度位移模式,避免了复杂的遗传操作,同时它 特有的记忆使其可以动态跟踪当前的搜索情况以调整其搜索策略,具有全局收敛能力和鲁 棒性,且不需要借助问题的特征信息。微粒群算法的特点吸引了大量学者对其进行研究, 并被广泛的应用到了各个领域。 微粒群算法是基于同种群体内信息共享的假设而提出的,它反映了在一个种群中的个 体之间的合作关系。然而,在自然界的生态系统中,很多物种是通过和其他物种相互作用 来提高自己的生存能力的。这种相互作用存在于所有的生物机体中,从细胞到高级动物, 同时也存在于动物和植物之间。为了克服微粒群算法的缺点并且受到协同进化的启发,从 而产生了协同微粒群算法的思想。 图像分割是图像处理到图像分析的关键步骤。由于图像目标和背景之间差异的多样 性以及噪声的影响,使得图像分割变得困难,目前图像分割仍然是研究的热点之一。传统 的图像分割方法对某些图像是有效的,但是对一些特殊领域的图像和具有特殊特征的图像 来说并不一定有效。目前还没有一种通用的图像分割方法。 本文致力于研究协同微粒群算法,并将其应用到图像分割中。本文的主要工作为: 1 、提出了一种协同微粒群算法 受自然界共生现象的启发,将协同进化与微粒群算法相结合,并将高斯概率分布应用 到随机数的生成以及粒子变异中,提出了一种使用高斯分布的协同微粒群算法( c p s o - g ) , 进化过程中,粒子不仅要与本种群内的其他粒子交换信息而且还要受到其他种群的影响。 利用高斯概率分布来生成随机数,可以加速局部搜索收敛速度。将高斯概率分布应用到粒 子变异中,此分布能够增加粒子多样性从而跳出局部极值点。实验数据表明,此算法在一 定程度上避免了陷入局部极值点并且加快了收敛速度。 2 、将协同微粒群算法用于图像分割 在众多图像分割方法中,模糊c 均值( f c m ) 聚类算法是一种结合无监督聚类和模糊 集合概念的图像分割技术,比较有效,但存在着受初始聚类中心和隶属度矩阵影响,可能 山东师范大学硕士学位论文 收敛到局部极小的缺点。根据微粒群算法和模糊c 均值聚类的特点,提出一种基于 c p s o g 及模糊c 均值聚类的图像分割方法。实验结果证明这种算法可以有效地克服模 糊c 均值聚类算法依赖初始聚类中心的不足,获得较好的分割效果。 关键词:微粒群算法;协同进化;协同微粒群;模糊c 均值聚类;图像分割 分类号:t p 3 9 1 7 2 l i 山东师范大学硕士学位论文 r e s e a r c ho fc o e v o l u t i o np a r t i c l es w a n n0 p t i m i z a t i o na n di t sa p p l i c a t i o n i ni m a g es e g m e n t a t i o n a b s t r a c t p a n i c l es w a 肌o p t i m i z a t i 衄( p s 0 ) w 勰p r c n t e di l l2 0 t hc e n t u 巧9 0 s ,i t s 粕叩t i m i z a t i o na l g o r i i h mb a d o nt h e o 巧o f 洲i i l t c u 蟾e n c e i np s o ,s w a 瑚i n t e l l i g e n c eg u i d e st h eo p t i m i z a t i o n 陀a r c h ,w h i c hi s p r o d u c e db yc o o p e 豫t i o na n dc o m p e t i t i o na m o n gp a f t i c l e si ns w a f m c b m p a r e dw i t he v o l u t i o na l g o r i t h m , g l o b a l a f c h i i l gs t r a t e g yb a do np o p u l a t i o ni s 他r v e d ,s i m p l es p e e dd i s p l a c e m e n tp a t t e mi sa d o p t e da n d c o m p l e xg e n e t i co p e m t i o ni sa v o i d e di np s o t h em e m o r yw h i c hp s o h a sm a k ei tt f a c kd y n a m i cs e a r c h i n g i n s l a n c ct oa d j u s t a r c h i n gs t m t e g y p s oh 髂酎o b a lc o n v e r g e n c ea b i l i t ya n dr o b u s t n e s sa n dn e e d n t c h a r a c t e ri n f 0 咖a t i o no fp r o b l e m 1 kf e a t u r e so fp s oh a v ea t t f a c t e dm 弛ys c h o l 缸s ,p s 0h 勰a p p l i e dt 0 k i n d so ff i e l d sw i d e l y p s 0i sb a s c do nah y p o t h e s i st h a ti n f 0 咖a “o ns h a f i n gi l io n es w a 肋,i tr e n e c t sc o u a b o f a t i o na m o n g i n d i v i d u a l s h o 、e v e r i nn a t u m le c o s y s t c m ,m a n ys p c c i e si m p m v es u r v i v a la b i l i t yt h r o u g hi n t e r a c t i o nw i t h o t h e rs p c c i e s t h ei n t c r a c t i o ne x i s t si na uo f g 锄i s m s ,f 幻m ut oa d v 如c c db i o l o g y ,e x i s t sb e m e e na n i m a l a n dp l 姐ta sw e u f 0 rc o n q u e 血g 圮d e f e c t s0 fp s o 龃di l l u m i n e db yc o c v o l u t i o n ,c 0 e v o l u t i o np s oi s p r o p o s e d t _ l l ei m a g es e g m e n t a t i o ni sak e yp m s so ft h ei m a g e 觚a l y s i sa n dt h ei m a g ec o m p r e h e n s i o n b e c a u s eo f t h ei i l n u e n c eo ft h ec o m p l i c a t e db a c k g r o u n d ,t h eo b j e c tc h a r a c t e r i s t i c sd i v e f s i t ya n dt h en o i s e ,t h ei m a g e g m e n t a t i o ni st h ed i f f i c u l ta n dh o t 舱缸c hi s s u e so nt h ei m a g ep r o c c s s i n g t h et r a d i t i o n a ls e g m e n t a t i o n m e t h o d sa 陀e f f 醯t i v ct os o n 圮i m a g e s ,b u ta r cl i i i l i t e dt oo t h e ri i i l a g e sw h i c ha r ca p p l i e dt ot h ee s p e c i a lf i e l d 强dc h a m c t e r i s t i c s p 托辩n t l y ,t h eg e n e r a l 辩罟珊e n t a t i o nm e t h o di sn o tf o u n d m u c ha t t e n t i o nh a sb e e np a i dt ot h ec o m b i n a t i o no fp a n i c l es w a 咖o p t i m i z a t i o na n dc 0 - c v o l u t i o n ,t h e nt o c r e a t eac 0 c v o l u t i o np a i t i c l es w a 咖o p t i m i z a t i o na l g o r i t h i i lw h i c hs u p p o r t i n gi m a g es e g m e n t a t i o ni nt h i s p a p e r 1 飞em a i nw o f ki sa sf o l l o w s : 1 p r o p 0 辩ac 0 - e v o l u t i o np a r t i c k 洲缸mo p t i m 边a t i o na 1 9 0 r i t h m l ki u u m i 聆db yt h es y m b i o s i si nn a t u r e ,一e v o l u t i o ni sc o m b i n e dw i t hp a n i c l es w a 珊o p t i m i z a t i o n a l g o f i t h i i lu s i i l gg a u 醛i a nd i s t r i b u t i o n ,c r e a t eac o - e v o l u t i o np a n i c l es w a 珊o p t i m _ i z a t i o na l g o r i t h mu s i n g g a u s s i 柚d i s t r i b u t i o n ( c p s o g ) i nt h ep m 豁o fe v 0 1 u t i o n ,p a r t i c l e sn o to l l l ye x c h a n g et h ci n f o 珊a t i o nw i t h i i i 山东师范大学硕士学位论文 o t h e rp a f t i d e si nm es 锄e 跚a n i l ,b u tw i t hp a n i d e si no t h e rs w a 咖s g 叭鼹i a nd i s t r i b u t i o ni sa p p l i e dt ot h e g e n e m t i o no fm d o mn u m b e 璐a l l dp a j t i c l ev a r i a t i o nw h i c hc a np m v i d e saf a s t e rc o n v e r g e n c ei n1 0 c a ls e 盯c h a n di n c r c a t h ed i v e 硌i t yo fp a n i c k s t h a tc a nh e l pt h ep a n i c l ee s c a p i n gf r o ml o c a le x t r e m u m n u m e r i c e x p e r i m e n t sp r 0 v et l l ev a l i d i t yo ft h i sa l g o r i t h m 2 n ec 0 创0 l u t i o np a r t i c l e 哪姗 0 p t i i i l i z a t i o na 1 9 0 r i t h i i l鹏n t i o n e da b o v ei s a p p l i e d t 0i m a g c g m e n t a t i o n n ef h z z yc 船柚s ( f c m ) c l u s t e f i n ga l g o 矗t h i i li s 觚e 舭c t i v ei m g e g i i l e n t a t i o na l g o r i t h i l l b u ti ti s n s i t i v et 0i n i t i a lc l u s t e 血gc e n l e ra n dm e m b e r s h i pm a t r i x 蛐dl i k c l yc o n v e r g e si n t ot h el o c a lm i n i m u m , w h i c hc a u st l 怆q u a l i t yo fi i i l a g es e g m e n t a t i o nl o w e lan e wi i i l a g cs e g m e n l a t i o na 1 9 0 r i t h mi s p f o p o s e d , w h i c hc o m b k sn l cc p s o - ga n df c mc l u s t e 血g s o m ee x p c r i m e n tr e s u l l sa r e 西v e n ,w h i c hs h o wl l l a tt h e a k o r i t h i i lh a st h ee 矗e c t i v ea b i l i t yo fs e a r c h i n gg l o b a lo p t i m a ls o l u t i o n y w o r d s :p a n i c l es w 姗o p 缸i z a t i 伽;c 0 e v o l u l i 伽;c 0 - e v o l u “伽p a r t j c l es w a 珊0 p t i m i z a t i o n ;f u z z y c 。m e a n s ( f c m ) c l u s t e 咖g ;i n l a g es e g m e n t a t i o n c l a s s i 矗姐t i o n :t p 3 9 1 7 2 i v 山东师范大学硕士学位论文 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或 撰写过的研究成果,也不包含为获得( 注:如没有其他需要特别声明的, 本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名李菲嘉 导师签字 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定,有权保留并向国 家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅和借阅。本人授权刳堑可 以将学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名: 夺弃菲 签字日期:2 0 0 万年j 月如日 山东师范大学硕士学位论文 第一章绪论 本章首先介绍了微粒群算法的研究背景及前沿,其次阐述了图像分割的发展现状,最 后介绍了本文的主要工作和组织结构。 1 1 研究现状 1 1 1 微粒群算法的研究现状 微粒群优化算法( p a r t i c l es w a n no p t i m i z a t i o na 1 9 0 r i t h m ,p s 0 ) 是由美国社会心理学家 j a m e sk 七n n e d y 和电气工程师r u s s e ue b e r h a n 于1 9 9 5 年提出的一种新的进化计算算法1 1 j , 其基本思想是受他们早期对许多鸟类的群体行为进行建模与仿真研究结果的启发,并利用 了生物学家f r 孤kh e p p n e r 的生物群体模型。 由于p s o 概念和参数调整都很简单而且容易编程实现,它既保持传统进化算法深刻的 群体智慧背景,同时又有自己许多良好的优化性能因此,p s o 一经提出,立刻引起进化计 算领域学者们的广泛关注,短短几年便获得快速发展,在诸多领域得到应用而且应用范围越 来越广泛,已形成学术界一个新的研究热点。 在微粒群算法的改进方面,首先是由k e n n e d v 和e b e r h a n 在1 9 9 7 年提出的二进制p s o 算法【2 】为p s o 算法与遗传算法的性能比较提供了一个有用的方式,该方法可用于神经 网络的结构优化。其次,为了提高算法的收敛性能,s h i 和e b e r h a r t 于1 9 9 8 年对p s 0 算 法的速度项引入了惯性权重w 【3 】,并提出在进化过程中动态调整惯性权重以平衡收敛的全 局性和收敛速度,该进化方程己被相关学者称之为标准p s 0 算法。c l e r c 于1 9 9 9 年在进 化方程中引入收缩因子以保证算法的收敛性【4 】,同时使得速度的限制放松。有关学者己通 过代数方法对此方法进行了详细的算法分析,并给出了参数选择的指导性建议。 a m g e l i n e 于1 9 9 9 年借鉴进化计算中的选择概念i5 。,将其引入p s o 算法中。通过比较 各个微粒的适应值淘汰掉差的微粒,而将具有较高适应值的微粒进行复制以产生等数额的 微粒来提高算法的收敛性。而h v b j e r g 等人进一步将进化计算机制应用于p s o 算法【酬, 如复制、交叉等,给出了算法的交叉的具体形式,并通过典型测试函数的仿真实验说明了 算法的有效性。 为了提高p s 0 算法收敛的全局性,保证微粒的多样性是关键。为了保证进化过程中 群体中微粒的多样性,s u g 觚t h 觚在标准p s o 算法中引入了空间邻域的概念n 将处于同 山东师范大学硕士学位论文 一个空间邻域的微粒构成一个子微粒群分别进行进化,并随着进化动态地改变选择阈值以 保证群体的多样性;k c n n e d y 引入邻域拓扑的概念来调整邻域的动态选择【8 】,同时引入社 会信念将空间邻域与邻域拓扑中的环拓扑相结合以增加邻域间的信息交流,提高群体的多 样性。i j d v b j e r g 等人于2 0 0 1 年将遗传算法中的子群体概念引入p s o 算法中,同时引入了 繁殖算予以进行子群体的信息交流。 很多学者在p s 0 算法的行为分析和收敛分析方面进行了大量的研究工作。首先是采 用代数方法对几种典型的p s o 算法的运行轨迹进行了分析,给出了保证收敛性的参数选 择范围【9 1 。在收敛性方面,v a nd e nb e r g l l 引用s o l i s 和w e t s 关于随机性算法的收敛准则, 证明了标准p s o 算法不能收敛于全局最优解,甚至于局部最优解【1 0 】。证明了保证收敛的 p s o 算法能够收敛于局部最优解,而不能保证收敛于全局最优解。 在p s 0 算法的应用方面,最早被应用于人工神经网络的训练方法,k e n n e d v 和e b e r h a n 成功地将p s o 算法应用于分类x o r 问题的神经网络训练。随后,p s o 算法在函数优化、 约束优化、极大极小问题、多目标优化等问题中均取得了成功的应用。特别是在电力系统、 集成电路设计、系统识别、状态估计等问题中的应用均有相关报道。 协同进化算法是近十几年来在协同进化论基础上提出的一类新的进化算法,协同进化 算法在进化算法的基础上,考虑了种群与环境之间、种群与种群之间在进化过程中的协调。 虽然在这方面的研究起步较晚,但由于协同进化算法的优越性,越来越多的学者对此进行 了研究,目前协同进化算法已成为当前进化计算的一个热点问题。因而协同微粒群算法也 是微粒群算法发展的一个方面,目前已有一些对多种群协同进化的研究。 l d v b j e 玛m ,r 弱m u s s e ntk 心i i l k l 1 1 1 j 于2 0 0 1 年提出了一种混合微粒群算法,算法中 引入了多种群和遗传算法中繁殖的概念。实验中将混合微粒群分为2 个,4 个,6 个子 种群,对实验结果进行详细地对比和分析,表明该算法极大地提高了算法的收敛性能。 h 0 n g y u nm e n g ,x i a o - h u az h 卸g ,s a i l y a n gu u 【1 2 1 于2 0 0 5 年提出了一种求解多目标优化问题 的协同微粒群算法,该算法加入了协同进化算子、竞争突变算子和新的选择机制来指导整 个进化过程,通过在微粒之间信息的共享和交换,在缩小了搜索空间的同时保持了种群的 多样性,避免陷入局部最优。b e nn i u ,y u n l o n gz h u ,x i a o x i a nh e 【1 3 】于2 0 0 5 年受到自然生态 系统中共生现象的启发,提出了一种多种群协作微粒群算法( m c p s o ) ,建立了一个 m a s t e r - s l a v e 模型,该模型中有一个m a s t e r 种群和多个s l a v e 种群。s l a v e 种群个自独立地 执行标准微粒群算法以保持个体多样性,而m 硒t e r 种群则依据自身及各s l a v e 种群的知识 来更新。r e n a t oa k r o h l i n g ,f r a i i l 【h o f f m 强n ,k a n d r od o ss a n t o sc o e l h o 【1 4 】于2 0 0 4 年将高斯 2 山东师范大学硕士学位论文 分布引入c o p s o ,并用于求解最大最小问题。r e n a t oa k r o h l i n g ,k 飙d r 0d o ss a n t o s c o e l h o 【1 5 】于2 0 0 6 年又提出了一种求解限制优化问题的协同微粒群算法。 总之,p s o 算法的优越性吸引了很多学者对其进行了大量的研究工作,并被广泛应 用于各个领域。但是,p s o 算法易于陷入局部极小,而协同进化算法由于考虑了种群与 环境之间,种群与种群之间在进化过程中的协调问题,可以与p s o 算法相结合,所以协 同微粒群算法具有广阔的研究前景。 1 1 2 图像分割的研究现状 在对图像的研究和应用中,人们往往仅对图像中的某些部分或者说某些区域感兴趣。 这些部分常称为目标或前景( 其他部分称为背景) ,它们一般对应图像中特定的、具有独 特性质的区域。为了辨识和分析目标,需要将它们从图像中分离提取出来,在此基础上才 有可能对目标进一步利用。图像分割就是指把图像分成各具特性的区域并提取出感兴趣目 标的技术和过程。这里的特性可以是像素的灰度、颜色和纹理等,预先定义的目标可以对 应单个区域,也可以对应多个区域。 图像分割是由图像处理到图像分析的一个关键步骤,在图像工程中占非常重要的位 置,也是进一步图像理解的基础。一方面它是目标表达的基础,对特征测量有重要的影响。 另一方面,因为图像分割及其基于分割的目标表达、特征提取和参数测量等将原始图像转 化为更紧凑的形式,使得更高层的图像分析和理解成为可能。 图像分割的研究最早可以追溯到2 0 世纪6 0 年代,经过四十多年的研究,国内外学者 已经提出了各种算法上千种,但目前还没有一种适合于所有图像的通用的分割算法,绝大 多数算法都是针对具体问题而提出的。另一方面,给定一个实际应用要选择适合的分割算 法仍是一个很麻烦的问题,由于缺少通用的理论指导,常常需要反复的进行实验。在现有 的分割算法中,大体上可以分为以下几种:阈值分割法【1 6 1 、区域增长技术【1 7 】【1 8 】【1 9 1 、边缘 检测方法【1 6 】。另外,在这些经典算法的基础上,又提出了基于小波变换的分割算法【2 0 1 、 基于数学形态学的分割算法【2 1 1 、基于遗传算法的分割方法【2 2 1 【2 3 1 、聚类分割方法【2 4 】【冽【2 6 】【2 7 】 等等。 1 2 研究意义 1 微粒群算法自提出以来,由于它的计算快速性和算法本身的易实现性,已经在很 多领域得到了广泛的应用。但是由于微粒群算法提出的时间并不长,存在的问题还很多, 3 山东师范大学硕士学位论文 如何改进微粒群算法存在的不足成为值得研究的问题。 2 协同进化算法是近十几年来在协同进化论基础上提出的一类新的进化算法,协同 进化算法与进化算法的区别在于:协同进化算法在进化算法的基础上,考虑了种群与环境 之间、种群与种群之间在进化过程中协调。将协同进化和微粒群算法相结合,比较贴近自 然现象,能有效的维持粒子的多样性,从而避免陷入局部极值点,多种群同时进行搜索, 可以加快收敛速度。 3 图像分割技术在图像工程中占居重要地位,它是计算机视觉和图像理解的最基本 问题,其分割结果关键性地决定图像处理系统高层模块的性能。只有在图像分割的基础上 才能对目标进行特征提取和参数测量,使得更高层的图像分析和理解成为可能。因此对图 像分割方法的研究具有十分重要的意义。将基于协同进化的微粒群算法应用到图像分割, 能够在获得更好的分割效果的基础上提高效率。 1 3 本文的创新点 本文致力于研究协同微粒群算法及其在图像分割中的应用问题,主要工作体现在以下 方面: 1 、提出了一种使用高斯分布的协同微粒群算法 将协同进化与微粒群算法相结合,提出了一种协同微粒群算法,进化过程中,粒子 不仅要与本种群内的其他粒子交换信息而且还要受到其他种群的影响;将高斯分布应用于 随机数的生成和变异操作中。利用高斯概率分布来生成随机数,可以加速局部搜索收敛速 度。将高斯概率分布应用到粒子变异中,此分布能够增加粒子多样性从而跳出局部极值点。 为了验证这种协同微粒群算法的有效性,本文选取了一些经典的标准测试函数进行了大量 的实验,并同其他改进的微粒群算法进行比较,实验数据表明,此算法在一定程度上提高 了全局搜索能力并且加快了收敛速度。 2 、将协同微粒群算法用于图像分割 在众多图像分割方法中,模糊c 均值( f c m ) 聚类算法是一种结合无监督聚类和模糊 集合概念的图像分割技术,比较有效,但存在着受初始聚类中心和隶属度矩阵影响,可能 收敛到局部极小的缺点。根据微粒群算法和模糊c 均值聚类的特点,提出一种基于 c p s o g 及模糊c 均值聚类的图像分割方法。试验证明这种算法可以有效地克服模糊c 均值聚类算法依赖初始聚类中的不足,获得较好的分割效果。 4 山东师范大学硕士学位论文 1 4 本文的组织 本文的组织如下: 第一章绪论。 第二章介绍了微粒群算法的基础知识,包括微粒群算法的提出、算法的原理和算法流 程、标准微粒群算法,并将微粒群算法与其他进化算法进行了对比。 第三章详细介绍了图像分割的一些方法,包括图像分割的数学描述、使用阈值的图像 分割方法、基于梯度的图像分割方法、边缘检测和连接以及区域增长。 第四章提出了一种使用高斯分布的协同微粒群算法( c p s o g ) 。首先给出了相关的 研究背景;其次详细介绍了未使用高斯分布的协同微粒群算法的协同方式和信息交流方 式,在此基础上建立协同微粒群算法;然后,将高斯概率分布引入协同微粒群算法中;最 后介绍仿真实验情况,实验结果表明新算法的有效性。 第五章提出了一种c p s o g 与模糊c 均值聚类相结合的图像分割算法。首先介绍了 模糊c 均值聚类算法,然后将c p s o g 算法应用于基于模糊c 均值聚类的图像分割算法 中,最后介绍了实验情况,结果表明新算法的优越性。 第六章总结了本文的主要工作和进一步的研究方向。 5 山东师范大学硕士学位论文 第二章微粒群算法 微粒群算法是协同微粒群算法的理论基础之一。本章主要介绍了微粒群优化算法的原 理、算法的发展和算法的应用。 2 1 引言 k e n n e d v 和e b e r h a n 在1 9 9 5 年的匝e e 国际神经网络学术会议上正式发表了题为 “p a r t i c l es w 锄o p t i m i z a t i o n ”的文章,标志着微粒群算法的诞生。 微粒群优化算法是一种进化计算技术,是进化计算领域中的一个新的分支,其源于对 鸟群和鱼群群体运动行为的研究。与基于达尔文“适者生存,优胜劣汰”进化思想的遗传 算法不同的是,微粒群优化算法是通过个体之间的协作来寻找最优解的。文献【1 1 引用了生 物社会学家e o w l i o s n 关于生物群体的一段话,“至少在理论上,一个生物群体中的一员 可以从这个群体中所有其他成员以往在寻找食物过程中积累的经验和发现中获得好处。只 要食物源不可预知地分布于不同地方,这种协作带来的优势可能变成决定性的,超过群体 中个体之间对食物竞争所带来的劣势 【捌。这段话的意思是说生物群体中信息共享会产 生进化优势,这也正是微粒群优化算法的基本思想。 p s o 算法概念简单,容易实现,其代码只有短短的几行,和其他优化算法相比,这 也是它的优点之一。短短几年里,p s o 算法己经获得了很大的发展,并己经在一些领域 得到应用,现在己出现不少相关的文献,已经成为一个研究热点。 2 2 微粒群优化算法原理 自然界中一些生物的行为特征呈现群体特征,可以用简单的几条规则将这种群体行为 ( s w a 加b e h a v i o r ) 在计算机中建模,实际上就是在计算机中用简单的几条规则来建立个体 的运动模型,但这个群体的行为可能很复杂。例如,r y e n o l d s 使用了下列三个规则作为简 单的行为规则【2 9 l : 1 ) 向背离最近的同伴的方向运动 2 ) 向目的运动 3 ) 向群体的中心运动 在这个群体中每个个体的运动都遵循这三条规则,通过这个模型来模拟整个群体的运 动。p s 0 算法的基本概念也是如此,每个微粒( p a n i c l e ) 的运动可用几条规则来描述, 因此p s o 算法简单,容易实现,越来越多地引起人们的注竟。 山东师范大学硕士学位论文 2 2 1 基本原理 微粒群优化算法起源于对简单社会系统的模拟。最初设想是模拟鸟群觅食的过程。但 后来发现p s o 算法是一种很好的优化工具。设想这样一个场景:一群鸟在随机搜索食物。 在这个区域里只有一块食物,所有的鸟都不知道食物在那里,但是它们知道当前的位置离 食物还有多远。那么找到食物的最优策略是什么呢? 最简单有效的方法就是搜寻目前离食 物最近的鸟的周围区域。p s o 算法从这种模型中得到启示并用于解决优化问题。p s o 算 法中,每个优化问题的解都是搜索空间中的一只鸟,称之为“微粒 。所有的微粒都有一 个由被优化的函数决定的适应值,每个微粒还有一个速度决定他们飞翔的方向和距离。然 后微粒们就追随当前的最优微粒在解空间中搜索,p s o 算法初始化为一群随机微粒( 随机 解) ,然后通过迭代找到最优解。在每一次迭代中,微粒通过跟踪两个“极值来更新自 己。第一个就是微粒本身所找到的最优解,这个解叫做个体极值,另一个极值是整个种群 目前找到的最优解,这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分 作为微粒的邻居,那么在所有邻居中的极值就是局部极值。这就是p s o 算法的所谓全局 版和局部版,前者速度快不过有时会陷入局部最优,后者收敛速度慢一点不过很难陷入局 部最优。在实际应用中,可以先用全局p s o 算法找到大致的结果,再由局部p s o 算法进 行搜索。 下面是关于基本微粒群算法的介绍: 假设在一个n 维空间进行搜索,则有: x ;= ( z n ,x ,z “) 为微粒f 的当前位置。 一( ,n ,v , ,“) 为微粒f 的当前飞行速度。 只一( pn ,p 川,p 抽) 为微粒f 所经历的最好位置,也就是微粒f 所经历过的具有 最好适应值的位置,称为个体最好位置。对于最小化问题,目标函数值越小,对应的适应 值越好。 为了讨论方便,设,( x ) 为最小化的目标函数,则微粒f 的当前最好位置由下式确 定 只o + d 一 :名,+ d , 若- 厂 ,o + 1 ) ) 厂( o ) ) 萄“o + 1 ) ) 厂( 置 ( 2 1 ) 设群体中的微粒数为s ,群体中所有微粒所经历过的最好位置为名( f ) ,称为全局 7 山东师范大学硕士学位论文 最好位置。则 乞o ) i 昂1 3 f ) ,只( f ) ,只。州厂( 只( f ) ) 一m i n i 厂蛾1 3 f ) ) ,假1 3 f ) ) ,化o ) ) i 有了以上定义,基本微粒群算法的进化方程可描述为: o + 1 ) 一b o ) + c l ,o ) 【岛o ) 一勤o ) 】+ c z ,2 j o ) 【p 量o ) 一嘞o ) 】 x o + 1 ) - z o ) + y o + 1 ) ( 2 2 ) ( 2 3 ) ( 2 4 ) 其中:下标“j ”表示微粒的第j f 维,j 一1 ,2 ,以,“f 表示微粒f , f 一1 ,2 ,f 表示第f 代,c ,、c :为加速常数,通常在o 2 间取值,l 口【厂( o ,1 ) , ,:口u ( o ,1 ) 为两个互相独立的随机函数。 从上述微粒进化方程可以看出,c ,调节微粒飞向自身最好位置方向的步长,c :调节 微粒向全局最好位置飞行的步长。为了减少在进化过程中,微粒离开搜索空间的可能性, ,u 通常限定于一定范围内,即y 玎 一 ,m 。,。, 。如果问题的搜索空间限定在 一l ,m 。, ,m 。, 内,贝i j 可设定v 。一七菇。,o 1 墨七1 o 。 基本微粒群算法的初始化过程为: ( 1 ) 设定群体规模n 。 ( 2 ) 对任意f ,j 在 一工m 。,z m 。 内服从均匀分布产生x u 。 ( 3 ) 对任意f ,| 在 一v m 。,v m 。 内服从均匀分布产生y u 。 ( 4 ) 对任意f ,设y ,一石;。 2 2 2 基本p s 0 算法流程 ( 1 ) 依照初始化过程,对微粒群的随机位置和速度进行初试设定。 ( 2 ) 计算每一个微粒的适应值。 ( 3 ) 对于每个微粒,将其适应值与所经过的最好位置曰的适应值进行比较,若较好, 则将其作为当前的最好位置。 ( 4 ) 对于每个微粒,将其适应值与全局所经历的最好位置只的适应值进行比较,若较 好,则将其作为当前的全局最好位置。 山东师范大学硕士学位论文 ( 5 ) 根据方程( 2 3 ) 、方程( 2 4 ) 对微粒的速度和位置进行进化。 ( 6 ) 如未达到结束条件通常为足够好的适应值或达到一个预设最大代数( g m 。) ,则返 回步骤( 2 ) 。 2 2 3 两种基本进化模型 在基本p s o 算法中,根据直接相互作用的微粒群定义可构造p s o 算法的两种不同版 本,也就是说,可以通过定义全局最好微粒( 位置) 或者局部最好微粒( 位置) 构造具有 不同社会行为的p s o 算法。 1 g b e s t 模型( 全局最好模型) g b e s t 模型以牺牲算法的鲁棒性为代价提高算法的收敛速度,基本p s 0 算法就是该模 型的具体实现。在该模型中,整个算法以该微粒为吸引子,将所有微粒拉向它,使所有微 粒最终收敛于该位置。这样,如果在进化过程中,最好解得不到有效地更新,则微粒群将 出现类似于遗传算法中的早熟现象。为了讨论方便,将p s o 的进化方程重新表述如下: bo ) 峨o ) ,只o ) ,co ) i l ,( c ( f ) ) 一m i n i ,( 昂o ”,厂( 只( f ”,( 只o ) ) i y o + 1 ) - v fo ) + c 1 _ ,o ) 【p 牙( f ) 一x fo ) 】+ c 2 吃,o ) 【p o ) 一x o ) 】 ( 2 7 ) ( 2 8 ) 其中,乞o ) 称为全局最好位置,对应于称之为全局最好微粒所处的位置。 2 i j b e s t 模型( 局部最好模型) 为了防止g b e s t 模型可能出现的早熟现象,i j b e s t 模型采用多吸引子代替g b e s t 模型 中的单一吸引子。首先将整个微粒群分解为若干个子群,在每一子群中保留其局部最好微 粒只( f ) ,称之为局部最好位置或邻域最好位置。假设第f 个子群处在长度为z 的领域内, 则l b e s t 模型的进化方程可描述为 : ;一l 霉。o ) ,只一“。o ) ,一。o ) ,丑o ) ,足+ 。p ) ,e + ,一,o ) ,+ ,o ) i ( 2 9 ) 卑o + ,) k i 厂仍o + 1 ) ) 一m i n 厂( 口) i ,讹m ( 2 1 0 ) y fo + z ) 一( f ) + c - 1 ,o ) 【p 驴o ) 一勤o ) 】+ c 2 ,2 j ( f ) 【p 酊o ) 一z f ( f ) 】 ( 2 1 1 ) 山东师范大学硕士学位论文 注意:子群,中的微粒与其在搜索空间域内所处的位置无关,仅依赖微粒的索引数 或者微粒的编码。这样一方面避免了微粒间的聚类分析,节省了计算时间,另一方面能够 加快更好解信息在整个群体间的扩散。 很容易看出,g b e s t 模型实际上是l b e s t 模型在z - s 时的特殊情况。实验证明:z 一1 时的l b e s t 模型,其收敛速度低于g b e s t 模型,而1 z 4 z 收缩因子 m a s t e r 种群的速度和位置更新结束后,要计算每个微粒的适应值,找出最好的微粒。 如果最好的微粒的位置差于g ,则继续保留g 。否则,将g 更新为最好微粒的位置。更 新结束后要将m a s t e r 种群清空。 协同微粒群算法流程 3 2 b e g i n 加ri - lt on 扣r j = lt om 初始化每个譬嘶e 群体中的每个微粒 e n d 扣r p n 颤归,。 如ri - 1t on 计算每个微粒的适应值找出最好的微粒 将最好的微粒加入m 伍啦e r 种群o e n 蜘r 对眦啦e r 种群中的微粒找出最好的微粒作为g 清空嗍嘁e r 种群o w h t l e ( g 不满足条件或未达到迭代次萎鳓 f o ri = lt on 将每个妇e 种群按概率分为两部分 其中一部分进行交叉、变异操作 另一部分按照公式( 4 。n 和h 更新速度和位置 计算每个微粒的适应值找出最好的微粒 更薪p 、l 和致 将最好的微粒加入呐妣r 种群 p 靠朗归r 对m n s t e r 种群中的每个微粒根据公式1 4 。4 ) 和4 。s ) 更耨速度和位置计算适应值更额g 清空m n s t e r 种群 p ,l m i 跆 砌d 山东师范大学硕士学位论文 4 4 使用高斯分布的协同微粒群算法 我们在m p s c 算法的基础上又提出了一些改进,这主要体现在高斯分布在随机数的 生成和粒子变异上的应用,我们称这个算法为使用高斯分布的协同微粒群算法 ( c p s o g ) 。一些学者已经将高斯分布应用于随机数的产生1 1 4 】【1 5 1 ,在这里我们将借鉴这 些学者的方法,将高斯分布应用到m p s c 算法中。 高斯概率分布可以加速局部搜索收敛速度,对于s l a v c 种群,我们将公式( 4 1 ) 改为: 哆o + 1 ) 一z ( w 1 ,;o ) + g 口“1 c 1 ( p ;一z :o ) ) + g 口h 2 c 2 ( 一z :o ) ) + 弘“3 c 3 ( g x ;o ) ” ( 4 7 ) 这里g 口“,g 口“:,g 口“,是由高斯概率分布产生的在区间【o ,1 】上的随机数。 交叉操作:父代位置每一维的数学交叉产生子代的每一维的位置。 幽泓l o i ) 一p ix 胛,e n t l “) + ( 1 一鼽) 脚,明t 2 j ) 西f 瞄2 i ) 一a 艘翮f 2 f ) + ( 1 一见) p 口r e 以f 1 f ) 其中见是介于0 和1 之间的随机数。子代的速率向量是每个父代的速率向量规范化 嘲嫡。每篙b 刊 i p 口旭以f l ( y ) + p 口,g 玎f 2 ( ,) | 。 如峨( ;) 。产堕掣型掣i p 口瑚以苫) i l p 口,朗f l ( ,) + 艘硎f 2 ( 1 ,) l 。 。 变异操作:引入高斯分布,使用以下方程1 4 q m h f o ) 。x ( 1 + 肛“黜胁,l ( 口) ) 仃设为每一维搜索空间长度的0 1 倍,x 是粒子每一维的位置。此分布能够增加粒子 多样性从而跳出局部极值点。 对于m a s t e r 种群,我们将公式( 4 4 ) 改为: 叫w ( a ) 一z ( w 叫w + 肛比l c i ( g 尸一

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论