粒子群优化算法的思想起源

2.1.1　粒子群优化算法的思想起源

1．复杂适应系统

复杂适应系统(Complex Adaptive System，简称CAS)^［54］理论是美国霍兰(John Holland)教授于1994年在桑塔菲研究所(Santa Fe Institute)成立10周年时正式提出的。所谓复杂适应系统，是指系统与外部环境交互作用的过程中，通过自适应改变系统本身的组织结构和行为特点，从而不断向前发展和演化。我们把系统中的成员称为具有适应性的主体(Adaptive Agent)，简称为主体。所谓具有适应性，就是指它能够与环境以及其他主体进行交流，在这种交流的过程中“学习”或“积累经验”，并且根据学到的经验改变自身的结构和行为方式。整个系统的演变或进化，包括新层次的产生、分化和多样性的出现，新的、聚合而成的、更大的主体的出现等，都是在这个基础上出现的。CAS理论在模拟经济、社会、生物、生态等复杂系统方面发挥了巨大的功用^［55］。CAS理论有如下四个基本特点。

(1)主体是主动的、活的实体。

(2)个体与环境(包括个体之间)的相互影响、相互作用是系统演变和进化的主要动力。

(3)这种方法不像许多其他的方法那样，把宏观和微观截然分开，而是把它们有机地联系起来。

(4)这种建模方法还引进了随机因素的作用，使它具有更强的描述和表达能力。

粒子群优化算法源于1987年克莱格·雷诺尔德(Craig Reynolds)对鸟群社会系统(Boids)的仿真研究^［56］，Boids模型也是一个CAS，因此PSO算法中也包含了上面列出的四个基本特点。在Boids模型中，Reynolds使用了下列三个规则作为简单的行为规则:

(1)鸟与鸟之间不能距离太近，避免与相邻的鸟发生碰撞冲突;

(2)鸟以大致相同的速度飞行，尽量与周围的鸟在速度上保持协调一致;

(3)鸟向群体的中心运动。

这就是著名的Boids模型。在这个群体中每个个体的运动都遵循上述三条原则，通过这个模型来模拟整个种群的运动。PSO算法的基本概念也是如此，每个粒子(Particle)的运动可以用这几条基本规则来描述。只不过Reynolds将其作为CAS的一个实例做仿真研究，而并未将它用于优化计算中，也没有任何实用价值。将其用于优化计算中，这一开创性工作是由Kennedy和Eberhart共同完成的。

2．人工生命

人工生命(Artificial Life，简称AL)^［57］是首先由计算机科学家克里斯·朗顿(Chris Langton)于1987年在首次召开的“人工合成以及模拟生命系统的国际会议”上提出的。AL是用来研究具有某些生命基本特征的人工系统，它包括以下两方面的内容:

(1)研究如何利用计算技术研究生物现象;

(2)研究如何利用生物技术研究计算问题。

现在关注的是第二部分的内容，并且已经有很多源于生物现象的计算技巧，例如人工神经网络是简化的大脑模型，遗传算法是模拟基因进化过程的。现在讨论另一种生物系统————社会系统，更确切地说，是由简单个体组成的群落与环境以及个体之间的互动行为，也可称做“群智能”。

与基于达尔文“适者生存，优胜劣汰”进化思想的遗传算法不同的是，粒子群算法是通过个体之间的协作来寻找最优解的。社会生物学家E.Q.Wilson关于生物群体有一段话，“至少理论上，一个生物群体中的一员可以从这个群体中所有其他成员以往在寻找食物过程中积累的经验和发现中获得好处。只要食物源不可预知地分布在不同地方，这种协作带来的优势可能变成决定性的，超过群体中个体之间对食物竞争所带来的劣势。”这段话的意思是说生物群体中信息共享会产生进化优势，这也是粒子群优化算法的基本思想^［58］。

设想这样一个场景:一群鸟在随机搜索食物，而在这区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远，那么找到食物的最优策略是什么呢?最简单有效的策略就是搜索目前离食物最近的鸟的周围区域。这是一种共享机制，在心理学中对应的是在寻求一致的认知过程中，个体往往记住它们的信念，同时考虑其他个体的信念。当个体察觉其他个体的信念较好时，它将进行适应性的调整。PSO算法从这个模型中得到启示并用于解决优化问题，PSO算法中每个优化问题的可行解都被看成是搜索空间中的一只鸟，称之为“粒子”。每个粒子都有一个由被优化问题决定的适应度，每个粒子还有一个速度决定它们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间搜索。PSO算法初始化为一群随机粒子，然后根据它们本身的飞行经验和同伴的飞行经验来动态调整。