模式识别与智能计算-MATLAB技术实现（第5版）-课件 第十二章+粒子群算法聚类分析

模式识别与智能计算

杨淑莹天津理工大学计算机科学与工程学院第十二章粒子群算法聚类分析12.1粒子群算法的基本原理12.2全局模式和局部模式12.3粒子群算法的实现方法与步骤

粒子群算法的概述粒子群算法(ParticleSwarmOptimization,PS)是一种有效的全局寻优算法，最早由美国的Kennedy和Cberhart于1995年提出。它是基于群体智能理论的优化算法，通过群休中粒子间的合作与竞争产生的群体智能指导优化搜索。与传统的进化算法相比，粒子群算法保留了基于种样的全局搜索策略，但是其采用的速度一位移模型，操作简单，避免了复杂的遗传操作，它特有的记忆使其可以动态跟踪当前的搜索情况调整其搜索策略。由于每代种群中的解具有“自我”学习提高和向“他人”学习的双重优点，从而能在较少的迭代次数内找到最优解。目前已广泛应用于函数优化、数据挖掘、神经网络训练等应用领域。12.1粒子群算法的基本原理粒子群算法的思想源于对鸟群觅食行为的研究，鸟群通过集体的信息共享使群体找到最优的目的地。设想这样一个场景：鸟群在森林中随机搜索食物，它们想要找到食物量最多的位置。但是所有的鸟都不知道食物具体在哪个位置，只能感受到食物大概在哪个方向。每只鸟沿着自己判定的方向进行搜索，并在搜索的过程中记录自己曾经找到过食物且量最多的位置，同时所有的鸟都共享自己每一次发现食物的位置以及食物的量，这样鸟群就知道当前在哪个位置食物的量最多。在搜索的过程中每只鸟都会根据自己记忆中食物量最多的位置和当前鸟群记录的食物量最多的位置调整自己接下来搜索的方向。鸟群经过一段时间的搜索后就可以找到森林中哪个位置的食物量最多（全局最优解）。12.1.1鸟类觅食鸟群觅食粒子群算法鸟粒子森林求解空间食物的量目标函数值每只鸟所处的位置空间中的一个解（粒子位置）食物量最多的位置全局最优解12.1.2初始粒子群代码实现%生产初始粒子群

fori=1:particleNum

forj=1:patternNum

m_pattern(j).category=ptDitrib(i,j);

end

forj=1:centerNum

m_center(j)=CalCenter(m_center(j),m_pattern,patternNum);

end

Particle(i).location=m_center;

end

%初始化参数

w_max=1;

w_min=0;

h1=2;

h2=2;

foriter=1:iterNum在生成初始粒子群部分，首先生成一组包含多个粒子的粒子群，其中每个粒子包含多个特征，即每个特征表示一个样本的类别。ptDitrib是一个1xparticleNum的矩阵，表示每个粒子的初始类别分布，可以根据实际问题进行设置。然后根据每个粒子的类别分布，计算每个类别的中心点m_center，用于初始化粒子的位置。在初始化参数部分，设置了惯性因子w的最大值和最小值，以及加速因子h1和h2的值，用于控制粒子的速度和位置更新。iterNum表示算法的迭代次数，用于控制算法的收敛性。12.1.3粒子群算法的描述

12.1.4加权求和示意图粒子下一步迭代的移动方向=惯性方向+个体最优方向+群体最优方向12.1.5粒子移动方向的决定因素12.1.6速度和位置更新代码实现%更新粒子速度，位置

fori=1:particleNum

forj=1:centerNum

Particle(i).velocity(j).feature=

w*Particle(i).velocity(j).feature+h1*rand(Nwidth,Nwidth).*

(P_id(i).location(j).feature-Particle(i).location(j).feature)

+h2*rand(Nwidth,Nwidth).*(P_gd.location(j).feature

-Particle(i).location(j).feature);

Particle(i).location(j).feature=Particle(i).location(j).feature

+Particle(i).velocity(j).feature;

end

end

