0 引言

粒子群优化算法(particle swarm optimization, PSO)是由Kennedy等^[1]受鸟群觅食行为启发而提出的一种基于群体智能的随机优化方法, 其主要思想是通过粒子个体的学习行为和群体之间的合作交互实现问题求解. 由于PSO算法具有结构简单、并行性强、收敛速度快等优势, 多被应用于解决多目标优化^[2]、神经网络训练^[3]、图像处理^[4]等问题. 然而, PSO也存在早熟收敛、易陷入局部最优等现象. 针对这些问题, 众多学者从多方面提出了改进方法, 如参数调整、精英选择和算法混合等不同策略^[5]. Shi等^[6]较早提出了一种惯性权重线性递减的规则; 文献[7]在此基础上通过动态调整策略提高算法的收敛性和收敛速度. 此外, 也有学者对PSO的加速因子进行了类似的改进, 提出时变自组织PSO算法(HPSO-TVAC)^[8]. 为进一步提高粒子的寻优能力, Zhang等^[9]将邻域最优解作用到速度更新公式上, 通过迭代进程决定学习强度. 近年来, 利用改变拓扑结构来选择学习榜样也得到了较好的结果. 如Chen等^[10]利用双差分突变策略设计两层新型种群结构, 采用两种不同控制参数的推理突变操作产生精英粒子, 以保证种群多样性. 文献[11]提出了一种具有异构分簇的粒子群算法(APSO-C), 采用$ K $-均值聚类对种群进行动态分簇, 通过Ring型结构对各簇进行信息交流, 选择学习样本. 许多研究表明, 动态多种群结构^[12]和自适应学习框架^[13]均能有效提高算法的全局搜索能力, 在一定程度上可以克服PSO的早熟现象. 混合算法方面, 一些学者也采用遗传算子^[14]和模拟退火操作^[15]加深局部寻优, 结合差分进化算法^[16]修正全局最优粒子. 而文献[17]还将粒子群算法与人工蜂群算法(ABC)进行杂交, 提出一种重组算法.

粒子群优化算法的寻优能力主要取决于两个特征: 开采性和勘探性^[18]. 为了平衡两者能力, 提高算法的综合性能, 与已有研究不同, 本文提出一种具有重组学习和混合变异的动态多种群粒子群优化算法(dynamic multi-population particle swarm optimization algorithm with recombined learning and hybrid mutation, DMPSORH). 借鉴小生境的思想将种群划分成规模相等的子种群以及局部PSO模型, 再对其实施不同的速度更新策略. 同时, 利用重构粒子引导速度方向来加强种群的局部开采能力, 借助于历史最优位置的子空间信息指导粒子进行局部搜索. 并且, 为了进一步扩大全局有效搜索范围, 提出一种基于概率性度量概念的混合变异策略, 在保持最优学习轨迹的同时进行自适应维度更新. DMPSORH在迭代过程中随机选择变异方式, 采用反向学习策略(opposition-based learning, OBL)和极值扰动操作(disturbed extremum, DE), 为最优粒子逃离局部困境提供更多步长增量, 引导其探索更多新区域. 重构粒子与混合变异结合, 可以在进化早期保持种群的多样性, 并加快后期收敛速度, 有效地兼顾全局勘探与局部开采能力.

1 具有重组学习和混合变异的动态多种群粒子群优化算法 1.1 标准粒子群优化算法原理

