基于PSO算法的SOR最优松弛因子选取研究

薛 丹，姚若侠

(陕西师范大学 计算机科学学院，陕西 西安 710119)

0 引 言

在科学和工程领域中，许多重要的问题常常可以归结为对大型稀疏线性代数系统的求解问题。这类线性代数系统的系数矩阵阶数较高，采用直接法进行Gauss消去或者是矩阵的三角分解，计算量大并且复杂度高，对于这种情况，通常采用迭代法求解[1]。迭代法是指从一个初始向量出发，按照给定的迭代公式，逐次迭代来逼近方程组的解，因此，迭代法是否收敛，收敛速度以及迭代次数成为衡量迭代算法非常重要的指标。逐次超松弛迭代法(successive overrelaxation，SOR)是对Gauss-Seidel(G-S)迭代法的改进，由Frankel和Young提出，随后被广泛应用于求解核反应扩散、石油天然气存储、天气预测等大型实际问题的数学模型[2]。求解方程组Ax=b的SOR迭代公式如下[1]：

(1)

其中，k=1,2,…表示每一步迭代计算；i=1,2,…n，xi表示解向量x的各个分量。松弛因子w是影响SOR迭代法的关键，w选取恰当，可以使SOR迭代法快速收敛，而不恰当的w可能减缓SOR迭代法的收敛速度甚至导致发散。因此，研究如何选取最优的松弛因子w在数值代数领域具有重要意义。

定理1[1]：若SOR迭代收敛，则松弛因子w需满足w(0,2)。

文献[3]指出，通过数学公式确定最优松弛因子w具有一定难度，因而另辟蹊径提出通过计算机算法选取最优松弛因子，即在区间(0,2)上分别采用二分比较法、黄金分割法、逐步搜索法选取最优松弛因子w。通过对这三种算法的研究和分析，发现传统的分割算法等虽然容易实现，但却对参数设置有较强的依赖，且无法保证在(0,2)区间上可以成功选取全局最优松弛因子。因此，该文根据群智能优化算法可以在解空间根据迭代规则智能靠近最优解的思路，拟通过粒子群优化算法(particle swarm optimization，PSO)来实现在(0,2)区间上选取SOR迭代法最优松弛因子w，以进一步推动通过计算机算法选取SOR最优松弛因子w的研究发展。

1 粒子群优化算法

粒子群优化算法是由Eberhart和Kennedy于1995年提出的一类基于群智能的随机优化算法[4]。PSO算法的基本思想来源于对鸟群捕食行为的研究：一群鸟在随机搜寻食物，如果这个区域里只有一块食物，那么找到食物的最简单有效的策略是，搜寻目前离食物最近的鸟的周围区域。粒子群优化算法自提出以来，由于形式简单，实现容易，需要调整的参数较少，已被广泛应用于多个学科和工程领域[5-6]。

1.1 PSO算法

PSO算法首先初始化一组种群数为n的随机粒子，每个随机粒子代表D维解空间的一个解，粒子i在d维的位置用xid表示，粒子i在d维的速度用vid表示，粒子通过改变vid来改变自己的位置，不断靠近潜在最优解。vid的更改受到两个极值的影响：一个极值是粒子本身找到的最优解，称为个体极值，记为pbestid；另一个极值是整个种群找到的最优解，称为全局极值，记为gbestd[4]。vid体现了粒子在群体中追随潜在最优解流动的速度和方向，文献[4]最早提出的粒子群追踪潜在最优解的进化方程如下式所示[4]：

c2r2(gbestd-xid)

(2)

(3)

其中，i=1,2,…,n；d=1,2,…,D；r1和r2是[0,1]之间的随机数；学习因子c1、c2为非负常数，通常取c1=c2=2；vid∈[-vmax,vmax]，vmax是用户设定的常数，表示速度更改的最大值。进化终止条件为预设的最大迭代次数或预定的最小适应度阈值，该算法也被称为全局版PSO算法。

1.2 PSO算法的发展

全局版PSO算法虽然形式简单、易于理解、容易实现且能快速收敛至潜在最优解，但存在容易陷入局部极值、进化后期收敛速度慢等问题，许多学者也一直致力于研究如何提高PSO算法的寻优能力。1998年，Yuhui Shi和Russell Eberhart通过给式(3)添加惯性权重(weight)来优化PSO算法的能力，并通过实验得出结论：当惯性权重在区间[0.9,1.2]时，PSO算法有较高的概率可以搜索到全局最优解[7]，修改后的进化方程如式(4)和式(5)[7]式所示：

c2r2(gbestd-xid)

(4)

(5)

很多学者将式(4)和式(5)称为基本粒子群优化算法(basic particle swarm optimization，bPSO)。

2006年，胡旺等提出简化粒子群优化算法(simple particle swarm optimization，sPSO)[8]，sPSO算法仅由粒子位置控制进化过程。实验证明，该算法能够有效避免粒子群进化后期收敛速度变慢和精度低等问题[8]。sPSO算法的进化方程为[8]：

(6)

