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

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

基于元學(xué)習(xí)推薦的優(yōu)化算法自動選擇框架與實證分析

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

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

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

算法自動選擇;元學(xué)習(xí);元模型;實證分析;預(yù)測準(zhǔn)確率

0 引言

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

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

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

在機器學(xué)習(xí)領(lǐng)域,人們基于元學(xué)習(xí)思想研究如何從大量的數(shù)據(jù)中尋找規(guī)律,進(jìn)行分類并作出新的行為預(yù)測或判斷?？梢栽O(shè)想,若以已有的大量問題數(shù)據(jù)集為依托,通過提取它們的關(guān)鍵特征,并利用元學(xué)習(xí)方法建立關(guān)鍵特征與不同優(yōu)化算法性能測度之間的映射模型,則有可能預(yù)測出適用于此類問題的優(yōu)化算法,從而達(dá)到問題-算法最佳匹配的目的。

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

1 算法選擇問題

1.1 研究現(xiàn)狀

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

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

綜上所見,算法選擇問題一直是相關(guān)領(lǐng)域關(guān)注的焦點,研究的重點在于如何實現(xiàn)最適用算法的自動選擇。

1.2 相關(guān)理論

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

為了擁有充分的理論依據(jù),本文基于兩個著名的定理針對組合優(yōu)化問題提出了一個關(guān)于優(yōu)化算法選擇定理。

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

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

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

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

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

定理2UD定理[22]?！俺笮▲喤c白天鵝之間的區(qū)別和兩只白天鵝之間的區(qū)別一樣大”。該定理引申的含義表明:世界上不存在分類的客觀標(biāo)準(zhǔn),一切分類的標(biāo)準(zhǔn)都是主觀的。分類的結(jié)果取決于選擇哪些特征作為分類標(biāo)準(zhǔn),而特征的選擇又依存于分類的目的。

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

推論2 算法優(yōu)劣的比較只能在明確界定的特定范圍內(nèi)才有意義。

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

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

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

2 組合優(yōu)化問題算法自動選擇框架

依照Rice概念圖和元學(xué)習(xí)方法,本文提出了組合優(yōu)化問題算法自動選擇框架,如圖2所示。按照該框架,算法的選擇過程如下:首先提取問題數(shù)據(jù)集的元特征,形成反映問題特征的元數(shù)據(jù);然后把各候選算法應(yīng)用到問題數(shù)據(jù)集,依據(jù)算法性能測度指標(biāo)評估各算法的相對性能,形成關(guān)于算法優(yōu)劣的基礎(chǔ)元數(shù)據(jù);接著采用適當(dāng)?shù)脑獙W(xué)習(xí)方法對基礎(chǔ)元數(shù)據(jù)進(jìn)行元學(xué)習(xí),以獲取問題元特征與算法相對性能測度間對應(yīng)的元模型,用于對未見數(shù)據(jù)集作算法匹配預(yù)測,按照匹配程度的高低從中選擇最適用的算法。

圖2 組合優(yōu)化問題算法自動選擇框架

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

3 算法選擇實證分析

3.1 問題數(shù)據(jù)集的選取

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

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

3.2 數(shù)據(jù)集元特征的提取

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

對于MRCPSP來說,網(wǎng)絡(luò)復(fù)雜度系數(shù)、資源系數(shù)、資源強度、次序強度等是其基本的固有特征。但是因所選取問題的結(jié)構(gòu)性質(zhì)相近,特征值差別很小,故不能充分反映此類問題的性能特征,也不能保證與優(yōu)化算法的性能測度強相關(guān)。為此,本文結(jié)合特征分類方法進(jìn)一步選取了一系列其他相關(guān)特征。表1列出了所選中3組共38個特征。其中,固有特征20個,統(tǒng)計特征5個,目標(biāo)函數(shù)值特征13個。

表1 MRCPSP可選特征列表

3.3 優(yōu)化算法的設(shè)計與實現(xiàn)

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

第一維(活動模式): 131232123121

第二維(優(yōu)先級): 135211486710912

1)遺傳算法的設(shè)計。

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

2)粒子群算法的設(shè)計。

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

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

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

3.4 優(yōu)化算法的性能測度指標(biāo)

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

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

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

3.5 元學(xué)習(xí)訓(xùn)練過程

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

START: 給定訓(xùn)練算例x∈P,測試算例xnew∈P;元學(xué)習(xí)算法t∈T;元啟發(fā)式算法集合α∈A;算法性能測度集y∈Y。

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

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

Step3 執(zhí)行元學(xué)習(xí)算法t∈T,使得訓(xùn)練數(shù)據(jù)的預(yù)測結(jié)果的均方根差最小,獲得元模型(Metamodel);

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

3.6 實證結(jié)果分析

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

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

表2 算法二選一的選擇結(jié)果

注:交叉驗證數(shù)次均為10。

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

4 結(jié)語

元學(xué)習(xí)概念最早源于人工智能領(lǐng)域的機器學(xué)習(xí)理論,用于探究學(xué)習(xí)過程和學(xué)習(xí)機制,以便于改進(jìn)或調(diào)整學(xué)習(xí)效果,其目標(biāo)是把問題的元特征與元模型關(guān)聯(lián)起來,構(gòu)建自適應(yīng)的自動學(xué)習(xí)機制。本文把這一理念引入到元啟發(fā)式算法的自動選擇過程中,為解決現(xiàn)實中“問題-算法”之間盲目或者低效率匹配這一矛盾嘗試了一條新的思路。

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

)

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

[2] 汪定偉, 王俊偉, 王洪峰, 等. 智能優(yōu)化方法 [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] 李曉磊, 邵之江, 錢積新. 一種基于動物自治體的尋優(yōu)模式:魚群算法 [J]. 系統(tǒng)工程理論與實踐, 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] 曾子林, 張宏軍, 張睿. 基于元學(xué)習(xí)思想的算法選擇問題綜述 [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] 陳龍, 韓兆蘭, 崔建雙. 求解多模式資源約束的項目調(diào)度問題的離散粒子群算法 [J]. 計算機應(yīng)用, 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。 基金項目:國家自然科學(xué)基金資助項目(71471016)。

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

1001- 9081(2017)04- 1105- 06

10.11772/j.issn.1001- 9081.2017.04.1105

TP181

A