基于多种群多策略的竞争粒子群算法

李媛媛,李文博,尚志豪

(大连交通大学 软件学院,辽宁 大连 116028)

粒子群优化算法是一种基于群体智能的优化算法,它通过模拟智能群体中每个个体的行为来解决优化问题.主要应用在工程设计[1]、控制工程[2]、路径规划[3]、计算机视觉[4]等方面.文献[1]为了在锻坯过程中找到最佳的工艺参数,改善传统数值模拟方法的不足,采用粒子群算法对参数进行优化,从材料本身和锻压成形节能的角度出发,采用该算法找到最合适的参数结果.文献[2]使用非线性PID (NLPID)控件取代了传统的PID控件,提出了一种基于广义对立学习算法的粒子群优化算法来优化NLPID控制器,成功抑制了系统超调.文献[4]提出了一种灵活的卷积自编码器,利用粒子群优化设计了一种架构发现方法,该方法能够自动搜索所提出的柔性卷积自编码器的最优架构,无需任何人工干预,大大减少计算资源,解除了传统卷积自编码器对卷积层和池化层数量的禁锢,并证明了加入粒子群算法后的新的图像分类算法远优于其他同类算法.

标准粒子群优化算法(standarding particle swarm optimization,SPSO)最初由Shi和Eb-erhart等[5]在1998年提出,它拥有惯性权重,是为了解决原始PSO算法易陷入局部最优值而进行的改进.带有压缩因子的粒子群优化算法在1999年由Clerc等[6]提出,目的是在帮助粒子跳脱局部最优值的同时加快整个优化过程的收敛速度.这两种改进方式是针对原始PSO最经典的改进方法.其他的改进算法通常都是在此基础上进行改进,方法包括：改变粒子拓扑结构、与其他算法结合、引入新的机制、或是对参数进行修改.例如：为了克服传统的Pareto最优前沿形状变化分解方法的不稳定性,Zheng Jinhua等[7]提出了1种基于对抗分解和邻域演化的动态多目标粒子群优化算法;针对存在多个pareto最优解且适应度值相同的多模态多目标优化问题,Liang Jing等[8]提出了一种具有自组织机制的多目标粒子群优化算法;Liu Yaxian等[9]通过将强化学习算法与粒子群算法结合起来,得到了自适应参数;为了使算法寻优过程中更轻松地跳出局部最优值,徐利锋等[10]在带有收缩因子的粒子群算法基础上引入了多级扰动机制.

粒子群优化算法的优势在于它可以快速收敛到最优解,同时具有较好的全局搜索能力.在众多应用中,粒子群优化算法已经取得了良好的效果,但是在实际应用中还是会出现易陷入局部最优[11-12]、收敛性差[13-14]、求解精度低[15]等问题.为了减少这些问题对算法的影响,作者对标准粒子群算法进行改进,提出基于Logistic混沌映射权重及混合高斯、柯西扰动变异,同时使用了收缩因子的多种群多策略竞争粒子群算法(multi-swarm multistrategy competitive particle swarm optimization,MMCPSO).为了获得比标准粒子群算法更好的寻优性能,作者将每一代的粒子群划分为不同的子种群,并使用不同的更新机制来更新这些子种群,从而使粒子的全局搜索能力和局部开采能力在寻优过程中达到平衡.

1 标准粒子群算法

在粒子群算法中,每个粒子的位置代表了给定问题的潜在解决方案,并使用适应度函数来评判当前位置的优劣.群体中的粒子会通过信息共享机制来更新自身的速度和位置,从而更新整个群体.群体在迭代过程中不断追寻最优粒子,在解空间内进行搜索运动,从而逐渐从无序向有序演变,最终达到在限制条件内求得待解决问题的帕累托最优解的目的.

粒子速度和位置更新公式：

vij(t+1)=wvij(t)+c1r1(pbestij(t)-xij(t))+c2r2(gbestij(t)-xij(t)).

(1)

xij(t+1)=xij(t)+vij(t+1).

(2)

