Table of Contents

一、粒子群优化算法概念

粒子群算法 (PSO) 属于群智能算法的一种，是通过模拟鸟群捕食行为设计的。假设区域里就只有一块食物（即通常优化问题中所讲的最优解），鸟群的任务是找到这个食物源。鸟群在整个搜寻的过程中，通过相互传递各自的信息，让其他的鸟知道自己的位置，通过这样的协作，来判断自己找到的是不是最优解，同时也将最优解的信息传递给整个鸟群，最终，整个鸟群都能聚集在食物源周围，即我们所说的找到了最优解，即问题收敛。

基本思想：

PSO 模拟的是鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。

鸟群在整个搜寻的过程中，通过相互传递各自的信息，让其他的鸟知道自己的位置，通过这样的协作，来判断自己找到的是不是最优解，同时也将最优解的信息传递给整个鸟群，最终，整个鸟群都能聚集在食物源周围，即找到了最优解。

PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为**“粒子”**。所有的粒子都有一个由被优化的函数决定的适应值 (fitness value)，**每个粒子还有一个速度决定他们飞翔的方向和距离。**然后粒子们就追随当前的最优粒子在解空间中搜索。

PSO 初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个"极值"来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。

二、粒子群优化算法流程

鸟被抽象为没有质量和体积的微粒(点)，并延伸到 N 维空间，粒子 i 在 N 维空间的位置表示为矢量$Xi＝(x1，x2，…，xN)$，飞行速度表示为矢量 $Vi＝ (v1，v2，…，vN)$。每个粒子都有一个由目标函数决定的适应值 (fitness value) ，并且知道自己到目前为止发现的最好位置 $($pbest$) $和现在的位置 Xi 。这个可以看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置$($gbest$)$($gbest$是$ pbest $中的最好值)，这个可以看作是粒子同伴的经验。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。

上一节已经描述了鸟类寻找食物的过程，抽象的粒子群算法流程与之相同。

image-20211008174419936

速度与位置的更新

img

公式三为：

image-20211008180301038

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

更加详细参考粒子群算法详细解析

三、粒子群优化算法工具箱

1. 快速开始

  1. 定义问题

    1
2
3

    def demo_func(x):
    x1, x2, x3 = x
    return x1 ** 2 + (x2 - 0.05) ** 2 + x3 ** 2

  2. 运行粒子群算法

    1
2
3
4
5

    from sko.PSO import PSO

pso = PSO(func=demo_func, n_dim=3, pop=40, max_iter=150, lb=[0, -1, 0.5], ub=[1, 1, 1], w=0.8, c1=0.5, c2=0.5)
pso.run()
print('best_x is ', pso.gbest_x, 'best_y is', pso.gbest_y)

  3. 画出结果

    1
2
3
4

    import matplotlib.pyplot as plt

plt.plot(pso.gbest_y_hist)
plt.show()

    image-20211008183952759

  4. 案例2：增加非线性约束

    加入你的非线性约束是个圆内的面积 (x[0] - 1) ** 2 + (x[1] - 0) ** 2 - 0.5 ** 2<=0

    源码

    image-20211008185658639

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

    import numpy as np
from sko.PSO import PSO


def demo_func(x):
    x1, x2 = x
    return -20 * np.exp(-0.2 * np.sqrt(0.5 * (x1 ** 2 + x2 ** 2))) - np.exp(
        0.5 * (np.cos(2 * np.pi * x1) + np.cos(2 * np.pi * x2))) + 20 + np.e


constraint_ueq = (
    lambda x: (x[0] - 1) ** 2 + (x[1] - 0) ** 2 - 0.5 ** 2
    ,
)

max_iter = 50
pso = PSO(func=demo_func, n_dim=2, pop=40, max_iter=max_iter, lb=[-2, -2], ub=[2, 2]
          , constraint_ueq=constraint_ueq)
pso.record_mode = True
pso.run()
print('best_x is ', pso.gbest_x, 'best_y is', pso.gbest_y)

# %% Now Plot the animation
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation

record_value = pso.record_value
X_list, V_list = record_value['X'], record_value['V']

fig, ax = plt.subplots(1, 1)
ax.set_title('title', loc='center')
line = ax.plot([], [], 'b.')

X_grid, Y_grid = np.meshgrid(np.linspace(-2.0, 2.0, 40), np.linspace(-2.0, 2.0, 40))
Z_grid = demo_func((X_grid, Y_grid))
ax.contour(X_grid, Y_grid, Z_grid, 30)

ax.set_xlim(-2, 2)
ax.set_ylim(-2, 2)

t = np.linspace(0, 2 * np.pi, 40)
ax.plot(0.5 * np.cos(t) + 1, 0.5 * np.sin(t), color='r')

plt.ion()
p = plt.show()


def update_scatter(frame):
    i, j = frame // 10, frame % 10
    ax.set_title('iter = ' + str(i))
    X_tmp = X_list[i] + V_list[i] * j / 10.0
    plt.setp(line, 'xdata', X_tmp[:, 0], 'ydata', X_tmp[:, 1])
    return line


ani = FuncAnimation(fig, update_scatter, blit=True, interval=25, frames=max_iter * 10)
plt.show()

ani.save('pso.gif', writer='pillow')

    pso2

2. 算法参数

image-20211008185742263

3. 算法进阶

离散粒子群算法

原始的PSO采用实数编码，对于速度计算、位置更新等非常方便而自然，但是对于离散优化和组合优化问题，有时实数编码难以直接应用，这就需要应用二进制编码(Binary encoding)或者排列编码(Permutation encoding)，对于非实数编码，需要重新定义距离、速度、位置的含义和相应操作。

目前该库没提供这些功能。

想了解实现的可以参考一些研究，简单实现如：

离散粒子群算法（DPSO）和离散二进制粒子群算法（BPSO ）

整数编码的粒子群算法

四、总结

粒子群算法虽然自提出以来就吸引了大量学者的目光，但粒子群算法也存在诸多弊端，如局部搜索能力差，容易陷入局部极值，搜索精度低等。

粒子群算法是一个简洁且强大的优化算法。它可以嵌套非凸模型、逻辑模型、复杂模拟模型、黑箱模型、甚至实际实验来进行优化计算，是一个让人欲罢不能的算法。虽然粒子群算法在诸多领域均有不错表现，如电力系统，生物信息，物流规划等，但对于一些特定问题的求解，粒子群并不能保证解的质量。因此，粒子群算法的发展仍在继续，其研究仍有许多未知领域，如粒子群理论的数学验证等等。