陳春玲++張瑞霞++曹萌萌

摘 要：云環(huán)境下的工作流，進(jìn)行合理的任務(wù)調(diào)度，可以克服地理限制，節(jié)省資源，從而提高用戶的滿意度。本文提出改進(jìn)算法：快速非支配排序貝葉斯算法NSGAboa，該算法是快速非支配排序算法NSGAII和貝葉斯算法BOA的結(jié)合，根據(jù)種群中個(gè)體間的分布收斂程度來改變產(chǎn)生個(gè)體的方法，利用了種群個(gè)體信息和全局信息。實(shí)驗(yàn)證明該算法使得最優(yōu)解的分布更加均勻，加快了個(gè)體產(chǎn)生的速度，縮短了種群的收斂速度。

關(guān)鍵詞：任務(wù)調(diào)度；快速非支配排序；貝葉斯；云計(jì)算

Improvement of Cloud-based Scheduling Algorithm

Ruixia Zhang Chunling Chen Mengmeng Cao（Nangjing University of Posts

and Telecommunications School of Computer Science &Technology，School of Software；Nanjing China；210003）

Abstract：The workflow reasonable scheduling in the cloud environment， which has the ability to improve user satisfaction， can overcome geographical restrictions and saving resources. The article process a new algorithm： NSGAboa. the NSGAboa algorithm is a union of the fast nondominated sorting algorithm and Bayesian algorithm. NSGAboa algorithm， based on the degree of convergence of the distribution of the population among individuals changes the methods of generating solution individuals. The algorithm takes full advantage of the individual information of the populations and global information. Experiments show that this approach allows a more uniform distribution of the optimal solution， and reduces the convergence rate of population.

Key words：task scheduling；fast nondominated sorting；BOA；cloud computing

任務(wù)調(diào)度[1]策略對(duì)云計(jì)算的性能具有重要的影響，調(diào)度不同環(huán)境中的不同任務(wù)在云計(jì)算中是一種常見現(xiàn)象，傳統(tǒng)的分布式計(jì)算和并行計(jì)算卻不能滿足這種應(yīng)用。任務(wù)調(diào)度算法有很多，它們?cè)谝欢ǔ潭壬咸岣吡斯ぷ髁鞯膱?zhí)行效率，減少了執(zhí)行時(shí)間。在云環(huán)境中任務(wù)調(diào)度的優(yōu)化可以減少任務(wù)完成時(shí)間，提高服務(wù)質(zhì)量，所以研究任務(wù)調(diào)度算法意義重大。傳統(tǒng)算法各有其優(yōu)點(diǎn)，我們將快速非支配排序算法和貝葉斯算法結(jié)合，讓貝葉斯算法彌補(bǔ)快速非支配算法不能利用種群全局信息的不足，最終是改進(jìn)后算法充分利用種群的全局信息和局部信息。在種群個(gè)體收斂到適當(dāng)?shù)臅r(shí)刻由快速非支配排序算法轉(zhuǎn)換成貝葉斯算法，使得個(gè)體產(chǎn)生的速度加快，提高新算法的效率。

1 云計(jì)算中任務(wù)調(diào)度相關(guān)介紹

云計(jì)算作為一種計(jì)算模式，區(qū)別于傳統(tǒng)的分布式計(jì)算和網(wǎng)格計(jì)算。云計(jì)算中的計(jì)算任務(wù)分布在虛擬的資源池上。這些資源池由許多地理位置分散的網(wǎng)絡(luò)終端構(gòu)成，這些網(wǎng)絡(luò)終端通過互聯(lián)網(wǎng)和路由器進(jìn)行通信。各種應(yīng)用系統(tǒng)按需透明地獲得性價(jià)比較高的計(jì)算能力、存儲(chǔ)資源和信息服務(wù)。云計(jì)算具有虛擬化、靈活性、可擴(kuò)展性、可靠性等特點(diǎn)[2]。

