劉燈明，荊俊峰，劉 凱，房志奇

(華北計算機系統(tǒng)工程研究所，北京 100083)

0 引言

現(xiàn)代社會進入了大數(shù)據(jù)時代，傳統(tǒng)的計算模式存在很多局限性，不能夠滿足這種大數(shù)據(jù)的處理需求，因此“云計算”應(yīng)運而生[1]。云計算中一個十分關(guān)鍵的問題就是負(fù)載均衡，負(fù)載均衡的含義是把任務(wù)平均地分配到云計算系統(tǒng)中的各個資源點上，所以設(shè)計出高效合理的資源分配策略非常重要[2]。目前資源分配策略的相關(guān)研究已經(jīng)取得了不錯的研究成果，例如：譚一鳴等人提出了一種能夠降低系統(tǒng)能耗的資源分配策略，李安南創(chuàng)新性地提出了一種QoS 約束簡化的資源分配策略[3]。在云計算資源分配策略中采用了各種算法，例如：蟻群算法。蟻群算法有很多優(yōu)點，因此經(jīng)常被應(yīng)用到云計算資源分配問題上[4]。然而在實際的項目中會發(fā)現(xiàn)蟻群算法直接應(yīng)用于云計算資源分配問題時效果不好，常常會出現(xiàn)負(fù)載失衡，所以本文針對蟻群算法進行了一系列改進，對蟻群算法進行改進方面的研究是本文的研究重點，改進后進行了實驗，實驗結(jié)果表明：對蟻群算法的改進是有效的。

1 蟻群算法

1.1 蟻群算法的原理

蟻群算法啟發(fā)于螞蟻尋找食物的過程，螞蟻視力很差但卻能夠輕松地找到食物源到蟻穴的最優(yōu)路徑，也就是最短路徑，相關(guān)研究發(fā)現(xiàn)螞蟻會在路徑上釋放信息素來進行通信[5]，某條路徑上的信息素越多，對螞蟻的吸引力就越強，螞蟻會選擇走該條信息素多的路徑。與此同時，會把信息素釋放在該條路徑上，該路徑上的信息素將得到進一步增加，反過來提升了對螞蟻的吸引力，這里面存在一種正反饋過程，隨著這個過程不斷進行，最終的結(jié)果是會收斂得到某條最優(yōu)路徑，于是便確定了蟻穴到食物源的最短路徑[6]。

1.2 蟻群算法的數(shù)學(xué)模型

根據(jù)旅行商問題(Traveling Salesman Problem，TSP)來闡述蟻群算法的數(shù)學(xué)模型，TSP 是假設(shè)有一組城市，經(jīng)過每個城市一次，求最短路徑和，各因子含義如下：dij是i、j 城市間的距離大?。籲 是城市個數(shù)，m 是螞蟻數(shù)量；τij(t)是t 時刻在(i，j)路徑上的信息素含量；bi(t)表示t 時刻位于城市i 的螞蟻數(shù)，于是；tabuk是禁忌表，作用是存放螞蟻目前已經(jīng)經(jīng)過的城市。螞蟻k 在t時刻從城市i 遷移到城市j 的狀態(tài)轉(zhuǎn)移概率為：

其中，C 代表所有城市組成的城市集合，allowedk={C-tabuk}代表螞蟻k 能夠遷移到的城市范圍；ηij(t)代表啟發(fā)因子，表示路徑長短對螞蟻的吸引力，并且ηij(t)=1/dij，dij越小，則ηij(t)越大，于是就越大；α代表信息素啟發(fā)性因子，該因子的含義表示路徑上累積的信息素的權(quán)重大??；β 代表期望啟發(fā)式因子，該因子表示ηij(t)的權(quán)重大小[7]。隨著算法的不斷進行,路徑上積累的信息素會越來越多，會導(dǎo)致啟發(fā)信息被殘留信息淹沒,因此路徑上的信息素需要持續(xù)不斷地?fù)]發(fā)，所以t+n 時刻在路徑(i，j)上的信息素更新公式如下：

其中，ρ 表示信息素?fù)]發(fā)系數(shù)，Δτij(t)表示信息素的增量大小，是螞蟻k 釋放在(i，j)路徑上的信息素含量。蟻群算法有3 種基本的計算模型，分別是Ant-Cycle、Ant-Quantity、Ant-Density，這3 種模型的區(qū)別僅僅是采用了不同的信息素更新方式，即的計算方式不同。這3 種計算方式分別為：

(1)Ant-Cycle 模型

(2)Ant-Quantity 模型

(3)Ant-Density 模型

其中，Q 是信息素濃度大小，Lk是螞蟻經(jīng)過的路徑總長。Ant-Cycle 模型表示螞蟻經(jīng)過全部城市后才更新信息素，是一種信息素全局更新方式；Ant-Quantity 模型以及Ant-Density 模型表示螞蟻每經(jīng)過一個城市就更新信息素，是一種信息素局部更新方式。通常來講，Ant-Cycle模型求解TSP 效果最佳，所以通常都是采用Ant-Cycle模型來解決該類問題[8]。

