用Python实现粒子群算法(PSO)
粒子群算法是一种基于鸟类觅食开发出来的优化算法,它是从随机解出发,通过迭代寻找最优解,通过适应度来评价解的品质。
From 《An Improved PSO Algorithm to Optimize BP Neural Network》
PSO算法的搜索性能取决于其全局探索和局部细化的平衡,这在很大程度上依赖于算法的控制参数,包括粒子群初始化、惯性因子w、最大飞翔速度和加速常数与等。
PSO算法具有以下优点:
不依赖于问题信息,采用实数求解,算法通用性强。
需要调整的参数少,原理简单,容易实现,这是PSO算法的最大优点。
协同搜索,同时利用个体局部信息和群体全局信息指导搜索。
收敛速度快, 算法对计算机内存和CPU要求不高。
更容易飞越局部最优信息。对于目标函数仅能提供极少搜索最优值的信息,在其他算法无法辨别搜索方向的情况下,PSO算法的粒子具有飞越性的特点使其能够跨过搜索平面上信息严重不足的障碍,飞抵全局最优目标值。比如Generalized Rosenbrock函数全局最小值在原占附近.但是此函数全局最优值与可到达的局部最优值之间右一条独长的山路,曲面山谷中点的最速下降方向几乎与到函数最小值的最佳方向垂直,找到全局最小值的可能性微乎其微, 但是PSO算法完全有可能找到全局最优值。
同时, PSO算法的缺点也是显而易见的:
算法局部搜索能力较差,搜索精度不够高。
算法不能绝对保证搜索到全局最优解。
PSO算法设计的具体步骤如下:
- 初始化粒子群(速度和位置)、惯性因子、加速常数、最大迭代次数、算法终止的最小允许误差。
- 评价每个粒子的初始适应值。
- 将初始适应值作为当前每个粒子的局部最优值,并将各适应值对应的位置作为每个粒子的局部最优值所在的位置。
- 将最佳初始适应值作为当前全局最优值,并将最佳适应值对应的位置作为全局最优值所在的位置。
- 依据公式更新每个粒子当前的飞翔速度。
- 对每个粒子的飞翔速度进行限幅处理,使之不能超过设定的最大飞翔速度。
- 依据公式更新每个粒子当前所在的位置。
- 比较当前每个粒子的适应值是否比历史局部最优值好,如果好,则将当前粒子适应值作为粒子的局部最优值,其对应的位置作为每个粒子的局部最优值所在的位置。
- 在当前群中找出全局最优值,并将当前全局最优值对应的位置作为粒子群的全局最优值所在的位置。
- 重复步骤(5)~(9),直到满足设定的最小误差或最大迭代次数
- 输出粒子群的全局最优值和其对应的位置以及每个粒子的局部最优值和其对应的位置。
本文中我们假设要求解一个维度为10的向量,这里的适应度函数采用简单的线性误差求和。
1 #基本粒子群算法 2 #vi+1 = w*vi+c1*r1*(pi-xi)+c2*r2*(pg-xi) 速度更新公式 3 #xi+1 = xi + a*vi+1 位置更新公式(一般a=1) 4 #w = wmax -(wmax-wmin)*iter/Iter 权重更新公式 5 #iter当前迭代次数 Iter最大迭代次数 c1、c2学习因子 r1、r2随机数 pi粒子当前最优位置 pg粒子群全局最优 6 #初始化 wmax=0.9 wmin=0.4 通常c1=c2=2 Iter对于小规模问题(10,20)对于大规模(100,200) 7 #算法优劣取决于w、c1和c2,迭代结束的条件是适应度函数的值符合具体问题的要求 8 #初始化粒子群,包括尺寸、速度和位置 9 #本算法假设想要的输出是长度为10的矩阵,y=[1.7]*10,适应度函数f(x)= |x-y| <=0.001符合要求 10 11 import numpy as np 12 13 swarmsize = 500 14 partlen = 10 15 wmax,wmin = 0.9,0.4 16 c1 = c2 = 2 17 Iter = 400 18 19 def getwgh(iter): 20 w = wmax - (wmax-wmin)*iter/Iter 21 return w 22 23 def getrange(): 24 randompv = (np.random.rand()-0.5)*2 25 return randompv 26 27 def initswarm(): 28 vswarm,pswarm = np.zeros((swarmsize,partlen)),np.zeros((swarmsize,partlen)) 29 for i in range(swarmsize): 30 for j in range(partlen): 31 vswarm[i][j] = getrange() 32 pswarm[i][j] = getrange() 33 return vswarm,pswarm 34 35 def getfitness(pswarm): 36 pbest = np.zeros(partlen) 37 fitness = np.zeros(swarmsize) 38 for i in range(partlen): 39 pbest[i] = 1.7 40 41 for i in range(swarmsize): 42 yloss = pswarm[i] - pbest 43 for j in range(partlen): 44 fitness[i] += abs(yloss[j]) 45 return fitness 46 47 def getpgfit(fitness,pswarm): 48 pgfitness = fitness.min() 49 pg = pswarm[fitness.argmin()].copy() 50 return pg,pgfitness 51 52 vswarm,pswarm = initswarm() 53 fitness = getfitness(pswarm) 54 pg,pgfit = getpgfit(fitness,pswarm) 55 pi,pifit = pswarm.copy(),fitness.copy() 56 57 for iter in range(Iter): 58 if pgfit <= 0.001: 59 break 60 #更新速度和位置 61 weight = getwgh(iter) 62 for i in range(swarmsize): 63 for j in range(partlen): 64 vswarm[i][j] = weight*vswarm[i][j] + c1*np.random.rand()*(pi[i][j]-pswarm[i][j]) + c2*np.random.rand()*(pg[j]-pswarm[i][j]) 65 pswarm[i][j] = pswarm[i][j] + vswarm[i][j] 66 #更新适应值 67 fitness = getfitness(pswarm) 68 #更新全局最优粒子 69 pg,pgfit = getpgfit(fitness,pswarm) 70 #更新局部最优粒子 71 for i in range(swarmsize): 72 if fitness[i] < pifit[i]: 73 pifit[i] = fitness[i].copy() 74 pi[i] = pswarm[i].copy() 75 76 for j in range(swarmsize): 77 if pifit[j] < pgfit: 78 pgfit = pifit[j].copy() 79 pg = pi[j].copy() 80 print(pg) 81 print(pgfit)
下面的结果分别是迭代300次和400次的结果。
可以看到400次迭代虽然适应度没有达到预期,得到的向量已经很接近期望的结果了。
写在最后:粒子群算法最重要的参数就是惯性权重和学习因子,针对这两个参数有了新的优化粒子群算法(IPSO)。还有初始化粒子群时速度和位置范围的确定,包括种群的大小和迭代次数的选择,这些都是‘摸着石头过河’,没有标准答案。
上一篇: 用Python实现的粒子群优化算法及其实际运用探索
下一篇: 粒子群算法详解
推荐阅读
-
用 Python 实现支持向量机算法
-
用 python 实现冒泡排序算法的两种方法
-
粒子群算法和鲸鱼算法的比较(Matlab 代码实现 粒子群算法(带约束处理)--Python 和 Matlab 鲸鱼优化算法的实现(Matlab 实现)
-
SCI I | Matlab 实现 PSO-TCN-BiGRU-Attention 粒子群算法,优化多变量时间序列预测的时间卷积双向门控循环单元融合注意机制
-
追赶法/托马斯算法在常微分方程两点边值问题中的差分求解、紧差分求解(用 python 代码实现并作图)
-
回归预测 | Matlab实现PSO-BiLSTM-Attention粒子群算法优化双向长短期记忆神经网络融合注意力机制多变量回归预测
-
用Python实战:粒子群优化算法(PSO)第二部分 - 代码实例解析
-
用Python实现粒子群优化算法(附详细教程和示例代码) - 第四部分:算法实战
-
用C语言打造粒子群优化算法(PSO)详解教程
-
实操指南:用Python实现遗传算法的案例解析