引言

蟻群算法(AntColonyOptimization,ACO)是模擬蟻群尋找食物的一種生物啟發(fā)式算法⑴，通過研究圖論來尋找優(yōu)化路徑。針對網(wǎng)絡(luò)資源管理中路徑負載、路由選擇、集群并行計算等研究課題，將網(wǎng)絡(luò)流量工程與蟻群算法相結(jié)合,提出基于蟻群算法的網(wǎng)絡(luò)流量負載均衡和路由選擇優(yōu)化的新方法。

流量負載均衡與路由選擇優(yōu)化，一直都是網(wǎng)絡(luò)資源優(yōu)化研究中的重要課題⑵；云網(wǎng)絡(luò)集群和分布式并行計算，是當前網(wǎng)絡(luò)發(fā)展和研究的前沿課題。本文研究的目標就是把海量服務(wù)請求合理地分配到現(xiàn)有網(wǎng)絡(luò)資源，避免網(wǎng)絡(luò)擁塞瓶頸，提高網(wǎng)絡(luò)服務(wù)質(zhì)量(QoS)。網(wǎng)絡(luò)流量的負載均衡如圖1所示。

1  蟻群算法概述

1.1  蟻群算法

蟻群算法是繼模擬退火算法、基因遺傳算法、禁忌搜索算法、人工神經(jīng)網(wǎng)絡(luò)算法之后的又一種搜索算法,主要應(yīng)用于復(fù)雜組合問題的搜索優(yōu)化其。該算法具有智能搜索、正反饋、全局優(yōu)化、快速求解，以及穩(wěn)健性、分布式計算、易于與其它算法結(jié)合等優(yōu)點。

1.2  算法基本原理

蟻群算法是通過蟻群間信息素的動態(tài)交互(即蟻群內(nèi)信息素相互增強，蟻群間信息素相互減弱)來建立數(shù)學(xué)模型，模擬蟻群尋找食物的一種搜索算法。

螞蟻屬于群居昆蟲，個體行為極其簡單，而群體行為卻極其復(fù)雜。一群螞蟻通過彼此之間的相互協(xié)作，能夠很容易從蟻巢出發(fā)去找到食物源，并且所經(jīng)過的路徑最短。人們通過大量的研究發(fā)現(xiàn)，螞蟻個體之間是通過在其走過的路徑上留下一種可稱之為“信息素(Pheromone)w的物質(zhì)來進行信息傳遞。后到的螞蟻遇到信息素時，檢測出該物質(zhì)存在量的多少，并且根據(jù)信息素的濃度來指引自己前進的方向。同時，隨著時間的推移，信息素會逐漸消減，路徑的長短和路徑上螞蟻的多少對路徑上殘余信息素的強度產(chǎn)生影響，反過來信息素的強弱又指引其它螞蟻前進的方向。因此，路徑上走過的螞蟻越多，則后來螞蟻選擇

該路徑的概率越大，這就構(gòu)成了螞蟻群體行為表現(xiàn)出的一種信息正反饋機制螞蟻個體間就是通過這種信息交流來快速搜索到食物源。

圖1    網(wǎng)絡(luò)流量的負載均衡

蟻群從蟻巢到達食物源的過程中,外界環(huán)境是不斷變化的，如信息素的濃度、障礙物等。螞蟻覓食過程中釋放的信息素具有三點特性：

首先是具有揮發(fā)性，隨著時間的流逝，路徑上的信息素會逐漸減弱。

其次是具有隨機性，對下一步路徑的選擇是隨機的。

另外，就是具有啟發(fā)性,路徑上的信息素越多，被選中的概率就越高。

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

為了模擬螞蟻的行為，以求解N個城市的旅行商問題(TravelingSalesmanProblem,TSP)為例。已知有N個城市，尋找一條訪問兩個城市之間的最短路徑。設(shè)蟻群中螞蟻數(shù)量為m,城市/和j之間的路徑

式中，螞蟻總數(shù)m等于N個城市在t時刻螞蟻數(shù)量BiCt)之和。

