基于元學習推薦的優化算法自動選擇框架與實證分析

崔建雙,劉曉嬋,楊美華,李雯燕

北京科技大學 東凌經濟管理學院,北京 100083)(*通信作者電子郵箱cuijs@manage.ustb.edu.cn)

基于元學習推薦的優化算法自動選擇框架與實證分析

崔建雙*,劉曉嬋,楊美華,李雯燕

北京科技大學 東凌經濟管理學院,北京 100083)(*通信作者電子郵箱cuijs@manage.ustb.edu.cn)

算法選擇的目的是從眾多可用優化算法中自動地選出最適用于當前問題的算法。針對算法選擇問題提出了基于元學習推薦的優化算法自動選擇框架。依據此框架,以多模式資源受限的項目調度問題為實證數據集,設計實現了遺傳算法(GA)、粒子群算法(PSO)和模擬退火算法(SA)三種算法的自動選擇過程。從項目調度問題數據庫中隨機選取了378個問題算例,提取其中的固有特征和統計特征作為元數據,并利用前饋型神經網絡(FNN)算法訓練獲得用于預測的元模型對未見算例作出預測。實證結果表明兩選一的算法預測準確率最高可超過95%,交叉驗證準確率平均達到85%;三選一的算法預測準確率最高可達92%,交叉驗證準確率平均超過80%。實證結果驗證了所提算法選擇框架是成功的,基于元學習思想的優化算法自動選擇方法是可行的。

算法自動選擇;元學習;元模型;實證分析;預測準確率

0 引言

管理科學與工程領域圍繞著如何提高勞動生產效率、增強經濟效益等目標,對生產實際問題進行建模與優化。其中,大量的研究與實踐活動均可歸結為組合優化問題[1]。這類問題的主要特征是規模大、變量多,不一定能給出解析式,也不一定必須求得最優解[2]。因傳統運籌方法能力有限,故多采用啟發式或元啟發式算法加以解決。過去多年來,先后涌現出了遺傳[3]、模擬退火[4]、蟻群[5]、粒子群[6]、細菌覓食[7]、人工魚群[8]、混合蛙跳[9]、人工蜂群[10]、螢火蟲[11]、布谷鳥搜索[12]、蝙蝠[13]、蝦群覓食[14]、狼群[15]、獅群[16]等多種基于群集智能優化的元啟發式算法。這些算法具有廣泛的適用性和較高的搜索效率。但目前來看這類算法的內在運行機理仍不明朗,突出表現為應用效果明顯波動,對不同問題的自適應能力較差。為此,人們提出了各種改進措施:或者依賴特定的啟發式策略,或者引入各種拓撲結構或模因(memetic)模型,或者選擇不同的參數、嘗試各種混合策略,因而導致各種變形算法的“泛濫”。

依據沒有免費的午餐(No Free Lunch, NFL)定理[17]:不存在一個與具體應用無關的,普遍適用的“通用算法”能夠一勞永逸地解決所有優化問題。其深層的含意在于:在問題域的內在屬性特征與算法相對性能測度之間有可能存在某種內在關聯,關聯程度的高低決定著算法的應用效果。鑒于現實問題的復雜性和多樣性：一方面,人們針對所要解決的問題域的內在特征缺乏足夠的認知,算法的選擇具有主觀隨意性和盲目性;另一方面,人們對各種算法的適用范圍也缺乏足夠的經驗,直接拿來應用難免“取短舍長”。“算法過剩”與“算法濫用”困擾著領域知識的進一步發展。為此,亟須尋求一種 “超啟發式算法”,依據問題的屬性特征從“在線”的各種算法中自發地選擇最適用的算法或算法的組合,從而解決問題-算法之間低效率的盲目匹配這一明顯的“鴻溝”。

算法自動選擇(匹配)問題也是許多研究領域需要解決的NP難題[18]。在諸如人工智能、運籌學、管理科學與工程以及生物信息等學科領域,都有一大批復雜難解的問題處于開放(open)狀態,也都有一批類型和能力不同的算法可以在不同程度上解決這些問題,但又都令人難以滿意。所謂算法的自動選擇主要解決這樣一個問題:針對所要解決的問題,對于已知的可用算法,到底哪一個執行的效果最好?顯然,依次執行所有可供選擇的算法會過于消耗時間和資源;而通過專家經驗來選擇,則因缺乏可擴展性難以推廣，故有必要尋求更高效、更方便的算法選擇方法。

