摘要：該文從工程應用角度給出了車間調(diào)度的問題建模和求解車間作業(yè)調(diào)度問題的標準遺傳算法及優(yōu)缺點，結(jié)合RL對動態(tài)的生產(chǎn)環(huán)境提出一種基于智能體RL的車間調(diào)度方法。該算法將遺傳算法與RL相結(jié)合，根據(jù)彈性生產(chǎn)環(huán)境獲取較優(yōu)的交叉率，從而優(yōu)化在線算法。

關(guān)鍵詞：遺傳算法；增強學習RL；交叉率；生產(chǎn)調(diào)度

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）25-0218-02

模具制造屬于非重復性的離散生產(chǎn)過程，模具生產(chǎn)結(jié)構(gòu)復雜、工藝制作繁瑣。加工步驟及工時的不確定使得模具制造車間管理變得復雜。在制定車間作業(yè)計劃時，由于沒有樣件的試制，有些問題會在生產(chǎn)過程中暴露出來。遇上突發(fā)事件如某臺機器發(fā)生故障，相關(guān)的零件加工也要作相應的調(diào)整，前后相關(guān)的生產(chǎn)任務也要做修改，這就引發(fā)了動態(tài)的生產(chǎn)調(diào)度管理。要提高生產(chǎn)資源的利用率，對人力資源及現(xiàn)有生產(chǎn)設(shè)備如何按最優(yōu)化的形式進行調(diào)配，使得對制造車間進行生產(chǎn)調(diào)度顯得特別困難和重要。

1 模型建立

模具車間調(diào)度生產(chǎn)問題模型可以描述為：

（1）零件集：加工i個零件，需要機器j臺，每零件有k道加工序列，在一個時間段一臺機器只能加工一個零件的某道工序，并有零件加工順序約束，每道工序可以占有若干臺機器；

（2）機器集：因生產(chǎn)調(diào)度時有機床約束而不會出現(xiàn)人員約束，所以只給出工序的機器分配，車間內(nèi)可用機床臺，標號組成機床集；

（3）機器使用時間：每個零件使用每臺機器的時間用T矩陣表示，tijk表示第i個零件在j臺機器上加工第k道所消耗的時間，可以由n臺機器加工第k道工序，第k道工序在n臺機器上的加工時間隨操作人員、設(shè)備性能的不同使加工時間有所不同，要表示加工時間值上下波動的不確定因素常采用三角數(shù)，最少時間、最大時間、最小時間 [1]。

則調(diào)度目標：零件i投入生產(chǎn)時間為（，，），完工期為 =，當零件的在內(nèi)加工完成時用戶滿意度為1，反之為0；要用表示，當j臺機床在加工第零件的第道工序時為1，反之為0；當?shù)趇工件第k道工序設(shè)定完工時間是，實際完成時間為，則滿意度為設(shè)定完工時間的所屬函數(shù)與完成期的所屬函數(shù)交叉面積與完成期的所屬函數(shù)面積的比[1]，由滿意度得到調(diào)度目標函數(shù)為：

工件的加工工序在機器上完工時間：。

2 遺傳算法求解車間調(diào)度經(jīng)驗

遺傳算法在求解車間作業(yè)問題時，將搜索空間中的參數(shù)轉(zhuǎn)換成遺傳空間中的染色體，通過一定規(guī)則進行逐步迭代產(chǎn)生新個體，新個體經(jīng)交叉、變異和復制操作又產(chǎn)生新的個體，遺傳算法的操作簡單，全局搜索能力強，缺點是控制參數(shù)如個體規(guī)模、適應度指標、變異率、交叉率等較多，參數(shù)組合不同，搜索過程可能會出現(xiàn)多方面的功效，影響遺傳算法行為和性能的關(guān)鍵因素是如何選擇交叉概率和變異概率，交叉概率過小，會降低搜索過程，新個體結(jié)構(gòu)產(chǎn)生不易；而交叉概率過大，加快產(chǎn)生新個體，也越有可能破壞遺傳模式[1]。

要求出制造車間生產(chǎn)調(diào)度問題中遺傳算法各參數(shù)的合適值是一件難事，必須通過反復試驗才能獲取當前最優(yōu)值，因而這些參數(shù)如果能進行自適應動態(tài)實時的變動對遺傳算法在解決生產(chǎn)調(diào)度問題上有著積極的作用。

