粒子群综述-

粒子群优化算法综述

第一章概述

粒子群优化算法(PSO)是近年来被广为关注和研究的一种智能优化算法，源于对鸟群捕食系统的模拟。它收敛速度快、易实现并且仅有少量参数需要调整，因而一经提出就成为智能优化与进化计算领域的一个新的研究热点，目前己经被广泛应用于目标函数优化、动态环境优化、神经网络训练、模糊控制系统等许多领域[1]。其中最具应用前景的领域包括多目标问题的优化、系统设计、分类、模式识别、生物系统建模、规划、信号处理、决策和模拟等。粒子群优化算法的理论背景是“人工生命”。人工生命(artificial life)是用来研究具有某些生命基本特征的人工系统，其中一个重要部分是利用生物技术来研究计算问题。粒子群优化算法的诞生来源于一种生物一社会系统，该生物一社会系统的研究集中于简单个体组成的群落与环境之间的关系，以及个体之间的互动行为。群居个体以集体的力量进行觅食、御敌，单个个体只能完成简单的任务，而由单个个体组成的群体却能完成复杂的任务，这种群体所表现出来的“智能”，就称之为群体智能(Swarm Intelligence，SI)[2]。而从群居昆虫互相合作进行工作中得到启迪，研究其中的原理，并以此原理来设计新的求解问题的算法被称为群智算法。在计算智能领域主要有两种基于群智能的算法，一种是蚁群算法(Ant Colony Optimization，ACO)，它是对蚂蚁群落食物采集过程的模拟，己经成功运用在很多离散优化问题上[3]；另一种是粒子群优化算法，最初由Jim Kennedy于1995年提出并成功的用于函数优化，后来又进行了有效的拓展[4]。但是，PSO的发展历史尚短，在理论基础与应用推广上都还存在一些问题有待解决。当PSO应用于高维复杂问题优化时，往往会早熟收敛(premature)，也就是种群在还没有找到全局最优点时已经聚集到一点停滞不动。这些早熟收敛点，有可能是局部极小点，也有可能是局部极小点邻域中的一个点。换句话说，早熟收敛并不能保证算法收敛到局部极小点。因而，对算法早熟收敛行为的研究可为算法的进一步改进奠定基础。此外，PSO在接近或进入最优点区域时的收敛速度也比较缓慢。实际上对PSO的研究发现，PSO早期收敛速度较快，但到寻优的后期，其结果改进则不甚理想。

第二章粒子群优化算法

起初Kennedy和Eberhart[4]只是设想模拟鸟群觅食的过程，但后来发现PSO是一种很好的优化工具。与其他进化算法相类似，PSO算法也是通过个体间的协作与竞争，实现复杂空间中最优解的搜索。PSO第一步生成初始种群，即在可行解空间中随机初始化一群粒子，每个粒子都为优化问题的一个可行解，并由目标函数为之确定一个适应值。每个粒子将在解空间中运动，并由一个速度决定其方向和距离。通常粒子将追随当前的最优粒子，并经逐代搜索最后得到最优解。在每一代中，粒子将跟踪两个极值，一个是粒子本身迄今找到的最优解pbest，另一个是整个种群迄今找到的最优解gbest。

2．1 PSO算法基本原理

自然界中一些生物的行为特征呈现群体特征，可以用简单的几条规则将这种群体行为(Swarm Behavior)在计算机中建模，实际上就是在计算机中用简单的几条规则来建立个体的运动模型，但这个群体的行为可能很复杂。例如，Reynolds使用了下列三个规则作为简单的行为规则[5]：

1) 向背离最近的同伴的方向运动；

2) 向目的运动：

3) 向群体的中心运动。

这即是著名的Bold(Bird—oid)模型。在这个群体中每个个体的运动都遵循这三条规则，通过这个模型来模拟整个群体的运动。PSO算法的基本概念也是如此每个粒子(Particle)的运动可用几条规则来描述，因此PSO算法简单，容易实现，越来越多地引起人们的注意。设想这样一个场景：一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO算法就从这种生物种群行为特性中得到启发并用于求解优化问题。在PSO中，每个优化问题的潜在解都可以想象成d维搜索空间上的一个点，我们称之为“粒子”(Particle)。粒子在搜索空间中以一定的速度飞行，这个速度根据

它本身的飞行经验和同伴的飞行经验来动态调整。所有的粒子都有一个被目标函数决定的适应值(fitness value)，并且知道自己到目前为止发现的最好位置(particle best，记为pbest)和当前的位置。这个可以看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(global best，记为gbest)(gbest是在pbest中的最好值)，这个可以看作是粒子的同伴的经验。每个粒使用下列信息改变自己的当前位置：1)当前位置；2)当前速度；3)当前位置与自己最好位置之间的距离；4)当前位置与群体最好位置之间的距离。优化搜索正是在由这样一群随机初始化形成的粒子而组成的一个种群中，以迭代的方式进行。

2．2 PSO算法数学描述

数学描述[6]可以是：假设在一个d维的目标搜索空间中，有m个代表潜在问题解的粒子组成的一个种

群，其中m表示第i个粒子在d维解空问的一个矢量点。将代入一个与求解问题相关的目标函数可以计算出相应的适应值。用m 记录第i个粒子自身搜索到的最好点(所谓最好，是指计算得到的适应值为最小，即pbest)。而在这个种群中，至少有一个粒子是最好的，将其编号记为g，则就是种群搜索到的最好值(即

gbest)，其中g∈{1,2,…,m}。而每个粒子还有一个速度变量，可以用

m表示第f个粒子的速度。

PSO算法一般是采用下面的公式对粒子进行操作的。

(2．1a)

(2．2a)

其中粒子的标号i=1,2,…,m：k为迭代代数；学习因子c1、c2是两个正常数，一般取值为2；r1、r2是均匀分布于[0，1]之问的两个随机数。为了控制形和的值在合理的区域内，需要指定来限制。

公式(2．1a)主要通过三部分来计算粒子i新的速度：粒子i前一时刻的速度，粒子i当前位置与自己最好置之间的距离，粒子i当前位置与群体最好位置之间的距离。粒子i通过公式(2．2a)计算新位置的坐标。通过式(2．1a)、(2．2a)粒子，决定下一步的运动位置。在图2．1中，以两维空间为例描述了粒子根据公式(2．1a)、(2．2a)从位置到移动的原理。

如果从社会学的角度来看，公式(2．1a)的第一部分称为记忆项，表示上次速度大小和方向的影响；公式的第二部分称为自身认知项，是从当前点指向此粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的部分；公式的第三部分称为群体认知项，是一个从当前点指向种群最好点的一个矢量，反映了粒子间的协同合作和知识的共享。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动，这与人类的决策何其相似，人们通常也是通过综合自身己有的信息和从外界得到的信息来作出决策的。

图2.1 粒子移动原理图

2．3 基本PSO的算法步骤

从前述分析可见该PSO算法是一种全局优化算法，其计算步骤如下：

基本PSO算法具体实现[6]

选定PSO种群规模m：

设X[i]为种群中第i个粒子的位置；

设fitness[i]为第i个粒子的适应值；

设V[i]为第i个粒子的速度；

设gBest为种群最好粒子的标号；

设Pbest[i]为第i个粒子自身搜索到的最好点位置；

设Pbest_fitness[i]为第i个粒子自身搜索到的最好适应值，即Pbest[i]处的适应函数值；

Stepl：(初始化)对于每一个种群中的粒子i，i=1，2,?，m

Stepl.1: 随机初始化X[i]

Step1.2：随机初始化v[i]

Stepl.3：计算fitness[i]，并以此初始化Pbest_fitness[i]

Stepl.4：以种群中最好适应值的粒子标号初始化gBest

Stepl.5：以X[i]初始化Pbest[i]

Step2：循环迭代，直到满足PSO终止条件

Step2.1：选择算法控制参数w；

Step2.2：对每个粒子，计算其适应值fitness[i]。若fitness[i]< Pbest_fitness[i]，则

Pbest_fitness[i]=fitness[i]，且Pbest[i]=X[i]

Step2.3：搜索gBest值：若Pbest_fitness[i]< Pbest_fitness[gBest]，则gBest=i；

Step2.4：对每个粒子，依据公式(2．1b)、(2．2b)更新V[i]和X[i]值

2．4 PSO算法的改进

2.4.1 加入惯性权重因子w的PSO算法[6]

正如先前所述，公式(2．1a)由三部分组成：第一部分是粒子先前的速度项，即，第二部分和第三部分是导致粒子速度变化的两项，即和。

一方面，公式(2．1a)如果没有后两项，粒子将保持在相同的方向上以当前的速度“飞翔”至下一个点，直至达到边界值。这样的PSO将不能找到一个可接受的解，除非这样的飞行轨迹是一种合理的方案，而这在现实中是非常少见的。

