馮志雨，游曉明，劉 升

1.上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620

2.上海工程技術(shù)大學(xué) 管理學(xué)院，上海 201620

1 引言

旅行商問題（traveling salesman problem，TSP）屬于NP難問題[1]，仿生進(jìn)化思想的發(fā)展為NP難問題提供了新的思路，這其中以蟻群算法（ant colony optimization，ACO）最為顯著。蟻群算法的提出[2]，是源于Marco Dorigo的博士論文，它是一種具有進(jìn)化思想的啟發(fā)式算法，根據(jù)正反饋機制實現(xiàn)種群間的信息交流。蟻群算法1992年提出至今，針對算法的不足，研究學(xué)者一直進(jìn)行著改進(jìn)工作以提高算法的實現(xiàn)效率。Dorigo等人[3]和Stützle等人[4]分別提出了蟻群系統(tǒng)、最大-最小蟻群算法，對傳統(tǒng)蟻群算法在信息素更新方式以及界限進(jìn)行了改進(jìn)；對于TSP問題，有n個節(jié)點，那么相應(yīng)的就會有(n-1)!個可行解，對應(yīng)的時間復(fù)雜度就變成了O(n!)。隨著TSP問題規(guī)模越來越大，時間復(fù)雜度會愈加增大，運算難度就會愈加增大。傳統(tǒng)蟻群算法在解決大規(guī)模的TSP問題時，運算時間會增大并且解精度會降低。因此，應(yīng)對TSP問題，越來越多的學(xué)者試著結(jié)合多種智能算法的優(yōu)點去獲得更好的運算性能。文獻(xiàn)[5]提出蟻群算法（ACO）與3Opt并行合作混合方法。利用蟻群算法找到TSP問題的路徑解，然后運用3Opt算法優(yōu)化找到的路徑解，進(jìn)一步提高解精度，避免算法陷入局部最優(yōu)。雖然算法運行時間有所提高，但是為了算法中種群的并行運行，需要不止一臺實驗的仿真設(shè)備來完成，這無形中增大了仿真硬件要求。文獻(xiàn)[6]提出粒子群算法（particle swarm optimization，PSO）+蟻群算法（ACO）+3Opt方法，解決不同的TSP問題所需要的參數(shù)不盡相同，故利用粒子群算法去優(yōu)化蟻群算法中的信息素因子α和啟發(fā)式因子β，以便蟻群算法可以找到期望的路徑最優(yōu)解。然后再經(jīng)3Opt算法優(yōu)化解路徑。雖然算法提高了某些TSP問題的解精度，但是并沒有縮短算法的運算時間，并且當(dāng)TSP問題規(guī)模增大的時候，提出的改進(jìn)算法并沒有獲得較好的解路徑值。文獻(xiàn)[7]提出融合遺傳算法、模擬退火、蟻群算法、粒子群算法等多種群技術(shù)去解決TSP問題。先通過蟻群算法獲得初始最優(yōu)路徑解，然后通過遺傳模擬退火算法去優(yōu)化初始最優(yōu)路徑，當(dāng)?shù)瓿梢欢螘r間后，通過粒子群算法去優(yōu)化各路徑上的信息素，然后再進(jìn)行迭代運行。該算法在較大規(guī)模的TSP問題上獲得了理想的解路徑值，但是由于融合了多種優(yōu)化算法，算法本身的計算復(fù)雜度被提高了，運算時間沒有縮短。文獻(xiàn)[8]提出了基于蟻群算法的改進(jìn)信息素更新機制以及新的信息素平滑機制去解決TSP問題，利用迭代最優(yōu)路徑上的信息素確定新探邊的動態(tài)最佳路徑變化信息，從而加快算法收斂速度，利用平滑機制對信息素矩陣進(jìn)行重新初始化，從而擴大種群多樣性，增強算法的全局搜索能力，但是算法的計算復(fù)雜度為O(n2)，并沒有較大程度地降低算法的計算復(fù)雜度。

本文提出的DP-ACS（density peak clustering algorithm-ant colony system）算法利用分工合作[9]的思想，將大規(guī)模的TSP案例進(jìn)行節(jié)點分組歸納，然后運用改進(jìn)的蟻群算法尋找新形成的二類TSP問題的解路徑，最終切割斷點重組二類TSP問題的解路徑構(gòu)成原始TSP問題的最優(yōu)路徑。DP-ACS算法在保證問題解精度的前提下，明顯加快了算法運算時間，并且有效降低了算法的時間復(fù)雜度。

2 相關(guān)工作

2.1 TSP問題描述

旅行商問題是一個經(jīng)典的組合優(yōu)化問題，組合優(yōu)化是根據(jù)數(shù)學(xué)方法對某離散事件進(jìn)行整編、分組、排序等。旅行商問題是說一個旅行者要走遍給定數(shù)量的城市，但是前提這些給定的城市只允許旅行者拜訪一次，要求找出旅行者走遍每個城市后的最短路徑。給定的城市數(shù)量越大，求解問題的空間復(fù)雜度、時間復(fù)雜度不可避免地會增大，而且呈指數(shù)函數(shù)增長，因此TSP問題的解不是窮舉就可以得到的，問題的復(fù)雜度已經(jīng)遠(yuǎn)遠(yuǎn)超出了人們想象。求解TSP問題的算法一般分為兩大類：精確算法和啟發(fā)式算法。前者適用于小規(guī)模旅行商問題，后者適用于中大型TSP問題。精確算法主要有定界法、規(guī)劃法等。啟發(fā)式算法有GA（genetic algorithm）、SA（simulated annealing）、PSO、ACO等。其中蟻群算法，由于具備進(jìn)化思想，為解決旅行商問題提供了新的思路。

