云環(huán)境下對遺傳蟻群算法的改進研究

摘要：本文對于常見的遺傳蟻群算法，根據(jù)云計算環(huán)境，提出了智能化的編碼方案，過濾掉冗余編碼，并把最短完成時限寫進適應(yīng)函數(shù)，在算法初始階段過濾掉不符合時間要求的調(diào)度方案，并在蟻群算法中進行了雙重收斂加速，并考慮到了負載均衡。實驗證明，本算法取得了較好的效果。

關(guān)鍵詞：云計算；改進型遺傳蟻群算法；智能編碼；雙重收斂加速

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1007-9599 （2012） 23-0000-02

1 引言

云計算是一種以“租賃服務(wù)”為目標的商業(yè)實現(xiàn)。它的理念來自于用戶經(jīng)常發(fā)現(xiàn)他們需要的是某種服務(wù)，而不是通常購買的軟件，平臺或者服務(wù)器。如果用戶不需要購買，只需要租賃這些資源，那該是一件多么美好的事情。普遍來講，云計算就是通過互聯(lián)網(wǎng)將數(shù)據(jù)中心的各種資源打包成服務(wù)向外提供。

而目前云計算的任務(wù)調(diào)度（任務(wù)資源映射）沒有通用的算法。常用的啟發(fā)式任務(wù)調(diào)度算法系統(tǒng)開銷大，且沒有考慮到用戶的要求，負載均衡方面也不理想。所以人們提出了一種遺傳蟻群融合算法，即保留了遺傳算法前期搜索速度快的優(yōu)點，也保證了蟻群算法搜索后期高效的優(yōu)勢，但存在著編碼不夠合理，適應(yīng)函數(shù)不夠規(guī)范，融合點的定位不夠動態(tài)，蟻群算法收斂加速不夠等缺點。本文在一種常用的遺傳螞蟻算法基礎(chǔ)上（參考文獻[8]）進行改進，試圖使其調(diào)度性能更加理想。

2 算法的改進

2.1 染色體編碼的改進

文獻[8]提出了這樣一種編碼方案，采用十進制實數(shù)編碼，每個染色體代表一種調(diào)度方案。假設(shè)有i個任務(wù)j個資源，則染色體長度i+j。資源與任務(wù)映射規(guī)則如下：調(diào)度任務(wù)到最鄰近的右端資源。比如當前有5個任務(wù)3個計算節(jié)點，則數(shù)字1到5表示任務(wù)，6到8表示資源。編碼12734856表示任務(wù)1，2分配給7；3和4分配給8；5給6.解碼規(guī)則為逆運算。

然而由于12734856實際上和21743856是一樣的，這種編碼會帶來極大的資源浪費。對此假如有5個任務(wù)，我們先對任務(wù)隊列排序，優(yōu)先級較大的或較小的任務(wù)靠前，編碼為1到5，這樣出現(xiàn)了7個位置，先對位置7隨機一個資源，這樣可以保證任務(wù)得到完全調(diào)度（在本例中即保證染色體必需由678的一個結(jié)尾），再對另外兩個資源節(jié)點隨機分配1到6的位置，并不許重復(fù)（不允許12673458這樣的染色體出現(xiàn)，雖然它也有可能表示一定意義，比如67123458表示67節(jié)點可能負載比較重而不分配新到任務(wù)。在本步驟忽略這種情況，負載均衡由蟻群算法控制。）。比如資源6隨機到的位置是3，7對應(yīng)4，8對應(yīng)7，則生成字符串應(yīng)為12637458。

2.2 適應(yīng)函數(shù)的改進

由于我們在初代染色體的生成上采用了較小任務(wù)優(yōu)先調(diào)度的思想以期總時間較短的思想，這就很可能造成每個資源節(jié)點上任務(wù)完成總時間較好但一個用戶的各個子任務(wù)的平均完成時間不佳。為了解決這個問題，適應(yīng)函數(shù)設(shè)計如下。

