核心期刊發(fā)表量子粒子群優(yōu)化的DAG并行任務(wù)調(diào)度

　　摘 要:任務(wù)調(diào)度是網(wǎng)絡(luò)并行計(jì)算系統(tǒng)的核心問題之一。在有向無環(huán)圖(DAG)描述問題的基礎(chǔ)上,提出了一種進(jìn)行并行任務(wù)調(diào)度的量子粒子群優(yōu)化算法。首先對(duì)DAG并行任務(wù)調(diào)度問題作出定義,并給出了優(yōu)化問題的目標(biāo);然后分別探討了問題的編碼表示、解碼方案、位置向量的計(jì)算方法、離散問題連續(xù)化、算法的總體流程等;最后給出算法的仿真實(shí)驗(yàn)情況與研究,實(shí)驗(yàn)結(jié)果表明,該算法有良好的全局尋優(yōu)性能和快捷的收斂速度,調(diào)度效果優(yōu)于遺傳算法和粒子群優(yōu)化算法。

　　關(guān)鍵詞:任務(wù)調(diào)度,量子粒子群優(yōu)化,有向無環(huán)圖,核心期刊發(fā)表

　　Research on DAG parallel task scheduling problem based on ?quantum-behaved particle swarm optimization

　　ZHANG Cong,SHEN Hui-zhang

　　(Antai College of Economics & Management, Shanghai Jiaotong University, Shanghai 200052, China)

　　Abstract:Task scheduling is one of the important problems in parallel computing system.This paper proposed a quantum-?behaved particle swarm optimization algorithm for task scheduling based on directed acyclic graph.First redefined the parallel task scheduling problem and its aim.Then discussed the representation of the encoding, the procedure of the decoding, the computational method of position vector, the continuative of the discrete problem and the structure of the algorithm respectively.In the end,presented the algorithm simulation,experiment result analysis and the conclusions.The simulation results show that this algorithm has better global optimizing ability and more rapid convergence, and it is superior to genetic algorithm and particle swarm optimization algorithm.

　　Key words:task scheduling; quantum-behaved particle swarm optimization(QPSO); directed acyclic graph(DAG)

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

　　粒子群優(yōu)化(PSO)算法是由Kennedy等人提出的一種源于對(duì)鳥群捕食行為模擬的進(jìn)化計(jì)算技術(shù),已成為進(jìn)化計(jì)算的一個(gè)最吸引人的分支。與遺傳算法類似,PSO是一種基于迭代的優(yōu)化方法,系統(tǒng)初始化為一組隨機(jī)解,通過迭代搜尋最優(yōu)值,但是在許多實(shí)際應(yīng)用領(lǐng)域,更勝于遺傳算法,尤其是在非線性優(yōu)化問題上。量子粒子群優(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ù)分配問題的求解,本文設(shè)計(jì)出合適的粒子編碼,利用改進(jìn)的量子粒子群算法求解任務(wù)分配問題,并與其他算法相比較。實(shí)驗(yàn)結(jié)果表明,本文提出的算法可以獲得質(zhì)量更高的解職稱論文。

　　1 問題描述

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

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

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

　　其中:

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

　　G是子任務(wù)集T的依賴關(guān)系圖,它通過DAG來表示各個(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ù)依賴關(guān)系圖中的有向邊集�！碩?i,T?j〉∈E(i,j=1,2,…,m),則表示在子任務(wù)T?i沒有完成之前,任務(wù)T?j不能執(zhí)行。這時(shí)稱T?i為T?j的一個(gè)前驅(qū),T?j為T?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ù)在滿足依賴關(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í)間滿足以下兩式:

　　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上的開始執(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)度問題,在不失問題一般性的情況下,可忽略數(shù)據(jù)傳輸延時(shí),即在下文中可假設(shè)所有的ψij=0。

　　2 算法

　　2.1 PSO算法

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

　　系統(tǒng)初始化為一組共n個(gè)隨機(jī)解,通過迭代搜尋整個(gè)群體的最優(yōu)值。粒子i的當(dāng)前位置為x?i=(xi1,xi2,…,xid),其飛行速度記為v?i=(vi1,vi2,…,vid),在解空間中追隨適應(yīng)度最優(yōu)的粒子進(jìn)行搜索。在每一次迭代中, 粒子通過跟蹤兩個(gè)“極值”來更新自己: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)化過程中粒子離開搜索空間的可能性,粒子的每一維速度被限定在[-Vmax,Vmax]內(nèi)。

　　2.2 QPSO算法

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

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

　　3.1 編碼與解碼

　　任務(wù)調(diào)度的常見編碼包括基于任務(wù)的編碼、基于操作的編碼和基于優(yōu)先規(guī)則的編碼等。由于DAG并行任務(wù)調(diào)度的復(fù)雜性,采用任一種上述編碼形式均無法保證所有解的合法性,這將浪費(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表示在算法迭代過程中第i次迭代時(shí)發(fā)生的沖突利用優(yōu)先規(guī)則R?i消除。本文選擇了五種優(yōu)先規(guī)則,包括最短執(zhí)行時(shí)間(SPT)、最長(zhǎng)執(zhí)行時(shí)間(LPT)、最早開工時(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)。

　　在解碼過程中,設(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由所有無前驅(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í)間(開工、完工或執(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ù)無其他前驅(qū),或其他前驅(qū)都已被調(diào)度執(zhí)行,則將其加入TS中。

　　e)令t=t+1,若t　　通過下面示例說明解碼過程:

　　任務(wù)的DAG如圖1所示。

　　優(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所示。

　　由上述編碼方式和解碼過程可知,本文編碼能保證調(diào)度的可行性,且碼長(zhǎng)較短,無冗余,解碼復(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)度問題為整數(shù)規(guī)劃問題,將離散優(yōu)化轉(zhuǎn)變成對(duì)實(shí)數(shù)向量的連續(xù)優(yōu)化,具體過程如下:

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

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

　　r=c×?ki=1q?i×bk-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×bk-j)div bk-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)過迭代后的情況:

　　逆變換后得到

　　r0.531.120.91

　　子串(203)(422)(331)

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

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

　　通過上述映射和逆映射,整數(shù)規(guī)劃問題轉(zhuǎn)換為連續(xù)優(yōu)化問題,從而可以利用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)步,直到滿足迭代的次數(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ù)化與邊界問題均使用本文的方案;文獻(xiàn)算法的雜交概率為1.0,變異概率為0.05;文獻(xiàn)算法的內(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ù)的百分比。

　　表1 仿真實(shí)驗(yàn)結(jié)果

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

　　完成時(shí)間/s

　　文獻(xiàn)?算法文獻(xiàn)?算法PSO?算法本文?算法

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

　　2528527127926539312529

　　250565543551538166131108125

　　1001 5481 4291 4271 416418339285323

　　2519318618817953463338

　　450457429428417194168135157

　　1001 1981 1361 1391 073516468323339

　　2515214113813473544952

　　850341297292281336217163212

　　1001 106911923875727621538601

　　表2 收斂到其已知最優(yōu)解的次數(shù)占進(jìn)化總次數(shù)的百分比%

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

　　文獻(xiàn)算法876448

　　文獻(xiàn)算法969281

　　PSO算法928967

　　本文算法1009996

　　由表1、2和算法的靜態(tài)性能曲線可以得出:

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

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

　　5 結(jié)束語

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