另一方面，如果公式(2．1a)没有第一项，那么“飞翔”粒子的速度仅仅取决于粒子的当前位置和它们最好的历史位置。速度自身是没有记忆性的。假设在开始的时候，粒子i正好是整体最好所在的点，那么粒子i将以速度为0“飞翔”，这将保持粒子此次的位置不变，直到出现新的一个最好点替代粒子i。同时，每一个粒子将向自身最好点和整体最好点的质心方向“飞翔”。推荐c1和c2都取常数2，这正如文献[7]中提到的那样，这样使得“社会认知”和“个体经验”的权重为l。在这种状况下，各个粒子逐渐的向当前最好的位置处收缩，直到出现新的最好值，而那样粒子群体又向这个位置收缩。因此可以想象，在没有第一项情况下的PSO搜索过程，其搜索空间将在迭代中逐渐衰退，这类似与局部搜索算法。只有当全局最好点包含在

初始搜索空间内的时候，才有可能找到满意解。这样，最终解在很大程度上要依赖于初始化种群。这也说明了在没有第一项内容的情况下，PSO算法更多的显现的是局部搜索能力。从另一层意思来说，第一项内容使得粒子有一种扩展搜索空间的能力，即开拓能力（explore ability)，是一种全局搜索能力的表现。

在各类问题的解决，局部搜索和全局搜索都起着重要作用。对于某一类优化问题的具体解决中，我们应该权衡局部搜索和全局搜索的贡献。我们可以考虑在公式(2．1a)中引入一个惯性权重因子W，以起到权衡全局搜索和局部搜索能力。惯性权重因子w可以是个正整数常数，也可以是以时问为变量的线性或非线性正整数。这样公式(https://www.wendangku.net/doc/2416265018.html,)(2．2a)就变为：

(2．1b)

(2．2b)

以上的算法公式中所涉及到的参数较少，算法也相对比较简单，可将此称为基本粒子群优化算法(Simple Particle Swarm Optimization，SPSO)。

2.4.2 拓扑结构的研究（参考王晗丁的PSO综述）

对于粒子群拓扑结构的研究最早是源于对于gbest和pbest两种拓扑结构的研究，gbest为整个粒子群的最优者，而pbest为粒子邻居中的最优者。gbest结构允许信息在整个种群中传播，粒子跟随gbest ，因此该结构的收敛速度比较快，同时多样性的保持较差，较容易陷入局部最优。相反的，pbest结构中，粒子跟随相应的pbest飞行，相当于在多个区域内搜索，且信息是逐步通过邻居扩散出去的，因此在收敛速度上相比gbest结构相对慢，但其多样性的保持较好[8]。

上述两种结构是研究的比较多的结构，也有一些其他的新的结构在实验结果上也有较好的效果。

gbest 环形结构方形结构von Neumann结构

除此之外还有其他策略也与拓扑结构有关，划分子群策略[9][10]和小生境技术[11]可以很好的保持整个种群的多样性，文献[12]是以每个变量为一个子群，通过子群间的合作来进行优化的。

第三章基本PSO与其他进化算法的比较与结合

3．1 基本PSO与其他算法的比较

3.1.1相似点

粒子群算法与其他进化算法有许多相似之处。首先，粒子群算法和其它进化算法都使用“种群”概念(Swarm)，用于表示一组解空间中的个体集合。两者都随机初始化种群，都使用适应值来评价个体，而且都根据适应值来进行一定的随机搜索，两个算法都不能保证一定找到最优解[13]。如果将粒子所持有的最好位置也看作种群的组成部分，则粒子群的每一步迭代都可以看作是一种弱化的选择机制[14]。在(μ+λ)进化策略算法中，子代与父代竞争，若子代具有更好的适应值，则子代将替换父代，而PSO算法的进化方程式也具有与此类似的机制，只有当粒子的当前位置与所经历的最好位置相比具有更好的适应值时，所经历的最好位置才会唯一地被当前的位置所替代。可见PSO算法中也隐藏着一定形式的“选择”机制。

PSO和GA都具有隐含并行性。搜索过程是从问题解的一个集合开始的，而不是从单个个体开始，从而减小了陷入局部极小的可能性。这种并行性易于在并行计算机上实现，以提高算法的性能和效率。

3.1.2 不同点

与GA等其他进化算法比较，PSO具有独特的信息共享机制。在GA中，染色体互相共享信息，所以整个种群的移动是比较均匀地向最优区域移动。在全局版PSO中，只有全局最优粒子提供信息给其他的粒子，这是单向的信息流动，整个搜索更新过程是跟随当前最优解的过程。与遗传算法比较，所有的粒子很可能更快地收敛于最优解。PSO算法与其他进化算法的另一个重要不同点在于它在进化过程中同时保留和利用位置与速度信息，而其它进化算法仅保留和利用位置信息。

从以上分析中看，基本PSO算法与其他进化算法有相似之处，但同时也具备其它算法不具备的特性，特别的是PSO算法同时将粒子的位置与速度模型化，并给出了它们的进化方程。

3．2 基本PSO与其他算法的结合

PSO与一般的EA有相似之处，也有很多的不同点[15]，PSO没有进化意义层面上的交叉、变异和选择算子，但是通过文献[16]可知一般意义上的交叉和变异都是很低效的，然而PSO是有指导的选择交叉的父代以及变异的方向，但PSO得选择机制是很弱的，只是保留了全局最优以及个人最优。因此目前主流EA与PSO 结合的算法就是在PSO中添加交叉[17]、差分[18]、变异[19]和选择[20]算子。除与其他EA结合的PSO之外，PSO 与其他算法结合也有较好的的效果，如正交量子群优化（OPSO，Orthogonal Particle Swarm Optimization）[21]等。

第四章PSO算法的发展

PSO算法概念简单容易实现，其代码只有短短的几行，和其他优化算法相比，这也是它的优点之一。短短几年里，PSO算法己经获得了很大的发展，并已在一些领域得到应用。但是它的缺点是易陷入局部极小点，搜索精度不高，因此研究者们对其作了各种各样的改进。现在已经从PSO基本算法发展出许多不同的版本，这些版本是对基本PSO算法的改进或者是在某一方面应用领域的延伸。

4．1 自适应PSO(Adaptive Particle Swarm Optimization，APSO)

我们已经研究了惯性因子w对优化性能的影响，发现较大的w值有利于跳出局部极小点，而较小的w值有利于算法收敛，因此提出了自适应调整w的策略，即随着迭代的进行，线性地减小w的值。这种方法的进一步发展是用模糊规则动态地修改w的值[27]，即构造一个2输入、l输出的模糊推理机来动态地修改惯性因子w。模糊推理机的两个输入分别是当前w值，以及规范化的当前最好性能演化(the normalized current best performance evaluation，NCBPE)：而输出是w的增量。

CBPE是PSO算法迄今为止发现的最好候选解的性能测度。CBPE可以有不同的定义方法，但是一般CBPE可以定义为最好候选解的适应值。NCBPE用下式计算：

其中和分别是可能取值的上下限。

模糊推理机的输入、输出的论域定义为3个模糊集合：LOW，MEDIUM和HIGH，相应的模糊隶属度函数分别是leftTriangle，Traingle，rightTriangle，其中文献[27]给出的这三种模糊隶属度函数的定义分别如下：leftTrangle的定义：

Triangle的定义：

rightTriangle的定义：

模糊度函数的图形如下：图2．2］

图2．2模糊度函数

文献[27]也为模糊推理机定义了9条规则进行模糊推理，决定当前w的增量。对于一些基准函数，如Rosennbrock、Rasrigrin、Griewank的试验结果表明，这一类自适应PSO算法都能取得满意的结果，同样也适用于许多优化问题。通过自适应调整全局系数，兼顾搜索效率和搜索精度，是一类有效的算法。但对许多复杂的非线性优化问题，试图通过自适应调整一个全局系数提高搜索精度的余地是有限的。

4．2 混合PSO(Hybrid Particle Swarm Optimization，HPSO)

借鉴遗传算法的思想，文献[22，23]最早提出了混合PSO算法(Hybrid PSO，HPSO)的概念。混合PSO算法是将基本PSO算法和选择机制相结合而得到的，基本PSO算法的搜索过程很大程度上依赖pbest和gbest，它的搜索区域受到pbest和gbest的限制。在通常的进化算法中，选择机制用来选择相对较好的区域和淘汰较差的区域。可以更合理地分配有限的资源。

混合PSO算法的选择机制与其它进化算法十分相似，如遗传算法。混合PSO算法计算每个个体基于当前位置的适应值，并将这些适应值进行排序，然后将群体中一半适应值差的个体的当前位置和速度替换为另一半好的个体的当前位置和速度，但保留每个个体的最好位置pbest。因此，群体搜索集中到相对较优的空间，但还受到个体自身以前最好位置的影响。

混合PSO算法的流程如下：

1)初始化所有粒子；

2)评价每个粒子的适应值；

3)使用适应值对粒子进行选择；

4)调整粒子的搜索位置，粒子从新的位置开始搜索；

5)检查终止条件．如果达到最大迭代次数或者最好解停滞不再变化，就终止迭代；否则回到步骤(2)。

混合PSO算法的流程如图2．3

图2．3混合PSO算法的流程图

