带冲撞和制动的自适应粒子群优化算法

李 眩，吴晓兵，方婷婷

（铜陵职业技术学院经贸系，安徽铜陵 244061）

粒子群优化（particle swarm optimization，PSO）算法源于对鸟类觅食行为的研究，受其启发运用群体协作和个体间信息共享解决优化问题的智能随机搜索算法，其应用从最初数学领域的函数最值求解扩展到如今的工程领域的过程优化、模糊系统的控制、图像处理等更加广阔的领域〔1〕。PSO 算法诞生较晚，但有易理解、易实现、收敛速度快的优点。虽然PSO 算法在一些领域应用中有着不错的表现，但随着应用范围的拓展，发现标准PSO 算法在解决一些复杂特定问题时效果还有待提升，譬如多目标动态规划存在早熟收敛、维数灾难、后期趋同导致多样性不足等问题〔2〕，因此改进PSO 算法，提升其解决实际问题的效率十分有意义。在自适应粒子群优化（adaptive particle swarm optimization，APSO）算法的基础上，借鉴沙丁鱼受刺激加速游动避免死亡的原理，引入冲撞机制对标准PSO 算法进行改进，以此来提高算法摆脱局部最优的束缚和全局寻优能力。另外，为了兼顾算法的全局探索和局部精细搜索能力，在粒子群搜索过程中，引入一个动态变化的制动算子来控制粒子的速度，这样可有效避免粒子群过早丧失全局探索能力和后期速度过大错失全局最优解的情况出现，从而提高算法的整体效率。

1 标准PSO 算法及性能提升分析

PSO 算法是受鸟群觅食行为启发而提出的智能优化算法，PSO 算法通过粒子相互之间的信息交互和配合使得整个群体达到和谐统一，实现在复杂搜索空间中协同寻优〔3〕。

在PSO 算法前期，较大的粒子速度有助于在限定的时间内尽可能遍历全部可行区域，从而提高算法的收敛速度和全局收敛的能力，而在进化后期在最优解邻域内进行探索时，粒子速度不能过快，因为较小的粒子速度便于粒子在全局最优解附近精细搜索，同时又能防止粒子飞行惯性过大逃离最优解区域而错失全局最优解，因此必须遵循算法需要全程适时地对粒子速度进行有效适当的掌控和约束〔4〕。而标准PSO 算法缺乏对粒子速度的动态调整，容易陷入局部最优或者不易收敛，为了满足算法性能提升要求，本研究引入制动算子实时控制粒子速度。另外针对PSO 算法存在易陷入局部最优的缺陷，受刺激沙丁鱼加速游动避免死亡案例的启发，在算法陷入局部最优时，引入一个冲撞算子激发粒子群运动活性使其有效摆脱局部最优的困扰。同时，在动态APSO 算法基础上结合非线性变化的制动因子，来适时适当调整粒子的飞行速度改善算法的性能。

2 带冲撞和制动的APSO 算法

人们发现PSO 算法采用自适应变化的动态参数比固定取值的参数更有助于提高算法的性能和效率〔5〕。PSO 算法的惯性权重设置不当对算法的性能产生不利影响，虽然惯性权重的动态非线性自适应调整比固定权重或线性变化权重能更好地提升PSO 算法性能，但仅用单一策略进行优化，对算法性能的提升相对有限〔6〕。因此本研究在自适应调整惯性权重的基础上，同时考虑到算法要具备快速摆脱局部极值束缚的能力以及兼顾算法全局探索和局部精细搜索的能力，再进一步整合冲撞和制动多项策略改进算法来尽可能深度挖掘算法性能。因此在本研究中采用反正切函数对惯性权重进行改进，使其随进化过程体现出非线性递减特征，调整如式（1）所示：

反正切函数是一个单调函数，随着自变量的增加，函数值变化步长逐渐减少。自变量等于1.56 时，函数值等于1，在进化过程中，惯性权重值前期减少的速度比较慢，后期减少的速度较快，在保证前期收敛速度的同时保证了搜索能力，能较好避开局部最优的现象出现，运用反正切函数改良后的动态非线性惯性权重符合PSO 算法性能的提升要求〔2〕。wstart=0.9，wend=0.4。当t=1 时，w（t）=wstart=0.9，当达到最大迭代次数tmax时，w（t）=wend=0.4。k 为控制因子，影响w（t）变化曲线的平滑度，k 取0.3，算法能取得较好的稳定性。

