李文超 嚴(yán)洪森

1．東南大學(xué)復(fù)雜工程系統(tǒng)測量與控制教育部重點實驗室，南京，210096 2．江蘇大學(xué)，鎮(zhèn)江，212013

0 引言

知識化制造系統(tǒng)（knowledgeable manufacturing system，KMS）是于2001年出現(xiàn)的關(guān)于制造系統(tǒng)的一個新概念［1］，它以時間、質(zhì)量、成本、服務(wù)和環(huán)境為主要目標(biāo)，具備自適應(yīng)、自學(xué)習(xí)、自進(jìn)化、自重構(gòu)等特征，是一種高智能制造系統(tǒng)。近年來隨著對KMS研究的逐步深入，不斷有新的成果推出。如文獻(xiàn)［2－4］提出將先進(jìn)制造模式用知識網(wǎng)表示，運用知識網(wǎng)多重集的運算，實現(xiàn)先進(jìn)制造模式的自重構(gòu)；文獻(xiàn)［5］利用B－Q學(xué)習(xí)算法，構(gòu)建了一種適用于KMS中動態(tài)調(diào)度問題的自適應(yīng)調(diào)度控制策略；文獻(xiàn)［6］通過構(gòu)建一種分布式自動機(jī)死鎖監(jiān)控器來解決知識化制造單元死鎖問題；文獻(xiàn)［7］提出了一種運用自學(xué)習(xí)方法確定不同模型的組合權(quán)重對產(chǎn)品市場擴(kuò)散進(jìn)行預(yù)測的方法；文獻(xiàn)［8］對知識網(wǎng)多重集表達(dá)式進(jìn)行優(yōu)化，給出了基于用戶功能需求的知識網(wǎng)自動生成方法。

上述文獻(xiàn)多偏重于對KMS的整體性能進(jìn)行研究（如對系統(tǒng)自重構(gòu)、自適應(yīng)等特征進(jìn)行研究），而對于組成KMS的基本單元KMC的個體性能（如自進(jìn)化）的研究則較少涉及。KMS作為復(fù)雜大系統(tǒng)，其基本元素KMC間差別很大，可分為加工Agent、物料運輸設(shè)備、工業(yè)現(xiàn)場總線、產(chǎn)品市場預(yù)測、調(diào)度決策等類型模塊。不同類別KMC間存在本質(zhì)差別，對其個體性能的研究應(yīng)針對具體問題進(jìn)行具體分析。通過對流水型知識化制造單元（FSKMC）的分析，我們提出一種有別于常規(guī)，以尋優(yōu)為目的，具備學(xué)習(xí)能力的自進(jìn)化算法。該算法能夠通過離線學(xué)習(xí)，通過從環(huán)境中獲取相應(yīng)知識來不斷提高其搜索能力。

流水型知識化制造單元是以Flow－shop問題為對象的一類調(diào)度決策型制造單元。與傳統(tǒng)Flow－shop問題研究所不同的是，該單元雖然以獲取最優(yōu)調(diào)度策略作為其目標(biāo)，但更注重于在運行過程中通過對已往調(diào)度數(shù)據(jù)的分析學(xué)習(xí)獲得相關(guān)知識的能力，使其調(diào)度水平能夠不斷提升，即具備自進(jìn)化能力。機(jī)器數(shù)大于2的Flow－shop調(diào)度（簡稱Flow－shop）問題自1976年被證明為NP完全問題后［9］，對于該問題的研究大多集中于以尋找較優(yōu)解為目標(biāo)的近似算法，如文獻(xiàn)［10］所提的禁忌搜索算法、文獻(xiàn)［11－12］的遺傳算法，以及文獻(xiàn)［13］的模擬退火算法等。這些啟發(fā)式近似算法對于規(guī)模較大問題能夠在規(guī)定時間內(nèi)找到較滿意近優(yōu)解，但這類方法由于引入隨機(jī)性，也存在一些缺點，如對問題參數(shù)敏感、依賴初始解等不穩(wěn)定特征，并且由于其結(jié)構(gòu)是一固定程式，算法性能得不到改善。