在一个$ {{\mathit{\boldsymbol{D}}}} $维的搜索空间中, 设有一个个体数为$ n $的种群$ {{\mathit{\boldsymbol{X}}}} = ({{\mathit{\boldsymbol{X}}}}_1, {{\mathit{\boldsymbol{X}}}}_2, \ldots, {{\mathit{\boldsymbol{X}}}}_n) $, 而向量$ {{\mathit{\boldsymbol{X}}}}_i = [X_{i1}, X_{i2}, \ldots, X_{iD}]^\mathrm{T} $表示第$ i $个粒子的位置. 同样, 可用向量$ {{\mathit{\boldsymbol{V}}}}_i = [V_{i1}, V_{i2}, \ldots, V_{iD}]^\mathrm{T}, {{\mathit{\boldsymbol{P}}}}_i = [P_{i1}, P_{i2}, \ldots, P_{iD}]^\mathrm{T} $分别表示第$ i $个粒子的速度及其极值(Pbest). 除此之外, 向量$ {{\mathit{\boldsymbol{P}}}}_{{g}} = [{P}_{g1}, P_{g2}, \ldots, P_{gD}]^\mathrm{T} $代表种群的全局极值(Gbest), 然后依据目标函数$ F $计算出每个$ {{\mathit{\boldsymbol{X}}}}_i $的适应度值. 第$ k+1 $代时, 第$ i $个粒子的第$ d $维的速度和位置更新公式如下:

$ \begin{align} &V^{k+1}_{id} = \omega V^{k}_{id}+c_{1}r_{1}({P}^{k}_{id}-X^{k}_{id})+\\ &\; \; \; \; \; \; \; \; \; \; \; \; \; \; \; c_{2}r_{2}({P}^{k}_{{g}d}-X^{k}_{id}), \end{align} $

(1)

$ \begin{align} &X^{k+1}_{id} = X^{k}_{id}+V^{k+1}_{id}. \end{align} $

(2)

其中: $ \omega $是惯性权重; $ c_1 $、$ c_2 $是学习因子, 为非负常数; $ r_1 $、$ r_2 $是[0, 1]之间的随机数.

飞行速度$ {{\mathit{\boldsymbol{V}}}} $可以表征粒子在整个搜索空间中进行遍历的能力^[5], 它将直接影响粒子位置更新的步长, 而为了避免粒子越界, 飞出搜索空间, 通常将其限制在$ [-V_{\max}, V_{\max}] $的飞行区域中, $ V_{\max} $一般取值为可行域的10%$ \sim $20%.

1.2 动态多种群划分策略

多种群PSO算法其实也是一种基于特殊邻域拓扑结构的局部PSO算法^[19], 相比于固定划分多种群, 动态随机重组可以避免过于限制粒子的自由, 提升个体信息交流效率. 文献[20]基于分类的思想以适应度值的均值和标准差为测度, 通过评价粒子的位置关系将种群分为多个等级. 但是在迭代后期, 优秀种群会吸引更多个体加入, 将导致粒子过于聚集, 种群间信息交流困难. 所以, 本文在此基础上以适应度值升序的中位值为界划分子种群, 每一代都实行动态调整. 适应度值较小的为“顶层粒子”, 较大的为“底层粒子”; 再从两者当中分别抽出同等数量的粒子组成局部PSO模型, 并确保3个种群规模均衡, 分别为离最优解较近的“亲邻域”、局部PSO模型的“重组域”以及“疏离域”.

“亲邻域”中的粒子适应度值较小, 需要继承种群中最优解的位置信息, 缩小步长进行更加细密的搜索; 而“疏离域”中的粒子则应扩大“步伐”, 在向全局极值靠近的同时探索周围新的优解来提升开采能力; 作为局部模型的“重组域”将动态调整种群的多样性, 既要吸取个体经验, 也要共享全局信息.

1.3 重构粒子引导及速度更新机制

粒子群在每代的飞行中都将更新历史最优位置, 而自身极值中的认知经验便会被忽略. 本文在执行速度更新时利用重构粒子保留Pbest的子空间信息, 不仅是为了保持精英学习的轨迹, 而且也从多维角度增加群体的多样性. 基于重构粒子引导的速度更新公式为

$ \begin{align} V^{k+1}_{id} = \;&\omega V^{k}_{id}+(c_{1}-c_{3})r_{1}(P^{k}_{id}-X^{k}_{id})+\\ &c_{2}r_{2}(P^{k}_{gd}-X^{k}_{id})+c_{3}r_{3}(P^{k}_{\rm mix}-X^{k}_{id}), \end{align} $

(3)

