粒子群算法聚类设计

主讲：周润景教授单位：电子信息工程学院粒子群算法聚类设计目录算法简介经典的粒子群算法的运算过程两种基本的进化模型改进的粒子群优化算法粒子群算法应用到模式分类结论一.算法简介MacroDorigo粒子群优化算法（ParticleSwarmOptimization，PSO）是由美国的Kennedy和Eberhar在1995年提出的一种新的进化算法，该算法源于对鸟群体觅食行为的研究。粒子群优化算法是近些年来发展起来的一种仿生优化算法，因其具有的多种优点受到学术界广泛关注和研究，目前已经被广泛应用于函数优化、神经网络、模式识别等科学和工程领域。一.算法简介粒子群算法的基本思想是模拟鸟类群体行为，并利用了生物学家的生物群体模型，因为鸟类的生活使用了简单的规则：（1）飞离最近的个体；（2）飞向目标；（3）飞向群体的中心；来确定自己的飞行方向和飞行速度，并且成功的寻找到栖息地。二.经典的粒子群算法的运算过程经典粒子群算法和其他的进化算法相似，采用“群体”与“进化”的概念，根据个体即微粒（particle）的适应度大小进行操作。所不同的是，微粒群算法将每个个体看作是在N维搜索空间中的一个无重量无体积的微粒，并在搜索空间中以一定的速度飞行。该飞行速度是根据个体的飞行经验和群体的飞行经验来进行动态地调整。二.经典的粒子群算法的运算过程Kennedy和Eberhart最早提出的PSO算法的进化方程如下：下标“i”表示第i个微粒，下标“j”表示的是微粒i的第j维分量，t表示第t代，学习因子和为非负常数，用来调节微粒向本身最好位置飞行的步长，用来调节微粒向群体最好位置飞行的步长。)1())()(())()(()()1(2211txtprctxtprcttijgjijijijij)2()1()()1(tvtxtxijijij1c2c1c2c三.两种基本的进化模型两种粒子群算法模型:全局模式(globalversionPSO)和局部模型（localversionPSO)。模型（全局最好模型）模型以牺牲算法的鲁棒性为代价提高算法的收敛速度，基本PSO算法就是典型的该模型的体现。在该模型中，整个算法以该微粒（全局最好的微粒）为吸引子，将所有微粒拉向它，使所有的微粒最终收敛于该位置。如果在进化过程中，该全局最优解得不到更新，则微粒群将出现类似于遗传算法早熟的现象。bestGbestG三.两种基本的进化模型模型（局部最好模型）为了防止模型可能出现早熟现象，模型采用多个吸引子代替全局模型中的单一吸引子。首先将为粒子群分解为若干个子群，在每个粒子群中保留其局部最好微粒,称为局部最好的位置或邻域最好位置。实验表明,局部最好模型的PSO比全局最好模型的收敛慢,但不容易陷入局部最优解。bestLbestGbestL四.改进的粒子群优化算法1.基本粒子群算法的缺陷粒子群算法是一种局部搜索效率高的搜索算法，收敛快，特别是在算法的早期，但也存在着精度较低、易发散等缺点。若加速系数、最大速度等参数太大，粒子群可能错过最优解，算法不能收敛；在收敛的情况下，由于所有的粒子都同时向最优解的方向飞去，所以粒子趋向同一化(失去了多样性)，这样就使算法容易陷入局部最优解，即算法收敛到一定精度时，无法继续优化。四.改进的粒子群优化算法2.粒子群优化算法原理粒子群优化算法具有进化计算和群智能的特点。与其他进化算法相类似，粒子群算法也是通过个体间的协作与竞争，实现复杂空间中最优解的搜索。粒子群算法可描述为：设粒子群在一个n维空间中搜索，由m个粒子组成种群，其中的每个粒子所处的位置都表示问题的一个解。粒子通过不断调整自己的位置来搜索新解。每个粒子都能记住自己搜索到的最好解，记做，以及整个粒子群经历过的最好的位置，即目前搜索到的最优解，记做。此外每个粒子都有一个速度，记作，当两个最优解都找到后，每个粒子根据式（3)来更新自己的速度。mZZZZ,...,,21imiiiZZZZ,...,,21iZidpgdpiniivvv,...,1)3())()(())()(()()1(2211tztprtztprtwtidgdidididid)4()1()()1(tvtztzididid四.改进的粒子群优化算法式中，表示第个粒子在t+1次迭代中第d维上的速度，w为惯性权重，、为加速常数，、为0-1之间的随机数。此外，为使粒子速度不致过大，可以设置速度上限，当式（3）中时，；时，从式（3）和式（4）可以看出，粒子的移动方向由三部分决定：自己原有的速度、与自己最佳经历的距离、与群体最佳经历的距离并分别由权重系数w，，决定其重要性。)1(tid121r2rmaxmax)1(tidmax)1(tidmax)1(tidmax)1(tid)(tid)(tzpidid)(tzpidgd12四.改进的粒子群优化算法3.参数设置PSO算法中需要调节的参数主要包括：（1）学习因子、学习因子（也称加速度系数）和分别调节粒子向全局最优粒子和个体最优粒子方向飞行的最大步长。若太小，则粒子可能远离目标区域；若太大则可能导致粒子忽然向目标区域飞去或飞过目标区域。合适的和可以加快收敛且不易陷入局部最优。121221四.改进的粒子群优化算法（2）种群规模NPSO算法种群规模较小，一般令N=20～40。其实对于大部分问题10个粒子就能取得很好结果，但对于较难或者特定类别的问题，粒子数可能取到100或200。（3）适应度函数：其中:w是0，1矩阵，当x属于该类时元素为0，否则为1。2111)(kjnpjpipsiijCXwF四.改进的粒子群优化算法（4）惯性权重系数w惯性权重系数w用来控制前面的速度对当前速度的影响，较大的w可以加强PSO的全局搜索能力，而较小的能加强局部搜索能力。目前普遍采用将w设置为从0.9到0.1线性下降的方法，这种方法可使得PSO在开始时探索较大的区域，较快地定位最优解的大致位置，随着w逐渐减小，粒子速度减慢，开始精细地局部搜索。maxminmaxmaxtwwtww四.改进的粒子群优化算法4.粒子群优化算法的基本流程初始化粒子群计算每个粒子的适应度值更新粒子的个体最优位置和全局最优位置根据式（10-3）和式（10-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;ticdata=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:Nclmat(i,:)=randperm(S);%随机取整数endclmat(clmatK)=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:Mfori=1:Nww=zeros(S,K);%%产生零矩阵forii=1:Sww(ii,clmat(i,ii))=1;%加权矩阵，元素非0即1endccc=[];tmp=0;forj=1:K五.粒子群算法应用到模式分类sumcs=sum(ww(:,j)*ones(1,D).*data);countcs=sum(ww(:,j));ifcountcs==0cen(j,:)=zeros(1,D);elsecen(j,:)=sumcs/countcs;%求类别中心endccc=[ccc,cen(j,:)];%串联聚类中心aa=find(ww(:,j)==1);iflength(aa)~=0fork=1:length(aa)tmp=tmp+(sum((data(aa(k),:)-cen(j,:)).^2));%%适应度计算endendendx(i,:)=ccc;fitt2(i)=tmp;%%适应度值Fitnessvalueend五.粒子群算法应用到模式分类%更新群体和个体最优解fori=1:Niffitt2(i)fitt(i)fitt(i)=fitt2(i);y(i,:)=x(i,:);%个体最优iffitt2(i)fgpg=x(i,:);%群体最优fg=fitt2(i);%群体最优适应度fljg=clmat(i,:);%当前最优聚类endendendbfit(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:Kcen(k,:)=x((k-1)*D+1:k*D);%拆分粒子位置，获得K个中心end%重新归类forj=1:Stmp1=zeros(1,K);fork=1:Ktmp1(k)=sum((data(j,:)-cen(k,:)).^2);%每个样本关于各类的距离end[tmp2clmat(i,j)]=min(tmp1);%最近距离归类endendend%------循环结束------------M%迭代次数fljg%最优聚类输出fg%最优适应度输出五.粒子群算法应用到模式分类figure(1)plot(bfit);%绘制最优适应度轨迹xlabel('种群迭代次数');ylabel('适应度');title('适应度曲线');cen%聚类中心toc五.粒子群算法应用到模式分类仿真适应度曲线如图所示：PSO算法仿真适应度准确值为：适应度=5.07E+06五.粒子群算法应用到模式分类对预测样本值的仿真输出结果如下：Fl