李 絮，郭 英，劉爭艷

(阜陽師范學(xué)院 計算機與信息工程學(xué)院，安徽 阜陽 236041)

蟻群算法(Ant Colony Algorithm，ACA)是受自然界中螞蟻覓食行為啟發(fā)，由意大利學(xué)者Marco Dorigo 等人提出的一種仿生智能優(yōu)化算法，已被廣泛應(yīng)用到路徑規(guī)劃、車輛調(diào)度、旅行商問題( TSP)等一系列組合優(yōu)化問題中[1-3]。目前研究者們對蟻群算法進行了大量的改進研究，如文獻[4]利用粒子群算法對蟻群算法的參數(shù)進行優(yōu)化選取，設(shè)計了一種全局異步與精英策略相結(jié)合的信息素更新機制;文獻[5]通過引入揮發(fā)率動態(tài)衰減機制，并重新定義啟發(fā)式信息及引入邊界對稱變異策略，提出了一種新蟻群優(yōu)化算法。雖然改進的算法的求解質(zhì)量有所提高，但算法仍存在后期易陷入局部極優(yōu)、收斂速度慢等問題，而其中一個關(guān)鍵問題是如何在“探索”和“開發(fā)”之間建立一個平衡。

云模型是由我國學(xué)者李德毅教授提出的一種定性定量之間的不確定性轉(zhuǎn)換模型。近年來云模型這一不確定性處理機制也被引入到對群智能進化算法的改進中，如文獻[6]利用云模型控制量子粒子群算法中關(guān)鍵參數(shù)，以達到對粒子尋優(yōu)自適應(yīng)控制的目的;文獻[7]采用云模型對粒子群算法進行改進，都取得了顯著效果。

本文借鑒云模型理論，提出一種新的基于云模型的自適應(yīng)蟻群算法( Adaptive Ant Colony Algorithm Based on Cloud Model，CACA)。利用云模型所獨具的隨機性和穩(wěn)定性的特點，使得提出的算法既能保持種群的多樣性，改善蟻群算法對未知解的探索能力，同時又能加強蟻群算法對已知解的開發(fā)和利用，提高算法的收斂速度和求解質(zhì)量。

1 基本蟻群算法

1.1 路徑構(gòu)建方式

以求解TSP 問題為例，螞蟻從起點城市出發(fā)，遍歷其余城市各一次，再回到起點，這樣便構(gòu)建了一條連接各個城市的路徑?；鞠伻核惴ㄖ形浵佅扔嬎阌伤诔鞘修D(zhuǎn)移到其它各個城市的概率，然后按隨機比例規(guī)則選擇具體要訪問的城市。

在t 時刻，螞蟻k 由城市i 轉(zhuǎn)移到另一城市j 的概率為:

式中，tabuk表示螞蟻k 下一步選擇的城市的禁忌表; τi，j為( i，j) 邊上的信息素強度; ηi，j為啟發(fā)式函數(shù)，表達式為1/di，j，di，j表示城市i，j 間的距離;α、β 為啟發(fā)式因子，分別表示信息素與啟發(fā)式信息對路徑選擇的重要性。

1.2 信息素更新方式

經(jīng)過n 個時刻，螞蟻完成一次循環(huán)( i，j) 路徑上的信息素更新方式如下:

式中，ρ 為信息素?fù)]發(fā)因子，m 為螞蟻個數(shù)，Δτi，j(t+n)為本次循環(huán)中路徑( i，j) 上的信息素增量，Q 為信息素強度，Lk為螞蟻k 在本次循環(huán)中走過的路徑總長度。

2 云模型理論

定義 設(shè)X 是一個用精確數(shù)值表示的論域，X上對應(yīng)著定性概念A(yù)，對于X 中任意一個元素x，都存在一個有穩(wěn)定傾向的隨機數(shù)μA(x) ，叫做x 對A的隸屬度，x 在X 上的分布稱為云模型，簡稱為云[8]。

云模型主要由期望值Ex，熵En 和超熵He 三個數(shù)值來表征，它們反映了定性概念A(yù) 整體上的定量特征。Ex 表示論域空間分布的期望，En 表示定性概念A(yù) 的不確定性，超熵He 是熵的不確定性度量。若存在x ～N(Ex，En′2) ，其中En′ ～N(En，He2) ，且滿足，則該分布稱為正態(tài)云模型[9]。圖1給出由Ex =0，En =2，He =0.3，隨機產(chǎn)生1 000 個云滴的正態(tài)云模型示意圖。

圖1 正態(tài)云模型的三個數(shù)字特征示意圖

3 云自適應(yīng)蟻群算法(CACA)

3.1 信息素更新方式

本文信息素更新方式采用局部信息素和全局信息素相結(jié)合的更新方式。

局部信息素更新是對螞蟻經(jīng)過的每一條邊上的信息素進行更新，更新方式如下:

其中，0 ＜ξ ＜1，τ0是信息素的初始值。

