張德惠，游曉明，劉 升

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

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

1 引言

旅行商問題（traveling salesman problem，TSP）是一類經典的組合優(yōu)化問題，是指一位旅行者從某一起點出發(fā)，通過所有給定的需求點，且每個需求點只經過一次，最后回到起點的最短路徑問題。

蟻群算法（ant colony optimization，ACO）[1-2]最初由意大利學者Dorigo 等在1996 年根據螞蟻覓食機制而提出的用來解決旅行商和分布式優(yōu)化問題的一種算法。例如，人們利用蟻群算法來解決路徑規(guī)劃[3]、車間調度以及網絡路徑負載均衡[4]等問題。其中蟻群算法在解決TSP 問題的實驗中能夠提供較好的解決方案，但在解決大規(guī)模問題時會出現(xiàn)陷入局部最優(yōu)和收斂速度慢等問題。后來，Dorigo 又提出了蟻群系統(tǒng)（ant colony system，ACS）[5]，將局部信息素更新與全局信息素更新相結合，提高算法的收斂速度。2000 年，Stutzle 等提出了最大最小蟻群算法（minmax ant system，MMAS）[6]，通過限制信息素的范圍來改善算法中過早停滯的問題。以上是經典的螞蟻算法，它們具有高效的搜索能力，但仍存在著容易陷入局部最優(yōu)、收斂速度慢等問題。文獻[7]使用了一種改進信息素二次更新與局部優(yōu)化策略，實驗結果證明這些算法增強了全局搜索能力，多樣性更好，但是收斂速度卻有待提高。李俊等人[8]提出融入2-opt 鄰域搜索策略，增強算法對TSP 問題解的構造能力,從而提高解的質量。文獻[9]利用信息素全局更新和局部更新動態(tài)結合的方法，使當前最優(yōu)路徑上的信息素能夠動態(tài)地調配，幫助算法跳出局部最優(yōu)，避免算法停滯。張立毅等人[10]將細菌覓食算法和蟻群算法相結合以改進蟻群算法收斂速度慢和易陷入局部最優(yōu)的不足。為了平衡多樣性和收斂速度，文獻[11]定義一種新的方向信息素來刻畫尋優(yōu)過程中的全局信息，從而保證在最優(yōu)路徑的基礎上提高解的全局性，并加快算法的收斂。此外，由于新的探索率因子的提出及全局選擇策略的修正，使得信息素較弱的路徑得以選擇，進而擴大了搜索的范圍，提高了算法的魯棒性。文獻[12]提出了一種用貓群算法來解決TSP 問題，利用貓群的跟蹤搜尋兩種特殊模式，使其兼顧了較好的全局搜索性質和不易陷入局部最優(yōu)解的兩種優(yōu)勢。以上改進的蟻群算法中，在大規(guī)模的TSP 問題中仍然存在收斂速度慢且容易陷入局部最優(yōu)等問題。

為此，本文提出了一種融合貓群算法的動態(tài)分組蟻群算法。貓群算法中利用貓的搜索和跟蹤兩種特性來平衡算法的多樣性和收斂速度，故本文利用貓群算法中的分工思想引入動態(tài)分組機制，將參與實驗的螞蟻分為搜索螞蟻和跟蹤螞蟻，帶著不同的任務去執(zhí)行各自的路徑構建以及信息素更新算子。通過定義動態(tài)分組算子使前期搜索螞蟻多，增加解的多樣性；后期跟蹤螞蟻多，加快收斂速度，進一步結合信息素擴散機制避免算法陷入局部最優(yōu)，最后利用3-opt 算子優(yōu)化解的質量。實驗結果表明，改進后的算法的多樣性及收斂速度均優(yōu)于傳統(tǒng)蟻群算法以及其他智能算法。

2 相關研究

2.1 蟻群算法原理及研究現(xiàn)狀