文献[24]进一步提出具有繁殖和子群的HPSO算法。粒子群中的粒子被赋予一个杂交概率，这个杂交概率是用户确定的，与粒子的适应值无关。在每次迭代中，依据杂交概率选取指定数量的粒子放入一个池中。池中的粒子随机地两两杂交，产生同样数目的孩子粒子，并用孩子粒子代替父母粒子，以保持种群的粒子数目不变。孩子粒子的位置由父母粒子的位置的算术加权和计算，即

(2．3)

(2．4)

其中是D维的位置矢量，而和，k=1,2分别指明是孩子粒子还是父母粒子的位置；

是D维均匀分布的随机数向量，为杂交概率，的每个分量都在[0，1]取值。

孩子粒子的速度分别由下面的公式得到：

（2.5）

（2.6）

其中是D维的速度矢量，而和，k=l，2分别指明是孩子粒子还是父母粒子的速度。对局部版的PSO算法而言，相当于在一个种群中划分了若干个子群，因此，杂交操作既可以在同一子群内部进行，也可以选择再不同的子群之间进行。

同时，在文献[22-24]的实验结果显示，HPSO算法的收敛速度比较快，搜索精度也相对比较高，对一类非线性优化问题可以得到满意的结果。不过引入了较多的待调整参数，对使用者的经验有一定要求。

4．3 协同PSO(Cooperative Particle Swarm Optimization，CPSO)

文献[25,28]提出了一种协同PSO算法，其基本思想是用K个相互独立的粒子群分别在D维的目标搜索空间中的不同维度方向上进行搜索。具体做法是：选定划分因子(split factor)K和粒子群的粒子数M，将输入的D维向量(粒子的位置及速度向量)划分到K个粒子群。前(D mod K)个粒子群，其粒子的位置及速度向量都是D／K维的；而后K一(D mod K)个粒子群，其粒子的位置及速度向量也是D／K维的。在每一步迭代中这K 个的粒子群相互独立地进行状态更新，粒子群之间不共享信息。

计算适应值时，将每个粒子群中最优粒子的位置向量拼接起来，组成D维向量并代入适应函数计算适应值。例如，考虑有24个自变量的优化问题，即D=24。如果选取M=10，K=5，那么每个粒子的位置及速度向量的维数就是D／K=5。

这种协同PSO算法有明显的“启动延迟”[25](start up delay)现象，在迭代初期，适应值下降缓慢，换言之，收敛速度慢。文献[27]的实验结果显示粒子群数目越大，收敛越慢。不过这种协同PSO算法因为实际上

采用的是局部学习策略，因此比基本PSO算法更易跳出局部极小点，达到较高的收敛精度。

4．4 离散PSO(Discrete Particle Swarm Optimization)

PSO的基本算法最初是用来对连续函数进行优化的。而实际中许多问题是组合优化向题，因此，Kennedy 和Eberhart博士在基本PSO算法[26]的基础上发展了离散二进制版PSO算法来解决这一类问题。

离散二进制版PSO算法与基本PSO算法的主要区别在于运动方程(即公式(1)，(2))，离散二进制版PSO算法的运动方程如下：

（2.7）

（2.8）

式（2.8）中，是sigmoid函数；是随机矢量的第d维分量，粒子的位置只有(o，1)两种状态，而速度V与某个概率的门限值相关，速度越大，则粒子位置取1的可能性越大，反之越小。

在式(2．7)中没有权重函数w对速度进行调节。为防止速度V过大，可以设置Vmax，使函数sig(V)不会过于接近0或1，以保证一定的概率使算法从一种状态跃迁到另一种状态。

从上文可以看出，除了式(2．7)，(2．8)不同，离散二进制版的PSO算法与基本PSO算法几乎一样。

而文献[27]推广了这一工作，研究了离散版的PSO算法，并将其应用于旅行商问题(TSP)的求解。离散PSO算法扩展了基本PSO算法的应用领域，尤其是让人看到了在一类组合优化问题中的应用前景。但是，正如文献[26]指出的那样，PSO算法的优势在于求解一些连续函数的优化问题，目前的离散PSO算法在组合优化这类问题上未能有如同蚁群算法那样有优势。

第五章PSO的应用

已经有一些利用PSO算法代替反向传播算法来训练神经网络的论文，研究表明PSO算法是一种很有潜力的神经元网络训练算法。PSO算法速度比较快而且可以得到比较好的结果，还没有遗传算法碰到的问题[29]。PSO算法被用于选择BP神经元网络的权值[30]。文献[30]使用BP神经网络的输入层、隐含层和输出层分别有5个、3个和1个神经元。他们使用标准BP算法训练，需要大约3.5小时，而使用PSO算法以后，训练时间降为2.2分钟。此外，用PSO算法进化神经网络的一个成功例子是用于分析人的颤抖。

对人的颤抖的诊断，包括帕金森(Parkinson)病和原发性振颤(Essential Tremor)，是一个非常有挑战性的领域[31]。PSO算法被应用于进化一个神经网络这个进化神经网络能快速和准确地辨别正常颤抖和病态颤抖。

PSO算法也被成功地应用于电力系统领域[32-35]，这里主要涉及到带有约束条件的，使用不同版本的PSO 算法相结合用来决定对连续和离散的控制变量的控制策略的问题。

PSO算法和其它演化计算算法类似，能用于求解大多数优化问题，比如多元函数的优化问题，包括带

约束的优化问题[36]。此外，PSO还在动态问题[37]和多目标优化问题[38]中得到应用。

目前，对PSO算法的研究才刚刚起步，相对其它比较成熟的演化算法，应用的范围小。但随着研究的进一步深入，PSO算法将会应用到越来越多的领域中，如电路设计、分类、作业调度、机器人路径。

第六章总结与展望

PSO从被提出至今，已经经历了15个年头，PSO也从最初的完善模型阶段到现在的广泛应用阶段，经历了从幼稚到成熟的蜕变。最初的PSO算法研究主要是粒子群模型的的构建，当静态的粒子群优化算法成熟后，学者们发现这类算法不能很好的适应解决一些多模态复杂搜索空间的问题，因此很多学者致力于研究动态参数的PSO算法，在这方面上也取得了不小的成就，除此之外，由于PSO是一种特殊的进化算法，其在算法末期也存在多样性不足而容易陷入局部最优的问题，对于PSO拓扑结构的研究证实不同的拓扑结构对于种群的多样性保持的效果也不同，运用不同的拓扑结构来改进PSO算法也是一种比较有效的方法，PSO算法存在一些不足也可以与其他算法结合来解决。

PSO是一种模拟社会模型的优化算法，其强调“自我感知”和“社会学习”，是不同于强调“自然选择”的进化算法的，这是比自然进化更高级的过程，于是PSO有了很好的高效性，因此在各种实际问题上应用取得了较好的效果。但是不可避免的是，PSO算法模型设计过于简单，其实在现实世界中的“自我感知”同“社会学习”过程是很复杂的，两者之间的关系也不是简单的叠加所能描述的，所以目前的PSO算法模型限制了其发展空间。因此，以下几个方面是PSO未来的发展方向：

?更加灵活的自适应调节PSO算法的参数；

?设计更复杂拓扑结构来模拟社会模型；

?寻找PSO算法和其他算法更好的结合点。

参考文献

[1] Angeline P J. Evolutionary Optimization Versus Particle Swarm Optimization：Philosophy and Performance

Differences．Proc．Seventh Annual Conference on Evolutionary Programming，1998,256-260

[2] 张丽平. 粒子群优化算法的理论与实践：[博士学位论文]．杭州：浙江大学，2005

[3] 李士勇. 蚁群算法及其应用．哈尔滨：哈尔滨工业大学出版社，2004，18-21

[4] Eberhart R C，Kennedy J.A New Optimizer Using Particle Swarm Theory.Proc.Sixth International Symposium on Micromachine and

Human Science，1995，V ol．3：39-43

[5] Reynolds C．Flocks，Herds，and Schools：A Distributed Behavioral Model．Computer Graphics．1987．2 1(4)：25—34

[6] 李建勇. 优化算法研究[硕士学位论文]. 浙江大学, 2004

[7] Koza J R．Genetic Programming：On the Programming of Computers by Means if Natural Selection．MIT Press，Cambridge，1992

[8] J. Kennedy and R. Mendes, “Population structure and particle swarm performance,” in Proc. IEEE Congr. Evol.

Comput., Honolulu, HI, 2002, pp. 1671–1676.

[9] Morten L?vbjerg, Thomas Kiel Rasmussen and Thiemo Krink, “Hybrid Particle Swarm Optimiser with Breeding and

Subpopulations”,

[10] J. J. Liang and P. N. Suganthan, “Dynamic multi-swarm particle swarm optimizer with local search,”in Proc. IEEE Congr. Evol.

Comput., 2005,pp. 522–528.

[11] R. Brits, A. P. Engelbrecht, and F. van den Bergh, “A niching particle swarm optimizer,” in Proc. 4th Asia-Paci?c Conf. Simul. Evol.

Learn.,2002, pp. 692–696.

[12] F. van den Bergh and A. P. Engelbrecht, “A cooperative approach to particle swarm optimization,”IEEE Trans. Evol. Comput., vol.

8, no. 3,pp. 225–239, Jun. 2004.

