劉子墨

（首都經(jīng)濟(jì)貿(mào)易大學(xué)管理工程學(xué)院，北京 100070）

蟻群算法從大自然中誕生，是尋優(yōu)問(wèn)題中一種優(yōu)秀的解決策略[1]。最初是由DORⅠGO 等[2]首次向世人介紹了蟻群算法。由于螞蟻的移動(dòng)是隨機(jī)的，當(dāng)種群規(guī)模達(dá)到一定程度時(shí)，蟻群算法需要很長(zhǎng)時(shí)間才能找到較優(yōu)的解決方案。因此，GAMBARDELLA 等[3]又對(duì)經(jīng)典的AS 算法進(jìn)行了改進(jìn)，提出了一種更為通用的算法“Ant-Q System”。針對(duì)蟻群算法易過(guò)早停滯的缺陷，1997 年，STUTZLE 等[4]提出了MAX-MⅠN Ant System，為其中每條邊可允許擁有的跟蹤信息素的量設(shè)置了范圍限制。而后GAMBARDELLA 等[5]提出了HAS，在HAS 的迭代中，利用螞蟻獲取的每個(gè)解，對(duì)局部進(jìn)行檢測(cè)，尋找局部最優(yōu)，從而提升解的品質(zhì)。如今，蟻群算法已頻繁出現(xiàn)在專(zhuān)業(yè)學(xué)術(shù)會(huì)議上，許多關(guān)于蟻群算法的論文也被發(fā)表在Nature、Generation Computer System等專(zhuān)業(yè)的學(xué)術(shù)刊物上，許多計(jì)算機(jī)學(xué)者對(duì)其研究十分熱切。

針對(duì)蟻群算法的缺陷，國(guó)內(nèi)的研究人員也有著不同的解決策略，其中吳慶洪等[6]提出將突變機(jī)制應(yīng)用于蟻群算法中，提高算法收斂速率；王穎等[7]提出針對(duì)參數(shù)的自適應(yīng)調(diào)整，解決不易求得全局最優(yōu)的不足；李擎等[8]利用蟻群算法易于與其他方法結(jié)合的特點(diǎn)，結(jié)合粒子群與蟻群，改進(jìn)了信息素的更新策略，對(duì)性能進(jìn)行了一定的提升。

1 相關(guān)理論與技術(shù)基礎(chǔ)

1.1 ACO 算法

1.1.1 ACO 算法簡(jiǎn)述

對(duì)ACO 算法的具體過(guò)程進(jìn)行參數(shù)設(shè)置，設(shè)τij為0，螞蟻數(shù)目為m。第k（k=1，2，…，m）只的每一步選擇由信息素濃度決定，其狀態(tài)轉(zhuǎn)移概率為，計(jì)算公式為：

其中，ak={1，2，…，n}－tabuk為下一次可選擇的所有城市的集合，tabuk則是螞蟻k當(dāng)前已經(jīng)過(guò)的城市，它會(huì)隨著ACO 算法的運(yùn)行而有一定變化。i代表螞蟻當(dāng)前所位于的城市，j為集合tabuk中的一員，為螞蟻k由城市i轉(zhuǎn)移至下一個(gè)城市j的概率，為螞蟻從城市i去往j的期望程度，τij為路徑（i，j）上的信息素軌跡強(qiáng)度。由公式1 可知，與[τij（t）]α[ηij（t）]β的關(guān)系成正比例，因此當(dāng)螞蟻進(jìn)行路徑的選擇時(shí)會(huì)優(yōu)先挑選信息素濃度較高的城市進(jìn)行轉(zhuǎn)移[9]。

1.1.2 ACO 算法優(yōu)點(diǎn)與缺陷

ACO 算法作為仿生算法，繼承了螞蟻行為的諸多特點(diǎn)，有以下幾點(diǎn)優(yōu)點(diǎn)：①本質(zhì)并行性。多個(gè)螞蟻個(gè)體可位于多點(diǎn)同時(shí)進(jìn)行搜索，相當(dāng)于多項(xiàng)代理的分布式系統(tǒng)，具有較高的算法運(yùn)行效率。②易與其他算法相結(jié)合。以ACO 算法為基礎(chǔ)，引入其他算法的優(yōu)秀機(jī)制與之進(jìn)行互補(bǔ)，可進(jìn)一步提升算法質(zhì)量。③強(qiáng)魯棒性。ACO 算法只需進(jìn)行很小的改動(dòng)便能使用在其他方面，有助于拓寬使用領(lǐng)域范圍。