2.2 蟻群算法求解TSP問題

在標(biāo)準(zhǔn)的蟻群算法中，螞蟻根據(jù)式（1）[3]狀態(tài)轉(zhuǎn)移概率規(guī)則，判斷螞蟻下一個去往的城市。

式中，τij(t)是t迭代過程中，城市i與j連接路徑上的信息素值；ηij是城市i與j連接路徑長度的倒數(shù)值，是一種啟發(fā)式信息，如果城市i與j連接路徑長度越短，那么螞蟻選擇的下一個城市越可能是j；Allowedk表示螞蟻k未走過的城市；α和β分別決定了信息素和啟發(fā)因子的重要性。當(dāng)所有螞蟻完成了一次完整的路徑構(gòu)建，即完成一次迭代，此時信息素的更新將會按照式（2）進(jìn)行。

式中，ρ表示信息素?fù)]發(fā)參數(shù)，m是每次迭代的螞蟻總數(shù)量，表示螞蟻k在路徑(i,j)上釋放的信息素值，Lk(t)是螞蟻k旅行路徑長度。通過設(shè)置最大迭代次數(shù)，當(dāng)算法運行迭代數(shù)達(dá)到設(shè)定最大值，結(jié)束運行，得出算法最優(yōu)解。如果在迭代過程中出現(xiàn)停滯現(xiàn)象，則初始化處理，從而擺脫停滯，繼續(xù)迭代運行，直到達(dá)到設(shè)定的迭代上界。

2.3 密度峰聚類算法

密度峰聚類算法（density peak clustering algorithm，DPCA）[10]的基本思想是對于一個數(shù)據(jù)集，聚類中心被一些低局部密度的數(shù)據(jù)點包圍，而且這些低局部密度的點距離其他有高局部密度的點的距離都比較大。DPCA主要有兩個需要計算的量：（1）局部密度ρi；（2）與高密度點之間的距離δi。密度峰聚類算法是將給出的數(shù)據(jù)點通過計算點與點之間的歐式距離dij，然后根據(jù)ρi以及δi選取出聚類中心，聚類中心的選取衡量標(biāo)準(zhǔn)是具備較大局部密度ρi和較大距離δi。然后將所有非聚類中心的散點歸類到比自身密度更大的最相近的類中心所在的簇中。

2.3.1 局部密度ρi

其中，dc是截斷距離，N是數(shù)據(jù)點總數(shù)，percent是比例因子，本文設(shè)為2%，ρi是統(tǒng)計數(shù)據(jù)點i與其他數(shù)據(jù)點的歐式距離小于dc的個數(shù)。

2.3.2 與高密度點之間的距離δi

式中，δi是在所有較數(shù)據(jù)點i的局部密度ρi都大的數(shù)據(jù)點中，選出那些點與數(shù)據(jù)點i的歐式距離的最小值。

2.4 3Opt算法

3Opt[11]是一個應(yīng)用于優(yōu)化旅行商問題解質(zhì)量的局部搜索算法。在本算法中，3Opt主要用于從螞蟻找到全局最優(yōu)解中任意挑選3對節(jié)點，打亂重新組合3對節(jié)點的連接，并記錄所有重新組合的8種連接情況。然后評估重新連接的線路質(zhì)量與最初線路質(zhì)量的好與差，如果比對出更好的連接線路，則覆蓋之前螞蟻找到的全局最優(yōu)線路，反之保留起初線路。如果蟻群算法沒有使用3Opt，螞蟻容易陷入局部最小并導(dǎo)致搜尋不到最好的旅行長度，故3Opt進(jìn)一步遏制了局部最優(yōu)情況的發(fā)生。如圖1所示，左側(cè)連接圖有3條邊經(jīng)3Opt算法處理后可以重新生成更優(yōu)的連接圖。

Fig.1 3Opt algorithm implementation圖1 3Opt算法實現(xiàn)

2.5 粒子群算法

粒子群算法[12]是一種基于社會環(huán)境的自適應(yīng)算法，其中設(shè)置一組種群粒子去訪問給定域的盡可能的位置，每個位置都有對應(yīng)的可計算的適應(yīng)值。在每次迭代中，粒子將隨機地返回到先前的最佳適應(yīng)位置和種群最佳適應(yīng)位置。種群中的所有粒子都在分享自身找到的最佳搜索區(qū)域的信息。

粒子的運動由式（5）主導(dǎo)，vf表示粒子f的速度，xf表示粒子f的位置。

式中，c1、c2是非負(fù)整數(shù)，分別稱作“認(rèn)知”與“社會”，前者是粒子本身的思考，后者是粒子間的信息共享與合作，都是學(xué)習(xí)因子。r1、r2是[0,1]內(nèi)的隨機數(shù)，都是比例因子。w、χ是非負(fù)實數(shù)，分別稱作慣性權(quán)重和收縮因子。blf表示粒子f經(jīng)過的歷史最好位置，bg表示種群中所有粒子所經(jīng)過的最好位置。

