数学建模社区-数学中国

标题: 一道TSP问题的多种解法（模拟退火，遗传算法，改进遗传算法） [打印本页]

作者: 平凡如我 时间: 2015-1-31 13:43
标题: 一道TSP问题的多种解法（模拟退火，遗传算法，改进遗传算法）
本帖最后由平凡如我于 2015-1-31 13:42 编辑

已知100个目标的经度、纬度如下表所示：

经度和纬度数据表

经度	纬度	经度	纬度	经度	纬度	经度	纬度
53.7121	15.3046	51.1758	0.0322	46.3253	28.2753	30.3313	6.9348
56.5432	21.4188	10.8198	16.2529	22.7891	23.1045	10.1584	12.4819
20.1050	15.4562	1.9451	0.2057	26.4951	22.1221	31.4847	8.9640
26.2418	18.1760	44.0356	13.5401	28.9836	25.9879	38.4722	20.1731
28.2694	29.0011	32.1910	5.8699	36.4863	29.7284	0.9718	28.1477
8.9586	24.6635	16.5618	23.6143	10.5597	15.1178	50.2111	10.2944
8.1519	9.5325	22.1075	18.5569	0.1215	18.8726	48.2077	16.8889
31.9499	17.6309	0.7732	0.4656	47.4134	23.7783	41.8671	3.5667
43.5474	3.9061	53.3524	26.7256	30.8165	13.4595	27.7133	5.0706
23.9222	7.6306	51.9612	22.8511	12.7938	15.7307	4.9568	8.3669
21.5051	24.0909	15.2548	27.2111	6.2070	5.1442	49.2430	16.7044
17.1168	20.0354	34.1688	22.7571	9.4402	3.9200	11.5812	14.5677
52.1181	0.4088	9.5559	11.4219	24.4509	6.5634	26.7213	28.5667
37.5848	16.8474	35.6619	9.9333	24.4654	3.1644	0.7775	6.9576
14.4703	13.6368	19.8660	15.1224	3.1616	4.2428	18.5245	14.3598
58.6849	27.1485	39.5168	16.9371	56.5089	13.7090	52.5211	15.7957
38.4300	8.4648	51.8181	23.0159	8.9983	23.6440	50.1156	23.7816
13.7909	1.9510	34.0574	23.3960	23.0624	8.4319	19.9857	5.7902
40.8801	14.2978	58.8289	14.5229	18.6635	6.7436	52.8423	27.2880
39.9494	29.5114	47.5099	24.0664	10.1121	27.2662	28.7812	27.6659
8.0831	27.6705	9.1556	14.1304	53.7989	0.2199	33.6490	0.3980
1.3496	16.8359	49.9816	6.0828	19.3635	17.6622	36.9545	23.0265
15.7320	19.5697	11.5118	17.3884	44.0398	16.2635	39.7139	28.4203
6.9909	23.1804	38.3392	19.9950	24.6543	19.6057	36.9980	24.3992
4.1591	3.1853	40.1400	20.3030	23.9876	9.4030	41.1084	27.7149

我方有一基地，经度和纬度为（70，40）.假设我方飞机的速度为1000km/h.我方排一飞机从基地出发，侦查完所有目标回到基地，在每一目标侦查时间不计，求飞机所花费的时间？

这是一个典型的TSP问题，下面给出了三种解决方案：
一、模拟退火：

clc,clear
load sj.txt %加载敌方100 个目标的数据，数据按照表格中的位置保存在纯文本
文件sj.txt 中
x=sj(:,1:2:8);x=x(

;
y=sj(:,2:2:8);y=y(

;
sj=[x y]; d1=[70,40];
sj=[d1;sj;d1]; sj=sj*pi/180;
d=zeros(102); %距离矩阵d
for i=1:101
for j=i+1:102
temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2));
d(i,j)=6370*acos(temp);
end
end
d=d+d';
S0=[];Sum=inf;
rand('state',sum(clock));
for j=1:1000
S=[1 1+randperm(100),102];
temp=0;
for i=1:101
temp=temp+d(S(i),S(i+1));
end
if temp<Sum
S0=S;Sum=temp;
end
end
e=0.1^30;L=20000;at=0.999;T=1;
%退火过程
for k=1

%产生新解
c=2+floor(100*rand(1,2));
c=sort(c);
c1=c(1);c2=c(2);
[hide=d60,600]%计算代价函数值
df=d(S0(c1-1),S0(c2))+d(S0(c1),S0(c2+1))-d(S0(c1-1),S0(c1))-d(S0(c2),S0(c2+1));
%接受准则
if df<0
S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102)];
Sum=Sum+df;
elseif exp(-df/T)>rand(1)
S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102)];
Sum=Sum+df;
end
T=T*at;
if T<e
break;
end
end
% 输出巡航路径及路径长度
S0,Sum[/hide]

二、遗传算法：

