淺論量子粒子群優(yōu)化的DAG并行任務(wù)調(diào)度

　　網(wǎng)絡(luò)并行計(jì)算環(huán)境下的任務(wù)調(diào)度問(wèn)題是指在一定約束條件下,如何將一組任務(wù)分配到多臺(tái)處理機(jī)上執(zhí)行的組合優(yōu)化問(wèn)題,其已被證明是NP完全問(wèn)題,不可能在多項(xiàng)式時(shí)間內(nèi)找到問(wèn)題的最優(yōu)解[1,2]。目前常見(jiàn)的并行任務(wù)調(diào)度問(wèn)題按照任務(wù)之間有無(wú)數(shù)據(jù)依賴(lài)關(guān)系可以劃分為獨(dú)立任務(wù)調(diào)度和依賴(lài)關(guān)系任務(wù)調(diào)度。前者在調(diào)度任務(wù)時(shí)不需要考慮任務(wù)之間的數(shù)據(jù)依賴(lài)關(guān)系;而后者通常用有向無(wú)環(huán)圖(DAG)表示任務(wù)之間的數(shù)據(jù)依賴(lài)關(guān)系,在調(diào)度過(guò)程中滿(mǎn)足任務(wù)之間的數(shù)據(jù)依賴(lài)關(guān)系。依賴(lài)關(guān)系任務(wù)調(diào)度的求解優(yōu)化過(guò)程比獨(dú)立任務(wù)調(diào)度的要復(fù)雜許多,且其適用范圍也更廣。以DAG表示的并行任務(wù)模型的研究得到了廣泛關(guān)注和迅速發(fā)展。近年出現(xiàn)的一些啟發(fā)式算法(如模擬退火算法、遺傳算法等)為求解此類(lèi)NP完全問(wèn)題提供了新的途徑[3~5],但是這些算法有些復(fù)雜性太高難以實(shí)現(xiàn),有些實(shí)現(xiàn)起來(lái)太費(fèi)時(shí),所以有必要尋求更好的算法來(lái)解決此問(wèn)題。

　　粒子群優(yōu)化(PSO)算法是由Kennedy等人[6]提出的一種源于對(duì)鳥(niǎo)群捕食行為模擬的進(jìn)化計(jì)算技術(shù),已成為進(jìn)化計(jì)算的一個(gè)最吸引人的分支。與遺傳算法類(lèi)似,PSO是一種基于迭代的優(yōu)化方法,系統(tǒng)初始化為一組隨機(jī)解,通過(guò)迭代搜尋最優(yōu)值,但是在許多實(shí)際應(yīng)用領(lǐng)域,更勝于遺傳算法,尤其是在非線性?xún)?yōu)化問(wèn)題上。量子粒子群優(yōu)化(QPSO)算法是在傳統(tǒng)的PSO基礎(chǔ)上提出的一種新型的具有高效率全局搜索能力的進(jìn)化算法[7,8]。它主要是引入量子物理的思想改進(jìn)了PSO的進(jìn)化方法,即更新粒子位置的方法;在更新粒子位置時(shí)重點(diǎn)考慮各個(gè)粒子的當(dāng)前局部最優(yōu)位置信息和全局最優(yōu)位置信息。QPSO具有調(diào)整參數(shù)少、容易實(shí)現(xiàn)、收斂能力強(qiáng)等優(yōu)勢(shì)。為適應(yīng)任務(wù)分配問(wèn)題的求解,本文設(shè)計(jì)出合適的粒子編碼,利用改進(jìn)的量子粒子群算法求解任務(wù)分配問(wèn)題,并與其他算法相比較。實(shí)驗(yàn)結(jié)果表明,本文提出的算法可以獲得質(zhì)量更高的解職稱(chēng)論文。

　　1 問(wèn)題描述

