蟻群算法中參數(shù)設(shè)置的研究

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

關(guān)鍵詞：蟻群算法;參數(shù)設(shè)置;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? 引? 言

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

1? 蟻群算法的基本理論

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

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

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

最終得到一條較優(yōu)的鏈接n個城市的線路。

2? 蟻群算法的參數(shù)分析

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

2.1? 分析螞蟻總數(shù)m

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

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

2.2? 分析啟發(fā)因子α

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

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

2.3? 分析期望因子β

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

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

2.4? 分析信息素揮發(fā)系數(shù)ρ

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

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

3? 結(jié)? 論

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

參考文獻：

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

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

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

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

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

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

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