Particle Swarm Optimization(PSO,粒子群优化算法)

群智能化算法

• 根据大自然及物种的自然规律及行为规律衍生而来的算法

  • 遗传算法(GA)
    • 物竞天择，设计染色体编码，根据适应值函数进行染色体选择、交叉和变异操作，优化求解
  • 人工神经网络(ANN)
    • 模仿生物神经元，透过神经元的信息传递、训练学习、联想，优化求解
  • 模拟退火算法(SA)
    • 模仿金属物质退火过程
  • 蚁群优化算法
  • 狼群优化算法

• 背景：人工生命

  人工是名是来研究具有某些生命基本特征的人工系统，包括两个方面:

  1、研究如何利用计算技术研究生物现象

  2、研究如何利用生物技术研究计算问题

---

PSO

发展历史

由Kennedy和Eberhart于1995年提出了一种新的全局优化金花算法，也是一种非常有效而被广泛应用的敌人待优化算法，该算法模拟鸟群飞行觅食行为，通过鸟之间的集体协同使群体达到最优。

而PSO基本算法有以下优缺点：

• 优点：
  • PSO算法没有交叉和编译运算，依靠粒子速度完成搜索，并且在迭代进化中只有最优的粒子把信息传递给其他粒子，搜索速度快。
  • PSO算法具有记忆性，粒子群体的历史最好位置可以记忆并传递给其他粒子
  • 需调整的参数较少，结构简单，易于工程实现
  • 采用实数编码，直接由问题的解决定，问题解的变量数直接作为粒子的维数
• 缺点：
  • 容易陷入局部最优，导致收敛精度低和不易收敛
  • 不能有效解决离散及组合优化问题
  • 不能有效求解一些非直角坐标系描述问题，如有关能量场或场内粒子运动规律的求解问题(这些求解空间的边界大部分是基于极坐标、球坐标或柱坐标)

Shi Y H.于1998年建立了PSO算法的惯性权重模型，惯性权重的引入，提高了算法的全局搜索能力。

Suganthan P N.提出了带邻域操作的PSO模型，客服了PSO模型在优化搜索后期随迭代次数增加搜索结果无明显改进的缺点。

Parsopoulos K E.提出将拉伸技术用于PSO最小化问题的求解，力图避免PSO算法易陷入局部最小值的问题。

高海兵等人针对PSO一直未能有效解决离散及组合优化问题，提出了一种广义粒子群优化模型（CPSO），该模型的鲁棒性和通用性还有待进一步的证明。

基本PSO

基本思想

粒子群算法的思想源于鸟群捕食行为的研究，模拟鸟群飞行觅食的行为，鸟之间通过集体协作使群体达到最有目的， 是一种基于Swarm Intelligence的优化方法。

场景：一群鸟在随机搜索食物

已

知

=

