前言：本站為你精心整理了小議處于混合決策樹的調(diào)度知識獲取算法范文，希望能為你的創(chuàng)作提供參考價值，我們的客服老師可以幫助你提供個性化的參考范文，歡迎咨詢。

摘要：提出了一種基于混合決策樹的調(diào)度知識獲取算法。將模擬退火算法融入遺傳算法中，作為一種具有自適應(yīng)變概率的變異操作，構(gòu)成一種混合優(yōu)化方法。利用這種混合方法求解在不同調(diào)度目標(biāo)下制造系統(tǒng)的最優(yōu)特征子集，同時確定控制決策樹規(guī)模的最優(yōu)參數(shù)；使用決策樹評價混合方法中染色體編碼的適應(yīng)度，在得到不同調(diào)度目標(biāo)下的最優(yōu)特征子集和最優(yōu)決策樹參數(shù)后，生成調(diào)度知識。仿真實驗結(jié)果表明，該算法在性能上優(yōu)于其他算法。

關(guān)鍵詞:調(diào)度知識；特征選??；遺傳算法；模擬退火算法；決策樹

適應(yīng)調(diào)度是一種較好的生產(chǎn)調(diào)度方法，能夠根據(jù)當(dāng)前系統(tǒng)的工作狀態(tài)及調(diào)度目標(biāo)選擇使用合適的調(diào)度規(guī)則[1]。它具有動態(tài)調(diào)度能力，非常適合生產(chǎn)系統(tǒng)復(fù)雜、生產(chǎn)過程隨機干擾因素較多的制造系統(tǒng)。調(diào)度知識實現(xiàn)了從生產(chǎn)狀態(tài)到調(diào)度規(guī)則的映射，是決定適應(yīng)調(diào)度系統(tǒng)性能的關(guān)鍵因素。機器學(xué)習(xí)是目前獲取調(diào)度知識的主要技術(shù)之一，它從仿真數(shù)據(jù)(訓(xùn)練樣本)中學(xué)習(xí)調(diào)度知識，并將其以隱含或顯式的方式表示。

如何利用機器學(xué)習(xí)技術(shù)，高效快捷地獲取調(diào)度知識以適應(yīng)日益復(fù)雜的生產(chǎn)要求，吸引了大量學(xué)者對此進行研究。彭觀等人[2]和Chen等人[3]利用人工神經(jīng)網(wǎng)絡(luò)(artificialneuralnetwork，ANN)表示和學(xué)習(xí)調(diào)度知識。這充分利用了ANN的學(xué)習(xí)能力、復(fù)雜非線性映射能力和并行運算能力，但其主要問題是神經(jīng)網(wǎng)絡(luò)隱含的知識表示方式不能增加決策者對調(diào)度問題的認(rèn)識，也無法評價其隱含推理過程的正確性。Park等人[1]、Arzi等人[4]和孫容磊等人[5]則應(yīng)用歸納學(xué)習(xí)技術(shù)推導(dǎo)調(diào)度知識。該技術(shù)使用ifthen規(guī)則或決策樹(decisiontree,DT)的形式表示學(xué)習(xí)到的調(diào)度知識，但是如果結(jié)構(gòu)復(fù)雜，將導(dǎo)致對應(yīng)的調(diào)度知識過分凌亂，使決策者難以理解。

Caskey[6]和Shiue等人[7]將多種機器學(xué)習(xí)技術(shù)相結(jié)合，構(gòu)成了不同的知識學(xué)習(xí)與表示混合方法，并取得了引人注目的成果。其中研究的熱點之一是使用遺傳算法等亞啟發(fā)式算法優(yōu)化決策樹，使之簡潔，并解決過度擬合問題。Schmitt等人[8]指出由于難以控制GA的收斂，致使GA容易發(fā)生“早熟”現(xiàn)象，而且GA中控制參數(shù)的確定過多地依賴經(jīng)驗，缺乏嚴(yán)謹(jǐn)?shù)目茖W(xué)理論依據(jù)。這些因素會影響決策樹的優(yōu)化質(zhì)量和知識庫的性能。為此，本文對GA進行改進，將模擬退火算法融入GA中，作為GA中具有自適應(yīng)變概率的變異算子。稱這種混合優(yōu)化方法為GASA。GASA不僅增強了進化能力，而且在某種程度上減小了對經(jīng)驗參數(shù)的依賴。筆者使用GASA求解不同調(diào)度目標(biāo)下制造系統(tǒng)的最優(yōu)特征子集，并確定控制決策樹規(guī)模的最優(yōu)參數(shù)。DT用于評價GASA求解過程中染色體編碼的適應(yīng)度，在獲取到最優(yōu)特征子集和最優(yōu)參數(shù)后生成調(diào)度知識。

