分層遞進(jìn)的改進(jìn)聚類蟻群算法解決TSP問題

粱藝瓊

摘要：現(xiàn)在社會不斷的發(fā)展和進(jìn)步，關(guān)于旅行商的問題（TSP）規(guī)模也在不斷地變多，傳統(tǒng)的蟻群算法已經(jīng)不能滿足現(xiàn)在的要求，在工作的時候經(jīng)常會出現(xiàn)一些力不從心的情況出現(xiàn)，在這樣的背景下，人們開始慢慢找到一些新的解決辦法，分層遞進(jìn)就是這個時候出現(xiàn)的產(chǎn)物。分層遞進(jìn)能夠有效地解決TSP的問題。分層遞進(jìn)算法是人們根據(jù)分工合作的原理想出來的一種方法。

關(guān)鍵詞：分層遞進(jìn);蟻群算法;TSP問題

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2020）05-0197-03

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

TSP問題屬于一種NP難問題。分析NP難問題的時候主要依靠的是仿生進(jìn)化思想，仿生進(jìn)化思想中主要以蟻群算法為主。蟻群算法最開始的時候是在一個博士論文中提出的結(jié)論。從1992年提出到現(xiàn)在，研究的人們一直在不斷地分析和改善蟻群算法，爭取用最好的讓蟻群算法用最好的狀態(tài)來解決TSP問題。

1 蟻群算法的歷史

傳統(tǒng)的蟻群算法雖然也能夠解決TSP出現(xiàn)的問題，凡是在解決的時候會花費很多的時間，在運算上也有很大的難度，所以更多的研究者開始希望能夠找出一些多種智能的方法來提高運算的性能。有的研究者認(rèn)為，蟻群算法應(yīng)該和30pt-起合作使用，通過30pt算法來提高蟻群算法的一個準(zhǔn)確度，這樣就能減少在計算時候出現(xiàn)的一些誤差情況。但是這樣合作的算法有一個缺點就是在計算的時候需要大量的仿真設(shè)備來支持，這樣就會在一定程度上加大工作的成本。還有的研究者認(rèn)為：可以利用粒子群算法來解決蟻群算法出現(xiàn)的漏洞，進(jìn)而給蟻群算法找到更多的出路，之后在用30pt算法來優(yōu)化，這樣的算法雖然解決了TSP問題的解經(jīng)度，但同時也增加了運算的時間，有的時候如果TSP的問題增加規(guī)模的時候還會影響運轉(zhuǎn)。還有的人認(rèn)為可以把融合遺傳算法和模擬退火等方法混合在一起解決TSP的問題。具體的辦法就是首先用模擬退火優(yōu)化最開始的路徑，通過一段時間之后在用粒子群算法進(jìn)行優(yōu)化，優(yōu)化出來的信息素在進(jìn)行迭代運行。

這樣綜合的方法雖然能解決TSP出現(xiàn)的問題，但還是不能縮短運算的時間。還有的人認(rèn)為可以通過改進(jìn)蟻群算法里面的信息素更新來解決存在的TSP問題，這樣除了能夠加快運算的速度，還能擴大種群的多樣性，讓算法的搜索能力變大，但是還是不能解決計算的復(fù)雜性問題。在無數(shù)次的試驗之后最終人們終于找出一種辦法就是利用分工合作的方式把一些相對來說比較大的TSP案例進(jìn)行一個分組歸納在運用蟻群算法來解決TSP問題，這樣的方法既能保證解決問題的精準(zhǔn)度又能加快算法運算的時間，還能降低算法的時間復(fù)雜度，是目前為止最好的解決TSP問題的方法。

2 關(guān)于TSP問題的內(nèi)容

TSP問題是典型的組合優(yōu)化問題，通過一些數(shù)學(xué)計算的方法整編、分組、排序處理一些離散的事情。TSP問題的前提是只給旅行者在特定的城市中拜訪一次的機會。給定的城市數(shù)量越大就會增加越多的空間復(fù)雜度和時間復(fù)雜度。在解決TSP問題的時候一般可以通過兩種方法：精確算法和啟發(fā)式的算法。精確算法適合一些小規(guī)模的TSP問題，啟發(fā)式算法適合一些大規(guī)模的TSP問題。精確算法包含很多的算法，最常用的就是蟻群算法，蟻群算法的出現(xiàn)給TSP問題提供更多的幫助。

3 蟻群算法解決TSP問題的過程

1）蟻群算法解決TSP問題的公式為：

在根據(jù)公式的要求設(shè)置一個最大的迭代次數(shù)，這樣在運行迭代次數(shù)達(dá)到最大值的時候就可以結(jié)束運行，最后獲得一個最優(yōu)解的算法。如果在計算的時候有一些停滯的現(xiàn)象發(fā)生，就需要重新開始運行，最后達(dá)到想要的要求。

2）密度峰聚類算法：