云計(jì)算中，任務(wù)調(diào)度的實(shí)質(zhì)是將n個(gè)相互獨(dú)立的任務(wù)分配到m個(gè)異構(gòu)的可用資源上，使得總?cè)蝿?wù)的完成時(shí)間最少，并能充分的利用資源[3]。由于云計(jì)算系統(tǒng)的異構(gòu)性和動(dòng)態(tài)性，資源類型和任務(wù)的差異性，性能較低的調(diào)度算法，會(huì)增加任務(wù)執(zhí)行時(shí)間，從而降低系統(tǒng)的性能，甚至引起系統(tǒng)崩潰。

調(diào)度算法的好壞對(duì)云計(jì)算的性能表現(xiàn)具有重要的意義，很多現(xiàn)有算法都不能完全滿足云環(huán)境下對(duì)算法的需求。本文將快速非支配排序[4，8]和貝葉斯兩種算法結(jié)合，充分利用了種群的局部和全局信息，提高了算法的性能，使得新算法更好的適應(yīng)云計(jì)算系統(tǒng)。

2 任務(wù)調(diào)度算法研究

2.1 非支配排序算法NSGAⅡ

2.1.1 快速非支配排序算法

NSGA II引入了快速非支配排序算法，降低了計(jì)算的復(fù)雜度。在保持種群個(gè)體多樣性并可以使Pareto最優(yōu)解分布的更加均勻的前提下，對(duì)種群個(gè)體進(jìn)行分層，把種群個(gè)體的擁擠度作為衡量個(gè)體品質(zhì)的標(biāo)桿，選出高品質(zhì)個(gè)體。為了擴(kuò)大采樣空間，使用精英策略即把子代種群和它的父代種群合并，讓兩個(gè)時(shí)代的所有個(gè)體相互競(jìng)爭(zhēng)產(chǎn)生下一代。精英策略讓所有的基因都參與競(jìng)爭(zhēng)，不僅剔除了不良基因而且保證了優(yōu)良基因的傳承。

現(xiàn)用pop表示種群，設(shè)pop中有N個(gè)個(gè)體i（i=1，2，…，N），種群中有ni個(gè)解支配個(gè)體i，Si為這ni個(gè)解組成的集合，我們稱其為支配集，ni、Si是個(gè)體i的兩個(gè)重要參數(shù)。將種群pop分為m層，每層設(shè)為一個(gè)子集Fi，則共有m個(gè)子集Fi、…、Fm，則∪Fj，其中j=1，2，…，m。

快速非支配排序算法的描述如下：endprint

（1）將ni=0即支配集為空的個(gè)體劃分到分層集合F1中，組成非支配層。（2）遍歷分層集F1，設(shè)F1每一個(gè)個(gè)體k的支配集為 Sk，支配集Sk中的個(gè)體數(shù)為nk，若nk≠o則將n減1，若nk=o，則將個(gè)體k放入F2中，組成非支配層F2。（3）把集合pop當(dāng)做當(dāng)前非支配層集合重復(fù)1-2，直到種群pop中的個(gè)體都被劃分到非支配層中。

2.1.2 擁擠度[5]、精英策略和基因操作

通過個(gè)體支配集和支配集中個(gè)體數(shù)篩選產(chǎn)生下一代種群，種群中的個(gè)體是分散存在。每個(gè)個(gè)體與相鄰個(gè)體間的距離叫做這個(gè)個(gè)體的擁擠度，如個(gè)體i的擁擠度表示為P[i]distance。擁擠度計(jì)算的主要步驟是排序，排序完成后再依次計(jì)算個(gè)體的擁擠度。排序操作是以種群中個(gè)體的目標(biāo)函數(shù)值的大小為依據(jù)對(duì)個(gè)體進(jìn)行排序。如果有m個(gè)目標(biāo)函數(shù)，并使用速度較快的快速排序時(shí)，該算的時(shí)間復(fù)雜度為o（m*N*logN）。

NSGA II引入了精英策略，為了防止在傳統(tǒng)的遺傳算法進(jìn)化過程中，出現(xiàn)破壞或者丟失父代中具有優(yōu)秀基因個(gè)體的現(xiàn)象。精英策略就是把子代的個(gè)體和其父代的個(gè)體合并在一起，讓他們共同參與到進(jìn)化過程中。使用精英策略后再用快速非支配排序算法對(duì)合并后的種群進(jìn)行分層。

