一種協(xié)同設計任務調(diào)度算法的研究

一種協(xié)同設計任務調(diào)度算法的研究

合作設計是由不同領域的多組設計團隊共同協(xié)調(diào)完成同一污染物設計的過程。任務的分割及并發(fā)執(zhí)行可以有效地提高設計效率,協(xié)同設計的初衷也正基于此。由于設計產(chǎn)品的復雜性及不同設計組之間的交流,分割的子任務之間存在相互依賴、相互制約的關系。任務規(guī)劃的目的便是將產(chǎn)品設計包含的所有設計任務按照一定的原則分為若干個任務組,并進一步將任務組分配給合適的設計組,這是協(xié)同設計中的關鍵環(huán)節(jié)。因此,合理的任務規(guī)劃將有利于協(xié)同設計的順利進行,勢必影響設計效率和質(zhì)量。Agent常被用于解決任務規(guī)劃問題。文獻提出了協(xié)同裝配任務規(guī)劃系統(tǒng),借助于Agent解決任務分配問題。文獻針對協(xié)同工程設計問題提出了一個任務分配協(xié)議,討論了設計Agent如何選擇任務,任務如何挑選設計Agent等問題。文獻介紹了一種多Agent設計系統(tǒng)中的協(xié)作方法,提出了支持動態(tài)任務分配的公告板機制以及設計過程中的沖突協(xié)調(diào)方法。公告板模型結合了黑板模型與合同網(wǎng)模型的優(yōu)點。設計結構矩陣亦被用于任務規(guī)劃問題。同時更多的文章采用了啟發(fā)式算法來進行任務規(guī)劃問題的研究。文獻引入了分組遺傳算法。文獻考慮時間、任務順序、任務協(xié)作等因素,引入遺傳算法解決任務分配問題。文獻主要采用遺傳算法解決任務調(diào)度和分配問題,設計了在任務調(diào)度和分配中的遺傳算子。文獻仍舊采用遺傳算法實現(xiàn)了并行設計中的任務調(diào)度,但結果顯示,優(yōu)化效果基本達不到最優(yōu)。于是文獻用多步Q學習算法代替遺傳算法作為協(xié)同設計中的任務調(diào)度算法,以同樣的任務實例作為比照對象,在優(yōu)化效果上明顯優(yōu)于文獻中遺傳算法,但是對于大規(guī)模任務問題,多步Q學習算法耗時耗空間。本文則面向協(xié)同設計的實際需求,改進了AGA算法及GASA算法,將其作為協(xié)同設計中的任務調(diào)度算法,描述了算法實現(xiàn)的具體步驟,并采用文獻和文獻中實例與本文中算法進行縱向比較,并采用復雜任務實例對本文中的兩個算法進行橫向比較,分析其優(yōu)劣。1任務前趨圖與約束條件在協(xié)同設計中,任務間的相互依賴和約束是協(xié)同進程的重要方面,每一個設計者可能會需要獲取他人的設計結果才可順利完成自身的任務,但是設計者之間的合作并不總是協(xié)調(diào)一致的,于是就需要在任務之間協(xié)調(diào)、規(guī)劃以保證任務協(xié)作的效率。這種協(xié)調(diào)被理解為為了能夠達到最終目標而對子任務間相互約束和依賴的控制。我們采用有向圖的方式來描述任務之間的約束及任務之間的驅動,從而形成了任務約束圖及任務前趨圖。任務前趨圖,是一種反映了先后執(zhí)行關系的抽象的圖結構,存儲了任務節(jié)點以及它們之間的前趨后繼關系?；诰酆吓c并序的轉換算法的提出實現(xiàn)了由約束圖向任務前趨圖的轉換。定義1任務前趨圖TPG=(PV,PE),PV集的每一個任務節(jié)點vi表示設計子任務,PE集中的每一條有向邊eij則表示任務之間的直接驅動關系,是一種前趨與后繼關系,具有傳遞性。圖1為設計實例所產(chǎn)生的任務前趨圖示例。ΡV={vi},PV={vi},ΡE={eij=Edge(pvi,pvj)|pvj∈Succ(pvi)}PE={eij=Edge(pvi,pvj)|pvj∈Succ(pvi)}i,j∈{1,2,3?n}i,j∈{1,2,3?n}pvi=(M-ID,T-ID,Com,IP,Ord,Sta,Sin,PosJ)其中:M-ID——任務的ID號,T-ID——模板的ID號,Com——該任務包含的設計組件,IP——接收該任務的設計者IP,Ord——該任務節(jié)點的執(zhí)行次序,Sta——任務的完成狀態(tài),Sin——任務節(jié)點的入度即驅動該任務的任務節(jié)點數(shù)目,PosJ——該任務在并行任務間的位置。Succ(pvi):PV→PV指任務節(jié)點pvi的直接后繼節(jié)點集,即繼pvi之后立即執(zhí)行的任務節(jié)點集。After(pvi):PV→PV指任務節(jié)點pvi的直接或間接后繼節(jié)點集,即繼pvi之后執(zhí)行的任務節(jié)點集。Pre(pvi):PV→PV指任務節(jié)點pvi的直接前趨節(jié)點集,即在pvi之前執(zhí)行的前趨任務節(jié)點集。定義2任務節(jié)點pvi的深度值H(pvi)={01+max(Η(pvj))Ρre(nj)=?否則{01+max(H(pvj))Pre(nj)=?否則其中,Pre(pvi)表示pvi的前趨節(jié)點集合,pvj∈Pre(pvi)。定義3任務前趨圖TPG中的任務與參與協(xié)同的設計者的任務匹配矩陣為NPMm×n={dij|1≤i≤m,1≤j≤n}={dij|1≤i≤m,1≤j≤n},當dij=1表示任務pvj調(diào)度給了設計者i,當dij=0,則表示任務pvj沒有調(diào)度給設計者i。定義NPMm×n為一個調(diào)度策略記為s,為了確保任務的正常執(zhí)行,在該策略中增加了兩個約束條件:(1)n∑j=1dij≥1,m∑i=1dij=1∑j=1ndij≥1,∑i=1mdij=1,該約束條件表示每個設計者至少分配一個任務,并且一個任務只能調(diào)度給一個設計單元;(2)調(diào)度給同一個設計者的所有任務是按深度值遞增方式來排列的。定義4時間效率矩陣,由設計者提供的完成時間獲得,ΝΡΤm×n={tij|1≤i≤m,1≤j≤n}NPTm×n={tij|1≤i≤m,1≤j≤n},描述了各設計者對各個子任務的執(zhí)行效率,其中,tij表示設計者i完成子任務pvj所需時間。本文算法的流程是在獲得①描述子任務間驅動關系的任務前趨圖與②設計者完成各個子任務所需時間的基礎上,采用改進的進化算法求得最優(yōu)的任務匹配矩陣,即所有任務完成所需的時間最短。2任務的開始時間在此,調(diào)度策略生成的目的是使得在該策略下設計者執(zhí)行任務的時間最短,該類問題涉及到時間效率執(zhí)行的優(yōu)化,任務間的執(zhí)行時間彼此影響。設計單元上某一個子任務的開始時間既受任務前趨圖中其前趨任務集中子任務的最后結束時間影響,亦受其在該設計單元中的前趨任務的結束時間影響,取其中最大值作為該任務的開始時間。如果要求整個調(diào)度策略的時間,只要計算所有設計單元NSi任務列表中的最后一個子任務結束時間的最大值即可。任務進行初步的篩選,篩選后任務被執(zhí)行的快慢往往是任務規(guī)劃的最重要目標,于是可以將各個目標按重要度排序,并以時間列為最重要的影響因素。本文采用了兩種改進的遺傳算法來完成時間效率目標的規(guī)劃,適應度函數(shù)、遺傳交叉、變異算子均采用文獻中的設計方案。2.1自適應遺傳算法遺傳算法的參數(shù)中交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關鍵所在,直接影響算法的收斂性,Srinvivas等提出一種自適應遺傳算法(AGA),Pc和Pm能夠隨著適應度自動改變。在自適應遺傳算法中,Pc和Pm按如下公式進行自適應調(diào)整:Pc={Ρm1-(Ρc1-Ρc2)(f′-favg)fmax-favgf′≥favgΡc1f′<favg(1)Pm={Ρm1-(Ρm1-Ρm2)(fmax-f)fmax-favgf≥favgΡm1f<favg(2)本文適應任務規(guī)劃實際問題需要,對自適應GA進行了改進。(1)并行執(zhí)行,縮短策略執(zhí)行時間任務前趨圖中的并行任務,即深度值H(pvi)相同的任務,適宜在任務執(zhí)行過程中并行執(zhí)行,可縮短策略的執(zhí)行時間。因此在初始化種群時,將并行任務分布分配,分給不同的設計者,相當于在種群個體注入了優(yōu)化基因,在選擇、交叉和變異過程中保留該基因的概率也相應增大,從而達到縮短執(zhí)行時間的目的。(2)實驗結果和分析在每一代個體中選擇適應度最高的符合策略中約束條件的個體直接復制到下一代中。下面給出改進的自適應GA的算法描述:Step1讀入任務前趨圖,計算圖中各子任務的深度值H(pvi)Step2按并行任務分布分配的原則生成初始種群Step3如果不滿足算法的終止條件(如達到進化代數(shù)),執(zhí)行Step4;否則,轉Step8Step4計算種群中每個個體的適應度Step5利用輪盤賭算法進行個體選擇Step6以公式(1),(2)計算交叉概率和變異概率,并以概率Pc和Pm執(zhí)行交叉運算和變異運算Step7計算種群中的每個個體的調(diào)度時間t(si),保存適應度最高的染色體,t=t+1,轉Step3Step8輸出最好解,算法結束經(jīng)過實驗分析,該算法適用于小規(guī)模的任務分配問題。對于文獻和文獻中的調(diào)度實例,實驗結果如表1所示。其中Pc1=0.9,Pc2=0.6,Pm1=0.1,Pm2=0.001。2.2sa模式下的個體目標退火行為檢測GASA算法是遺傳算法與模擬退火算法的結合。算法描述如下:Step1初始化算法參數(shù),包括種群數(shù)目p、初始溫度tk、退溫速率λ等Step2初始化遺傳算法種群Step3計算種群中所有個體的適應度,確定最優(yōu)適應度及最優(yōu)個體Step4判斷最優(yōu)適應度S是否連續(xù)t步?jīng)]有發(fā)生變化?如果穩(wěn)定,執(zhí)行Step9,否則,繼續(xù)執(zhí)行Step5循環(huán)執(zhí)行k次:隨機選擇個體與最優(yōu)個體執(zhí)行外部交叉操作,擴大種群數(shù)量,同時,篩選優(yōu)秀個體,更新最優(yōu)適應度及最優(yōu)個體Step6按變異概率Pm對個體執(zhí)行變異操作,篩選優(yōu)秀個體,更新最優(yōu)適應度及最優(yōu)個體Step7對遺傳算法生成的種群執(zhí)行模擬退火操作Step7.1判斷所有個體是否都執(zhí)行過退火操作?如果是,執(zhí)行Step8,否則,執(zhí)行以下循環(huán)Step7.2取種群中未退火個體Step7.3判斷最優(yōu)適應度是否連續(xù)s步?jīng)]有發(fā)生變化?如果穩(wěn)定,執(zhí)行Step7.1Step7.4由SA狀態(tài)產(chǎn)生函數(shù)產(chǎn)生新個體Step7.5如果適應度增加則更新個體,否則,以概率min(1,exp(s1-s2)/tk)接受新個體Step7.6更新最優(yōu)適應度及最優(yōu)個體Step8進行退溫操作,tk=λ×tk-1,返回Step4Step9算法結束,輸出結果其中,SA算法中狀態(tài)生成函數(shù)的步驟描述如下:Step1隨機選擇一個子任務,即在任務匹配矩陣NPMm×n中選擇了一個基因列Step2計算該子任務分配給不同設計者的效率,并將該任務分配與執(zhí)行效率最高即消耗時間最短的設計者(如果原方案已經(jīng)符合該原則,則無須改動)Step3如果此策略不符合分配策略的兩個約束條件,則轉Step1,否則結束通過采用文獻和文獻中的調(diào)度實例,得實驗結果如表2所示。其中t=20,k=4,s=20,λ=0.8,tk=5。顯然,對于上述小規(guī)模問題,不論是改進的自適應GA算法還是GASA算法,效果明顯優(yōu)于文獻中算法,獲得最優(yōu)值的頻率高的多。3算法之間的比較構造復雜實例驗證算法效果,共4個設計者,10個設計子任務,其任務前趨圖如圖2所示。時間效率矩陣如表3所示。采用本文中的兩類算法進行實現(xiàn),其比較結果如表4。對于復雜實例,改進的GASA算法得到最優(yōu)值的次數(shù)明顯高于自適應GA算法。文獻中的Q學習算法與多步Q學習算法,對于上述小規(guī)模實例均能達到最優(yōu),其中多步Q學習算法收斂速度更快。但是當面臨規(guī)模大的問題時,Q學習算法狀態(tài)-動作空間亦很大,收斂速度明顯下降,耗時多。4算法對比分析協(xié)同設計是多個設計者共同協(xié)作完成一件復雜設計任務的過程。各個子任務之間存在著約束關系,相互制約。對子任務進行合理排序和規(guī)劃,能夠促進協(xié)同設計的效率。本文為了提高任務分配及規(guī)劃的質(zhì)量,改進了自適應遺傳算法和GASA算法,描述了算法實現(xiàn)的詳細步驟,進行了算法比較:首先分別用這兩個算法實現(xiàn)引用任務實