%%蚁群算法商旅问题matlab程序
%%导入数据(城市的坐标)
citys=[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;3238 1229;4196 1004;4312 790;4386 570;3007 1970;2562 1756;2788 1491;2381 1676;1332 695;3715 2370;3780 2212;3676 2578;4029 2838;4263 2367;3394 23;3439 3201;2935 3240;3140 2826;2370 2975];
%%计算城市之间相互距离
n=size(citys,1);
D=zeros(n,n);
for i=1:n
for j=1:n
if i~=j
D(i,j)=sqrt(sum((citys(i,:)-citys(j,:)).^2));
else
1678;3918 2931;3429 3550;2545 2179;4061 1908;3507 2357;2778
D(i,j)=1e-4;
end
end
end
%%初始化参数
m=31;
alpha=1;
beta=5;
rho=0.1;
Q=1;
Eta=1./D;
Tau=ones(n,n);
Table=zeros(n,n);
iter=1;
iter_max=200;
Route_best=zeros(iter_max,n);
Leng_best=zeros(iter_max,1);
Leng_ave=zeros(iter_max,1);
%%迭代寻找最佳路径（主体循环）
while iter<=iter_max
%（1）随机产生各个蚂蚁的起点城市
start=zeros(m,1);
for i=1:m
temp=randperm(n);
start(i)=temp(1);
end
Table(:,1)=start;
%（2）构建解空间
citys_index=1:n;
for i=1:m %逐个蚂蚁路径选择
for j=2:n %逐个城市路径选择
tabu=Table(i,1:(j-1)); %已访问的城市集合（禁忌表）
allow_index=~ismember(citys_index,tabu);
allow=citys_index(allow_index); %待访问的城市集合
P=allow;
%计算城市间转移概率
for k=1:length(allow)
P(k)=Tau(tabu(end),allow(k))^alpha*Eta(tabu(end),allow(k))^beta;
end
P=P/sum(P);
%轮盘赌法选择下一个访问城市
Pc=cumsum(P);
target_index=find(Pc>=rand);
target=allow(target_index(1));
Table(i,j)=target;
end
end
%（3）计算各个蚂蚁的路径距离
Length=zeros(m,1);
for i=1:m
Route=Table(i,:);
for j=1:(n-1)
Length(i)=Length(i)+D(Route(j),Route(j+1));
end
Length(i)=Length(i)+D(Route(n),Route(1));
end
%（4）计算最短路径距离及平均距离
if iter==1
[min_Length,min_index]=min(Length);
Length_best(iter)=min_Length;
Length_ave(iter)=mean(Length);
Route_best(iter,:)=Table(min_index,:);
else
[min_Length,min_index]=min(Length);
Length_best(iter)=min(Length_best(iter-1),min_Length);
Length_ave(iter)=mean(Length);
if Length_best(iter)==min_Length
Route_best(iter,:)=Table(min_index,:);
else
Route_best(iter,:)=Route_best((iter-1),:);
end
end
%（5）更新信息素
Delta_Tau=zeros(n,n);
%逐个蚂蚁计算
for i=1:m
%逐个城市计算
for j=1:(n-1)
Delta_Tau(Table(i,j),Table(i,j+1))=Delta_Tau(Table(i,j),Table(i,j+1))+Q/Length(i);
end
Delta_Tau(Table(i,n),Table(i,1))=Delta_Tau(Table(i,j),Table(i,1))+Q/Length(i);
end
Tau=(1-rho)*Tau+Delta_Tau;
%迭代次数加1，清空路径记录表
iter=iter+1;
Table=zeros(m,n);
end
%%结果显示
[Shortest_Length,index]=min(Length_best);
Shortest_Route=Route_best(index,:);
disp(['最短距离：' num2str(Shortest_Length)]);
disp(['最短路径：' num2str([Shortest_Route Route_best(1)])]);
%%绘图
figure(1)
plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],[citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'b-');
grid on
for i=1:size(citys,1)
text(citys(i,1),citys(i,2),[' ' num2str(i)]);
end
text(citys(Shortest_Route(1),1),citys(Shortest_Route(1),2),'起点');
text(citys(Shortest_Route(end),1),citys(Shortest_Route(end),2),'终点');
xlabel('城市位置横坐标')
ylabel('城市位置纵坐标')
figure(2)
plot(1:iter_max,Length_best,'b',1:iter_max,Length_ave,'r')
legend('最短距离','平均距离''')
xlabel('迭代次数')
ylabel('距离')
text('各代最短距离与平均距离对比')
