之前已經使用遺傳算法、模拟退火算法是實作了對于TSP問題求解。本次主要使用的是蟻群算法進行求解，算法的基本原理已經在第一篇算法入門中做了詳細的講解。下面主要就是進行代碼的實作：
資料使用測試資料如下：
徐州
常州
青島
北京
祁縣
洛陽
黃山
武漢
西安
九江
舟山
徐州
471
410
392
399.5
412
449
348
335
517
600
常州
62
490
433
458.5
503
423
414
445
600
574
青島
70
559
418
313.5
503
535
627
445
740
810
北京
99
549
465
382
431
532
459
430
575
792
祁縣
111.5
579.5
365.5
387
472
517
390
321
581.5
646.5
洛陽
34
534
465
346
382
468
373
308
492
609
黃山
99
482
525
475
455
496
440
419
475
527
武漢
39
514
658
443
369
442
481
411
500
541
西安
55
574
505
443
329
406
489
440
511
654
九江
87
579
650
438
439.5
440
395
379
361
554
舟山
140
523
690
625
474.5
527
417
390
474
524
clear all
clc
%程式開始運作時開始計時
t0 = clock;
%載入資料
citys = xlsread('C:\Users\Administrator\Desktop\算法\ACA\Ch9_spots_data.xlsx','B2:L12');
%
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
D(i,j) = 1e-4; %設定的對角矩陣修正值
end
end
end
%初始化參數
m = 31; % 螞蟻數量
alpha = 1; % 資訊素重要程度因子
beta = 5; % 啟發函數重要程度因子
vol = 0.2; % 資訊素揮發因子
Q = 10; % 常系數
Heu_F = 1./D; % 啟發函數
Tau = ones(n,n); % 資訊素矩陣
Table = zeros(m,n); % 路徑記錄表
iter = 1; % 疊代次數初值
iter_max = 100; % 最大疊代次數
Route_best = zeros(iter_max,n); % 各代最佳路徑
Length_best = zeros(iter_max,1); % 各代最佳路徑的長度
Length_ave = zeros(iter_max,1); % 各代路徑的平均長度
Limit_iter = 0; % 程式收斂時疊代次數
%疊代是使用ACA尋找最優解
while iter <= iter_max
%随機分布螞蟻的初始城市
start = zeros(m,1);
for i = 1:m
temp = randperm(n);
start(i) = temp(1);
end
Table(:,1) = start;
%構造解空間
citys_index = 1:n;
%逐個螞蟻選擇路徑
for i = 1:m
% 逐個城市路徑選擇
for j = 2:n
tabu = Table(i,1:(j - 1)); % 已通路的城市集合(禁忌表)
allow_index = ~ismember(citys_index,tabu); %ismember根據一個變量的元素是否在另一個變量傳回0-1矩陣
allow = citys_index(allow_index); % 待通路的城市集合
P = allow;
% 計算城市間轉移機率
for k = 1:length(allow)
P(k) = Tau(tabu(end),allow(k))^alpha * Heu_F(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
% 計算各個螞蟻的路徑距離
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
% 計算最短路徑距離及平均距離
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,:);
Limit_iter = 1;
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,:);
Limit_iter = iter;
else
Route_best(iter,:) = Route_best((iter-1),:);
end
end
% 更新資訊素
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,n),Table(i,1)) + Q/Length(i);
end
Tau = (1-vol) * Tau + Delta_Tau;
iter = iter + 1;%疊代次數加一
Table = zeros(m,n);%清空本次的路徑表
end
% 結果顯示
[Shortest_Length,index] = min(Length_best);
Shortest_Route = Route_best(index,:);
Time_Cost=etime(clock,t0);
disp(['最短距離:' num2str(Shortest_Length)]);
disp(['最短路徑:' num2str([Shortest_Route Shortest_Route(1)])]);
disp(['收斂疊代次數:' num2str(Limit_iter)]);
disp(['程式執行時間:' num2str(Time_Cost) '秒']);
% 繪圖
figure(1)
plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],... %三點省略符為Matlab續行符
[citys(Shortest_Route,2);citys(Shortest_Route(1),2)],'o-');
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('城市位置縱坐标')
title(['ACA最優化路徑(最短距離:' num2str(Shortest_Length) ')'])
figure(2)
plot(1:iter_max,Length_best,'b')
legend('最短距離')
xlabel('疊代次數')
ylabel('距離')
title('算法收斂軌迹')
算法結果：
最短距離:6746.8159
最短路徑:11 8 10 9 5 3 4 6 1 2 7 11
收斂疊代次數:62
程式執行時間:1.434秒