Ttj(t)表示t時刻在i?j路徑&頊殘留的信息量。初始時刻，在各條路徑上的信息量相等，設(shè)烏(0)=C(C為常數(shù)，初始化時通常取為0)。螞蟻Kfe=1,2,…)在運動過程中，根據(jù)各路徑上的信息量濃度大小決定轉(zhuǎn)移方向，t時刻螞蟻&由位置/轉(zhuǎn)移到j(luò)的概率P$(t)：

式中，rejected；.={k}表示螞蟻k已經(jīng)走過，下一步不會途經(jīng)的城市集合，即禁忌表;allowed*={N—k}表示螞蟻方還沒有走過,下一步可能會途徑的城市集合，即候選表-rejectedjs)表示禁忌表中的第s個元素；烏(t)表示螞蟻后在t時刻在城市i到j(luò)的路徑上捕獲的信息素強度，其大小可由路徑上殘留的信息素、當前螞蟻k釋放的信息素和信息素本身揮發(fā)剩余量綜合確定;入”1)表示螞蟻后在t時刻由城市/到j(luò)的期望程度(亦稱可見度)，其值可根據(jù)某種啟發(fā)式算法確定。當相。)>0時，表示鄰域，處的螞蟻京在t時刻按概率P§(t)移至鄰域j的可能性；當Ai;(t)<0時，鄰域/處的螞蟻及做鄰域搜索,其搜索半徑為r(此值可由實驗得出)；a,/3分別表示螞蟻在運動過程中所積累的信息及啟發(fā)式因子在螞蟻選擇路徑中所起的不同作用，它們是控制信息素強度與可見度相對重要性的參數(shù)?？梢姡D(zhuǎn)移概率是期望程度(即可見度)和信息素強度的綜合權(quán)衡的結(jié)果。

人工蟻群系統(tǒng)與真實螞蟻系統(tǒng)不同，為了使人工蟻群系統(tǒng)更加智能與高效，還需使其具有一定的記憶功能，用rejected*O=1,2,…)記錄螞蟻k目前已途經(jīng)過的城市。但是隨著時間的慢慢推移，先前釋放留下的信息素濃度會逐漸揮發(fā)消逝。設(shè)信息素濃度的保留系數(shù)為p(0<p<1)，它體現(xiàn)了信息素強度的頻繁性和持久性;而1—p表示信息素的消逝程度。經(jīng)過時間間隔，螞蟻完成一次循環(huán)搜索，路徑上信息素濃度可按下式計算：

式中，△在表示螞蟻k在本次循環(huán)時間間隔內(nèi)，在路徑eg邊上留下的新增信息素量;而爲"函)表示全部螞蟻m={1,2,…}在本次循環(huán)時間間隔內(nèi)，在路徑邊上留下的信息素濃度之和；q(t十△[)表示i-j路徑上信息素濃度的總和，其中△者可表示為：

式中，n表示螞蟻k在本次循環(huán)中所漫游的城市數(shù)目(n≤N)。

綜上所述，式(1)?式(6)中出現(xiàn)的a，B，p,Q等參數(shù)根據(jù)實際用途與領(lǐng)域，用試驗的方法確定g(t),烏表達式可根據(jù)具體問題而定。由于上述過程是一個遞推過程，易在計算機上編程實現(xiàn),其停止條件可以用固定循環(huán)次數(shù)或者當進化趨勢不明顯時停止。

2  基于蟻群算法的網(wǎng)絡(luò)負載均衡

2.1  數(shù)學(xué)建模的基本思想

通過模擬蟻群釋放出的信息素這個紐帶,可以抽象出表1所列的模型假設(shè)。

表1    蟻群算法的假設(shè)模型

2.2  蟻群算法的設(shè)計原理

假設(shè)各節(jié)點間的初始信息素強度都相等，將m只螞蟻置于m個源節(jié)點。

初始時刻，m只螞蟻位于加個源節(jié)點，N個節(jié)點的信息素強度相同。

每次循環(huán)前，檢驗是否滿足終止條件。如果滿足終止條件，則停止移動;如果不滿足終止條件，則按照下列的轉(zhuǎn)移規(guī)則進行移動。

