云平臺(tái)中多任務(wù)分配集成蟻群優(yōu)化算法

姚光偉

（韓山師范學(xué)院 潮州師范分院，廣東 潮州 521000）

0 引 言

云計(jì)算是當(dāng)今這個(gè)信息爆炸時(shí)代的研究熱點(diǎn)，無論是傳統(tǒng)企業(yè)，還是互聯(lián)網(wǎng)企業(yè)都越來越重視對(duì)各種相關(guān)的數(shù)據(jù)進(jìn)行分析和利用，如何對(duì)海量數(shù)據(jù)處理已成為互聯(lián)網(wǎng)企業(yè)的核心競(jìng)爭(zhēng)力之一。云計(jì)算的開源實(shí)現(xiàn)及其高容錯(cuò)、跨平臺(tái)等眾多優(yōu)勢(shì)，使之迅速得到眾多企業(yè)的青睞，它利用分布式計(jì)算和虛擬資源管理等技術(shù)，將分散的ICT資源集中起來形成共享的資源池，改變傳統(tǒng)用戶必須購(gòu)買昂貴的軟硬件設(shè)備，只需向相應(yīng)的服務(wù)提供商支付少量的租賃費(fèi)用即可使用整個(gè)資源池的資源，從而有效地實(shí)現(xiàn)對(duì)互聯(lián)網(wǎng)上資源設(shè)施等實(shí)時(shí)、按需、快捷地訪問共享的計(jì)算模式。但是，這也預(yù)示著云計(jì)算的規(guī)模會(huì)非常龐大。因此，為云計(jì)算環(huán)境找到一個(gè)合理的任務(wù)分配方法已經(jīng)迫在眉睫。

1 蟻群優(yōu)化算法

蟻群算法是模擬自然界螞蟻搜索行為的一種啟發(fā)式仿生進(jìn)化算法［1－2］。在求解復(fù)雜優(yōu)化問題方面有一定優(yōu)勢(shì)，特別是在一些離散優(yōu)化問題上具有良好優(yōu)勢(shì)。目前，基本蟻群算法都具有收斂速度快，且易陷入局部最優(yōu)解等眾多不足。同理，在云平臺(tái)的資源服務(wù)中，在同一時(shí)刻越多的用戶訪問同一條服務(wù)路徑上的資源和數(shù)據(jù)，就越容易造成相應(yīng)的該網(wǎng)段網(wǎng)絡(luò)負(fù)荷過重；倘若該最優(yōu)路徑上用戶數(shù)量超出網(wǎng)絡(luò)的承受能力，則極可能導(dǎo)致局部網(wǎng)絡(luò)擁塞，嚴(yán)重則導(dǎo)致整個(gè)網(wǎng)絡(luò)癱瘓，使廠商利益嚴(yán)重受損，乃至出現(xiàn)虧損等情況［3］。

為了改進(jìn)蟻群算法使其性能更優(yōu)，許多學(xué)者已經(jīng)開始從各種層面或不同的策略蟻群算法提出了改進(jìn)；如文獻(xiàn)［4］中提出云模型蟻群算法（Cloud Ant Colony Algorithm，CACA），文獻(xiàn)［5］提出混合蟻群算法（Hybrid Ant Colony Algorithm，HACA），文獻(xiàn)［6］提出兩步蟻群算法，文獻(xiàn)［7］提出超管道蟻群算法，文獻(xiàn)［8］提出廣義蟻群算法，文獻(xiàn)［9］提出啟發(fā)式基于密度的蟻群算法，文獻(xiàn)［10］提出倍城市當(dāng)前城市號(hào)蟻群算法，文獻(xiàn)［11］提出將蟻群算法與變異策略結(jié)合，文獻(xiàn)［12］提出多態(tài)蟻群算法，文獻(xiàn)［13］提出了用于連續(xù)域?qū)?yōu)的分組蟻群算法。然而這些算法在網(wǎng)絡(luò)搜索中都容易陷入局部最優(yōu)解，而且收斂速度和尋優(yōu)精度等都有待進(jìn)一步提高。

