一種基于混合決策樹的調度知識獲取算法

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

關鍵詞:調度知識； 特征選取； 遺傳算法； 模擬退火算法； 決策樹

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2007)12-0054-03

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

如何利用機器學習技術，高效快捷地獲取調度知識以適應日益復雜的生產要求，吸引了大量學者對此進行研究。彭觀等人^[2]和Chen等人^[3]利用人工神經網絡(artificial neural network，ANN)表示和學習調度知識。這充分利用了ANN的學習能力、復雜非線性映射能力和并行運算能力，但其主要問題是神經網絡隱含的知識表示方式不能增加決策者對調度問題的認識，也無法評價其隱含推理過程的正確性。Park等人^[1]、Arzi等人^[4]和孫容磊等人^[5]則應用歸納學習技術推導調度知識。該技術使用ifthen規則或決策樹(decision tree， DT)的形式表示學習到的調度知識，但是如果結構復雜，將導致對應的調度知識過分凌亂，使決策者難以理解。

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

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

5結束語

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

參考文獻:

[1]PARK S C， RAMAN N， SHAW M J. Adaptive scheduling in dynamic flexible manufacturing systems: a dynamic rule selection approach [J]. IEEE Transactions on Robotics and Automation， 1997，13(4):486-502.

[2]彭觀，陳統堅，歐陽惠芳. 基于神經網絡的FMS 動態調度決策[J].華南理工大學學報：自然科學版， 1998，26(6):60-64.

[3]CHEN C C， YIH Y， WU Y C. Autobias selection for learningbased scheduling systems [J]. International Journal of Production Research， 1999，37(9):1987-2002.

[4]ARZI Y， IAROSLAVITZ L. Operating an FMC by a decisiontreebased adaptive production control system [J]. International Journal of Production Research， 2000，38(3):675-697.

[5]孫容磊，熊有倫，杜潤生，等. 規則調度的迭代優化[J]. 計算機集成制造系統，2002，8(7): 546-550.

[6]CASKEY R C. A manufacturing problem solving environment combing evaluation， search， and generation methods [J]. Computer in Industry， 2001，44:175-187.

[7]SHIUE Y R， GUH R S. The optimization of attribute selection in decision treebased production control systems [J]. International Journal of Advanced Manufacturing Technology，2005，28(7):737-746.

[8]SCHMITT L M， NEHANIV C L， FUJII R H. Linearanalysis of genetic algorithms [J]. Theoretical Computer Science， 1998，200(1-2): 101-134.

[9]KIM H， KOEHLER G J. Theory and practice of decision tree induction [J]. Omega，1995，23(6):637-652.

[10]WANG Ling， ZHENG Dazhong. An effective hybrid optimization strategy for jobshop scheduling problems [J]. Computers Operations Research， 2001，28:585-596.

[11]MONTAZERI M， WASSENHORE L N van. Analysis of scheduling rules for an FMS [J]. International Journal of Production Research， 1990，28(4):785-802.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”