许文俊,王锡淮

(上海海事大学物流工程学院,上海 201306)

1 引言

粒子群优化PSO(Particle Swarm Optimization)算法是Kennedy等[1,2]于1995年提出的一种生物启发式算法。PSO模拟鸟群和鱼群的觅食行为,通过群体中个体的自身认知和个体之间的信息交流来实现在解空间内的寻优操作。PSO具有收敛性好、结构简单、需要设置的参数少等优点,一经提出就得到了国内外研究人员的关注,现已在微电网运行优化[3]、图像处理[4]、神经网络[5]和调度问题[6]等领域得到了广泛的应用。但是,PSO在应用中也暴露出不少缺点,如:容易陷入局部最优、收敛速度慢、搜索精度不高和鲁棒性较差等[7]。针对PSO的不足,国内外研究人员进行了大量研究,对PSO进行了诸多改进与优化。Zhang等[8]针对PSO收敛速度慢的问题,提出基于黑洞机制的PSO——RBHPSO(Random Black Hole Particle Swarm Optimization)算法,通过黑洞的吸引使粒子快速到达全局最优附近,增强了算法的全局探索能力。蒋丽等[9]为了提高PSO的群体多样性、改善算法易陷入局部最优等缺陷,在二阶振荡PSO的振荡环节采用互不相同的参数取值来调节PSO的全局和局部搜索能力,进一步提高算法的寻优能力。胡锦帆等[10]提出了基于单纯形搜索的PSO,通过自适应策略确定PSO的惯性权重,同时利用单纯形搜索来引导粒子的搜索方向,提高了PSO的收敛速度和求解精度。Mahfouf等[11]在PSO中引入了自适应惯性权重和加速因子,增强了PSO的全局搜索能力,同时为算法跳出局部最优提供了有效的机制。Du等[12]针对PSO收敛速度慢、易陷入局部最优的问题,提出了一种基于Levy飞行机制的改进自适应粒子群优化算法,通过Levy飞行的跳跃帮助算法逃离局部最优,增强了PSO的收敛速度与收敛精度。

为了克服PSO收敛速度慢、易早熟收敛的问题,本文提出了基于变尺度黑洞和种群迁徙的PSO——IRBHPSO(Improved Random Black Hole Particle Swarm Optimization)算法。其思路是引入变尺度黑洞来平衡全局探索和局部寻优的权重;引入基于混合策略的位移系数,增强算法在迭代前期的收敛速度和迭代后期的局部寻优能力;把基于种群迁徙的蝴蝶优化算法BOA (Butterfly Optimization Algorithm)[13]作为局部算子融入PSO中,改善了PSO收敛速度慢、易陷入局部最优的问题。基于12个基准测试函数进行仿真实验以及Wilcoxon秩和检验。实验结果表明,本文所提IRBHPSO改善了PSO收敛速度慢、易早熟收敛的问题,增强了PSO的全局探索能力和局部寻优能力,验证了IRBHPSO的优越性和本文所提改进策略的有效性。

2 粒子群优化算法

2.1 基本粒子群优化算法

PSO采用的是速度-位置搜索模型,PSO忽略掉粒子的质量与体积,按照一定速度飞行,根据自身经验与群体经验更新速度与位置[14]。在每次迭代过程中,粒子都会向着2个最优粒子移动,一个是粒子本身在迭代过程中搜寻到的最优点,即个体最优pbest,另一个是所有粒子在迭代过程中搜寻到的最优点,即全局最优gbest。所有粒子的速度和位置分别按照式(1)和式(2)更新:

v(t+1)=

ωv(t)+c1r1(pbest-x(t))+c2r2(gbest-x(t))

(1)

x(t+1)=x(t)+v(t+1)

(2)

其中,v(t)和v(t+1)分别为粒子在第t次和第t+1次迭代时的速度;x(t)和x(t+1)分别为粒子在第t次和第t+1次迭代时的位置;pbest为粒子的个体最优位置;gbest为粒子的全局最优位置;ω为惯性权重;c1和c2为学习因子;r1和r2为[0,1]的随机数。

2.2 黑洞机制

