粒子群算法解决TSP问题代码

以下是Python代码实现粒子群算法解决TSP问题：

import random
import math

POPULATION_SIZE = 30
MAX_ITERATION = 1000
C1 = 0.5
C2 = 0.5
W = 0.7

class Particle:
    def __init__(self, cities):
        self.position = random.sample(cities, len(cities))
        self.velocity = [0] * len(cities)
        self.pbest = self.position[:]
        self.pbest_fitness = self.fitness()
        
    def fitness(self):
        distance = 0
        for i in range(len(self.position) - 1):
            distance += math.sqrt((self.position[i][0] - self.position[i+1][0])**2 + (self.position[i][1] - self.position[i+1][1])**2)
        distance += math.sqrt((self.position[0][0] - self.position[-1][0])**2 + (self.position[0][1] - self.position[-1][1])**2)
        return distance
        
    def update_velocity(self, gbest):
        for i in range(len(self.velocity)):
            r1 = random.random()
            r2 = random.random()
            cognitive_component = C1 * r1 * (self.pbest[i][0] - self.position[i][0], self.pbest[i][1] - self.position[i][1])
            social_component = C2 * r2 * (gbest.position[i][0] - self.position[i][0], gbest.position[i][1] - self.position[i][1])
            self.velocity[i] = W * self.velocity[i] + cognitive_component + social_component
            
    def update_position(self):
        for i in range(len(self.position)):
            self.position[i] = (self.position[i][0] + self.velocity[i][0], self.position[i][1] + self.velocity[i][1])
            
        # check boundary
        for i in range(len(self.position)):
            if self.position[i][0] < 0:
                self.position[i] = (0, self.position[i][1])
            if self.position[i][0] > 1:
                self.position[i] = (1, self.position[i][1])
            if self.position[i][1] < 0:
                self.position[i] = (self.position[i][0], 0)
            if self.position[i][1] > 1:
                self.position[i] = (self.position[i][0], 1)
                
    def update_pbest(self):
        fitness = self.fitness()
        if fitness < self.pbest_fitness:
            self.pbest = self.position[:]
            self.pbest_fitness = fitness
            
class PSO_TSP:
    def __init__(self, cities):
        self.population = [Particle(cities) for _ in range(POPULATION_SIZE)]
        self.gbest = min(self.population, key=lambda x: x.pbest_fitness)
        
    def run(self):
        for i in range(MAX_ITERATION):
            for particle in self.population:
                particle.update_velocity(self.gbest)
                particle.update_position()
                particle.update_pbest()
                
            self.gbest = min(self.population, key=lambda x: x.pbest_fitness)
            
        return self.gbest.pbest

其中，cities是一个列表，表示每个城市的坐标，例如：

cities = [(0.1, 0.5), (0.6, 0.4), (0.3, 0.2), (0.7, 0.8), (0.9, 0.1)]

然后，可以创建一个PSO_TSP对象并调用其run方法，得到TSP问题的最优解。例如：

pso = PSO_TSP(cities)
solution = pso.run()

其中，solution是一个列表，表示最优解路径的顺序。