云計算任務調度策略與優化算法研究

TURGANBEK DILNUR

摘 要：將云環境運用到科學工作當中，即可以使得任務調度更好的完成，還可以使得用戶更加滿意，之前解決調度問題的方式是將一個大問題轉換成各個小問題，然后樹立多數量的目標，將云環境彈性的特點充分發揮出來，之后提出了更加完善的方法是快速非支配排序分布算法，主要目的是使得工作時間縮短降低成本，使得云計算完全運用到服務當中。將快速飛支配排序算法和分布估計計算法共同運用在模擬調度當中，借鑒種群收斂和有關遺傳的知識分子呢對種群進行采樣分析，培養出全新的個體。這個方法是通過種群來培養新的個體，也就是將種群的特點和個體的特點相結合，使得最好的方式得到充分的運用。將非支配排序算法運用到云計算中，然后在模擬器中進行運行。工作流主要用神經學工作流，同時與運用其他工作流的模擬器進行對比。之后設計出了相關函數，是為了測量培養出的新個體的質量的大小，。通過對實驗結果的對比，改進之后的算法可以達到降低時間和成本的目的，同時使得用戶的滿意度提高。

關鍵詞：快速非支配排序;任務調度;多目標優化;云計算;分布估計

1.課題的研究意義

任務調解和資源的分派在云計算里面起到了兩個重要的作用。在系統的工作流調度算法，沒有辦法在多個時間內求解。這是一個完整的NP問題。事實證明，

針對解決云計算調度問題，啟發式比定性算法更合適。因為如果采用不適合解決云計算調度問題的方式，會降低工作效率同時還會增加成本，在云計算中的云服務中會使得經濟效益減弱，在滿足用戶的質量的同時要提升服務的目標是一個宗旨，為此研究科學工作流下的云計算調度優化算法是極其重要的。

通過介紹課題在云計算、科學工作流和調度算法中的研究背景，并結合現有的算法存在一些問題，會造成一定的資源浪費。對現有算法進行改進，不僅能夠節省資源成本還能夠提升效率，所以說，研究云計算調度策略的優化算法是十分必要且有意義的。

2.非支配排序算法和分布估計算法的研究

為了以更快的方式找出運行過程中最好的方式，主要的方式就是講非支配排序算法和分布估計法以最快的速度結合起來，首先對非支配排列算法進行了概述。接下來介紹分布估計算法的相關概念。最后介紹兩種方法的組合。

2.1非支配排序算法

由于非主要的NSGA計算很復雜，所以針對于. NSGA的維護系統還沒有被研制出來。在2000年的時候，Deb等人對NSGA進行全新升級，于是出現了NSGAII，它的出現使得NSGA計算的復雜性降低，之前的適應度都是人主觀上決定的，現在NSGAII的出現通過擁擠度代替了之前的方法，這就使得在使用非支配順序之后，個體遺傳還能保持一致，就可以保證種群的種類多。NSGAII還研究出了對NSGA的維護系統，可以將各代個體相結合，之后將培養出的精英新個體保留下來，實現對NSGA系統的維護，以及精英個體的保留。由于個體中的所有個體都是分層存儲的，因此不會丟失精英個體，并且可以實現快速增加個體數量的目標。 NSGAⅡ算法的優點是可以均勻分配近似最優解，而不會限制優化目標函數的數量。此功能可以從多個基于Pareto的非主導級別中為當前方案選擇最佳解決方案，尤其是用于解決交通信號的多目標優化計時問題。

2.2分布估計算法

所謂分布估算法，最早是在統計學原理中用于對解空間問題從宏觀進化角度的解釋，

分布估算法和遺傳法相比較，分布估算法的優勢更大，因為這個方法的搜索能力是很強的，其次就是個體的收斂速度占據優勢。近幾年分布估算法被頻繁的運用到柔性作業車間：Wang等人提出了雙種群分布估算法，在培養出很多代之后，運用雙種群分布估算法對得到的個體進行分類和篩選，之后將不同的種群進行結合，在合并過程進行之前，要滿足合并的原則，然后對結合的種群進行采樣，對采樣數據進行分析，。因為車間的調度的問題是和云計算有一定關系的，所以采用的方法是多目標的，所以就研制出了一種叫Pareto的分布估計算法，這種方法主要依據的就是概率。但是這樣的算法很容易導致培養出的新個體早熟，所以就將兩個不同的種群通過不同的當時培養出精英個體，由此看來，通過不同的當時進行精英的開發，是最優解。[1]

