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

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

ID:57235006

大小:154.00 KB

页数:25页

时间:2020-08-04

粒子群优化算法求解旅行商问题课件.ppt_第1页
粒子群优化算法求解旅行商问题课件.ppt_第2页
粒子群优化算法求解旅行商问题课件.ppt_第3页
粒子群优化算法求解旅行商问题课件.ppt_第4页
粒子群优化算法求解旅行商问题课件.ppt_第5页
资源描述:

《粒子群优化算法求解旅行商问题课件.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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。