基于模擬退火遺傳算法的云計算任務(wù)調(diào)度的研究.pdf

1、近年來，隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，云計算成為了學(xué)術(shù)領(lǐng)域和商業(yè)領(lǐng)域的研究熱點。云計算的中心思想是將需要處理的計算任務(wù)分配到由廉價的計算機群構(gòu)成的虛擬資源池上進行處理。大量用戶在請求云計算資源的服務(wù)時，云服務(wù)提供商需要制定一個有效的資源分配方案才能使得用戶有滿意的體驗。因此在云計算這個龐大的系統(tǒng)中，如何進行合理的資源組織和任務(wù)調(diào)度就成云計算的關(guān)鍵技術(shù)之一。但是現(xiàn)今關(guān)于云計算的任務(wù)資源分配問題的研究尚處于摸索和發(fā)展階段，現(xiàn)有的相關(guān)理論在科學(xué)性和方

2、法論上還不太完善。如果分配調(diào)度方法不合理，則會造成用戶的需求得不到滿足等問題。為了設(shè)計出合理的任務(wù)調(diào)度方案便以給用戶帶來高效的云計算服務(wù)體驗，本文對云計算環(huán)境下的任務(wù)調(diào)度問題進行了數(shù)學(xué)建模，建立了基于模擬退火遺傳算法的數(shù)學(xué)模型，對單線程且相互獨立的任務(wù)調(diào)度問題進行了充分的研究分析。
　　本文在參照國內(nèi)外相關(guān)研究的基礎(chǔ)上對云環(huán)境下單線程相互獨立的任務(wù)調(diào)度問題進行了分析研究。首先，介紹了云計算的概念以及云環(huán)境下任務(wù)調(diào)度的過程以及特點。

3、然后，以最小任務(wù)完成時間為目標，建立了任務(wù)調(diào)度的數(shù)學(xué)規(guī)劃模型，并利用優(yōu)先選擇所需計算時間最少的任務(wù)調(diào)度算法Min-min算法進行仿真分析，得到任務(wù)完成的最終所需時間為572秒。最后，根據(jù)遺傳算法以及模擬退火算法的優(yōu)缺點，將兩種算法結(jié)合起來，并且在遺傳算法的編碼方式和交叉、變異操作上較傳統(tǒng)的遺傳算法做了很大的改進，在此基礎(chǔ)上建立了基于模擬退火遺傳算法的任務(wù)調(diào)度模型，利用模擬退火遺傳算法得到的任務(wù)調(diào)度方案最終的任務(wù)完成所需時間為334秒。與

4、Min-min算法比較而言模擬退火遺傳算法大大縮短了任務(wù)完成所需要的時間，證實了算法的有效性。同時該算法也適用于云計算環(huán)境下不同目標的任務(wù)調(diào)度問題。
　　在模擬退火遺傳算法的具體過程中，本文將遺傳算法中的染色體分成兩個子串分開編碼，兩個子串分別代表任務(wù)的分配和任務(wù)的調(diào)度順序。在選擇、變異、交叉的操作中兩部分子串也是分開進行操作，最后再將染色體子串連接起來成為一條染色體代表一個個體或一個解。另外，在變異和交叉的操作中，為了盡量使優(yōu)秀

5、個體的基因值不被破壞并且使不那么優(yōu)秀的個體朝優(yōu)秀個體的方向進化，本文采用自適應(yīng)的交叉概率Pc和自適應(yīng)的變異概率Pm: Pc={k1*fmax-f/fmax-favg，f≥favg和Pm={k3*fmax-f'/fmax-favg，f'≥favg k4,f'＜favg k2,f＜favgfmax、favg分別為種群適應(yīng)度的最大值、平均值，f為父代中適應(yīng)度值的較大值，f'為種群中任一個體的適應(yīng)度值，k1，k2，k3，k4為參數(shù)。進行完遺傳操