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

(四川師范大學(xué) 計算機科學(xué)學(xué)院, 四川 成都 610101)

1 準備知識

受自然界生物進化機制和群體行為的啟發(fā),許多元啟發(fā)式算法在過去幾十年中得到了廣泛的發(fā)展和應(yīng)用,如遺傳算法[1-2]、模擬退火算法[3]、差分進化算法[4]、粒子群算法[5]、人工魚群算法[6]、人工蜂群算法[7]、蟻群算法[8]、灰狼優(yōu)化算法[9]和螢火蟲算法[10]等.以上這些算法是不依賴于問題特征的高級算法,在解決各種復(fù)雜的優(yōu)化問題上能達到優(yōu)異的效果.然而,正如“沒有免費的午餐定理”[11]中所提到的：并不存在一個與具體無關(guān)的、普遍適用的通用型算法能夠解決所有的優(yōu)化問題.因此,對于不同類型的問題,仍然需要不同的算法.這時,人們開始針對特定問題研發(fā)合適的算法[12-13].但是專用的算法設(shè)計需要不同領(lǐng)域的知識,很難為不同領(lǐng)域的問題開發(fā)新的算法.另外,通過進行大量實驗來選擇現(xiàn)有的最佳算法是也不切實際的,因為許多工業(yè)優(yōu)化問題計算成本很高[14-15].目前最為常見的算法選擇方法是基于經(jīng)驗進行的[16],實際上,算法選擇問題仍沒有根本解決.

為了解決算法選擇問題,Rice[17]提出了算法選擇概念框架,通過研究問題特征與算法之間的關(guān)系,從給定問題中獲取問題特征,找到特征與算法之間的映射關(guān)系.在此理論基礎(chǔ)之上,研究者們將算法選擇看作是一個學(xué)習(xí)的過程,并應(yīng)用在機器學(xué)習(xí)領(lǐng)域,形成了元學(xué)習(xí)基本思想.元學(xué)習(xí)的基本思想是由Vilalta和Drissi[18]提出的,描述了分類問題的特征并驗證其特征對算法的影響.Smith-Miles[19]提出了基于元學(xué)習(xí)的算法選擇框架,將該方案快速拓展到了其他領(lǐng)域,其中包括時間序列的預(yù)測問題、回歸問題、排序問題、約束問題和優(yōu)化問題等.Hutter等[20]提出適用于NP難題的算法選擇和配置的自動化技術(shù).崔建雙等[21]基于Rice模型和元學(xué)習(xí)推薦的優(yōu)化算法提出了組合優(yōu)化問題算法自動選擇框架.在元學(xué)習(xí)思想基礎(chǔ)框架下,研究者們將算法選擇作為一個算法分類任務(wù),并在機器學(xué)習(xí)算法上進行驗證,其中,Koch等[22]采用單側(cè)的支持向量回歸的方法幫助算法選擇.最近,深度學(xué)習(xí)的方法在各個領(lǐng)域興起[23],當然也有研究者采用深度學(xué)習(xí)方法解決算法選擇問題.如Kerschke等[24]將機器學(xué)習(xí)與探索性景觀特征相結(jié)合,提出自動構(gòu)建優(yōu)化問題的算法選擇模型,但該方法只針對單目標的連續(xù)黑盒優(yōu)化問題.在此基礎(chǔ)之上,He等[25]提出從優(yōu)化問題中提取特征信息并保存為二維圖像的方法,利用卷積神經(jīng)網(wǎng)絡(luò)(VGG)對黑盒測試問題進行分類和選擇.Muoz等[26]試圖利用神經(jīng)網(wǎng)絡(luò)來預(yù)測協(xié)方差自適應(yīng)進化策略算法(CMA-ES)的性能,但是由于輸入的大小和能夠訓(xùn)練參數(shù)的數(shù)量都比較小,該方法不能完全體現(xiàn)深度神經(jīng)網(wǎng)絡(luò)的性能.雖然對約束滿足問題的算法選擇已經(jīng)做了很多研究,但在單目標的無約束優(yōu)化問題上卻很少有工作關(guān)注將深度學(xué)習(xí)模型應(yīng)用于算法選擇問題.為了填補這一空白,本文將提出從優(yōu)化問題中提取景觀信息的方法,并使用卷積神經(jīng)網(wǎng)絡(luò)來學(xué)習(xí)這些景觀特征信息.