在機器學習領域,人們基于元學習思想研究如何從大量的數據中尋找規律,進行分類并作出新的行為預測或判斷。可以設想,若以已有的大量問題數據集為依托,通過提取它們的關鍵特征,并利用元學習方法建立關鍵特征與不同優化算法性能測度之間的映射模型,則有可能預測出適用于此類問題的優化算法,從而達到問題-算法最佳匹配的目的。

本文以在人工智能領域著名的NFL定理[17]和丑小鴨(Ugly Duckling, UD)定理[19]為理論依據,首先提出并證明了組合優化問題算法選擇定理,明確肯定了:若給定條件滿足,在多個優化算法中必定有一個最適用于給定問題的算法，其意義在于為進一步開展問題-算法匹配的研究奠定理論基礎。然后結合元啟發式優化算法的特點,以Rice抽象概念圖[20]為基礎,以元學習算法為工具,提出了一種優化算法自動選擇框架。最后以多模式資源受限項目調度問題(Multi-mode Resource Constrained Scheduling Problem, MRCPSP)[21]作為驗證數據集,選取了三種元啟發式算法(遺傳、粒子群和模擬退火)對所設計的算法自選擇框架進行實證分析。結果表明,算法的自動選擇過程是成功的,結果是可接受的。取三種算法兩兩比較,能夠以達到95%的準確率預測出最佳算法,交叉驗證的平均準確率也達到了85%；若三種算法同時作出比較,平均預測準確率也達到了80%。

1 算法選擇問題

1.1 研究現狀

算法選擇問題在不同研究領域有不同的表述和側重點[18]，如超啟發式算法[22]、算法自動選擇[23]、算法自適應匹配、算法推薦[24]等。20世紀80年代末,有學者意識到算法選擇過程實際上可看成是一種學習過程[25]。于是,算法選擇問題在機器學習領域成為一個研究熱點,并逐漸發展形成了元學習思想[26-28]。一般的學習是指通過學習建立有關對象的知識,而元學習是對學習過程的學習,通過探查學習過程的機理,不斷地完善自我學習過程。其主要過程是通過對學習算法的屬性或所學問題特征的分析,建立靈活的自我學習機器[29-30]。元建模則通過建立反映輸入與輸出之間關系的數學模型來擬合或代理樣本數據。常見的元建模方法包括多項式回歸、高斯過程回歸、支持向量回歸、徑向基函數、多元適應性回歸樣條和人工神經網絡等。這些方法大多依賴于統計樣本數據來構建模型,故又稱為無分布統計方法。

20世紀90年代初,歐洲開展了大型分類算法比較項目[31],其主要目標是比較機器學習、神經網絡和統計學方法等在不同問題上的性能,并通過研究數據集特征與算法性能表現之間的聯系獲取關于算法選擇的知識。為了簡化問題的處理,Pfahringer等[32]提出了地標策略。在大型分類算法比較項目研究基礎上,歐洲一些國家繼續資助了一些基于該研究成果的算法選擇研究項目。Rice[20]在其具有開創性的文獻中給出了算法選擇問題的概念圖。Rendell等[33]提出了一種描述分類問題特征的方法,并利用問題規模和分類的集中特征驗證了對算法行為產生的影響。Aha[34]把這一思路拓展到基于規則的學習算法,即如果給定的數據集具備C1,C2,…,Cn的特征,則選用算法A而不是算法B。Smith-Miles[35]曾提出基于元學習思想不同學科領域實現算法選擇的統一框架。Misir[36]證實了機器學習用于算法選擇的效果。Messelis等[37]研究了基于實證難度模型的多模式資源受限項目調度問題的自動算法推薦。Vilalta等[38]曾利用元學習方法解決了一種隨時間改變的動態數據的算法推薦問題。Miranda等[39]提出了基于元學習框架的支持向量機改進模型。Smith-Miles等[40]量化了組合優化問題一般特征和部分組合優化問題的特定特征。Leyva等[41]提出了一種基于知識的算例選擇系統,該系統使用元學習思想從多種可用算法中,為每一個專用數據庫選擇最適用的算例選擇算法。Bhatt等[42]對當前基于數據集特征的元學習方法所面臨的挑戰進行了綜述。Lemke等[43]對于元學習及其未來發展趨勢進行了文獻述評。

