李庚松 劉 藝 鄭奇斌 李 翔 劉 坤 秦 偉 王 強 楊長虹

1 （國防科技創(chuàng)新研究院 北京 100071）

2 （軍事科學(xué)院 北京 100091）

3 （天津（濱海）人工智能創(chuàng)新中心 天津 300457）

在大數(shù)據(jù)時代背景下，利用數(shù)據(jù)進行分析和決策成為了不同領(lǐng)域的重要工作，各種人工智能算法為此提供了不可忽視的助力.然而，“沒有免費午餐”定理表明，不存在一個在所有問題上具備優(yōu)越性能的“最優(yōu)”算法[1].如何從大量可行方法中為給定任務(wù)選擇滿足需求的合適算法成為了工程中的關(guān)鍵問題，即算法選擇問題[2].算法選擇問題可以通過人工選擇方法和機器學(xué)習(xí)方法解決.人工選擇方法包括實驗試錯法和專家知識法.前者通過大量的實驗獲得算法性能，分析結(jié)果并選擇算法；后者則按照領(lǐng)域?qū)＜业闹笇?dǎo)進行算法選擇.然而，實驗試錯法成本較高，專家知識法基于專家的經(jīng)驗知識，存在人為偏差且獲取較為困難.機器學(xué)習(xí)方法提取問題的抽象特征，設(shè)計模型實現(xiàn)自動化的算法選擇，包括基于元學(xué)習(xí)的方法和基于協(xié)同過濾的方法[3-4].其中，基于元學(xué)習(xí)的方法研究基礎(chǔ)較為深厚，具有靈活性高、適用范圍廣、計算成本低等優(yōu)點，成為了算法選擇的主要方法[5-7].

基于元學(xué)習(xí)的算法選擇利用問題的元特征（抽象特征）和歷史學(xué)習(xí)經(jīng)驗訓(xùn)練元算法，構(gòu)建問題元特征到合適算法的映射.元特征和元算法是其中的關(guān)鍵內(nèi)容，而現(xiàn)有研究在元特征和元算法的選擇和使用上存在一些缺點：在元特征方面，多數(shù)研究選擇固定的元特征[8-10]，可擴展性較弱，且難以充分利用元特征的互補性；在元算法方面，研究或采用單個元算法，泛化性能不足，或采用同構(gòu)集成元算法[11-14]，沒有利用不同元算法的優(yōu)勢，導(dǎo)致多樣性不足.

集成學(xué)習(xí)的相關(guān)研究表明，利用準確且多樣的基學(xué)習(xí)器進行集成可以獲得更精確、更穩(wěn)定的學(xué)習(xí)性能[15-16].選擇性集成方法根據(jù)基學(xué)習(xí)器的準確性和多樣性從多個基學(xué)習(xí)器中選取部分進行集成，可以減少集成算法的存儲空間和預(yù)測時間并提升其泛化性能，是集成學(xué)習(xí)的熱點方向之一[17-19].演化算法有著魯棒性強、適用性高、可以全局搜索等特性，在選擇性集成研究中得到了廣泛應(yīng)用[20-22].

蟻獅優(yōu)化（ant lion optimizer，ALO）[23]算法是近年來出現(xiàn)的演化算法，它模擬蟻獅捕食螞蟻的行為機制對最優(yōu)解進行搜索，具有尋優(yōu)性能強、參數(shù)設(shè)置少、易于實現(xiàn)等優(yōu)點.研究人員將ALO 擴展應(yīng)用于多目標優(yōu)化問題，在污水處理、工程設(shè)計等領(lǐng)域取得了良好的應(yīng)用效果[24-26].

為了提升基于元學(xué)習(xí)的算法選擇性能，提出基于多目標混合蟻獅優(yōu)化的選擇性集成算法選擇方法（selective ensemble algorithm selection method based on multi-objective hybrid ant lion optimizer，SAMO），該方法包括一種算法選擇模型和一種多目標混合蟻獅優(yōu)化算法.算法選擇模型以集成元算法的準確性和多樣性作為優(yōu)化目標，同時選擇元特征和構(gòu)建選擇性集成元算法.多目標混合蟻獅優(yōu)化算法對模型進行優(yōu)化，通過離散型編碼選擇元特征子集，使用連續(xù)型編碼構(gòu)建集成元算法，在此基礎(chǔ)上應(yīng)用增強游走策略和偏好精英選擇機制提升尋優(yōu)性能.

本文的主要貢獻包括3 個方面:

1）提出一種算法選擇模型，同時從元特征和元算法2 個方面提升基于元學(xué)習(xí)的算法選擇性能.模型通過元特征選擇尋找互補性較強的元特征子集，通過選擇性集成構(gòu)建異構(gòu)集成元算法.

2）提出一種多目標混合蟻獅優(yōu)化算法，求解算法選擇模型.通過混合編碼機制使個體同時進行元特征選擇和選擇性集成；采用增強游走策略，在個體搜索過程中引入隨機性，增加算法的種群多樣性；應(yīng)用偏好精英選擇機制，以不同的優(yōu)化目標為偏好選擇精英個體，增強算法的尋優(yōu)能力.

3）使用260 個數(shù)據(jù)集、150 種元特征和9 種候選算法構(gòu)建分類算法選擇問題，在此基礎(chǔ)上將所提方法與8 種典型方法在4 種性能指標上進行對比分析，結(jié)果證明了所提方法的有效性和優(yōu)越性.

1 相關(guān)概念和工作

1.1 基于元學(xué)習(xí)的算法選擇

1.1.1 基于元學(xué)習(xí)的算法選擇框架

