Python&Matlab實現螞蟻群算法求解最短路徑問題的示例
1 知識點
詳細知識點見:智能優化算法—蟻群算法(Python實現)
我們這一節知識點隻講蟻群算法求解最短路徑步驟及流程。
1.1 蟻群算法步驟
設螞蟻的數量為m,地點的數量為n,地點i與地點j之間相距Dij,t時刻地點i與地點j連接的路徑上的信息素濃度為Sij,初始時刻每個地點間路徑上的信息素濃度相等。
螞蟻k根據各個地點間連接路徑上的信息素決定下一個目標地點,Pijk表示t時刻螞蟻k從地點i轉移的概率,概率計算公式如下:
上式中,為啟發函數,,表示螞蟻從地點i轉移到地點j的期望程度;為螞蟻k即將訪問地點的集合,開始時中有n-1個元素(除出發地點),隨時間的推移,螞蟻每到達下一個地點,中的元素便減少一個,直至空集,即表示所有地點均訪問完畢;a為信息素重要程度因子,值越大,表明信息素的濃度在轉移中起到的作用越大,也就是說螞蟻選擇距離近的下一個地點的概率更大,β為啟發函數重要程度因子。
螞蟻在釋放信息素的同時,每個地點間連接路徑上的信息素逐漸消失,用參數
表示信息素的揮發程度。因此,當所有螞蟻完成一次循環後,每個地點間連接路徑上的信息素濃度需更新,也就是有螞蟻路過並且留下信息素,有公式表示為:
其中,表示第k隻螞蟻在地點i與j連接路徑上釋放的信息素濃度;表示所有螞蟻在地點i與j連接路徑上釋放的信息素濃度之和;Q為常數,表示螞蟻循環一次所釋放的信息素總量;Lk表示第k隻螞蟻經過路徑的長度,總的來說,螞蟻經過的路徑越短,釋放的信息素濃度越高,最終選出最短路徑。
1.2 蟻群算法程序
(1)參數初始化
在尋最短路錢,需對程序各個參數進行初始化,蟻群規模m、信息素重要程度因子α、啟發函數重要程度因子β、信息素會發因子、最大迭代次數ddcs_max,初始迭代值為ddcs=1。
(2)構建解空間
將每隻螞蟻隨機放置在不同的出發地點,對螞蟻訪問行為按照公式計算下一個訪問的地點,直到所有螞蟻訪問完所有地點。
(3)更新信息素
計算每隻螞蟻經過的路徑總長Lk,記錄當前循環中的最優路徑,同時根據公式對各個地點間連接路徑上的信息素濃度進行更新。
(4)判斷終止
迭代次數達到最大值前,清空螞蟻經過的記錄,並返回步驟(2)。
2 螞蟻算法求解最短路徑問題——Python實現
2.1 源碼實現
智能優化算法—蟻群算法(Python實現)
2.2 ACA_TSP實現
補充知識點:scipy.spatial.distance.cdist
#============導入相關庫================= import numpy as np from scipy import spatial import pandas as pd import matplotlib.pyplot as plt from sko.ACA import ACA_TSP num_points = 25 points_coordinate = np.random.rand(num_points, 2) # 生成點的坐標 distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')#函數用於計算兩個輸入集合的距離 def cal_total_distance(routine): num_points, = routine.shape return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)]) #=============ACA_TSP解決================================== aca = ACA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=200, distance_matrix=distance_matrix) best_x, best_y = aca.run() #=============可視化======================= fig, ax = plt.subplots(1, 2) best_points_ = np.concatenate([best_x, [best_x[0]]]) best_points_coordinate = points_coordinate[best_points_, :] ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r') pd.DataFrame(aca.y_best_history).cummin().plot(ax=ax[1]) plt.show()
3 螞蟻算法求解最短路徑問題——Matlab實現
3.1 流程圖
3.2 代碼實現
下表為一些坐標點,找出最短路線:
%蟻群算法尋找最短路徑程序 %% 清空環境變量 clear clc %% 導入數據,導入方式,看個人習慣 zuobiao=[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 1678 3918 2179 4061 2370 3780 2212 3676 2578 4029 2838 4263 2931 3429 1908 3507 2367 3394 2643 3439 3201 2935 3240 3140 3550 2545 2357 2778 2826 2370 2975]; %% 計算城市間相互距離 n = size(zuobiao,1);%城市個數 jl = zeros(n,n);%首先求得各個坐標點的距離,這裡是矩陣初始化 for i = 1:n for j = 1:n if i ~= j %~=是不等於的意思,zuobiao矩陣中每行都有個坐標,坐標相減用i和j區分不同的坐標點,然後求兩點距離 jl(i,j) = sqrt(sum((zuobiao(i,:) - zuobiao(j,:)).^2)); %上式運算如a=[2,2;1,1]=>a(1,:)-a(2,:)=>ans =1 1,然後1?+1?=2,最後開根號 else jl(i,j) = 1e-4;%相等的點相減準確說是等於0的,這裡設置成瞭一個很小的數,是為瞭避免後面程序運算出錯 end end end %% 初始化參數 m = 50; % 螞蟻數量,視情況而定,坐標點多的話可以適當增加螞蟻數量 a= 1; % 信息素重要程度因子 b= 5; % 啟發函數重要程度因子 r = 0.1; % 信息素揮發因子 Q = 1; % 常數 qfhs = 1./jl; % 啟發函數,將jl矩陣中每個元素轉化為倒數 xxsjz = ones(n,n); % 信息素矩陣初始化 ljjl = zeros(m,n); % 路徑記錄表矩陣初始化 ddcs = 1; % 迭代次數初值 ddcs_max = 200; % 最大迭代次數 Lujin_best = zeros(ddcs_max,n); % 各代最佳路徑 L_best = zeros(ddcs_max,1); % 各代最佳路徑的長度 L_ave = zeros(ddcs_max,1); % 各代路徑的平均長度 %% 迭代尋找最佳路徑 while ddcs <= ddcs_max%在ddcs小於ddcs_max前,一直循環 %% 隨機產生各個螞蟻的起點 start = zeros(m,1); for i = 1:m temp = randperm(n);%功能是隨機打亂一個數字序列,也就是現將坐標點排號再打亂,相當於將螞蟻隨機分佈在各個地點 start(i) = temp(1); end ljjl(:,1) = start; %% 構建解空間 zuobiao_index = 1:n; % 逐個螞蟻路徑選擇 for i = 1:m % 逐個地點路徑選擇 for j = 2:n yfw = ljjl(i,1:(j - 1)); % 已訪問的地點集合(禁忌表) allow_index = ~ismember(zuobiao_index,yfw);%ismember用於判斷矩陣某個元素是否存在,用法詳見後文函數講解 allow = zuobiao_index(allow_index); % 待訪問的城市集合 P = allow; % 計算城市間轉移概率 for k = 1:length(allow) P(k) = xxsjz(yfw(end),allow(k))^a * qfhs(yfw(end),allow(k))^b;%見文中公式 end P = P/sum(P); % 選擇下一個訪問城市 Plj = cumsum(P); %cumsum函數用於累加,具體用法詳見後文函數講解 yidong_index = find(Plj >= rand); yidong = allow(yidong_index(1)); ljjl(i,j) = yidong; end end % 計算各個螞蟻的路徑距離 L = zeros(m,1); for i = 1:m Lujin = ljjl(i,:); for j = 1:(n - 1) L(i) = L(i) + jl(Lujin(j),Lujin(j + 1)); end L(i) = L(i) + jl(Lujin(n),Lujin(1)); end % 計算最短路徑距離及平均距離 if ddcs == 1 [min_L,min_index] = min(L); L_best(ddcs) = min_L; L_ave(ddcs) = mean(L); Lujin_best(ddcs,:) = ljjl(min_index,:); else [min_L,min_index] = min(L); L_best(ddcs) = min(L_best(ddcs - 1),min_L); L_ave(ddcs) = mean(L); if L_best(ddcs) == min_L Lujin_best(ddcs,:) = ljjl(min_index,:); else Lujin_best(ddcs,:) = Lujin_best((ddcs-1),:); end end %% 更新信息素 S = zeros(n,n); % 逐個螞蟻計算 for i = 1:m % 逐個城市計算 for j = 1:(n - 1) S(ljjl(i,j),ljjl(i,j+1)) = S(ljjl(i,j),ljjl(i,j+1)) + Q/L(i); end S(ljjl(i,n),ljjl(i,1)) = S(ljjl(i,n),ljjl(i,1)) + Q/L(i); end xxsjz = (1-r) * xxsjz + S; % 迭代次數加1,清空路徑記錄表 ddcs = ddcs + 1; ljjl = zeros(m,n); end %% 結果顯示 [Shortest_L,index] = min(L_best); Shortest_Lujin = Lujin_best(index,:); disp(['最短距離:' num2str(Shortest_L)]); disp(['最短路徑:' num2str([Shortest_Lujin Shortest_Lujin(1)])]); %% 繪圖 figure(1) plot([zuobiao(Shortest_Lujin,1);zuobiao(Shortest_Lujin(1),1)],... [zuobiao(Shortest_Lujin,2);zuobiao(Shortest_Lujin(1),2)],'o-'); grid on for i = 1:size(zuobiao,1) text(zuobiao(i,1),zuobiao(i,2),[' ' num2str(i)]); end text(zuobiao(Shortest_Lujin(1),1),zuobiao(Shortest_Lujin(1),2),' 起點'); text(zuobiao(Shortest_Lujin(end),1),zuobiao(Shortest_Lujin(end),2),' 終點'); xlabel('城市位置橫坐標') ylabel('城市位置縱坐標') title(['蟻群算法優化路徑(最短距離:' num2str(Shortest_L) ')']) figure(2) plot(1:ddcs_max,L_best,'b',1:ddcs_max,L_ave,'r') legend('最短距離','平均距離') xlabel('迭代次數') ylabel('距離') title('各代最短距離與平均距離對比')
3.3 結果
到此這篇關於Python&Matlab實現螞蟻群算法求解最短路徑問題的示例的文章就介紹到這瞭,更多相關Python&Matlab螞蟻群最短路徑內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- python matlab庫簡單用法講解
- 解決python調用matlab時的一些常見問題
- Python實現 MK檢驗示例代碼
- python實現由數組生成對稱矩陣
- python保存大型 .mat 數據文件報錯超出 IO 限制的操作