在剩余未走過的節(jié)點集合中，隨機選擇一個路由節(jié)點,按照轉(zhuǎn)移概率和轉(zhuǎn)移規(guī)則進行移動，直到完成一次搜索結(jié)束。

轉(zhuǎn)移到下一個節(jié)點后，如果此節(jié)點為目標節(jié)點，則顯示訪問成功,返回請求服務(wù)信息;如果此節(jié)點為源節(jié)點，則重新初始化,按步驟(3)進行。

按照信息調(diào)整規(guī)則，在本次搜索結(jié)束后，對各節(jié)點間的信息素進行更新調(diào)整，為下一次的轉(zhuǎn)移做準備。

重復(fù)步驟(2),如滿足終止條件，則終止搜索，標記顯示搜索路徑與搜索時間；如果不滿足終止條件，則重復(fù)步驟(3)?(5),直到滿足終止條件為止*。

圖2所示是根據(jù)蟻群算法設(shè)計的基本流程圖。

2.3  基于蟻群算法實現(xiàn)負載均衡的編程設(shè)計

蟻群算法是對自然界螞蟻覓食過程的抽象，通過建立數(shù)學(xué)模型，在電腦上模擬實現(xiàn)。事實上，每只螞蟻并不需要知道整個世界的信息，它們只需要關(guān)心自身附近很小范圍內(nèi)的信息，根據(jù)捕獲的局部信息，利用幾條簡單的規(guī)則進行判斷與決策。這樣，在蟻群這個集體里,復(fù)雜性的行為就會凸現(xiàn)出來，抽象成簡單規(guī)則。蟻群算法的設(shè)計就是把復(fù)雜問題抽象成簡單的數(shù)學(xué)模型,抽象設(shè)計遵循以下六條規(guī)則：

圖2    蟻群算法的基本流程

2.3.1  搜索范圍

螞蟻觀察的范圍為一個抽象的方格世界,螞蟻轉(zhuǎn)移參數(shù)為速度半徑(初始化為3),這樣螞蟻觀察到的范圍就是一個3X3的方格世界，轉(zhuǎn)移到下一個路由節(jié)點的距離在這個范圍之內(nèi)。

2.3.2  環(huán)境變化

螞蟻所在的環(huán)境在電腦模擬中是一個虛擬的世界,其中有障礙物、有別的螞蟻、還有信息素。信息素有兩種，一種是找到食物灑下的食物信息素，另一種是找到蟻巢后螞蟻灑下的蟻巢信息素。每只螞蟻都僅能感知它范圍之內(nèi)(3X3)的鄰近區(qū)域。同時，隨著時間的流逝，環(huán)境讓信息素以一定的速率逐漸消減。

2.3.3  覓食規(guī)則

每只螞蟻在能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去;否則看路徑上是否有信息素，比較哪一點的信息素強度最大，螞蟻就朝哪個方向轉(zhuǎn)移;同時螞蟻也會以小概率犯錯誤，即并不是每次都理想地往信息素最多的節(jié)點移動。螞蟻找窩的規(guī)則和上面一樣，不同的是僅對窩的信息素做出反應(yīng)，而對食物信息素沒反應(yīng)。

2.3.4  轉(zhuǎn)移規(guī)則

螞蟻都朝向信息素最多的方向轉(zhuǎn)移，當周圍沒有信息素指引時，它會繼續(xù)自己原來的軌跡，慣性地移動下去。同時，螞蟻在運動的方向上也會有一個隨機的小擾動。為了預(yù)防螞蟻原地轉(zhuǎn)圈，它會記住自己的歷史軌跡，盡量避開已走過的節(jié)點，從而遍歷新節(jié)點。

2.3.5  避障規(guī)則

如果螞蟻要移動的方向有障礙物擋住，它會隨機地選擇一個其它方向，并且在信息素強弱的指引下做出智能判斷和選擇。

2.3.6  釋放信息素規(guī)則

螞蟻在剛找到食物或蟻巢時會散發(fā)更多的信息素,并隨著它走遠的距離，釋放出的信息素會越來越少;隨著時間的流逝，殘留的信息素也會慢慢消失。

基于蟻群算法原理,在計算機上編程模擬實現(xiàn)：最大信息素:螞蟻初始時擁有的信息素總量。

