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蚂蚁群最短路径内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/weixin_46039719/article/details/123036
相关文章
- 这篇文章主要介绍了python-opencv-画外接矩形框的实例代码,代码简单易懂,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-04
Python astype(np.float)函数使用方法解析
这篇文章主要介绍了Python astype(np.float)函数使用方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2020-06-08- 2022虎年新年即将来临,小编为大家带来了一个利用Python编写的虎年烟花特效,堪称全网最绚烂,文中的示例代码简洁易懂,感兴趣的同学可以动手试一试...2022-02-14
- 在本篇文章里小编给大家分享的是一篇关于python中numpy.empty()函数实例讲解内容,对此有兴趣的朋友们可以学习下。...2021-02-06
python-for x in range的用法(注意要点、细节)
这篇文章主要介绍了python-for x in range的用法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-05-10- 这篇文章主要介绍了Python 图片转数组,二进制互转操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-09
- 这篇文章主要介绍了Python中的imread()函数用法说明,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-16
- 这篇文章主要介绍了python如何实现b站直播自动发送弹幕,帮助大家更好的理解和学习使用python,感兴趣的朋友可以了解下...2021-02-20
python Matplotlib基础--如何添加文本和标注
这篇文章主要介绍了python Matplotlib基础--如何添加文本和标注,帮助大家更好的利用Matplotlib绘制图表,感兴趣的朋友可以了解下...2021-01-26- 这篇文章主要介绍了解决python 使用openpyxl读写大文件的坑,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-13
- 今天小编就为大家分享一篇python 计算方位角实例(根据两点的坐标计算),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-27
- 这篇文章主要为大家详细介绍了python实现双色球随机选号,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-05-02
- 在本篇文章里小编给大家整理的是一篇关于python中使用np.delete()的实例方法,对此有兴趣的朋友们可以学习参考下。...2021-02-01
- 这篇文章主要介绍了使用Python的pencolor函数实现渐变色功能,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-09
Python getsizeof()和getsize()区分详解
这篇文章主要介绍了Python getsizeof()和getsize()区分详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-20- 这篇文章主要介绍了python自动化办公操作PPT的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-05
- 这篇文章主要介绍了解决python 两个时间戳相减出现结果错误的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-12
- 这篇文章主要为大家详细介绍了python实现学生通讯录管理系统,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-25
- 这篇文章主要介绍了PyTorch一小时掌握之迁移学习篇,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-08
- 这篇文章主要介绍了Python绘制的爱心树与表白代码,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-06