針對以上問題,本文提出了基于深度學(xué)習(xí)的算法選擇框架,即一個可以將深度學(xué)習(xí)應(yīng)用于算法選擇問題的整體框架.在本框架中利用卷積神經(jīng)網(wǎng)絡(luò)方法作為算法選擇問題的訓(xùn)練和預(yù)測工具.

本文的安排如下:第2部分提出基于深度學(xué)習(xí)的算法選擇框架;第3部分介紹產(chǎn)生問題實例樣本的基準問題生成器;第4部分介紹基于卷積神經(jīng)網(wǎng)絡(luò)算法選擇問題模型和設(shè)計;第5部分對算法選擇問題進行實驗,并對實驗結(jié)果進行分析;最后,對本文工作進行簡要總結(jié)以及對未來工作的展望.

2 基于深度學(xué)習(xí)的算法選擇框架

2.1 基于Rice的算法選擇算法選擇解決的主要問題是：對于待解決的問題,在已知算法上進行搜索,尋找效果最好的算法,即最佳匹配算法.1976年Rice首次提出了算法選擇問題的抽象模型,具體模型如圖1所示.

圖1 Rice算法選擇抽象模型

2.2 基于深度學(xué)習(xí)的算法選擇框架以Rice提出的算法選擇抽象模型為原型,本文提出基于深度學(xué)習(xí)的算法選擇框架,如圖2所示,其中算法選擇框架主要包含：問題域(P)、算法域(A)和表現(xiàn)域(Y).由于“特征域”是最難定義、最難選擇、最難提取的,而卷積神經(jīng)網(wǎng)絡(luò)相較于傳統(tǒng)手工特征提取的方法最大的優(yōu)點是它在學(xué)習(xí)過程中自動提取數(shù)據(jù)的主要特征,所以本文采用卷積神經(jīng)網(wǎng)絡(luò)對問題特征進行自動提取,跳過了特征域的問題.

圖2 基于深度學(xué)習(xí)的算法選擇框架

基于深度學(xué)習(xí)的算法選擇過程如下：首先利用基準問題生成器,產(chǎn)生大量的問題實例樣本,將這些問題實例集作為訓(xùn)練集.然后,采用深度學(xué)習(xí)中的學(xué)習(xí)方法進行特征學(xué)習(xí),獲取問題特征與算法性能相對應(yīng)的表現(xiàn)域.

基于深度學(xué)習(xí)的算法選擇過程實現(xiàn)步驟如下：

1) 通過收集或生成問題實例數(shù)據(jù)集;

2) 設(shè)計神經(jīng)網(wǎng)絡(luò)模型;

3) 利用神經(jīng)網(wǎng)絡(luò)訓(xùn)練出算法選擇模型;

4) 將訓(xùn)練好的算法選擇神經(jīng)網(wǎng)絡(luò)模型預(yù)測新的數(shù)據(jù)集,驗證準確率并做出評價.

3 基準問題生成器(HFEBG)

由于本文采用卷積神經(jīng)網(wǎng)絡(luò)實現(xiàn)算法選擇問題,需要大量數(shù)據(jù)對模型進行訓(xùn)練.基準問題生成器能夠產(chǎn)生大量的基準優(yōu)化問題.基準問題是標準優(yōu)化的問題,應(yīng)用于優(yōu)化算法的估計、表現(xiàn)特征和性能度量.一般情況下,常用的基準問題有4類：

2) 在有影響力的文章中所使用的知名基準問題,如文獻[29];