黑洞机制保留原位置更新策略,同时引入一种新的位置更新策略,通过黑洞吸引概率P在2种位置更新策略中选择。新的位置更新策略在以全局最优gbest为球心、R为半径的区域内设定一个假想黑洞,以黑洞吸引概率P表示黑洞对粒子吸引的能力。对于[0,1]的随机数L,如果L

(3)

其中,gbest为全局最优,R为黑洞的半径,L和r3为[0,1]的随机数,P为黑洞吸引概率。

3 改进粒子群优化算法

3.1 变尺度黑洞

黑洞机制通过假想黑洞的吸引使得粒子快速移动至全局最优附近,从而实现算法的快速寻优。黑洞机制增强了算法的全局探索能力,但该策略会使粒子过早到达全局最优附近,增加粒子陷入局部最优的可能性。RBHPSO虽然提高了PSO的收敛速度,但是并未改善PSO易早熟收敛的问题。综上,本文提出变尺度黑洞来平衡全局探索和局部寻优的权重,变尺度黑洞具体实现如式(4)所示:

(4)

其中,Rstart和Rend分别为变尺度黑洞半径Rc的迭代初始值和迭代最终值;t为当前迭代次数;T为算法最大迭代次数。

变尺度黑洞机制对黑洞半径进行改进,使其可以随着迭代次数的增加而线性减小。变尺度黑洞保留了黑洞机制较强的全局探索能力,同时平衡了算法的全局探索和局部寻优的权重。在迭代前期,粒子被黑洞吸引后,移动至当前全局最优附近。由于当前黑洞半径较大,则粒子距离当前全局最优较远,算法陷入局部最优的可能性较低;在迭代后期,当粒子被黑洞吸引,粒子移动至全局最优附近。由于此时黑洞半径较小,并且当前全局最优已经非常接近理论最优,粒子可以在局部区域内仔细寻优,算法的局部寻优能力得到改善。

3.2 基于混合策略的位移系数

在PSO的位置更新策略中,粒子位置的系数始终为1。固定的位移系数使得在迭代前期,粒子无法以较大的位移进行全局搜索,无法快速收敛;在迭代后期,粒子已经移动至全局最优附近,此时粒子又以较大的步长在全局最优附近大幅度移动,易错过全局最优值。位移系数始终为1会导致算法过度信赖已有解,同时削弱了算法潜在的全局寻优能力,放大了PSO局部寻优能力弱的缺点。基于上述分析,本文提出一种基于线性递减和混沌映射的位移系数β,简称基于混合策略的位移系数,基于混合策略的位移系数具体实现如式(5)～式(9)所示:

β=β1+β2

(5)

(6)

(7)

(8)

x(t+1)=β·x(t)+v(t+1)

(9)

其中,β1为线性递减的位移系数,β1s为β1的迭代初始值,β1e为β1的迭代最终值,St为正弦混沌映射,β2为基于正弦映射的位移系数,β为基于混合策略的位移系数。

基于混合策略的位移系数β受到线性递减策略和正弦混沌映射的作用,随着迭代次数的增加而非线性地减小。在迭代前期,β1较大,β2的比重较小,此时粒子的位移系数大于1,粒子在解空间内快速寻优,较大的步长可以加速粒子移动至全局最优附近,增强算法的收敛能力;在迭代后期,β1较小,β2的比重增大,此时粒子的位移系数较小,且在一定范围内混沌地变化。粒子以较小的位移在局部范围内仔细寻优,提高算法的收敛精度。并且若粒子陷入局部最优,在β2的作用下,粒子可以借助变化的位移逃离局部最优,有效增强了算法的局部寻优能力。

3.3 种群迁徙的BOA

蝴蝶优化算法BOA是Arora等[13]于2019年提出的启发式优化算法。BOA是受到自然界中蝴蝶通过自身的感知器官分辨食物的位置的启发而提出的。BOA参数少、原理简单、易于实现。在研究中发现,BOA的收敛速度和寻优精度要明显优于PSO[15]的。

BOA中的蝴蝶个体强调个体本身的搜索,降低了由于精英个体的错误引导而导致群体陷入局部最优的可能性。但是,BOA缺乏有效的加速收敛机制,导致其收敛速度依然较慢。为了改善PSO收敛速度慢、易陷入局部最优等问题,本文提出基于种群迁徙的BOA,将其作为局部算子融入PSO的位置更新公式中,改进后的位置更新公式如式(10)～式(13)所示:

x(t+1)=

(10)

f=C·Iγ

(11)

Lt+1=μ·Lt·(1-Lt)

(12)

(13)

其中,rand为[0,1]的随机数;f为蝴蝶产生的香味;C、I和γ分别为蝴蝶的感觉因子、香味的刺激强度和幂指数;xa(t)和xb(t)分别为随机生成的第a和第b只蝴蝶在第t次迭代的位置;P1～P3为选择概率;Lt为logistic映射;μ=4;xp(t+1)为蝴蝶个体经过种群迁徙后的位置。

在基于变尺度黑洞的PSO中加入基于种群迁徙的BOA算子,既保留了变尺度黑洞机制较强的全局寻优能力,又在BOA的作用下强调种群中个体自身的寻优,增强了算法的局部寻优能力,克服了PSO易早熟、易陷入局部最优的缺点。同时,在种群迁徙的作用下,通过全局最优解和更新后的位置引导种群整体向全局最优靠近,增加了算法的收敛速度,为算法提供了一种有效的加速收敛机制,增强了算法的全局收敛能力。

这种基于变尺度黑洞、混合策略的位移系数和以种群迁徙的BOA为局部算子的PSO称为改进RBHPSO,简称IRBHPSO。

3.4 算法步骤

本文提出的IRBHPSO寻优步骤如下所示:

步骤1种群初始化:随机生成含有N个粒子的种群,对粒子的速度和位置进行初始化。

步骤2根据适应度函数计算出粒子的适应度值,选择出个体最优和全局最优。

步骤3按照式(8)和式(12)更新正弦映射和logistic映射。

步骤4按照式(4)和式(5)更新变尺度黑洞半径Rc和基于混合策略的位移系数β。

步骤5粒子按照式(1)和式(10)更新粒子的速度和位置。

步骤6按照式(13)进行种群迁徙。

步骤7更新粒子的适应度值,并重新选择个体最优和全局最优。

步骤8判断当前运算是否满足停止条件,如果满足,输出最优结果,终止运算;若不满足,则跳转到步骤3继续运算。

IRBHPSO算法流程图如图1所示。

Figure 1 Flow chart of IRBHPSO图1 IRBHPSO流程图

3.5 IRBHPSO的时间复杂度分析

设粒子群的规模为N,算法最大迭代次数为T,搜索空间的维度为D,根据IRBHPSO的描述和时间复杂度的运算规则,增加变尺度黑洞的时间复杂度为O(N·D·T);增加基于混合策略的位移系数的时间复杂度为O(N·D·T);增加基于种群迁徙的BOA算子的时间复杂度为O(N·D·T)。所以,IRBHPSO总的时间复杂度为O(N·D·T)。因此,相较于PSO,IRBHPSO的时间复杂度并未增加,没有增加计算负担。

4 实验与结果分析

4.1 实验设计与基准测试函数

为了验证本文提出的IRBHPSO的优越性和改进策略的有效性,对12个基准测试函数进行仿真实验。实验所用基准测试函数包括4个单模态基准测试函数、4个多模态基准测试函数和4个复合基准测试函数。各个基准测试函数的相关信息如表1所示。

4.2 算法参数设置

本文在Intel®i7-5500 CPU@2.40 GHz, 内存为8.00 GB,Windows 10操作系统和MATLAB 2016a的环境下对文中所提所有算法进行仿真实验。

本文选取PSO、引力搜索算法GSA (Gravitational Search Algorithm)[16]、RBHPSO、BOA和IRBHPSO进行仿真实验。为了使实验结果可信、客观,设本文所有实验算法的种群规模N=30,算法最大迭代次数T=1000,算法其他主要参数如表2所示。

4.3 IRBHPSO性能分析

为了验证IRBHPSO的优越性,本节列出PSO、GSA、RBHPSO、BOA及IRBHPSO在12个基准测试函数上独立运行30次得到的寻优结果的最优值(best)、最差值(worst)、平均值(mean)和标准差(std),不同算法的寻优结果对比如表3所示。

4.3.1 IRBHPSO收敛精度分析

