粒子群算法的边界问题研究

方 田

（中冶华天工程技术有限公司，江苏 南京210019）

0 引言

粒子群算法（Particle Swarm Optimization Algorithm），缩写为PSO，是近年来发展起来的一种新的进化算法。它是Kennedy和Eberhart受人工生命研究结果的启发、通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法，1995年IEEE国际神经网络学术会议发表了题为Particle Swarm Optimization的论文，标志着PSO算法诞生。[1]该算法具有很好的生物社会背景，对非线性、多峰问题均具有较强的全局搜索能力，在科学研究与工程实践中得到了广泛的关注和应用。[2]

在粒子群算法的进化计算过程中，经常会遇到被搜索空间边界约束的情况。边界问题理论上并不会对粒子群算法的造成巨大的破坏，但在实际应用中却会造成计算资源的极大浪费。同时，在有限的进化次数限制下，会对算法效果产生较大影响。

本文就粒子群算法的边界问题进行了研究和分析，并提出一些解决方案以供参考。

1 粒子群算法原理

粒子群算法最初是受到飞鸟集群活动的规律性启发，进而利用群体智能建立的一个简化模型。其生物学模型主要源于生物学家Frank Heppner提出的鸟类栖息模型。[3]社会心理学研究成果揭示了社会性群体中的个体之间会发生信息交流，并产生趋同认知。以鸟群为例，每只飞鸟之间会通过声音或动作交流其个体的认知信息，同时，独立的飞鸟个体会趋向于跟随群体的大方向飞行。这样，每个个体就会在自身经验的基础上，获得了群体的经验知识，增加了觅食的成功率。如果将每只飞鸟作为一个智能计算体(agent)，将这样的一组智能体作为族群，用计算机来模拟其觅食过程，就构建了基本的粒子群算法思想，而所谓食物就是算法的目标函数。这样的基本粒子群算法也被称之为鸟群算法。

在粒子群算法中，每个粒子都是一个智能体，具有以下几个功能：

1）运动功能：能在计算空间中自由运动。

2）判断功能：能判断自身的适应度。

3）记忆功能：能记忆自身的历史经验。

4）交流功能：能和整个群体交流各自的经历。

这样的粒子集合就构成了粒子群，该粒子群是一个智能体的群落，同时具有个体不具备的群体智能。

基于以上思想，基本粒子群算法表述如下：

其中vij(t)代表第i个粒子在第t次进化时的速度；xij(t)表示第i个粒子在第t次进化时的位置；pbest,ij(t)是第i个粒子的个体历史最佳值；gbest,j(t)是群体历史最佳值；w是粒子运动的惯性因子；c1是自身记忆影响因子；c2是群体影响因子；r1j(t)，r2(t)是随机因子；i是粒子序号；j是计算空间的维度序号。

2 边界问题的产生和分析

由上一章节可以看到，基本粒子群算法兼顾了种群中每个粒子的惯性、自身经验和群体经验，在进化计算过程中模拟了鸟群觅食的社会性群体机制，达到了全局搜索的目的。但是在实际应用中，有一个情况不可忽略，那就是实际问题的搜索空间一般都是是有界的，也就是说群体是被限制在了一个封闭的空间中，单独的个体并不能任意运动。当单个个体突破了空间界限的限制，就会给算法结构带来破坏，造成以下一些问题：

1）适应度函数失效：超出适应度函数的定义域，导致判据失效，得到错误的结论。

2）解区间错误：在搜索空间之外，无法得到有效解。

3）计算资源浪费：在搜索空间之外不会得到有效经验，也不会对群体知识进行改进，这样的计算完全是浪费。

4）延误进化进程：粒子个体在走出限制空间之后，由于惯性原因，会在错误的空间产生滞留，严重影响算法收敛速度。

针对这样一些问题，在算法上有必要增加一定的机制加以限制，使粒子的运动限制在搜索空间范围内，增加算法效率，改善优化搜索效果。在实践过程中，笔者发现可以采用以下一些方式对算法加以改进：

1）增加搜索空间外的适应度定义，可以将该区域的适应度设为最小值。这样，可以依靠粒子自身的智能回归正确的空间。

2）当粒子运动到空间边界时，强制该粒子停止运动，当前速度置为0，粒子的适应度用当前所处的边界位置计算。

3）将空间边界设置为反射面，当粒子碰撞到空间边界时，就产生反射作用，让粒子根据一定的机制反弹回原空间，并保持一定的速度。

以上几种方式从不同的的角度来处理粒子群算法的边界问题，各有优缺点。

增加适应度定义的方法可以保持粒子群算法机制上的完善，充分发挥粒子的智能和自主性。但是这样会牺牲一部分算法效率，也就是牺牲掉粒子自主纠错的计算时间。强制粒子停止的方法可以最大化的节约边界问题的错误纠正时间，但是，粒子一旦停止后，就会丧失原运动过程的惯性体系，影响种群的多样性。让粒子反射的方法可以杜绝边界问题的产生，同时，也有利于保持种群多样性。但是反射过程的运动计算在一定程度上增加了计算时间消耗。

3 结语

通过上述研究可知，粒子群算法是一种优秀的群体智能优化算法，它机理清晰，应用广泛。粒子群算法的边界问题影响到算法的效率和最终结果，必须加以重视。在实际应用中，采用适当的方法可以对边界问题加以处理，使算法更加完善。

［1］Kennedy J,Eberhart R.Particle swarm optimization [C]//Proceedings of the 4th IEEEInternational Conference on Neural Networks.Piscataway:IEEEService Center,1995:1942-1948.

［2］Garnier S,Gautrais J,Theraulaz G.The biological principles of swarm intelligence[J].Swarm Intelligence,2007,30(1):3-31.

［3］Banks A,Vincent J,Anyakoha C.A review of particle swarm optimization.Part I:background and development[J].Natural Computing,2007,45(6):55-57.