版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
基于量子粒子群優(yōu)化的DAG并行任務(wù)調(diào)度討論摘要:任務(wù)調(diào)度是網(wǎng)絡(luò)并行計(jì)算系統(tǒng)的核心問題之一。在有向無環(huán)圖(dag)描繪問題的根底上,提出了一種進(jìn)展并行任務(wù)調(diào)度的量子粒子群優(yōu)化算法。首先對(duì)dag并行任務(wù)調(diào)度問題作出定義,并給出了優(yōu)化問題的目的;然后分別討論了問題的編碼表示、解碼方案、位置向量的計(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)圖?researhndagparalleltaskshedulingprblebasedn?quantu-behavedpartilesarptiizatinzhangng,shenhui-zhang(antaillegefenisanageent,shanghaijiatnguniversity,shanghai200052,hina)abstrat:taskshedulingisneftheiprtantprblesinparallelputingsyste.thispaperprpsedaquantu-?behavedpartilesarptiizatinalgrithfrtaskshedulingbasedndiretedayligraph.firstredefinedtheparalleltaskshedulingprbleanditsai.thendisussedtherepresentatinftheending,thepredurefthededing,theputatinalethdfpsitinvetr,heend,presentedthealgrithsiulatin,experientresultanalysisandthenlusins.thesiulatinresultsshthatthisalgrithhasbetterglbalptiizingabilityandrerapidnvergene,anditissuperirtgenetialgrithandpartilesarptiizatinalgrith.keyrds:tasksheduling;quantu-behavedpartilesarptiizatin(qps);diretedayligraph(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)注和迅速開展。近年出現(xiàn)的一些啟發(fā)式算法(如模擬退火算法、遺傳算法等)為求解此類np完全問題提供了新的途徑[3~5],但是這些算法有些復(fù)雜性太高難以實(shí)現(xiàn),有些實(shí)現(xiàn)起來太費(fèi)時(shí),所以有必要尋求更好的算法來解決此問題。粒子群優(yōu)化(ps)算法是由kennedy等人[6]提出的一種源于對(duì)鳥群捕食行為模擬的進(jìn)化計(jì)算技術(shù),已成為進(jìn)化計(jì)算的一個(gè)最吸引人的分支。與遺傳算法類似,ps是一種基于迭代的優(yōu)化方法,系統(tǒng)初始化為一組隨機(jī)解,通過迭代搜尋最優(yōu)值,但是在許多實(shí)際應(yīng)用領(lǐng)域,更勝于遺傳算法,尤其是在非線性優(yōu)化問題上。量子粒子群優(yōu)化(qps)算法是在傳統(tǒng)的ps根底上提出的一種新型的具有高效率全局搜索才能的進(jìn)化算法[7,8]。它主要是引入量子物理的思想改良了ps的進(jìn)化方法,即更新粒子位置的方法;在更新粒子位置時(shí)重點(diǎn)考慮各個(gè)粒子的當(dāng)前部分最優(yōu)位置信息和全局最優(yōu)位置信息。qps具有調(diào)整參數(shù)少、容易實(shí)現(xiàn)、收斂才能強(qiáng)等優(yōu)勢(shì)。為適應(yīng)任務(wù)分配問題的求解,本文設(shè)計(jì)出適宜的粒子編碼,利用改良的量子粒子群算法求解任務(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ù)處理完畢后才能開場(chǎng)執(zhí)行。該模型的調(diào)度目的就是要使得整個(gè)dag圖的調(diào)度長度最短。為了便于分析問題,可以用以下五元組表述:π=(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?}為個(gè)子任務(wù)的集合,一個(gè)子任務(wù)t?i就是圖g中的一個(gè)節(jié)點(diǎn),e是任務(wù)依賴關(guān)系圖中的有向邊集?!磘?i,t?j〉∈e(i,j=1,2,…,),那么表示在子任務(wù)t?i沒有完成之前,任務(wù)t?j不能執(zhí)行。這時(shí)稱t?i為t?j的一個(gè)前驅(qū),t?j為t?i的一個(gè)后繼,e可用鄰接矩陣存儲(chǔ)。θ是一個(gè)×n矩陣,其元素θij表示任務(wù)t?i在處理機(jī)p?j上的執(zhí)行時(shí)間,假設(shè)每個(gè)任務(wù)的執(zhí)行時(shí)間預(yù)知(i=1,2,…,;?j=1,2,…,n)。ψ是一個(gè)×矩陣,其元素ψij表示任務(wù)t?i與t?j之間的數(shù)據(jù)傳輸延時(shí)(i,j=1,2,…,),同時(shí)假設(shè)各處理機(jī)間的通信才能是一樣的,且忽略網(wǎng)絡(luò)擁塞,即傳輸?shù)臄?shù)據(jù)量是惟一影響ψij大小的因素。ω是一個(gè)×n的任務(wù)分配矩陣,其中ωij=1表示t?i分配到處理機(jī)p?j上執(zhí)行;否那么ωij=0(i=1,2,…,;j=1,2,…,n)。要實(shí)現(xiàn)的目的是尋找一個(gè)分配調(diào)度策略,將個(gè)子任務(wù)分配到n個(gè)處理機(jī)上,合理調(diào)度各個(gè)子任務(wù)的執(zhí)行次序,使得各子任務(wù)在滿足依賴關(guān)系圖g的約束下,整個(gè)任務(wù)的完成時(shí)間最短。現(xiàn)假設(shè)某一合法的分配調(diào)度s,將t中的個(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)=axt?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,…,;j,r=1,2,…,n(2)其中:st(t?i,p?j)和ft(t?i,p?j)分別表示子任務(wù)t?i在處理機(jī)p?j上的開場(chǎng)執(zhí)行時(shí)刻和完畢執(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ù)的完畢執(zhí)行時(shí)刻。設(shè)γ(s)為在調(diào)度策略s下完成任務(wù)所使用的總時(shí)間,那么:γ(s)=ax(ft(t?i,p?j));?i=1,2,…,;j=1,2,…,n。任務(wù)調(diào)度目的就是in(γ(s))?s,即尋找一個(gè)分配調(diào)度s,使得γ(s)最校鑒于本文主要考慮任務(wù)調(diào)度問題,在不失問題一般性的情況下,可忽略數(shù)據(jù)傳輸延時(shí),即在下文中可假設(shè)所有的ψij=0。2算法2.1ps算法粒子群優(yōu)化(ps)算法是一種進(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)=vi,d(t)+?1r1,d(t)(pbest?i,d-xi,d(t))+??2r2,d(t)(gbest?d(t)-xi,d(t))(3)x?i(t+1)=x?i(t)+v?i(t+1)(4)其中:是慣性權(quán)重,動(dòng)態(tài)調(diào)整慣性權(quán)重以平衡收斂的全局性和收斂速度;?1和?2為加速常數(shù),通常在0~2取值,?1調(diào)節(jié)粒子飛向自身最好位置方向的步長,?2調(diào)節(jié)粒子飛向全局最好位置方向的步長;r1,d(t),r2,d(t)~u(0,1),且d=1,2,…,n。為了減少在進(jìn)化過程中粒子分開搜索空間的可能性,粒子的每一維速度被限定在[-vax,vax]內(nèi)。2.2qps算法`sun等人從量子力學(xué)的角度,通過對(duì)粒子收斂行為的研究,基于粒子群算法提出了一種新的算法模型——量子粒子群(qps)算法。在該算法中,由于粒子滿足聚集態(tài)的性質(zhì)完全不同,使粒子在整個(gè)可行解空間中進(jìn)展搜索尋求全局最優(yōu)解,因此qps算法在搜索才能上遠(yuǎn)遠(yuǎn)優(yōu)于所有已開發(fā)的ps算法。qps算法參數(shù)個(gè)數(shù)少,進(jìn)化方程的形式更加簡(jiǎn)單,更容易控制。在qps算法中,每一個(gè)粒子必須收斂于各自的隨機(jī)點(diǎn)p?i,粒子按照下面的三式挪動(dòng):best=1?i=1p?i=(1?i=1pi1,…,1?i=1pij)(5)ppij=fpij+(1-f)pgj,f=rand(6)xij=ppij±a|best?j-xij|ln(1/u),u=rand(7)其中:best是粒子群pbest的中間位置;pij為粒子本身所找到的最優(yōu)解pbest;pgj為整個(gè)粒子群目前找到的最優(yōu)解gbest;ppij為pij與pgj之間的隨機(jī)點(diǎn);a為qps的收縮擴(kuò)張系數(shù),它是qps收斂的一個(gè)重要參數(shù),第t次迭代時(shí)一般可取a=aax-t(aax-ain)/tax(8)其中:tax是迭代的最大次數(shù),aax與ain分別是最大和最小系數(shù)。qps的算法流程如下:a)迭代次數(shù)t=0,對(duì)種群的每個(gè)粒子的位置向量進(jìn)展初始化。b)根據(jù)目的函數(shù)計(jì)算每個(gè)粒子的目的函數(shù)值。)更新每個(gè)粒子的新部分最優(yōu)位置p?i。d)更新粒子群的全局最優(yōu)位置p?g。e)根據(jù)式(5)計(jì)算best。f)根據(jù)式(6)計(jì)算每個(gè)粒子隨機(jī)點(diǎn)pp?i。g)根據(jù)式(7)(以一定的概率取加或減)更新每個(gè)粒子的新位置。h)令t=t+1,返回到b),重新計(jì)算,直到終止條件滿足。3基于qps的dag并行任務(wù)調(diào)度3.1編碼與解碼任務(wù)調(diào)度的常見編碼包括基于任務(wù)的編碼、基于操作的編碼和基于優(yōu)先規(guī)那么的編碼等。由于dag并行任務(wù)調(diào)度的復(fù)雜性,采用任一種上述編碼形式均無法保證所有解的合法性,這將浪費(fèi)大量的求解時(shí)間。本文設(shè)計(jì)了一種復(fù)合的編碼方案:編碼長度為2,可描繪為兩個(gè)向量,第一個(gè)向量采用基于優(yōu)先規(guī)那么的編碼方式,為一個(gè)包含維的向量(r?1,r?2,…,r?)。其中r?i表示在算法迭代過程中第i次迭代時(shí)發(fā)生的沖突利用優(yōu)先規(guī)那么r?i消除。本文選擇了五種優(yōu)先規(guī)那么,包括最短執(zhí)行時(shí)間(spt)、最長執(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è)包含維的向量(?1,?2,…,?)。其中?i表示編號(hào)為i的子任務(wù)被分配到編號(hào)為(?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ī)分配向量(?1,??2,…,?)中找到分配給每個(gè)子任務(wù)的處理機(jī),并在θ中找到詳細(xì)執(zhí)行時(shí)間。)根據(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,假設(shè)t通過下面例如說明解碼過程:任務(wù)的dag如圖1所示。優(yōu)先規(guī)那么向量:(032140)即:(spteftestlptlftspt)處理機(jī)分配向量:(011010)即(p1p2p2p1p2p1)在θ中查到的處理時(shí)間:(246537)處理時(shí)間指1~6號(hào)子任務(wù)在對(duì)應(yīng)處理機(jī)上的執(zhí)行時(shí)間。根據(jù)例如數(shù)據(jù)得到的調(diào)度列表ps為(t?1t?2t?4t?6t?3t?5),甘特圖如圖2所示。由上述編碼方式和解碼過程可知,本文編碼能保證調(diào)度的可行性,且碼長較短,無冗余,解碼復(fù)雜性不高。3.2qps中向量的計(jì)算方法對(duì)每個(gè)粒子,它的優(yōu)先規(guī)那么向量和處理機(jī)分配向量可以表示為xpririty(1..)和xahine(1..),按式(5)~(7)計(jì)算這兩個(gè)向量。由于前面所述的qps為連續(xù)空間算法,而dag并行任務(wù)調(diào)度問題為整數(shù)規(guī)劃問題,將離散優(yōu)化轉(zhuǎn)變成對(duì)實(shí)數(shù)向量的連續(xù)優(yōu)化,詳細(xì)過程如下:a)將每個(gè)向量切斷分成假設(shè)干個(gè)子串,各段子串的長度可以相等,也可以不相等,子串形如(q?1,q?2,…,q?k)。b)從整數(shù)組成的子串到實(shí)數(shù)作一個(gè)映射,可表示為r=×?ki=1q?i×b??k-i(9)其中:r為映射的實(shí)數(shù);是常數(shù),一般取足夠小的實(shí)數(shù),本文取值為0.01;b為基數(shù),對(duì)于xpririty,b取值為5,對(duì)于xahine,b取值為n。)在計(jì)算任務(wù)執(zhí)行總時(shí)間前,需將r轉(zhuǎn)換為子串,即式(9)的逆映射:q?i=(r-?i-1j=1q?j×b??k-j)divb??k-i(10)其中:div為整除,得到的商q?i為整數(shù),在實(shí)際運(yùn)算時(shí),可用一個(gè)循環(huán),i從1~k得到子串中所有分量。例如9個(gè)子任務(wù)的情況,xpririty=(242143410),分為三段,各子串長度均為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值取在邊界上。假設(shè)r0,取值0;r1.24,取值1.24。通過上述映射和逆映射,整數(shù)規(guī)劃問題轉(zhuǎn)換為連續(xù)優(yōu)化問題,從而可以利用qps優(yōu)化獲得高質(zhì)量的解。3.3算法流程a)初始化粒子群,根據(jù)編碼方案設(shè)定各粒子的隨機(jī)位置。b)根據(jù)式(10)將每個(gè)粒子的實(shí)數(shù)向量轉(zhuǎn)換為整數(shù)向量。)對(duì)每個(gè)粒子的整數(shù)向量解碼后,計(jì)算每個(gè)粒子的目的函數(shù)值。d)更新每個(gè)粒子的部分最優(yōu)值p?i。e)更新粒子群的全局最優(yōu)值p?g。f)根據(jù)式(5)計(jì)算best。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)是在atlab軟件上實(shí)現(xiàn)的。實(shí)驗(yàn)所用dag圖隨機(jī)生成,每個(gè)任務(wù)節(jié)點(diǎn)有1~4個(gè)前驅(qū)與后繼,估計(jì)運(yùn)行時(shí)間θij為1~50s的隨機(jī)數(shù)。實(shí)驗(yàn)計(jì)算了文獻(xiàn)[3,4]的算法、ps與本文的qps共四種情況,算法中主要參數(shù):種群大小為80,終止代數(shù)為1500,aax取值1,ain取值0.5;ps的慣性權(quán)重與qps中的收縮擴(kuò)張系數(shù)a取值一樣,?1和?2均為2,編碼、解碼、連續(xù)化與邊界問題均使用本文的方案;文獻(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ù)的百分比。表1仿真實(shí)驗(yàn)結(jié)果處理機(jī)?個(gè)數(shù)子任務(wù)?個(gè)數(shù)完成時(shí)間/s文獻(xiàn)[3]?算法文獻(xiàn)[4]?算法ps?算法本文?算法收斂時(shí)的進(jìn)化代數(shù)252852712792653931252925056554355153816613110812510015481429142714164183392853232519318618817953463338450457429428417194168135157100119811361139107351646832333925152141138134735449528503412972922813362171632121001106911923875727621538601表2收斂到其最優(yōu)解的次數(shù)占進(jìn)化總次數(shù)的百分比%各算法子任務(wù)個(gè)數(shù)25子任務(wù)個(gè)數(shù)50子任務(wù)個(gè)數(shù)100文獻(xiàn)[3]算法876448文獻(xiàn)[4]算法969281ps算法928967本文算法1009996由表1、2和算法的靜態(tài)性能曲線可以得出:a)在任務(wù)數(shù)較多、處理機(jī)較多的情況下,ps與本文qps算法的收斂速度比文獻(xiàn)[3]算法快很多,但與文獻(xiàn)[4]算法比擬時(shí),ps算法的收斂速度明顯比文獻(xiàn)[4]算法快,本文qps算法那么與文獻(xiàn)[4]算法相當(dāng);而在任務(wù)數(shù)少的情況下,除文獻(xiàn)[3]算法稍慢,其他算法相差不大。b)本文qps算法能找到的最優(yōu)解比文獻(xiàn)[3,4]算法有明顯的進(jìn)步,尤其是子任務(wù)數(shù)較多、處理機(jī)數(shù)較多時(shí)。)ps與本文qps算法比擬時(shí),發(fā)現(xiàn)qps算法的收斂速度比ps算法慢,但得到的最優(yōu)解比ps算法好。這是因?yàn)?首先,本文對(duì)問題的編碼可以覆蓋整個(gè)解空間,相對(duì)來說文獻(xiàn)[3,4]的算法只能從一個(gè)相對(duì)較小的空間內(nèi)搜索;其次,本文采用了離散空間到連續(xù)空間的轉(zhuǎn)換過程,它不僅滿足了qps算法對(duì)待解問題的取值要求,還在一定程度上能更好地保護(hù)與遺傳優(yōu)良的解片段。另外,ps算法收斂過快,而qps的量子搜索方式對(duì)傳統(tǒng)的ps算法有了很大的改良,實(shí)驗(yàn)證明可防止早熟。5完畢語基于dag的并行任務(wù)調(diào)度問題是np難問題,傳統(tǒng)的優(yōu)化算法很難求得全局最優(yōu)解,雖然已有人將遺傳算法應(yīng)用于此問題,但結(jié)果有待進(jìn)一步改善。本文給出了新的問題定義,對(duì)qps算法作出調(diào)整與改良,編碼表示采用了合適于任務(wù)調(diào)度問題的優(yōu)先規(guī)那么與處理機(jī)分配相結(jié)合的形式,并將離散空間優(yōu)化問題轉(zhuǎn)換為連續(xù)空間優(yōu)化問題,使得qps有較好的搜索才能。最后通過仿真實(shí)驗(yàn)得到的一系列數(shù)據(jù),說明了本文的改良qps算法比遺傳算法和ps算法有更好的性能
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 央視頻X快手《LIVE“來?!敝埂肥滞?策劃方案
- 市場(chǎng)營銷活動(dòng)與促銷制度
- 醫(yī)療消毒滅菌制度
- 崗位職責(zé)車輛管理
- 人教部編版四年級(jí)語文上冊(cè)第7課《呼風(fēng)喚雨的世紀(jì)》精美課件
- 【寒假閱讀提升】四年級(jí)下冊(cè)語文試題-現(xiàn)代文閱讀(二)-人教部編版(含答案解析)
- 2024年玉林客運(yùn)從業(yè)資格考試題庫
- 2024年黃石客運(yùn)從業(yè)資格證考試模擬
- 2024年寧夏客運(yùn)員考試題庫答案
- 2024年鄂爾多斯客運(yùn)資格證題庫
- 課件零件手冊(cè)vespa gts250ie2011-2013cina
- 咽喉解剖生理醫(yī)學(xué)課件
- 幼兒園課件《撓撓小怪物》
- 政府會(huì)計(jì)基礎(chǔ)知識(shí)講義
- 骨質(zhì)疏松癥-PPT課件
- 調(diào)查問卷-“職工之家”建設(shè)調(diào)查問卷
- 2019年11月系統(tǒng)集成項(xiàng)目管理工程師真題
- 小小建筑師公開課-PPT課件
- 完整版老舊住宅小區(qū)綜合整治工程施工組織設(shè)計(jì)方案
- 小學(xué)三年級(jí)(12)班家長會(huì)課件
- 裝配式模殼剪力墻體系的標(biāo)準(zhǔn)解讀及工程應(yīng)用
評(píng)論
0/150
提交評(píng)論