針對解決柔性作業車間的這個問題，何小娟等人是有很好的解決辦法的，主要的方法就是運用概率，剛開始的時候，將不同的種群進行分類，然后運用不同的當時將工件制作出來， 統計每一種方法制作出工件的時間，篩選出消耗時間最短的方法作為最優解。之后通過實驗結果建立概率，然后設計模型，最后通過運用Bayesian將概率和模型總和起來，由于采樣的過程太多會導致個體的早熟，為了避免這種現象的出現，他又通過k均值的方法兩種群放在一起進行培養，最終得到優勢種群。在柔性作業車間調度問題中，分布估算法起到了很明顯的作用，然而建立準確的模型對于解決復雜問題是更加重要的。

所謂分布估算法，最早是在統計學原理中用于對解空間問題從宏觀進化角度的分布估算法和遺傳法相比較，分布估算法的優勢更大，因為這個方法的搜索能力是很強的，其次就是個體的收斂速度占據優勢。近幾年分布估算法被頻繁的運用到柔性作業車間：Wang等人提出了雙種群分布估算法，在培養出很多代之后，運用雙種群分布估算法對得到的個體進行分類和篩選，之后將不同的種群進行結合，在合并過程進行之前，要滿足合并的原則，然后對結合的種群進行采樣，對采樣數據進行分析。因為車間的調度的問題是和云計算有一定關系的，所以采用的方法是多目標的，所以就研制出了一種叫Pareto的分布估計算法，這種方法主要依據的就是概率。但是這樣的算法很容易導致培養出的新個體早熟，所以就將兩個不同的種群通過不同的當時培養出精英個體，由此看來，通過不同的當時進行精英的開發，是最優解。[1]

針對解決柔性作業車間的這個問題，何小娟等人是有很好的解決辦法的，主要的方法就是運用概率，剛開始的時候，將不同的種群進行分類，然后運用不同的當時將工件制作出來， 統計每一種方法制作出工件的時間，篩選出消耗時間最短的方法作為最優解。之后通過實驗結果建立概率，然后設計模型，最后通過運用Bayesian將概率和模型總和起來，由于采樣的過程太多會導致個體的早熟，為了避免這種現象的出現，他又通過k均值的方法兩種群放在一起進行培養，最終得到優勢種群。在柔性作業車間調度問題中，分布估算法起到了很明顯的作用，然而建立準確的模型對于解決復雜問題是更加重要的。

3.算法研究

3.1非支配排序算法

NSGAⅡ的執行步驟：

（1）隨機產生初始種群，此時種群的進化代數Gen=0。

（2）判斷第一代種群是否生成，如果是的話，執行下一步，否則通過遺傳操作（選擇、交叉和變異）來產生第一代的種群。

（3）將父代與子代中的個體進行合并，然后對合并后的種群采取快速非支配排序、分層。對解個體執行擁擠度計算，通過精英策略產生下一代種群。

（4）選擇、交叉和變異，生成新的種群。

（5）查看進化代數值是否達到預設值。

（6）所得種群就是所求的即為最優解集，否則使Gen=Gen+1，執行步驟（3）。

快速非支配排序的偽代碼：

Fast=nondominated=sort（Pop）

{

For each i in Pop

{

For each j in Pop

{if i dominate j then

Si=Si∪{j};

else if j dominate i then

ni=ni+1;

}

if ni=0 then

Fi=Fi∪{p}

}

i=1

While（Fi！=NULL）

{

H=NULL;

for each i in Fi

{ for each j in Si

nj=nj-1;

if nj=0 then H-H∪{j};

}

i=i+1;

Fi=H;

}

}

計算擁擠度的偽代碼：

Crowding-distance-assignment（Pop）

{

N=∣Pop∣

for each I， P[i]distance=0

for each object m

{

Pop=sort（Pop，m）

for i=2 to （N-1）

P[i]distance=P[i]distance+（P[i+1].m-P[i-1].m）

}

P[0]distance=P[N]distance=∞

}

這里將邊界值設置為無窮大，保證第一個和最后一個解個體一定會被選中。

3，2分布估計算法

（1）種群的初始化：令t=0，設種群為Pop（t），其中包含N個解。Pop（t）中的解個體適應度值都是采用隨機方式生成的。

（2）計算個體適應度：根據適應度函數計算解個體適應度值。

（3）選擇策略：運用一定的選擇策略選取適應度值最高的M個個體作為優秀個體，令個體集為S（t）。

（4）建立概率模型：根據S（t）估計出概 率分布模型Prob（t）。