因此，如何充分利用云平臺(tái)中實(shí)現(xiàn)云端多任務(wù)分配調(diào)度，是云計(jì)算領(lǐng)域的一個(gè)研究重點(diǎn)和難點(diǎn)。文中提出一種針對(duì)云計(jì)算資源中大量任務(wù)進(jìn)行高效的調(diào)度研究。該算法在原有ANT算法基礎(chǔ)上加以優(yōu)化模擬，并通過數(shù)學(xué)模型運(yùn)用于云計(jì)算平臺(tái)中，最后通過仿真實(shí)驗(yàn)驗(yàn)證，使之能夠在云計(jì)算資源高效、快捷地找到所需訪問的服務(wù)節(jié)點(diǎn)，可有效解決ANT在網(wǎng)絡(luò)搜索中出現(xiàn)停滯現(xiàn)象，大大提高了資源調(diào)度的效率。

2 基于蟻群優(yōu)化算法的云端多任務(wù)調(diào)度

由于整個(gè)云計(jì)算的體系結(jié)構(gòu)及其資源分布的實(shí)際情況都處于沒有明確的機(jī)制中，任何一條線路上的網(wǎng)絡(luò)負(fù)荷情況在不同的時(shí)刻都存在眾多不可預(yù)期的動(dòng)蕩變幻中。部分算法單從調(diào)度性能方面進(jìn)行了優(yōu)化改進(jìn)，但這并未充分考慮到網(wǎng)絡(luò)負(fù)載也存在眾多不可預(yù)期的大幅度變幻，這種從單方面角度去做優(yōu)化改進(jìn)，不僅不能高效地滿足云資源調(diào)度的要求，且不利于云計(jì)算尋求資源共享和資源的最大利用率，尤其是優(yōu)勢(shì)資源的目標(biāo)；同時(shí)，每個(gè)節(jié)點(diǎn)的軟硬件環(huán)境、結(jié)構(gòu)、吞吐量及容量等性能也都不同，使得各個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)和鏈路的負(fù)載動(dòng)蕩不均衡，這不僅造成資源浪費(fèi)和成本增加，同時(shí)使服務(wù)的質(zhì)量大打折扣。

云計(jì)算中資源異構(gòu)且動(dòng)態(tài)變化，在調(diào)度時(shí)隨時(shí)可能有新的云資源加入，也隨時(shí)有云資源故障或掉線，這種不確定性給云資源調(diào)度帶來了很大困難，而蟻群算法中螞蟻對(duì)路徑的選擇本身也存在諸多不確定因素，對(duì)此提出使用熵對(duì)云資源的不確定因素進(jìn)行度量，提高算法收斂速度，利用信息素?cái)U(kuò)散原理更新信息素增加算法解的性能。

文中從物理學(xué)范疇中引入一個(gè)度量不確定方法的概念——信息熵，它是系統(tǒng)不確定性的有效度量，其定義如下：

式中：P——信號(hào)源每個(gè)狀態(tài)發(fā)生的概率值；

k——熱 力 學(xué) 常 量 玻 爾 曼 常 數(shù)，k＝1.380 650 5×10－23J／K。

當(dāng)所有螞蟻釋放信息素后，通過式（1）計(jì)算系統(tǒng)的信息熵H（t）：

式中：ρ（t）——隨時(shí)間t而改變；

n——資源j的內(nèi)存總和。

根據(jù)式（2）將螞蟻個(gè)體在一個(gè)搜索周期后更新系統(tǒng)信息熵，通過式（3）調(diào)節(jié)揮發(fā)因子。

這樣伴隨著系統(tǒng)信息熵調(diào)節(jié)揮發(fā)因子變化，使該算法能夠通過揮發(fā)因子的變化自適應(yīng)收斂調(diào)節(jié)，可有效避免螞蟻在網(wǎng)絡(luò)搜索中陷入局部最優(yōu)解，從而提高算法效率。

2.1 算法描述

設(shè)云計(jì)算環(huán)境下t刻節(jié)點(diǎn)域slave表示為G＝（V，E），V為所有云節(jié)點(diǎn)，m和E 分別代表搜索螞蟻數(shù)目和所有鏈路集合。τsm（t）為t時(shí)刻路徑（s，m）上的信息素，ρ表示信息素?fù)]發(fā)系數(shù)，（1－ρ）表示信息素殘留因子［14］。

