◎姜賽達

（商丘職業(yè)技術(shù)學院 計算機系，河南 商丘 476000）

云計算是由網(wǎng)格計算發(fā)展而來的一種更注重商業(yè)化的新興商業(yè)計算模式，近年來得到快速的發(fā)展和廣泛的應(yīng)用而受到多行業(yè)的青睞。由于云計算技術(shù)的迅速發(fā)展推動了原有數(shù)據(jù)中心的變革，產(chǎn)生了一種新型的數(shù)據(jù)中心——云數(shù)據(jù)中心。云數(shù)據(jù)中心基于用戶，采用分布式技術(shù)，根據(jù)用戶需求為各類云服務(wù)提供資源共享架構(gòu)。在這種資源共享架構(gòu)下，用戶可以根據(jù)自己的需要動態(tài)使用云數(shù)據(jù)中心的硬件和軟件資源。硬件資源包括了計算、存儲和帶寬等多種資源，同時用戶根據(jù)服務(wù)使用資源量支付一定的服務(wù)費用，因此云數(shù)據(jù)中心具有：容器化、智能化、高效化、透明化，能夠按需服務(wù)和計量付費的特點。

1 問題描述

伴隨著云計算的廣泛應(yīng)用，現(xiàn)有云數(shù)據(jù)中心由于云資源種類繁多，不可避免地會產(chǎn)生大量各種類型的碎片資源（計算，存儲，帶寬等），進而浪費大量資源。因此，從云數(shù)據(jù)中心的角度來看，希望充分利用碎片資源和充分利用可用的云資源。近年來，云數(shù)據(jù)中心資源調(diào)度方面進行了大量的研究工作。并取得了顯著的成果，但目前的高效調(diào)度技術(shù)還存在一些問題和研究缺陷：①我們沒有充分考慮計算，存儲，帶寬資源等云資源的多樣性。②云數(shù)據(jù)中心用戶所獲得的服務(wù)質(zhì)量（諸如:云服務(wù)用戶的需求響應(yīng)時間和對獲得服務(wù)結(jié)果的滿意程度）尚未得到有效保證。③云數(shù)據(jù)中心提供的各類資源性服務(wù)的資源利用率較低。④三種類型的碎片資源（計算，存儲和帶寬）未有效利用。

為充分利用多種碎片資源，提高多類型云資源利用率。本文提出了一種融合了兩種智能優(yōu)化算法（遺傳算法和蟻群算法）多維云資源高效調(diào)度方法模型。

2 遺傳與蟻群結(jié)合算法

作為仿生智能算法的遺傳算法和蟻群算法，具有搜索能力強、并行性的特點，應(yīng)用到云資源調(diào)度模型中，用于提高云資源的調(diào)度效率。在實際的應(yīng)用中單一的算法容易陷入局部最優(yōu)解、收斂速度慢等問題，因此需要對算法進行改進。改進后的遺傳蟻群（GA-ACO）算法將遺傳算法全局搜索性能強和蟻群算法局部搜索性能強的優(yōu)勢相結(jié)合，克服遺傳算法局部搜索能力弱和蟻群算法全局搜索能力弱的不足?；旌喜⑿羞z傳蟻群算法利用遺傳算法的魯棒性，隨機性和全局收斂性的特點，生成初始信息素分布來解決該問題。通過選擇，交叉和變異操作，生成一組新的個體，然后利用蟻群算法，利用群并行性，正反饋，高效率等特點，解決多維云資源高效調(diào)度問題以提高效率。顯著提高了算法的運行效率和解決方案質(zhì)量，提高了算法的有效性。

并行遺傳和蟻群算法：

2.1 編碼

根據(jù)云數(shù)據(jù)中心的資源配置特點，采用整數(shù)編碼。此編碼方式操作意義直觀，將并行GA-ACO算法直接應(yīng)用到編碼個體上，這樣編碼與解空間不用進行轉(zhuǎn)換，在算法的運行效率得到提高，算法的時間和空間復雜度得到改進。

2.2 種群初始化

并行GA-ACO算法中，種群初始化采用隨機深度優(yōu)先搜索算法，從起始源點開始隨機選擇下一個資源節(jié)點，依次繼續(xù)選擇資源節(jié)點。在GA-ACO算法的鏈接時設(shè)置迭代范圍Gmin≤Gite≤Gmax作為判斷條件，進行判斷選擇，最終搜索遍歷獲得符合條件的信息節(jié)點。

2.3 適應(yīng)度函數(shù)

