◆楊昌昊 張 琢

基本蟻群算法在解決TSP問(wèn)題中參數(shù)選擇的研究

◆楊昌昊 張 琢

（東北師范大學(xué)信息科學(xué)與技術(shù)學(xué)院 吉林 130117）

蟻群算法是受自然界中真實(shí)蟻群覓食行為的啟發(fā)而提出的一種優(yōu)化算法，基本蟻群算法是其中基礎(chǔ)且較為經(jīng)典的一種算法，而基本蟻群算法中的參數(shù)對(duì)算法效果有很大的影響。本文以使用基本蟻群算法解決TSP問(wèn)題為例，在對(duì)相關(guān)內(nèi)容進(jìn)行介紹后，進(jìn)而對(duì)基本蟻群算法的參數(shù)選擇進(jìn)行了實(shí)驗(yàn)及分析，最終給出了基本蟻群算法中各個(gè)參數(shù)的基本選擇范圍。

蟻群算法；基本蟻群算法；TSP問(wèn)題

0 引言

啟發(fā)式算法(Heuristic algorithm)是一類(lèi)基于生物學(xué)、物理學(xué)和人工智能的，具有全局優(yōu)化性能、魯棒性強(qiáng)、通用性強(qiáng)且適用于并行處理的算法[1]?，F(xiàn)階段，啟發(fā)式算法以仿生優(yōu)化算法[2]為主，主要包括模擬退火算法[3]、粒子群算法[4]、遺傳算法[5]、混合蛙跳算法[6]、蟻群算法等。

蟻群算法(Ant colony optimization algorithm)是受自然界中真實(shí)蟻群覓食行為的啟發(fā)，發(fā)現(xiàn)雖然單個(gè)螞蟻沒(méi)有太多的智力，也無(wú)法掌握附近的地理信息，但整個(gè)蟻群卻可以找到一條從巢穴到食物源之間的最優(yōu)路線而提出的一種仿生優(yōu)化算法[7]。

在蟻群算法的研究中，研究者們常以TSP問(wèn)題作為該算法的運(yùn)行實(shí)例。TSP (Traveling salesman problem)問(wèn)題又稱(chēng)為旅行商問(wèn)題，是一種比較經(jīng)典的NP難題，問(wèn)題描述較簡(jiǎn)單，而獲得最優(yōu)解卻十分困難。求解TSP問(wèn)題不僅為其他算法提供了使用平臺(tái)，而且算法的優(yōu)劣性能也可通過(guò)其求得TSP問(wèn)題的解集來(lái)驗(yàn)證。TSP問(wèn)題的經(jīng)典描述為：已知N個(gè)城市及相互間的距離，旅行商從某城市出發(fā)遍歷這N個(gè)城市后再回到原點(diǎn)，在旅行商每個(gè)城市都只訪問(wèn)一次的前提下確定一條最短路徑[8]。本文也將以TSP問(wèn)題作為基本蟻群算法中對(duì)參數(shù)設(shè)計(jì)方案進(jìn)行驗(yàn)證的運(yùn)行實(shí)例。

基本蟻群算法是蟻群算法中最經(jīng)典且基礎(chǔ)的一種，在使用基本蟻群算法解決TSP問(wèn)題時(shí)，算法中的各個(gè)參數(shù)對(duì)算法的效果有很大影響，在Wei Xianmin所著論文[9]中便提到了蟻群數(shù)量、信息素重要程度系數(shù)及兩城市間距離重要程度系數(shù)三個(gè)參數(shù)算法效果的影響，并給出了實(shí)驗(yàn)數(shù)據(jù)。但對(duì)于全部參數(shù)對(duì)算法的影響情況，目前暫未有論文進(jìn)行實(shí)驗(yàn)論證。

因此，本文將對(duì)基本蟻群算法的執(zhí)行流程、影響算法執(zhí)行的參數(shù)進(jìn)行介紹，并對(duì)相關(guān)參數(shù)進(jìn)行一系列實(shí)驗(yàn)與分析，最終得出使用基本蟻群算法解決TSP問(wèn)題時(shí)參數(shù)的基本選擇范圍。

1 基本蟻群算法模型介紹

1.1基本蟻群算法簡(jiǎn)介

基本蟻群算法通過(guò)模擬自然界的螞蟻覓食過(guò)程對(duì)目標(biāo)進(jìn)行搜索，人工螞蟻會(huì)根據(jù)路徑上的信息素濃度的函數(shù)，按概率選擇下一個(gè)將要訪問(wèn)的城市，信息素濃度越高，則該路徑被選擇的概率越大。當(dāng)人工螞蟻進(jìn)行完一次循環(huán)后，其會(huì)在其訪問(wèn)過(guò)的每條邊上都留下相應(yīng)的信息素。

