引入特征遷移和匹配學習的雙蟻型蟻群算法

陳 達，游曉明+，劉 升

1.上海工程技術大學 電子電氣工程學院，上海 201620

2.上海工程技術大學 管理學院，上海 201620

旅行商問題（traveling salesman problem，TSP）是經典的組合優化問題，可以簡單地描述成：旅行商從規定的幾個城市中的某一起點出發，并通過所有給定的城市，且每個城市只經過一次，最后回到起點，從而找到一條最短閉合回路的路徑問題。目前有很多可以解決TSP 問題的算法，蟻群算法因其良好的并行性和較好的魯棒性成為了解決TSP問題最好的算法之一。

20 世紀90 年代初，意大利學者Dorigo 等人[1-2]受到螞蟻覓食行為的啟發提出了螞蟻算法（ant system，AS），但算法有著收斂速度慢、容易陷入局部最優的缺點。于是在此基礎上，Dorigo 等人在1997 年提出了全新的蟻群算法（ant colony system，ACS）[3]，相較于AS算法，該算法大大地提高了收斂速度和求解精度。同時期，由Stutzle 等人提出了最大最小螞蟻系統（max-min ant system，MMAS）[4]，該算法為信息素設置了上下限閾值，避免了信息素濃度無限累加以致算法停滯，提高了算法的求解效率。以上就是經典的蟻群算法，它們都具有效率較高的求解能力，但仍就存在易于陷入局部最優、收斂速度慢等問題。

此后眾多的專家學者針對這些問題提出了自己的改進，文獻[5-7]提出了融合遺傳-蟻群算法，一種引入代價算子的蟻群算法和一種自適應分組的蟻群算法，分別利用了遺傳算法前期收斂速度快，引入代價算子控制搜索方向和讓蟻群自適應分組的方式，很好地提高了算法的收斂速度，但存在著多樣性較差，求解質量不高的問題。文獻[8]與文獻[9]分別使用了一種新的信息素二次更新機制和使用K-Means 聚類算法生成城市關聯矩陣影響螞蟻選擇城市的概率的方法，從而增加了算法的多樣性，但算法收斂速度略有不足。文獻[10]提出了一種新的信息素更新方式，從而在加快算法收斂速度的同時擴大了搜索范圍；文獻[11]使用了擁擠度與2-opt 算子，提高蟻群算法的收斂速度和全局搜索能力，從而很好地平衡了收斂速度和多樣性之間的關系，但由實驗結果可知，對于較大規模的城市的求解精度有待提高。

針對以上問題，提出一種引入特征遷移和匹配學習的雙蟻型蟻群算法（dual ant colony algorithm based on backtracking migration and matching learning，BMACS），通過改進的動態分級策略，根據個體適應度的評價，將螞蟻分為探索蟻和追蹤蟻，探索蟻適應度好，通過較大權重的動態信息素更新增強自己的影響力，起到導向作用；追蹤蟻跟隨探索蟻，每只探索蟻通過分配規則分到若干追蹤蟻，隨后追蹤蟻在探索蟻附近搜索次優路徑，擴大搜索范圍。其次，提出一種局部遷移機制，通過局部特征遷移策略將探索蟻得到的解選出公共路徑，并作為局部特征通過局部信息素獎勵遷移到信息素矩陣中，進一步加快收斂速度；通過變異學習策略，針對探索蟻的路徑使用分配的追蹤蟻進行變異學習操作，搜索探索蟻附近路徑的探索，從而增加多樣性，產生的新個體與原個體進行比較擇優保留。最后匹配學習機制通過余弦相似度選出歷史最優解，并與當前最優解進行匹配，保留之間公共路徑的信息素，并對非公共路徑的信息素進行平滑操作，幫助算法跳出局部最優。實驗結果表明，本文算法在解決TSP問題時相比原算法有一定的提高，較好平衡了算法收斂速度與多樣性之間的矛盾，并對較大規模的TSP問題求解也具有一定的提高。

1 蟻群算法求解TSP問題步驟

1.1 路徑構建

在ACS算法中，螞蟻k當前位置在i處，遵循偽隨機規則選擇自己將要訪問的城市j，其規則如式（1）：

其中，q是均勻分布在區間[0,1]上的隨機變量；q0是一個參數，其范圍是[0,1]；J是根據式（2）給出的一個變量。