全局信息素更新不僅是對全局最優(yōu)路徑信息素更新，同時也對確定為次優(yōu)路徑上的信息素進行更新。更新方式如下:

其中，T′為全局最優(yōu)或次優(yōu)路徑，L( T′) 為相應(yīng)路徑的總長度，μ 為路徑對應(yīng)的最優(yōu)或次優(yōu)解在云模型中的隸屬度值，全局信息素增量＇則是由隸屬度與解的質(zhì)量共同確定。

3.2 信息素取值區(qū)間界定

針對蟻群算法運行過程中易出現(xiàn)停滯及擴散問題，本文將信息素的取值范圍限定在區(qū)間[τmin，τmax]內(nèi)，判斷公式如下:

在算法尋優(yōu)過程中，每發(fā)現(xiàn)一條至今最優(yōu)路徑Tbest，就更新τmax值，τmax定義為1/ρTbest。相應(yīng)的信息素下界τmin定義為τmax/a，a 是個參數(shù)，其值由實驗來確定。

3.3 云參數(shù)設(shè)置及次優(yōu)解確定

CACA 中涉及到的云參數(shù)有期望值Ex，熵En，超熵He 及隸屬度閾值q。Ex 設(shè)置為算法在每次迭代中找到的全局最優(yōu)解Best。En 值根據(jù)“3En”規(guī)則確定，令Ex +3En 為算法找到的全局最差解Worst，因此En =( Worst －Best) /3。He 由En 和信息素分布狀況信息值R 共同確定，He =En/R，其中R 值是由信息素分布狀況的評價算法得出( 見3.4)。隸屬度閾值q 則是根據(jù)信息素分布狀況信息值R 進行自適應(yīng)地調(diào)整，將q 設(shè)定為q=1 －1/R。

次優(yōu)解則是依據(jù)隸屬度μ 和隸屬度閾值q 的關(guān)系來確定。即在每次迭代之后，根據(jù)云模型參數(shù)Ex，En 和He 值，計算算法找到的可行解的隸屬度μ，然后將μ ＞q 的可行解確定為次優(yōu)解。

3.4 信息素分布狀況評價算法

螞蟻在完成路徑構(gòu)建之后，需要對各條路徑上的信息素分布狀況進行評價，以便及時調(diào)整算法的運行狀態(tài)。信息素分布狀況的評價算法如下:

For 每個城市節(jié)點

計算該城市到其他所有城市路徑上的平均信息素值;

再統(tǒng)計大于此平均信息素值的路徑邊數(shù);

End For

對所有城市的大于其平均信息素值的路徑邊數(shù)進行求平均，其值記為R。

3.5 自適應(yīng)控制機制

由上分析可知，本文CACA 算法的自適應(yīng)控制機制主要表現(xiàn)在通過信息素分布狀況信息值R，能夠?qū)υ颇Ｐ蛥?shù)He 和隸屬度閾值q 進行自適應(yīng)調(diào)整，同時動態(tài)確定全局次優(yōu)解范圍。若R 值較小，則表示信息素分布得較集中，這時隸屬度閾值q 也會較小，相應(yīng)的也就會有較多的可行解被認(rèn)定為次優(yōu)解。這就使得算法在下一次迭代中選擇最優(yōu)路徑的概率降低，從而能夠提高算法對未知路徑的探索能力。若R 值較大，則表示信息素分布得較均勻，這時隸屬度閾值q 也會較大，相應(yīng)的只有較少的可行解被認(rèn)定為次優(yōu)解。這就使得算法在下一次迭代中選擇最優(yōu)路徑的概率提高，從而能夠提高算法對最優(yōu)路徑的開發(fā)能力。

3.6 算法流程

本文CACA 算法的基本流程如下:

Step 1. 初始化參數(shù);

Step 2. 隨機選擇起點;

Step 3. 對每只螞蟻構(gòu)建路徑，同時進行局部信息素更新;

Step 4. 評價信息素分布狀況;

Step 5. 自適應(yīng)調(diào)整云模型中各參數(shù);

Step 6. 確定全局最優(yōu)及次優(yōu)路徑;

Step 7. 進行全局信息素更新并限定取值區(qū)間;

Step 8. 終止條件不滿足則轉(zhuǎn)Step2。

4 仿真實驗

表1 問題ulysses22 的結(jié)果數(shù)據(jù)分析對比

表2 問題bays29 的結(jié)果數(shù)據(jù)分析對比

