基于TSP的蟻群算法參數(shù)選擇問題分析

丁上凌++李斌

摘要：根據(jù)目前針對(duì)社會(huì)性動(dòng)物群體活動(dòng)的實(shí)驗(yàn)調(diào)查，發(fā)現(xiàn)其自組織行為廣泛存在，例如群體活動(dòng)較為頻繁的螞蟻，在群體覓食過程中能夠找到蟻穴到食物的最短路徑，即蟻群算法。文章圍繞蟻群算法在TSP中的應(yīng)用，就算法的參數(shù)選擇進(jìn)行了深入的研究。最后通過對(duì)全文的研究工作進(jìn)行了總結(jié)，并展望了其應(yīng)用價(jià)值及后期還需繼續(xù)研究的問題。

關(guān)鍵詞：蟻群算法 TSP 最短路徑 參數(shù)選擇

中圖分類號(hào)：TP183 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2016）12-0131-02

蟻群算法是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型算法。它由Marco Dorigo提出，它主要的依據(jù)就是螞蟻在覓食過程中能夠找到蟻穴到食物的最短路徑。螞蟻的視覺系統(tǒng)非常薄弱，幾乎可以說是瞎子，但是它們卻能發(fā)現(xiàn)食物與蟻穴之間最短的距離。生態(tài)學(xué)家的研究表明，螞蟻是借助信息素來實(shí)現(xiàn)這一點(diǎn)的。蟻群算法也越來越多被應(yīng)用到實(shí)際的問題中，并且取得了較好的效果，例如調(diào)度問題、著色問題、求解旅行商問題（TSP），并在大規(guī)模集成電路設(shè)計(jì)，通信路由控制等諸多領(lǐng)域表現(xiàn)出較好的性能。本文在介紹蟻群算法的基本原理的基礎(chǔ)上，主要分析了蟻群算法參數(shù)的選擇策略問題。

1 蟻群算法的基本原理

1.1 蟻群算法的原理

蟻群算法是從自然界啟發(fā)中得到的一種新型的模擬進(jìn)化算法，應(yīng)用該算法求解TSP問題取得了較好的結(jié)果?？茖W(xué)家發(fā)現(xiàn)雖然單個(gè)螞蟻無法掌握附近的地理信息，但整個(gè)蟻群卻可以找到一條從巢穴到食物源之間的最優(yōu)路線。經(jīng)過大量研究發(fā)現(xiàn)：螞蟻在運(yùn)動(dòng)過程中，能夠留下一種稱之為信息素的物質(zhì)，而且螞蟻在運(yùn)動(dòng)過程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上單位時(shí)間走過的螞蟻越多，表明該路線的可用性越好，則后來者選擇該路徑的概率就越大。蟻群算法具有實(shí)現(xiàn)簡(jiǎn)單、正反饋、分布式的優(yōu)點(diǎn)。

人工蟻群和自然界蟻群的相似之處在于，兩者優(yōu)先選擇的都是含“信息素”濃度較大的路徑。這在兩種情況下，較短的路徑上都能聚集比較多的信息素，受到上述情況的啟發(fā)，科研人員在此基礎(chǔ)上提出了蟻群算法，它不僅具有蟻群覓食行為中的信息傳遞功能，還具有自然界蟻群所沒有的記憶能力，即能夠保存已經(jīng)去過的地方和已經(jīng)走過的路徑，從而能夠更加智能的選擇下一地點(diǎn)和路徑，并且按照一定的規(guī)律總結(jié)出特有的算法進(jìn)行最短路徑的選擇。

1.2 基于TSP問題的蟻群算法數(shù)學(xué)模型

TSP問題又稱為旅行商問題，是數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)有一個(gè)旅行商人要拜訪M個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最終要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求旅行商人怎樣才能得到最短的路徑，取得最佳的利益。

根據(jù)信息素更新的策略不同，Dorigo M曾給出了不同的蟻群算法模型，分別稱為ant-cycle模型，ant-quantity模型和ant-density模型。它們的差別在于循環(huán)中路徑的信息素的增量的求法不同。