其中，α為信息啟發式因子；β為期望啟發式因子；為螞蟻下一步可以直接到達并且尚未訪問過的城市的集合；ηij為啟發函數，其表達式為式（3）；τij是城市i到城市j所在邊信息素的大小。

1.2 信息素更新

局部信息素更新規則：螞蟻k從當前城市i到下一城市j后，立即進行更新信息素，如式（4）所示：

其中，ρ是局部信息素蒸發系數，其范圍是[0,1]；τ0是信息素初始值，這里根據實驗結果選取τ0的值為1/nC時，算法性能較好；n是城市節點數，C是一個常數。

全局信息素更新規則：當所有螞蟻都走完之后，選擇本次迭代中的當前最短路徑進行全局信息素更新，如式（5）所示：

其中，ξ為全局信息素蒸發系數，Lbs為全局最優的路徑長度；為全局最優的路徑改變的信息素，按照式（6）計算。

2 算法改進（BMACS）

2.1 改進的動態分級策略

傳統蟻群算法螞蟻的探索行為單一，且個體之間的協作溝通不足，為了解決這一問題，本節提出一種改進的動態分級策略，通過式（7）評價每只螞蟻個體適應度的好壞，并將螞蟻分成探索螞蟻和追蹤螞蟻，隨后將若干追蹤螞蟻通過2.1.3 小節的分配規則分給探索螞蟻，隨后探索螞蟻執行局部特征遷移策略交流各自的優秀解或片段，增強其導向作用，追蹤螞蟻通過變異學習策略跟隨探索螞蟻所走的路徑附近，追蹤次優級的路徑，并通過局部信息素的自適應更新反饋給探索螞蟻，提高探索螞蟻的局部搜索能力，若追蹤螞蟻在局部搜索的過程中找到更優的解則替換掉該路徑，提高算法效率，兩種螞蟻的關系如圖1所示。

圖1 探索螞蟻與追蹤螞蟻交流Fig.1 Communication between exploration and tracking ants

2.1.1 適應度評價算子

在TSP問題中，螞蟻在跑完路徑之后得到的長度相差較大，并不適合直接評判解的優劣，故本小節提出一種適應度評價方法，如式（7）所示：

其中，Lj是第j個個體的解，λj是個體j的適應度，N是種群數目。由上述公式可知，適應度越小，螞蟻個體得到的路徑長度越小，從而適應度越好。

2.1.2 動態分級算子

動態分級規則如式（8）、式（9），由公式可知兩種螞蟻的數量并不是固定不變的，探索螞蟻和追蹤螞蟻可以按照算法的當前狀態互相轉變。在算法的前期，探索螞蟻數量較多，這樣可以增強算法的導向能力，加快算法的收斂；在算法的中后期，追蹤螞蟻的數量變多，將會加大對次優級路徑的探索，增加算法多樣性，使得算法不容易陷入局部最優。

其中，λi是個體適應度的大小，由式（7）計算得出，式（9）將根據個體λi的大小將螞蟻種群分為兩類，在0 ＜λi≤m中的為探索螞蟻，在m＜λi＜1 中的為追蹤螞蟻。由式（9）可以看出，兩種群體的數量會根據個體適應度的大小動態變化；m是兩種螞蟻的動態閾值界點，由式（8）計算得出，其中λmin是當前迭代最小的適應度，λmax是當前迭代最大的適應度，是當前迭代所有適應度的平均值，在算法前期，個體之間適應度的差異較大，因此m的值也較大，更多的螞蟻被選為探索螞蟻；在算法的中后期，隨著個體之間的適應度差異減小，m也相應變小，更多螞蟻被選為追蹤螞蟻。C是常數，由實驗給出，以eil51 為例，每組30次實驗，由表1可知當C取3時算法的平均誤差最小。

表1 C 的取值對精度的影響統計Table 1 Statistics on influence of value of C on accuracy

2.1.3 追蹤螞蟻的分配規則

本小節將對2.1.2小節分級后的追蹤螞蟻進行分配，每只探索螞蟻分到數量不等的追蹤螞蟻幫助其局部搜索。在算法前期，每只螞蟻得到的解的質量不等，未進行充分的發展，所有解都可以認為有相同的潛力，因此在前期將追蹤螞蟻均勻地分配給每只探索螞蟻；在算法的中后期，經過充分發展后，每只探索螞蟻的潛力將通過其各自的適應度體現，在這一階段將按照探索螞蟻的適應度成比例地分配追蹤螞蟻，適應度好的探索螞蟻會分到更多的追蹤螞蟻從而獲得更大的搜索能力，充分發揮其潛力。如圖2所示，式（10）是每只探索螞蟻按比例得到追蹤螞蟻的公式。