20 世紀90 年代初期科學家通過實驗發(fā)現(xiàn)，螞蟻在進行覓食時，會在走過的路徑上留下一種對同類有吸引性的化學物質——信息素，螞蟻會根據信息素濃度的大小來選擇下一條路徑，濃度越高被選中的幾率越大。同時由于信息素的揮發(fā)特性，較差路徑上的信息素會越來越少，從而最優(yōu)路徑也就能慢慢地被選擇出來。目前已經出現(xiàn)了各種對蟻群算法的改進，例如：對算法參數進行優(yōu)化，對信息素更新規(guī)則或路徑構建規(guī)則進行改進[13]，使用其他智能算法優(yōu)化蟻群算法[14-15]等。雖然這些改進算法在一定程度上改善了算法的性能，但是仍然存在多樣性不足，收斂速度慢等問題。而本文改進算法與其他改進算法不同的是，引入貓群算法的思想對螞蟻進行了分工，加強了螞蟻之間的協(xié)作能力，使算法能夠更好地平衡多樣性與收斂速度。與其他改進算法相同的是，對擁有不同任務的螞蟻的路徑構建規(guī)則以及信息素更新規(guī)則進行了改進，使其達到相應的效果。

2.2 蟻群系統(tǒng)解決TSP 問題

2.2.1 路徑構建規(guī)則

在ACS 算法中，螞蟻k當前位置在i處，按照偽隨機比例規(guī)則來選擇下一個將要訪問的城市j，其規(guī)則如式（1）：

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

其中，α為信息啟發(fā)式因子；β為期望啟發(fā)式因子；為螞蟻下一步可以直接到達并且尚未訪問過的城市的集合；ηij為啟發(fā)函數，其表達式為式（3）：

2.2.2 信息素更新規(guī)則

局部信息素更新規(guī)則：螞蟻在進行一次路徑選擇時，即從當前城市i到下一個城市j后，立即更新信息素，其公式如式（4）：

其中，ρ為局部信息素蒸發(fā)系數，其范圍為(0,1)；τ0為信息素初始值，經實驗發(fā)現(xiàn)τ0取1/nC時，算法能擁有較好的性能；n為城市數目，C是由最近鄰方法得到的路徑長度。

全局信息素更新規(guī)則：所有螞蟻進行一次迭代后更新信息素，且只有在全局最優(yōu)路徑上的螞蟻可以更新，這樣加快了算法的收斂速度，其公式如式（5）：

其中，ξ為全局信息素蒸發(fā)系數；Cbs為全局最優(yōu)路徑的長度；為全局最優(yōu)路徑上增加的信息素，按式（6）計算。

2.3 貓群算法

貓群算法[16]（cat swarm optimization，CSO）是由臺灣學者Chu 等人在2006 年提出的一種新型群體智能算法。后來有很多對于貓群算法的改進與應用[17-18]。貓群算法將貓群分成跟蹤和搜索兩種模式。每只貓即對應問題的一個解。每只貓的屬性由貓的速度、貓的適應值、貓?zhí)幱诟櫥蛩阉髂Ｊ降臉酥局到M成。每只貓?zhí)幱诔跏嘉恢茫缓笸ㄟ^每只貓的標志值來判斷貓?zhí)幱谒阉髂Ｊ竭€是跟蹤模式。若貓?zhí)幱诟櫮Ｊ剑瑒t執(zhí)行跟蹤算子；若貓?zhí)幱谒阉髂Ｊ?，則執(zhí)行搜索算子。最后使得貓?zhí)幱谝粋€新的位置，并保留最優(yōu)貓直至算法滿足結束條件。

貓群算法基本步驟如下：

（1）初始化貓群；

（2）根據分組率將貓群隨機劃分為跟蹤和搜索兩種模式；

（3）根據貓的標志值對貓執(zhí)行相應的算子，進行位置更新；

（4）計算每只貓的適應度，記錄并保留適應度最優(yōu)的貓；

（5）若滿足結束條件則終止算法，否則再返回步驟（2）。

3 改進算法

3.1 貓群算法的引入