密度峰聚類算法就是在一個數(shù)據(jù)集里面，有一些地局部密度的數(shù)據(jù)點包圍了聚類中心，這些地局部密度的點就會和一些高局部密度的點出現(xiàn)很大的距離。具體的局部密度公式為：與高密度點之間的距離公式為：

3） 30pt算法：

優(yōu)化TSP問題的時候還可以使用30pt算法。在運算的時候能夠準(zhǔn)確地找出和組合出一些節(jié)點進(jìn)行連接，重新組合后的連接情況要及時的記錄。在對比重新組合后的數(shù)據(jù)和最初的數(shù)據(jù)進(jìn)行分析，找出一個最合適的線路。

4）粒子群算法：

要想適應(yīng)社會可以選擇粒子群算法，這種算法在計算的時候會先設(shè)置一組種群粒子拜訪指定區(qū)域，這樣就會讓每一個位置都有能夠計算的適應(yīng)值。在計算的時候主要的公式為：

4 改進(jìn)算法

隨著TSP問題在不斷擴大，蟻群算法的復(fù)雜程度也會相應(yīng)地進(jìn)行一定程度的提升。當(dāng)TSP問題的一個節(jié)點數(shù)超過100的時候就很難找到蟻群算法的一個平衡點，在TSP問題中城市節(jié)點小于40的時候是運行時間最佳和解決問題最佳的時候。

1）改進(jìn)后的密度峰聚類算法：

改進(jìn)后的密度峰聚類算法主要公式為：

y_{i ^{=ρi xδi}}

2）改進(jìn)的蟻群算法：

改進(jìn)的蟻群算法公式為：

τ_{ij^{（t+1） =（l -ρ）τij（t）+p△rij（t）}}

3）改進(jìn)算法的流程圖：

如圖l是DP-ACS算法解決TSP問題的步驟：

從圖中可以知道改進(jìn)算法首先要先設(shè)置一個初始的參數(shù)值，然后在根據(jù)問題制定相應(yīng)的節(jié)點坐標(biāo)，之后在根據(jù)截斷距離的定義計算，最后根據(jù)改進(jìn)的密度蜂聚類算法確定一個拐點，之后根據(jù)選舉出的聚類中心變成簇。因為每個簇包含的節(jié)點都不一樣，所以要用粒子群的算法來進(jìn)行設(shè)定，最后找出解決問題的方法。

之后把所有形成的二類TSP問題進(jìn)行重組，最后形成全局解路徑，之后再把二類的TSP問題還原成初始的TSP問題，解路徑在區(qū)域連接重新融合。最后將重新連接后的全局路徑通過30pt的處理，達(dá)到重新連接優(yōu)化的目的，再看算法辨別有沒有達(dá)到預(yù)先設(shè)置的要求，如果達(dá)到了就可以退出，如果沒有就需要注意如果在運行的時候出現(xiàn)停止的現(xiàn)象，就需要從最開始進(jìn)行操作。

41 DP-ACS算法原理圖：

如圖2是DP-ACS的算法原理圖：

5）仿真實驗結(jié)果分析：

本次實驗采用的是兩種數(shù)據(jù)進(jìn)行，一種是小規(guī)模的，一種是大規(guī)模的。如表1所示是通過粒子群算法找到的一些關(guān)于不同問題集的蟻群算法的信息素：

如表2是設(shè)置蟻群算法的初始參數(shù)值和算法運行的迭代門限值：

6） DP-ACS算法解決小規(guī)模的TSP問題：

如圖3是運行10次之后的一個對比：

從圖中可以知道：經(jīng)過密度蜂聚類算法處理之后雖然問題的規(guī)模集節(jié)點變少，但是還是需要一定的時間。當(dāng)TSP案例的城市規(guī)模小于100的時候，算法之間的運行時間并沒有很大程度的差距，現(xiàn)在城市規(guī)模慢慢變大，這個時候就能體現(xiàn)出密度峰聚類算法的一個優(yōu)勢。

7） DP-ACS算法處理大規(guī)模TSP問題：

對于大規(guī)模的TSP問題，可以通過密度蜂聚類算法來進(jìn)行處理，之后在通過蟻群算法來進(jìn)行運算形成一個二類TSP問題的路徑圖，通過找到兩個聚類簇之間的鄰節(jié)點，切割重組之后形成最優(yōu)的路徑圖。在計算的時候如果發(fā)現(xiàn)是大規(guī)模TSP問題的時候就可以使用密度蜂聚類算法來進(jìn)行解決。

在解決大規(guī)模TSP問題的時候，經(jīng)過改進(jìn)之后也可以用密度蜂聚類算法來進(jìn)行計算，這樣就能減輕具備自適應(yīng)信息素里面的更新機制還有蟻群算法運算的復(fù)雜度。在解決一些大規(guī)模的TSP問題的時候使用蟻群算法能夠快速地找到一個問題的解決思路，同時還不會在計算的時候出現(xiàn)局部優(yōu)化的情況。當(dāng)所有的全局路徑線路都經(jīng)過處理之后，就能提高解精度。

8）算法收斂速度和多樣化的分析：