綜上所見,算法選擇問題一直是相關領域關注的焦點,研究的重點在于如何實現最適用算法的自動選擇。

1.2 相關理論

基于元學習思想的算法選擇通過改善學習算法的學習行為來處理算法的選擇問題，本質上是從大量的問題實例所具有的潛在結構特征中,獲得有價值的信息用于對新實例的行為作出預測判斷。構成元知識的元特征和元目標分別來自于數據集以及對算法性能指標的估值或排序。需要探究的是問題的元特征與算法的性能表現之間存在著怎樣的關系,如何利用學習過程逐漸積累的知識建立起完善的元模型,并用于對未來新問題的算法選擇。

為了擁有充分的理論依據,本文基于兩個著名的定理針對組合優化問題提出了一個關于優化算法選擇定理。

引理1 若一個組合優化問題具有可行解,則該問題至少有一個最優解。

證明 因該組合問題具有可行解,故在滿足給定約束條件下,經有窮次搜索之后,可找到全部可行解,最優解必包含在其中。

Rice抽象概念圖定義[20]:問題的特征屬性和算法性能測度之間存在著關聯，因而算法選擇過程可以歸納為一個形式化的抽象模型,如圖1所示。對于給定問題實例x∈P,若其特征為f(x)∈F,則找到選擇映射α=S(f(x))→A,可使得所選算法α∈A最大化性能y(α(x))∈Y。在本文論域內,四元組〈P,A,F,Y〉被視為元數據。

圖1 Rice算法選擇抽象概念圖

定理1NFL定理[17]。在有限搜索空間內,由于對所有可能函數的相互補償,最優化算法的性能是等價的,即沒有其他任何算法能夠比搜索空間的線性列舉或者純隨機搜索算法更優。NFL定理的意義在于:當明確表明一個算法比另一個算法“更好”時,只是針對具有特定特征的問題或者特定的先驗信息、數據分布、訓練樣本的數目、代價或獎勵函數等。

定理2UD定理[22]。“丑小鴨與白天鵝之間的區別和兩只白天鵝之間的區別一樣大”。該定理引申的含義表明:世界上不存在分類的客觀標準,一切分類的標準都是主觀的。分類的結果取決于選擇哪些特征作為分類標準,而特征的選擇又依存于分類的目的。

推論1 由定理1,任何優化算法都有局限性,即:局限于某個問題,或者局限于某個領域,或者局限于某種特性。

推論2 算法優劣的比較只能在明確界定的特定范圍內才有意義。

組合優化問題算法選擇定理:若一個組合優化問題具有可行解,且該問題特征屬性的選擇偏好明確可析,則針對該問題至少存在一個優化算法能夠取得最佳匹配。換句話說,在多個優化算法中必定有一個最適用于求解該問題的算法。

證明 由引理1,該問題至少有一個最優解。因該問題的特征屬性的選擇偏好明確可析,故由定理1,不管采用何種算法,則至少存在一個目標函數,能夠使得其中一個算法效果最佳;由定理2,當把優化算法的選擇看作是對算法作出的分類,則針對該問題的最佳算法取決于特征屬性的選擇偏好以及對目標函數的指定。再由Rice抽象概念圖定義,為了選擇適合給定問題的最佳算法,不但需要獲取問題的特征屬性,還要考慮對于特定問題域,哪些特征屬性與算法的性能相關。

組合優化問題算法選擇定理表明,當明確定義了問題域的特征屬性并且建立起與算法相對性能測度之間的關系模型時,就能夠針對所要解決的問題選擇出最佳算法。

2 組合優化問題算法自動選擇框架

依照Rice概念圖和元學習方法,本文提出了組合優化問題算法自動選擇框架,如圖2所示。按照該框架,算法的選擇過程如下:首先提取問題數據集的元特征,形成反映問題特征的元數據;然后把各候選算法應用到問題數據集,依據算法性能測度指標評估各算法的相對性能,形成關于算法優劣的基礎元數據;接著采用適當的元學習方法對基礎元數據進行元學習,以獲取問題元特征與算法相對性能測度間對應的元模型,用于對未見數據集作算法匹配預測,按照匹配程度的高低從中選擇最適用的算法。

圖2 組合優化問題算法自動選擇框架

