蚁群算法求解TSP问题python代码(另有基于两交换法的贪婪算法与蚁群算法的比较)
蚁群算法求解TSP问题-基于python本文将贪婪算法与蚁群算法求解含80个城市的TSP问题的结果进行对比代码如下:参数或坐标点数据均可自己调整import numpy as npfrom scipy import spatialimport matplotlib.pyplot as plt城市参数num_city = 80 # 城市数量rng1 = np.random.RandomState(0
蚁群算法求解TSP问题-基于python
本文将贪婪算法与蚁群算法求解含80个城市的TSP问题的结果进行对比
代码如下:参数或坐标点数据均可自己调整
import numpy as np
from scipy import spatial
import matplotlib.pyplot as plt
城市参数
num_city = 80 # 城市数量
rng1 = np.random.RandomState(0)
co = rng1.rand(num_city, 2) # 城市坐标
绘制城市
plt.scatter(co[:, 0], co[:, 1], c='r', s=10)
贪婪算法参数
greedy_iter = 200 # 贪婪算法迭代次数
距离矩阵
distance_matrix = spatial.distance.cdist(co, co, metric='euclidean')
初始解
initial_solution = np.arange(num_city)
np.random.shuffle(initial_solution)
总距离计算函数
def distance_calculation(x):
total_distance = 0
for i in range(len(x)):
total_distance += distance_matrix[x[i % len(x)]][x[(i + 1) % len(x)]]
return total_distance
基于两交换的贪婪算法求解
##设解序列为[1,2,4,8,7],现将第2位元素与第4位元素进行两交换,得到新序列为[1,8,4,2,7]
for i in range(greedy_iter):
a, b = np.random.randint(0, num_city, 2)
initial_solution1 = initial_solution.copy()
initial_solution1[a] = initial_solution[b]
initial_solution1[b] = initial_solution[a]
if distance_calculation(initial_solution1) < distance_calculation(initial_solution):
# 若两交换后新的解序列的目标函数值(路径距离总长)小于原序列,则以新序列取代原序列,否则continue,循环继续。
initial_solution = initial_solution1
print(distance_calculation(initial_solution))
蚁群算法参数
num_ant = 100 # 蚂蚁数量
alpha = 2 # 信息素权重
beta = 3 # 可见度权重
ru = 0.7 # 信息素挥发率
T = 100 # 蚁群算法主循环迭代次数
##信息素矩阵
tao = 0.25 * np.ones([num_city, num_city])
##所有蚂蚁的路径矩阵
route_matrix = []
##所有蚂蚁的路径距离矩阵
distance_all_ants = []
蚁群算法主循环
for q in range(T):
# time_matrix为记录第k只蚂蚁经过弧ij次数的三维数组,shape为(k,i,j)
time_matrix = np.zeros([num_ant, num_city, num_city])
route_matrix = []
for i in range(num_ant):
start_point = np.random.randint(0, num_city)
route = [start_point]
for j in range(len(initial_solution) - 1):
p = []
route_set = set(route)
next_city_set = set(list(np.arange(num_city)))
next_city = list(next_city_set - route_set)
for item in next_city:
p.append(tao[route[-1]][item] ** alpha + (1 / (distance_matrix[route[-1]][item])) ** beta)
p = np.array(p)
p = p / np.sum(p)
p = np.cumsum(p)
r = np.random.rand()
if r < p[0]:
route.append(next_city[0])
time_matrix[i][route[-1]][next_city[0]] = time_matrix[i][route[-1]][next_city[0]] + 1
elif r > p[-1]:
route.append(next_city[-1])
time_matrix[i][route[-1]][next_city[-1]] = time_matrix[i][route[-1]][next_city[-1]] + 1
else:
for w in range(len(p) - 1):
if p[w] <= r <= p[w + 1]:
route.append(next_city[w + 1])
time_matrix[i][route[-1]][next_city[w + 1]] = time_matrix[i][route[-1]][next_city[w + 1]] + 1
time_matrix[i][route[-1]][route[0]] = time_matrix[i][route[-1]][route[0]] + 1
# 记录每只蚂蚁访问ij弧的次数
for h in range(len(time_matrix[i])):
for k in range(len(time_matrix[i][h])):
s = time_matrix[i][h][k]
d = time_matrix[i][k][h]
time_matrix[i][h][k] = s + d
time_matrix[i][k][h] = s + d
route_matrix.append(route)
distance_all_ants = [distance_calculation(route_matrix[i]) for i in range(len(route_matrix))]
# 信息素更新
for i in range(len(tao)):
for j in range(i, len(tao[i])):
tao[i][j] = tao[i][j] * (1 - ru) + sum(
distance_all_ants[z] ** (-1) * time_matrix[z][i][j] for z in range(num_ant))
tao[j][i] = tao[i][j]
print('第', q + 1, '代已迭代完成')
print(distance_all_ants)
print(route_matrix)
best_solution = min(distance_all_ants)
best_ant = route_matrix[distance_all_ants.index(best_solution)]
print('最优解为', best_solution)
print('最优个体为\n', best_ant)
绘制最优解路径图
for i in range(len(best_ant)):
plt.plot([co[best_ant[i % len(best_ant)]][0], co[best_ant[(i + 1) % len(best_ant)]][0]],
[co[best_ant[i % len(best_ant)]][1], co[best_ant[(i + 1) % len(best_ant)]][1]], c='b', linewidth=1)
plt.show()
求解结果
最优个体为:
[77, 75, 13, 73, 8, 41, 46, 76, 52, 45, 54, 2, 62, 16, 20, 40, 24, 32, 66, 63, 39, 38, 27, 23, 30, 7, 47, 29, 42, 64, 56, 50, 28, 31, 21, 37, 34, 33, 49, 26, 36, 61, 19, 58, 78, 5, 60, 1, 53, 67, 22, 18, 68, 0, 11, 55, 71, 3, 6, 44, 51, 74, 9, 72, 59, 10, 35, 4, 70, 57, 25, 65, 69, 14, 79, 43, 48, 12, 17, 15]
路径总长为:9.610793651286054
绘制路径图如下所示:
贪婪算法(两交换)求解结果:
路径总长:25.471712780003617
一般在城市个数较少时,基于两交换法的贪婪算法与蚁群算法求解结果相差不大,一旦城市规模超过50,蚁群算法的最终解将明显好于贪婪算法
更多推荐
所有评论(0)