　　本模型的計(jì)算系統(tǒng)由一系列異構(gòu)的處理機(jī)組成,需要處理的總?cè)蝿?wù)已分解成一系列子任務(wù)。模型的約束條件為:任務(wù)執(zhí)行具有非搶占性,即處理機(jī)只有在執(zhí)行完某個(gè)任務(wù)之后才能處理另外一個(gè)任務(wù);另外這些任務(wù)之間具有前驅(qū)后繼的數(shù)據(jù)依賴(lài)關(guān)系,某個(gè)子任務(wù)只有在其所有的前驅(qū)任務(wù)處理完畢后才能開(kāi)始執(zhí)行。該模型的調(diào)度目標(biāo)就是要使得整個(gè)DAG圖的調(diào)度長(zhǎng)度最短。

　　為了便于分析問(wèn)題,可以用下列五元組表述:

　　Π=(P,G,Θ,Ψ,Ω)

　　其中:

　　P={P?1,P?2,…,P?n}為n個(gè)處理機(jī)的集合。

　　G是子任務(wù)集T的依賴(lài)關(guān)系圖,它通過(guò)DAG來(lái)表示各個(gè)子任務(wù)間的調(diào)度約束關(guān)系。G=(T,E),其中T={T?1,T?2,…,T?m}為m個(gè)子任務(wù)的集合,一個(gè)子任務(wù)T?i就是圖G中的一個(gè)節(jié)點(diǎn),E是任務(wù)依賴(lài)關(guān)系圖中的有向邊集?！碩?i,T?j〉∈E(i,j=1,2,…,m),則表示在子任務(wù)T?i沒(méi)有完成之前,任務(wù)T?j不能執(zhí)行。這時(shí)稱(chēng)T?i為T(mén)?j的一個(gè)前驅(qū),T?j為T(mén)?i的一個(gè)后繼,E可用鄰接矩陣存儲(chǔ)。

　　Θ是一個(gè)m×n矩陣,其元素θij表示任務(wù)T?i在處理機(jī)P?j上的執(zhí)行時(shí)間,假設(shè)每個(gè)任務(wù)的執(zhí)行時(shí)間預(yù)知(i=1,2,…,m;?j=1,2,…,n)。

　　Ψ是一個(gè)m×m矩陣,其元素ψij表示任務(wù)T?i與T?j之間的數(shù)據(jù)傳輸延時(shí)(i,j=1,2,…,m),同時(shí)假設(shè)各處理機(jī)間的通信能力是相同的,且忽略網(wǎng)絡(luò)擁塞,即傳輸?shù)臄?shù)據(jù)量是惟一影響ψij大小的因素。

　　Ω是一個(gè)m×n的任務(wù)分配矩陣,其中ωij=1表示T?i分配到處理機(jī)P?j上執(zhí)行;否則ωij=0(i=1,2,…,m;j=1,2,…,n)。

　　要實(shí)現(xiàn)的目標(biāo)是尋找一個(gè)分配調(diào)度策略,將m個(gè)子任務(wù)分配到n個(gè)處理機(jī)上,合理調(diào)度各個(gè)子任務(wù)的執(zhí)行次序,使得各子任務(wù)在滿(mǎn)足依賴(lài)關(guān)系圖G的約束下,整個(gè)任務(wù)的完成時(shí)間最短?，F(xiàn)假設(shè)某一合法的分配調(diào)度S,將T中的m個(gè)子任務(wù)分配到n個(gè)處理機(jī)上,其中子任務(wù)T?i被分配到處理機(jī)P?j上執(zhí)行,那么子任務(wù)T?i在處理機(jī)P?j上的執(zhí)行時(shí)間滿(mǎn)足以下兩式:

　　St(T?i,P?j)=maxT?k∈Pred(T?i)(Ft(T?k,P?r)+(1-ωkj)ψki)(1)

　　Ft(T?i,P?j)=St(T?i,P?j)+θij;i,k=1,2,…,m;j,r=1,2,…,n

　　(2)

　　其中:St(T?i,P?j)和Ft(T?i,P?j)分別表示子任務(wù)T?i在處理機(jī)P?j上的開(kāi)始執(zhí)行時(shí)刻和結(jié)束執(zhí)行時(shí)刻;Pred(T?i)表示子任務(wù)T?i的前驅(qū)節(jié)點(diǎn)集合,假設(shè)子任務(wù)T?k∈Pred(T?i)被分配到處理機(jī)?P?r上。

