粱藝瓊

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

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

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

文章編號(hào)：1009-3044（2020）05-0197-03

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

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

1 蟻群算法的歷史

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

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

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

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

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

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

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

2）密度峰聚類算法：

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

3） 30pt算法：

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

4）粒子群算法：

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

4 改進(jìn)算法

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

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è)置一個(gè)初始的參數(shù)值，然后在根據(jù)問題制定相應(yīng)的節(jié)點(diǎn)坐標(biāo)，之后在根據(jù)截?cái)嗑嚯x的定義計(jì)算，最后根據(jù)改進(jìn)的密度蜂聚類算法確定一個(gè)拐點(diǎn)，之后根據(jù)選舉出的聚類中心變成簇。因?yàn)槊總€(gè)簇包含的節(jié)點(diǎn)都不一樣，所以要用粒子群的算法來進(jìn)行設(shè)定，最后找出解決問題的方法。

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

41 DP-ACS算法原理圖：

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

5）仿真實(shí)驗(yàn)結(jié)果分析：

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

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

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

如圖3是運(yùn)行10次之后的一個(gè)對(duì)比：

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

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