其中$ P^k_{\rm mix} $为第$ k $代的重构粒子, 其每一维度都随机选自每个粒子当前历史最优位置Pbest所对应的某一维, 且不重复选取同一个粒子的多个维度.

重构粒子生成过程如图 1所示.

下面以二维的搜索空间覆盖范围为例, 对引入重构粒子的策略进行特性分析. 为便于简化, 引入记号如下:

$ \begin{align*} &\alpha = \omega V^{k}_{i}+c_{2}r_{2}({P}^{k}_{{g}}-X^{k}_{i}), \; \beta = c_{1}({P}^{k}_{i}-X^{k}_{i}), \notag\\ &\mu = c_{3}({P}^{k}_{\rm mix}-X^{k}_{i}), \; \beta' = (c_{1}-c_{3})({P}^{k}_{i}-X^{k}_{i}). \end{align*} $

同时, 将式(1)改写成

$ \begin{align} V^{k+1}_{i} = \alpha+r_{1}\beta, \end{align} $

(4)

式(3)改写成

$ \begin{align} &V^{k+1}_{i} = \alpha+r_{1}\beta'+r_{3}\mu, \end{align} $

(5)

$ \begin{align} &\beta' = \dfrac{(c_{1}-c_{3})}{c_{1}}\beta. \end{align} $

(6)

在改写后的速度更新公式中, 由于两式存在相同项$ \alpha $, 暂且将它看作定值, 只比较其他项的变化对更新结果的影响. 因为$ r_1 $、$ r_3 $是$ [0, 1] $之间的随机数, 所以式(4)中$ V_i^{k+1} $的更新方向可能是由两个向量构成的三角形范围, 如图 2(a)所示; 而对于式(5), $ V_i^{k+1} $的最终变化方向在一定程度上取决于$ \mu $, 当前两项的向量式加权和将速度方向控制在一个范围内时, $ \mu $的引入可以引导粒子拥有更多的选择方向, 如图 2(b)所示. $ \mu $在Ⅰ区域将会小幅度地改变既定的搜索方向; Ⅱ区域的$ \mu $相对于图 2(a), 将沿合成向量方向进行伸缩并伴随一定的旋转角度. 多方向的随机扰动使得粒子因记忆历史最优位置信息而减缓了当前的学习强度, 但在一定程度上反而增强了搜索过程中的多样性. 这样的寻优方式更加适合“疏离域”中的粒子在解空间中进行波动性搜索, 加深局部学习. 同时, 图 2也可以解释某些通过新增个体来丰富多样性的策略得不到理想结果的原因, 即改进措施只是单纯强调群体的多样性而忽略了对不同搜索阶段造成的影响程度. 粒子的搜索步长随着迭代进程变小, 促使$ \mu $延续Pbest的经验逐渐与$ \beta' $方向一致, 继而实现“优中寻优”; 相反, 如果此时新增个体的精英学习操作较为薄弱, 则它的引入将会具有“对立性”, 使得个体缺乏正向进化.

本文所构建的3个子种群各自更新方式如下: “亲邻域”中的粒子采用基本PSO的更新公式, 即式(1)和(2);“疏离域”利用式(3)和(2)进行更新; “重组域”介于两者之间, 由于个体间的差异在算法前期较大, 侧重于其认知部分可以实现多方交流, 而在后期加强全局极值的引领力, 能够促使粒子向最优解的周围聚集. 因此, 学习因子引入余弦、正弦函数, 分别呈现递减和递增的趋势. 粒子位置按照式(2)更新, 有

$ \begin{align} V^{k+1}_{id} = \;&\omega V^{k}_{id}+2\cos\Big(\frac{{\rm{ \mathsf{ π}}} t}{2T}\Big)r_{1}(P^{k}_{id}-X^{k}_{id})+\\[6pt] &2\sin\Big(\frac{{\rm{ \mathsf{ π}}} t}{2T}\Big)r_{2}({P}^{k}_{{g}d}-X^{k}_{id}). \end{align} $

(7)

其中: $ t $为当前迭代次数, $ T $为最大迭代次数. 式(7)为“重组域”种群的速度更新公式.

