劉曉平， 杜 琳， 石 慧

（合肥工業(yè)大學(xué)計算機與信息學(xué)院，安徽 合肥 230009）

隨著產(chǎn)品設(shè)計的復(fù)雜化和多樣化，協(xié)同工作已成為設(shè)計制造領(lǐng)域中的必由之路。協(xié)同工作的開展，不僅加強了企業(yè)內(nèi)部和企業(yè)間的交流與合作，更能夠充分發(fā)揮企業(yè)自身的群組優(yōu)勢，從而提高產(chǎn)品的開發(fā)效率，增強企業(yè)在市場中的競爭力。而在產(chǎn)品生產(chǎn)過程中，任務(wù)的規(guī)劃和分解，子任務(wù)間的調(diào)度與優(yōu)化作為協(xié)同工作的基礎(chǔ)，就顯得尤為重要。目前，有效的調(diào)度方法與優(yōu)化技術(shù)的研究和應(yīng)用，已經(jīng)成為先進生產(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)解等弊端，也不容忽視，因此有必要尋求更加有效的算法來解決此問題。強化學(xué)習(xí)作為一種無監(jiān)督的學(xué)習(xí)方法，它具有其他機器學(xué)習(xí)方法無可比擬的優(yōu)點，它考慮的是在沒有外界指導(dǎo)的情況下，智能體通過與不確定的外界環(huán)境進行交互，從而獲得最優(yōu)解的學(xué)習(xí)過程。Wei Yingzi等人將Q學(xué)習(xí)應(yīng)用于動態(tài)車間作業(yè)調(diào)度中，取得了較好的效果[6]。Shah等人在無線傳感網(wǎng)絡(luò)中，提出了一種基于Q學(xué)習(xí)的分布式自主資源管理框架，并通過仿真與對比試驗，證明其比現(xiàn)存的其他方法大大提高了系統(tǒng)效率，并且提出了一種基于多步信息更新值函數(shù)的多步Q學(xué)習(xí)調(diào)度算法，并結(jié)合實例闡明其解決任務(wù)調(diào)度問題的有效性[7]。針對此，本文改進了現(xiàn)有的基于Metropolis原則的Q學(xué)習(xí)算法，并將其應(yīng)用到協(xié)同設(shè)計的任務(wù)調(diào)度上，通過和文獻[8]所示實例的對比，表明該算法具有更好的收斂速度和泛化性。

1 問題定義

任務(wù)調(diào)度問題可以簡單的描述為，由設(shè)計任務(wù)分解出的N個子任務(wù)要在M個處理機上加工，每個子任務(wù)要在某個處理機上連續(xù)加工一段時間，調(diào)度就是將各個子任務(wù)恰當?shù)姆峙浣o處理機，使給定的目標得到最優(yōu)解。

下面，作者給出任務(wù)分配和調(diào)度問題的一般性定義：

4）一個任務(wù)約束關(guān)系圖，由任務(wù)前驅(qū)圖[9]來表示各個子任務(wù)間的時序約束關(guān)系，如圖1是7個子任務(wù)的約束關(guān)系圖。對于一個任務(wù)前驅(qū)圖G，G=(T，L)，其中T為子任務(wù)集，一個子任務(wù)Ti，就是圖G中的一個節(jié)點；L是任務(wù)前驅(qū)圖中的有向邊集，它表示任務(wù)之間的直接驅(qū)動關(guān)系，(Ti，Tj)∈L即子任務(wù) Tj必須在子任務(wù) Ti完成之后才能執(zhí)行，Ti為 Tj的一個前趨，Tj為 Ti的一個后驅(qū)。

圖1 任務(wù)前驅(qū)圖

5） 子任務(wù)節(jié)點Ti的深度值

（2）調(diào)度在同一臺處理機中的所有任務(wù)是按深度值升序排列的。

現(xiàn)在的目標就是，尋找一個分配調(diào)度策略s，將n個子任務(wù)指派到m個處理機上，合理調(diào)度各個子任務(wù)的執(zhí)行順序，使得各個任務(wù)在滿足任務(wù)前驅(qū)圖G的約束下，整個大任務(wù)的完成時間t(s)最短。

2 算法描述

2.1 任務(wù)調(diào)度的MDP模型

強化學(xué)習(xí)以馬爾可夫決策過程(Markov decision process, MDP)為基礎(chǔ)[10]，通過試錯機制來獲得最優(yōu)行為策略。因此，采用強化學(xué)習(xí)求解設(shè)計任務(wù)調(diào)度問題的關(guān)鍵就在于如何將調(diào)度問題建模為MDP 模型。一個MDP模型可以表示如下其中S為狀態(tài)空間，A為動作空間，系統(tǒng)處于狀態(tài)St時，執(zhí)行決策動作at后轉(zhuǎn)移到下一狀態(tài)的轉(zhuǎn)移概率，r( St, at)為在狀態(tài)St下執(zhí)行動作at獲得的立即回報， W ( St, at)為值函數(shù)。MDP的本質(zhì)是：當前狀態(tài)向下一狀態(tài)轉(zhuǎn)移的概率和回報值只取決于當前狀態(tài)和決策，而與歷史狀態(tài)和決策無關(guān)。據(jù)此，本文給出如下MDP描述

