粒子群算法python tsp

粒子群算法（Particle Swarm Optimization，PSO）是一种启发式优化算法，常用于解决旅行商问题（Traveling Salesman Problem，TSP）。以下是一个使用Python实现粒子群算法解决TSP问题的示例代码：

import numpy as np
import random

class Particle:
    def __init__(self, num_cities):
        self.position = np.random.permutation(num_cities)
        self.velocity = np.zeros(num_cities)
        self.best_position = self.position.copy()
        self.best_cost = float('inf')

def tsp_pso(cities, num_particles, num_iterations):
    num_cities = len(cities)
    particles = [Particle(num_cities) for _ in range(num_particles)]
    global_best_position = np.zeros(num_cities)
    global_best_cost = float('inf')

    for _ in range(num_iterations):
        for particle in particles:
            cost = calculate_cost(cities, particle.position)

            if cost < particle.best_cost:
                particle.best_position = particle.position.copy()
                particle.best_cost = cost

            if cost < global_best_cost:
                global_best_position = particle.position.copy()
                global_best_cost = cost

            update_velocity(particle, global_best_position)
            update_position(particle)

    return global_best_position, global_best_cost

def calculate_cost(cities, path):
    num_cities = len(cities)
    cost = 0

    for i in range(num_cities - 1):
        cost += cities[path[i]][path[i+1]]

    cost += cities[path[-1]][path[0]]  # Return to the starting city
    return cost

def update_velocity(particle, global_best_position):
    inertia_weight = 0.7
    cognitive_weight = 1.4
    social_weight = 1.4

    num_cities = len(particle.position)
    for i in range(num_cities):
        r1 = random.random()
        r2 = random.random()
        particle.velocity[i] = (inertia_weight * particle.velocity[i] +
                                cognitive_weight * r1 * (particle.best_position[i] - particle.position[i]) +
                                social_weight * r2 * (global_best_position[i] - particle.position[i]))

def update_position(particle):
    num_cities = len(particle.position)
    for i in range(num_cities):
        particle.position[i] += int(round(particle.velocity[i]))

        if particle.position[i] >= num_cities:
            particle.position[i] = num_cities - 1
        elif particle.position[i] < 0:
            particle.position[i] = 0

def main():
    cities = [[0, 10, 15, 20],
              [10, 0, 35, 25],
              [15, 35, 0, 30],
              [20, 25, 30, 0]]

    num_particles = 50
    num_iterations = 100

    best_path, best_cost = tsp_pso(cities, num_particles, num_iterations)
    print("Best path:", best_path)
    print("Best cost:", best_cost)

if __name__ == '__main__':
    main()

该代码使用粒子群算法来解决一个包含4个城市的旅行商问题。你可以根据实际问题自定义城市之间的距离矩阵，调整粒子数量和迭代次数。运行代码后将输出找到的最佳路径和成本。