粒子群优化算法求解旅行商问题ppt课件.ppt

《粒子群优化算法求解旅行商问题ppt课件.ppt》由会员分享，可在线阅读，更多相关《粒子群优化算法求解旅行商问题ppt课件.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1粒子群优化算法求解粒子群优化算法求解旅行商问题旅行商问题深圳大学信息工程学院黄彩玲2005年6月16日SZUTI DSP Lab2粒子群优化算法求解旅行商问题粒子群优化算法求解旅行商问题 参照：粒子群优化算法求解旅行商问题 黄岚等 吉林大学学报（理学版） 2003年10月SZUTI DSP Lab3五个定义五个定义 1设n个节点的TSP问题的解序列为s=(ai),I=1n.定义交换子SO(i1,i2)为交换解S中的点ai1和ai2,则S=S+SO(i1,i2)为解S经算子SO(i1,i2)操作后的新解。这里的的含义是执行交换操作。2 一个或多个交换子的有序队列就是交换序，记作SS，SS=(S

2、O1,SO2,SON),SO1,SO2等是交换子，之间的顺序是有意义的。作用于一个TSP问题是意味着所有的交换子依次作用于该解上。3 不同的交换序作用于同一解上可能产生相同的新解，所有有相同效果的交换序的集合称为交换序的等价集。4 若干个交换序可以合并成一个新的交换序，定义为两个交换序的合并算子。5 在交换序等价集中，拥有最少交换子的交换序称为该等价集的基本交换序。SZUTI DSP Lab4算式算式Vid=Vid+alpha(Pid-Xid)+beta(Pgd-Xid) （式1）Xid=Xid+Vid （式2） alpha和beta为（0，1）之间的随机数。 (Pid-Xid)和(Pgd-X

3、id)是基本交换序，表示Xid经过交换得到Pid和Pgd。 alpha(Pid-Xid)表示基本交换序(Pid-Xid)中的所有交换子以概率alpha保留。beta(Pgd-Xid)同理。 SZUTI DSP Lab5算法步骤算法步骤1初始化粒子群，给每个粒子一个初始解和随机的交换序。2如果满足结束条件，转步骤5。3根据粒子当前位置X计算下一新解X: 1）计算（Pid-Xid）交换序。 2）计算(Pgd-Xid)。 3）计算式1，并将Vid转换为基本交换序。 4）计算式2，更新Xid。 5）如果找到一个更好得解，更新Pid。4如果整个群体找到一个更好的解，更新Pgd，转步骤2。5显示结果。 S

4、ZUTI DSP Lab6程序分析程序分析 主要数据结构：种群大小(PopSize)空间维数(NDim)最大迭代次数(MaxIter) 城市之间的距离(nodeDistance)各粒子当前适应度值(fvalue)更新前各粒子适应度值(fpbest)各粒子位置(population)各粒子速度(velocity) 各粒子的最佳位置(pbest) 全局最佳粒子位置(gbest)全局最佳粒子序号(index)得到相近适应度值的迭代次数(samecounter)计算samecounter的临时变量 (oldbestval)SZUTI DSP Lab7主要函数主要函数 BeginWith1：使每个路径都

5、从节点1开始排起。（这个命名不好）wholeDistance：计算路径即一个循环后的距离。（改为caculateWholeDistance）ExchangeIndex： 计算（Pid-Xid）等交换序。（大小写要统一,CaculateWholeDistance,ChangeIndex）HoldByAlpha：计算以概率保留交换序。changeIndex：进行交换操作。SZUTI DSP Lab8初始化各主要数据（设求14点的TSP） flag=0;%停止程序标志oldbestval=0;%记录旧的适应度值samecounter=0; %记录得到相同适应度值的迭代次数iteration = 0;

6、%迭代次数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为起点重排每个路径SZUTI DSP Lab9初始化各主要数据 node=16.47 96.10; 16.47 94.44; 20.09 92.54; 22.3

7、9 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:Pop

8、Size%计算各路径的距离 fvalue(i) = wholeDistance(population(:,i),nodeDistance);Endvelocity =zeros(NDim,PopSize); %产生交换序for i=1:PopSize velocity(:,i)=round(rand(1,NDim)*NDim);endSZUTI DSP Lab10初始化各主要数据 pbest = population; %记录各粒子的个体极值点位置,即个体找到的最短路径fpbest = fvalue; %记录最佳适应度值,即个体找到的最短路径的长度fbestval,index = min(fv

9、alue); % 找出全局极值和相应的序号 SZUTI DSP Lab11主程序 while(flag = 0) & (iteration MaxIter)%寻找最优主程序 iteration = iteration +1;%迭代次数递增 for i=1:PopSize%更新全局极值点位置,这里指路径 gbest(:,i) = population(:,index); end pid_xid=ExchangeIndex(population,pbest);%求pid-xid ,pgd-xid交换序 pid_xid=HoldByAlpha(pid_xid,alpha); %以概率alpha保留交

