Python&Matlab實現螞蟻群演演算法求解最短路徑問題的範例

2022-03-04 19:00:46

1 知識點

我們這一節知識點只講蟻群演演算法求解最短路徑步驟及流程。

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('各代最短距離與平均距離對比')