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

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

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9599 （2012） 23-0000-02

1 引言

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

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

2 算法的改進(jìn)

2.1 染色體編碼的改進(jìn)

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

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

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

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

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

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

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

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

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

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

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

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

2.4 遺傳算法與蟻群算法融合點(diǎn)的改進(jìn)

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

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

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

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

2.5 蟻群算法的改進(jìn)

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

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

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

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

Pij=

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

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

3 算法仿真結(jié)果

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

4 小結(jié)

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

參考文獻(xiàn)：

[1]劉鵬.云計(jì)算的定義和特點(diǎn)[J].中國云計(jì)算.

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

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

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

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

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

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

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

[9]華夏渝，鄭駿，胡文心.基于云計(jì)算環(huán)境的蟻群優(yōu)化計(jì)算資源分配算法.華東師范大學(xué)學(xué)報(bào)，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.