基于遗传算法tsp问题解决

基于遗传算法tsp问题解决

ID:26651071

大小:242.50 KB

页数:10页

时间:2018-11-28

基于遗传算法tsp问题解决_第1页
基于遗传算法tsp问题解决_第2页
基于遗传算法tsp问题解决_第3页
基于遗传算法tsp问题解决_第4页
基于遗传算法tsp问题解决_第5页
资源描述:

《基于遗传算法tsp问题解决》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

1、基于遗传算法的TSP问题解决—余小欢B07330230概述:TSP问题是一个经典的运筹学的组合优化问题,针对此问题,研究人员提出了个中各样的算法,主要有贪婪算法,遗传算法,混沌搜索算法等。在本文中分别用贪婪算法和遗传算法去解决30个城市的最短路径问题,并把两者得到了最优解进行比较,发现用遗传算法解决TSP问题非常具有优越性,同时在文章的最后提出了对此遗传算法进行改进的方向。1.贪婪算法x=[188774712558413182471646883585451374127222562879183414544];y=[54767871383550404040424460586969

2、62678494996460623273846262135];a=zeros(30,30);fori=1:30forj=1:30a(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2);%求取距离矩阵的值enda(i,i)=1000;%主对角线上的元素置为1000作为惩罚endb=0;c=zeros(30);forj=1:30[m,n]=min(a(:,j));b=b+m;%得到的b值即为贪婪最佳路径的总距离a(n,:)=1000;%已经选择的最小值对应的行的所有值置为1000作为惩罚c(j)=n;endx1=zeros(30);y1=zeros(30

3、);fort=1:30x1(t)=x(c(t));y1(t)=y(c(t));endplot(x1,y1,'-or');xlabel('Xaxis'),ylabel('Yaxis'),title('Ì°À·Â·¾¶');axis([0,1,0,1]);axis([0,100,0,100]);axison用贪婪算法得出的最佳路径走遍30个城市所走的路程为449.3845km其具体的路径图如下:1.遗传算法1主函数部分clc;clearall;closeall;globalxycityfile=fopen('city30.txt','rt');%取30个城市的样本cities=f

4、scanf(cityfile,'%f%f',[2,inf]);%fscanf返回数据的个数fclose(cityfile);t=30+1;%城市的数目是30个s=1500;%样本的数目是1400个G=300;%运算的代数c=25;%选择算子中每次替代的样本的数量x=cities(1,:);y=cities(2,:);pc=0.10;%交叉的概率pm=0.8;%变异的概率pop=zeros(s,t);%得初始的pop矩阵,矩阵的最后一列表示所在行的样本的路径距离fori=1:spop(i,1:t-1)=randperm(t-1);%随机产生1—(t-1)的t-1个数endfor

5、k=1:1:G%GA开始ifmod(k,50)==1kendpop=distance(pop);%调用距离函数求距离pop=select(pop,c);%调用选择函数p1=rand;ifp1>=pcpop=cross(pop);%调用交叉函数endp2=rand;ifp2>=pmpop=mutate(pop);%调用变异函数endend%GA结束%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%bestL=min(pop(:,t))J=pop(:,t);fi=1./J

6、;[Oderfi,Indexfi]=sort(fi);%对于fi进行排序BestS=pop(Indexfi(s),:);%得到最短路I=BestS;fori=1:1:t-1x1(i)=x(I(i));y1(i)=y(I(i));endx1(t)=x(I(1));y1(t)=y(I(1));cities_new=[x1;y1];disp('BestRouteis:');disp(cities_new);pos=[cities_newcities_new(:,1)];lentemp=0;fori=1:1:t-1temp=sqrt((pos(1,i)-pos(1,i+1))^2+(

7、pos(2,i)-pos(2,i+1))^2);lentemp=lentemp+temp;enddisp('ShortestLengthis:');disp(lentemp);figure(1);subplot(1,2,1);%窗口分割的左边部分x(t)=x(1);y(t)=y(1);plot(x,y,'-or');xlabel('Xaxis'),ylabel('Yaxis'),title('原始路径');axis([0,1,0,1]);axis([0,100,0,100]);axisonholdon;

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

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

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