導(dǎo)語(yǔ)：混合決策樹(shù)調(diào)度獲取研究思考一文來(lái)源于網(wǎng)友上傳，不代表本站觀點(diǎn)，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

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

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

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

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

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

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

5結(jié)束語(yǔ)

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

參考文獻(xiàn):

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

[2]彭觀,陳統(tǒng)堅(jiān),歐陽(yáng)惠芳.基于神經(jīng)網(wǎng)絡(luò)的FMS動(dòng)態(tài)調(diào)度決策[J].華南理工大學(xué)學(xué)報(bào)：自然科學(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]孫容磊,熊有倫,杜潤(rùn)生,等.規(guī)則調(diào)度的迭代優(yōu)化[J].計(jì)算機(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.