1.4 概率性混合变异策略选择

粒子群算法在优化后期收敛速度变得缓慢的主要原因是其难以摆脱当前局部极值, 导致精度下降. 很多学者为此提出了一些改进方法, 如重新初始化^[21]、自适应PSO^[22]和杂交策略^[23]等, 并在不同程度上取得了良好的效果, 提高了收敛速度和精度. 但是, 这些改进措施缺乏对算法收敛于局部最优的根本原因以及其在不同阶段的动态效果的综合考虑, 存在一定的局限性. 文献[24]和文献[25]从数学理论的角度, 通过严格推导得到如下公式, 从而解释了PSO在进化停滞状态下的“聚集”现象:

$ \begin{align} &\lim\limits_{t\to\infty}x(t) = {P}_{{g}}' = \frac{c_{1}{P}_{i}+c_{2}{P}_{{g}}}{c_{1}+c_{2}} = \\ &\; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; \; (1-\lambda){P}_{i}+\lambda{P}_{{g}}, \end{align} $

(8)

$ \begin{align} &\; \lambda = \frac{c_{2}}{c_{1}+c_{2}}. \end{align} $

(9)

由式(8)和(9)可知, 在算法进程中, 自身极值$ P_i $和全局极值$ P_g $将决定粒子聚集位置. 当所有粒子逐步靠近$ P^\prime_{{g}} $却没有找到比$ P_g $更优的位置时, 将处于停滞状态, 从而向$ P^\prime_{{g}} $聚集陷入局部最优, 所以给$ P_g $施加变异策略将是摆脱局部极值的有效途径. 不过, 变异方式及程度将决定找到更优解的几率. 较大的变异步长确实能帮助粒子跳出当前“困境”, 但同时也有可能导致与最优值“失之交臂”, 增加寻优的难度和复杂性. 因此, 在变异过程中也需要伴随着邻域学习, 加深高密度的搜索, 这样既能给予粒子更多的搜寻机会, 也能保证其不逃离次优解的区域.

本文基于上述分析, 提出一种概率性混合变异策略(probability-based hybrid mutation, M-P), 综合采用反向学习策略(OBL)和极值扰动操作(DE), 以时变概率随机选择变异方式.

1) 最优粒子的反向学习变异.

它的主要思想是计算并评估Gbest与其反解, 从两者中选择较优值作为下一代的全局引导, 增加跳出局部最优的概率.下面给出相关定义.

定义1  反向点. 设$ X_i = (x_{i1}, x_{i2}, \ldots, x_{iD}) $为$ D $维空间中的一个点, 且$ x_{ij}\in[a_j, b_j] $, 则$ X_i $对应的反向点$ X^\prime_i = (x^\prime_{i1}, x^\prime_{i2}, \ldots, x^\prime_{iD}) $可定义为

$ \begin{align} x^\prime_j = a_{j}+b_{j}-x_{j}. \end{align} $

(10)

定义2  最优粒子反向解. 设$ X = (x_1, x_2, \ldots, $ $ x_D) $是全局极值点, 其反向解$ X^* = (x^*_1, x^*_2, \ldots, x^*_{D} $)可定义为

$ \begin{align} x^*_j = k({\rm da}+{\rm db})-x_j. \end{align} $

(11)

其中: $ x_j\in[a, b], k\in U(0, 1) $为一般化系数; $ [{\rm da}, {\rm db}] $为搜索空间中的动态边界, 按下式计算得到:

$ \begin{align} {\rm da} = \min(x), \; {\rm db} = \max({x}). \end{align} $

(12)

利用动态边界代替搜索空间中的固定边界, 既能保证生成的反向解位于逐步缩小的空间中^[26], 也能控制过度学习, 提高有效变异率. 同时, 本文考虑到全局极值的最优特性, 采用Gbest的维度最值作为动态边界, 不引入其他粒子携带的搜索信息影响它的“优越性”. 当然, 在反向学习的过程中, 反向解有飞越动态边界的可能, 因此, 对其采用下式的方法生成在$ [{\rm da}, {\rm db}] $中的随机数:

$ \begin{align} x^*_j = {\rm da}+k({\rm db}-{\rm da}), \; x^*_j<{\rm da}\; {\rm or}\; x^*_j>{\rm db}. \end{align} $

(13)

2) 最优粒子的邻域学习变异.

文献[27]提出了一种高斯变异策略(Gaussian mutation, GM), 采用下式对Gbest进行扰动:

$ \begin{align} {\rm Gbest}^\prime_d = {\rm Gbest}_{d}+r(X_{\rm max}-X_{\rm min})\rm Gaussian(\mu, \delta^2). \end{align} $

(14)

其中: $ {\rm Gbest}^\prime_d $为最优粒子扰动后的$ d $维分量, $ [X_{\rm min}, X_{\rm max}] $表示$ d $维空间的搜索范围, $ \mu $是高斯随机数的均值, $ \delta^2 $是高斯随机数的方差. 文献[27]中$ \delta^2 = |{\rm Gbest}_{d}|, r\in(0, 1) $是服从均匀分布的随机数. 该策略在一些函数的测试中取得了较好的效果, 如Rastrigin函数, 但对于另外一些复杂函数却作用不大.

本文提出的全局极值扰动策略, 主要是依据方差可调的正态随机分布对Gbest实施变异, 得到新的最优粒子$ {\rm Gbest}^\prime $, 即

$ \begin{align} {\rm Gbest}{^t_d}^\prime = N({\rm Gbest}^t_d, \delta). \end{align} $

(15)

其中$ \delta $表示相对于$ {\rm Gbest}_{d} $的不确定度, 是关于循环变量$ t $的递减函数, 用以衡量扰动值的偏离程度. 本文的$ \delta $按下式变换:

$ \begin{align} \delta = 10^{\zeta_{1}-(\zeta_{1}-\zeta_{2})\cdot t/T}. \end{align} $

(16)

其中$ \zeta_{1} $、$ \zeta_{2} $是控制正态扰动幅度的半径参数, 这里分别取$ −1 $和$ −3 $, 表示$ \delta $随算法的迭代进程从$ 10^{−1} $递减到$ 10^{−3} $. 在算法早期$ \delta $较大时, 扰动策略使得全局最优解在附近较大的邻域进行搜索学习, 并为其提供简单高效的多路径并行引导; 而后期较小的$ \delta $, 能够控制当前最优粒子几乎不再跳出较优区域, 保证算法具有较好的收敛性.

一般地, 在群体进化的初期, 进行多维度学习可以帮助最优粒子加速跳出局部极值区域, 为其提供更多的学习机会; 而在末期, 全局极值已经接近最优解, 尽量保留各维度的优势信息有利于提高算法精度. 因此, 本文采用下式进行变异维度的规模选择.

$ \begin{align} {\rm dim} = \lceil(1-(t-1)/T)\cdot D \rceil. \end{align} $

(17)

其中: dim表示选择变异的维度数量, $ D $表示维数, $ \lceil\; \rceil $表示向上取整. 同时, 基于贪婪保留策略对Gbest采用逐维更新的方式, 即

$ \begin{align} {\rm Gbest}_d = \begin{cases} {\rm Gbest}^\prime_d, \; {\rm fit}({\rm Gbest}^\prime_d)<{\rm fit}({\rm Gbest}_d);\\ {\rm Gbest}_d, \; \rm otherwise. \end{cases} \end{align} $

(18)

下面给出M-P策略的伪代码用来描述其基本步骤. 其中: TR为时变概率, 是服从$ U(0, 1) $的随机数; OR是使用反向学习策略的概率.

算法  M-P策略.

randomly disorganize $ D $;

update dim according to eq.(17);

