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

用模拟退火算法、遗传算法（或蚁群算法）求解10城市的TSP（旅行商）问题，计算旅行封闭的最短旅行距离。

解：用遗传算法解决TSP问题，首先需要确定城市个数及城市间的距离，随机产生城市序列作为一个个体，确定目标函数，通过遗传算法的复制、交叉、变异求出最优解。

目标函数f x = ????=0?? ??,??+1 +??(??,0)

??? ?? +???????? ?? ??

0 ??(??)≥????????

遗传算法的步骤为

复制+交叉+变异=新一代

遗传算法主程序：

DG=0.9; MAXDD=100; ZQDX=150; Pc=0.7; Pm=0.01;

ZQ=[0 118 1272 2567 1653 2097 1425 1177 3947 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 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 (Q

Q=Q+1; end

OV=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); end

适应度函数：

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=trials(:,ones(1,Nind))';

[NewChrIx,ans]=find(Mt

function XZ=JIAOC(XZ,Pc) NSel=size(XZ,1);

for (i=1:2:NSel-mod(NSel,2)) if (Pc>=rand)

[XZ(i,:),XZ(i+1,:)]=ICS(XZ(i,:),XZ(i+1,:)); end end

ICS函数

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=find(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 end end

变异：

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)); end end

进化逆转：

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]);

XZ1(1,mininverse:maxinverse)=XZ1(i,maxinverse:-1:mininverse); end

OV1=XLCD(ZQ,XZ1); index=OV1

XZ(index,:)=XZ(index,:);

得到新一代：

function EE=CCZ(EE,XZ,OV) ZQDX =size(EE,1); NSel=size(XZ,1); [TobjV,index]=sort(OV);

EE=[EE(index(1: ZQDX -NSel),:);XZ];

计算线路长度：

function len=XLCD(ZQ,EE) [row,col]=size(ZQ); ZQDX =size(EE,1); len=zeros(ZQDX,1); for (i=1: ZQDX)

p=[EE(i,:) EE(i,1)]; i1=p(1:end-1); i2=p(2:end);

len(i,1)=sum(ZQ ((i1-1)*col+i2)); end

输出线路长度：

function p=SCXL(R) R=[R,R(1)]; N=length(R); p=num2str(R(1)); for (i=2:N)

p=[p,'->',num2str(R(i))]; end disp(p)

本文来源：https://www.bwwdw.com/article/zn73.html