基于卷积神经网络的算法选择研究

林秀丽, 李均利, 田竟民, 程小帆

(四川师范大学 计算机科学学院, 四川 成都 610101)

1 准备知识

受自然界生物进化机制和群体行为的启发,许多元启发式算法在过去几十年中得到了广泛的发展和应用,如遗传算法[1-2]、模拟退火算法[3]、差分进化算法[4]、粒子群算法[5]、人工鱼群算法[6]、人工蜂群算法[7]、蚁群算法[8]、灰狼优化算法[9]和萤火虫算法[10]等.以上这些算法是不依赖于问题特征的高级算法,在解决各种复杂的优化问题上能达到优异的效果.然而,正如“没有免费的午餐定理”[11]中所提到的：并不存在一个与具体无关的、普遍适用的通用型算法能够解决所有的优化问题.因此,对于不同类型的问题,仍然需要不同的算法.这时,人们开始针对特定问题研发合适的算法[12-13].但是专用的算法设计需要不同领域的知识,很难为不同领域的问题开发新的算法.另外,通过进行大量实验来选择现有的最佳算法是也不切实际的,因为许多工业优化问题计算成本很高[14-15].目前最为常见的算法选择方法是基于经验进行的[16],实际上,算法选择问题仍没有根本解决.

为了解决算法选择问题,Rice[17]提出了算法选择概念框架,通过研究问题特征与算法之间的关系,从给定问题中获取问题特征,找到特征与算法之间的映射关系.在此理论基础之上,研究者们将算法选择看作是一个学习的过程,并应用在机器学习领域,形成了元学习基本思想.元学习的基本思想是由Vilalta和Drissi[18]提出的,描述了分类问题的特征并验证其特征对算法的影响.Smith-Miles[19]提出了基于元学习的算法选择框架,将该方案快速拓展到了其他领域,其中包括时间序列的预测问题、回归问题、排序问题、约束问题和优化问题等.Hutter等[20]提出适用于NP难题的算法选择和配置的自动化技术.崔建双等[21]基于Rice模型和元学习推荐的优化算法提出了组合优化问题算法自动选择框架.在元学习思想基础框架下,研究者们将算法选择作为一个算法分类任务,并在机器学习算法上进行验证,其中,Koch等[22]采用单侧的支持向量回归的方法帮助算法选择.最近,深度学习的方法在各个领域兴起[23],当然也有研究者采用深度学习方法解决算法选择问题.如Kerschke等[24]将机器学习与探索性景观特征相结合,提出自动构建优化问题的算法选择模型,但该方法只针对单目标的连续黑盒优化问题.在此基础之上,He等[25]提出从优化问题中提取特征信息并保存为二维图像的方法,利用卷积神经网络(VGG)对黑盒测试问题进行分类和选择.Muoz等[26]试图利用神经网络来预测协方差自适应进化策略算法(CMA-ES)的性能,但是由于输入的大小和能够训练参数的数量都比较小,该方法不能完全体现深度神经网络的性能.虽然对约束满足问题的算法选择已经做了很多研究,但在单目标的无约束优化问题上却很少有工作关注将深度学习模型应用于算法选择问题.为了填补这一空白,本文将提出从优化问题中提取景观信息的方法,并使用卷积神经网络来学习这些景观特征信息.

针对以上问题,本文提出了基于深度学习的算法选择框架,即一个可以将深度学习应用于算法选择问题的整体框架.在本框架中利用卷积神经网络方法作为算法选择问题的训练和预测工具.

本文的安排如下:第2部分提出基于深度学习的算法选择框架;第3部分介绍产生问题实例样本的基准问题生成器;第4部分介绍基于卷积神经网络算法选择问题模型和设计;第5部分对算法选择问题进行实验,并对实验结果进行分析;最后,对本文工作进行简要总结以及对未来工作的展望.

2 基于深度学习的算法选择框架

2.1 基于Rice的算法选择算法选择解决的主要问题是：对于待解决的问题,在已知算法上进行搜索,寻找效果最好的算法,即最佳匹配算法.1976年Rice首次提出了算法选择问题的抽象模型,具体模型如图1所示.

图1 Rice算法选择抽象模型