其中,vij(t)表示第t代粒子i在第j维度上的速度,wvij(t)部分表示上一代历史速度对当前速度的影响,惯性权重w用来调节此影响的大小,从而调节粒子在解空间的搜寻范围,使粒子全局搜索和局部开采能力达到平衡.c1r1(pbestij(t)-xij(t))为粒子的自我认知部分,c2r2(gbestj(t)-xij(t))为社会认知部分.pbestij(t),gbestj(t)分别为粒子的个体历史最优位置和全局历史最优位置.加速度因子c1,c2分别用来调节粒子向自己历史最优位置和全局最优位置学习的步长.随机数r1,r2都取值[0,1]内,用以增加粒子搜索的随机性.

2 改进的粒子群算法MMCPSO

标准PSO寻优过程一直伴随着局部搜索能力不够强,搜索精度差,处理复杂非线性多峰问题常陷入局部最优等问题.为了摆脱这个困扰,MMCPSO根据同代种群粒子的适应度值将粒子分别划为3个子种群：优等子群(superiors)、普通子群(ordinaries)、劣等子群(inf-eriors);针对不同子种群粒子的特点分别加入扰动变异、Logistic混沌映射、收缩因子3种不同策略来进行粒子的更新;不同子种群产生的新一代粒子通过参与适应度值竞争排序后,更新到不同的子种群;算法中的每个子种群会通过粒子更新公式,不同程度的参与引领整个种群更新.不同于标准PSO的所有粒子只对本身历史最优和全局历史最优进行追逐,这种新的更新策略使整体算法寻优全程拥有较强的全局和局部寻优能力并兼具了易跳出局部最优、保持种群多样性的特性,弥补了标准PSO的不足.下面将详细介绍MMCPSO的种群划分方式和不同子种群的更新策略.

2.1 种群划分

以求最小值问题为例,在MMCPSO中,每一代的所有粒子按照适应度从低到高进行竞争排序后,求得当代种群适应度的平均值和标准差.在求最小值的优化问题中：取平均适应度一倍标准差内的粒子组成普通子群;取适应度值小于普通子群的粒子组成优等子群;取适应度值大于普通子群的粒子为劣等子群.劣等子群向优等子群和普通子群两个子群按照合理的权重学习更新,尽快向两个区域靠拢;普通子群使用带有w惯性的更新公式,平衡普通子群粒子的全局和局部探索能力.

适应度平均值和标准差的计算公式如下：

(3)

(4)

图1 子种群划分方式

2.2 优等子群更新策略

优等子群粒子已经获得了较优的适应度值,所以优等子群进行自我学习更新.同时,该种群粒子聚集在局部最优解附近.为了避免陷入局部最优,同时又使粒子具备好的局部寻优能力,作者设计了带有局部开发能力强的高斯变异和具有两翼分布概率且更易跳出局部最优的柯西变异的粒子更新方式.

高斯-柯西变异算子GC定义式：

GC=αG+(1-α)C,0<α<1.

(5)

G=Gaussion(0,1)=rand(0,1)～N(0,1).

(6)

(7)

优等子群粒子更新公式：

(8)

(9)

2.3 劣等子群更新策略

劣等子群中的个体通过主要向优等子群学习,兼顾受种群中心平均值牵引的方式更新.采用收缩因子对整个更新过程进行压缩,使劣等子群的粒子能快速脱离劣势区域向优势区域收敛,同时又能对各个学习因子进行调节,均衡了该阶段算法的收敛性能,避免在快速靠近优等子群的过程中丧失了开发能力.

收缩因子φ定义式：

c=c1+c2+c3,c≥4.

(10)

(11)

劣等子群更新公式：

(12)

2.4 普通子群更新策略

普通子群粒子处于解空间合理位置范围内,无明显优劣势,该子群进化过程中需要平衡算法的勘探和开采能力.SPSO算法使用的线性递减权重w在一定程度上平衡了粒子的全局探索和局部开发,但线性的调整方式在多维复杂非线性函数的优化过程中常陷入局部最优.混沌映射作为非线性映射方式的一种,其产生的随机序列具有良好的空间便利性.因此,作者在SPSO算法基础上对权重w加入Logistic混沌映射,用非线性权重wL对粒子的速度进行更新,使算法搜索能力均衡的同时又能很好地遍历解空间,不易陷入局部最优.

Logistic混沌映射惯性权重wL定义式：

r(t+1)=4r(t)(1-r(t)),r(0)=rand(0,1)且r(0)≠{0,0.25,0.75,1}.