表4和5的結(jié)果間接驗證了GASA混合方法對選取的特征子集和DT的參數(shù)優(yōu)化結(jié)果的合理性。使用過多的特征會導(dǎo)致訓(xùn)練樣本的過度擬合，降低調(diào)度知識的泛化能力；使用過少的特征將影響學(xué)習(xí)能力，降低調(diào)度知識的分類能力。與GA方法相比，顯然GASA能夠以突出的優(yōu)勢減小這兩種情況發(fā)生的概率。GASA也使得本文算法有效地控制了決策樹的規(guī)模，相應(yīng)地減少了最優(yōu)規(guī)則的搜索時間。這說明GASA將兩種不同搜索機制相結(jié)合，不僅減少了對經(jīng)驗參數(shù)的依賴，而且大大改善了搜索質(zhì)量。

5結(jié)束語

構(gòu)建性能優(yōu)良的調(diào)度知識庫能夠使適應(yīng)調(diào)度系統(tǒng)快速響應(yīng)日益復(fù)雜的生產(chǎn)要求，制定出實時的調(diào)度策略。本文提出了一種混合決策樹的調(diào)度知識獲取算法。利用GASA混合優(yōu)化方法求解在不同調(diào)度目標(biāo)下的制造系統(tǒng)的近似最優(yōu)特征子集，以及控制DT規(guī)模的最佳參數(shù)；使用DT評價GASA求解過程中染色體編碼的適應(yīng)度，在得到最優(yōu)特征子集和最優(yōu)參數(shù)后，生成調(diào)度知識。仿真結(jié)果表明，本文提出的算法與多種算法相比，性能非常優(yōu)秀。

參考文獻(xiàn):

[1]PARKSC,RAMANN,SHAWMJ.Adaptiveschedulingindynamicflexiblemanufacturingsystems:adynamicruleselectionapproach[J].IEEETransactionsonRoboticsandAutomation,1997,13(4):486-502.

[2]彭觀,陳統(tǒng)堅,歐陽惠芳.基于神經(jīng)網(wǎng)絡(luò)的FMS動態(tài)調(diào)度決策[J].華南理工大學(xué)學(xué)報：自然科學(xué)版,1998,26(6):60-64.

[3]CHENCC,YIHY,WUYC.Autobiasselectionforlearningbasedschedulingsystems[J].InternationalJournalofProductionResearch,1999,37(9):1987-2002.

[4]ARZIY,IAROSLAVITZL.OperatinganFMCbyadecisiontreebasedadaptiveproductioncontrolsystem[J].InternationalJournalofProductionResearch,2000,38(3):675-697.

[5]孫容磊,熊有倫,杜潤生,等.規(guī)則調(diào)度的迭代優(yōu)化[J].計算機集成制造系統(tǒng),2002,8(7):546-550.

[6]CASKEYRC.Amanufacturingproblemsolvingenvironmentcombingevaluation,search,andgenerationmethods[J].ComputerinIndustry,2001,44:175-187.

[7]SHIUEYR,GUHRS.Theoptimizationofattributeselectionindecisiontreebasedproductioncontrolsystems[J].InternationalJournalofAdvancedManufacturingTechnology,2005,28(7):737-746.

[8]SCHMITTLM,NEHANIVCL,FUJIIRH.Linearanalysisofgeneticalgorithms[J].TheoreticalComputerScience,1998,200(1-2):101-134.

[9]KIMH,KOEHLERGJ.Theoryandpracticeofdecisiontreeinduction[J].Omega,1995,23(6):637-652.

[10]WANGLing,ZHENGDazhong.Aneffectivehybridoptimizationstrategyforjobshopschedulingproblems[J].Computers&OperationsResearch,2001,28:585-596.

[11]MONTAZERIM,WASSENHORELNvan.AnalysisofschedulingrulesforanFMS[J].InternationalJournalofProductionResearch,1990,28(4):785-802.