螞蟻算法在TSP問題求解的有效利用

李明偉，李永芳

（云南開放大學 云南 昆明 650223）

1 問題的提出

計算機科學的出現，對人們的生活及行為方式帶來了極大的改變。作為一個信息爆棚的時代，尋求組合優化的空間規模和時間級是巨大的，常規方法求解是難以實現的，屬于NP完全問題。這一類問題不能使用精確算法，而需要尋求問題的有效近似算法[1]。

具體來講，我們可以將TSP這樣進行表述：假設有一個旅行商人要拜訪N個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發的城市，簡而言之就是求最短環路的問題。那么尋求TSP問題求解的優化算法可以說既具有理論意義，又具有時間價值。為了便于討論優化算法的應用問題，這里將TSP問題轉化為數學描述[2]：

假架設旅行商需要遍歷的城市數量為n，那么N個城市的集合為c={c1，c2，…cn}，那么城市i，j間的距離D（ci，cj）的距離為正實數，且i≥1，j≤n，那么在每個城市僅訪問一次的情況下，使函數（1）

達到最小城市序列 c={cρ（1），cρ（2），…，cρ（n）}。其中ρ（1），ρ（2），…ρ（n）為1，2，N的全排列。

2 TSP問題求解螞蟻算法的模型建立

在解決TSP問題求解的算法上，以仿生學算法取得的效果最佳，目前已經應用的算法包括模擬退火法、遺傳學法、人工神經網絡法等。螞蟻算法是近來來新提出的仿生進化算法，無論是個體局部收斂還是多個個體空間收斂的速度都比較快，算法設置也相較于簡單，易于應用[3]。

那么針對本文所提出的TSP問題，我們需要建立人工的螞蟻算法模型。那么假設建設有m個人工螞蟻，將其隨機分配在N個城市上，城市與城市之間形成一條邊，且該邊具有初始化信息素τij（0），將每個螞蟻的禁忌表的第一個元素設置為該螞蟻的初始城市。那么可以確定每只螞蟻在選擇路徑時的概率函數，可以表達為：

其中禁忌表tabuk（k=1，2，…m）為螞蟻k當前所走過的所有城市；τij（t）為城市i，j之間邊弧上信息素的強度，設定i為起始城市，j為到達城市，ηij=1/dij表示為ij城市間的距離因子dij為經過城市邊弧路徑（i，j）所需的花費。α為信息啟發因子，β為期望值啟發因子，且α，β∈[0，+∞)。分別表示信息素、路徑長度在選擇概率上的作用。那么對于螞蟻的城市選擇概率而言，信息素和城市間路徑的長短決定概率的大小。那么對于m個螞蟻而言，在經過n次循環后，獲得完整的禁忌表。也就是說每個螞蟻所走過的路徑長度中可以尋找最短路徑并保存，記錄這一最短路徑并更改這一路徑是哪個的信息素。不斷重復這一過程到最大遍歷值結束[4]，那么可以獲得信息素的更新公式：

