MATLAB中33省会城市序号
北京 1
天津 2
上海 3
重庆 4
拉萨 5
乌鲁木齐 6
银川 7
呼和浩特 8
南宁 9
哈尔滨 10
长春 11
沈阳 12
石家庄 13
太原 14
西宁 15
济南 16
郑州 17
南京 18
合肥 19
杭州 20
福州 21
南昌 22
长沙 23
武汉 24
广州 25
海口 26
兰州 27
西安 28
成都 29
贵阳 30
昆明 31
香港 32
澳门 33
MATLAB程序代码
%%一个旅行商人要拜访全国33个省会城市,且每个城市只能拜访一次,求所有路径之中的最小值
%%%禁忌搜索算法求解TSP问题%%%%%%%%%%%%%%%%%%%%%
function [BestShortcut,theMinDistance]=TabuSearch
clear all;
close all;
clc;
Clist=[10481.4 4438.90;10548 4351.06;...
10933.2 3471.50;9588.6 3290.259;...
8199.9 3332.5139;7891.2 4867.0049;...
9564.3 4277.671;10048.5 4538.9796;...
9749.7 2539.6936;11396.7 5087.1710;...
11281.5 4879.2363;11104.2 4647.9507;...
10303.2 4228.7456;10127.7 4210.9544;...
9156.6 4065.289;10530 4075.2965;...
10228.5 3865.138;10690.2 3562.6876;...
10554.3 3542.6725;10817.1 3364.7605;...
10737 2899.96545;10430.1 3189.0724;...
10170 3136.8107;10287.9 3393.6712;...
10190.7 2575.2760;9931.5 2226.1237;...
9335.7 4006.3556;...
9805.5 3810.6524;9365.4 3410.3504;...
9603.9 2954.4510;9245.7 2784.3226;...
10269 2468.5288;10199.7 2460.745];%全国33个省会城市坐标
CityNum=size(Clist,1);%TSP问题的规模,即城市数目
dislist=zeros(CityNum);
for i=1:CityNum
for j=1:CityNum
dislist(i,j)=((Clist(i,1)-Clist(j,1))^2+(Clist(i,2)-Clist(j,2))^2)^0.5;
end
end
TabuList=zeros(CityNum); % (tabu list)
TabuLength=round((CityNum*(CityNum-1)/2)^0.5);%禁忌表长度(tabu length)
Candidates=200; %候选集的个数 (全部领域解个数)
CandidateNum=zeros(Candidates,CityNum); %候选解集合
S0=randperm(CityNum); %随机产生初始解
BSF=S0; %best so far;
BestL=Inf; %当前最佳解距离
p=1; %记录迭代次数
StopL=2001; %最大迭代次数
figure(1);
stop = uicontrol('style','toggle','string'...
,'stop','background','white');
tic; %用来保存当前时间
%%%%%%%%%%%%%%%%%%%%%%禁忌搜索循环%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
while p<StopL
if Candidates>CityNum*(CityNum-1)/2
disp('候选解个数不大于n*(n-1)/2!');
break;
end
ALong(p)=Fun(dislist,S0); %当前解适配值
i=1;
A=zeros(Candidates,2); % 解中交换的城市矩阵
%以下while的 是生成随机的200 X 2 的矩阵矩阵A。每一个元素都是在1-31之间的
while i<=Candidates
M=CityNum*rand(1,2);
M=ceil(M);
if M(1)~=M(2)
A(i,1)=max(M(1),M(2));
A(i,2)=min(M(1),M(2));
if i==1
isa=0;
else
for j=1:i-1
if A(i,1)==A(j,1) && A(i,2)==A(j,2)
isa=1;
break;
else
isa=0;
end
end
end
if ~isa
i=i+1;
else
end
else
end
end
%%%%%%%%产生领域解%%%%%%%%%%%%%%%%%%%%%%%
BestCandidateNum=100;%保留前BestCandidateNum个最好候选解
BestCandidate=Inf*ones(BestCandidateNum,4);
F=zeros(1,Candidates);
%这相当于是产生一个S0的邻域...
for i=1:Candidates
CandidateNum(i,:)=S0; %候选解集合。
CandidateNum(i,[A(i,2),A(i,1)])=S0([A(i,1),A(i,2)]);
F(i)=Fun(dislist,CandidateNum(i,:));
if i<=BestCandidateNum
BestCandidate(i,2)=F(i);
BestCandidate(i,1)=i;
BestCandidate(i,3)=S0(A(i,1));
BestCandidate(i,4)=S0(A(i,2));
else
for j=1:BestCandidateNum
if F(i)<BestCandidate(j,2)
BestCandidate(j,2)=F(i);
BestCandidate(j,1)=i;
BestCandidate(j,3)=S0(A(i,1));
BestCandidate(j,4)=S0(A(i,2));
break;
end
end
end
end
%对BestCandidate
[JL,Index]=sort(BestCandidate(:,2));
SBest=BestCandidate(Index,:);
BestCandidate=SBest;
%%%%%%%%%%%%%%%%%%%%%%%藐视准则%%%%%%%%%%%%%%%%%%%%%%%%%%%%
if BestCandidate(1,2)<BestL
BestL=BestCandidate(1,2);
S0=CandidateNum(BestCandidate(1,1),:);
BSF=S0;
for m=1:CityNum
for n=1:CityNum
if TabuList(m,n)~=0
TabuList(m,n)=TabuList(m,n)-1; % 更新禁忌表
end
end
end
TabuList(BestCandidate(1,3),BestCandidate(1,4))=TabuLength; % 更新禁忌表
else
for i=1:BestCandidateNum
if TabuList(BestCandidate(i,3),BestCandidate(i,4))==0
S0=CandidateNum(BestCandidate(i,1),:);
for m=1:CityNum
for n=1:CityNum
if TabuList(m,n)~=0
TabuList(m,n)=TabuList(m,n)-1; % 更新禁忌表
end
end
end
TabuList(BestCandidate(i,3),BestCandidate(i,4))=TabuLength; % 更新禁忌表
break;
end
end
end
ArrBestL(p)=BestL;
for i=1:CityNum-1
plot([Clist(BSF(i),1),Clist(BSF(i+1),1)],[Clist(BSF(i),2),Clist(BSF(i+1),2)],'bo-');
hold on;
end
plot([Clist(BSF(CityNum),1),Clist(BSF(1),1)],[Clist(BSF(CityNum),2),Clist(BSF(1),2)],'ro-');
title(['迭代次数:',int2str(p),' 优化最短距离:',num2str(BestL)]);
hold off;
pause(0.005);
if get(stop,'value')==1
break;
end
%存储中间结果为图片
if (p==1||p==5||p==10||p==20||p==60||p==150||p==400||p==800||p==1500||p==2000)
filename=num2str(p);
fileformat='jpg';
saveas(gcf,filename,fileformat);
end
p=p+1; %迭代次数加1
end
toc; %用来保存完成时间
BestShortcut=BSF; %最佳路线
theMinDistance=BestL; %最佳路线长度
set(stop,'style','pushbutton','string','close', 'callback','close(gcf)');
figure(2);
plot(ArrBestL,'b');
xlabel('迭代次数');
ylabel('目标函数值');
title('适应度进化曲线');
grid;
hold on;
%%figure(3)
%%plot(toc-tic,'b');
%%grid;
%%title('运行时间');
%%legend('Best So Far','当前解');
%%%%%适配值函数%%%%%%%%%%%%%%%%%%%%%
function F=Fun(dislist,s)
DistanV=0;
n=size(s,2);
for i=1:(n-1)
DistanV=DistanV+dislist(s(i),s(i+1));
end
DistanV=DistanV+dislist(s(n),s(1));
F=DistanV;