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

關(guān)鍵詞：蟻群算法;參數(shù)設(shè)置;TSP

中圖分類號(hào)：TP301.6? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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)能力、拓展性強(qiáng)、并行性和魯棒性，其應(yīng)用較為廣泛，并且該算法在解決離散問(wèn)題的同時(shí)也可以針對(duì)連續(xù)的問(wèn)題，且均可以得到較好的解。本文是在基于蟻群算法求解最優(yōu)旅游路徑的研究課題中，發(fā)現(xiàn)蟻群算法的復(fù)雜性，而算法解的優(yōu)劣很大程度上取決于算法中的參數(shù)設(shè)置，參數(shù)的選擇決定著算法的最優(yōu)解和收斂速度。并且沒(méi)有相關(guān)完整的可行性參考文獻(xiàn)提供參考，而這也是此算法進(jìn)一步突破的關(guān)鍵點(diǎn)。故有本篇研究，為的是在使用蟻群算法尋求最優(yōu)路徑時(shí)參數(shù)選擇有所依據(jù)，同時(shí)也為其他使用者在參數(shù)設(shè)置時(shí)提供一定的依據(jù)和參考。并且找到蟻群算法參數(shù)的合理范圍，對(duì)于進(jìn)一步推進(jìn)蟻群算法的研究有重要的意義。

1? 蟻群算法的基本理論

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

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

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

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

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

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

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

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

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

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

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

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

2.3? 分析期望因子β

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

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

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

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

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

3? 結(jié)? 論

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

參考文獻(xiàn)：

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

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

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

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

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

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

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