　　根據(jù)式(1)(2)迭代計(jì)算,可得到所有子任務(wù)的結(jié)束執(zhí)行時(shí)刻。設(shè)Γ(S)為在調(diào)度策略S下完成任務(wù)所使用的總時(shí)間,那么:Γ(S)=max(Ft(T?i,P?j));?i=1,2,…,m;j=1,2,…,n。

　　任務(wù)調(diào)度目標(biāo)就是min(Γ(S))?S,即尋找一個(gè)分配調(diào)度S,使得Γ(S)最小。

　　鑒于本文主要考慮任務(wù)調(diào)度問(wèn)題,在不失問(wèn)題一般性的情況下,可忽略數(shù)據(jù)傳輸延時(shí),即在下文中可假設(shè)所有的ψij=0。

　　2 算法

　　2.1 PSO算法

　　粒子群優(yōu)化(PSO)算法是一種進(jìn)化計(jì)算方法,是一種基于迭代的優(yōu)化工具。該算法通過(guò)群體中各粒子間的合作與競(jìng)爭(zhēng)來(lái)搜索全局最優(yōu)點(diǎn)。

　　系統(tǒng)初始化為一組共n個(gè)隨機(jī)解,通過(guò)迭代搜尋整個(gè)群體的最優(yōu)值。粒子i的當(dāng)前位置為x?i=(xi1,xi2,…,xid),其飛行速度記為v?i=(vi1,vi2,…,vid),在解空間中追隨適應(yīng)度最優(yōu)的粒子進(jìn)行搜索。在每一次迭代中, 粒子通過(guò)跟蹤兩個(gè)“極值”來(lái)更新自己:a)每個(gè)粒子本身所找到的最優(yōu)解pbest。如果粒子當(dāng)前位置對(duì)應(yīng)的適應(yīng)度小于pbest的適應(yīng)度,則pbest更新為當(dāng)前位置。b)整個(gè)種群從起始到目前所找到的最優(yōu)解gbest。每個(gè)粒子按以下兩個(gè)公式進(jìn)行動(dòng)態(tài)進(jìn)化,調(diào)整粒子的位置:

　　vi,d(t+1)=wvi,d(t)+c?1r1,d(t)(pbest?i,d-xi,d(t))+?c?2r2,d(t)(gbest?d(t)-xi,d(t))(3)

　　x?i(t+1)=x?i(t)+v?i(t+1)(4)

　　其中:w是慣性權(quán)重,動(dòng)態(tài)調(diào)整慣性權(quán)重以平衡收斂的全局性和收斂速度;c?1和c?2為加速常數(shù),通常在0～2取值,c?1調(diào)節(jié)粒子飛向自身最好位置方向的步長(zhǎng),c?2調(diào)節(jié)粒子飛向全局最好位置方向的步長(zhǎng);r1,d(t),r2,d(t)～U(0,1),且d =1,2,…,n。為了減少在進(jìn)化過(guò)程中粒子離開(kāi)搜索空間的可能性,粒子的每一維速度被限定在[-Vmax,Vmax]內(nèi)。

　　2.2 QPSO算法

