蟻群算法
蟻群算法
蟻群算法是一種用來尋找優化路徑的機率型算法。它由Marco Dorigo于1992年提出，其靈感來源于螞蟻在尋找食物過程中發現路徑的行為。這種算法具有分布計算、資訊正回報和啟發式搜尋的特征，本質上是進化算法中的一種啟發式全局優化算法。
蟻群算法的基本原理
1、螞蟻在路徑上釋放資訊素。
2、碰到還沒走過的路口，就随機挑選一條路走。同時，釋放與路徑長度有關的資訊素。
3、資訊素濃度與路徑長度成反比。後來的螞蟻再次碰到該路口時，就選擇資訊素濃度較高路徑。
4、最優路徑上的資訊素濃度越來越大。
5、最終蟻群找到最優尋食路徑。
蟻群走過較短的那一側的螞蟻數數量會多于較長那一側的，是以留下的資訊素就會多，漸漸的螞蟻就隻走較短的那一側了。
蟻群算法對TSP的求解主要有兩大步驟：（TSP問題就是要找到最短哈密爾頓回路）
1、路徑建構
AS中的随機比例規則；對于每隻螞蟻k，路徑記憶向量R^k.按照通路順序記錄了所有k已經經過的城市序号。設螞蟻k目前所在城市為i,則其選擇城市j作為下一個通路對象的機率為:
2、資訊素更新
這裡m是螞蟻個數, ρ是資訊素的蒸發率，規定0≤ ρ≤1，在AS中通常設定為 ρ =0.5，Δτij是第k隻螞蟻在它經過的邊上釋放的資訊素量，它等于螞蟻k本輪建構路徑長度的倒數。C^k表示路徑長度，它是R^k中所有邊的長度和。
建構圖：建構圖與問題描述圖是一緻的，成份的集合C對應着點的集合（即：C=N），連接配接對應着邊的集合（即L=A）,且每一條邊都帶有一個權值，代表點i和j之間的距離。
限制條件：所有城市都要被通路且每個城市最多隻能被通路一次。
資訊素和啟發式資訊：TSP 問題中的資訊素表示在通路城市i後直接通路城市j的期望度。啟發式資訊值一般與城市i和城市j的距離成反比。
解的建構：每隻螞蟻最初都從随機選擇出來的城市出發，每經過一次疊代螞蟻就向解中添加一個還沒有通路過的城市。當所有城市都被螞蟻通路過之後，解的建構就終止。
蟻群算法存在缺陷：
蟻群算法在解決小規模TSP問題是勉強能用，稍加時間就能發現最優解，但是若問題規模很大，蟻群算法的性能會極低，甚至卡死。是以可以進行改進，例如精英螞蟻系統。
精英螞蟻系統是對基礎蟻群算法的一次改進，它在原AS資訊素更新原則的基礎上增加了一個對至今最優路徑的強化手段。在每輪資訊素更新完畢後，搜尋到至今最優路徑的那隻螞蟻将會為這條路徑添加額外的資訊素。精英螞蟻系統引入 這種額外的資訊素強化手段有助于更好的引導螞蟻搜尋的偏向，使算法更快收斂
針對不同影響因素進行測試
m = 50; % 螞蟻數量
alpha = 1; % 資訊素重要程度因子
beta = 5; % 啟發函數重要程度因子
rho = 0.1; % 資訊素揮發因子
螞蟻數量50，資訊素重要程度因子1，啟發函數重要程度因子5， 資訊素揮發因子0.1在疊代次數在40次左右收束
m = 50; % 螞蟻數量
alpha = 0.5; % 資訊素重要程度因子
beta = 10; % 啟發函數重要程度因子
rho = 0.1; % 資訊素揮發因子
螞蟻數量50，資訊素重要程度因子0.5，啟發函數重要程度因子10， 資訊素揮發因子0.1在疊代次數在15次左右收束 ，大幅減少疊代次數（降低了資訊素，增加了啟發函數重要程度因子）
m = 50; % 螞蟻數量
alpha = 0.1; % 資訊素重要程度因子
beta = 10; % 啟發函數重要程度因子
rho = 0.1; % 資訊素揮發因子
螞蟻數量50，資訊素重要程度因子0.1，啟發函數重要程度因子10， 資訊素揮發因子0.1在疊代次數在60次左右收束 ，疊代次數不減反增，可見資訊素重要程度因子不能過小
m = 50; % 螞蟻數量
alpha = 0.1; % 資訊素重要程度因子
beta = 5; % 啟發函數重要程度因子
rho = 0.1; % 資訊素揮發因子
螞蟻數量50，資訊素重要程度因子0.1，啟發函數重要程度因子5， 資訊素揮發因子0.1在疊代次數在55次左右收束，啟發函數重要程度因子在超過一定數值後并不能有效降低，是以啟發函數重要程度因子不宜超過5
m = 100; % 螞蟻數量
alpha = 1; % 資訊素重要程度因子
beta = 5; % 啟發函數重要程度因子
rho = 0.1; % 資訊素揮發因子
螞蟻數量100，資訊素重要程度因子1，啟發函數重要程度因子5， 資訊素揮發因子0.1在疊代次數在45次左右收束，增加蟻群數量後能一定程度上減少疊代次數，但是沒有明顯作用，且增加了運作時間成本，不建議過大。
m = 50; % 螞蟻數量
alpha = 1; % 資訊素重要程度因子
beta = 5; % 啟發函數重要程度因子
rho = 0.2; % 資訊素揮發因子
螞蟻數量50，資訊素重要程度因子1，啟發函數重要程度因子5， 資訊素揮發因子0.2在疊代次數在60次左右收束，資訊素揮發因子在增大也沒有更加明顯的優化了，推薦0.1-0.2即可。
蟻群算法代碼
%% 旅行商問題(TSP)優化
%% 清空環境變量
clear all
clc
%% 導入資料
load citys_data.mat
%% 計算城市間互相距離
fprintf(\'Computing Distance Matrix... \n\');
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
%% 初始化參數
fprintf(\'Initializing Parameters... \n\');
m = 50; % 螞蟻數量
alpha = 1; % 資訊素重要程度因子
beta = 5; % 啟發函數重要程度因子
rho = 0.2; % 資訊素揮發因子
Q = 1; % 常系數
Eta = 1./D; % 啟發函數
Tau = ones(n,n); % 資訊素矩陣
Table = zeros(m,n); % 路徑記錄表
iter = 1; % 疊代次數初值
iter_max = 150; % 最大疊代次數
Route_best = zeros(iter_max,n); % 各代最佳路徑
Length_best = zeros(iter_max,1); % 各代最佳路徑的長度
Length_ave = zeros(iter_max,1); % 各代路徑的平均長度
%% 疊代尋找最佳路徑
figure;
while iter <= iter_max
fprintf(\'疊代第%d次\n\',iter);
% 随機産生各個螞蟻的起點城市
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);
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
% 計算各個螞蟻的路徑距離
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,:);
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
% 更新資訊素
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-rho) * Tau + Delta_Tau;
% 疊代次數加1，清空路徑記錄表
% figure;
%最佳路徑的疊代變化過程
[Shortest_Length,index] = min(Length_best(1:iter));
Shortest_Route = Route_best(index,:);
plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...
[citys(Shortest_Route,2);citys(Shortest_Route(1),2)],\'o-\');
pause(0.3);
iter = iter + 1;
Table = zeros(m,n);
% end
end
%% 結果顯示
[Shortest_Length,index] = min(Length_best);
Shortest_Route = Route_best(index,:);
disp([\'最短距離:\' num2str(Shortest_Length)]);
disp([\'最短路徑:\' num2str([Shortest_Route Shortest_Route(1)])]);
%% 繪圖
figure(1)
plot([citys(Shortest_Route,1);citys(Shortest_Route(1),1)],...
[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([\'蟻群算法優化路徑(最短距離:\' num2str(Shortest_Length) \')\'])
figure(2)
plot(1:iter_max,Length_best,\'b\',1:iter_max,Length_ave,\'r:\')
legend(\'最短距離\',\'平均距離\')
xlabel(\'疊代次數\')
ylabel(\'距離\')
title(\'各代最短距離與平均距離對比\') 總結
蟻群算法(AS)的缺點：
1、收斂速度慢（運作一次要等好久）
2、易于陷入局部最優
m -> 螞蟻數量:
m數目越多,得到的最優解就越精确,但是會有螞蟻重複路過同一城市,大量的重複增加了運作時間（100差不多了，運作好久）
alpha -> 資訊素重要程度因子:
alpha值過大,螞蟻選擇之前走過的路徑可能性就越大,蟻群搜尋路徑的随機性減弱。alpha值過小,蟻群搜尋範圍就會減少,易陷入局部最優解。（感覺1或者2就挺好）
beta -> 啟發函數重要程度因子：
beta值增大,蟻群更容易選擇局部較短路徑,能加快算法的運作速度,但是可能陷入局部最優解（4或5就挺大的了）
rho -> 資訊素揮發因子：
rho值初始設定為0.1，當rho很小的時候，每條路徑的殘留資訊很多，會被反複搜尋，增加運作時間。rho設定的很大的時候,會放棄搜尋很多有效路徑,可能會忽略最優值。