PSO算法粒子群算法在局域网中的并行实现研究+程序(3)

菜单

粒子群算法最早是在1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart 共同提出的，粒子群算法的基本思想是受他们早期对鸟类群体行为进行建模与仿真研究结果的启发。而他们的模型及仿真算法主要利用了生物学家Frank Heppner的模型。

Frank Heppner的鸟类模型在反映群体行为方面与其它类模型有许多相同之处，所不同之处在于：鸟类被吸引飞向栖息地。在仿真中，一开始每一只鸟均无特定目标进行飞行，直到有一只鸟飞到栖息地，当设置期望栖息比期望留在鸟群中具有较大的适应值时，每一只鸟都将离开群体而飞向栖息地，随后就自然地形成了鸟群，。

由于鸟类使用简单的规则确定自己的飞行方向与飞行速度（实质上，每一只鸟都试图停在鸟群中而又不相互碰撞），当一只鸟飞离鸟群而飞向栖息地时，将导致它周围的其它鸟也飞向栖息地。这些鸟一旦发现栖息地，将降落在此，驱使更多的鸟落在栖息地，直到整个鸟群都落在栖息地。

由于James Kennedy和 Russell Eberhart所具有的专业背景，就能很容易理解他们为什么会对Hepper的鸟类模型感兴趣。鸟类寻找栖息地与对一个特定问题寻找解很类似，已经找到栖息地的鸟引导它周围的鸟飞向栖息地的方式，增加了整个鸟群都找到栖息地的可能性，也符合信念的社会认知观点。

Eberhart和Kennedy对Heppner的模型进行了修正，以使粒子能够飞向解空间并在最好解处降落。其关键在于如何保证粒子降落在最好解处而不降落在其它解处，这就是信念的社会性及智能性所在。

信念具有社会性的实质在于个体向它周围的成功者学习。个体与周围的其它同类比较，并模仿其优秀者的行为。将这种思想用算法实现将导致一种新的最优化算法。

要解决上述问题，关键在于在探索（寻找一个好解）和开发（利用一个好解）之间寻找一个好的平衡。太小的探索导致算法收敛于早期所遇到的好解处，而太小的开发会使算法不收敛。

另一方面，需要在个性与社会性之间寻求平衡，也就是说，既希望个体具有个性化，像鸟类模型中的鸟不互相碰撞，又希望其知道其它个体已经找到的好解并向它们学习，即社会性。

Eberhart和Kennedy较好地解决了上述问题，提出了粒子群优化算法(Particle Swarm Optimization, PSO)[Kennedy 1995]。PSO 从这种模型中得到启示并用于解决优化问题。在PSO中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值（fitness value），每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子（随机解）。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解。这个解称为个体极值。另一个极值是整个种群目前找到的最优解。这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值[5]。

1.3 粒子群算法的发展与应用

1.3.1 粒子群算法的改进

在粒子群算法的改进方面，首先是由Eberhart 和 Kennedy 在1997年提出的二进制PSO算法[Kennedy 1997],为PSO算法与遗传算法的性能比较提供了一个有用的方式。其次，为了提高算法的收敛性能，Shi和Eberhart与1998年对PSO算法的速度项引入了惯性权重 [Shi 1998]，并提出在进化过程中动态调整惯性权重以平衡收敛的全局性和收敛速度，该进化方程已被相关学者称为标准PSO算法。Clerc于1999年在进化方程中引入收缩因子以保证算法的收敛性[Clerc 1999]，同时使得速度的限制放松。Angeline于1999年借鉴进化计算中的选择概念，将其引入PSO算法中。通过比较各个粒子的适应值淘汰掉差的粒子，而将具有较高适应值的粒子进行复制易产生等数额的粒子还提高算法的收敛性。而Lovbjerg 等人进一步将进化计算机之应用于PSO算法，如复制、交叉等，给出了算法交叉的具体形式，并通过典型测试函数的仿真实验说明了算法的有效性。文献综述