基于元學(xué)習(xí)的算法選擇框架[27-28]如圖1 所示.框架首先提取歷史數(shù)據(jù)集的元特征，并通過性能測度評估確定歷史數(shù)據(jù)集的最優(yōu)算法，在過程中采用不同的性能測度方法可能獲得不同的最優(yōu)算法；然后以元特征為屬性，以最優(yōu)算法為標簽組成元實例構(gòu)建元數(shù)據(jù)集，并在元數(shù)據(jù)集上訓(xùn)練元算法；最后，提取新數(shù)據(jù)集的元特征輸入已訓(xùn)練的元算法，元算法即對其最優(yōu)算法進行預(yù)測輸出.

Fig.1 Framework of algorithm selection based on metalearning圖1 基于元學(xué)習(xí)的算法選擇框架

1.1.2 元特征相關(guān)內(nèi)容

根據(jù)反映數(shù)據(jù)集特性的不同，元特征分為4 類：

1）基于統(tǒng)計和信息論的元特征采用統(tǒng)計學(xué)和信息論的方法提取數(shù)據(jù)集的抽象特征[27].該類型元特征應(yīng)用廣泛且易于提取，然而其難以較好地刻畫數(shù)據(jù)集特性.

2）基于決策樹的元特征在數(shù)據(jù)集上訓(xùn)練決策樹，使用決策樹的結(jié)構(gòu)信息作為元特征[28].其能夠發(fā)掘數(shù)據(jù)集的整體特性，但提取成本高昂.

3）基于基準的元特征將基準算法在數(shù)據(jù)集上的性能指標值作為元特征[29]，其提取方法較為簡單，然而對基準算法的依賴度較高.

4）基于問題復(fù)雜度的元特征從類重疊、類不平衡、數(shù)據(jù)稀疏度等方面對數(shù)據(jù)集的幾何復(fù)雜度進行量化評估[30].該類型元特征反映了求解問題的困難程度，應(yīng)用效果較好，但是計算復(fù)雜度較大.

1.1.3 元算法相關(guān)內(nèi)容

按照訓(xùn)練過程的技術(shù)特點，將元算法分為4 類：

1）基于規(guī)則的元算法生成候選算法的選擇規(guī)則，通過將元特征與規(guī)則進行匹配，為新數(shù)據(jù)集選擇合適算法，該方法具備較強的可解釋性，但泛化性能較差.針對負荷預(yù)測問題，文獻[8]提取18 種數(shù)據(jù)集元特征，訓(xùn)練分類回歸樹（classification and regression tree，CART）選擇最優(yōu)算法.

2）基于距離的元算法通過元特征測度距離，評估數(shù)據(jù)集之間的相似度，使用相似數(shù)據(jù)集的最優(yōu)算法作為新數(shù)據(jù)集的合適算法.k最近鄰（knearest neighbors，kNN）是研究中常見的元算法，其實現(xiàn)簡單且運行較快，但關(guān)鍵參數(shù)k的最優(yōu)值設(shè)置較為困難.文獻[9]使用32 種分類數(shù)據(jù)集元特征，基于kNN 構(gòu)建元特征到最優(yōu)算法的映射.

3）基于回歸的元算法預(yù)測各候選算法的性能指標值并進行比較，從而完成算法選擇決策，使用較為廣泛的元算法為支持向量回歸（support vector regression，SVR）.該類方法可以靈活地增減候選算法，但訓(xùn)練成本較高.文獻[10]選用12 種元特征，應(yīng)用SVR 學(xué)習(xí)元特征與候選分類算法性能的映射關(guān)系.

4）基于集成的元算法通過一定策略組合多個性能較弱的元算法，得到具有較強性能的集成元算法，常見的元算法包括隨機森林（random forest，RF）、極端梯度提升（extreme gradient boosting，XGB）等，這些方法的泛化性能較好，但訓(xùn)練速度較慢且參數(shù)設(shè)置較為復(fù)雜.文獻[11]提取22 種元特征，采用RF 學(xué)習(xí)元特征到最優(yōu)分類算法的映射.文獻[12]使用22 種元特征，采用隨機森林回歸（random forest regression，RFR）預(yù)測候選分類算法的性能.文獻[13]提取98 種圖像元特征，分別訓(xùn)練RF 和XGB 并預(yù)測最優(yōu)圖像分割算法.文獻[14]選擇39 種分類數(shù)據(jù)集元特征，應(yīng)用輕量梯度提升機（light gradient boosting machine，LGBM）進行算法選擇.

在上述研究中，元特征和元算法的選用仍存在一些問題：在元特征方面，研究通常根據(jù)需求選取固定的元特征，耦合度較高，可擴展性較弱；不同元特征從不同方面描述和提取數(shù)據(jù)集的抽象特征，具備一定的互補性，然而現(xiàn)有的方法難以有效利用.在元算法方面，現(xiàn)有研究或使用泛化性能較弱的單個元算法，或采用同構(gòu)基學(xué)習(xí)器的集成元算法，未能充分利用不同元算法的優(yōu)勢和多樣性.

1.2 多目標優(yōu)化問題

多目標優(yōu)化是指同時優(yōu)化多個目標且目標間相互矛盾的問題，該問題通常是NP 難的，無法獲取唯一最優(yōu)解，而是一組次優(yōu)解[31].不失一般性地以最小化問題為例，給出多目標優(yōu)化問題的定義.

定義1.多目標優(yōu)化問題.給定一個具有n維決策變量，m（m≥2）個目標的優(yōu)化問題，其數(shù)學(xué)模型的定義如式（1）所示：

其中x=（x1,x2,…,xn），x為決策向量，Ω為決策空間；F:Ω→Λ，F(xiàn)為目標函數(shù)向量，Λ為由m個優(yōu)化目標構(gòu)成的目標空間.

定義2.帕累托支配.給定2 個解x和y，當(dāng)滿足如式（2）所示約束條件時，則稱x支配y，表示為x?y.

定義3.帕累托最優(yōu)解.給定解x∈Ω，當(dāng)且僅當(dāng)不存在另一個解支配它，即?y∈Ω:y?x時，x為帕累托最優(yōu)解.