傳統(tǒng)的蟻群算法是各個螞蟻單獨行動且每只螞蟻都執(zhí)行相同的操作，螞蟻之間的協(xié)作不足，可能會導致滯后、算法陷入局部最優(yōu)以及減少找到最優(yōu)解的可能性等問題。而貓群算法采用貓的跟蹤搜索兩種特殊模式使其兼顧了較好的全局搜索性質和不易陷入局部最優(yōu)解的兩種優(yōu)勢。但是貓群算法自身也存在著很多的局限性，貓群算法中的貓執(zhí)行的不同模式是根據分組率隨機劃分的，而該分組率是定值，算法從始至終處于兩種模式的貓的數量是一定的，在算法前期也會有部分貓執(zhí)行跟蹤模式，這部分貓缺乏全局搜索性質，算法多樣性較差；在算法后期仍然有部分貓?zhí)幱谒阉髂Ｊ?，在無目標搜索，導致收斂速度下降。故3.2 節(jié)中引入動態(tài)分組機制，使貓群算法中的分組率動態(tài)變化，增加螞蟻之間的協(xié)作交流，最大化地平衡多樣性與收斂速度。本文算法將m只螞蟻分成搜索螞蟻和跟蹤螞蟻兩類：搜索螞蟻主要負責增加多樣性；跟蹤螞蟻主要負責在加快收斂速度的同時能避免陷入局部最優(yōu)解。在一定迭代數后，重新分配跟蹤螞蟻與搜索螞蟻，增加螞蟻之間的交流，利于尋找更優(yōu)解。

3.2 動態(tài)分組機制

CACS（dynamic grouping ant colony algorithm combined with cat swarm optimization）在種群初始化時，讓每只螞蟻能分配在不同的初始城市（螞蟻數若大于城市數時，則使螞蟻能夠均勻分布在不同的城市），使構建的解的多樣性更加豐富。本文引入動態(tài)分組算子ε動態(tài)地將m只螞蟻分為搜索螞蟻m(1-ε)只和跟蹤螞蟻mε只。其劃分規(guī)則為：將每次迭代后螞蟻所走的路徑進行升序排序，排序后的路徑所對應的前mε只螞蟻變成跟蹤螞蟻，其余為搜索螞蟻。ε公式為式（7），由式（7）可看出，每只螞蟻在每一代都有可能會改變自己的職責，或者為跟蹤螞蟻或者為搜索螞蟻，將前幾名路徑的螞蟻變?yōu)楦櫸浵仯Y合3.4 節(jié)的信息素擴散機制，突出較優(yōu)路徑的重要性以及較優(yōu)路徑附近的較優(yōu)子路徑的作用，避免陷入局部最優(yōu)；而跟蹤螞蟻和搜索螞蟻的數量卻是間隔一定代數才會變化，這是為了避免跟蹤螞蟻在前期過多，導致信息素過量累積，降低算法的性能。

其中，iter為當前迭代數；max_iter為最大迭代數。螞蟻選擇下一個城市的概率規(guī)則為：跟蹤螞蟻按照式（2）進行路徑構建，搜索螞蟻按照式（8）進行路徑構建。

其中，μ為環(huán)境適應度因子閾值，是(0,1)之間的常數；隨著迭代的繼續(xù)，某些路徑上的信息素會逐漸增加，使算法具有導向性，故設f為環(huán)境適應度因子，隨著迭代數的增加，ε越來越大，f越來越小。因此在算法的前期，搜索螞蟻的數量多且搜索螞蟻選擇×rand的概率也大，豐富了解的多樣性；后期時，跟蹤螞蟻數量多，搜索螞蟻數量少并且按照傳統(tǒng)ACS 的路徑選擇的概率變大，算法具有導向性逐漸收斂。

3.3 CACS 信息素更新規(guī)則

CACS 算法采用的是局部信息素更新和全局信息素更新相結合的信息素更新機制，本文對局部信息素更新規(guī)則進行了變異，見式（10），信息素增加的部分是對跟蹤螞蟻的額外獎勵，該獎勵源自于信息素擴散機制，將在3.4 節(jié)詳細介紹。全局信息素更新規(guī)則為式（5）。局部信息素更新側重開發(fā)較差路徑中的較優(yōu)子路徑，提高多樣性，降低陷入局部最優(yōu)的可能；全局信息素更新側重加快算法的收斂速度。

其中，ρ為局部信息素蒸發(fā)速率；為第t次迭代跟蹤螞蟻在附近邊釋放的可以擴散的信息素擴散到邊(i,j)的信息素量，其公式見式（11）。

3.4 自適應信息素擴散機制