粒子速度有规律地变化能极大提升算法的效率和性能，并且其变化规律是可控的，因此适时地对粒子速度进行适量制动可以提升算法性能。在粒子位置更新公式中引入一个随算法迭代不断减小的制动算子ρ（t），实现对粒子速度逐渐增强的制动约束作用，来平衡算法的全局探索和局部精细搜索能力。制动算子值越小，对粒子的速度制动作用就越强，粒子速度减少值就越大。但要注意的是算法没有结束或全局收敛前，不能对粒子群进行彻底制动，让其完全停止搜索没有运动，因为粒子停止运动，意味着无法继续搜索最优解，所以制动算子值的变化应从某个较大值逐渐减少为某个最小值，但不能减少为0。

制动算子变化规律按照式（2）进行调整：

其中，ρmax设为1.6，ρmin设为0.4，α 为常数，设为0.009，tmax为最大迭代次数，t 为当前寻优次数。如此，粒子位置更新按式（3）调整：

如此设计的制动算子值随迭代呈现先大后小非线性递减的变化特征，但最终并不减少为0。由此可见，按照式（2）设计的制动算子完全满足算法改进的要求。但在粒子加速冲撞跳脱局部极值陷阱的特殊情况下不能受制动影响，加入制动因子会逐渐降低粒子的运动速度，这一情况在后面会进行详细阐述。

自然界沙丁鱼生性懒惰，不爱游动，长时间运输几乎全部死亡。但当受到外部刺激譬如鲶鱼追赶，沙丁鱼会加速游动，运动量大大增加，很少出现缺氧死亡的情况。同理，标准PSO 算法一旦落入局部极值邻域内就很难跳出，体现出运动惰性，寻优过程将会停滞，极易早熟收敛。为了激活陷入局部极值陷阱时粒子群的运动活性，受到沙丁鱼受外部刺激加速游动避免死亡的案例启发，以粒子群当前最优值与前几代群体最优值相等为触发条件，通过给粒子群一个比较大的瞬间冲量，相当于给予一个较大的外部刺激改变其惰性停滞状态，驱动粒子突然加速冲出局部最优邻域进入新一轮的探索，从而防止算法早熟收敛，增强其全局寻优能力。

当算法未达到终止条件而陷入局部最优停顿时，表现为粒子群当前最优适应度值一直保持不变，以此来构造算法受局部极值影响陷入停顿的判断条件，其表述如下：

其中，i 表示当前的迭代次数，gb（i）表示群体当前最佳的适应度值，n 表示参照当前回溯的迭代次数。在本研究中取n=5，意为连续5 次迭代群体当前最优值保持不变时，即可认定算法停顿。

算法满足所设置的局部最优触发条件时，引入冲撞驱动算子强行驱动粒子重新搜索，此情况下粒子速度更新公式按式（4）进行更新：

其中，rand（）*k+k 称为冲撞算子，rand（）为位于［0，1］区间的随机数，w×vij（t）+c1×r1×［pij（t）-xij（t）］+c2×r2×［pgj（t）-xij（t）］表示正常情况下的速度更新，常数k 表示冲撞强度，本研究中取k=5，意为算法未结束而停滞时，当前粒子速度随机增大到理论更新速度的5 到10 倍，以此来强行突破局部最优束缚。但要考虑到算法陷入局部极值，冲撞加速摆脱困境的情况下，不能同时又受制动的影响，那样粒子速度会减缓，势必会削弱冲撞效果，所以约定在算法陷入局部极值粒子加速冲撞时，其位置更新公式中不带入制动因子，仍然采用原来方式xij（t+1）=xij（t）+vij（t+1）进行更新。

如上所述，改进后的PSO 算法具有较好的算法性能，陷入局部极值时仍然具有较高的运动活性而不至于出现搜索停滞，同时在算法实现过程中，可以对粒子进行自适应的制动，很好地协调平衡粒子全局探索和局部搜索能力，既不会过早放弃对全部解空间的探索，又同时防止粒子惯性大越过最优解区域从而错失全局最优解。

