用模拟退火算法或者遗传算法解决TSP问题程序

1、用模拟退火算法、遗传算法（或蚁群算法）求解10城市的TSP（旅行商）问题，计算旅行封闭的最短旅行距离。解：用遗传算法解决TSP问题，首先需要确定城市个数及城市间的距离，随机产生城市序列作为一个个体，确定目标函数，通过遗传算法的复制、交叉、变异求出最优解。目标函数fx=i=0ndi,i+1+d(n,0)适应度函数Fx= -fx+Cmax fxCmax0 f(x)Cmax遗传算法的步骤为复制+交叉+变异=新一代遗传算法主程序：DG=0.9; MAXDD=100; ZQDX=150;Pc=0.7; Pm=0.01; ZQ=0 118 1272 2567 1653 2097 1425 1177 394

2、7 1574 118 0 1253 2511 1633 2077 1369 1157 3961 1518 1272 1253 0 1462 380 1490 821 856 3660 385 2567 2511 1462 0 922 2335 1562 2165 3995 933 1653 1633 380 922 0 1700 1041 1135 3870 456 2097 2077 1490 2335 1700 0 2311 920 2170 1920 1425 1369 821 1562 1041 2311 0 1420 4290 626 1177 1157 856 2165 1135

3、920 1420 0 2870 1290 3947 3961 3660 3995 3870 2170 4290 2870 0 4090 1574 1518 385 993 456 1920 626 1290 4090 0; 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 (QMAXDD) OV=XLCD(ZQ,EE); POV=min(OV); SY

4、D=SHYD(OV); XZ=XUANZE(EE,SYD,DG); XZ=JIAOC(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);初始化全局变量：function EE=CSHZQ(ZQDX,D)EE=zeros(ZQDX,D);for (i=1: ZQDX)EE(i,:)=randperm(D); e

5、nd适应度函数：function SYD=SHYD(len)SYD=1./len;选择程序：function XZ=XUANZE(EE,SYD,DG)ZQDX =size(EE,1);NSel=max(floor(ZQDX *DG+.5),2);ChrIx=sus(SYD,NSel);XZ=EE(ChrIx,:);function NewChrIx=sus(SYD,Nsel)Nind,ans=size(SYD);cumfit=cumsum(SYD);trials=cumfit(Nind)/Nsel*(rand+(0:Nsel-1);Mf=cumfit(:,ones(1,Nsel);Mt=tri

6、als(:,ones(1,Nind);NewChrIx,ans=find(MtMf &zeros(1,Nsel);Mf(1:Nind-1,:)=rand) XZ(i,:),XZ(i+1,:)=ICS(XZ(i,:),XZ(i+1,:); endendICS函数function a,b=ICS(a,b)L=length(a);r1=randsrc(1,1,1:L);r2=randsrc(1,1,1:L);if r1=r2 a0=a;b0=b; s=min(r1,r2); e=max(r1,r2); for i=s:e a1=a;b1=b; a(i)=b0(i); b(i)=a0(i); x=fi

7、nd(a=a(i); y=find(b=b(i); i1=x(x=i); i2=y(y=i); if isempty(i1) a(i1)=a1(i); end if isempty(i2) b(i2)=b1(i); end endend变异：function XZ=BY(XZ,Pm)NSel,L=size(XZ);for (i=1:NSel) if (Pm=rand) R=randperm(L); XZ(i,R(1:2)=XZ(i,R(2:-1:1); endend进化逆转：function XZ=NZ(XZ,ZQ)row,col=size(XZ);OV=XLCD(ZQ,XZ);XZ1=XZ;for i=1:row r1=randsrc(1,1,1:col); r2=randsrc(1,1,1:col); mininverse=min(r1,r2); maxinverse=max(r1,r2);