国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于遺傳算法的云計(jì)算任務(wù)分配

2013-08-06 07:08:54周書臣
關(guān)鍵詞:計(jì)算環(huán)境任務(wù)調(diào)度適應(yīng)度

王 倩,周書臣

(1.周口師范學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,河南 周口 466001;2.黃淮學(xué)院 國際學(xué)院,河南 駐馬店 463000)

目前,云計(jì)算成為信息技術(shù)領(lǐng)域所討論的熱點(diǎn)[1-2].關(guān)于云計(jì)算,文獻(xiàn)3里這樣描述:基礎(chǔ)設(shè)施(用來構(gòu)造應(yīng)用程序,相當(dāng)于微型計(jì)算機(jī)的OS)和云計(jì)算應(yīng)用(建立在基礎(chǔ)設(shè)施之上).與網(wǎng)格計(jì)算相比,網(wǎng)格程序是把大的任務(wù)分解成許多個(gè)小的任務(wù)并行運(yùn)行在不同的集群以及服務(wù)器上,看重的是科學(xué)地進(jìn)行計(jì)算應(yīng)用程序的運(yùn)行.對(duì)于云計(jì)算而言,它是一個(gè)具有更廣泛定義的計(jì)算平臺(tái),不僅能夠支持網(wǎng)格的應(yīng)用,還支持非網(wǎng)格的應(yīng)用,比如,支持網(wǎng)絡(luò)服務(wù)程序中的前臺(tái)網(wǎng)絡(luò)服務(wù)器、數(shù)據(jù)庫服務(wù)器和應(yīng)用服務(wù)器這三層應(yīng)用程序架構(gòu)模式等.云計(jì)算是能夠提供虛擬化、動(dòng)態(tài)資源池和高可用性的下一代計(jì)算平臺(tái)[3].當(dāng)前,云計(jì)算服務(wù)可分基礎(chǔ)設(shè)施即服務(wù)(如Amazon的彈性計(jì)算云等)、平臺(tái)即服務(wù)(如Google的Google AppEngine等)和軟件即服務(wù)(如Salesforce公司的客戶關(guān)系管理服務(wù)等)為這3個(gè)層次[4].

云計(jì)算的核心思想是將大量計(jì)算資源(用網(wǎng)絡(luò)連接的)進(jìn)行統(tǒng)一的管理和調(diào)度,形成一個(gè)計(jì)算資源池,以便按照用戶的需要進(jìn)行服務(wù).云的含義是提供資源的網(wǎng)絡(luò).在用戶看來,“云”中的資源是能夠無限擴(kuò)展的,還能隨時(shí)獲取,按使用付費(fèi).總的來說,云計(jì)算是并行計(jì)算和網(wǎng)格計(jì)算的進(jìn)一步的發(fā)展.企業(yè)數(shù)據(jù)中心的運(yùn)行將與互聯(lián)網(wǎng)更相似,使計(jì)算分布在大量的分布式計(jì)算機(jī)上.這樣能夠使企業(yè)將資源切換到所需的應(yīng)用上,按照需求去訪問計(jì)算機(jī)和存儲(chǔ)系統(tǒng).它意味著計(jì)算能力也能作為一種商品進(jìn)行流通,像煤氣、水電一樣,取用方便,費(fèi)用低廉.與煤氣、水電相比,最大的不同之處是通過互聯(lián)網(wǎng)傳輸.

對(duì)于云計(jì)算服務(wù)提供商來說,其核心技術(shù)是如何對(duì)用戶申請(qǐng)的計(jì)算資源進(jìn)行分配和管理,其效率直接影響整個(gè)云計(jì)算環(huán)境的工作性能以及企業(yè)效益.因此,為云計(jì)算環(huán)境找到一個(gè)合理的任務(wù)分配方法迫在眉睫.本文提出了一種基于遺傳算法的任務(wù)調(diào)度算法,實(shí)驗(yàn)證明了該算法有效地提高了資源的分配和管理.

1 遺傳算法