消失的速度：隨著時間的流逝，路徑上的信息素慢慢揮發(fā)、消減的速度。

錯誤概率：螞蟻做出移動選擇，不僅需要根據(jù)信息素強度的大小，而且自身也有一個隨機的小擾動，錯誤概率越大，表示螞蟻越有獨立性與創(chuàng)新性。

速度半徑：螞蟻一次搜索過程中轉(zhuǎn)移的最大距離，也就是螞蟻能感知的最大范圍。

記憶能力：記錄螞蟻剛剛走過的路由節(jié)點信息，這樣能夠避免螞蟻原地轉(zhuǎn)圈、避免重復(fù)。

初始時，螞蟻從蟻巢出發(fā)，尋找食物，找到食物后再返回蟻巢，蟻群遇到路障后的轉(zhuǎn)移規(guī)則如圖3所示。

圖3    螞蟻遇到路障的轉(zhuǎn)移規(guī)則

由圖3可見，當無路障時，螞蟻根據(jù)路徑上信息素濃度和自身隨機的移動規(guī)則，繼續(xù)轉(zhuǎn)移；

遇到單路障時，螞蟻根據(jù)信息素濃度大小和隨機選擇綜合確定，繞過路障繼續(xù)轉(zhuǎn)移。

而當遇到多個路障時，螞蟻遵循單路障規(guī)則，然后繞過路障繼續(xù)轉(zhuǎn)移。

人工蟻群和自然界蟻群的相似之處在于,兩者優(yōu)先選擇的都是含“信息素”濃度較大的路徑，選擇路徑時會有一個小擾動，這樣在較短的路徑上會聚集較多的信息素。

2.4  基于蟻群算法實現(xiàn)負載均衡的編程設(shè)計流程圖蟻群算法實現(xiàn)負載均衡的編程設(shè)計流程圖如圖4所示。

Start

圖4    用蟻群算法實現(xiàn)負載均衡的程序流程圖

3  實驗結(jié)果與性能分析

3.1  單服務(wù)器下基于蟻群算法的網(wǎng)絡(luò)路由選擇基于蟻群算法的基本原理可用C語言在計算機上編程，以模擬網(wǎng)絡(luò)環(huán)境。

圖5所示是基于蟻群算法的單服務(wù)器下的網(wǎng)絡(luò)路由選擇方法，圖5中的內(nèi)容描述如表2所列。

表2    單服務(wù)器下的網(wǎng)絡(luò)路由選擇

圖5(a)：開始1s時，蟻群都集中于蟻巢H及其附近區(qū)域，即將進行食物路徑的遍歷搜索。

圖5(b)：14s后，正在進行路徑遍歷搜索，搜索

2012年/第2期物聯(lián)網(wǎng)技術(shù)61\

達到食物目標節(jié)點的最優(yōu)路徑。

圖5(c)：42s后，已經(jīng)基本完成遍歷搜索，并在全局范圍內(nèi)找到了最優(yōu)路徑。

圖5    單服務(wù)器下的網(wǎng)絡(luò)路由選擇

上述實驗結(jié)果表明，蟻群算法具有智能搜索、全局優(yōu)化的特性，利用正反饋機制可以快速地尋找到最優(yōu)路徑。

3.2  多服務(wù)器下基于蟻群算法實現(xiàn)流量負載均衡

基于蟻群算法來實現(xiàn)多服務(wù)器的網(wǎng)絡(luò)負載流量均衡的研究實驗結(jié)果如圖6所示。圖中的內(nèi)容描述如表3所列。

圖6    多服務(wù)器下的流量負載均衡

表3    多服務(wù)器下的負載均衡選擇

圖6(a)：開始1s時，蟻群都集中于蟻巢H及其附近區(qū)域，即將進行食物路徑的遍歷搜索。

圖6(b)：19s后，正在進行遍歷搜索時，螞蟻首先搜索到最近的食物，并根據(jù)螞蟻的需求與食物本身的多少，綜合考慮后做出是否需要尋找下一處食物的抉擇。

圖6(c)：33s后，由于紅色的食物不能滿足螞蟻的需求，即分擔過載(標記成f),于是螞蟻需要尋找下一處的服務(wù)器(即白色食物F),以達到負載均衡。