同时，为了克服bPSO、sPSO算法在进化后期容易陷入局部极值的缺点，提出了带极值扰动的粒子群优化算法(extremum disturbed particle swarm optimization，tPSO)[8]和带极值扰动的简化粒子群优化算法(extremum disturbed and simple particle swarm optimization，tsPSO)[8]。tPSO、tsPSO算法的基本思路是：在粒子群进化方程中，通过扰动因子r3、r4分别对个体极值和全局极值添加随机扰动，以提升算法跳出局部极值的能力。具体扰动策略为：将粒子群的进化停滞步数作为随机扰动的触发条件，用t0和tg分别表示个体极值和全局极值进化停滞步数，用T0和Tg分别表示个体极值和全局极值需要扰动的停滞步数阈值。T0和Tg的具体取值由用户设定，当t0≤T0时，个体极值不需要扰动，r3=1；否则对个体极值进行随机扰动，r3=U(0,1)。同理，当tg≤Tg时，全局极值不需要扰动，r4=1；否则对全局极值进行随机扰动，r4=U(0,1)。tPSO算法的进化方程为：

c2r2(r4*gbestd-xid)

(7)

(8)

tsPSO算法的进化方程为：

(9)

扰动因子r3、r4的取值分别为：

(10)

(11)

通过对粒子群优化算法的研究及应用现状的调查和分析[9-14]，选取bPSO、sPSO、tPSO、tsPSO等四个算法分别应用在(0,2)区间上针对不同方程组Ax=b选取SOR迭代法的最优松弛因子w，实验具体设计、部署和结果分析将在下文详细介绍。

2 实验与分析

2.1 实验环境及数据准备

实验环境信息如下：Win 10操作系统，Intel®Core(TM)i7-8550U CPU处理器，8 GB内存，Python开发语言，Python3.5解释器版本，PyCharm2018.1.4开发环境。

算法的参数设置如下：种群粒子数=3，进化世代数阈值=50，c1=c2=2，惯性系数：weight=0.9，bPSO、tPSO算法中速度更改的最大值vmax=0.3；sPSO、tsPSO算法中粒子位置更改的最小值=0.001，最大值=1.999；tPSO、tsPSO算法中个体极值需要扰动的停滞步数阈值To=3，全局极值需要扰动的停滞步数阈值Tg=5。实验中用到的两个形为Ax=b的线性方程组数据[1, 3,16]如下：

b[1]=[-2,-6, 6,12]T

S[1]=[ 1,-2,-1, 3]T

b[2]=[0,5,0,6,-2,6]T

S[2]=[1,2,1,2,1,2]T

其中，S[i],i=1,2是方程组的精确解。

2.2 算法设计

应用bPSO、sPSO、tPSO、tsPSO算法在(0,2)区间上对上述两个线性方程组分别求最优松弛因子w，算法的程序流程如图1～图4所示。

图1 bPSO算法程序流程

图2 sPSO算法程序流程

图3 tPSO算法程序流程

图4 tsPSO算法程序流程

2.3 实验结果及分析

运行以上四个算法，分别对两个线性方程组在(0,2)区间各执行一次搜索SOR迭代法最优松弛因子w，程序执行结果见表1。由表1数据可知：

(2)相对于文献[3]中应用二分查找法、黄金分割法等搜索方程组1的SOR最优松弛因子w，该文应用bPSO、sPSO、tPSO、tsPSO算法搜索的w对应的SOR迭代次数为8次，优于文献[3]中的12次。

表1 四种算法选取最优w的实验结果

该文在实验编码过程中调用Python的matplotlib库，对粒子的执行过程进行了可视化展示。仅列出以上四个算法在搜索方程组2的SOR最优松弛因子时的执行过程，见图5。

(a)bPSO算法

(b)sPSO算法

(c)tPSO算法

(d)tsPSO算法

由图5(a)可以看出，bPSO算法搜索方程组2最优松弛因子w时，主要搜索区间集中在(0.5,1.5)，在进化第8次时找到最优松弛因子1.122，对应的SOR迭代次数为8次。图5(b)反映了sPSO算法实际搜索区间在(0,2)，覆盖的解区间的范围更广，粒子在进化第4次时找到最优松弛因子1.122，对应的SOR迭代次数为8次。图5(c)反映了tPSO算法主要搜索区间在(0,1.5)，在进化第26次时找到最优松弛因子1.119，对应的SOR迭代次数为8次。图5(d)反映了tsPSO算法主要搜索区间在(0,2)，几乎覆盖全部解区间，其结果最具全局最优性，且粒子在进化第35次时找到最优松弛因子1.122，对应的SOR迭代次数为8次。

3 结束语

应用bPSO、sPSO、tPSO、tsPSO等四个算法分别对两个不同的线性方程组搜索SOR最优松弛因子w，获得以下结论：

(1)bPSO、sPSO、tPSO、tsPSO算法均成功实现在(0,2)区间上选取SOR全局最优松弛因子w，且实验结果优于文献[3]中的二分比较法等算法。

(2)对于同一个方程组的应用中，bPSO算法的实际搜索区间较小，容易陷入局部极值。sPSO算法、tPSO算法、tsPSO算法，实际搜索范围相较bPSO算法有所扩大，其中tsPSO算法的搜索范围几乎覆盖了全部解区间，其搜索结果也更具全局最优性。