-
伴随人工智能的发展, 大量的启发式算法被提出, 如遗传算法、粒子群优化算法等, 这些算法在优化领域中有着出色的表现, 随着优化问题复杂程度的加深, 这些算法的弊端开始显现, 如算法"早熟"或种群多样性丧失导致精度下降, 计算成本上升等问题, 为解决这些问题近年来大量的改进策略被提出, 这些改进策略可以划分为两大类.
其中一类的改进方案属于经典力学范畴, 如对算法的参数进行调节, 1998 年 Yuhui Shi 和 Eberhart 等学者对粒子群优化算法 (PSO) 的惯性系数进行研究, 分析惯性系数对全局搜索和局部搜索的影响, 以此提高 PSO 的性能[1-3], 或是融合其他算法的某种机制以提高自身性能, 如文献[4]将粒子群优化算法的局部快速收敛性与模拟退火算法的全局收敛性结合, 提出一种协同进化的算法, 新算法在全局收敛能力和收敛速度上都有所提高, 或是以算法迭代过程中的种群为入手点, 改变种群的更新方式或将单一种群进行分组或划分, 使其多种群化, 如基于生物学上物种划分的小生境遗传算法[5]. 2010 年 Ruhai Luo 等基于人工智能体的原始结构, 将人工智能体划分为几个独立的子群体, 不同的子群体中进行通信, 这一方法被证实有效[6]. 同时也有学者基于拓扑结构或层次结构对 PSO 中粒子进行种群划分[7-9], 以此平衡算法的勘探能力和开采能力[10].
另一类改进方案是在原算法基础上引入量子机制, 从量子物理与优化问题在概率意义上的相似性出发, 通过引入量子机制提高算法的性能, 在优化算法中应用较为广泛的量子机制可分为如下几类:
(1) 量子波动的引入, 1994 年 Finnila 在模拟退火算法(SA)中引入量子波动[11], 利用系统中逐级递减的量子波动寻找经典系统的基态, 提出量子退火算法(QA). 量子波动的引入将函数优化问题转化为求解系统基态的问题, 目标函数
$ f(x) $ 则对应量子系统中的势阱, 伴随量子系统的演化, 粒子有一定的概率发生隧道效应, 在量子系统中粒子能通过势垒贯穿出现在经典禁区(可映射为最优解区间), 这称之为隧道效应, 隧道效应增强了算法跳出局部最优的能力, 但量子退火算法并未对隧道效应的发生概率进行主观控制.(2) 势阱等效, 通过薛定谔方程建立采样函数与目标函数
$ f(x) $ 之间的关系, Sun J 等学者以 Delta 势阱下的波函数模方引导粒子位置更新, 提出量子粒子群优化算法(QPSO), 将粒子寻优空间等效为势阱, 粒子的搜索行为受势阱约束, 全局最优位置映射为势能最低点位置[12-13], Wang P等学者通过模拟量子谐振子从高能态向基态收敛过程, 将目标函数以谐振子势进行等效, 提出用于解决高维函数优化问题的多尺度量子谐振子优化算法[14](Multi-scale quantum harmonic oscillator algorithm, MQHOA), 并于 2019 年通过模拟量子系统下自由粒子的运动过程解决函数优化问题, 提出了基于自由粒子模型的优化算法框架[15]. 通过势阱等效, 采用某一势阱下的波函数对粒子搜索过程进行概率描述, 较经典力学的种群确定性演化过程而言该体系下算法的随机性更强.(3) 叠加态原理的应用, 首先是 Narayanan 等学者在 1996 年通过多种群的方式将量子多宇宙的概念引入遗传算法[16], 随后 Han 等学者将量子编码和量子旋转门应用在种群的编码和更新过程中, 提出量子遗传算法[17], 叠加态原理在遗传算法中的应用提升了算法的寻优能力, 采用量子编码的染色体可表达多个态的叠加, 通过量子手段增加了种群的多样性, 类似的改进工作有量子蚁群算法[18], 同时文献[19]采用量子编码的方式对差分进化算法进行改进, 并在电力系统的优化问题中取得了不错的效果, 将量子叠加态的概率特性以量子编码的形式应用在已有的算法改进工作中被证明有效.
不论是量子退火算法中以递减的量子波动寻找量子系统基态, 还是通过势阱等效的方法使粒子在量子系统下寻找势能最低点, 在算法的迭代过程中, 粒子都有一定的概率发生量子隧道效应, 发生隧道效应的概率在函数优化问题中可衡量采样点从局部最优跳到全局最优的能力, 隧道效应的发生是量子系统特有的现象, 目前应用量子机制改进算法的方案中虽涉及隧道效应的发生, 但未对隧道效应发生概率有效控制以及隧道效应概率大小对算法性能影响做研究. 势垒与粒子簇对量子隧道效应的发生概率具有较大的影响, 因此在算法迭代过程中对这两个变量信息的获取与利用变得尤为重要, 本文以经典力学中多种群搜索方式为基础, 将子种群的个体数映射为某一粒子簇中粒子的数量, 将子种群间分布的相对位置用于评估当前粒子簇(采样点) 到函数最优解间的势垒宽度, 将经典力学下的多种群搜索策略赋予量子意义, 通过动态调节迭代过程中子种群规模而增加种群整体量子隧道效应的发生概率, 达到增强算法性能的目的, 从控制隧道效应发生概率的角度为算法改进提供一种新思路.
全文安排如下, 第1节阐述优化算法的隧道效应, 并建立多种群搜索策略隧道效应发生概率的关系, 第2节和第3节以 MQHOA 为例, 说明其优化过程背后的物理背景, 同时从发生隧道效应的角度分析该算法的不足之处, 证明通过多种群手段增加隧道效应发生概率的必要性, 然后基于蒙特卡洛评估的思想提出子种群规模自适应的策略, 第4节给出改进后具体的算法(MQHOA-d, Multi-scale quantum harmonic oscillator algorithm based on dynamic subpopulation) 并以双阱函数为例设计实验跟踪算法在寻优过程中发生量子隧道效应点的数量变化情况, 同时说明隧道效应对算法寻优的影响, 第五节设计实验并对改进后的算法(MQHOA-d) 从寻优误差、计算资源消耗等方面进行分析.
-
在经典力学体系下, 将优化算法的采样方式由单一种群采样改进为多种群采样, 从某种程度上增加了算法迭代过程中解的多样性, 由此提高原算法寻优能力, 但该方法仍存在弊端, 对于将原算法单一种群采样变为多种群采样这一类改进方案, 普遍存在一个共性, 即当算法对子种群的划分完成后, 其子种群的数目是固定的, 随着迭代进行,子种群的个体数并不会动态变化.
对于类似多种群化的改进策略, 除种群间的协作或学习等方式对算法性能的提高外, 采样过程中子种群规模的变化对算法性能也具有影响, 大量的算法改进专注于种群间的行为方式, 而忽略子种群规模自身对性能的影响. 如果从量子力学的角度看待多种群策略, 可将以多种群的形式代表的整体采样点中子种群的数量映射为粒子簇的数量, 某一子种群规模(个体数) 映射为粒子簇中粒子的数量, 当前子种群到最优解区间的距离用于势垒的评估, 目标函数
$ f(x) $ 用于势能评估, 详细对应关系见表1, 由此可将函数优化过程看作种群寻找势能最低点位置的过程, 在量子体系下粒子向势能最低点的搜索过程中, 粒子存在穿越势垒到达势能最低点的可能性, 即采样点从局部最优跳到全局最优区间, 这种现象称之为隧道效应, 也是量子系统特有的现象, 而隧道效应的发生概率受子种群个体数与当前子种群到最优解区间的距离(势垒) 所影响, 通过势垒信息自适应的调节子种群规模, 可改变总体隧道效应的发生概率, 达到增强算法寻优能力的目的, 同时弥补了经典力学下多种群改进方案忽略子种群规模自身影响算法性能的弊端.表 1 量子理论与优化算法的对应关系
Table 1. The relationship between quantum theory and optimization algorithm
量子理论 优化算法 说明 势能评估/势能最低点 $f(x)$ / $f(x)$ 的全局最小值 量子系统下将函数优化问题转化为寻找势能最低点问题 波函数 解的概率分布 量子系统下波函数对优化问题的概率描述 势阱等效 优化问题目标函数的近似方法 如QPSO中用Delta势阱逼近目标函数, MQHOA以谐振子逼近目标函数 势垒宽度 子种群位置到最优解的相对距离 势垒宽度越大, 隧道效应概率越低 量子隧道效应 跳出局部最优能力 波函数计算隧道效应概率, 增加迭代过程中发生隧道效应的采样点数量, 可提高算法性能 通过定义优化问题的波函数, 可将最优区域
$[x_0- \varepsilon ,x_0+\varepsilon]$ ($ x_0 $ 为最优解,$ \varepsilon $ 为求解误差) 发生隧道效应的概率通过波函数进行计算, 此处记为$ P_i $ , 则通过量子隧道效应在下一次迭代中出现在最优区域的个体数为$\displaystyle\sum\nolimits_{i = 1}^k {{dyn_i} \cdot P_i}$ , 其中$ k $ 为种群数,$ dyn_i $ 为第$ i $ 个子种群的规模(个体数). 在寻优过程中, 发生隧道效应的粒子将出现在最优解区域, 由于多种群采样方式具有一定的信息交流, 发生量子隧道效应的个体可引导所属的子种群向最优解方向迁移, 以此达到由各子种群组成的种群整体向最优区域收敛.这里不妨假设一种情况, 某一子种群
$ i $ 的规模(个体数) 为$ dyn_i $ 且当前区域内发生隧道效应的概率为$ P_i $ , 则该子种群在下一次迭代过程中通过隧道效应达到全局最优区间的个体数期望为$ P_i*dyn_i $ , 无限制的增大子种群规模$ dyn_i $ 可以增强该种群向最优解区间的迁移能力, 但该操作会改变种群采样率, 文献[20]指出增加采样点(种群规模)的数量会提高采样率, 而采样率越小算法效率越高, 出于上述考虑, 基于蒙特卡洛估计的思想[21], 提出可以根据种群适应度动态调节子种群个体数的策略, 该策略在不改变算法采样率的基础上改变了迭代过程中种群发生隧道效应的概率, 由此提高了算法性能, 同时这一策略可以广义的应用在各种优化算法的改进工作中.下节将以 MQHOA 为例, 从控制隧道效应的角度对该算法做改进, 选择 MQHOA 作为改进案例的原因在于该算法是基于量子理论提出的优化算法, 若选择经典力学体系下的优化算法作为目标算法, 量子机制的引入容易从多个维度增强算法随机性(如种群在量子体系下的叠加性), 虽然能增强算法性能达到改进的目的, 但无法准确的验证通过子种群规模自适应改变隧道效应的发生对提高算法寻优能力的有效性. 而 MQHOA 以薛定谔方程为基础, 建立了优化问题与量子系统之间的关系, 将优化问题转化为求解粒子在约束下的基态波函数, MQHOA 在迭代过程中会自发的产生隧道效应, 以 MQHOA 为目标算法, 通过动态调节子种群个体数的方式改变其迭代过程中发生隧道效应的粒子数, 可以更好验证通过隧道效应改进优化算法的有效性和可行性.
-
量子力学中波函数可以描述粒子在某位置出现的概率, 通过文献[22]可知, 薛定谔方程可以描述量子系统, 不随时间变化的薛定谔方程表示如下:
$$ \begin{array}{l} E\psi (x) = \left( { - \dfrac{{{\hbar ^2}}}{{2m}}\dfrac{{{d^2}}}{{d{x^2}}} + V(x)} \right)\psi (x) \end{array} $$ (1) 其中
$ \hbar $ 为普朗克常数,$ m $ 为粒子的质量,$ \psi (x) $ 为波函数,$ V(x) $ 为粒子的势阱. 可将目标函数$ f(x) $ 代替薛定谔方程中的势阱$ V(x) $ , 同时在目标函数$ f(x) $ 全局最小值的位置采用泰勒序列展开$f(x) = f({x_0}) \!+\! f'({x_0})(x \!-\! {x_0}) \!+\! \dfrac{1}{2}f''({x_0}){(x \!-\! {x_0})^2} \!+\! \cdots.$ MQHOA通过二阶近似下谐振子的基态波函数表达优化问题的解, 由于更高阶的泰勒展开所对应势能的薛定谔方程很难解出一个简单的概率分布作为基态波函数, 而二阶近似下谐振子的基态波函数已可以较好的表达优化问题的解, 因此只对泰勒展开式做二阶近似. 其中$ {x_0} $ 为极值位置, 可知$ f({x_0}) $ 为一常数, 由于$ f'({x_0}) = 0 $ 且常数项$ f({x_0}) $ 对$ V(x) $ 的最小值位置无影响, 因此去除高次项后$f(x) \cong \dfrac{1}{2}f"({x_0}) {(x - {x_0})^2}$ , 优化问题是以目标函数$ f(x) $ 为势能约束下的量子系统, 即薛定谔方程中的$ V(x) = f(x) $ , 因此优化问题的薛定谔的表达形式如下:$$ \begin{array}{l} E\psi (x) = \left( { - \dfrac{{{\hbar ^2}}}{{2m}}\dfrac{{{d^2}}}{{d{x^2}}} + f(x)} \right)\psi (x) \end{array} $$ (2) 通过薛定谔方程的变换, 可将求解目标函数最小值问题转化为求解谐振子势阱下的基态波函数的问题. 经过近似操作后, 波函数在基态的概率密度函数如下:
$$ \begin{split} &{\left| {{\psi _{\rm{0}}}(x)} \right|^{\rm{2}}} = \sqrt {\dfrac{{m\omega }}{{\pi \hbar }}} \cdot \; \exp ( - \dfrac{{m\omega {x^2}}}{\hbar })\\ &\omega = \sqrt {\dfrac{k}{m}} \end{split} $$ (3) 由等式(3) 可知, 目标函数的最优解的概率分布为高斯分布. MQHOA 算法以高斯采样为基本操作,
$ k $ 个高斯采样点作为粒子, 利用$ k $ 个高斯采样叠加作为波函数描述当前最优解的概率分布, 在 MQHOA 的收敛过程中, 谐振子波函数从高能态逐步变向基态, 从高能态多个正态分布的概率叠加, 逐步收敛到基态单一正态分布的稳定状态, 此时算法获得最优解. -
MQHOA 算法流程如下所示:
算法 1. MQHOA 算法
1: Initialize
$ k $ ,$ {\sigma _{{\rm{min}}}} $ ,$ S = \left[ {LB,LU} \right] $ ,$ {\sigma _s} $ 2: Randomly
$ {x_i} $ in domain$ \left[ {LB,UB} \right] $ 3: Calculate the standard deviation
$ {\sigma _k} $ for all$ x_i $ 4: while
$ {{\sigma _s} > {\sigma _{\min }}} $ do5: while
$ {{\sigma _k} > {\sigma _s}} $ do6: while
$ {\Delta {\sigma _k} > {\sigma _s}} $ do7:
$ \forall {x_i} $ , generate$ x^{'}_i \sim N({x_i}, \sigma _s^2) $ 8:
$ \forall {x_i} $ and$ x^{'}_i $ , if$ f(x^{'}_i) < f({x_i}) $ then$ x_i = x^{'}_i $ 9: Calculate
$ {\sigma _k} $ for all$ x_i $ 10:
$ \Delta {\sigma _k} = \left| {{\sigma _k} - \sigma^{'} _k} \right| $ 11: Update
$ \sigma^{'} _k:\sigma^{'} _k \leftarrow {\sigma _k} $ 12: end while
13: Update the worst solution:
${x^{worst}} = {x^{mean}}$ 14: end while
15:
$ {\sigma_s} = {\sigma_s}/2 $ 16: end while
17: Output
$ x^{best} $ ,$ f(x^{best}) $ 其中参数
$ k $ 为采样中心数,$ S $ 为第一次采样区间,$ \sigma_0 $ 和$ \sigma_{min} $ 分别为初始尺度和最小尺度, 其中$ \sigma_{min} $ 对算法解的精度具有重要影响.$ f(x) $ 为目标函数. 伪代码中从内到外的三层循环分别对应 MQHOA 的3种物理过程, 分别是能级稳定、能级下降、尺度下降. 第一层循环即对应能级稳定过程, 在此过程中以$ k $ 个采样点为中心分别按正态分布$ N\left( {{x_i},\sigma^{2}_s} \right) $ 在每一个维度进行采样, 以此生成新的采样点, 计算当前采样点的目标函数值$ f(x^{'}_i) $ 是否小于当前采样中心的目标函数值$ f({x}_i) $ , 满足则进行替换, 不满足则暂不替换当前采样中心. 此外, 如采样过程中受优化空间限制, 则使用映射操作将越界点映射到优化空间内, 在此文不讨论映射机制.当
$ k $ 个位置的采样中心全部完成采样后, 计算$ x_0\sim x_k $ 的方差$ \sigma_k $ , 然后与迭代前的方差$ \sigma^{'}_k $ 做差, 计算出迭代前后方程的变化量$ \Delta{\sigma_k} $ . 如果$ \Delta{\sigma_k}<\sigma_s $ 则判定算法能级稳定过程结束, 进行能级下降操作, 以$ k $ 个采样点的均值替换当前目标函数值最差的采样点即$ {x^{worst}} = {x^{mean}} $ . 当算法基态判据满足$ {\sigma _k} < {\sigma _s} $ 时, 可认为算法达到了尺度$ \sigma_s $ 下的能量基态, 将进行尺度下降过程, 这个过程通过尺度减半的操作即$ \sigma_s/2 $ 降低当前尺度, 这一过程决定了搜索精度, 随着尺度下降这一步骤的进行, 算法从全局搜索逐步过渡到局部搜索. -
原算法(MQHOA)忽视了不同采样中心在整个迭代过程中的适应度值是变化的, 不同采样中心发生隧道效应概率不同, 因此在每个中心位置采取相同的采样行为是不合理的. 在解空间中, 当部分采样点陷入局部最优区域时应增强该区域种群通过隧道效应跳出该区域的能力, 由于原算法存在上述缺陷, 由此对部分函数寻优时容易发生算法"早熟"现象.
MQHOA搜索过程为
$ k $ 个正态概率分布不断向最优解位置迭代的过程, 即算法的波函数为$ k $ 个正态分布的叠加, 可用公式 (4) 表示.$$ \begin{array}{l} {\left| {\psi (x)} \right|^{\rm{2}}} = \displaystyle\sum\limits_{i = 1}^k N ({x_i},\sigma^{2}_s) = \sum\limits_{i = 1}^k {\dfrac{1}{{\sqrt {2\pi } {\sigma _s}}}} {e^{\textstyle\frac{{{{(x - {x_i})}^2}}}{{2\sigma^2 _s}}}} \end{array} $$ (4) 以一维函数为例,
$ x_i(i = 1,2,3...k) $ 为当前各正态分布期望,$ \varepsilon $ 为误差上限, 存在$ k $ 个正态分布$ N_i^{}({x_i},\sigma _s^2) $ , 对$ k $ 个正态分布约束下的任一采样点$ x_i $ 在当前采样中能找到最优解的概率为:$$ \begin{array}{l} {P_{({x_i})}} = \displaystyle\int\limits_{{x_0} - \varepsilon }^{{x_0} + \varepsilon } {N_i^{}({x_i},\sigma _s^2)dx} = \int\limits_{{x_0} - \varepsilon }^{{x_0} + \varepsilon } {{\dfrac{1}{{\sqrt {2\pi } {\sigma _s}}}}{e^{\textstyle\frac{{{{(x - {x_i})}^2}}}{{2\sigma^2 _s}}}}dx} \end{array} $$ (5) 此时以该正态分布进行采样的种群发生量子隧道效应采样点的数量计算公式为:
$dyn_i \cdot \int\nolimits_{{x_0} - \varepsilon }^{{x_0} + \varepsilon } {{N_i}({x_i},{\sigma _s}^2)} dx$ 其中$ x_0 $ 为最优解位置,$ dyn_i $ 为以当前正态分布采样的子种群个体数, MQHOA 为单一种群采样, 可看作$ k $ 个规模为1(采样点) 的子种群集合所构成的种群整体(单一种群), 因此对 MQHOA 而言$dyn_i = 1, (i = 1,2,3,\cdots k)$ . 由于采样中心$x_i(i = 1,2,3\cdots k)$ 的不同, 进行$ N_i^{}({x_i},\sigma _s^2) $ 采样时, 采样点落在区间$ [x_0-\varepsilon ,x_0+\varepsilon] $ 的概率$ P_{(x_i)} $ 具有差异性, (在高维函数解空间中任意两采样中心$ x_1,x_2 $ 相等的概率极低, 因此不考虑这种情况). 图1 所示的2条高斯曲线分别代表采样中心$ x_1 = 2,x_2 = 8 $ 的概率密度分布情况,$ x $ 轴上的黑点代表最优解$ x_0 $ 的位置, 阴影部分为采样点落在区间$ [x_0-\varepsilon ,x_0+\varepsilon] $ 的概率$ P_{(x_i)} $ , 以$ x = 2 $ 为中心的高斯曲线下阴影部分面积大于以$ x = 8 $ 为中心的高斯曲线下的阴影部分面积, 即在这次采样过程中$ x = 2 $ 为中心的采用区域能获得最优解位置的概率大于以$ x = 8 $ 采样中心的区域. 因此采样成功的概率会随采样中心的变化而产生差异.
图 1 不同采样中心概率密度曲线
Figure 1. Probability density curves of different sampling centers
本文将采样中心在当前迭代中能找到最优解的概率称作适应度值, 适应度的大小以采样点与最优解间的势垒宽度评估, 在采样点所构成的集合中, 采样点
$ x_i $ 通过隧道效应跳到最优解区域的概率最大, 本文仅需比较$ k $ 个采样中心适应度的排名, 不需要进行精确计算, 且当前适应度值最大的采样中心$ x_{best} $ 应满足:$$ \begin{array}{l} \displaystyle\int\limits_{{x_0} - \varepsilon }^{{x_0} + \varepsilon } {N_{best}^{}({x_{best}},\sigma^2 _s)dx} \ge \int\limits_{{x_0} - \varepsilon }^{{x_0} + \varepsilon } {N_r^{}(x{_{r}},\sigma^2 _s)dx} \end{array} $$ (6) 公式(6)中
$ x_r $ 为除具有最大适应度采样点$ x_{best} $ 外的任一采样点, 原算法忽略了对适应度不同的采样中心进行区别采样, 导致种群在适应度较小的区域采样时, 不能准确获取最优解位置信息, 即能级稳定过程缓慢且易陷入局部最优解, 同时影响收敛速度. 实验表明当目标函数的维度较高时, 在规定的迭代次数中 MQHOA 的求解成功率会大幅度的降低. 当算法随着迭代次数的增加, 从全局搜索过渡到局部搜索后, 这种采样策略在搜索能力上的不足开始体现, 寻优误差较大.为了解决上述问题, 针对不同适应度的采样中心, 在一次迭代过程可以进行重复次数的采样, 即同一采样空间进行
$ m $ 次的采样, 同一波函数下的采样点成功率$ p{(x_i)} $ 为定值, 且采样操作相互独立, 因此满足二项分布$ \zeta \sim B(m,p({x_i})) $ . 在重复采样操作中, 当满足$ \exists $ $ x^{'}_i $ $ \in $ $ \left[ {{x_0} - \varepsilon ,{x_0} + \varepsilon } \right] $ 时, 即可判定采样成功,$ x^{'}_i $ 为该算法以$ x_i $ 为某一子种群的中心生成的采样点, 以$ x_i $ 为子种群中心生成的采样点集合记为$ \; S $ ,$ x^{'}_i $ 为集合$ \; S $ 中的任一元素, 此时采样中心$ x_i $ 的成功率应为:$p{({x_i})^{'}} = 1 - C_m^{0}p{({x_i})^{0}} \cdot {(1 - p({x_i}))^{m}}$ 其中$ m $ 为大于1 的正整数, 其值根据适应度不同而动态调节, 具体的适应度计算方法将在下一节中说明. 由于$ p({x_i}) \in \left( {0,1} \right] $ 因此$1 - p({x_i}) \in \left[ {0,1} \right)$ , 可以证明$1 - C_m^0p{({x_i})^0} (1 - p({x_i}))^m > p({x_i})$ 因此可以推出改进后的$ p{({x_i})^{'}}>p(x_i) $ . -
函数的优化问题从某方面是具有黑盒特性的, 在优化问题中目标函数的表达式
$ f(x) $ 是不确定的, 在迭代过程中, 每一个子种群发生$ m_i $ 次测量,$ m_i $ 为当前子种群的个体数(规模), 实际上可以将采样映射为对函数$ f(x) $ 积分的评估. 通过上一节可知增加以当前中心$ x_i $ 的采样次数$ m_i $ 可以增大找到最优解概率, 本小节具体分析对不同$ m_i $ 之间是否应该具有差异. 基于蒙特卡洛思想[23] 我们知道采样越多, 越近似于最优解. 对于函数优化, 在最优解$ x_o $ 所在误差范围$ [x_0-\varepsilon ,x_0+\varepsilon] $ 内, 应满足:$$ \begin{array}{l} \displaystyle\int\limits_{{x_0} - \varepsilon }^{{x_0} + \varepsilon } {f(x)} dx \le \int\limits_{{x_i} - \varepsilon }^{{x_i} + \varepsilon } {f(x)} dx \end{array} $$ (7) 由于MQHOA采样过程中尺度
$ \sigma_s $ 是不断递减的, 对于$ k $ 个子种群搜索过程而言, 实际上是评估$ k $ 个子种群在当前尺度下积分最小的问题, 表达如下:$$ \begin{array}{l} \min \left(\displaystyle\sum\limits_{i = 1}^k {\int\limits_{{x_i} - {\rm{3}}{\sigma _s}}^{{x_i}{\rm{ + 3}}{\sigma _s}} {f({x})} dx} \right) \end{array} $$ (8) 由于波函数概率密度函数为正态分布, 函数采样区间有限, 这里做近似处理
$\int\nolimits_{{x_i} - {\rm{3}}{\sigma _s}}^{{x_i}{\rm{ + 3}}{\sigma _s}} {{N_i}({x_i},{\sigma _s}^2)} dx = 1$ . 因此函数优化问题可以映射到所在定义域内以$ [x_i-\varepsilon ,x_i+\varepsilon] $ 为区间, 此时$ \varepsilon = 3\sigma _s $ , 评估积分最小化的问题. 利用蒙特卡洛方法可以实现对${\int\nolimits_{{x_i} - {\rm{3}}{\sigma _s}}^{{x_i}{\rm{ + 3}}{\sigma _s}} {f({x_i})} dx}$ 的估计, 蒙特卡洛算子如下:$$ \begin{array}{l} {F_N} = \dfrac{1}{N}\displaystyle\sum\limits_{i = 1}^N {\frac{{f({x_i})}}{{P({x_i})}}} \end{array} $$ (9) 公式(9)是以
$ x_{i(i = 1...k)} $ 为中心的子种群对当前区域的评估蒙特卡洛算子,$m_{i(i = 1\cdots k)}$ 为该子种群的规模(个体数),$P(x_i)_{(i = 1\cdots k)}$ 为当前第$ i $ 个子种群的概率密度函数其中$ N $ 为采样次数, 它与$ m_i $ 相对应,$ f(x) $ 为目标函数,$ P(x) $ 为$ x $ 的概率密度函数, 我们记$\dfrac{{f({x_i})}}{{P({x_i})}} = g(x_i)$ , 据大数定律可知:$$ \begin{array}{l} \mathop {\lim }\limits_{N \to \infty } {F_N} = E[g({x_i})] \end{array} $$ (10) 由此可以推出区间内积分在
$ N $ 次重复采样下的表现形式:$$ \begin{split} E[g({x_i})] =& \displaystyle\int\limits_{{x_0} - \varepsilon }^{{x_0} + \varepsilon } {g({x_i})} \cdot P({x_i})dx\\ \mathop {\lim }\limits_{N \to + \infty } {F_N} =& \int\limits_{{x_0} - \varepsilon }^{{x_0} + \varepsilon } f ({x_{}})dx \end{split} $$ (11) 对于不同中心
$ X_i $ 而言, 定义域内的采样概率密度函数具有差异, 而固定区间内对函数的积分为定值, 此时应分析概率密度函数对积分评估的影响, 我们知道所有采样中心点服从正态分布的方差是相同的, 不同的是期望, 而期望值为采样中心的坐标信息. 此时计算方差$ Var[F_N] $ :$$ \begin{split} &Var[{F_N}] = E[{F_N}^2] - E{[{F_N}]^2}=\\ &\dfrac{1}{{{N^2}}}\left(E\left[{\left(\displaystyle\sum\limits_{i = 1}^N {g({x_i})} \right)^2}\right] - E{\left[\sum\limits_{i = 1}^N {g({x_i})} \right]^2}\right)=\\ &\dfrac{1}{{{N^2}}}Var\left[\sum\limits_{i = 1}^N {g({x_i})} \right] \end{split} $$ (12) 我们记
$ g(x_i) $ 方差为$ {\sigma ^2} $ , 此时$ g(x_i) $ 相互独立, 因此蒙特卡洛方差与$ {\sigma ^2} $ 的关系为:$$ \begin{array}{l} Var[{F_N}] = \dfrac{1}{{{N^2}}}Var\left[\displaystyle\sum\limits_{i = 1}^N {g({x_i})} \right] = \dfrac{{{\sigma ^2}}}{N} \end{array} $$ (13) 可以看出, 当
$ N $ 越大时, 蒙特卡洛估计的方差越小,$ N $ 为大于等于1的定值, 且$ N = m_i $ , 从蒙特卡洛估计上看, 不同种群的规模不一样, 其采样数的不同对种群自身所处位置的评估具有差异性, 且误差为$O\left( {1/\sqrt N } \right)$ , 每一个子种群所评估的区域积分占总体的比例为$\int\nolimits_{x - {\rm{3}}{\sigma _s}}^{x{\rm{ + 3}}{\sigma _s}} {f(x)} dx/ \sum\nolimits_{i = 1}^k {\int\nolimits_{{x_i} - {\rm{3}}{\sigma _s}}^{{x_i}{\rm{ + 3}}{\sigma _s}} {f(x)} dx}$ , 适应度差的子种群其分布区域积分较其他种群而言偏大, 为了保证总体评估准确性, 将适应度差的子种群尽可能在下一次迭代中扩大规模, 扩大子种群规模会提高该子种群发生隧道效应的概率, 提高适应度差的子种群向最优解区间的迁移能力, 而适应度好的子种群可适量缩减其种群规模, 以此保证总体评估的误差和采样效率, 该方法在不改变采样率的情况下对隧道效应实现了有效控制. -
$ k $ 个种群以当前种群中心的波函数为基准进行采样, 每个子种群的个体数$ {m_i}_{(i = 1 \cdots k)} $ 的更新是根据当前中心到适应度最高种群中心的欧氏距离决定, 更新公式见 (14) 其中$ n $ 为维度大小,$ l $ 为当前维度:$$ \begin{array}{l} d({X^i},{X^{best}}) = \sqrt {\displaystyle\sum\limits_l^n {{{\left(x_l^i - x_l^{best}\right)}^2}} } \end{array} $$ (14) $ {X^i} $ 是当前种群中心,$ {X^{best}} $ 为适应度最高的采样中心, 依据欧氏距离的种群规模更新见公式 (15):$$ \begin{array}{l} dyn^{i}_g = \frac{{d\left({X^i},{X^{best}}\right)}}{{\displaystyle\sum\limits_{i = 1}^k {d({X^i},{X^{best}})} }} \cdot \lambda \end{array} $$ (15) 其中
$ dyn^{i}_g $ 为 第$ i $ 次迭代过程中第$ g $ $(g = 1, 2,3\cdots k)$ 个子种群的当前个体数,$ \lambda $ 为定值, 代表所有种群中个体总数.公式 (14)通过各子种群中心
$ X^{i} $ 到当前最优子种群中心$ X^{best} $ 的欧式距离评估各子种群所处解空间的适应度, 离当前最优子种群中心距离越远, 则判断该子种群适应度越差, 由此通过公式 (15) 更新该子种群规模(个体数), 该操作在量子力学上的意义在于通过评估粒子簇与最优解区间的势垒宽度(公式14对子种群中心欧式距离的计算) 调节粒子数量(公式15对子种群规模的调节) 从而改变该区域发生量子隧道效应的概率.能级稳定判据对算法在当前尺度下种群进行充分搜索有重要影响, 当
$ k $ 个种群迁移速度过快, 达到能级稳定判据标准时, 会进行能级下降, 种群分布聚集, 由此容易导致算法早熟, 全局搜索不充分. 因此, 我们需要在每轮迭代过程中对当前尺度下的对种群空间进行限定, 即实现种群迁移步长控制. MQHOA-d 在迭代过程中, 首先初始化$ k $ 个种群中心, 以当前尺度$ {\sigma _s}^{\rm{2}} $ 生成$ n $ 维协方差矩阵, 具体公式如下:$$ \begin{array}{l} {\mathop{\rm cov}} _{}^{(g)} = diag({\sigma _s}^{2}) = \left( {\begin{array}{*{20}{c}} {{\sigma _s}^{\rm{2}}}&{}&{}\\ {}& \ddots &{}\\ {}&{}&{{\sigma _s}^{\rm{2}}} \end{array}} \right) \end{array} $$ (16) 其中
$ {{\mathop{\rm cov}} ^{(g)}} $ 表示第$ g $ 代的协方差矩阵, 在当前种群中心$ {X^i} $ 处按照正态分布$ N({X^i}, {{\mathop{\rm cov}} ^{(g)}}) $ 生成$ dyn_g^i $ 个采样点, 完成当前种群个体初始化. 当种群方差满足能级稳定判据时($ \Delta {\sigma _k} \le {\sigma _s} $ ), MQHOA-d 进行能级下降操作, 我们需要将适应度最差的种群所有个体淘汰. 取剩下$ k $ 个种群中心位置的均值坐标, 初始化一个新的种群中心$ {m^{(g)}} $ , 具体如下:$$ \begin{array}{l} {m^{(g)}} = \dfrac{1}{k}\displaystyle\sum\limits_{i = 1}^k {X_{i:k}^{(g)}} \end{array} $$ (17) 以
$ {X^i} $ 为中心通过公式 (14) (15) 生成种群个体, 用新种群替换当前最差种群, 完成替换过程, 实现能级下降. 当所有的个体满足能级下降判据, 此时在当前尺度的搜索过程完成, 下一步在更小的尺度进行搜索, 进行尺度下降操作, MQHOA-d 的尺度下降步骤与MQHOA 相同, 任为尺度减半操作. 当满足基态判据时, 输出当前最优解, 寻优结束.图2表示
$ k $ 为30,$ \lambda $ 为1000时, MQHOA-d所生成的种群在 Ellipsoidal 函数上种群分布示意图, 函数最优解位置为$\vec x = (1,2,3 \cdots ,n)$ , 粗点代表当前种群中心$ {X^{i}} $ , 细点为采样点(当前子种群个体), 本文中子种群是指以当前位置$ {X^i} $ 为均值, 根据正态分布$ N({X^{i}},{{\mathop{\rm cov}} ^{(g)}}) $ 生成的$ dyn_g^i $ 个采样点, 即属于同一个子种群中的个体 (采样点) 变更满足$ N({X^{i}}, {{\mathop{\rm cov}} ^{(g)}}) $ , 图2可见依据公式 (14) (15) 生成的种群特点如下: 适应度差的区域分布子种群规模大, 即个体数多. 适应度优的区域子种群分布规模小. 这一操作的目的是降低2.1节中对适应度差的子种群空间的评估误差, 以此保证整体评估的稳定性.
图 2 MQHOA-d所生成种群在Ellipsoidal函数二维空间分布示意图
Figure 2. Schematic diagram of spatial distribution of subpopulations generated by MQHOA-d in Ellipsoidal function of 2D
MQHOA-d 伪代码见算法2,
$ k $ 为种群的数量,$ S $ 为第一次采样区间,$ {\sigma _{\rm{s}}} $ 和$ {\sigma _{\rm{min}}} $ 分别为当前尺度和最小尺度, 其中$ {\sigma _{\rm{s}}} $ 初始化为$ {\sigma _{\rm{s}}} $ =$ UB-LB $ , 初始化的$ k $ 个采样中心.$ dyn_g^i $ $(g = 1,2\cdots k)$ 代表每一个种群的规模 (个体数).算法 2. MQHOA-d 算法
1: Initialize
$ k $ ,$ {\sigma _{{\rm{min}}}} $ ,$ S = \left[ {LB,LU} \right] $ ,$ {\sigma _s} $ 2: Randomly
$ {x_i} $ in domain$ \left[ {LB,UB} \right] $ 3: Calculate the standard deviation
$ {\sigma _k} $ for all$ x_i $ 4: while Not Stop Criteria
5: Calculate the
$ {{\mathop{\rm cov}} ^{(g)}} $ by formula (16)6: for
$ i = 1 $ to$ k $ do7: Calculate the
$ dyn_g^i $ by formula (15)8: Calculate
$ {\sigma _k} $ for all$ x_i $ 9: end for
10: Update the worst subpopulation by formula (17)(14)(15)
11: end while
12: Output
$ x^{best} $ ,$ f(x^{best}) $ -
多种群化可以增加种群发生量子隧穿的概率, 为了更好的分析该策略与粒子发生量子隧道效应的关系, 用 MQHOA/MQHOA-d 做对照实验. 实验组1中 MQHOA 采样方式为单一种群采样, 种群数为1, 个体数通常为30, 这里为控制参数一致, 将个体数设置为200; 实验组2中 MQHOA-d 采样方式为多种群采样, 设置子种群数为30, 个体总数为200. 在迭代过程中可以根据当前波函数的概率密度计算发生量子隧道效应点的数量, 见公式(18):
$$ \begin{array}{l} \displaystyle\sum\limits_{i = 1}^k {dy{n_i} \cdot \int\limits_{{x_0} - \varepsilon }^{{x_0} + \varepsilon } {{N_i}({x_i},{\sigma _s}^2)} dx} \end{array} $$ (18) 其中
$ dyn_i $ 表示当前子种群规模(个体数),$ k $ 为子种群数量, 其中实验组1中$ dyn_i = 200 $ ,$ k = 1 $ . 在量子物理中, 一个被限制在双阱势中的粒子是一个理想的经典模型, 它常被用来分析量子系统的波函数和隧道效应或能量, 因此测试函数选用的是双势阱所对应的双阱函数, 函数表达式为$f(x) = v \times \dfrac{{{{({x^2} - {a^2})}^2}}}{{{a^4}}} + \Delta \cdot x + C$ , 其中参数设置为$v = 6,\; a = 5 , \Delta = 0.9$ , 测试函数全局最优区间为$ [ - 5.3,5.5] $ ,$ C $ 为一常数, 用于控制$ f(x) $ 的最小值, 本实验将$ f(x) $ 的最小值控制为0, 根据公式(18) 计算两对照组在寻优过程中的发生量子隧道效应点数量的期望, 具体见图3和图4.
图 3 一维双阱函数图与隧道效应示意图
Figure 3. One dimensional double well function diagram and tunnel effect diagram
图 4 MQHOA-d与MQHOA发生隧道效应点数量与迭代次数关系图
Figure 4. The relationship between the number of tunneling points and the number of iterations between MQHOA-d and MQHOA
图3(a) 中实线为实验所用函数的一维示意图, 其中加粗部分为最优区间, 图3(b)为子种群中部分采样个体发生量子隧道效应, 贯穿势垒跳出局部最优示意图, 由公式(18)可知在下一次迭代过程中, 该子种群发生隧道效应的个体数量与当前子种群规模正相关, 通过4.1节中公式(15) 通过适应度的差异性调节各子种群的规模, 由此增加适应度差的子种群个体数, 以此增加当前能级下该子种群量子隧穿到最优解区域的概率, 提高该子种群向最优解区域的迁移能力. 隧道效应的发生是粒子数量与势垒(本文映射为适应度) 共同影响的结果, 固定子种群规模的搜索策略忽略了子种群个体数量对隧道效应的影响, 因此基于子种群自适应策略改进的 MQHOA-d 在相同的环境下较固定种群规模搜索策略的算法发生隧道效应的概率更大, 由此可以提升算法搜索能力.
实验的目之一就是计算种群中通过量子隧道效应出现在最优区间的点的数量, 虚线为随迭代次数增加采样概率密度函数尺度递减示意图, 当迭代次数增加到一定次数时, 概率密度函数中
$ \sigma _s $ 收敛于0, 此时发生量子隧道效应的概率也趋近于0, 因此会发生图4中随迭代次数增加, 发生量子隧道效应的点的数量先增加后递减甚至趋于0. 图4中三角形折线和圆形折线分别代表 MQHOA-d 和 MQHOA 种群中发生量子隧道效应的点数量随迭代次数的关系图, MQHOA-d 与 MQHOA 的迭代过程中, 在相同的迭代次数下, MQHOA-d 发生量子隧道效应点的数量要大于 MQHOA, 实验设置的输出条件为迭代次数达到10000, 通过图4可知 MQHOA-d 在迭代次数达到约2500时尺度$ \sigma_s $ 收敛于0, 即种群已完成搜索, 而 MQHOA 需要迭代约9500次才完成搜索. 从发生量子隧道效应点数量随迭代次数的关系图可知, 快速的达到隧道效应点数量最大化有利于缩减算法搜索时间, 提高种群收敛速度, 这也是对3.1节中通过欧式距离评估适应度而动态调节子种群规模使整体发生量子隧道效应最大化的有效性验证.发生量子隧道效应的点数量越多可映射为当前种群分布寻找到最优解区域的概率越大, MQHOA-d 在迭代次数较小时即可达到整体种群发生隧道效应的最大状态, 此时尺度的缩减程度低, 可以说明 MQHOA-d 在全局搜索时即可快速定位全局最优区域, 面对复杂函数或多峰函数时更具有优势, 而 MQHOA 在整体种群发生隧道效应达到最大状态时的需要迭代次数较大, 此时尺度
$ \sigma _s $ 缩减程度高, 在大尺度下对全局的评估不如 MQHOA-d, 由此可以推测当测试函数为结构复杂的函数时 MQHOA 容易陷入局部最优区域, 且 MQHOA 的寻优能力不如 MQHOA-d. 从蒙特卡洛估计积分的角度上看, 合理降低适应度差的子种群采样方差可以提高对当前种群整体分布的评估准确度, 有利于解空间的全局评估. -
为了全面分析 MQHOA-d 的性能, 选取烟花算法[24-25] (FWA) 的衍生 EFWA[26]、AFWA[27]、以及 MQHOA、SPSO2011[28]、QPSO[29-30] 作为对照组.
所有的算法将在 CEC2013 标准函数测试集[31] 上进行, 每组实验重复51次, 单次运算的最大迭代次数为10000
$ *d $ , 其中$ d $ 为维度, 实验维度设置为30. 测试集一共包括28个测试函数, 根据函数结构不同可划分为单峰函数 ($ f_1-f_5 $ ), 多峰函数 ($ f_6- f_{20} $ ), 复合函数 ($ f_{21}-f_{28} $ ). 所有函数的定义域为$ \left[ { - 100,100} \right] $ , 后续对实验结果的误差进行分析. 实验环境为Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz 2.21GHz, 16.0GB, 程序采 Matlab2018a 编写. 其中 MQHOA、MQHOA-d 的种群数设置为30, MQHOA-d 的个体总数$ \lambda $ 设置为200; QPSO 和 SPSO2011 粒子总数设置为30. 具体实验数据见表1(EFWA、AFWA实验数据来自于文献[32]). 表1中 MeanErr 表示误差均值, Std 代表解的标准差, 最优的实验结果在表2中用粗体标出.表 2 CEC2013测试函数维度为30情况下各算法51重复实验的平均误差和标准差
Table 2. Mean errors and standard deviation of each algorithm on CEC2013 repeated 51 times in the 30-dimensional
$ f $ MQHOA MQHOA-d SPSO2011 QPSO EFWA AFWA MeanErr Std MeanErr Std MeanErr Std MeanErr Std MeanErr Std MeanErr Std 1 $9.71\!\!\times\!\! 10^{\!-\!11}$ $1.44\!\!\times\!\! 10^{\!-\!11}$ $3.25\!\!\times\! \!10^{\!-\!13}$ $1.14\!\!\times\!\! 10^{\!-\!13}$ $2.36\!\!\times\!\! 10^{\!-\!13}$ $4.46\!\!\times\!\! 10^{\!-\!14}$ $2.59\!\!\times\!\! 10^{\!-\!13}$ $9.12\!\!\times \!\!10^{\!-\!14}$ $7.82\!\!\times\!\! 10^{-2}$ $1.31\!\!\times\!\! 10^{\!-\!2}$ ${\bf{0.00\!\!\times\!\! 10^{0} } }$ ${\bf{0.00\!\!\times\! \!10^{0} } }$ 2 $1.15\!\times\! 10^{6}$ $2.65\!\times \!10^{5}$ $1.76\!\times \!10^{6}$ $3.97\!\times\! 10^{5}$ ${\bf{9.68\!\times \!10^{4} } }$ ${\bf{4.82\!\times \!10^{4} } }$ $1.62\!\times\! 10^{7}$ $7.01\!\times\! 10^{6}$ $5.43\!\times\! 10^{5}$ $2.04\!\times\! 10^{5}$ $8.92\!\times\! 10^{5}$ $3.92\!\times\! 10^{5}$ 3 $3.32\!\times\! 10^{7}$ $ 3.94\times 10^{7} $ ${\bf{3.60\times 10^{6}}} $ ${\bf{4.19\times 10^{6}}} $ $ 1.07\times 10^{8} $ $ 1.58\times 10^{8} $ $ 2.28\times 10^{8} $ $ 3.23\times 10^{8} $ $ 1.26\times 10^{8} $ $ 2.15\!\times\! 10^{8} $ $ 1.26\!\times\! 10^{8} $ $ 1.54\!\times\! 10^{8} $ 4 $ 3.83\times 10^{4} $ $ 5.80\times 10^{3} $ $ 4.24\times 10^{4} $ $ 4.43\times 10^{3} $ $ 1.55\times 10^{3} $ $ 5.87\times 10^{2} $ $ 1.03\times 10^{4} $ $ 2.49\times 10^{3} $ ${\bf{1.09\times 10^{0}}} $ ${\bf{3.53\!\times\! 10^{\!-\!1}}} $ $ 1.14\times 10^{1} $ $ 6.83\!\times \!10^{0} $ 5 $ 1.92\!\!\times\!\! 10^{\!-\!3} $ $ 2.46\!\!\times\!\! 10^{\!-\!4} $ $ 2.22\!\!\times\!\! 10^{\!-\!3} $ $ 4.23\!\!\times\!\! 10^{\!-\!4} $ $ 4.03\!\!\times\!\! 10^{\!-\!4} $ $ 2.92\!\!\times\!\! 10^{\!-\!5} $ ${\bf{3.40\!\!\times\!\! 10^{\!-\!7}}} $ ${\bf{3.94\!\!\times\!\! 10^{\!-\!7}}} $ $ 7.90\!\!\times\!\! 10^{\!-\!2} $ $ 1.01\!\!\times\!\! 10^{\!-\!2} $ $ 6.04\!\!\times\!\! 10^{\!-\!4} $ $ 9.24\!\!\times\!\! 10^{\!-\!5} $ 6 $ 3.16\times 10^{1} $ $ 2.65\times 10^{1} $ $ 2.41\times 10^{1} $ $ 1.60\times 10^{1} $ ${\bf{1.70\times 10^{1}}} $ ${\bf{2.02\times 10^{1}}} $ $ 3.21\times 10^{1} $ $ 2.15\times 10^{1} $ $ 3.49\times 10^{1} $ $ 2.71\times 10^{1} $ $ 2.99\times 10^{1} $ $ 2.63\times 10^{1} $ 7 ${\bf{2.07\times 10^{1}}} $ ${\bf{1.26\times 10^{1}}} $ $ 2.23\times 10^{1} $ $ 8.22\times 10^{0} $ $ 5.65\times 10^{1} $ $ 2.03\times 10^{1} $ $ 4.71\times 10^{1} $ $ 1.66\times 10^{1} $ $ 1.33\times 10^{2} $ $ 4.34\times 10^{1} $ $ 9.19\times 10^{1} $ $ 2.63\times 10^{1} $ 8 $ 2.10\!\times\! 10^{1} $ $ 4.43\!\times\! 10^{\!-\!2} $ ${\bf{2.09\!\times\! 10^{1}}} $ ${\bf{5.62\!\times\! 10^{\!-\!2}}} $ ${\bf{2.09\!\times\! 10^{1}}} $ ${\bf{6.88\!\times\! 10^{\!-\!2}}} $ ${\bf{2.09\!\times\! 10^{1}}} $ ${\bf{5.15\!\times\! 10^{\!-\!2}}} $ $ 2.10\!\times\! 10^{1} $ $ 4.82\!\times\! 10^{\!-\!2} $ ${\bf{2.09\!\times\! 10^{1}}} $ ${\bf{7.85\!\times\! 10^{\!-\!2}}} $ 9 $ 3.91\times 10^{1} $ $ 1.37\times 10^{0} $ $ 2.29\times 10^{1} $ $ 6.38\times 10^{0} $ $ 2.41\times 10^{1} $ $ 4.10\times 10^{0} $ ${\bf{2.12\times 10^{1}}} $ ${\bf{7.99\times 10^{0}}} $ $ 3.19\times 10^{1} $ $ 3.48\times 10^{0} $ $ 2.48\times 10^{1} $ $ 4.89\times 10^{0} $ 10 $ 4.75\!\times\! 10^{\!-\!1} $ $ 2.53\!\times\! 10^{\!-\!1} $ $ 5.43\!\times\! 10^{\!-\!2} $ $ 2.97\!\times\! 10^{\!-\!2} $ $ 2.13\!\times\! 10^{\!-\!1} $ $ 9.54\!\times\! 10^{\!-\!2} $ $ 1.92\!\times\! 10^{0} $ $ 1.26\!\times\! 10^{0} $ $ 8.29\!\times\! 10^{\!-\!1} $ $ 8.42\!\times\! 10^{\!-\!2} $ ${\bf{4.73\!\times\! 10^{\!-\!2}}} $ ${\bf{3.44\!\times\! 10^{\!-\!2}}} $ 11 $ 1.67\times 10^{2} $ $ 4.78\times 10^{1} $ ${\bf{3.41\times 10^{1}}} $ ${\bf{2.23\times 10^{1}}} $ $ 8.61\times 10^{1} $ $ 3.02\times 10^{1} $ $ 1.59\times 10^{2} $ $ 2.01\times 10^{1} $ $ 4.22\times 10^{2} $ $ 9.26\times 10^{1} $ $ 1.05\times 10^{2} $ $ 3.43\times 10^{1} $ 12 $ 1.71\times 10^{2} $ $ 3.93\times 10^{1} $ ${\bf{2.64\times 10^{1}}} $ ${\bf{6.96\times 10^{0}}} $ $ 7.21\times 10^{1} $ $ 2.53\times 10^{1} $ $ 2.03\times 10^{2} $ $ 1.51\times 10^{1} $ $ 6.33\times 10^{2} $ $ 1.38\times 10^{2} $ $ 1.52\times 10^{2} $ $ 4.43\times 10^{1} $ 13 $ 1.87\times 10^{2} $ $ 1.58\times 10^{1} $ ${\bf{6.83\times 10^{1}}} $ ${\bf{1.40\times 10^{1}}} $ $ 1.39\times 10^{2} $ $ 3.02\times 10^{1} $ $ 2.06\times 10^{2} $ $ 1.51\times 10^{1} $ $ 4.51\times 10^{2} $ $ 7.45\times 10^{1} $ $ 2.36\times 10^{2} $ $ 6.06\times 10^{1} $ 14 $ 7.13\times 10^{3} $ $ 2.03\times 10^{2} $ $ 3.16\times 10^{3} $ $ 1.07\times 10^{3} $ $ 4.54\times 10^{3} $ $ 8.04\times 10^{2} $ $ 6.17\times 10^{3} $ $ 5.54\times 10^{2} $ $ 4.16\times 10^{3} $ $ 6.16\times 10^{2} $ ${\bf{2.97\times 10^{3}}} $ ${\bf{5.70\times 10^{2}}} $ 15 $ 7.32\times 10^{3} $ $ 2.59\times 10^{2} $ ${\bf{2.80\times 10^{3}}} $ ${\bf{6.30\times 10^{2}}} $ $ 4.45\times 10^{3} $ $ 6.60\times 10^{2} $ $ 7.25\times 10^{3} $ $ 3.79\times 10^{2} $ $ 4.13\times 10^{3} $ $ 5.61\times 10^{2} $ $ 3.81\times 10^{3} $ $ 5.03\times 10^{2} $ 16 $ 2.48\times 10^{0} $ $2.67\!\times\! 10^{\!-\!1}$ ${\bf{3.23\!\times\! 10^{\!-\!1} } }$ ${\bf{2.85\!\times\! 10^{\!-\!1} } }$ $ 1.88\times 10^{0} $ $ 3.94\!\times\! 10^{\!-\!1} $ $ 2.50\times 10^{0} $ $ 2.67\!\times\! 10^{\!-\!1} $ $ 5.92\!\times\! 10^{\!-\!1} $ $ 2.30\!\times\! 10^{\!-\!1} $ $ 4.97\!\times\! 10^{\!-\!1} $ $ 2.56\!\times\! 10^{\!-\!1} $ 17 $ 2.10\times 10^{2} $ $ 1.33\times 10^{1} $ ${\bf{5.94\times 10^{1}}} $ ${\bf{1.33\times 10^{1}}} $ $ 1.34\times 10^{2} $ $ 3.06\times 10^{1} $ $ 2.32\times 10^{2} $ $ 1.44\times 10^{1} $ $ 3.10\times 10^{2} $ $ 6.52\times 10^{1} $ $ 1.45\times 10^{2} $ $ 2.55\times 10^{1} $ 18 $ 2.09\times 10^{2} $ $ 1.21\times 10^{1} $ ${\bf{6.02\times 10^{1}}} $ ${\bf{2.00\times 10^{1}}} $ $ 1.38\times 10^{2} $ $ 2.48\times 10^{1} $ $ 2.38\times 10^{2} $ $ 1.64\times 10^{1} $ $ 1.75\times 10^{2} $ $ 3.81\times 10^{1} $ $ 1.75\times 10^{2} $ $ 4.92\times 10^{1} $ 19 $ 1.58\times 10^{1} $ $ 1.58\times 10^{0} $ ${\bf{3.01\times 10^{0}}} $ ${\bf{1.46\times 10^{0}}} $ $ 7.91\times 10^{0} $ $ 3.37\times 10^{0} $ $ 1.73\times 10^{1} $ $ 1.75\times 10^{0} $ $ 1.23\times 10^{1} $ $ 3.68\times 10^{0} $ $ 6.92\times 10^{0} $ $ 2.37\times 10^{0} $ 20 ${\bf{1.20\times 10^{1}}} $ ${\bf{4.32\!\times\! 10^{\!-\!1} } }$ $ 1.46\times 10^{1} $ $2.32\!\times\! 10^{\!-\!1}$ $ 1.31\times 10^{1} $ $ 1.91\times 10^{0} $ $ 1.25\times 10^{1} $ $2.55\!\times\! 10^{\!-\!1}$ $ 1.46\times 10^{1} $ $1.73\!\times\! 10^{\!-\!1}$ $ 1.30\times 10^{1} $ $9.72\!\times\! 10^{\!-\!1}$ 21 $ 3.38\times 10^{2} $ $ 7.88\times 10^{1} $ ${\bf{2.86\times 10^{2}}} $ ${\bf{7.01\times 10^{1}}} $ $ 3.46\times 10^{2} $ $ 8.31\times 10^{1} $ $ 3.00\times 10^{2} $ $ 6.99\times 10^{1} $ $ 3.24\times 10^{2} $ $ 9.67\times 10^{1} $ $ 3.16\times 10^{2} $ $ 9.33\times 10^{1} $ 22 $ 7.64\times 10^{3} $ $ 3.03\times 10^{2} $ ${\bf{3.12\times 10^{3}}} $ ${\bf{7.19\times 10^{2}}} $ $ 4.16\times 10^{3} $ $ 7.19\times 10^{2} $ $ 6.16\times 10^{3} $ $ 5.17\times 10^{2} $ $ 5.75\times 10^{3} $ $ 1.08\times 10^{3} $ $ 3.45\times 10^{3} $ $ 7.44\times 10^{2} $ 23 $ 7.51\times 10^{3} $ $ 3.35\times 10^{2} $ ${\bf{3.50\times 10^{3}}} $ ${\bf{5.83\times 10^{2}}} $ $ 4.52\times 10^{3} $ $ 8.56\times 10^{2} $ $ 7.30\times 10^{3} $ $ 2.83\times 10^{2} $ $ 5.74\times 10^{3} $ $ 7.59\times 10^{2} $ $ 4.70\times 10^{3} $ $ 8.98\times 10^{2} $ 24 $ 2.40\times 10^{2} $ $ 7.21\times 10^{0} $ ${\bf{2.20\times 10^{2}}} $ ${\bf{4.94\times 10^{0}}} $ $ 2.53\times 10^{2} $ $ 9.33\times 10^{0} $ $ 2.46\times 10^{2} $ $ 7.35\times 10^{0} $ $ 3.37\times 10^{2} $ $ 7.33\times 10^{1} $ $ 2.70\times 10^{2} $ $ 1.31\times 10^{1} $ 25 $ 3.14\times 10^{2} $ $ 3.34\times 10^{0} $ $ 2.73\times 10^{2} $ $ 8.64\times 10^{0} $ $ 2.81\times 10^{2} $ $ 6.78\times 10^{0} $ ${\bf{2.60\times 10^{2}}} $ ${\bf{6.08\times 10^{0}}} $ $ 3.56\times 10^{2} $ $ 2.80\times 10^{1} $ $ 2.99\times 10^{2} $ $ 1.24\times 10^{1} $ 26 $ 2.22\times 10^{2} $ $ 4.67\times 10^{1} $ ${\bf{2.03\times 10^{2}}} $ ${\bf{1.74\times 10^{1}}} $ $ 2.67\times 10^{2} $ $ 7.25\times 10^{1} $ $ 2.91\times 10^{2} $ $ 6.83\times 10^{1} $ $ 3.21\times 10^{2} $ $ 9.04\times 10^{1} $ $ 2.73\times 10^{2} $ $ 8.51\times 10^{1} $ 27 $ 7.73\times 10^{2} $ $ 2.03\times 10^{2} $ ${\bf{5.42\times 10^{2}}} $ ${\bf{3.92\times 10^{1}}} $ $ 8.10\times 10^{2} $ $ 1.11\times 10^{2} $ $ 7.47\times 10^{2} $ $ 1.26\times 10^{2} $ $ 1.28\times 10^{3} $ $ 1.10\times 10^{2} $ $ 9.72\times 10^{2} $ $ 1.33\times 10^{2} $ 28 $ 3.39\times 10^{2} $ $ 2.76\times 10^{2} $ ${\bf{3.00\times 10^{2}}} $ ${\bf{6.97\!\times\! 10^{\!-\!11} } }$ $ 4.29\times 10^{2} $ $ 5.27\times 10^{2} $ $ 3.64\times 10^{2} $ $ 2.59\times 10^{2} $ $ 4.34\times 10^{3} $ $ 2.08\times 10^{3} $ $ 4.37\times 10^{2} $ $ 4.67\times 10^{2} $ -
为更直观分析数据, 将6组实验数据的误差均值进行等级划分(1到6 级), 均值误差最小的为1, 最大的为6, 同时计算对照组的平均等级并绘制成图5.
图 5 CEC2013上各算法误差等级图(维度为30,重复51次)
Figure 5. Rank sum test results of all algorithms repeated 51 times in the 30-dimensional case
与原 MQHOA 算法相比较, 通过表2和图6可以看出 MQHOA-d 在单峰函数上 (除
$ f_3 $ ) 表现较差, 这是 MQHOA-d 每一个高斯采样空间中产生的$ dyn_g^i $ 个采样点并不能实现向最优解空间的快速迁移, 一次采样所需要的计算次数为$\displaystyle\sum\nolimits_{i = 1}^k {} dyn_g^i$ , 而这一操作对应算法的能级稳定过程: MQHOA 仅在每一个高斯采样空间中生成一个采样点, 即一次采样仅需要计算$ k $ 次. 而结构简单的单峰函数并无过多局部最优解, 多种群搜索的策略虽可以提高跳出局部最优解的概率, 但针对这类型的函数, 需要的是整个种群快速向最优解区域收敛, 即搜索空间从大尺度向小尺度的过渡, 这一过程对应 MQHOA/MQHOA-d 的能级下降过程, 算法需要尽快从全局过渡到局部. 而 MQHOA-d 的多种群生成决定了它将大量的计算资源消耗在能级稳定过程中, 由于实验计算次数存在上限, 因此在有限的计算中 MQHOA-d 进行能级下降次数比 MQHOA 少, 即尺度缩减程度不如 MQHOA.
图 6 CEC2013测试函数在30维情况下重复51次实验箱体图
Figure 6. Boxplots of CEC2013 benchmark functions repeated 51 times in the 30-dimensional case
从多峰函数和复合函数上看 MQHOA-d 的求解误差要远小于原 MQHOA, 这也验证了4.2节中根据量子隧道效应实验数据对算法性能的推测是可靠的, MQHOA-d 在大尺度的状态下尽可能多的进行搜索, 全局搜索更加全面: 此策略在适应度低的区域生成更多的采样个体, 对整个种群的计算能力进行合理分配, 提高了种群多样性, 增加跳出局部最优解概率. 因此 MQHOA-d 对结构复杂的多峰函数和复合函数更具有针对性. 相比于 SPSO2011、QPSO、EFWA、AFWA 等算法, 通过图6可知 MQHOA-d 在单峰函数下处于劣势, 但多峰函数和复合函数的平均等级最小, 且总体平均误差等级最小. 综合28个测试函数分析, MQHOA-d的平均误差等级值最小, 仅为1.93. 从表2中可知 MQHOA-d 的标准差在多峰函数和复合函数中较小, 具有较强的鲁棒性. 通过每组实验重复51次的数据绘制箱体图(具体见图6). 这些箱体图清晰的显示 MQHOA-d 在多峰函数和复合函数中的准确性和稳定性占据主导地位.
MQHOA-d 性能的增强得益于搜索随机性的增强, 在量子模型下该算法的随机性可由量子隧道效应衡量, 种群个体数自适应过程扩大适应度差的子种群规模, 以此增强搜索过程的随机性, 同时降低种群对目标函数的评估误差, 在量子模型下解释为当势垒宽度较宽时, 增加粒子数量可以加大粒子簇发生隧道效应的概率, 非量子模型下的优化算法通常以增加扰动项或设置变异操作的方式增强算法的随机性, 如文献[30]中通过评估种群所处的阶段实现变异策略的反馈调节, 由此提出基于状态估计反馈的策略自适应差分进化算法 SEFDE, 且 SEFDE 在与 CEC2013 中性能最好的 DE 改进算法 SHADE 的对比实验中表现出较强竞争力, 将表2中 MQHOA-d 的 CEC2013 测试数据与文献[33]中 SEFDE 在同等条件下的 CEC2013 测试数据做对比, 结果显示 MQHOA-d 在16个函数优化上优于 SEFDE, 该16个函数除
$ f_2 $ 外, 都为多峰函数或复合函数, 与此同时 MQHOA-d 在函数$ f_8 $ 的优化上与 SEFDE 具有相似的优化效果, 总体而言 MQHOA-d 在多峰函数与复合函数的优化上优于 SEFDE. 这也验证了基于蒙特卡洛评估提出的动态种群策略和合理性, 增大适应度差的种群规模可以提高算法搜索随机性, 有利于降低整体评估误差.统计51次重复实验的平均迭代时间, 绘制成图7. 在图7中方框中数字代表算法在对应测试函数中所消耗的平均时间, 单位为秒(s). 将时间归一化后进行涂色, 颜色越深的区域代表消耗时间越多.
图 7 测试函数30维情况下各算法重复51次实验平均时间消耗热力图
Figure 7. Rank of mean time consumption on CEC2013 repeated 51 times in the 30-dimensional case
本次实验中算法MQHOA在测试函数
$ f_1 $ 上的平均迭代次数为$ 3.49\times 10^{4} $ 小于上限$ D*10000 $ , 其它实验组的平均迭代次数均达到上限$ D*10000 $ . 在针对测试函数$ f_1 $ 而言, MQHOA 所消耗时间较其他3种算法少一个数量级, 且图6中箱体图显示 MQHOA 的51次求解数据分布不稳定, 可见 MQHOA 在$ f_1 $ 测试函数上存在算法“早熟”现象, 过早的收敛在某一局部无法跳出, 也验证了增大种群初期发生量子隧道效应的概率更不易陷入局部最优, 在测试函数$ f_9 $ 上, MQHOA-d 所消耗时间较其他3种算法具有极大的优势, 平均误差仅次于 QPSO, 且误差范围与 QPSO 在同一个数量级, 当实际工业生产面对结构类似于$ f_9 $ 函数时, 可在节约计算成本的情况下使用 MQHOA-d. 总体而言 MQHOA 算法消耗时间最少但寻优精度远不如其他3种算法, MQHOA-d 消耗时间仅次于 MQHOA, 但寻优精度和鲁棒性强于 MQHOA、QPSO 和 SPSO2011. -
本文基于蒙特卡洛估计中不同子种群对总体评估误差具有差异性, 提出动态调节子种群规模的寻优策略, 将此策略应用于 MQHOA 的改进, 改进后的算法(MQHOA-d)在未增加随机化特征, 或者添加扰动等多余步骤的前提下解决了原算法的“早熟” 现象[34]. 核心在于动态调节种群规模方式对增大种群迭代初期发生量子隧道效应概率, 使其对解空间全局评估更加精准. 在迭代次数相同的情况下 MQHOA-d 对多峰函数和复合函数寻优误差更小, 根据适应度评估的多种群采样方式动态的调节了种群规模, 在解空间中更加合理进行勘探和开发, 同时种群利用率得到了提高. 改进后的算法虽然结构上较之前相比变得复杂, 但时间复杂度上仍优于几大主流算法(SPSO2011、QPSO). 目前 MQHOA-d 仍有局限性, 如: (1) MQHOA 系列算法的随机性和隐含并行性尚不明确[35-36]. (2) MQHOA-d 种群个体行为所抽象的随机游走模型[37-38]尚未研究.
Multi-scale Quantum Harmonic Oscillator Algorithm Based on Subpopulation Number Adaptive
More Information-
摘要: 优化算法中多种群采样方式可转化为蒙特卡洛对当前函数积分的评估, 针对不同子种群对整体评估的差异性, 提出子种群规模 (个体数) 自适应的改进策略, 并用于多尺度量子谐振子优化算法(Multi-scale quantum harmonic oscillator algorithm, MQHOA) 的改进, 同时阐述多种群策略所具有的量子特性以及量子隧道效应与寻优性能的相关性, 已有的优化算法忽视了动态调节子种群规模对寻优能力的影响, 该策略通过动态调节子种群规模, 提高适应度差的子种群发生量子隧道效应的概率, 增强了算法的寻优能力, 将改进后的算法MQHOA-d(Multi-scale quantum harmonic oscillator algorithm based on dynamic subpopulation) 与 MQHOA 及其他优化算法在 CEC2013 测试集上进行测试, 结果表明原算法 MQHOA"早熟"问题在 MQHOA-d 中得到解决, 且 MQHOA-d 对多峰函数和复合函数优化具有显著优势, 求解误差和计算时间均小于几种经典优化算法.Abstract: The optimization algorithm of multiple subpopulations of sampling can be converted monte carlo evaluation function definite integral, because of the differences between different subpopulations in the overall evaluation, an adaptive strategy of subpopulation size (number of individuals) is proposed, which is used to improve multi-scale quantum harmonic oscillator optimization algorithm (MQHOA). The quantum properties of multi-population strategy and the correlation between quantum tunneling effect and optimization performance are discussed, the performance of existing optimization algorithm ignores the dynamic adjustment of subpopulation size influence on optimization ability, this strategy by dynamically adjusting population size, improve fitness poor child population incidence of quantum tunnel effect, increase the optimization ability of the algorithm. Compared the improved algorithm multi-scale quantum harmonic oscillator algorithm based on dynamic subpopulation (MQHOA-d) with MQHOA and other optimization algorithms on CEC2013 standard test functions. The experimental results show that the improved algorithm is more efficient in the optimization of basic multimodal functions and composition functions and the experimental results are better than several classical optimization algorithms and premature convergence problem has been solved.
-
Key words:
- Optimization algorithm /
- quantum tunneling effect /
- dynamic population /
- subpopulation /
- monte carlo
-
图 2 MQHOA-d所生成种群在Ellipsoidal函数二维空间分布示意图
Fig. 2 Schematic diagram of spatial distribution of subpopulations generated by MQHOA-d in Ellipsoidal function of 2D
图 3 一维双阱函数图与隧道效应示意图
Fig. 3 One dimensional double well function diagram and tunnel effect diagram
图 4 MQHOA-d与MQHOA发生隧道效应点数量与迭代次数关系图
Fig. 4 The relationship between the number of tunneling points and the number of iterations between MQHOA-d and MQHOA
图 5 CEC2013上各算法误差等级图(维度为30,重复51次)
Fig. 5 Rank sum test results of all algorithms repeated 51 times in the 30-dimensional case
图 6 CEC2013测试函数在30维情况下重复51次实验箱体图
Fig. 6 Boxplots of CEC2013 benchmark functions repeated 51 times in the 30-dimensional case
图 7 测试函数30维情况下各算法重复51次实验平均时间消耗热力图
Fig. 7 Rank of mean time consumption on CEC2013 repeated 51 times in the 30-dimensional case
表 1 量子理论与优化算法的对应关系
Table 1 The relationship between quantum theory and optimization algorithm
量子理论 优化算法 说明 势能评估/势能最低点 $f(x)$ /$f(x)$ 的全局最小值量子系统下将函数优化问题转化为寻找势能最低点问题 波函数 解的概率分布 量子系统下波函数对优化问题的概率描述 势阱等效 优化问题目标函数的近似方法 如QPSO中用Delta势阱逼近目标函数, MQHOA以谐振子逼近目标函数 势垒宽度 子种群位置到最优解的相对距离 势垒宽度越大, 隧道效应概率越低 量子隧道效应 跳出局部最优能力 波函数计算隧道效应概率, 增加迭代过程中发生隧道效应的采样点数量, 可提高算法性能 
下载: 导出CSV
七星彩规则表 2 CEC2013测试函数维度为30情况下各算法51重复实验的平均误差和标准差
Table 2 Mean errors and standard deviation of each algorithm on CEC2013 repeated 51 times in the 30-dimensional
$ f $ MQHOA MQHOA-d SPSO2011 QPSO EFWA AFWA MeanErr Std MeanErr Std MeanErr Std MeanErr Std MeanErr Std MeanErr Std 1 $9.71\!\!\times\!\! 10^{\!-\!11}$ $1.44\!\!\times\!\! 10^{\!-\!11}$ $3.25\!\!\times\! \!10^{\!-\!13}$ $1.14\!\!\times\!\! 10^{\!-\!13}$ $2.36\!\!\times\!\! 10^{\!-\!13}$ $4.46\!\!\times\!\! 10^{\!-\!14}$ $2.59\!\!\times\!\! 10^{\!-\!13}$ $9.12\!\!\times \!\!10^{\!-\!14}$ $7.82\!\!\times\!\! 10^{-2}$ $1.31\!\!\times\!\! 10^{\!-\!2}$ ${\bf{0.00\!\!\times\!\! 10^{0} } }$ ${\bf{0.00\!\!\times\! \!10^{0} } }$ 2 $1.15\!\times\! 10^{6}$ $2.65\!\times \!10^{5}$ $1.76\!\times \!10^{6}$ $3.97\!\times\! 10^{5}$ ${\bf{9.68\!\times \!10^{4} } }$ ${\bf{4.82\!\times \!10^{4} } }$ $1.62\!\times\! 10^{7}$ $7.01\!\times\! 10^{6}$ $5.43\!\times\! 10^{5}$ $2.04\!\times\! 10^{5}$ $8.92\!\times\! 10^{5}$ $3.92\!\times\! 10^{5}$ 3 $3.32\!\times\! 10^{7}$ $ 3.94\times 10^{7} $ ${\bf{3.60\times 10^{6}}} $ ${\bf{4.19\times 10^{6}}} $ $ 1.07\times 10^{8} $ $ 1.58\times 10^{8} $ $ 2.28\times 10^{8} $ $ 3.23\times 10^{8} $ $ 1.26\times 10^{8} $ $ 2.15\!\times\! 10^{8} $ $ 1.26\!\times\! 10^{8} $ $ 1.54\!\times\! 10^{8} $ 4 $ 3.83\times 10^{4} $ $ 5.80\times 10^{3} $ $ 4.24\times 10^{4} $ $ 4.43\times 10^{3} $ $ 1.55\times 10^{3} $ $ 5.87\times 10^{2} $ $ 1.03\times 10^{4} $ $ 2.49\times 10^{3} $ ${\bf{1.09\times 10^{0}}} $ ${\bf{3.53\!\times\! 10^{\!-\!1}}} $ $ 1.14\times 10^{1} $ $ 6.83\!\times \!10^{0} $ 5 $ 1.92\!\!\times\!\! 10^{\!-\!3} $ $ 2.46\!\!\times\!\! 10^{\!-\!4} $ $ 2.22\!\!\times\!\! 10^{\!-\!3} $ $ 4.23\!\!\times\!\! 10^{\!-\!4} $ $ 4.03\!\!\times\!\! 10^{\!-\!4} $ $ 2.92\!\!\times\!\! 10^{\!-\!5} $ ${\bf{3.40\!\!\times\!\! 10^{\!-\!7}}} $ ${\bf{3.94\!\!\times\!\! 10^{\!-\!7}}} $ $ 7.90\!\!\times\!\! 10^{\!-\!2} $ $ 1.01\!\!\times\!\! 10^{\!-\!2} $ $ 6.04\!\!\times\!\! 10^{\!-\!4} $ $ 9.24\!\!\times\!\! 10^{\!-\!5} $ 6 $ 3.16\times 10^{1} $ $ 2.65\times 10^{1} $ $ 2.41\times 10^{1} $ $ 1.60\times 10^{1} $ ${\bf{1.70\times 10^{1}}} $ ${\bf{2.02\times 10^{1}}} $ $ 3.21\times 10^{1} $ $ 2.15\times 10^{1} $ $ 3.49\times 10^{1} $ $ 2.71\times 10^{1} $ $ 2.99\times 10^{1} $ $ 2.63\times 10^{1} $ 7 ${\bf{2.07\times 10^{1}}} $ ${\bf{1.26\times 10^{1}}} $ $ 2.23\times 10^{1} $ $ 8.22\times 10^{0} $ $ 5.65\times 10^{1} $ $ 2.03\times 10^{1} $ $ 4.71\times 10^{1} $ $ 1.66\times 10^{1} $ $ 1.33\times 10^{2} $ $ 4.34\times 10^{1} $ $ 9.19\times 10^{1} $ $ 2.63\times 10^{1} $ 8 $ 2.10\!\times\! 10^{1} $ $ 4.43\!\times\! 10^{\!-\!2} $ ${\bf{2.09\!\times\! 10^{1}}} $ ${\bf{5.62\!\times\! 10^{\!-\!2}}} $ ${\bf{2.09\!\times\! 10^{1}}} $ ${\bf{6.88\!\times\! 10^{\!-\!2}}} $ ${\bf{2.09\!\times\! 10^{1}}} $ ${\bf{5.15\!\times\! 10^{\!-\!2}}} $ $ 2.10\!\times\! 10^{1} $ $ 4.82\!\times\! 10^{\!-\!2} $ ${\bf{2.09\!\times\! 10^{1}}} $ ${\bf{7.85\!\times\! 10^{\!-\!2}}} $ 9 $ 3.91\times 10^{1} $ $ 1.37\times 10^{0} $ $ 2.29\times 10^{1} $ $ 6.38\times 10^{0} $ $ 2.41\times 10^{1} $ $ 4.10\times 10^{0} $ ${\bf{2.12\times 10^{1}}} $ ${\bf{7.99\times 10^{0}}} $ $ 3.19\times 10^{1} $ $ 3.48\times 10^{0} $ $ 2.48\times 10^{1} $ $ 4.89\times 10^{0} $ 10 $ 4.75\!\times\! 10^{\!-\!1} $ $ 2.53\!\times\! 10^{\!-\!1} $ $ 5.43\!\times\! 10^{\!-\!2} $ $ 2.97\!\times\! 10^{\!-\!2} $ $ 2.13\!\times\! 10^{\!-\!1} $ $ 9.54\!\times\! 10^{\!-\!2} $ $ 1.92\!\times\! 10^{0} $ $ 1.26\!\times\! 10^{0} $ $ 8.29\!\times\! 10^{\!-\!1} $ $ 8.42\!\times\! 10^{\!-\!2} $ ${\bf{4.73\!\times\! 10^{\!-\!2}}} $ ${\bf{3.44\!\times\! 10^{\!-\!2}}} $ 11 $ 1.67\times 10^{2} $ $ 4.78\times 10^{1} $ ${\bf{3.41\times 10^{1}}} $ ${\bf{2.23\times 10^{1}}} $ $ 8.61\times 10^{1} $ $ 3.02\times 10^{1} $ $ 1.59\times 10^{2} $ $ 2.01\times 10^{1} $ $ 4.22\times 10^{2} $ $ 9.26\times 10^{1} $ $ 1.05\times 10^{2} $ $ 3.43\times 10^{1} $ 12 $ 1.71\times 10^{2} $ $ 3.93\times 10^{1} $ ${\bf{2.64\times 10^{1}}} $ ${\bf{6.96\times 10^{0}}} $ $ 7.21\times 10^{1} $ $ 2.53\times 10^{1} $ $ 2.03\times 10^{2} $ $ 1.51\times 10^{1} $ $ 6.33\times 10^{2} $ $ 1.38\times 10^{2} $ $ 1.52\times 10^{2} $ $ 4.43\times 10^{1} $ 13 $ 1.87\times 10^{2} $ $ 1.58\times 10^{1} $ ${\bf{6.83\times 10^{1}}} $ ${\bf{1.40\times 10^{1}}} $ $ 1.39\times 10^{2} $ $ 3.02\times 10^{1} $ $ 2.06\times 10^{2} $ $ 1.51\times 10^{1} $ $ 4.51\times 10^{2} $ $ 7.45\times 10^{1} $ $ 2.36\times 10^{2} $ $ 6.06\times 10^{1} $ 14 $ 7.13\times 10^{3} $ $ 2.03\times 10^{2} $ $ 3.16\times 10^{3} $ $ 1.07\times 10^{3} $ $ 4.54\times 10^{3} $ $ 8.04\times 10^{2} $ $ 6.17\times 10^{3} $ $ 5.54\times 10^{2} $ $ 4.16\times 10^{3} $ $ 6.16\times 10^{2} $ ${\bf{2.97\times 10^{3}}} $ ${\bf{5.70\times 10^{2}}} $ 15 $ 7.32\times 10^{3} $ $ 2.59\times 10^{2} $ ${\bf{2.80\times 10^{3}}} $ ${\bf{6.30\times 10^{2}}} $ $ 4.45\times 10^{3} $ $ 6.60\times 10^{2} $ $ 7.25\times 10^{3} $ $ 3.79\times 10^{2} $ $ 4.13\times 10^{3} $ $ 5.61\times 10^{2} $ $ 3.81\times 10^{3} $ $ 5.03\times 10^{2} $ 16 $ 2.48\times 10^{0} $ $2.67\!\times\! 10^{\!-\!1}$ ${\bf{3.23\!\times\! 10^{\!-\!1} } }$ ${\bf{2.85\!\times\! 10^{\!-\!1} } }$ $ 1.88\times 10^{0} $ $ 3.94\!\times\! 10^{\!-\!1} $ $ 2.50\times 10^{0} $ $ 2.67\!\times\! 10^{\!-\!1} $ $ 5.92\!\times\! 10^{\!-\!1} $ $ 2.30\!\times\! 10^{\!-\!1} $ $ 4.97\!\times\! 10^{\!-\!1} $ $ 2.56\!\times\! 10^{\!-\!1} $ 17 $ 2.10\times 10^{2} $ $ 1.33\times 10^{1} $ ${\bf{5.94\times 10^{1}}} $ ${\bf{1.33\times 10^{1}}} $ $ 1.34\times 10^{2} $ $ 3.06\times 10^{1} $ $ 2.32\times 10^{2} $ $ 1.44\times 10^{1} $ $ 3.10\times 10^{2} $ $ 6.52\times 10^{1} $ $ 1.45\times 10^{2} $ $ 2.55\times 10^{1} $ 18 $ 2.09\times 10^{2} $ $ 1.21\times 10^{1} $ ${\bf{6.02\times 10^{1}}} $ ${\bf{2.00\times 10^{1}}} $ $ 1.38\times 10^{2} $ $ 2.48\times 10^{1} $ $ 2.38\times 10^{2} $ $ 1.64\times 10^{1} $ $ 1.75\times 10^{2} $ $ 3.81\times 10^{1} $ $ 1.75\times 10^{2} $ $ 4.92\times 10^{1} $ 19 $ 1.58\times 10^{1} $ $ 1.58\times 10^{0} $ ${\bf{3.01\times 10^{0}}} $ ${\bf{1.46\times 10^{0}}} $ $ 7.91\times 10^{0} $ $ 3.37\times 10^{0} $ $ 1.73\times 10^{1} $ $ 1.75\times 10^{0} $ $ 1.23\times 10^{1} $ $ 3.68\times 10^{0} $ $ 6.92\times 10^{0} $ $ 2.37\times 10^{0} $ 20 ${\bf{1.20\times 10^{1}}} $ ${\bf{4.32\!\times\! 10^{\!-\!1} } }$ $ 1.46\times 10^{1} $ $2.32\!\times\! 10^{\!-\!1}$ $ 1.31\times 10^{1} $ $ 1.91\times 10^{0} $ $ 1.25\times 10^{1} $ $2.55\!\times\! 10^{\!-\!1}$ $ 1.46\times 10^{1} $ $1.73\!\times\! 10^{\!-\!1}$ $ 1.30\times 10^{1} $ $9.72\!\times\! 10^{\!-\!1}$ 21 $ 3.38\times 10^{2} $ $ 7.88\times 10^{1} $ ${\bf{2.86\times 10^{2}}} $ ${\bf{7.01\times 10^{1}}} $ $ 3.46\times 10^{2} $ $ 8.31\times 10^{1} $ $ 3.00\times 10^{2} $ $ 6.99\times 10^{1} $ $ 3.24\times 10^{2} $ $ 9.67\times 10^{1} $ $ 3.16\times 10^{2} $ $ 9.33\times 10^{1} $ 22 $ 7.64\times 10^{3} $ $ 3.03\times 10^{2} $ ${\bf{3.12\times 10^{3}}} $ ${\bf{7.19\times 10^{2}}} $ $ 4.16\times 10^{3} $ $ 7.19\times 10^{2} $ $ 6.16\times 10^{3} $ $ 5.17\times 10^{2} $ $ 5.75\times 10^{3} $ $ 1.08\times 10^{3} $ $ 3.45\times 10^{3} $ $ 7.44\times 10^{2} $ 23 $ 7.51\times 10^{3} $ $ 3.35\times 10^{2} $ ${\bf{3.50\times 10^{3}}} $ ${\bf{5.83\times 10^{2}}} $ $ 4.52\times 10^{3} $ $ 8.56\times 10^{2} $ $ 7.30\times 10^{3} $ $ 2.83\times 10^{2} $ $ 5.74\times 10^{3} $ $ 7.59\times 10^{2} $ $ 4.70\times 10^{3} $ $ 8.98\times 10^{2} $ 24 $ 2.40\times 10^{2} $ $ 7.21\times 10^{0} $ ${\bf{2.20\times 10^{2}}} $ ${\bf{4.94\times 10^{0}}} $ $ 2.53\times 10^{2} $ $ 9.33\times 10^{0} $ $ 2.46\times 10^{2} $ $ 7.35\times 10^{0} $ $ 3.37\times 10^{2} $ $ 7.33\times 10^{1} $ $ 2.70\times 10^{2} $ $ 1.31\times 10^{1} $ 25 $ 3.14\times 10^{2} $ $ 3.34\times 10^{0} $ $ 2.73\times 10^{2} $ $ 8.64\times 10^{0} $ $ 2.81\times 10^{2} $ $ 6.78\times 10^{0} $ ${\bf{2.60\times 10^{2}}} $ ${\bf{6.08\times 10^{0}}} $ $ 3.56\times 10^{2} $ $ 2.80\times 10^{1} $ $ 2.99\times 10^{2} $ $ 1.24\times 10^{1} $ 26 $ 2.22\times 10^{2} $ $ 4.67\times 10^{1} $ ${\bf{2.03\times 10^{2}}} $ ${\bf{1.74\times 10^{1}}} $ $ 2.67\times 10^{2} $ $ 7.25\times 10^{1} $ $ 2.91\times 10^{2} $ $ 6.83\times 10^{1} $ $ 3.21\times 10^{2} $ $ 9.04\times 10^{1} $ $ 2.73\times 10^{2} $ $ 8.51\times 10^{1} $ 27 $ 7.73\times 10^{2} $ $ 2.03\times 10^{2} $ ${\bf{5.42\times 10^{2}}} $ ${\bf{3.92\times 10^{1}}} $ $ 8.10\times 10^{2} $ $ 1.11\times 10^{2} $ $ 7.47\times 10^{2} $ $ 1.26\times 10^{2} $ $ 1.28\times 10^{3} $ $ 1.10\times 10^{2} $ $ 9.72\times 10^{2} $ $ 1.33\times 10^{2} $ 28 $ 3.39\times 10^{2} $ $ 2.76\times 10^{2} $ ${\bf{3.00\times 10^{2}}} $ ${\bf{6.97\!\times\! 10^{\!-\!11} } }$ $ 4.29\times 10^{2} $ $ 5.27\times 10^{2} $ $ 3.64\times 10^{2} $ $ 2.59\times 10^{2} $ $ 4.34\times 10^{3} $ $ 2.08\times 10^{3} $ $ 4.37\times 10^{2} $ $ 4.67\times 10^{2} $
下载: 导出CSV
-
[1] Shiand Y H, Eberhart R C. Parameter selection in particle swarm optimizer. In: Proceedings of the 7th Annual Conference Evolutionary Programming, 1998, 25−27 [2] Clerc M, Kennedy J. The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE transactions on Evolutionary Computation, 2002, 6(1): 58?73 doi: 10.1109/4235.985692 [3] 王东风, 孟丽. 粒子群优化算法的性能分析和参数选择. 自动化学报, 2016, 42(10): 1552?1561 Wang Dong-Feng, Meng Li. Performance analysis and parameter selection of PSO algorithms. Acta Automatica Sinica, 2016, 42(10): 1552?1561 [4] 王丽芳, 曾建潮. 基于微粒群算法与模拟退火算法的协同进化方法. 自动化学报, 2006, 32(4): 630?635 Wang Li-Fang, Zeng Jian-Chao. A cooperative evolutionary algorithm based on particle swarm optimization and simulated annealing algorithm. Acta Automatica Sinica, 2006, 32(4): 630?635 [5] Chang D X, Zhang X D, Zheng C W, Zhang D M. A robust dynamic niching genetic algorithm with niche migration for automatic clustering problem. Pattern Recognition, 2010, 43(4): 1346?1360 doi: 10.1016/j.patcog.2009.10.020 [6] Luo R, Pan T S, Tsai P W, Pan J S. Parallelized artificial bee colony with ripple-communication strategy. In: Proceedings of 2010 Fourth International Conference on Genetic and Evolutionary Computing. IEEE, 2010, 350-353 [7] Wang D Z, Yan Y, Wang D W, Wang H F. OpenMP-based multi-population PSO algorithm to solve the uncapacitated facility location problem. Journal of Northeastern University, 2008, 29 [8] Roshanzamir M, Balafar M A, Razavi S N. A new hierarchical multi group particle swarm optimization with different task allocations inspired by holonic multi agent systems. Expert Systems with Applications, 2020, 149: 113292 doi: 10.1016/j.eswa.2020.113292 [9] Kennedy J, Eberhart R C. Particle swarm optimization. In: Proceedings of the IEEE International Conference on Neural Networks. Piscataway: IEEE Press, 1995, 1942−1948 [10] Matej ?repin?ek, Liu S H, Mernik M. Exploration and exploitation in evolutionary algorithms: a survey. ACM Computing Surveys, 2013, 45(3): 1?33 [11] Finnila A B, Gomez M A, Sebenik C. Quantumannealing: a new method for minimizing multidimensional functions. Chemical Physics Letters, 1994, 219: 343?348 doi: 10.1016/0009-2614(94)00117-0 [12] 方伟, 孙俊, 谢振平, 须文波. 量子粒子群优化算法的收敛性分析及控制参数研究. 物理学报, 2010, 59(6): 3686?3694 doi: 10.7498/aps.59.3686 Fang Wei, Sun Jun, Xie Zhen-Ping, Xu Wen-Bo. Convergence analysis of quantum behaved particle swarm optimization algorithm and study on its control parameter. Acta Physica Sinica, 2010, 59(6): 3686?3694 doi: 10.7498/aps.59.3686 [13] Sun J, Fang W, Wu X. Quantum-behaved particle swarm optimization: analysis of the individual particle behavior and paramseter selection. Evolutionary Computation, 2012, 20: 349?393 doi: 10.1162/EVCO_a_00049 [14] 王鹏, 黄焱, 任超, 郭又铭. 多尺度量子谐振子高维函数全局优化算法. 电子学报, 2013, 41(12): 2468?2473 doi: 10.3969/j.issn.0372-2112.2013.12.023 Wang Peng, Huang Yan, Ren Chao, Guo You-Ming. Multi-scale quantum harmonic oscillator for high dimensional function global optimization algorithm. Acta Electronica Sinica, 2013, 41(12): 2468?2473 doi: 10.3969/j.issn.0372-2112.2013.12.023 [15] 王鹏, 杨云亭. 基于量子自由粒子模型的优化算法框架. 电子学报, 2020, 48(7): 1348?1354 doi: 10.3969/j.issn.0372-2112.2020.07.013 Wang Peng, Yang Yun-Ting. Optimization algorithm farmework based on quantum free particle model. Acta Electronica Sinica, 2020, 48(7): 1348?1354 doi: 10.3969/j.issn.0372-2112.2020.07.013 [16] Narayanan A, Moore M. Quantum-inspired genetic algorithms. In: Proceedings of the IEEE Conference on Evolutionary Computation, 1996, 61−66 [17] Han K H, Kim J H. Genetic quantum algorithm and its application to combinatorial optimization problem. In: Proceedings of the 2000 Congress on Evolutionary Computation, 2000, 1354−1360 [18] Wang L, Niu Q, Fei M. A novel quantum ant colony optimization algorithm. In: Proceedings of the International Conference on Life System Modeling and Simulation, 2007, 277−286 [19] Li Y C, Li Z P, Yang L Q, Wang B. An improved quantum differential evolution algorithm for optimization and control in power systems including DGs. Acta Automatica Sinica, 2017, 43(7): 1280?1288 [20] Wang P, Ye X. Multi-scale quantum harmonic oscillator algorithm for global numerical optimization. Applied Soft Computing, 2018, 69: 655?670 doi: 10.1016/j.asoc.2018.05.005 [21] Rosenthal, Jeffrey S. Markov Chain Monte Carlo Algorithms: Theory and Practice. 2009, 157−169 [22] 王鹏, 黄焱. 多尺度量子谐振子优化算法物理模型. 计算机科学与探索, 2015, 9(10): 1271?1280 doi: 10.3778/j.issn.1673-9418.1502003 Wang Peng, Huang Yan. Physical model of multi-scale quantum harmonic oscillator optimization algorithm. Journal of Frontiers of Computer Science Technology, 2015, 9(10): 1271?1280 doi: 10.3778/j.issn.1673-9418.1502003 [23] Pharr, Matt, Greg Humphreys. Physically Based Rendering: From Theory to Implementation. 2004, 489−531 [24] Tan Y, Zhu Y. Fireworks algorithm for optimization. In: Proceedings of International conference in swarm intelligence. Springer, Berlin, Heidelberg, 2010, 355−364 [25] Tan Y, Yu C, Zheng S Q, Ding k. Introduction to fireworks algorithm. International Journal of Swarm Intelligence Research, 2013, 4(4): 39?70 doi: 10.4018/ijsir.2013100103 [26] Zheng S, Janecek A, Tan Y. Enhanced fireworks algorithm. In: Proceedings of 2013 IEEE congress on evolutionary computation. IEEE, 2013, 2069−2077 [27] Li J, Zheng S, Tan Y. Adaptive fireworks algorithm. In: Proceedings of 2014 IEEE Congress on evolutionary computation. IEEE, 2014, 3214−3221 [28] Zambrano B M, Clerc M, Rojas R. Standard particle swarm optimisation 2011 at cec-2013: A baseline for future pso improvements. In: Proceedings of 2013 IEEE Congress on Evolutionary Computation. IEEE, 2013, 2337−2344 [29] Sun J, Xu W, Feng B. A global search strategy of quantum-behaved particle swarm optimization. In: Proceedings of IEEE Conference on Cybernetics and Intelligent Systems, 2004, IEEE, 2004, 1: 111−116 [30] Sun J, Fang W, Wu X J, Vasile Palade, Xu W B. Quantum-behaved particle swarm optimization: Analysis of individual particle behavior and parameter selection. Evolutionary computation, 2012, 20(3): 349?393 doi: 10.1162/EVCO_a_00049 [31] Liang J J, Qu B Y, Suganthan P N, Alfredo G. Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization. In: Proceedings of Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou, China and Nanyang Technological University, Singapore, Technical Report, 2013 [32] Li J, Tan Y. Loser-out tournament-based fireworks algorithm for multimodal function optimization. IEEE Transactions on Evolutionary Computation, 2017, 22(5): 679?691 [33] 王柳静, 张贵军, 周晓根. 基于状态估计反馈的策略自适应差分进化算法. 自动化学报, 2020, 46(4): 752?766 Wang Liu-Jing, Zhang Gui-Jun, Zhou Xiao-Gen. Strategy self-adaptive differential evolution algorithm based on state estimation feedback. Acta Automatica Sinica, 2020, 46(4): 752?766 [34] Andre J, Siarry P, Dognon T. An improvement of the standard genetic algorithm fighting premature convergence in continuous optimization. Advances in engineering software, 2001, 32(1): 49?60 doi: 10.1016/S0965-9978(00)00070-3 [35] Holland J H. Adaptation in Natural and Artificial Systems. Michigan: University of Michigan Press, 1975 [36] Bertoni A, Dorigo M. Implicit parallelism in genetic algorithms. Articial Intelligence, 1993, 61(2): 307?314 doi: 10.1016/0004-3702(93)90071-I [37] Codling E A, Plank M J, Benhamou S. Random walk models in biology. Journal of the Royal Society Interface, 2008, 5(25): 813?834 doi: 10.1098/rsif.2008.0014 [38] Shenvi N, Kempe J, Whaley K B. Quantum random-walk search algorithm. Physical Review A, 2003, 67(5): 052307 doi: 10.1103/PhysRevA.67.052307 -
点击查看大图
计量
- 文章访问数: 14
- HTML全文浏览量: 1
- 被引次数: 0