圖2表明,基于元學習推薦的算法自動選擇過程需要實現以下幾個步驟:1)收集并整理問題數據集;2)定義并提取問題數據集特征;3)確定參與自動選擇的優化算法及其性能評價指標;4)選擇元學習算法訓練問題數據集,得到元模型;5)把元模型用于新數據集的預測,驗證準確率并作出評價。

3 算法選擇實證分析

3.1 問題數據集的選取

MRCPSP是在資源約束的項目調度問題(Recourse-ConstrainedProjectSchedulingProblem,RCPSP)基礎上增加活動多模式以及若干種不可更新資源而形成的一類資源約束項目調度問題。經多年研究已經產生了許多求解方法和典型的標桿算例庫[21,44],為不同方法的優劣比較提供參考標準。

本文從算例庫中選出活動規模分別為0、12、14、16、18、20和30,每一活動有3種執行模式的標桿算例庫中隨機選取了378個算例作為實證分析的基本數據集。

3.2 數據集元特征的提取

元特征提取的基本要求是盡量與元啟發式算法的性能相關,盡量降低提取過程的計算復雜度。具有代表性的數據集特征大致可以分為3類[18]:1)基于統計和信息論的元特征;2)基于基準算法的元特征;3)基于模型的元特征。

對于MRCPSP來說,網絡復雜度系數、資源系數、資源強度、次序強度等是其基本的固有特征。但是因所選取問題的結構性質相近,特征值差別很小,故不能充分反映此類問題的性能特征,也不能保證與優化算法的性能測度強相關。為此,本文結合特征分類方法進一步選取了一系列其他相關特征。表1列出了所選中3組共38個特征。其中,固有特征20個,統計特征5個,目標函數值特征13個。

表1 MRCPSP可選特征列表

3.3 優化算法的設計與實現

遺傳算法、粒子群算法和模擬退火算法三種算法性能相近且都具有魯棒性和并行搜索等優點，如果能夠在性能相近的算法中區分出優劣,則更能說明所設計的自動算法選擇方法的有效性。三種算法中針對MRCPSP的調度排序均采用雙維編碼[45],第一維代表活動模式,第二維代表活動的優先權值。下面給出了一個具有10個活動,每一活動有三種模式的項目調度問題編碼實例:

第一維(活動模式): 131232123121

第二維(優先級): 135211486710912

1)遺傳算法的設計。

首先隨機產生種群規模為30的一組雙維染色體編碼,然后開始300輪迭代。每一輪迭代過程都分別對雙維編碼作隨機單點交叉和變異。交叉概率0.7,變異概率0.01,采用歸一化幾何輪盤賭策略,從新生染色體中選擇下一代。

2)粒子群算法的設計。

首先隨機產生規模為30的一組雙維粒子群編碼,接著開始300輪迭代。每一輪迭代依據標準粒子群算法計算公式更新粒子的速度和位置。學習因子c1、c2分別是0.8和0.7,慣性權重w=0.93-0.3×Iter/MaxIter(其中:Iter為當前迭代次數，MaxIter為最大迭代次數)隨迭代次數不斷下降[45]。

3)模擬退火算法的設計。

首先隨機產生30組雙維編碼調度,從中選擇一個最好的解作為初始解。給定最大鄰域解數量60,對初始解作隨機2-opt交換,產生60個鄰域解。每次都以最佳鄰域解作為當前最優解,若未產生更好的解則按照轉移概率接受劣解,通過內外循環迭代,逐漸降溫。算法參數設定如下:初始溫度設定為Tk=500;內循環最大迭代次數ILk=300; 外循環最大迭代次數OLk=300;降溫系數λ=0.99;轉移概率遵從Metropolis準則。

3.4 優化算法的性能測度指標

優化算法性能測度指標既能夠充分測度出算法的性能表現同時又不會消耗過多的時間。本文設計的指標包括運行效率(時間)以及目標值與最優值之間的偏差。由于僅需比較算法的相對性能優劣,故把各算法的運行時間限定為60s,記錄算法在運行結束時的結果,包括偏差和結束時間。每一算法運行5次取平均值。

算法優劣的比較原則如下:先比較偏差,偏差小的算法較優;若偏差相等再比較運行時間,時間短的算法較優。最終得到的是三種元啟發式算法的相對優劣排序,以1、2、3作出標號。