clc,clear
load sj.txt %加载敌方100 个目标的数据
x=sj(:,1:2:8); x=x(

;
y=sj(:,2:2:8); y=y(

;
sj=[x y]; d1=[70,40];
sj0=[d1;sj;d1]; sj=sj0*pi/180;
d=zeros(102); %距离矩阵d
for i=1:101
for j=i+1:102
temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj

(j,2))+sin(sj(i,2))*sin(sj(j,2));
d(i,j)=6370*acos(temp);
end
end
d=d+d';L=102;w=50;dai=100;
%通过改良圈算法选取优良父代A
for k=1:w
c=randperm(100);
c1=[1,c+1,102];
flag=1;
while flag>0
flag=0;
for m=1

-3
for n=m+2

-1
if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))<d(c1(m),c1(m

+1))+d(c1(n),c1(n+1))
flag=1;
c1(m+1:n)=c1(n:-1:m+1);
end
end
end
end
J(k,c1)=1:102;
end
J=J/102;
J(:,1)=0;J(:,102)=1;
rand('state',sum(clock));
%遗传算法实现过程
A=J;
for k=1:dai %产生0～1 间随机数列进行编码
B=A;
c=randperm(w);
%交配产生子代B
for i=1:2:w
F=2+floor(100*rand(1));
temp=B(c(i),F:102);
B(c(i),F:102)=B(c(i+1),F:102);
B(c(i+1),F:102)=temp;
end
%变异产生子代C
by=find(rand(1,w)<0.1);
if length(by)==0
by=floor(w*rand(1))+1;
end
C=A(by,

;
L3=length(by);
for j=1

3
bw=2+floor(100*rand(1,3));
bw=sort(bw);
C(j,

=C(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw

(3)+1:102]);
end
G=[A;B;C];
TL=size(G,1);
%在父代和子代中选择优良品种作为新的父代
[hide=d60,600][dd,IX]=sort(G,2);temp(1:TL)=0;
for j=1:TL
for i=1:101
temp(j)=temp(j)+d(IX(j,i),IX(j,i+1));
end
end
[DZ,IZ]=sort(temp);
A=G(IZ(1:w),

;
end
path=IX(IZ(1),

long=DZ(1)
toc
xx=sj0(path,1);yy=sj0(path,2);
plot(xx,yy,'-o')[/hide]

三、改进遗传算法：
clc,clear
load sj.txt %加载敌方100 个目标的数据
x=sj(:,1:2:8);x=x(

;
y=sj(:,2:2:8);y=y(

;
sj=[x y];
d1=[70,40];
sj=[d1;sj;d1];
sj=sj*pi/180;
d=zeros(102); %距离矩阵d
for i=1:101
for j=i+1:102
temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj

(j,2))+sin(sj(i,2))*sin(sj(j,2));
d(i,j)=6370*acos(temp);
end
end
d=d+d';L=102;w=50;dai=100;
%通过改良圈算法选取优良父代A
for k=1:w
c=randperm(100);
c1=[1,c+1,102];
flag=1;
while flag>0
flag=0;
for m=1

-3
for n=m+2

-1
if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))<d(c1(m),c1(m

+1))+d(c1(n),c1(n+1))
flag=1;
c1(m+1:n)=c1(n:-1:m+1);
end
end
end
end
J(k,c1)=1:102;
end
J=J/102;
J(:,1)=0;J(:,102)=1;
rand('state',sum(clock));
[hide=d60,600]%遗传算法实现过程
A=J;
for k=1:dai %产生0～1 间随机数列进行编码
B=A;
%交配产生子代B
for i=1:2:w
ch0=rand;ch(1)=4*ch0*(1-ch0);
for j=2:50
ch(j)=4*ch(j-1)*(1-ch(j-1));
end
ch=2+floor(100*ch);
temp=B(i,ch);
B(i,ch)=B(i+1,ch);
B(i+1,ch)=temp;
end
%变异产生子代C
by=find(rand(1,w)<0.1);
if length(by)==0
by=floor(w*rand(1))+1;
end[/hide]
C=A(by,

;
L3=length(by);
for j=1

3
bw=2+floor(100*rand(1,3));
bw=sort(bw);
C(j,

=C(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw

(3)+1:102]);
end
G=[A;B;C];
TL=size(G,1);
%在父代和子代中选择优良品种作为新的父代
[dd,IX]=sort(G,2);temp(1:TL)=0;
for j=1:TL
for i=1:101
temp(j)=temp(j)+d(IX(j,i),IX(j,i+1));
end
end
[DZ,IZ]=sort(temp);
A=G(IZ(1:w),

;
end
path=IX(IZ(1),

long=DZ(1)

matlab源程序见附件
实验运行结果如图
——摘自《数学建模算法与应用》司守奎主编

模拟退火.jpg (154.6 KB, 下载次数: 309)