蚁群算法求解旅行商问题 (TSP)

本实验利用蚁群算法解决旅行商问题 (TSP)，即求解30个城市之间的最短路径。

代码实现

import numpy as np
import matplotlib.pyplot as plt
import matplotlib
import math
import random

matplotlib.rcParams['font.family'] = 'STSong'

city_name = []
city_condition = []
with open('30城市的坐标.txt', 'r', encoding='UTF-8') as f:
    lines = f.readlines()
    for line in lines:
        line = line.split('
')[0]
        line = line.split(',')
        city_name.append(line[0])
        city_condition.append([float(line[1]), float(line[2])])

city_condition = np.array(city_condition)

# 距离矩阵
city_count = len(city_name)
Distance = np.zeros((city_count, city_count))
for i in range(city_count):
    for j in range(city_count):
        if i != j:
            Distance[i][j] = math.sqrt((city_condition[i][0] - city_condition[j][0]) ** 2 + (city_condition[i][1] - city_condition[j][1]) ** 2)
        else:
            Distance[i][j] = 100000

# 蚂蚁数量
AntCount = 200
# 城市数量
city_count = len(city_name)
# 信息素
alpha = 1
beta = 2
rho = 0.1
iter = 0
MAX_iter = 200
Q = 1
# 初始信息素矩阵
pheromonetable = np.ones((city_count, city_count))

# 候选集列表
candidate = np.zeros((AntCount, city_count)).astype(int)

# 存放每次迭代后的最优路径
path_best = np.zeros((MAX_iter, city_count))

# 存放每次迭代的最优距离
distance_best = np.zeros(MAX_iter)
# 倒数矩阵
etable = 1.0 / Distance

while iter < MAX_iter:
    # 蚂蚁初始点选择
    if AntCount <= city_count:
        candidate[:, 0] = np.random.permutation(range(city_count))[:AntCount]
    else:
        m = AntCount - city_count
        n = 2
        candidate[:city_count, 0] = np.random.permutation(range(city_count))[:]
        while m > city_count:
            candidate[city_count * (n - 1):city_count * n, 0] = np.random.permutation(range(city_count))[:]
            m = m - city_count
            n = n + 1
        candidate[city_count * (n - 1):AntCount, 0] = np.random.permutation(range(city_count))[:m]
    length = np.zeros(AntCount)

    # 选择下一个城市
    for i in range(AntCount):
        unvisit = list(range(city_count))
        visit = candidate[i, 0]
        unvisit.remove(visit)
        for j in range(1, city_count):
            protrans = np.zeros(len(unvisit))
            for k in range(len(unvisit)):
                protrans[k] = np.power(pheromonetable[visit][unvisit[k]], alpha) * np.power(
                    etable[visit][unvisit[k]], (alpha + 1))

            cumsumprobtrans = (protrans / sum(protrans)).cumsum()
            cumsumprobtrans -= np.random.rand()
            k = unvisit[list(cumsumprobtrans > 0).index(True)]
            candidate[i, j] = k
            unvisit.remove(k)
            length[i] += Distance[visit][k]
            visit = k
        length[i] += Distance[visit][candidate[i, 0]]

    # 更新路径等参数
    if iter == 0:
        distance_best[iter] = length.min()
        path_best[iter] = candidate[length.argmin()].copy()
    else:
        if length.min() > distance_best[iter - 1]:
            distance_best[iter] = distance_best[iter - 1]
            path_best[iter] = path_best[iter - 1].copy()
        else:
            distance_best[iter] = length.min()
            path_best[iter] = candidate[length.argmin()].copy()

    # 更新信息素
    changepheromonetable = np.zeros((city_count, city_count))
    for i in range(AntCount):
        for j in range(city_count - 1):
            changepheromonetable[candidate[i, j]][candidate[i][j + 1]] += Q / length[i]
        changepheromonetable[candidate[i, j + 1]][candidate[i, 0]] += Q / length[i]
    pheromonetable = (1 - rho) * pheromonetable + changepheromonetable
    iter += 1

print("蚁群算法的最优路径", path_best[-1] + 1)
print("迭代", MAX_iter, "次后", "蚁群算法求得最优解", distance_best[-1])

# 路线图绘制
fig = plt.figure()
plt.title("Best roadmap")
x = []
y = []
path = []
for i in range(len(path_best[-1])):
    x.append(city_condition[int(path_best[-1][i])][0])
    y.append(city_condition[int(path_best[-1][i])][1])
    path.append(int(path_best[-1][i]) + 1)
x.append(x[0])
y.append(y[0])
path.append(path[0])
for i in range(len(x)):
    plt.annotate(path[i], xy=(x[i], y[i]), xytext=(x[i] + 0.3, y[i] + 0.3))
plt.plot(x, y, '-o')

# 距离迭代图
fig = plt.figure()
plt.title("Distance iteration graph")
plt.plot(range(1, len(distance_best) + 1), distance_best)
plt.xlabel("Number of iterations")
plt.ylabel("Distance value")
plt.show()

实验内容

读取数据： 读取30个城市的名称和坐标信息，并利用距离公式计算出城市之间的距离矩阵。
初始化参数： 设置蚂蚁数量、信息素因子、挥发速度等参数。
迭代求解： 循环迭代，每只蚂蚁根据信息素浓度和启发式信息选择下一个城市，计算路径长度，并更新信息素。
结果可视化： 绘制最优路径图和距离迭代图，展示算法的运行过程和结果。

实验步骤

准备数据： 创建名为 30城市的坐标.txt 的文件，包含30个城市的名称和坐标信息，每行格式为 城市名称,经度,纬度。
运行代码： 运行代码，得到最优路径和最优距离。
分析结果： 观察最优路径图和距离迭代图，分析算法的效率和准确性。

总结

蚁群算法是一种有效的解决TSP问题的启发式算法，它通过模拟蚂蚁觅食行为，利用信息素来引导搜索路径，最终找到最优解。代码中可视化结果可以更直观地展示算法的运行过程和效果。