定義4.帕累托解集（Pareto set，PS).決策空間Ω中所有帕累托最優(yōu)解的集合稱為帕累托解集，如式（3）所示：

定義5.帕累托前沿（Pareto front，PF）.PS對應(yīng)的目標向量集合稱為帕累托前沿，如式（4）所示：

多目標優(yōu)化旨在獲取靠近真實PF的解集S，從2 個方面評估解集S的質(zhì)量：收斂性，即解集S與真實PF的接近程度；分布性，即解集S在目標空間中的散布程度.

1.3 ALO

ALO 通過螞蟻的隨機游走模擬蟻獅使用陷阱誘捕螞蟻的過程，實現(xiàn)個體解的搜索更新.螞蟻各維度的隨機游走方法如式（5）所示：

其中t為當(dāng)前迭代次數(shù)，T為最大迭代次數(shù)，X（t）表示隨機游走位置，cusum表示隨機游走步長的累加和，用于生成隨機游走步長，rand表示位于[0,1]之間均勻分布的隨機數(shù).

在隨機游走過程中，螞蟻逐漸滑入陷阱，其游走邊界隨之縮小，如式（6）所示：

其中c和d表示個體各維度值的上界和下界，ct和dt分別表示第t次迭代中螞蟻各維度值搜索范圍的上界和下界，縮小程度I的計算如式（7）所示：

其中倍率因子w的值取決于當(dāng)前迭代次數(shù)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值呈遞增趨勢，而ct和dt呈遞減趨勢.

ALO 將適應(yīng)度最優(yōu)的蟻獅選為精英蟻獅，每只螞蟻通過輪盤賭方法選擇1 個蟻獅，圍繞精英蟻獅和輪盤賭蟻獅進行隨機游走，并根據(jù)式（8）更新位置：

其中At為第t次迭代螞蟻的位置向量，e和r分別表示精英蟻獅和輪盤賭蟻獅，為第t次迭代螞蟻圍繞e進行隨機游走得到的向量，為第t次迭代螞蟻圍繞r進行隨機游走所得向量.

2 SAMO

為了充分利用元特征的互補性和元算法的多樣性來提升算法選擇性能，SAMO 設(shè)計算法選擇模型，并提出多目標混合蟻獅優(yōu)化算法對模型進行求解，從而構(gòu)建準確性和多樣性較強的集成元算法.

使用SAMO 進行算法選擇的流程如圖2 所示.將元數(shù)據(jù)集輸入SAMO 后，SAMO 利用所提優(yōu)化算法對模型進行優(yōu)化，輸出集成元算法集合，然后從其中選擇一個集成元算法用于預(yù)測新數(shù)據(jù)集的最優(yōu)算法.

Fig.2 Algorithm selection process of SAMO圖2 SAMO 算法選擇流程

2.1 算法選擇模型

2.1.1 模型優(yōu)化目標

模型使用分類錯誤率（error rate，ER），評估集成元算法的準確性.

設(shè)有m個測試元實例X={x1,x2,…,xm}，各個元實例對應(yīng)的最優(yōu)算法標簽為Y={y1,y2,…,ym}，且有yk∈A,1 ≤k≤m，其中A={a1,a2,…,al}為包含l個候選算法標簽的集合，ER的計算公式為

其中E表示集成元算法，和yi分別表示第i個測試元實例的預(yù)測最優(yōu)算法標簽和真實最優(yōu)算法標簽.通過加權(quán)投票法，利用集成權(quán)重W={w1,w2,…,wv}組合v個基分類器B={b1,b2,…,bv}構(gòu)建集成元算法E，E對測試元實例xk∈X進行預(yù)測，如式（10）所示：

其中E（xk）表示預(yù)測最優(yōu)算法結(jié)果；a為A中的一個候選算法標簽；bi表示B中的第i個基分類器，bi（xk）表示對xk的預(yù)測結(jié)果；I（）為示性函數(shù)，當(dāng)其中的表達式邏輯為真時，I（）=1，否則I（）=0；wi為第i個基分類器的集成權(quán)重；函數(shù)表示取使其內(nèi)部表達式最大的算法標簽a.ER值越小，表示集成元算法的性能越好.

采用不同的多樣性指標（diversity indicator，DI），度量集成元算法的多樣性，包括Q 統(tǒng)計量（Q statistic，QS）、K 統(tǒng)計量（K statistic，KS）、相關(guān)系數(shù)（correlation coefficient，CC）、一致度量（agreement measure，AM）和雙錯測度（double fault，DF）.

基分類器bi和bj對X的預(yù)測結(jié)果列聯(lián)表如表1所示.

Table 1 Contingency Table of Prediction Results表1 預(yù)測結(jié)果列聯(lián)表

表1 中，c表示bi和bj均預(yù)測正確的元實例數(shù)；p表示bi預(yù)測正確而bj預(yù)測錯誤的元實例數(shù)；q表示bi預(yù)測錯誤而bj預(yù)測正確的元實例數(shù)；d表示bi和bj均預(yù)測錯誤的元實例數(shù).根據(jù)表1，bi和bj的QS，KS，CC，AM，DF指標計算公式為

式（11）～（15）所述的指標值越小代表基分類器多樣性越強，除AM和DF指標的值域為[0,1]外，其余指標的值域均為[-1,1]；此外，這5 個指標均為成對指標，即滿足DIbi,bj=DIbj,bi.集成元算法E的DI值為所有成對基分類器DI值的平均值，如式（16）所示：

綜上，算法選擇模型的目標函數(shù)向量為

2.1.2 模型設(shè)計

模型從元特征和元算法2 個方面提升算法選擇性能.在元特征方面，選擇互補性較強的元特征子集，從而有效利用元特征；在元算法方面，通過選擇性集成方法，對異構(gòu)基分類器進行集成，構(gòu)建具有較強泛化性能和多樣性的集成元算法.為了利用不同基分類器的優(yōu)勢和多樣性，采用kNN、支持向量機（support vector machine，SVM）和CART 作為基分類器，且本文設(shè)置每種基分類器的個數(shù)相等.