3 改进算法性能仿真分析

为验证应用自适应调整、冲撞和制动组合策略提升PSO 算法性能的有效性，选择几个典型非线性多模态和高维函数最小值的求解对算法进行实验研究。如果优化算法能较为满意地解决这些标准测试问题，则可认为在解决优化问题上有比较满意的效果。第一个测试函数是较简单的三维函数f1，其表达式为：

函数三维图像见图1，该函数图像存在一个局部极值点，一旦粒子群掉落其中，很难跳出。

图1 函数f1 三维图像

为探究算法改进前后的效果和合理性，求函数f1在区间［-4，4］的最小值，测试过程中，取粒子群规模为100，粒子维数为2 维，最大迭代次数为200次。将标准PSO 算法（惯性权重为定值，本研究取为2）、带冲撞和制动的APSO 算法（adaptive particle swarm optimization with strategy of collision and braking，APSO-WCB）两者寻优过程进行对比，两者的适应度值进化曲线见图2。

图2 两种算法基于函数f1 的适应度值进化曲线

从适应度值进化曲线可以看出，采用APSOWCB 算法其适应度进化曲线较为光滑，说明不易于陷入局部最优，并且在进化初期具有较快的收敛特性，进化次数约为5 次即达到全局收敛，表明优化后的算法性能较好。而标准PSO 算法在迭代过程中陷入局部极值的频率较多，而且多次迭代才能跳出局部极值陷阱。

第二测试函数是由正弦和余弦复合形成的复杂非线性多峰多谷函数，存在大量的凹陷、鞍点和波峰，可有效检测算法的全局探索性能。传统的优化算法很容易在寻找全局最优的过程中陷入局部最优。测试函数f2如式（6）所示，函数在区间［0，3π］的图像见图3。

图3 函数f2 图像

采用相同的算法参数设置，同样将寻优过程中标准PSO 算法和APSO-WCB 算法的适应度值进化曲线进行分析对比，两者的适应度值进化曲线见图4。

图4 两种算法基于函数f2 的适应度值进化曲线

从适应度值变化情况来看，标准PSO 算法易陷入局部极值，且摆脱局部最优的能力较弱，最终没能收敛于全局最优；APSO-WCB 算法收敛极快，得益于冲撞算子的应用，整个过程中没有陷入局部极值的情况出现，而且收敛于全局最小值，其综合效率比较高，同时也说明改进后给算法性能带来的提升还是理想的。

求解高维最优化问题最能验证智能优化算法的性能和效率，以下用一个典型的高维函数进一步测试改进后算法的性能。采用Shaffer 函数（记为f3）对其进行测试，其表达式为：

当n 取值较大时，该函数为一个典型的复杂高维函数，求解该函数最优值有助于验证智能算法在解决高维度优化问题上的寻优效率，该函数最小值点位于x=（0，0，…，0），整个定义域内函数最小值为-1。探讨10 维空间上该函数的最小值求解，所以n取值为10。仍然将标准PSO 算法和APSO-WCB 算法进行对比，两者的适应度值进化曲线见图5。从适应度函数值的变化来看，标准PSO 算法求解高维函数最优值的进化过程中，极易落入局部极值陷阱并难以逃脱，而且对该函数最优求解最终没能收敛于全局最优点。但APSO-WCB 算法最终收敛位置非常接近全局最优点，且在进化初期就能探测到最优解邻域，表明改进后的算法在复杂高维优化问题上效率亦有较大的提升。

图5 两种算法基于函数f3 的适应度值进化曲线

本研究对标准PSO 算法的惯性权重进行了动态的自适应改进，并加入对应的制动算子来提升算法的效率。同时针对算法易陷入局部极值难以逃脱的情况，引入冲撞算子加强粒子群对局部最优陷阱的逃脱能力。Matlab 环境下的测试实验结果证明改进方法给PSO 算法带来的性能提升是很显著的。另外，对算法也可以采用其他方法（如混沌初始化、多种群协同等）进行优化改进，改进后的PSO 算法在解决复杂优化问题中性能较标准PSO 算法有较大提升，在群体智能算法中具有重要的地位和应用前景。