粒子群优化算法求优

单击此处编辑母版标题样式,*,SZUTI DSP Lab,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,粒子群优化算法求优及,LBG,算法的运行,深圳大学信息工程学院,黄彩玲,1,一. 粒子群优化算法求最优解,初始化一群随机粒子（随机解）,每次迭代中，粒子通过跟踪两个极值更新自己：,粒子本身找到的历史最后解（个体极值点,pbest,）,整个种群目前找到的最好解（全局极值点,gbest,）,需要计算粒子的适应值，以判断粒子位置距最优点的距离。,每次迭代中，根据适应度值更新,pbest,和,gbest,。,迭代中止条件：设置最大迭代次数或全局最优位置满足预定最小适应阈值。,2,粒子群优化算法求最优解,D,维空间中，有,N,个粒子；,粒子,i,位置：,x,i,=(x,i1,x,i2,x,id,)，,将,x,i,代入适应函数,f(x,i,),求适应值；,粒子,i,速度：,v,i,=(v,i1,v,i2,v,id,),粒子,i,个体极值点位置：,pbest,i,=(p,i1,p,i2,p,id,),种群的全局极值点位置：,gbest,=(g,1,g,2,g,d,),粒子,i,的第,n,维速度和位置更新公式：,v,in,=w*,v,in,+c1*r1*(,pbest,in,-,x,in,)+c2*r2*(,gbest,n,-,x,in,),x,in,=,x,in,+,v,in,c1,c2,学习因子，,经验值取,c1=c2=2，,调节学习最大步长,r1,r2,两个随机数，,取值范围（0，1），,以增加搜索随机性,w,惯性因子，,非负数,，调节对解空间的搜索范围,3,基本粒子群优化算法流程图,开始,初始化粒子群,计算每个粒子的适应度,根据适应度更新,pbest,、,gbest,，,更新粒子位置速度,结束,no,yes,达到最大迭代次数或,全局最优位置满足最小界限？,4,程序分析,主要数据结构：,种群大小(,PopSize,)空间维数(,NDim,),矢量的边界(,Bound,)最大迭代次数(,MaxIter,),C1、C2、W、R1、R2,各粒子当前适应度值(,fvalue,),各粒子位置(,population,)各粒子速度(,velocity,),各粒子的最佳位置(,pbest,) 全局最佳粒子位置(,gbest,)全局最佳粒子序号(,index,)更新前各粒子适应度值,(,fpbest,),得到相近适应度值的迭代次数,(,samecounter,),临时,适应度值,(,oldbestval,),5,初始化各主要数据（设三维的,Sphere,函数求最优）,flag=0;%,停止程序标志,oldbestval,=0;%,记录旧的适应度值,samecounter,=0; %,记录得到相同适应度值的迭代次数,iteration = 0;%,迭代次数,MaxIter,=100; %,最大迭代次数,PopSize,=20; %,种群大小,c1 = .5; %,学习因子,c2 = .5; %,学习因子,w=0.8;,%,惯性因子,Bound=-100 100;-100 100;-100 100;%,粒子的坐标范围,NDim,= length(Bound);%,空间维数,for i=1:,PopSize,%,定义粒子上下边界,lowerbound,(:,i)=Bound(:,1);,upperbound,(:,i)=Bound(:,2);,end,6,初始化各主要数据,for i=1:,Ndim,%,初始化各粒子初始位置，在有效范围内随机选数,population(i,:)=rand(1,PopSize,)*(Bound(i,2)-Bound(i,1) + Bound(i,1);,end,for i=1:,Ndim,%,初始化各粒子最大速度，使粒子不能越出边界,vmax,(i,:)=(Bound(i,2)-Bound(i,1)/2;,end,velocity =,vmax,.*rand(,NDim,PopSize,);,for i = 1:,PopSize,%,计算各粒子的适应度值,fvalue,(i) = population(1,i)2+population(2,i)2+population(3,i)2;,end,pbest,= population; %,记录各粒子的个体极值点位置,fpbest,=,fvalue,; %,记录最佳适应度值,fbestval,index = min(,fvalue,); %,找出全局极值和相应的序号,7,主程序,while(flag = 0) & (iteration ,MaxIter,)%,寻找最优主程序,iteration = iteration +1;%,迭代次数递增,for i=1:,PopSize,%,更新全局极值点位置,gbest,(:,i) = population(:,index);,end,R1 = rand(,NDim,PopSize,);%,重新设置随机性,R2 = rand(,NDim,PopSize,);,R3 = rand(,NDim,PopSize,);,velocity = w*velocity + c1*R1.*(,pbest,-population) + c2*R2.*(,gbest,-population);,%,更新各粒子速度,population = population + velocity;%,更新各粒子位置,OutFlag,= population=,upperbound,; %,逸出标志,population = population -,OutFlag,.*velocity;%,阻止逸出,8,主程序,for i = 1:,PopSize,%,更新各粒子适应度值,fvalue,(i) = population(1,i)2+population(2,i)2+population(3,i)2;,end,changeColumns,=,fvalue,= 20%,多次迭代的适应度值相近时程序停止,flag=1;,end,Best(iteration) =,fbestval,;%,输出及描出找到的全局极值,plot(Best,ro,);,xlabel,(generation);,ylabel,(f(x);,text(0.5,0.95,Best = , num2str(Best(iteration),Units,normalized);,drawnow,;,end,10,运行结果,(添加三维图等，使之直观点，,达优范围要查,),函数名,表达式,维数,初值范围,理想达优值,运行次数,最大迭代次数,达优次数,平均值,Sphere,，,-100,x100,3,-100,100,0,50,50,46,0.053,Rosenbrock,，,-100,x100,5,-15,30,0,50,200,26,21.9756,六峰驼背函数,，,0,x1,1,(0,1),0.1989,50,50,41,18.8867,11,二.,LBG,算法矢量量化码书设计,LBG,算法以初始码字开始，不断迭代直至收敛，每个迭代过程包括对训练矢量分类和更新码字。,缺点：计算量大，生成的码书无序，码书质量受初始码书影响。,基于两条优化准则：,最近邻域准则。对于给定码书，训练矢量集的最优分类可通过把每个矢量映射为离它最近的码字而得到。,质心条件。对于给定的训练矢量分类，其对应的最优码书中各码字是通过求各胞腔的中心矢量而获得。,12,LBG,矢量量化码书程序流程图,开始,初始化矢量和码书,找最接近码字，矢量重新分类,算失真和信噪比,更新码书,平均失真率达到要求？,结束,输出图像,no,yes,13,程序分析,主要函数：,main_,lbg,():,主程序,cal_ed_ad()：,由矢量和码书得到矢量和码字距离，矢,量索引号，空胞腔数目,LBG()：,由训练矢量、旧码书，旧,ed、,矢量索引号等进,行,LBG,计算，得到新码书，新的矢量索引号、,新的矢量失真、空胞腔数目,14,main_,lbg,(),主要程序分析,V=50; %,迭代次数,epsilon=0.001;%,出错率极限,Line,Col=size(,img,_,lena,); %,读出图像的大小,n=4; %,设定向量维数为,n*n,M=Line*Col/n/n; %,训练矢量大小,tv,=zeros(Line*Col/n/n,n*n);,for i=0:Line/n-1%,分割图像，得到矢量，,tv,(4096*16),for j=0:Col/n-1,tv,(i*Col/n+1+j,:)=,img,_,lena,(i*n+1,j*n+1:j*n+n),img,_,lena,(i*n+2,j*n+1:j*n+n),img,_,lena,(i*n+3,j*n+1:j*n+n),img,_,lena,(i*n+4,j*n+1:j*n+n);,(,令,f=i*n,使程序速度提高),end,end,15,main_,lbg,(),主要程序分析,cbook,_new=,tv,(round(rand(1,256)*M),:);,cbook,_old=,cbook,_new; %,cbook,_old,为更新前码书，,cbook,_new,为更新后码书，初始化,N,L=size(,cbook,_old); % N=256,L=16，,码书大小,img,_new=zeros(M,L); %,训练矢量更新, 4096,x 16,ety,_,cv,=zeros(1,V+1);% No_of_empty_,cv,每次迭代后空胞腔数目，共,V+151,次迭代,ed_old,ad,ind,_,tv,_old,no_,ecv,=cal_ed_ad(,tv,cbook,_old,0); %,由矢量和码书得到矢量和码字距离，矢,%,量索引号，空胞腔数目,D(1)=ad; %,第一次迭代后的平均失真,ety,_,cv,(1)=no_,ecv,; %,第一次迭代后的空胞腔数目,img,_,ini,=zeros(M,L);,for i = 1:M,img,_,ini,(i,:)=,cbook,_old(,ind,_,tv,_old(i),:); %,重新划分后的矢量,End,psnr,=10*log10(GL*GL/mean(mean(,img,_,ini,-,tv,).2) %,第一次迭代后的信噪比,PSNR(1)=,psnr,;,16,main_,lbg,(),主要程序分析,for v = 1:V%,迭代50次,if stop_flag=0,cbook,_new,ind,_,tv,_new,ed_new,img,_new,ad,psnr,no_,ecv,.,= LBG(,tv,cbook,_old,ed_old,ind,_,tv,_old,L,M,N,GL); %,由训练矢量、旧码书，旧,ed、,矢量索引号等进,行,LBG,计算，得到新码书，新的矢量索引号、新的矢量失真、空胞腔数目,no_,ecv,=no_,ecv,%,空胞腔数目,ety,_,cv,(v+1)=no_,ecv,; %,第,v1,次迭代后的空胞腔数目,adr,=abs(D(v+1)-D(v)/D(v)%,平均失真率,if,adr,=epsilon%,如果平均失真率达到要求就停止运算,stop_flag=1;,else,cbook,_old=,cbook,_new;%,否则更新码书,ind,_,tv,_old=,ind,_,tv,_new;%,更新矢量索引号,ed_old=ed_new;%,更新所有训练矢量与所有码字的距离,end,end,end,17,cal_ed_ad(),主要程序分析,for i = 1:M,for j = 1:N,ed(i,j)=norm(,tv,(i,:)-,cb,(j,:); %,计算每个训练矢量与每个码字的距离,end,end,if,cho,=0,y_ed,ind,_,tv,=min(ed,2);%,找每个矢量对应最近码字及相应的索引号,for i = 1:M,ad=ad+(norm(,tv,(i,:)-,cb,(,ind,_,tv,(i),:)2/M; %,计算平均失真率,end,no_,ecv,=0;%,记录空胞腔数目,identified_,cb,=zeros(1,N);%,值为1 是非空, 0 是空胞腔,for i = 1:M,identified_,cb,(,ind,_,tv,(i)=1;%,非空矢量作标记1,end,no_,ecv,=N-sum(identified_,cb,);%,计算空胞腔数目,end,18,LBG(),主要程序分析,for i = 1:M%,产生想得到新的码书用，码书为胞腔内矢量之和,mf_,lbg,(i,ind,_,tv,_old(i)=1;,end,cb,_new=mf_,lbg,*,tv,; %,码书为胞腔内矢量之和,for j = 1:N%,更新码书,no_,tv,=sum(mf_,lbg,(:,j);,if no_,tv,=0,cb,_new(j,:)=,cb,_old(j,:); %,为空胞腔时这个码字不变,else,cb,_new(j,:)=,cb,_new(j,:)/no_,tv,;%,非空时取中间值产生新码字,end,End,cb,_new_r=round(,cb,_new);%,四舍五入取整，新码书,ed_new,ad,ind,_,tv,_new,no_,ecv,=cal_ed_ad(,tv,cb,_new_r,0); %,更新,ed,和,ad,19,LBG(),主要程序分析,for i = 1:M %,由新的码书产生新的训练矢量,img,_new(i,:)=,cb,_new_r(,ind,_,tv,_new(i),:);,end,psnr,=10*log10(GL*GL/mean(mean(,img,_new-,tv,).2);,20,运行结果,Lena,原图,LBG,算法译码图像,21,运行结果,PSNR 28.7641,耗时：59.3350,s,平均失真：1.3829,e+003,22,谢谢！,23,