蟻群算法中參數設置的研究

摘? 要：蟻群算法是一種智能仿生算法，以TSP為例分析蟻群算法中的參數設置情況，蟻群算法中的參數較多，不同的參數組合都影響著蟻群算法的全局收斂性和收斂速度，同時也是蟻群算法研究的難點，且至今為止都沒有完整的理論支持，只能依靠學者的經驗或者大量的數據實驗。該文主要通過仿真實驗，依據每個參數對蟻群算法的最優路徑的影響，最終得出每個參數較為合理的取值范圍。且以TSP為例有較好的實用價值。

關鍵詞：蟻群算法;參數設置;TSP

中圖分類號：TP301.6? ? ? 文獻標識碼：A 文章編號：2096-4706（2020）22-0095-05

Research on Parameter Setting in Ant Colony Algorithm

——Take TSP as an Example

XIANG Yongjing

（College of Information Engineering，Tongren Polytechnic College，Tongren? 554300，China）

Abstract：Ant colony algorithm is an intelligent bionic algorithm，taking TSP as an example，the parameter setting of ant colony algorithm is analyzed. There are many parameters in ant colony algorithm，the different parameter combinations affect the global convergence and convergence speed of ant colony algorithm，and also the difficulty of ant colony algorithm research. So far there is no complete theoretical support，can only rely on the experience of scholars or a large number of data experiments. This paper mainly through simulation experiments，according to the impact of each parameter on the optimal path of the ant colony algorithm，and finally get a reasonable value range for each parameter. Taking TSP as an example，it has good practical value.

Keywords：ant colony algorithm;parameter setting;TSP

0? 引? 言

蟻群算法是受自然界螞蟻的啟發而得到的一種智能啟發式算法，該算法具有良好的尋優能力、拓展性強、并行性和魯棒性，其應用較為廣泛，并且該算法在解決離散問題的同時也可以針對連續的問題，且均可以得到較好的解。本文是在基于蟻群算法求解最優旅游路徑的研究課題中，發現蟻群算法的復雜性，而算法解的優劣很大程度上取決于算法中的參數設置，參數的選擇決定著算法的最優解和收斂速度。并且沒有相關完整的可行性參考文獻提供參考，而這也是此算法進一步突破的關鍵點。故有本篇研究，為的是在使用蟻群算法尋求最優路徑時參數選擇有所依據，同時也為其他使用者在參數設置時提供一定的依據和參考。并且找到蟻群算法參數的合理范圍，對于進一步推進蟻群算法的研究有重要的意義。

1? 蟻群算法的基本理論

蟻群算法（Ant Colony Optimization，ACO），又稱螞蟻算法，是由Dorigo和Colorni等人提出的，得益于螞蟻個體在尋找食物時，個體之間的相互協作運行方式所影響。以TSP為例，其主要思想是：假設有n個城市，m只螞蟻，這m只螞蟻能夠以一定的概率來選擇下一個城市，（t）為t時刻第k只螞蟻從城市i到訪問城市j的概率：

其中，τij（t）為t時刻路徑（i，j）上的信息素含量;ηij（t）為t時刻路徑（i，j）上的能見度，即路徑（i，j）的啟發信息，一般將其設為ηij=1/dij其中，dij為城市i到j之間的距離;allowedk為螞蟻k下一步可以訪問的城市;α為啟發因子，表示信息素的相對重要程度（α≥0）;β為期望因子，表示能見度的重要性（β≥0）。并且螞蟻在走過的這條線路上留下相應的信息素為：

其中，ρ為信息素的揮發系數（0<ρ<1），1-ρ為信息素的殘留系數， 為螞蟻k在路徑（i，j）上留下的信息素含量，Δτij為一次循環結束，所有走過路徑（i，j）上的螞蟻留下的信息素的和。對于 的設置，Dorigo等給出了三種不同的計算方法，分別是ant-cycle、ant-quantity和ant-density模型，根據學者們的研究經驗，ant-cycle模型即全局信息模型在求解過程中優于另外兩個模型。ant-cycle模型為：

最終得到一條較優的鏈接n個城市的線路。

