◎姜賽達(dá)

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

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

1 問(wèn)題描述

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

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

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

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

并行遺傳和蟻群算法：

2.1 編碼

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

2.2 種群初始化

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

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

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

2.4 選擇操作

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

2.5 交叉操作

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

2.6 變異操作

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

2.7 信息素設(shè)置

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

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

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

2.8 結(jié)束條件

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

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

3 實(shí)驗(yàn)與分析

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

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

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

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

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

4 結(jié)束語(yǔ)

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