群体智能优化算法处理高维多模态问题时面临的瓶颈是高维制约了每一维的可实现性和容易陷入局部最优解^[1].粒子群优化(PSO)算法^[2]是一种典型的群体智能优化算法, 但不能全局收敛^[3].QPSO算法^[4]是将PSO算法拓展到量子空间.相较于PSO算法, QPSO算法具有控制参数选择少, 收敛速度快, 进化方程形式更为简单和鲁棒性好等优势, 并且能够实现全局收敛^[4-5], 在很多领域得到了广泛应用^[6-10].但是其依然存在着粒子早熟收敛^[11]的缺陷.为此, 很多学者提出了基于QPSO的改进算法, 如用随机平均最优位置替代原始中的算法平均最优位置的QPSO算法^[12], 个体间相互协作的QPSO算法^[13], 基于平均最优位置加权的QPSO算法^[14]等.

针对QPSO算法在解决高维多模态问题存在早熟收敛的问题, 本文提出了一种改进的QPSO算法(IQPSO).IQPSO算法定义了一种动态邻域选择机制和三种不同策略的局部吸引子更新方程来保持种群的“活跃性”和“多样性”, 并且为拓展最优解空间引入了狼群优化中的综合评价方法.

1 量子行为粒子群优化算法

QPSO算法可视为PSO算法在量子空间的扩展.QPSO算法的进化方程和PSO算法具有根本的差别.PSO算法依据粒子的飞行速度进行位置的更新, 而QPSO算法以δ势阱为基础, 通过求解薛定谔方程得到粒子在某点出现的概率密度函数, 然后再利用蒙特卡洛反变换获得粒子位置^[1], QPSO和PSO的进化方程如下:

$ {m_{{\rm{bes}}{{\rm{t}}^t}}} = \frac{1}{N}\sum\limits_{i = 1}^N {{P_{{\rm{best}}_i^t}}} , $

(1)

$ P_i^t = \alpha \times {P_{{\rm{best}}_i^t}} + \left( {1 - \alpha } \right) \times {G_{{\rm{bes}}{{\rm{t}}^t}}}, $

(2)

$ X_i^{t + 1} = P_i^t \pm \beta \left| {{m_{{\rm{bes}}{{\rm{t}}^t}}} - X_i^t} \right|\ln \left( {\frac{1}{u}} \right), $

(3)

