文档介绍：第八章粒子群算法及其改进算法(初稿)
引言
自然界中一些生物的行为特征呈现群体特征,可以用简单的几条规则将这种群体行为(Swarm Behavior)在计算机中建模,实际上就是在计算机中用简单的几条规则来建立个体的运动模型,但这个群体的行为可能很复杂。例如,Reynolds使用了下列三个规则作为简单的行为规则[1]。
(1) 冲突避免(Collision Avoidance):
群体在一定容积空间移动,个体有自己移动的意志,但不能影响各别个体移动,避免碰撞与争执。
(2) 速度匹配(Velocity Matching):
个体必须配合群体中心移动速度,不管在方向、距离与速率上都必须互相配合。
(3) 群集中心(Flock Centering):
个体将会往群体中心移动,配合群体中心往目标前进。
这即是著名的Boid (Bird-bid)模型。在这个群体中每个个体的运动都遵循这三条规则,通过这个模型来模拟整个群体的运动。PSO算法的基本概念也是如此。每个粒子(Particle)的运动可用几条规则来描述,因此PSO算法简单,容易实现,越来越多地引起人们的注意。设想这样一个场景:一群鸟在随机搜寻食物,在这个区域里只有一块食物,所有的鸟都不知道食物在哪里,但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。
粒子群优化算法是Kennedy和Eberhart于1995年时提出,在研究PSO的过程中,有各种不同版本出现[2-6]。PSO的概念源自群体行为理论,启发自观察鸟群或鱼群行动时,能透过个体间特别的讯息传递方式,使整个团体朝同一方向、目标而去,是模仿此类生物行为反应来寻求完成群体最大利益的方法。
其构成的原理如下:
1) 接近原则:粒子与群体应能够依目标前进。
2). 特性原则:群体应该能够反应环境的变化,当所处之环境并非是最佳解空间时,能够快速飞离此解空间区域。
3). 不同响应原则:群体不会朝向不佳的解前进。
4). 稳定原则:当环境有所改变时,群体移动不会改变其运动模式。
5). 适应原则:计算当下最佳解时,群体将会考量适当参数变动。
第二节基本粒子群优化算法
以平面例子说明,如图8-1,T为目标,A~E为搜寻粒子,初始粒子群分散于各处。此时群体最佳的粒子是离目标T最近的粒子D,称之为。假设粒子经过三次移动之后,位置如图8-2所示,此时群体最佳的粒子则为E4。粒子群亦分别纪录自身搜寻的最佳纪录,称之为,如图2-2,粒子A目前停驻位置为A4,其自身最佳搜寻纪录为坐标A3。
在PSO中,每个优化问题的潜在解都可以想象成d维搜索空间上的一个点,我们称之为“粒子”(Particle)。粒子在搜索空间中以一定的速度飞行,这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。所有的粒子都有一个被目标函数决定的适应值(fitness value),并且知道自己到目前为止发现的最好位置(particle best,记为)和当前的位置。这个可以看作是粒子自己的飞行经验。除此之外,每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(global best,记为,是在中的最好值),这个可以看作是粒子的同伴的经验。每个粒子使用下列信息改变自己的当前位置:1