在對元數(shù)據(jù)集進行元特征選擇的基礎(chǔ)上，算法選擇模型構(gòu)建集成元算法的過程如圖3 所示.首先使用自助法對訓(xùn)練集進行若干次抽樣生成多個訓(xùn)練子集；然后運用基分類器在訓(xùn)練子集上進行訓(xùn)練形成基分類器集合；最后通過選擇性集成方法，從集合中選擇準確性和多樣性較強的基分類器并基于加權(quán)投票法策略進行組合，得到集成元算法.

Fig.3 Construction process of ensemble meta-learner圖3 集成元算法構(gòu)建過程

2.2 多目標混合蟻獅優(yōu)化算法

2.2.1 混合編碼機制

多目標混合蟻獅優(yōu)化算法針對元特征選擇的離散特性（元特征選擇與否），使用離散型編碼選擇元特征子集；采用連續(xù)型編碼構(gòu)建集成元算法，該連續(xù)型編碼包括1 個用于控制基分類器選擇概率的選擇閾值編碼，以及若干個基分類器權(quán)重編碼，用于選擇基分類器的訓(xùn)練子集并生成集成權(quán)重.

個體的混合編碼方式如圖4 所示.設(shè)元數(shù)據(jù)集含有M個元特征，則個體的離散型編碼數(shù)為M；設(shè)基分類器個數(shù)為V，則自助法抽樣生成的訓(xùn)練子集個數(shù)為V，個體依次為kNN，SVM，CART 使用V個編碼選擇訓(xùn)練子集和生成集成權(quán)重，因此基分類器權(quán)重編碼數(shù)為3V，個體的連續(xù)型編碼數(shù)為3V+1.

Fig.4 Coding pattern of individuals圖4 個體編碼方式

根據(jù)混合編碼機制，對個體各維度的編碼值進行初始化，如式（18）所示：

其中Ai為個體第i維的編碼值，個體前M維編碼為離散型的元特征選擇編碼，其值為1 表示第i維編碼對應(yīng)的元特征被選中，值為0 表示未被選中.個體第M+1 維編碼為選擇閾值編碼，其后的3V個編碼為基分類器權(quán)重編碼，前V個基分類器權(quán)重編碼為kNN 選擇訓(xùn)練子集，如式（19）所示：

其中AM+1為選擇閾值編碼值，J（Ai）= 1 表示第i維編碼對應(yīng)的訓(xùn)練子集被選中，J(Ai)= 0 表示未被選中，以此類推可得SVM 和CART 的訓(xùn)練子集.3 種基分類器分別在選擇的訓(xùn)練子集上獨立訓(xùn)練，得到基分類器集合B={b1,b2,…,bv}，通過基分類器權(quán)重編碼值生成這3 種基分類器集合對應(yīng)的集成權(quán)重W={w1,w2,…,wv}，如式（20）所示：

其中wi為第i個基分類器的集成權(quán)重，Ai為第i個基分類器對應(yīng)的基分類器權(quán)重編碼值，Aj為第j個基分類器對應(yīng)的基分類器權(quán)重編碼值.通過式（20）的歸一化方法，使得集成權(quán)重和為1，即=1.

2.2.2 增強游走策略

在混合編碼機制的基礎(chǔ)上，采用增強游走策略對個體進行搜索更新.

在迭代過程中，個體的離散型編碼使用離散隨機游走方法，如式（21）所示：

Fig.5 Change trend of m(t)圖5 m(t)變化趨勢

隨機游走后，螞蟻離散型編碼值更新為

對于個體的連續(xù)型編碼，在其游走更新過程中引入隨機性.ALO 中每只螞蟻的搜索邊界ct和dt變化趨勢相同，種群多樣性不足.為了增強所提算法的種群多樣性，對式（6）進行改進，如式（24）所示：

Fig.6 Change trend of search boundary圖6 搜索邊界變化趨勢

通過上述設(shè)計，增強游走策略對個體不同類型的編碼進行搜索更新，保留了螞蟻搜索邊界變化的遞減趨勢，同時在該過程中引入了隨機性，增加了算法的種群多樣性.

2.2.3 偏好精英選擇機制

算法將帕累托解作為蟻獅保存至外部存檔S，為了提升算法的尋優(yōu)能力，分別以不同優(yōu)化目標為偏好，從存檔S中選擇在該目標上最優(yōu)的精英蟻獅.為了增強解的分布性，通過小生境技術(shù)計算蟻獅解的稀疏度從而量化其分布性，然后利用稀疏度通過輪盤賭選擇蟻獅，蟻獅解xS的稀疏度為

其中s(xS,φ)表示給定半徑 φ的小生境范圍內(nèi)解xS的稀疏度，yS表示存檔S中的另一個解，半徑 φ計算為

其中m（m≥2）為優(yōu)化目標個數(shù)，ei和ej分別表示第i個和第j個優(yōu)化目標對應(yīng)的精英蟻獅，‖‖計算二者目標函數(shù)值向量的歐氏距離，c為常數(shù)；‖F(xiàn)(xS)-F(yS)‖計算解xS和解yS目標函數(shù)值向量的歐氏距離，其值小于半徑 φ時表示yS是xS的相鄰解.給定解在存檔中的相鄰解越多，則該解的稀疏度越低，分布性越差.以2 個優(yōu)化目標為例，稀疏度計算示意如圖7 所示.

Fig.7 Schematic diagram of sparsity calculation圖7 稀疏度計算示意圖

在迭代過程中，對于每個優(yōu)化目標，每只初始化螞蟻根據(jù)蟻獅的稀疏度通過輪盤賭選擇1 個蟻獅，圍繞該優(yōu)化目標的精英蟻獅和輪盤賭蟻獅進行隨機游走，產(chǎn)生新的個體解.由此可得個體數(shù)是初始化種群的新螞蟻種群的m倍，將新螞蟻種群加入外部存檔，篩選保留存檔中的帕累托解作為新一代蟻獅.