3 改進(jìn)算法（DP-ACS）

運用蟻群算法求解TSP問題的過程中，隨著TSP問題規(guī)模的增大，蟻群算法的運算復(fù)雜度會呈指數(shù)上升。當(dāng)TSP問題中的節(jié)點數(shù)超過100時，依靠蟻群算法自身很難在運行時間和解精度之間找到平衡性，往往會消耗更多的時間去尋求更高的解精度。文獻(xiàn)[13]提出當(dāng)TSP問題中的城市節(jié)點小于40個時，蟻群算法在運行時間以及求解的精度都獲得最優(yōu)。文獻(xiàn)[14]提出了K-means聚類算法，這種算法快速、簡單，但是局限于處理數(shù)據(jù)分布呈球狀的簇。密度峰聚類算法是一種基于密度的聚類算法，尋求被低密度區(qū)域分離的高密度區(qū)域，能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點，聚類形狀不受限制。

3.1 改進(jìn)的密度峰聚類算法

密度峰聚類算法選取聚類中心依靠局部密度ρi和與高密度點之間的距離δi，故定義式（6）中γi為衡量點i是否為聚類中心：

因為聚類中心同時具備較大的ρi和δi，所以γi的值越大，說明點i越有可能是聚類中心，對集合γ進(jìn)行降序排序，選取集合γ的前8%個點，記為DE（density），對排序后的點重新編號，記為j，然后繪制γ關(guān)于j的數(shù)據(jù)圖，數(shù)據(jù)圖呈非遞增狀態(tài)。

定義ε為拐點，點ε為數(shù)據(jù)圖中前后兩點的γ值相差過大的點，點ε滿足式（7）給出的條件：

式中，kj表示點j+1與點j構(gòu)成線段的斜率，當(dāng)確定拐點之后，由于集合γ是降序排序的，故潛在的聚類中心點均位于拐點的左側(cè)。當(dāng)確定了潛在聚類中心后，按照需要解決的TSP問題規(guī)模確定劃分多少個聚類中心。

如圖2，以TSP案例lin105為例，利用Matlab仿真繪制出γ關(guān)于j的排序圖，其中橫軸對應(yīng)的是篩選出的城市節(jié)點重新編號，縱軸對應(yīng)的是原城市節(jié)點根據(jù)式（6）計算的γ值，圖中數(shù)據(jù)點旁的標(biāo)號是原TSP問題的城市編號。從圖2可以得出城市節(jié)點51是拐點，故城市節(jié)點77、23均為潛在的聚類中心。

Fig.2 γsorting chart圖2 γ排序圖

3.2 改進(jìn)的蟻群算法

文獻(xiàn)[2-4]的局部信息素更新都是根據(jù)式（8）進(jìn)行的。

式中，ρ表示信息素?fù)]發(fā)參數(shù)，取值范圍在[0,1]。一般將ρ的值設(shè)為0.1，但是TSP問題不同的數(shù)據(jù)規(guī)模算法需要的運算復(fù)雜度是不同的。ρ設(shè)為定值將不能滿足問題的解要求，比如kroA200，需要將ρ的值設(shè)大一些，以防蟻群算法過早收斂，獲得局部最優(yōu)解，降低了算法精度。因此提出式（9）自適應(yīng)地改變信息素?fù)]發(fā)值。

其中，k為比例因子，設(shè)為0.1；c為歸一化因子，設(shè)為2。通過式（9）將信息素?fù)]發(fā)參數(shù)ρ與信息素τij(t)之間建立線性關(guān)系。以e為底的指數(shù)函數(shù)呈單調(diào)遞增的特性，而信息素τij(t)的值隨著算法迭代運行呈上升趨勢。對τij(t)取反處理，這樣經(jīng)exp函數(shù)處理后所得值控制在（0,1）內(nèi)，從而經(jīng)式（9）處理，信息素?fù)]發(fā)參數(shù)ρ隨著信息素τij(t)的增大而增大，并且ρ的值控制在（0.1,0.2）。

算法迭代運行初期，TSP問題中節(jié)點構(gòu)成的路徑上面螞蟻數(shù)隨機，信息素相差甚微，路徑與路徑間的受螞蟻的歡迎度相差不大。隨著算法的迭代運行推進(jìn)，路徑上面的信息素量的差距開始拉大，此時某些受歡迎度高的路徑上的信息素值較高，這時在還沒有找到全局最優(yōu)路徑的情況下，蟻群算法很容易陷入局部最優(yōu)。這時根據(jù)式（9）的關(guān)系，避免了信息素過高帶來的影響，此時信息素?fù)]發(fā)參數(shù)對應(yīng)提高，有效遏制了較歡迎路徑上的信息素濃度的進(jìn)一步提高。反過來，當(dāng)信息素?fù)]發(fā)參數(shù)ρ值升高時，必然會造成算法收斂速度的下降。這時候根據(jù)式（9）的關(guān)系，信息素τij(t)必然會略有提高來應(yīng)對信息素?fù)]發(fā)參數(shù)ρ值升高帶來路徑上面的信息素殘余量過少的情況，在一定程度上避免了蟻群算法收斂速度減緩的情況發(fā)生。信息素?fù)]發(fā)參數(shù)ρ與信息素τij(t)之間相互平衡，當(dāng)ρ過大時，τij(t)相應(yīng)就會增大，避免算法運算復(fù)雜度的上升；當(dāng)τij(t)過大時，ρ相應(yīng)就會增大，避免算法過早收斂陷入局部最優(yōu)。

