基本介绍
粒子群优化算法(Particle swarm optimization, PSO)是一种基于群体搜索的处理连续或者离散空间内优化问题的算法。
粒子群算法使用在解空间中不断移动的粒子作为寻优的群体，每个粒子具有位置和速度两个属性(位置和速度的维数和解空间的维数相同)，粒子的位置代表了某个可行解，速度代表了与下一个寻找到的可行解的差值。
每个粒子根据自己已经寻找过的最优解和群体当前寻找到的最优解来调整自己的速度(按某种特定规则)，以搜索到更优的解。
粒子群算法的基本过程
总体过程
初始化过程
初始化常数和各记录矩阵：
- 代价函数计算函数CostFunction; 代价函数参数数目nVar; 代价函数各参数上下界(即粒子位置的边界)[VarMin,VarMax]
- 最大迭代次数iter_max
- 粒子群体的数量nPop
- 粒子速度边界[VelMin,VelMax]
- 单粒子最优加速常数C1
- 全局最优加速常数C2(一般取 C 1 = C 2 ∈ [ 0 , 4 ] C1=C2\in[0,4] C1=C2∈[0,4])
- 惯性因子W
- 粒子位置记录矩阵PopPosition(nPop行nVar列，每一行是一个粒子的位置坐标)
- 粒子速度记录矩阵PopVelocity(nPop行nVar列，每一行是一个粒子的速度各分量)
- 单粒子历史最优位置记录矩阵Pbest(nPop行nVar列，每一行是一个粒子历史最优位置坐标)
- 全局历史最优位置记录矩阵Gbest(一行nVar列，只记录最最优解)
- 历史最优值记录矩阵(iter_max行一列，每一代的最优解值)
初始化粒子位置和速度：
在粒子的解空间中随机初始化各粒子的位置；在粒子各个速度分量的范围内随机初始化各粒子的初速度。
计算代价函数
计算各粒子当前位置对应的代价函数值，并与该粒子历史最优解比较，更新Pbest矩阵；同时与Gbest比较，更新Gbest值；并更新历史最优值记录矩阵
更新速度和位置
在更新Pbest矩阵和Gbest矩阵后，按下公式更新粒子的速度：
V i + 1 = W V i + C 1 R 1 ( P i − X i ) + C 2 R 2 ( G − X i ) V_{i+1} = WV_i + C_1R_1(P_i-X_i) + C_2R_2(G-X_i) Vi+1=WVi+C1R1(Pi−Xi)+C2R2(G−Xi)
其中，W为惯性因子，表征粒子维持原速不变的能力；C1为单粒子加速常数，表征粒子向他自己历史最优解出加速的能力；C2位全局最优加速常数，表征粒子向当前全局最优解处加速的能力；R1、R2为两个0到1之间的随机数。
计算完速度之后注意要限制速度边界，一旦速度大于边界值，令其等于边界值。
更新速度之后，应该计算粒子下一次的位置，并保存为当前粒子位置：
X i + 1 = X i + V i + 1 X_{i+1} = X_i + V_{i+1} Xi+1=Xi+Vi+1
同理，计算完位置后也要限制边界。
循环迭代和输出
循环迭代计算代价函数和更新速度和位置，达到最大代数之后输出结果即可。
在使用面向对象的语言实现该算法的时候，可以定义粒子这一对象，其应具有属性：当前位置、当前速度、当前代价值、历史最优位置、历史最优代价值，应具有方法：速度更新方法、位置更新方法、代价值更新方法。
代码实现
用粒子群算法接着算这个函数的：最小值
f ( x , y ) = − 20 e − 0.2 x 2 + y 2 2 − e c o s 2 π x + c o s 2 π y 2 + 20 + e f(x,y) = -20 e^{-0.2 \sqrt{\frac{x^2+y^2}{2}}} - e^{\frac{cos \ 2 \pi x \ +\ cos \ 2\pi y}{2}} + 20 + e f(x,y)=−20e−0.22x2+y2
−e2cos 2πx + cos 2πy+20+e
这个神一般的函数在区间 [ − 4 , 4 ] [-4,4] [−4,4]上的最小值。该函数的图像如下，根据图像易知最小值点为 ( 0 , 0 ) (0,0) (0,0)，最小值为0。
Python代码如下：
#使用蜂群算法计算这个函数f = @(x,y) -20.*exp(-0.2.*sqrt((x.^2+y.^2)./2))-exp((cos(2.*pi.*x)+cos(2.*pi.*y))./2)+20+exp(1)在区间[-4,4]上的最小值
#它真正的最小值点是(0,0)
import numpy as np
import matplotlib.pyplot as plt
#定义待优化函数：只能处理行向量形式的单个输入，若有矩阵形式的多个输入应当进行迭代
def CostFunction(input):
x = input[0]
y = input[1]
result = -20*np.exp(-0.2*np.sqrt((x*x+y*y)/2))- \
np.exp((np.cos(2*np.pi*x)+np.cos(2*np.pi*y))/2)+20+np.exp(1)
return result
#初始化各参数
nVar = 2
VarMin = -4 #求解边界
VarMax = 4
VelMin = -8 #速度边界
VelMax = 8
nPop = 40
iter_max = 100 #最大迭代次数
C1 = 2 #单粒子最优加速常数
C2 = 2 #全局最优加速常数
W = 0.5 #惯性因子
Gbest = np.inf #全局最优
History = np.inf*np.ones(iter_max) #历史最优值记录
#定义“粒子”类
class Particle(object):
#初始化粒子的所有属性
def __init__(self):
self.Position = VarMin + (VarMax-VarMin)*np.random.rand(nVar)
self.Velocity = VelMin + (VelMax-VelMin)*np.random.rand(nVar)
self.Cost = np.inf
self.Pbest = self.Position
self.Cbest = np.inf
#根据当前位置更新代价值的方法
def UpdateCost(self):
global Gbest
self.Cost = CostFunction(self.Position)
if self.Cost < self.Cbest:
self.Cbest = self.Cost
self.Pbest = self.Position
if self.Cost < Gbest:
Gbest = self.Cost
#根据当前速度和单粒子历史最优位置、全局最优位置更新粒子速度
def UpdateVelocity(self):
global Gbest
global VelMax
global VelMin
global nVar
self.Velocity = W*self.Velocity + C1*np.random.rand(1)\
*(self.Pbest-self.Position) + C2*np.random.rand(1)\
*(Gbest-self.Position)
for s in range(nVar):
if self.Velocity[s] > VelMax:
self.Velocity[s] = VelMax
if self.Velocity[s] < VelMin:
self.Velocity[s] = VelMin
#更新粒子位置
def UpdatePosition(self):
global VarMin
global VarMax
global nVar
self.Position = self.Position + self.Velocity
for s in range(nVar):
if self.Position[s] > VarMax:
self.Position[s] = VarMax
if self.Position[s] < VarMin:
self.Position[s] = VarMin
#初始化粒子群
Group = []
for j in range(nPop):
Group.append(Particle())
#开始迭代
for iter in range(iter_max):
for j in range(nPop):
Group[j].UpdateCost()
if Group[j].Cost < History[iter]:
History[iter] = Group[j].Cost
for j in range(nPop):
Group[j].UpdateVelocity()
Group[j].UpdatePosition()
#输出结果
print(Gbest)
for i in range(nPop):
if i % 5 == 0:
print("这是最后的第i个粒子：",Group[i].Position, Group[i].Cost)
y = History.tolist()
x = [i for i in range(iter_max)]
plt.plot(x,y)
plt.show()
输出如下：
收敛图如下：
在实际代码操作过程中，W取1的时候算法发散，只有W取0.5的时候算法收敛，下面是别人的研究成果：