NSGA II算法產(chǎn)生的子代種群之所以繼承了父代的優(yōu)秀基因是因?yàn)槔昧诉z傳算法[6]。遺傳算法在算法設(shè)計(jì)中，是依據(jù)進(jìn)化論中生物繁衍優(yōu)勝劣汰的真實(shí)情況設(shè)計(jì)的，包括選擇、雜交和變異。NSGA II所用的遺傳算法采用二元錦標(biāo)賽選擇個(gè)體，采用模擬二進(jìn)制交叉SBX和多項(xiàng)式變異來完成交叉和變異操作。好的遺傳算法不僅是要能理論實(shí)現(xiàn)，更重要的是可以達(dá)到實(shí)際需要的目標(biāo)，并能夠得到包括所有優(yōu)秀基因的最優(yōu)解。

2.2 貝葉斯優(yōu)化算法（BOA）[8]

在分布式算法中，變量之間相互獨(dú)立或者存在某種依賴關(guān)系，不同分布式算法的主要區(qū)別在于選取下一代的概率模型不同。貝葉斯優(yōu)化算法具有良好全局收斂性，這正是是本文改進(jìn)算法所需要的。

貝葉斯優(yōu)化算法是多變量相關(guān)型分布式算法的一種。貝葉斯算法的初始種群是根據(jù)概率分布模型均勻分布隨機(jī)產(chǎn)生的。我們通過很多進(jìn)化算法來選出優(yōu)秀個(gè)體，如比例選擇、截?cái)噙x擇和二進(jìn)制錦標(biāo)賽選擇等。選擇出的優(yōu)秀個(gè)體組成新的種群，然后在這個(gè)新種群上建立貝葉斯網(wǎng)絡(luò)概率模型。對(duì)模型進(jìn)行采樣，從中獲取新的個(gè)體，并將新的個(gè)體重新放入原有種群中或者是完全替代原有種群，在滿足終止條件之前一直重復(fù)這個(gè)過程。貝葉斯優(yōu)化算法的終止條件有：最優(yōu)解已經(jīng)找到，種群的多樣性已經(jīng)消失或者是陷入了局部最優(yōu)。

貝葉斯優(yōu)化算法：（1）set：t=0，均勻分布隨機(jī)產(chǎn)生初始種群P0；（2）根據(jù)個(gè)體指標(biāo)從Pt中選擇優(yōu)秀個(gè)體集St；（3）在一定的選擇方法（本文實(shí)驗(yàn)中采用的是比例選擇）和限制條件下構(gòu)建符合要求的貝葉斯網(wǎng)絡(luò)B；（4）根據(jù)貝葉斯網(wǎng)絡(luò)B的聯(lián)合分布函數(shù)產(chǎn)生新的解集合Ot，形成新的種群Pt+1：將Ot放入Pt中，或者用Ot完全替代P，為了保證優(yōu)秀基因的完整，本文采用的是前一種做法；（5）轉(zhuǎn)向（2）直到滿足終止條件結(jié)束。

貝葉斯算法的核心和關(guān)鍵是通過數(shù)據(jù)分析來獲得貝葉斯網(wǎng)絡(luò)。貝葉斯網(wǎng)絡(luò)是具有結(jié)構(gòu)和參數(shù)的有向無環(huán)圖模型，其中的節(jié)點(diǎn)對(duì)應(yīng)的是變量，邊對(duì)應(yīng)的是變量間的關(guān)系，而參數(shù)就是由變量間的關(guān)系決定的。這些參數(shù)和變量間存在聯(lián)合概率分布： ，這里的X=（X1，X2，…，Xn）是一個(gè)向量，是網(wǎng)絡(luò)中所有變量的集合， 是Xi的所有父輩的集合， 是Xi在給定父輩 下的條件概率。

2.3 兩種算法的對(duì)比

NSGAⅡ引進(jìn)了快速非支配算法和精英策略，但是它的遺傳操作忽略了多目標(biāo)問題解空間Pareto解集分布的規(guī)律性，僅作用于個(gè)體之間。即該算法只考慮到了種群的局部信息沒有全局概念，沒有很好地利用Pareto解集分布的規(guī)律性。

