基于量子遺傳算法的網(wǎng)格任務調(diào)度算法研究.pdf

1、隨著計算機技術(shù)的飛速發(fā)展，人們?yōu)榱顺浞掷脧V域網(wǎng)上的分布式資源，提出了網(wǎng)格計算的概念。網(wǎng)格計算是分布式計算的一種，其目的是建立大規(guī)模計算和海量數(shù)據(jù)處理的通用基礎支撐結(jié)構(gòu)，將網(wǎng)絡上的各種高性能計算機、服務器、PC、信息系統(tǒng)、海量數(shù)據(jù)存儲和處理系統(tǒng)、應用模擬系統(tǒng)、虛擬現(xiàn)實系統(tǒng)、儀器設備和信息獲取設備集成在一起，為用戶提供一個統(tǒng)一的、整合的、虛擬的計算環(huán)境，實現(xiàn)跨組織的資源共享、管理與訪問。在網(wǎng)格系統(tǒng)中，任務調(diào)度系統(tǒng)是重要組成部分，它根據(jù)任務

2、信息采用適當?shù)牟呗园巡煌娜蝿辗峙涞较鄳馁Y源節(jié)點上去運行。由于網(wǎng)格系統(tǒng)的異構(gòu)性和動態(tài)性，以及運行于網(wǎng)格系統(tǒng)之中的應用程序?qū)τ谫Y源的不同需求，使得任務調(diào)度變得極其復雜，它在一般形式下是一個NP完全問題。 量子遺傳算法是一種新的優(yōu)化算法，是由量子計算和遺傳算法相結(jié)合而產(chǎn)生的。量子遺傳算法建立在量子態(tài)矢量表示的基礎之上，將量子比特的概率幅表示為應用于遺傳算法中染色體的編碼，使得一條染色體可以表達多個態(tài)的疊加，并利用量子邏輯門代替遺傳

3、操作，實現(xiàn)染色體的更新，從而實現(xiàn)目標的優(yōu)化求解。通過分析量子遺傳算法，本文提出了改進的量子遺傳算法，提高了量子遺傳算法的搜索效率，并通過多峰值函數(shù)求解問題證明了其正確性和優(yōu)越性。 本文通過量子遺傳算法及其改進算法在網(wǎng)格任務調(diào)度中的應用，以減少任務調(diào)度時間為主要目標，增加資源利用率為次要目標，提出了基于量子遺傳算法及其改進算法的網(wǎng)格任務調(diào)度算法。算法采用量子比特間接編碼的方式，通過有向無環(huán)圖(DAG)來描述子任務之間的依賴關(guān)系，根