蚁群算法求解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，蚁群算法的最终解将明显好于贪婪算法