[13]周明，孙树栋．遗传算法原理及应用北京：国防工业出版社，1999，18．24

[14]Angeline P J Using Selection to Improve Particle Swarm Optimization Proc．IEEE International Congress on Evolutionary

Computation(CEC 1998)，278—282

[15] P. Angeline, “Evolutio nary optimization versus particle swarm optimization: Philosophy and performance

differences,” in Evolutionary Programming VII, V. W. Porto, N. Saravanan, D. Waagen, and A. E. Eiben, Eds. Berlin, Germany: Springer-Verlag, 1998, pp. 601–610.

[16] R. C. Eberhart and Y. Shi, ”Comparison between Genetic Algorithms and Particle SwarmOptimization”, Evolutionary Programming

VII (1998), Lecture Notes in Computer Science 1447, 611–616. Springer.

[17] Y. P. Chen, W. C. Peng, and M. C. Jian, “Particle swarm optimization with recombination and dynamic linkage discovery,” IEEE

Trans. Syst., Man, Cybern. B, Cybern., vol. 37, no. 6, pp. 1460–1470, Dec. 2007.

[18] W. J. Zhang and X. F. Xie, “DEPSO: Hybrid particle swarm with differential evolution operator,” in Proc. IEEE Conf. Syst., Man,

Cybern.,Oct. 2003, pp. 3816–3821.

[19] P. S. Andrews, “An investigation into mutation operators for particle swarm optimization,” in Proc. IEEE Congr.

Evol. Comput., Vancouver, BC, Canada, 2006, pp. 1044–1051.

[20] P. J. A ngeline, “Using selection to improve particle swarm optimization,” in Proc. IEEE Congr. Evol. Comput., Anchorage, AK, 1998,

pp. 84–89.

[21] S.-Y. Ho, H.-S. Lin, W.-H. Liauh, and S.-J. Ho, “O PSO: Orthogonal particle swarm optimization and its

appl ication to task assignment problems,” IEEE Trans. Syst., Man, Cybern. A, Syst., Humans, vol. 38, no. 2,pp. 288–298, Mar.

2008.

[22]Angeline P．Using Selection to Improve Particle Swarm Optimization．In．Proc．of IEEE Intl．Conf．on Evolutionary

Computation(ICEC’98)．Anchorage．May 1998

[23]Angeline，P．Evolutionary Optimization versus particle swaIm Philosophy and Performance Differences[C]．In：Evolutionary

Programming VII。1998：601—6lO

[24]Lovbjerg，M．Rasmussen，T，K，Krink，T．Hybrid Particle Swarm Optimization with Breeding and Subpopulations[C]．In：

Proc of the third Genetic and Evolutionary Computation Conference，2001

[25]Van den Bergh，F．Engelbrecht，A．P．Effects of Swarm Size on Cooperatire Particle Swarm optimisers．In：Proceedings of the

Genetic and Evolutionary Computation Conference(GECCO)，San Franci SCO，USA，2001

[26]Kennedy J，Eberhart R．A discrete binary version of the particle swarm optimization algorithm．In：Proc．of the 1997 Conf．on

Systems，Man，and Cybernet ics(SMC’97)．1997．4104—4109

[27]Shi，Y．and Eberhart，RC．Fuzzy adaptive particle swarm optimization．Proceedings of the IEEE Congress on Evolutionary

Computation(CEC 2001)，Seoul，Korea．2001．

[28]Yan den Bergh F．Engelhrecht A P．Trainning Product Unit Networks Using Cooperative Particle Swarm Optimizers[C]．In．Proc of

the third Genetic and Evelutionarv Computation Conference．San https://www.wendangku.net/doc/2416265018.html,A Microprocessors and Microsystems 26(2002)363—371

[29]Hu Yiaohui．粒子群优化算法介绍．http：// icdweb．cc．purdue．edu／~hux

[30]Kennedy J，Eberhart R C and Shi Y．Swarm Intelligence．Morgan Kaufmann Publishers，San FranciSCO，California，200l.

[31]Eberhart R．Hu Xiaohui．Human tremor analysis using particle swarm optimization In：Proc．of the Congress on EvoIntonary

Computation[C]，1999．1927—1930

[32]Fukuyama Y．et a1．A Particle Swarm Ootimization for Reactive Power and V oltage Control Consideriug V oltage Security

Accessment．IEEE Transaction on Power Systems．2000．15(4)

[33]Fukuyama Y．Yoshtda H．A Particle Swarm Optimization for Reactive Power and V oltage Control m Electric Power Systems．In：

Proe．of Congress on Evolutionary Computation(CEC2001)．Seoul．Korea．Piscataway．NJ：IEEE Service Center．2001 [34]Naka S．Genji T．Y ura T．Fukuyama Y．Practical Distribution State Estimation Using Hybrid Particle Swarm OrItim atmn．In：

Proc．of IEEE Power Engineering Society Winter Meetting Columbus，01io，USA．2001

[35]Yoshida H，Kawata K．Fukuyamna Y．Nakanishi Y．A particle swarm optimization for reactive power and voltage control considering

voltage stability．In：G，L¨Torres．A．P．Alves da Silva．eds．Proe．of Intl．Conf．on Intelligent System Application to Power Systems(ISAP’99)．Rio de Janeiro．Bracul．1999．117一121

[36]Ray T，Mew i M．A swarm with an effective information sharing mechanism for unconstrained and constrained single objective

optimization problems lAJ．In：Proc IEEE Inc．Conf．on Evolutionary Computation[C]，2001．75 80

[37]Eberhart R，S1it Yuhui．Tracking and optimizing dynamic systems with particle swarms[A]．In：Proc．IEEE Int．Conf．on Evolutionary

Computation EC]．2001．94．100

[38]Parsopouloa K E．Vrahatis M N．Particle Swarm Optimimtion Method in Mulnobjective Problems．In：Proc．of the 2002 ACM

Symposium on Applied Computing(SAC 2002)．PP．603 607．ISBN：1-58113-

聚类分析K-means算法综述

聚类分析K-means算法综述 摘要：介绍K-means聚类算法的概念，初步了解算法的基本步骤，通过对算法缺点的分析，对算法已有的优化方法进行简单分析，以及对算法的应用领域、算法未来的研究方向及应用发展趋势作恰当的介绍。 关键词：K-means聚类算法基本步骤优化方法应用领域研究方向应用发展趋势 算法概述 K-means聚类算法是一种基于质心的划分方法，输入聚类个数k，以及包含n个数据对象的数据库，输出满足方差最小标准的k个聚类。 评定标准：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算。 解释：基于质心的划分方法就是将簇中的所有对象的平均值看做簇的质心，然后根据一个数据对象与簇质心的距离，再将该对象赋予最近的簇。 k-means 算法基本步骤 （1）从n个数据对象任意选择k 个对象作为初始聚类中心 （2）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分 （3）重新计算每个（有变化）聚类的均值（中心对象） （4）计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤（2） 形式化描述 输入：数据集D，划分簇的个数k 输出：k个簇的集合 （1）从数据集D中任意选择k个对象作为初始簇的中心； （2）Repeat （3）For数据集D中每个对象P do （4）计算对象P到k个簇中心的距离 （5）将对象P指派到与其最近（距离最短）的簇；

（6）End For （7）计算每个簇中对象的均值，作为新的簇的中心； （8）Until k个簇的簇中心不再发生变化 对算法已有优化方法的分析 (1)K-means算法中聚类个数K需要预先给定 这个K值的选定是非常难以估计的，很多时候,我们事先并不知道给定的数据集应该分成多少个类别才最合适，这也是K一means算法的一个不足"有的算法是通过类的自动合并和分裂得到较为合理的类型数目k，例如Is0DAIA算法"关于K一means算法中聚类数目K 值的确定，在文献中，根据了方差分析理论，应用混合F统计量来确定最佳分类数，并应用了模糊划分嫡来验证最佳分类数的正确性。在文献中，使用了一种结合全协方差矩阵RPCL算法，并逐步删除那些只包含少量训练数据的类。文献中针对“聚类的有效性问题”提出武汉理工大学硕士学位论文了一种新的有效性指标：V(k km) = Intra(k) + Inter(k) / Inter(k max)，其中k max是可聚类的最大数目,目的是选择最佳聚类个数使得有效性指标达到最小。文献中使用的是一种称为次胜者受罚的竞争学习规则来自动决定类的适当数目"它的思想是：对每个输入而言不仅竞争获胜单元的权值被修正以适应输入值，而且对次胜单元采用惩罚的方法使之远离输入值。 (2)算法对初始值的选取依赖性极大以及算法常陷入局部极小解 不同的初始值，结果往往不同。K-means算法首先随机地选取k个点作为初始聚类种子，再利用迭代的重定位技术直到算法收敛。因此，初值的不同可能导致算法聚类效果的不稳定，并且，K-means算法常采用误差平方和准则函数作为聚类准则函数(目标函数)。目标函数往往存在很多个局部极小值，只有一个属于全局最小，由于算法每次开始选取的初始聚类中心落入非凸函数曲面的“位置”往往偏离全局最优解的搜索范围，因此通过迭代运算，目标函数常常达到局部最小，得不到全局最小。对于这个问题的解决，许多算法采用遗传算法(GA)，例如文献中采用遗传算法GA进行初始化，以内部聚类准则作为评价指标。 (3)从K-means算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时,算法的时间开销是非常大 所以需要对算法的时间复杂度进行分析，改进提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的候选集，而在文献中，使用的K-meanS算法是对样本数据进行聚类。无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。