近些年仿生學(xué)迅猛發(fā)展,仿生技術(shù)也備受各界學(xué)者的關(guān)注,已經(jīng)用于解決復(fù)雜的問題(如:任務(wù)分配、路徑等).遺傳算法(簡(jiǎn)稱GA)研究歷史比較短,它是模擬生物界中的遺傳和進(jìn)化的一種最優(yōu)化的方法.1975年,John Holland等人出版了《自然與人工系統(tǒng)中的自適應(yīng)》專著,標(biāo)志著GA正式誕生.現(xiàn)今,GA已成功應(yīng)用于生物、計(jì)算機(jī)科學(xué)、圖像處理等領(lǐng)域.由于其并行性、全局搜索以及高求解精度且易于和其他方法相結(jié)合的特點(diǎn),能在龐大的解空間中最大限度地尋找全局最優(yōu),在解決組合優(yōu)化問題方面顯示出了較大優(yōu)勢(shì).其核心思想是:通過隨機(jī)方式產(chǎn)生若干個(gè)所求解問題的數(shù)字編碼,即染色體,形成初始種群,通過適應(yīng)度函數(shù)給每個(gè)個(gè)體一個(gè)數(shù)值評(píng)價(jià),淘汰低適應(yīng)度的個(gè)體,選擇高適應(yīng)度的個(gè)體參加遺傳操作,經(jīng)過遺傳操作后的個(gè)體集合形成下一代新的種群.再對(duì)這個(gè)新種群進(jìn)行下一輪進(jìn)化.

精英個(gè)體是指具有較高適應(yīng)度值的個(gè)體.在群體里,文獻(xiàn)[5]指出:全局最優(yōu)解和精英個(gè)體的親和度要大于全局最優(yōu)解和非精英個(gè)體的親和度,并與精英個(gè)體有較大親和度的個(gè)體也應(yīng)該具有較高的適應(yīng)度值.所以,在種群的進(jìn)化過程中精英個(gè)體起著非常重要的推動(dòng)作用.

協(xié)同進(jìn)化與傳統(tǒng)遺傳算法相比,它具有強(qiáng)搜索能力和漸進(jìn)學(xué)習(xí)能力,能夠克服傳統(tǒng)遺傳算法的早熟收斂現(xiàn)象.能夠有效地解決遺傳算法中進(jìn)化模式單一性的問題,從而較好地保持種群個(gè)體的多樣性,避免了未成熟收斂和收斂速度慢等問題.

近年來,GA的研究仍然被眾多學(xué)者所關(guān)注,并取得了顯著的成果.文獻(xiàn)[7]結(jié)合遺傳算法與線性鑒別分析提出了一種玉米品種的快速鑒別方法,與常用的PCA等方法相比,運(yùn)算時(shí)間更短,正確率更高.文獻(xiàn)[8]針對(duì)噪聲環(huán)境下多模函數(shù)的優(yōu)化,本文理論上分析了噪聲對(duì)多模函數(shù)優(yōu)化的收斂精度和全局收斂性的影響,并對(duì)全局區(qū)域收斂精度和全局區(qū)域搜索率進(jìn)行分析噪聲對(duì)算法的影響程度.噪聲的強(qiáng)度和加多模函數(shù)尋優(yōu)的難度,遺傳算法的全局區(qū)域搜索率都在下降,全局區(qū)域收斂精度總體變差;重采樣的方法能夠有效提高算法的全局區(qū)域搜索率,總體改善算法的全局區(qū)域收斂精度.遺傳算法被應(yīng)用各個(gè)領(lǐng)域.文獻(xiàn)[9]提出了一種混合競(jìng)爭(zhēng)協(xié)同進(jìn)化遺傳算法(htCGA),其基本思想是,將局部搜索方法引入到協(xié)同進(jìn)化遺傳算法中,提高了算法局部搜索的能力.但上述兩種算法都采用了對(duì)解空間進(jìn)行分割的策略.因此較容易陷入局部極小值的問題.文獻(xiàn)[1]提出了一種蜜蜂進(jìn)化型遺傳算法,該算法充分利用了精英個(gè)體的信息.但該算法中隨機(jī)種群的比例參數(shù)需要通過人為經(jīng)驗(yàn)來確定,一定程度上增加了算法的隨機(jī)性.遺傳算法容易陷入局部最優(yōu)解,而且收斂速度和尋優(yōu)精度有待提高.為此,本文提出了的算法對(duì)云計(jì)算中的任務(wù)調(diào)度策略進(jìn)行改進(jìn),通過對(duì)任務(wù)的優(yōu)化調(diào)度來最大限度地提高云計(jì)算環(huán)境的效率.