1）狀態(tài)空間S由任務(wù)匹配矩陣TPm×n表示，即任務(wù)調(diào)度問題的一個可行解。強化學(xué)習(xí)的狀態(tài)轉(zhuǎn)移就是在解空間上的搜索。

2）動作空間A由子任務(wù)的集合T表示，對于任一狀態(tài)，都有n個動作，也即n個任務(wù)數(shù)。第j個動作（1≤j≤n）把第j個任務(wù)遷移到下一個處理機中，如果當前狀態(tài)中dij= 1，那么動作i

3）由上可知轉(zhuǎn)移概率p(St,at,St+1)=1。

2.2 Q學(xué)習(xí)

Q 學(xué)習(xí)是一種基于隨機動態(tài)過程的不依賴模型的強化學(xué)習(xí)方法。自Watkins等[11]提出Q學(xué)習(xí)并證明其收斂性以后，該算法在強化學(xué)習(xí)研究領(lǐng)域中得到了人們的普遍關(guān)注。Q學(xué)習(xí)過程由步驟(step)和情節(jié)(Episode)組成，每個情節(jié)包含若干步驟。Q學(xué)習(xí)在訓(xùn)練過程中，不斷重復(fù)以下步驟：觀察當前狀態(tài)St，選擇和執(zhí)行動作at，轉(zhuǎn)變?yōu)橄乱粻顟B(tài)St+1并接受即時回報 r ( St, at)，然后利用下式來調(diào)整Wt值

其中，學(xué)習(xí)率0 ≤ η ≤ 1控制學(xué)習(xí)的速度，學(xué)習(xí)率越大，收斂越快，但容易產(chǎn)生振蕩；學(xué)習(xí)率越小，收斂越慢。折扣因子0≤γ≤1表示學(xué)習(xí)系統(tǒng)的遠視程度，如果取值比較小，則表示系統(tǒng)更關(guān)注最近的動作的影響；如果比較大，則對比較長的時間內(nèi)的動作都很關(guān)注。一般來說，η取得較小，γ取得較大[10]。

2.3 Metropolis規(guī)則

模擬退火(Simulated Annealing, SA)算法近年來被證明是解決組合優(yōu)化問題的有效近似算法，其基本思想就是用一個物理系統(tǒng)的退火過程來模擬優(yōu)化問題的尋優(yōu)過程，當物理系統(tǒng)達到最小能量狀態(tài)時，優(yōu)化問題的目標函數(shù)值也相應(yīng)地達到其全局最優(yōu)值。

模擬退火算法通過Metropolis準則來確定接收新解的概率

其中， f ( xi)為當前解， f ( xj)為新產(chǎn)生的解，f( x)為目標函數(shù)，T為控制參數(shù)，類似固體退火中的溫度。因此，模擬退火算法并非總是接受優(yōu)化解，還在一個限定范圍內(nèi)接受惡化解，從而有助于跳出局部最優(yōu)。只要初始溫度足夠高，退火過程足夠慢，算法就能收斂到全局最優(yōu)解。

2.4 改進的基于Metropolis 規(guī)則的Q學(xué)習(xí)算法

與Q學(xué)習(xí)收斂速率緊密相關(guān)的因素有

1）狀態(tài)空間；

2）動作選擇。

因此，要想提高Q學(xué)習(xí)的收斂速率，就需要使問題的狀態(tài)空間盡可能地小，也即縮小可行解空間；以及尋找合適的動作選擇策略，使得Q學(xué)習(xí)在探索和利用之間達到平衡，既避免一味的貪心利用陷入局部最優(yōu)，又防止過多的探索降低學(xué)習(xí)算法的性能[12]。

針對以上兩點，本文提出了一種改進的基于Metropolis的Q學(xué)習(xí)，下面給出此算法描述：

Step 1 初始化所有 W ( St,at)，情節(jié)數(shù)k=0和情節(jié)設(shè)定值K，以及t；

Step 2 隨機初始化狀態(tài) S，并使其滿足

Step 3 根據(jù)貪婪策略，從動作集A中選取當前狀態(tài)S的值函數(shù) W ( St, at)最大的動作ap，若W( St, at)為最大的數(shù)量超過2，則隨機從對應(yīng)的幾個動作中選取一at作為ap；

