小議處于混合決策樹的調(diào)度知識獲取算法

小議處于混合決策樹的調(diào)度知識獲取算法

摘要：提出了一種基于混合決策樹的調(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ī)則。它具有動態(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ù)中學(xué)習(xí)調(diào)度知識，并將其以隱含或顯式的方式表示。

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

caskey和Shiue等人將多種機器學(xué)習(xí)技術(shù)相結(jié)合，構(gòu)成了不同的知識學(xué)習(xí)與表示混合方法，并取得了引人注目的成果。其中研究的熱點之一是使用遺傳算法等亞啟發(fā)式算法優(yōu)化決策樹，使之簡潔，并解決過度擬合問題。Schmitt等人指出由于難以控制GA的收斂，致使GA容易發(fā)生“早熟”現(xiàn)象，而且GA中控制參數(shù)的確定過多地依賴經(jīng)驗，缺乏嚴謹?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)秀。

參考文獻:

PARkSc,RAmANN,micflexiblemanufacturingsystems:adynamicruleselectionapproach.IEEETransactionsonRoboticsandAutomation,1997,13:486-502.

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

cHENcc,yIHy,biasselectionforlearningbasedschedulingsystems.InternationaljournalofProductionResearch,1999,37:1987-20XX.

ARZIy,treebasedadaptiveproductioncontrolsystem.InternationaljournalofProductionResearch,20XX,38:675-697.

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

,search,puterinIndustry,20XX,44:175-187.

SHIUEyR,basedproductioncontrolsystems.InternationaljournalofAdvancedmanufacturingTechnology,20XX,28:737-746.

ScHmITTLm,NEHANIVcL,analysisofgeneticalgorithms.TheoreticalcomputerScience,1998,200:101-134.

kImH,.omega,1995,23:637-652.

wANGLing,ZHENGD