圖6(d)：44s后，螞蟻在紅色食物F(f)和白色食物F等多處食物處尋找食物，以滿足自身的需求，緩解單一食物處的需求壓力，從而達到了負載均衡訪問。

3.3  實驗結(jié)果分析與研究結(jié)論

為了提升訪問的效率和速度，可以提出設(shè)置多臺服務(wù)訪問終端，并作鏡像處理,如此就可以在地理位置、訪問時間、服務(wù)質(zhì)量等方面,使訪問得到極大的優(yōu)化與改善。實現(xiàn)網(wǎng)絡(luò)流量負載均衡的方法有多種，但是從當前的應(yīng)用技術(shù)和實際實施看，采取在不同的地理位置配置多臺服務(wù)終端設(shè)備來實現(xiàn)服務(wù)請求的及時響應(yīng)是主流技術(shù)。因此,本文從這個角度出發(fā)，采用C語言在計算機上編程模擬實現(xiàn)了網(wǎng)絡(luò)環(huán)境下的網(wǎng)絡(luò)流量負載均衡的研究與實現(xiàn)，并取得了良好的實驗效果。

通過對實驗結(jié)果的分析表明，蟻群算法具有智能搜索、全局優(yōu)化、穩(wěn)健性與正反饋等優(yōu)點，能夠在較短的時間內(nèi)尋找到最優(yōu)路由，使服務(wù)請求得到最快的服務(wù)響應(yīng)。

3.4  實驗的改善方法及其研究擴展

本實驗采取在不同的地理位置，配置多臺服務(wù)終端，從硬件角度考慮，設(shè)計并實現(xiàn)了網(wǎng)絡(luò)服務(wù)請求的及時響應(yīng),并取得了良好的實驗效果。

本實驗從軟件的角度考慮,充分利用蟻群算法正反饋的特性，對一臺或多臺服務(wù)器訪問，選擇較為合適的路徑，同樣也達到網(wǎng)絡(luò)流量負載均衡的良好效果。

4  蟻群算法的發(fā)展前景

多年來世界各地研究工作者對蟻群算法也進行了精心研究和應(yīng)用開發(fā),該算法已被大量應(yīng)用于網(wǎng)絡(luò)路由選擇、機器人協(xié)作求解、分布式集群計算、大規(guī)模數(shù)據(jù)挖掘等前沿領(lǐng)域。

以蟻群算法為代表的群智能已成為當今分布式

人工智能研究的一個熱點，許多源于蜂群和蟻群模型設(shè)計的算法已越來越多地被應(yīng)用于企業(yè)的運轉(zhuǎn)模式的研究。英國電信公司和美國世界通信公司以電子螞蟻為基礎(chǔ)，對新的電信網(wǎng)絡(luò)管理方法進行了試驗,群智能還被應(yīng)用于工廠生產(chǎn)計劃的制定和運輸部門的后勤管理，美國通用汽車公司、法國液氣公司、荷蘭公路交通部和美國一些移民事務(wù)機構(gòu)也都采用這種技術(shù)來改善其運轉(zhuǎn)機能。鑒于群智能廣闊的應(yīng)用前景,美國和歐盟均于近幾年開始出資資助基于群智能模擬的相關(guān)研究項目，并在一些院校開設(shè)群體智能的相關(guān)課程。在國內(nèi)，國家自然科學(xué)基金“十五”期間學(xué)科交叉類優(yōu)先資助領(lǐng)域中的認知科學(xué)及其信息處理的研究內(nèi)容中也明確列出了群智能領(lǐng)域的進化、自適應(yīng)與現(xiàn)場認知主題。

5  結(jié)語

目前,蟻群算法在啟發(fā)式方法范疇內(nèi)已逐漸成為一個獨立的分支,在有關(guān)國際會議上多次作為專題加以討論。隨著研究的深入，蟻群算法將廣泛應(yīng)用于網(wǎng)絡(luò)路由選擇、分布式計算和搜索組合優(yōu)化，展現(xiàn)出勃勃生機和廣闊的發(fā)展前景。