圖2 追蹤蟻的分配Fig.2 Distribution process of tracking ants

2.2 局部特征遷移學習機制

2.2.1 局部特征遷移策略

螞蟻在遍歷完所有城市后會得到一個解，解是由一組城市編號組成的序列，而適應度較好的個體一般具有一些共同的序列片段，這些序列片段可以看作每個個體之間共同的局部特征，本小節利用局部特征遷移策略提取出適應度較好的螞蟻個體解中一些共有的局部特征，并將這些特征遷移通過局部信息素更新將這些特征映射到信息素矩陣中，隨著算法的不斷迭代，被采集特征的樣本變多，被提取局部特征更加可靠，從而使得信息素空間更加具有導向作用，進一步提高算法的正向反饋能力。

（1）遷移樣本選擇

為了讓優秀的個體提高其影響力，本小節將選取每次迭代中適應度較好的解作為特征提取樣本，而探索蟻具有較好的適應度，因此本文選擇探索蟻作為遷移樣本。所選取的特征遷移到每只探索蟻各自被分配到的追蹤蟻的解中進行解的重組從而得到新解。

（2）特征提取

如圖3所示，每只螞蟻個體的解是由城市序列組成的數組，每次選取的特征是螞蟻走過城市編號的排列，在當前迭代下，選取的局部特征是當前探索蟻個體所有解的交集，如式（11）所示。

圖3 公共路徑選取Fig.3 Common feature selection

其中，v(t)是當前探索蟻個體所有解的交集；A1到是當前探索蟻的路徑，是由城市編號組成的一組序列，當前螞蟻走過相同的路徑超過三個節點即可被稱為公共路徑。

（3）局部特征遷移

如圖4 所示，將探索蟻的公共路徑選擇之后，算法通過局部信息素的更新對這些公共路徑進行獎勵，從而完成對局部特征的遷移，之后通過信息素矩陣的影響，加快算法的收斂速度。式（12）是針對公共路徑信息素的濃度。

圖4 特征遷移Fig.4 Feature migration process

其中，是公共路徑邊的信息素；n是城市的節點數；Lmin是當前最優路徑的長度。

2.2.2 變異學習策略

算法完成特征遷移后提高了收斂速度，但也增大了陷入局部最優的可能性，為了平衡特征遷移機制，本小節提出一種變異學習機制，幫助追蹤蟻在探索蟻路徑的次優路徑進行局部搜索。如圖5所示，在追蹤蟻完成分配后，追蹤蟻平均分布在探索蟻的路徑上，隨后針對每一段路徑進行變異學習，完成對探索蟻次優路徑的探索，從而提高算法的多樣性。若新個體比原有個體適應度好，則代替舊個體進行局部信息素更新。

圖5 變異學習Fig.5 Mutation learning process

變異學習規則對于符合要求的解在某個維度d(1 ≤d≤n)上面生成一個介于0 到1 之間的隨機數，該隨機數即為此解X的子序列X[d,d+l]突變的概率，其中d為1到n之間的一個隨機數，l是由TSP城市的規模決定的，且l在[0,n-d]之間，對于選好之后X的子序列，將其序列進行翻轉學習。在變異學習完成后，產生的新個體計算適應度并與原有個體比較，保留適應度較好的個體，提高算法效率。

2.2.3 信息素更新規則

（1）局部信息素更新

BMACS算法局部信息素更新如式（13）～（15）所示：

式（13）中λi是當前螞蟻的適應度，λmax是當前迭代適應度的最大值；式（14）中Lgb是當前迭代最優路徑的長度；式（15）中τa-l是被選中的片段更新的信息素，且只在該片段進行更新，La-l是當前螞蟻找到的路徑長度；ρ是局部信息素蒸發系數。

（2）全局信息素更新

BMACS 全局信息素更新如式（5）、式（6）所示，在完成最優解的更新之后，將對自適應回溯策略的公共區域獎勵信息素，獎勵的大小如式（6）所示將按照當前迭代的最優解進行獎勵。