Step 4 從動作集A中隨機選取一動作ar；

Step 5 若W( St,ap)≥W( St, ar)，則a=ap；否則，產(chǎn)生[0,1]之間的隨機數(shù)ε；如果a=ap；

Step 7 由式(1)更新 W ( St, at)；

Step 8 St=St+1，i=i+1，如果步驟數(shù)i達到設(shè)定值 I，返回 Step 2，并令 k=k+1，t=t* ( K -k)/K；若情節(jié)數(shù)k也達到設(shè)定值K，算法結(jié)束；否則，返回Step 3繼續(xù)。

算法描述中Step 3至Step 5是Metropolis原則的應(yīng)用，其中加入了貪婪策略，試圖利用已學(xué)習(xí)到的信息采用當前最優(yōu)的動作，而隨機數(shù)ε的存在，又使得算法不放棄探索，以exp(ΔQ/t)的概率接受新的動作嘗試。隨著溫度t的降低，探索成分將極大減少，最終幾乎不存在探索。在探索中，算法采用隨機選取相同最大 W 值動作的做法，旨在保證每步訓(xùn)練動作完全隨機選擇，使得結(jié)果訓(xùn)練序列無限頻繁的訪問每個動作—狀態(tài)轉(zhuǎn)換對，確定學(xué)習(xí)到W函數(shù)，以及最優(yōu)策略[12]。

Step 2和Step 6意在縮小狀態(tài)空間，對于圖1所示的7個任務(wù)和3個處理機的任務(wù)調(diào)度問題，總的狀態(tài)空間為221，但采用了Step 2和Step 6的限定，狀態(tài)空間為 37-27×3+3=1806個，不足211，使得狀態(tài)空間達到了指數(shù)級的下降。雖然算法在狀態(tài)判斷中會花費時間，但相比于在K×I步循環(huán)中更新所有狀態(tài)空間的W值時所花費的時間，可忽略不計。

3 實驗對比與分析

為了驗證和比較本文算法，采用文獻[8]中的調(diào)度實例進行試驗。該設(shè)計任務(wù)由7個子任務(wù)節(jié)點組成，任務(wù)之間的約束關(guān)系如圖1所示；3個處理機，矩陣如表1所示。

算法中用到的主要參數(shù)均采用文獻[8]所用參數(shù)：折扣因子 γ = 0 .9，權(quán)重參數(shù)λ=0.85，學(xué)習(xí)率α=0.1，初始溫度t =500，K=30。本算法最終收斂于8，也即最好調(diào)度策略的執(zhí)行時間為8。并且找出了所有解，其對應(yīng)的TPm×n為

表1 子任務(wù)i在處理機j上的平均運行時間

表2給出了本算法在取不同步驟時收斂到最優(yōu)解8的平均執(zhí)行時間。圖2所示的是本文算法與文獻[8]給出的兩種Q學(xué)習(xí)算法的性能比較，從中可以很明顯的看出本文的改進 Q算法在時間效率和收斂速度上的較大優(yōu)勢（實驗在普通 PC上運行，CPU2.6GHZ，內(nèi)存768MB，VC 6.0）。作者猜想算法間如此大的差別可能是狀態(tài)空間不同，文獻[8]中的兩種算法狀態(tài)空間均為 221，這就意味著Q學(xué)習(xí)幾乎要更新221個W值，并在此龐大的狀態(tài)空間中不斷搜索查詢，而本文的算法加入了狀態(tài)判斷，使狀態(tài)空間縮小到1806個，從而大大減少了搜索時間，也使得算法的執(zhí)行時間獲得了指數(shù)性的下降。從圖2還可以看出文獻[8]中的兩種算法均隨著步驟數(shù)的增加，收斂速度加快，執(zhí)行時間變短。這一點在本文的改進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)W值更新增多的時間花費淹沒了上述改變，所以從整體上看執(zhí)行時間反而有增加的趨勢。

表2 不同步驟收斂到最優(yōu)解的平均執(zhí)行時間

圖2 本算法與其它算法性能比較

圖3 不同步驟數(shù)算法收斂速度比較