for $ d = 1 $: length (dim)

  if TR $ < $ OR then

    generate the opposite Gbest by eq.(11);

    if $ {\rm Gbest}_d<\min({\rm Gbest})\; {\rm or}\; {\rm Gbest}_d> $

    $ \max({\rm Gbest})\; {\rm then} $

      generate the opposite $ {\rm Gbest} $ by eq.(13)

      again;

    end

  else

    execute the DE strategy on Gbest by

    eqs.(15) and (16);

  end

  compare fit and select Gbest according to

  eq.(18);

end

1.5 算法流程及时间复杂性分析

综合算法的构造思想及以上具体策略, 现给出算法流程(见图 3)和时间复杂度分析.

由图 3可以看出, DMPSORH主要包括5个部分: 初始化, 划分种群, M-P策略, 引入重构粒子, 速度、位置与极值的更新. 算法迭代一次各部分所需的操作为: 1)初始化种群的复杂度为$ {O}({N\!\cdot \!D}) $; 2)进行划分动态子种群的操作是$ O(1) $; 3) M-P策略中变异维度规模呈线性递减, 若取最大规模进行计算, 则复杂度为$ O(D) $; 4)生成重构粒子作为引导的基本运算是$ O(D) $; 5)对粒子的飞行速度、位置以及对极值的更新为$ O(N\!\cdot \!D) $. 因此, DMPSORH算法迭代一次的时间复杂度是

$ \begin{align*} &O({N\!\cdot \!D})+{O}(1)+{O}(D)+O(D)+O({N\!\cdot \!D}) = \\ &O({N\!\cdot \!D}), \end{align*} $

与基本PSO算法具有相同的复杂度.

2 数值实验及分析 2.1 测试函数

为了测试算法的性能, 本文实验采用表 1中的14个国际标准benchmark测试函数, 按照其属性分为单峰函数$ (f_1\sim f_2) $、多峰函数$ (f_3\sim f_9) $、带平移变换的函数$ (f_{10}\sim f_{11}) $和带旋转变换的多峰函数$ (f_{12}\sim $ $ f_{14}) $. 维度$ D = 30 $, 定义域$ X\in R^D, F^* $是理论极值.“threshold”为解的精度阈值$ (F-F^*) $, 用来判断算法是否运行成功.

2.2 算法构造策略的有效性和叠加影响分析

本文通过划分多种群、引入重构粒子以及使用M-P策略来提升PSO的综合性能. 本节将在基本PSO算法的基础上逐步增加相应措施, 比较几种策略在相同迭代次数下的作用. bPSO是基本PSO算法; DMPSO、PSOR、PSOH是在PSO框架中分别增加3种策略; DMPSOR是在划分动态多种群的基础上融入重构粒子作为引导, DMPSOH在划分动态多种群的基础上增加对最优解的变异策略, PSORH是在引入重构粒子的基础上实施混合变异; DMPSORH是结合3种策略的综合算法. 同时还与其他两种改进算法进行比较, 分别是HPSO-TS^[28]和CLPSO^[29].

本节实验所有算法均采取相同的迭代次数$ T = $ $ 3\, 000 $. 对每个测试函数独立运行30次, 记录中位值和平均执行时间. 实验环境为: Intel i5 CPU 2.30 GHz. RAM 4.0 GB, Windows10操作系统, Matlab R2014a. 其他参数设置如下: 种群规模$ {\rm size} = 30 $; 惯性权重$ \omega = 0.8\times {\rm e}^{(−0.5 \times t/T)} $; 最大飞行速度$ V_{\rm max} $为可行域的1/10;学习因子$ c_1 = 1, c_2 = 1.2, c_3 = 0.3 $ (bPSO、DMPSO、PSOH、DMPSOH中$ c_3 = 0) $; OR $ = $ 0.2. HPSO-TS和CLPSO的参数设置与原文献相同. 实验结果见表 2, 最优值用粗体显示, 次优值用斜体显示, 各算法运行时间见图 4.

表 2的实验结果表明:

1) 在相同的迭代次数下, 本文所提出的算法DMPSORH在14个测试函数中取得10个最优结果和4个次优结果, HPSO-TS、CLPSO分别取得7个最优结果和5个次优结果.

