模式识别与人工智能（基于MATLAB）（第2版）课件 10 粒子群算法聚类设计

粒子群算法聚类设计目录

算法简介经典的粒子群算法的运算过程两种基本的进化模型改进的粒子群优化算法粒子群算法应用到模式分类结论

一.算法简介MacroDorigo

粒子群优化算法（ParticleSwarmOptimization，PSO）是由美国的JamesKennedy和RussellC.Eberhart在1995年提出的一种新的进化算法，该算法源于对鸟群体觅食行为的研究。粒子群优化算法是近些年来发展起来的一种仿生优化算法，因其具有的多种优点受到学术界广泛关注和研究，目前已经被广泛应用于函数优化、神经网络、模式识别等科学和工程领域。一.算法简介粒子群算法的基本思想是模拟鸟类群体行为，并利用了生物学家的生物群体模型，因为鸟类的生活使用了简单的规则：（1）飞离最近的个体；（2）飞向目标；（3）飞向群体的中心；来确定自己的飞行方向和飞行速度，并且成功的寻找到栖息地。一.算法简介在PSO中，把一个优化问题看作是在空中觅食的鸟那么“食物”就是优化问题的最优解，而在空中飞的每一只觅食的“鸟”就是PSO算法中在解空间中进行搜索的一个“粒子”(Particle)。“群”(Swarm)的概念来自于人工生命，满足人工生命的基本原则。因此PSO算法也可看作是对简化了的社会模型的模拟，这其中最重要的是社会群体中的息共享机制，这是推动算法的主要机制。一.算法简介鱼群/鸟群行为二.经典的粒子群算法的运算过程经典粒子群算法和其他的进化算法相似，采用“群体”与“进化”的概念，根据个体即微粒（particle）的适应度大小进行操作。所不同的是，微粒群算法将每个个体看作是在N维搜索空间中的一个无重量无体积的微粒，并在搜索空间中以一定的速度飞行。该飞行速度是根据个体的飞行经验和群体的飞行经验来进行动态地调整。二.经典的粒子群算法的运算过程Kennedy和Eberhart最早提出的PSO算法的进化方程如下：下标“i”表示第i个微粒，下标“j”表示的是微粒i的第j维分量，t表示第t代，学习因子和为非负常数，用来调节微粒向本身最好位置飞行的步长，用来调节微粒向群体最好位置飞行的步长。二.经典的粒子群算法的运算过程经典微粒群算法的算法流程如下：步骤一：依照如下步骤初始化，对微粒群的随机位置和速度进行初始设定。①设定群体规模，即粒子数为N；②对任意i,j，随机产生,；③对任意i初始化局部最优位置为：；④初始化全局最优位置；二.经典的粒子群算法的运算过程步骤二：根据目标函数，计算每个微粒的适应度值。步骤三：对于每个微粒，将其适应度值与其本身所经历过的最好位置的适应度值进行比较，如更好，则将现在的位置作为新的。步骤四：对每个微粒，将其经过的最好位置的适应度值与群体的最好位置的适应度值比较，如果更好，则将的位置作为新的。步骤五：对微粒的速度和位置进行更替。如未达到结束条件,则返回步骤二。三.两种基本的进化模型两种粒子群算法模型:全局模式(globalversionPSO)和局部模型（localversionPSO)。

模型（全局最好模型）