（5）采樣并更新種群：依據建立的概率模型，采樣產生新的個體。令t=t+1，更新種群Pop（t+1）。

（6）終止判斷：檢查是否滿足終止條件，滿足，算法結束;否則，返回步驟（2））。

圖2為分布估計算法流程圖。

優化的非支配排序算法：

NSGA II引入了快速的非優勢排序算法和精英策略，但是對于大多數多目標問題，在決策空間中，對于Pareto解集的分布通常有特定的規則。NSGAⅡ基因工程忽略了該規則，僅在各個解決方案之間起作用。分布估計算法EDA中變量之間的關系由概率模型描述，這使得最大化利用人口分布信息并有效利用人口產生的歷史信息成為可能。然而，分布估計算法EDA的建模過程復雜且難以操作。在算法的早期階段，解決方案個體在總體中的分布是隨機且完全無規則的。目前，我們已經使用分布估計算法的隨機模型來建立新的個體，通常離最優解集很遠。此外，分布估計算法沒有像快速非優勢排序算法NSGAII那樣有效地使用單個局部信息。

本文將離散分布估計算法與非優勢排序算法結合在一起，以充分利用每種算法。當算法開始運行時，非主導算法的遺傳運算（交叉，變異）是分布式模型概率模型，因為初始組的各個解更加分散并且它們之間的關系相對較小。生成個體的可能性要高于生成新個體的可能性。當通過執行算法使總體的分布收斂到預定的期望值時，當總體的解個體顯示出特定的分布規律時，使用分布估計的概率模型生成解個體。可能性逐漸增加。

在算法的早期階段，使用隨機建模構建的解決方案的個體通常與Pareto最優解決方案集相去甚遠。遺傳算法具有快速優化優化的能力。在算法開始時，不滿足收斂規則。遺傳算法（交叉，變異）用于生成新的求解個體，從而加速了Pareto最優求解集的求解。首先，生成范圍為[0，1]的隨機變量。設置根據總體收斂性分配的比較變量，并將rand（）與CF進行比較，以確定用于生成新個體的方法。如果個體在人口中的分布是分散的，則沒有收斂的趨勢，或者收斂程度沒有達到期望值，并且如果CF = 0.7，則遺傳算法生成的個體數數量會增加。如果人口分布收斂到期望值且CF = 0.3，則概率模型將采樣更多新個體。

4.仿真實驗及結果分析

要想科學工作流能夠在云環境中正常進行，本文在模擬器中進行了實驗。針對云計算來說，它是一個可以對基礎架構進行建模和仿真的自包含平臺。 在進行模擬實驗之前，應設置實驗參數，例如帶寬值和任務長度。

算法完成后，通過檢查上一代解決方案的分布。將總體大小設置為70，將迭代次數設置為400，然后運行算法10次以獲取非劣性解集。使用快速非支配排序算法對總體進行分層，并使用擁堵作為同一層的選擇標準。

這種方式可以將Pareto的最優解被運用到各種地方，使得種群的種類數增大，將種群的信息以及相關信息了解的更加清楚。把NSGAeda算法與NSGAII算法對比一下。如圖4，在解決調度問題的時候，通過NSGAeda方法算出來的結果更具普遍性，種群種類數量更多。從圖中可以看出改進算法NSG Aeda調度的成本較低。由于這是一個多用途問題，因此在理想情況下，解決方案集中的各個方案無法同時實現調度時間和服務成本。用戶可以根據實際情況在執行時間和服務成本之間進行折中選擇，并對選擇的解決方案進行解碼以找到正確的任務調度解決方案。

圖4 解分布情況

不同數量的處理器具有不同的處理能力。不同的虛擬資源具有不同的處理任務的能力。當可用資源數量較少時，改進算法NSGAeda的最佳解決方案能力很差，并且通常無法找到最佳解決方案集。隨著虛擬資源數量的增加，NSGAeda算法找到最佳解決方案集的能力顯著提高，如圖5和6所示。

圖5 最優解的百分比 ? ? ? ? ? ? ? ? ? ? ? ? ? ?圖6 處理器數目

5.總結

為了更充分的理解本課題，首先對云計算、科學工作流和多目標問題的基本概念進行介紹。云計算的彈性特點是非常顯著的，在運用到科學工作流中的時候，優點更加明顯，主要的優點有：

（1）云計算可以出現在任何時候任何地方，當運用到科學工作中時，科學工作就不僅僅存在于實驗室中，還可以在任何地方被運用。

（2）數據云在任務調度中也起到很大作用，而且科學工作流中的數據驅動模式也是需要在任務調度中起作用，于是二者相互配合。