2.3 匹配學習機制

傳統的蟻群算法容易陷入局部最優，一般而言，當蟻群算法的信息素矩陣在某一條路徑上的路徑的信息素濃度過高時會減少對其他路徑的探索，從而陷入局部最優；根據這一特點，當算法陷入局部最優時，通過對信息素矩陣重組，改變信息素的分布就能增加算法跳出局部最優的可能性。重組信息素的方法有很多，其中最簡單的是初始化信息素，但這種方法的缺點是不能記錄螞蟻尋解的經驗，降低了算法的搜索效率；本節中，為了盡量保留螞蟻的經驗，提出一種匹配學習機制，在該機制中，算法將會記錄每次迭代的最優解，并通過相似度評價選擇歷史最優解，并與當前最優解進行匹配學習，保留公共路徑信息素的同時，平滑非公共路徑的信息素，最大程度上保留螞蟻的優秀經驗。

2.3.1 余弦相似度

余弦相似度是通過向量的余弦值判斷個體之間差異的度量，本文中，用余弦相似度來度量當前最優解與歷史最優解之間的相似度，從而選擇一個相似度最高的歷史最優解進行匹配學習。本文選擇信息熵和公共路徑節點與總結點的比值作為當前最優解的兩個特征組成解的向量，如式（16）所示：

其中，T是余弦相似度；x和y分別是歷史最優解和當代最優解的二維向量，此二維向量(E,V)由信息熵E和公共路徑節點與總結點的比值V組成，分別由式（17）、式（18）得到。

其中，E(x)是種群的信息熵；L(x)是螞蟻x解的倒數；V是公共路徑與城市節點的比值；n是城市節點數；v是公共路徑，由式（11）得到。

2.3.2 信息素重組

通過余弦相似度匹配到學習的歷史最優解后，保留當前最優解與歷史最優解之間的信息素，而后對非公共路徑節點的信息素進行信息素的平滑操作，平滑的大小如式（19）所示：

其中，Ph是非公共路徑的信息素；Phmin是信息素中的最小值；Phmax是信息素中的最大值；通過信息素中最大值和最小值的平均值對非公共路徑的信息素進行平滑。

2.4 BMACS算法偽代碼展示

算法1解決TSP問題的BMACS算法

2.5 BMACS算法與其他算法復雜度對比分析