从表3可知,在f1、f2、f3、f4、f5、f6、f7、f8和f10上,相较于PSO,IRBHPSO的收敛精度高出多个数量级,并且IRBHPSO在f7上直接收敛至理论最优,以上表明IRBHPSO可以有效克服PSO易早熟、易陷入局部最优的缺点;在f11和f12上,IRBHPSO和PSO都收敛至理论最小值附近,两者收敛精度的数量级相同,表明IRBHPSO和PSO在f11和f12上的收敛能力基本一致。在f9上,IRBHPSO表现较差,PSO的收敛精度高出IRBHPSO的3个数量级,IRBHPSO未能产生较好的优化效果。根据无免费午餐NFL(No-Free-Lunch)[17,18]定理,在有限的搜索空间,对于任意2种算法,它们的期望性能是相同的,也就是说,针对某个具体的优化问题,在该问题上表现好的算法,在其他问题上的表现也可能不尽如人意。基于以上分析,IRBHPSO在大部分函数上的收敛精度均较高,但是在f9上的收敛精度较差,这种现象是可以接受的。综上所述,本文提出的IRBHPSO可以克服PSO易早熟、易陷入局部最优的缺点,有效提高了PSO的收敛精度。

Table 1 Benchmark test functions表1 基准测试函数

Table 2 Main parameters of each algorithm表2 算法的主要参数

相较于RBHPSO,IRBHPSO表现出了优良的收敛精度。除f9外,IRBHPSO的收敛精度高于RBHPSO的,表明IRBHPSO的收敛精度相较于RBHPSO的得到了提升。对比其他经典寻优算法(GSA和BOA),IRBHPSO依旧表现优异。在f1、f2、f3、f5、f6、f8和f10上,IRBHPSO的收敛精度提升多个数量级。在f4、f11和f12上,IRBHPSO的收敛精度与GSA和BOA的基本持平。在f7上,IRBHPSO的收敛精度高于GSA的,但低于BOA的。IRBHPSO仅在f9上的收敛精度低于GSA和BOA的。

综上所述,IRBHPSO无论是相较于PSO、改进PSO(RBHPSO)还是其他寻优算法(GSA和BOA),其收敛精度都处于较高水平,表明本文提出的IRBHPSO可以有效克服PSO易早熟、易陷入局部最优的缺点,验证了IRBHPSO在收敛精度上的优越性。

Table 3 Comparison of optimization results of PSO and related algorithms表3 PSO与相关算法寻优结果对比

4.3.2 IRBHPSO收敛速度分析

由于篇幅限制,同时为了直观展示不同算法的寻优过程、比较各算法的收敛速度,本节选取5种算法对f1、f2、f3、f4、f6、f7和f10的迭代进化曲线,如图2～图8所示。f1～f4为单峰函数,此类函数比较容易达到最优值;f6、f7和f10为多峰函数,此类函数具有较多局部最优,易使算法过早收敛。对于f1～f4,从图2～图5可以直观看出,IRBHPSO的收敛速度远大于PSO、GSA、RBHPSO和BOA的收敛速度,表明IRBHPSO在面对单峰函数时具有较好的全局收敛能力;对于f6、f7和f10,IRBHPSO依旧表现出了较强的收敛性能。从图6～图8可以看出,IRBHPSO的收敛速度快于或约等于其他4种算法的,表明IRBHPSO在面对复杂函数时依然可以进行很有效的全局寻优。

综上,在单峰函数和多峰函数上,IRBHPSO都表现出了较强的全局探索性能,证明IRBHPSO改善了PSO收敛速度慢的问题,增强了算法的全局探索能力,验证了IRBHPSO在收敛速度上的优越性。

Figure 2 Iterative evolution curves of PSO and related algorithms on f1图2 PSO与相关算法对f1的迭代进化曲线

Figure 5 Iterative evolution curves of PSO and related algorithms on f4图5 PSO与相关算法对f4的迭代进化曲线

Figure 6 Iterative evolution curves of PSO and related algorithms on f6图6 PSO与相关算法对f6的迭代进化曲线

Figure 7 Iterative evolution curves of PSO and related algorithms on f7图7 PSO与相关算法对f7的迭代进化曲线

Figure 8 Iterative evolution curves of PSO and related algorithms on f10图8 PSO与相关算法对f10的迭代进化曲线

4.3.3 IRBHPSO稳定性分析