3) 可調(diào)基準生成器,如最大集合高斯(MSG)景觀生成器[30];

4) 現(xiàn)實中優(yōu)化問題[31].

本文采用Lou等[32-34]提出的基于層次適應(yīng)度的基準問題生成器(HFEBG)生成滿足本實驗要求的訓(xùn)練樣本.HFEBG的目的是找到在算法A1上表現(xiàn)最佳的問題實例(UE-A1),其中算法

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

圖3 HFEBG產(chǎn)生問題實例流程

HFEBG通過輸入一組算法集合,可調(diào)基準問題生成器和進化問題實例的進化算法.最后輸出滿足條件的結(jié)果,即問題實例.HFEBG中采用最大集合高斯測試問題生成器(MSG)作為基準問題生成器.問題實例I由5個參數(shù)組成,分別是問題維度(d)、局部最優(yōu)值的數(shù)量(n)、每個局部最優(yōu)值的標準差σ(n*1)、在局部最優(yōu)值的每個維度下的壓縮率Q(n*d)和局部最優(yōu)值與全局最優(yōu)值的比值r.通常問題維數(shù)d=d0和局部最優(yōu)值個數(shù)n=n0都是固定的,于是問題實例I可以表示為

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

其中

x={σ,Q,r}.

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

于是本文的問題實例的由3部分組成,分別是標準差、壓縮率和全局最優(yōu)值和局部最優(yōu)值的比值.

4 卷積神經(jīng)網(wǎng)絡(luò)

4.1 卷積神經(jīng)網(wǎng)絡(luò)卷積神經(jīng)網(wǎng)絡(luò)[35]主要由3部分組成,分別是卷積層、池化層和全連接層.卷積層提取特征,池化層進行降維操作,全連接層完成分類輸出.具體操作如下：

1) 卷積層.卷積層主要是通過卷積核對輸入數(shù)據(jù)進行特征提取操作.卷積核的大小和數(shù)量對整個網(wǎng)絡(luò)的性能起著關(guān)鍵性的作用.卷積核的個數(shù)與網(wǎng)絡(luò)的整體性能是成正比的,但是一旦卷積核的個數(shù)增加(同時也在增加計算的規(guī)模)到一定的值后,性能的提升就微乎其微.因此,卷積核數(shù)量的設(shè)計對于不同的分類任務(wù)就會設(shè)置不同的參數(shù).卷積計算公式為

i=1,2,…,q，

(1)

通常在卷積操作過后,會使用激活函數(shù)實現(xiàn)函數(shù)的非線性變換.常用的激活函數(shù)有Sigmoid、Tanh、ReLU和Maxout.卷積神經(jīng)網(wǎng)絡(luò)中使用頻率最多的激活函數(shù)為ReLU,其表達式為

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

i=1,2,…,q.

(2)

該激活函數(shù)的作用是將所有非零數(shù)值都映射為0,將大于0的數(shù)值不變，其中g(shù)(i)表示ReLU的輸入數(shù)據(jù),f(g(i))是ReLU的輸出數(shù)據(jù).

2) 池化層.在卷積層后采用池化層(也稱采樣層),不僅降低了提取的特征的維數(shù),也降低計算規(guī)模,還對特征提供基本的平移不變性.雖然池化層有以上這些好處,但池化的比例要適中,若池化的比例過大,大量的數(shù)據(jù)特征丟失,也會迫使網(wǎng)絡(luò)性能下降.常見的池化方法包括均值池化、最大池化等.具體池化計算公式為

p

j=1,2,…,q,

(3)

3) 全連接層.在卷積層和池化層之后,最后采用全連接層來完成分類任務(wù).全連接層通常和激活函數(shù)一起使用.在處理兩分類問題時,輸出層一般采用Sigmod函數(shù)作為激活函數(shù)；處理多分類問題時采用Softmax函數(shù).本實驗采用Softmax函數(shù),函數(shù)將多個神經(jīng)元的輸出映射到[0,1]區(qū)間內(nèi),輸出概率作為分類的結(jié)果.具體激活函數(shù)為