1.2基本蟻群算法執(zhí)行流程

（1）初始化

算法開(kāi)始時(shí)，將m只螞蟻隨機(jī)的放到n座城市中。將每只螞蟻k的禁忌表tabuk的第一個(gè)元素設(shè)置為當(dāng)前它所在的城市，下一步允許選擇的城市表allowedk設(shè)為除當(dāng)前它所在的城市外的所有城市。同時(shí)，將各條路徑上的信息素量統(tǒng)一設(shè)為一較小的常數(shù)。該常數(shù)的選擇有很多種方式，本文中選為1/(m*n)。

（2）每只螞蟻獨(dú)立的選擇一次周游的路徑

每只螞蟻按照各條路徑上的信息素量、兩城市間的距離及其相關(guān)的參數(shù)獨(dú)立的選擇下一座城市。在時(shí)刻t，螞蟻k在城市i上選擇城市j的概率Pijk(t)為：

其中，allowedk表示螞蟻k下一步允許選擇的城市，即在所有城市中減去禁忌表tabuk中的城市，α代表信息素的相對(duì)重要程度，β代表兩城市間距離的相對(duì)重要程度。

當(dāng)allowedk變?yōu)榭諘r(shí)，即完成了一次周游。

（3）每只螞蟻獨(dú)立的選擇一次周游的路徑

當(dāng)全部m只螞蟻都完成一次循環(huán)之后，各路徑上的信息素將會(huì)根據(jù)下式進(jìn)行更新：

其中，ρ代表信息素的殘留系數(shù)。關(guān)于Δτijk的計(jì)算方法，M.Dorigo給出了三種不同的實(shí)現(xiàn)方法，分別對(duì)應(yīng)三種不同的螞蟻系統(tǒng)模型[11]：Ant-cycle模型、Ant-density模型及Ant-quantity模型。它們的計(jì)算方法如下：

在Ant-quantity模型中：

在Ant-density模型中：

在Ant-cycle模型中：

上面的三個(gè)公式中，Q為一正常數(shù)，表示螞蟻循環(huán)一周所釋放的信息素總量。Lk表示螞蟻k在本次循環(huán)中所經(jīng)過(guò)的路徑的長(zhǎng)度。

2 基本蟻群算法中各參數(shù)對(duì)算法性能影響的研究

在蟻群算法中，算法運(yùn)行參數(shù)的選取對(duì)算法性能有著至關(guān)重要的影響。對(duì)于不同的優(yōu)化問(wèn)題，算法的參數(shù)選取不同。即使對(duì)于同一類(lèi)型優(yōu)化問(wèn)題，由于問(wèn)題規(guī)模不一樣，算法的參數(shù)選取也不盡相同[12]。

本文使用TSPLIB提供的att48數(shù)據(jù)集，針對(duì)基本蟻群算法中各個(gè)參數(shù)的不同取值進(jìn)行了大量實(shí)驗(yàn)，意圖找出參數(shù)選擇的規(guī)律。

att48數(shù)據(jù)集包含美國(guó)本土48州州府的地理位置坐標(biāo)，其最優(yōu)解為10628。

2.1實(shí)驗(yàn)硬件、軟件環(huán)境

實(shí)驗(yàn)使用MacBook Pro (Retina, 13-inch, Early 2013)型計(jì)算機(jī)，處理器為2.6 GHz Intel Core i5，內(nèi)存為8 GB 1600 MHz DDR3。操作系統(tǒng)為macOS High Sierra 10.13.2，JDK版本為JDK 1.7.0_80。

2.2蟻群數(shù)量對(duì)算法性能的影響

蟻群算法是一種并行隨機(jī)搜索算法, 它是通過(guò)多個(gè)候選解組成的群體進(jìn)化過(guò)程來(lái)搜索最優(yōu)解。蟻群數(shù)量越大可以提高蟻群算法的全局搜索能力以及算法的穩(wěn)定性，但螞蟻數(shù)目增加到一定程度以后，會(huì)使大量的曾被搜索過(guò)的解(路徑)上的信息量的變化比較平均，信息正反饋的作用不明顯，搜索的隨機(jī)性增強(qiáng)，造成收斂速度變慢。反之，蟻群數(shù)量越小，特別是當(dāng)要處理的問(wèn)題規(guī)模比較大時(shí)，會(huì)使那些從來(lái)沒(méi)被搜索到的路徑上信息素量減小到接近0，搜索的隨機(jī)性減弱，雖然收斂速度較快，但是會(huì)使算法的全局性能降低。