ACO 算法作為新生代仿生算法，仍有著一些缺陷，主要有：①不易取得最優(yōu)解。由于ACO 算法的特性，信息素在運(yùn)行時(shí)較易集群在個(gè)別路段上，從而陷入局部最優(yōu)。②求解時(shí)間長(zhǎng)。構(gòu)造解的過(guò)程需要很大的計(jì)算量，當(dāng)待解決問(wèn)題需要構(gòu)造的可行解數(shù)目增多時(shí)，螞蟻尋找最優(yōu)解所需要的時(shí)間將會(huì)變長(zhǎng)。③參數(shù)的設(shè)置理論不足。ACO 算法的性能與關(guān)鍵參數(shù)息息相關(guān)，目前還沒(méi)有對(duì)參數(shù)的設(shè)置給出嚴(yán)密的理論認(rèn)證，多依賴(lài)實(shí)驗(yàn)經(jīng)驗(yàn)而定[10-11]。

1.2 GA 算法

1.2.1 GA 算法簡(jiǎn)述

GA 算法由HOLLAND 在1975 時(shí)首次提出，該算法參照的是達(dá)爾文的“優(yōu)勝劣汰” 進(jìn)化論原則。在遺傳算法的實(shí)現(xiàn)過(guò)程中，通過(guò)計(jì)算適應(yīng)度函數(shù)所獲取的結(jié)果可較為直觀地判斷出種群個(gè)體（染色體）適應(yīng)度的強(qiáng)弱程度，從而決定它們的存留[12]。

1.2.2 遺傳算法步驟

遺傳算法步驟如下。

步驟1：初始化種群。設(shè)置參數(shù)，選擇合適的編碼方式，產(chǎn)生非固定數(shù)據(jù)并進(jìn)行組合來(lái)獲取初始種群。

步驟2：計(jì)算適應(yīng)度值。使用適應(yīng)度函數(shù)獲取值后，選擇后續(xù)操作個(gè)體。

步驟3：執(zhí)行交叉運(yùn)算。

步驟4：執(zhí)行變異運(yùn)算。

步驟5：判斷是否能夠結(jié)束，若滿足條件則輸出結(jié)果，否則回到步驟2，最終得出最優(yōu)解。

1.3 TSP 問(wèn)題

TSP 問(wèn)題指有N個(gè)城市，由初始位置出發(fā)，遍歷每一個(gè)城市，不能重復(fù)，且最終回到原來(lái)出發(fā)點(diǎn)的問(wèn)題，同時(shí)需找到在過(guò)程中所付出的代價(jià)最小，即最短的路徑。TSP 問(wèn)題雖然描述起來(lái)并不困難，但是要獲取其精確的解卻并不是一件容易的事情，單是其所有可行路徑就有（n－1）！/2 條，學(xué)術(shù)界將其稱(chēng)為NP-Hard問(wèn)題[13-14]。

TSP 是NP 完全問(wèn)題，若一種算法在對(duì)解決TSP應(yīng)用而言表現(xiàn)良好，則通常在解決其他的應(yīng)用上也可以獲得不錯(cuò)的結(jié)果，因此以TSP 問(wèn)題來(lái)驗(yàn)證算法的改進(jìn)是否有效是比較可靠的[15-16]。

2 ACO-GA 混合算法及其在TSP 中的應(yīng)用

2.1 ACO-GA 混合算法

2.1.1 ACO-GA 混合算法原理

ACO-GA 混合算法將ACO 算法和GA 算法進(jìn)行結(jié)合，每進(jìn)行一次迭代，最差螞蟻個(gè)體就會(huì)被最好染色體所取代，替換后的解影響了信息素矩陣，從而影響最后所求最優(yōu)解。同時(shí)，在迭代過(guò)程中融入輪盤(pán)賭算法，讓適應(yīng)值與個(gè)體選中概率成正比。

2.1.2 ACO-GA 混合算法步驟

ACO-GA 混合算法步驟如下。

