一種基于Q學(xué)習(xí)的任務(wù)調(diào)度算法的改進(jìn)研究.doc

5一種基于Q學(xué)習(xí)的任務(wù)調(diào)度算法的改進(jìn)研究一種基于Q學(xué)習(xí)的任務(wù)調(diào)度算法的改進(jìn)研究摘 要：本文針對協(xié)同工作中的任務(wù)調(diào)度問題，提出了一種改進(jìn)的基于模擬退火的Q學(xué)習(xí)算法。該算法通過引入模擬退火，并結(jié)合貪婪策略，以及在狀態(tài)空間上的篩選判斷，顯著地提高了收斂速度，縮短了執(zhí)行時間。最后與其它文獻(xiàn)中相關(guān)算法的對比分析，驗證了本改進(jìn)算法的有效性。關(guān)鍵詞：任務(wù)調(diào)度 Q學(xué)習(xí) 強(qiáng)化學(xué)習(xí) 模擬退火1 引 言隨著產(chǎn)品設(shè)計的復(fù)雜化和多樣化，協(xié)同工作已成為設(shè)計制造領(lǐng)域中的必由之路。協(xié)同工作的開展，不僅加強(qiáng)了企業(yè)內(nèi)部和企業(yè)間的交流與合作，更能夠充分發(fā)揮企業(yè)自身的群組優(yōu)勢，從而提高產(chǎn)品的開發(fā)效率，增強(qiáng)企業(yè)在市場中的競爭力。而在產(chǎn)品生產(chǎn)過程中，任務(wù)的規(guī)劃和分解，子任務(wù)間的調(diào)度與優(yōu)化作為協(xié)同工作的基礎(chǔ)，就顯得尤為重要。目前，有效的調(diào)度方法與優(yōu)化技術(shù)的研究和應(yīng)用，已經(jīng)成為先進(jìn)生產(chǎn)技術(shù)實踐的基礎(chǔ)和關(guān)鍵，所以對它的研究與應(yīng)用具有重要的理論和實用價值1。任務(wù)調(diào)度問題已經(jīng)被證明是一個NP完全問題2，不可能在多項式時間內(nèi)找到問題的最優(yōu)解。近年出現(xiàn)的一些啟發(fā)式算法為求解此類NP完全問題提供了新的途徑。其中遺傳算法以解決大空間、非線性、全局尋優(yōu)等復(fù)雜問題時具有傳統(tǒng)方法所不具備的優(yōu)越性，受到了研究人員的普遍關(guān)注3-5。但是遺傳算法在求解大規(guī)模任務(wù)調(diào)度問題時存在的計算效率偏低、收斂于局部最優(yōu)解等弊端，也不容忽視，因此有必要尋求更加有效的算法來解決此問題。強(qiáng)化學(xué)習(xí)作為一種無監(jiān)督的學(xué)習(xí)方法，它具有其他機(jī)器學(xué)習(xí)方法無可比擬的優(yōu)點(diǎn)，它考慮的是在沒有外界指導(dǎo)的情況下，智能體通過與不確定的外界環(huán)境進(jìn)行交互，從而獲得最優(yōu)解的學(xué)習(xí)過程。文獻(xiàn)6將Q學(xué)習(xí)應(yīng)用于動態(tài)車間作業(yè)調(diào)度中，取得了較好的效果。Shah7等人在無線傳感網(wǎng)絡(luò)中，提出了一種基于Q學(xué)習(xí)的分布式自主資源管理框架，并通過仿真與對比試驗，證明其比現(xiàn)存的其他方法大大提高了系統(tǒng)效率。文獻(xiàn)7提出了一種基于多步信息更新值函數(shù)的多步Q學(xué)習(xí)調(diào)度算法，并結(jié)合實例闡明其解決任務(wù)調(diào)度問題的有效性，但其在收斂速度上還有待提高。針對此，本文改進(jìn)了現(xiàn)有的基于Metropolis原則的Q學(xué)習(xí)算法，并將其應(yīng)用到協(xié)同設(shè)計的任務(wù)調(diào)度上，通過和文獻(xiàn)8所示實例的對比，表明該算法具有更好的收斂速度和泛化性。2 問 題 定 義任務(wù)調(diào)度問題可以簡單的描述為，由設(shè)計任務(wù)分解出的N個子任務(wù)要在M個處理機(jī)上加工，每個子任務(wù)要在某個處理機(jī)上連續(xù)加工一段時間，調(diào)度就是將各個子任務(wù)恰當(dāng)?shù)姆峙浣o處理機(jī)，使給定的目標(biāo)得到最優(yōu)解。下面，我們給出任務(wù)分配和調(diào)度問題的一般性定義：(1) n個子任務(wù)的集合T=T1, T2，Tn，Ti為第i個子任務(wù)；(2) m個處理機(jī)的集合P=P1, P2，Pm ，Pi為第i個處理機(jī)；(3) 一個m n的矩陣Cmn，C i,j 為子任務(wù)Ti在處理機(jī)Pj上的平均運(yùn)行時間；圖1 任務(wù)前驅(qū)圖(4) 一個任務(wù)約束關(guān)系圖，由任務(wù)前驅(qū)圖10來表示各個子任務(wù)間的時序約束關(guān)系，如圖1是7個子任務(wù)的約束關(guān)系圖對于一個任務(wù)前驅(qū)圖TPG，TPG=(T，L)，其中T為子任務(wù)集，一個子任務(wù)Ti ，就是圖TPG中的一個節(jié)點(diǎn)；L是任務(wù)前驅(qū)圖中的有向邊集，它表示任務(wù)之間的直接驅(qū)動關(guān)系，（Ti，Tj）L即子任務(wù) Tj 必須在子任務(wù) Ti 完成之后才能執(zhí)行，Ti 為 Tj 的一個前趨，Tj 為 Ti 的一個后驅(qū)。(5) 子任務(wù)節(jié)點(diǎn)Ti的深度值 ，其中，表示的前驅(qū)節(jié)點(diǎn)集合，。(6) 一個任務(wù)匹配矩陣TPmn = dij | 1im，1jn ，若dij =1 表示任務(wù)Tj 分配給了處理機(jī)Pi，反之dij = 0。稱TPmn 為一個調(diào)度策略記為s，如果滿足：1) ，該約束條件的意義是每個處理機(jī)至少分配一個任務(wù)，并且一個任務(wù)同時只能調(diào)度給一臺處理機(jī)。2) 調(diào)度在同一臺處理機(jī)中的所有任務(wù)是按深度值升序排列的。(7) 一個調(diào)度策略s的執(zhí)行時間 ，其中為調(diào)度策略s中處理機(jī)Pi上最后一個任務(wù)完成的時間，t0為開始時間?，F(xiàn)在的目標(biāo)就是，尋找一個分配調(diào)度策略s，將n個子任務(wù)指派到m個處理機(jī)上，合理調(diào)度各個子任務(wù)的執(zhí)行順序，使得各個任務(wù)在滿足任務(wù)前驅(qū)圖TPG的約束下，整個大任務(wù)的完成時間t(s)最短3 算 法 描 述 Q學(xué)習(xí)的基本思想是根據(jù)動態(tài)規(guī)劃原理，用即時回報和下一個狀態(tài)的估計值來更新當(dāng)前狀態(tài)動作對的值函數(shù)，從估計的值函數(shù)中得到最優(yōu)策略11。與Q學(xué)習(xí)收斂速率緊密相關(guān)的因素有：(1) 狀態(tài)空間；(2) 動作選擇；因此，要想提高Q學(xué)習(xí)的收斂速率，就需要使問題的狀態(tài)空間盡可能地小，也即縮小可行解空間；以及尋找合適的動作選擇策略，使得Q學(xué)習(xí)在探索和利用之間達(dá)到平衡，既避免一味的貪心利用陷入局部最優(yōu)，又防止過多的探索降低學(xué)習(xí)算法的性能12。針對以上兩點(diǎn)，本文提出了一種改進(jìn)的基于Metropolis的Q學(xué)習(xí)，下面給出此算法描述：Step1：初始化所有，情節(jié)數(shù)k=0和情節(jié)設(shè)定值K，以及t；Step2：隨機(jī)初始化狀態(tài)S，并使其滿足，的原則，步驟數(shù)i =1和步驟設(shè)定值I;Step3：根據(jù)貪婪策略，從動作集A中選取當(dāng)前狀態(tài)S的值函數(shù)最大的動作ap，若為最大的數(shù)量超過2，則隨機(jī)從對應(yīng)的幾個動作中選取一at作為ap；Step4：從動作集A中隨機(jī)選取一動作ar；Step5：若，則a=ap；否則，產(chǎn)生0 , 1之間的隨機(jī)數(shù)；如果，則a=ar，反之a(chǎn)=ap。Step6：執(zhí)行動作a，進(jìn)入下一狀態(tài)S，若此S不滿足，則返回Step3，反之繼續(xù)；Step7：由式（1）更新；Step8：，如果步驟數(shù)i達(dá)到設(shè)定值I，返回Step2，并令k=k+1，；若情節(jié)數(shù)k也達(dá)到設(shè)定值K，算法結(jié)束；否則，返回Step3繼續(xù)。算法描述中Step3至Step5是Metropolis原則的應(yīng)用，其中加入了貪婪策略，試圖利用已學(xué)習(xí)到的信息采用當(dāng)前最優(yōu)的動作，而隨機(jī)數(shù)的存在，又使得算法不放棄探索，以exp(Q/t)的概率接受新的動作嘗試。隨著溫度t的降低，探索成分將極大減少，最終幾乎不存在探索。在探索中，算法采用隨機(jī)選取相同最大Q值動作的做法，旨在保證每步訓(xùn)練動作完全隨機(jī)選擇，使得結(jié)果訓(xùn)練序列無限頻繁的訪問每個動作狀態(tài)轉(zhuǎn)換對，確定學(xué)習(xí)到Q函數(shù)，以及最優(yōu)策略12。Step2和Step6意在縮小狀態(tài)空間，對于圖1所示的7個任務(wù)和3個處理機(jī)的任務(wù)調(diào)度問題，總的狀態(tài)空間為221，但采用了Step2和Step6的限定，狀態(tài)空間為37-273+3=1806個，不足211，使得狀態(tài)空間達(dá)到了指數(shù)級的下降。雖然算法在狀態(tài)判斷中會花費(fèi)時間，但相比于在KI步循環(huán)中更新所有狀態(tài)空間的Q值時所花費(fèi)的時間，可忽略不計。4 實驗對比與分析為了驗證和比較本文算法，我們采用文獻(xiàn)8中的調(diào)度實例進(jìn)行試驗。該設(shè)計任務(wù)由7個子任務(wù)節(jié)點(diǎn)組成，任務(wù)之間的約束關(guān)系如圖1所示；3個處理機(jī)，Cmn矩陣如表1所示。表1 子任務(wù)i在處理機(jī)j上的平均運(yùn)行時間T1T2T3T4T5T6T7P12314254P24231723P31426122算法中用到的主要參數(shù)均采用文獻(xiàn)8所用參數(shù)：折扣因子，權(quán)重參數(shù)，學(xué)習(xí)率，初始溫度t=500，K=30。本算法最終收斂于8，也即最好調(diào)度策略的執(zhí)行時間為8。并且找出了所有解，其對應(yīng)的TPmn為：或表2給出了本算法在取不同步驟時收斂到最優(yōu)解8的平均執(zhí)行時間。圖2所示的是本文算法與文獻(xiàn)8給出的兩種Q學(xué)習(xí)算法的性能比較，從中可以很明顯的看出本文的改進(jìn)Q算法在時間效率和收斂速度上的較大優(yōu)勢（實驗在普通PC上運(yùn)行，CPU2.6GHZ，內(nèi)存768M，VC 6.0）。作者猜想算法間如此大的差別可能是狀態(tài)空間不同，文獻(xiàn)8中的兩種算法狀態(tài)空間均為221，這就意味著Q學(xué)習(xí)幾乎要更新221個Q值，并在此龐大的狀態(tài)空間中不斷搜索查詢，而本文的算法加入了狀態(tài)判斷，使?fàn)顟B(tài)空間縮小到1806個，從而大大減少了搜索時間，也使得算法的執(zhí)行時間獲得了指數(shù)性的下降。從圖2還可以看出文獻(xiàn)8中的兩種算法均隨著步驟數(shù)的增加，收斂速度加快，執(zhí)行時間變短。這一點(diǎn)在本文的改進(jìn)Q中也有體現(xiàn)出來，如圖3所示，隨著步驟數(shù)的增大（從200到1000），情節(jié)數(shù)遞減，收斂速度加快，但執(zhí)行時間并沒有相應(yīng)的變短，原因在于步驟數(shù)i =200時，Q學(xué)習(xí)已經(jīng)在情節(jié)數(shù)平均k =25處收斂于最優(yōu)值。因此，隨著步驟數(shù)的提高，雖然收斂速度在加速，理論上出現(xiàn)最優(yōu)解的時間變短，但增大的步驟數(shù)所帶來的搜索空間變大，各狀態(tài)Q值更新增多的時間花費(fèi)淹沒了上述改變，所以從整體上看執(zhí)行時間反而有增加的趨勢。 表2 不同步驟收斂到最優(yōu)解的平均執(zhí)行時間步驟數(shù)5001000150020002500300035004000執(zhí)行時間(s)1014201616192416圖2 本算法與其它算法性能比較圖3 不同步驟數(shù)算法收斂速度比較5 結(jié) 語本文針對協(xié)同工作中的任務(wù)調(diào)度問題，提出了一種改進(jìn)的基于Metropolis 規(guī)則的Q學(xué)習(xí)算法。該算法通過引入Metropolis 原則，并結(jié)合貪婪策略，既考慮了當(dāng)前最優(yōu)，又根據(jù)溫度隨機(jī)地選取其他解以增加探索的機(jī)會，確保了算法能夠盡快在全局尋得最優(yōu)解。為提高Q學(xué)習(xí)的收斂速度，算法加入了特定狀態(tài)的篩選，使得狀態(tài)空間達(dá)到了指數(shù)級的下降，從而大大加快了收斂速度，縮短了執(zhí)行時間。最后本文通過和文獻(xiàn)8中實例的對比分析，驗證了算法的有效性和優(yōu)越點(diǎn)。由于本文提出的改進(jìn)Q學(xué)習(xí)算法屬于靜態(tài)調(diào)度算法，因此下一步的研究方向?qū)⒅赜谌绾斡行Ы鉀Q動態(tài)任務(wù)調(diào)度問題。參 考 文 獻(xiàn)1 冷晟, 魏孝斌, 王寧生. 柔性工藝路線蟻群優(yōu)化單元作業(yè)調(diào)度J. 機(jī)械科學(xué)與技術(shù), 2005, 24(11): 1268-1271.2 RongXie, DanielaRus, CliffStein. Scheduling multi-task agentsC. Proceedings of the 5th International Conference on Mobile Agents, 2001: 260 - 276.3 耿汝年, 須文波. 基于自適應(yīng)選擇遺傳算法的任務(wù)調(diào)度與分配J. 計算機(jī)工程, 2008, 34(3): 43-45.4 Deepa, R. Srinivasan, T. Miriam, D.D.H. An Efficient Task Scheduling Technique in Heterogeneous Systems Using Self-Adaptive Selection-Based Genetic AlgorithmC. Parallel Computing in Electrical Engineering, 2006: 343-348.5 Loukopoulos, T. Lampsas, P. Sigalas, P. Improved Genetic Algorithms and List Scheduling Techniques for Independent Task Scheduling in Distributed SystemsC. Parallel and Distributed Computing, Applications and Technologies, 2007: 67-74.6 Yingzi Wei, Mingyang Zhao. Composite rules selection using reinforcement learning for dynamic job-shop scheduling RoboticsC. Automation and Mechatronics, 2004 IEEE Conference on, 2004(2): 1083-1088.7 Shah, K. Kumar, M.Distributed Independent Reinforcement Learning(DIRL)Approach to Resource Management in Wireless Sensor NetworksC. Mobile Adhoc and Sensor Systems, 2007. MASS 2007. IEEE International Conference on, 2007: 1-9.8 陳圣磊, 吳惠中, 肖亮, 朱耀琴. 系統(tǒng)設(shè)計任務(wù)調(diào)度的多步Q學(xué)習(xí)算法J. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 2007, 19(3): 398-402。9 Xiaoping Liu, Hui Shi, Qiang Lu, Zhengqiang Mao. Visual Task-driven Based on Task Precedence Graph for Collaborative DesignJ. Computer Supported Cooperative Work in Design, 2007. CSCWD 2007. 11th International Conference on, 2007: 246-251.10 王雪松, 田西蘭, 程玉虎, 易建強(qiáng). 基于協(xié)同最小二乘支持向量機(jī)的Q 學(xué)習(xí)J. 自動化學(xué)報, 2009, 35(2): 214-219.11 CHRISTOPHER J.C.H. WATKINS. Q-learningJ. Machine Learning, 1992, 8: 279-292.12 Tom M. Mitchell著, 曾華軍, 張銀奎等譯. 機(jī)器學(xué)習(xí). 北京: 機(jī)械工業(yè)出版社, 2003.Research on Improvement of Task Scheduling Based on Q-LearningAbstract: In this paper, a Markov Decision Process model