綜合上述過程,得到378行×39列的算例數據集特征矩陣。其中：378行代表378個算例,前38列對應38個特征值,第39列對應1、2、3數值標號,標出最適于該算例的算法。

3.5 元學習訓練過程

問題可測特征與算法性能測度之間的映射關系,體現在二者之間通過大量數據的訓練而獲得的訓練模型。本文采用基于模型的元學習方法——前饋型神經網絡(FeedforwardNeuralNetwork,FNN)算法對元數據進行訓練學習。FNN算法假定在問題元特征與算法性能排序之間存在一個可經樣本數據進行訓練的潛在模型。按照誤差逆傳播算法訓練多層前饋網絡,由信息的正向傳播和誤差的反向傳播兩個過程組成。首先將數據輸入計算出一個輸出,然后與實際輸出比較,完成一次學習的正向傳播處理過程;當實際輸出與期望輸出不符時誤差反傳,通過不斷調整權值和閾值,使誤差平方和最小。本文直接采用了Matlab2016b人工神經網絡工具箱提供的FNN函數來運行算例數據。輸入層共有38個神經元,代表38個問題特征;隱含層選擇10、15、20,激活函數采用radbas、logsig、tansig三者之一自動優選。不同神經元數量、隱含層個數、使用的激活函數對訓練結果有不同影響。為了遴選出最佳隱含層和激活函數,把隱含側和激活函數二者交叉形成9種組合,每種組合單獨獲取訓練模型,比較篩選出具有最小均方根差的訓練模型作為最佳模型。基于前饋神經網絡元學習算法的優化算法選擇流程如下:

START: 給定訓練算例x∈P,測試算例xnew∈P;元學習算法t∈T;元啟發式算法集合α∈A;算法性能測度集y∈Y。

Step1 執行所有算例問題特征的提取f(x);

Step2 對x∈P,執行?α∈A,找到各算法依據性能測度集y∈Y的排序,使得y(αk-1(x))≥y(αk(x));

Step3 執行元學習算法t∈T,使得訓練數據的預測結果的均方根差最小,獲得元模型(Metamodel);

Step4 利用元模型對xnew作出預測,推薦αbest=Model(xnew)。

3.6 實證結果分析

通過提取MRCPSP數據集特征和3個算法的性能測度值,得到了378行×39列的原始特征與預測目標值對應的矩陣,然后利用前饋人工神經網絡算法對該目標進行預測計算。378個算例按照測試算例個數/訓練算例個數的既定比例,隨機拆分為訓練組和測試組,訓練組用于訓練獲得元模型,測試組用于驗證模型的預測準確率。預測準確率定義為:元模型預測值減去性能測度數值標號(第39列)出現0的個數與測試算例的總個數之比,即被準確預測的算法占總測試算例數量的百分比。

平均準確率是指作10次隨機交叉驗證后得到的準確率或稱命中率(Hitrate)的平均值。表2列出了GA、PSO和SA三種算法兩兩之間進行比較的結果。從結果看，兩選一的算法預測準確率最高可超過95%，交叉驗證準確率平均達到85%。隨著測試算例/訓練算例比值的上升,準確率略有下降,這說明減少訓練算例的占比會影響到預測準確率。若三種算法同時參與比較,預測準確率最高可達92%,交叉驗證準確率平均為80%。可見,增加參與比較的優化算法數量也會降低預測準確率。

表2 算法二選一的選擇結果

注:交叉驗證數次均為10。

經驗表明,在求解Benchmark問題過程中經常出現的情況是:一個算法用于其中多數算例會得到很好的結果,但是其中總是有一小部分算例的結果不能令人滿意;而當換用另外一個算法時,會有另一小部分算例的結果表現不好。本文方法能夠針對當前算例自動地推薦一個較好的算法,從而避免了盲目的算法使用,可以顯著地改變計算效率,提高解決問題的總體表現。

4 結語

元學習概念最早源于人工智能領域的機器學習理論,用于探究學習過程和學習機制,以便于改進或調整學習效果,其目標是把問題的元特征與元模型關聯起來,構建自適應的自動學習機制。本文把這一理念引入到元啟發式算法的自動選擇過程中,為解決現實中“問題-算法”之間盲目或者低效率匹配這一矛盾嘗試了一條新的思路。