2? 蟻群算法的參數分析

在蟻群算法中，需要設置大量的參數，參數的設置對算法的收斂速度和尋優能力均有影響，而且這些參數的設置至今沒有完整的理論支持，只能依靠大量的實驗測試和相關學者的經驗來參考取舍，如文獻[6]和大多數學者主要是以數據eil51 TSP為例，對ant-cycle的各個參數設置進行試驗研究分析;文獻[5]則是以數據TSP30為研究對象，對其中的參數設置進行研究分析。上述研究分別是針對不同規模的數據進行分析，沒有通用的參考性。本文將從橫向不同規模的數據和縱向單個數據來比較分析，利用TSPLIB測試庫的實驗數據為對象，主要對螞蟻總數m、啟發因子α、信息素揮發系數ρ和期望因子β進行分析。在研究參數對蟻群算法的性能時，統一采用的模型是ant-cycle模型，運行20次取平均和最小值。測試集有bayg29，berlin52、eil76和eil101，它們的城市規模分別為29、52、76和101。對于ant-cycle模型大多數學者認為最好的實驗結果是m=n，0≤α≤5，0≤β≤5，0.10≤ρ≤0.99。

2.1? 分析螞蟻總數m

在蟻群算法中，主要是依靠螞蟻對節點進行選擇，信息的交流與協作，然后在更新信息素，從而得到較優解，其中是將螞蟻分布在不同的城市上。在處理問題時，增加m的值時，會增加蟻群算法的全局搜索能力，但若m的值過大則會影響算法信息素的正反饋機制，從而導致收斂速度變慢，但若m的值過小，將加快算法的收斂速度，但容易陷入局部最優且全局搜索能力也會減弱。故需選擇適當m值。文獻[1]表明，當螞蟻數目遠遠大于城市數量即m>>n時，再增加螞蟻量對算法的性能有一定的提高，但效果不是很明顯。杜衡吉[4]研究得出，當m∈[0.75n，1.50n]時（其中n為城市數量），既可以保證算法的收斂速度，也可以得到較好的解，且此結果與文獻[2，3]一致。針對4組數據，固定m的取值，其他參數設置如表1所示。

圖1是各測試集最優路徑和螞蟻數目之間的關系圖，從圖1可以看出，當螞蟻數目很小的時候，算法不能得到最優解且其不穩定，當螞蟻數目逐漸增加，能得到最優解且其波動的范圍較小，但也可以發現如果螞蟻數目大于城市數目之后仍持續增加，其最優解并沒有得到較好的改善，反而增加了算法的運算量，降低了收斂速度。其中上面4組數據的最佳取值范圍分別是m∈[0.85n，1.20n]、m∈[0.80n，1.20n]、m∈[0.80n，1.20n]和m∈[0.70n，n]。故可以總結為，當城市規模小于100時，m∈[0.85n，1.20n]即可得到較優的結果，當大于100后，m∈[0.70n，n]既可得到較優的結果，也可加快收斂速度，即螞蟻數目應取小于數據規模的值。

2.2? 分析啟發因子α

啟發因子α反映的是螞蟻在選擇路徑時信息素τij（t）的相對重要程度，其大小是信息素對螞蟻選擇路徑的指導強度，也是螞蟻在搜索路徑中隨機性的強度。α越大，表明前面積累的信息量對螞蟻有很強的指導作用，隨機性減弱，收斂速度加快，易陷入局部最優。反之，則隨機性增強，收斂速度減慢，無法體現正反饋機制。陳文卓[5]研究表明，在n為30的情況下，當α∈[0.5，1.0]時，算法的整體性能較好;而文獻[4，6]得出，在n為51的情況下，α∈[1.0，3.0]時，算法的整體性能較好。固定α的取值范圍α=1.0：0.5：10.0，其他參數設置如表2所示。

在確定螞蟻數目和啟發式因子的范圍的情況下，由以上理論和圖2的仿真實驗可知，啟發式因子α過大或者過小都對算法的搜索和尋優造成不利的影響。對于上面4張圖其α的最佳取值范圍分別是α∈[1.0，4.5]、α∈[1.0，5.0]、α∈[1.0，3.0]和α∈[1.0，2.5]，即α的取值范圍一般在α∈[1.0，3.0]時能取得較優的值。