其中Vτij是城市邊弧上新增信息素累加和，φ表示信息素消散的等級，殘留信息的保留部分。那么1—φ表示已經消散或削弱的部分，其中φ∈[0，1），這能夠避免信息大量無用的積累。

螞蟻k遍歷（i，j）（4）來獲得，其中Q代表螞蟻遍歷一周所釋放的信息總量，該參數為常量。由此依據上述算法的模型公式，確定參數α、β、φ、Q、螞蟻數量m的最優組合值需要通過實現確定，并得出以下結論：

①α作為信息啟發因子，其數值是每個節點上信息量受重視的程度，數值越大螞蟻選擇重復點的可能性越大。但該值不加以限制，則會出現局部最優解，該解過早得出，不利于解的最優化。

②同理β作為期望值啟發因子，代表了啟發式信息受重視的程度。其數值越大也就表明螞蟻選擇最近城市的可能性越大。

③φ值是路徑上信息素的保留情況，顯然該數值的大小會影響信息素的累積及選擇，取值不良則會產生相應的不良結果，難以取得最優組合。

④螞蟻數量m值對算法的收斂速度產生影響。當這一數量規模接近于問題研究的總量時，其所獲得的結果也就越精確。但是這也就代表了實驗過程中需要進行的循環次數會增加，算法的收斂速度就會減慢。相同螞蟻數量時，問題的規模越大，全局搜索能力越低。而參數Q則與之相反，Q值越大，算法的收斂速度也就越快，但不代表Q值可以無限增大，要與其他參數相適應[5]。

總的來說，當最終搜索達到預先定義的NCmax或者當所有實驗的螞蟻均已經選擇了同一最短路徑時，這一搜索循環可以停止。在計算機程序邏輯上可以這樣描述：

第一步為初始化，設定t=0，NC=0。城市間邊弧上的信息素強度及信息累加參數均為0.將m個螞蟻分散到n個城市上。NC表示迭代循環數。

第二步把第k個螞蟻的初始城市值放入到禁忌表tabu（s）。重復這一過程直到所有的禁忌表均已填滿。

第三步根據概率公式將螞蟻k移送到城市j中，j屬于求解的城市集合。

第四步計算第k個螞蟻遍歷的總路徑長度Lk，確定最短路徑，并更新最短路徑及相應的信息素濃度。

第五步對各邊?。╥，j）設置信息素強度變量為0及信息累計參數為NC+1.如果不是所有的螞蟻均選擇同一路徑或者未達到最大值，則清空禁忌表重新返回執行第二步。若達到NCmax或所有螞蟻均選擇同一路徑則程序終止[6]。

3 實證分析

根據螞蟻算法的基本執行方式及相關參數，通過相關實證對各參數對實驗結果的影響進行驗證。

（1）信息素的保留程度φ

設置問題研究規模為N=51，α=0.1，β=2，Q=0.5，m=20。對φ進行不同取值，分別為0.1，0.2，0.3，05，0.7，0.9，并進行實驗。當φ值為0.2～0.5之間時期所所得的最優路徑長度在434.9～436.0之間，數值比較接近。搜索循環次數依次為61/103/141.當φ值增加為0.9時，路徑上消散的信息量為0.1，所獲得的最優路徑長度為454.2，循環次數達567次?？梢姦罩档拇笮λ惴ǖ氖諗克俣戎兄匾绊懀^小會提早產生局部最優解，但是過大會增加收斂時間。

（2）螞蟻數量m

設置問題研究規模為N=51，α=0.1，β=2，Q=0.5，φ=0.2。對m進行不同取值，分別為 10，20，25，30，35，40，45，50，并進行實驗。當m值在 20～30之間時期獲得最優路徑長度為440～450之間，且循環次數比較少，位于43到86之間，雖然當m值增加到35～50之間，其所取得的最優路徑結果與m=20時比較相近，但是循環次數達到200～550次之間，收斂速度大大下降。

（3）信息總量Q

設置問題研究規模為N=51，α=0.1，β=2，m=20，φ=0.2。對進行不同取值，分別為1，10，100并進行實驗。當信息總量為100時，搜尋最佳路徑長度為446.5，循環次數為91次。大參數分別為1，10得到結果分別為446.8/447.1，搜索次數比較接近，分別為89/86，可以看出，信息總量Q值越大，信息積累越快，所得到的正反饋性能也就越好。

（4）α、β因子

α、β因子對求解的影響我們一般將兩個參數放在一起研究，其根據組合的不同，對算法的性能產生影響。其中α分別取值0.1，0.1，0.2，0.3，1.0，5.0，10.0。β分別取值0.5，1，2，3，4，8，10。當α、β均為最小值0.1/0.5時，搜索循環次數最大為157次，最優路徑長度為454.8.而當兩個參數均取最大值時，搜索次數最小，但所獲得的最優路徑長度出現局部最優解為469.7.所以可以看出當α、β取值不合理時會造成算法性能下降會過早出現最優解，不利于正常的取值。

4 結語

綜上所述，螞蟻算法是一種有效的仿生算法，適用于TSP問題求解及其相關衍生問題。但是在應用過程中要注意信息啟發因子、期望式啟發因子α、β，信息素的保留程度φ，螞蟻數量m，信息總量Q等參數的合理取值，提升算法的優越性。對于基本螞蟻算法而言，可在對參數性能的研究上進行優化。

[1]陳靈佳.蟻群算法在解決TSP問題中的應用[J].電子技術與軟件工程，2017(10)：145-146.

[2]高志娥，薛艷鋒，蘭靜.混合型蟻群算法及其應用--以旅行商問題為例[J].軟件導刊，2015(4)：138-142.

[3]顏穎.基于蟻群算法的TSP問題研究[J].哈爾濱職業技術學院學報，2017(2)：83-86.

[4]易正俊，李勇霞，易校石.自適應蟻群算法求解最短路徑和TSP問題[J].計算機技術與發展，2016，26(12)：1-5.

[5]張弛，涂立，王加陽.新型蟻群算法在TSP問題中的應用[J].中南大學學報(自然科學版)，2015(8)：2944-2949.

[6]張開碧，張洋川，萬素波，等.一種改進的競爭型蟻群算法在TSP問題中的應用[J].計算機與數字工程，2016，44(3)：396-399.