本文以資源約束項目調度問題為驗證數據集,依照設計的算法自動選擇框架對三種優化算法的選擇進行了實證分析,取得了初步成果。從預測準確率來看,基于元學習推薦的算法自動選擇這一設想仍值得進一步的深入研究。下一步的工作包括:進一步提升數據集元特征提取的精準度,尋找那些更能夠反映數據集本質特征的數據;進一步探索算法的性能測度表現與問題元特征之間的關聯關系。除了關注問題特征之外,對于算法性能的評測標準目前主要集中在時間和準確率上,下一步將嘗試從多維角度對算法性能進行評測,例如,對評測指標分配不同的權重。現實中有許多具有NP難特性的組合優化問題,本文所嘗試的這一研究路線完全適用于任何類似問題的算法自動選擇過程。

)

[1]HILLIERFS,LIEBERMANGJ.IntroductiontoOperationsResearch[M]. 9thed.NewYork:McGraw-Hill, 2014:12-17.

[2] 汪定偉, 王俊偉, 王洪峰, 等. 智能優化方法 [M]. 北京: 高等教育出版社, 2007: 1-9.(WANGDW,WANGJW,WANGHF,etal.IntelligentOptimizationMethod[M].Beijing:HigherEducationPress, 2007:1-9).

[3]HOLLANDJH.AdaptationinNaturalandArtificialSystems[M].AnnArbor:UniversityofMichiganPress, 1975: 22-30.

[4]KIRKPATRICKS,GELATTJR,VECCHIMP.Optimizationbysimulatedannealing[J].Science, 1983, 220(4598): 671-680.

[5]COLORNIA,DORIGOM,MANIEZZOA.Distributedoptimizationbyantcolonies[EB/OL]. [2016- 03- 01].http://faculty.washington.edu/paymana/swarm/colorni92-ecal.pdf.

[6]KENNEDYJ,EBERHARTR.Particleswarmoptimization[C]//Proceedingsofthe1995IEEEInternationalConferenceonNeuralNetworks.Piscataway,NJ:IEEE, 1995: 1942-1948.

[7]PASSINOKM.Biomimicryofbacterialforagingfordistributedoptimizationandcontrol[J].IEEEControlSystemsMagazine, 2002, 22(3): 52-67.

[8] 李曉磊, 邵之江, 錢積新. 一種基于動物自治體的尋優模式:魚群算法 [J]. 系統工程理論與實踐, 2002, 22(11): 32-38.(LIXL,SHAOZJ,QIANJX.Anoptimizingmethodbasedonautonomousanimats:fish-swarmalgorithm[J].SystemEngineering&TheoryPractice, 2002, 22(11):32-38.)

[9]EUSUFFM,LANSEYK.Optimizationofwaterdistributionnetworkdesignusingtheshuffledfrogleapingalgorithm[J].JournalofWaterResourcesPlanningandManagement, 2003, 129(3): 210-215.

[10]KARABOGAD.Anideabasedonhoneybeeswarmfornumericaloptimization[R].Kayseri,Turkiye:ErciyesUniversity, 2005.

[11]XINSHEY.Nature-inspiredmetaheuristicalgorithms[M].London:LuniverPress, 2008: 38-50.

[12]XINSHEY.Cuckoosearchvialevyflights[C]//NaBIC2009:Proceedingsofthe2009WorldCongressonNature&BiologicallyInspiredComputing.Piscataway,NJ:IEEE, 2009: 210-214.

[13]XINSHEY,GANDOMIAH.Batalgorithm:anovelapproachforglobalengineeringoptimization[J].EngineeringComputations, 2012, 29(5): 464-483.

[14]GANDOMIAH,ALAVIAH.Krillherd:anewbio-inspiredoptimizationalgorithm[J].CommunicationsinNonlinearScienceandNumericalSimulation, 2012, 17(12): 4831-4845.

[15]TANGR,FONGS,YANGX,etal.Wolfsearchalgorithmwithephemeralmemory[C]//ProceedingsoftheSeventhInternationalConferenceonIEEEDigitalInformationManagement.Piscataway,NJ:IEEE, 2012: 165-172.

[16]YAZDANIM,JOLAIF.LionOptimizationAlgorithm(LOA):anature-inspiredmetaheuristicalgorithm[J].JournalofComputationalDesignandEngineering, 2016, 3(1): 24-36.