其中costi表示i個有最短完成時限的任務(wù)，deadline（i）表示這個任務(wù)的最短完成時限。如果有最短時限要求的任務(wù)未能按時完成，則適應(yīng)度置0，；其他的按平均完成時間設(shè)置適應(yīng)度。當都完成最短時限時，我們根據(jù)用戶的完成時間期望（或者付費額度或者任務(wù)優(yōu)先級）設(shè)置加權(quán)參數(shù)M和N，分別核算用戶TASK1和TASK2的加權(quán)完成時間再計算平均值。

比如說有12634758染色體，其中135屬于用戶1的子任務(wù)，24屬于用戶2，用戶1時間期望比用戶2高，或者他付費更多，那么我們就分別計算用戶1的135子任務(wù)分別調(diào)度到678的時間之和再乘以系數(shù)m，24調(diào)度給67的時間之和再乘以系數(shù)n，得到的和再除以任務(wù)數(shù)。在本文中，為簡化實驗只設(shè)定兩個用戶，且m=1.2，n=0.9。

這話改進方式不僅僅以完成時間以最重要的適應(yīng)度度量，而且考慮到了任務(wù)的時間期待或者優(yōu)先級，更符合云環(huán)境商業(yè)應(yīng)用的特點。

2.3 此種編碼方式下遺傳算子設(shè)計

（1）根據(jù)適應(yīng)函數(shù)值大小排序，從隊列中選出按百分比P值，選擇P/2（P值自定）個染色體，再另隨機選出P/2個染色體選擇準備進行交叉；

（2）交叉操作采用Davis順序交叉方法；如P1=126|374|58和P2=162|348|57，保留割點間的片段得到N1=XXX|374|XX和N2=XXX|348|XX，為得到后代N1，將P2中去除374得到16285，依次插入P1得到P1=16237485.這樣做的好處是既保證了交叉的有效性，又保證了我們?nèi)蝿?wù)排序的約束。由于我們在編碼時設(shè)定了兩點約束，即資源節(jié)點不允許相鄰，且必須以資源節(jié)點結(jié)束，所以我們需要定義修補算子。

修補算子定義如下：如果存在資源節(jié)點相鄰，則相鄰的后一個節(jié)點向右交換直至符合規(guī)定；如果不以資源節(jié)點結(jié)束，則自右向左尋找最近的資源與最后一位交換。如在本例中最終得到的P1=16237458。

（3）變異算子在本文中簡化為修補算子，因為此種編碼方案不能進行常規(guī)變異。交叉操作后適應(yīng)函數(shù)有改進的保留，無改進或有未按最短時限完成的任務(wù)則丟棄。

2.4 遺傳算法與蟻群算法融合點的改進

如上圖所示，為最大限度的利用遺傳算法的搜索初期速度快，蟻群算法后期效率高的特點，融合應(yīng)在tb和td之間最合適（tc最佳）。但常見的融合點設(shè)計無論是遺傳固定的代數(shù)，還是當遺傳進化率低于固定值時結(jié)束，都不能正確的定位tb與td區(qū)間。本文提出一種新的思路：

（1）如果遺傳迭代次數(shù)大于最小迭代次數(shù)，連續(xù)N代遺傳進化率都在下降，且連續(xù)M代本代最優(yōu)解適應(yīng)值小于當前最優(yōu)解適應(yīng)值，則視為遺傳算法可結(jié)束。

（2）如果遺傳迭代次數(shù)達到最大迭代次數(shù)，則結(jié)束遺傳算法。

這種思路基于這樣一種想法——如果我們設(shè)置一定連續(xù)代遺傳進化率小于固定值作為遺傳算法的結(jié)束條件（或超出最大代），那么我們尋找到的時間點通常在td之后。如果不能準確定位tc點，那么在tb之后，且沒有更優(yōu)解的情況下，盡早進入螞蟻算法可以使算法更加的簡潔高效。

2.5 蟻群算法的改進

2.5.1 在初始化信息素后，即根據(jù)一定量的最優(yōu)染色體進行初始信息素增加。

進入蟻群算法后更新方程重寫如下：τjnew= τjold+lj c ηj

其中l(wèi)j表示當前資源節(jié)點的任務(wù)負載率，為已完成任務(wù)和負載總量，負載率低的增加信息素多一點。ηj為評估當前資源節(jié)點QoS質(zhì)量的參數(shù)，如帶寬，CPU占用率等，QoS狀態(tài)好的節(jié)點增加信息素多一點。c為調(diào)整參數(shù)。這樣設(shè)計更新方程既考慮了負載平衡可以使收斂具有一定的方向性，加速收斂。