由于傳統(tǒng)蟻群算法螞蟻間協(xié)作不足，存在陷入局部最優(yōu)的缺陷，故CACS 提出信息素自適應擴散機制來加強螞蟻間的協(xié)作。在跟蹤螞蟻進行路徑構建時，當其從城市i轉移到城市j時，不僅會釋放一定濃度的信息素在邊(i,j)上，還會額外釋放一定濃度的信息素在城市i上，然后以城市i為圓心，以dij為半徑向四周其他子路徑進行信息素的自適應擴散。該信息素一方面直接影響后代經過邊(i,j)上的螞蟻，另一方面還會影響當代附近螞蟻的行為。

Fig.1 Pheromone diffusion range圖1 信息素擴散范圍

為防止信息素過度累積，降低算法的性能，令只有跟蹤螞蟻能產生可以擴散的信息素。如圖1，以i為圓心dij為半徑的圓為信息素擴散區(qū)域，當跟蹤螞蟻從城市i轉移到城市j時，會額外產生能擴散的信息素，令此信息素集中在城市i點，則此時i處信息素最大，記為τmax，則其信息素以i為圓心，以dij為半徑向四周擴散。若此時存在城市g到城市i的距離dig＜dij時，則螞蟻k在第t次迭代時在城市i上的信息素擴散到邊(i,g)上的信息素量為式（12）。dig越小時，擴散到邊(i,g)的信息素越多，越能使該較優(yōu)子路徑發(fā)揮作用，且選用dij作為揮發(fā)半徑達到自適應的效果。在傳統(tǒng)蟻群算法的中后期，算法會逐漸收斂，螞蟻所探索到的路徑逐漸收斂在一些路徑之間，使獲得的解的多樣性下降，算法容易陷入局部最優(yōu)。而信息素擴散機制一方面能使陷入局部最優(yōu)解中的子路徑以及該局部最優(yōu)解路徑附近的較優(yōu)子路徑上的信息素濃度增加，加大了后代螞蟻選擇該較優(yōu)子路徑的概率，保持著解的多樣性，避免算法陷入局部最優(yōu)；另一方面，在算法后期，信息素擴散機制給較優(yōu)子路徑增加了信息素，使更多的螞蟻以更大的可能性選擇這些優(yōu)質的子路徑，而該子路徑很大可能是最優(yōu)解的一部分，故信息素擴散機制也適當地提高了算法的收斂速度。

其中，C2為信息素擴散因子，是(0,1)之間的一個常數；Q為螞蟻k釋放的信息素總量，是一個常數。

3.5 3-opt算子

為了使蟻群算法每次迭代過程中產生的解能夠得到優(yōu)化，采用3-opt算子進行優(yōu)化。

3-opt算法的基本流程如下：

（1）隨機生成一條初始路徑T。

（2）在路徑T上隨機選擇三點斷開，形成三條路徑，每條路徑都有起點和終點。

（3）隨機交換三條路徑的起點和終點，形成一條新的路徑T′。

（4）比較T與T′，留下較優(yōu)路徑。

（5）重復（3）和（4），直至所有交換的可能都比較結束。

3.6 算法描述

步驟1參數初始化。

步驟2將m只螞蟻均勻地放置在不同的初始城市，m只螞蟻全定義為搜索螞蟻。

步驟3搜索螞蟻和跟蹤螞蟻分別按照式（2）和式（8）選擇下一個需要訪問的城市,每選擇一次，螞蟻結合信息素擴散機制（見式（10））進行局部信息素更新。

步驟4m只螞蟻完成一次完整的路徑構建后，將產生的m個解進行升序排序，根據動態(tài)分組機制（見式（7））劃分出跟蹤螞蟻和搜索螞蟻。

步驟5將當前最優(yōu)解用3-opt進行優(yōu)化得到更優(yōu)解，將此更優(yōu)解路徑根據式（5）進行全局信息素更新。

步驟6重復步驟3～步驟5 直到達到最大迭代數，結束。

3.7 時間復雜度分析

算法1 解決TSP 問題的CACS 算法框架