3.3 改進(jìn)算法的流程圖

本文DP-ACS算法求解旅行商問題的基本步驟如圖3所示。

由圖3可以看出，本文提出的改進(jìn)算法（DPACS）先進(jìn)行設(shè)置初始參數(shù)值，例如最大迭代次數(shù)、城市節(jié)點上信息素初始值、信息素?fù)]發(fā)參數(shù)的初始值、螞蟻數(shù)量等，然后根據(jù)初始TSP問題數(shù)據(jù)集給定的節(jié)點坐標(biāo)，運算節(jié)點與節(jié)點之間的歐式距離，進(jìn)而根據(jù)式（3）截斷距離的定義計算dc，再根據(jù)式（3）、式（4）計算出每個節(jié)點的局部密度ρi以及與高密度點之間的距離δi。通過改進(jìn)的密度峰聚類算法確定拐點，根據(jù)拐點的位置篩選出潛在的聚類中心，聚類中心的個數(shù)由初始TSP問題規(guī)模決定。根據(jù)選舉出的聚類中心形成簇，每個簇包含一個聚類中心，一個城市節(jié)點只能屬于一個簇。由于每個簇包含的節(jié)點數(shù)不盡相同，故利用粒子群算法去尋找對應(yīng)不同規(guī)模的TSP問題應(yīng)該設(shè)定的蟻群算法的信息素因子α和啟發(fā)式因子β。形成的這些簇中的數(shù)據(jù)節(jié)點各自又構(gòu)成了新的TSP問題，本文稱為二類TSP問題。用具備自適應(yīng)局部信息素更新的蟻群算法對二類TSP問題求解最優(yōu)路徑解，當(dāng)這些二類TSP問題結(jié)束運行后，通過近鄰原則選取兩個相鄰簇之間最近的兩個節(jié)點，切割斷開經(jīng)過這兩個節(jié)點的相關(guān)路徑，通過之前斷開的節(jié)點之間的相互連接實現(xiàn)兩簇相連的效果，依此類推，將所有形成的二類TSP問題解路徑重新組合成全局解路徑，這樣二類TSP問題將還原成初始設(shè)置的TSP問題，解路徑從區(qū)域連接重新融合組成整體。再將重新連接后的全局路徑經(jīng)過局部優(yōu)化策略3Opt的處理，以達(dá)到進(jìn)一步優(yōu)化重新連接后的全局路徑的效果。最后通過算法辨別是否達(dá)到了預(yù)先設(shè)置的迭代次數(shù)上限。如果達(dá)到了，算法退出運行，輸出運行結(jié)果；否則，算法繼續(xù)迭代運行。如果算法在運行過程中出現(xiàn)停滯狀況，算法將進(jìn)行初始化信息素操作，以達(dá)到強制算法恢復(fù)運行的效果。

Fig.3 DP-ACS algorithm flowchart圖3 DP-ACS算法流程圖

3.4 DP-ACS算法的原理圖

如圖4，以TSP問題lin105為例，改進(jìn)算法先經(jīng)過密度峰聚類算法處理，選取出3個聚類中心，分別是初始TSP問題的節(jié)點23、51、77，然后對新形成的二類TSP問題經(jīng)改進(jìn)的蟻群算法運算，找出各自的最優(yōu)路徑解。由圖4可知新形成的二類TSP問題構(gòu)造的是密閉的環(huán)形路徑解，需要通過近鄰原則選取節(jié)點進(jìn)行分割。將左側(cè)的二類TSP問題的節(jié)點39與節(jié)點37之間的線段切割斷開，將右側(cè)的二類TSP問題的節(jié)點2與節(jié)點9之間的線段切割斷開，然后將左側(cè)的二類TSP問題的節(jié)點69與右側(cè)的二類TSP問題的節(jié)點1相連。因為TSP問題中規(guī)定每個被訪問的城市節(jié)點只允許訪問一次，考慮到構(gòu)建的全局最優(yōu)路徑解最短的要求，所以斷開右側(cè)的二類TSP問題的節(jié)點1與節(jié)點4之間連接的線段，然后將節(jié)點4與節(jié)點2相連。依此類推，斷開中間的二類TSP問題的節(jié)點2與節(jié)點18、節(jié)點3與節(jié)點4、節(jié)點19與節(jié)點22之間的線段，將左側(cè)的二類TSP問題中的節(jié)點37與中間的二類TSP問題的節(jié)點3相連，將右側(cè)的二類TSP問題的節(jié)點9與中間的二類TSP問題的節(jié)點22相連。同樣考慮到每個被訪問的節(jié)點僅允許訪問一次，將中間的二類TSP問題的節(jié)點2與節(jié)點4相連。最終經(jīng)過改進(jìn)的蟻群算法運算的所有二類TSP問題的局部最優(yōu)路徑重組構(gòu)成了初始TSP問題的全局最優(yōu)路徑解，再經(jīng)過3-Opt算法優(yōu)化解路徑，最后得到了lin105問題的最優(yōu)路徑解，即14 379。