表2展示了不同智能算法的復雜度[12]，本文算法BMACS分別與離散蝙蝠算法（discrete bat algorithm，DBA）、自適應模擬退火蟻群算法（adaptive simulated annealing ant colony algorithm，SA-MMAS）、煙花算法（fireworks algorithm，FWA）、混沌煙花算法(chaotic fireworks algorithm，CFWA）和ACS 算法進行對比分析，結果表明，BMACS 算法的復雜度與其他智能算法的復雜度相同，并未增加算法的時間復雜度。

表2 不同算法復雜度對比Table 2 Comparison of complexity of different algorithms

3 實驗結果分析

為了驗證BMACS的算法性能，本文選取TSPLIP中14 個TSP 實例樣本對算法進行測試，每個實例進行30 次實驗，迭代2 000 次。本文實驗測試環境為Windows 10 操作系統，利用MATLAB2019a 進行仿真，并與傳統算法與其他的智能算法進行對比。

3.1 算法參數的確定

本節針對BMACS 算法的5 個參數使用正交實驗確定最佳的參數組合，如表3所示。使用城市實例eil76，建立五因素四水平的正交實驗，如表4 所示。每組的參數分別做20次實驗并做平均，如表5所示。BMACS 的最佳參數組合是：α=2，β=4，ρ=0.2，ξ=0.2，q0=0.9。

表3 BMACS的實驗因素和水平Table 3 Experimental factors and levels of BMACS

表4 正交實驗方案及BMACS實驗結果Table 4 Orthogonal test scheme and test results of BMACS

表5 BMACS測試結果分析Table 5 Analysis of test results of BMACS

3.2 BMACS算法的對比分析

本節使用14 個TSP 實例，將BMACS 算法與ACS 算法和ACS-3opt 算法進行對比，實驗結果如表6所示。誤差率的計算公式如式（20）所示：

由表6可知，BMACS算法在14個實例中在平均解、最優解、誤差率等各項指標的對比中均優于ACS-3opt、ACS 算法；在eil51、eil76 和rat99 這些小規模的城市中3 個算法均能夠找到最優解，但BMACS 算法找到最優解的收斂迭代次數要小于ACS-3opt、ACS算法，這表明BMACS 算法有更快的收斂速度；在kroA100、kroB100、ch130、kroA150、kroB150、kroA200、kroB200、tsp225 這些中等規模的城市中，BMACS 算法在kroA100、kroB100中找到了最優解，在其他的實例中誤差也均小于0.5%，這表明算法在中規模的城市中與另外兩個經典的算法相比較求解精度也較高；在大規模的城市中，求解a280 的誤差率在0.31%，在lin318、fl417 這兩個實例的求解誤差率也均在1%左右，這表明在大規模的城市中，BMACS算法也有著較高的求解精度。

由表6 的對比可知，經過特征遷移機制的影響，BMACS 算法很好地平衡了收斂速度和多樣性之間的關系，使得算法在中小規模實例中的求解性能均優于ACS-3opt、ACS算法，在大規模的城市實例中雖然沒有找到最優解，但求解的誤差也較小，這說明BMACS 算法的局部特征遷移學習策略也發揮著較好的效果。圖6 所示的是BMACS 算法找到最優解城市的路徑。

表6 ACS、ACS+3opt、BMACS在不同測試集的性能對比Table 6 Performance comparison of ACS、ACS+3opt、BMACS in different test sets

圖6 最優路徑圖Fig.6 Optimum path maps

3.2.1 BMACS算法多樣性和收斂性分析

為了更好地驗證BMACS算法性能，本小節將算法與ACS 和ACS-3opt 在收斂性和多樣性兩方面進行對比。本小節選取實例rat99、kroB150、kroA200做出各自的多樣性圖和收斂圖，結果如圖7～圖9所示。

圖7～圖9中的（a）、（b）是BMACS和ACS-3opt的多樣性圖，隨著城市數量的增多，兩種算法的標準差波動差距隨之變大，這說明算法的多樣性也更為豐富，這是通過動態分級策略中的追蹤蟻與變異學習機制的影響使得種群的多樣性得到改善。由各圖的（c）可以知道三種算法在收斂性上的表現，由收斂圖可以很明顯看到，BMACS在各種中大規模的城市中均能夠快速收斂并且求解精度也高于ACS-3opt、ACS 算法。這是由于在算法的前期，通過局部特征遷移策略將優秀個體的解與其他個體充分交流，讓其他個體吸收較好的片段，使得其快速收斂；在算法運行的中后期，算法極易陷入局部最優，匹配學習機制使得當前最優解通過相似度匹配歷史最合適的最優解，保留公共路徑的信息素，平滑非公共路徑的信息素，增加了算法后期的多樣性，使得算法在后期更容易跳出局部最優。

圖7 rat99測試集的對比Fig.7 Comparison of rat99 test set

圖8 kroA150測試集的對比Fig.8 Comparison of kroA150 test set

圖9 kroA200測試集的對比Fig.9 Comparison of kroA200 test set

3.2.2 BMACS算法與其他算法的對比分析

本小節將BMACS算法分別與隨機插入煙花算法（random insertion of fireworks algorithm，RBIFWA）[12]、自適應升溫模擬退火算法（adaptive temperature rise simulated annealing algorithm，SGSAA）[13]、基于SAC模型改進的遺傳算法（improved genetic algorithm for solving TSP problem based on SAC model，GA-SAC）[14]、基于信息素初始分配和動態更新的蟻群算法（ant colony algorithm based on initial pheromone assignment and dynamic update，IADUACO）[15]、蟻群算法與3-OPT相結合的算法（ant colony algorithm combined with 3-OPT，PACO-3OPT）[16]、基于信息熵的動態異構蟻群算法（dynamic heterogeneous ant colony algorithm based on information entropy，EDHACO）[17]、基于皮爾遜相關系數的多種群蟻群算法（multiple swarm ant colony algorithm based on Pearson correlation coefficient，PCCACO）[18]、蜘蛛猴優化算法（spider monkey optimization algorithm，DSMO）[19]與水波優化算法（water wave optimization algorithm，WWO）[20]進行對比，實驗結果表明相比其他算法，BMACS算法的精度更高，實驗結果如表7所示。

表7 BMACS算法與其他算法的對比Table 7 Comparison between BMACS algorithm and other algorithms

3.3 算法機制的有效性分析

3.3.1 BMACS個體分布及其影響

為了研究兩種個體在不同時期的影響力，本小節使用城市例子rat99列出了兩種個體在不同時期的分布圖表。圖10中的兩段折線圖分別是探索蟻與追蹤蟻在不同迭代次數下的分布。

圖10 個體分布圖Fig.10 Individual distribution map

由圖10 可知，由于動態分級策略，探索蟻、追蹤蟻的數量隨著迭代次數的變化而動態改變，探索蟻及其影響力隨著迭代次數的增大而減小，追蹤蟻及其影響力隨著迭代次數的增大而增大。

在算法前期，圖中200代左右，探索蟻數量多，對其他個體產生的影響大，通過信息素更新產生了導向作用，使得算法能夠在前期很快收斂到某個較好的路徑。同時，追蹤蟻發揮作用，搜索探索蟻周圍的次優級路徑。平衡精英個體，增加前期的多樣性，避免算法陷入局部最優。

在算法中期，圖中1 000代、1 400代左右，追蹤蟻數量增多，加大了對探索蟻周圍的搜索，增加了算法的多樣性。

在算法后期，圖中的1 800代、2 000代，追蹤蟻產生的影響最大，此時信息素已經積累到了精度較高的路徑。通過追蹤蟻的搜索，并通過局部信息素更新，算法增加其他路徑片段區域內的信息素濃度，避免算法陷入局部最優。

3.3.2 特征遷移策略的有效性分析

局部特征遷移策略作用于對螞蟻種群中的比較優秀的個體，本文選取探索蟻作為局部特征遷移的作用對象，加快算法的收斂速度。為了驗證其有效性，選取kroA100 做了三組實驗，驗證其在單獨作用時迭代速度比經典的ACS算法快。由表8所知，在局部遷移機制單獨作用下的算法與原算法相比精度與迭代速度均有所提高。隨著迭代次數的增加，算法的精度越高，對于最優解的路徑依賴就越強，個體之間的差異性越小，因此局部特征遷移策略增強了傳統蟻群算法的正向反饋。

表8 性能對比Table 8 Performance comparison

3.3.3 變異學習策略的有效性分析

變異學習策略的作用對象是追蹤蟻，變異對象由隨機數與各自的適應度對比大小選出，被篩選出的螞蟻會進行多維度的變異操作形成一個全新的個體，增加算法的多樣性。選取eil51 對不同迭代次數下單獨作用的變異學習與原算法對比多樣性，結果如圖11所示。

圖11 eil51實例上變異學習與原算法對比Fig.11 Comparison between variant learning and original algorithm on eil51

3.3.4 匹配學習機制的有效性分析

匹配學習機制可以使得算法在陷入局部最優時增加算法多樣性，保持最優個體的優勢，從而幫助其提高跳出局部最優的可能性，因此在解決較大規模的TSP問題時自適應回溯機制可以幫助ACS算法提高尋解精度。本小節用lin318、fl417這兩個大規模的實例各自做30 次實驗，對加了自適應回溯機制的ACS 算法與經典ACS 算法進行對比，驗證其有效性。由表9所知，匹配學習機制幫助ACS算法找到了更好的解，從而驗證了機制可以增加算法跳出局部最優的可能性。

表9 匹配學習機制的對比分析Table 9 Contrastive analysis of matching learning mechanism

4 結束語

針對傳統蟻群算法收斂速度慢、易于陷入局部最優等缺點，本文提出了一種引入特征遷移與匹配學習的雙蟻型蟻群算法。首先，通過動態分級將螞蟻分為探索蟻和追蹤蟻，提高了螞蟻之間的協作能力；其次，通過特征遷移策略提高了算法的收斂速度，通過變異學習策略提高算法的多樣性；最后，提出匹配學習機制幫助算法跳出局部最優。

實驗仿真結果表明，相較于經典的蟻群算法，本文算法加快了收斂速度，提高了多樣性。在解決中小規模的TSP問題時，本文算法能夠很快地找到最優解；在解決大規模TSP問題中，本文算法雖然沒有快速收斂到最優解，但依舊能保證解的多樣性，在求解精度上，誤差也較低。下一步的研究方向是利用聚類思想來解決大規模的TSP問題。