在分析算法收斂速度和多樣化的時候，可以先選擇一些TSP的問題案例進(jìn)行分析，如圖4所示：

可以通過圖4顯示知道：圖a能夠知道在計算的時候，運行500次的時候是全局最優(yōu)解的時候，雖然ACS算法的多樣性非常強，但是并不是全局最優(yōu)解的一種計算方法。圖b能夠知道在運行前180次的時候路徑解都在不斷優(yōu)化，但是從80次的時候就收斂了算法然后找到最優(yōu)解的方法。從圖c能夠知道DP-ACS算法表現(xiàn)的時候全局多樣性會變得更加的優(yōu)越，并且算法在收斂的時候也會變慢和真實的結(jié)果就會差得非常遠(yuǎn)。從圖d能夠知道，如果選擇的TSP案例出現(xiàn)增加的時候，DP-ACS算法就是最好的計算方法，在種群的時候也會有更多的多樣性，同時也不會出現(xiàn)早收斂的現(xiàn)象。但是ACS算法和MMAS算法在運行300次的時候都會陷入局部最佳的情況，這個時候就不會提高算法解精度。

如圖5是ACS算法和DP-ACS算法在解決問題的時候的算法多樣性的表現(xiàn)。

從圖5a能夠知道，ACS算法在運行前200次的時候會有非常大的上升趨勢，這個時候的種群多樣性也比較好。但是發(fā)現(xiàn)圖b表現(xiàn)出來的種群多樣性會更好，這個時候DP-ACS算法在前700次運行的時候，前后迭代運算的時候也能一直是不斷上升的趨勢，這個時候就能夠證明DP-ACS算法在一直不斷地走在優(yōu)化解路徑的道路上。對于這兩圖能夠發(fā)現(xiàn)：DP-ACS算法在每次迭代的時候都比ACS算法的標(biāo)準(zhǔn)值要差很多，在第400次的時候，DP-ACS的標(biāo)準(zhǔn)差數(shù)要比ACS算法的標(biāo)準(zhǔn)差相差500，這就說明DP-ACS算法中運行的時候螞蟻找到的路徑解數(shù)值會相距非常大，同時還能更好地表現(xiàn)出種群的多樣性。

9）分析時間復(fù)雜度：

如表3是改進(jìn)算法與其他算法運行的時間：

從圖中的信息能夠知道：當(dāng)案例城市節(jié)點數(shù)量上升的時候表3中的算法運算時間也在不斷上升。但是因為沒有經(jīng)過粒子群的處理，所以運算的時間變短。并且案例規(guī)模不斷增加的時候更加能夠體現(xiàn)改進(jìn)算法的最大優(yōu)勢。DP-ACS算法需要的運行時間就是衡量算法優(yōu)化TSP問題性能的指標(biāo)。

5 結(jié)論

現(xiàn)在TSP問題一直在不斷增加，雖然蟻群算法能解決這些問題，但是在解決問題的時候還會有一些不足，這些不足需要時間慢慢進(jìn)行更新。還可以用密度蜂聚類的算法把這些原始的TSP問題分成一些比較小的簇，這樣這些簇就能更好的用蟻群算法來進(jìn)行計算。同時這些二類的TSP問題還能利用閉合的解路徑利用一些近鄰點切割斷開之后重組之后就變成一些新的原始TSP問題的解路徑回路。通過這些實驗的數(shù)據(jù)能夠知道：到現(xiàn)在為止解精度和收斂速度最好的一種算法就是DP-ACS算法。特別需要注意的是當(dāng)TSP問題規(guī)模越來越大的時候，算法的優(yōu)越感就更能體現(xiàn)出來。在以后的日子，還需要把蟻群算法研究得更加深入，除此之外還需要把二類的TSP問題怎么形成的路徑進(jìn)行有效的研究，一起構(gòu)建一個新型的全局最優(yōu)路徑。

參考文獻(xiàn)：

[1]任珂欣，王興偉，馬連博，等.蟻群分工啟發(fā)的ICN負(fù)載均衡機制[J].計算機科學(xué)與探索，2018，12（7）：1109-1116.

[2]姜道銀，葛洪偉，袁羅.一種動態(tài)劃分的混合連續(xù)域蟻群優(yōu)化算法[J].計算機工程與應(yīng)用，2018，54（7）：144-151. [3]劉中強，游曉明，劉升.一種啟發(fā)式動態(tài)信息素更新策略的蟻群算法[J].計算機工程與應(yīng)用，201 8，54（20）：20-27.

[4]高妮，賀毅岳，申元，等.漏洞類型聚類的層次化漏洞修復(fù)模型[J].計算機科學(xué)與探索，2018，12（2）：274-281.

[5]馬學(xué)森，宮帥，朱建，等.動態(tài)凸包引導(dǎo)的偏優(yōu)規(guī)劃蟻群算法求解TSP問題[J].通信學(xué)報，2018，39（10）：59-71.

【通聯(lián)編輯：唐一東】