3 智能RL模式

Muller提出的智能增強學習（Reinforcement Learning）是一種基于行為方法的半監(jiān)督學習，它包括負責智能體之間信息交換的通訊層、完成指定任務的協(xié)作求解的協(xié)作層和接收命令來感知環(huán)境變化及改變環(huán)境任務的控制層[5]。增強學習RL的目的是動態(tài)調(diào)整參數(shù)從而實現(xiàn)信號強化，當一個動作行為作用于環(huán)境，RL將產(chǎn)生動作評價獎懲值合反饋環(huán)境狀態(tài)給智能體，根據(jù)相關(guān)策略智能體選擇下一個行為去影響環(huán)境狀況，并對新環(huán)境做出調(diào)整，修改后的新環(huán)境狀態(tài)所給出的信息和獎懲值重新影響智能體，RL中智能體依靠自身經(jīng)歷進行學習獲取知識，從而改進行動方案來適應環(huán)境?；镜腞L模型包括離散的狀態(tài)信號反饋集合、行為集合、動作評價獎懲值和環(huán)境狀態(tài)集合，如下圖：

遺傳算法中變異和交叉概率值的選擇直接影響算法的收斂性，針對制造車間的工件加工順序、機床調(diào)配和加工時間等生產(chǎn)調(diào)度問題，最佳的變異和交叉概率值得獲取需要通過反復實驗，當加工狀況一旦變化最優(yōu)概率值又要重新尋找，因而單一的遺傳算法是不能滿足實時動態(tài)的車間作業(yè)調(diào)度的決策過程，而且在調(diào)度規(guī)模較大時很難保證獲取最優(yōu)值的收斂速度[2]，智能RL能根據(jù)行為和評價的環(huán)境獲取知識進而改變行動方案來適應環(huán)境的能力可以有效地完成隨機搜索，遺傳算法如能結(jié)合RL可以提高獲取最佳變異概率和交叉概率的速度。

4 基于RL的遺傳算法的設(shè)計

增強學習RL在一個環(huán)境下的行為產(chǎn)生一個獎懲值，獎懲值越大，則該行為被采用的可能性越大[3]，通過不斷重復的學習積累獎懲值找到一個最優(yōu)的變異概率和交叉概率的行為策略，這與人為調(diào)整概率值有很大的差異[4]，因而作為一種解決復雜的車間動態(tài)作業(yè)生產(chǎn)調(diào)度問題，提出了結(jié)合增強學習與遺傳算法的智能體自適應模型。

（1）強化學習RL決策過程

基于增強學習的智能體在遺傳算法中起協(xié)調(diào)作用，它在增強學習決策過程中應包含行為集，環(huán)境狀態(tài)集，反饋的信號映射集：，狀態(tài)轉(zhuǎn)移函數(shù)，值為：

獨立的增強學習能感知其他智能體的行為，并從環(huán)境中得到反饋值Q，當智能體在狀態(tài)選擇行為，強化學習智能體在t時刻的獎懲值更新為：

處于環(huán)境狀態(tài)時，增強學習RL對算法進行局部調(diào)整獲取值，經(jīng)過一輪自學習獲取一個環(huán)境反饋值，算法在更新前的局部RL獎懲值簡化為：

在結(jié)束局部RL更新并保存該+1，一輪算法結(jié)束獲取全局獎懲值，保留該次學習所得值后對染色體的交叉變異率進行一次更新。

當增強學習協(xié)調(diào)作用于遺傳算法中染色體交叉和變異時，RL能根據(jù)染色體的當前環(huán)境狀態(tài)做出概率調(diào)整，在狀態(tài)下，RL的行為會就當前環(huán)境狀態(tài)及先前的獎懲值去選擇一個值，被選中的合適的交叉和變異率可能性越大，過小或過大概率值被選中的可能性也越小，獲取合適的交叉和變異率并得到一個狀態(tài)轉(zhuǎn)移函數(shù)值，根據(jù)這個函數(shù)值得出獎懲值；感知一次學習后記下遺傳算法的交叉和變異率，獎懲值大的交叉和變異率在下一次行為中更有可能被選中的。由于獎懲值對交叉和變異率有明顯的優(yōu)化作用，形成正向反饋后的獎罰值使遺傳算法的交叉和變異率最后落實到較優(yōu)值上，個體就更好的遺傳了父串的染色體，在算法更新時對該染色體結(jié)構(gòu)中交叉及變異的適應度函數(shù)獎懲值也會更大，明顯提高遺傳算法的收斂速度[5]。