（3）云計算和科學工作流都是具有動態特征的，二者相結合，不會一直持續工作完成成本的浪費，可以節約成本。

（4）用戶運用云計算的費用低，這樣可以增加用戶數量，增加用戶的滿意度。

綜上所述，可以看出在云上執行科學工作流是可行的。且目前分布估計算法和非支配排序算法已經較為成熟，可以將二者相結合解決多目標問題。

對云計算的相關概念和特點進行了介紹，然后對工作流任務調度技術進行了總結，分析了多目標優化問題和相應的最優解。闡述了非支配排序算法和分布估算法的基本概念。此外還將分布估算法的優點運用到非支配排序算法中，對其進行改進，優點共存缺點互補，設計出了新的算法，為了很符合云計算無限資源的特點，設計出了目標函數，然后進行實驗，對實驗結果進行分析，最終得出結論。

參考文獻：

[1]Iuon-Chang Lin，Chen-Yang Cheng，Hsiang-Yu Chen. A real-time parking service with proxy re-encryption in vehicular cloud computing[J]. Engineering Applications of Artificial Intelligence，2019，85.

[2]Bahador Shojaiemehr，Amir Masoud Rahmani，Nooruldeen Nasih Qader. Automated negotiation for ensuring composite service requirements in cloud computing[J]. Journal of Systems Architecture，2019，99.

[3]Services Computing; Recent Findings in Services Computing Described by Researchers from Chongqing University （Energy and Migration Cost-aware Dynamic Virtual Machine Consolidation In Heterogeneous Cloud Datacenters）[J]. Computers， Networks & Communications，2019.

[4]AT&T Intellectual Property I L.P.; Patent Issued for Virtual Zones For Open Systems Interconnection Layer 4 Through Layer 7 Services In A Cloud Computing System （USPTO 10，389，796）[J]. Computers， Networks & Communications，2019.

[5]Information Technology - Cloud Computing; Researchers at Chosun University Target Cloud Computing （Ontology-based Security Context Reasoning for Power Iot-cloud Security Service）[J]. Computers， Networks & Communications，2019.

[6]胡朋.中小企業使用云計算技術的必要性分析[J].決策探索（下），2019（09）：24-25.

[7]Yawen Wang，Yunfei Guo，Zehua Guo，Thar Baker，Wenyan Liu. CLOSURE： A cloud scientific workflow scheduling algorithm based on attack–defense game model[J]. Future Generation Computer Systems，2019.

[8]黃引豪，馬鄆，林兵，於志勇，陳星.混合云環境下面向代價優化的工作流數據布局方法[J].計算機科學，2019，46（S2）：354-358+386.

[9]尚蕾，劉茜萍.基于任務分配和數據副本的科學工作流數據布局[J/OL].計算機工程：1-8[2020-01-02].https：//doi.org/10.19678/j.issn.1000-3428.0055397.

[10]Perkel Jeffrey M. Workflow systems turn raw data into scientific knowledge.[J]. Nature，2019，573（7772）.

[11]馮復劍.云環境下科學工作流的調度算法[J].計算機系統應用，2019，28（07）：127-132.

[12]黨云龍，封筠，殷夢瑩.截止時間約束的工作流調度自適應進化方法[J].石家莊鐵道大學學報（自然科學版），2019，32（03）：94-100.

[13]張繼炎，鄭漢垣.云環境下基于預算分配的科學工作流調度研究[J].計算機工程，2019，45（09）：40-48.

[14]Wenjun Ji. Research on Computer Software Engineering based on Scientific Workflow[P]. Proceedings of the 3rd International Conference on Mechatronics Engineering and Information Technology （ICMEIT 2019），2019.

[15]. China approves Thermo Fisher Scientific's PCR workflow to detect ASF[J]. National Hog Farmer，2019.

[16]高天羽. 截止時間約束下的云工作流成本優化算法研究[D].西北大學，2019.

[17]尹成國.云計算技術發展分析及其應用探討[J].網絡安全技術與應用，2019（09）：55-56.

[18]路艷雪，趙超凡，吳曉鋒，韓曉霞.基于改進的NSGA-Ⅱ多目標優化方法研究[J].計算機應用研究，2018，35（06）：1733-1737.

[19]吳燁燁，高尚.改進的分布估計算法求解多目標優化問題[J].計算機與數字工程，2019，47（06）：1357-1363.

[20]鄭瑛.云計算數據中心節能調度算法改進研究[J].西南大學學報（自然科學版），2019，41（12）：135-142.