Flow－shop屬于NP完全問題，至今仍未有獲取其最優(yōu)解的有效算法。近來不斷有學(xué)者提出一些具備學(xué)習(xí)能力的算法，這類算法的特點是在運行時通過對已往數(shù)據(jù)進(jìn)行分析能夠獲取問題特征及規(guī)律，使算法的求解性能得以提升，如文獻(xiàn)［14－16］提出的算法均能夠在一定程度上通過學(xué)習(xí)提高算法搜索能力?；诘膹娀瘜W(xué)習(xí)（reinforcement learning）對于調(diào)度類問題展現(xiàn)了較好的學(xué)習(xí)能力，目前已被應(yīng)用于調(diào)度問題研究［17－19］。由于Flow－shop的解空間隨著問題規(guī)模變大急劇增加，使強化學(xué)習(xí)所面臨的狀態(tài)空間迅速變大，導(dǎo)致值函數(shù)收斂速度變慢。針對該問題，本文提取問題典型參數(shù)來表征系統(tǒng)狀態(tài)特征，有效降低了狀態(tài)空間的復(fù)雜性。同時采用一種混合核支持向量機(jī)（SVM）對值函數(shù)進(jìn)行逼近，使所學(xué)知識具備較強泛化能力，具備良好自進(jìn)化能力。

1 問題描述

流水型知識化制造單元含有m個處理Agent，有n項任務(wù)（task）待處理。需要對n項任務(wù)進(jìn)行調(diào)度，即確定各項任務(wù)在各Agent上的處理順序，使得某些性能指標(biāo)達(dá)到最優(yōu)，通常以任務(wù)最大完工周期（makespan）作為指標(biāo)。各項任務(wù)在各Agent上處理時，需滿足如下要求：①每項任務(wù)按相同次序通過m個Agent；②每個Agent上各項任務(wù)通過次序相同；③每項任務(wù)在每個Agent上的處理時間是確定的；④每個Agent在同一時間只能完成一項任務(wù)；⑤每項任務(wù)在同一時間只能在一個Agent上完成。

該單元每個可行調(diào)度方案可用排列：ω＝（ω（1），ω（2），…，ω（i），…，ω（n））表 示，ω（i）（i ＝1，2，…，n）為排在第i個位置上的待處理任務(wù)。記Cmax（ω）為序列ω的最大完工周期，Π為該單元所有可行調(diào)度方案的集合，則最優(yōu)調(diào)度方案為

記piω（j）為序列ω 中第j 項任務(wù)ω（j）在第i個Agent上的處理時間，則n項任務(wù)在m個Agent上的處理時間可用一m×n矩陣P（ω）表示，即

式中，piω（j）為P（ω）的第i行第j列的元素。

2 算法相關(guān)理論基礎(chǔ)

本文所提自進(jìn)化算法以強化學(xué)習(xí)中值迭代思想為基礎(chǔ)，以q因子表示值函數(shù)，通過一種混合核支持向量機(jī)實現(xiàn)對q因子的學(xué)習(xí)。

2.1 強化學(xué)習(xí)

作為機(jī)器學(xué)習(xí)和智能控制方面的一種重要技術(shù)方法，強化學(xué)習(xí)已被廣泛應(yīng)用于控制系統(tǒng)、機(jī)器人、庫存控制、調(diào)度管理等諸多領(lǐng)域。其主要思想在于智能系統(tǒng)通過觀察環(huán)境對自身行為的反饋信號，獲取知識，改進(jìn)行動策略，達(dá)到預(yù)定目的。

系統(tǒng)在狀態(tài)s采取策略π時，期望回報可用值函數(shù)vπ（s）表示如下［20］：

系統(tǒng)在狀態(tài)s采取的最優(yōu)策略π＊（s）可由對應(yīng)最優(yōu)值函數(shù)v＊（s）確定。理論上可求解式（5）獲得v＊（s）值。對于流水型知識化制造單元，由于每個問題狀態(tài)空間隨問題規(guī)模急劇增加，該方法不可行。我們采取值迭代方法求取v＊（s）。記狀態(tài)—動作對（si，a）的q因子為

則式（5）可寫為

在一定簡化條件下，式（8）所得＾q（si，a）可完全收斂于q（si，a）［21］。即便如此，對于流水型知識化制造單元，由于前述原因，該方法依然不現(xiàn)實。為此，我們用支持向量機(jī)通過離線學(xué)習(xí)方式，實現(xiàn)對q（si，a）的逼近。