　　`Sun等人從量子力學(xué)的角度,通過(guò)對(duì)粒子收斂行為的研究,基于粒子群算法提出了一種新的算法模型——量子粒子群(QPSO)算法。在該算法中,由于粒子滿(mǎn)足聚集態(tài)的性質(zhì)完全不同,使粒子在整個(gè)可行解空間中進(jìn)行搜索尋求全局最優(yōu)解,因而QPSO算法在搜索能力上遠(yuǎn)遠(yuǎn)優(yōu)于所有已開(kāi)發(fā)的PSO算法。

　　QPSO算法參數(shù)個(gè)數(shù)少,進(jìn)化方程的形式更加簡(jiǎn)單,更容易控制。在QPSO算法中,每一個(gè)粒子必須收斂于各自的隨機(jī)點(diǎn)P?i,粒子按照下面的三式移動(dòng):

　　mbest=1m?mi=1P?i=(1m?mi=1Pi1,…,1m?mi=1Pij)(5)

　　PPij=fPij+(1-f)Pgj, f=rand(6)

　　xij=PPij±a|mbest?j-xij|ln(1/u),u=rand(7)

　　其中:mbest是粒子群pbest的中間位置;Pij為粒子本身所找到的最優(yōu)解pbest;Pgj為整個(gè)粒子群目前找到的最優(yōu)解gbest; PPij為Pij與Pgj之間的隨機(jī)點(diǎn);a為QPSO的收縮擴(kuò)張系數(shù),它是QPSO收斂的一個(gè)重要參數(shù),第t次迭代時(shí)一般可取

　　a=amax-t(amax-amin)/tmax(8)

　　其中:tmax是迭代的最大次數(shù),amax與amin分別是最大和最小系數(shù)。QPSO的算法流程如下:

　　a)迭代次數(shù)t=0,對(duì)種群的每個(gè)粒子的位置向量進(jìn)行初始化。

　　b)根據(jù)目標(biāo)函數(shù)計(jì)算每個(gè)粒子的目標(biāo)函數(shù)值。

　　c)更新每個(gè)粒子的新局部最優(yōu)位置P?i。

　　d)更新粒子群的全局最優(yōu)位置P?g。

　　e)根據(jù)式(5)計(jì)算mbest。

　　f)根據(jù)式(6)計(jì)算每個(gè)粒子隨機(jī)點(diǎn)PP?i。

　　g)根據(jù)式(7)(以一定的概率取加或減)更新每個(gè)粒子的新位置。

　　h)令t=t+1,返回到b),重新計(jì)算,直到終止條件滿(mǎn)足。

　　3 基于QPSO的DAG并行任務(wù)調(diào)度

　　3.1 編碼與解碼

　　任務(wù)調(diào)度的常見(jiàn)編碼包括基于任務(wù)的編碼、基于操作的編碼和基于優(yōu)先規(guī)則的編碼等。由于DAG并行任務(wù)調(diào)度的復(fù)雜性,采用任一種上述編碼形式均無(wú)法保證所有解的合法性,這將浪費(fèi)大量的求解時(shí)間。本文設(shè)計(jì)了一種復(fù)合的編碼方案:編碼長(zhǎng)度為2 m,可描述為兩個(gè)向量,第一個(gè)向量采用基于優(yōu)先規(guī)則的編碼方式,為一個(gè)包含m維的向量(R?1,R?2,…,R?m)。其中R?i表示在算法迭代過(guò)程中第i次迭代時(shí)發(fā)生的沖突利用優(yōu)先規(guī)則R?i消除。本文選擇了五種優(yōu)先規(guī)則,包括最短執(zhí)行時(shí)間(SPT)、最長(zhǎng)執(zhí)行時(shí)間(LPT)、最早開(kāi)工時(shí)間(EST)、最早完工時(shí)間(EFT)、最晚完工時(shí)間(LFT),數(shù)字0、1、2、3、4分別對(duì)應(yīng)優(yōu)先規(guī)則SPT、LPT、EST、EFT、LFT。第二個(gè)向量是處理機(jī)分配向量,即一個(gè)包含m維的向量(M?1,M?2,…,M?m)。其中M?i表示編號(hào)為i的子任務(wù)被分配到編號(hào)為(M?i)的處理機(jī)上執(zhí)行(所有處理機(jī)編號(hào)為0,1,…,n-1)。

　　在解碼過(guò)程中,設(shè)t為調(diào)度的時(shí)間步,PS為調(diào)度列表。其中PS?t為第t步調(diào)度執(zhí)行的子任務(wù);TS為所有前驅(qū)已經(jīng)被調(diào)度的子任務(wù)所構(gòu)成的集合。解碼算法如下:

　　a)令t=1,PS為空,TS由所有無(wú)前驅(qū)的子任務(wù)構(gòu)成。

　　b)由TS中所有子任務(wù)編碼,在處理機(jī)分配向量(M?1,?M?2,…,M?m)中找到分配給每個(gè)子任務(wù)的處理機(jī),并在Θ中找到具體執(zhí)行時(shí)間。

　　c)依據(jù)約束條件和執(zhí)行時(shí)間,得到TS中每個(gè)子任務(wù)對(duì)應(yīng)的指標(biāo)時(shí)間(開(kāi)工、完工或執(zhí)行時(shí)間),由編碼R?t所對(duì)應(yīng)的優(yōu)先規(guī)則選出一個(gè)子任務(wù)(如優(yōu)先規(guī)則為最短執(zhí)行時(shí)間,則選TS中執(zhí)行時(shí)間最短的子任務(wù),如果有多個(gè)子任務(wù)符合優(yōu)先規(guī)則,則任選一個(gè)),該子任務(wù)就是PS?t,從TS中刪除它,并將其加入PS的尾部。

　　d)逐個(gè)考察PS?t的后繼子任務(wù),如果該子任務(wù)無(wú)其他前驅(qū),或其他前驅(qū)都已被調(diào)度執(zhí)行,則將其加入TS中。

　　e)令t=t+1,若t

　　通過(guò)下面示例說(shuō)明解碼過(guò)程:

　　優(yōu)先規(guī)則向量:

　　(032140)

　　即:(SPT EFT EST LPT LFT SPT)

　　處理機(jī)分配向量:

　　(0 1 1 0 1 0)

　　即(P1 P2 P2 P1 P2 P1)

　　在Θ中查到的處理時(shí)間:

　　(2 4 6 5 3 7)

　　處理時(shí)間指1～6號(hào)子任務(wù)在對(duì)應(yīng)處理機(jī)上的執(zhí)行時(shí)間。

　　根據(jù)示例數(shù)據(jù)得到的調(diào)度列表PS為(T?1 T?2 T?4 T?6 T?3 T?5),甘特圖如圖2所示。

　　由上述編碼方式和解碼過(guò)程可知,本文編碼能保證調(diào)度的可行性,且碼長(zhǎng)較短,無(wú)冗余,解碼復(fù)雜性不高。

　　3.2 QPSO中向量的計(jì)算方法

　　對(duì)每個(gè)粒子,它的優(yōu)先規(guī)則向量和處理機(jī)分配向量可以表示為Xpriority(1..m)和Xmachine(1..m),按式(5)~(7)計(jì)算這兩個(gè)向量。由于前面所述的QPSO為連續(xù)空間算法,而DAG并行任務(wù)調(diào)度問(wèn)題為整數(shù)規(guī)劃問(wèn)題,將離散優(yōu)化轉(zhuǎn)變成對(duì)實(shí)數(shù)向量的連續(xù)優(yōu)化,具體過(guò)程如下:

　　a)將每個(gè)向量切斷分成若干個(gè)子串,各段子串的長(zhǎng)度可以相等,也可以不相等,子串形如(q?1,q?2,…,q?k)。

　　b)從整數(shù)組成的子串到實(shí)數(shù)作一個(gè)映射,可表示為

　　r=c×?ki=1q?i×b??k-i(9)

　　其中:r為映射的實(shí)數(shù);c是常數(shù),一般取足夠小的實(shí)數(shù),本文取值為0.01;b為基數(shù),對(duì)于Xpriority,b取值為5,對(duì)于Xmachine,b取值為n。

　　c)在計(jì)算任務(wù)執(zhí)行總時(shí)間前,需將r轉(zhuǎn)換為子串,即式(9)的逆映射:

　　q?i=(rc-?i-1j=1q?j×b??k-j)div b??k-i(10)

　　其中:div為整除,得到的商q?i為整數(shù),在實(shí)際運(yùn)算時(shí),可用一個(gè)循環(huán),i從1~k得到子串中所有分量。

　　例如9個(gè)子任務(wù)的情況,Xpriority=(2 4 2 1 4 3 4 1 0),分為三段,各子串長(zhǎng)度均為3。

　　子串 (242); (143); (410)

　　變換后得到

　　r0.720.481.05

　　經(jīng)過(guò)迭代后的情況:

　　逆變換后得到

　　r0.531.120.91

　　子串(203)(422)(331)

　　在初始化時(shí),可省掉式(9)的轉(zhuǎn)換過(guò)程,直接給粒子位置賦實(shí)數(shù)。

　　解決了連續(xù)化問(wèn)題之后,還有一個(gè)邊界問(wèn)題,如上例r的取值為[0,1.24],如迭代過(guò)程中z的運(yùn)算結(jié)果超出范圍時(shí),將r值取在邊界上。若r<0,取值0;r>1.24,取值1.24。

　　通過(guò)上述映射和逆映射,整數(shù)規(guī)劃問(wèn)題轉(zhuǎn)換為連續(xù)優(yōu)化問(wèn)題,從而可以利用QPSO優(yōu)化獲得高質(zhì)量的解。

　　3.3 算法流程

　　a)初始化粒子群,根據(jù)編碼方案設(shè)定各粒子的隨機(jī)位置。

　　b)根據(jù)式(10)將每個(gè)粒子的實(shí)數(shù)向量轉(zhuǎn)換為整數(shù)向量。

　　c)對(duì)每個(gè)粒子的整數(shù)向量解碼后,計(jì)算每個(gè)粒子的目標(biāo)函數(shù)值。

　　d)更新每個(gè)粒子的局部最優(yōu)值P?i。

　　e)更新粒子群的全局最優(yōu)值P?g。

　　f)根據(jù)式(5)計(jì)算mbest。

　　g)根據(jù)式(6)計(jì)算每個(gè)粒子隨機(jī)點(diǎn)PP?i。

　　h)根據(jù)式(7)更新每個(gè)粒子的新位置。

　　i)返回b)步,直到滿(mǎn)足迭代的次數(shù)。

　　4 仿真實(shí)驗(yàn)與結(jié)果分析

　　4.1 實(shí)驗(yàn)參數(shù)選取

　　本文的仿真實(shí)驗(yàn)是在MATLAB軟件上實(shí)現(xiàn)的。實(shí)驗(yàn)所用DAG圖隨機(jī)生成,每個(gè)任務(wù)節(jié)點(diǎn)有1～4個(gè)前驅(qū)與后繼,估計(jì)運(yùn)行時(shí)間θij為1～50 s的隨機(jī)數(shù)。實(shí)驗(yàn)計(jì)算了文獻(xiàn)[3,4]的算法、PSO與本文的QPSO共四種情況,算法中主要參數(shù):種群大小為80,終止代數(shù)為1 500,amax取值1,amin取值0.5;PSO的慣性權(quán)重w與QPSO中的收縮擴(kuò)張系數(shù)a取值相同,c?1和c?2均為2,編碼、解碼、連續(xù)化與邊界問(wèn)題均使用本文的方案;文獻(xiàn)[3]算法的雜交概率為1.0,變異概率為0.05;文獻(xiàn)[4]算法的內(nèi)部雜交概率為0.8,遷移概率為0.2,演化策略中的參數(shù)為μ/λ=5。

　　4.2 計(jì)算結(jié)果與分析

　　對(duì)于隨機(jī)生成的同一個(gè)DAG圖,分別用上述四種算法進(jìn)行計(jì)算,記錄各算法收斂時(shí)得到的最優(yōu)解的完成時(shí)間和收斂時(shí)的進(jìn)化代數(shù)。計(jì)算結(jié)果如表1所示。為了消除數(shù)據(jù)隨機(jī)性的影響,更好地反映算法的性能,表1中的進(jìn)化代數(shù)是100次進(jìn)化的平均收斂代數(shù),完成時(shí)間是所有100次進(jìn)化中得到的最優(yōu)解的平均完成時(shí)間。圖3為四個(gè)處理機(jī)100個(gè)子任務(wù)情況下四種算法分別進(jìn)化的靜態(tài)性能曲線,列出了各算法在不同進(jìn)化代數(shù)時(shí)所找到的最優(yōu)解。表2為四種算法在進(jìn)化中能收斂到其最優(yōu)解的次數(shù)占實(shí)驗(yàn)總次數(shù)的百分比。

　　處理機(jī)?個(gè)數(shù)子任務(wù)?個(gè)數(shù)

　　完成時(shí)間/s

　　文獻(xiàn)[3]?算法文獻(xiàn)[4]?算法PSO?算法本文?算法

　　收斂時(shí)的進(jìn)化代數(shù)

　　2528527127926539312529

　　250565543551538166131108125

　　1001 5481 4291 4271 416418339285323

　　2519318618817953463338

　　450457429428417194168135157

　　1001 1981 1361 1391 073516468323339

　　2515214113813473544952

　　850341297292281336217163212

　　1001 106911923875727621538601

　　各算法子任務(wù)個(gè)數(shù)25子任務(wù)個(gè)數(shù)50子任務(wù)個(gè)數(shù)100

　　文獻(xiàn)[3]算法876448

　　文獻(xiàn)[4]算法969281

　　PSO算法928967

　　本文算法1009996

　　a)在任務(wù)數(shù)較多、處理機(jī)較多的情況下,PSO與本文QPSO算法的收斂速度比文獻(xiàn)[3]算法快很多,但與文獻(xiàn)[4]算法比較時(shí),PSO算法的收斂速度明顯比文獻(xiàn)[4]算法快,本文QPSO算法則與文獻(xiàn)[4]算法相當(dāng);而在任務(wù)數(shù)少的情況下,除文獻(xiàn)[3]算法稍慢,其他算法相差不大。

　　b)本文QPSO算法能找到的最優(yōu)解比文獻(xiàn)[3,4]算法有明顯的提高,尤其是子任務(wù)數(shù)較多、處理機(jī)數(shù)較多時(shí)。

　　c)PSO與本文QPSO算法比較時(shí),發(fā)現(xiàn)QPSO算法的收斂速度比PSO算法慢,但得到的最優(yōu)解比PSO算法好。

　　這是因?yàn)?首先,本文對(duì)問(wèn)題的編碼能夠覆蓋整個(gè)解空間,相對(duì)來(lái)說(shuō)文獻(xiàn)[3,4]的算法只能從一個(gè)相對(duì)較小的空間內(nèi)搜索;其次,本文采用了離散空間到連續(xù)空間的轉(zhuǎn)換過(guò)程,它不僅滿(mǎn)足了QPSO算法對(duì)待解問(wèn)題的取值要求,還在一定程度上能更好地保護(hù)與遺傳優(yōu)良的解片段。另外,PSO算法收斂過(guò)快,而QPSO的量子搜索方式對(duì)傳統(tǒng)的PSO算法有了很大的改進(jìn),實(shí)驗(yàn)證明可防止早熟。

　　5 結(jié)束語(yǔ)

　　基于DAG的并行任務(wù)調(diào)度問(wèn)題是NP難問(wèn)題,傳統(tǒng)的優(yōu)化算法很難求得全局最優(yōu)解,雖然已有人將遺傳算法應(yīng)用于此問(wèn)題,但結(jié)果有待進(jìn)一步改善。本文給出了新的問(wèn)題定義,對(duì)QPSO算法作出調(diào)整與改進(jìn),編碼表示采用了適合于任務(wù)調(diào)度問(wèn)題的優(yōu)先規(guī)則與處理機(jī)分配相結(jié)合的形式,并將離散空間優(yōu)化問(wèn)題轉(zhuǎn)換為連續(xù)空間優(yōu)化問(wèn)題,使得QPSO有較好的搜索能力。最后通過(guò)仿真實(shí)驗(yàn)得到的一系列數(shù)據(jù),表明了本文的改進(jìn)QPSO算法比遺傳算法和PSO算法有更好的性能,并有理由認(rèn)為,合理的編碼表示與高效的搜索策略相結(jié)合是任務(wù)分配調(diào)度問(wèn)題全局尋優(yōu)的有效途徑。