(13)

(14)

普通子群粒子更新公式：

(15)

(16)

图2 惯性权重随迭代次数变化图

3 实验

3.1 标准函数测试

选取11个基本测试函数与标准粒子群算法从寻优精度、寻优速度,跳出局部最优的能力等方面进行比对,来验证MMCPSO算法的有效性.11个标准测试函数的基本信息由表1给出,fopt为函数最优值.函数f1～f6是用来测试算法寻优的快慢和所得解优劣的单峰函数,函数f7～f11为测试算法跳出局部最优,避免过早收敛的能力的多峰函数.

3.2 算法性能测试

将MMCPSO与SPSO进行对比实验,给予2种算法相同的种群大小N=90和最大迭代次数tmax=150,令二者在一个30维的解空间内对11个基本测试函数进行最小值寻优.在相同的硬件条件下,运行两个算法50次,记录两种算法50次的寻优结果,分别求取平均值(Mean)和标准差(standard deviation,SD)作为评价算法性能的指标.算法参数设置见表2.

2种算法对基本测试函数的寻优结果见表3.

表1 11个标准测试函数

表2 各算法参数表

表3 2种算法求解11个标准测试函数适应度的平均值和标准差

绘制出FPSO和MMCPSO在求解11个标准测试函数时的适应度曲线,以便更直观的对比观察2种算法的求解精度和收敛速度,如图3、图4、图5所示.

(a)f1 (b)f2

(c)f3 (d)f4图3 各算法f1～f4函数寻优适应度曲线

(a)f5 (b)f6

(c)f7 (d)f8图4 各算法f5～f8函数寻优适应度曲线

(a)f5 (b)f6 (c)f6图5 各算法f9～f11函数寻优适应度曲线

从表3可知,在标准测试函数f1～f4、f7～f9上MMCPSO算法的寻优精度较FPSO算法有着明显的数量级优势,在剩余的测试函数上新算法求得适应度的平均值也更接近函数本身的最优值.从图3、图4、图5中各个测试函数的适应度曲线可以看出新算法收敛速度更加迅速,又得益于变异机制和混沌映射惯性权重,跳出局部最优解的能力也更强.

3.3 对比实验

为了证明MMCPSO算法的优越性,将其与3种典型的PSO变体进行比较,包括自适应惯性权重的全局PSO(GPSO-AW)[16]、动态维度自适应PSO(DDAPSO)[17]和局部竞争PSO(LC-PSO)[18].具体的参数设置如表4所示.为确保用不同算法进行实验比较的公正性,测试函数的维度D设置为30,种群规模N设置为90,最大迭代次数t_max设置为150,每个算法独立运行50次.

表5给出了MMCPSO算法和当前3种PSO在11个基准测试函数上的性能比较结果.

表4 算法参数表

实验结果分析：

1)算法寻优能力.将MMCPSO 算法与GPSO-AW、DDAPSO、LC-PSO 3个算法在多个单峰、双峰函数下进行测试,MMCPSO算法表现极佳.无论是在单峰测试函数f1、f3、f4、f5,还是多峰测试函数f2、f7～f9上,其求得的Mean值比其它算法更接近测试函数的最优值.这说明该算法寻优能力出众.

2)算法稳定性.在性能评价指标中的SD值也远小于其它算法,这说明MMCPSO算法性能稳定.美中不足的是在f6和f11上MMCPSO算法的表现都不如GPSO-AW算法.

表5 不同算法性能比较

4 结语

设计了1种可以根据不同子种群状况,采用不同更新策略的改进粒子群算法MM-CPSO.MMCPSO利用竞争学习机制和收缩因子加快了劣等子群学习速度;通过引入融合的变异算子和使用自适应变异步长增大了优等子群中粒子局部开发能力和跳出局部最优的概率值;加入Logistic混沌映射惯性权重令普通子群更好地遍历解空间.新的更新策略有效地避免种群在优化单峰、多峰问题时早熟收敛和无法跳出局部最优解.改进后的算法在11个标准测试函数上的优化表现表明采用不同子种群不同更新策略能够有效取得探索和开发能力的最佳平衡.下一步的目标是将该算法引入到深度学习中,帮助神经网络模型选取优秀的初始权重和高效的网络结构模型.