Fig.4 DP-ACS algorithm schematic圖4 DP-ACS算法原理圖

4 仿真實驗與結(jié)果分析

本文算法采用Matlab 2014b仿真軟件，基于Intel?CoreTMi5-4200M CPU@2.50 GHz處理器，RAM為16 GB，操作系統(tǒng)為64位的Win10。本文選取了TSPLIB里的典型問題集，這些問題集通常用于測試和優(yōu)化算法。本文將問題集分為兩組進(jìn)行實驗，一組是小規(guī)模，另一組是大規(guī)模。參考文獻(xiàn)[15]可知，密度峰聚類算法處理后的TSP問題形成的二類TSP問題規(guī)模在30～40個數(shù)據(jù)集節(jié)點最優(yōu)。

如表1，利用粒子群算法中的粒子與種群尋找對應(yīng)不同問題集的蟻群算法的信息素因子α和啟發(fā)式因子β。

Table 1 Sets of parameters factor values表1 參數(shù)因子值集

如表2，設(shè)置蟻群算法的初始參數(shù)值以及算法運行迭代門限值等。

Table 2 Setting of basic parameters表2 基本參數(shù)設(shè)置

表2中ρ表示信息素?fù)]發(fā)參數(shù)，Nmax表示算法運行迭代門限，Q表示螞蟻循環(huán)一周釋放的信息素總量，m表示螞蟻數(shù)，n表示城市節(jié)點數(shù)，τ0表示信息素初始參數(shù)值。

4.1 DP-ACS算法處理小規(guī)模TSP問題

圖5給出的是蟻群算法在迭代運行10次時，添加密度峰聚類算法和不添加密度峰聚類算法進(jìn)行實驗比較。

Fig.5 Comparison of algorithm running time圖5 算法運行時間對比

從圖5可以得出，經(jīng)過密度峰聚類算法處理分割的TSP問題雖然在蟻群算法運算過程中還是需要一些時間，但是問題規(guī)模數(shù)據(jù)集節(jié)點的減少，降低了蟻群算法運算時間，并且運算時間減少會隨著問題規(guī)模的增大而越發(fā)明顯。當(dāng)TSP案例的城市規(guī)模小于100時，算法之間的運行時間差距并不明顯，隨著城市規(guī)模增大，運用密度峰聚類算法所顯現(xiàn)出的優(yōu)勢越發(fā)明顯。以kroA100問題為例，算法運行時間開始加快，比不使用密度峰聚類算法降低了1.59 s。以ch150問題為例，算法運行時間明顯加快，比不使用密度峰聚類算法降低了4.70 s。

如表3所示，選取6個規(guī)模不同的TSP問題案例，分別添加3Opt算法和不添加3Opt算法進(jìn)行20次仿真運行，利用式（10）驗證3Opt算法對改進(jìn)算法的運行時間和運行解精度的影響力。

Table 3 Comparison of application of 3Opt algorithm表3 3Opt算法的運用比較

其中，RL表示路徑解相對優(yōu)化比例，RT表示3Opt算法運行時間占改進(jìn)算法的總運行時間比例，l1表示改進(jìn)算法不運用3Opt算法的解長度平均值，l2表示改進(jìn)算法運用3Opt算法處理后得到的解長度平均值，t1表示3Opt算法的運行時間，t2表示改進(jìn)算法的總運行時間。

從表3中可以得出，選取的6個案例運用3Opt算法處理對改進(jìn)算法找到的全局路徑解都起到了一定的優(yōu)化作用，特別是案例fl417，路徑解相對優(yōu)化比例達(dá)到了31.91%。雖然案例eil51優(yōu)化力度最小，僅為1.72%，但是RT值最小，僅為0.01%，可以忽略不計。隨著案例規(guī)模的增大，運用3Opt算法處理顯現(xiàn)出的優(yōu)勢越發(fā)明顯，并且RT值的增幅放緩。

從圖6可以得出，左側(cè)的全局路徑線路圖在未經(jīng)過3Opt算法處理前，存在3處路徑線路重疊現(xiàn)象，右側(cè)的全局路徑線路圖在經(jīng)過3Opt算法處理后，原先存在的3處重疊不存在了。因此經(jīng)過3Opt算法的處理，可以將改進(jìn)算法運算得出的全局路徑線路的邊緣重疊問題消除，減少路徑的總長度，從而得到更好的全局最優(yōu)解。雖然3Opt算法提供了很好的路徑優(yōu)化方案，但是運用3Opt算法增加了改進(jìn)算法整體的運行時間，參考式（11）可以得出3Opt算法的時間復(fù)雜度為O(n3)。

其中,n3Opt表示在3Opt算法中，需要檢查邊節(jié)點交換的次數(shù)，n表示城市節(jié)點數(shù)量。

Fig.6 3Opt algorithm optimization case kroA200圖6 3Opt算法優(yōu)化案例kroA200