2 基于遺傳算法的云任務(wù)分配

2.1 云計(jì)算中的模型

目前,云計(jì)算的環(huán)境大多數(shù)采用Map/Reduce模型[10].本文采用基于Map/Reduce的思想開發(fā)的編程工具,這模型適用于產(chǎn)生和處理大規(guī)模的數(shù)據(jù)集.

圖1 Map/Reduce的執(zhí)行過程

圖1看出,Map/Reduce主要分兩個(gè)階段:

第一個(gè)階段(Map階段):通過Map/Reduce函數(shù)將一個(gè)大的任務(wù)劃分多個(gè)小的任務(wù),然后并行執(zhí)行(執(zhí)行Map操作的worker),輸出處理后的中間文件.

第二個(gè)階段(Reduce階段):將第一個(gè)階段處理后的結(jié)果匯總分析并處理,輸出最后結(jié)果.

目前一些任務(wù)調(diào)度的算法過多地關(guān)注總?cè)蝿?wù)的完成時(shí)間(造成潛在優(yōu)良基因丟失).既要關(guān)注總?cè)蝿?wù)的完成時(shí)間,又要關(guān)注平均完成時(shí)間,所以,本文提出了一種對(duì)云計(jì)算中任務(wù)調(diào)度的改進(jìn)算法,最大限度地提高云計(jì)算環(huán)境的效率.

2.2 算法流程

2.2.1 個(gè)體評(píng)價(jià)策略

本文對(duì)群體中的個(gè)體進(jìn)行適應(yīng)度評(píng)價(jià)采用以下策略.定義:

其中,P={a1,a2,…,an}是群體所包含的個(gè)體集合,n是表示群的規(guī)模分別表示i和j個(gè)體第l位的值.這個(gè)策略引入了差異度作為其權(quán)系數(shù),能夠有效地保持種群的多樣性,從而避免因有效模式缺失而導(dǎo)致的早熟收斂問題.

2.2.2 交叉操作

傳統(tǒng)的遺傳算法采用統(tǒng)一的交叉、變異策略,很大程度上增加了算法的隨機(jī)性,降低了算法的收斂速度.本文受MECA算法[11]的啟發(fā),采用兩種交叉算子:?jiǎn)吸c(diǎn)交叉算子和兩點(diǎn)算子(兩點(diǎn)交叉是設(shè)置兩個(gè)交叉點(diǎn),為選定父代基因鏈上的兩個(gè)位置進(jìn)行交叉).當(dāng)個(gè)體i,j的差異度時(shí),產(chǎn)生新個(gè)體采用單點(diǎn)交叉算子x=(x1,x2,…,xn)和y=(y1,y2,…,yn).當(dāng)個(gè)體i,j相似時(shí),使用兩點(diǎn)交叉算子(如表1所示)產(chǎn)生新個(gè)體.

表1 兩點(diǎn)交叉

2.2.3 精英進(jìn)化

對(duì)于種群的進(jìn)化,精英個(gè)體起著非常重要的作用.遺傳算法采用精英策略能夠較快地收斂到全局最優(yōu)解.DECGA算法采用雙精英進(jìn)化策略.這一算法的核心操作是以精英個(gè)體作為進(jìn)化的,在進(jìn)化過程中充分地發(fā)揮了精英個(gè)體的推動(dòng)作用,使個(gè)體有方向地朝好的方向進(jìn)化.

初始種群生成時(shí),首先組成精英庫種群(隨著種群的進(jìn)化而不斷更新),精英種群是從種群中前M個(gè)適應(yīng)度值最高的不同個(gè)體中選擇出來的,每一代中的兩個(gè)精英個(gè)體都是也是這樣選擇的,用EliteA(提高算法收斂速度,能夠有效避免因種群個(gè)體過于相似而導(dǎo)致的無效交叉,從而提高算法的進(jìn)化效率)和EliteB(避免出現(xiàn)算法由于選擇壓力而造成的過早收斂現(xiàn)象)來表示兩個(gè)精英個(gè)體,這兩個(gè)精英個(gè)體協(xié)同進(jìn)化,最終完成算法的整個(gè)進(jìn)化操作.