2.2 基于深度学习的算法选择框架以Rice提出的算法选择抽象模型为原型,本文提出基于深度学习的算法选择框架,如图2所示,其中算法选择框架主要包含：问题域(P)、算法域(A)和表现域(Y).由于“特征域”是最难定义、最难选择、最难提取的,而卷积神经网络相较于传统手工特征提取的方法最大的优点是它在学习过程中自动提取数据的主要特征,所以本文采用卷积神经网络对问题特征进行自动提取,跳过了特征域的问题.

图2 基于深度学习的算法选择框架

基于深度学习的算法选择过程如下：首先利用基准问题生成器,产生大量的问题实例样本,将这些问题实例集作为训练集.然后,采用深度学习中的学习方法进行特征学习,获取问题特征与算法性能相对应的表现域.

基于深度学习的算法选择过程实现步骤如下：

1) 通过收集或生成问题实例数据集;

2) 设计神经网络模型;

3) 利用神经网络训练出算法选择模型;

4) 将训练好的算法选择神经网络模型预测新的数据集,验证准确率并做出评价.

3 基准问题生成器(HFEBG)

由于本文采用卷积神经网络实现算法选择问题,需要大量数据对模型进行训练.基准问题生成器能够产生大量的基准优化问题.基准问题是标准优化的问题,应用于优化算法的估计、表现特征和性能度量.一般情况下,常用的基准问题有4类：

2) 在有影响力的文章中所使用的知名基准问题,如文献[29];

3) 可调基准生成器,如最大集合高斯(MSG)景观生成器[30];

4) 现实中优化问题[31].

本文采用Lou等[32-34]提出的基于层次适应度的基准问题生成器(HFEBG)生成满足本实验要求的训练样本.HFEBG的目的是找到在算法A1上表现最佳的问题实例(UE-A1),其中算法

A1∈SA={A1,A2,…,An}.

图3 HFEBG产生问题实例流程

HFEBG通过输入一组算法集合,可调基准问题生成器和进化问题实例的进化算法.最后输出满足条件的结果,即问题实例.HFEBG中采用最大集合高斯测试问题生成器(MSG)作为基准问题生成器.问题实例I由5个参数组成,分别是问题维度(d)、局部最优值的数量(n)、每个局部最优值的标准差σ(n*1)、在局部最优值的每个维度下的压缩率Q(n*d)和局部最优值与全局最优值的比值r.通常问题维数d=d0和局部最优值个数n=n0都是固定的,于是问题实例I可以表示为

I=MSG(d0,n0)(x),

其中

x={σ,Q,r}.

I*=HFEBGDE(MSG(d0,n0)(x*)).

于是本文的问题实例的由3部分组成,分别是标准差、压缩率和全局最优值和局部最优值的比值.

4 卷积神经网络

4.1 卷积神经网络卷积神经网络[35]主要由3部分组成,分别是卷积层、池化层和全连接层.卷积层提取特征,池化层进行降维操作,全连接层完成分类输出.具体操作如下：

1) 卷积层.卷积层主要是通过卷积核对输入数据进行特征提取操作.卷积核的大小和数量对整个网络的性能起着关键性的作用.卷积核的个数与网络的整体性能是成正比的,但是一旦卷积核的个数增加(同时也在增加计算的规模)到一定的值后,性能的提升就微乎其微.因此,卷积核数量的设计对于不同的分类任务就会设置不同的参数.卷积计算公式为

i=1,2,…,q，

(1)

通常在卷积操作过后,会使用激活函数实现函数的非线性变换.常用的激活函数有Sigmoid、Tanh、ReLU和Maxout.卷积神经网络中使用频率最多的激活函数为ReLU,其表达式为

y(i)=f(g(i))=max{0,g(i)},

i=1,2,…,q.

(2)

该激活函数的作用是将所有非零数值都映射为0,将大于0的数值不变，其中g(i)表示ReLU的输入数据,f(g(i))是ReLU的输出数据.

2) 池化层.在卷积层后采用池化层(也称采样层),不仅降低了提取的特征的维数,也降低计算规模,还对特征提供基本的平移不变性.虽然池化层有以上这些好处,但池化的比例要适中,若池化的比例过大,大量的数据特征丢失,也会迫使网络性能下降.常见的池化方法包括均值池化、最大池化等.具体池化计算公式为

p

j=1,2,…,q,

(3)

3) 全连接层.在卷积层和池化层之后,最后采用全连接层来完成分类任务.全连接层通常和激活函数一起使用.在处理两分类问题时,输出层一般采用Sigmod函数作为激活函数；处理多分类问题时采用Softmax函数.本实验采用Softmax函数,函数将多个神经元的输出映射到[0,1]区间内,输出概率作为分类的结果.具体激活函数为