2.2 支持向量機(jī)

基于VC維理論由結(jié)構(gòu)風(fēng)險最小化原則導(dǎo)出的支持向量機(jī)已被廣泛應(yīng)用于許多模式識別、非線性函數(shù)回歸問題［21］，其基本思想是：將輸入向量映射到一個高維線性特征空間，利用定義在特征空間的懲罰超平面作為決策面，使模型的復(fù)雜性問題在高維空間得以解決，結(jié)果具備很好的泛化性能。

對于樣本集X ＝ ｛（xi，di）｜i＝1，2，…，n｝，d與x存在函數(shù)依賴關(guān)系。d的估計y可通過將x映射到高維線性空間實現(xiàn)，即

引入非負(fù)松弛變量ξi、ξ′i，上述函數(shù)回歸問題可轉(zhuǎn)化為模式分類問題，相應(yīng)地，在高維空間分類超平面約束優(yōu)化問題可描述為［21］

式中，C、ε為給定常數(shù)。上述約束優(yōu)化問題可通過引入Lagrange函數(shù)并構(gòu)造其對偶問題進(jìn)行求解，可得到d的逼近函數(shù)為

式中，αi、α′i為Lagrange乘子，可由式（10）的Lagrange函數(shù)對偶問題求得；k（x，xi）為由Mercer定理定義的內(nèi)積核函數(shù)［21］。

內(nèi)積核函數(shù)的具體形式在很大程度上決定著SVM的性能。目前常用核函數(shù)形式主要有多項式核函數(shù)、Gauss核函數(shù)、Sigmoid核函數(shù)等。多項式核函數(shù)有良好全局性能，具備較強外推能力；Gauss核函數(shù)局部性能較好；Sigmoid核函數(shù)不穩(wěn)定，若選擇參數(shù)不當(dāng)則不能滿足核函數(shù)要求。為充分發(fā)揮SVM的性能，本文提出一種混合核函數(shù)，并證明其滿足核函數(shù)條件。所給核函數(shù)形式為

式中，λ為最優(yōu)混合系數(shù)，λ∈ （0，1）。

為簡化式（12）的證明過程，先引入一核函數(shù)判定定理，具體如下：

引理1［22］X 為一給定有限輸入空間，k（x，z）（x，z∈X）為定義在該空間上的一對稱函數(shù)，則k（x，z）為核函數(shù)的充分必要條件是矩陣K為半正定陣，即

定理1 式（12）所給函數(shù)kmix（x，z）是定義在Rd空間上的核函數(shù)。

證明 函數(shù)k1（x，z）＝ （xTz＋1）2是定義在Rd空間上的一多項式核函數(shù)，則矩陣K（1）為

對 ?x?Rd，有

有

即矩陣K為半正定陣。另外，由式（12）可知：kmix（x，z）＝kmix（z，x），即kmix（x，z）是對稱函數(shù)，故它是定義在Rd空間上一核函數(shù)，證畢。

3 FSKMC調(diào)度自進(jìn)化算法

基于強化學(xué)習(xí)的FSKMC調(diào)度自進(jìn)化算法能夠通過離線仿真學(xué)習(xí)，所學(xué)知識隱含在SVM的回歸函數(shù)中，如遇到類似問題，調(diào)度單元調(diào)用所獲知識能夠迅速給出問題決策方案。在算法具體實施中存在一些技術(shù)性問題，如系統(tǒng)狀態(tài)識別、動作表示等，這些問題的處理直接影響著算法性能。

3.1 FSKMC狀態(tài)特征識別

對于一具體FSKMC問題，其可行調(diào)度方案ω和處理時間矩陣P（ω）能準(zhǔn)確表示其狀態(tài)。這種表示難以被學(xué)習(xí)系統(tǒng)識別，需要抽取系統(tǒng)的主要特征，并做必要簡化，使同規(guī)模FSKMC問題有相同表示形式。具體實施方法如下：

（1）處理時間矩陣P（ω）歸一化。對具體問題的P（ω）進(jìn)行歸一化處理，消除其數(shù)值上的差別。歸一化后的矩陣記為P（ω）＝ （piω（j））m×n，可表示為

（2）狀態(tài)特征抽取。各種狀態(tài)特征參數(shù)定義如下：

縱向指標(biāo)t