σ(z)

(4)

4.2 基于卷積神經(jīng)網(wǎng)絡(luò)的算法選擇問題模型設(shè)計用于解決算法選擇問題的卷積神經(jīng)網(wǎng)絡(luò)的整體架構(gòu)由6個卷積層、6個歸一化層、一個池化層、一個輸出層(Dropout)和一個全連接層組成.考慮到本文中問題實例結(jié)構(gòu)為向量形式,故卷積核大小設(shè)置為向量,總體框架設(shè)計如圖4所示,具體網(wǎng)絡(luò)參數(shù)設(shè)置如表1所示.

圖4 算法選擇問題神經(jīng)網(wǎng)絡(luò)模型

表1 算法選擇問題模型結(jié)構(gòu)參數(shù)

為了使分類的效果達到最佳,特地對卷積神經(jīng)網(wǎng)絡(luò)模型中參數(shù)的設(shè)置以及層次的安排做出一些調(diào)整.

首先,在每個卷積操作之后添加ReLU作為激活函數(shù).另外,也在每一個卷積層后采用了批處理歸一化(BN)操作.批處理歸一化操作通過規(guī)范化使得每一個層的網(wǎng)絡(luò)輸入數(shù)據(jù)的均值和方差都在一定的范圍內(nèi),允許每一個層進行獨立的學(xué)習(xí),提高整個神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)速度.當學(xué)習(xí)率參數(shù)更新過大時,使用批處理歸一化操作就不會受到參數(shù)值大小的影響.另外還能夠有效緩解梯度消失等問題.

其次,還添加了Dropout層、L2歸一化方法和最大池化層.池化層用于減少輸出特征圖的大小和加快模型訓(xùn)練的速度,而Dropout層能夠讓一維卷積神經(jīng)網(wǎng)絡(luò)模型避免出現(xiàn)過度擬合的情況.

最后,利用Softmax函數(shù)將分類問題輸出.Softmax層的輸出數(shù)目等于分類個數(shù).例如,如果是從3個算法組成的算法集中為給定的問題推薦一個合適的算法,那么該任務(wù)中Softmax層的輸出數(shù)應(yīng)該是3.Softmax層采用交叉熵損失對分類誤差進行評估.交叉熵損失公式為

Losslog

(1-pi)log

(5)

5 實驗與結(jié)果分析

5.1 數(shù)據(jù)集在實驗中,采用基準問題生成器生成足夠多的訓(xùn)練樣本集,作為卷積神經(jīng)網(wǎng)絡(luò)的輸入數(shù)據(jù).HFEBG基準問題生成器的輸入包含：

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

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

2) 可調(diào)基準問題生成器;

3) 優(yōu)化問題實例的算法.

輸出：與目標算法所對應(yīng)的最佳問題實例.

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

將集合中的算法依次設(shè)置為目標算法.選用最大集合高斯景觀生成器(MSG)作為問題生成器.選擇差分算法(DE)進化最佳問題實例,具體參數(shù)設(shè)置參照文獻[37].最后設(shè)置問題維數(shù)d0=10,局部最優(yōu)值個數(shù)n0=10和重復(fù)迭代次數(shù)r=20,并且所有問題實例的搜索范圍在[-1,1]d0,最大評估數(shù)為d0×n0×103次.

通過以上參數(shù)設(shè)置運行程序后,分別產(chǎn)生了3類最佳的問題實例集,其中包含UE-ABC、UE-CoDE和UE-CMA-ES問題實例集,并為這3類問題進行標注標簽.詳細標簽值與問題的對應(yīng)見表2.

表2 問題實例結(jié)構(gòu)和問題實例標簽值

5.2 實驗設(shè)置本實驗環(huán)境配置如表3所示.

表3 實驗環(huán)境配置