σ(z)

(4)

4.2 基于卷积神经网络的算法选择问题模型设计用于解决算法选择问题的卷积神经网络的整体架构由6个卷积层、6个归一化层、一个池化层、一个输出层(Dropout)和一个全连接层组成.考虑到本文中问题实例结构为向量形式,故卷积核大小设置为向量,总体框架设计如图4所示,具体网络参数设置如表1所示.

图4 算法选择问题神经网络模型

表1 算法选择问题模型结构参数

为了使分类的效果达到最佳,特地对卷积神经网络模型中参数的设置以及层次的安排做出一些调整.

首先,在每个卷积操作之后添加ReLU作为激活函数.另外,也在每一个卷积层后采用了批处理归一化(BN)操作.批处理归一化操作通过规范化使得每一个层的网络输入数据的均值和方差都在一定的范围内,允许每一个层进行独立的学习,提高整个神经网络的学习速度.当学习率参数更新过大时,使用批处理归一化操作就不会受到参数值大小的影响.另外还能够有效缓解梯度消失等问题.

其次,还添加了Dropout层、L2归一化方法和最大池化层.池化层用于减少输出特征图的大小和加快模型训练的速度,而Dropout层能够让一维卷积神经网络模型避免出现过度拟合的情况.

最后,利用Softmax函数将分类问题输出.Softmax层的输出数目等于分类个数.例如,如果是从3个算法组成的算法集中为给定的问题推荐一个合适的算法,那么该任务中Softmax层的输出数应该是3.Softmax层采用交叉熵损失对分类误差进行评估.交叉熵损失公式为

Losslog

(1-pi)log

(5)

5 实验与结果分析

5.1 数据集在实验中,采用基准问题生成器生成足够多的训练样本集,作为卷积神经网络的输入数据.HFEBG基准问题生成器的输入包含：

1) 建立好的一组算法集合

S={A1,A2,…,A};

2) 可调基准问题生成器;

3) 优化问题实例的算法.

输出：与目标算法所对应的最佳问题实例.

SA={ABC,CoDE,CMA-ES}.

将集合中的算法依次设置为目标算法.选用最大集合高斯景观生成器(MSG)作为问题生成器.选择差分算法(DE)进化最佳问题实例,具体参数设置参照文献[37].最后设置问题维数d0=10,局部最优值个数n0=10和重复迭代次数r=20,并且所有问题实例的搜索范围在[-1,1]d0,最大评估数为d0×n0×103次.

通过以上参数设置运行程序后,分别产生了3类最佳的问题实例集,其中包含UE-ABC、UE-CoDE和UE-CMA-ES问题实例集,并为这3类问题进行标注标签.详细标签值与问题的对应见表2.

表2 问题实例结构和问题实例标签值

5.2 实验设置本实验环境配置如表3所示.

表3 实验环境配置

实验1中,将训练迭代次数(epoch)设置为150,其中一轮迭代表示整个网络训练数据一次.将批量(batch size)设置为16,即每次训练的实例数.使用Adam优化器来优化神经网络,并将学习速率设置为3E-4.Adam优化器的第一动量(β1)、第二动量(β2)和ε分别设置为0.9、0.999和10E-8,遵循Tensorflow 2.0框架库中的推荐设置.在每个时期结束时,使用验证实例来测试网络的性能.其参数在验证实例上表现最好(即具有最高精度)的网络将被保存.在训练之后,使用测试实例来评估训练有素的网络的性能,并通过HFEBG共产生25 455个问题实例,让其在3个优化算法(人工蜂群、复合差分进化算法和协方差自适应调整进化策略)独立运行,并选择最佳算法作为标签.样本实例按照6∶2∶2进行划分,60%的实例用于训练,20%的实例用于测试集和20%的实例用于验证集,各类实例详细样本个数见表4.在这个实验中,只研究了在维度为10的(D=10)问题实例在3个优化算法上的性能，于是只有3种可能的预测输出，因此本实验的基线精度应为1/3≈33.33%.为了获得可靠的结果,重复训练和测试过程5次,并记录预测的3类问题实例的平均准确率.

表4 样本数据集

