基于改進(jìn)遺傳算法的云計(jì)算任務(wù)調(diào)度算法研究

《基于改進(jìn)遺傳算法的云計(jì)算任務(wù)調(diào)度算法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、分類號(hào)TP311．13密級(jí)公開重慶郵電大學(xué)碩士學(xué)位論文論文題目基于改進(jìn)遺傳算法的云計(jì)算任務(wù)調(diào)度算法研究碩士研究生Computingbasedonimprovedgeneticalgorit——hm——袁永勝學(xué)科專業(yè)計(jì)算機(jī)技術(shù)論文提交日期至Ql墨璽壘目論文答辯日期2Q!墨璽互且2魚日．論文評(píng)閱人答辯委員會(huì)主席重壟拯壑邀2013年?duì)巒27Et獨(dú)創(chuàng)性聲明本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。據(jù)我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得重迭魚B電太堂或其他教育機(jī)構(gòu)的學(xué)位或證書而使用過

2、的材料。與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均己在論文中作了明確的說(shuō)明并表示謝意。學(xué)位論文作者簽簽字日期：20B年6月3日學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解重迭由E電太堂有關(guān)保留、使用學(xué)位論文的規(guī)定，有權(quán)保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和磁盤，允許論文被查閱和借閱。本人授權(quán)重麼出E電盍堂可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文。(保密的學(xué)位論文在解密后適用本授權(quán)書)學(xué)位論文作者簽名：導(dǎo)師簽名簽字日期：20乃年6月多日簽字日期：日重慶郵電大學(xué)碩士論文摘要云計(jì)算自2007年提出以來(lái)，憑借

3、其簡(jiǎn)單、廉價(jià)的特點(diǎn)得到了前所未有的發(fā)展，在各行各業(yè)存在著巨大的市場(chǎng)需求，未來(lái)必然對(duì)人的生活方式和工作方式產(chǎn)生影響。云計(jì)算商用以后，面向的是龐大的用戶群體，他們對(duì)資源的需求是各式各樣的，如何在滿足所有用戶需求的情況下對(duì)海量任務(wù)進(jìn)行合理的調(diào)度變得十分關(guān)鍵。遺傳算法是一種全局搜索算法，相比于傳統(tǒng)的啟發(fā)式搜索算法，它具有自組織、自適應(yīng)、自學(xué)習(xí)性和并行性，尤其是在解決海量任務(wù)的時(shí)候，遺傳算法的并行性具有很大的優(yōu)勢(shì)，可以把任務(wù)進(jìn)行拆分后分配到多個(gè)處理機(jī)上同時(shí)進(jìn)行處理。同時(shí)遺傳算法還具有擴(kuò)展性，可以方便地和其他算法進(jìn)行結(jié)合，吸收其他算法的優(yōu)勢(shì)。目前已有學(xué)者將遺傳算法應(yīng)用到網(wǎng)格計(jì)算中進(jìn)行

4、任務(wù)調(diào)度，得出的調(diào)度方案具有更短的任務(wù)完成時(shí)間。云計(jì)算是在網(wǎng)格計(jì)算的基礎(chǔ)上發(fā)展而來(lái)的，它的基本框架和網(wǎng)格計(jì)算的相似，因此本文將遺傳算法應(yīng)用到云計(jì)算的任務(wù)調(diào)度中。但是遺傳算法應(yīng)用到云計(jì)算中后存在一些問題：容易陷入局部最優(yōu)解，算法收斂過程比較長(zhǎng)，對(duì)非線性約束的處理不是很合理，適應(yīng)度函數(shù)考慮的因素比較單一，不能得到最優(yōu)的初始種群等。本文針對(duì)收斂速度慢、約束處理不合理、適應(yīng)度函數(shù)考慮因素單一進(jìn)行了改進(jìn)。為了解決算法收斂速度慢的問題，本文對(duì)傳統(tǒng)的串行編碼方式進(jìn)行了改進(jìn)，采用矩陣編碼方式，解決了染色體過長(zhǎng)的問題，而且染色體交叉和變異操作更加有效，產(chǎn)生的新個(gè)體是潛在最優(yōu)解的概率更大。為

5、了解決算法對(duì)非線性約束處理不合理的問題，本文在原有深度值排序的基礎(chǔ)上增加了對(duì)任務(wù)約束關(guān)系為特殊DAG圖的任務(wù)分配方式，對(duì)一些特殊的任務(wù)進(jìn)行優(yōu)先處理，減少被依賴任務(wù)的等待時(shí)間，最終減少任務(wù)的總完成時(shí)間。為了解決適應(yīng)度函數(shù)考慮因素單一的問題，本文對(duì)適應(yīng)度函數(shù)進(jìn)行了改進(jìn)，將平均任務(wù)完成時(shí)間和任務(wù)完成所需成本加入適應(yīng)度函數(shù)當(dāng)中，讓算法依據(jù)適應(yīng)度值選出的個(gè)體既有總?cè)蝿?wù)完成時(shí)間和成本較少的，也有平均任務(wù)完成時(shí)間和成本較少的。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的遺傳算法在云計(jì)算環(huán)境中進(jìn)行任務(wù)調(diào)度的時(shí)候，可以減少任務(wù)的完成時(shí)間，提高調(diào)度算法的收斂速度，并在完成時(shí)間．成本中尋找到了一個(gè)平衡點(diǎn)。因此，該算法

6、是一種可行且有效的任務(wù)調(diào)度算法。關(guān)鍵詞：云計(jì)算，任務(wù)調(diào)度，遺傳算法，約束，成本開銷，矩陣編碼重慶郵電大學(xué)碩士論文Abstractsince2007，cloudcomputinghasthehithertounknowndevelopmentbyitssimpleandcheapfeature．Therehasahugemarketdemandinallwalksoflife．Itwillinfluencethelifeandworkofpeople．Aftercloudcomputingcommercialapplication，itfacethehugeusergrou

7、ps，theirdemandforresourcesarediverse，Howtoreasonableschedulingtomassivetaskinthesituationofmeetallusersdemandbecomesverycritical．Geneticalgorithmisaglobalsearchalgorithm，comparedtothetraditionalheuristicsearchalgorithm，itisself-organizing，self-adaptive，self-learning