模型以牺牲算法的鲁棒性为代价提高算法的收敛速度，基本PSO算法就是典型的该模型的体现。在该模型中，整个算法以该微粒（全局最好的微粒）为吸引子，将所有微粒拉向它，使所有的微粒最终收敛于该位置。如果在进化过程中，该全局最优解得不到更新，则微粒群将出现类似于遗传算法早熟的现象。三.两种基本的进化模型模型（局部最好模型）为了防止模型可能出现早熟现象，模型采用多个吸引子代替全局模型中的单一吸引子。首先将为粒子群分解为若干个子群，在每个粒子群中保留其局部最好微粒,称为局部最好的位置或邻域最好位置。实验表明,局部最好模型的PSO比全局最好模型的收敛慢,但不容易陷入局部最优解。四.改进的粒子群优化算法1.基本粒子群算法的缺陷粒子群算法是一种局部搜索效率高的搜索算法，收敛快，特别是在算法的早期，但也存在着精度较低、易发散等缺点。若加速系数、最大速度等参数太大，粒子群可能错过最优解，算法不能收敛；在收敛的情况下，由于所有的粒子都同时向最优解的方向飞去，所以粒子趋向同一化(失去了多样性)，这样就使算法容易陷入局部最优解，即算法收敛到一定精度时，无法继续优化。四.改进的粒子群优化算法2.粒子群优化算法原理粒子群优化算法具有进化计算和群智能的特点。与其他进化算法相类似，粒子群算法也是通过个体间的协作与竞争，实现复杂空间中最优解的搜索。粒子群算法可描述为：设粒子群在一个n维空间中搜索，由m个粒子组成种群

，其中的每个粒子所处的位置

都表示问题的一个解。粒子通过不断调整自己的位置

来搜索新解。每个粒子都能记住自己搜索到的最好解，记做

，以及整个粒子群经历过的最好的位置，即目前搜索到的最优解，记做

。此外每个粒子都有一个速度，记作

，当两个最优解都找到后，每个粒子根据式（3)来更新自己的速度。四.改进的粒子群优化算法式中，表示第个粒子在t+1次迭代中第d维上的速度，w为惯性权重，、为加速常数，、为0-1之间的随机数。此外，为使粒子速度不致过大，可以设置速度上限，当式（3）中时，；

时，从式（3）和式（4）可以看出，粒子的移动方向由三部分决定：自己原有的速度、与自己最佳经历的距离、与群体最佳经历的距离并分别由权重系数w

，，决定其重要性。四.改进的粒子群优化算法3.参数设置PSO算法中需要调节的参数主要包括：（1）学习因子、学习因子（也称加速度系数）和分别调节粒子向全局最优粒子和个体最优粒子方向飞行的最大步长。若太小，则粒子可能远离目标区域；若太大则可能导致粒子忽然向目标区域飞去或飞过目标区域。合适的和可以加快收敛且不易陷入局部最优。