2) 引入重构粒子的PSOR算法和实施变异操作的PSOH算法在所有测试函数上都不同程度地优于bPSO, 可见这两种策略对算法性能的提升有一定促进作用.

3) 叠加两种策略的算法DMPSOH、PSORH都取得了5个最优结果和2个次优结果, 并且在大部分函数上都比PSOH表现优越; 同时, DMPSOR算法在函数$ f_1 $、$ f_2 $、$ f_{10} $、$ f_{11} $上比PSOR更具有优势, 并在$ f_{14} $上取得最优结果, 只有在$ f_5\thicksim f_{8} $上稍差于PSOR. 可以保守地认为, 在进行单峰及平移变换函数的优化时, 动态划分子种群可以在一定程度上改善PSOR算法的性能.

4) 与前面7个算法相比, 结合3种策略的DMPSORH算法除了在$ f_{14} $上略差于DMPSOR外, 其他计算结果均更优.

综上所述, 本文提出的3种策略都具有积极作用, 并且将其融合能够促进算法性能大幅度提升, 从而取得更满意的计算结果.

图 4中, HPSO-TS算法的执行时间最长, bPSO的时间最短, 其次是PSOR、CLPSO. 对比前4种算法可以发现, 划分种群和实施变异会导致算法时间具有明显的增长, 而融入重构粒子的策略对运行时间影响较小. DMPSORH除了在$ f_{10} $、$ f_{11} $上的时间比PSOH、DMPSOH和PSORH少之外, 其他测试时间均比前7个算法长. 总之, 组合策略确实会在一定程度上增加算法的执行时间, 但对于优化平移函数而言, DMPSORH所需时间并非处于劣势.

2.3 算法的搜索过程对比及分析

为了对比测试算法的搜索性能, 本文选取不同叠加方式并与其他两种改进类算法进行对比实验. 图 5给出了PSO、PSOR、PSORH、DMPSORH、HPSO-TS和CLPSO六种算法在30次独立运行中的迭代过程.

其中: $ x $是迭代次数, $ y $轴以对数形式表示每代最优适应度值在独立运行中的中位值.

从图 5可以看出, 与数值实验结果相似, 6种算法的进化趋势互有差异. DMPSORH和PSORH的收敛精度在大部分函数上都明显优于bPSO、PSOR和CLPSO. 在函数$ f_{1} $、$ f_{4} $、$ f_{5} $、$ f_{8} $上, DMPSORH与PSORH的收敛曲线基本重合, 这说明在对这5个函数进行优化时, M-P策略起主导作用. 从图 5(b)、(g)和(i)$ \sim $(n)中也可以发现各策略的独立效果还是不如叠加组合的效果好. 此外, 对于优化复杂函数$ (f_{10}\sim{f}_{14}) $, DMPSORH算法的进化趋势表现最好, 收敛精度和速度更具优势, 而HPSO-TS的表现相对最差, 其次是基本粒子群算法bPSO.

2.4 M-P策略与参数敏感性分析

由上述实验结果和分析可知, M-P策略对提升算法性能有显著优势. 为了进一步探究M-P策略中变异方式的效用, 将不含极值扰动策略的DMPSORH (DMPSORH-Null)和集成GM策略代替DE策略的DMPSORH (DMPSORH-GM)作为对比算法. 每个函数迭代次数为3 000, 独立运行30次. 实验中记录算法运行30次的成功率(success rate, SR), 即算法最终解达到表 1中阈值次数占运行总次数的比例. 同时, 也统计算法中变异策略成功次数的中位值(median number of successful mutation, MNSM), 若变异后的Gbest更优, 则表明变异策略成功. 表 3给出了实验结果, 其中“median”代表中位值.

从表 3的仿真结果可以看出:

1) 除$ f_{10} $外, DMPSORH在大部分测试函数上均比DMPSORH-Null、DMPSORH-GM的结果更优, 并且它的求解成功率也是最高. 此外, 在求解精度相当、成功率相同的情况下$ (f_2 $、$ f_5 $、$ f_6 $、$ f_{14}) $, DMPSORH的MNSM也高于其他两种算法, 说明融入DE策略的算法更具优势.