為了讓改進(jìn)算法加快解決TSP問題的時間，必須優(yōu)化3Opt算法處理進(jìn)程。3Opt算法是在重復(fù)地做著同一件事，比較三邊長短，然后新構(gòu)造的邊短就會重新更新路徑，否則不會更改。因此通過加速這些單一步驟，整個改進(jìn)算法的運行時間將會縮短。CPU并行方法是預(yù)先將節(jié)點與節(jié)點間的距離計算好存儲在緩存內(nèi)存中，這種處理方法會隨著問題規(guī)模的增大而降低效率，并且也會受到內(nèi)存帶寬的限制。故本文參考文獻(xiàn)[16]中的GPU并行方法，利用GPU內(nèi)存存儲城市的坐標(biāo)，并且存儲在共享內(nèi)存的快速片上，需要時就計算兩城市間的距離，從而提高了數(shù)據(jù)讀取速率。隨著TSP問題規(guī)模的增大，GPU處理進(jìn)程中計算兩城市間的距離的比例會降低，這是由于快速片具有共享性，并且相比于CPU并行方法，GPU并行方法具有更高的峰值內(nèi)存吞吐量。

從表4可以得出，當(dāng)TSP問題集選取案例較小時，比如eil51、berlin52，除蟻群算法外，DP-ACS算法與其他兩種算法的實驗結(jié)果相差不大，幾乎相同，并且算法均能找到eil51、berlin52問題的最優(yōu)路徑解，解值分別是426、7 542。雖然說eil51和berlin52問題的城市點數(shù)幾乎相同，但是從它們的最優(yōu)路徑解值可以看出它們各自的城市點位置分布稀疏情況不同，eil51的城市點與點之間更為靠近，berlin52的城市點與點之間更為疏遠(yuǎn)。當(dāng)通過改進(jìn)的聚類算法對問題集berlin52進(jìn)行聚類處理后，可以將問題中的城市點進(jìn)行分類，劃分到一類簇中。然后根據(jù)粒子群算法優(yōu)化后的參數(shù)α和β交由改進(jìn)后的蟻群算法進(jìn)行運算處理，這樣可以節(jié)約螞蟻判斷前往下一個城市的運算時間。因為由蟻群算法狀態(tài)轉(zhuǎn)移規(guī)則可知，兩個城市間的間隔越短，螞蟻從當(dāng)前城市去往間隔短的城市的概率就會越大，密度峰聚類就是把離中心節(jié)點最近的城市化為一類，那么在這一類中的節(jié)點與節(jié)點之間的距離遠(yuǎn)遠(yuǎn)小于與其他類中的節(jié)點距離。

本文選取5組小規(guī)模TSP問題集，即eil51、berlin52、eil76、kroA100、ch150，用改進(jìn)算法進(jìn)行仿真實驗，每組TSP問題分別實驗20次，并將DP-ACS算法的實驗結(jié)果與 ACO[17]、ACO+3Opt[5]、PSO+ACO+3Opt[6]進(jìn)行比較。蟻群算法中參數(shù)α與β值的選取參考表1中的6個小規(guī)模TSP問題對應(yīng)的參數(shù)值設(shè)置。

從表4可以得出，針對eil51問題，DP-ACS算法在找到問題最優(yōu)路徑解值的前提下，標(biāo)準(zhǔn)差較ACO[17]降低了3.72，這說明DP-ACS算法更加穩(wěn)定，實驗仿真結(jié)果的波動性更小。針對kroA100問題，DP-ACS算法與其他算法相比，平均值分別降低了1 581.66、28.34、146.64。DP-ACS算法在20次仿真實驗中得出的最優(yōu)路徑解值更接近問題已知最優(yōu)解，因此DPACS算法的解精度更高一些，并且較ACO[17]、PSO+ACO+3Opt[6]，DP-ACS算法可以找到問題已知最優(yōu)路徑規(guī)劃。在標(biāo)準(zhǔn)差值中，DP-ACS算法比其他算法低211.73、10.27、54.79，得出DP-ACS算法具有更高的穩(wěn)定性，算法每次找到的最優(yōu)路徑解偏差較小，改進(jìn)算法具有更強的魯棒性能。針對ch150問題，DPACS算法找出的最優(yōu)路徑解與已知最優(yōu)解值相差只為5，與已知路徑最優(yōu)解值幾乎相同，比ACO[17]找到的路徑最優(yōu)解縮小了115.51，比ACO+3Opt[5]找到的路徑最優(yōu)解縮小了37，比PSO+ACO+3Opt[6]找到的路徑最優(yōu)解縮小了5，DP-ACS算法較大程度上提高了算法的解精度，改進(jìn)算法在平均值和標(biāo)準(zhǔn)差上都比其他算法更優(yōu)，故DP-ACS算法具有更強的穩(wěn)定性。

Table 4 Comparison of DP-ACS algorithm with other algorithms on small-scale TSP instances表4 DP-ACS算法與其他算法在小規(guī)模TSP案例上的比較

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

本文選取4組大規(guī)模TSP問題集，即kroA200、rd400、fl417、d493，用DP-ACS算法進(jìn)行仿真實驗，每組TSP問題分別實驗20次，并將DP-ACS算法的實驗結(jié)果與 ACO+3Opt[5]、PSO+ACO+3Opt[6]進(jìn)行比較。ACO中參數(shù)α與β值的選取參考表1中的TSP問題對應(yīng)的參數(shù)值設(shè)置。

