螞蟻算法解決旅行商問題

1.簡介

蟻群算法是一種用來尋找優化路徑的概率型算法。它由Marco Dorigo于1992年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發現路徑的行為。 [1]
這種算法具有分布計算、信息正反饋和啟發式搜索的特征，本質上是進化算法中的一種啟發式全局優化算法。

2.算法原理

TSP求解中，假設蟻群算法中的每只螞蟻是具有以下特征的簡單智能體：每次周游，每只螞蟻在其經過的支路（i.j）上都留下信息素。螞蟻選擇城市的概率與城市之間的距離和當前連接之路上所包含的信息素余量有關。禁忌表用來控制螞蟻以走訪過的城市。

2.1算法參數函數分析

函數分析：

路勁構建：作為螞蟻訪問下一個城市選擇的依據

信息素更新：ρ是信息素的揮發率，Δτij是第k只螞蟻在它經過的 邊上釋放的信息素量，它等于螞蟻k本輪構建路徑長度的 倒數。Ck表示路徑長度，它是Rk中所有邊的長度和。

參數分析：

螞蟻數量：螞蟻的數量決定了信息素變化，同時數量的過多過少可能會導致找不到全局最優解。所以螞蟻的數量一般設定為城市數量的1.5倍。
信息素因子：信息素因子是螞蟻在搜索中重要的向導，其值過大，螞蟻選擇以前走過的路勁概率會大大提高，搜索隨機性會減少，其值過小則容易使陷入局部最優。
啟發函數因子：反映的是蟻群尋優過程中先驗性和確定性因素的作用強度。過大時，雖然收斂速度會加快，但容易陷入局部最優，過小時容易陷入隨機搜索，找不到最優解。
信息揮發率：表示信息素的消失水平，它的大小直接關系刀蟻群算法的全局搜索能力和收斂速度。
最大迭代次數：最大迭代次數過小，可能導致算法還沒收斂就結束了，過大則會導致浪費資源，本文中實驗次數取100次。

3.matlab具體實現

3.1代碼截圖

%% 旅行商問題(TSP)優化 %% 清空環境變量 clear all clc%% 導入數據 load citys_data.mat%% 計算城市間相互距離 fprintf('Computing Distance Matrix... \n'); n = size(citys,1); D = zeros(n,n); for i = 1:nfor j = 1:nif i ~= jD(i,j) = sqrt(sum((citys(i,:) - citys(j,:)).^2));elseD(i,j) = 1e-4; endend end%% 初始化參數 fprintf('Initializing Parameters... \n'); m = 50; % 螞蟻數量 alpha = 3; % 信息素重要程度因子 beta = 3; % 啟發函數重要程度因子 rho = 0.3; % 信息素揮發因子 Q = 1; % 常系數 Eta = 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); % 各代路徑的平均長度 %% 迭代尋找最佳路徑 figure; while iter <= iter_maxfprintf('迭代第%d次\n',iter);% 隨機產生各個螞蟻的起點城市start = zeros(m,1);for i = 1:mtemp = randperm(n);start(i) = temp(1);endTable(:,1) = start; % 構建解空間citys_index = 1:n;% 逐個螞蟻路徑選擇for i = 1:m% 逐個城市路徑選擇for j = 2:ntabu = 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;endP = P/sum(P);% 輪盤賭法選擇下一個訪問城市Pc = cumsum(P); target_index = find(Pc >= rand); target = allow(target_index(1));Table(i,j) = target;endend% 計算各個螞蟻的路徑距離Length = zeros(m,1);for i = 1:mRoute = Table(i,:);for j = 1:(n - 1)Length(i) = Length(i) + D(Route(j),Route(j + 1));endLength(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_LengthRoute_best(iter,:) = Table(min_index,:);elseRoute_best(iter,:) = Route_best((iter-1),:);endend% 更新信息素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);endDelta_Tau(Table(i,n),Table(i,1)) = Delta_Tau(Table(i,n),Table(i,1)) + Q/Length(i);endTau = (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('各代最短距離與平均距離對比')

3.2結果截圖及分析

為了更好的確定信息素因子啟發函數因子及揮發因子之間的關系，采取控制變量的方式得取實驗結果進行一一比較，得出最優解數據確定三個因子的取值。

確定不變的變量：

螞蟻數量=50，迭代次數=100次

1 alpha=1,beta=3,rho=0.3

2 alpha=2,beta=3,rho=0.3

3 alpha=3,beta=3,rho=0.3

小結：改變alpha(信息素重要程度)，通過觀察發現增高alpha值提高了函數的收斂速度，但陷入了局部最優不能找到函數的最優解，其原因是alpha增高了，降低了蟻群的隨機搜索性，最后通過對比，發現當alpha=2使函數有了比較明顯的優化，故將alpha改為2。

4 alpha=2,beta=4,rho=0.3

小結：本圖修改了beta(函數啟發因子)為4。所求得得最短路徑隨之變化，它表現的是啟發式信息在指導蟻群搜索過程之中相對重要的程度，它的大小影響著蟻群在整個尋短過程中的先驗性和確定性。將4圖和圖2進行比較，發現收斂速度無明顯增加，且陷入了局部最優。故beta不修改。

5 alpha=2,beta=3,rho=0.4

小結：本階段將修改rho(信息素揮發度)來找到最優rho，本圖5與圖2進行比較，收斂速度明顯加快，但依舊陷入局部最優。故不做修改，繼續修改rho值實驗。

6 alpha=2,beta=3,rho=0.5

小結：本圖6與圖2相比依舊為局部最優故增加rho只能降低蟻群的搜索不確定性，故增大rho不做討論。

7 alpha=2,beta=3,rho=0.2

小結：本圖7與圖2比較收斂速度明顯下降，且任然為局部最優。故rho最優值確立為3。

3.3總結：

本實驗通過比較得出alpha=2，beta=3，rho=3為最優，除此之外得出了rho的大小直接影響了蟻群算法的全局搜索能力和收斂速度。各個參數實際上都直接或間接得影響著蟻群的搜索能力及收斂速度。同時蟻群算法的優點也顯而易見。在解決最短路徑長度這一塊，蟻群能很快得得出幾十幾百甚至成千上萬個城市之間得旅行商問題。在實際生活中生產中，蟻群算法還可以解決其他一些問題，通過改良版的蟻群優化算法有更高效的執行效率，例如光網絡的智能化管理，計算機網絡路由，聚類問題等等。

總結

以上是生活随笔為你收集整理的蚂蚁算法matlab的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。