粒子群优化算法综述

粒子群优化算法综述 摘要：本文围绕粒子群优化算法的原理、特点、改进与应用等方面进行全面综述。侧重于粒子群的改进算法，简短介绍了粒子群算法在典型理论问题和实际工业对象中的应用，并给出了粒子群算三个重要的网址，最后对粒子群算做了进一步展望。 关键词；粒子群算法；应用；电子资源；综述 0.引言 粒子群优化算法]1[(Particle Swarm Optimization ，PSO)是由美国的Kenned 和Eberhar 于1995年提出的一种优化算法,该算法通过模拟鸟群觅食行为的规律和过程，建立了一种基于群智能方法的演化计算技术。由于此算法在多维空间函数寻优、动态目标寻优时有实现容易，鲁棒性好，收敛快等优点在科学和工程领域已取得很好的研究成果。 1. 基本粒子群算法]41[- 假设在一个D 维目标搜索空间中，有m 个粒子组成一个群落，其中地i 个粒子组成一个D 维向量，),,,(21iD i i i x x x x =，m i ,2,1=，即第i 个粒子在D 维目标搜索空间中的位置是i x 。换言之，每个粒子 的位置就是一个潜在的解。将i x 带入一个目标函数就可以计算出其适 应值，根据适应值得大小衡量i x 的优劣。第i 个粒子的飞翔速度也是一个D 维向量，记为),,,(21iD i i i v v v v =。记第i 个粒子迄今为止搜索到的最优位置为),,,(21iD i i i p p p p =，整个粒子群迄今为止搜索到的最优位置为),,,(21gD gi g g p p p p =。 粒子群优化算法一般采用下面的公式对粒子进行操作

)()(22111t id t gd t id t id t id t id x p r c x p r c v v -+-+=+ω (1) 11+++=t id t id t id v x x (2) 式中，m i ,,2,1 =；D d ,,2,1 =；ω是惯性权重， 1c 和2c 是非负常数， 称为学习因子， 1r 和2r 是介于]1,0[间的随机数；],[max max v v v id -∈，max v 是常数，由用户设定。 2. 粒子群算法的改进 与其它优化算法一样PSO 也存在早熟收敛问题。随着人们对算 法搜索速度和精度的不断追求，大量的学者对该算法进行了改进，大致可分为以下两类：一类是提高算法的收敛速度；一类是增加种群多样性以防止算法陷入局部最优。以下是对最新的这两类改进的总结。 2.1.1 改进收敛速度 量子粒子群优化算法]5[:在量子系统中，粒子能够以某一确定的 概率出现在可行解空间中的任意位置，因此，有更大的搜索范围，与传统PSO 法相比，更有可能避免粒子陷入局部最优。虽然量子有更大的搜索空间，但是在粒子进化过程中，缺乏很好的方向指导。针对这个缺陷，对进化过程中的粒子进行有效疫苗接种，使它们朝着更好的进化方向发展，从而提高量子粒子群的收敛速度和寻优能力。 文化粒子群算法]6[:自适应指导文化PSO 由种群空间和信念空间 两部分组成。前者是基于PSO 的进化，而后者是基于信念文化的进化。两个空间通过一组由接受函数和影响函数组成的通信协议联系在一起，接受函数用来收集群体空间中优秀个体的经验知识；影响函数利用解决问题的知识指导种群空间进化；更新函数用于更新信念空间；

蚁群聚类算法综述

计算机工程与应用2006.16 引言 聚类分析是数据挖掘领域中的一个重要分支[1],是人们认 和探索事物之间内在联系的有效手段,它既可以用作独立的 据挖掘工具,来发现数据库中数据分布的一些深入信息,也 以作为其他数据挖掘算法的预处理步骤。所谓聚类(clus- ring)就是将数据对象分组成为多个类或簇(cluster),在同一 簇中的对象之间具有较高的相似度,而不同簇中的对象差别大。传统的聚类算法主要分为四类[2,3]:划分方法,层次方法, 于密度方法和基于网格方法。 受生物进化机理的启发,科学家提出许多用以解决复杂优 问题的新方法,如遗传算法、进化策略等。1991年意大利学A.Dorigo等提出蚁群算法,它是一种新型的优化方法[4]。该算不依赖于具体问题的数学描述,具有全局优化能力。随后他 其他学者[5～7]提出一系列有关蚁群的算法并应用于复杂的组优化问题的求解中,如旅行商问题(TSP)、调度问题等,取得 著的成效。后来其他科学家根据自然界真实蚂蚁群堆积尸体分工行为,提出基于蚂蚁的聚类算法[8,9],利用简单的智能体 仿蚂蚁在给定的环境中随意移动。这些算法的基本原理简单懂[10],已经应用到电路设计、文本挖掘等领域。本文详细地讨现有蚁群聚类算法的基本原理与性能,在归纳总结的基础上 出需要完善的地方,以推动蚁群聚类算法在更广阔的领域内 到应用。 2聚类概念及蚁群聚类算法 一个簇是一组数据对象的集合,在同一个簇中的对象彼此 类似,而不同簇中的对象彼此相异。将一组物理或抽象对象分组为类似对象组成的多个簇的过程被称为聚类。它根据数据的内在特性将数据对象划分到不同组(或簇)中。聚类的质量是基于对象相异度来评估的,相异度是根据描述对象的属性值来计算的,距离是经常采用的度量方式。聚类可用数学形式化描述为:设给定数据集X={x 1 ,x 2 ,…,x n },!i∈{1,2,…,n},x i ={x i1 ,x i2 , …,x

粒子群算法综述

粒子群算法综述 【摘要】：粒子群算法(pso)是一种新兴的基于群体智能的启发式全局搜索算法，具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已得到广泛研究和应用。为了进一步推广应用粒子群算法并为深入研究该算法提供相关资料，本文对目前国内外研究现状进行了全面分析，在论述粒子群算法基本思想的基础上，围绕pso的运算过程、特点、改进方式与应用等方面进行了全面综述，并给出了未来的研究方向展望。 【关键词】：粒子群算法优化综述 优化理论的研究一直是一个非常活跃的研究领域。它所研究的问题是在多方案中寻求最优方案。人们关于优化问题的研究工作，随着历史的发展不断深入，对人类的发展起到了重要的推动作用。但是，任何科学的进步都受到历史条件的限制，直到二十世纪中期，由于高速数字计算机日益广泛应用，使优化技术不仅成为迫切需要，而且有了求解的有力工具。因此，优化理论和算法迅速发展起来，形成一门新的学科。至今已出现线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。这些优化技术在诸多工程领域得到了迅速推广和应用，如系统控制、人工智能、生产调度等。随着人类生存空间的扩大，以及认识世界和改造世界范围的拓宽，常规优化法如牛顿法、车辆梯度法、模式搜索法、单纯形法等已经无法处理人们所面的复杂问题，因此高效的

优化算法成为科学工作者的研究目标之一。 1.粒子群算法的背景 粒子群算法(particle swarm optimization，pso)是一种新兴的演化算法。该算法是由j.kennedy和r.c.eberhart于1995年提出的一种基于群智能的随机优化算法。这类算法的仿生基点是：群集动物(如蚂蚁、鸟、鱼等)通过群聚而有效的觅食和逃避追捕。在这类群体的动物中，每个个体的行为是建立在群体行为的基础之上的，即在整个群体中信息是共享的，而且在个体之间存在着信息的交换与协作。如在蚁群中，当每个个体发现食物之后，它将通过接触或化学信号来招募同伴，使整个群落找到食源；在鸟群的飞行中，每只鸟在初始状态下处于随机位置，且朝各个方向随机飞行，但随着时间推移，这些初始处于随机状态的鸟通过相互学习(相互跟踪)组织的聚集成一个个小的群落，并以相同的速度朝着相同的方向飞行，最终整个群落聚集在同一位置──食源。这些群集动物所表现的智能常称为“群体智能”，它可表述为：一组相互之间可以进行直接通讯或间接通讯(通过改变局部环境)的主体，能够通过合作对问题进行分布求解。换言之，一组无智能的主体通过合作表现出智能行为特征。粒子群算法就是以模拟鸟的群集智能为特征，以求解连续变量优化问题为背景的一种优化算法。因其概念简单、参数较少、易于实现等特点，自提出以来已经受到国内外研究者的高度重视并被广泛应用于许多领域。

粒子群优化算法介绍及matlab程序

粒子群优化算法(1)—粒子群优化算法简介 PSO算法就是模拟一群鸟寻找食物的过程，每个鸟就是PSO中的粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中，不停改变自己在空中飞行的位置与速度。大家也可以观察一下，鸟群在寻找食物的过程中，开始鸟群比较分散，逐渐这些鸟就会聚成一群，这个群忽高忽低、忽左忽右，直到最后找到食物。这个过程我们转化为一个数学问题。寻找函数y=1-cos(3*x)*exp(-x)的在[0,4]最大值。该函数的图形如下： 当x=0.9350-0.9450，达到最大值y=1.3706。为了得到该函数的最大值，我们在[0, 4]之间随机的洒一些点，为了演示，我们放置两个点，并且计算这两个点的函数值，同时给这两个点设置在[0, 4]之间的一个速度。下面这些点就会按照一定的公式更改自己的位置，到达新位置后，再计算这两个点的值，然后再按照一定的公式更新自己的位置。直到最后在y=1.3706这个点停止自己的更新。这个过程与粒子群算法作为对照如下： 这两个点就是粒子群算法中的粒子。 该函数的最大值就是鸟群中的食物。 计算两个点函数值就是粒子群算法中的适应值，计算用的函数就是粒子群算法中的适应度函数。 更新自己位置的公式就是粒子群算法中的位置速度更新公式。 下面演示一下这个算法运行一次的大概过程： 第一次初始化 第一次更新位置

第二次更新位置 第21次更新 最后的结果（30次迭代） 最后所有的点都集中在最大值的地方。

粒子群优化算法(2)—标准粒子群优化算法 在上一节的叙述中，唯一没有给大家介绍的就是函数的这些随机的点（粒子）是如何运动的，只是说按照一定的公式更新。这个公式就是粒子群算法中的位置速度更新公式。下面就介绍这个公式是什么。在上一节中我们求取函数y=1-cos(3*x)*exp(-x)的在[0, 4]最大值。并在[0,4]之间放置了两个随机的点，这些点的坐标假设为x1=1.5，x2=2.5；这里的点是一个标量，但是我们经常遇到的问题可能是更一般的情况—x 为一个矢量的情况，比如二维z=2*x1+3*x22的情况。这个时候我们的每个粒子均为二维，记粒子P1＝(x11,x12),P2=(x21,x22),P3=(x31,x32)，......Pn=(xn1,xn2)。这里n 为粒子群群体的规模，也就是这个群中粒子的个数，每个粒子的维数为2。更一般的是粒子的维数为q ，这样在这个种群中有n 个粒子，每个粒子为q 维。 由n 个粒子组成的群体对Q 维（就是每个粒子的维数）空间进行搜索。每个粒子表示为：x i ＝（x i1,x i2,x i3,...,x iQ ），每个粒子对应的速度可以表示为v i =(v i1,v i2,v i3,....,v iQ )，每个粒子在搜索时要考虑两个因素： 1. 自己搜索到的历史最优值 p i ，p i =(p i1,p i2,....,p iQ )，i=1,2,3,....,n ； 2. 全部粒子搜索到的最优值p g ，p g =(p g1,p g2,....,p gQ )，注意这里的p g 只有一个。 下面给出粒子群算法的位置速度更新公式： 112()()()()k k k k i i i i v v c rand pbest x c rand gbest x ω+=+??-+??-, 11k k k i i i x x av ++=+. 这里有几个重要的参数需要大家记忆，因为在以后的讲解中将会经常用到，它们是： ω是保持原来速度的系数，所以叫做惯性权重。1c 是粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识，所以叫“认知”。通常设置为2。2c 是粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识，所以叫做“社会知识”，经常叫做“社会”。通常设置为2。()rand 是[0,1]区间内均匀分布的随机数。a 是对位置更新的时候，在速度前面加的一个系数，这个系数我们叫做约束因子。通常设置为1。这样一个标准的粒子群算法就介绍结束了。下图是对整个基本的粒子群的过程给一个简单的图形表示。 判断终止条件可是设置适应值到达一定的数值或者循环一定的次数。 注意：这里的粒子是同时跟踪自己的历史最优值与全局（群体）最优值来改变自己的位置预速度的，所以又叫做全局版本的标准粒子群优化算法。

K-means-聚类算法研究综述

K-means聚类算法研究综述 摘要:总结评述了K-means聚类算法的研究现状，指出K-means聚类算法是一个NP难优化问题，无法获得全局最优。介绍了K-means聚类算法的目标函数，算法流程，并列举了一个实例，指出了数据子集的数目K，初始聚类中心选取，相似性度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法，指出了K-means 聚类的进一步研究方向。 关键词：K-means聚类算法；NP难优化问题；数据子集的数目K；初始聚类中心选取；相似性度量和距离矩阵 Review of K-means clustering algorithm Abstract: K-means clustering algorithm is reviewed. K-means clustering algorithm is a NP hard optimal problem and global optimal result cannot be reached. The goal，main steps and example of K-means clustering algorithm are introduced. K-means algorithm requires three user-specified parameters: number of clusters K，cluster initialization，and distance metric. Problems and improvement of K-means clustering algorithm are summarized then. Further study directions of K-means clustering algorithm are pointed at last. Key words: K-means clustering algorithm; NP hard optimal problem; number of clusters K; cluster initialization; distance metric K-means聚类算法是由Steinhaus1955年、Lloyed1957年、Ball & Hall1965年、McQueen1967年分别在各自的不同的科学研究领域独立的提出。K-means聚类算法被提出来后，在不同的学科领域被广泛研究和应用，并发展出大量不同的改进算法。虽然K-means聚类算法被提出已经超过50年了，但目前仍然是应用最广泛的划分聚类算法之一[1]。容易实施、简单、高效、成功的应用案例和经验是其仍然流行的主要原因。 文中总结评述了K-means聚类算法的研究现状，指出K-means聚类算法是一个NP难优化问题，无法获得全局最优。介绍了K-means聚类算法的目标函数、算法流程，并列举了一个实例，指出了数据子集的数目K、初始聚类中心选取、相似性度量和距离矩阵为K-means聚类算法的3个基本参数。总结了K-means聚类算法存在的问题及其改进算法，指出了K-means聚类的进一步研究方向。 1经典K-means聚类算法简介 1.1K-means聚类算法的目标函数 对于给定的一个包含n个d维数据点的数据集 12 {x,x,,x,,x} i n X=??????，其中d i x R ∈，以及要生成的数据子集的数目K，K-means聚类算法将数据对象组织为 K个划分{c,i1,2,} k C K ==???。每个划分代表一个类c k，每个类c k有一个类别中心iμ。选取欧氏距离作为相似性和 距离判断准则，计算该类内各点到聚类中心 i μ的距离平方和 2 (c) i i k i k x C J xμ ∈ =- ∑（1） 聚类目标是使各类总的距离平方和 1 (C)(c) K k k J J = =∑最小。 22 1111 (C)(c) i i K K K n k i k ki i k k k x C k i J J x d x μμ ==∈== ==-=- ∑∑∑∑∑ （2）其中， 1 i i ki i i x c d x c ∈ ? =? ? ? 若 若 ，显然，根据最小二乘 法和拉格朗日原理，聚类中心 k μ应该取为类别 k c类各数据点的平均值。 K-means聚类算法从一个初始的K类别划分开始，然

粒子群优化算法及其应用研究【精品文档】(完整版)

摘要 在智能领域，大部分问题都可以归结为优化问题。常用的经典优化算法都对问题有一定的约束条件，如要求优化函数可微等，仿生算法是一种模拟生物智能行为的优化算法，由于其几乎不存在对问题的约束，因此，粒子群优化算法在各种优化问题中得到广泛应用。 本文首先描述了基本粒子群优化算法及其改进算法的基本原理,对比分析粒子群优化算法与其他优化算法的优缺点，并对基本粒子群优化算法参数进行了简要分析。根据分析结果,研究了一种基于量子的粒子群优化算法。在标准测试函数的优化上粒子群优化算法与改进算法进行了比较,实验结果表明改进的算法在优化性能明显要优于其它算法。本文算法应用于支持向量机参数选择的优化问题上也获得了较好的性能。最后,对本文进行了简单的总结和展望。 关键词：粒子群优化算法最小二乘支持向量机参数优化适应度

目录 摘要...................................................................... I 目录....................................................................... II 1.概述. (1) 1.1引言 (1) 1.2研究背景 (1) 1.2.1人工生命计算 (1) 1.2.2 群集智能理论 (2) 1.3算法比较 (2) 1.3.1粒子群算法与遗传算法(GA)比较 (2) 1.3.2粒子群算法与蚁群算法(ACO)比较 (3) 1.4粒子群优化算法的研究现状 (4) 1.4.1理论研究现状 (4) 1.4.2应用研究现状 (5) 1.5粒子群优化算法的应用 (5) 1.5.1神经网络训练 (6) 1.5.2函数优化 (6) 1.5.3其他应用 (6) 1.5.4粒子群优化算法的工程应用概述 (6) 2.粒子群优化算法 (8) 2.1基本粒子群优化算法 (8) 2.1.1基本理论 (8) 2.1.2算法流程 (9) 2.2标准粒子群优化算法 (10) 2.2.1惯性权重 (10) 2.2.2压缩因子 (11) 2.3算法分析 (12) 2.3.1参数分析 (12) 2.3.2粒子群优化算法的特点 (14) 3.粒子群优化算法的改进 (15) 3.1粒子群优化算法存在的问题 (15) 3.2粒子群优化算法的改进分析 (15) 3.3基于量子粒子群优化(QPSO)算法 (17) 3.3.1 QPSO算法的优点 (17) 3.3.2 基于MATLAB的仿真 (18) 3.4 PSO仿真 (19) 3.4.1 标准测试函数 (19) 3.4.2 试验参数设置 (20) 3.5试验结果与分析 (21) 4.粒子群优化算法在支持向量机的参数优化中的应用 (22) 4.1支持向量机 (22) 4.2最小二乘支持向量机原理 (22)

粒子群算法的研究现状及其应用

智能控制技术 课程论文 中文题目: 粒子群算法的研究现状及其应用姓名学号: 指导教师： 年级与专业： 所在学院： XXXX年XX月XX日

1 研究的背景 优化问题是一个古老的问题，可以将其定义为：在满足一定约束条件下，寻找一组参数值，使系统的某些性能指标达到最大值或最小值。在我们的日常生活中，我们常常需要解决优化问题，在一定的范围内使我们追求的目标得到最大化。为了解决我们遇到的最优化问题，科学家，们进行了不懈的努力，发展了诸如牛顿法、共轭梯度法等诸多优化算法，大大推动了优化问题的发展，但由于这些算法的低运行效率，使得在计算复杂度、收敛性等方面都无法满足实际的生产需要。 对此，受达尔文进化论的影响，一批新的智能优化算法相继被提出。粒子群算法（PSO ）就是其中的一项优化技术。1995 年Eberhart 博士和Kennedy 博士[1]-[3]通过研究鸟群捕食的行为后，提出了粒子群算法。设想有一群鸟在随机搜索食物，而在这个区域里只有一块食物，所有的鸟都不知道食物在哪里。那么找到食物最简单有效的办法就是鸟群协同搜寻，鸟群中的每只鸟负责离其最近的周围区域。 粒子群算法是一种基于群体的优化工具，尤其适用于复杂和非线性问题。系统初始化为一组随机解，通过迭代搜寻最优值，通过采用种群的方式组织搜索，同时搜索空间内的多个区域，所以特别适合大规模并行计算，具有较高的效率和简单、易操作的特性。 目前使用的粒子群算法的数学描述[3]为：设粒子的寻优空间是m 维的，粒子的数目为ps ，算法的最大寻优次数为Iter 。第i 个粒子的飞行速度为T i i1i2im v [v v ]= ,,,v ，位置为T i i1i2im x [x x x ]= ,,,，粒子的个体极值T i i1i2im Pbest [,]P = ,P ,P ，全局极值为 T i i1i2im Gbest [,]g = ,g ,g 。 粒子群算法的寻优过程主要由粒子的速度更新和位置更新两部分组成，其更新方式如下： i+11122v ()()i i i i i v c r Pbest x c r Gbest x =+?+?； i+1i+1i x x v =+， 式中：12c c ，为学习因子，一般取2；12r r ，是均与分布着[0,1]上的随机数。

粒子群算法详解-附matlab代码说明

粒子群算法(1)----粒子群算法简介 一、粒子群算法的历史 粒子群算法源于复杂适应系统（Complex Adaptive System,CAS）。CAS理论于1994年正式提出，CAS中的成员称为主体。比如研究鸟群系统，每个鸟在这个系统中就称为主体。主体有适应性，它能够与环境及其他的主体进行交流，并且根据交流的过程“学习”或“积累经验”改变自身结构与行为。整个系统的演变或进化包括：新层次的产生（小鸟的出生）；分化和多样性的出现（鸟群中的鸟分成许多小的群）；新的主题的出现（鸟寻找食物过程中，不断发现新的食物）。 所以CAS系统中的主体具有4个基本特点（这些特点是粒子群算法发展变化的依据）： 首先，主体是主动的、活动的。 主体与环境及其他主体是相互影响、相互作用的，这种影响是系统发展变化的主要动力。 环境的影响是宏观的，主体之间的影响是微观的，宏观与微观要有机结合。 最后，整个系统可能还要受一些随机因素的影响。 粒子群算法就是对一个CAS系统－－－鸟群社会系统的研究得出的。 粒子群算法（Particle Swarm Optimization, PSO）最早是由Eberhart和Kennedy于1995年提出，它的基本概念源于对鸟群觅食行为的研究。设想这样一个场景:一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 PSO算法就从这种生物种群行为特性中得到启发并用于求解优化问题。在PSO中，每个优化问题的潜在解都可以想象成d维搜索空间上的一个点，我们称之为“粒子”（Particle），所有的粒子都有一个被目标函数决定的适应值(Fitness Value )，每个粒子还有一个速度决定他们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索。Reynolds对鸟群飞行的研究发现。鸟仅仅是追踪它有限数量的邻居但最终的整体结果是整个鸟群好像在一个中心的控制之下.即复杂的全局行为是由简单规则的相互作用引起的。 二、粒子群算法的具体表述 上面罗嗦了半天，那些都是科研工作者写论文的语气，不过，PSO的历史就像上面说的那样。下面通俗的解释PSO算法。 PSO算法就是模拟一群鸟寻找食物的过程，每个鸟就是PSO中的粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中，不停改变自己在空中飞行的位置与速度。大家也可以观察一下，鸟群在寻找食物的过程中，开始鸟群比较分散，逐渐这些鸟就会聚成一群，这个群忽高忽低、忽左忽右，直到最后找到食物。这个过程我们转化为一个数学问题。寻找函数y=1-cos(3*x)*exp(-x)的在[0,4]最大值。该函数的图形如下：

粒子群算法(1)----粒子群算法简介

粒子群算法(1)----粒子群算法简介 二、粒子群算法的具体表述 上面罗嗦了半天，那些都是科研工作者写论文的语气，不过，PSO的历史就像上面说的那样。下面通俗的解释PSO算法。 PSO算法就是模拟一群鸟寻找食物的过程，每个鸟就是PSO.中的粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中，不停改变自己在空中飞行的位置与速度。大家也可以观察一下，鸟群在寻找食物的过程中，开始鸟群比较分散，逐渐这些鸟就会聚成一群，这个群忽高忽低、忽左忽右，直到最后找到食物。这个过程我们转化为一个数学问题。寻找函数y=1-cos(3*x)*exp(-x)的在[0,4]最大值。该函数的图形如下： 当x=0.9350-0.9450，达到最大值y=1.3706。为了得到该函数的最大值，我们在[0，4]之间随机的洒一些点，为了演示，我们放置两个点，并且计算这两个点的函数值，同时给这两个点设置在[0，4]之间的一个速度。下面这些点就会按照一定的公式更改自己的位置，到达新位置后，再计算这两个点的值，然后再按照一定的公式更新自己的位置。直到最后在y=1.3706这个点停止自己的更新。这个过程与粒子群算法作为对照如下： 这两个点就是粒子群算法中的粒子。 该函数的最大值就是鸟群中的食物 计算两个点函数值就是粒子群算法中的适应值，计算用的函数就是粒子群算法中的适应度函数。 更新自己位置的一定公式就是粒子群算法中的位置速度更新公式。 下面演示一下这个算法运行一次的大概过程： 第一次初始化

第一次更新位置 第二次更新位置

第21次更新 最后的结果（30次迭代） 最后所有的点都集中在最大值的地方。

粒子群算法基本原理

4.1粒子群算法基本原理 粒子群优化算法[45]最原始的工作可以追溯到1987年Reynolds 对鸟群社会系统Boids （Reynolds 对其仿真鸟群系统的命名）的仿真研究 。通常，群体的行为可以由几条简单的规则进行建模，虽然每个个体具有简单的行为规则，但是却群体的行为却是非常的复杂，所以他们在鸟类仿真中，即Boids 系统中采取了下面的三条简单的规则： （1）飞离最近的个体(鸟)，避免与其发生碰撞冲突； （2）尽量使自己与周围的鸟保持速度一致； （3）尽量试图向自己认为的群体中心靠近。 虽然只有三条规则，但Boids 系统已经表现出非常逼真的群体聚集行为。但Reynolds 仅仅实现了该仿真，并无实用价值。 1995年Kennedy [46-48]和Eberhart 在Reynolds 等人的研究基础上创造性地提出了粒子群优化算法，应用于连续空间的优化计算中 。Kennedy 和Eberhart 在boids 中加入了一个特定点，定义为食物，每只鸟根据周围鸟的觅食行为来搜寻食物。Kennedy 和Eberhart 的初衷是希望模拟研究鸟群觅食行为，但试验结果却显示这个仿真模型蕴含着很强的优化能力，尤其是在多维空间中的寻优。最初仿真的时候，每只鸟在计算机屏幕上显示为一个点，而“点”在数学领域具有多种意义，于是作者用“粒子（particle ）”来称呼每个个体，这样就产生了基本的粒子群优化算法[49]。 假设在一个D 维搜索空间中，有m 个粒子组成一粒子群，其中第i 个粒子的空间位置为123(,,,...,)1,2,...,i i i i iD X x x x x i m ==，它是优化问题的一个潜在

基于聚类的图像分割方法综述

信息疼术2018年第6期文章编号=1009 -2552 (2018)06 -0092 -03 DOI：10.13274/https://www.wendangku.net/doc/2416265018.html,ki.hdzj.2018. 06.019 基于聚类的图像分割方法综述 赵祥宇\陈沫涵2 (1.上海理工大学光电信息与计算机学院，上海200093; 2.上海西南位育中学，上海200093) 摘要：图像分割是图像识别和机器视觉领域中关键的预处理操作。分割理论算法众多，文中 具体介绍基于聚类的分割算法的思想和原理，并将包含的典型算法的优缺点进行介绍和分析。经过比较后，归纳了在具体应用中如何对图像分割算法的抉择问题。近年来传统分割算法不断 被科研工作者优化和组合，相信会有更多的分割新算法井喷而出。 关键词：聚类算法；图像分割；分类 中图分类号：TP391.41 文献标识码：A A survey of image segmentation based on clustering ZHAO Xiang-yu1，CHEN Mo-han2 (1.School of Optical Electrical and Computer Engineering，University of Shanghai for Science and Technology，Shanghai200093，China；2.Shanghai Southwest Weiyu Middle School，Shanghai200093，China) Abstract:Image segmentation is a key preprocessing operation in image recognition and machine vision. There are many existing theoretical methods,and this paper introduces the working principle ol image segmentation algorithm based on clustering.Firstly,the advantages and disadvantages ol several typical algorithms are introduced and analyzed.Alter comparison,the paper summarizes the problem ol the selection ol image segmentation algorithm in practical work.In recent years,the traditional segmentation algorithms were improved and combined by the researchers,it believes that more new algorithms are blown out. Key words:clustering algorithm；image segmentation；classilication 0引百 近年来科学技术的不断发展，计算机视觉和图像 识别发挥着至关重要的作用。在实际应用和科学研 究中图像处理必不可少,进行图像处理必然用到图像 分割方法,根据检测图像中像素不重叠子区域，将感 兴趣目标区域分离出来。传统的图像分割方法:阈值 法[1]、区域法[2]、边缘法[3]等。近年来传统分割算法 不断被研究人员改进和结合，出现了基于超像素的分 割方法[4]，本文主要介绍超像素方法中基于聚类的经 典方法，如Mean Shift算法、K-m eans 算法、Fuzzy C-mean算法、Medoidshilt算法、Turbopixels算法和 SLIC 算法。简要分析各算法的基本思想和分割效果。 1聚类算法 1.1 Mean Shil't算法 1975年,Fukunaga[5]提出一种快速统计迭代算法，即Mean Shilt算法（均值漂移算法）。直到1995 年,Cheng[6]对其进行改进，定义了核函数和权值系 数，在全局优化和聚类等方面的应用，扩大了 Mean shil't算法适用范围。1997至2003年间，Co-maniciu[7-9]提出了基于核密度梯度估计的迭代式 搜索算法,并将该方法应用在图像平滑、分割和视频 跟踪等领域。均值漂移算法的基本思想是通过反复 迭代计算当前点的偏移均值，并挪动被计算点，经过 反复迭代计算和多次挪动，循环判断是否满足条件, 达到后则终止迭代过程[10]。Mean shil't的基本形 式为： 收稿日期：2017-06 -13 基金项目：国家自然科学基金资助项目（81101116) 作者简介：赵祥宇（1992-)，男，硕士研究生，研究方向为数字图像处理。 —92 —

启发式优化算法综述【精品文档】(完整版)

启发式优化算法综述 一、启发式算法简介 1、定义 由于传统的优化算法如最速下降法，线性规划，动态规划，分支定界法，单纯形法，共轭梯度法，拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解，使得学者们期望探索一种算法:它不依赖问题的数学性能，如连续可微，非凸等特性; 对初始值要求不严格、不敏感，并能够高效处理髙维数多模态的复杂优化问题，在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求，智能优化算法应运而生。智能优化算法借助自然现象的一些特点，抽象出数学规则来求解优化问题，受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。 为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。因此，采用一种相对好的求解算法，去尽可能逼近最优解，得到一个相对优解，在很多实际情况中也是可以接受的。启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。 启发式算法是和问题求解及搜索相关的，也就是说,启发式算法是为了提高搜索效率才提出的。人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题

时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案，以随机或近似随机方法搜索非线性复杂空间中全局最优解的寻取。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。 2、发展历史 启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，才能取得了巨大的成就。纵观启发式算法的历史发展史： 40年代：由于实际需要，提出了启发式算法（快速有效）。 50年代：逐步繁荣，其中贪婪算法和局部搜索等到人们的关注。 60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规模的问题仍然无能为力（收敛速度慢）。 70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。由此必须引入新的搜索机制和策略。 Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的兴趣。 80年代以后：模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。 最近比较火热的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms），拟人拟物算法，量子算法等。

数据挖掘中的聚类算法综述

收稿日期:2006201204;修返日期:2006203219基金项目:国家自然科学基金资助项目(60473117) 数据挖掘中的聚类算法综述 3 贺　玲,吴玲达,蔡益朝 (国防科学技术大学信息系统与管理学院,湖南长沙410073) 摘　要:聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术。全面总结了数据挖掘中聚类算法的研究现状,分析比较了它们的性能差异和各自存在的优点及问题,并结合多媒体领域的应用需求指出了其今后的发展趋势。 关键词:数据挖掘;聚类;聚类算法 中图法分类号:TP391 文献标识码:A 文章编号:100123695(2007)0120010204 Survey of Clustering A lgorith m s in Data M ining HE L ing,WU L ing 2da,CA I Yi 2chao (College of Infor m ation Syste m &M anage m ent,N ational U niversity of D efense Technology,Changsha Hunan 410073,China ) Abstract:Clustering is an i m portant technique in Data M ining (DM )f or the discovery of data distributi on and latent data pattern .This paper p r ovides a detailed survey of current clustering algorith m s in DM at first,then it makes a comparis on a mong the m,illustrates the merits existing in the m,and identifies the p r oblem s t o be s olved and the ne w directi ons in the fu 2ture according t o the app licati on require ments in multi m edia domain .Key works:Data M ining;Clustering;Clustering A lgorith m 1　引言 随着信息技术和计算机技术的迅猛发展,人们面临着越来越多的文本、图像、视频以及音频数据,为帮助用户从这些大量数据中分析出其间所蕴涵的有价值的知识,数据挖掘(Data M ining,DM )技术应运而生。所谓数据挖掘,就是从大量无序 的数据中发现隐含的、有效的、有价值的、可理解的模式,进而发现有用的知识,并得出时间的趋向和关联,为用户提供问题求解层次的决策支持能力。与此同时,聚类作为数据挖掘的主要方法之一,也越来越引起人们的关注。 本文比较了数据挖掘中现有聚类算法的性能,分析了它们各自的优缺点并指出了其今后的发展趋势。 2　DM 中现有的聚类算法 聚类是一种常见的数据分析工具,其目的是把大量数据点的集合分成若干类,使得每个类中的数据之间最大程度地相似,而不同类中的数据最大程度地不同。在多媒体信息检索及数据挖掘的过程中,聚类处理对于建立高效的数据库索引、实现快速准确的信息检索具有重要的理论和现实意义。 本文以聚类算法所采用的基本思想为依据将它们分为五类,即层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法以及用于高维数据的聚类算法,如图1所示。 聚类 层次聚类算法 聚合聚类:Single 2L ink,Comp lete 2L ink,Average 2L ink 分解聚类 分割聚类算法基于密度的聚类基于网格的聚类 基于图论的聚类 基于平方误差的迭代重分配聚类:概率聚类、最近邻 聚类、K 2medoids 、K 2means 基于约束的聚类算法 机器学习中的聚类算法 人工神经网络方法 基于进化理论的方法:模拟退火、遗传算法用于高维数据的聚类算法 子空间聚类 联合聚类 图1　聚类算法分类示意图 211　层次聚类算法 层次聚类算法通过将数据组织成若干组并形成一个相应的树状图来进行聚类,它又可以分为两类,即自底向上的聚合层次聚类和自顶向下的分解层次聚类。聚合聚类的策略是先将每个对象各自作为一个原子聚类,然后对这些原子聚类逐层进行聚合,直至满足一定的终止条件;后者则与前者相反,它先将所有的对象都看成一个聚类,然后将其不断分解直至满足终止条件。 对于聚合聚类算法来讲,根据度量两个子类的相似度时所依据的距离不同,又可将其分为基于Single 2L ink,Comp lete 2L ink 和Average 2L ink 的聚合聚类。Single 2L ink 在这三者中应用最为广泛,它根据两个聚类中相隔最近的两个点之间的距离来评价这两个类之间的相似程度,而后两者则分别依据两类中数据点之间的最远距离和平均距离来进行相似度评价。 CURE,ROCK 和CHAME LE ON 算法是聚合聚类中最具代 表性的三个方法。 Guha 等人在1998年提出了C URE 算法 [1] 。该方法不用 单个中心或对象来代表一个聚类,而是选择数据空间中固定数目的、具有代表性的一些点共同来代表相应的类,这样就可以