通過偏好精英選擇機制，分別圍繞不同優(yōu)化目標上的最優(yōu)個體進行迭代更新，增強算法的尋優(yōu)性能；采用輪盤賭方法以較大概率選擇分布性較好的個體，并圍繞該個體進行搜索，使解的分布性更強.

2.3 SAMO 方法整體描述

SAMO 流程如圖8 所示.方法首先輸入元數(shù)據(jù)集；然后根據(jù)混合編碼機制初始化螞蟻種群；計算螞蟻的適應(yīng)度，通過帕累托支配關(guān)系從中選出帕累托解作為蟻獅保存至外部存檔；按照偏好精英選擇機制，從蟻獅中選出準確性和多樣性優(yōu)化目標上的精英個體，分別稱為準確性精英蟻獅和多樣性精英蟻獅，并計算蟻獅的稀疏度；在迭代過程中，每只初始化螞蟻根據(jù)蟻獅稀疏度進行2 次輪盤賭選擇蟻獅，圍繞準確性精英蟻獅和第1 次輪盤賭蟻獅，以及圍繞多樣性精英蟻獅和第2 次輪盤賭蟻獅，基于增強游走策略進行隨機游走，生成2 只新的螞蟻；計算新螞蟻種群的適應(yīng)度并將其加入存檔，更新存檔和精英蟻獅；最后，達到最大迭代時，輸出蟻獅構(gòu)建的集成元算法集合.在該過程中，個體的適應(yīng)度為集成元算法的準確性和多樣性指標值.

Fig.8 Process of SAMO圖8 SAMO 流程

SAMO 方法的偽代碼如算法1 所示.

算法1.SAMO 方法.

現(xiàn)對SAMO 的時間復(fù)雜度進行分析，設(shè)元特征數(shù)為M，基分類器個數(shù)為V，可得個體維度數(shù)D=M+3V+1；設(shè)種群規(guī)模為N，最大迭代次數(shù)為T，則螞蟻隨機游走進行迭代的時間復(fù)雜度為O（2N×D×T），計算解的支配關(guān)系和稀疏度的時間復(fù)雜度為O（N2×T）.綜上所述，SAMO 的時間復(fù)雜度為O（N×T×（N+2D））.

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

3.1 實驗設(shè)置

3.1.1 數(shù)據(jù)集

由于分類算法應(yīng)用的廣泛性，通過分類算法選擇問題進行測試實驗.實驗使用來自于UCI[32]，KEEL[33]，StatLib[34]，OpenML[35]的260 個分類數(shù)據(jù)集，這些數(shù)據(jù)集的數(shù)據(jù)來源領(lǐng)域各異，實例數(shù)從13～149 332 不等，屬性數(shù)從1～1 558 不等，類數(shù)從2～188 不等，具有一定的差異性，構(gòu)成多樣化的數(shù)據(jù)集，從而能夠有效評估方法的性能.實驗數(shù)據(jù)集信息如表2 所示.

表2（續(xù)）

Table 2 Information of Experimental Datasets表2 實驗數(shù)據(jù)集信息

3.1.2 元特征

通過元特征提取工具MFE[36]提取常用的150 種分類數(shù)據(jù)集元特征，包括77 種基于統(tǒng)計和信息論的元特征、24 種基于決策樹的元特征、14 種基于基準的元特征和35 種基于問題復(fù)雜度的元特征.元特征信息如表3 所示.

Table 3 Information of Meta-Features表3 元特征信息

3.1.3 候選算法

使用8 種sklearn[37]機器學(xué)習(xí)平臺的分類算法，包括kNN、RF、SVM、邏輯回歸（logistic regression，LR）、樸素貝葉斯（naive Bayes，NB）、線性判別分析（linear discriminant analysis，LDA）、ID3 決策樹和多層感知機（multi-layer perceptron，MLP），以及基于Keras[38]構(gòu)建的卷積神經(jīng)網(wǎng)絡(luò)（convolutional neural network，CNN）作為候選算法.基于sklearn 實現(xiàn)的算法均采用其默認參數(shù)設(shè)置，對于CNN，使用1 個含有32 個卷積核的1 維卷積層、1 個全連接層以及1 個最大池化層構(gòu)成其隱藏層，并設(shè)置其卷積層和全連接層使用ReLU（rectified linear unit）激活函數(shù)，輸出層使用softmax 激活函數(shù).

3.1.4 候選算法性能測度

使用準確率（Acc）、查準率（Pre）、查全率（Rec）、F1 得分（F1）和ARR（adjusted ratio of ratios）[39]指標測度并比較候選算法的性能.ARR指標綜合考慮算法的運行時間和準確率，其計算如式（27）（28）所示：

其中ai和aj表示候選算法，l為候選算法數(shù)，Acc和Rt表示算法在數(shù)據(jù)集上的準確率和運行時間；α為可變參數(shù)，表示準確率和運行時間的相對重要程度.實驗中ARR的 α值取研究中常用的0.1，0.01，0.001，并各自記為ARR1，ARR2，ARR3指標，以獲得較為全面的算法性能測度結(jié)果.

通過5 次10 折交叉驗證獲取候選算法在各數(shù)據(jù)集上的性能指標值，對指標值進行比較從而確定數(shù)據(jù)集的最優(yōu)算法，將最優(yōu)算法作為標簽與元特征結(jié)合，構(gòu)建相應(yīng)性能指標的元數(shù)據(jù)集.采用DAcc，DPre，DRec，DF1表示通過準確率、查準率、查全率和F1得分指標構(gòu)建的元數(shù)據(jù)集；使用DARR1，DARR2，DARR3分別表示通過ARR1，ARR2，ARR3指標生成的元數(shù)據(jù)集.此外，當(dāng)應(yīng)用基于回歸的元算法時，為各候選算法構(gòu)建單獨的元數(shù)據(jù)集，其中的元實例標簽為性能指標值，訓(xùn)練元算法預(yù)測各候選算法的性能指標值，比較預(yù)測值從而選出最優(yōu)算法.

