Python&Matlab实现蚂蚁群算法求解最短路径问题的示例 Python&Matlab实现蚂蚁群算法求解

1知识点

1.1 蚁群算法步骤
1.2 蚁群算法程序

2蚂蚁算法求解最短路径问题——Python实现

2.1源码实现
2.2 ACA_TSP实现

3 蚂蚁算法求解最短路径问题——Matlab实现

3.1流程图
3.2代码实现
3.3结果

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.2ACA_TSP实现
补充知识点：scipy.spatial.distance.cdist

#============导入相关库=================import numpy as npfrom scipy import spatialimport pandas as pdimport matplotlib.pyplot as pltfrom 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.shapereturn 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()

文章图片

【Python&Matlab实现蚂蚁群算法求解最短路径问题的示例】
3 蚂蚁算法求解最短路径问题——Matlab实现
3.1 流程图

文章图片

3.2 代码实现
下表为一些坐标点，找出最短路线：

文章图片

%蚁群算法寻找最短路径程序%% 清空环境变量clearclc%% 导入数据，导入方式，看个人习惯zuobiao=[13042312363913154177224437121399348815353326155632381229419610044312790438657030071970256217562788149123811676133269537151678391821794061237037802212367625784029283842632931342919083507236733942643343932012935324031403550254523572778282623702975]; %% 计算城市间相互距离n = size(zuobiao,1); %城市个数jl = zeros(n,n); %首先求得各个坐标点的距离，这里是矩阵初始化for i = 1:nfor j = 1:nif 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，最后开根号elsejl(i,j) = 1e-4; %相等的点相减准确说是等于0的，这里设置成了一个很小的数，是为了避免后面程序运算出错endendend%% 初始化参数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:mtemp = randperm(n); %功能是随机打乱一个数字序列,也就是现将坐标点排号再打乱，相当于将蚂蚁随机分布在各个地点start(i) = temp(1); endljjl(:,1) = start; %% 构建解空间zuobiao_index = 1:n; % 逐个蚂蚁路径选择for i = 1:m% 逐个地点路径选择for j = 2:nyfw = 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; %见文中公式endP = P/sum(P); % 选择下一个访问城市Plj = cumsum(P); %cumsum函数用于累加，具体用法详见后文函数讲解yidong_index = find(Plj >= rand); yidong = allow(yidong_index(1)); ljjl(i,j) = yidong; endend% 计算各个蚂蚁的路径距离L = zeros(m,1); for i = 1:mLujin = ljjl(i,:); for j = 1:(n - 1)L(i) = L(i) + jl(Lujin(j),Lujin(j + 1)); endL(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_LLujin_best(ddcs,:) = ljjl(min_index,:); elseLujin_best(ddcs,:) = Lujin_best((ddcs-1),:); endend%% 更新信息素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); endS(ljjl(i,n),ljjl(i,1)) = S(ljjl(i,n),ljjl(i,1)) + Q/L(i); endxxsjz = (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 onfor i = 1:size(zuobiao,1)text(zuobiao(i,1),zuobiao(i,2),['' num2str(i)]); endtext(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 结果