Computational-intelligence

一种使用收缩因子的粒子群优化算法

本文介绍的一种使用收缩因子的粒子群优化算法是基于Eberhart R C发表的一篇名为《Comparing inertia weights and constriction factors in particle swarm optimization》论文而写的,在该论文中作者首次提到了该算法,并使用该算法与带有惯性权重的粒子群优化算法进行比较。

1 摘要

在参考文献[1]中Eberhart R C提到了本文所讲的算法,并将使用惯性权重的粒子群优化算法与使用收缩因子的粒子群优化算法进行性能上的比较。通过使用五个基准函数进行比较后得出的结论是,使用收缩因子的粒子群优化算法在性能上要优于使用惯性权重的粒子群优化算法,并且这种方法在基准函数上的性能优于作者已知的任何其他已发表的结果。在之后Kennedy, J. 和 R. Mendes在《Population structure and particle swarm performance》再次提及该算法。

2 算法介绍

在文献[1]中作者介绍了一种带有收缩因子的粒子群算法,对于算法的来由却没有细致的讲解,只是说在众多的测试当中得到该方法。在文献[2]中提及这是实现了文献[3]中的第一种类型聚拢的粒子群优化算法。对于文献[3],该文分析了粒子在离散时间运动时的轨迹(代数观点),然后发展到连续时间的观点(分析观点)。开发了一个五维描述,它完整地描述了系统。这些分析导致了算法的广义模型,其中包含一组用于控制系统收敛趋势的系数。粒子群优化器的一些结果,实现了从分析中得出的修改,提出了改变原始算法的方法,以消除问题并提高粒子群找到一些经过充分研究的测试函数的最优值的能力。

但是对于本文所讲的粒子群优化算法,或许可以使用一种更为方便理解的方式进行描述。为了便于描述,接下来使用 VPSO 代指使用收缩因子的粒子群优化算法,OPSO 代指使用惯性权重的粒子群优化算法。

首先,该算法对于普通的粒子群优化算法的结构并未有较大的改变,主要变化在于速度的更新,即与在 粒子群优化二 中介绍的带惯性权重 $\omega$ 的粒子群优化算法(OPSO)相似。VPSO的速度更新公式如下: \(v_i^d=\chi(v_i^d-c_1*rand*(pBest_i^d-x_i^d)+c_2*rand*(gBest^d-x_i^d))\tag{1}\) 从公式(1)来看,VPSO与OPSO的区别并不大,OPSO速度更新公式如下: \(v_i^d=\omega v_i^d+c_1\times rand_i^d\times (pBest_i^d-x_i^d)+c_2\times rand_i^d\times (gBest^d-x_i^d) \tag{2}\) 说区别不大系数个数并未改变,仅仅是将 $\omega$ 拿到了最外面,并将该未知数的表示换成 $\chi$ ,但这同时又是一个极大的改变,在OPSO中,随着搜索进行而不断减少小的速度增量只有 $v_i^d$ ,而当防止在最外面的时候就完全改变了这种状态,此时是将整体的位移减少,以此达到更加细致的搜索效果。

这会带来怎样的效果呢?可以举一个简单的例子! 公式(2)中的速度更新是通过粒子历史最优以及全局历史最优两者的矢量和叠加得到的,而后再加上上一次速度的 $\omega$ 倍,所以可以看出粒子会以一个极高的速度接近全局最优点。而VPSO则不同,$\chi$ 在更新速度时是作用于全局,以至于粒子在接近全局最优时会减少其步长,如此就能达到更缓慢的逼近全局最优解。

在OPSO中 $\omega$ 是随迭代次数的进行在[0.9,0.5]之间线性递减的。而在VPSO中 $\chi$ 是一个定值,大小为:0.729844,而 $\chi$ 与 $c_1,c_2$ 具有如下关系: \(\chi=\frac{2}{\vert 2-\varphi-\sqrt{\varphi^2-4\varphi} \vert};\varphi=c_1+c_2,\varphi>4\tag{3}\) 在文献[1]与文献[2]中皆提到它们的取值,但是有点不一样,在文献[2]中 $c_1,c_2$ 取值是2.01,倘若取该值,则无法得到对应的 $\chi$ 值,所以应该是作者笔误,在VPSO中 $c_1,c_2$ 的取值为 2.05。

在文献[1]中作者对速度的设置是和位置取值范围相同的,同时对粒子是否越界不进行判断的,但是其实只要对应算法采用的方式一样,那么通过对比便能得出VPSO确实比其他粒子群优化算法要更为优越。

3 算法实现

VPSO实现和其他算法一样,除了速度的更新方式不同,具体代码请见code文件夹,可获取相应语言的完整代码。

4 参考文献

[1] Eberhart R C . Comparing inertia weights and constriction factors in particle swarm optimization[C]// Proceedings of the 2000 IEEE Congress on Evolutionary Computation, La Jolla, CA. IEEE, 2002. [2] Kennedy, J. and R. Mendes (2002). Population structure and particle swarm performance. Proceedings of the Evolutionary Computation on 2002. CEC ‘02. Proceedings of the 2002 Congress - Volume 02, IEEE Computer Society: 1671–1676. [3] Clerc M , Kennedy J . The particle swarm - explosion, stability, and convergence in a multidimensional complex space[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(1):58-73.