一種協(xié)同設(shè)計(jì)任務(wù)調(diào)度算法的研究

一種協(xié)同設(shè)計(jì)任務(wù)調(diào)度算法的研究

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