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

1、一種基于Q學(xué)習(xí)的任務(wù)調(diào)度算法的改進(jìn)研究*基金資助：國(guó)家自然科學(xué)基金(60673028), 合肥市科研計(jì)劃項(xiàng)目(2008-1004).作者簡(jiǎn)介：杜琳(1985-), 女, 河南南陽(yáng)人, 碩士研究生, 研究方向?yàn)橛?jì)算機(jī)圖形學(xué)與計(jì)算機(jī)輔助設(shè)計(jì); 石慧(1980-), 女, 安徽合肥人, 碩士, 助教, 研究方向?yàn)镃SCW和CAD; 劉曉平(1964-), 男, 山東濟(jì)南人, 教授, 博導(dǎo), 研究方向?yàn)榻！⒎抡婧蛥f(xié)同計(jì)算.杜琳 石慧 劉曉平合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽合肥 230009摘 要：本文針對(duì)協(xié)同工作中的任務(wù)調(diào)度問(wèn)題，提出了一種改進(jìn)的基于模擬退火的Q學(xué)習(xí)算法。該算法通過(guò)引入模擬退火，并

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

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

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

5、要在某個(gè)處理機(jī)上連續(xù)加工一段時(shí)間，調(diào)度就是將各個(gè)子任務(wù)恰當(dāng)?shù)姆峙浣o處理機(jī)，使給定的目標(biāo)得到最優(yōu)解。下面，我們給出任務(wù)分配和調(diào)度問(wèn)題的一般性定義：(1) n個(gè)子任務(wù)的集合T=T1, T2，Tn，Ti為第i個(gè)子任務(wù)；(2) m個(gè)處理機(jī)的集合P=P1, P2，Pm ，Pi為第i個(gè)處理機(jī)；(3) 一個(gè)m n的矩陣Cmn，C i,j 為子任務(wù)Ti在處理機(jī)Pj上的平均運(yùn)行時(shí)間；圖1 任務(wù)前驅(qū)圖(4) 一個(gè)任務(wù)約束關(guān)系圖，由任務(wù)前驅(qū)圖10來(lái)表示各個(gè)子任務(wù)間的時(shí)序約束關(guān)系，如圖1是7個(gè)子任務(wù)的約束關(guān)系圖對(duì)于一個(gè)任務(wù)前驅(qū)圖TPG，TPG=(T，L)，其中T為子任務(wù)集，一個(gè)子任務(wù)Ti ，就是圖TPG中的一個(gè)節(jié)點(diǎn)；

6、L是任務(wù)前驅(qū)圖中的有向邊集，它表示任務(wù)之間的直接驅(qū)動(dòng)關(guān)系，（Ti，Tj）L即子任務(wù) Tj 必須在子任務(wù) Ti 完成之后才能執(zhí)行，Ti 為 Tj 的一個(gè)前趨，Tj 為 Ti 的一個(gè)后驅(qū)。(5) 子任務(wù)節(jié)點(diǎn)Ti的深度值 ，其中，表示的前驅(qū)節(jié)點(diǎn)集合，。(6) 一個(gè)任務(wù)匹配矩陣TPmn = dij | 1im，1jn ，若dij =1 表示任務(wù)Tj 分配給了處理機(jī)Pi，反之dij = 0。稱(chēng)TPmn 為一個(gè)調(diào)度策略記為s，如果滿(mǎn)足：1) ，該約束條件的意義是每個(gè)處理機(jī)至少分配一個(gè)任務(wù)，并且一個(gè)任務(wù)同時(shí)只能調(diào)度給一臺(tái)處理機(jī)。2) 調(diào)度在同一臺(tái)處理機(jī)中的所有任務(wù)是按深度值升序排列的。(7) 一個(gè)調(diào)度策略s

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

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

9、反之a(chǎn)=ap。Step6：執(zhí)行動(dòng)作a，進(jìn)入下一狀態(tài)S，若此S不滿(mǎn)足，則返回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)的動(dòng)作，而隨機(jī)數(shù)的存在，又使得算法不放棄探索，以exp(Q/t)的概率接受新的動(dòng)作嘗試。隨著溫度t的降低，探索成分將極大減少，最終幾乎不存在探索。在探索中，算法采用隨機(jī)選取相同最大Q值動(dòng)作的做法，旨在保證每步訓(xùn)練動(dòng)作完全

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

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

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

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

14、確保了算法能夠盡快在全局尋得最優(yōu)解。為提高Q學(xué)習(xí)的收斂速度，算法加入了特定狀態(tài)的篩選，使得狀態(tài)空間達(dá)到了指數(shù)級(jí)的下降，從而大大加快了收斂速度，縮短了執(zhí)行時(shí)間。最后本文通過(guò)和文獻(xiàn)8中實(shí)例的對(duì)比分析，驗(yàn)證了算法的有效性和優(yōu)越點(diǎn)。由于本文提出的改進(jìn)Q學(xué)習(xí)算法屬于靜態(tài)調(diào)度算法，因此下一步的研究方向?qū)⒅赜谌绾斡行Ы鉀Q動(dòng)態(tài)任務(wù)調(diào)度問(wèn)題。參 考 文 獻(xiàn)1 冷晟, 魏孝斌, 王寧生. 柔性工藝路線蟻群優(yōu)化單元作業(yè)調(diào)度J. 機(jī)械科學(xué)與技術(shù), 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 耿汝年, 須文波. 基于自適應(yīng)選擇遺傳算法的任務(wù)調(diào)度與分配J. 計(jì)算機(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 陳圣磊, 吳惠中, 肖亮, 朱耀琴. 系統(tǒng)設(shè)計(jì)任務(wù)調(diào)度的多步Q學(xué)習(xí)算法J. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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 王雪松, 田西蘭, 程玉虎, 易建強(qiáng). 基于協(xié)同最小二乘支持向量機(jī)的Q 學(xué)習(xí)J. 自動(dòng)化學(xué)報(bào), 2009, 35(2): 214-219.11 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-LearningDu Lin Shi Hui Liu Xiao-pingSchool of Computer and Information, Hefei University of Technology, AnHui 230009,ChinaAbstract: In this paper, a Ma