步驟1：初始化算法參數(shù)。將Nc（迭代次數(shù)）置0，初始化τij和Δτij，對(duì)m、ρ、α、β、Q、Ncmax等參數(shù)賦值，設(shè)置啟發(fā)值和信息素矩陣。

步驟2：初始化種群。編碼并產(chǎn)生隨機(jī)數(shù)據(jù)并進(jìn)行組合來(lái)生成初始種群，初始化染色體。

步驟3：執(zhí)行染色體選擇、變異、交叉、解碼操作。

步驟4：解空間的構(gòu)建。將m個(gè)螞蟻分配到n個(gè)城市，并根據(jù)狀態(tài)轉(zhuǎn)移概率對(duì)未經(jīng)過(guò)的城市進(jìn)行計(jì)算，并在其中選擇算得的概率最大的城市逐步進(jìn)行下一步的轉(zhuǎn)移，該過(guò)程持續(xù)至螞蟻遍歷完所有的城市為止。最終每個(gè)成員都遵循規(guī)則獲取了一條路徑，在路徑表中實(shí)現(xiàn)更新路徑。

步驟5：如果蟻群的搜索未完成，那么就跳轉(zhuǎn)到步驟4，繼續(xù)進(jìn)行循環(huán)搜索。

步驟6：執(zhí)行染色體選擇操作。

步驟7：進(jìn)行總路程的計(jì)算，使用最好染色體取代最差螞蟻，更新信息素矩陣。

步驟8：當(dāng)Nc≥Ncmax，即算法循環(huán)迭代次數(shù)已到達(dá)設(shè)定的最大值，終止條件已滿足，則循環(huán)結(jié)束并輸出計(jì)算結(jié)果；否則，跳轉(zhuǎn)至步驟3。

2.2 改進(jìn)算法在TSP 問(wèn)題中的應(yīng)用

2.2.1 仿真實(shí)驗(yàn)

本文從通用TSPLⅠB 庫(kù)中選取了eil51、rand75、eil76、pr152、bier127 等10 個(gè)實(shí)例，算例名稱(chēng)即為城市數(shù)目，分別對(duì)ACO 算法和ACO-GA 混合算法的性能進(jìn)行測(cè)試，對(duì)比分析ACO 與ACO-GA 混合算法的仿真實(shí)驗(yàn)結(jié)果。

ACO 算法參數(shù)設(shè)置：α=1，β=3，ρ=0.4，m=城市數(shù)，Q=100，迭代次數(shù)為200。

ACO-GA 混合算法的參數(shù)設(shè)置：α=1，β=3，ρ=0.4，m=城市數(shù)，Q=100，Pc=0.6，Pm=0.02，迭代次數(shù)為200。

每組測(cè)試案例獨(dú)立運(yùn)行20 次，選擇其中最佳優(yōu)化路線，即20 次尋優(yōu)中求解出的距離最短的一次。

2.2.2 測(cè)試結(jié)果與分析

分別對(duì)ACO 算法和ACO-GA 混合算法的數(shù)據(jù)進(jìn)行整理，保留4 位小數(shù)，結(jié)果如表1 和表2 所示。

表2 ACO-GA 混合算法在TSP 問(wèn)題中的實(shí)現(xiàn)

3 實(shí)驗(yàn)結(jié)果分析

運(yùn)行時(shí)間對(duì)比。ACO-GA 混合算法和ACO 算法的運(yùn)行時(shí)長(zhǎng)均隨著城市問(wèn)題量的擴(kuò)大而擴(kuò)大。當(dāng)城市規(guī)模較小、循環(huán)次數(shù)相同時(shí)，2 種算法在運(yùn)行時(shí)間上并未有明顯差距。但當(dāng)測(cè)試數(shù)據(jù)達(dá)到并超過(guò)eil51 時(shí)，ACO-GA 混合算法的求解速度體現(xiàn)了明顯優(yōu)勢(shì)，且隨規(guī)模增大，優(yōu)勢(shì)更加明顯。

最優(yōu)解對(duì)比。ACO-GA 混合算法整體上獲取的最優(yōu)解值較ACO 算法好。

最差解對(duì)比。從表1、表2 可知，ACO 算法獲得的最差解大于ACO-GA 混合算法，且與最優(yōu)解差異較大。表明ACO-GA 混合算法較均勻，尋優(yōu)效果較好。