1.3 蟻群算法流程圖

蟻群算法流程圖如圖1 所示。

圖1 蟻群算法流程圖

2 蟻群算法的改進

蟻群算法比較容易陷入到局部最優(yōu)解，在算法搜索的初始階段，每條路徑上的信息素都比較稀缺，使得算法在剛開始不久進行搜索時速度太慢，嚴(yán)重影響了算法的性能，所以有必要對算法進行一些改進[9]。本文的改進包括兩個方面：(1)對蟻群算法自身進行改進，具體包括：引入偽隨機比例規(guī)則，進行全局信息素強化，引入了交叉變異操作；(2)將遺傳算法和蟻群算法進行融合，形成遺傳蟻群算法。

2.1 引入偽隨機比例規(guī)則

蟻群算法存在一個很嚴(yán)重的問題，就是容易陷入局部最優(yōu)解。為了解決這個問題，必須擴大螞蟻的選擇范圍，使得螞蟻不僅能選擇當(dāng)前最優(yōu)路徑，還能夠以一定的概率選擇其余路徑。因此引入偽隨機比例規(guī)則：

式中，q0代表一個遵循均勻分布的變量。按照信息素含量以及啟發(fā)信息，可以計算出螞蟻最優(yōu)轉(zhuǎn)移方式的可能性大小q0，與此同時，螞蟻能夠以1-q0的概率搜尋其他路徑。為了使得螞蟻能夠選擇究竟是搜尋最優(yōu)路徑，還是搜尋其他地方的路徑，能夠通過設(shè)置q0的值來控制算法對下一條路徑的選擇狀態(tài)，把q 定義為，其中K=1，2，…，NC，假如q≤q0，就根據(jù)式(7)計算；否則采用輪盤賭方式，輪盤賭方式如下：

(1)設(shè)置參數(shù)r=rand(0，1)；

(2)若s≥r，轉(zhuǎn)步驟(4)；

(4)算法結(jié)束[10]。

2.2 全局信息素強化

蟻群算法中螞蟻選擇路徑是互不影響、相對獨立的，存在一定的盲目性，這導(dǎo)致算法收斂速度慢，收斂準(zhǔn)確性也低；另外當(dāng)問題的規(guī)模比較大時，蟻群算法會求出很多無效路徑，存儲太多無效路徑會使得算法效率降低。因此，本文給出了一種優(yōu)化方法：用一個變量來標(biāo)記每次迭代過程完成后的一條最優(yōu)路徑，然后對最優(yōu)路徑做一次信息素的加強操作，加強后，最優(yōu)路徑上的信息素比原來的信息素要強，這樣會有效地避免求出太多無效路徑，大大地加快了算法的尋優(yōu)速度。因此全局信息素更新式(2)可以改成式(8)。

2.3 交叉變異操作

為了克服螞蟻容易陷入局部最優(yōu)解的缺點，本文給出了一種優(yōu)化方法：該方法啟發(fā)于遺傳算法的變異操作，隨機地在當(dāng)次迭代過程中獲得的解集中選擇一條路徑并且設(shè)置一個變異率pλ，控制pλ為一個較小的值，當(dāng)滿足變異率時對該路徑的信息素值作一個隨機的修改，這些值要在[τmin，τmax]之間，τmin代表的是信息素最小值約束，τmax代表的是信息素最大值約束，通過這種約束條件可以使得信息素含量限制在一定的區(qū)間內(nèi)，有效地避免了算法因為各條路徑上的信息素存在較大的差距而使得算法的搜索尋優(yōu)過程出現(xiàn)停滯，造成陷入局部最優(yōu)解的情況的發(fā)生。

從遺傳算法的交叉操作中受到啟發(fā)，可以設(shè)置另外一個交叉率pθ，把pθ限制為一個較小的值，隨機地在該次迭代所有的解集中選擇兩條較優(yōu)解，然后再把這兩條較優(yōu)解進行交叉，交叉后會得到一條新的解，然后再把這條新的解加入到解集中，新的解通常更加接近最優(yōu)解，交叉操作增加了算法的隨機性，避免了算法陷入到局部最優(yōu)解[11]。

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

由于遺傳算法在初始階段的時候搜索能力特別強，與之相反，蟻群算法在初始階段搜索能力特別弱，如果單獨用蟻群算法進行資源分配，效率會非常低下。因此，本文將兩種算法融合起來，開始用遺傳算法進行搜索，然后把遺傳算法搜索到的較優(yōu)解變換為蟻群算法的起始信息素，后期再轉(zhuǎn)入蟻群算法進行搜索。于是便出現(xiàn)了兩個問題：第一是兩種算法的融合點怎么確定，第二是怎么把遺傳算法的較優(yōu)解變換為蟻群算法的起始信息素。下面先簡單地介紹一下遺傳算法，然后再具體闡述[12]。