10、换序 pgd_xid=ExchangeIndex(population,gbest); pgd_xid=HoldByAlpha(pgd_xid,beta); velocity=HoldByAlpha(velocity,w);%以概率w保留交换序 population = changeIndex(population,velocity);%根据交换序进行路径交换 population = changeIndex(population,pid_xid); population = changeIndex(population,pgd_xid);SZUTI DSP Lab12主程序 for i =

11、1:PopSize% 更新各路径距离 fvalue(i) = wholeDistance(population(:,i),nodeDistance); end changeColumns = fvalue = 20%多次迭代的适应度值相近时程序停止 flag=1; end Best(iteration) =fbestval;% 输出及描出找到的全局极值endSZUTI DSP Lab14BeginWith1()函数 function population=BeginWith1(population) x y=size(population); NO1,index=min(population,

12、2); %找最小值1 for i=1:y pop=population(:,i); temp1=pop(1: index(i)-1); temp2=pop(index(i): x); population(:,i)=temp2 temp1; endSZUTI DSP Lab15changeIndex（）函数 function population=changeIndex(population,velocity)x y=size(population);for i=1:y a=velocity(:,i); %取出其中一组交换序 pop=population(:,i); %取出对应的粒子 for

13、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; endSZUTI DSP Lab16ExchangeIndex （）函数 function pgid_xid=ExchangeIndex(population,pgbest);x y=size(population);pgid_xid=zeros(x,y);for i=1:y pop=pgbest(:,i); %从pgbest取出一个顺序 pop1=

14、population(:,i); %从粒子群中取出对应的顺序 for j=1:x %从pgbest的顺序中取出一个序号 NoFrompgbest=pop(j); for k=1:x %从对应的粒子顺序中取出一个序号 NoFromPopulation=pop1(k); if (NoFrompgbest=NoFromPopulation) & (j=k) %两序号同且不在同一位置 pgid_xid(j,i)=k; %交换算子 pop1(k)=pop1(j); pop1(j)=NoFromPopulation; end end endendSZUTI DSP Lab17HoldByAlpha （）函

15、数 function velocity=HoldByAlpha(velocity,w)x,y=size(velocity);for i=1:x for j=1:y if randw velocity(i,j)=0; end endendSZUTI DSP Lab18wholeDistance （）函数 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=dis

16、t+nodeDistance(path(1),path(L); %加上首尾节点的距离SZUTI DSP Lab19运行结果运行结果 节点数alphabetaw粒子数 理想达优值 opt程序运行次数结果不变最大迭代次数限制达优次数平均值ave平均值 平均运行时间err14 0.80.40.420030.87855020531.868531.60943.135s2.37% Err=(ave-opt)/optSZUTI DSP Lab20运行结果运行结果 运行五十次，每次得的最短距离如图所示 0510152025303540455030.53131.53232.53333.53434.535SZUT

17、I DSP Lab21改进微粒群优化算法求解旅行商问题改进微粒群优化算法求解旅行商问题 参照：改进微粒群优化算法求解旅行商问题肖健梅等 计算机工程与应用 2004 .35该论文在上述论文基础上作出改进，为了提高搜索效率，把速度位置算式改为：Xid1=Xid+wVidXid2=Xid1+alpha*rand()(Pid-Xid1)Xid3=Xid2+Beta*rand()(Pgd-Xid2)SZUTI DSP Lab22程序修改 去掉上述程序中的下列语句： pid_xid=ExchangeIndex(population,pbest); pid_xid=HoldByAlpha(pid_xid,a

18、lpha); %保留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(ve

19、locity,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);SZUTI DSP Lab23运行结果运行结果 节点数alphabetaw粒子数 理想达优值 opt程序运行次数结果不变最大迭代次数限制达优次数平均值ave平均值 平均运行时间err14 0.80.40.520030.87855020631.868532.10753.0334s3.98% Err=(ave-opt)/optSZUTI DSP Lab24运行结果运行结果 运行五十次，每次得的最短距离如图所示 0510152025303540455030.53131.53232.53333.53434.535SZUTI DSP Lab25 谢谢！