1、一種基于Q學習的任務調度算法的改進研究*基金資助：國家自然科學基金(60673028), 合肥市科研計劃項目(2008-1004).作者簡介：杜琳(1985-), 女, 河南南陽人, 碩士研究生, 研究方向為計算機圖形學與計算機輔助設計; 石慧(1980-), 女, 安徽合肥人, 碩士, 助教, 研究方向為CSCW和CAD; 劉曉平(1964-), 男, 山東濟南人, 教授, 博導, 研究方向為建模、仿真和協同計算.杜琳 石慧 劉曉平合肥工業大學計算機與信息學院，安徽合肥 230009摘 要：本文針對協同工作中的任務調度問題，提出了一種改進的基于模擬退火的Q學習算法。該算法通過引入模擬退火，并

2、結合貪婪策略，以及在狀態空間上的篩選判斷，顯著地提高了收斂速度，縮短了執行時間。最后與其它文獻中相關算法的對比分析，驗證了本改進算法的有效性。關鍵詞：任務調度 Q學習 強化學習 模擬退火1 引 言隨著產品設計的復雜化和多樣化，協同工作已成為設計制造領域中的必由之路。協同工作的開展，不僅加強了企業內部和企業間的交流與合作，更能夠充分發揮企業自身的群組優勢，從而提高產品的開發效率，增強企業在市場中的競爭力。而在產品生產過程中，任務的規劃和分解，子任務間的調度與優化作為協同工作的基礎，就顯得尤為重要。目前，有效的調度方法與優化技術的研究和應用，已經成為先進生產技術實踐的基礎和關鍵，所以對它的研究與應

3、用具有重要的理論和實用價值1。任務調度問題已經被證明是一個NP完全問題2，不可能在多項式時間內找到問題的最優解。近年出現的一些啟發式算法為求解此類NP完全問題提供了新的途徑。其中遺傳算法以解決大空間、非線性、全局尋優等復雜問題時具有傳統方法所不具備的優越性，受到了研究人員的普遍關注3-5。但是遺傳算法在求解大規模任務調度問題時存在的計算效率偏低、收斂于局部最優解等弊端，也不容忽視，因此有必要尋求更加有效的算法來解決此問題。強化學習作為一種無監督的學習方法，它具有其他機器學習方法無可比擬的優點，它考慮的是在沒有外界指導的情況下，智能體通過與不確定的外界環境進行交互，從而獲得最優解的學習過程。文獻

4、6將Q學習應用于動態車間作業調度中，取得了較好的效果。Shah7等人在無線傳感網絡中，提出了一種基于Q學習的分布式自主資源管理框架，并通過仿真與對比試驗，證明其比現存的其他方法大大提高了系統效率。文獻7提出了一種基于多步信息更新值函數的多步Q學習調度算法，并結合實例闡明其解決任務調度問題的有效性，但其在收斂速度上還有待提高。針對此，本文改進了現有的基于Metropolis原則的Q學習算法，并將其應用到協同設計的任務調度上，通過和文獻8所示實例的對比，表明該算法具有更好的收斂速度和泛化性。2 問 題 定 義任務調度問題可以簡單的描述為，由設計任務分解出的N個子任務要在M個處理機上加工，每個子任務

5、要在某個處理機上連續加工一段時間，調度就是將各個子任務恰當的分配給處理機，使給定的目標得到最優解。下面，我們給出任務分配和調度問題的一般性定義：(1) n個子任務的集合T=T1, T2，Tn，Ti為第i個子任務；(2) m個處理機的集合P=P1, P2，Pm ，Pi為第i個處理機；(3) 一個m n的矩陣Cmn，C i,j 為子任務Ti在處理機Pj上的平均運行時間；圖1 任務前驅圖(4) 一個任務約束關系圖，由任務前驅圖10來表示各個子任務間的時序約束關系，如圖1是7個子任務的約束關系圖對于一個任務前驅圖TPG，TPG=(T，L)，其中T為子任務集，一個子任務Ti ，就是圖TPG中的一個節點；