2.4.1 遺傳算法原理

遺傳算法模擬了自然界中生物的進化過程，首先通過隨機的方式產(chǎn)生一定數(shù)量的個體，由這些個體構(gòu)成起始種群，利用適應(yīng)度函數(shù)求出所有染色體的適應(yīng)度值，對于某個個體而言，它的適應(yīng)度值越高，表示它的適應(yīng)力越強，所以從中選擇適應(yīng)度值高的種群個體進行交叉變異，交叉變異后會得到適應(yīng)力更強的個體。該過程不斷迭代，滿足結(jié)束條件時終止算法，遺傳算法通過不斷地迭代來優(yōu)化問題的解[13]。

2.4.2 遺傳算法流程圖

遺傳算法的流程圖如圖2 所示。

圖2 遺傳算法流程圖

2.4.3 融合點的確定

為了將兩種算法進行融合，就必須要確定兩者的融合點，于是繪制了兩種算法的速度時間曲線圖，如圖3所示。由圖3 可知：0～ta時間段，遺傳算法搜尋速度明顯快于蟻群算法；在ta時間段以后，情況相反，蟻群算法搜尋速度明顯快于遺傳算法，ta時間點兩種算法的搜尋速度相同，因此ta點就是融合點。確定融合點的具體思路是：設(shè)置一個最小進化率pw，倘若連續(xù)三代的進化率都比pw要小，那么該點就為融合點，于是在該點結(jié)束遺傳算法，進入蟻群算法搜索階段[14]。

圖3 速度-時間曲線圖

2.4.4 初始信息素轉(zhuǎn)化方法

本文將遺傳算法的解變換為蟻群算法的起始信息素，具體實現(xiàn)過程為：在遺傳算法結(jié)束后以15%的概率選擇適應(yīng)度值最高的個體，每個個體都代表了一個較優(yōu)解；然后再將這些解變換成節(jié)點上的螞蟻數(shù)；接著再使用信息素轉(zhuǎn)化因子，將這些螞蟻數(shù)變換成節(jié)點上的信息素。于是(i，j)路徑上的起始信息素定義為：

2.4.5 融合后的算法流程圖

融合后的算法流程圖如圖4 所示。

圖4 融合后算法流程圖

3 實驗與分析

為了更加直觀地驗證對蟻群算法進行改進后的效果，本文分別對改進蟻群算法、基本遺傳算法和基本蟻群算法進行了MATLAB 仿真實驗，并把它們的實驗結(jié)果進行對比分析，從任務(wù)完成時間、算法迭代次數(shù)、負(fù)載均衡效果來評價算法的改進效果，同時設(shè)置了資源點數(shù)為8 個，任務(wù)數(shù)量從20～100 個，算法的各個參數(shù)是通過以往的文獻來確定的，各參數(shù)取值見表1。

表1 各參數(shù)取值

通過實驗得到實驗數(shù)據(jù)并進行實驗結(jié)果的對比分析，改進算法與基本蟻群算法任務(wù)完成時間對比如圖5所示，改進算法與基本遺傳算法的任務(wù)完成時間對比如圖6 所示。迭代次數(shù)對比如圖7 所示，負(fù)載均衡對比如圖8 所示。

圖5 改進算法與基本蟻群算法任務(wù)完成時間對比

圖6 改進算法與基本遺傳算法任務(wù)完成時間對比

由圖5 和圖6 可知：改進算法的任務(wù)完成時間明顯短于兩種未改進的算法，且在任務(wù)數(shù)量較大時改進效果越明顯，因此改進算法更加適合于大規(guī)模資源分配問題。由圖7 可知：迭代次數(shù)隨著任務(wù)數(shù)量的增加而增加，改進算法的迭代次數(shù)比兩種未改進算法的迭代次數(shù)更少，說明對算法進行改進提升了算法的效率。由圖8 可知：改進算法的負(fù)載均衡效果要好于其他兩種未改進的算法，說明了對算法進行改進提升了算法負(fù)載均衡性能。

圖7 迭代次數(shù)對比

圖8 負(fù)載均衡對比

4 結(jié)論

本文針對蟻群算法進行了一系列改進，并進行了MATLAB 仿真實驗。實驗結(jié)果表明，改進算法的任務(wù)完成時間更短，且在任務(wù)數(shù)量較大時效果越明顯，說明改進算法更加適合大規(guī)模資源分配問題。改進算法的迭代次數(shù)更少，說明對算法進行改進提升了算法的效率。此外，改進算法的負(fù)載均衡效果也更好。由此可以得出結(jié)論：對算法的改進是有效的，能明顯提升算法的綜合性能。