3.1.5 對比方法

采用kNN，SVM，CART，SVR，RF，RFR，XGB，LGBM 作為元算法與SAMO 進行對比實驗.研究表明kNN 的距離度量采用歐氏距離，鄰居數(shù)k值位于元數(shù)據(jù)集實例數(shù)的10%～15%之間時，其表現(xiàn)更好[9,40].經(jīng)過對比擇優(yōu)，本文設(shè)置k=30，距離度量采用以距離倒數(shù)為權(quán)重的加權(quán)歐氏距離.除kNN 外，其他基分類器和元算法均采用sklearn 中的默認參數(shù)設(shè)置.

通過5 折交叉驗證，即將元數(shù)據(jù)集隨機劃為5 份，選擇其中4 份作為訓(xùn)練集，1 份為測試集，計算各方法的性能指標值.

3.2 元數(shù)據(jù)集分析

對構(gòu)建的7 個元數(shù)據(jù)集進行分析，候選算法在各元數(shù)據(jù)集中的勝出次數(shù)如表4 所示.

Table 4 Win Times of the Candidate Algorithms表4 候選算法勝出次數(shù)

從表4 可以看出，在本文的測試環(huán)境中，RF 具有較為優(yōu)越的分類性能，但是其在DARR1元數(shù)據(jù)集中的勝出次數(shù)較少，表明運行時間是其短板.與RF 相對的是kNN 和NB，得益于算法較快的運行速度，kNN和NB 在ARR指標上具備一定優(yōu)勢，但其分類性能較差，因此，隨著α值的減小，運行時間的重要性降低，kNN 和NB 在ARR指標元數(shù)據(jù)集中的勝出次數(shù)減少.相較于kNN 和NB，LR 的分類性能略優(yōu)但時間開銷更高，在7 個指標上的表現(xiàn)較為平庸.SVM 的分類性能較優(yōu)且具有合適的時間開銷，在7 個指標上均取得了較好結(jié)果.LDA 和ID3 展現(xiàn)了較好的分類性能，另一方面，LDA 和ID3 在ARR指標的元數(shù)據(jù)集中也取得了較多次數(shù)的勝出，說明其在運行時間和準確率上較為均衡.MLP 的分類性能具有一定優(yōu)勢，但其在各數(shù)據(jù)集上的運行時間較長，因此MLP 在ARR指標的元數(shù)據(jù)集中取得的勝出次數(shù)較少.CNN 的分類性能較弱且運行開銷較高，在7 個指標上的結(jié)果較差.

3.3 參數(shù)敏感性分析

為了確定合適的參數(shù)設(shè)置，本節(jié)設(shè)置種群規(guī)模N=50 和最大迭代次數(shù)T=300，對方法的關(guān)鍵參數(shù)，即基分類器個數(shù)V和多樣性指標DI進行敏感性分析.

為了便于說明，以DAcc元數(shù)據(jù)集為例，DI∈{QS,KS,CC,AM,DF}，V∈{10, 15, 20, 25, 30}，對方法獨立運行20 次的平均帕累托解數(shù)量和準確性精英蟻獅的ER平均值進行對比，結(jié)果分別如圖9 和圖10 所示.

Fig.9 Pareto solution numbers of different diversity indicators圖9 不同多樣性指標時的帕累托解數(shù)量

Fig.10 Error rates of different base classifier numbers圖10 不同基分類器個數(shù)時的錯誤率

觀察圖9 中的帕累托解數(shù)量，其在5 種多樣性指標上均呈現(xiàn)相同的變化趨勢，即隨著基分類器個數(shù)V的增加，帕累托解數(shù)量整體呈現(xiàn)出先增加后減少的趨勢，當(dāng)V=15 時，SAMO 在5 種DI上的帕累托解數(shù)量相對較多.另一方面，當(dāng)使用QS，KS，CC指標時，SAMO 產(chǎn)生的帕累托解數(shù)量較為接近，優(yōu)于AM和DF指標上的結(jié)果.

分析圖10 結(jié)果可以發(fā)現(xiàn)，隨著基分類器個數(shù)V的增加，SAMO 的ER性能在5 種多樣性指標上均呈現(xiàn)出先降低后提升的趨勢，當(dāng)基分類器個數(shù)V=15 時，5 種指標上的ER值取得最優(yōu)結(jié)果.此外，當(dāng)基分類器個數(shù)V相同時，5 種指標上的ER性能較為接近，其中AM指標上的整體表現(xiàn)優(yōu)于其他指標.

進一步分析圖9 和圖10，隨著V的增加，基分類器的多樣性得到提升，集成的效果變好；而當(dāng)V＞15 時，基分類器多樣性的提升有限，卻引入了部分準確性較差的基分類器，同時方法個體的搜索空間擴大，搜索效率降低，導(dǎo)致了方法性能的下降.

綜合上述結(jié)果，為了獲取具有較好算法選擇性能的集成元算法，設(shè)置基分類器個數(shù)V=15 較為合適，多樣性指標DI宜使用AM指標.

3.4 優(yōu)化算法效果驗證

對本文所提多目標混合蟻獅優(yōu)化算法、多目標蟻獅優(yōu)化（multi-objective ALO，MALO）[41]、第2 代非支配排序遺傳算法（non-dominated sorting genetic algorithm 2，NSGA2）[42]、速度約束多目標粒子群優(yōu)化（speed-constrained multi-objective particle swarm optimization，SMPSO）[43]以及第2 代強度帕累托進化算法（strength Pareto evolutionary algorithm 2，SPEA2）[44]的優(yōu)化性能進行比較，其中NSGA2，SMPSO，SPEA2基于框架jMetalPy[45]實現(xiàn).各對比算法均采用連續(xù)型編碼，設(shè)置閾值為0.5 對個體的元特征選擇編碼進行離散化.具體而言，設(shè)Ai為個體的第i維元特征選擇編碼，當(dāng)Ai≥0.5 時表示第i個元特征被選擇，Ai＜0.5 時表示未被選擇；在個體的選擇性集成編碼部分設(shè)置與本文算法相同的編碼和解碼方式.