貝葉斯算法的初始種群是根據(jù)概率分布模型均勻分布隨機(jī)產(chǎn)生的，充分利用到了種群的全局信息。在種群當(dāng)中的個(gè)體開始呈現(xiàn)一定的分布規(guī)律的情況下使用該算法，可以增大產(chǎn)生個(gè)體的概率，從而能提高算法的收斂速度。

3 改進(jìn)算法NSGAboa

NSGAⅡ的遺傳操作忽略了多目標(biāo)問題解空間Pareto解集分布的規(guī)律性，只考慮到解的個(gè)體特征，而分布式估計(jì)算法充分地利用了種群的全局信息，但是分布式估計(jì)算法較且復(fù)雜操作困難[12]。貝葉斯算法簡(jiǎn)單易懂且充分利用到了種群的全局信息，因此本文將貝葉斯算法和NSGAⅡ算法結(jié)合。在個(gè)體比較分散的初期使用NSGAⅡ算法，隨著算法的運(yùn)行，種群中個(gè)體分布越緊湊，收斂程度越高，當(dāng)其收斂到一定程度時(shí)使用貝葉斯優(yōu)化算法。此時(shí)使用貝葉斯算法可以充分利用解集的規(guī)律性和種群的全局信息，增加個(gè)體的生產(chǎn)速度，最終提高了算法的性能。

NSGAⅡ中遺傳算法，一代代繁衍的過程中，個(gè)體不斷向Pareto目標(biāo)靠近，即不斷收斂。我們利用個(gè)體的這種收斂程度來判斷用哪種算法產(chǎn)生新的種群。目標(biāo)空間中的每一個(gè)個(gè)體都可以看做一個(gè)點(diǎn)，種群就是一個(gè)點(diǎn)集，判斷種群中個(gè)體的收斂程度就是判斷這個(gè)點(diǎn)集中點(diǎn)的收斂程度。

改進(jìn)算法NSGAboa的描述：

（1）set：t=0，初始化種群P0；

（2）評(píng)價(jià)群體；（3）判斷是否收斂，如果收斂set：CF=0.7，否則set：CF=0.3；

（4）判斷是否0﹤rand（）﹤1，是則改用貝葉斯優(yōu)化算法，建立概率模型產(chǎn)生下一代，否則繼續(xù)采用NSGAⅡ算法用遺傳操作產(chǎn)生下一代；

（5）從Pt中選擇，產(chǎn)生新種群Ot，將Ot加入或完全替代Pt，形成新的種群Pt+1；

（6）返回（2）直到滿足終止條件。

4 NSGAboa算法測(cè)試

此處使用三個(gè)基準(zhǔn)函數(shù)測(cè)試改進(jìn)后的算法，判斷改進(jìn)算法NSGAboa的性能。分別通過連續(xù)凸形、連續(xù)非凸形和具有五段離散性的三個(gè)函數(shù)來測(cè)試算法性能。endprint

函數(shù)1：

函數(shù)2：

函數(shù)3：

其中，n=50， 。

在多目標(biāo)優(yōu)化問題測(cè)試中，我們選取的測(cè)試目標(biāo)有兩個(gè)：收斂性測(cè)度M1和分布性測(cè)試sd。收斂性是實(shí)際解集與理論解集的最短距離的平均值，這個(gè)值越小說明其收斂性越好。分布性測(cè)度是個(gè)體間距離的標(biāo)準(zhǔn)差，標(biāo)準(zhǔn)差越小，說明實(shí)際解集中個(gè)體分布越均勻，個(gè)體間的距離相近。

假設(shè)實(shí)際解集為Y'，理論解集為 ，定義：

假設(shè)解集中個(gè)體數(shù)為n，di表示個(gè)體i到其他個(gè)體的距離的最小值， 是di的平均值，定義： 。

實(shí)驗(yàn)結(jié)果如圖1，改進(jìn)后的算法得到的Pareto前沿與真實(shí)前沿曲線基本吻合，由表1可發(fā)現(xiàn)NSGAboa算法與NSGAⅡ相比，在收斂性和分布性上有很大的改進(jìn)。

5 結(jié)論