實驗1中,將訓(xùn)練迭代次數(shù)(epoch)設(shè)置為150,其中一輪迭代表示整個網(wǎng)絡(luò)訓(xùn)練數(shù)據(jù)一次.將批量(batch size)設(shè)置為16,即每次訓(xùn)練的實例數(shù).使用Adam優(yōu)化器來優(yōu)化神經(jīng)網(wǎng)絡(luò),并將學(xué)習(xí)速率設(shè)置為3E-4.Adam優(yōu)化器的第一動量(β1)、第二動量(β2)和ε分別設(shè)置為0.9、0.999和10E-8,遵循Tensorflow 2.0框架庫中的推薦設(shè)置.在每個時期結(jié)束時,使用驗證實例來測試網(wǎng)絡(luò)的性能.其參數(shù)在驗證實例上表現(xiàn)最好(即具有最高精度)的網(wǎng)絡(luò)將被保存.在訓(xùn)練之后,使用測試實例來評估訓(xùn)練有素的網(wǎng)絡(luò)的性能,并通過HFEBG共產(chǎn)生25 455個問題實例,讓其在3個優(yōu)化算法(人工蜂群、復(fù)合差分進化算法和協(xié)方差自適應(yīng)調(diào)整進化策略)獨立運行,并選擇最佳算法作為標簽.樣本實例按照6∶2∶2進行劃分,60%的實例用于訓(xùn)練,20%的實例用于測試集和20%的實例用于驗證集,各類實例詳細樣本個數(shù)見表4.在這個實驗中,只研究了在維度為10的(D=10)問題實例在3個優(yōu)化算法上的性能，于是只有3種可能的預(yù)測輸出，因此本實驗的基線精度應(yīng)為1/3≈33.33%.為了獲得可靠的結(jié)果,重復(fù)訓(xùn)練和測試過程5次,并記錄預(yù)測的3類問題實例的平均準確率.

表4 樣本數(shù)據(jù)集

實驗2中,將本文的算法選擇問題卷積神經(jīng)網(wǎng)絡(luò)模型與傳統(tǒng)的機器學(xué)習(xí)的分類算法進行比較.傳統(tǒng)機器學(xué)習(xí)的數(shù)據(jù)預(yù)處理操作和訓(xùn)練參數(shù)與卷積神經(jīng)網(wǎng)絡(luò)中的設(shè)置相同,將算法選擇問題模型分別替換為：貝葉斯(Bayes)、邏輯回歸(Logistic Regression)、支持向量機(SVM).為保證實驗結(jié)果切實可信,重復(fù)執(zhí)行5次操作.

5.3 分類指標依照常見的分類指標對算法選擇模型進行比較,其中包含精準率(Precision)、召回率(Recall)、F1分數(shù)值(F1-score)、準確率(Accuracy)和混淆矩陣等指標.在計算以上指標時,會使用到參數(shù)TP、FP、TN、FN.TP表示樣本真實類別為正值,預(yù)測樣本類別也為正值;FP表示預(yù)測類別為正值,真實類別為負值;FN表示預(yù)測類別為負值,但是真實類別為正值;TN預(yù)測類別為負值,真實類別為負值.

準確率是預(yù)測正確的樣本數(shù)量占總樣本量的百分比,計算公式為

Accuracy

(6)

精準率是模型預(yù)測為正樣本時結(jié)果中真實正樣本所占的百分比,計算公式為

Precision

(7)

召回率與精準率不同,是在實際為正樣本中被預(yù)測為正樣本所占的百分比,計算公式為

Recall

(8)

F

(9)

另外,還采可以用混淆矩陣,對分類模型進行評估.