[17]WOLPERTDH,MACREADYWG.Nofreelunchtheoremsforoptimization[J].IEEETransactionsonEvolutionaryComputation, 1997, 1(1): 67-82.

[18] 曾子林, 張宏軍, 張睿. 基于元學習思想的算法選擇問題綜述 [J]. 控制與決策, 2014,29(6): 961-968.(ZENGZL,ZHANGHJ,ZHANGR.Summaryofalgorithmselectionbasedonmeta-learning[J].ControlandDecision, 2014,29(6): 961-968.)

[19]CRUZ-REYESL,GMEZ-SANTILLNC,PéREZ-ORTEGAJ.Algorithmselection:frommeta-learningtohyper-heuristics[EB/OL]. [2016- 03- 01].http://cdn.intechweb.org/pdfs/30653.pdf.

[20]RICEJR.Thealgorithmselectionproblem[J].AdvancesinComputation, 1976, 15: 65-118.

[21]JOSéC,MARIOV.Multi-moderesource-constrainedprojectschedulingusingRCPSPandSATsolvers[J].EuropeanJournalofOperationalResearch, 2011, 213(1): 73-82.

[22]WATANABES.KnowingandGuessing:AQuantitativeStudyofInferenceandInformation[M].NewYork:Wiley, 1969: 376-377.

[23]SONGQB,WANGGT,WANGC.Automaticrecommendationofclassificationalgorithmsbasedondatasetcharacteristics[J].PatternRecognition, 2012, 45(7): 2672-2689.

[24]CANC,MENGQIH,JEFFERYDW,etal.Arecommendationsystemformeta-modeling:ameta-learningbasedapproach[J].ExpertSystemswithApplications, 2016, 46: 33-44.

[25]BRODLEYCE.Recursiveautomaticbiasselectionforclassifierconstruction[J].MachineLearning, 1995, 20(1): 63-94.

[26]DESOUZABF,CARVALHOD,SOARESC.Metalearningforgeneexpressiondataclassification[C]//HIS2008:Proceedingsof2008EighthInternationalConferenceonHybridIntelligentSystems.Piscataway,NJ:IEEE, 2008: 441-446.

[27]LANZ,GUJ,ZHENGZ.Astudyofdynamicmeta-learningforfailurepredictioninlarge-scalesystems[J].JournalofParallelandDistributedComputing, 2010, 70(6): 630-643.

[28]ZHOUS,LAIKK,YENJ.Adynamicmeta-learningrate-basedmodelforgoldmarketforecasting[J].ExpertSystemswithApplications, 2012, 39(6): 6168-6173.

[29]GIRAUD-CARRIERC.Metalearning—atutorial[EB/OL]. [2016- 03- 10].https://pdfs.semanticscholar.org/5794/1a4891f673cadf06fba02419372aad85c3bb.pdf.

[30]ROSSIALD,CARVALHOA,SOARESC,etal.Meta-stream:ameta-learningbasedmethodforperiodicalgorithmselectionintime-changingdata[J].Neurocomputing, 2014, 127: 52-64.

[31]KINGRD,FENGC,SUTHERLANDA.STATLOG:comparisonofclassificationalgorithmsonlargereal-worldproblems[J].AppliedArtificialIntelligence, 1995, 9(3): 289-333.

[32]PFAHRINGERB,BENSUSANH,GARRIERCG.Meta-learningbylandmarkingvariouslearningalgorithms[C]//ICML2000:ProceedingsoftheSeventeenthInternationalConferenceonMachineLearning.SanFrancisco:MorganKaufmannPublishers, 2000: 743-750.

[33]RENDELLL,CHOH.Empiricallearningasafunctionofconceptcharacter[J].MachineLearning, 1990, 5(3): 267-298.

[34]AHAD.Generalizingfromcasestudies:acasestudy[C]//ICML1992:Proceedingsofthe9thInternationalConferenceonMachineLearning.SanFrancisco:MorganKaufmannPublishers, 1992: 1-10.

[35]SMITH-MILESKA.Cross-disciplinaryperspectivesonmeta-learningforalgorithmselection[J].ACMComputingSurveys, 2008, 41(1):1-25.

[36]MISIRM.Intelligenthyper-heuristics:atoolforsolvinggenericoptimizationproblems[D].Flanders,Belgium:KatholiekeUniversiteitLeuven, 2012.

