姓名：方文 19021210911
【嵌牛导读】粒子群优化算法(Particle swarm optimization, PSO)是一种基于群体搜索的处理连续或者离散空间内优化问题的算法。
【嵌牛鼻子】优化算法 粒子群算法
【嵌牛提问】粒子群算法的主要思想
【嵌牛正文】
一、粒子群算法的概述
粒子群算法(particleswarm optimization，PSO)由Kennedy和Eberhart在1995年提出，该算法对于Hepper的模拟鸟群(鱼群)的模型进行修正，以使粒子能够飞向解空间，并在最好解处降落，从而得到了粒子群优化算法。同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。PSO的优势在于简单，容易实现，无需梯度信息，参数少，特别是其天然的实数编码特点特别适合于处理实优化问题。同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用。
粒子群算法(PSO)属于群智能算法的一种，是通过模拟鸟群捕食行为设计的。假设区域里就只有一块食物（即通常优化问题中所讲的最优解），鸟群的任务是找到这个食物源。鸟群在整个搜寻的过程中，通过相互传递各自的信息，让其他的鸟知道自己的位置，通过这样的协作，来判断自己找到的是不是最优解，同时也将最优解的信息传递给整个鸟群，最终，整个鸟群都能聚集在食物源周围，即我们所说的找到了最优解，即问题收敛。
二、粒子群算法的流程
初始化过程
初始化常数和各记录矩阵：
代价函数计算函数CostFunction; 代价函数参数数目nVar; 代价函数各参数上下界(即粒子位置的边界)[VarMin,VarMax]
最大迭代次数iter_max
粒子群体的数量nPop
粒子速度边界[VelMin,VelMax]
单粒子最优加速常数C1
全局最优加速常数C2(一般取C1=C2∈[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矩阵后，按下公式更新粒子的速度：
Vi+1=WVi+C1R1(Pi−Xi)+C2R2(G−Xi)V(i+1) = WVi + C1R1(Pi-Xi) + C2R2(G-Xi)
其中，W为惯性因子，表征粒子维持原速不变的能力；C1为单粒子加速常数，表征粒子向他自己历史最优解出加速的能力；C2位全局最优加速常数，表征粒子向当前全局最优解处加速的能力；R1、R2为两个0到1之间的随机数。
计算完速度之后注意要限制速度边界，一旦速度大于边界值，令其等于边界值。
更新速度之后，应该计算粒子下一次的位置，并保存为当前粒子位置：
Xi+1=Xi+Vi+1X(i+1) = Xi + V(i+1)
同理，计算完位置后也要限制边界。
循环迭代和输出
循环迭代计算代价函数和更新速度和位置，达到最大代数之后输出结果即可。
在使用面向对象的语言实现该算法的时候，可以定义粒子这一对象，其应具有属性：当前位置、当前速度、当前代价值、历史最优位置、历史最优代价值，应具有方法：速度更新方法、位置更新方法、代价值更新方法。
代码实现
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()