橫向指標(biāo)a

記ac，i為第i個Agent完工時間，有

由上述特征參數(shù)，對于規(guī)模為m×n的FSKMC，其狀態(tài)特征（支持向量機(jī)的輸入量）可表示為

3.2 動作表示

通過SVM對q因子進(jìn)行函數(shù)逼近，狀態(tài)和動作都需要有明確的表示方法。在此給出FSKMC在學(xué)習(xí)過程中的具體動作定義，并給出其量化表示方法。

定義1 FSKMC處于狀態(tài)ω時，將ω中處于第f個位置上的任務(wù)ω（f）和處于第g個位置上的任務(wù)ω（g），相互交換位置的操作稱為對狀態(tài)ω的一個動作，記為sw（f，g）（f，g ∈ （1，2，…，n），f≠g），其值為

式（30）是對狀態(tài)ω采取動作sw（f，g）的一個數(shù)值化表示，因為該動作作為支持向量機(jī)的一個輸入變量，需要數(shù)值化。

對狀態(tài)ω采取動作sw（f，g），系統(tǒng)轉(zhuǎn)換到另外一個狀態(tài)ω＇，可表示如下：

3.3 自進(jìn)化算法實現(xiàn)

算法核心主要通過對式（8）不斷迭代更新，調(diào)整SVM逼近函數(shù)參數(shù)，使其能夠更加接近q因子真實值。其中＾qt（si，a）由式（11）逼近函數(shù)獲得，其逼近誤差為

在FSKMC中，狀態(tài)si、sj由其對應(yīng)序列解ωi、ωj的處理時間矩陣表示，即si＝P（ωi），sj＝P（ωj）。

記每次迭代狀態(tài)－動作對目標(biāo)值為

在每步迭代中，適當(dāng)改變逼近函數(shù)參數(shù)，以縮短誤差。

算法實現(xiàn)步驟如下：

（1）初始化。對SVM的權(quán)值w賦初始權(quán)值w0。從Π中隨機(jī)選擇序列ω0為FSKMC的初始狀態(tài)s0，即s0＝P（ω0）；對st賦值，即st＝s0，ω ＝ω0。給出計算循環(huán)次數(shù)上下界N1、N2和常數(shù)C、ε、Δ。

（2）對狀態(tài)st所在序列ω提取狀態(tài)特征，即求sc（ω）。選取使?fàn)顟B(tài)－動作對的立即回報值r（st，a）最大的動作為當(dāng)前動作，計算動作值sw（f，g）。

（3）由式（11）計算＾qt（st，a），由式（32）、式（33）分 別 計 算 Δqt（st，a）、qtart（st，a）， 并 判 斷｜Δqt（st，a）｜＜Δ是否成立。若成立，轉(zhuǎn)步驟（6）；否則轉(zhuǎn)步驟（4）。

（4）判斷計算循環(huán)次數(shù)是否超過上界N1，若是，則轉(zhuǎn)步驟（7）；否則，將 點 （sc（ω），sw（p，q），qtar（st，a））加入SVM的樣本點集X。對SVM重新進(jìn)行學(xué)習(xí)。

（5）更新狀態(tài)。將狀態(tài)－動作對（st，a）的后繼狀態(tài)s′t、ω＇分別賦予st、ω，轉(zhuǎn)步驟（2）。

（6）判斷計算循環(huán)次數(shù)是否低于下界N2。若是，則轉(zhuǎn)步驟（5）；否則，轉(zhuǎn)步驟（7）。

（7）終止程序。

4 數(shù)值仿真實驗

我們從兩個方面設(shè)計了數(shù)值仿真實驗：一方面從考察算法對問題求解整體效果角度進(jìn)行仿真實驗；另一方面從考察算法離線學(xué)習(xí)規(guī)模變化對算法性能影響進(jìn)行仿真實驗。前者主要針對一些典型算例，比較分析所提算法與傳統(tǒng)算法間的差別；后者主要通過改變算法離線學(xué)習(xí)時間（迭代次數(shù)）以及訓(xùn)練算例規(guī)模，分析比較算法性能變化規(guī)律。算法用MATLAB7．0編寫程序?qū)崿F(xiàn)，仿真實驗在 CPU 為 Celeron M（1．6GHz），內(nèi)存為504M的PC上進(jìn)行。

