RR-SC: Run-Time Reconfigurable Framework for Stochastic Computing-Based Neural Networks on Edge Devices
-
摘要:
随着人工智能民主化的发展，深度神经网络已经被广泛地应用于移动嵌入式设备上，例如智能手机和自动驾驶领域等. 随机计算作为一种新兴的、有前途的技术在执行机器学习任务时使用简单的逻辑门而不是复杂的二进制算术电路. 它具有在资源（如能源、计算单元和存储单元等）受限的边缘设备上执行深度神经网络低能耗、低开销的优势. 然而，之前的关于随机计算的工作都仅仅设计一组模型配置并在固定的硬件配置上实现，忽略了实际应用场景中硬件资源（如电池电量）的动态改变，这导致了低硬件效率和短电池使用时间. 为了节省电池供电的边缘设备的能源，动态电压和频率调节技术被广泛用于硬件重配置以延长电池的使用时间. 针对基于随机计算的深度神经网络，创新性地提出了一个运行时可重配置框架，即RR-SC，这个框架首次尝试将硬件和软件的重配置相结合以满足任务的时间约束并最大限度节省能源. RR-SC利用强化学习技术可以一次性生成多组模型配置，同时满足不同硬件配置（即不同的电压/频率等级）下的准确率要求. RR-SC得到的解具有最好的准确率和硬件效率权衡. 同时，多个模型配置运行时在同一个主干网络上进行切换，从而实现轻量级的软件重配置. 实验结果表明，RR-SC可以在110 ms内进行模型配置的轻量级切换，以保证在不同硬件级别上所需的实时约束. 同时，它最高可以实现7.6倍的模型推理次数提升，仅造成1%的准确率损失.
Abstract:With the development of AI democratization, deep neural networks (DNNs) have been widely applied to edge devices, such as smart phones and automated driving, etc. Stochastic computing (SC) as a promising technique performs fundamental machine learning (ML) tasks using simple logic gates instead of complicated binary arithmetic circuits. SC has advantages of low-power and low-cost DNNs execution on edge devices with constrained resources (e.g., energy, computation and memory units, etc.). However, previous SC work only designs one group of setting for fixed hardware implementation, ignoring the dynamic hardware resources (e.g., battery), which leads to low hardware efficiency and short battery life. In order to save energy for battery-powered edge devices, dynamic voltage and frequency scaling (DVFS) technique is widely used for hardware reconfiguration to prolong battery life. In this paper, we creatively propose a run-time reconfigurable framework, namely RR-SC, for SC-based DNNs and first attempt to combine hardware and software reconfigurations to satisfy the time constraint of inference and maximally save energy. RR-SC using reinforcement learning (RL) can generate multiple groups of model settings at one time, which can satisfy the accuracy constraints under different hardware settings (i.e., different voltage/frequency levels). The solution has the best accuracy and hardware efficiency trade-off. Meanwhile, the model settings are switched on a backbone model at run-time, which enables lightweight software reconfiguration. Experimental results show that RR-SC can switch the lightweight settings within 110 ms to guarantee the required real-time constraint at different hardware levels. Meanwhile, it can achieve up to 7.6 times improvement for the number of model inference with only 1% accuracy loss.
-
在大数据时代背景下，利用数据进行分析和决策成为了不同领域的重要工作，各种人工智能算法为此提供了不可忽视的助力. 然而，“没有免费午餐”定理表明，不存在一个在所有问题上具备优越性能的“最优”算法[1]. 如何从大量可行方法中为给定任务选择满足需求的合适算法成为了工程中的关键问题，即算法选择问题[2]. 算法选择问题可以通过人工选择方法和机器学习方法解决. 人工选择方法包括实验试错法和专家知识法. 前者通过大量的实验获得算法性能，分析结果并选择算法；后者则按照领域专家的指导进行算法选择. 然而，实验试错法成本较高，专家知识法基于专家的经验知识，存在人为偏差且获取较为困难. 机器学习方法提取问题的抽象特征，设计模型实现自动化的算法选择，包括基于元学习的方法和基于协同过滤的方法[3-4]. 其中，基于元学习的方法研究基础较为深厚，具有灵活性高、适用范围广、计算成本低等优点，成为了算法选择的主要方法[5-7].
基于元学习的算法选择利用问题的元特征（抽象特征）和历史学习经验训练元算法，构建问题元特征到合适算法的映射. 元特征和元算法是其中的关键内容，而现有研究在元特征和元算法的选择和使用上存在一些缺点：在元特征方面，多数研究选择固定的元特征[8-10]，可扩展性较弱，且难以充分利用元特征的互补性；在元算法方面，研究或采用单个元算法，泛化性能不足，或采用同构集成元算法[11-14]，没有利用不同元算法的优势，导致多样性不足.
集成学习的相关研究表明，利用准确且多样的基学习器进行集成可以获得更精确、更稳定的学习性能[15-16]. 选择性集成方法根据基学习器的准确性和多样性从多个基学习器中选取部分进行集成，可以减少集成算法的存储空间和预测时间并提升其泛化性能，是集成学习的热点方向之一[17-19]. 演化算法有着鲁棒性强、适用性高、可以全局搜索等特性，在选择性集成研究中得到了广泛应用[20-22].
蚁狮优化（ant lion optimizer，ALO）[23]算法是近年来出现的演化算法，它模拟蚁狮捕食蚂蚁的行为机制对最优解进行搜索，具有寻优性能强、参数设置少、易于实现等优点. 研究人员将ALO扩展应用于多目标优化问题，在污水处理、工程设计等领域取得了良好的应用效果[24-26].
为了提升基于元学习的算法选择性能，提出基于多目标混合蚁狮优化的选择性集成算法选择方法（selective ensemble algorithm selection method based on multi-objective hybrid ant lion optimizer，SAMO），该方法包括一种算法选择模型和一种多目标混合蚁狮优化算法. 算法选择模型以集成元算法的准确性和多样性作为优化目标，同时选择元特征和构建选择性集成元算法. 多目标混合蚁狮优化算法对模型进行优化，通过离散型编码选择元特征子集，使用连续型编码构建集成元算法，在此基础上应用增强游走策略和偏好精英选择机制提升寻优性能.
本文的主要贡献包括3个方面:
1）提出一种算法选择模型，同时从元特征和元算法2个方面提升基于元学习的算法选择性能. 模型通过元特征选择寻找互补性较强的元特征子集，通过选择性集成构建异构集成元算法.
2）提出一种多目标混合蚁狮优化算法，求解算法选择模型. 通过混合编码机制使个体同时进行元特征选择和选择性集成；采用增强游走策略，在个体搜索过程中引入随机性，增加算法的种群多样性；应用偏好精英选择机制，以不同的优化目标为偏好选择精英个体，增强算法的寻优能力.
3）使用260个数据集、150种元特征和9种候选算法构建分类算法选择问题，在此基础上将所提方法与8种典型方法在4种性能指标上进行对比分析，结果证明了所提方法的有效性和优越性.
1. 相关概念和工作
1.1 基于元学习的算法选择
1.1.1 基于元学习的算法选择框架
基于元学习的算法选择框架[27-28]如图1所示. 框架首先提取历史数据集的元特征，并通过性能测度评估确定历史数据集的最优算法，在过程中采用不同的性能测度方法可能获得不同的最优算法；然后以元特征为属性，以最优算法为标签组成元实例构建元数据集，并在元数据集上训练元算法；最后，提取新数据集的元特征输入已训练的元算法，元算法即对其最优算法进行预测输出.
1.1.2 元特征相关内容
根据反映数据集特性的不同，元特征分为4类：
1）基于统计和信息论的元特征采用统计学和信息论的方法提取数据集的抽象特征[27]. 该类型元特征应用广泛且易于提取，然而其难以较好地刻画数据集特性.
2）基于决策树的元特征在数据集上训练决策树，使用决策树的结构信息作为元特征[28]. 其能够发掘数据集的整体特性，但提取成本高昂.
3）基于基准的元特征将基准算法在数据集上的性能指标值作为元特征[29]，其提取方法较为简单，然而对基准算法的依赖度较高.
4）基于问题复杂度的元特征从类重叠、类不平衡、数据稀疏度等方面对数据集的几何复杂度进行量化评估[30]. 该类型元特征反映了求解问题的困难程度，应用效果较好，但是计算复杂度较大.
1.1.3 元算法相关内容
按照训练过程的技术特点，将元算法分为4类：
1）基于规则的元算法生成候选算法的选择规则，通过将元特征与规则进行匹配，为新数据集选择合适算法，该方法具备较强的可解释性，但泛化性能较差. 针对负荷预测问题，文献[8]提取18种数据集元特征，训练分类回归树（classification and regression tree，CART）选择最优算法.
2）基于距离的元算法通过元特征测度距离，评估数据集之间的相似度，使用相似数据集的最优算法作为新数据集的合适算法. k最近邻（k nearest neighbors，kNN）是研究中常见的元算法，其实现简单且运行较快，但关键参数k的最优值设置较为困难. 文献[9]使用32种分类数据集元特征，基于kNN构建元特征到最优算法的映射.
3）基于回归的元算法预测各候选算法的性能指标值并进行比较，从而完成算法选择决策，使用较为广泛的元算法为支持向量回归（support vector regression，SVR）. 该类方法可以灵活地增减候选算法，但训练成本较高. 文献[10]选用12种元特征，应用SVR学习元特征与候选分类算法性能的映射关系.
4）基于集成的元算法通过一定策略组合多个性能较弱的元算法，得到具有较强性能的集成元算法，常见的元算法包括随机森林（random forest，RF）、极端梯度提升（extreme gradient boosting，XGB）等，这些方法的泛化性能较好，但训练速度较慢且参数设置较为复杂. 文献[11]提取22种元特征，采用RF学习元特征到最优分类算法的映射. 文献[12]使用22种元特征，采用随机森林回归（random forest regression，RFR）预测候选分类算法的性能. 文献[13]提取98种图像元特征，分别训练RF和XGB并预测最优图像分割算法. 文献[14]选择39种分类数据集元特征，应用轻量梯度提升机（light gradient boosting machine，LGBM）进行算法选择.
在上述研究中，元特征和元算法的选用仍存在一些问题：在元特征方面，研究通常根据需求选取固定的元特征，耦合度较高，可扩展性较弱；不同元特征从不同方面描述和提取数据集的抽象特征，具备一定的互补性，然而现有的方法难以有效利用. 在元算法方面，现有研究或使用泛化性能较弱的单个元算法，或采用同构基学习器的集成元算法，未能充分利用不同元算法的优势和多样性.
1.2 多目标优化问题
多目标优化是指同时优化多个目标且目标间相互矛盾的问题，该问题通常是NP难的，无法获取唯一最优解，而是一组次优解[31]. 不失一般性地以最小化问题为例，给出多目标优化问题的定义.
定义1. 多目标优化问题. 给定一个具有n维决策变量，m（m≥2）个目标的优化问题，其数学模型的定义如式（1）所示：
\min {\boldsymbol{F}}({\boldsymbol{x}}) = {({f_1}({\boldsymbol{x}}),{f_2}({\boldsymbol{x}}), … ,{f_m}({\boldsymbol{x}}))^{\text{T}}},{\boldsymbol{x}} \in \varOmega \text{，} (1) 其中x=（x1, x2,…, xn），x为决策向量，Ω为决策空间；F:Ω→Λ，F为目标函数向量，Λ为由m个优化目标构成的目标空间.
定义2. 帕累托支配. 给定2个解x和y，当满足如式（2）所示约束条件时，则称x支配y，表示为{\boldsymbol{x}} \prec{\boldsymbol{ y }}.
\left\{\begin{aligned} & \forall i\in \{1,2,… ,m\},{f}_{i}({\boldsymbol{x}})\le {f}_{i}({\boldsymbol{y}})\text{，}\\ & \exists i\in \{1,2,… ,m\},{f}_{j}({\boldsymbol{x}}) < {f}_{j}({\boldsymbol{y}}). \end{aligned}\right. (2) 定义3. 帕累托最优解. 给定解x∈Ω，当且仅当不存在另一个解支配它，即{\nexists }{\boldsymbol{y}}\in \varOmega :{\boldsymbol{y}}\prec {\boldsymbol{x}}时，x为帕累托最优解.
定义4. 帕累托解集（Pareto set，PS). 决策空间Ω中所有帕累托最优解的集合称为帕累托解集，如式（3）所示：
PS=\{{\boldsymbol{x}}\in \varOmega |{\nexists }{\boldsymbol{y}}\in \varOmega ,{\boldsymbol{y}}\prec {\boldsymbol{x}}\} . (3) 定义5. 帕累托前沿（Pareto front，PF）. PS对应的目标向量集合称为帕累托前沿，如式（4）所示：
PF = \{ {\boldsymbol{F}}({\boldsymbol{x}}) \in \varLambda |{\boldsymbol{x}} \in PS\} . (4) 多目标优化旨在获取靠近真实PF的解集S，从2个方面评估解集S的质量：收敛性，即解集S与真实PF的接近程度；分布性，即解集S在目标空间中的散布程度.
1.3 ALO
ALO通过蚂蚁的随机游走模拟蚁狮使用陷阱诱捕蚂蚁的过程，实现个体解的搜索更新. 蚂蚁各维度的随机游走方法如式（5）所示：
\begin{split}{\boldsymbol{X}}({{t}})=&(0,cusum\left({r}_{{t}_{1}}\left(rand\right)\right),cusum\left({r}_{{t}_{2}}\left(rand\right)\right),\\ &\cdots ,cusum\left({r}_{{t}_{T}}\left(rand\right)\right))\text{，}\end{split} (5) 其中t为当前迭代次数，T为最大迭代次数，X（t）表示随机游走位置，cusum表示随机游走步长的累加和，{r}_{t}(rand)=\left\{\begin{array}{l}1,\text{ }rand > 0.5 \\ -1,\text{ }rand\leqslant 0.5 \end{array} \right. 用于生成随机游走步长，rand表示位于[0,1]之间均匀分布的随机数.
在随机游走过程中，蚂蚁逐渐滑入陷阱，其游走边界随之缩小，如式（6）所示：
{{\boldsymbol{c}}^t} = \frac{{\boldsymbol{c}}}{I},{{\boldsymbol{d}}^t} = \frac{{\boldsymbol{d}}}{I} . (6) 其中c和d表示个体各维度值的上界和下界， {{\boldsymbol{c}}^t} 和 {{\boldsymbol{d}}^t} 分别表示第t次迭代中蚂蚁各维度值搜索范围的上界和下界，缩小程度I的计算如式（7）所示：
I = {10^w}\frac{t}{T} \text{，} (7) 其中倍率因子w的值取决于当前迭代次数t. t ≤ 0.1T时，w = 0；t > 0.1T时，w = 2；t > 0.5T时，w = 3；t > 0.75T时，w = 4；t > 0.9T时，w = 5；t > 0.95T时，w = 6. 可见随着t的增加，10w和I值呈递增趋势，而 {{\boldsymbol{c}}^t} 和 {{\boldsymbol{d}}^t} 呈递减趋势.
ALO将适应度最优的蚁狮选为精英蚁狮，每只蚂蚁通过轮盘赌方法选择1个蚁狮，围绕精英蚁狮和轮盘赌蚁狮进行随机游走，并根据式（8）更新位置：
{{\boldsymbol{A}}^t} = \frac{{{\boldsymbol{R}}_{\boldsymbol{e}}^t + {\boldsymbol{R}}_{\boldsymbol{r}}^t}}{2} \text{，} (8) 其中At为第t次迭代蚂蚁的位置向量，e和r分别表示精英蚁狮和轮盘赌蚁狮，{\boldsymbol{R}}_{\boldsymbol{e}}^t为第t次迭代蚂蚁围绕e进行随机游走得到的向量，{\boldsymbol{R}}_{\boldsymbol{r}}^t为第t次迭代蚂蚁围绕r进行随机游走所得向量.
2. SAMO
为了充分利用元特征的互补性和元算法的多样性来提升算法选择性能，SAMO设计算法选择模型，并提出多目标混合蚁狮优化算法对模型进行求解，从而构建准确性和多样性较强的集成元算法.
使用SAMO进行算法选择的流程如图2所示. 将元数据集输入SAMO后，SAMO利用所提优化算法对模型进行优化，输出集成元算法集合，然后从其中选择一个集成元算法用于预测新数据集的最优算法.
2.1 算法选择模型
2.1.1 模型优化目标
模型使用分类错误率（error rate，ER），评估集成元算法的准确性.
设有m个测试元实例X={x1, x2,…, xm}，各个元实例对应的最优算法标签为Y={y1, y2,…, ym}，且有yk∈A,1 ≤ k ≤ m，其中A={a1, a2,…, al}为包含l个候选算法标签的集合，ER的计算公式为
E{R_E} = \frac{1}{m}\sum\limits_{i = 1}^m {e({{\hat y}_i},{y_i})} \text{，} (9) 其中E表示集成元算法，e({{\hat y}_i},{y_i}) = \left\{ \begin{aligned} & 1, {{\hat y}_i} \ne {y_i} \\ & 0, {{\hat y}_i} = {y_i} \end{aligned} \right.，{{\hat y}_i}和 {y_i} 分别表示第i个测试元实例的预测最优算法标签和真实最优算法标签. 通过加权投票法，利用集成权重W={w1, w2,…, wv}组合v个基分类器B={b1, b2,…, bv}构建集成元算法E，E对测试元实例xk∈X进行预测，如式（10）所示：
E({{\boldsymbol{x}}_k}) = \mathop {{\rm{arg\;max}} }_{a \in A} \left(\sum\limits_{i = 1}^v {{w_i}I({b_i}({{\boldsymbol{x}}_k}) = a)} \right) \text{.} (10) 其中E（xk）表示预测最优算法结果；a为A中的一个候选算法标签；bi表示B中的第i个基分类器，bi（xk）表示对xk的预测结果；I（）为示性函数，当其中的表达式逻辑为真时，I（）=1，否则I （）=0；wi为第i个基分类器的集成权重；函数 \mathop {\arg \max }\limits_{a \in A} （）表示取使其内部表达式最大的算法标签a. ER值越小，表示集成元算法的性能越好.
采用不同的多样性指标（diversity indicator，DI），度量集成元算法的多样性，包括Q统计量（Q statistic，QS）、K统计量（K statistic，KS）、相关系数（correlation coefficient，CC）、一致度量（agreement measure，AM）和双错测度（double fault，DF）.
基分类器bi和bj对X的预测结果列联表如表1所示.
表 1 预测结果列联表Table 1. Contingency Table of Prediction Resultsbj预测结果 bi预测结果 bi（xk）= yk bi（xk）≠ yk bj（xk）= yk c p bj（xk）≠ yk q d 表1中，c表示bi和bj均预测正确的元实例数；p表示bi预测正确而bj预测错误的元实例数；q表示bi预测错误而bj预测正确的元实例数；d表示bi和bj均预测错误的元实例数. 根据表1，bi和bj的QS，KS，CC，AM，DF指标计算公式为
Q{S_{{b_i}}}_{,{b_j}} = \frac{{c\times d - p\times q}}{{c\times d + p\times q}} \text{，} (11) K{S_{{b_i}}}_{,{b_j}} = \frac{{2(c \times d - p\times q)}}{{(c + p)(p + d) + (c + q)(q + d)}} \text{，} (12) C{C_{{b_i}}}_{,{b_j}} = \frac{{c\times d - p \times q}}{{\sqrt {(c + p)(c + q)(q + d)(p + d)} }} \text{，} (13) A{M_{{b_i}}}_{,{b_j}} = \frac{{c + d}}{m} \text{，} (14) D{F_{{b_i}}}_{,{b_j}} = \frac{d}{m} . (15) 式（11）~（15）所述的指标值越小代表基分类器多样性越强，除AM和DF指标的值域为[0,1]外，其余指标的值域均为[−1,1]；此外，这5个指标均为成对指标，即满足DI_{{b_i,b_j}}=DI_{{b_j,b_i}}. 集成元算法E的DI值为所有成对基分类器DI值的平均值，如式（16）所示：
D{I_E} = \frac{{\displaystyle\sum\limits_{j = i + 1}^v {\displaystyle\sum\limits_{i = 1}^{v - 1} {D{I_{{b_i}}}_{,{b_j}}} } }}{{({v^2} - v)/2}} . (16) 综上，算法选择模型的目标函数向量为
{{\boldsymbol{F}}_{{\rm{SAMO}}}} = \min (E{R_E},D{I_E}) \text{.} (17) 2.1.2 模型设计
模型从元特征和元算法2个方面提升算法选择性能. 在元特征方面，选择互补性较强的元特征子集，从而有效利用元特征；在元算法方面，通过选择性集成方法，对异构基分类器进行集成，构建具有较强泛化性能和多样性的集成元算法. 为了利用不同基分类器的优势和多样性，采用kNN、支持向量机（support vector machine，SVM）和CART作为基分类器，且本文设置每种基分类器的个数相等.
在对元数据集进行元特征选择的基础上，算法选择模型构建集成元算法的过程如图3所示. 首先使用自助法对训练集进行若干次抽样生成多个训练子集；然后运用基分类器在训练子集上进行训练形成基分类器集合；最后通过选择性集成方法，从集合中选择准确性和多样性较强的基分类器并基于加权投票法策略进行组合，得到集成元算法.
2.2 多目标混合蚁狮优化算法
2.2.1 混合编码机制
多目标混合蚁狮优化算法针对元特征选择的离散特性（元特征选择与否），使用离散型编码选择元特征子集；采用连续型编码构建集成元算法，该连续型编码包括1个用于控制基分类器选择概率的选择阈值编码，以及若干个基分类器权重编码，用于选择基分类器的训练子集并生成集成权重.
个体的混合编码方式如图4所示. 设元数据集含有M个元特征，则个体的离散型编码数为M；设基分类器个数为V，则自助法抽样生成的训练子集个数为V，个体依次为kNN，SVM，CART使用V个编码选择训练子集和生成集成权重，因此基分类器权重编码数为3V，个体的连续型编码数为3V+1.
根据混合编码机制，对个体各维度的编码值进行初始化，如式（18）所示：
{A}_{i}=\left\{\begin{array}{l}R(rand),i\le M\text{，}\\ rand,\text{}i > M\text{，}\end{array} \right. (18) 其中Ai为个体第i维的编码值，个体前M维编码为离散型的元特征选择编码，R(rand) = \left\{ \begin{gathered} 1,{\text{ }}rand \geqslant 0.5, \\ 0,{\text{ }}rand < 0.5 , \\ \end{gathered} \right.其值为1表示第i维编码对应的元特征被选中，值为0表示未被选中. 个体第M+1维编码为选择阈值编码，其后的3V个编码为基分类器权重编码，前V个基分类器权重编码为kNN选择训练子集，如式（19）所示：
J({A}_{i})=\left\{\begin{array}{l}1,\text{}{A}_{i}\ge {A}_{M+1}\text{，}\\ 0,\text{}{A}_{i} < {A}_{M+1}\text{，}\end{array}M+1 < i\le M+V+1\text{，}\right. (19) 其中AM+1为选择阈值编码值，J（Ai）= 1表示第i维编码对应的训练子集被选中，J({A}_{i}) = 0表示未被选中，以此类推可得SVM和CART的训练子集. 3种基分类器分别在选择的训练子集上独立训练，得到基分类器集合B={b1,b2,…,bv}，通过基分类器权重编码值生成这3种基分类器集合对应的集成权重W={w1,w2,…,wv}，如式（20）所示：
{w_i} = \frac{{{A_i}}}{{\displaystyle\sum\limits_{j = 1}^v {{A_j}} }} \text{，} (20) 其中wi为第i个基分类器的集成权重，Ai为第i个基分类器对应的基分类器权重编码值，Aj为第j个基分类器对应的基分类器权重编码值. 通过式（20）的归一化方法，使得集成权重和为1，即\displaystyle\sum\limits_{i = 1}^v {{w_i}} = 1.
2.2.2 增强游走策略
在混合编码机制的基础上，采用增强游走策略对个体进行搜索更新.
在迭代过程中，个体的离散型编码使用离散随机游走方法，如式（21）所示：
{R}_{{\rm{dis}},i}^{t}=\left\{\begin{array}{l}{L}_{{\rm{dis}},i}^{t},\text{ }{X}^{t}/t\ge m(t)\text{，}\\ 1-{L}_{{\rm{dis}},i}^{t},\text{ }{X}^{t}/t < m(t)\text{.}\end{array}\right. (21) 其中R_{{\rm{dis}},i}^t为第t次迭代蚂蚁的离散型编码进行离散随机游走后所得离散向量的第i维元素值；L_{{\rm{dis}},i}^t为第t次迭代蚂蚁所围绕游走的蚁狮第i维离散型编码值；X t为式（5）中第t次迭代对应的随机游走步长累加和，由式（5）可知其值在[−t, t]之间，由此可得X^t/t 位于[−1,1]之间，取反阈值m(t)计算如式（22）所示：
m(t) = (2rand - 1)\cos \frac{{\pi (t - 1)}}{{2(T - 1)}} . (22) 其中\cos \dfrac{{\pi (t - 1)}}{{2(T - 1)}}在[0,1]之间随着迭代次数t的增加呈现非线性递减趋势，（2rand−1）的值域为[−1,1]，使得m（t）在[−1,1]之间随t值增加呈现随机性的非线性递减趋势，如图5所示.
随机游走后，蚂蚁离散型编码值更新为
{A}_{{\rm{dis}},i}^{t}=\left\{\begin{array}{l}{R}_{{\rm{dis}},{\boldsymbol{e}},i}^{t},\text{}rand\ge 0.5\text{，}\\ {R}_{{\rm{dis}},{\boldsymbol{r}},i}^{t},\text{}rand < 0.5\text{，}\end{array}\right. (23) 其中A_{{\rm{dis}},i}^t为第t次迭代蚂蚁的第i维离散型编码值，R_{{\rm{dis}},{\boldsymbol{e}},i}^t和R_{{\rm{dis}},{\boldsymbol{r}},i}^t分别为蚂蚁在第t次迭代围绕精英蚁狮和轮盘赌蚁狮进行离散随机游走所得离散向量的第i维元素值.
对于个体的连续型编码，在其游走更新过程中引入随机性. ALO中每只蚂蚁的搜索边界{{\boldsymbol{c}}^t}和{{\boldsymbol{d}}^t}变化趋势相同，种群多样性不足. 为了增强所提算法的种群多样性，对式（6）进行改进，如式（24）所示：
\begin{aligned} & {{\boldsymbol{c}}}^{t}=\frac{{\boldsymbol{c}}}{I}\left(\mathrm{cos}\frac{\pi (t-1)}{3(T-1)}+rand-0.5\right)\text{，}\\ & {{\boldsymbol{d}}}^{t}=\frac{{\boldsymbol{d}}}{I}\left(\mathrm{cos}\frac{\pi (t-1)}{3(T-1)}+rand-0.5 \right)\text{，} \end{aligned} (24) 其中\cos \dfrac{{\pi (t - 1)}}{{3(T - 1)}}在[0.5,1]之间随着迭代次数t的增加呈现非线性递减趋势，使得\left(\cos \dfrac{{\pi (t - 1)}}{{3(T - 1)}} + rand - 0.5\right)在[0,1.5]之间呈现随机性的非线性递减趋势，从而在{{\boldsymbol{c}}^t}和{{\boldsymbol{d}}^t}的变化过程中引入一定随机性. 本文所提算法与ALO的搜索边界变化趋势对比如图6所示.
通过上述设计，增强游走策略对个体不同类型的编码进行搜索更新，保留了蚂蚁搜索边界变化的递减趋势，同时在该过程中引入了随机性，增加了算法的种群多样性.
2.2.3 偏好精英选择机制
算法将帕累托解作为蚁狮保存至外部存档S，为了提升算法的寻优能力，分别以不同优化目标为偏好，从存档S中选择在该目标上最优的精英蚁狮. 为了增强解的分布性，通过小生境技术计算蚁狮解的稀疏度从而量化其分布性，然后利用稀疏度通过轮盘赌选择蚁狮，蚁狮解xS的稀疏度为
s({{\boldsymbol{x}}_S},\varphi ) = \frac{{\left| S \right| - 1}}{{\left| {\left\{ {{{\boldsymbol{y}}_S} \in S\left| {\left\| {{\boldsymbol{F}}({{\boldsymbol{x}}_S}) - {\boldsymbol{F}}({{\boldsymbol{y}}_S})} \right\| < \varphi } \right.} \right\}} \right|}} . (25) 其中s({{\boldsymbol{x}}_S},\varphi ) 表示给定半径\varphi 的小生境范围内解xS的稀疏度，yS表示存档S中的另一个解，半径\varphi 计算为
\varphi =\frac{{\displaystyle \sum _{j=i+1}^{m}{\displaystyle \sum _{i=1}^{m-1}\Vert {\boldsymbol{F}}({{\boldsymbol{e}}}_{i})-{\boldsymbol{F}}({{\boldsymbol{e}}}_{j})\Vert }}}{({m}^{2}-m)c/2}\text{，}0 < c\le \left|S\right| \text{，} (26) 其中m（m≥2）为优化目标个数，ei和ej分别表示第i个和第j个优化目标对应的精英蚁狮， \left\| {{\boldsymbol{F}}({{\boldsymbol{e}}_i}) - {\boldsymbol{F}}({{\boldsymbol{e}}_j})} \right\| 计算二者目标函数值向量的欧氏距离，c为常数； \left\| {{\boldsymbol{F}}({{\boldsymbol{x}}_S}) - {\boldsymbol{F}}({{\boldsymbol{y}}_S})} \right\| 计算解xS和解yS目标函数值向量的欧氏距离，其值小于半径\varphi 时表示yS是xS的相邻解. 给定解在存档中的相邻解越多，则该解的稀疏度越低，分布性越差. 以2个优化目标为例，稀疏度计算示意如图7所示.
在迭代过程中，对于每个优化目标，每只初始化蚂蚁根据蚁狮的稀疏度通过轮盘赌选择1个蚁狮，围绕该优化目标的精英蚁狮和轮盘赌蚁狮进行随机游走，产生新的个体解. 由此可得个体数是初始化种群的新蚂蚁种群的m倍，将新蚂蚁种群加入外部存档，筛选保留存档中的帕累托解作为新一代蚁狮.
通过偏好精英选择机制，分别围绕不同优化目标上的最优个体进行迭代更新，增强算法的寻优性能；采用轮盘赌方法以较大概率选择分布性较好的个体，并围绕该个体进行搜索，使解的分布性更强.
2.3 SAMO方法整体描述
SAMO流程如图8所示. 方法首先输入元数据集；然后根据混合编码机制初始化蚂蚁种群；计算蚂蚁的适应度，通过帕累托支配关系从中选出帕累托解作为蚁狮保存至外部存档；按照偏好精英选择机制，从蚁狮中选出准确性和多样性优化目标上的精英个体，分别称为准确性精英蚁狮和多样性精英蚁狮，并计算蚁狮的稀疏度；在迭代过程中，每只初始化蚂蚁根据蚁狮稀疏度进行2次轮盘赌选择蚁狮，围绕准确性精英蚁狮和第1次轮盘赌蚁狮，以及围绕多样性精英蚁狮和第2次轮盘赌蚁狮，基于增强游走策略进行随机游走，生成2只新的蚂蚁；计算新蚂蚁种群的适应度并将其加入存档，更新存档和精英蚁狮；最后，达到最大迭代时，输出蚁狮构建的集成元算法集合. 在该过程中，个体的适应度为集成元算法的准确性和多样性指标值.
SAMO方法的伪代码如算法1所示.
算法1. SAMO方法.
输入：元数据集D、基分类器个数V、多样性指标DI、最大迭代次数T、种群规模N；
输出：蚁狮构建的集成元算法集合ES.
① initAnts←initialize（D,V,N）；/*获取D的元特征 数M，根据M和V确定个体不同类型编码 的维度数，基于混合编码机制，通过式（18） 获取N个蚂蚁的初始化种群initAnts*/
② trSubsets←bootStrap（V）；/*对训练集使用自助 法抽样生成V个训练子集trSubsets*/
③ for each ant A in initAnts
④ mfSubset←mfSelection（A）；/*根据蚂蚁A的 离散型编码选择元特征子集mfSubSet*/
⑤ EA←selEnsemble（A,mfSubset,trSubsets）；/*在 使用mfSubSet的基础上，根据A的连续 型编码，通过式（19）（20）为基分类器选 择训练子集和生成集成权重，训练基分 类器并集成得到集成元算法EA*/
⑥ FA=[EREA,DIEA]←caculateFit（EA, DI）；/*通过 式（9）（16）计算EA的ER值和DI值作为 A的适应度值FA*/
⑦ end for
⑧ S←updateArchive（initAnts）；/*将initAnts加入 外部存档S，根据式（2）计算解的支配关系， 保留存档中的帕累托解作为蚁狮*/
⑨ eER,eDI←updateElites（S）；/*从S中选择ER值最 优的准确性精英蚁狮eER和DI值最优的多 样性精英蚁狮eDI*/
⑩ while iter=1,iter≤T
⑪ sparS←caculateSparsity（S）；/*通过式（25）计 算存档中蚁狮的稀疏度sparS*/
⑫ for each ant A in initAnts
⑬ r←rouletteWheel（A,sparS）；/*A根据稀疏 度sparS通过轮盘赌选择蚁狮r*/
⑭ Re,Rr←randomWalk（A,eER,r）；
/*A通过式（21）~（24）围绕蚁狮eER和r进行随机 游走产生向量Re和Rr*/
⑮ A′=updateAnt（Re,Rr）；/*使用Re和Rr，通过 式（8）（23）生成新蚂蚁个体A′*/
⑯ 将步骤⑭~⑯中的eER和A′替换为eDI和 A″后，重复步骤⑭~⑯；
⑰ newAnts←newAnts∪{A′,A″}；/*将A′和A″ 加入新蚂蚁种群newAnts*/
⑱ end for
⑲ 将步骤④~⑩中的initAnts替换为newAnts 后，重复步骤④~⑩；
⑳ iter=iter+1；
㉑ end while
㉒ 输出S中蚁狮构建的集成元算法集合ES.
现对SAMO的时间复杂度进行分析，设元特征数为M，基分类器个数为V，可得个体维度数D=M+3V+1；设种群规模为N，最大迭代次数为T，则蚂蚁随机游走进行迭代的时间复杂度为O（2N×D×T），计算解的支配关系和稀疏度的时间复杂度为O（N2×T）.综上所述，SAMO的时间复杂度为O（N×T×（N+2D））.
3. 实验与结果分析
3.1 实验设置
3.1.1 数据集
由于分类算法应用的广泛性，通过分类算法选择问题进行测试实验. 实验使用来自于UCI[32]，KEEL[33]，StatLib[34]，OpenML[35]的260个分类数据集，这些数据集的数据来源领域各异，实例数从13~149332不等，属性数从1~1558不等，类数从2~188不等，具有一定的差异性，构成多样化的数据集，从而能够有效评估方法的性能. 实验数据集信息如表2所示.
表 2 实验数据集信息Table 2. Information of Experimental Datasets序号 数据集 属性数 实例数 类数 序号 数据集 属性数 实例数 类数 序号 数据集 属性数 实例数 类数 1 abalone 8 4177 29 88 divorce 54 170 2 175 online-shoppers 17 12330 2 2 absenteeism 20 740 18 89 dna 180 3186 3 176 optdigits 64 3823 10 3 ada-agnostic 48 4562 2 90 dry-bean 16 13611 7 177 ozone-1hr 72 2536 2 4 advertisement 1558 3279 2 91 echocardiogram 11 75 3 178 ozone-8hr 72 2534 2 5 aids 4 50 2 92 ecoli 7 336 8 179 page-blocks 10 5473 5 6 allrep 29 3772 4 93 eeg-eyestate 14 14980 2 180 parkinson-speech 26 1040 2 7 amazon-employ 9 32769 94 electricity 8 45132 2 181 pc1 21 1109 2 8 acd-assessment 15 13 4 95 energy-eff 9 768 37 182 pc3 37 1563 2 9 acd-authorship 70 841 4 96 engine1 5 383 3 183 pc4 37 1458 2 10 acd-bankruptcy 6 50 2 97 eucalyptus 19 736 5 184 penbased 16 10992 10 11 acd-birthday 3 365 7 98 fabert 800 8237 7 185 phishing-websites 30 2456 2 12 acd-bondrate 11 57 5 99 first-order 51 6118 6 186 phoneme 5 5404 2 13 acd-boxing1 3 120 2 100 flag 28 194 8 187 pima 8 768 2 14 acd-boxing2 3 132 2 101 flare 11 1066 6 188 polish-bankruptcy1 64 7027 2 15 acd-braziltour 8 412 7 102 gas-drift 128 13910 6 189 polish-bankruptcy5 64 5500 2 16 acd-broadway 9 95 5 103 german 20 1000 2 190 popularkids 10 478 3 17 acd-broadwaym 7 285 7 104 gesture-phase 32 9873 5 191 post-operative 8 90 3 18 acd-chall101 2 138 2 105 gina-prior2 784 3468 10 192 primary-tumor 17 339 22 19 acd-creditscore 6 100 2 106 glass 9 214 7 193 prnn-fglass 9 214 6 20 acd-currency 3 31 7 107 haberman 3 306 2 194 ring 20 7400 2 21 acd-cyyoung8 10 97 2 108 hayes-roth-test 4 28 4 195 risk-factors 35 858 26 22 acd-cyyoung9 10 92 2 109 hayes-roth-train 4 132 4 196 rmftsa-sleep 2 1024 4 23 acd-dmft 4 797 6 110 hcv-egyptian 28 1385 4 197 robot-failures-lp4 90 117 3 24 acd-draft 4 365 12 111 heart-statlog 13 270 2 198 saheart 9 462 2 25 acd-esr 2 32 2 112 helena 27 65196 100 199 sat11-hand-runtime 115 296 14 26 acd-germangss 5 400 4 113 hepatitis 19 155 2 200 satimage 36 6435 7 27 acd-halloffame 17 1340 3 114 hill-valley 100 1212 2 201 sat-test 36 2000 6 28 acd-homerun 26 162 2 115 horse-colic-test 27 68 2 202 sat-train 36 4435 6 29 acd-lawsuit 4 264 2 116 horse-colic-train 27 300 2 203 seeds 7 210 3 30 acd-mapleleafs 1 84 3 117 house-votes 16 232 2 204 semeion 256 1593 10 31 acd-marketing 32 310 5 118 ilpd 10 583 2 205 sensor-readings-24 24 5456 4 32 acd-supreme 7 4052 10 119 image-seg-test 19 210 7 206 sensor-readings-4 4 5456 4 33 acd-votesurvey 4 48 4 120 image-seg-train 19 2100 7 207 servo 4 167 2 34 anneal 38 798 6 121 indian-pines 220 9144 8 208 shuttle 9 58000 7 35 anomalydata-5 4 1050 2 122 internet-usage 70 10108 46 209 shuttle-landing 6 15 2 36 anomalydata-5h 10 1050 2 123 ionosphere 34 351 2 210 smartphone-har 66 180 6 37 appendicitis 7 106 2 124 iris 4 150 3 211 socmob 5 1156 2 38 arrhythmia 279 452 16 125 isolet1234 617 6238 26 212 sonar 60 208 2 39 artificial-charac 7 10218 10 126 isolet5 617 1559 26 213 soybean-large 35 307 19 40 asp-potassco 140 1294 11 127 japanese-vowels 14 9961 9 214 soybean-small 35 47 4 41 audiology 69 226 24 128 jungle-chess-l-e 46 4704 3 215 spambase 57 4597 2 42 australian 14 690 2 129 jungle-chess-p-l 46 4704 3 216 spect-test 22 187 2 43 autism-adult 20 704 2 130 jungle-chess-r-e 46 5880 3 217 spect-train 22 80 2 44 autohorse-fixed 68 201 186 131 kc1 21 2109 2 218 spectf-test 44 269 2 45 automobile 25 205 7 132 kc2 21 522 2 219 spectf-train 44 80 2 46 autouniv1-1000 20 1000 2 133 kr-vs-kp 36 3196 2 220 spectrometer 101 531 48 47 autouniv4-2500 100 2500 3 134 kropt 6 28056 18 221 speech 400 3686 2 48 autouniv6-1000 40 1000 8 135 leaf 15 340 30 222 splice 60 3190 3 49 autouniv6-750 40 750 8 136 leaves-margin 64 1600 100 223 steel-plates-faults 27 1941 7 50 autouniv7-1100 12 1100 5 137 leaves-shape 64 1600 100 224 student-mat 30 395 21 51 autouniv7-500 12 500 5 138 leaves-texture 64 1600 100 225 student-por 30 649 21 52 bach-choral 16 5665 102 139 led24 24 3200 10 226 surveillance 7 15 3 53 balance-scale 4 625 3 140 led7digit 7 500 10 227 synthetic-control 60 600 6 54 ballon 4 16 2 141 lense 5 24 3 228 tae 5 151 3 55 banana 2 5300 2 142 letter 16 20000 26 229 tamilnadu 3 45781 20 56 bank-marketing 16 45211 2 143 libras-move 90 360 15 230 texture 40 5000 11 57 banknote 4 1372 2 144 lung-cancer 56 32 3 231 thyroid 21 7200 3 58 biodeg 41 1055 2 145 lupus 3 87 2 232 thyroid-allbp 26 2800 5 59 blood-trans 4 748 2 146 lymphography 18 148 4 233 thyroid-allhyper 26 2800 5 60 breast-cancer 9 286 2 147 madelon 500 2600 2 234 tic-tac-toe 9 958 2 61 breast-cancer-w 9 699 2 148 magic 10 19020 2 235 titanic 3 2201 2 62 bupa 6 345 2 149 marketing 13 8993 9 236 toronto-apartment 6 1124 188 63 cacao 8 1795 42 150 mc1 38 9466 2 237 touch2 10 265 8 64 calendar-dow 32 399 5 151 meta-all 62 71 6 238 trains 32 10 2 65 car 6 1728 4 152 meta-stream 74 45164 13 239 twonorm 20 7400 2 66 car-evaluation 21 1728 4 153 mfeat-fac 216 2000 10 240 unix-user 2 9100 9 67 cardiotocograph 35 2126 3 154 mfeat-fou 76 2000 10 241 user-knowledge 5 403 5 68 castmetal1 37 327 2 155 mfeat-kar 64 2000 10 242 usps 256 9298 10 69 chess 36 3196 2 156 mfeat-mor 6 2000 10 243 vehicle 18 846 4 70 churn 20 5000 2 157 mfeat-pix 240 2000 10 244 vehicle-reproduced 18 846 4 71 clean2 165 6598 2 158 mfeat-zer 47 2000 10 245 volcanoes-a1 3 3252 4 72 cleveland 13 297 5 159 miceprotein 76 1080 8 246 volcanoes-d2 3 9172 4 73 click-prediction 9 39948 2 160 micro-a2 20 20000 5 247 volcanoes-e2 3 1080 4 74 climate-model 20 540 2 161 micro-mass 1300 571 20 248 vowel 13 990 11 75 cmc 9 1473 3 162 monks1-test 6 122 2 249 walking-activity 4 149332 22 76 cnae9 856 1080 9 163 monks1-train 6 124 2 250 waveform 21 5000 3 77 coil2000 85 9822 2 164 monks2-test 6 432 2 251 waveform-noise 40 5000 3 78 colleges-aaup 14 1161 4 165 monks2-train 6 169 2 252 wdbc 30 569 2 79 collins 19 1000 30 166 monks3-test 6 432 2 253 wifi-localization 7 2000 4 80 contraceptive 9 1473 3 167 monks3-train 6 122 2 254 wilt 5 4339 2 81 cpmp-2015 24 527 4 168 mozilla4 5 15545 2 255 wine 13 178 3 82 credit-card 23 30000 2 169 mushroom 22 8124 2 256 winequality-r 11 1599 10 83 crx 15 653 2 170 newthyroid 5 215 3 257 winequality-w 11 4898 10 84 cylinder-bands 19 539 2 171 nursery 8 12960 5 258 wpbc 32 198 2 85 dbworld-bodies 64 3721 2 172 obs-network 20 1075 4 259 yeast 8 1484 13 86 dermatology 34 366 6 173 oil-spill 49 937 2 260 zoo 16 101 7 87 diggle-table-a2 8 310 9 174 olivetti-faces 4096 400 40 3.1.2 元特征
通过元特征提取工具MFE[36]提取常用的150种分类数据集元特征，包括77种基于统计和信息论的元特征、24种基于决策树的元特征、14种基于基准的元特征和35种基于问题复杂度的元特征. 元特征信息如表3所示.
表 3 元特征信息Table 3. Information of Meta-Features元特征类型 元特征名称 基于统计和信
息论的元特征attr_conc.mean，attr_conc.sd，attr_ent.mean，attr_ent.sd，attr_to_inst，can_cor.mean，can_cor.sd，cat_to_num，class_conc.mean，class_conc.sd，class_ent，cor.mean，cor.sd，cov.mean，cov.sd，eigenvalues.mean，eigenvalues.sd，eq_num_attr，freq_class.mean，freq_class.sd，g_mean.mean，g_mean.sd，gravity，h_mean.mean，h_mean.sd，inst_to_attr，iq_range.mean，iq_range.sd，joint_ent.mean，joint_ent.sd，kurtosis.mean，kurtosis.sd，lh_trace，mad.mean，mad.sd，max.mean，max.sd，mean.mean，mean.sd，median.mean，median.sd，min.mean，min.sd，mut_inf.mean，mut_inf.sd，nr_attr，nr_bin，nr_cat，nr_class，nr_cor_attr，nr_disc，nr_inst，nr_norm，nr_num，nr_outliers，ns_ratio，num_to_cat，one_itemset.mean，one_itemset.sd，p_trace，range.mean，range.sd，roy_root，sd.mean，sd.sd，sd_ratio，skewness.mean，skewness.sd，sparsity.mean，sparsity.sd，t_mean.mean，t_mean.sd，two_itemset.mean，two_itemset.sd，var.mean，var.sd，w_lambda 基于决策树的
元特征leaves，leaves_branch.mean，leaves_branch.sd，leaves_corrob.mean，leaves_corrob.sd，leaves_homo.mean，leaves_homo.sd，leaves_per_class.mean，leaves_per_class.sd，nodes，nodes_per_attr，nodes_per_inst，nodes_per_level.mean，nodes_per_level.sd，nodes_repeated.mean，nodes_repeated.sd，tree_depth.mean，tree_depth.sd，tree_imbalance.mean，tree_imbalance.sd，tree_shape.mean，tree_shape.sd，var_importance.mean，var_importance.sd 基于基准的
元特征best_node.mean，best_node.sd，elite_nn.mean，elite_nn.sd，linear_discr.mean，linear_discr.sd，naive_bayes.mean，naive_bayes.sd，one_nn.mean，one_nn.sd，random_node.mean，random_node.sd，worst_node.mean，worst_node.sd 基于问题复杂
度的元特征c1，c2，cls_coef，density，f1.mean，f1.sd，f1v.mean，f1v.sd，f2.mean，f2.sd，f3.mean，f3.sd，f4.mean，f4.sd，hubs.mean，hubs.sd，l1.mean，l1.sd，l2.mean，l2.sd，l3.mean，l3.sd，lsc，n1，n2.mean，n2.sd，n3.mean，n3.sd，n4.mean，n4.sd，t1.mean，t1.sd，t2，t3，t4 3.1.3 候选算法
使用8种sklearn[37]机器学习平台的分类算法，包括kNN、RF、SVM、逻辑回归（logistic regression，LR）、朴素贝叶斯（naive Bayes，NB）、线性判别分析（linear discriminant analysis，LDA）、ID3决策树和多层感知机（multi-layer perceptron，MLP），以及基于Keras[38]构建的卷积神经网络（convolutional neural network，CNN）作为候选算法. 基于sklearn实现的算法均采用其默认参数设置，对于CNN，使用1个含有32个卷积核的1维卷积层、1个全连接层以及1个最大池化层构成其隐藏层，并设置其卷积层和全连接层使用ReLU（rectified linear unit）激活函数，输出层使用softmax激活函数.
3.1.4 候选算法性能测度
使用准确率（Acc）、查准率（Pre）、查全率（Rec）、F1得分（F1）和ARR（adjusted ratio of ratios）[39]指标测度并比较候选算法的性能. ARR指标综合考虑算法的运行时间和准确率，其计算如式（27）（28）所示：
AR{R_{{a_i},{a_j}}} = \frac{{{{Ac{c_{{a_i}}}} \mathord{\left/ {\vphantom {{Ac{c_{{a_i}}}} {Ac{c_{{a_j}}}}}} \right. } {Ac{c_{{a_j}}}}}}}{{1 + \alpha \times \lg \left( {{{R{t_{{a_i}}}} \mathord{\left/ {\vphantom {{R{t_{{a_i}}}} {R{t_{{a_j}}}}}} \right. } {R{t_{{a_j}}}}}} \right)}},1 \leqslant i \ne j \leqslant l \text{，} (27) AR{R_{{a_i}}} = \frac{{\displaystyle\sum_{j = 1 \wedge j \ne i}^l {AR{R_{{a_i},{a_j}}}} }}{{l - 1}},1 \leqslant i \ne j \leqslant l \text{.} (28) 其中ai和aj表示候选算法，l为候选算法数，Acc和Rt表示算法在数据集上的准确率和运行时间； \alpha 为可变参数，表示准确率和运行时间的相对重要程度. 实验中ARR的 \alpha 值取研究中常用的0.1，0.01，0.001，并各自记为ARR1，ARR2，ARR3指标，以获得较为全面的算法性能测度结果.
通过5次10折交叉验证获取候选算法在各数据集上的性能指标值，对指标值进行比较从而确定数据集的最优算法，将最优算法作为标签与元特征结合，构建相应性能指标的元数据集. 采用DAcc，DPre，DRec，DF1表示通过准确率、查准率、查全率和F1得分指标构建的元数据集；使用D_{AR{R_{{1}}}}，D_{ AR{R_{{2}}}}，D_{AR{R_{{3}}} }分别表示通过ARR1，ARR2，ARR3指标生成的元数据集. 此外，当应用基于回归的元算法时，为各候选算法构建单独的元数据集，其中的元实例标签为性能指标值，训练元算法预测各候选算法的性能指标值，比较预测值从而选出最优算法.
3.1.5 对比方法
采用kNN，SVM，CART，SVR，RF，RFR，XGB，LGBM作为元算法与SAMO进行对比实验. 研究表明kNN的距离度量采用欧氏距离，邻居数k值位于元数据集实例数的10%～15%之间时，其表现更好[9,40]. 经过对比择优，本文设置k=30，距离度量采用以距离倒数为权重的加权欧氏距离. 除kNN外，其他基分类器和元算法均采用sklearn中的默认参数设置.
通过5折交叉验证，即将元数据集随机划为5份，选择其中4份作为训练集，1份为测试集，计算各方法的性能指标值.
3.2 元数据集分析
对构建的7个元数据集进行分析，候选算法在各元数据集中的胜出次数如表4所示.
表 4 候选算法胜出次数Table 4. Win Times of the Candidate Algorithms候选算法 元数据集 D_{Acc} D_{Pre } D_{Rec } D_{F{\rm{1}} } D_{AR{R_{{1}}}} D_{AR{R_{ {2} } } } D_{AR{R_{ {3} } } } kNN 10 15 13 16 45 21 8 RF 106 100 84 94 10 66 98 SVM 37 28 20 21 21 32 32 LR 27 26 25 22 2 21 26 NB 11 13 21 13 51 17 14 LDA 20 24 26 25 66 40 22 ID3 21 27 38 38 65 46 34 MLP 23 18 23 24 0 14 21 CNN 5 9 10 7 0 3 5 注：黑体数值表示最多胜出次数. 从表4可以看出，在本文的测试环境中，RF具有较为优越的分类性能，但是其在 D_{AR{R_{{1}}}} 元数据集中的胜出次数较少，表明运行时间是其短板. 与RF相对的是kNN和NB，得益于算法较快的运行速度，kNN和NB在ARR指标上具备一定优势，但其分类性能较差，因此，随着α值的减小，运行时间的重要性降低，kNN和NB在ARR指标元数据集中的胜出次数减少. 相较于kNN和NB，LR的分类性能略优但时间开销更高，在7个指标上的表现较为平庸. SVM的分类性能较优且具有合适的时间开销，在7个指标上均取得了较好结果. LDA和ID3展现了较好的分类性能，另一方面，LDA和ID3在ARR指标的元数据集中也取得了较多次数的胜出，说明其在运行时间和准确率上较为均衡. MLP的分类性能具有一定优势，但其在各数据集上的运行时间较长，因此MLP在ARR指标的元数据集中取得的胜出次数较少. CNN的分类性能较弱且运行开销较高，在7个指标上的结果较差.
3.3 参数敏感性分析
为了确定合适的参数设置，本节设置种群规模N=50和最大迭代次数T=300，对方法的关键参数，即基分类器个数V和多样性指标DI进行敏感性分析.
为了便于说明，以DAcc元数据集为例，DI∈{QS, KS, CC, AM, DF}，V∈{10, 15, 20, 25, 30}，对方法独立运行20次的平均帕累托解数量和准确性精英蚁狮的ER平均值进行对比，结果分别如图9和图10所示.
![]()
图 9 不同多样性指标时的帕累托解数量Figure 9. Pareto solution numbers of different diversity indicators观察图9中的帕累托解数量，其在5种多样性指标上均呈现相同的变化趋势，即随着基分类器个数V的增加，帕累托解数量整体呈现出先增加后减少的趋势，当V=15时，SAMO在5种DI上的帕累托解数量相对较多. 另一方面，当使用QS，KS，CC指标时，SAMO产生的帕累托解数量较为接近，优于AM和DF指标上的结果.
分析图10结果可以发现，随着基分类器个数V的增加，SAMO的ER性能在5种多样性指标上均呈现出先降低后提升的趋势，当基分类器个数V=15时，5种指标上的ER值取得最优结果. 此外，当基分类器个数V相同时，5种指标上的ER性能较为接近，其中AM指标上的整体表现优于其他指标.
进一步分析图9和图10，随着V的增加，基分类器的多样性得到提升，集成的效果变好；而当V>15时，基分类器多样性的提升有限，却引入了部分准确性较差的基分类器，同时方法个体的搜索空间扩大，搜索效率降低，导致了方法性能的下降.
综合上述结果，为了获取具有较好算法选择性能的集成元算法，设置基分类器个数V=15较为合适，多样性指标DI宜使用AM指标.
3.4 优化算法效果验证
对本文所提多目标混合蚁狮优化算法、多目标蚁狮优化（multi-objective ALO，MALO）[41]、第2代非支配排序遗传算法（non-dominated sorting genetic algorithm 2，NSGA2）[42]、速度约束多目标粒子群优化（speed-constrained multi-objective particle swarm optimization，SMPSO）[43]以及第2代强度帕累托进化算法（strength Pareto evolutionary algorithm 2，SPEA2）[44]的优化性能进行比较，其中NSGA2，SMPSO，SPEA2基于框架jMetalPy[45]实现. 各对比算法均采用连续型编码，设置阈值为0.5对个体的元特征选择编码进行离散化. 具体而言，设Ai为个体的第i维元特征选择编码，当Ai≥0.5时表示第i个元特征被选择，Ai<0.5时表示未被选择；在个体的选择性集成编码部分设置与本文算法相同的编码和解码方式.
设置基分类器个数V=15，多样性指标DI为AM，算法种群规模N=50，最大迭代次数T=300，取算法独立运行20次的平均结果. 对算法准确性最优个体的ER值、多样性最优个体的DI值和帕累托解数量进行比较，结果如表5~7所示.
表 5 各算法错误率结果Table 5. Error Rate Results of the Algorithms% 元数据集 本文算法 MALO NSGA2 SMPSO SPEA2 DAcc 50.3 52.4 54.0 54.4 53.8 DPre 54.1 56.7 57.1 57.7 57.2 DRec 56.3 58.2 60.1 61.2 59.8 DF1 51.7 54.4 55.5 56.3 55.8 D_{AR{R_{ {1} } } } 51.6 54.3 57.8 59.2 58.9 D_{AR{R_{ {2} } } } 55.7 57.9 60.5 60.9 60.8 D_{AR{R_{ {3} } } } 50.9 52.2 53.9 54.2 53.8 注：黑体数值表示最优结果. 表 6 各算法多样性指标结果Table 6. Diversity Indicator Results of the Algorithms元数据集 本文算法 MALO NSGA2 SMPSO SPEA2 DAcc 0.561 0.590 0.654 0.64 0.651 DPre 0.592 0.628 0.668 0.665 0.662 DRec 0.560 0.601 0.636 0.631 0.639 DF1 0.549 0.582 0.634 0.627 0.637 D_{AR{R_{ {1} } } } 0.501 0.521 0.587 0.584 0.579 D_{AR{R_{ {2} } } } 0.568 0.601 0.646 0.646 0.657 D_{AR{R_{ {3} } } } 0.561 0.598 0.647 0.642 0.638 注：黑体数值表示最优结果. 表 7 各算法帕累托解数量结果Table 7. Pareto Solution Number Results of the Algorithms元数据集 本文算法 MALO NSGA2 SMPSO SPEA2 DAcc 12.6 5.9 6.2 7.2 6.6 DPre 9.3 5.5 5.8 7.2 5.8 DRec 10.4 5.4 6.1 5.9 6.2 DF1 12.2 5.6 6.1 5.9 5.7 D_{AR{R_{ {1} } } } 9.0 5.2 4.9 5.1 4.8 D_{AR{R_{ {2} } } } 10.2 5.7 5.5 6.0 5.1 D_{AR{R_{ {3} } } } 11.0 6.0 6.6 6.8 6.3 注：黑体数值表示最优结果. 从表5和表6可以看出，本文算法的准确性最优个体和多样性最优个体分别可以取得最低的ER值和DI值，说明其寻优性能优于其他对比算法. 对比MALO，NSGA2，SMPSO，SPEA2的结果，不难发现MALO的性能优于另外3种算法.
表7中，本文算法可以产生较多的帕累托解数量，而其他算法的帕累托解数量较之有明显的差距，进一步验证了本文算法具有较强的寻优性能.
使用非支配比率（non-dominance ratio，NR）[46]、超体积（hyper volume，HV）[47]和空间指标（spacing，SP）[48]，对各算法的解集质量进行评估. NR将不同算法产生的多个解集合并为1个解集并从中筛选出帕累托解构成解集Sm，然后计算某一个解集中的解在Sm中所占的比例，比值越大说明该解集的质量较之其他解集的质量越优. HV计算解集与目标空间中的最差点所构成空间的面积，ER和DI最差的指标值均为1，因此最差点为（1,1），HV值越大表示解集质量越好. SP计算解集中相距最近的2个解距离的标准差，其值越小代表解的分布性越好. 各算法在NR，HV，SP上的比较结果如表8~10所示.
表 8 各算法NR结果Table 8. NR Results of the Algorithms元数据集 本文算法 MALO NSGA2 SMPSO SPEA2 DAcc 0.743 0.252 0 0.010 0 DPre 0.834 0.166 0 0 0 DRec 0.713 0.297 0 0 0 DF1 0.778 0.225 0 0 0 D_{AR{R_{ {1} } } } 0.711 0.289 0 0 0 D_{AR{R_{ {2} } } } 0.764 0.229 0.010 0 0 D_{AR{R_{ {3} } } } 0.757 0.229 0.010 0 0 注：黑体数值表示最优结果. 表 9 各算法HV结果Table 9. HV Results of the Algorithms元数据集 本文算法 MALO NSGA2 SMPSO SPEA2 DAcc 0.209 0.190 0.157 0.160 0.158 DPre 0.181 0.158 0.140 0.139 0.142 DRec 0.184 0.164 0.141 0.139 0.141 DF1 0.208 0.186 0.159 0.158 0.157 D_{AR{R_{ {1} } } } 0.235 0.215 0.171 0.167 0.170 D_{AR{R_{ {2} } } } 0.184 0.164 0.137 0.135 0.132 D_{AR{R_{ {3} } } } 0.206 0.186 0.159 0.160 0.162 注：黑体数值表示最优结果. 表 10 各算法SP结果Table 10. SP Results of the Algorithms元数据集 本文算法 MALO NSGA2 SMPSO SPEA2 DAcc 0.013 0.019 0.017 0.024 0.021 DPre 0.018 0.014 0.020 0.016 0.018 DRec 0.012 0.011 0.019 0.018 0.014 DF1 0.013 0.021 0.015 0.016 0.022 D_{AR{R_{ {1} } } } 0.015 0.016 0.017 0.017 0.022 D_{AR{R_{ {2} } } } 0.013 0.011 0.018 0.014 0.018 D_{AR{R_{ {3} } } } 0.016 0.023 0.019 0.017 0.018 注：黑体数值表示最优结果. 对比表8中的NR结果，相较于其他算法，本文算法有明显的优势，展现了更强的收敛性. MALO可以搜索到本文算法所未能发现的帕累托解，具备一定的寻优性能. NSGA2，SMPSO，SPEA2在NR上的表现较差.
分析表9，所提算法在各元数据集上取得了最大的HV值，表明算法产生的解在目标空间中距离最差点较远，解集的质量高于其他算法. MALO在个别元数据集上可以取得与本文算法相近的HV值，其性能优于NSGA2，SMPSO，SPEA2.
表10的结果显示5种算法在不同元数据集上具有较优的SP值，其中本文算法和MALO分别在部分元数据集上都取得了最优结果，NSGA2，SMPSO，SPEA2的结果较为接近. 结合帕累托解数量结果，本文算法产生较多的帕累托解，同时可以保持较好的分布性.
综合上述分析，在对算法选择模型进行优化时，相较于其他4种算法，本文算法可以在2个优化目标上搜索到更优解，并且可以发现数量更多且质量更高的帕累托解，在收敛性和分布性上有较大的优势，说明本文算法在寻优性能上具备优越性.
3.5 SAMO实验结果
采用与3.4节相同的方法参数设置，取SAMO运行20次所得的准确性精英蚁狮的性能均值进行对比，各方法的ER比较结果如表11所示.
表 11 各方法ER结果Table 11. ER Results of the Methods% 方法 元数据集 排名 D_{Acc } D_{Pre} D_{Rec} D_{F{\rm{1} } } D_{AR{R_{ {1} } } } D_{AR{R_{ {2} } } } D_{AR{R_{ {3} } } } SAMO 50.3 54.1 56.3 51.7 51.6 55.7 50.9 1 kNN 59.2 66.5 68.5 63.8 74.6 73.5 59.6 7 SVM 59.6 61.9 66.9 63.1 78.1 75.4 63.1 8 CART 69.6 71.9 76.2 69.6 64.6 73.1 69.2 9 SVR 59.2 61.5 67.3 63.8 75.0 75.0 62.7 6 RF 55.8 55.4 58.8 54.2 54.2 57.7 54.6 2 RFR 60.0 62.3 63.8 60.8 66.5 71.2 66.9 5 XGB 59.6 57.7 56.9 54.2 54.2 58.1 56.5 4 LGBM 57.7 53.8 60 55.8 53.5 58.8 56.5 3 注：黑体数值表示最优结果. 对表11进行分析，可以看出SAMO在各元数据集上有更优越的性能，其在除DPre外的其他元数据集上均取得了最好结果. kNN，SVM，CART的性能较弱，SAMO的性能明显优于这3种元算法. SVR预测各候选算法的性能指标值，比较预测值并选择最优算法，计算开销较高，且其在ER指标上不具备性能优势. 在集成方法中，除SAMO外，RF具有较好的性能，在各元数据集上均有较好的表现；RFR结合集成和回归方法，预测算法的性能指标值，其性能优于SVR但明显劣于其他集成方法；XGB在DRec元数据集上的性能强于RF，但是方法的整体性能不如RF；LGBM的整体表现并不突出，但其在DPre元数据集上取得了最优结果. 将SAMO与平均性能排名第2的RF进行比较，SAMO有着2.9%的平均性能领先，证明了SAMO在ER指标上的优越性.
进一步使用查准率、查全率和F1得分指标比较方法性能，结果如表12~14所示.
表 12 各方法查准率结果Table 12. Precision Results of the Methods% 方法 元数据集 排名 D_{Acc } D_{Pre} D_{Rec} D_{F{\rm{1}} } D_{AR{R_{ {1} } } } D_{AR{R_{ {2} } } } D_{AR{R_{ {3} } } } SAMO 35.7 35.9 38.5 37.7 38.6 32.8 32.8 1 kNN 16.1 14.2 18.6 21.3 17.4 16.7 18.3 7 SVM 5.0 4.4 7.0 7.5 5.1 2.9 4.4 8 CART 19.9 18.0 17.3 19.7 30.1 21.4 22.3 6 SVR 5.0 4.4 4.7 5.3 7.3 3.0 4.4 9 RF 27.1 42.4 35.9 36.1 34.8 28.8 29.5 2 RFR 27.9 21.0 25.7 23.6 22.9 15.9 12.7 5 XGB 26.7 26.6 40.6 36.3 36.2 30.2 31.1 4 LGBM 27.7 37.3 36.9 37.3 38.1 27.0 29.1 3 注：黑体数值表示最优结果. 表 13 各方法查全率结果Table 13. Recall Results of the Methods% 方法 元数据集 排名 D_{Acc } D_{Pre} D_{Rec} D_{F{\rm{1} } } D_{AR{R_{ {1} } } } D_{AR{R_{ {2} } } } D_{AR{R_{ {3} } } } SAMO 28.0 29.7 30.9 31.6 38.9 31.2 27.4 1 kNN 18.8 16.1 17.8 18.9 17.7 17.0 20.8 7 SVM 11.9 11.3 11.9 12.1 15.8 11.3 11.4 8 CART 19.9 20.6 20.5 26.1 31.2 23.1 22.2 6 SVR 12.0 11.4 11.4 11.6 15.8 11.5 11.6 9 RF 22.8 28.9 31.2 29.4 33.4 28.7 25.7 4 RFR 29.4 25.7 25.7 26.5 24.9 17.7 13.9 5 XGB 23.7 27.4 36.3 34.0 34.7 31.2 27.0 2 LGBM 24.4 31.9 31.6 30.6 34.8 29.2 25.9 3 注：黑体数值表示最优结果. 表 14 各方法F1得分结果Table 14. F1 Score Results of the Methods% 方法 元数据集 排名 D_{Acc } D_{Pre} D_{Rec} D_{F{\rm{1} } } D_{AR{R_{ {1} } } } D_{AR{R_{ {2} } } } D_{AR{R_{ {3} } } } SAMO 28.0 28.8 29.5 30.4 36.6 29.5 26.4 1 kNN 16.3 13.8 15.0 16.5 16.4 15.0 18.4 7 SVM 7.0 6.2 6.7 7.2 6.1 4.6 6.3 8 CART 18.7 17.8 17.2 20.7 27.9 21.1 20.6 5 SVR 7.0 6.3 5.9 6.4 6.9 4.7 6.4 9 RF 22.5 30 29.6 27.5 32.1 26.5 24.5 4 RFR 25.0 20.9 22.7 22.1 22.0 14.8 11.5 6 XGB 23.3 25.4 34.8 31.6 33.1 29.3 26.6 2 LGBM 24.4 30.7 30.8 29.9 33.6 27.0 25.4 3 注：黑体数值表示最优结果. 分析表12查准率结果，SAMO在5个元数据集上均获得了最好性能. kNN和CART在查准率指标上的表现明显优于SVM和SVR. 在除SAMO外的集成方法中，RFR的性能不如其他方法. RF，XGB，LGBM的性能较优，其中RF在DPre元数据集上表现突出，XGB在DRec元数据集上具有优越性能. SAMO相较于kNN，SVM，CART，SVR有较大程度的性能优势，其与RF相比平均性能提升了2.5%，表明SAMO在查准率指标上具有优越性.
表13中，SAMO在ARR指标的元数据集上取得了较好的查全率结果. CART的查全率性能优于kNN和SVM，SVR的性能表现稍劣于SVM. RFR的性能优于CART，在DAcc上具有优异表现，但是在其他元数据集上的表现一般. RF，XGB，LGBM的查全率性能较好，其中XGB在DRec，DF1， D_{AR{R_{ {2} } } } 元数据集上以及LGBM在DPre元数据集上表现优异. SAMO的性能相较于RF平均领先了2.5%，相较于XGB平均领先了0.5%，说明SAMO在查全率指标上具备一定的有效性.
从表14可以看出，SAMO在各元数据集上的F1得分性能较好，在部分元数据集上取得了最好的结果. 在kNN，SVM，CART中，CART的性能优于kNN和SVM. SVR与SVM的性能较为接近，与其他方法的差距较大. RFR的性能稍劣于CART，表现较为一般. RF，XGB，LGBM具有较好的F1得分性能，其中XGB和LGBM分别在不同元数据集上表现突出. SAMO的F1得分优于kNN，SVM，CART，另一方面，其相较于RF性能平均提升了2.4%，与XGB相比则性能平均提升了0.8%，验证了SAMO在F1得分指标上的有效性.
将SAMO与RF，RFR，XGB，LGBM这4种集成方法进行对比，SAMO使用3种基分类器进行选择性集成，而其他方法仅使用CART基学习器进行集成，SAMO生成的集成元算法具有更强的多样性. 另一方面，在实验测试中，SAMO构建的集成元算法在DAcc，DPre，DRec，DF1， D_{AR{R_{ {1} } } } ， D_{AR{R_{ {2} } } } ， D_{AR{R_{ {3} } } } 上平均集成的基分类器数量分别为7.7，6.5，6.7，7.2，5.5，7.1，7.8，而其他方法固定使用100个基学习器进行集成，由此可见SAMO通过选择性集成有效减少了基学习器的数量，从而降低集成元算法的存储和运行开销.
综上所述，SAMO选择具有互补性的元特征子集，并使用不同类型的基分类器进行选择性集成，生成具有较好算法选择性能和多样性的集成元算法. 其在测试指标上的性能均明显优于kNN，SVM，CART，SVR方法，而与RF，XGB等采用同构基学习器的集成方法相比，也具有相对优越的性能表现，证明了SAMO的有效性和优越性.
4. 结 论
为了提升基于元学习的算法选择性能，提出基于多目标混合蚁狮优化的算法选择方法SAMO. 设计算法选择模型，引入元特征选择和选择性集成，同时寻找互补性较强的元特征子集和对多种元算法进行选择性集成；提出多目标混合蚁狮优化算法求解模型，使用混合编码机制选择元特征并构建集成元算法，采用增强游走策略和偏好精英选择机制提高寻优性能. 构建分类算法选择问题进行实验测试，将SAMO与8种典型的元算法进行对比，结果显示SAMO具有优异的算法选择性能，明显优于kNN，SVM，CART，SVR元算法，较之RF，RFR，XGB，LGBM这4种集成元算法也有一定优势，并且具备更强的多样性，综合体现了SAMO的有效性和优越性.
未来的工作包括3个方面：
1）由于算法选择相关因素较多，问题较为复杂，因此目前本文所提方法SAMO的效果有限，后续将深入研究数据集、元特征和元算法的内在关系，对SAMO进行改进，显著提升算法选择性能.
2）本文方法的时间复杂度较高，未来将通过并行计算、迁移学习等手段降低方法的训练开销.
3）将SAMO拓展应用于实际工程，构建算法选择系统.
作者贡献声明：李庚松提出方法设计，负责实验方案的实现和论文内容的撰写；刘艺提出研究问题，梳理论文结构；郑奇斌整理论文内容，负责实验数据集的收集和处理；李翔参与方法的实验结果分析；刘坤提出方法思路的改进建议；秦伟提出论文修改和优化建议；王强负责实验方案的实现指导；杨长虹给出完善论文整体框架的建议.
-
![]()
图 3 模型训练和推理阶段用以获得能耗、时延和推理准确率
Figure 3. Model training and inference stages used for obtaining energy, latency and accuracy
![]()
图 4 RR-SC搜索到的模型架构和SC算术电路可视化
Figure 4. Visualization of the model architecture and SC arithmetic circuit searched by RR-SC
表 1 Odroid-XU3 移动平台中 ARM Cortex A7 内核支持的电压/频率等级
Table 1 V/F Levels Supported by ARM Cortex A7 Core in Odroid-XU3 Mobile Platform
等级 频率/MHz 电压/mV l1 400 916.25 l2 600 917.5 l3 800 992.5 l4 1000 1066.25 l5 1200 1141.25 l6 1400 1240 
下载: 导出CSV
表 2 时间约束 45 ms下的3种实验设置运行结果对比
Table 2 Running Results Comparison of Three Experimental Settings with the Time Constraint of 45 ms
设置 模型 数据精度 准确率/% DVFS 推理时间/ms TC Satisfy 能耗/mJ 推理次数 提升 S1 M1 32 95.4 F 32.7 \surd 298.1 2.0 \times 105 - S2 M1 F 32.7 \surd 298.1 1.0 \times 105 32 95.4 N 45.8 \times 230.2 7.8 \times 104 1.4倍 E 57.2 \times 124.1 9.7 \times 104 S3 M1 32 95.4 F 32.7 \surd 298.1 1.0 \times 105 M2 16 88.1 N 28.9 \surd 142.1 1.3 \times 105 2.3倍 M3 8 62.2 E 23.8 \surd 51.8 2.3 \times 105 注：实验设置S1表示没有任何运行时重配置，S2表示仅具有硬件重配置，S3表示同时具有软件和硬件重配置；“-”表示性能比较基准.
下载: 导出CSV
表 3 RL控制器的状态空间
Table 3 State Space of RL Controller
状态 描述 Acc 基于SC的DNN在相应动作下的推理准确率 Runs 基于SC的DNN在给定能源总量
及相应V/F设置下的推理总次数
下载: 导出CSV
表 4 MLP，LeNet，AlexNet的具体搜索空间设置
Table 4 Specific Search Space Settings of MLP, LeNet and AlexNet
模型 搜索空间 设置 MLP 层数 1, 2, 3 每层神经元数 32, 64, 100, 128, 200, 256, 400, 512, 1024 SC算术电路库 XNOR-MUX, AND-SEP, uGEMM, AND-ACC, AND-LOOP 数据精度 4, 8, 16, 32, 64, 128 配置组合数 241920 LeNet 卷积层、池化层步长 1, 2 卷积核大小 3, 5, 7 池化层核大小 1, 2 卷积层输出通道数 6, 16, 32, 64 全连接层神经元数 32, 64, 100, 128, 200, 256, 400, 512, 1024 SC算术电路库 XNOR-MUX, AND-SEP, uGEMM, AND-ACC, AND-LOOP 数据精度 4, 8, 16, 32, 64, 128 配置组合数 940584960 AlexNet 卷积层、池化层步长 1, 2 卷积核大小 3, 5, 7 池化层核大小 1, 2 卷积层输出通道数 6, 16, 32, 64, 256 全连接层神经元数 32, 64, 100, 128, 200, 256, 400, 512, 1024 SC算术电路库 XNOR-MUX, AND-SEP, uGEMM, AND-ACC, AND-LOOP 数据精度 4, 8, 16, 32, 64, 128 配置组合数 30233088000000
下载: 导出CSV
表 5 MLP上SC相关工作和RR-SC在时间约束为95 ms时的比较结果
Table 5 Comparative Results of SC Relative Work and RR-SC with the Time Constraint 95 ms on MLP
方法 算术电路 数据精度 准确率/% 推理时间/ms TC Satisfy 能耗/mJ 推理次数 提升倍数（本文方法/该方法） 文献[13] XNOR-MUX 64 12.8 627.1 \times 2527.3 23741 3.9倍 文献[14] AND-SEP 64 25.5 94.7 \surd 762.6 78678 1.2倍 文献[15] uGEMM 64 64.8 430.5 \times 3378.3 17760 5.2倍 文献[16] AND-ACC 64 94.6 93.3 \surd 818.9 73269 1.3倍 文献[16] AND-LOOP 64 97.8 90.7 \surd 1306.7 45917 2.0倍 RR-SC（本文） AND-LOOP 64 97.8 90.7 \surd 1306.7 22959 32 96.3 73.22 \surd 582.3 30912 32 96.3 91.5 \surd 313.8 38241
下载: 导出CSV
表 6 MLP上SC相关工作和RR-SC在时间约束为120 ms时的比较结果
Table 6 Comparative Results of SC Relative Work and RR-SC with the Time Constraint 120 ms on MLP
方法 算术电路 数据精度 准确率/% 推理时间/ms TC Satisfy 能耗/mJ 推理次数 提升倍数（本文方法/该方法） 文献[13] XNOR-MUX 128 20.8 649.3 \times 2606.1 23023 4.3倍 文献[14] AND-SEP 128 59.2 123.9 \times 954.2 62880 1.6倍 文献[15] uGEMM 128 84.3 589.8 \times 4623.1 12978 7.6倍 文献[16] AND-ACC 128 94.3 121.9 \times 1072.3 55954 1.8倍 文献[16] AND-LOOP 128 98.3 118.2 \surd 1682.1 35670 2.8倍 RR-SC（本文） AND-LOOP 128 98.3 118.2 \surd 1682.1 17835 64 96.4 88.6 \surd 695.3 25888 32 95.6 63.9 \surd 216.3 55478
下载: 导出CSV
表 7 LeNet上SC相关工作和RR-SC在时间约束为540 ms时的比较结果
Table 7 Comparative Results of SC Relative Work and RR-SC with the Time Constraint 540 ms on LeNet
方法 算术电路 数据精度 准确率/% 推理时间/ms TC Satisfy 能耗/mJ 推理次数 提升倍数（本文方法/该方法） 文献[13] XNOR-MUX 64 10.8 3675.9 \times 1845.5 32512 1.4倍 文献[14] AND-SEP 64 56.3 555.2 \times 1538.6 38996 1.2倍 文献[15] uGEMM 64 66.3 2523.2 \times 2720.9 22051 2.1倍 文献[16] AND-ACC 64 95.1 547.0 \times 1637.9 36632 1.2倍 文献[16] AND-LOOP 64 97.6 531.5 \surd 2129.5 28175 1.6倍 RR-SC（本文） AND-LOOP 64 97.6 531.5 \surd 2129.5 14088 32 95.8 429.5 \surd 1275.3 14114 32 95.8 536.9 \surd 687.4 17457
下载: 导出CSV
表 8 LeNet上SC相关工作和RR-SC在时间约束为2700 ms时的比较结果
Table 8 Comparative Results of SC Relative Work and RR-SC with the Time Constraint 2700 ms on LeNet
方法 算术电路 数据精度 准确率/% 推理时间/ms TC Satisfy 能耗/mJ 推理次数 提升倍数（本文方法/该方法） 文献[13] XNOR-MUX 128 19.5 14320.7 \times 2961.9 20257 2.1倍 文献[14] AND-SEP 128 62.5 2621.5 \surd 2550.4 23525 1.8倍 文献[15] uGEMM 128 74.3 13008.4 \times 6244.0 9609 4.4倍 文献[16] AND-ACC 128 96.8 2687.9 \surd 2635.8 22763 1.8倍 文献[16] AND-LOOP 128 97.2 2607.6 \surd 4432.9 13535 3.1倍 RR-SC（本文） AND-ACC 128 96.8 2687.9 \surd 2635.8 11381 32 95.7 1147.4 \surd 1321.8 13617 32 95.7 1434.3 \surd 712.4 16844
下载: 导出CSV
表 9 AlexNet上SC相关工作和RR-SC在时间约束为21000 ms时的比较结果
Table 9 Comparative Results of SC Relative Work and RR-SC with the Time Constraint 21000 ms on AlexNet
方法 算术电路 数据精度 准确率/% 推理时间/ms TC Satisfy 能耗/mJ 推理次数 提升倍数（本文方法/该方法） 文献[13] XNOR-MUX 64 9.8 138038.7 \times 899459.9 66 3.6倍 文献[14] AND-SEP 64 48.2 20850.7 \surd 285989.9 209 1.1倍 文献[15] uGEMM 64 60.2 94754.1 \times 1237486.5 48 4.9倍 文献[16] AND-ACC 64 89.8 20542.9 \surd 310091.0 193 1.2倍 文献[16] AND-LOOP 64 90.1 19960.4 \surd 500412.8 119 2.0倍 RR-SC（本文） AND-LOOP 64 90.1 19960.4 \surd 500412.8 59 32 87.6 16131.8 \surd 223012.7 80 32 87.6 20164.7 \surd 120201.5 99
下载: 导出CSV
表 10 AlexNet上SC相关工作和RR-SC在时间约束为125000 ms时的比较结果
Table 10 Comparative Results of SC Relative Work and RR-SC with the Time Constraint 125000 ms on AlexNet
方法 算术电路 数据精度 准确率/% 推理时间/ms TC Satisfy 能耗/mJ 推理次数 提升倍数（本文方法/该方法） 文献[13] XNOR-MUX 128 13.6 682697.7 \times 6059624.1 9 4.0倍 文献[14] AND-SEP 128 57.4 124975.3 \surd 2317931.8 25 1.5倍 文献[15] uGEMM 128 70.3 620135.8 \times 11001805.0 5 7.3倍 文献[16] AND-ACC 128 90.0 128138.5 \times 2631405.5 22 1.7倍 文献[16] AND-LOOP 128 91.3 124310.2 \surd 4202999.0 14 2.8倍 RR-SC（本文） AND-LOOP 128 91.3 124310.2 \surd 4202999.0 7 64 91.1 93190.2 \surd 1737447.2 10 32 88.7 67245.5 \surd 540599.9 22
下载: 导出CSV
表 11 MLP模型上搭配/不搭配软硬件重配置方法的实验结果
Table 11 Experimental Results of Methods with/Without Hardware and Software Reconfiguration on MLP
方法 数据精度 准确率/% 推理时间/ms TC Satisfy 能耗/mJ 推理次数 提升倍数（本文方法/该方法） 文献[16] 64 97.8 90.7 \surd 1306.7 45917 2.0倍 HW 64 97.8 90.7 \surd 1306.7 22959 1.5倍 127.0 \times 1008.8 17842 158.7 \times 543.7 22070 SW 64 97.8 90.7 \surd 1306.7 22959 1.5倍 32 96.3 52.3 \surd 754.3 23863 32 96.3 52.3 \surd 754.3 15908 RR-SC（本文） 64 97.8 90.7 \surd 1306.7 22959 32 96.3 73.22 \surd 582.3 30912 32 96.3 91.5 \surd 313.8 38241
下载: 导出CSV
表 12 LeNet上搭配/不搭配软硬件重配置方法的实验结果
Table 12 Experimental Results of Methods with/Without Hardware and Software Reconfiguration on LeNet
方法 数据精度 准确率/% 推理时间/ms TC Satisfy 能耗/mJ 推理次数 提升倍数（本文方法/该方法） 文献[16] 64 97.6 531.5 \surd 2129.5 28175 1.6倍 HW 64 97.6 531.5 \surd 2129.5 14088 1.2倍 744.1 \times 1644.0 10948 930.1 \times 886.1 13542 SW 64 97.6 531.5 \surd 2129.5 14088 1.4倍 32 95.8 306.8 \surd 1651.9 10896 32 95.8 306.8 \surd 1651.9 7264 RR-SC（本文） 64 97.6 531.5 \surd 2129.5 14088 32 95.8 429.5 \surd 1275.3 14114 32 95.8 536.9 \surd 687.4 17457
下载: 导出CSV
表 13 AlexNet上搭配/不搭配软硬件重配置方法的实验结果
Table 13 Experimental Results of Methods with/Without Hardware and Software Reconfiguration on AlexNet
设置 数据精度 准确率/% 推理时间/ms TC Satisfy 能耗/mJ 推理次数 提升倍数（本文方法/该方法） 文献[16] 64 90.1 19960.4 \surd 500412.8 119 2.0倍 HW 64 90.1 19960.4 \surd 500412.8 59 1.5倍 27944.6 \times 386318.7 46 34930.7 \times 208221.8 57 SW 64 90.1 19960.4 \surd 500412.8 59 1.5倍 32 87.6 19960.4 \surd 288876.6 62 32 87.6 19960.4 \surd 288876.6 41 RR-SC（本文） 64 90.1 19960.4 \surd 500412.8 59 32 87.6 16131.8 \surd 223012.7 80 32 87.6 20164.7 \surd 120102.5 99
下载: 导出CSV
-
[1] Garvey C. A framework for evaluating barriers to the democratization of artificial intelligence [C] //Proc of the 32nd AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2018: 8079−8080
[2] Wang Hanrui, Wu Zhanghao, Liu Zhijian, et al. Hat: Hardware-aware transformers for efficient natural language processing [C] //Proc of the 58th Annual Meeting of the Association for Computational Linguistics. Stroudsburg, PA: ACL, 2020: 7675−7688
[3] Song Yuhong, Jiang Weiwen, Li Bingbing, et al. Dancing along battery: Enabling transformer with run-time reconfigurability on mobile devices [C] // Proc of the 58th Design Automation Conf. Piscataway, NJ: IEEE, 2021: 1003−1008
[4] Jiang Weiwen, Yang Lei, Dasgupta S. , et al. Standing on the shoulders of giants: Hardware and neural architecture co-search with hot start[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(11): 4154−4165 doi: 10.1109/TCAD.2020.3012863
[5] Peng Hongwu, Huang Shaoyi, Geng Tong, et al. Accelerating transformer-based deep learning models on FPGAs using column balanced block pruning [C] //Proc of the 22nd Int Symp on Quality Electronic Design (ISQED). Piscataway, NJ: IEEE, 2021: 142−148
[6] 纪荣嵘,林绍辉,晁飞,等. 深度神经网络压缩与加速综述[J]. 计算机研究与发展,2018,55(9):1871−1888 Ji Rongrong, Lin Shaohui, Chao Fei, et al. Deep neural network compression and acceleration: A review[J]. Journal of Computer Research and Development, 2018, 55(9): 1871−1888 (in Chinese)
[7] 龚成,卢冶,代素蓉,等. 一种超低损失的深度神经网络量化压缩方法[J]. 软件学报,2021,32(8):2391−2407 Gong Cheng, Lu Zhi, Dai Surong, et al. Ultra-low loss quantization method for deep neural network compression[J]. Journal of Software, 2021, 32(8): 2391−2407 (in Chinese)
[8] 孟子尧,谷雪,梁艳春,等. 深度神经架构搜索综述[J]. 计算机研究与发展,2021,58(1):22−33 Meng Ziyao, Gu Xue, Liang Yanchun, et al. Deep neural architecture search: A survey[J]. Journal of Computer Research and Development, 2021, 58(1): 22−33 (in Chinese)
[9] 李航宇,王楠楠,朱明瑞,等. 神经结构搜索的研究进展综述[J]. 软件学报,2022,33(1):129−149 Li Hangyu, Wang Nannan, Zhu Mingrui, et al. Recent advances in neural architecture search: A survey[J]. Journal of Software, 2022, 33(1): 129−149 (in Chinese)
[10] Gaines B R. Stochastic computing systems [G/OL] // Advances in Information Systems Science. Berlin: Springer, 1969 [2022-11-24]. https://link.springer.com/chapter/10.1007/978-1-4899-5841-9_2
[11] Jeavons P, Cohen D A, Shawe-Taylor J. Generating binary sequences for stochastic computing[J]. IEEE Transactions on Information Theory, 1994, 40(3): 716−720 doi: 10.1109/18.335883
[12] Qian Weikang, Li Xin, Riedel M D, et al. An architecture for fault-tolerant computation with stochastic logic[J]. IEEE Transactions on Computers, 2010, 60(1): 93−105
[13] Li Peng, Lilja D J, Qian Weikang, et al. Computation on stochastic bit streams digital image processing case studies[J]. IEEE Transactions on Very Large Scale Integration Systems, 2013, 22(3): 449−462
[14] Li Bingzhe, Qin Yaobin, Yuan Bo, et al. Neural network classifiers using stochastic computing with a hardware-oriented approximate activation function [C] //Proc of the 35th IEEE Int Conf on Computer Design (ICCD). Los Alamitos, CA: IEEE Computer Society, 2017: 97−104
[15] Wu Di, Li Jingjie, Yin Ruokai, et al. Ugemm: Unary computing architecture for gemm applications [C] //Proc of the 47th ACM/IEEE Annual Int Symp on Computer Architecture (ISCA). Piscataway, NJ: IEEE, 2020: 377−390
[16] Song Yuhong, Sha E H, Zhuge Qingfeng, et al. Bsc: Block-based stochastic computing to enable accurate and efficient TinyML [C] // Proc of the 27th Asia and South Pacific Design Automation Conf (ASP-DAC). Piscataway, NJ: IEEE, 2022: 314−319
[17] Kim K, Kim J, Yu J, et al. Dynamic energy-accuracy trade-off using stochastic computing in deep neural networks [C] // Proc of the 53rd Annual Design Automation Conf (DAC). New York: ACM, 2016: 124: 1−124: 6
[18] Sim H, Kenzhegulov S, Lee J. DPS: Dynamic precision scaling for stochastic computing-based deep neural networks [C] //Proc of the 55th Annual Design Automation Conf (DAC). New York: ACM, 2018: 13: 1−13: 6
[19] 刘全,翟建伟,章宗长,等. 深度强化学习综述[J]. 计算机学报,2018,41(1):1−27 Liu Quan, Zhai Jianwei, Zhang Zongzhang, et al. A survey on deep reinforcement learning[J]. Chinese Journal of Computers, 2018, 41(1): 1−27 (in Chinese)
[20] 余显,李振宇,孙胜,等. 基于深度强化学习的自适应虚拟机整合方法[J]. 计算机研究与发展,2021,58(12):2783−2797 Yu Xian, Li Zhenyu, Sun Sheng, et al. Adaptive virtual machine consolidation method based on deep reinforcement learning[J]. Journal of Computer Research and Development, 2021, 58(12): 2783−2797 (in Chinese)
[21] Sim H, Lee J. A new stochastic computing multiplier with application to deep convolutional neural networks [C] //Proc of the 54th Annual Design Automation Conf (DAC). New York: ACM, 2017: 29: 1−29: 6
[22] Tomic T, Schmid K, Lutz P, et al. Toward a fully autonomous UAV: Research platform for indoor and outdoor urban search and rescue[J]. IEEE Robotics & Automation Magazine, 2012, 19(3): 46−56
[23] Horowitz M, Indermaur T, Gonzalez R. Low-power digital design [C] // Proc of 1994 IEEE Symp on Low Power Electronics. Piscataway, NJ: IEEE, 1994: 8−11
[24] Jiang Weiwen, Zhang Xinyi, Sha E H, et al. Accuracy vs. Efficiency: Achieving both through FPGA-implementation aware neural architecture search [C/OL] // Proc of the 56th Annual Design Automation Conf (DAC). New York: ACM, 2019[2022-11-24].https://dl.acm.org/doi/abs/10.1145/3316781.3317757
[25] Williams R J. Simple statistical gradient-following algorithms for connectionist reinforcement learning[J]. Machine Learning, 1992, 8(3): 229−256
[26] Dong Xuanyi, Yang Yi. Nas-bench-201: Extending the scope of re-producible neural architecture search [C/OL] // Proc of the 8th Int Conf on Learning Representations (ICLR). 2020[2022-11-24].https://openreview.net/forum?id=HJxyZkBKDr
[27] Skadron K, Stan M, Huang Wei, et al. Temperature-aware microarchitecture [C] // Proc of the 30th Int Symp on Computer Architecture (ISCA). Los Alamitos, CA: IEEE Computer Society, 2003: 2−13
[28] Google. Odroid-XU3 [EB/OL]. 2020[2022-11-24].https://www.hardkernel.com/shop/odroid-xu3/, 2020.
[29] Liu Siting, Han jie. Energy efficient stochastic computing with sobol sequences [C] // Proc of the 20th Design, Automation & Test in Europe Conf & Exhibition (DATE). Piscataway, NJ: IEEE, 2017: 650−653
[30] Najafi M H, Lilja D J, Riedel M. Deterministic methods for stochastic computing using low-discrepancy sequences [C/OL] // Proc of the 37th IEEE/ACM Int Conf on Computer-Aided Design (ICCAD). New York: ACM, 2018[2022-11-24].https://dl.acm.org/doi/abs/10.1145/3240765.3240797
-
期刊类型引用(4)
1. 马良玉，程东炎，梁书源，耿妍竹，段新会. 基于LightGBM-VIF-MIC-SFS的风电机组故障诊断输入特征选择方法. 热力发电. 2024(01): 154-164 . 
百度学术
2. 王永兴，王彦坤. 基于改进蚁狮算法的智慧赋能工厂装配线任务分配优化. 自动化与仪器仪表. 2024(03): 167-170 . 百度学术
3. 韦修喜，彭茂松，黄华娟. 基于多策略改进蝴蝶优化算法的无线传感网络节点覆盖优化. 计算机应用. 2024(04): 1009-1017 . 百度学术
4. 刘艺，杨国利，郑奇斌，李翔，周杨森，陈德鹏. 无人系统数据融合流水线架构设计. 计算机应用. 2024(08): 2536-2543 . 百度学术
其他类型引用(3)
计量
- 文章访问数: 267
- HTML全文浏览量: 17
- PDF下载量: 115
- 被引次数: 7
