用蚁群算法的python代码解决旅行商问题并用折线图展现迭代过程

下面是用蚁群算法解决旅行商问题的 Python 代码，并用折线图展现迭代过程。

import numpy as np
import matplotlib.pyplot as plt

# 参数设置
ant_num = 50 # 蚂蚁数量
alpha = 1 # 信息素重要程度因子
beta = 2 # 启发式因子
rho = 0.5 # 信息素挥发因子
Q = 100 # 常系数
iter_max = 200 # 最大迭代次数

# 城市坐标
x = np.array([1, 1, 2, 4, 5, 7, 7, 6, 3])
y = np.array([1, 3, 5, 4, 0, 3, 6, 7, 5])

distance_graph = np.zeros((9, 9))  # 距离矩阵
for i in range(9):
    for j in range(i, 9):
        distance_graph[i][j] = distance_graph[j][i] = np.sqrt(
            (x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2
        )

pheromone_graph = np.ones((9, 9))  # 信息素矩阵

# 计算路径长度
def path_length(path):
    length = 0
    for i in range(len(path) - 1):
        length += distance_graph[path[i]][path[i + 1]]
    length += distance_graph[path[-1]][path[0]]  # 回到起点
    return length

# 蚂蚁类
class Ant:
    def __init__(self, ID):
        self.ID = ID
        self.path = []  # 当前路径
        self.unvisited = list(range(9))  # 未访问过的城市
        self.current_city = np.random.choice(self.unvisited)  # 当前所在城市
        self.path.append(self.current_city)
        self.unvisited.remove(self.current_city)
        self.path_cost = 0

    # 选择下一个城市
    def choose_next_city(self):
        P = np.zeros(9)
        for i in self.unvisited:
            P[i] = (
                pheromone_graph[self.current_city][i] ** alpha
                * (1.0 / distance_graph[self.current_city][i]) ** beta
            )
        P = P / sum(P)
        next_city = np.random.choice(range(9), p=P)
        self.path_cost += distance_graph[self.current_city][next_city]
        self.current_city = next_city
        self.path.append(next_city)
        self.unvisited.remove(next_city)

    # 更新信息素
    def update_pheromone(self):
        for i in range(len(self.path) - 1):
            pheromone_graph[self.path[i]][self.path[i + 1]] += Q / self.path_cost

# 初始化蚂蚁
ants = []
for i in range(ant_num):
    ants.append(Ant(i))

# 迭代
best_path = None
best_length = float("inf")
iter_length = []
for iter in range(iter_max):
    for ant in ants:
        while ant.unvisited:
            ant.choose_next_city()
        ant.path_cost += distance_graph[ant.path[-1]][ant.path[0]]  # 回到起点
        if ant.path_cost < best_length:
            best_length = ant.path_cost
            best_path = ant.path
        ant.update_pheromone()
        ant.__init__(ant.ID)  # 重新初始化蚂蚁
    # 信息素挥发
    pheromone_graph *= rho
    # 更新最优路径长度
    iter_length.append(best_length)

# 绘制折线图
plt.figure()
plt.plot(range(iter_max), iter_length)
plt.xlabel("Iteration")
plt.ylabel("Shortest Length")
plt.show()

代码中使用了 numpy 和 matplotlib 库，需要先安装。

运行代码后，会输出折线图，表示每次迭代后的最优路径长度。可以看到，随着迭代次数的增加，最优路径长度不断减小，最终收敛到一个较小的值。