6、L是任務前驅圖中的有向邊集，它表示任務之間的直接驅動關系，（Ti，Tj）L即子任務 Tj 必須在子任務 Ti 完成之后才能執行，Ti 為 Tj 的一個前趨，Tj 為 Ti 的一個后驅。(5) 子任務節點Ti的深度值 ，其中，表示的前驅節點集合，。(6) 一個任務匹配矩陣TPmn = dij | 1im，1jn ，若dij =1 表示任務Tj 分配給了處理機Pi，反之dij = 0。稱TPmn 為一個調度策略記為s，如果滿足：1) ，該約束條件的意義是每個處理機至少分配一個任務，并且一個任務同時只能調度給一臺處理機。2) 調度在同一臺處理機中的所有任務是按深度值升序排列的。(7) 一個調度策略s

7、的執行時間 ，其中為調度策略s中處理機Pi上最后一個任務完成的時間，t0為開始時間。現在的目標就是，尋找一個分配調度策略s，將n個子任務指派到m個處理機上，合理調度各個子任務的執行順序，使得各個任務在滿足任務前驅圖TPG的約束下，整個大任務的完成時間t(s)最短3 算 法 描 述 Q學習的基本思想是根據動態規劃原理，用即時回報和下一個狀態的估計值來更新當前狀態動作對的值函數，從估計的值函數中得到最優策略11。與Q學習收斂速率緊密相關的因素有：(1) 狀態空間；(2) 動作選擇；因此，要想提高Q學習的收斂速率，就需要使問題的狀態空間盡可能地小，也即縮小可行解空間；以及尋找合適的動作選擇策略，使得

8、Q學習在探索和利用之間達到平衡，既避免一味的貪心利用陷入局部最優，又防止過多的探索降低學習算法的性能12。針對以上兩點，本文提出了一種改進的基于Metropolis的Q學習，下面給出此算法描述：Step1：初始化所有，情節數k=0和情節設定值K，以及t；Step2：隨機初始化狀態S，并使其滿足，的原則，步驟數i =1和步驟設定值I;Step3：根據貪婪策略，從動作集A中選取當前狀態S的值函數最大的動作ap，若為最大的數量超過2，則隨機從對應的幾個動作中選取一at作為ap；Step4：從動作集A中隨機選取一動作ar；Step5：若，則a=ap；否則，產生0 , 1之間的隨機數；如果，則a=ar，

9、反之a=ap。Step6：執行動作a，進入下一狀態S，若此S不滿足，則返回Step3，反之繼續；Step7：由式（1）更新；Step8：，如果步驟數i達到設定值I，返回Step2，并令k=k+1，；若情節數k也達到設定值K，算法結束；否則，返回Step3繼續。算法描述中Step3至Step5是Metropolis原則的應用，其中加入了貪婪策略，試圖利用已學習到的信息采用當前最優的動作，而隨機數的存在，又使得算法不放棄探索，以exp(Q/t)的概率接受新的動作嘗試。隨著溫度t的降低，探索成分將極大減少，最終幾乎不存在探索。在探索中，算法采用隨機選取相同最大Q值動作的做法，旨在保證每步訓練動作完全

10、隨機選擇，使得結果訓練序列無限頻繁的訪問每個動作狀態轉換對，確定學習到Q函數，以及最優策略12。Step2和Step6意在縮小狀態空間，對于圖1所示的7個任務和3個處理機的任務調度問題，總的狀態空間為221，但采用了Step2和Step6的限定，狀態空間為37-273+3=1806個，不足211，使得狀態空間達到了指數級的下降。雖然算法在狀態判斷中會花費時間，但相比于在KI步循環中更新所有狀態空間的Q值時所花費的時間，可忽略不計。4 實驗對比與分析為了驗證和比較本文算法，我們采用文獻8中的調度實例進行試驗。該設計任務由7個子任務節點組成，任務之間的約束關系如圖1所示；3個處理機，Cmn矩陣如表

11、1所示。表1 子任務i在處理機j上的平均運行時間T1T2T3T4T5T6T7P12314254P24231723P31426122算法中用到的主要參數均采用文獻8所用參數：折扣因子，權重參數，學習率，初始溫度t=500，K=30。本算法最終收斂于8，也即最好調度策略的執行時間為8。并且找出了所有解，其對應的TPmn為：或表2給出了本算法在取不同步驟時收斂到最優解8的平均執行時間。圖2所示的是本文算法與文獻8給出的兩種Q學習算法的性能比較，從中可以很明顯的看出本文的改進Q算法在時間效率和收斂速度上的較大優勢（實驗在普通PC上運行，CPU2.6GHZ，內存768M，VC 6.0）。作者猜想算法間如