本文的改進 Q學(xué)習(xí)算法還與目前廣泛使用的幾種遺傳算法做了相應(yīng)的比較分析。由于經(jīng)典遺傳算法在進化代數(shù)達到1000時，14是作者得到的最好效果[13]，并沒有求出調(diào)度問題的最優(yōu)解8，因此本文另采用了文獻[14]提出的兩種改進的遺傳算法——AGA和 GASA，與本算法進行對比。AGA和GASA均使用原文獻中提供的參數(shù)，進化代數(shù)為200，初始種群為100；本文改進Q步驟數(shù)i =200，情節(jié)數(shù)k =30。圖4給出了3種算法的性能對比，從中可以看出GASA和AGA比經(jīng)典遺傳算法在求解任務(wù)調(diào)度問題上有了明顯的改進，其中GASA比AGA算法有更好的求解能力和收斂性。但不管是AGA還是GASA在時間效率上均遠遠大于本文的改進 Q算法。AGA最好效果是8，平均解是9，平均執(zhí)行時間為103.6秒；GASA均得到最優(yōu)解8，平均執(zhí)行時間為112.7秒；改進Q學(xué)習(xí)算法也均收斂到最優(yōu)解8，平均執(zhí)行時間為9.7秒，如表3所示。因此，本文提出的改進 Q學(xué)習(xí)算法在任務(wù)調(diào)度問題的求解上有著更好的效果。

圖4 改進Q與AGA、GASA的性能比較

表3 AGA、GASA與改進Q的計算結(jié)果

4 結(jié)束語

本文針對協(xié)同工作中的任務(wù)調(diào)度問題，建立了MDP模型，在此基礎(chǔ)上提出了一種改進的基于Metropolis 規(guī)則的Q學(xué)習(xí)算法。該算法通過引入Metropolis 原則，并結(jié)合貪婪策略，既考慮了當前最優(yōu)，又根據(jù)溫度隨機地選取其他解以增加探索的機會，確保了算法能夠盡快在全局尋得最優(yōu)解。為提高Q學(xué)習(xí)的收斂速度，算法加入了特定狀態(tài)的篩選，使得狀態(tài)空間達到了指數(shù)級的下降，從而大大加快了收斂速度，縮短了執(zhí)行時間。最后本文通過和文獻[8]、文獻[14]中實例的對比分析，驗證了算法的高效性和優(yōu)越點。由于本文提出的改進Q學(xué)習(xí)算法屬于靜態(tài)調(diào)度算法，因此下一步的研究方向?qū)⒅赜谌绾斡行Ы鉀Q動態(tài)任務(wù)調(diào)度問題。

[1]冷 晟, 魏孝斌, 王寧生. 柔性工藝路線蟻群優(yōu)化單元作業(yè)調(diào)度[J]. 機械科學(xué)與技術(shù), 2005, 24(11):1268-1271.

[2]Xie Rong, Rus D, Stein C. Scheduling multi-task agents[C]//Proceedings of the 5th International Conference on Mobile Agents, 2001: 260-276.

[3]耿汝年, 須文波. 基于自適應(yīng)選擇遺傳算法的任務(wù)調(diào)度與分配[J]. 計算機工程, 2008, 34(3): 43-45.

[4]Deepa R. Srinivasan T. Miriam D D H. An efficient task scheduling technique in heterogeneoussystems using self-adaptive selection-based genetic algorithm[C]//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 systems [C]//Parallel and Distributed Computing,Applications and Technologies, 2007: 67-74.

[6]Wei Yingzi, Zhao Mingyang. Composite rules selection using reinforcement learning for dynamic job-shop scheduling robotics[C]//Automation and Mechatronics,2004 IEEE Conference on, 2004: 1083-1088.

[7]Shah K. Kumar M. Distributed independent reinforcement learning (DIRL) approach to resource management in wireless sensor networks [C]//Mobile Adhoc and Sensor Systems, MASS 2007, IEEE Internatonal Conference on, 2007: 1-9.

[8]陳圣磊, 吳惠中, 肖 亮, 等. 系統(tǒng)設(shè)計任務(wù)調(diào)度的多步Q學(xué)習(xí)算法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報,2007, 19(3): 398-402.

[9]Liu Xiaoping, Shi Hui, Lu Qiang, et al. Visual task-driven based on task precedence graph for collaborative design [C]//Computer Supported Cooperative Work in Design, CSCWD 2007. 11th International Conference on, 2007: 246-251.

[10]王雪松, 田西蘭, 程玉虎, 等. 基于協(xié)同最小二乘支持向量機的Q 學(xué)習(xí)[J]. 自動化學(xué)報, 2009, 35(2):214-219.

[11]Christopher J C H, Watkins, Peter D. Q-learning [J].Machine Learning, 1992, (8): 279-292.

[12][美]Tom M M著. 機器學(xué)習(xí)[M]. 曾華軍, 張銀奎,等譯. 北京: 機械工業(yè)出版社, 2003: 251-268.

[13]殷國富, 羅 陽, 龍紅能, 等. 并行設(shè)計子任務(wù)調(diào)度的遺傳算法原理與實現(xiàn)方法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2004, 16(8): 1122-1126.

[14]石 慧, 劉曉平. 協(xié)同設(shè)計中的任務(wù)調(diào)度算法及實現(xiàn)[J]. 中山大學(xué)學(xué)報(自然科學(xué)版), 2008, 47(6):52-56.