$ \left\{ \begin{array}{l} V_i^{t + 1} = w * V_i^t + \left\{ {{c_1} * {r_1} * \left( {{P_{{\rm{best}}_i^t}} - X_i^t} \right)} \right\} + \\ \;\;\;\;\;\;\;\;\;\;\;\;\left\{ {{c_2} * {r_2} * \left( {{G_{{\rm{bes}}{{\rm{t}}^t}}} - X_i^t} \right)} \right\};\\ X_i^{t + 1} = V_i^{t + 1} + X_i^t. \end{array} \right. $

(4)

式中:N为种群个数, t为迭代次数; m_best^t为种群的最优平均位置, P_besti^t为第i个粒子的历史最优位置, X_i^t为第i个粒子的当前位置, G_best^t为种群的最优位置, V_i^t为第i个粒子的当前速度; a, u, r₁和r₂均满足(0, 1)正态分布, 即(α, u, r₁, r₂~U(0, 1)), β是收缩膨胀因子, c₁和c₂是学习因子, w是惯性权重(方程(1)~(3)是QPSO的进化方程, 方程(4)为PSO进化方程).

2 改进的量子行为粒子群优化算法 2.1 自适应动态邻域选择机制

Suganthan于1999年在标准PSO算法中引入了空间邻域的概念^[15]; 同年, Kennedy引入邻域拓扑的概念来调整邻域的动态选择^[16].

Kennedy提出的邻域结构包括环形结构、随机环形结构、轮形结构以及随机轮形结构, 见图 1.环形结构是一种最基本的邻域结构, 可看出, 无论环形结构还是随机环形结构, 由于每个粒子仅仅是与两个粒子进行信息交换, 都会导致信息交流非常慢; 而在轮形结构中, 每个粒子则可与结构中除此之外的所有粒子进行信息交换, 这样能够有效的提高了粒子之间的信息传播速度.

因而, 为了提高粒子之间的信息交换效率, 保持种群的“活跃性”, 本文在文献[15-16]关于邻域结构的思想基础上, 结合轮形邻域结构的特性, 提出了一种动态邻域更新机制.

2.1.1 动态邻域生成算法

本文提出的动态邻域结构生成方式保证每个粒子至少与1个粒子进行信息交换, 其具体实现如下:

上述的动态邻域生成算法保证每个粒子的邻域规模至少为1个, 则每个粒子的邻域求解实现如下:

2.1.2 自适应邻域规模控制参数

从种群动态邻域生成算法中可看出, 邻域规模控制参数p满足p∈[0, 1], 其大小和最终生成的动态邻域有密切关联.记事件A为:rand < p; 记事件B为:事件A发生的概率变大时, 每个粒子的邻域中的最优粒子是全局最优的粒子的概率变大.则在多次独立重复实验中, 若p变大, 那么事件A发生的概率变大, 同时事件B会发生, 给出详细证明:

证明 设p, p′∈ 0, 1且满足p < p′, 在N次独立重复实验中, rand < p发生的次数记为M, rand < p′发生的次数记为M′, 则有M≤M′, 即若p变大, 事件A发生的概率变大.本文提出的邻域生成算法, 可视为概率抽样, 即每个粒子被抽取到的概率是相等的.N可看作种群数量, M和M′分别看作粒子i (i=1, 2, …, N)在p和p′时对应的邻域中的粒子数量, 事件B就转化为:从样本N中分别抽取M和M′次, 抽到最优粒子概率的大小问题.根据概率抽样理论, 每个粒子被抽到的概率是相等的, 则抽取M和M′次, 其抽到最优粒子的概率分别为$\frac{M}{N}$和$\frac{{M'}}{N}$, 则有$\frac{M}{N}$ ≤ $\frac{{M'}}{N}$.

根据上述证明可推导出, 当邻域规模控制参数较大时, 不但会使得每个粒子的邻域中具有最优粒子的概率增加, 也会使得每个粒子的邻域中具有其它“优秀粒子”(比如稍劣于最优粒子的粒子)的概率增加, 这样会使得每个粒子的邻域中的最优粒子相差不大或者相同的概率增加, 这样就与提出的多策略局部吸引子更新机制的初衷是相悖的.因而, 实验中所选取的p值不宜较大, 且p应当与N成反比, 这样保证即使N过大, 也不会导致邻域规模过大.

基于上述分析, 给出了p的表达式为

$ p = 1.0 - {\left( {1.0 - \frac{{1.0}}{N}} \right)^3}. $

(5)

p可根据实际需要调整p的大小.

2.2 多策略局部吸引子更新机制

在QPSO算法中, 每个粒子的历史最优位置都会随着进化代数的增加而变的更加优秀或者与上一次进化的结果相同.粒子的历史最优位置之所以持续不断改善, 与局部吸引子的更新方程具有密切关联, 式(2)给出了QPSO中的局部吸引子更新方程.G_best^t中汲取“优良基因”, 从而使自身变的“优秀”, 但是同时也会在一定程度上破坏粒子自身的“属性”, 从而导致整个种群的多样性出现“萎缩”, 进而会使得种群粒子过早的“成熟”.基于此, 结合文中提出的自适应动态领域选择机制, 提出一种多策略的局部吸引子更新机制.设粒子i的邻域中的最优粒子位置记为lP_besti^t, 则本文提出的多策略局部吸引子更新方程如下:

$ P_i^t = \alpha \times {P_{{\rm{best}}_i^t}} + \left( {1 - \alpha } \right) \times {G_{{\rm{bes}}{{\rm{t}}^t}}}, $

(6)

$ P_i^t = \alpha \times {P_{{\rm{best}}_i^t}} + \left( {1 - \alpha } \right) \times l{P_{{\rm{best}}_i^t}}, $

(7)

$ P_i^t = \alpha \times {P_{{\rm{best}}_i^t}} + \left( {1 - \alpha } \right) \times \left( {{G_{{\rm{bes}}{{\rm{t}}^t}}} - l{P_{{\rm{best}}_i^t}}} \right). $

(8)

式(6)是QPSO算法中的原始局部吸引子更新方程, 表示从种群最优位置中吸收“优秀基因”; 式(7)将全局最优位置替换为了邻域最优位置, 表示从邻域最优位置中吸收“优秀基因”; 式(8)将全局最优位置替换为了全局最优位置与邻域最优位置的差, 表示从两者的差中吸收“优秀基因”.可看出本文提出的多策略局部吸引子更新方程丰富了粒子进化的方向, 能够有效的抑制粒子“早熟”.提出的多策略局部吸引子更新机制的具体实现如下:

虽然算法中提出了3种局部吸引子更新策略, 但是从种群最优位置中吸收“优秀基因”依然是最有利于算法收敛到最优解的, 因而应当赋予较大的比重, 入口参数权重l需满足l∈(0, 1/3).如果l过小则无法充分体现所提出的多策略局部吸引子更新机制的有效性, 因而在实验中取l=0.2.

2.3 狼群优化的综合评价方法

在灰狼优化算法中, 为了进行模拟灰狼的狩猎行为, 确定最佳的猎物潜在位置, 会把3个最优灰狼的位置进行平均^[17].本文借鉴灰狼优化算法的综合评价方法, 在每次进化之后, 按照适应度值的优劣对种群中的所有粒子进行排序, 越优的粒子排的越靠前, 排序之后的粒子个体历史最优位置的顺序记为${{\hat P}_{{\rm{best}}_i^t}}(i = 1, 2, \cdots, N)$, 然后挑选出最优的3个粒子位置进行粒子位置平均, 得到新生成位置$\overline {{m_{{\rm{bes}}{{\rm{t}}^t}}}} $为

$ \overline {{m_{{\rm{bes}}{{\rm{t}}^t}}}} = \frac{1}{3}\sum\limits_{i = 1}^3 {{{\hat P}_{{\rm{best}}_i^t}}} . $

(9)

将新生成的位置$\overline {{m_{{\rm{bes}}{{\rm{t}}^t}}}} $与最优的全局位置G_best^t进行比较, 若优于最优的全局位置, 则用新生成的位置替代全局最优位置.

2.4 改进算法的实现流程

本文提出的改进的量子粒子群优化算法实现流程如下:

步骤1  初始化种群大小N、粒子位置X_i⁰、最大迭代次数MAXIT、粒子最优位置P_besti⁰=X_i⁰; 依据式(5)求邻域规模控制参数prob, 执行种群动态邻域生成算法, 初始化邻域结构.

步骤2  对粒子个体历史最优适应度值升序排列(假设求解最小值), 然后依据式(10)更新个体最好位置的平均位置m_best^t为

$ {m_{{\rm{bes}}{{\rm{t}}^t}}} = \frac{1}{N}\sum\limits_{i = 1}^N {{{\hat P}_{{\rm{best}}_i^t}}} . $

(10)

步骤3   由式(11)获取整个种中的历史最优位置G_best^t, 根据式(9)求解$\overline {{m_{{\rm{bes}}{{\rm{t}}^t}}}} $, 若$\overline {{m_{{\rm{bes}}{{\rm{t}}^t}}}} $优于${G_{{\rm{bes}}{{\rm{t}}^t}}}$, 则${G_{{\rm{bes}}{{\rm{t}}^t}}} = \overline {{m_{{\rm{bes}}{{\rm{t}}^t}}}} $

$ {G_{{\rm{bes}}{{\rm{t}}^t}}} = {{\hat P}_{{\rm{best}}_1^t}}. $

(11)

步骤4   对种群中的每一个粒子i（1≤i≤N）执行步骤5~7.

步骤5  执行粒子邻域求解算法, 依据适应度值的优劣找出每个粒子邻域中的lP_besti^t; 执行多策略局部吸引子更新算法得到局部吸引子P_i^t.

步骤6  由式(12)更新粒子的进化方程为

$ X_i^{t + 1} = P_i^t \pm \beta \left| {{m_{{\rm{bes}}{{\rm{t}}^t}}} - X_i^t} \right|\ln \left( {\frac{1}{u}} \right). $

(12)

其中, β和u值的选取, 请参见文献[14].

步骤7  由式(13)获取个体粒子历史最好位置为

$ {P_{{\rm{best}}_i^{t + 1}}} = \left\{ \begin{array}{l} X_i^t,f\left[ {X_i^t} \right] < f\left[ {{P_{{\rm{best}}_i^t}}} \right],\\ {P_{{\rm{best}}_i^t}},f\left[ {X_i^t} \right] \ge f\left[ {{P_{{\rm{best}}_i^t}}} \right]. \end{array} \right. $

(13)

步骤8  执行步骤3, 得全局最优位置G_best^t+1.

步骤9  重复步骤4~8, 直到迭代次数达到最大, 最终得到的G_best^t+1即为所提出算法得到的最优位置, f(G_best^t+1)即为所求得的最优解.

3 实验结果及分析 3.1 测试函数

为测试本文提出算法的寻优性能, 实验选取12个经典的多峰基准测试函数(测试函数来自于西蒙弗雷泽大学仿真实验函数集, http://www.sfu.ca/~ssurjano/index.html), 表 1中给出了每个测试函数的具体数学表达式, 搜索区间的上下限及其所对应的最优解.

3.2 参数设置

本文选取了5个进化算法进行性能比较, 即差分进化(DE)算法、PSO算法、QPSO算法、WQPSO算法和本文提出的IQPSO算法, 各算法的具体参数设置如下:

DE算法:种群数量40, 交叉率0.8, 变异控制参数的上限为0.8, 变异控制参数的下限为0.2, 最大迭代次数1 000, 重复实验次数100.

PSO算法:种群数量40, 惯性权重1, 惯性权重阻尼比0.99, 个体学习系数2.05, 全局学习系数2.05, 最大迭代次数1 000, 重复实验次数100.

QPSO算法:种群数量40, 最大迭代次数1 000, 重复实验次数100.

WQPSO算法:种群数量40, 权重设置1.5到0.5线性下降, 最大迭代次数1 000, 重复实验次数100.

IQPSO算法:种群数量40, 最大迭代次数1 000, 重复实验次数100.

以上算法的仿真硬件设备为Intel core i5 1.8 GHz 8GB RAM笔记本; 仿真软件环境MATLAB R2017a.为更好的体现算法性能在横向和纵向的对比性, 本文实验选取两个测试维度分别为10和40.

3.3 评价指标

为了比较不同算法的性能着重考虑以下几个指标:

寻优精度:用100次独立重复实验得到的最优解的平均值作为衡量的依据.

收敛速度:用同一个测试函数, 不同算法在相同条件下搜索到相同最优解所用的评价次数来衡量, 评价次数越少, 表明收敛性能越好; 反之, 越差.

稳定性:用标准差来衡量, 标准差越小, 表明算法的稳定性越好; 标准差越大, 表明算法的稳定性越差.

有效性:用来衡量IQPSO算法引入狼群优化综合评价方法有效性的指标, 本文用该方法生效的次数来衡量.

3.4 实验结果分析

表 2、3分别给出了测试维度在10和40时的实验仿真结果, 包括不同算法在不同测试函数的最优解, 平均解, 最差解和均方差.

3.4.1 寻优精度

表 4中给出了5种算法在12个基准测试函数中收敛优势的统计表现.可看出本文的提出的IQPSO算法在维度为10时, 最优解和平均最优解中的统计结果分别为11和11;在维度为40时, 最优解和平均最优解中的统计结果分别为11和12.可看出, 相较于其余4种算法, IQPSO算法在寻优精度方面具有明显的优势, 并且随着维度的增加, 这种优势进一步凸显.展现了IQPSO算法求解高维优化问题的优越性能.

3.4.2 稳定性

表 4中给出了5种算法在12个基准测试函数中均方差方面的统计表现, 可看出IQPSO算法在维度为10和维度为40时的最优均方差的个数分别是8个和12个, 也就是说相较于其余4种算法, 本文提出的算法展现出极强的稳定性, 并且这种表现随着维度增加更加凸显, 展现出提出的IQPSO算法在求解高维优化问题时的较高稳定性.

3.4.3 有效性

为检验引入的狼群优化综合评价方法的有效性, 用IQPSO算法对12个测试函数优化时的评价方法生效次数的平均值作为衡量指标, 图 2给出了IQPSO算法对12个测试函数优化时分别做100次独立重复实验(迭代次数设置为1 000次)的评价方法生效次数的平均值:

由图 2可看出, 引入的狼群算法中的综合评价方法在12个测试函数中均具有较高的生效次数.图 2(a)中最低生效次数为31, 最高生效次数为497;图 2(b)中最低生效次数为54, 最高生效次数为397;综合评价生效意味着为下一次的进化找到一个更加有利的进化方向, 能够减少算法找到最优解的次数, 并且丰富了最优解搜索空间使得IQPSO算法能够进一步提升收敛精度.

3.4.4 收敛速度

为考察不同算法的收敛速度, 图 3给出了12个测试函数在不同算法下的平均适应度值在不同迭代次数下的表现情况(由于取的是平均适应度值的对数值, 因而当平均适应度值为0时, 其对应的对数值为负的无穷大, 故不在图中体现).

从图 3可看出, 无论测试维度是10还是40, 相较于其他4种算法, 提出的IQPSO算法均展现出了明显的收敛优势(除了图 3(c), 图 3(e), 图 3(g), 图 3(e)和图 3(u)), 并且这种收敛优势随着迭代次数的增加更加凸显, 这是因为在算法后期, 粒子之间的位置差距逐渐缩小, 三种进化策略逐渐转变为在粒子自身周围寻找最优解.相较于原始QPSO算法的单一进化策略, 三种不同的搜索策略联合, 拓展了搜索范围, 强化了全局搜索能力.另外, 从图 3中也可看出, 本文提出的IQPSO算法, 在维度为40时, 其在12个测试函数中均具有收敛优势, 而维度为10时, 仅在10个测试函数中有收敛优势, 这种现象展现出了IQPSO算法解决高维优化问题的优越性.

4 结论

为了求解高维多模态优化问题, 本文在分析QPSO算法原理的基础上, 提出了一种改进QPSO算法.改进的算法通过定义的自适应动态邻域机制保持种群的“活跃性”以及采取的多策略局部吸引子方程保持种群的“多样性”, 从而实现对粒子“早熟”的抑制, 并且为了拓展最优解空间, 引入了狼群优化算法的综合评价方法.实验仿真结果验证了算法改进策略的有效性.