12、此大的差別可能是狀態空間不同，文獻8中的兩種算法狀態空間均為221，這就意味著Q學習幾乎要更新221個Q值，并在此龐大的狀態空間中不斷搜索查詢，而本文的算法加入了狀態判斷，使狀態空間縮小到1806個，從而大大減少了搜索時間，也使得算法的執行時間獲得了指數性的下降。從圖2還可以看出文獻8中的兩種算法均隨著步驟數的增加，收斂速度加快，執行時間變短。這一點在本文的改進Q中也有體現出來，如圖3所示，隨著步驟數的增大（從200到1000），情節數遞減，收斂速度加快，但執行時間并沒有相應的變短，原因在于步驟數i =200時，Q學習已經在情節數平均k =25處收斂于最優值。因此，隨著步驟數的提高，雖然收斂速

13、度在加速，理論上出現最優解的時間變短，但增大的步驟數所帶來的搜索空間變大，各狀態Q值更新增多的時間花費淹沒了上述改變，所以從整體上看執行時間反而有增加的趨勢。 表2 不同步驟收斂到最優解的平均執行時間步驟數5001000150020002500300035004000執行時間(s)1014201616192416圖2 本算法與其它算法性能比較圖3 不同步驟數算法收斂速度比較5 結 語本文針對協同工作中的任務調度問題，提出了一種改進的基于Metropolis 規則的Q學習算法。該算法通過引入Metropolis 原則，并結合貪婪策略，既考慮了當前最優，又根據溫度隨機地選取其他解以增加探索的機會，

14、確保了算法能夠盡快在全局尋得最優解。為提高Q學習的收斂速度，算法加入了特定狀態的篩選，使得狀態空間達到了指數級的下降，從而大大加快了收斂速度，縮短了執行時間。最后本文通過和文獻8中實例的對比分析，驗證了算法的有效性和優越點。由于本文提出的改進Q學習算法屬于靜態調度算法，因此下一步的研究方向將著重于如何有效解決動態任務調度問題。參 考 文 獻1 冷晟, 魏孝斌, 王寧生. 柔性工藝路線蟻群優化單元作業調度J. 機械科學與技術, 2005, 24(11): 1268-1271.2 RongXie, DanielaRus, CliffStein. Scheduling multi-task agen

15、tsC. Proceedings of the 5th International Conference on Mobile Agents, 2001: 260 - 276.3 耿汝年, 須文波. 基于自適應選擇遺傳算法的任務調度與分配J. 計算機工程, 2008, 34(3): 43-45.4 Deepa, R. Srinivasan, T. An Efficient Task Scheduling Technique in Heterogeneous Systems Using Self-Adaptive Selection-Based Genetic AlgorithmC. Parall

16、el 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

17、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 Wi

18、reless Sensor NetworksC. Mobile Adhoc and Sensor Systems, 2007. MASS 2007. IEEE International Conference on, 2007: 1-9.8 陳圣磊, 吳惠中, 肖亮, 朱耀琴. 系統設計任務調度的多步Q學習算法J. 計算機輔助設計與圖形學學報, 2007, 19(3): 398-402。9 Xiaoping Liu, Hui Shi, Qiang Lu, Zhengqiang Mao. Visual Task-driven Based on Task Precedence Graph for

19、Collaborative DesignJ. Computer Supported Cooperative Work in Design, 2007. CSCWD 2007. 11th International Conference on, 2007: 246-251.10 王雪松, 田西蘭, 程玉虎, 易建強. 基于協同最小二乘支持向量機的Q 學習J. 自動化學報, 2009, 35(2): 214-219.11 Q-learningJ. Machine Learning, 1992, 8: 279-292.12 Tom M. Mitchell著, 曾華軍, 張銀奎等譯. 機器學習. 北京: 機械工業出版社, 2003.Research on Improvement of Task Scheduling Based on Q-LearningDu Lin Shi Hui Liu Xiao-pingSchool of Computer and Information, Hefei University of Technology, AnHui 230009,ChinaAbstract: In this paper, a Ma