差分進(jìn)化算法及其在云計(jì)算任務(wù)調(diào)度中的應(yīng)用研究

1、碩士學(xué)位論文差分進(jìn)化算法及其在云計(jì)算任務(wù)調(diào)度中的應(yīng)用研究T h e R e s e a r c h o f D i f f e r e n c e E v o l u t i o nA l g o r i t h ma n d I t sA p p l i c a t i o n s i nT a s k S c h e d u l i n g o f C l o u d C o m p u t i n g作者姓名：學(xué)科、專業(yè)：學(xué) 號：

2、指導(dǎo)教師：完成日期：蘭州交通大學(xué)L a n z h o u J i a o t o n gU n i v e r s i t y蘭州交通大學(xué)碩士學(xué)位論文摘 要云計(jì)算是一種商業(yè)計(jì)算模型，它將計(jì)算任務(wù)分布在大量計(jì)算機(jī)構(gòu)成的資源池上，使用戶能夠按需獲取I T 服務(wù)。而構(gòu)成資源池的計(jì)算機(jī)在計(jì)算、存儲、寬帶性能等方面都可能存在限制與不同，在滿足用戶多樣化、彈性的需求時(shí)，往往需要進(jìn)行復(fù)雜的任務(wù)調(diào)度，但仍難以滿足用戶的服務(wù)質(zhì)量( Q o S ) 需求

3、。云計(jì)算任務(wù)調(diào)度的研究就是為了解決此問題。云計(jì)算任務(wù)調(diào)度問題是一種組合優(yōu)化類的N P 難問題，現(xiàn)有云計(jì)算平臺的任務(wù)調(diào)度算法如F I F O 、公平調(diào)度、容量調(diào)度等都存在不足之處，難以很好地滿足實(shí)際應(yīng)用的需求。因此，人們提出了一些新的算法，這些算法中除了改進(jìn)一些經(jīng)典調(diào)度算法外，智能優(yōu)化算法也逐漸被引入，如遺傳算法、粒子群算法、蟻群算法、模擬退火算法等，但這些算法都處于探索與研究階段，仍存在各自的不足。差分進(jìn)化算法作為一種基于群體進(jìn)化的新型

4、仿生智能優(yōu)化算法，近年來引起廣大研究者的關(guān)注，該算法具有實(shí)現(xiàn)簡單、全局優(yōu)化能力強(qiáng)等優(yōu)點(diǎn)，但也存在不能直接用于離散問題、易陷入局部最優(yōu)、收斂速度較慢等不足之處，目前尚未被應(yīng)用于云計(jì)算領(lǐng)域。本文擬將其改進(jìn)后應(yīng)用于云計(jì)算任務(wù)調(diào)度問題。改進(jìn)分兩個(gè)步驟：首先，對基本差分進(jìn)化算法本身的不足進(jìn)行改進(jìn)：然后以此為基礎(chǔ)，面向云計(jì)算任務(wù)調(diào)度問題的特點(diǎn)，再作進(jìn)一步的改進(jìn)。針對差分進(jìn)化算法本身的不足，本文提出了改進(jìn)的離散差分進(jìn)化算法：M D D E 。提出了差

5、分進(jìn)化算法的離散化原則，使之可以應(yīng)用到組合優(yōu)化問題。然后，．針對算法優(yōu)化性能的不足，提出了進(jìn)化過程前后期的概念。在進(jìn)化前期設(shè)置了并行多種群，并定義了一種綜合差分策略，即進(jìn)化前后期分別采用差分策略D E l 與D E 2 ，均衡了M D D E 算法的全局探索和局部挖掘的能力，保證了算法在進(jìn)化前期擁有良好的全局探索能力，在后期擁有快速的局部挖掘性能。提出了貪婪交叉原則，并新增了變異操作之后的選擇機(jī)制，進(jìn)一步加快了算法的收斂速度。將M D

6、D E 算法應(yīng)用到T S P 問題的求解中，驗(yàn)證了其優(yōu)化性能。結(jié)合云計(jì)算任務(wù)調(diào)度的特點(diǎn)，本文在M D D E 算法的基礎(chǔ)上提出了滿足Q o S 需求的云計(jì)算任務(wù)調(diào)度算法：T C ．M D D E 。按照離散化原則，結(jié)合任務(wù)順序編碼法，針對差分運(yùn)算出現(xiàn)非法編碼的問題j 定義了“絕對值取整求余映射法”進(jìn)行非法編碼的合法化處理，保證了變異操作的順利進(jìn)行。針對云計(jì)算任務(wù)調(diào)度問題中Q o S 的多樣化需求，定義了參數(shù)靈活的適應(yīng)度函數(shù)，能夠根據(jù)用戶