資源描述：
《基于量子粒子群優(yōu)化的dag并行任務(wù)調(diào)度探討》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、基于量子粒子群優(yōu)化的DAG并行任務(wù)調(diào)度探討 摘要:任務(wù)調(diào)度是網(wǎng)絡(luò)并行計算系統(tǒng)的核心問題之一。在有向無環(huán)圖(DAG)描述問題的基礎(chǔ)上,提出了一種進(jìn)行并行任務(wù)調(diào)度的量子粒子群優(yōu)化算法。首先對DAG并行任務(wù)調(diào)度問題作出定義,并給出了優(yōu)化問題的目標(biāo);然后分別探討了問題的編碼表示、解碼方案、位置向量的計算方法、離散問題連續(xù)化、算法的總體流程等;最后給出算法的仿真實驗情況與研究,實驗結(jié)果表明,該算法有良好的全局尋優(yōu)性能和快捷的收斂速度,調(diào)度效果優(yōu)于遺傳算法和粒子群優(yōu)化算法?！ ￡P(guān)鍵詞:任務(wù)調(diào)度;量子粒子群優(yōu)
2、化;有向無環(huán)圖? ResearchonDAGparalleltaskschedulingproblembasedon?quantum-behavedparticlesoptimization ZHANGCong,SHENHui-zhang (AntaiCollegeofEconomicsManagement,ShanghaiJiaotongUniversity,Shanghai200052,China) Abstract:Taskschedulingisoneoftheimport
3、antproblemsinparallelputingsystem.Thispaperproposedaquantum-?behavedparticlesoptimizationalgorithmfortaskschedulingbasedondirectedacyclicgraph.Firstredefinedtheparalleltaskschedulingproblemanditsaim.Thendiscussedtherepresentationoftheencoding,theproce
4、dureofthedecoding,theputationalmethodofpositionvector,thecontinuativeofthediscreteproblemandthestructureofthealgorithmrespectively.Intheend,presentedthealgorithmsimulation,experimentresultanalysisandtheconclusions.Thesimulationresultsshohasbettergloba
5、loptimizingabilityandmorerapidconvergence,anditissuperiortogeicalgorithmandparticlesoptimizationalgorithm. Key-behavedparticlesoptimization(QPSO);directedacyclicgraph(DAG) 網(wǎng)絡(luò)并行計算環(huán)境下的任務(wù)調(diào)度問題是指在一定約束條件下,如何將一組任務(wù)分配到多臺處理機上執(zhí)行的組合優(yōu)化問題,其已被證明是NP完全問題,不可能在多項式時間內(nèi)找
6、到問題的最優(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)度過程中滿足任務(wù)之間的數(shù)據(jù)依賴關(guān)系。依賴關(guān)系任務(wù)調(diào)度的求解優(yōu)化過程比獨立任務(wù)調(diào)度的要復(fù)雜許多,且其適用范圍也更廣。以DAG表示的并行任務(wù)模型的研究得到了廣泛關(guān)注和迅速發(fā)展。近年出現(xiàn)的一些啟發(fā)式算法(如模擬退火算法、遺傳算法等)為求解此類NP完全問題提供了新的途徑[3
7、~5],但是這些算法有些復(fù)雜性太高難以實現(xiàn),有些實現(xiàn)起來太費時,所以有必要尋求更好的算法來解決此問題?！ ×Ｗ尤簝?yōu)化(PSO)算法是由Kennedy等人[6]提出的一種源于對鳥群捕食行為模擬的進(jìn)化計算技術(shù),已成為進(jìn)化計算的一個最吸引人的分支。與遺傳算法類似,PSO是一種基于迭代的優(yōu)化方法,系統(tǒng)初始化為一組隨機解,通過迭代搜尋最優(yōu)值,但是在許多實際應(yīng)用領(lǐng)域,更勝于遺傳算法,尤其是在非線性優(yōu)化問題上。量子粒子群優(yōu)化(QPSO)算法是在傳統(tǒng)的PSO基礎(chǔ)上提出的一種新型的具有高效率全局搜索能力的進(jìn)化算法[
8、7,8]。它主要是引入量子物理的思想改進(jìn)了PSO的進(jìn)化方法,即更新粒子位置的方法;在更新粒子位置時重點考慮各個粒子的當(dāng)前局部最優(yōu)位置信息和全局最優(yōu)位置信息。QPSO具有調(diào)整參數(shù)少、容易實現(xiàn)、收斂能力強等優(yōu)勢。為適應(yīng)任務(wù)分配問題的求解,本文設(shè)計出合適的粒子編碼,利用改進(jìn)的量子粒子群算法求解任務(wù)分配問題,并與其他算法相比較。實驗結(jié)果表明,本文提出的算法可以獲得質(zhì)量更高的解職稱論文?！ ?問題描述 本模型的計算系統(tǒng)由一系列異構(gòu)的處理機組成,需要處理的總?cè)蝿?wù)已分解成一系列子任務(wù)。模型的約