設(shè)置基分類器個數(shù)V=15，多樣性指標DI為AM，算法種群規(guī)模N=50，最大迭代次數(shù)T=300，取算法獨立運行20 次的平均結(jié)果.對算法準確性最優(yōu)個體的ER值、多樣性最優(yōu)個體的DI值和帕累托解數(shù)量進行比較，結(jié)果如表5～7 所示.

Table 5 Error Rate Results of the Algorithms表5 各算法錯誤率結(jié)果%

從表5 和表6 可以看出，本文算法的準確性最優(yōu)個體和多樣性最優(yōu)個體分別可以取得最低的ER值和DI值，說明其尋優(yōu)性能優(yōu)于其他對比算法.對比MALO，NSGA2，SMPSO，SPEA2 的結(jié)果，不難發(fā)現(xiàn)MALO 的性能優(yōu)于另外3 種算法.

表7 中，本文算法可以產(chǎn)生較多的帕累托解數(shù)量，而其他算法的帕累托解數(shù)量較之有明顯的差距，進一步驗證了本文算法具有較強的尋優(yōu)性能.

使用非支配比率（non-dominance ratio，NR）[46]、超體積（hyper volume，HV）[47]和空間指標（spacing，SP）[48]，對各算法的解集質(zhì)量進行評估.NR將不同算法產(chǎn)生的多個解集合并為1 個解集并從中篩選出帕累托解構(gòu)成解集Sm，然后計算某一個解集中的解在Sm中所占的比例，比值越大說明該解集的質(zhì)量較之其他解集的質(zhì)量越優(yōu).HV計算解集與目標空間中的最差點所構(gòu)成空間的面積，ER和DI最差的指標值均為1，因此最差點為（1,1），HV值越大表示解集質(zhì)量越好.SP計算解集中相距最近的2 個解距離的標準差，其值越小代表解的分布性越好.各算法在NR，HV，SP上的比較結(jié)果如表8～10 所示.

Table 8 NR Results of the Algorithms表8 各算法NR 結(jié)果

對比表8 中的NR結(jié)果，相較于其他算法，本文算法有明顯的優(yōu)勢，展現(xiàn)了更強的收斂性.MALO可以搜索到本文算法所未能發(fā)現(xiàn)的帕累托解，具備一定的尋優(yōu)性能.NSGA2，SMPSO，SPEA2 在NR上的表現(xiàn)較差.

分析表9，所提算法在各元數(shù)據(jù)集上取得了最大的HV值，表明算法產(chǎn)生的解在目標空間中距離最差點較遠，解集的質(zhì)量高于其他算法.MALO 在個別元數(shù)據(jù)集上可以取得與本文算法相近的HV值，其性能優(yōu)于NSGA2，SMPSO，SPEA2.

表10 的結(jié)果顯示5 種算法在不同元數(shù)據(jù)集上具有較優(yōu)的SP值，其中本文算法和MALO 分別在部分元數(shù)據(jù)集上都取得了最優(yōu)結(jié)果，NSGA2，SMPSO，SPEA2 的結(jié)果較為接近.結(jié)合帕累托解數(shù)量結(jié)果，本文算法產(chǎn)生較多的帕累托解，同時可以保持較好的分布性.

Table 10 SP Results of the Algorithms表10 各算法SP 結(jié)果

綜合上述分析，在對算法選擇模型進行優(yōu)化時，相較于其他4 種算法，本文算法可以在2 個優(yōu)化目標上搜索到更優(yōu)解，并且可以發(fā)現(xiàn)數(shù)量更多且質(zhì)量更高的帕累托解，在收斂性和分布性上有較大的優(yōu)勢，說明本文算法在尋優(yōu)性能上具備優(yōu)越性.

3.5 SAMO 實驗結(jié)果

采用與3.4 節(jié)相同的方法參數(shù)設(shè)置，取SAMO 運行20 次所得的準確性精英蟻獅的性能均值進行對比，各方法的ER比較結(jié)果如表11 所示.

Table 11 ER Results of the Methods表11 各方法ER 結(jié)果%

對表11 進行分析，可以看出SAMO 在各元數(shù)據(jù)集上有更優(yōu)越的性能，其在除DPre外的其他元數(shù)據(jù)集上均取得了最好結(jié)果.kNN，SVM，CART 的性能較弱，SAMO 的性能明顯優(yōu)于這3 種元算法.SVR 預(yù)測各候選算法的性能指標值，比較預(yù)測值并選擇最優(yōu)算法，計算開銷較高，且其在ER指標上不具備性能優(yōu)勢.在集成方法中，除SAMO 外，RF 具有較好的性能，在各元數(shù)據(jù)集上均有較好的表現(xiàn)；RFR 結(jié)合集成和回歸方法，預(yù)測算法的性能指標值，其性能優(yōu)于SVR 但明顯劣于其他集成方法；XGB 在DRec元數(shù)據(jù)集上的性能強于RF，但是方法的整體性能不如RF；LGBM的整體表現(xiàn)并不突出，但其在DPre元數(shù)據(jù)集上取得了最優(yōu)結(jié)果.將SAMO 與平均性能排名第2 的RF 進行比較，SAMO 有著2.9%的平均性能領(lǐng)先，證明了SAMO 在ER指標上的優(yōu)越性.

進一步使用查準率、查全率和F1 得分指標比較方法性能，結(jié)果如表12～14 所示.

Table 12 Precision Results of the Methods表12 各方法查準率結(jié)果%