從算法1 的算法流程中可以看出，跟蹤螞蟻與搜索螞蟻是獨立運行的，因此CACS 的時間復雜度是O(nc×m1×(n-1)+nc×m2×(n-1))，其中m1為每代跟蹤螞蟻的數量，m2為每代搜索螞蟻的數量，設總螞蟻數為m，則CACS 時間復雜度為O(nc×m×n)，ACS 的最大時間復雜度也為O(nc×m×n)。由此，本文的改進算法并沒有增加時間復雜度。

4 實驗仿真與結果分析

4.1 仿真環(huán)境與參數設置

為驗證改進后的算法性能，本文實驗測試環(huán)境為：Windows 10 操作系統(tǒng)，利用Matlab2016a 對TSP標準數據庫中的多組不同規(guī)模的城市進行仿真。對于實驗參數的設置，在ACS 實驗的基礎上，經過多次實驗參數的調節(jié)與數據統(tǒng)計發(fā)現(xiàn)，在ACS、ACS+3opt、CACS 這三種對比算法中所使用的參數值設置如表1 時，實驗效果最好。在三種對比實驗中，參數均設一致進行對比有較強的說服力且對于設計實驗時也方便。

Table 1 Parameters setting表1 參數設置

4.2 CACS 個體分布情況分析

圖2 為算法在eil51 算例上隨著迭代數的變化搜索螞蟻與跟蹤螞蟻的分布情況，其中橫軸為迭代數，縱軸為數量。搜索螞蟻與跟蹤螞蟻一共50 只，圖中第一列Scount為搜索螞蟻的數量，第二列Spath為搜索螞蟻在該迭代數下所產生的不同的路徑數量，第三列Gcount為跟蹤螞蟻的數量，第四列Gpath為跟蹤螞蟻在該迭代數下所產生的不同的路徑數量。從圖2 中可看出，由于動態(tài)分組機制，搜索螞蟻與跟蹤螞蟻的數量隨著迭代數的變化而變化，搜索螞蟻越來越少，跟蹤螞蟻越來越多。前期搜索螞蟻數量多，本文對搜索螞蟻的路徑構建機制進行了改善，使算法的多樣性更加豐富；中期搜索螞蟻與跟蹤螞蟻數量相當，與前期分析相同，搜索螞蟻能夠保持多樣性，而跟蹤螞蟻執(zhí)行信息素擴散機制在加快收斂速度的同時起到了保持多樣性，從而避免陷入局部最優(yōu)的作用。從圖2 中可看到，算法從前期的200 代和400代，到中期的1 000 代和1 200 代時，Gcount和Gpath的數量變化漸漸有了差距，說明跟蹤螞蟻所產生的解正在慢慢收斂，而Scount與Spath的數量變化差距正在逐漸變小，說明雖然搜索螞蟻的數量越來越少，但是算法的多樣性并沒有下降；后期跟蹤螞蟻數量多。從圖2 中也可看出，產生的不同路徑的數量也并沒有下降太多，這是由于信息素擴散機制使局部最優(yōu)路徑附近的子路徑加大了被選擇的概率，能夠跳出局部最優(yōu)，從而多樣性沒有過度下降。從圖2 中可看出，算法從中期的1 000 代和1 200 代到后期的1 800 代和2 000 代時，Gcount與Gpath的數量差距隨著迭代數的增加越來越大，而Gpath的值依舊很高，說明在后期算法的收斂速度在加快，但是由于信息素擴散機制使多樣性依然較好，從而使算法能夠跳出局部最優(yōu)。

Fig.2 Ants distribution at different time圖2 不同時期螞蟻分布圖

4.3 與傳統(tǒng)蟻群算法對比分析

對于小規(guī)模城市，現(xiàn)在大部分算法都能很好地找到最優(yōu)解且多樣性也較豐富，故本文選取kroA150、d198、a280 三種中大規(guī)模的城市結果進行對比分析。在ACS、ACS+3opt、CACS 三種算法中分別進行了15 次實驗，每次實驗進行2 000 次迭代，統(tǒng)計實驗數據得到圖3～圖5 實驗結果圖。

