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

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

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

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

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

5、個(gè)體的基因值不被破壞并且使不那么優(yōu)秀的個(gè)體朝優(yōu)秀個(gè)體的方向進(jìn)化，本文采用自適應(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'為種群中任一個(gè)體的適應(yīng)度值，k1，k2，k3，k4為參數(shù)。進(jìn)行完遺傳操