粒子群算法(PSO)基本思想
粒子群(PSO)算法最早是由美国电气工程师Eberhart和社会心理学家Kennedy在1995年基于群鸟觅食提出来的。
群鸟觅食其实是一个**决策的过程, 与人类决策的过程相似。Boyd和Re chars on探索了人类的决策过程,并提出了个体学习和文化传递的概念。根据他们的研究成果,人们在决策过程中常常会综合两种重要的信息:第一种是他们自己的经验,即他们根据以前自己的尝试和经历,已经积累了一定的经验,知道怎样的状态会比较好;第二种是其他人的经验,即从周围人的行为获取知识,从中知道哪些选择是正面的,哪些选择是消极的。
同样的道理,群鸟在觅食的过程中,每只鸟的初始状态都处于随机位置,且飞翔的方向也是随机的。每只鸟都不知道食物在哪里,但是随着时间的推移,这些初始处于随机位置的鸟类通过群内相互学习、信息共享和个体不断积累字觅食物的经验,自发组织积聚成一个群落,并逐渐朝唯一的目标-—食物前进。每只鸟能够通过一定经验和信息估计目前所处的位置对于能寻找到食物有多大的价值,即多大的适应值;每只鸟能够记住自己所找到的最好位置,称之为局部最优(p best) 。此外, 还能记住群鸟中所有个体所能找到的最好位置, 称为全局最优(g best) , 整个鸟群的觅食中心都趋向全局最优移动, 这在生物学上称之为“同步效应”。通过鸟群觅食的位置不断移动,即不断迭代,可以使鸟群朝食物步步进逼。
在群鸟觅食模型中,每个个体都可以被看成一个粒子,则鸟群可以被看成一个粒子群。假设在一个D维的目标搜索空间中,有m个粒子组成一个群体,其中第i个粒子(i=1,2,…,m)位置表示为 X i = ( x i 1 , x i 2 , … , x i D ) X_{i}=(x_{i}^{1},x_{i}^{2},…,x_{i}^{D}) Xi=(xi1,xi2,…,xiD),即第i个粒子在D维搜索空间中的位置是 X i X_{i} Xi。换言之,每个粒子的位置就是一个潜在解,将X,代人目标函数就可以计算出其适应值,根据适应值的大小衡量其优劣。粒子个体经历过的最好位置记为 P i = ( P i 1 , P i 2 , … , P i D ) P_{i}=(P_{i}^{1},P_{i}^{2},…,P_{i}^{D}) Pi=(Pi1,Pi2,…,PiD),整个群体所有粒子经历过的最好位置记为 P g = ( p g 1 , p g 2 , … , p g D ) P_{g}=(p_{g}^{1},p_{g}^{2},…,p_{g}^{D}) Pg=(pg1,pg2,…,pgD)。粒子i的速度记为 V i = ( v i 1 , v i 2 , … , v i D ) V_{i}=(v_{i}^{1},v_{i}^{2},…,v_{i}^{D}) Vi=(vi1,vi2,…,viD)。
粒子群算法采用下列公式对粒子所在的位置不断更新(单位时间1):
v i d = ω v i d + c 1 r 1 ( p i d − x i d ) + c 2 r 2 ( p g d − x i d ) ( 8 − 1 ) v_{i}^{d}=\omega v_{i}^{d}+c_{1}r_{1}(p_{i}^{d}-x_{i}^{d})+ c_{2}r_{2}(p_{g}^{d}-x_{i}^{d}) (8-1) vid=ωvid+c1r1(pid−xid)+c2r2(pgd−xid)(8−1)
x i d = x i d + α v i d ( 8 − 2 ) x_{i}^{d}= x_{i}^{d}+\alpha v_{i}^{d} (8-2) xid=xid+αvid(8−2)
其中,i=1,2,…m;d=1,2,…,D;w是非负数、称为惯性因子;加速常数c:和ca是非负常数; r 1 r_{1} r1和 r 2 r_{2} r2是[0,1]范围内变换的随机数;α称为约束因子,目的是控制速度的权重。
此外, v i d ∈ [ − v m a x d , v m a x d ] v_{i}^{d}\in [-v_{max}^{d},v_{max}^{d}] vid∈[−vmaxd,vmaxd] 即粒子i的飞翔速度V, 被一个最大速度 V m a x = ( v m a x 1 , v m a x 2 , … , v m a x D ) V_{max}=(v_{max}^{1},v_{max}^{2},…,v_{max}^{D}) Vmax=(vmax1,vmax2,…,vmaxD)所限制。如果当前时刻粒子在某维的速度 v 1 d v_{1}^{d} v1d更新后超过该维的最大飞翔速度 v m a x d v_{max}^{d} vmaxd则当前时刻该维的速度被限制在 v m a x d v_{max}^{d} vmaxd 。 v m a x v_{max} vmax为常数, 可以根据不同的优化问题设定。
迭代终止条件根据具体问题设定,一般达到预订最大迭代次数或粒子群且前为止搜索到的最优位置满足目标函数的最小允许误差。
PSO算法的优化
近年来, 一些学者将PSO算法推广到约束优化问题,其关键在于如何处理好约束, 即解的可行性。如果约束处理得不好,其优化的结果往往会出现不能收敛和结果是空集的状况。基于PSO算法的约束优化工作主要分为两类:
- ①罚函数法。罚函数的目的是将约束优化问题转化成无约束优化问题。
- ②将粒子群的搜索范围都限制在条件约束簇内,即在可行解范围内寻优。
图解Python数据结构与算法-实战篇

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/81137.html