粒子群优化(Particle Swarm Optimization, PSO)是一种基于群体智能的优
化算法,它通过模拟鸟群觅食行为中的信息共享机制来实现优化问题的求解。
下面是一个使用 Python 实现的基本粒子群算法的求解 10 城市 TSP 问题的示例
代码:
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial.distance import cdist
# 粒子类
class Particle:
def __init__(self, cities, init_order=None):
self.cities = cities
self.order = np.arange(cities.shape[0]) if init_order is None
else init_order
self.best_order = self.order.copy()
self.best_cost = self.calculate_cost()
def calculate_cost(self):
# 计算路径总长度
distances = cdist(self.cities, self.cities)
route_cost = sum(distances[self.order[:-1], self.order[1:]])
+ distances[self.order[-1], self.order[0]]
return route_cost
def update_velocity(self, gbest_order):
# 对于 TSP,速度是交换两个城市的概率,这里简化处理
pass # 在 TSP 中通常不使用速度概念,因此留空
def update_position(self, gbest_order):
# 随机交换两个城市的位置作为新的解
idx1, idx2 = np.random.choice(len(self.order), 2,
replace=False)
self.order[idx1], self.order[idx2] = self.order[idx2],
self.order[idx1]
current_cost = self.calculate_cost()
if current_cost < self.best_cost:
self.best_cost = current_cost
self.best_order = self.order.copy()