為了研究蟻群數(shù)量對(duì)算法性能的影響，將算法中其他的參數(shù)固定(采用Ant-quantity模型，迭代次數(shù)=100次，ρ=0.5，α=1.0，β=10，Q=10)，針對(duì)att48數(shù)據(jù)集，對(duì)不同的蟻群數(shù)量各進(jìn)行10次測(cè)試，結(jié)果如下表1：

表1 蟻群數(shù)量對(duì)算法性能的影響

根據(jù)實(shí)驗(yàn)結(jié)果可見(jiàn)，當(dāng)螞蟻數(shù)量小于30時(shí)，隨著蟻群數(shù)量的不斷增大，100次迭代后得到的平均路徑長(zhǎng)度不斷優(yōu)化，而當(dāng)螞蟻數(shù)量超過(guò)30時(shí)，螞蟻數(shù)量對(duì)于結(jié)果的影響開(kāi)始變得不再那么明顯。耗時(shí)方面，每增加5個(gè)螞蟻，耗時(shí)約增加4秒。因而，針對(duì)att48數(shù)據(jù)集，考慮效果與耗時(shí)，可將螞蟻數(shù)目設(shè)為30個(gè)，即約0.6倍的城市數(shù)目。

2.3算法模型對(duì)算法性能的影響

三種算法模型中，關(guān)于信息素增量的算法截然不同，因而可能會(huì)對(duì)算法結(jié)果產(chǎn)生較大的影響。

在Ant-quantity模型中，從城市i到城市j的螞蟻在路徑上的信息素增量為一個(gè)與路徑無(wú)關(guān)的常量Q。在Ant-density模型中，從城市i到城市j的螞蟻在路徑上的信息素增量為Q/dij，dij為城市i到城市j的距離，因而信息素增量會(huì)隨著城市間距離的不同而變化。在Ant-cycle模型中，從城市i到城市j的螞蟻在路徑上的信息素增量為Q/Lk，由于Lk為第k只螞蟻在該次循環(huán)中所走過(guò)的路徑的總長(zhǎng)度，因此信息素增量與該次循環(huán)中所獲得解循環(huán)路徑的優(yōu)劣有關(guān)，更新規(guī)則會(huì)讓短路經(jīng)較優(yōu)的解上對(duì)應(yīng)的信息素量逐步增加。

為了研究算法模型對(duì)算法性能的影響，將算法中其他的參數(shù)固定(蟻群數(shù)量=30，迭代次數(shù)=100次，ρ=0.5，α=1.0，β=10，Q=10)，針對(duì)att48數(shù)據(jù)集，對(duì)不同的算法模型各進(jìn)行10次測(cè)試，結(jié)果如下表2：

表2 算法模型對(duì)算法性能的影響

根據(jù)實(shí)驗(yàn)結(jié)果可見(jiàn)，當(dāng)螞蟻數(shù)量小于30時(shí)，隨著蟻群數(shù)量的不斷增大，100次迭代后得到的平均路徑長(zhǎng)度不斷優(yōu)化，而當(dāng)螞蟻數(shù)量超過(guò)30時(shí)，螞蟻數(shù)量對(duì)于結(jié)果的影響開(kāi)始變得不再那么明顯。耗時(shí)方面，每增加5個(gè)螞蟻，耗時(shí)約增加4秒。因而，針對(duì)att48數(shù)據(jù)集，考慮效果與耗時(shí)，可將螞蟻數(shù)目設(shè)為30個(gè)，即約0.6倍的城市數(shù)目。

2.4信息素殘留系數(shù)(ρ)對(duì)算法性能的影響

在蟻群算法中，人工螞蟻是具有記憶功能的，隨著時(shí)間的推移，以前留下的信息素將逐步消逝。當(dāng)信息素殘留系數(shù)(ρ)過(guò)大時(shí)，以前被搜索過(guò)的解被選擇的可能性過(guò)大，會(huì)影響到算法的隨機(jī)性能和全局搜索能力。反之，當(dāng)ρ過(guò)小時(shí)，雖然可以提高算法的隨機(jī)性能和全局搜索能力，但又會(huì)使算法的收斂速度降低。因此，選擇一個(gè)合適的信息素殘留系數(shù)是十分必要的。

