PSO求最短路径的python

粒子群优化（Particle Swarm Optimization，PSO）是一种模拟鸟群觅食行为的优化算法。它通过群体中粒子的协作和信息共享来寻找最优解。PSO可以用于求解最短路径问题，例如旅行商问题（TSP）。

以下是一个使用PSO求解最短路径的Python示例代码：

import numpy as np

class PSO:
    def __init__(self, num_particles, num_iterations, distance_matrix):
        self.num_particles = num_particles
        self.num_iterations = num_iterations
        self.distance_matrix = distance_matrix
        self.num_cities = len(distance_matrix)
        self.particles = np.array([np.random.permutation(self.num_cities) for _ in range(num_particles)])
        self.velocities = np.zeros((num_particles, self.num_cities))
        self.personal_best = self.particles.copy()
        self.personal_best_scores = np.array([self.fitness(particle) for particle in self.particles])
        self.global_best = self.particles[self.personal_best_scores.argmin()].copy()
        self.global_best_score = self.personal_best_scores.min()

    def fitness(self, particle):
        return sum(self.distance_matrix[particle[i], particle[(i + 1) % self.num_cities]] for i in range(self.num_cities))

    def update_velocities(self, inertia_weight, cognitive_constant, social_constant):
        r1 = np.random.rand(self.num_particles, self.num_cities)
        r2 = np.random.rand(self.num_particles, self.num_cities)
        cognitive_term = cognitive_constant * r1 * (self.personal_best - self.particles)
        social_term = social_constant * r2 * (self.global_best - self.particles)
        self.velocities = inertia_weight * self.velocities + cognitive_term + social_term

    def update_particles(self):
        self.particles = np.array([self.swap_operator(particle, velocity) for particle, velocity in zip(self.particles, self.velocities)])

    def swap_operator(self, particle, velocity):
        for i in range(self.num_cities):
            if np.random.rand() < sigmoid(velocity[i]):
                j = np.random.randint(self.num_cities)
                particle[i], particle[j] = particle[j], particle[i]
        return particle

    def optimize(self):
        for _ in range(self.num_iterations):
            self.update_velocities(inertia_weight=0.5, cognitive_constant=1, social_constant=2)
            self.update_particles()
            scores = np.array([self.fitness(particle) for particle in self.particles])
            for i in range(self.num_particles):
                if scores[i] < self.personal_best_scores[i]:
                    self.personal_best[i] = self.particles[i].copy()
                    self.personal_best_scores[i] = scores[i]
                    if scores[i] < self.global_best_score:
                        self.global_best = self.particles[i].copy()
                        self.global_best_score = scores[i]

        return self.global_best, self.global_best_score

def sigmoid(x):
    return 1 / (1 + np.exp(-x))

# 示例使用
distance_matrix = np.array([
    [0, 2, 9, 10],
    [1, 0, 6, 4],
    [15, 7, 0, 8],
    [6, 3, 12, 0]
])

pso = PSO(num_particles=10, num_iterations=100, distance_matrix=distance_matrix)
best_path, best_score = pso.optimize()
print("最短路径:", best_path)
print("最短距离:", best_score)

这个示例代码展示了如何使用PSO算法求解最短路径问题。首先定义了一个PSO类，并在其中实现了粒子初始化、速度更新、粒子更新和适应度计算等方法。然后在`optimize`方法中迭代更新粒子位置和速度，并找到全局最优解。