资源描述:
《用模拟退火算法或者遗传算法解决TSP问题程序.docx》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、用模拟退火算法、遗传算法(或蚁群算法)求解10城市的TSP(旅行商)问题,计算旅行封闭的最短旅行距离。解:用遗传算法解决TSP问题,首先需要确定城市个数及城市间的距离,随机产生城市序列作为一个个体,确定目标函数,通过遗传算法的复制、交叉、变异求出最优解。目标函数fx=i=0ndi,i+1+d(n,0)适应度函数Fx=-fx+Cmaxfx2、5117739471574118012532511163320771369115739611518127212530146238014908218563660385256725111462092223351562216539959331653163338092201700104111353870456209720771490233517000231192021701920142513698211562104123110142042906261177115785621651135920142002870129039473961366039953870217
3、04290287004090157415183859934561920626129040900];D=size(ZQ,1);EE=CSHZQ(ZQDX,D);disp('初始种群中的一个随机值:')SCXL(EE(1,:));RTH=XLCD(ZQ,EE(1,:));disp('总距离:');disp(num2str(RTH));Q=0;OV=XLCD(ZQ,EE);POV=min(OV);while(Q4、(XZ,Pc);XZ=BY(XZ,Pm);XZ=NZ(XZ,ZQ);EE=CCZ(EE,XZ,OV);Q=Q+1;endOV=XLCD(ZQ,EE);[minOV,minInd]=min(OV);disp('最优解:')p=SCXL(EE(minInd(1),:));disp('总距离:');disp(num2str(OV(minInd(1))));初始化全局变量:functionEE=CSHZQ(ZQDX,D)EE=zeros(ZQDX,D);for(i=1:ZQDX)EE(i,:)=randperm(D);end适应度函数:functionSYD=S
5、HYD(len)SYD=1./len;选择程序:functionXZ=XUANZE(EE,SYD,DG)ZQDX=size(EE,1);NSel=max(floor(ZQDX*DG+.5),2);ChrIx=sus(SYD,NSel);XZ=EE(ChrIx,:);functionNewChrIx=sus(SYD,Nsel)[Nind,ans]=size(SYD);cumfit=cumsum(SYD);trials=cumfit(Nind)/Nsel*(rand+(0:Nsel-1)');Mf=cumfit(:,ones(1,Nsel));Mt=tria
6、ls(:,ones(1,Nind))';[NewChrIx,ans]=find(Mt=rand)[XZ(i,:),XZ(i+1,:)]=ICS(XZ(i,:),XZ(i+1,:));endendICS函数function[
7、a,b]=ICS(a,b)L=length(a);r1=randsrc(1,1,[1:L]);r2=randsrc(1,1,[1:L]);ifr1~=r2a0=a;b0=b;s=min([r1,r2]);e=max([r1,r2]);fori=s:ea1=a;b1=b;a(i)=b0(i);b(i)=a0(i);x=find(a==a(i));y=find(b==b(i));i1=x(x~=i);i2=y(y~=i);if~isempty(i1)a(i1)=a1(i);endif~isempty(i2)b(i2)=b1(i);endendend变异:fu
8、nctionXZ=BY(XZ,Pm)[NSel,L]=size(XZ);for(