#|基于改进的蚂蚁群算法求解最短路径问题、二次分配问题、背包问题【Matlab&Python代码实现】算法|python|java|matlab|数学建模比

欢迎您的到来

??? 个人主页：电力系统科研室

专栏目录：电力系统与算法之美???

文章图片

【现在公众号名字改为：荔枝科研社】
?博主课外兴趣：中西方哲学，送予读者：
?做科研，涉及到一个深在的思想系统，需要科研者逻辑缜密，踏实认真，但是不能只是努力，很多时候借力比努力更重要，然后还要有仰望星空的创新点和启发点。在我这个专栏记录我有空时的一些哲学思考和科研笔记：科研和哲思。建议读者按目录次序逐一浏览，免得骤然跌入幽暗的迷宫找不到来时的路，它不足为你揭示全部问题的答案，但若能让人胸中升起一朵朵疑云，也未尝不会酿成晚霞斑斓的别一番景致，万一它居然给你带来了一场精神世界的苦雨，那就借机洗刷一下原来存放在那儿的“真理”上的尘埃吧。
或许，雨过云收，神驰的天地更清朗.......

文章图片

本文目录如下：??????
?
目录
1 知识点
1.1 蚁群算法步骤
1.2 蚁群算法程序
2 蚂蚁算法求解最短路径问题——Python实现
2.1 源码实现
2.2ACA_TSP实现
3 蚂蚁算法求解最短路径问题——Matlab实现
4 蚂蚁算法求解二次指派问题——Matlab实现
【#|基于改进的蚂蚁群算法求解最短路径问题、二次分配问题、背包问题【Matlab&Python代码实现】】5 蚂蚁算法求解背包问题——Matlab实现
6 改进蚂蚁算法——BP神经网络蚂蚁优化算法
7 写在最后

文章图片

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 np from scipy import spatial import pandas as pd import matplotlib.pyplot as plt from sko.ACA import ACA_TSPnum_points = 25points_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实现

文章图片

文章图片

完整代码点这里：蚂蚁算法求解最短路径

文章图片

4 蚂蚁算法求解二次指派问题——Matlab实现在社会网络分析中，有一种方法用来研究关系之间的关系，通俗来讲，就是研究两个方阵的相关性和回归性。这种方法叫做QAP(Quadratic Assignment Procedure，二次指派程序)。它对两个方阵各个格值的相似性进行比较，给出两个矩阵之间的相关系数，同时对系数进行非参数检验，它以对矩阵数据的置换为基础。
QAP与其他标准的统计程序的不同之处在于，矩阵的各个值之间不相互独立，因此用许多标准的统计程序就不能对其进行参数估计和统计检验，否则会计算出错误的标准差。对于这个问题，学者们利用一种随机化检验方法（randomization test）来检验，QAP属于其中一种。