算法的稳定性也是算法寻优能力的重要体现。为了进一步验证IRBHPSO的优越性,本节比较了表3中各算法对不同基准测试函数运行结果的标准差。

从表3可知,除f9、f11和f12外,在其他基准测试函数上,IRBHPSO运行结果的标准差都小于或者约等于PSO运行结果的标准差,表明IRBHPSO具有较好的稳定性和鲁棒性。在f11和f12上,虽然IRBHPSO的标准差不及PSO的,但是依然保持了较高的水平,IRBHPSO的稳定性和鲁棒性依旧较好。仅在f9上,IRBHPSO的标准差与PSO的相差较大,稳定性差于PSO的。综上,IRBHPSO在11个基准测试函数上都具有较好的稳定性,并且在9个基准测试函数上的稳定性优于PSO的,以上表明IRBHPSO的稳定性对比PSO的得到了较大的提升。IRBHPSO的良好稳定性是因为本文引入的3种改进策略平衡了算法的全局探索能力和局部寻优能力,使得IRBHPSO在相同的实验次数下可以更多次以更高的精度收敛到理想最优值附近,提高了算法的稳定性,在面对复杂问题时可以更好地寻优。

综合考虑算法收敛精度、收敛速度以及稳定性,在f1、f2、f3、f4、f5、f6、f7、f8和f10上,IRBHPSO的评价指标值都优于PSO的;在f11和f12上,虽然IRBHPSO的稳定性不如PSO的,但是IRBHPSO的收敛精度与PSO的基本相同,仍有较高水平;仅在f9上,IRBHPSO未展现出较好的优化效果。以上结论表明,IRBHPSO克服了PSO收敛速度慢和易早熟、易陷入局部最优等缺点,提高了算法的收敛精度和收敛速度,增强了算法的稳定性,验证了IRBHPSO的优越性和本文所提改进策略的有效性。

4.4 不同改进策略对比

为了展示不同的改进策略对PSO寻优能力的影响,进一步验证所提改进策略的有效性。本节将结合变尺度黑洞的PSO命名为PSO1,将结合混合策略位移系数的PSO命名为PSO2,将结合种群迁徙的BOA算子的PSO命名为PSO3。选取f1、f2、f5和f6,用PSO、PSO1、PSO2和PSO3分别对f1、f2、f5、f6独立运行30次,得到各算法对基准测试函数运行结果的平均值(mean)、最优值(best)和标准差(std),如表4所示。为了比较改进策略对算法收敛速度的影响,本节列出各算法对不同基准测试函数的迭代进化曲线,如图9～图12所示。

Table 4 Comparison ofoptimization results of PSO and single-strategy improved PSO algorithms表4 PSO与单策略改进PSO算法寻优结果对比

考虑算法的收敛精度,由表4可知,除PSO3对f5的优化结果,其他单策略改进的PSO对f1、f2、f5和f6的收敛精度相较于PSO的均得到了提升或者持平。同时,从表4还可以看出,PSO1的收敛精度是3种改进算法中最差的,但其收敛精度相较于PSO的仍有一定的提升。综上,PSO1、PSO2和PSO3的收敛精度相较于PSO的都得到了一定的提升,表明本文所提的3种改进策略都可以在一定程度上提高算法的收敛精度,验证了所提改进策略的有效性。

考虑算法收敛速度,从图9～图12中可以看出,PSO3在f1、f2、f5和f6上收敛速度极快,PSO1和PSO2的收敛速度略优于PSO的,表明本文所提改进策略可以有效改善PSO收敛速度慢的问题,增强算法的全局寻优能力,表明在本文所提3种改进策略中,PSO3中的策略在提升算法收敛速度上发挥了主要作用。

Figure 9 Iterative evolution curves of PSO and single-strategy improved PSO algorithms on f1图9 PSO与单策略改进PSO算法对f1的迭代进化曲线

Figure 11 Iterative evolution curves of PSO and single-strategy improved PSO algorithms on f5图11 PSO与单策略改进PSO算法对f5的迭代进化曲线

Figure 12 Iterative evolution curves of PSO and single-strategy improved PSO algorithms on f6图12 PSO与单策略改进PSO算法对f6的迭代进化曲线

