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

1、淺析基于量子粒子群優(yōu)化的DAG并行任務(wù)調(diào)度摘要:任務(wù)調(diào)度是網(wǎng)絡(luò)并行計算系統(tǒng)的核心問題之一。在有向無環(huán)圖(dag)描繪問題的根底上,提出了一種進展并行任務(wù)調(diào)度的量子粒子群優(yōu)化算法。首先對dag并行任務(wù)調(diào)度問題作出定義,并給出了優(yōu)化問題的目的;然后分別討論了問題的編碼表示、解碼方案、位置向量的計算方法、離散問題連續(xù)化、算法的總體流程等;最后給出算法的仿真實驗情況及分析,實驗結(jié)果說明,該算法有良好的全局尋優(yōu)性能和快捷的收斂速度,調(diào)度效果優(yōu)于遺傳算法和粒子群優(yōu)化算法。zhangng,shenhui-zhang(antaillegefenisanageent,shanghaijiatnguniversi

2、ty,shanghai200052,hina)keyrds:tasksheduling;quantu-behavedpartilesarptiizatin(qps);diretedayligraph(dag)網(wǎng)絡(luò)并行計算環(huán)境下的任務(wù)調(diào)度問題是指在一定約束條件下,如何將一組任務(wù)分配到多臺處理機上執(zhí)行的組合優(yōu)化問題,其已被證明是np完全問題,不可能在多項式時間內(nèi)找到問題的最優(yōu)解1,2。目前常見的并行任務(wù)調(diào)度問題按照任務(wù)之間有無數(shù)據(jù)依賴關(guān)系可以劃分為獨立任務(wù)調(diào)度和依賴關(guān)系任務(wù)調(diào)度。前者在調(diào)度任務(wù)時不需要考慮任務(wù)之間的數(shù)據(jù)依賴關(guān)系;而后者通常用有向無環(huán)圖(dag)表示任務(wù)之間的數(shù)據(jù)依賴關(guān)系,在調(diào)度過程

3、中滿足任務(wù)之間的數(shù)據(jù)依賴關(guān)系。依賴關(guān)系任務(wù)調(diào)度的求解優(yōu)化過程比獨立任務(wù)調(diào)度的要復雜許多,且其適用范圍也更廣。以dag表示的并行任務(wù)模型的研究得到了廣泛關(guān)注和迅速開展。近年出現(xiàn)的一些啟發(fā)式算法(如模擬退火算法、遺傳算法等)為求解此類np完全問題提供了新的途徑35,但是這些算法有些復雜性太高難以實現(xiàn),有些實現(xiàn)起來太費時,所以有必要尋求更好的算法來解決此問題。粒子群優(yōu)化(ps)算法是由kennedy等人6提出的一種源于對鳥群捕食行為模擬的進化計算技術(shù),已成為進化計算的一個最吸引人的分支。與遺傳算法類似,ps是一種基于迭代的優(yōu)化方法,系統(tǒng)初始化為一組隨機解,通過迭代搜尋最優(yōu)值,但是在許多實際應(yīng)用領(lǐng)域,

4、更勝于遺傳算法,尤其是在非線性優(yōu)化問題上。量子粒子群優(yōu)化(qps)算法是在傳統(tǒng)的ps根底上提出的一種新型的具有高效率全局搜索才能的進化算法7,8。它主要是引入量子物理的思想改進了ps的進化方法,即更新粒子位置的方法;在更新粒子位置時重點考慮各個粒子的當前局部最優(yōu)位置信息和全局最優(yōu)位置信息。qps具有調(diào)整參數(shù)少、容易實現(xiàn)、收斂才能強等優(yōu)勢。為適應(yīng)任務(wù)分配問題的求解,本文設(shè)計出適宜的粒子編碼,利用改進的量子粒子群算法求解任務(wù)分配問題,并與其他算法相比較。實驗結(jié)果說明,本文提出的算法可以獲得質(zhì)量更高的解。1問題描繪本模型的計算系統(tǒng)由一系列異構(gòu)的處理機組成,需要處理的總?cè)蝿?wù)已分解成一系列子任務(wù)。模型的

5、約束條件為:任務(wù)執(zhí)行具有非搶占性,即處理機只有在執(zhí)行完某個任務(wù)之后才能處理另外一個任務(wù);另外這些任務(wù)之間具有前驅(qū)后繼的數(shù)據(jù)依賴關(guān)系,某個子任務(wù)只有在其所有的前驅(qū)任務(wù)處理完畢后才能開始執(zhí)行。該模型的調(diào)度目的就是要使得整個dag圖的調(diào)度長度最短。為了便于分析問題,可以用以下五元組表述:=(p,g,)其中:(2)鑒于本文主要考慮任務(wù)調(diào)度問題,在不失問題一般性的情況下,可忽略數(shù)據(jù)傳輸延時,即在下文中可假設(shè)所有的ij=0。2算法2.1ps算法粒子群優(yōu)化(ps)算法是一種進化計算方法,是一種基于迭代的優(yōu)化工具。該算法通過群體中各粒子間的合作與競爭來搜索全局最優(yōu)點。2.2qps算法sun等人從量子力學的角度

6、,通過對粒子收斂行為的研究,基于粒子群算法提出了一種新的算法模型量子粒子群(qps)算法。在該算法中,由于粒子滿足聚集態(tài)的性質(zhì)完全不同,使粒子在整個可行解空間中進展搜索尋求全局最優(yōu)解,因此qps算法在搜索才能上遠遠優(yōu)于所有已開發(fā)的ps算法。ppij=fpij+(1-f)pgj,f=rand(6)其中:best是粒子群pbest的中間位置;pij為粒子本身所找到的最優(yōu)解pbest;pgj為整個粒子群目前找到的最優(yōu)解gbest;ppij為pij與pgj之間的隨機點;a為qps的收縮擴張系數(shù),它是qps收斂的一個重要參數(shù),第t次迭代時一般可取a=aax-t(aax-ain)/tax(8)其中:tax是迭代的最大次數(shù),aax與ain分別是最大和最小系數(shù)。qps的算法流程如下:a)迭代次數(shù)t=0,對種群的每個粒子的位置向量進展初始化。b)根據(jù)目的函數(shù)計算每個粒子的目的函數(shù)值。e)根據(jù)式(5)計算best。g)根據(jù)式(7)(以一定的概率取加或減)更新