粒子群算法（PSO算法）求解实例---旅行商问题 (TSP)

一、采用PSO求解 (TSP)
二、旅行商问题
- 2.1 实际例子：求解 6 个城市的 TSP
- 2.2 ==**求解该问题的代码**==
- 2.3 代码运行过程截屏
- 2.4 代码运行结果截屏（后续和其他算法进行对比）
三、 ==如何修改代码？==
- 3.1 减少城市坐标，如下：
- 3.2 增加城市坐标，如下：
四、PSO粒子群算法原理
- 4.1 PSO算法定义
- 4.2 PSO算法的基本思想
- 4.3 PSO算法的工作原理
- 4.4 PSO算法的参数
- 4.5 PSO算法的优缺点
- - 4.5.1 优点
  - 4.5.2 缺点
- 4.6 PSO算法的应用场景

一、采用PSO求解 (TSP)

求解代码在文中，后续会出其他算法求解TSP问题，你们参加数学建模竞赛只需要会改代码即可。

用来对比此专栏的遗传算法（GA算法）求解实例—旅行商问题 (TSP)，注意每次运行PSO算法得到的结果可能不太一样。

我知道大家对原理性的东西不感兴趣，我把原理性的东西放在后面，大家如果需要写数模论文可以拿去，但是记得需要改一改，要不然查重过不去。

二、旅行商问题

2.1 实际例子：求解 6 个城市的 TSP

假设有 6 个城市，其坐标如下：

城市	X 坐标	Y 坐标
0	10	20
1	30	40
2	20	10
3	40	30
4	10	10
5	50	20

目标是找到一个经过所有城市且总距离最短的路径。

2.2 求解该问题的代码

import numpy as np
import random# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30],[10, 10],[50, 20]
])# 计算两城市之间的欧几里得距离
def calculate_distance(city1, city2):return np.sqrt(np.sum((city1 - city2) ** 2))# 计算总旅行距离
def total_distance(path):distance = 0for i in range(len(path) - 1):distance += calculate_distance(cities[path[i]], cities[path[i + 1]])distance += calculate_distance(cities[path[-1]], cities[path[0]])  # 回到起点return distance# 粒子群优化算法主函数
def pso_tsp(cities, num_particles=30, max_iter=500, w=0.5, c1=1.5, c2=1.5):num_cities = len(cities)# 初始化粒子群particles = [np.random.permutation(num_cities).tolist() for _ in range(num_particles)]velocities = [random.sample(range(num_cities), 2) for _ in range(num_particles)]  # 初始化每个粒子的速度为两两交换# 初始化每个粒子的历史最佳位置和全局最佳位置p_best = particles.copy()p_best_scores = [total_distance(p) for p in particles]g_best = p_best[np.argmin(p_best_scores)]g_best_score = min(p_best_scores)for iteration in range(max_iter):for i in range(num_particles):# 更新每个粒子的速度r1, r2 = random.random(), random.random()swap_prob = w * np.array(velocities[i]) \+ c1 * r1 * np.random.randint(0, num_cities, size=2) \+ c2 * r2 * np.random.randint(0, num_cities, size=2)# 随机选择两个位置进行交换操作swap_idx = np.argsort(swap_prob)[:2]particles[i][swap_idx[0]], particles[i][swap_idx[1]] = particles[i][swap_idx[1]], particles[i][swap_idx[0]]# 评估新位置current_distance = total_distance(particles[i])# 更新历史最佳位置if current_distance < p_best_scores[i]:p_best[i] = particles[i].copy()p_best_scores[i] = current_distance# 更新全局最佳位置if current_distance < g_best_score:g_best = particles[i].copy()g_best_score = current_distanceprint(f"Iteration {iteration} Best distance: {g_best_score:.2f}")return g_best, g_best_score# 运行粒子群优化算法
best_path, best_distance = pso_tsp(cities)
print("Best path:", best_path)
print("Best distance:", best_distance)

2.3 代码运行过程截屏

在这里插入图片描述

2.4 代码运行结果截屏（后续和其他算法进行对比）

在这里插入图片描述

三、如何修改代码？

这一部分是重中之重，大家参加数学建模肯定是想跑出自己的结果，所以大家只需要把自己遇到的数学问题，抽象成TSP问题，然后修改代码的城市坐标，然后运行即可。

# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30],[10, 10],[50, 20]
])

3.1 减少城市坐标，如下：

# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30]
])

3.2 增加城市坐标，如下：

# 定义城市坐标
cities = np.array([[10, 20],[30, 40],[20, 10],[40, 30],[30, 40],[20, 10],[10, 10],[50, 20]
])

四、PSO粒子群算法原理

4.1 PSO算法定义

粒子群优化算法 (Particle Swarm Optimization, PSO) 是一种基于群体智能的优化算法，由 Kennedy 和 Eberhart 在 1995 年提出。PSO 模拟了鸟群或鱼群的群体行为，通过个体之间的信息共享和相互学习，搜索解空间以找到问题的最优解。PSO 被广泛应用于函数优化、机器学习、神经网络训练、路径规划等领域。

4.2 PSO算法的基本思想

粒子群优化算法的核心思想是利用群体中各个“粒子”的位置和速度来表示可能的解，粒子在搜索空间中移动，受其自身经验（历史最优位置）和群体经验（全局最优位置）的影响。在迭代过程中，每个粒子根据当前的速度、历史最佳位置和全局最佳位置来调整自己的位置，从而逐步逼近最优解。

4.3 PSO算法的工作原理

初始化种群：随机初始化一组粒子的位置和速度，每个粒子代表问题的一个潜在解。
计算适应度值：根据适应度函数（目标函数）计算每个粒子的适应度值，评价粒子的优劣。
更新个体最佳位置和全局最佳位置：
- 每个粒子记录其迄今为止找到的最佳位置（个体最佳位置 p_best）。
- 记录群体中的最佳位置（全局最佳位置 g_best）。
更新速度和位置：
- 粒子的速度根据以下公式更新：
  $v_{i}(t+1) = w \cdot v_{i}(t) + c_{1} \cdot r_{1} \cdot (p_{i\_best} - x_{i}(t)) + c_{2} \cdot r_{2} \cdot (g_{best} - x_{i}(t))$
  其中：
  - $v_{i}(t)$ 表示粒子 (i) 在第 (t) 次迭代的速度。
  - $x_{i}(t)$ 表示粒子 (i) 在第 (t) 次迭代的位置。
  - $w$ 是惯性权重，控制粒子保持其当前速度的趋势。
  - $c_{1}, c_{2}$ 是加速度常数，分别表示粒子向个体最佳位置和全局最佳位置移动的加速因子。
  - $r_{1}, r_{2}$ 是介于 0 和 1 之间的随机数，增加搜索的随机性。
- 粒子的位置根据以下公式更新：
  $x_{i}(t+1) = x_{i}(t) + v_{i}(t+1)$
重复迭代：重复步骤 2-4，直到满足终止条件（如达到最大迭代次数或找到满意解）。