基于RL的遺傳算法的制造車間生產(chǎn)調(diào)度研究

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

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）25-0218-02

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

1 模型建立

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

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

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

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

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

工件的加工工序在機(jī)器上完工時(shí)間：。

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

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

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

3 智能RL模式

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

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

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

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

（1）強(qiáng)化學(xué)習(xí)RL決策過程

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

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

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

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

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

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

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

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

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

5 總結(jié)

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

參考文獻(xiàn)：

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

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

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

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

[5] 李瓊，郭御風(fēng)，蔣艷凰.基于強(qiáng)化學(xué)習(xí)的智能I/O調(diào)度算法[J]. 計(jì)算機(jī)工程與科學(xué)， 2010， 32（7）.

[6] 葉婉秋.基于智能強(qiáng)化學(xué)習(xí)的遺傳算法研究[J].電腦學(xué)習(xí)，2010（4）.