在ant-quantity模型中：

其中，是信息素強(qiáng)度，它影響算法的收斂速度是指兩座城市之間的歐氏距離，是指第只螞蟻所走的路徑長(zhǎng)度。ant-quantity和ant-density是利用局部信息完成求解運(yùn)算，ant-cycle是利用整體信息完成求解運(yùn)算。通過實(shí)驗(yàn)得到ant-cycle的模型比其他兩種模型效果好。

2 參數(shù)優(yōu)化策略

通過對(duì)蟻群算法基本原理及其數(shù)學(xué)模型的學(xué)習(xí)理解，可以使用MATLAB進(jìn)行蟻群算法求解TSP最短路徑問題的仿真試驗(yàn)工作，其主要任務(wù)是：根據(jù)城市的坐標(biāo)，使用蟻群算法求解TSP最優(yōu)化問題，并繪制最佳結(jié)果的路徑圖，生成平均距離和最短距離統(tǒng)計(jì)圖。

算法中的主要參數(shù)有：城市的個(gè)數(shù)，城市的坐標(biāo)（城市個(gè)數(shù)*2的矩陣），最大循環(huán)次數(shù)（即迭代的次數(shù)），螞蟻個(gè)數(shù)，表征信息素重要程度的參數(shù)，表征啟發(fā)因子（期望）重要程度的參數(shù)，信息素?fù)]發(fā)系數(shù)，信息素強(qiáng)度的系數(shù)（一般是一個(gè)常量），最佳路線的長(zhǎng)度。

實(shí)現(xiàn)步驟為：第一步：變量初始化；第二步：循環(huán)開始，判斷變量是否達(dá)到最大迭代次數(shù)，如果沒有達(dá)到，繼續(xù)下一步運(yùn)行，否則，循環(huán)結(jié)束；第三步：將所有螞蟻隨機(jī)放到所有城市上；第四步：所有螞蟻按概率函數(shù)選擇下一座城市，完成各自的周游；第五步：記錄本次迭代最佳路線；第六步：更新信息素；禁忌表清零，回到第二步，達(dá)到停止條件時(shí)跳到第七步；第七步：輸出結(jié)果。

仿真中采用最短路徑作為參考項(xiàng)，進(jìn)行多目標(biāo)測(cè)試得出結(jié)果，并由結(jié)果分析出蟻群算法中的參數(shù)如何選擇優(yōu)化。

2.1 缺省值的選擇

在實(shí)驗(yàn)過程中，本文在進(jìn)行參數(shù)選擇時(shí)，取城市個(gè)數(shù)為20，迭代次數(shù)為100，螞蟻個(gè)數(shù)為15，信息素重要程度為1，啟發(fā)因子重要程度為1，信息素?fù)]發(fā)系數(shù)為0.15，信息素強(qiáng)度的系數(shù)為100，并設(shè)定20個(gè)城市坐標(biāo)為（602，972）（989，483）（54，550）（95，868）（529，430）（982，351）（654，23）（738，372）（539，594）（560，850）（229，806）（411，710）（83，706）（937，801）（12，994）（694，809）（795，759）（339，148）（956，644）（346，726）。

多次運(yùn)行程序后，求得最佳路線的長(zhǎng)度的最優(yōu)解為4148.6，使用其作為缺省值，以此在下面進(jìn)行參數(shù)關(guān)系選擇時(shí)作為對(duì)比參考值。

2.2 迭代次數(shù)的選擇

由于蟻群算法中迭代的重要性，所以選取合適的迭代次數(shù)可以在較少耗費(fèi)系統(tǒng)資源的同時(shí)得到較優(yōu)的解。經(jīng)過試驗(yàn)可以得出在迭代次數(shù)太少時(shí)，求出的解與最優(yōu)解相差很大，這是由于迭代次數(shù)太少時(shí)，解還未收斂造成的。當(dāng)?shù)螖?shù)太多時(shí)，其耗費(fèi)了大量系統(tǒng)資源，但是求出的解已基本不再變化，甚至有時(shí)出現(xiàn)抖動(dòng)，求出不優(yōu)解。所以合適選取迭代次數(shù)的值非常重要，在其他參數(shù)采用缺省值的情況下，可以通過實(shí)驗(yàn)得出選取110次左右的迭代次數(shù)較好。

