Python实现粒子群算法求解TSP问题

粒子群优化（Particle Swarm Optimization, PSO）是一种基于群体智能的优化算法，它通过模拟鸟群觅食行为中的信息共享机制来实现优化问题的求解。下面是一个使用Python实现的基本粒子群算法的求解10城市TSP问题的示例代码:

import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial.distance import cdist


# 粒子类
class Particle:
    def __init__(self, cities, init_order=None):
        self.cities = cities
        self.order = np.arange(cities.shape[0]) if init_order is None else init_order
        self.best_order = self.order.copy()
        self.best_cost = self.calculate_cost()

    def calculate_cost(self):
        # 计算路径总长度
        distances = cdist(self.cities, self.cities)
        route_cost = sum(distances[self.order[:-1], self.order[1:]]) + distances[self.order[-1], self.order[0]]
        return route_cost

    def update_velocity(self, gbest_order):
        # 对于TSP，速度是交换两个城市的概率，这里简化处理
        pass  # 在TSP中通常不使用速度概念，因此留空

    def update_position(self, gbest_order):
        # 随机交换两个城市的位置作为新的解
        idx1, idx2 = np.random.choice(len(self.order), 2, replace=False)
        self.order[idx1], self.order[idx2] = self.order[idx2], self.order[idx1]
        current_cost = self.calculate_cost()
        if current_cost < self.best_cost:
            self.best_cost = current_cost
            self.best_order = self.order.copy()

        # PSO类


class PSO_TSP:
    def __init__(self, cities, swarm_size=200, max_iter=500):
        self.cities = cities
        self.swarm_size = swarm_size
        self.max_iter = max_iter
        self.swarm = [Particle(cities) for _ in range(swarm_size)]
        self.gbest_cost = float('inf')
        self.gbest_order = None

    def optimize(self):
        cost_history = []
        for i in range(self.max_iter):
            for particle in self.swarm:
                particle.update_position(self.gbest_order)
                if particle.best_cost < self.gbest_cost:
                    self.gbest_cost = particle.best_cost
                    self.gbest_order = particle.best_order.copy()
            cost_history.append(self.gbest_cost)
        return self.gbest_order, cost_history

    # 随机产生城市坐标


num_cities = 10
cities = np.random.rand(num_cities, 2)

# 优化TSP
pso = PSO_TSP(cities)
best_order, cost_history = pso.optimize()

# 绘制迭代曲线
plt.plot(cost_history)
plt.xlabel('Iteration')
plt.ylabel('Cost')
plt.title('PSO for TSP - Cost Convergence')
plt.show()

# 绘制路线图
ordered_cities = cities[best_order]
ordered_cities_with_return = np.vstack((ordered_cities, ordered_cities[0]))
plt.figure()
plt.plot(ordered_cities_with_return[:, 0], ordered_cities_with_return[:, 1], 'o-')
plt.title('Best TSP Route Found by PSO')
plt.xlabel('X-coordinate')
plt.ylabel('Y-coordinate')
plt.show()