[37]MESSELIST,CAUSMAECKERPD.Anautomaticalgorithmselectionapproachforthemulti-moderesource-constrainedprojectschedulingproblem[J].EuropeanJournalofOperationalResearch, 2014, 233(3): 511-528.

[38]VILALTAR,DRISSIY.Aperspectiveviewandsurveyofmeta-learning[J].ArtificialIntelligenceReview, 2002, 18(2): 77-95.

[39]MIRANDAPBC,PRUDENCIORBC,CARVALHOA,etal.Ahybridmeta-learningarchitectureformulti-objectiveoptimizationofSVMparameters[J].Neurocomputing, 2014, 143: 27-43.

[40]SMITH-MILESK,LOPESL.Measuringinstancedifficultyforcombinatorialoptimizationproblems[J].Computers&OperationsResearch, 2012, 39(5): 875-889.

[41]LEYVAE,CAISESY,GONZLEZA,etal.Ontheuseofmeta-learningforinstanceselection:anarchitectureandanexperimentalstudy[J].InformationSciences, 2014, 266: 16-30.

[42]BHATTN,THAKKARA,GANATRAA.Asurvey¤tresearchchallengesinmeta-learningapproachesbasedondatasetcharacteristics[J].InternationalJournalofSoftComputingandEngineering, 2012, 2(1): 239-247.

[43]LEMKEC,BUDKAM,GABRYSB.Meta-learning:asurveyoftrendsandtechnologies[J].ArtificialIntelligenceReview, 2015, 44(1):117-130.

[44]KOLISCHR,SPRECHERA.PSPLIB—aprojectschedulingproblemlibrary[J].EuropeanJournalofOperationalResearch, 1996, 96(1): 205-216.

[45] 陳龍, 韓兆蘭, 崔建雙. 求解多模式資源約束的項目調度問題的離散粒子群算法 [J]. 計算機應用, 2015, 35(增刊2):101-105.(CHENL,HANZL,CUIJS.Discreteparticleswarmoptimizationforsolvingmulti-moderesource-constrainedprojectschedulingproblem[J].JournalofComputerApplications, 2015, 35(Suppl2):101-105.)

ThisworkispartiallysupportedbytheNationalNaturalScienceFoundationofChina(71471016).

CUI Jianshuang, born in 1961, Ph. D., associate professor. His research interests include project scheduling, intelligent optimization algorithms.

LIU Xiaochan, born in 1993, M. S. candidate. His research interests include data mining.

Meta-learning based optimization algorithm selection framework and its empirical study

CUI Jianshuang*, LIU Xiaochan, YANG Meihua, LI Wenyan

(Donlinks School of Economics and Management,University of Science and Technology Beijing, Beijing 100083, China)

The goal of algorithm selection is to automatically select the best suitable algorithm for current problem from a batch of available algorithms. For this purpose, an intelligent recommendation framework based on meta-learning approach was presented. The automatic selection procedure for Genetic Algorithm (GA), Particle Swarm Optimization (PSO) and Simulated Annealing (SA) was designed according to this framework by using Multi-mode Resource-Constrained Project Scheduling Problem (MRCPSP) as the validation data set. Three hundred and seventy-eight instances of MRCPSP were randomly picked out from the Project Scheduling Problem Library (PSPLib), and the inherent and statistic features of each instance were extracted and used as the metadata, then the prediction meta-model for new examples was obtained by using Feed-forward Neural Network (FNN) algorithm. The empirical results demonstrate that the hit rate reaches 95% at most, and the average hit rate is 85% when choosing one algorithm from two ones; the best hit rate reaches 92% and 80% respectively when choosing one algorithm from three ones. The proposed intelligent recommendation framework is successful and the automatic selection for optimization algorithms is feasible.

algorithm automatic selection; meta-learning; meta model; empirical study; hit rate

2016- 08- 31;

2016- 12- 29。 基金項目:國家自然科學基金資助項目(71471016)。

崔建雙(1961—),男,河北衡水人,副教授,博士,主要研究方向:項目優化調度、智能優化算法; 劉曉嬋(1993—),女,河北石家莊人,碩士研究生,主要研究方向:數據挖掘。

1001- 9081(2017)04- 1105- 06

10.11772/j.issn.1001- 9081.2017.04.1105

TP181

A