對于大規(guī)模的TSP問題，通過密度峰聚類算法處理后得到的簇中包含的數(shù)據(jù)集節(jié)點限制在40個以內(nèi)[15]。然后經(jīng)過蟻群算法運算后各自形成的二類TSP問題的路徑圖，這些簇與簇之間交流的時間很短，通過找到兩個聚類簇之間最近鄰節(jié)點，然后切割重組成初始TSP問題的最優(yōu)路徑圖。對于大規(guī)模的TSP問題，運用密度峰聚類算法和不運用密度峰聚類算法之間的差別是顯著的，特別在算法運行時間上的減少是明顯的。

由表5可以得出，與ACO+3Opt[5]、PSO+ACO+3Opt[6]相比，DP-ACS算法找到了案例kroA200的最優(yōu)路徑解，并且在平均誤差百分比（平均值與理論最優(yōu)解的差值除以理論最優(yōu)解）上降低了0.7%，因此DP-ACS算法運行更加穩(wěn)定。在案例rd400、fl417上，DP-ACS算法的平均誤差百分比分別降低了1.28%、1.79%、0.66%、0.6%，DP-ACS算法在每個TSP案例中的20次仿真實驗結(jié)果精度更高，解路徑值更加接近TSP案例的理論最優(yōu)解。在案例d493上，DP-ACS算法的運算結(jié)果精度有所提高，較其他算法的最優(yōu)解值，DP-ACS算法找到的最優(yōu)路徑分別縮短了382、436。

對于大規(guī)模的TSP問題，經(jīng)過改進(jìn)的密度峰聚類算法處理后，得到的二類TSP問題城市節(jié)點數(shù)量較初始TSP問題更少，這樣減輕了具備自適應(yīng)信息素更新機制的蟻群算法的運算復(fù)雜度。相對于大規(guī)模TSP問題，蟻群算法解決二類TSP問題更容易找到全局路徑最優(yōu)解，對于螞蟻在尋找自身的局部最優(yōu)解的時候，城市節(jié)點數(shù)量越少，蟻群更加容易找到局部最優(yōu)路徑，密度峰聚類算法的運用加快了蟻群算法在處理二類TSP問題的收斂速度，并且由于城市數(shù)量的減少，蟻群算法[18]不易陷入局部最優(yōu)。當(dāng)全局路徑線路經(jīng)過3Opt算法處理后，進(jìn)一步優(yōu)化算法已知最優(yōu)路徑解，有效地提高了解精度，本文在構(gòu)建局部最優(yōu)路徑路線的基礎(chǔ)上優(yōu)化了全局最優(yōu)路徑路線。

4.3 算法收斂速度與多樣性分析

選取4個TSP問題的基本案例，kroA100、ch150、kroA200、fl417，將 DP-ACS算法與蟻群算法（ant colony system，ACS）、最大-最小蟻群算法（max-min ant system，MMAS）進(jìn)行仿真實驗對比。

Table 5 Comparison of DP-ACS algorithm with other algorithms on large-scale TSP instances表5 DP-ACS算法與其他算法在大規(guī)模TSP案例上的比較

從圖7（a）可以得出，DP-ACS算法在kroA100案例中收斂速度比ACS算法、MMAS算法都快，大約在算法迭代運行了500次后，DP-ACS算法已經(jīng)收斂到了全局最優(yōu)解，即21 282。雖然ACS算法多樣性很強，但是ACS算法并沒有找到全局最優(yōu)解。從圖7（b）可以得出，DP-ACS算法在前180次迭代運行中，路徑解都在不斷經(jīng)過優(yōu)化，并且從迭代曲線看，每次迭代優(yōu)化的數(shù)值都較大。而ACS算法自80次迭代運行開始就收斂到了算法找到的最優(yōu)解，陷入了局部最優(yōu)，解路徑值沒有再變優(yōu)。MMAS算法表現(xiàn)出豐富的多樣性，但是找到的路徑最優(yōu)解較DP-ACS算法還是相差甚遠(yuǎn)。從圖7（c）可以得出，DP-ACS算法表現(xiàn)出的全局多樣性更優(yōu)越，ACS算法收斂速度慢并且算法找到的結(jié)果與理論最優(yōu)解相距甚遠(yuǎn)。MMAS算法過早收斂到算法最優(yōu)解，多樣性較差，并沒有找到理論最優(yōu)解。從圖7（d）可以得出，當(dāng)所選TSP案例增大時，DP-ACS較其他算法更加優(yōu)越，種群多樣性更優(yōu)，沒有出現(xiàn)過早收斂的情況，而ACS算法、MMAS算法均在300次迭代后陷入局部最優(yōu)，并沒有有效提高算法的解精度。

圖8（a）、圖8（b）分別是ACS算法與DP-ACS算法在解決fl417問題所表現(xiàn)出的算法多樣性[19]。從圖8（a）可以得出，ACS算法在前200次迭代運行中，前后迭代運算的標(biāo)準(zhǔn)差呈上升趨勢，種群多樣性較好。但是圖8（b）中DP-ACS算法所表現(xiàn)出種群多樣性更好，DP-ACS算法在前700次迭代運行過程中，前后迭代運算的標(biāo)準(zhǔn)差一直呈上升趨勢，這說明DPACS算法一直在不斷優(yōu)化解路徑。對比圖8（a）和圖8（b），DP-ACS算法每次迭代運算的標(biāo)準(zhǔn)差都較ACS算法的標(biāo)準(zhǔn)差數(shù)值大，在第400次迭代時，DP-ACS算法運算出的標(biāo)準(zhǔn)差數(shù)值較ACS算法運算出的標(biāo)準(zhǔn)差相差約500，這表明了DP-ACS算法中每次迭代運行中的螞蟻所尋找的路徑解數(shù)值相距較大，DP-ACS算法表現(xiàn)出更好的種群多樣性。