2.3? 分析期望因子β

期望因子β反映的是螞蟻在選擇路徑時啟發信息ηij（t）的相對重要程度，其大小是距離的倒數，反映了先驗知識對螞蟻選擇路徑的指導作用，也是螞蟻在搜索路徑中的確定性的因素。其值的大小影響著算法性能的優劣。文獻[4]得出，算法在β∈{3，4，5}時，性能較好。文獻[6]得出，在β∈{2，4}時效果較好，文獻[5]得出，在β∈{2，3，4，5}時性能較好。固定期望因子β的取值范圍為β=0.0：0.5：20.0，其他參數設置如表3所示。

由圖3的仿真實驗和以上理論可知，期望因子β是不宜過大也不宜過小，從圖3可以看出，當β大于一定值時其波動性未發生明顯的變化，說明其他的參數在影響著β的波動范圍。通過圖3中的四張圖期望因子的最佳取值范圍分別是β∈[1.0，2.5]、β∈[1.0，4.5]、β∈[1.0，4.5]和β∈[2，6]。

2.4? 分析信息素揮發系數ρ

信息素揮發系數ρ表示信息素在路徑上隨著時間逐漸揮發的程度，隨著迭代次數的增加，信息素將會累計。1-ρ表示信息素揮發之后剩下的部分信息素，值的大小間接反映了螞蟻個體之間相互關系的強弱。ρ值過大，則路徑上的信息素揮發就越多，這條路徑上的信息素濃度就越淡，減小了螞蟻之間的協作性，增強了算法的隨機性和全局搜索能力;ρ值過小，路徑上揮發的信息素較少，留下較多的信息素，增強了螞蟻之間的協作，算法的正反饋機制加強，隨機性減弱。對于這個參數幾乎不同的作者得出的結果都不相同，分別有ρ∈{0.1，0.15，[0.3，0.5]，[0.5，0.8]}。固定信息素揮發系數ρ的取值范圍ρ=0.00：0.05：0.95，其他參數的設置如表4所示。

由圖4的仿真實驗和以上理論可知，ρ值太大或者太小都會影響算法的全局搜索能力。通過圖4可以看出，測試集bayg29的最佳取值范圍為ρ∈[0.4，0.7]，測試集berlin52的最佳取值范圍是ρ∈[0.3，0.7]，測試集eil76的最佳取值點為0.85，而測試集eil101的最佳取值點則為0.75。

3? 結? 論

在蟻群算法中，參數設置的優劣直接決定算法的性能。本文對蟻群算法的基本原理和仿真實驗來分析參數的設置問題。得出結論：對于螞蟻數目m，當城市規模小于100時，m∈[0.85n，1.20n]，當大于100時，m∈[0.70n，n]算法性能較好，且m

參考文獻：

[1] 葉家琪，符強，賀亦甲，等.基于聚類集成的蟻群算法求解大規模TSP問題 [J].計算機與現代化，2020（2）：31-35.

[2] 杜玉紅，張巖，趙煥峰.基于參數優化蟻群算法的機器人路徑規劃研究 [J].現代制造工程，2020（9）：7-14.

[3] 四川旅游學院.基于模糊蟻群算法的旅游線路優化方法：CN201911035554.4 [P].2019-10-29.

[4] 杜衡吉，李勇.蟻群算法中參數設置對其性能影響的研究 [J].現代計算機（專業版），2012（13）：3-7.

[5] 陳文卓，劉萍，姜豐，等.基于參數組合優化的救援機器人蟻群算法研究 [J].華北科技學院學報，2020，17（1）：71-76.

[6] 黃少榮.蟻群算法的參數選擇研究 [J].電腦知識與技術，2010，6（20）：5588-5590.

作者簡介：向永靖（1992—），女，侗族，貴州凱里人，講師，碩士研究生，主要研究方向：數理統計、機器學習。