12.1.7粒子群算法的基本流程12.2全局模式与局部模式Kennedy等在对鸟群觅食的观察过程巾发现，每只鸟并不总是能看到鸟群中其他所有鸟的位置和运动方向，而往往只是看到相邻的鸟的位置和运动方向。因此提出了两种粒子群算法模式：全局模式(globalversionPS)和局部模式(localversionPSO）.12.2.1全局模式与局部模式对比

速度更新公式：全局模式具有较快的收敛速度，但是鲁棒性较差。相反，局部模式具有较高的鲁棒性而收敛速度相对较慢，因此在运用粒子群算法解决不同的优化问题时，应针对具体情况采用相应的模式。

12.2.2参数选取12.2.3参数选取规则

①粒子群算法和其他进化算法都基于“种群”概念，用于表示一组解空间中的个体集合。它们都随机初始化种群，使用适应度值来评价个体，而且都根据适应度值来进行一定的随机搜索，并且不能保证一定能找到最优解。②种群进化过程中通过子代与父代竞争，若子代具有更好的适应度值，则子代将替换父代，因此都具有一定的选择机制。③算法都具有并行性，即搜索过程是从一个解集合开始的，而不是从单个个体开始的，不容易陷入局部极小值。并且这种并行性易于在并行计算机上实现，提高算法的性能和效率。12.2.4粒子群算法与其他进化算法的相同点①粒子群算法在进化过程中同时记忆位置和速度信息，而遗传算法和蚁群算法通常只记忆位置信息。②粒子群算法的信息通信机制与其他进化算法不同。遗传算法中染色体互相通过交叉等操作进行通信，蚁群算法中每只蚂蚁以蚁群全体构成的信息素轨迹作为通信机制，因此整个种群比较均匀地向最优区域移动。在全局模式的粒子群算法中，只有全局最优粒子提供信息给其他的粒子，整个搜索更新过程是跟随当前最优解的过程，因此所有的粒子很可能更快地收敛于最优解。12.2.5粒子群算法与其他进化算法的不同点12.3粒子群算法的实现方法与步骤

理论基础：是第j个聚类的中心，为样品到对应聚类中心距离，聚类准则函数j即为各类样品到对应聚类中心距离的总和。12.3.1理论基础

12.3.2粒子群算法求解聚类问题在粒子群算法求解聚类问题中，每个粒子作为一个可行解组成粒子群（即解集）。根据解的含义不同，通常可以分为两种方法：一种是以聚类结果为解；一种是以聚类中心集合为解。采用的是基于聚类中心集合作为粒子对应解，也就是每个粒子的位置是由M个聚类中心组成，M为已知的聚类数目。一个具有M个聚类中心，样品向量维数为n的聚类问题中，每个粒子i由三部分组成，即粒子位置、速度和适应度值。粒子结构i表示为：12.3.3粒子群算法求解聚类问题粒子的位置编码结构表示为：每个粒子还有一个速度：粒子适应度值Particle.fitness为一实数，表示粒子的适应度，可以采用以下方法计算其适应度。①按照最近邻法式确定该粒子的聚类划分。②根据聚类划分，重新计算聚类中心，按照计算总的类内离散度J。③粒子的适应度可表示为式：J为总的类内离散度和，k为常数，根据具体情况而定。即粒子所代表的聚类划分的总类间离散度越小，粒子的适应度越大。12.3.4编码格式粒子编码

12.3.5粒子群算法求解聚类问题

根据左边二式，可以得到粒子i的速度和位置更新公式：12.3.6实现步骤12.3.7ω的取值

12.3.8粒子适应度代码实现%计算粒子适应度

fori=1:particleNum

temp=0;

forj=1:patternNum

temp=temp+GetDistance(m_pattern(j),Particle(i).location(ptDitrib(i,j)),disType);

end

if(temp==0)%最优解，直接退出

iter=iterNum+1;

break;

end

Particle(i).fitness=1/temp;

end

if(iter>iterNum)

break;

end

w=w_max-iter*(w_max-w_min)/iterNum;%更新权重系数

fori=1:particleNum%更新P_id,P_gd

if(Particle(i).fitness>P_id(i).fitness)

P_id(i).fitness=Particle(i).fitness;

P_id(i).location=Particle(i).location;

P_id(i).velocity=Particle(i).velocity;

if(Particle(i).fitness>P_gd(i).fitness)

P_gd(i).fitness=Particle(i).fitness;

P_gd(i).location=Particle(i).location;

P_gd(i).velocity=Particle(i).velocity;

P_gd.string=ptDitrib(i,:);

end

end

end首先遍历每个粒子，并计算该粒子的适应度。适应度的计算是通过计算每个样本点到该粒子所属的类别中心点的距离来实现的。如果该粒子的适应度达到最优解，则直接退出迭代过程。在更新部分，首先根据当前迭代次数更新惯性因子w的值。然后，使用循环语句遍历每个粒子，根据当前适应度更新个体最优解P_id和全局最优解P_gd，并记录最优解的字符串ptDitrib。具体来说，如果该粒子的适应度大于个体最优解的适应度，则更新个体最优解；如果该粒子的适应度大于全局最优解的适应度，则更新全局最优解。最后，将最优解的字符串ptDitrib保存到P_gd中。这样，随着粒子群迭代的进行，不断计算粒子的适应度并更新最优解，最终找到最佳解。12.3.9聚类中心代码实现%最近邻聚类

fori=1:particleNum

forj=1:patternNum

min=inf;

fork=1:centerNum

tempDis=GetDistance(m_pattern(j),Particle(i).location(k),disType);

if(tempDis<min)

min=tempDis;

m_pattern(j).category=k;

ptDitrib(i,j)=k;

end

end

end

%重新计算聚类中心

forj=1:centerNum

Particle(i).location(j)=CalCenter(Particle(i).location(j),m_pattern,patternNum);

end

end

fori=1:patternNum

m_pattern(i).category=P_gd.string(1,i);

end根据当前粒子的位置信息重新对样本进行聚类，并计算新的聚类中心。在最近邻聚类部分，首先遍历每个粒子和每个样本点。对于每个样本点，遍历当前粒子的每个聚类