智能算法解决tsp问题及源代码

《智能算法解决tsp问题及源代码》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、智能算法作业S20116096方震遗传算法解决10个城市TSP问题姓名：方震学号：S20116096一﹑问题描述10个城市的坐标如下：号12345678910X0.66830.61950.40000.24390.17070.22930.51710.87320.68780.8488Y0.25360.26340.44390.14630.22930.76100.94140.65360.52190.3609该问题的理论解为2.6907.二﹑方案设计1.编码及初始化种群以城市号编码，随机产生得到初始种群，利用randperm（城市数）函数产生，例如：674

2、953281012.计算适应度直接计算每条染色体（路径）的长度，取倒数为适应度。3.轮盘赌选择4.交叉——常规交配法（CM）设有父代1和父代2，随机选择一个交配位，子代1交配位之前的基因为父代1交配位之前的基因，交配位之后的基因，从父代2中按顺序选择那些没有出现过的基因，子代2也做类似的处理，例如（

3、为交配位）：父代1:1234

4、5678父代2:5217

5、3846子代1:1234

6、5786子代2:5217

7、34685.变异随机选择一条染色体中两个基因进行交换，例如，随机选择两个位置如3和7则：67495328101→672953481016.更新

8、种群将本代中初始种群s和变异后得到的种群s3合并为A，更新的种群s’中一半来自A中最优秀的，其余一半来自A中除了被选走的最优秀的，其他基因的随机。6智能算法作业S20116096方震三﹑结果输出与统计程序输出结果如下：》myGA近似最近路径为：54211098763近似最小路程为：2.6907运行几次后输出表格：6智能算法作业S20116096方震附录：源代码ldistance.mfunction[distan]=distance(coord)m=length(coord);distan=zeros(m);fori=1:mforj=i:mdist

9、an(i,j)=(sum((coord(:,i)-coord(:,j)).^2))^0.5;distan(j,i)=distan(i,j);endendlfit.mfunction[f,g,p]=fit(s,distan)[inn,m]=size(s);f=zeros(1,inn);g=zeros(1,inn);p=zeros(1,inn);fsum=0;fori=1:inn;forj=2:m;g(i)=g(i)+distan(s(i,j-1),s(i,j));endg(i)=g(i)+distan(s(i,m),s(i,1));f(i)=1/g

10、(i);endfsum=sum(f);fori=1:inn;p(i)=f(i)/fsum;endendlselect.mfunction[s1]=select(s,p)pl=length(p);sel=zeros(1,pl);pr=rand(1,pl);fori=1:plsump=0;j=ceil(pl*rand);whilesump

11、oss.mfunction[s2]=cross(s1,pcross)[inn,m]=size(s1);s11=zeros(inn,m);s12=zeros(inn,m);l=zeros(1,m);fori=1:inn;ifrand<=pcrosss11(i,:)=s1(i,:);l(i)=1;elses12(i,:)=s1(i,:);l(i)=0;endendifmod(sum(l),2)==1i=0;whilei==0j=ceil(m*rand);i=l(j);endl(j)=0;s12(j,:)=s11(j,:);s11(j,:)=zeros

12、(1,m);ends11(all(s11==0,2),:)=[];s12(all(s12==0,2),:)=[];[u,v]=size(s11);ifu==0s2=s1;elsefori=1:(u/2)[s11(2*i-1,:),s11(2*i,:)]=crosschrom(s11(2*i-1,:),s11(2*i,:));ends2=[s11;s12];endldif.m6智能算法作业S20116096方震function[C]=dif(A,B)la=length(A);lb=length(B);n=1;fori=1:laisequal=0;f

13、orj=1:lbifA(i)==B(j)isequal=1;break;endendifisequal==0C(n)=A(i);n=n+