旅行商问题 蚁群算法 python

以下是使用蚁群算法解决旅行商问题的Python代码示例：

import numpy as np

# 城市坐标
cities = np.array([[1304, 2312], [3639, 1315], [4177, 2244], [3712, 1399], [3488, 1535], [3326, 1556], [3238, 1229], [4196, 1004], [4312, 790], [4386, 570], [3007, 1970], [2562, 1756], [2788, 1491], [2381, 1676], [1332, 695], [3715, 1678], [3918, 2179], [4061, 2370], [3780, 2212], [3676, 2578], [4029, 2838], [4263, 2931], [3429, 1908], [3507, 2367], [3394, 2643], [3439, 3201], [2935, 3240], [3140, 3550], [2545, 2357], [2778, 2826], [2370, 2975]])

# 计算城市之间的距离
def distance(city1, city2):
    return np.sqrt(np.sum((city1 - city2) ** 2))

num_cities = len(cities)
distance_matrix = np.zeros((num_cities, num_cities))
for i in range(num_cities):
    for j in range(i+1, num_cities):
        distance_matrix[i][j] = distance(cities[i], cities[j])
        distance_matrix[j][i] = distance_matrix[i][j]

# 蚂蚁类
class Ant:
    def __init__(self, alpha, beta, distance_matrix):
        self.alpha = alpha
        self.beta = beta
        self.distance_matrix = distance_matrix
        self.num_cities = len(distance_matrix)
        self.pheromone_matrix = np.ones((self.num_cities, self.num_cities)) / (self.num_cities ** 2)
        self.path = []
        self.distance = 0.0

    # 选择下一个城市
    def select_next_city(self):
        available_cities = list(set(range(self.num_cities)) - set(self.path))
        probabilities = [self._calculate_prob(city) for city in available_cities]
        selected_city = np.random.choice(available_cities, p=probabilities)
        self.path.append(selected_city)
        self.distance += self.distance_matrix[self.path[-2]][selected_city]

    # 计算选择每个城市的概率
    def _calculate_prob(self, city):
        pheromone = self.pheromone_matrix[self.path[-1]][city]
        dist = self.distance_matrix[self.path[-1]][city]
        probs = pheromone ** self.alpha * ((1.0 / dist) ** self.beta)
        total_probs = sum([self.pheromone_matrix[self.path[-1]][i] ** self.alpha * ((1.0 / self.distance_matrix[self.path[-1]][i]) ** self.beta) for i in range(self.num_cities) if i not in self.path])
        return probs / total_probs

    # 更新信息素
    def update_pheromone(self, delta_pheromone_matrix):
        self.pheromone_matrix = (1 - evaporation_rate) * self.pheromone_matrix + delta_pheromone_matrix

# 蚁群算法类
class ACO:
    def __init__(self, num_ants, num_iterations, alpha, beta, evaporation_rate, distance_matrix):
        self.num_ants = num_ants
        self.num_iterations = num_iterations
        self.alpha = alpha
        self.beta = beta
        self.evaporation_rate = evaporation_rate
        self.distance_matrix = distance_matrix

    # 运行蚁群算法
    def run(self):
        best_path = []
        best_distance = float('inf')
        for i in range(self.num_iterations):
            ants = [Ant(self.alpha, self.beta, self.distance_matrix) for j in range(self.num_ants)]
            for ant in ants:
                for j in range(self.distance_matrix.shape[0] - 1):
                    ant.select_next_city()
                ant.distance += self.distance_matrix[ant.path[-1]][ant.path[0]]
                if ant.distance < best_distance:
                    best_distance = ant.distance
                    best_path = ant.path
                delta_pheromone_matrix = np.zeros((self.distance_matrix.shape[0], self.distance_matrix.shape[1]))
                for j in range(self.distance_matrix.shape[0] - 1):
                    delta_pheromone_matrix[ant.path[j]][ant.path[j+1]] += 1.0 / ant.distance
                    delta_pheromone_matrix[ant.path[j+1]][ant.path[j]] += 1.0 / ant.distance
                delta_pheromone_matrix[ant.path[-1]][ant.path[0]] += 1.0 / ant.distance
                delta_pheromone_matrix[ant.path[0]][ant.path[-1]] += 1.0 / ant.distance
                ant.update_pheromone(delta_pheromone_matrix)
        return best_path, best_distance

# 运行蚁群算法
num_ants = 50
num_iterations = 500
alpha = 1
beta = 5
evaporation_rate = 0.5
aco = ACO(num_ants, num_iterations, alpha, beta, evaporation_rate, distance_matrix)
best_path, best_distance = aco.run()

# 输出结果
print('最短路径为：', best_path)
print('最短距离为：', best_distance)