MSGAⅡ引進(jìn)快速非支配排序算法并根據(jù)擁擠度選擇優(yōu)異個(gè)體，在保持種群個(gè)體多樣性的前提下降低了復(fù)雜程度，使最優(yōu)解分布更均勻。貝葉斯優(yōu)化算法根據(jù)多目標(biāo)優(yōu)化問題的實(shí)質(zhì)，將變量之間的關(guān)系量化，估計(jì)概率模型，用非占先排序及擁擠度來選擇優(yōu)異個(gè)體。MSGAⅡ關(guān)注的是種群中的個(gè)體信息，而貝葉斯優(yōu)化算法則充分考慮了種群的全局信息。本文將兩種算法結(jié)合，根據(jù)種群中個(gè)體間的分布收斂程度來改變個(gè)體的產(chǎn)生方法。通過實(shí)驗(yàn)證明這樣做產(chǎn)生了顯著的效果，結(jié)合產(chǎn)生的新算法NSGAboa加快了個(gè)體產(chǎn)生的速度，提高了算法的性能，在收斂性和分布性上有了很大的提高。對(duì)于資源消耗、負(fù)載均衡、種群初始化等問題本文沒有進(jìn)行過多的考慮，還需進(jìn)一步深入研究。

[參考文獻(xiàn)]

[1]徐小龍，程春玲，熊婧夷，王汝傳.一種基于移動(dòng)Agent的云端計(jì)算任務(wù)安全分割與分配算法[J].北京理工大學(xué)學(xué)報(bào)，2011，31（8）：922-926.

[2]曹萌萌.基于云計(jì)算的調(diào)度算法的研究與改進(jìn)[D].南京郵電大學(xué)， 2012.

[3]史恒亮.云計(jì)算任務(wù)調(diào)度研究[D].南京理工大學(xué)，2012.

[4]江敏.貝葉斯優(yōu)化算法的若干問題研究及應(yīng)用[D].上海大學(xué)，2011.

[5]KRUATRACHUE B，LEWIS T.Grain size determination for parallel processing [J].IEEE Software，1988，5（1）：23-32.

[6]SEHADRI A，Multi-objective optimization using evolutionary algorithms（MOEA）[J].IEEE Transactions on evolutionary Computation，2002，Volume 6，Issue 5，：526-526.

[7]陳靜.改進(jìn)的非支配排序多目標(biāo)遺傳算法及應(yīng)用[D].湘潭：湘潭大學(xué)，2009.

[8]PELIKAN M，GOLDBERG D E，CANTUPAZ E B：The bayesian optimization algorithm[C].Proceedings of the Genetic and Evolutionary Computation Conference，Orlando，F(xiàn)lorida， USA.1999：525-532.

[9]王浣塵.可行性研究和多目標(biāo)決策[M].北京：清華大學(xué)出版社，1995.

[10]LARRANAGA P，LOZANO J.Estimation of distribution algorithms：A new tool for evolutionary computation[M]. Holland：Kluwer Academic Publishers：2002.

[11]張林，羅曉初，徐瑞林，趙理.基于時(shí)間序列的電力負(fù)荷預(yù)測(cè)新算法研究[J].電網(wǎng)技術(shù)，2006-12-30.

[12]李小俊，熊勵(lì).基于對(duì)稱點(diǎn)對(duì)序列的帶狀圖骨架化算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2006-10-21.endprint

函數(shù)1：

函數(shù)2：

函數(shù)3：

其中，n=50， 。

在多目標(biāo)優(yōu)化問題測(cè)試中，我們選取的測(cè)試目標(biāo)有兩個(gè)：收斂性測(cè)度M1和分布性測(cè)試sd。收斂性是實(shí)際解集與理論解集的最短距離的平均值，這個(gè)值越小說明其收斂性越好。分布性測(cè)度是個(gè)體間距離的標(biāo)準(zhǔn)差，標(biāo)準(zhǔn)差越小，說明實(shí)際解集中個(gè)體分布越均勻，個(gè)體間的距離相近。

假設(shè)實(shí)際解集為Y'，理論解集為 ，定義：

假設(shè)解集中個(gè)體數(shù)為n，di表示個(gè)體i到其他個(gè)體的距離的最小值， 是di的平均值，定義： 。

