编写蚁群算法求解tsp问题的代码

下面是一个简单的 Python 蚁群算法实现，用于解决 TSP 问题：

import numpy as np

# 定义蚂蚁类
class Ant:
    def __init__(self, start_city, num_cities, alpha, beta, pheromone, distances):
        self.start_city = start_city
        self.num_cities = num_cities
        self.alpha = alpha
        self.beta = beta
        self.pheromone = pheromone
        self.distances = distances
        self.path = [start_city]
        self.visited = np.zeros(num_cities, dtype=bool)
        self.visited[start_city] = True
        self.distance = 0.0

    # 选择下一个城市
    def choose_next_city(self):
        curr_city = self.path[-1]
        unvisited_cities = np.where(~self.visited)[0]
        if len(unvisited_cities) == 0:
            return None
        probs = np.zeros(len(unvisited_cities))
        for i, city in enumerate(unvisited_cities):
            probs[i] = self.pheromone[curr_city, city] ** self.alpha * \
                       (1.0 / self.distances[curr_city, city]) ** self.beta
        probs /= np.sum(probs)
        next_city = np.random.choice(unvisited_cities, p=probs)
        self.visited[next_city] = True
        self.path.append(next_city)
        self.distance += self.distances[curr_city, next_city]
        return next_city

# 定义蚁群算法类
class ACO:
    def __init__(self, num_ants, num_iterations, alpha, beta, rho, q, distances):
        self.num_ants = num_ants
        self.num_iterations = num_iterations
        self.alpha = alpha
        self.beta = beta
        self.rho = rho
        self.q = q
        self.distances = distances
        self.pheromone = np.ones_like(distances) / len(distances)
        self.global_best_path = None
        self.global_best_distance = np.inf

    # 运行蚁群算法
    def run(self):
        for i in range(self.num_iterations):
            ants = [Ant(np.random.randint(self.distances.shape[0]), self.distances.shape[0],
                        self.alpha, self.beta, self.pheromone, self.distances) for _ in range(self.num_ants)]
            for ant in ants:
                while ant.choose_next_city():
                    pass
                if ant.distance < self.global_best_distance:
                    self.global_best_distance = ant.distance
                    self.global_best_path = ant.path
                for j in range(len(ant.path) - 1):
                    curr_city, next_city = ant.path[j], ant.path[j + 1]
                    self.pheromone[curr_city, next_city] *= (1.0 - self.rho)
                    self.pheromone[curr_city, next_city] += self.q / ant.distance

    # 返回全局最优路径和距离
    def get_global_best_path(self):
        return self.global_best_path, self.global_best_distance

使用示例：

# 定义距离矩阵
distances = np.array([[0, 2, 9, 10],
                      [1, 0, 6, 4],
                      [15, 7, 0, 8],
                      [6, 3, 12, 0]])

# 创建蚁群算法对象
aco = ACO(num_ants=10, num_iterations=100, alpha=1.0, beta=2.0, rho=0.5, q=100.0, distances=distances)

# 运行算法
aco.run()

# 获取全局最优路径和距离
print(aco.get_global_best_path())

这个例子中，我们使用了一个包含 4 个城市的 TSP 问题，使用了一个含有 10 只蚂蚁、运行 100 次迭代的蚁群算法。