蚁群算法Python代码实现
时间: 2024-03-30 09:32:51 浏览: 20
蚁群算法是一种模拟蚂蚁觅食行为的启发式优化算法,常用于解决组合优化问题。下面是一个简单的蚁群算法的Python代码实现:
```python
import numpy as np
# 初始化参数
num_ants = 10 # 蚂蚁数量
num_iterations = 100 # 迭代次数
alpha = 1 # 信息素重要程度因子
beta = 2 # 启发函数重要程度因子
rho = 0.5 # 信息素挥发因子
Q = 100 # 信息素增加强度因子
# 初始化城市距离矩阵
distance_matrix = np.array([[0, 2, 4, 5],
[2, 0, 7, 3],
[4, 7, 0, 6],
[5, 3, 6, 0]])
# 初始化信息素矩阵
pheromone_matrix = np.ones(distance_matrix.shape) / distance_matrix.shape[0]
# 迭代搜索
for iteration in range(num_iterations):
# 初始化蚂蚁的位置和路径
ant_positions = np.zeros(num_ants, dtype=int)
ant_paths = np.zeros((num_ants, distance_matrix.shape[0]), dtype=int)
for ant in range(num_ants):
# 蚂蚁选择下一个城市
for i in range(1, distance_matrix.shape[0]):
available_cities = np.delete(np.arange(distance_matrix.shape[0]), ant_paths[ant, :i])
probabilities = np.power(pheromone_matrix[ant_paths[ant, i-1], available_cities], alpha) * \
np.power(1 / distance_matrix[ant_paths[ant, i-1], available_cities], beta)
probabilities /= np.sum(probabilities)
next_city = np.random.choice(available_cities, p=probabilities)
ant_paths[ant, i] = next_city
# 更新蚂蚁的位置和路径
ant_positions[ant] = ant_paths[ant, -1]
# 计算路径长度和更新信息素
path_lengths = np.zeros(num_ants)
for ant in range(num_ants):
for i in range(distance_matrix.shape[0] - 1):
path_lengths[ant] += distance_matrix[ant_paths[ant, i], ant_paths[ant, i+1]]
path_lengths[ant] += distance_matrix[ant_paths[ant, -1], ant_paths[ant, 0]]
for i in range(distance_matrix.shape[0] - 1):
pheromone_matrix[ant_paths[ant, i], ant_paths[ant, i+1]] *= (1 - rho)
pheromone_matrix[ant_paths[ant, i+1], ant_paths[ant, i]] = pheromone_matrix[ant_paths[ant, i], ant_paths[ant, i+1]]
pheromone_matrix[ant_paths[ant, -1], ant_paths[ant, 0]] *= (1 - rho)
pheromone_matrix[ant_paths[ant, 0], ant_paths[ant, -1]] = pheromone_matrix[ant_paths[ant, -1], ant_paths[ant, 0]]
pheromone_matrix[ant_paths[ant, :-1], ant_paths[ant, 1:]] += Q / path_lengths[ant]
pheromone_matrix[ant_paths[ant, 1:], ant_paths[ant, :-1]] = pheromone_matrix[ant_paths[ant, :-1], ant_paths[ant, 1:]]
# 输出最优路径
best_path = ant_paths[np.argmin(path_lengths)]
print("最优路径:", best_path)
print("最优路径长度:", np.min(path_lengths))
```