為了研究信息素殘留系數(shù)對(duì)算法性能的影響，將算法中其他的參數(shù)固定(采用Ant-quantity模型，蟻群數(shù)量=30，迭代次數(shù)=100次，α=1.0，β=10，Q=10)，針對(duì)att48數(shù)據(jù)集，對(duì)不同的信息素殘留系數(shù)各進(jìn)行10次測(cè)試，結(jié)果如下表3：

表3 ρ對(duì)算法性能的影響

根據(jù)實(shí)驗(yàn)結(jié)果可見(jiàn)，針對(duì)att48數(shù)據(jù)集，信息素殘留系數(shù)為0.5時(shí)，平均路徑長(zhǎng)度最小，而五組不同的ρ值對(duì)于耗時(shí)幾乎不存在影響。因而，本文認(rèn)為，信息素殘留系數(shù)設(shè)為0.5較優(yōu)，原因在于，每只螞蟻需要忘記過(guò)去獲得的一部分經(jīng)驗(yàn)，避免螞蟻過(guò)早的收斂到一個(gè)局部最優(yōu)解，使得螞蟻可以更好的探索新引入的全局信息。

2.5信息素重要程度系數(shù)(α)對(duì)算法性能的影響

信息素重要程度系數(shù)(α)的大小反映了在蟻群路徑搜索中的隨機(jī)性因素作用的強(qiáng)度，其值越大，螞蟻選擇以前走過(guò)的路徑的可能性也越大，搜索的隨機(jī)性減弱。因而，α值過(guò)大會(huì)使蟻群的搜索過(guò)早陷于局部最優(yōu)。

為了研究信息素重要程度系數(shù)對(duì)算法性能的影響，將算法中其他的參數(shù)固定(采用Ant-quantity模型，蟻群數(shù)量=30，迭代次數(shù)=100次，ρ=0.5，β=10，Q=10)，針對(duì)att48數(shù)據(jù)集，對(duì)不同的信息素重要程度系數(shù)各進(jìn)行10次測(cè)試，結(jié)果如下表4：

表4 α對(duì)算法性能的影響

根據(jù)實(shí)驗(yàn)結(jié)果可見(jiàn)，針對(duì)att48數(shù)據(jù)集，信息素重要程度系數(shù)為1.0時(shí)，平均路徑長(zhǎng)度最小，而六組不同的α值對(duì)于耗時(shí)的影響不大。因而，本文認(rèn)為，信息素重要程度系數(shù)設(shè)為1.0左右較優(yōu)。原因在于，α過(guò)小時(shí)，而且算法易陷入局部最優(yōu)解；而α過(guò)大時(shí)，局部最優(yōu)路徑上的正反饋?zhàn)饔煤軓?qiáng)，算法會(huì)出現(xiàn)過(guò)早收斂，同樣對(duì)結(jié)果存在負(fù)影響。

2.6兩城市間距離重要程度系數(shù)(β)對(duì)算法性能的影響

兩城市間距離(β)的大小反映了在蟻群路徑搜索中確定性因素作用的強(qiáng)度，其值越大，螞蟻在某個(gè)局部點(diǎn)上選擇局部最短路徑的可能性越大，盡管搜索的收斂速度加快，但蟻群在最優(yōu)路徑的搜索過(guò)程中的隨機(jī)性減弱，易于陷入局部最優(yōu)。

為了研究?jī)沙鞘虚g距離重要程度系數(shù)對(duì)算法性能的影響，將算法中其他的參數(shù)固定(采用Ant-quantity模型，蟻群數(shù)量=30，迭代次數(shù)=100次，ρ=0.5，α=1.0，Q=10)，針對(duì)att48數(shù)據(jù)集，對(duì)不同的兩城市間距離重要程度系數(shù)各進(jìn)行10次測(cè)試，結(jié)果如下表5：

表5 β對(duì)算法性能的影響

根據(jù)實(shí)驗(yàn)結(jié)果可見(jiàn)，針對(duì)att48數(shù)據(jù)集，在兩城市間距離重要程度系數(shù)小于10時(shí)，隨著β值的增長(zhǎng)，效果迅速優(yōu)化；而當(dāng)β值超過(guò)10后，β值對(duì)于結(jié)果開(kāi)始呈現(xiàn)負(fù)影響。因而，本文認(rèn)為，兩城市間距離重要程度系數(shù)設(shè)為10左右較優(yōu)，既保證了一定的隨機(jī)性，又保證了路徑搜索中確定性因素作用的強(qiáng)度。

2.7螞蟻循環(huán)一周在經(jīng)過(guò)的路徑上釋放的信息素總量(Q)對(duì)算法性能的影響