針對文獻(xiàn)［10］中的五類規(guī)模（分別為20×20、50×20、100×20、200×20、500×20）算例，分別從求解精度和效率兩個方面對文獻(xiàn)［10－11］所提算法（分別記為TSGW和RY）和我們所提算法（記為SEFSMC）進(jìn)行比較。算法SEFSMC在求解問題前進(jìn)行了有限度離線學(xué)習(xí)，學(xué)習(xí)過程各參數(shù)設(shè)定如表1所示。

表1 學(xué)習(xí)過程主要參數(shù)

圖1所示為三種算法求解精度比較（橫坐標(biāo)Ti表示不同規(guī)模算例，順序同前；縱坐標(biāo)為各類算例最大完工周期Cmax）。圖中顯示出算法SEFSMC的精度低于算法TSGW和RY的精度，在問題規(guī)模較小時差別較顯著，但隨著問題規(guī)模增加，算法SEFSMC和算法TSGW、RY的精度間差距逐步減小。

圖1 三種算法求解精度比較

圖2 所示為三種算法求解效率比較。算法SEFSMC求解所花時間遠(yuǎn)低于算法TSGW和RY的求解時間，且隨著問題規(guī)模增加，算法TSGW和RY花費時間急劇增加，而SEFSMC所花費時間上升幅度緩慢。

不像傳統(tǒng)算法，其求解性能保持固定不變，算法SEFSMC的性能是隨著迭代次數(shù)和訓(xùn)練算例增加而不斷提升的。圖3所示為算法SEFSMC對規(guī)模為100×20算例學(xué)習(xí)時，求解精度與迭代次數(shù)、訓(xùn)練算例數(shù)目之間的變化趨勢。由圖3可知，算法求解精度隨學(xué)習(xí)過程中迭代次數(shù)的增加

圖2 三種算法求解效率比較

圖3 求解精度與迭代次數(shù)、訓(xùn)練算例之間的趨勢

而不斷提高，學(xué)習(xí)樣本（即算例）增加使得學(xué)習(xí)更充分，從而使算法求解精度得到提高。算例按文獻(xiàn)［23］方法隨機(jī)產(chǎn)生，圖中縱坐標(biāo)為各算例最大完工周期的均值，橫坐標(biāo)為學(xué)習(xí)過程迭代次數(shù)。

圖4所示為算法SEFSMC對規(guī)模為200×20算例學(xué)習(xí)時，求解時間與迭代次數(shù)、訓(xùn)練算例數(shù)目之間的變化趨勢。由圖4可知，當(dāng)學(xué)習(xí)樣本較少時因?qū)W習(xí)不太充分，算法求解時間雖然隨迭代次數(shù)增加而總體下降，但不很穩(wěn)定。當(dāng)學(xué)習(xí)樣本增多（10個算例以上），學(xué)習(xí)過程充分時，求解時間就會隨著迭代次數(shù)的增加而不斷降低。算例產(chǎn)生方式同圖3，圖中縱坐標(biāo)為求解時間均值，橫坐標(biāo)為學(xué)習(xí)過程迭代次數(shù)。

圖4 求解時間與迭代次數(shù)、訓(xùn)練算例之間的趨勢

圖3 、圖4仿真說明，算法SEFSMC在充分學(xué)習(xí)的情況下，其自身求解精度和求解效率能不斷得到提高，這些學(xué)習(xí)過程均可在離線情況下通過仿真完成。

5 結(jié)語

本文針對流水型知識化制造單元（FSKMC），提出一種具備學(xué)習(xí)能力的調(diào)度自進(jìn)化算法。通過離線學(xué)習(xí)算法能夠從環(huán)境中獲取相應(yīng)知識，不斷提高其搜索能力。提出一種混合核支持向量機(jī)能夠?qū)χ岛瘮?shù)進(jìn)行有效逼近，避免學(xué)習(xí)過程中狀態(tài)過多問題。數(shù)值仿真實驗表明，算法雖然在求解精度方面存在不足，但在求解效率方面有明顯優(yōu)勢，且求解精度的不足可通過不斷進(jìn)行離線學(xué)習(xí)加以提升，因此比較適合工程應(yīng)用。