算法的流程描述如下:

(1)隨機(jī)產(chǎn)生初始種群,計(jì)算每個(gè)個(gè)體的適應(yīng)度函數(shù)并排序.

(2)選擇前M個(gè)適應(yīng)度值相異的優(yōu)秀個(gè)體作為精英庫Best(0)成員,并令 t=0;

(3)選擇Best(t)中的最優(yōu)個(gè)體作為EliteA,并利用種群分割策略得到分割種群P0Pe和P0Pc.

(4)按比例選擇法選擇與EliteA相異的個(gè)體EliteA,種群個(gè)體評(píng)價(jià)函數(shù).

(5)將 A(t+1)和 B(t+1)種群合并,得到種群 Temp(t+1),并計(jì)算Temp(t+1)的適應(yīng)度值;

(6)精英庫Best(t)與temp(t+1)中的個(gè)體競(jìng)爭(zhēng),并計(jì)算Temp(t+1)中不存在此精英個(gè)體,則用此精英個(gè)體替代Temp(t+1)中的最差個(gè)體;否則不進(jìn)行任何操作.得到下一代種群P(t+1),并將種群按適應(yīng)度降序排列;

(7)若P(t+1)中的最優(yōu)個(gè)體 bestlndividual大于Best(t)中的最優(yōu)個(gè)體,則用最優(yōu)個(gè)體bestlndividual替代Best(t)中的最差個(gè)體.得到更新后的精英庫Best(t+1);

(8)是否滿足終止條件:若是,則結(jié)束;否則,轉(zhuǎn)到Step3.

3 仿真實(shí)驗(yàn)結(jié)果與分析

本文制作仿真實(shí)驗(yàn)并對(duì)結(jié)果進(jìn)行分析,目的是在云計(jì)算任務(wù)分配上改進(jìn)遺傳算法和遺傳算法有更好的對(duì)比以及預(yù)測(cè)時(shí)間與實(shí)際執(zhí)行時(shí)間的比較.

3.1 實(shí)驗(yàn)?zāi)P?/h3>

為了驗(yàn)證上述遺傳算法在云計(jì)算任務(wù)分配上的可行性以及較好的穩(wěn)定性,本文需要選擇一個(gè)有意義的測(cè)試環(huán)境.本文選用2.40GHz的CPU和2GB的RAM作為硬件環(huán)境,Windows XP的操作系統(tǒng),JDK7.0的基礎(chǔ)環(huán)境及Ant1.8.2的編譯工具.

首先設(shè)置參數(shù):worker為50,task為50;每個(gè)task劃分為子任務(wù)數(shù)范圍為[20,80].

終止條件:達(dá)到最大迭代數(shù)或如果連續(xù)50代總?cè)蝿?wù)完成時(shí)間與任務(wù)平均完成時(shí)間都沒有變化時(shí),終止算法.

3.2 實(shí)驗(yàn)結(jié)果

在增加流量負(fù)載和暫時(shí)飽和的情況下,本文算法的平均完成時(shí)間與GA算法進(jìn)行比較(如圖2所示).橫坐標(biāo)為任務(wù)的申請(qǐng)數(shù)量.縱坐標(biāo)為兩種算法分別進(jìn)行處理申請(qǐng)作業(yè)所消耗的時(shí)間.

圖2 云計(jì)算環(huán)境下的算法比較

通過實(shí)驗(yàn),可以看出:本文算法(藍(lán)線)的平均完成時(shí)間在任務(wù)較少時(shí)優(yōu)勢(shì)較小而任務(wù)較多時(shí)遠(yuǎn)遠(yuǎn)小于GA算法(紅線),主要原因是:采用了雙精英策略思想,隨著任務(wù)數(shù)量的增多預(yù)測(cè)時(shí)間逐漸接近實(shí)際時(shí)間.

4 結(jié)束語

本文提出了一種基于遺傳算法的任務(wù)調(diào)度算法,減少了處理請(qǐng)求任務(wù)的平均完成時(shí)間,保證云服務(wù)的質(zhì)量.通過本算法可以對(duì)云計(jì)算環(huán)境下這種模型實(shí)現(xiàn)較為理想的任務(wù)調(diào)度,它是一種有效的任務(wù)調(diào)度算法.