Fig.7 Comparison of algorithm iterations for different TSP problems圖7 不同TSP問題的算法迭代情況比較

Fig.8 Comparison of algorithm diversity圖8 算法多樣性比較

4.4 分析時間復(fù)雜度

如表6所示，選取6個TSP問題案例，然后經(jīng)過改進(jìn)算法的運算，統(tǒng)計20次仿真實驗，求取平均運算時間，比較改進(jìn)算法與ACO+3Opt[5]算法、PSO+ACO+kOpt[20]的平均運算時間。

Table 6 Comparison of running time between improved algorithm and other algorithms表6 改進(jìn)算法與其他算法的運行時間比較 s

從表6可以得出，隨著案例的城市節(jié)點數(shù)量上升，3種算法的運算時間均在增大。由于ACO+3Opt[5]算法沒有經(jīng)過聚類[21-22]處理以及沒有運用粒子群算法，因此針對eil51案例，ACO+3Opt[5]算法運算時間更短。但是，隨著案例規(guī)模的增大，改進(jìn)算法的運算時間顯現(xiàn)出明顯的優(yōu)勢。

DP-ACS算法的運行時間是衡量算法優(yōu)化TSP問題性能的一個重要指標(biāo)。對于單純用蟻群算法解決TSP問題，提出式（12）來表達(dá)算法的運算復(fù)雜度。

其中，Nmax是蟻群算法迭代運行的次數(shù)，n表示TSP問題規(guī)模，即城市節(jié)點總數(shù)額，c表示與n成比例的常數(shù)。

令nm表示TSP問題經(jīng)過密度峰聚類算法聚類形成的二類TSP問題所能包含的最大節(jié)點數(shù)額。本文參考文獻(xiàn)[14]將nm設(shè)置為40。提出式（13）來計算DP-ACS算法的時間復(fù)雜度。

其中，O(n1)是密度峰聚類算法對TSP問題每個節(jié)點進(jìn)行計算處理的時間復(fù)雜度，O(n2)是經(jīng)過3Opt算法進(jìn)一步優(yōu)化找到的最優(yōu)路徑的時間復(fù)雜度O(n3)。因為經(jīng)過密度峰聚類算法處理過的TSP問題形成的二類TSP問題規(guī)模大致相同，并且每個二類TSP問題的規(guī)模都不會超過nm，所以蟻群算法處理二類TSP問題的時間復(fù)雜度為然后再乘以經(jīng)過向上取整的n/nm，得出經(jīng)過密度峰聚類算法處理后的蟻群算法時間復(fù)雜度O(n)，其中表示聚類算法處理后形成的二類TSP問題的數(shù)額。因此，整個改進(jìn)算法的時間復(fù)雜度為O(n3)。

4.5 DP-ACS算法找到的最優(yōu)路徑圖

如圖9～圖12，分別是DP-ACS算法就TSP問題ch150、lin105、kroA200、fl417處理得到的算法最優(yōu)路徑解。

Fig.9 Optimal path for ch150 problem(length:6 533)圖9 ch150問題的最優(yōu)路徑(最短距離:6 533)

Fig.10 Optimal path for lin105 problem(length:14 379)圖10 lin105問題的最優(yōu)路徑(最短距離:14 379)

5 結(jié)束語

Fig.11 Optimal path for kroA200 problem(length:29 368)圖11 kroA200問題的最優(yōu)路徑(最短距離:29 368)

Fig.12 Optimal path for fl417 problem(length:11 898)圖12 fl417問題的最優(yōu)路徑(最短距離:11 898)

隨著TSP問題規(guī)模的增大，蟻群算法在問題解精度以及算法收斂速度上表現(xiàn)不足[23]，提出具有自適應(yīng)信息素更新策略的聚類蟻群算法（DP-ACS）。利用密度峰聚類算法將原始TSP問題切割成較小的簇，這些簇再由具有自適應(yīng)信息素更新策略的蟻群算法求解形成解路徑。這些二類TSP問題各自形成的閉合解路徑通過近鄰點切割斷開重組構(gòu)成原始TSP問題的解路徑回路，再經(jīng)局部優(yōu)化策略（3Opt）優(yōu)化最優(yōu)路徑解，通過這些改進(jìn)策略共同作用提高改進(jìn)算法的性能。實驗結(jié)果證明，DP-ACS算法的最優(yōu)解精度以及收斂速度都較其他的改進(jìn)蟻群算法更優(yōu)越，當(dāng)TSP問題規(guī)模增大的時候，DP-ACS算法的優(yōu)越性更加突出。在接下來的研究過程中，將探討蟻群算法求解二類TSP問題的解精度與算法的迭代運行次數(shù)之間的關(guān)聯(lián)；另一方面，將研究二類TSP問題各自形成的解路徑如何有效地連接在一起構(gòu)成全局最優(yōu)路徑。