考虑算法稳定性,从表4可知,除PSO3对f5运行结果的标准差外,3种改进算法运行结果的标准差都低于PSO运行结果的标准差,表明本文所提的改进算法比PSO更稳定,可以更有效地进行寻优。虽然PSO3对f5运行结果的标准差较大,但PSO3在f1、f2和f6上的标准差均小于PSO的标准差,表明PSO3中的改进策略可以有效提高算法的稳定性。所以,从总体上说,3种改进策略都可以提升PSO的稳定性,验证了本文所提策略的有效性。

综上,从3个评价指标的实验结果可以看出,本文所提的3种改进策略都可以在一定程度上提升算法收敛精度、收敛速度和稳定性,改善了PSO收敛速度慢和易早熟、易陷入局部最优的问题,验证了本文所提3种改进策略的有效性。

4.5 Wilcoxon秩和检验

为了进一步验证IRBHPSO的优越性和本文所提改进策略的有效性,本节采用Wilcoxon秩和检验[19]进行统计分析,判断比较IRBHPSO与其他算法之间是否有显著性差异。将PSO、GSA、RBHPSO、BOA以及IRBHPSO分别在f1～f12上独立运行15次,将IRBHPSO的15次寻优结果分别与PSO、GSA、RBHPSO和BOA进行Wilcoxon秩和检验,设置显著水平为0.05。Wilcoxon秩和检验结果分析结果如表5所示。其中,H为检验的结果,W为显著性判断结果。若H<0.05,W为“+”,表明IRBHPSO的寻优结果显著性优于其他算法的;若H>0.05,W为“-”,表明IRBHPSO的寻优结果与其他算法的无显著性差异;若H=NaN,W为“”,表明无法进行显著性判断。

从表5可以看出,在f1、f2、f3、f4、f6和f7上,相较于其他算法,IRBHPSO的寻优结果具有显著性的优势。对于f5,IRBHPSO的寻优结果与GSA、RBHPSO的相比没有显著性优势,但是相较于PSO的仍有显著性优势,表明IRBHPSO的寻优性能依旧优于PSO的。对于f8,除RBHPSO的寻优结果,IRBHPSO相较于其他算法的寻优结果均有显著性优势。对于f9,虽然IRBHPSO与4种算法对比的H值都很小,但这是因为在f9上IRBHPSO的表现较差,导致其他算法的寻优结果显著优于IRBHPSO的,从而使得IRBHPSO与其他算法的寻优结果有显著性差异。在f10～f12上,IRBHPSO与其他算法对比的H值多为NaN或者大于0.05,这是因为复合基准测试函数的维度都较小,算法容易收敛至理论最优附近,导致不同算法的寻优结果差距较小,而实际上所有算法都得到了较好的寻优效果。综上,IRBHPSO在单模态基准测试函数上具有绝对的显著性优势,在大部分多模态基准测试函数上优势明显,在复合基准测试函数上有较高的收敛精度。以上结果表明,IRBHPSO相较于其他算法表现出了更好的寻优性能,竞争优势明显,验证了IRBHPSO的优越性和本文所提改进策略的有效性。

Table 5 Results of Wilcoxon rank sum test 表5 Wilcoxon秩和检验结果

5 结束语

本文提出了一种基于变尺度黑洞和种群迁徙的PSO——IRBHPSO,在PSO的基础上引入变尺度黑洞来平衡全局探索和局部寻优的权重;在算法位置更新策略中加入基于混合策略的位移系数,增强算法迭代前期的收敛能力和迭代后期的局部寻优能力;将基于种群迁徙的BOA作为局部算子加入PSO中,改善了PSO收敛速度慢、易陷入局部最优等问题。最后通过对基准测试函数的仿真实验和Wilcoxon秩和检验验证了本文所提IRBHPSO的优越性和改进策略的有效性。IRBHPSO克服了PSO收敛速度慢和易早熟、易陷入局部最优的缺点,在收敛精度和收敛速度上都有明显的提升,体现出了算法优异的全局探索能力和局部寻优能力。由于IRBHPSO的研究处于初始阶段,接下来将扩展本文算法在实际工程问题中的应用,例如IRBHPSO在微电网日调度运行优化、分布式电源配电网动态重构和船舶微电网故障重构等任务中的应用。