螞蟻循環(huán)一周在經(jīng)過(guò)的路徑上釋放的信息素總量(Q)越大，則在螞蟻所走過(guò)的路徑上的信息素的累積加快，因而可以加強(qiáng)蟻群搜索時(shí)的正反饋性能，有助于算法的快速收斂。但一般認(rèn)為，蟻群算法參數(shù)中對(duì)算法性能起主要作用是α、β及ρ三個(gè)參數(shù)，而總信息量對(duì)算法性能的影響有賴(lài)于以上三個(gè)參數(shù)的配置，對(duì)算法性能的影響不大。

為了研究Q值對(duì)算法性能的影響，將算法中其他的參數(shù)固定(采用Ant-quantity模型，蟻群數(shù)量=30，迭代次數(shù)=100次，ρ=0.5，α=1.0，β=10)，針對(duì)att48數(shù)據(jù)集，對(duì)不同的Q值各進(jìn)行10次測(cè)試，結(jié)果如下：

表6 Q對(duì)算法性能的影響

根據(jù)實(shí)驗(yàn)結(jié)果可見(jiàn)，針對(duì)att48數(shù)據(jù)集，Q值在1~20之間時(shí)，對(duì)結(jié)果的影響的影響十分微弱，直到Q值為50時(shí)，結(jié)果才有較為明顯的劣化。而在耗時(shí)方面，Q值幾乎對(duì)耗時(shí)不存在任何影響。因而在實(shí)際使用時(shí)，Q值可以在1~20之間靈活的選取。

3 結(jié)束語(yǔ)

在基本蟻群算法的實(shí)際使用中，參數(shù)對(duì)算法效果有十分顯著的影響，若選擇不當(dāng)，則容易暴露出其存在的但搜索時(shí)間長(zhǎng)、易陷于局部最優(yōu)解的缺點(diǎn)。本文通過(guò)一系列的實(shí)驗(yàn)，研究了在att48數(shù)據(jù)集下參數(shù)的設(shè)置對(duì)蟻群算法性能的影響。實(shí)驗(yàn)結(jié)果表明，基本蟻群算法中參數(shù)的最優(yōu)設(shè)置為：蟻群數(shù)量約為0.6倍城市數(shù)量，信息素重要程度系數(shù)(α)約為1.0左右，兩城市間距離重要程度系數(shù)(β)約為10左右，信息素殘留系數(shù)(ρ)約為0.5左右，螞蟻循環(huán)一周在經(jīng)過(guò)的路徑上釋放的信息素總量(Q)可以在1~20之間靈活的選取。算法模型方面，若Ant-cycle模型的效果較其他兩者優(yōu)勢(shì)較大，則應(yīng)選擇Ant-cycle模型；若效果優(yōu)勢(shì)不大，則可考慮選擇耗時(shí)較短的其他兩種模型。

[1]叢明煜，王麗萍.現(xiàn)代啟發(fā)式算法理論研究[J].高技術(shù)通訊, 2003.

[2]熊偉平，曾碧卿.幾種仿生優(yōu)化算法的比較研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2010.

[3]馮玉蓉.模擬退火算法的研究及其應(yīng)用[D].昆明理工大學(xué)，2005.

[4]梁軍.粒子群算法在最優(yōu)化問(wèn)題中的研究[D].廣西師范大學(xué)，2008.

[5]王銀年.遺傳算法的研究與應(yīng)用[D].江南大學(xué)，2009.

[6]鄒采榮，張瀟丹，趙力.混合蛙跳算法綜述[J].信息化研究，2012.

[7]吳慶洪，張穎，馬宗民.蟻群算法綜述[J].微計(jì)算機(jī)信息， 2011.

[8]吳華鋒，陳信強(qiáng)，毛奇凰等.基于自然選擇策略的蟻群算法求解TSP問(wèn)題[J].通信學(xué)報(bào)，2013.

[9]Wei Xianmin. Parameters Analysis for Basic Ant Colony Optimization Algorithm in TSP[J]. International Journal of u-and e-Services, Science and Technology, Vol.7, No.4 (2014).

[10]楊劍峰.蟻群算法及其應(yīng)用研究[D].浙江大學(xué)，2007.

[11]劉乃文，王奎峰.蟻群優(yōu)化算法及其應(yīng)用[J].山東師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2006.

[12]劉利強(qiáng)，戴運(yùn)桃，王麗華.蟻群算法參數(shù)優(yōu)化[J].計(jì)算機(jī)工程，2008.