s［s］［m］（s，m＝0，1，2，…，m－1；i≠j）的計(jì)算如下：

dsm——以節(jié)點(diǎn)i為中心，到其它m－1個(gè)節(jié)點(diǎn)的最大距離。

據(jù)此結(jié)果，首先置初始時(shí)刻各條路徑（s節(jié)點(diǎn)到m節(jié)點(diǎn)）上的信息量如下：

式中：Csm——節(jié)點(diǎn)sm路徑上信息素的濃度初始值；

E——節(jié)點(diǎn)的個(gè)數(shù)；

S——CPU的速度。

針對(duì)搜索蟻群的做法是：螞蟻k（k＝1，2，…，n）在t時(shí)刻搜尋路徑，從其中節(jié)點(diǎn)s出發(fā)，以一定的概率搜尋下一節(jié)點(diǎn)，螞蟻k從節(jié)點(diǎn)s移動(dòng)到節(jié)點(diǎn)m的概率的計(jì)算公式如下：

式中：η——權(quán)重因子，兩個(gè)城市之間的距離越遠(yuǎn)，則權(quán)重值越小，ηsm＝1／dsm；

tabuk——未被訪問的節(jié)點(diǎn)集合，也就是禁忌表。

經(jīng)過一次循環(huán)以后，更新每條通路上的信息素余量，對(duì)每條通路給出信息素反饋質(zhì)量。該反饋質(zhì)量將作為以后循環(huán)的判斷依據(jù)，為螞蟻選擇通路提供信息。信息素的更新如下：

蟻群算法首先進(jìn)行參數(shù)的初始化，隨機(jī)選擇一條路徑并更新禁忌表。在第一次循環(huán)過后，更新信息素余量，然后根據(jù)式（4）計(jì)算得到的轉(zhuǎn)移概率重新進(jìn)行循環(huán)迭代，直到達(dá)到最大迭代次數(shù)或滿足終止條件為止。

2.2 算法分析

蟻群之間通過所搜路徑上的濃度變化進(jìn)行互相協(xié)作和信息交換，以便迅速搜索到一條覓食的較短路徑。但隨著時(shí)間推移及迭代次數(shù)逐漸遞增，后續(xù)的ANT所搜尋的路徑逐漸趨于同一化，從而陷入云數(shù)據(jù)庫中局部無休止搜尋中。而RACO算法充分兼顧了各個(gè)物理節(jié)點(diǎn)的時(shí)延、能量消耗等影響，并將這些負(fù)面因素作為判斷條件因素；算法在開始時(shí)被初始化并保持原算法的搜索方式，隨著算法的運(yùn)行被更新，當(dāng)各搜索的網(wǎng)絡(luò)節(jié)點(diǎn)上的信息素濃度出現(xiàn)較為明顯的變化時(shí)，便開始發(fā)揮云資源的節(jié)點(diǎn)上參數(shù)的有效性。

即每一次具體的分配與之前螞蟻留在這次分配上的信息素相關(guān)。這樣便可更好地消除原算法中螞蟻個(gè)體在搜尋路徑過程中“短視”的不足。使任務(wù)完成時(shí)間最短，減少資源消耗，提高云計(jì)算的效率和性能。