RL要獲取最佳行為必須不斷探索環(huán)境狀態(tài)，如何判斷已最佳交叉變異率是決定重新探索還是利用已知的最佳值的關(guān)鍵點。智能增強學習體可參照行為預測設(shè)定值來減少學習過程中考慮的因素而縮短學習過程，避免陷入次優(yōu)行為找不到全局最佳交叉變異率。在開始智能學習時，隨機獲取交叉變異率去探索第一輪新值，RL將獎懲值與歷史記錄比較，保存較優(yōu)值淘汰較劣值，經(jīng)過多次增強學習探索，最佳的概率值得以保留，已證明智能增強學習的收斂與行為選擇策略無關(guān)，設(shè)定行為預測值不影響RL的過程。

（2）智能體RL實現(xiàn)的流程

為快速求取普通遺傳算法染色體中交叉變異率的最優(yōu)選擇，結(jié)合普通遺傳算法與智能體增強學習RL，智能體RL的自我學習能夠就狀態(tài)、行為、學習率等的情況做出決策，對遺傳算法解決車間調(diào)度問題編碼中的染色體進行個體種群初始化，求取個體適應度函數(shù)值并判斷是否終止遺傳算法，如果終止條件不符合，則根據(jù)適應度函數(shù)值對染色體進行局部遺傳算子的交換和變異，獎懲初始值0，RL探索學習交叉變異率的進程中，當前獎懲值比較之前值并保留局部較優(yōu)值，一次學習結(jié)束更新交叉變異率，記錄全局獎懲值同時進行全局優(yōu)化探索學習，通過反復學習獲取經(jīng)驗，保留良好的獎懲值實現(xiàn)染色體的交叉變異概率的最佳選擇，實現(xiàn)作業(yè)車間的智能調(diào)度的算法流程如圖示：

交叉和變異率能隨智能增強學習機制的獎懲值自動改變，獎懲值較大時交叉和變異概率增加，跳出局部最優(yōu)，獎懲值較小時交叉和變異了降低，有利保留良好種群，由于RL是一種動態(tài)即時智能學習，隨著智能體學習的推進，保留的交叉變異率值逐漸良好，染色體的種群逐漸優(yōu)化，因此智能RL與遺傳算法結(jié)合在保證染色體編碼多樣性的同時也保證了遺傳算法的收斂特性，當適應度函數(shù)值不再有明顯改進，智能增強學習結(jié)束，最優(yōu)解求出算法終止。

5 總結(jié)

模具制造車間生產(chǎn)調(diào)度問題在企業(yè)中普遍存在，如何優(yōu)化對提高企業(yè)競爭力有積極的影響，本文結(jié)合智能RL與遺傳算法，建立了車間作業(yè)調(diào)度模型的在線調(diào)度，幫助企業(yè)合理安排工作進程。仿真實驗證明該算法能有效提高企業(yè)資源的優(yōu)化分配，合理安排加工任務，在動態(tài)的生產(chǎn)狀況下能快速智能的做調(diào)整。

參考文獻：

[1] 王萬良，吳啟迪.生產(chǎn)調(diào)度智能算法及其機器應用[M].科學出版社，2007.

[2] 宋毅. 基于遺傳算法的生產(chǎn)調(diào)度方法及其軟件實現(xiàn)[D].杭州：浙江工業(yè)大學，2003.

[3] 王雪輝，李世杰，張玉芝.Multi-Agent 技術(shù)在車間調(diào)度中的應用[J].河北工業(yè)大學學報，2005，34（2）：106-109.

[4] 陳文，王時龍，黃河.基于多Agent的蟻群算法在車間動態(tài)調(diào)度中的應用研究[J].組合機床與自動化加工技術(shù)，2004.

[5] 李瓊，郭御風，蔣艷凰.基于強化學習的智能I/O調(diào)度算法[J]. 計算機工程與科學， 2010， 32（7）.

[6] 葉婉秋.基于智能強化學習的遺傳算法研究[J].電腦學習，2010（4）.