算法背景
粒子群算法,也称粒子群优化算法或鸟群觅食算法(Particle Swarm Optimization),缩写为PSO。
粒子群优化算法是一种进化计算技术(evolutionary computation), 1995 年由Eberhart博士和
kennedy博士提出,源于对鸟群捕食的行为研究。
该算法最初是受到飞鸟集群活动的规律性启发,进而利用群体智能建立的一一个简化模型。粒
子群算法在对动物集群活动行为观察基础上,利用群体中的个体对信息的共享使整个群体的运动在
问题求解空间中产生从无序到有序的演化过程,从而获得最优解。
算法原理
1)假设在一个D维的目标搜索空间,有N个粒子组成一个群落,其中第i个粒子表示为1个D维的向量:
2)第一个粒子“飞行”速度也是一个D维向量,记为(粒子自身有一个方向):
3)在第t代的第i个粒子向第t+1代进化时,根据如下式子更新:
(粒子的一个惯性+自身个体方向+朝向目标方向)
(粒子更新的方向)
4)如下图:假设目前在C位置,个体极值位置B,全局最优A,该粒子下一步运动状态
B对应,A对应
。
每个粒子也有自己的极值位置。黄色为当前速度方向,绿色个体极值飞行步长,红色全局最值飞行步长
算法流程
输入:参数w 0.5-0.8,c1c2:0.1-2,:取决于优化函数
Step1:初始化种群x
Step2:计算个体适应度
Step3:更新粒子速度->更新粒子位置
Step4:计算新位置适应度,若新位置适应度更高,则将该粒子位置更新,否则不更新
Step5:判断是否满足终止条件,是否退出,否则返回2
输出:最优值
注:一般,我们优化目标是最小化的一个函数值,所以个体计算函数值越小,适应度越高
1、maxf = min -f(最小化问题)
2、更新速度后,先进性速度边界检测,v(v>vmax)=vmax,位置同理
3、常见终止条件为设定迭代进化次数,适应度n代不再变化等
算法分析
优点:
原理比较简单,实现容易,参数少。
缺点:
易早熟收敛至局部最优、迭代后期收敛速度慢的。
解释:
标准粒子群算法的参数是固定的。w描述的是粒子的“惯性”,在进化前期w应该大一些,保证
各个粒子独立飞行充分搜索空间,后期应该小一点,多向其他粒子学习。c1, c2分别向个体极值和
全局极值最大飞行步长。前期c1应该大一些,后期c2应该大一些, 这样就能平衡粒子的全局搜索
能力和局部搜索能力。3个参数共同影响了粒子的飞行方向,导致即使其他粒子找到更好的,但是
当前粒子惯性太大,不能很快的飞向更优的位置。
算法拓展
针对缺点改进
1)实现参数自适应变化
2)引入一些其他机制,比如随机的因素,速度,位置的边界变化-后期压缩最大速度等
3)结合其他智能优化算法:遗传算法、免疫算法、模拟退火等,帮助粒子跳出局部最优,改善收 敛速度
案例实操
求解
import numpy as np
import matplotlib.pyplot as plt# 目标函数
def f(x):return x * np.sin(x) * np.cos(2 * x) - 2 * x * np.sin(3 * x) + 3 * x * np.sin(4 * x)class Particle:def __init__(self, lower_bound, upper_bound, dim):self.position = np.random.uniform(lower_bound, upper_bound, dim)self.velocity = np.zeros(dim)self.best_position = self.position.copy()self.best_score = f(self.position)
class PSO:def __init__(self, swarm_size, lower_bound, upper_bound, dim, omega=0.5, c1=0.5, c2=0.5):self.swarm_size = swarm_sizeself.lower_bound = lower_boundself.upper_bound = upper_boundself.dim = dimself.omega = omegaself.c1 = c1self.c2 = c2self.swarm = [Particle(lower_bound, upper_bound, dim) for _ in range(swarm_size)]self.gbest_position = self.swarm[0].position.copy()self.gbest_score = self.swarm[0].best_scoredef update_gbest(self):for particle in self.swarm:if particle.best_score < self.gbest_score:self.gbest_score = particle.best_scoreself.gbest_position = particle.best_position.copy()def update_velocity_position(self):for particle in self.swarm:r1 = np.random.rand(self.dim)r2 = np.random.rand(self.dim)cognitive_velocity = self.c1 * r1 * (particle.best_position - particle.position)social_velocity = self.c2 * r2 * (self.gbest_position - particle.position)particle.velocity = self.omega * particle.velocity + cognitive_velocity + social_velocityparticle.position += particle.velocityparticle.position = np.clip(particle.position, self.lower_bound, self.upper_bound)particle_score = f(particle.position)if particle_score < particle.best_score:particle.best_score = particle_scoreparticle.best_position = particle.position.copy()def optimize(self, iterations):for _ in range(iterations):self.update_gbest()self.update_velocity_position()return self.gbest_position, self.gbest_score# PSO参数swarm_size = 30
iterations = 100
dim = 1 # 因为我们是在一维空间上搜索
lower_bound = 0
upper_bound = 50# 运行PSO
pso = PSO(swarm_size, lower_bound, upper_bound, dim)
best_position, best_score = pso.optimize(iterations)# 绘制函数图像和PSO找到的最小值点
x_values = np.linspace(0, 50, 1000)
y_values = f(x_values)plt.plot(x_values, y_values, label='f(x)')
plt.scatter(best_position, f(best_position), color='red', label='PSO Minimum')
plt.xlabel('x')
plt.ylabel('f(x)')
plt.title('Function f(x) and PSO Minimum')
plt.legend()
plt.grid(True)
plt.show()