同時(shí)，RACO算法可利用μsm因子來自適應(yīng)收斂調(diào)節(jié)螞蟻搜索路徑中信息素的濃度，可有效杜絕隨機(jī)搜索陷入局部最優(yōu)解難題。因?yàn)榧词刮锢砉?jié)點(diǎn)上ANT搜尋路徑是最優(yōu)解，則局部的節(jié)點(diǎn)更新仍能夠適當(dāng)?shù)卣{(diào)節(jié)該路徑上的信息素濃度，有效避免了后續(xù)的ANT所搜尋的路徑逐漸趨于同一化，以適當(dāng)抑制正反饋對(duì)全局搜尋具有積極的效用，從而實(shí)現(xiàn)名副其實(shí)的網(wǎng)絡(luò)各物理節(jié)點(diǎn)的負(fù)載均衡自適應(yīng)。

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

為了驗(yàn)證上述蟻群優(yōu)化算法在云計(jì)算任務(wù)分配上的可行性及較好的穩(wěn)定性，文中通過模擬構(gòu)建云計(jì)算的局部仿真環(huán)境來測(cè)試算法的效率。

由于在云計(jì)算資源中存在眾多不可預(yù)測(cè)的具體情況，且網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)時(shí)常變化不一，所以選擇一個(gè)既有較短的時(shí)間跨度，保證任務(wù)能夠被盡可能快地完成，又具有良好的負(fù)載平衡能力的云計(jì)算平臺(tái)至關(guān)重要；這里主要驗(yàn)證改進(jìn)后的蟻群算法能夠高效地在云計(jì)算環(huán)境中完成計(jì)算資源搜索與分配的工作，并能夠優(yōu)化搜索性能，減少搜索時(shí)間，降低網(wǎng)絡(luò)負(fù)載［14］。因此，實(shí)驗(yàn)是一個(gè)模擬云計(jì)算的局部域：實(shí)驗(yàn)設(shè)備為一般的IBM服務(wù)器及普通PC機(jī)、集中存儲(chǔ)的磁盤陣列、SAN交換網(wǎng)絡(luò)統(tǒng)一組成一個(gè)資源池，提供硬件平臺(tái)資源，仿真軟件為Matla7.8。

通過云計(jì)算仿真軟件Matla7.8采用離散事件模擬了云計(jì)算實(shí)驗(yàn)環(huán)境，驗(yàn)證原始蟻群算法與改進(jìn)后的蟻群算法在云環(huán)境中的運(yùn)行情況。通過Matla7.8中的DataCenter和一系列的輔助類，模擬了云計(jì)算的計(jì)算和網(wǎng)絡(luò)資源，以構(gòu)建云計(jì)算局部環(huán)境。實(shí)驗(yàn)數(shù)據(jù)為實(shí)驗(yàn)室的模擬數(shù)據(jù)，首先隨機(jī)獲取1 000個(gè)個(gè)體物理資源，并對(duì)它們進(jìn)行虛擬化，開始時(shí)集中存儲(chǔ)在主服務(wù)器上，這樣保證了云平臺(tái)下的虛擬任務(wù)的多樣性及物理資源的復(fù)雜性。由于本實(shí)驗(yàn)中的數(shù)據(jù)存儲(chǔ)和傳輸?shù)某杀鞠鄬?duì)于CPU的計(jì)算成本而言基本可以忽略不計(jì)，因此，忽視了這部分的影響。隨著時(shí)間的推移及不同數(shù)據(jù)量的逐漸增加，分別取其平均值作為算法的最終結(jié)果，該兩種算法的延遲性及查詢響應(yīng)時(shí)間見表1。

表1 兩種算法達(dá)到最優(yōu)解的迭代次數(shù)及最優(yōu)解對(duì)比

由表1的實(shí)驗(yàn)數(shù)據(jù)可以看出，改進(jìn)算法無論在最優(yōu)解的精確度還是收斂到最優(yōu)解的速度都比原算法有很大提高，原因在于原有蟻群算法隨著迭代次數(shù)逐漸增加，搜索的路徑逐漸趨近于同一化，從而陷入局部最優(yōu)而抑制了全局搜索能力，導(dǎo)致局部網(wǎng)絡(luò)負(fù)荷過重，以致影響調(diào)度效果。而改進(jìn)算法在局部更新時(shí)，不僅考慮到螞蟻所走過的路徑上的信息素，也考慮到其對(duì)周圍路徑信息素濃度的影響，從而兼顧到整體的網(wǎng)絡(luò)負(fù)載均衡，所以，隨著任務(wù)數(shù)和資源數(shù)增多，其優(yōu)勢(shì)更為明顯，越能體現(xiàn)其最優(yōu)解的性能。

4 結(jié) 語