2.3 信息素重要程度與啟發(fā)因子重要程度參數(shù)的關(guān)系選擇

從上述分析過程來看，我們所取的參數(shù)只是針對(duì)某一方面，參數(shù)較為單一，沒有考慮不同參數(shù)值的組合所能呈現(xiàn)的不同效果，所以，接下來，本文就這一問題的缺陷性，對(duì)信息素重要程度與啟發(fā)因子重要程度參數(shù)的關(guān)系選擇進(jìn)行了重新組合，在試驗(yàn)過程中，取不同組合的信息素重要程度α與啟發(fā)因子重要程度β參數(shù)組合，求最短路徑長(zhǎng)度的最優(yōu)解，其中，α在1到3之間取值，β在3到5之間取值，進(jìn)行排列組合取值，特別地，α和β同時(shí)取1作為缺省值，即總共有10種情況。經(jīng)過多次試驗(yàn)得出：α和β的值為（1，1）、（1，4）、（1，5）時(shí)均能取得較好的解。

2.4 螞蟻個(gè)數(shù)與城市個(gè)數(shù)的關(guān)系選擇

經(jīng)過實(shí)際應(yīng)用可以知道，螞蟻的個(gè)數(shù)與城市個(gè)數(shù)影響著TSP的求解，當(dāng)少數(shù)螞蟻在較大的城市中運(yùn)動(dòng)，它們所能得到的信息是有限的，這時(shí)算法不穩(wěn)定，容易出現(xiàn)早停滯現(xiàn)象。相反，當(dāng)大量的螞蟻在較小的城市運(yùn)動(dòng)，它們雖然能夠搜索的較為全面的信息，但是浪費(fèi)了資源，收斂速度慢。本文選取螞蟻個(gè)數(shù)/城市個(gè)數(shù)為0.5、1.5、2.5進(jìn)行比較，經(jīng)多次實(shí)驗(yàn)可以得出在城市數(shù)較少的系統(tǒng)中，螞蟻數(shù)的變化對(duì)其影響較小，而在城市數(shù)較多的系統(tǒng)中時(shí)，螞蟻數(shù)/城市數(shù)為1.5時(shí)可以取得較好的解，如表1所示。

在通信系統(tǒng)中，路由是關(guān)鍵的組件之一，它涉及到建立和使用路由表來指導(dǎo)數(shù)據(jù)通信量在網(wǎng)絡(luò)范圍內(nèi)的分配活動(dòng)。普通路由問題可以理解為是要建立一個(gè)路由表使得網(wǎng)絡(luò)性能的一些量度最大化，是基于TSP的蟻群算法的重要應(yīng)用。

3 結(jié)論和展望

蟻群算法易于與其他算法融合，在實(shí)際應(yīng)用中參數(shù)對(duì)最優(yōu)路徑的選擇有較大的影響，本文針對(duì)蟻群的參數(shù)選擇問題進(jìn)行分析，經(jīng)過試驗(yàn)得到了一些參數(shù)的最佳取值范圍。在以后的研究中可以將其應(yīng)用于路由選擇協(xié)議中，并考慮更多的網(wǎng)絡(luò)實(shí)際情況，加入流量控制、網(wǎng)絡(luò)擁塞等將其應(yīng)用于實(shí)際之中，以取得更為準(zhǔn)確的測(cè)試結(jié)果。

參考文獻(xiàn)

[1]高博，盧輝斌.改進(jìn)型粒子蟻群算法的應(yīng)用研究[J].計(jì)算機(jī)安全，2010（11）：11-13.

[2]王戈，徐俊剛.基于路徑選擇的自適應(yīng)蟻群算法研究[J].電子技術(shù)，2010，37（1）：14-16.

[3]葉菁.基于免疫-蟻群算法的TSP問題研究.[J].計(jì)算機(jī)工程，2010，36（24）：156-157+160.