2.5.2 任務(wù)i和資源j的映射概率改寫為：

Pij=

其中 j為資源j的當前的狀態(tài)，表征CPU利用率，可用內(nèi)存，可用帶寬等。 和 為調(diào)整參數(shù)。需要注意的是因為我們在更新方程中已經(jīng)根據(jù)資源狀態(tài)（當時包含了負載率）控制了信息素分布，所以現(xiàn)在的 值應(yīng)較常規(guī)螞蟻算法比較小。收斂加速的雙重控制可以更精確的加速收斂，通過不斷調(diào)整參數(shù)達到理想的收斂速度。

2.5.3 為了避免蟻群算法后期常常陷入局部最優(yōu)解，如果在最大迭代代數(shù)的3/4代之前連續(xù)N代收斂于同一解，則降低該解所分布資源的信息素為之前的R倍。本文選擇R為0.4。

3 算法仿真結(jié)果

上述結(jié)果表明在所搜索節(jié)點比率減小或規(guī)模擴大時，本算法優(yōu)勢明顯。

4 小結(jié)

本文根據(jù)云環(huán)境的特點，對常用的遺傳蟻群融合算法進行改良，提出了比較智能的編碼方案；并提出了獨特的融合算法；更加動態(tài)的定位融合點；根據(jù)資源的狀態(tài)，在算法進入蟻群算法后提出了雙重約束，更加精確的控制收斂速度又保證了負載均衡。最終試驗證明取得了較好的效果。

參考文獻：

[1]劉鵬.云計算的定義和特點[J].中國云計算.

[2]馬學(xué)彬，溫濤，郭權(quán)，王剛.一種基于遺傳算法的網(wǎng)格任務(wù)調(diào)度算法[J].東北大學(xué)學(xué)報.

[3]高曙，鄭德.一種基于蟻群算法的任務(wù)調(diào)度方法.

[4]陳峻，沈潔，秦玲.蟻群算法進行連續(xù)參數(shù)優(yōu)化的新途徑[J].系統(tǒng)工程理論與實踐，2003.

[5]馬良，蔣馥.多目標旅行售貨員問題的螞蟻算法求解[J].系統(tǒng)工程理論方法應(yīng)用，1999.

[6]房秉毅，張云勇，程瑩.云計算國內(nèi)外發(fā)展現(xiàn)狀分析[J].電信科學(xué)，2010，8A：1-5.

[7]王靜宇，譚躍生，陳振江.基于遺傳蟻群混合算法的網(wǎng)絡(luò)任務(wù)調(diào)度研究[J].計算機與信息技術(shù)，2008，9（3）：53-55.

[8]張雨，李芳，周濤.云計算環(huán)境下予以遺傳蟻群算法的任務(wù)調(diào)度研究.計算機工程與應(yīng)用，2012.9.

[9]華夏渝，鄭駿，胡文心.基于云計算環(huán)境的蟻群優(yōu)化計算資源分配算法.華東師范大學(xué)學(xué)報，2010.01.

[10]Downey and D.Feitelson.1999.The elusive goal of work-load characterization. In Performance Evaluation Review， pages 14-29.

[11]Albert Greenberg.2008. VL2： a scalable and flexible data center network.51-62，SIGCOMM.

[12]A. Land and A. Doig. 1960.An automatic method of solving discrete programming problem ，Econometrica.pp. 497-520.

[13]Germain R C， RANA O F. 2009. The Convergence of Clouds， Grids， and Autonomics [J]. IEEE.Internet Computing，12（6）：9.

[14]Haifeng Yu， Amin Vahdat. 2002. Minimal Replication Cost for Availability， PODC， Monterey，Califormia， USA.

[15]J. Lockwood， N. McKeown， G. Watson， G. Gibb， P. Hartke， J. Naous， R. Raghuraman， and J. Luo.2007. NetFPGA–An Open Platform for Gigabit-rate Network Switching and Routing. In IEEE International Conference on Microelectronic Systems Education.