实验2中,将本文的算法选择问题卷积神经网络模型与传统的机器学习的分类算法进行比较.传统机器学习的数据预处理操作和训练参数与卷积神经网络中的设置相同,将算法选择问题模型分别替换为：贝叶斯(Bayes)、逻辑回归(Logistic Regression)、支持向量机(SVM).为保证实验结果切实可信,重复执行5次操作.

5.3 分类指标依照常见的分类指标对算法选择模型进行比较,其中包含精准率(Precision)、召回率(Recall)、F1分数值(F1-score)、准确率(Accuracy)和混淆矩阵等指标.在计算以上指标时,会使用到参数TP、FP、TN、FN.TP表示样本真实类别为正值,预测样本类别也为正值;FP表示预测类别为正值,真实类别为负值;FN表示预测类别为负值,但是真实类别为正值;TN预测类别为负值,真实类别为负值.

准确率是预测正确的样本数量占总样本量的百分比,计算公式为

Accuracy

(6)

精准率是模型预测为正样本时结果中真实正样本所占的百分比,计算公式为

Precision

(7)

召回率与精准率不同,是在实际为正样本中被预测为正样本所占的百分比,计算公式为

Recall

(8)

F

(9)

另外,还采可以用混淆矩阵,对分类模型进行评估.

5.4 实验结果表5记录了预测3类问题准确率结果.平均准确率为90.01%,完全优于基线准确率.对于大多数问题类,准确率都在90%以上.图5记录了算法选择模型混淆矩阵结果.从图5中可以观察到,该模型能够正确预测较多的第0类问题,是能够帮助绝大部分的UE-CMA-ES问题实例准确找到最佳算法协方差自适应调整进化策略(CMA-ES).另外,相较于第0类问题，该模型将第1类和第2类问题错误分类的数量较多,但是也能为大部分的UE-ABC和UE-CoDE问题实体推荐最佳算法人工蜂群那和复杂差分.造成这两类问题数据的错误分类,最有可能的原因是第1类和第2问题的相似特征比较多,所以导致了该结果.从表5和图5的结果可以看出，该方法能够为大多数优化问题实例推荐最合适的优化算法.

表5 预测实例准确率

图5 算法选择问题模型混淆矩阵

在表6中,算法选择问题模型的准确率可以达到90.01%,而贝叶斯的准确率仅仅只有54.51%,逻辑回归和支持向量机中最高的准确率也只达到81.33%.很显然这样的结果是完全小于CNN的结果.另外,在精准率、召回率、F1分数值分类指标下CNN模型优于贝叶斯、逻辑回归、支持向量机分类方法.该结果证明,在本文数据集上采用分类模型比传统的机器学习方法更适合解决算法选择问题.其原因在于浅层模型特征学习能力有限,学习到的特征不具备较好的分类特性.另外,从该实验结果中还可以得出,无论是传统的机器学习分类算法还是本文提出的基于深度学习的卷积神经网络分类模型的结果都是远远高于这3类算法的试验基线精度,这些方法都能够有效的解决算法选择问题,只是每种算法针对的这3类问题达到的准确率结果不同.

表6 分类模型算法性能比较

从以上实验结果得出,本文提出的方法可以为大多数优化问题实例推荐最合适的优化算法.

6 结束语

算法选择问题是一个重要的课题,因为不同类型的优化问题需要不同的优化算法.近年来,研究人员将算法选择视为分类或回归任务,并提出了许多解决方法.另外,神经网络特别是卷积神经网络在处理分类和回归任务方面表现出很强的能力.然而,将深度学习应用于算法选择的研究还比较少,而将深度学习应用于无约束的连续优化问题的算法选择的研究就更少.

本文提出了基于深度学习的算法选择模型,并利用卷积神经网络结构对算法选择的方法进行验证.实验利用训练有素的卷积神经网络来推荐优化算法,并采用预测的算法来优化给定的问题.比较实验结果表明,深度学习方法中的卷积神经网络可以有效地解决优化问题.

对于下一步的工作，首先,本文只是把算法选择问题当作分类任务,其实将其作为回归任务也是可行的.其次,本文的卷积神经网络结构也可以替换成深度学习算法中更新的架构，这也是合理的.此外,还需要提高提取有效数据集的问题特征,查找能够反映问题难度的问题特征,能够更进一步探讨算法性能与问题特征的关系.最后,不仅仅要关注低维问题特征,还应该从高维度问题对算法性能进行评估.