蚂蚁群算法求解最短路径问题（Python&Matlab实现）_蚁群算法python解最短路csdn

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.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
学好 Python 不论是就业还是做副业赚钱都不错，但要学会 Python 还是要有一个学习规划。最后大家分享一份全套的 Python 学习资料，给那些想学习 Python 的小伙伴们一点帮助！

一、Python所有方向的学习路线

Python所有方向路线就是把Python常用的技术点做整理，形成各个领域的知识点汇总，它的用处就在于，你可以按照上面的知识点去找对应的学习资源，保证自己学得较为全面。

二、学习软件

工欲善其事必先利其器。学习Python常用的开发软件都在这里了，给大家节省了很多时间。

三、全套PDF电子书

书籍的好处就在于权威和体系健全，刚开始学习的时候你可以只看视频或者听某个人讲课，但等你学完之后，你觉得你掌握了，这时候建议还是得去看一下书籍，看权威技术书籍也是每个程序员必经之路。

四、入门学习视频

我们在看视频学习的时候，不能光动眼动脑不动手，比较科学的学习方法是在理解之后运用它们，这时候练手项目就很适合了。

五、实战案例

光学理论是没用的，要学会跟着一起敲，要动手实操，才能将自己的所学运用到实际当中去，这时候可以搞点实战案例来学习。

六、面试资料

我们学习Python必然是为了找到高薪的工作，下面这些面试题是来自阿里、腾讯、字节等一线互联网大厂最新的面试资料，并且有阿里大佬给出了权威的解答，刷完这一套面试资料相信大家都能找到满意的工作。

网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。

需要这份系统化学习资料的朋友，可以戳这里无偿获取

一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！