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

1、云計(jì)算自2007年提出以來，憑借其簡單、廉價(jià)的特點(diǎn)得到了前所未有的發(fā)展，在各行各業(yè)存在著巨大的市場需求，未來必然對人的生活方式和工作方式產(chǎn)生影響。云計(jì)算商用以后，面向的是龐大的用戶群體，他們對資源的需求是各式各樣的，如何在滿足所有用戶需求的情況下對海量任務(wù)進(jìn)行合理的調(diào)度變得十分關(guān)鍵。
　　 遺傳算法是一種全局搜索算法，相比于傳統(tǒng)的啟發(fā)式搜索算法，它具有自組織、自適應(yīng)、自學(xué)習(xí)性和并行性，尤其是在解決海量任務(wù)的時(shí)候，遺傳算法的并行性

2、具有很大的優(yōu)勢，可以把任務(wù)進(jìn)行拆分后分配到多個(gè)處理機(jī)上同時(shí)進(jìn)行處理。同時(shí)遺傳算法還具有擴(kuò)展性，可以方便地和其他算法進(jìn)行結(jié)合，吸收其他算法的優(yōu)勢。目前已有學(xué)者將遺傳算法應(yīng)用到網(wǎng)格計(jì)算中進(jìn)行任務(wù)調(diào)度，得出的調(diào)度方案具有更短的任務(wù)完成時(shí)間。云計(jì)算是在網(wǎng)格計(jì)算的基礎(chǔ)上發(fā)展而來的，它的基本框架和網(wǎng)格計(jì)算的相似，因此本文將遺傳算法應(yīng)用到云計(jì)算的任務(wù)調(diào)度中。
　　 但是遺傳算法應(yīng)用到云計(jì)算中后存在一些問題:容易陷入局部最優(yōu)解，算法收斂過程比較

3、長，對非線性約束的處理不是很合理，適應(yīng)度函數(shù)考慮的因素比較單一，不能得到最優(yōu)的初始種群等。
　　 本文針對收斂速度慢、約束處理不合理、適應(yīng)度函數(shù)考慮因素單一進(jìn)行了改進(jìn)。
　　 為了解決算法收斂速度慢的問題，本文對傳統(tǒng)的串行編碼方式進(jìn)行了改進(jìn)，采用矩陣編碼方式，解決了染色體過長的問題，而且染色體交叉和變異操作更加有效，產(chǎn)生的新個(gè)體是潛在最優(yōu)解的概率更大。
　　 為了解決算法對非線性約束處理不合理的問題，本文在原有深

4、度值排序的基礎(chǔ)上增加了對任務(wù)約束關(guān)系為特殊DAG圖的任務(wù)分配方式，對一些特殊的任務(wù)進(jìn)行優(yōu)先處理，減少被依賴任務(wù)的等待時(shí)間，最終減少任務(wù)的總完成時(shí)間。
　　 為了解決適應(yīng)度函數(shù)考慮因素單一的問題，本文對適應(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)