5.4 實驗結(jié)果表5記錄了預(yù)測3類問題準確率結(jié)果.平均準確率為90.01%,完全優(yōu)于基線準確率.對于大多數(shù)問題類,準確率都在90%以上.圖5記錄了算法選擇模型混淆矩陣結(jié)果.從圖5中可以觀察到,該模型能夠正確預(yù)測較多的第0類問題,是能夠幫助絕大部分的UE-CMA-ES問題實例準確找到最佳算法協(xié)方差自適應(yīng)調(diào)整進化策略(CMA-ES).另外,相較于第0類問題，該模型將第1類和第2類問題錯誤分類的數(shù)量較多,但是也能為大部分的UE-ABC和UE-CoDE問題實體推薦最佳算法人工蜂群那和復(fù)雜差分.造成這兩類問題數(shù)據(jù)的錯誤分類,最有可能的原因是第1類和第2問題的相似特征比較多,所以導(dǎo)致了該結(jié)果.從表5和圖5的結(jié)果可以看出，該方法能夠為大多數(shù)優(yōu)化問題實例推薦最合適的優(yōu)化算法.

表5 預(yù)測實例準確率

圖5 算法選擇問題模型混淆矩陣

在表6中,算法選擇問題模型的準確率可以達到90.01%,而貝葉斯的準確率僅僅只有54.51%,邏輯回歸和支持向量機中最高的準確率也只達到81.33%.很顯然這樣的結(jié)果是完全小于CNN的結(jié)果.另外,在精準率、召回率、F1分數(shù)值分類指標下CNN模型優(yōu)于貝葉斯、邏輯回歸、支持向量機分類方法.該結(jié)果證明,在本文數(shù)據(jù)集上采用分類模型比傳統(tǒng)的機器學(xué)習(xí)方法更適合解決算法選擇問題.其原因在于淺層模型特征學(xué)習(xí)能力有限,學(xué)習(xí)到的特征不具備較好的分類特性.另外,從該實驗結(jié)果中還可以得出,無論是傳統(tǒng)的機器學(xué)習(xí)分類算法還是本文提出的基于深度學(xué)習(xí)的卷積神經(jīng)網(wǎng)絡(luò)分類模型的結(jié)果都是遠遠高于這3類算法的試驗基線精度,這些方法都能夠有效的解決算法選擇問題,只是每種算法針對的這3類問題達到的準確率結(jié)果不同.

表6 分類模型算法性能比較

從以上實驗結(jié)果得出,本文提出的方法可以為大多數(shù)優(yōu)化問題實例推薦最合適的優(yōu)化算法.

6 結(jié)束語

算法選擇問題是一個重要的課題,因為不同類型的優(yōu)化問題需要不同的優(yōu)化算法.近年來,研究人員將算法選擇視為分類或回歸任務(wù),并提出了許多解決方法.另外,神經(jīng)網(wǎng)絡(luò)特別是卷積神經(jīng)網(wǎng)絡(luò)在處理分類和回歸任務(wù)方面表現(xiàn)出很強的能力.然而,將深度學(xué)習(xí)應(yīng)用于算法選擇的研究還比較少,而將深度學(xué)習(xí)應(yīng)用于無約束的連續(xù)優(yōu)化問題的算法選擇的研究就更少.

本文提出了基于深度學(xué)習(xí)的算法選擇模型,并利用卷積神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)對算法選擇的方法進行驗證.實驗利用訓(xùn)練有素的卷積神經(jīng)網(wǎng)絡(luò)來推薦優(yōu)化算法,并采用預(yù)測的算法來優(yōu)化給定的問題.比較實驗結(jié)果表明,深度學(xué)習(xí)方法中的卷積神經(jīng)網(wǎng)絡(luò)可以有效地解決優(yōu)化問題.

對于下一步的工作，首先,本文只是把算法選擇問題當作分類任務(wù),其實將其作為回歸任務(wù)也是可行的.其次,本文的卷積神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)也可以替換成深度學(xué)習(xí)算法中更新的架構(gòu)，這也是合理的.此外,還需要提高提取有效數(shù)據(jù)集的問題特征,查找能夠反映問題難度的問題特征,能夠更進一步探討算法性能與問題特征的關(guān)系.最后,不僅僅要關(guān)注低維問題特征,還應(yīng)該從高維度問題對算法性能進行評估.