（计算机软件与理论专业论文）基于微粒群算法的聚类算法.pdf

中文摘要 数据挖掘是从大量数据中挖掘出未知的、有价值的模式或规律的复杂过程。 聚类分析是数据挖掘中的一个重要研究领域，其目的是按照事物间的相似性对给 定事物进行区别和分类，并采用数学方法对其属性进行研究和处理。聚类分析算 法大致可划分为以下几类：层次聚类算法、分割聚类算法、基于现实约束的聚类 算法、机器学习中的聚类算法以及用于高维数据的聚类算法。动态聚类算法是分 割聚类算法中的一个重要分支，但现有的动态聚类算法在运算过程中容易陷入局 部最小和对初始值敏感等不足，限制了它的发展。很多学者尝试采用全局寻优算 法来改进聚类算法，如：遗传算法、免疫规划和模拟退火等算法，取得了一定的 成效。微粒群算法是一种高效的群体智能算法，具有收敛速度快、容易实现等优 点，因此，将微粒群算法应用到聚类算法中将能有效的改进现有聚类算法的不足。 本文分析了现有的聚类算法，这些算法的聚类数目需要提前确定。在此基础 上，提出一种基于微粒群算法和k 均值聚类算法的混合聚类算法，该算法定义了 两种类间距离，构造出一种新的聚类有效性函数，利用该函数对最佳聚类数进行 求解。仿真结果显示了该方法合理有效。 现有聚类算法的目标函数是样本到聚类中心欧式距离平方加权和的最小值， 依据样本到聚类中心的距离将样本划分到离聚类中心最近的类中，这些聚类算法 很难对复杂形状的数据进行聚类。因此，本文提出了基于生长树的聚类算法，其 中定义了最邻近距离和生长树等概念，并将最邻近距离作为生长树的生长方向和 样本划分依据，以生长树的大小作为聚类效果的判定函数。新算法利用网格和密 度阈值来去除数据集中的孤立点，并从网格集中随机选取种子点，最终通过微粒 群算法确定聚类结果。测试结果表明，基于网格生长树的微粒群聚类算法对于规 模较大、形状复杂并且非重叠的数据是可行有效的。 关键词：聚类算法：微粒群算法；聚类有效性函数；生长树 r e s e a r c ho f p s o b a s e dc l u s t e r i n ga l g o r i t h m g r a d u a t en a m e ：c a om i n g h u a( c o m p u t e rs o f t w a r ea n dt h e o r y ) d i r e c t e db y ：j i ej i n g ，z e n gj i a n c h a o ， a b s t r a c t d a t am i n i n gi sac o m p l e xp r o c e s sw h ic hc a ne x t r a c ta n dm i n et h e u n k n o w na n dv a l u a b l em o d e lo rr u l e c l u s t e ra n a l y s i si sa ni m p o r t a n t r e s e a r c hf i e l di nd a t am i n i n g ，a n di t sm a i np u r p o s ei st od i s t i n g u i s hf r o m c l a s s i f yk n o w nt h i n g sa c c o r d i n gt ot h es i m i l a r i t yo ft h e s et h i n g s ，a n du s e m a t h e m a t i c a lm e t h o d st os t u d yt h ep r o p e r t i e so ft h i n g sa n dd e a lw i t h t h e m g e n e r a l l y , c l u s t e ra n a l y s i sa l g o r i t h mc a nb ec l a s s i f i e di n t oa st h e f o l l o w s ：h i e r a r c h i c a l c l u s t e r i n ga l g o r i t h m ，s e g m e n t a t i o nc l u s t e r i n g a l g o r i t h m ，r e a l i t y - b a s e do fc o n s t r a i n e dc l u s t e r i n ga l g o r i t h m s ，m a c h i n e l e a r n i n g ，a sw e l la st h ec l u s t e r i n ga l g o r i t h mf o rh i g h d i m e n s i o n a ld a t a c l u s t e r i n ga l g o r i t h m d y n a m i cc l u s t e r i n ga l g o r i t h m i sa n i m p o r t a n t b r a n c hi nd i v i d e dc l u s t e r i n ga l g o r i t h m h o w e v e r ，t h ee x i s t i n gd y n a m i c c l u s t e r i n ga l g o r i t h m s h a v el o t so fs h o r t c o m i n g sw h i c hr e s t r i c ti t s d e v e l o p m e n tg r e a t l y ，s u c ha st e n d i n gt oal o c a lm i n i m u me a s i l ya n db e i n g s e n s i t i v et ot h ei n i t i a lv a l u e ，e t c m a n ys c h o l a r st r y t ou s eg l o b a l o p t i m i z a t i o na l g o r i t h mt oi m p r o v et h ec l u s t e r i n ga l g o r i t h m ，f o re x a m p l e ： g e n e t i ca l g o r i t h m ，i m m u n ep l a n n i n ga n ds i m u l a t e da n n e a l i n ga l g o r i t h m p s oa l g o r i t h mi sa ne f f i c i e n ts w a r mi n t e l l i g e n ta l g o r i t h mt h a to w n saf a s t c o n v e r g e n ts p e e da n di se a s yt oi m p l e m e n t t h e r e f o r e ，a p p l y i n gt h ep s o a l g o r i t h m t ot h e c l u s t e r i n gp r o b l e m c a ne f f e c t i v e l yo v e r c o m ea n d i m p r o v et h ee x i s t i n gc l u s t e r i n ga l g o r i t h m sd e f i c i e n c i e s t h i sd i s s e r t a t i o na n a l y z e st h ee x i s t i n gc l u s t e r i n ga l g o r i t h m sw h i c h n e e dt od e t e r m i n et h en u m b e ro fc l u s t e rc e n t e rb e f o r ec l u s t e r i n g ，a n d d e v e l o pa ni m p r o v e dh y b r i dc l u s t e r i n ga l g o r i t h mb a s e do nk - m e a na n d p s o t h eh y b r i da l g o r i t h md e f i n e st w on e wc o n c e p t st h a ta r er e f e ：r r e dt o a st h ed i s t a n c eb e t w e e nt w oc l a s s e sa n da d o p tt h e s et w oc o n c e p t st o c o n s t r u c tt h en e wc l u s t e rv a l i d i t yf u n c t i o n t h ep r o p o s e dm e t h o di s a p p l i e d t od e t e r m i n et h eo p t i m u m c l u s t e r i n g n u m b e rf o rs e v e r a l c l u s t e r i n gp r o b l e m s t h es i m u l a t i o nr e s u l t s s h o wt h ev a l i d i t yo ft h i s m e t h o d t h e o b j e c t i v e f u n c t i o no fc u r r e n tc l u s t e r i n ga l g o r i t h m s i s c o n s t r u c t e db yt h em i n i m u mo fs q u a r ew e i g h t e ds u mo fc o n t i n e n t a l d i s t a n c et ot h ec l u s t e rc e n t e ra n dt h es a m p l e sd i v i s i o ni sa c c o r d i n gt ot h e d i s t a n c eo fs a m p l e sf x o mt h ec e n t e ro fc l u s t e r i n g ，t h o s ea l g o r i t h m sa r e h a r dt oc l u s t e rt h ec o m p l e xs h a p ed a t a i nv i e wo ft h i sd e f e c t ，w e i n t r o d u c et h ec l u s t e r i n ga l g o r i t h mb a s e do nt h eg r o w t ho ft r e e si nt h i s p a p e r t h ei m p r o v e da l g o r i t h mi n t r o d u c e st w on e wc o n c e p t sw h i c ha r e t h en e a r e s td i s t a n c ea n dt h eg r o w t ht r e e t h en e a r e s td i s t a n c ei sa d o p t e d a st h eg r o w i n gd i r e c t i o no ft h eg r o w t ht r e ea n dt h eb a s i so ft h es a m p l e s d i v i s i o n ，w h e r e a s ，t h eu l t i m a t eg r o w t ht r e e ss i z ei su s e da st h ed e t e c t i o n f u n c t i o no fc l u s t e r i n ge f f e c t a tt h es a m et i m e ，t h ei m p r o v e da l g o r i t h m t a k e sa d v a n t a g eo ft h et h r e s h o l do ft h eg r i da n dt h ed e n s i t yt or e m o v et h e i s o l a t e dd a t ap o i n t s ，a n ds e l e c t sr a n d o ms e e df r o mt h e 鲥ds e t f i n a l l y ， p s oa l g o r i t h mi su s e dt od e t e r m i n et h ef i n a lc l u s t e r i n gr e s u l t s t e s t r e s u l t ss h o wt h a tp s o b a s e dc l u s t e ra l g o r i t h mw i t hg r i dg r o w t ht r e ei s f e a s i b l ea n de f f e c t i v ef o rl a r g ea n dc o m p l e xs h a p eo fn o n o v e r l a p p i n g d a t a k e yw o r d s ：c l u s t e r i n ga l g o r i t h m ；p a r t i c l es w a r mo p t i m i z a t i o n ；c l u s t e r v a l i d i t yf u n c t i o n ；p r o p a g a t i n gt r e e 一一 i i i 承诺书承话吊 本人郑重声明：所呈交的学位论文，是在导师指导 下独立完成的，学位论文的知识产权属于太原科技大学。 如果今后以其他单位名义发表与在读期间学位论文相关 的内容，将承担法律责任。除文中已经注明引用的文献 资料外，本学位论文不包括任何其他个人或集体已经发 表或撰写过的成果。 学位论文作者( 签章) ： 2 0 0 8 年5 月8 日 第一章绪论 第一章绪论 1 1 课题背景及意义 随着信息技术的快速发展，存储了大量的各种数据，这些数据背后隐藏许多重 要的信息和知识，对其进行更高层次的分析处理，以便更好地利用这些数据，是信 息技术所面临的问题。传统的数据管理方法可以高效地实现数据的查询、统计等功 能，但无法发现数据中存在的各种关系和内在的知识，导致“数据爆炸而知识贫乏” 的现象。于是，研究新的理论和技术，使之能够智能地、自动地将这些数据转化处 理为有用的信息和知识。数据挖掘( d a t am i n i n g ，d m ) 就是在这一背景下产生的， 现在数据挖掘技术在各方面等得到成功应用。同时，数据挖掘的研究和应用也为计 算机技术和人工智能理论的发展注入了新的活力。 聚类是数据挖掘中的一种基本方法，是依据属性值将目标对象划分成一系列有 意义子集的任务。聚类将数据点集合分成若干类或簇，使得每个簇中的数据点之间 最大的相似，而不同簇中的数据点最大程度的不同，从而发现数据集中新颖有用且 可以理解的模式或数据分布。聚类的目的是使同一簇中对象的特性尽可能地相似， 而不同对象间的特性差异尽可能地大。通过聚类，人们可以辨认出空旷和拥挤的区 域，进而发现整个的分布模式，以及数据属性之间所存在有价值的相关关系。聚类 已被应用到许多领域，其中包括：模式识别、数据分析、图象处理、空间遥感技术、 地理信息系统、计算机视觉、模糊控制信息检索和市场分析等。在模式识别中聚类 分析被应用于语音识别、字符识别、雷达信号识别、文本识别等方面；在图象处理 中聚类分析方法被应用于灰度图像的分割、彩色图像的分割、纹理图像的分割、图 像边缘的检测、图像增强恢复与压缩等方面；在计算机视觉中，聚类分析被应用于 物体边界的检测与曲线拟合；聚类分析方法还被应用于机器自动化和工具状态检测； 在模糊控制中，聚类分析方法主要用于控制规则的提取、系统建模、此外聚类分析 还被应用于其他多个领域，如用聚类方法进行气候分类，食品检验和水质分析，电 力系统控制等等。 在19 9 5 年由美国社会心理学家j a m e sk e n n e d y 和电气工程师r u s s e l le b e r b a r t 共 同提出的微粒群算法【l 】。其基本思想是受鸟类捕食时所表现的群体社会行为的启发， 算法模型及仿真算法主要利用了生物学家f r a n kh e p p n e r 的模型。 自微粒群算法提出以来，由于其在计算上的快速性和算法本身的易实现性，在 基于微粒群算法的聚类算法 国际上引发一场研究热潮。现有的动态聚类算法易陷入局部最优，聚类效果有待提 高。微粒群算法具有很好的全局寻优性，并且算法简洁，易于实现。因而，如何使用 微粒群算法来解决聚类问题，提高算法的合理性和有效性，是值得研究的课题。 1 2 聚类算法的概述 聚类算法依据所采用的基本思想分为五类，即层次聚类算法、分割聚类算法、 基于现实约束的聚类算法、机器学习中的聚类算法以及用于高维数据的聚类算法1 2 1 。 层次聚类算法对给定数据对象进行层次上的分解。根据层次分解的顺序是自下 向上的还是自上向下的分为两类，分别是自底向上的聚合层次聚类和自项向下的分 解层次聚类。层次聚类算法主要包括有c u r e ，r o c k 和c h a m e l e o n 等代表性的算 法。c u r e 算法t 3 1e h g u b a 等人于1 9 9 8 年提出，该方法选择数据空间中固定数目的、具 有代表性的一些点共同来代表相应的类，这样就可以识别具有复杂形状和不同大小 的聚类，从而能很好地过滤孤立点。r o c k 算法【4 】是基于c u r e 的改进，将原有算法 扩展应用于类别属性的数据。由k a r y p i s 于1 9 9 9 年提出的c h a m e l e o n 算法【5 】是在原 有的层次聚类算法的过程中利用的动态建模的技术。层次聚类的主要缺陷是，一旦 一个步骤( 合并或分裂) 完成，它就不能被撤消，因而不能更正错误的决定。 分割聚类算法作为一种常用的聚类方法。它先将目标数据集分为k 个初始划分， 然后从这k 个初始划分开始，通过重复的控制策略使某个准则最优化以达到最终的结 果。依据不同的判定原则又可分为基于密度的聚类、基于网格的聚类、基于图论或 平方误差的迭代重分配聚类。 基于密度的聚类算法主要用于对空间数据的聚类，算法由于定义聚类为密度相 连的点的最大集合。算法依据数据对象的分布密度，将密度足够大的相邻区域连接 起来，从而可以发现具有任意形状的聚类，并能有效处理异常数据。算法包括 d b s c a n 6 】和d e n c l u e 7 1 ，后者引入了属性空间的聚类。基于网格的聚类算法首先 将数据空间划分成为有限个单元的网格结构，所有的处理都是以单个的单元为对象 的。处理速度通常与目标数据库中记录的个数无关，它只与单元的个数有关，算法 的突出优点是处理速度很快。该算法主要包括以下三类：s t i n g t 8 】是一个基于网格多 分辨率的聚类方法，它将空间划分为方形单元，不同层次的方形单元对应不同层次 的分辨率。s t i n g + 9 】则对其进行了改进以用于处理动态进化的空间数据。c l i q u e 1 o 】 也是一个基于网格的聚类算法，它结合了网格聚类与密度聚类的思想，对于处理大 规模高维数据具有较好的效果。基于图论的方法是把聚类转换为一个组合优化问题， 2 第一章绪论 并利用图论和相关的启发式算法来解决该问题。其做法一般是先构造数据集的最小 生成树( m i n i m a ls p a n n i n gt r e e ，m s t ) ，然后逐步删除m s t 中具有最大长度的那些边， 从而形成更多的聚类。基于超图的划分和基于光谱的图划分方法是这类算法的两个 主要应用形式。该方法的一个优点在于它不需要进行一些相似度的计算，就能把聚 类问题映射为图论中的一个组合优化问题。基于平方误差的重分配聚类方法的主要 思想是逐步对聚类结果进行优化、不断将目标数据向各个聚类中心进行重新分配以 获得最优解( 判断是否是最优解的目标函数通常通过平方误差计算法得到) 。此类方 法又可进一步分为概率聚类算法、考虑了最近邻影响的最近邻聚类算法以及 k m e d o i d s 算法和k - m e a n s 算法。 基于约束的聚类算法，真实世界中的聚类问题往往是具备多种约束条件的，然 而由于在处理过程中不能准确表达相应的约束条件、不能很好地利用约束知识进行 推理以及不能有效利用动态的约束条件，使得这一方法无法得到广泛的推广和应用。 这里的约束可以是对个体对象的约束，也可以是对聚类参数的约束，它们均来自相 关领域的经验知识。该方法的一个重要应用在于对存在障碍数据的二维空间数据进 行聚类。c o d ( c l u s t e r i n gw i t ho b s t r u c t e dd i s t a n c e ) 就是处理这类问题的典型算法，其 主要思想是用两点之间的障碍距离取代了一般的欧式距离来计算其间的最小距离。 机器学习中的聚类算法是指与机器学习相关、采用了某些机器学习理论的聚类 方法，它主要包括人工神经网络方法以及基于进化理论的方法。自组织映射( s e l f - o r g a n i z i n gm a p ，s o m ) 禾t j 用人工神经网络进行聚类的较早尝试，它也是向量量化方法 的典型代表之一。利用进化理论进行聚类的缺陷在于它依赖于一些经验参数的选取， 并且具有较高的计算复杂度。为了克服上述不足之处，有研究者尝试组合利用多种 策略，如将遗传算法与k m e a n s 结合起来，并且使用变长基因编码，这样不仅能提高 k m e a r l s 算法的效率，还能运行多个k m e a n s 算法以确定合适的k 值。 高维数据聚类是目前多媒体数据挖掘领域面临的重大挑战之一。对高维数据聚 类的困难主要来源于以下两个因素：1 高维属性空间中那些无关属性的出现使得数据 失去了聚类趋势；2 高维使数据之间的区分界限变得模糊。除了降低数据维度这一最 直接的方法之外，对高维数据的聚类处理还包括子空间聚类以及联合聚类技术等。 c a c t u s i n 】采用了子空间聚类的思想，它基于对原始空间在二维平面上的一个投影 处理。c l i q u e 也是用于数值属性数据的一个简单的子空间聚类方法，它不仅同时结 合了基于密度和基于网格的聚类思想，还借鉴7 a p r i o r i 算法，并利用m d l ( m i n i m u m d e s c r i p t i o nl e n g t h ) 原理选择合适的子空间。 3 基于微粒群算法的聚类算法 1 3 本文的研究内容 本文在研究了基本微粒群算法及其各种改进策略的基础上，对现有的聚类算法 和基于微粒群的聚类算法进行详细分析，将两种类间距离引入聚类有效性函数中， 对微粒群聚类算法的最佳聚类数进行求解。同时在原有的基于微粒群聚类算法的基 础上，提出了一种基于网格生长树的微粒群聚类算法。算法利用网格和密度阈值去 除数据集中的孤立点，从网格集中随机的选取种子点，以基于密度距离作为判断生 长方向及分类的依据，以网格生长树的大小作为聚类目标函数。引入微粒群算法确 定最终的聚类结果。测试表明，基于网格生长树的微粒群聚类算法对于大规模形状 复杂非重叠的数据是可行且有效的。 4 第二章微粒群算法综述 第二章微粒群算法综述 2 1 微粒群算法概述 从2 0 世纪9 0 年代初，研究者开始对自然生物群体( s w a r m ) 行为进行研究，并由此 带来群智能( s w a r mi m e l l i g e n c e ) 演化计算技术。群体( s w a m i ) 的概念源于对蜜蜂、 蚂蚁、大雁等这类群居生物群体行为的观察和研究，是一种在自然界生物群体所表 现出的智能现象启发下提出的人工智能实现模式，是对简单生物群体的智能涌现现 象的具体模式研究，该智能模式需要以相当数目的智能个体来实现对某类问题的求 解功能。最主要的两种算法是：m d o r i g o 于1 9 9 1 年提出蚁群算、法【1 2 】和微粒群算法。 微粒群算法( 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 ) 就是在这种背景下，由e b e r h a r t 和 k e n n e d y 研究模拟鸟群、鱼群的行为方式于1 9 9 5 年提出的一种演化计算技术【。微粒 群算法是起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，后来又发现 它是一种很好的优化工具。其基本思想是受他们早期对许多鸟类的群体行为进行建 模与仿真研究结果的启发。而他们的模型及仿真算法主要利用了生物学家f r a n k h e p p n e r 的模型。 微粒群算法求解优化问题时，问题的解对应于搜索空间中一个鸟的位置，定义 这些鸟为微粒。每个微粒都有自己的位置和速度( 决定飞行的方向和距离) ，还有一 个由被优化函数决定的适应值。各个微粒记忆、追随当前的最优微粒，在解空间中 搜索。每次迭代的工程不是完全随机的，如果找到较好解，将会以此为依据寻找下 一个解。 2 2 基本微粒群算法 微粒群算法【1 3 】与其他演化算法相似，也是基于群体的，根据对环境的适应度将 群体中的个体移动到好的区域，然而它不像其他演化算法那样对个体使用演化算子， 而是将每个个体看作d 维搜索空间中的一个没有体积的微粒( 点) ，在搜索空间中以一 定的速度飞行。这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整。 算法的基本思想是：优化问题的候选解都是搜索空间中的一个微粒所有的微粒 都对应一个由被优化函数决定的适应值，每个微粒的速度决定它们的飞行方向和距 离。然后所有微粒就在解空间中追随最优微粒。微粒群优化算法初始化为一群随机 微粒，然后通过多次迭代找到最优解。在每一次迭代中，微粒通过跟踪两个极值来 更新自己，其中一个极值是微粒本身所找到的最优解，这个最优解称为个体极值；另 5 基于微粒群算法的聚类算法 一个极值是整个微粒群目前找到的最优解，这个解称为全局极值。在连续空间坐标 系中，设微粒群体规模为n ，第i 个微粒在d 维空间中的坐标位置可表示为 x ，= ( x ，f x ，：x 出) ，微粒i ( i = 1 ，) 在第d ( a = 1 ，d ) 维子空间中的飞行速度v 耐按下 式调整： v “= v 村+ c 。r a n d ，( x p d x 村) + c 2 r a n d ：( x p 耐一x 耐) ( 2 1 ) x 耐2x ，d + v 耐 ( 2 2 ) 其中：尸。是整个微粒群的历史最优位置记录，称为全局最好位置。用微粒，当前 位置与群体最好的位置之间的距离之差来改变当前微粒向群体最优值运动的增量分 量，并进行了一定程度的随机化，c2 r a n d ：【) i p 耐一x ，卅被称为“社会认知”部分，表示 微粒间的社会信息共享。如果没有这一部分则微粒间缺乏信息交流，微粒间没有交 互使得一个规模为n 的群体等价于运行了n 个单个微粒，因而得到最优解的概率非常 小，尸是当前微粒的历史最优位置记录，用微粒i 当前位置与自己最好的位置之间的 距离之差来改变当前微粒向该微粒最优值运动的增量分量，也进行了随机运动设定， c l r a n d t lj i p ，d x 耐j 为“个体认知”部分它考虑了微粒自身的经验。如果没有这一部 分则微粒在相互作用下，有能力达到新的搜索空间，虽然它的收敛速度较快但是对 于复杂问题则容易陷入局部最优点。c l ，晓为加速度常数，通常在o n4 之间取值； c o 是惯性权重，为了能在前期有较高的探索能力以得到合适的适应值，在后期有较 高的开发能力以加快收敛速度，可将国设定成随着进化而线性减少。微粒则通过( 2 2 ) 调整自身的位置。 在整个寻优过程中，各微粒通过目标值函数来求的适应值，并且每个微粒通过 “社会认知”和“个体认知”的学习，通过式( 2 1 ) 和式( 2 2 ) 不断调整速度和位置， 使的整个微粒群体逐渐逼近最优目标。 算法的具体步骤是： s t e p l 初始化：初始化搜索点的位置及其速度通常是在允许的范围内随机产生的，每 个微粒的p 坐标设置为其当前位置，且计算出其相应的个体极值p ( 即个体 极值点的适应度值) ，而全局极值只( 即全局极值点的适应度值) 就是个体极值 中最好的，记录最好微粒的序号，并将只设置为最好微粒的当前位置。 s t e p 2 评价微粒：计算微粒的适应度值，如果好于该微粒当前的个体极值，则将p 设 置为该微粒的位置，且更新个体极值。如果所有微粒的个体极值中最好的好于 当前的全局极值，则将只设置为该微粒的位置，记录该微粒的序号，且更新全局 6 第二章微粒群算法综述 极值。 s t e p 3 微粒的更新用式( 2 1 ) 和式( 2 2 ) 对每一个微粒的速度和位置进行更新。 s t e p 4 检验是否符合结束条件，如果当前的迭代次数达到了预先设定的最大次数( 或 达到最小错误要求) ，则停止迭代，输出最优解，否则转到s t e p2 。 算法的流程图如下： 图2 1 基本微粒群算法流程图 2 3 微粒群算法的两种基本模型 从一个角度来讲，在基本微粒群算法中，根据直接相互作用的微粒群定义可构 7 摹于微粒群算法的聚类算法 造微粒群算法的两个不同版本，文献l l3 j 提出了两种基本进化模型，即通过定义全局 最好微粒( 位置) 或局部最好微粒( 位置) 构造具有不同社会行为的微粒群算法： 2 3 1g b e s t 模型( 全局最好模型) g b e s t 模型以牺牲算法的鲁棒性为代价提高算法的收敛速度，基本微粒群算法就 是该模型的具体体现。在该模型中，整个算法以全局最优微粒为吸引子，将所有微 粒拉向它，使所有微粒最终收敛于该位置。这样，如果在进化过程中，全局最优微 粒得不到有效地更新，则微粒群将出现类似于遗传算法中的早熟现象。 2 3 2l b e s t 模型( 局部最好模型) 为了防止g b e s t 模型可能出现的早熟现象，l b e s t 模型采用多吸引子代替g b e s t 模型中的单一吸引子。首先将整个微粒群分解为若干个子群，在每一子群中保留其 局部最好位置尸，称之为局部最好位置或邻域最好位置。假设第，个子群处于长度为 l 的邻域内，则l b e s t 模型的进化方程可描述为： n ，= 谚h o ) ，p ，- i + 1 0 ) ，p 。o ) ，p ，o ) ，p ，+ ，o ) ，p , i - i o ) ，p o ) ( 2 3 ) p ，o + ，) ，i 0 ，o + 1 ”= m i n f ( a ) l v a ； ( 2 4 ) y 。o + ，) = v 。o ) + c l r a 门d 。o 岫。o ) 一x t j o ) j + c ：阳挖d ：o ) p 哥( ，) 一x 。( ，) j ： ( 2 5 ) 容易得出，g b e s t 模型实际上是l b e s t 模型的一种特殊情况。需要注意的是，子 种群，中的微粒与其在搜索空间域内所处的位置无关，仅依赖微粒的索引数或者微 粒的编码。这样，一方面避免了微粒间的聚类分析节省了计算时间，另一方面能够 加快更好解信息在整个群体间的扩散。 2 4 微粒群算法的国内外研究动态 p s o 算法也存在一些缺陷，如易陷入局部极值，收敛速度较慢，不能保证种群 多样性等。尤其对处理多峰值优化函数的性能不佳。国内外做出了诸多改进： 2 4 1 动态调整进化方程参数的 1 ) 调整惯性权重 s h i 和e b e r h a r t 对p s o 算法的速度项中引入了惯性权重c o 1 4 1 1 5 】，该进化方程已被 相关学者称之为标准p s o 算法。算法采用在进化过程中自适应动态调整参数c o ，改 进后的算法在迭代初期探索能力较强，可以更好的搜索新的区域，后期开发能力逐 步增强，可对潜在解的附近进行详细搜素。另外的研究显示利用模糊规则动态调 r 第二章微粒群算法综述 整参数的值，通过对当前最好性能评价和当前惯性权重制定相应的隶属函数依据 模糊推理规则确定惯性权重的增量，试验结果显示该方法与惯性权重递减的算法 类似的结果。 2 ) 增加收缩因子 c l e r c 在进化方程中引入收缩因子以保证算法的收敛性，同时使得速度的限制 降低。有关学者已通过代数方法对此方法进行了详细的算法分析，并给出了参数选 择的指导性建议 2 4 2 构建动态邻域结构的 由于g b e s t 模型存在的多样性少，易早熟收敛的缺点，因此在此基础上提出了 l b e s t 模型，以增加种群的多样性，从而更好的实现全局搜索，避免陷入局部最优。 s u g a n t h a n 提出一种具有可变邻域算子的微粒群算法【1 8 】，算法在初始阶段微粒的 邻域为它本身，随着进化代数的增长，邻域逐渐扩大到整个群体。算法后期的随机 搜索和惯性权值的大小也逐渐调整，使算法在优化的最后阶段拥有更好的开发搜索。 j k e n n e d y 和r m e n d e s 研究了不同邻域拓扑结构对局部最优模型( l b e s t 模型) 中的效果，发现v o nn e u m a n n 邻域结构能取得更好的效果，并依次提出两种改进方 法p s o n 和p s o w n t l 9 】。前者在微粒更新过程中邻域内的例子也对新一代的微粒产 生影响，后一种算法将邻域内的微粒依据影响力进行权值调整，更加符合现实情况。 j j l i a n g 和p n s u g a n t h a n 提出了一种多样群体微粒群算法f 2 0 】，分阶段搜索首先将 整个群体随机分割成多个子群，各子群内部采用局部最优化模型进化，若干代后进 行重新分组，以提高种群的多样性。第二阶段使用全局最优化模型进化，以加快全 局最优搜索的能力和速度。提出的算法将“勘探”和“开发”达到了很好的平衡，对复杂 多峰函数的优化能取得很好的结果。 此外，微粒群算法与复杂网络模型的结合也是微粒群算法在动态构造邻域模型 方面的一个新的研究热点。 2 4 3 与其他算法的结合 a n g e l i n e 提出将选择方法引入微粒群算法，采用进化计算中的锦标赛选择方法， 将每一个体的适应度基于当前的位置与其他个体进行比较，记录最差的个体适应度， 并根据比较结果进行排序，用微粒群中最好一半的当前位置和速度替换较差一半的 位置和速度，同时保留每个个体所记忆的最好位置。经验证该方法拥有更好的开发 能力【2 l 】。 9 基于微粒群算法的聚类算法 a n g e l i n e 将遗传思想中的杂交引入微粒群算法【2 2 1 ，微粒群中的微粒被赋予一个杂 交概率，依据杂交概率选取指定数量的微粒随机的两两杂交，产生相同数目的子代 微粒，并用子代取代父代，进入下一次迭代。如b e a s l e y 等提出的最初使用在遗传 算法中的序列生境技术可以系统地访问每一个全局极值【2 3 】，其思想是在找到每一个极 值后，都用下降函数来自适应地改变适应度函数，因此算法就不会再回到该极值。夏 桂梅等对一种基于轮盘赌选择遗传算法的随机微粒群算法的研列2 4 】也大大提高了算 法的精确度。s h ix h 等人提出了一种改进型的基于遗传算法的改进p s o 算法【2 5 1 ， 算法具有动态的群体个数，算法思想源于生物体自然死亡的自然规律，每一代个数 不固定，如果该个体生存代数多于限定值则令其死亡。算法的收敛性较g a 和p s o 对比有明显提高。 l o v b j e r g 等提出了基于繁殖和子群的杂交微粒群算澍2 6 】，他们在繁殖过程中引入 繁殖概率来代替适应度。每次迭代时，依据繁殖概率在微粒中选取一定数量的微粒 放入池中随机两两进行算术“杂交”繁殖，产生数目相同的后代，用后代微粒代替父 母微粒，使种群数目保持不变，同时引入繁殖因子以进行子群体的信息交流。 h i g a s h i 等提出了用进化计算中的高斯“变异”算子与微粒群算法杂交的思想。该 方法在传统的速度与位置更新规则中融入高斯“变异”，以避免陷入局部最优。李宁 等，吕振肃等也提出将变异算子【2 7 】 2 s 1 引入到p s o 中，在算法陷入局部极值的情况下， 如果出现早熟，则按一定概率更新g 。删的值。 高鹰等将模拟退火思想引人到微粒群算法中【2 9 1 ，避免了微粒陷人局部最优，提 高了收敛性能。王丽芳和曾建潮将模拟退火算法和微粒群算法结合，得到以概率1 全局收敛的改进算法【3 0 l 。b ol i u , l i n gw a n g 等人将混沌算法( c h a o s ) 引入微粒群算 法中诞生出基于混沌的微粒群算法( c h a o sp a r t i c l es w a r mo p t i m i z a t i o n c p s o ) ，算法 效能达到很大的提耐”】。 2 4 4 收敛性分析及加快收敛速度 为了避免p s o 算法所存在的过早收敛问题，r i g e t 提出了一种保证种群多样性的 微粒群算法( a t t r a c t i v ea n dr e p u l s i v ep a r t i c l es w a r mo p t i m i z e r ，简称a r p s o ) 3 2 1 ，引入 “吸l ( a t t r a c t i v e ) ”和“扩散( r e p u l s i v e ) ”两个算子，动态地调整“勘探”与“开发”比例，从 而能更好的提高算法效率。 v a nd e nb e r g h 在2 0 0 2 年提出了一种具有局部收敛性能的改进微粒群算法 ( g u a r a n t e e dc o n v e r g e n c ep a r t i c l es w a r mo p t i m i z e r ，简称g c p s o ) 【3 3 】。为了进一步讨 1 0 第二章微粒群算法综述 论g c p s o 的性能，在文献【3 4 】中使用了不同连接拓扑的p s o 进行实验。 在收敛性方面，s o l i s 和w e t s 对随机优化算法提出了其全局收敛必须满足的条件 f 3 5 】，v a nd e nb e r g h 利用该条件对p s o 的全局收敛性和局部收敛性进行了研究【3 6 1 ，证 明了p s o 算法不能全局收敛，甚至于局部收敛。同时，证明了g c p s o 算法能够收 敛于局部最优解，而不能保证收敛于全局最优解。 曾建潮等提出了一种保证全局收敛的随机微粒群算法( 简称s p s o ) 3 7 】，大大提高 了p s o 的全局收敛能力与速度。同时分析已有的一些微粒群算法，提出了一种统一 模型【3 8 1 ，并通过线性控制理论分析了其收敛性能。 赫然等提出了一种改进的自适应逃逸微粒群算法( 简称a e p s o ) p 9 1 ，当微粒飞行 速度过小时通过逃逸运动( 逃逸行为是一种简化的确定变异操作) 使微粒能够有效地 进行全局和局部搜索，减弱了随机变异操作带来的不稳定性，不仅提高了收敛速度， 而且能有效地进行全局搜索。 高海兵等基于微粒群优化的神经网络训练算法研究，提出了基于连接结构优化 的微粒群优化算法，该算法在提高分类误差精度的同时可加快训练收敛的速度【4 0 1 。 微粒群算法损失了微粒的多样性，所有微粒被迄今为止找打的最好微粒所吸引， 杨亚平和谭瑛等提出了二次微粒群【4 1 】的概念，保证了微粒的多样性，提高了算法效 率。受协同进化遗传算法的启发，多人提出了微粒群算法的并行化，王元元等提出 多种群协同进化的微粒群算法【4 2 1 ，算法将整个种群分解为多个子种群，各子种群独 立进化，周期性的更新共享信息，采用多种更新策略，试验显示合适的更新周期能 提高算法的收敛性。 2 5 微粒群算法的应用领域 最初p s o 算法是为解决连续变量的非线性优化问题提出的，现在己经扩展到离 散变量的求解中。它以一个简单的概念为基础，实现简单，计算量和占有的内存小， 算法的性能却可以和遗传算法相媲美，因而近年来己经在各领域中得到广泛的应用： 诸如函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。还可 以将微粒群算法用于解决多目标优化问题、最小最大化问题、整数规划问题和定位 等全局极值问题。一般来说，微粒群算法比较有潜力的应用包括系统设计、多目标 优化、分类、模式识别、调度、信号处理与决策、机器人应用等。 2 5 1 函数优化 许多实际的工程问题本质上是函数优化问题或者可以转化为函数优化问题进行 基于微粒群算法的聚类算法 求解，对于函数优化问题已经有一些成熟的解决方法如遗产算法。但是对于超高维、 多局部极值的复杂函数而言，遗传算法往往在优化的收敛速度和精度上难以达到期 望的要求。现有的由经过大量的实验研究发现，微粒群算法在解决一些典型的函数 优化问题时，能够取得比遗传算法更好的优化结果。以上表明微粒群算法在解决实 际问题时同样具有很好的应用前景【4 3 1 。 2 。5 2 神经网络调练 研究表明，神经网络能够以任意精度模拟复杂的非线性关系，而神经网络的性 能依赖于对神经网络的充分训练。因此，训练算法对神经网络的性能有较大影响。 神经网络的训练赖于对神经网络的充分训练。因此，训练算法对神经网络的性 能有较大影响。神经网络的训练问题属于非线性的复杂度较高的优化问题。基于梯 度下降的b p 算法依赖于初始权重的选择，收敛速度缓慢且容易陷入局部最优。b p 的上述缺陷尤其是局部优化特性使得其训练的神经网络的输出具有不一致