［1］ 嚴(yán)洪森，劉飛．知識化制造系統(tǒng)－新一代先進(jìn)制造系統(tǒng)［J］．計算機(jī)集成制造系統(tǒng)，2001，7（8）：7－11．

［2］ Yan Hongsen．A New Complicated Knowledge Representation Approach Based on Knowledge Meshes［J］．IEEE Transactions on Knowledge and Data Engineering，2006，18（1）：47－62．

［3］ 嚴(yán)洪森．新的先進(jìn)制造模式知識表示方法［J］．機(jī)械工程學(xué)報，2006，42（10）：80－90．

［4］ 薛朝改，嚴(yán)洪森．基于Agent網(wǎng)的知識網(wǎng)的自重構(gòu)研究［J］．計算機(jī)集成制造系統(tǒng)，2003，9（11）：995－1000．

［5］ 楊宏兵，嚴(yán)洪森．知識化制造系統(tǒng)中動態(tài)調(diào)度的自適應(yīng)策略研究［J］．控制與決策，2007，22（12）：1335－1340．

［6］ 楊宏兵，嚴(yán)洪森．基于自動機(jī)的知識化制造單元死鎖控制策略研究［J］．中國機(jī)械工程，2009，20（5）：546－552．

［7］ 馬開平，嚴(yán)洪森．產(chǎn)品市場擴(kuò)散行為預(yù)測的自學(xué)習(xí)方法［J］．計算機(jī)集成制造系統(tǒng)，2008，14（12）：2484－2491．

［8］ 薛朝改，嚴(yán)洪森．．基于用戶功能需求的知識網(wǎng)的自動生成研究［J］．控制與決策，2005，20（9）：996－1001．

［9］ Garey M R，Johnson D S，Sethi R．The Complexity of Flow－shop and Job－shop Scheduling［J］．Mathematics of Operations Research，1976，1（2）：117－129．

［10］ Grabowski J，Wodecki M．A Very Fast Tabu Search Algorithm for the Permutation Flow－shop Problem with Makespan Criterion［J］．Computers and Operations Research，2004，31（11）：1891－1909．

［11］ Reeves C R，Yamada T．Genetic Algorithms，Path Relinking，and the Flowshop Sequencing Problem［J］．Evolutionary Computation，1998，6（1）：45－60．

［12］ Wang L，Zheng D Z．An Effective Hybrid Heuristic for Flow Shop Scheduling［J］．The International Journal of Advanced Manufacturing Technology，2003，21（1）：38－44．

［13］ Ogbu F，Smith D．Simulated Annealing for Permutation Flowshop Problem［J］．Omega，1990，19（1）：64－67．

［14］ Anurag A，Selcuk C，Enes E．Improvement Heuristic for the Flow－shop Scheduling Problem：an Adaptive－learning Approach［J］．European of Operational Research，2006，169（2）：801－815．

［15］ Lee I，Michael J S．A Neural－net Approach to Real Time Flow－shop Sequencing［J］．Computers＆Industrial Engineering，2000，38（1）：125－147．

［16］ Solimanpur M，Vrat P，Shankar R．A Neural－tabu Search Heuristic for Flow－shop Scheduling Problem［J］．Computers ＆ Operations Research，2004，31（11）：2151－2164．

［17］ Aydin M E，O¨ztemel E．Dynamic Job－shop Scheduling Using Reinforcement Learning Agents［J］．Robotics and Autonomous Systems，2000，33（2）：169－178．

［18］ Stefan P．Flow－shop Scheduling Based on Reinforcement Learning Algorithm［J］．Production Systems and Information Engineering，2003，1（1）：83－90．

［19］ Wang Y C，Usher J M．Application of Reinforcement Learning for Agent－based Production Scheduling［J］．Engineering Applications of Artificial Intelligence，2005，18（1）：73－82．

［20］ Mitchell T M．Machine Learning［M］．Beijing：China Machine Press，2003．

［21］ Haykin S．Neural Networks：a Comprehensive Foundation［M］．2nd．Beijing：China Machine Press，2004．

［22］ Cristianini N，Shawe T J．An Introduction to Support Vector Machines and other Kernel－based Learning Methods［M］．Beijing：China Machine Press，2005．

［23］ Taillard E．Benchmarks for Basic Scheduling Problems［J］．European Journal of Operational Research，1993，64（2）：278－285．