粒子群优化算法求解旅行商问题ppt课件.ppt
1,粒子群优化算法求解旅行商问题,深圳大学信息工程学院黄彩玲2005年6月16日,2,粒子群优化算法求解旅行商问题,参照：粒子群优化算法求解旅行商问题 黄岚等 吉林大学学报（理学版） 2003年10月,3,五个定义,设n个节点的TSP问题的解序列为s=(ai),I=1n.定义交换子SO(i1,i2)为交换解S中的点ai1和ai2,则S=S+SO(i1,i2)为解S经算子SO(i1,i2)操作后的新解。这里的的含义是执行交换操作。2 一个或多个交换子的有序队列就是交换序，记作SS，SS=(SO1,SO2,SON),SO1,SO2等是交换子，之间的顺序是有意义的。作用于一个TSP问题是意味着所有的交换子依次作用于该解上。3 不同的交换序作用于同一解上可能产生相同的新解，所有有相同效果的交换序的集合称为交换序的等价集。4 若干个交换序可以合并成一个新的交换序，定义为两个交换序的合并算子。5 在交换序等价集中，拥有最少交换子的交换序称为该等价集的基本交换序。,4,算式,Vid=Vid+alpha(Pid-Xid)+beta(Pgd-Xid) （式1）Xid=Xid+Vid （式2） alpha和beta为（0，1）之间的随机数。 (Pid-Xid)和(Pgd-Xid)是基本交换序，表示Xid经过交换得到Pid和Pgd。 alpha(Pid-Xid)表示基本交换序(Pid-Xid)中的所有交换子以概率alpha保留。beta(Pgd-Xid)同理。,5,算法步骤,1初始化粒子群，给每个粒子一个初始解和随机的交换序。2如果满足结束条件，转步骤5。3根据粒子当前位置X计算下一新解X: 1）计算（Pid-Xid）交换序。 2）计算(Pgd-Xid)。 3）计算式1，并将Vid转换为基本交换序。 4）计算式2，更新Xid。 5）如果找到一个更好得解，更新Pid。4如果整个群体找到一个更好的解，更新Pgd，转步骤2。5显示结果。,6,程序分析,主要数据结构：种群大小(PopSize)空间维数(NDim)最大迭代次数(MaxIter) 城市之间的距离(nodeDistance)各粒子当前适应度值(fvalue)更新前各粒子适应度值(fpbest)各粒子位置(population)各粒子速度(velocity) 各粒子的最佳位置(pbest) 全局最佳粒子位置(gbest)全局最佳粒子序号(index)得到相近适应度值的迭代次数(samecounter)计算samecounter的临时变量 (oldbestval),7,主要函数,BeginWith1：使每个路径都从节点1开始排起。（这个命名不好）wholeDistance：计算路径即一个循环后的距离。（改为caculateWholeDistance）ExchangeIndex： 计算（Pid-Xid）等交换序。（大小写要统一,CaculateWholeDistance,ChangeIndex）HoldByAlpha：计算以概率保留交换序。changeIndex：进行交换操作。,8,初始化各主要数据（设求14点的TSP）,flag=0;%停止程序标志oldbestval=0;%记录旧的适应度值samecounter=0; %记录得到相同适应度值的迭代次数iteration = 0;%迭代次数MaxIter =2000; %最大迭代次数PopSize=200; %种群大小alpha=0.8;%概率beta=0.4;w=0.4;NDim = 14;population = ones(NDim,PopSize); %初始化各粒子，即产生路径种群for i=1:PopSize population(:,i)=randperm(NDim);endpopulation=BeginWith1(population); %以1为起点重排每个路径,9,初始化各主要数据,node=16.47 96.10; 16.47 94.44; 20.09 92.54; 22.39 93.37; 25.23 97.24;. 22.00 96.05; 20.47 97.02; 17.20 96.29; 16.30 97.38; 14.05 98.12;. 16.53 97.38; 21.52 95.59; 19.41 97.13; 20.09 94.55;节点坐标nodeDistance=zeros(NDim,NDim); %计算每个城市之间的距离for i=1:NDim for j=1:NDim nodeDistance(i,j)=sqrt(node(i,1)-node(j,1)2+(node(i,2)-node(j,2)2); endEndfor i = 1:PopSize%计算各路径的距离 fvalue(i) = wholeDistance(population(:,i),nodeDistance);Endvelocity =zeros(NDim,PopSize); %产生交换序for i=1:PopSize velocity(:,i)=round(rand(1,NDim)*NDim);end,10,初始化各主要数据,best = population; %记录各粒子的个体极值点位置,即个体找到的最短路径fpbest = fvalue; %记录最佳适应度值,即个体找到的最短路径的长度fbestval,index = min(fvalue); % 找出全局极值和相应的序号,11,主程序,while(flag = 0) ,12,主程序,for i = 1:PopSize% 更新各路径距离 fvalue(i) = wholeDistance(population(:,i),nodeDistance); end changeColumns = fvalue fpbest;% 更新后的距离优于更新前的，记录序号 pbest(:, find(changeColumns) = population(:, find(changeColumns); % 更新个体最佳路径 fpbest = fpbest.*( changeColumns) + fvalue.*changeColumns; %更新个体最佳路径距离 fbestval, index = min(fvalue); %更新全局最佳路径,记录相应的序号 if fbestval=oldbestval%比较更新前和更新后的适应度值; samecounter=samecounter+1;%相等时记录加一; else oldbestval=fbestval; %不相等时更新适应度值，并记录清零; samecounter=0; end,13,主程序,if samecounter = 20%多次迭代的适应度值相近时程序停止 flag=1; end Best(iteration) =fbestval;% 输出及描出找到的全局极值end,14,BeginWith1()函数,function population=BeginWith1(population) x y=size(population); NO1,index=min(population,2); %找最小值1 for i=1:y pop=population(:,i); temp1=pop(1: index(i)-1); temp2=pop(index(i): x); population(:,i)=temp2 temp1; end,15,changeIndex（）函数,function population=changeIndex(population,velocity)x y=size(population);for i=1:y a=velocity(:,i); %取出其中一组交换序 pop=population(:,i); %取出对应的粒子 for j=1:x %取出其中一个交换算子作交换 if a(j)=0 pop1=pop(j); %temp; %temp(a(j); pop(j)=pop(a(j); pop(a(j)=pop1; end end population(:,i)=pop; end,16,ExchangeIndex （）函数,function pgid_xid=ExchangeIndex(population,pgbest);x y=size(population);pgid_xid=zeros(x,y);for i=1:y pop=pgbest(:,i); %从pgbest取出一个顺序 pop1=population(:,i); %从粒子群中取出对应的顺序 for j=1:x %从pgbest的顺序中取出一个序号 NoFrompgbest=pop(j); for k=1:x %从对应的粒子顺序中取出一个序号 NoFromPopulation=pop1(k); if (NoFrompgbest=NoFromPopulation) end end endend,17,HoldByAlpha （）函数,function velocity=HoldByAlpha(velocity,w)x,y=size(velocity);for i=1:x for j=1:y if randw velocity(i,j)=0; end endend,18,wholeDistance （）函数,function dist=wholeDistance(path,nodeDistance)L=length(path); %path为一个循环的节点顺序dist=0;for i=1:L-1 dist=dist+nodeDistance(path(i),path(i+1);enddist=dist+nodeDistance(path(1),path(L); %加上首尾节点的距离,19,运行结果,Err=(ave-opt)/opt,20,运行结果,运行五十次，每次得的最短距离如图所示,21,改进微粒群优化算法求解旅行商问题,参照：改进微粒群优化算法求解旅行商问题肖健梅等 计算机工程与应用 2004 .35该论文在上述论文基础上作出改进，为了提高搜索效率，把速度位置算式改为：Xid1=Xid+wVidXid2=Xid1+alpha*rand()(Pid-Xid1)Xid3=Xid2+Beta*rand()(Pgd-Xid2),22,程序修改,去掉上述程序中的下列语句： pid_xid=ExchangeIndex(population,pbest); pid_xid=HoldByAlpha(pid_xid,alpha); %保留alpha的交换序 pgd_xid=ExchangeIndex(population,gbest); pgd_xid=HoldByAlpha(pgd_xid,beta); velocity=HoldByAlpha(velocity,w); population = changeIndex(population,velocity); population = changeIndex(population,pid_xid); population = changeIndex(population,pgd_xid); 改为以下语句： velocity=HoldByAlpha(velocity,w); population=changeIndex(population,velocity); velocity=ExchangeIndex(population,pbest); velocity=HoldByAlpha(velocity,alpha*rand(1); population=changeIndex(population,velocity); velocity=ExchangeIndex(population,gbest); velocity=HoldByAlpha(velocity,beta*rand(1); population=changeIndex(population,velocity);,23,运行结果,Err=(ave-opt)/opt,24,运行结果,运行五十次，每次得的最短距离如图所示,25,谢谢！,
