资源描述：
《粒子群优化算法求解旅行商问题课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、粒子群优化算法求解 旅行商问题深圳大学信息工程学院黄彩玲2005年6月16日1粒子群优化算法求解旅行商问题参照：粒子群优化算法求解旅行商问题黄岚等吉林大学学报（理学版）2003年10月2五个定义设n个节点的TSP问题的解序列为s=(ai),I=1…n.定义交换子SO(i1,i2)为交换解S中的点ai1和ai2,则S’=S+SO(i1,i2)为解S经算子SO(i1,i2)操作后的新解。这里的＋的含义是执行交换操作。2一个或多个交换子的有序队列就是交换序，记作SS，SS=(SO1,SO2,…SON),SO1,SO2等是交换子，之间的顺序是有
2、意义的。作用于一个TSP问题是意味着所有的交换子依次作用于该解上。3不同的交换序作用于同一解上可能产生相同的新解，所有有相同效果的交换序的集合称为交换序的等价集。4若干个交换序可以合并成一个新的交换序，定义＋为两个交换序的合并算子。5在交换序等价集中，拥有最少交换子的交换序称为该等价集的基本交换序。3算式Vid’=Vid+alpha(Pid-Xid)+beta(Pgd-Xid)（式1）Xid’=Xid+Vid（式2）－alpha和beta为（0，1）之间的随机数。－(Pid-Xid)和(Pgd-Xid)是基本交换序，表示Xid经过交换得
3、到Pid和Pgd。－alpha(Pid-Xid)表示基本交换序(Pid-Xid)中的所有交换子以概率alpha保留。beta(Pgd-Xid)同理。4算法步骤1初始化粒子群，给每个粒子一个初始解和随机的交换序。2如果满足结束条件，转步骤5。3根据粒子当前位置X计算下一新解X’:1）计算（Pid-Xid）交换序。2）计算(Pgd-Xid)。3）计算式1，并将Vid’转换为基本交换序。4）计算式2，更新Xid。5）如果找到一个更好得解，更新Pid。4如果整个群体找到一个更好的解，更新Pgd，转步骤2。5显示结果。5程序分析主要数据结构：种群
4、大小(PopSize)空间维数(NDim)最大迭代次数(MaxIter)城市之间的距离(nodeDistance)各粒子当前适应度值(fvalue)更新前各粒子适应度值(fpbest)各粒子位置(population)各粒子速度(velocity)各粒子的最佳位置(pbest)全局最佳粒子位置(gbest)全局最佳粒子序号(index)得到相近适应度值的迭代次数(samecounter)计算samecounter的临时变量(oldbestval)6主要函数BeginWith1：使每个路径都从节点1开始排起。（这个命名不好）wholeDi
5、stance：计算路径即一个循环后的距离。（改为caculateWholeDistance）ExchangeIndex：计算（Pid-Xid）等交换序。（大小写要统一,CaculateWholeDistance,ChangeIndex）HoldByAlpha：计算以概率保留交换序。changeIndex：进行交换操作。7初始化各主要数据（设求14点的TSP）flag=0;%停止程序标志oldbestval=0;%记录旧的适应度值samecounter=0;%记录得到相同适应度值的迭代次数iteration=0;%迭代次数MaxIter=
6、2000;%最大迭代次数PopSize=200;%种群大小alpha=0.8;%概率beta=0.4;w=0.4;NDim=14;population=ones(NDim,PopSize);%初始化各粒子，即产生路径种群fori=1:PopSizepopulation(:,i)=randperm(NDim)';endpopulation=BeginWith1(population);%以1为起点重排每个路径8初始化各主要数据node=[16.4796.10;16.4794.44;20.0992.54;22.3993.37;25.2397
7、.24;...22.0096.05;20.4797.02;17.2096.29;16.3097.38;14.0598.12;...16.5397.38;21.5295.59;19.4197.13;20.0994.55];％节点坐标nodeDistance=zeros(NDim,NDim);%计算每个城市之间的距离fori=1:NDimforj=1:NDimnodeDistance(i,j)=sqrt((node(i,1)-node(j,1))^2+(node(i,2)-node(j,2))^2);endEndfori=1:PopSize
8、%计算各路径的距离fvalue(i)=wholeDistance(population(:,i)',nodeDistance);Endvelocity=zeros(NDim,PopSize);%产生交换序f