為了驗證CACA 算法的有效性，本文從TSPLIB數(shù)據(jù)集中選取ulysses22 問題和bays29 問題( http: //elib. zib. de/pub/mp-testdata/tsp/tsplib/)，將該算法與最成功的蟻群改進算法ACS[10]和MMAS[11]進行仿真實驗對比。實驗參數(shù)如下:最大迭代次數(shù)為1 000，螞蟻個數(shù)為100，α =1，β =2，ρ=0.1，ξ=0.1，a=100，τ0=1/n* Len( n 為城市節(jié)點數(shù)，Len 為最近鄰算法找到的初始路徑值)。云模型中相關(guān)參數(shù)則完全由算法根據(jù)其自身運行狀況自適應(yīng)地確定。

圖2 ACS 運行結(jié)果(ulysses22 問題)

圖3 MMAS 運行結(jié)果(ulysses22 問題)

圖4 CACA 運行結(jié)果(ulysses22 問題)

圖5 ACS 運行結(jié)果(bays29 問題)

圖6 MMAS 運行結(jié)果(bays29 問題)

圖7 CACA 運行結(jié)果(bays29 問題)

使用ACS、MMAS 和CACA 算法，分別對ulysses22 問題和bays29 問題進行20 次獨立實驗，繪出算法找到的最優(yōu)路徑值隨迭代次數(shù)的進化曲線圖，其中ulysses22 問題的實驗結(jié)果如圖2-圖4所示，bays29 問題的實驗結(jié)果如圖5-圖7所示。同時，分別對三種算法運行20 次后的結(jié)果數(shù)據(jù)進行統(tǒng)計分析，記錄了20 次實驗中算法找到的最好值、最差值和平均值，如表1-表2所示。

由圖2-圖7和表1-表2很容易發(fā)現(xiàn)，無論是求解質(zhì)量還是收斂速度，本文CACA 算法在求解ulysses22 問題和bays29 問題中均明顯優(yōu)于ACS 和MMAS 算法。CACA 算法基本上在迭代100 次左右就可以找到問題的最優(yōu)解，而且基本上每次實驗均可以找到最優(yōu)解，這說明算法具有優(yōu)良的全局搜索能力。而ACS 和MMAS 算法在1 000 次迭代后均沒有找到問題的最優(yōu)解。同時，隨著問題復(fù)雜度(即城市節(jié)點數(shù)目) 的增加，ACS 和MMAS 算法性能明顯下降，而CACA 算法卻非常穩(wěn)定，仍然表現(xiàn)出很好的性能。實驗結(jié)果也再次表明，通過引入云模型理論及自適應(yīng)機制，能夠使算法具有較好的探索未知解的能力，使其搜索到高質(zhì)量的解，同時又能使算法充分利用已知解的信息，促進其快速收斂。

5 結(jié)束語

本文將云模型作為算法的模糊隸屬函數(shù)，通過對信息素分布狀況進行評價，動態(tài)自適應(yīng)地確定云模型的期望值，熵，超熵以及隸屬度閾值，并對確定為全局最優(yōu)及次優(yōu)路徑進行全局信息素更新，同時將信息素大小限制在一個最大最小區(qū)間，以提高算法的求解質(zhì)量和收斂速度。通過對兩個TSP 問題的多次仿真實驗，結(jié)果表明本文算法具有明顯的優(yōu)越性。今后將進一步完善算法機制，擴大算法的應(yīng)用領(lǐng)域。

[1]申鉉京，劉陽陽，黃永平，等.求解TSP 問題的快速蟻群算法[J].吉林大學(xué)學(xué)報:工學(xué)版，2013，43(1):147-151.

[2]牟廉明. 求解子旅行商問題的改進蟻群算法[J]. 計算機工程，2012，38(23):190-193，197.

[3]劉 振，胡云安.一種多粒度模式蟻群算法及其在路徑規(guī)劃中的應(yīng)用[J]. 中南大學(xué)學(xué)報: 自然科學(xué)版，2013，44(9):3 714-3 722.

[4]李 擎，張 超，陳 鵬，等.一種基于粒子群參數(shù)優(yōu)化的改進蟻群算法[J]. 控制與決策，2013，28(6):873-878.

[5]劉 全，陳 浩，張永剛，等.一種動態(tài)揮發(fā)率和啟發(fā)式修正的蟻群優(yōu)化算法[J]. 計算機研究與發(fā)展，2012，49(3):620-627.

[6]馬 穎，田維堅，樊養(yǎng)余.基于云模型的自適應(yīng)量子粒子群算法[J]. 模式識別與人工智能，2013，26(8):787-793.

[7]劉紅慶.基于云模型粒子群算法的WSN 節(jié)點部署優(yōu)化[J]. 華中師范大學(xué)學(xué)報( 自然科學(xué)版)，2013，47(2):186-188.

[8]劉常昱，李德毅，杜 鹢，等.正態(tài)云模型的統(tǒng)計分析[J].信息與控制，2005，34(2):236-239，248.

[9]張煜東，吳樂南，王水花，等.基于隸屬云模型蟻群算法與LK 搜索的TSP 求解[J]. 計算機工程與應(yīng)用，2011，47(14):46-55.

[10]Dorigo M，Gambardella L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation，1997，1(1): 53-66.

[11]Stützle T，Hoos H H. MAX-MIN ant system[J]. Future Generation Computer Systems，2000，16(8): 889-914.