從圖3～圖5 中的（a）、（b）圖可以看出，CACS 算法由于動態(tài)分組機制使前期搜索螞蟻數量較多，再搭配搜索螞蟻中被改善過的路徑構建規(guī)則，從而使CACS 算法的多樣性大大增加。從kroA150 到d198再到a280，隨著城市規(guī)模的不斷增大，從圖中也可看出，多樣性波動的差距也越來越大，表明多樣性的豐富度也在增加，能以更大的可能性找到更優(yōu)的解。從多樣性的圖中還可看出，CACS 算法在后期依然保持著多樣性，由于后期跟蹤螞蟻數量多，而跟蹤螞蟻利用信息素擴散機制避免算法陷入局部最優(yōu)，從而繼續(xù)保持著算法的多樣性。而對于算法的收斂性，跟蹤螞蟻利用局部信息素擴散機制和全局信息素更新的共同作用，加快了算法的收斂速度。從圖3～圖5 的（c）圖可以看出，CACS 的收斂性優(yōu)于ACS 和ACS+3opt，且解的質量也更好。

為了更好地驗證CACS 的性能，本文從TSP 測試集中選取了13 個不同規(guī)模的城市進行實驗，并與ACS 和ACS+3opt算法進行對比，結果如表2。從表2中eil51、eil76、rat99 等小規(guī)模城市的實驗結果可知，CACS 能夠快速地找到最優(yōu)解，且最差解與平均解均優(yōu)于ACS 和ACS+3opt。對于kroA100、kroA150、kroA200、kroB100、kroB150、kroB200、ch130 以 及d198 的中規(guī)模實驗結果中，kroA100 和kroB150 均找到了最優(yōu)解，其余城市雖然沒有找到最優(yōu)，但是誤差值均在1%以內，也說明了本文算法性能優(yōu)于另外兩種算法。對于a280、lin318 等大規(guī)模城市的測試雖然沒有找到標準最優(yōu)解，但測試結果顯示CACS 還是優(yōu)于原始ACS 且誤差值保持在1%左右。綜合以上：CACS 整體上改善了算法的多樣性與收斂速度，尋優(yōu)能力大大超過了ACS 和ACS+3opt。

Fig.3 kroA150 comparison of experimental results圖3 kroA150 實驗結果對比

Fig.4 d198 cmparison of experimental results圖4 d198 實驗結果對比

Fig.5 a280 comparison of experimental results圖5 a280 實驗結果對比

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

圖6 給出了參加實驗的13 個城市的平均誤差率，結合表2 中的平均解可看出：本文算法得到的平均解以及平均誤差率均優(yōu)于另外兩種算法。隨著城市規(guī)模的不斷增加，三種算法的平均誤差率的差距也處于增大的趨勢中，這表明CACS 算法比ACS 和ACS+3opt 更加穩(wěn)定，且城市規(guī)模越大這種穩(wěn)定性越明顯。

Fig.6 Comparison of algorithm stability圖6 算法穩(wěn)定性對比

圖7 給出參加實驗的13 個不同規(guī)模城市中達到標準最優(yōu)解的路徑圖。

4.4 與改進蟻群算法以及其他算法進行對比

本文改進的算法還與其他改進的蟻群算法以及其他智能算法進行比較來驗證其性能。表3 中改進單種群蟻群算法（ant colony algorithm for heuristic dynamic pheromone update strategy，D-ACS）數據來自于文獻[19]，面向旅行商問題改進的蟻群算法（improved ant colony algorithm，IACA）數據來自于文獻[20]，改進粒子群算法（improved random greedy particle swarm optimization based on Hamming distance,IMRGHPSO）數據來自于文獻[21]，遺傳算法（genetic algorithm，GA）和人工蜂群算法（artificial bee colony algorithm，ABC）數據來自于文獻[22]。從表3 中可看出，CACS 算法所得的解的質量明顯優(yōu)于IMRGHPSO、GA 以及ABC 這三種智能算法；與單蟻群的改進算法D-ACS以及面向旅行商問題改進的蟻群算法IACA 相比較，解的精度也較優(yōu)。

Table 3 Comparison of CACS with other algorithms on TSP instances表3 CACS 與其他算法在TSP 案例上的比較

Fig.7 The optimum path圖7 最優(yōu)路徑

綜合3.2 節(jié)與3.3 節(jié)的實驗對比分析，本文所提出的融合貓群算法的動態(tài)分組蟻群算法與傳統(tǒng)蟻群法、改進蟻群算法以及其他智能算法相比均具有一定的優(yōu)勢，解的質量以及收斂速度均有一定程度的提高。