實(shí)驗(yàn)結(jié)果如圖1，改進(jìn)后的算法得到的Pareto前沿與真實(shí)前沿曲線基本吻合，由表1可發(fā)現(xiàn)NSGAboa算法與NSGAⅡ相比，在收斂性和分布性上有很大的改進(jìn)。

5 結(jié)論

MSGAⅡ引進(jìn)快速非支配排序算法并根據(jù)擁擠度選擇優(yōu)異個(gè)體，在保持種群個(gè)體多樣性的前提下降低了復(fù)雜程度，使最優(yōu)解分布更均勻。貝葉斯優(yōu)化算法根據(jù)多目標(biāo)優(yōu)化問題的實(shí)質(zhì)，將變量之間的關(guān)系量化，估計(jì)概率模型，用非占先排序及擁擠度來選擇優(yōu)異個(gè)體。MSGAⅡ關(guān)注的是種群中的個(gè)體信息，而貝葉斯優(yōu)化算法則充分考慮了種群的全局信息。本文將兩種算法結(jié)合，根據(jù)種群中個(gè)體間的分布收斂程度來改變個(gè)體的產(chǎn)生方法。通過實(shí)驗(yàn)證明這樣做產(chǎn)生了顯著的效果，結(jié)合產(chǎn)生的新算法NSGAboa加快了個(gè)體產(chǎn)生的速度，提高了算法的性能，在收斂性和分布性上有了很大的提高。對(duì)于資源消耗、負(fù)載均衡、種群初始化等問題本文沒有進(jìn)行過多的考慮，還需進(jìn)一步深入研究。

[參考文獻(xiàn)]

[1]徐小龍，程春玲，熊婧夷，王汝傳.一種基于移動(dòng)Agent的云端計(jì)算任務(wù)安全分割與分配算法[J].北京理工大學(xué)學(xué)報(bào)，2011，31（8）：922-926.

[2]曹萌萌.基于云計(jì)算的調(diào)度算法的研究與改進(jìn)[D].南京郵電大學(xué)， 2012.

[3]史恒亮.云計(jì)算任務(wù)調(diào)度研究[D].南京理工大學(xué)，2012.

[4]江敏.貝葉斯優(yōu)化算法的若干問題研究及應(yīng)用[D].上海大學(xué)，2011.

[5]KRUATRACHUE B，LEWIS T.Grain size determination for parallel processing [J].IEEE Software，1988，5（1）：23-32.

[6]SEHADRI A，Multi-objective optimization using evolutionary algorithms（MOEA）[J].IEEE Transactions on evolutionary Computation，2002，Volume 6，Issue 5，：526-526.

[7]陳靜.改進(jìn)的非支配排序多目標(biāo)遺傳算法及應(yīng)用[D].湘潭：湘潭大學(xué)，2009.

[8]PELIKAN M，GOLDBERG D E，CANTUPAZ E B：The bayesian optimization algorithm[C].Proceedings of the Genetic and Evolutionary Computation Conference，Orlando，F(xiàn)lorida， USA.1999：525-532.

[9]王浣塵.可行性研究和多目標(biāo)決策[M].北京：清華大學(xué)出版社，1995.

[10]LARRANAGA P，LOZANO J.Estimation of distribution algorithms：A new tool for evolutionary computation[M]. Holland：Kluwer Academic Publishers：2002.

[11]張林，羅曉初，徐瑞林，趙理.基于時(shí)間序列的電力負(fù)荷預(yù)測(cè)新算法研究[J].電網(wǎng)技術(shù)，2006-12-30.

[12]李小俊，熊勵(lì).基于對(duì)稱點(diǎn)對(duì)序列的帶狀圖骨架化算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2006-10-21.endprint

函數(shù)1：

函數(shù)2：

函數(shù)3：

其中，n=50， 。

在多目標(biāo)優(yōu)化問題測(cè)試中，我們選取的測(cè)試目標(biāo)有兩個(gè)：收斂性測(cè)度M1和分布性測(cè)試sd。收斂性是實(shí)際解集與理論解集的最短距離的平均值，這個(gè)值越小說明其收斂性越好。分布性測(cè)度是個(gè)體間距離的標(biāo)準(zhǔn)差，標(biāo)準(zhǔn)差越小，說明實(shí)際解集中個(gè)體分布越均勻，個(gè)體間的距離相近。

