基于遗传算法tsp问题解决

《基于遗传算法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;