4.5 算法性能分析

在算法的前期，傳統(tǒng)蟻群算法由于信息素的差距不大，其對于路徑選擇的干擾不大，故多樣性較豐富；本文算法提出的動態(tài)分組機制使搜索螞蟻的數量多于跟蹤螞蟻，因此算法產生的解基本上來源于搜索螞蟻，而本文對搜索螞蟻的路徑構建規(guī)則進行了改善。根據式（8）可知，環(huán)境適應度因子f是根據迭代數的改變而改變的，迭代開始時，f值較大，搜索螞蟻基本上按照×rand路徑構建規(guī)則選擇下一個城市，由于rand的隨機性，算法在前期多樣性表現(xiàn)得很好。

在算法的中期，傳統(tǒng)蟻群算法由于路徑之間的信息素逐漸產生差距，其對于螞蟻路徑的構建已經能起到大部分的作用了，會使算法的多樣性降低，可能會導致算法停滯；本文改進算法在中期搜索螞蟻與跟蹤螞蟻數量相當，此時f較小，搜索螞蟻對于路徑構建的選擇會有部分使用×rand，而rand的隨機性使一部分搜索螞蟻增加了隨機選擇路徑的可能性，這部分螞蟻能夠保持著算法的多樣性，而跟蹤螞蟻由于信息素擴散機制，使可能陷入局部最優(yōu)的路徑或其他較優(yōu)路徑附近的較優(yōu)子路徑得到更多的信息素，加大了較優(yōu)子路徑被選擇的概率，減少了算法趨于停滯的可能性。

在算法的后期，傳統(tǒng)蟻群算法由于路徑之間的信息素差距較大，其對螞蟻的路徑構建完全干擾，使算法更容易陷入局部最優(yōu)；本文算法在此時跟蹤螞蟻的數量多于搜索螞蟻，因此算法產生的解基本上來源于跟蹤螞蟻，雖然此時搜索螞蟻依然存在，其對于路徑的選擇跟傳統(tǒng)蟻群算法一樣，但是搜索螞蟻過少，對于算法的整體幾乎沒有影響。對于跟蹤螞蟻，由于其使用信息素擴散機制使局部最優(yōu)路徑附近的較優(yōu)子路徑的信息素得到增加，加大了較優(yōu)子路徑被選擇的概率，有利于算法跳出局部最優(yōu)，從而也保持著算法的多樣性。并且由于跟蹤螞蟻的信息素擴散機制使較優(yōu)子路徑上的信息素逐漸累積，而這些子路徑很可能是最優(yōu)解的一部分，信息素擴散機制使更多的螞蟻以更大的可能性去選擇這些較優(yōu)子路徑，會使算法逐漸向收斂趨勢發(fā)展。再加上信息素全局更新機制對每次迭代產生的優(yōu)解路徑進行信息素更新也會加快收斂速度，故算法整體上在后期收斂速度會被加快。

故本文改進算法在整體上平衡了多樣性與收斂速度，使獲得的解的質量更優(yōu)。

5 結束語

針對傳統(tǒng)蟻群所存在的容易陷入局部最優(yōu)以及收斂速度慢等問題，本文提出了一種融合貓群算法的動態(tài)分組蟻群算法，引入動態(tài)分組機制將螞蟻分為搜索螞蟻和跟蹤螞蟻。搜索螞蟻改善了路徑構建規(guī)則，使算法多樣性得以豐富；跟蹤螞蟻改善了信息素更新規(guī)則，保持了算法的多樣性，避免算法陷入局部最優(yōu)，最后使用信息素全局更新機制加快了算法的收斂速度。

仿真結果表明，本文算法不僅提高了多樣性，也在一定程度上加快了收斂速度。在中小規(guī)模的TSP問題上，該算法能快速地找到最優(yōu)解，在大規(guī)模的TSP 問題上雖然不能快速地找到最優(yōu)解，但還是能保證解的多樣性和解的相對質量。下一步的研究方向是利用多種群來繼續(xù)研究大規(guī)模城市的路徑優(yōu)化問題。