{

在

这

块

区

域

里

只

有

一

块

食

物

所

有

鸟

都

不

知

道

食

物

在

哪

但

它

们

能

感

受

到

当

前

的

位

置

离

食

物

还

有

多

远

已知=\left\{ \begin{aligned} &在这块区域里只有一块食物 \\ &所有鸟都不知道食物在哪 \\ &但它们能感受到当前的位置离食物还有多远 \end{aligned} \right.

已知=⎩⎪⎨⎪⎧​​在这块区域里只有一块食物所有鸟都不知道食物在哪但它们能感受到当前的位置离食物还有多远​

那么：找到食物的最优策略是什么？

方法：搜寻目前离食物最近的鸟的周围区域，根据自己飞行的经验判断食物的缩在

PSO正是从这种模型中得到启发，因此PSO的基础是：信息的社会共享

算法介绍

• 每个寻优的问题解都被想象成一只鸟，称“粒子”，所有粒子都在一个D维空间内进行搜索
• 所有粒子都有一个fitness function确定适应值以判断目前的位置好坏
• 每个粒子必须赋予记忆功能，能记住所搜寻到的最佳位置
• 每个粒子还有一个速度以决定飞行的距离和方向，这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整。

D维空间中，有N个粒子：

​ 粒子i位置：x_i=(x_i1,x_i2,…,x_iD)，将x_i代入适应函数f(x_i)求适应值；

​ 粒子速度：v₁=(v_i1,v_i2,…,v_iD)

​ 粒子 i 个体经历过的最好位置：pbest_i=(p_i1，p_i2，…,p_iD)

​ 粒子种群所经历过的最好位置：gbest=(g₁,g₂,…,g_D)

通常，在第d（1<= d <= D）维的位置变化范围限定在[X_MIN,d,X_MAX,d]内，速度变化范围限定在[-V_max,d,V_max,d]

即若在迭代过程中若v_id、x_id超出边界值，则该速度或者位置应该被限制为最大速度或者边界位置。

粒子 i 的第d维速度更新公式：

v

i

d

k

=

w

v

i

d

k

−

1

+

c

1

r

1

(

p

b

e

s

t

i

d

−

x

i

d

k

−

1

)

+

c

2

r

2

(

g

b

e

s

t

d

−

x

i

d

k

−

1

)

v^k_{id}=wv^{k-1}_{id}+c_1r_1(pbest_{id}-x^{k-1}_{id})+c_2r_2(gbest_d-x^{k-1}_{id})

vidk​=wvidk−1​+c1​r1​(pbestid​−xidk−1​)+c2​r2​(gbestd​−xidk−1​)

• 粒子速度更新公式包含3个部分：

  1.粒子先前的速度

  2.个体“认知”部分，表示粒子本身的思考，可理解为粒子 i 当前位置也自己最好位置之间的距离

  3.“社会认知”部分，表示粒子间的信息共享与合作，可以理解为粒子 i 当前位置与群体最好位置之间的距离

粒子 i 的第d维位置更新公式：

x

i

d

k

=

x

i

d

k

−

1

+

v

i

d

k

−

1

x^k_{id}=x^{k-1}_{id}+v^{k-1}_{id}

xidk​=xidk−1​+vidk−1​

v

i

d

k

v^k_{id}

vidk​——第k次迭代粒子i飞行速度矢量的第d维向量

x

i

d

k

x^k_{id}

xidk​——第k次迭代粒子i位置矢量的第d维向量

c

1

,

c

2

c_1,c_2

c1​,c2​——加速度常数，调节学习最大步长，也称为学习因子。

c

1

=

0

c_1=0

c1​=0，则只有社会，没有自我，丧失群体多样性，易于陷入局部最优而无法跳出。

r

1

,

r

2

r_1,r_2

r1​,r2​——两个随机函数，取值范围[0，1]，以增加搜索随机性

w

w

w——惯性权重，非负数，调节对解空间的搜索范围

最大速度V_max：

1.V_max较大时，探索能力增强，但是粒子容易飞过最优解

2.V_max较小时，开发能力增强，但容易陷入局部最优

3.V_max一般设为每维变量变化范围的10%~20%

算法流程

//功能：粒子群优化算法伪代码
//说明: 本粒以求问题最小值为目标
//参数： N为群体规模
procedure PSO
	for each particle i
		Initialize velocity Vi and position Xi for particle i
		Evaluate particle i and set pBesti = Xi
	end for
	gBest = min{pBesti}
	while not stop
		for i = 1:N
			Update the velocity and position of praticle i
			Evaluate particle i
			if fit(xi) < fit(pBesti)
				pBesti = Xi;
			if fit(pBesti) < fit(gBest)
				gBest = pBesti;
		end for
	end while
	print gBest
end procedure	

惯性因子

w

w

w 叫惯性因子，其值为非负

$ w=\left{ \begin{aligned} 较大，全局寻优能力强，局部寻优能力弱 \ 较小，全局寻优能力弱，局部寻优能力强 \end{aligned} \right. $
动态

w

w

w 能获得比固定值更好的寻优结果，动态

w

w

w 可在PSO搜索过程中线性变化，可以根据PSO性能的某个测度函数动态改变。

目前采用较多的是线性递减全脂（Linearly Decreasing Weight,LDW）策略：

w

(

t

)

=

w

m

a

x

−

(

w

m

a

x

−

w

m

i

n

)

∗

r

u

n

r

u

n

m

a

x

w^{(t)} = w_{max}-(w_{max} – w_{min})*\frac{run}{run_{max}}

w(t)=wmax​−(wmax​−wmin​)∗runmax​run​
其中,

w

m

a

x

w_{max}

wmax​ 是最大惯性权重，

w

m

i

n

w_{min}

wmin​ 是最小惯性权重，

r

u

n

run

run 为当前迭代次数，

r

u

n

m

a

x

run_{max}

runmax​ 为最大迭代次数。随着迭代次数增加，惯性权重$ w $ 应不断减小，从而使得粒子群算法在初期具有较强的全局收敛能力，而晚期具有较强的局部收敛能力。

收敛因子法

1999年，Clerc引入了收敛因子以保证算法的收敛性

速度更新公式为：

v

i

d

=

K

[

v

i

d

+

ψ

1

r

1

(

p

b

e

s

t

i

d

−

x

i

d

)

+

ψ

2

r

2

(

g

b

e

s

t

d

−

x

i

d

)

]

v_{id} = K[v_{id}+\psi_{1}r_{1}(pbest_{id}-x_{id})+\psi_2r_2(gbest_d-x_{id})]

vid​=K[vid​+ψ1​r1​(pbestid​−xid​)+ψ2​r2​(gbestd​−xid​)]
其中，收缩因子

K

K

K为受

ψ

1

,

ψ

2

\psi_1,\psi_2

ψ1​,ψ2​ 限制的

w

w

w .

ψ

1

,

ψ

2

\psi_1,\psi_2

ψ1​,ψ2​是需要预先设定的模型参数

K

=

2

∣

2

−

ψ

−

ψ

2

−

4

ψ

∣

,

ψ

=

ψ

1

+

ψ

2

.

ψ

>

4

K = \frac{2}{|2-\psi-\sqrt{\psi^2-4\psi}|},\psi = \psi_1+\psi_2.\psi>4

K=∣2−ψ−ψ2−4ψ
​∣2​,ψ=ψ1​+ψ2​.ψ>4
收缩因子法控制系统行为最终收敛，且可以有效搜索不同区域，该法能得到较高质量的解。

离散二进制PSO算法

离散二进制粒子群算法（Discrete Binary Particle Swarm Optimization Algorithm， BPSO）最初由J.Kennedy和R.C.Eberhart在1997年设计;

PSO主要优化连续实值问题，BPSO主要优化离散空间约束问题；

BPSO是在离散粒子群算法基础上，约定位置向量、速度向量均由0、1值构成；

BPSO有很强全局搜索能力，但不能收敛于全局最优值，且随着算法迭代搜索随机性越来越强，缺乏后期的局部搜索能力；

离散二进制粒子群算法步骤：

初始化粒子位置：按一定策略，生成二进制编码；

速度更新公式：

v

i

d

=

w

v

i

d

+

c

1

r

a

n

d

(

)

(

p

b

e

s

t

i

d

−

x

i

d

)

+

c

2

r

a

n

d

(

)

(

g

b

e

s

t

−

x

i

d

)

v_{id} = wv_{id}+c_1rand()(pbest_{id}-x_id)+c_2rand()(gbest-x_{id})

vid​=wvid​+c1​rand()(pbestid​−xi​d)+c2​rand()(gbest−xid​)

**位置更新公式：**使用概率映射方式，采用sigmiod函数将速度映射到[0,1]区间作为概率，这个概率就是粒子下一步取值为1的概率：

​

s

(

v

i

d

)

=

1

1

+

e

x

p

(

−

v

i

d

)

s(v_id)=\frac{1}{1+exp(-v_id)}

s(vi​d)=1+exp(−vi​d)1​

位置变化的绝对概率： 当前位置为0变换为1，当前位置1变换为0，这种变换称谓绝对变化，概率表示为：

x

i

d

=

{

1

i

f

 

r

a

n

d

(

)

≤

s

(

v

i

d

)

0

o

t

h

e

r

w

i

s

e

x_{id}=\left\{ \begin{aligned} &1 \quad if\ rand() \leq s(v_{id}) \\ &0 \quad otherwise \end{aligned} \right.

xid​={​1if rand()≤s(vid​)0otherwise​

PSO研究热点

• 算法收敛性分析： PSO在实际应用中被证明是有效的，但目前还没有给出收敛性、收敛速度估计等方面的数学证明，已有工作还不够。
• 粒子群拓扑结构： 不同的粒子群邻居拓扑结构是对不同类型社会的模拟，研究不同拓扑结构的使用范围，对PSO算法推广和使用有重要意义。
• 参数的选择与优化： 参数$w,{\Phi }_1,{\Phi }_2$ 的选择分别关系粒子速度3个部分：惯性部分、社会部分和自身部分在搜索中的作用。如何选择、优化和调整参数，使得算法既能够避免早熟又能比较快地收敛，对工程实践有这重要意义。
• 与其他演化计算的融合
• 算法应用