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

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

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

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

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

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

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

0 引言

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

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

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

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

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

1 算法選擇問(wèn)題

1.1 研究現(xiàn)狀

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

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

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

1.2 相關(guān)理論

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

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

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

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

Rice抽象概念圖定義[20]:問(wèn)題的特征屬性和算法性能測(cè)度之間存在著關(guān)聯(lián)，因而算法選擇過(guò)程可以歸納為一個(gè)形式化的抽象模型,如圖1所示。對(duì)于給定問(wèn)題實(shí)例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),由于對(duì)所有可能函數(shù)的相互補(bǔ)償,最優(yōu)化算法的性能是等價(jià)的,即沒(méi)有其他任何算法能夠比搜索空間的線性列舉或者純隨機(jī)搜索算法更優(yōu)。NFL定理的意義在于:當(dāng)明確表明一個(gè)算法比另一個(gè)算法“更好”時(shí),只是針對(duì)具有特定特征的問(wèn)題或者特定的先驗(yàn)信息、數(shù)據(jù)分布、訓(xùn)練樣本的數(shù)目、代價(jià)或獎(jiǎng)勵(lì)函數(shù)等。

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

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

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

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

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

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

2 組合優(yōu)化問(wèn)題算法自動(dòng)選擇框架

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

圖2 組合優(yōu)化問(wèn)題算法自動(dòng)選擇框架

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

3 算法選擇實(shí)證分析

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

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

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

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

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

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

表1 MRCPSP可選特征列表

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

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

第一維(活動(dòng)模式): 131232123121

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

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

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

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

首先隨機(jī)產(chǎn)生規(guī)模為30的一組雙維粒子群編碼,接著開(kāi)始300輪迭代。每一輪迭代依據(jù)標(biāo)準(zhǔn)粒子群算法計(jì)算公式更新粒子的速度和位置。學(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è)計(jì)。

首先隨機(jī)產(chǎn)生30組雙維編碼調(diào)度,從中選擇一個(gè)最好的解作為初始解。給定最大鄰域解數(shù)量60,對(duì)初始解作隨機(jī)2-opt交換,產(chǎn)生60個(gè)鄰域解。每次都以最佳鄰域解作為當(dāng)前最優(yōu)解,若未產(chǎn)生更好的解則按照轉(zhuǎn)移概率接受劣解,通過(guò)內(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)化算法的性能測(cè)度指標(biāo)

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

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

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

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

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

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

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

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

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

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

3.6 實(shí)證結(jié)果分析

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

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

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

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

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

4 結(jié)語(yǔ)

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

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

)

[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] 李曉磊, 邵之江, 錢積新. 一種基于動(dòng)物自治體的尋優(yōu)模式:魚(yú)群算法 [J]. 系統(tǒng)工程理論與實(shí)踐, 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í)思想的算法選擇問(wèn)題綜述 [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] 陳龍, 韓兆蘭, 崔建雙. 求解多模式資源約束的項(xiàng)目調(diào)度問(wèn)題的離散粒子群算法 [J]. 計(jì)算機(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。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(71471016)。

崔建雙(1961—),男,河北衡水人,副教授,博士,主要研究方向:項(xiàng)目?jī)?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