2) 结合GE策略的DMPSORH-GM算法在函数$ f_{3} $、$ f_{7} $上明显差于DMPSORH-Null和DMPSORH. 但在$ f_{3} $的平移和旋转变换以及$ f_{4} $的旋转变换, 即$ f_{11} $、$ f_{12} $、$ f_{13} $上, DMPSORH-GM的结果优于DMPSORH-Null, 略差于DMPSORH. 这表明GE策略在搜索空间复杂化之后能够起到一定的积极作用, 但是DE的效果更佳, 算法稳定性更强.

M-P策略中的两种变异方式以OR为转换标志. 为了测试OR对DMPSORH算法性能的影响, 本次实验将0.1作为间隔, OR取[0.1, 0.9]之间的数值, 算法最大运行次数设置为3 000. 由于$ f_{1} $ (Sphere)、$ f_4 $ (Griewank)、$ f_{6} $ (Rastrigin)、$ f_{8} $ (Weierstrass)和$ f_{9} $ (Nocon$ _{-} $Rastrigin)在测试中都收敛到了极小值, 实验中抽取$ T = 200 $的数据进行比较. 每个测试函数分别运行30次, 记录中位值. 实验结果见表 4和表 5.

表 4的实验结果表明, $ f_{1} $、$ f_{4} $、$ f_{6} $、$ f_{8} $和$ f_{9} $受OR的影响比较大. 随着取值的增加, 第200代的收敛精度在逐渐减小且有较明显的波动.但是, 这5个测试函数在达到最大迭代次数时都可以收敛到极小值, 说明在相同的迭代进程中, OR的取值将会影响算法的收敛速度.

从表 5的测试结果可以发现, 未收敛到极小值的9个函数对OR的敏感性较低, 波动幅度一般在0$ \sim $3个数量级. 但除了$ f_5 $的极值随OR取值增加而变优以外, 其他函数都呈现出基本不变$ (f_{7} $、$ f_{12} $、$ f_{13} $、$ f_{14}) $或者变差$ (f_2 $、$ f_3 $、$ f_{10} $、$ f_{11}) $的趋势. 由此可见, OR的波动对这些函数的影响不大, 却在一定程度上决定了算法的求解质量.

基于上述分析可以得出OR对不同测试函数的影响程度会有明显差异的结论, 即对表 4中的函数进行优化时可以采用较大的OR来加快收敛速度, 而对表 5中的函数则偏向用较小的OR提高算法的收敛精度. 不过, 考虑到算法的通用性和整体性并综合实验数据, 本文给出OR的取值范围在[0.2, 0.4]之间, 更有利于加强算法的求解能力. 此外, 表 3的数据结果显示: 对函数$ f_{1}\sim f_{9} $优化时, OBL表现出较强的促进作用, 在M-P策略中占据重要地位; 但是, 从OR的敏感性测试中可以看出, 频繁使用该策略反而会降低部分函数的求解精度. 所以, 充分发挥OBL策略需要合理地控制学习强度以及应用范围.

3 结论

本文在融合粒子重组学习和概率性混合变异策略的基础上, 提出了一种动态多种群优化算法. 利用重构粒子引导调整速度更新方向, 并与标准粒子群搜索探测进行一般性对比分析, 在保持子种群精英学习的基础上考虑了群体的多样性和收敛性; 算法中采用M-P策略对全局最优解进行逐维变异, 扩大群体搜索范围的同时增强了邻域探索能力, 从而较好地保持了算法的开发与勘探能力之间的平衡. 实验结果表明, 本文提出的混合改进措施具有一定协作互补作用, DMPSORH的性能在叠加各策略之后比所选对比算法表现更好, 具有较为明显的优势. 本文算法力求综合多方信息以优化种群搜索, 但还存在一定不足, 尤其面向多峰函数优化问题时种群间隐含信息的提取与利用还有待于进一步深入研究. 后续工作将结合算法对工业生产中的高维优化和多目标优化问题进行应用研究.