遺傳過程個體的適應(yīng)度準則通過遺傳的適應(yīng)度函數(shù)約束，并行GA-ACO算法中信息個體是資源虛擬機到處理器的映射關(guān)系，該映射關(guān)系的合理性和適應(yīng)度，主要表現(xiàn)在數(shù)據(jù)中心物理資源和帶寬資源利用率和任務(wù)響應(yīng)時間。整體資源利用率高，任務(wù)響應(yīng)時間短，映射關(guān)系具有合理適應(yīng)性。

2.4 選擇操作

選擇操作就是為了選擇出種群中的優(yōu)秀個體進入下一代。每代中個體按照適應(yīng)度值來判斷決定它能夠復制到下一代的概率，以繁殖出更接近目標的新個體。通過選擇操作，種群中優(yōu)秀人員的數(shù)量不斷聚集，演化過程繼續(xù)朝著最佳解決方案前進。

2.5 交叉操作

交叉操作使用固定的交叉概率，即根據(jù)適應(yīng)度函數(shù)的優(yōu)劣從現(xiàn)代種群中排序。依次選取相鄰的兩個個體，根據(jù)交叉準則以固定單位概率交叉生成兩個新個體。這個過程結(jié)束，直到下一代個體交叉操作與初始種群個體數(shù)量一致。交叉規(guī)則如下：①兩個父代個體中的一些基因交換形成兩個新個體；②一個子個體中的一些染色體被交換以形成新的個體。

2.6 變異操作

變異操作是在交叉操作形成的新一代子個體，以變異操作概率0.05為基礎(chǔ)進行變異操作。這種變異操作遵循：在新一代子個體的一些染色體的整數(shù)編碼中根據(jù)概率隨機選取一個或多個比特；選取的編碼位在新生成的子個體中超出范圍，進行刪除操作。再次變異初始生成的新個體，進行重復操作。

2.7 信息素設(shè)置

各節(jié)點的最小值選取信息素的初始值，用于模擬螞蟻的分泌物的信息素值選取遺傳算法求解結(jié)果。同時，在螞蟻行進路徑上的路徑選擇，參照各條路徑上信息素值的大小。用概率Pijk（t）表示時間點t螞蟻i由j節(jié)點選擇k節(jié)點[1]，則：

隨著路徑選擇得進行，信息素將逐漸消逝。因此，信息素更新方程為：

同時，τjk（t+1）為+1 時刻節(jié)點的信息素，τjk（t）是 t時刻節(jié)點的信息素[2]。

2.8 結(jié)束條件

并行GA-ACO算法終止條件為：

云數(shù)據(jù)中心和各子系統(tǒng)所占資源在上式中表示為和，并行GA-ACO算法的流程圖如圖1所示。

3 實驗與分析

為了驗證算法模型在云數(shù)據(jù)中心計算資源調(diào)度的可行性及有效性，采用CloudSim實驗平臺模擬云計算環(huán)境進行驗證。將基于整數(shù)Markov理論的并行GA-ACO算法與貪婪算法 (Greedy Algorithm,GDA)在云數(shù)據(jù)中心資源調(diào)度性能從任務(wù)響應(yīng)時間和計算、存儲、帶寬資源利用率幾個方面進行比較。[3]設(shè)置的虛擬機特性和實驗環(huán)境如下，100到1500臺虛擬機，任務(wù)到達時間為10到100的隨機分布區(qū)間,同時考慮計算、存儲和帶寬等類型資源且資源量100到3000之間。在實驗進程中，動態(tài)生成的虛擬機節(jié)點數(shù)在100到1500之間，同時，計算資源、存儲資源和帶寬資源是生成虛擬機對它們的資源依賴權(quán)重。[4]

圖1 并行GA-ACO算法的流程

圖2 GA-ACO計算、存數(shù)和帶寬資源利用率

GA-ACO計算、存數(shù)和帶寬資源利用率表

在圖2中，水平坐標表示VM數(shù)量,垂直坐標表示并行GA-ACO算法的計算、存儲、帶寬資源的利用率。實驗結(jié)果表顯示三種資源利用率均有明顯提升，并且實驗結(jié)果顯示資源利用率曲線在經(jīng)歷過逐步加速上升后逐漸趨于平穩(wěn)，表明并行遺傳與蟻群結(jié)合算法對提升云數(shù)據(jù)中心的資源利用率具有明顯穩(wěn)定的效果。

4 結(jié)束語

筆者提出了一種融合遺傳與蟻群算法的資源調(diào)度方案，該方案充分考慮了云數(shù)據(jù)中心的多維資源和資源調(diào)度產(chǎn)生的大量碎片，通過實驗驗證了方案在云數(shù)據(jù)中心資源高效調(diào)度的有效性。