四.改进的粒子群优化算法（2）种群规模NPSO算法种群规模较小，一般令N=20～40。其实对于大部分问题10个粒子就能取得很好结果，但对于较难或者特定类别的问题，粒子数可能取到100或200。（3）适应度函数：其中:w是0，1矩阵，当x属于该类时元素为0，否则为1。四.改进的粒子群优化算法（4）惯性权重系数w惯性权重系数w用来控制前面的速度对当前速度的影响，较大的w可以加强PSO的全局搜索能力，而较小的能加强局部搜索能力。目前普遍采用将w设置为从0.9到0.1线性下降的方法，这种方法可使得PSO在开始时探索较大的区域，较快地定位最优解的大致位置，随着w逐渐减小，粒子速度减慢，开始精细地局部搜索。四.改进的粒子群优化算法4.粒子群优化算法的基本流程五.粒子群算法应用到模式分类在本例对酒瓶颜色进行分类，希望将三元色数据按照颜色数据所表征的特点，将数据按照各自所属的类别归类。由于粒子群优化算法是迭代求取最优值，所以事先无需训练数据，故取后30组数据确定类别。重要程序代码介绍：1.设定参数PSO优化算法需要设定粒子的学习因子（速度更新参数）、最大迭代次数以及惯性权重初始和终止值及聚类类数。参数设定如下：c1=1.6;c2=1.6;%设定学习因子值（速度更新参数）wmax=0.9;wmin=0.4;%设定惯性权重初始及终止值M=1800;%最大迭代数K=4;%类别数五.粒子群算法应用到模式分类2.初始化fitt=inf*ones(1,N);%初始化个体最优适应度fg=inf;%初始化群体最优适应度fljg=clmat(1,:);%当前最优分类v=rand(N,K*D);%初始速度x=zeros(N,K*D);%初始化粒子群位置y=x;%初始化个体最优解pg=x(1,:);%初始化群体最优解cen=zeros(K,D);%类别中心定维fitt2=fitt;%粒子适应度定维五.粒子群算法应用到模式分类完整程序代码：clc;clearall;formatlong;ticdata=importdata(‘simulate_data.dat');%--------参数设定-----------N=70;%粒子数c1=1.6;c2=1.6;%设定学习因子值（速度更新参数）wmax=0.9;wmin=0.4;%设定惯性权重初始及终止值M=1600;%最大迭代数K=4;%类别数[SD]=size(data);%样本数和特征维数%--------初始化----------------fori=1:Nclmat(i,:)=randperm(S);%随机取整数endclmat(clmat>K)=fix(rand*K+1);%取整函数五.粒子群算法应用到模式分类fitt=inf*ones(1,N);%初始化个体最优适应度fg=inf;%初始化群体最优适应度fljg=clmat(1,:);%当前最优分类v=rand(N,K*D);%初始速度x=zeros(N,K*D);%初始化粒子群位置y=x;%初始化个体最优解pg=x(1,:);%初始化群体最优解cen=zeros(K,D);%类别中心定维fitt2=fitt;%粒子适应度定维%------循环优化开始------------fort=1:Mfori=1:Nww=zeros(S,K);%%产生零矩阵

forii=1:Sww(ii,clmat(i,ii))=1;%加权矩阵，元素非0即1endccc=[];tmp=0;forj=1:K五.粒子群算法应用到模式分类sumcs=sum(ww(:,j)*ones(1,D).*data);countcs=sum(ww(:,j));ifcountcs==0cen(j,:)=zeros(1,D);elsecen(j,:)=sumcs/countcs;%求类别中心

endccc=[ccc,cen(j,:)];%串联聚类中心

aa=find(ww(:,j)==1);iflength(aa)~=0fork=1:length(aa)tmp=tmp+(sum((data(aa(k),:)-cen(j,:)).^2));%%适应度计算

endendendx(i,:)=ccc;fitt2(i)=tmp;%%适应度值Fitnessvalueend五.粒子群算法应用到模式分类%更新群体和个体最优解fori=1:Niffitt2(i)<fitt(i)fitt(i)=fitt2(i);y(i,:)=x(i,:);%个体最优

iffitt2(i)<fgpg=x(i,:);%群体最优

fg=fitt2(i);%群体最优适应度

fljg=clmat(i,:);%当前最优聚类

endendendbfit(t)=fg;%最优适应度记录w=wmax-t*(wmax-wmin)/M;%更新权重,线性递减权重法的粒子群算法

fori=1:N%更新粒子速度和位置

v(i,:)=w*v(i,:)+c1*rand(1,K*D).*(y(i,:)-x(i,:))+c2*rand(1,K*D).*(pg-x(i,:));x(i,:)=x(i,:)+v(i,:);五.粒子群算法应用到模式分类fork=1:Kcen(k,:)=x((k-1)*D+1:k*D);%拆分粒子位置，获得K个中心

end%重新归类

forj=1:Stmp1=zeros(1,K);fork=1:Ktmp1(k)=sum((data(j,:)-cen(k,:)).^2);%每个样本关于各类的距离

end[tmp2clmat(i,j)]=min(tmp1);%最近距离归类

endendend%------循环结束------------M%迭代次数fljg%最优聚类输出fg%最优适应度输出五.粒子群算法应用到模式分类figure(1)plot(bfit);%绘制最优适应度轨迹xlabel('种群迭代次数');ylabel('适应度');title('适应度曲线');cen%聚类中心toc五.粒子群算法应用到模式分类仿真适应度曲线如图所示：PSO算法仿真适应度准确值为：适应度=5.07E+06五.粒子群算法应用到模式分类对预测样本值的仿真输出结果如下：Fljg（最优聚类输出）=1至16列

224243324222134317至30列

42433221141222Fg（最优适应度值）=5.0744271694490