假設(shè)實(shí)際解集為Y'，理論解集為 ，定義：

假設(shè)解集中個(gè)體數(shù)為n，di表示個(gè)體i到其他個(gè)體的距離的最小值， 是di的平均值，定義： 。

實(shí)驗(yàn)結(jié)果如圖1，改進(jìn)后的算法得到的Pareto前沿與真實(shí)前沿曲線基本吻合，由表1可發(fā)現(xiàn)NSGAboa算法與NSGAⅡ相比，在收斂性和分布性上有很大的改進(jìn)。

5 結(jié)論

MSGAⅡ引進(jìn)快速非支配排序算法并根據(jù)擁擠度選擇優(yōu)異個(gè)體，在保持種群個(gè)體多樣性的前提下降低了復(fù)雜程度，使最優(yōu)解分布更均勻。貝葉斯優(yōu)化算法根據(jù)多目標(biāo)優(yōu)化問題的實(shí)質(zhì)，將變量之間的關(guān)系量化，估計(jì)概率模型，用非占先排序及擁擠度來選擇優(yōu)異個(gè)體。MSGAⅡ關(guān)注的是種群中的個(gè)體信息，而貝葉斯優(yōu)化算法則充分考慮了種群的全局信息。本文將兩種算法結(jié)合，根據(jù)種群中個(gè)體間的分布收斂程度來改變個(gè)體的產(chǎn)生方法。通過實(shí)驗(yàn)證明這樣做產(chǎn)生了顯著的效果，結(jié)合產(chǎn)生的新算法NSGAboa加快了個(gè)體產(chǎn)生的速度，提高了算法的性能，在收斂性和分布性上有了很大的提高。對(duì)于資源消耗、負(fù)載均衡、種群初始化等問題本文沒有進(jìn)行過多的考慮，還需進(jìn)一步深入研究。

[參考文獻(xiàn)]

[1]徐小龍，程春玲，熊婧夷，王汝傳.一種基于移動(dòng)Agent的云端計(jì)算任務(wù)安全分割與分配算法[J].北京理工大學(xué)學(xué)報(bào)，2011，31（8）：922-926.

[2]曹萌萌.基于云計(jì)算的調(diào)度算法的研究與改進(jìn)[D].南京郵電大學(xué)， 2012.

[3]史恒亮.云計(jì)算任務(wù)調(diào)度研究[D].南京理工大學(xué)，2012.

[4]江敏.貝葉斯優(yōu)化算法的若干問題研究及應(yīng)用[D].上海大學(xué)，2011.

[5]KRUATRACHUE B，LEWIS T.Grain size determination for parallel processing [J].IEEE Software，1988，5（1）：23-32.

[6]SEHADRI A，Multi-objective optimization using evolutionary algorithms（MOEA）[J].IEEE Transactions on evolutionary Computation，2002，Volume 6，Issue 5，：526-526.

[7]陳靜.改進(jìn)的非支配排序多目標(biāo)遺傳算法及應(yīng)用[D].湘潭：湘潭大學(xué)，2009.

[8]PELIKAN M，GOLDBERG D E，CANTUPAZ E B：The bayesian optimization algorithm[C].Proceedings of the Genetic and Evolutionary Computation Conference，Orlando，F(xiàn)lorida， USA.1999：525-532.

[9]王浣塵.可行性研究和多目標(biāo)決策[M].北京：清華大學(xué)出版社，1995.

[10]LARRANAGA P，LOZANO J.Estimation of distribution algorithms：A new tool for evolutionary computation[M]. Holland：Kluwer Academic Publishers：2002.

[11]張林，羅曉初，徐瑞林，趙理.基于時(shí)間序列的電力負(fù)荷預(yù)測(cè)新算法研究[J].電網(wǎng)技術(shù)，2006-12-30.

[12]李小俊，熊勵(lì).基于對(duì)稱點(diǎn)對(duì)序列的帶狀圖骨架化算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2006-10-21.endprint