云計(jì)算環(huán)境中如何實(shí)現(xiàn)將海量計(jì)算資源組成的IT資源池動(dòng)態(tài)、實(shí)時(shí)、按需、合理的分配使用資源是一個(gè)非常關(guān)鍵的問題。因此，尋求一個(gè)好的資源調(diào)度算法至關(guān)重要。文中將改進(jìn)蟻群算法（RACO）和云模型技術(shù)結(jié)合起來，進(jìn)行了有力的探討，均衡系統(tǒng)中各計(jì)算節(jié)點(diǎn)的負(fù)載，依據(jù)節(jié)點(diǎn)的處理能力和鏈路帶寬狀況進(jìn)行不同數(shù)據(jù)量的分布，并結(jié)合網(wǎng)絡(luò)帶寬來確定任務(wù)調(diào)度最優(yōu)策略，最終達(dá)到降低系統(tǒng)響應(yīng)時(shí)間，提高了系統(tǒng)的整體性能與資源利用效率。實(shí)驗(yàn)表明，改進(jìn)后的RACO可有效地運(yùn)用在云平臺(tái)上，很好地完成計(jì)算資源分配、搜尋等工作，消除搜索“短視”，均衡網(wǎng)絡(luò)負(fù)載，迅速搜尋至最優(yōu)解，對(duì)海量網(wǎng)絡(luò)信息提取具有高效性和適應(yīng)性。

［1］Dorigo M，Stutzle T.Ant colony optimization［M］.Cambrige，UK：MIT Press，2009.

［2］史恒亮，唐振民，劉傳領(lǐng)，等.基于蟻群優(yōu)化算法的云數(shù)據(jù)庫動(dòng)態(tài)路徑規(guī)劃［J］.計(jì)算機(jī)科學(xué)，2010，37（5）：143－147.

［3］陳真.改進(jìn)蟻群算法在云計(jì)算環(huán)境路徑優(yōu)化設(shè)計(jì)［J］.江西理工大學(xué)學(xué)報(bào)，2012，33（3）：66－70.

［4］段海濱，于道波，于秀芬.基于云模型理論的蟻群算法改進(jìn)研究［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2005，37（11）：115－119.

［5］Blum C，Valles M Y，Blesa M J.An ant colony optimization algorithm for DNA sequencing by hybrid－ization［J］.Computers ＆ Operations Research，2008，35（11）：3620－3625.

［6］Wang H S.A two－phase ant colony algorithm for multi－echelon defective supply chain network design［J］.European Journal of Operational Research，2009，192（1）：243－252.

［7］Carpaneto E，Chicco G.Distribution system minimum loss reeonfiguration in the hypercube ant colony optimization framework［J］.Electric Power Systems Research，2008，78（12）：2037－2045.

［8］Hou Y H，Wu Y W，Lu L J，et al.Generalized ant colony optimization for economic dispatch of power system［C］／／Proceedings of the 2002International Conference on Power System Technology.Washington，DC：IEEE Computer Society，2002，1：225－229.

［9］Cheny F，Liuy S，F(xiàn)AqTAH C A，et al.HDACC：A heuristic density based ant colony clustering algorithm［C］／／Proceedings of the IEEE／W IC／ACM International Conference on Intelligent Agent Technology.Washington，DC：IEEE Computer Society，2004：397－400.

［10］Nalmi H M，Taherinejad N.New robust and efficient ant colony algorithms：Using new interpretation of local updating process［J］.Expert Systems with Applications，2009，36（1）：481－488.

［11］Yang J H，Shi X H，Marchese M，et al.An ant colony optimization method for generalized TSP problem［J］.Progress in Natural Science，2008，18（11）：1417－1422.

［12］徐精明，曹先彬，王煦法.多態(tài)蟻群算法［J］.中國(guó)科學(xué)技術(shù)大學(xué)學(xué)報(bào)，2005，35（1）：59－65.

［13］李秋云，朱慶保，馬衛(wèi).用于連續(xù)域?qū)?yōu)的分組蟻群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46（30）：46－49.

［14］陳真.基于蟻群優(yōu)化算法的云計(jì)算資源分配［J］.青島科技大學(xué)學(xué)報(bào)，2012，33（6）：619－624.