|
自然界生物有时候是以群体形式存在的。人工生命研究的主流之一是探索这些自然生物是如何以群体的形式生存，并在计算机里面重构这种模型。很多科学家很早以前就对鸟群和鱼群的生物行为进行计算机模拟，其中较为著名的有Reynolds、Hepper、Kennedy和Grenander对鸟群的模拟。Reynolds通过CG动画仿真了鸟群的复杂群体行为，他是综合三条简单的准则来构建这种行为：
其基本思想是受多位科学家早期对许多鸟类的群体行为进行建模与仿真研究结果的启发，他们的模型及仿真算法主要利用了生物学家Hepper的模型。在Hepper的仿真中，鸟在一块栖息地附近聚群，这块栖息地吸引着鸟，直到它们都落在这块地上。Hepper模型中的鸟是知道栖息地的位置的，但在实际情况中，鸟类在刚开始是不知道食物的所在地的。所以Kennedy等认为鸟之间存在着相互交换信息，于是他们在仿真中增加了一些内容：每个个体能够通过一定规则估计自身位置的适应值；每个个体能够记住自己当前所找到的最好位置，称为“局部最优pbest”；此外还记住群体中所有鸟中找到的最好位置，称为“全局最优gbest”。这两个最优变量使得鸟在某种程度上朝这些方向靠近。他们综合这一切内容，提出了实际鸟群的简化模型，即我们所说的粒子群算法。
粒子群算法是一个非常简单的算法，且能够有效地优化各种函数。从某种程度上说，此算法介于遗传算法和进化规划之间。此算法非常依赖于随机的过程，这也是和进化规划的相似之处。此算法中朝全局最优和局部最优靠近的调整非常类似于遗传算法中的交叉算子。此算法还使用了适应值的概念，这是所有进化计算方法所共有的特征。
基本粒子群算法在粒子群算法中，每个个体称为一个“粒子”，其实每个粒子代表一个潜在的解。例如，在一个
D
D
D维的目标搜索空间中，每个粒子看成是空间内的一个点。设群体由
m
m
m个粒子构成。
m
m
m也被称为群体建模，过大的
m
m
m会影响算法的运算速度和收敛性。设
z
i
=
(
z
i
1
,
z
i
2
,
?
?
,
z
i
D
)
z_i=(z_{i1}, z_{i2}, \cdots, z_{iD})
zi?=(zi1?,zi2?,?,ziD?)为第
i
i
i个粒子的
D
D
D维位置向量，根据事先设定适应值函数（与要解决的问题有关）计算
z
i
z_i
zi?当前的适应值，即可衡量粒子位置的优劣。
v
i
=
(
v
i
1
,
v
i
2
,
?
?
,
v
i
D
)
vi=(v_{i1}, v_{i2}, \cdots, v_{iD})
vi=(vi1?,vi2?,?,viD?)为粒子
i
i
i的飞行速度，即粒子移动的距离；
p
i
=
(
p
i
1
,
p
i
2
,
?
?
,
p
i
D
)
p_i=(p_{i1}, p_{i2}, \cdots, p_{iD})
pi?=(pi1?,pi2?,?,piD?)为粒子迄今为止搜索到的最优位置；
p
g
=
(
p
g
1
,
p
g
2
,
?
?
,
p
g
D
)
p_g=(p_{g1}, p_{g2}, \cdots, p_{gD})
pg?=(pg1?,pg2?,?,pgD?)为整个粒子群迄今为止搜索到的最优位置。
在每次迭代中，粒子根据以下式子更新速度和位置：
v
i
d
k
+
1
=
v
i
d
k
+
c
1
r
1
(
p
i
d
?
z
i
d
k
)
+
c
2
v
2
(
p
g
d
?
z
i
d
k
)
z
i
d
k
+
1
=
z
i
d
k
+
i
d
k
+
1
v_{id}^{k+1}=v_{id}^k+c_1r_1(p_{id}-z_{id}^k)+c_2v_2(p_{gd}-z_{id}^k)\\ \quad\\ z_{id}^{k+1}=z_{id}^k+_{id}^{k+1}
vidk+1?=vidk?+c1?r1?(pid??zidk?)+c2?v2?(pgd??zidk?)zidk+1?=zidk?+idk+1?
其中，
i
=
1
,
2
,
?
?
,
m
i=1, 2, \cdots, m
i=1,2,?,m，
d
=
1
,
2
,
?
?
,
D
d=1, 2, \cdots, D
d=1,2,?,D，
k
k
k是迭代次数，
r
1
r_1
r1?和
r
2
r_2
r2?为
[
0
,
1
]
[0, 1]
[0,1]之间的随机数，这两个参数是用来保持群体的多样性；
c
1
c_1
c1?和
c
2
c_2
c2?为学习因子，也称加速因子，其使粒子具有自我总结和向群体中优秀个体学习的能力，从而向自己的历史最优点以及群体内历史最优点靠近。这两个参数对粒子群算法的收敛起的作用不是很大，但如果适当调整这两个参数，可以减少局部最小值的困扰，当然也会使收敛速度变快。由于粒子群算法中没有实际的机制来控制粒子速度，所以有必要对速度的最大值进行限制。当速度超过这个阈值时，设其为
v
max
v_\text{max}
vmax?，这个参数被证明是非常重要的，因为值太大会导致粒子跳过最好解，但太小的话又会导致对搜索空间的不充分搜索。此外速度
v
i
v_i
vi?最小取值为
v
min
v_\text{min}
vmin?，位置
Z
i
Z_i
Zi?的取值范围为
Z
max
～
Z
min
Z_\text{max}\sim Z_\text{min}
Zmax?～Zmin?。
v
i
d
k
+
1
v_{id}^{k+1}
vidk+1?的第二项是“认知”部分（Cognition Part），代表了粒子对自身的学习。而公式的第三项是“社会”部分（Social Part），代表着粒子间的协作。上式正是粒子根据它上一次迭代的速度、它当前位置和自身最好经验与群体最好经验之间的距离来更新速度。
从此可得到粒子群算法是主要遵循了五个基本原则，定义内容如下
- 邻近原则（Proximity）：粒子群必须能够执行简单的空间和时间计算。
- 品质原则（Quality）：粒子群必须能够对周围环境的品质因素有所反应（变量
pbest和gbest）隐含着这一原则。 - 多样性反应原则（Diverse Response）：粒子群不应该在过于狭窄的范围内活动。④定性原则（Stability）：粒子群不应该在每次环境改变的时候都改变自身的行为。⑤适应性原则（Adaptability）：在能够接受的计算量下，粒子群需能够在适当的时候改变它们的行为。
|