python粒子群算法实现tsp

以下是使用Python实现粒子群算法解决TSP问题的代码示例：

import numpy as np
import random

# 计算两个城市之间的距离
def distance(city1, city2):
    return np.sqrt((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2)

# 计算路径的总长度
def path_length(path, cities):
    length = 0
    for i in range(len(path) - 1):
        length += distance(cities[path[i]], cities[path[i+1]])
    length += distance(cities[path[-1]], cities[path[0]])
    return length

# 初始化粒子群
def init_swarm(num_particles, num_cities):
    swarm = []
    for i in range(num_particles):
        path = list(range(num_cities))
        random.shuffle(path)
        swarm.append(path)
    return swarm

# 更新粒子群
def update_swarm(swarm, cities, w, c1, c2):
    global_best_path = min(swarm, key=lambda x: path_length(x, cities))
    for i in range(len(swarm)):
        particle = swarm[i]
        velocity = np.zeros(len(particle), dtype=int)
        for j in range(len(particle)):
            r1, r2 = random.random(), random.random()
            velocity[j] = w * particle[j] + c1 * r1 * (global_best_path[j] - particle[j]) + c2 * r2 * (swarm[i-1][j] - particle[j])
        particle += velocity
        swarm[i] = particle
    return swarm

# 粒子群算法求解TSP问题
def pso_tsp(cities, num_particles=50, num_iterations=100, w=0.5, c1=1, c2=1):
    swarm = init_swarm(num_particles, len(cities))
    for i in range(num_iterations):
        swarm = update_swarm(swarm, cities, w, c1, c2)
    best_path = min(swarm, key=lambda x: path_length(x, cities))
    return best_path, path_length(best_path, cities)

# 示例
cities = [(60, 200), (180, 200), (80, 180), (140, 180), (20, 160), (100, 160), (200, 160), (140, 140), (40, 120), (100, 120), (180, 100), (60, 80), (120, 80), (180, 60), (20, 40), (100, 40), (200, 40), (20, 20), (60, 20), (160, 20)]
best_path, length = pso_tsp(cities)
print("最短路径：", best_path)
print("路径长度：", length)