分析表12 查準率結(jié)果，SAMO 在5 個元數(shù)據(jù)集上均獲得了最好性能.kNN 和CART 在查準率指標上的表現(xiàn)明顯優(yōu)于SVM 和SVR.在除SAMO 外的集成方法中，RFR 的性能不如其他方法.RF，XGB，LGBM 的性能較優(yōu)，其中RF 在DPre元數(shù)據(jù)集上表現(xiàn)突出，XGB 在DRec元數(shù)據(jù)集上具有優(yōu)越性能.SAMO相較于kNN，SVM，CART，SVR 有較大程度的性能優(yōu)勢，其與RF 相比平均性能提升了2.5%，表明SAMO在查準率指標上具有優(yōu)越性.

表13 中，SAMO 在ARR指標的元數(shù)據(jù)集上取得了較好的查全率結(jié)果.CART 的查全率性能優(yōu)于kNN和SVM，SVR 的性能表現(xiàn)稍劣于SVM.RFR 的性能優(yōu)于CART，在DAcc上具有優(yōu)異表現(xiàn)，但是在其他元數(shù)據(jù)集上的表現(xiàn)一般.RF，XGB，LGBM 的查全率性能較好，其中XGB 在DRec，DF1，DARR2元數(shù)據(jù)集上以及LGBM 在DPre元數(shù)據(jù)集上表現(xiàn)優(yōu)異.SAMO 的性能相較于RF 平均領(lǐng)先了2.5%，相較于XGB 平均領(lǐng)先了0.5%，說明SAMO 在查全率指標上具備一定的有效性.

從表14 可以看出，SAMO 在各元數(shù)據(jù)集上的F1得分性能較好，在部分元數(shù)據(jù)集上取得了最好的結(jié)果.在kNN，SVM，CART 中，CART 的性能優(yōu)于kNN和SVM.SVR 與SVM 的性能較為接近，與其他方法的差距較大.RFR 的性能稍劣于CART，表現(xiàn)較為一般.RF，XGB，LGBM 具有較好的F1 得分性能，其中XGB 和LGBM 分別在不同元數(shù)據(jù)集上表現(xiàn)突出.SAMO的F1 得分優(yōu)于kNN，SVM，CART，另一方面，其相較于RF 性能平均提升了2.4%，與XGB 相比則性能平均提升了0.8%，驗證了SAMO 在F1 得分指標上的有效性.

將SAMO 與RF，RFR，XGB，LGBM 這4 種集成方法進行對比，SAMO 使用3 種基分類器進行選擇性集成，而其他方法僅使用CART 基學(xué)習(xí)器進行集成，SAMO 生成的集成元算法具有更強的多樣性.另一方面，在實驗測試中，SAMO 構(gòu)建的集成元算法在DAcc，DPre，DRec，DF1，DARR1，DARR2，DARR3上平均集成的基分類器數(shù)量分別為7.7，6.5，6.7，7.2，5.5，7.1，7.8，而其他方法固定使用100 個基學(xué)習(xí)器進行集成，由此可見SAMO 通過選擇性集成有效減少了基學(xué)習(xí)器的數(shù)量，從而降低集成元算法的存儲和運行開銷.

綜上所述，SAMO 選擇具有互補性的元特征子集，并使用不同類型的基分類器進行選擇性集成，生成具有較好算法選擇性能和多樣性的集成元算法.其在測試指標上的性能均明顯優(yōu)于kNN，SVM，CART，SVR 方法，而與RF，XGB 等采用同構(gòu)基學(xué)習(xí)器的集成方法相比，也具有相對優(yōu)越的性能表現(xiàn)，證明了SAMO 的有效性和優(yōu)越性.

4 結(jié) 論

為了提升基于元學(xué)習(xí)的算法選擇性能，提出基于多目標混合蟻獅優(yōu)化的算法選擇方法SAMO.設(shè)計算法選擇模型，引入元特征選擇和選擇性集成，同時尋找互補性較強的元特征子集和對多種元算法進行選擇性集成；提出多目標混合蟻獅優(yōu)化算法求解模型，使用混合編碼機制選擇元特征并構(gòu)建集成元算法，采用增強游走策略和偏好精英選擇機制提高尋優(yōu)性能.構(gòu)建分類算法選擇問題進行實驗測試，將SAMO 與8 種典型的元算法進行對比，結(jié)果顯示SAMO具有優(yōu)異的算法選擇性能，明顯優(yōu)于kNN，SVM，CART，SVR 元算法，較之RF，RFR，XGB，LGBM 這4 種集成元算法也有一定優(yōu)勢，并且具備更強的多樣性，綜合體現(xiàn)了SAMO 的有效性和優(yōu)越性.

未來的工作包括3 個方面：

1）由于算法選擇相關(guān)因素較多，問題較為復(fù)雜，因此目前本文所提方法SAMO 的效果有限，后續(xù)將深入研究數(shù)據(jù)集、元特征和元算法的內(nèi)在關(guān)系，對SAMO 進行改進，顯著提升算法選擇性能.

2）本文方法的時間復(fù)雜度較高，未來將通過并行計算、遷移學(xué)習(xí)等手段降低方法的訓(xùn)練開銷.

3）將SAMO 拓展應(yīng)用于實際工程，構(gòu)建算法選擇系統(tǒng).

作者貢獻聲明：李庚松提出方法設(shè)計，負責(zé)實驗方案的實現(xiàn)和論文內(nèi)容的撰寫；劉藝提出研究問題，梳理論文結(jié)構(gòu)；鄭奇斌整理論文內(nèi)容，負責(zé)實驗數(shù)據(jù)集的收集和處理；李翔參與方法的實驗結(jié)果分析；劉坤提出方法思路的改進建議；秦偉提出論文修改和優(yōu)化建議；王強負責(zé)實驗方案的實現(xiàn)指導(dǎo)；楊長虹給出完善論文整體框架的建議.