〔1〕FOSTER I,YONG ZHAO,RAICU I,et al.Cloud computing and grid computing 360-degree compared[C]//Proceedings of the 2008 Grid Computing Environments Workshop.Washington, DC:IEEE Computer Society,2008:1-10.

〔2〕ARMBRUST M,Fox A,GRIFFITH R,et al.Above the clouds:A Berkeley view of cloud computing[EB/OL].[2010-01-25].http://www.eecs.berleley.edu/Pubs/Techrpts/2009/EECS-2009-28.pdf.

〔3〕陳康.云計(jì)算:系統(tǒng)實(shí)例與研究現(xiàn)狀[D].軟件學(xué)報(bào),2009.

〔4〕馮登國,等.云計(jì)算安全研究[D].軟件學(xué)報(bào),2011.

〔5〕Meng W,Han XD,Hong BR.Bee evolutionary genetic algorithm.Acta Electronica Sinica,2006,34(7):1294-1300(in Chinese with English abstract).

〔6〕Eglover,Tabu search:Part I.ORSA Journal on Computing.1989,1(3):1 90-206.

〔7〕王徽蓉,等.基于遺傳算法與線性鑒別的近紅外光譜玉米品種鑒別研究[D].光譜學(xué)與光譜分析,2011(3).

〔8〕李軍華,等.噪聲環(huán)境下多模態(tài)函數(shù)優(yōu)化的遺傳算法[D].電子學(xué)報(bào),2012(2).

〔9〕Danoy G.Bouvry P,Martins T.Hlcga:A hybrid com-petitive coevolutionary genetic algorithm.In:Hoes L,ed.Proc.of the 6th Int,I Conf.on Hybrid Intelligent Systems.Com-puter Society Press,2006.48-51.[doi:10.1109/HIS.2006.264931].

〔10〕DEAN J,GHEMAWAT S.MapReduce:simplified data processing on large clusters[C]//Proceedings of the 6th Symposium on Operating System Design and Implementation.New York:ACM,2004:137-150.

〔11〕Mu CH.Jiao LC,Liu Y.M-Elite coevolutionary algorithm for numerical optimization.Journal of Softwar-e,2009,20(11):2925-2938(in Chinese with English abstrac-t).http://www.jos.org.cn/1000-9825/3496.htm[doi-:10.3724/SP.J.1001.2009.03496].

猜你喜歡
計(jì)算環(huán)境任務(wù)調(diào)度適應(yīng)度
云計(jì)算環(huán)境下網(wǎng)絡(luò)安全等級(jí)保護(hù)的實(shí)現(xiàn)途徑
改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法
基于改進(jìn)NSGA-Ⅱ算法的協(xié)同制造任務(wù)調(diào)度研究
基于時(shí)間負(fù)載均衡蟻群算法的云任務(wù)調(diào)度優(yōu)化
大數(shù)據(jù)云計(jì)算環(huán)境下的數(shù)據(jù)安全
電子制作(2017年20期)2017-04-26 06:57:48
基于空調(diào)導(dǎo)風(fēng)板成型工藝的Kriging模型適應(yīng)度研究
中國塑料(2016年11期)2016-04-16 05:26:02
云計(jì)算環(huán)境中任務(wù)調(diào)度策略
云計(jì)算中基于進(jìn)化算法的任務(wù)調(diào)度策略
云計(jì)算中基于進(jìn)化算法的任務(wù)調(diào)度策略
基于云計(jì)算環(huán)境下的分布存儲(chǔ)關(guān)鍵技術(shù)探討
河南科技(2014年11期)2014-02-27 14:16:47
青阳县| 周至县| 富裕县| 威海市| 岳池县| 平南县| 东至县| 大名县| 宝丰县| 迁安市| 平顶山市| 大厂| 三明市| 彝良县| 庄河市| 全南县| 新乡市| 泰和县| 汨罗市| 西充县| 江津市| 台山市| 嫩江县| 通山县| 铅山县| 济南市| 伊金霍洛旗| 永川市| 德清县| 江北区| 大港区| 潼南县| 涡阳县| 武隆县| 静乐县| 开封市| 禄丰县| 辽宁省| 尚志市| 财经| 大关县|