当前位置：首页 > news >正文

数学建模——启发式算法（蚁群算法）

news 2025/7/8 2:55:42

算法原理

蚁群算法来自于蚂蚁寻找食物过程中发现路径的行为。蚂蚁并没有视觉却可以寻找到食物，这得益于蚂蚁分泌的信息素，蚂蚁之间相互独立，彼此之间通过信息素进行交流，从而实现群体行为。

蚁群算法的基本原理就是蚂蚁觅食的过程。首先，蚂蚁在觅食的过程中会在路径上留下信息素（pheromone），并在寻找食物的过程中感知这种物质的强度，并指导自己的行为方向，他们总会朝着浓度高的方向前进。因此可以看得出来，蚂蚁觅食的过程是一个正反馈的过程，该路段经过的蚂蚁越多，信息素留下的就越多，浓度越高，更多的蚂蚁都会选择这个路段。

运行实例

例题（用蚁群算法解决旅行商问题）

假设有一个旅行商需要从城市1出发，经过若干个城市，最后回到城市1。已知城市之间的距离矩阵，旅行商的目标是最小化经过所有城市的总距离。请使用蚁群算法求解该问题。

问题定义：
- 假设有n个城市，城市之间的距离矩阵为D，其中D[i][j]表示城市i到城市j的距离。
初始化参数：
- 蚂蚁数量：m
- 信息素重要程度因子：alpha
- 启发函数重要程度因子：beta
- 信息素蒸发系数：rho
- 信息素增强系数：Q
- 最大迭代次数：iter_max
算法步骤：
- 初始化信息素矩阵tau，所有元素设为相同值。
- 迭代过程：
  - 每只蚂蚁根据概率选择下一个城市，概率计算公式为：
  - 更新路径和距离
  - 更新信息素矩阵
  - 重复迭代直到满足停止条件

代码示例

import numpy as np
import random# 初始化参数
n = 10  # 城市数量
m = 50  # 蚂蚁数量
alpha = 1  # 信息素重要程度因子
beta = 5  # 启发函数重要程度因子
rho = 0.1  # 信息素蒸发系数
Q = 100  # 信息素增强系数
iter_max = 200  # 最大迭代次数# 生成距离矩阵
D = np.random.rand(n, n)
D = (D + D.T) / 2  # 确保距离矩阵是对称的
for i in range(n):D[i][i] = np.inf  # 对角线元素设为无穷大# 初始化信息素矩阵
tau = np.ones((n, n))# 启发函数矩阵
eta = 1.0 / (D + np.eye(n))# 存储最佳路径
best_length = np.inf
best_path = []# 迭代过程
for iter in range(iter_max):# 存储每只蚂蚁的路径和距离paths = []lengths = []for i in range(m):path = []length = 0visited = np.zeros(n)  # 标记已访问城市start = random.randint(0, n-1)  # 随机选择起始城市visited[start] = 1path.append(start)for j in range(n-1):tabu = path  # 禁忌表allow_list = [index for index in range(n) if index not in tabu]  # 可访问城市列表P = np.zeros(len(allow_list))  # 计算概率# 计算转移概率for k in range(len(allow_list)):P[k] = np.power(tau[start][allow_list[k]], alpha) * np.power(eta[start][allow_list[k]], beta)P = P / P.sum()# 轮盘赌选择下一个城市next_city = allow_list[np.random.choice(range(len(allow_list)), p=P)]path.append(next_city)length += D[start][next_city]start = next_city# 回到起始城市length += D[start][path[0]]paths.append(path)lengths.append(length)# 更新最佳路径if length < best_length:best_length = lengthbest_path = path# 更新信息素矩阵delta_tau = np.zeros((n, n))for i in range(m):for j in range(n - 1):delta_tau[paths[i][j]][paths[i][j + 1]] += Q / lengths[i]delta_tau[paths[i][-1]][paths[i][0]] += Q / lengths[i]tau = (1 - rho) * tau + delta_tau# 输出结果print("最佳路径长度:", best_length)print("最佳路径:", best_path)

以上代码实现了基本的蚁群算法求解TSP问题。代码中，我们首先初始化了参数，并生成了城市之间的距离矩阵。然后，我们通过迭代过程让蚂蚁在每一轮中根据信息素和启发函数选择下一个城市，并记录每只蚂蚁的路径和路径长度。在每一轮迭代结束后，我们更新信息素矩阵，并记录下目前为止找到的最短路径。

需要注意的是，代码中的一些参数（如蚂蚁数量、信息素蒸发系数等）可以根据实际情况进行调整以获得更好的性能。此外，由于使用了随机数生成器，每次运行代码得到的结果可能有所不同。

最后，代码输出了最佳路径长度和路径。这只是一个简单的例子，蚁群算法可以应用于更复杂的问题，并且可以通过各种方式改进算法的性能。