融合貓群算法的動(dòng)態(tài)分組蟻群算法*

張德惠，游曉明，劉 升

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

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

1 引言

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

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

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

2 相關(guān)研究

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

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

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

2.2.1 路徑構(gòu)建規(guī)則

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

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

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

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

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

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

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

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

2.3 貓群算法

貓群算法[16]（cat swarm optimization，CSO）是由臺(tái)灣學(xué)者Chu 等人在2006 年提出的一種新型群體智能算法。后來(lái)有很多對(duì)于貓群算法的改進(jìn)與應(yīng)用[17-18]。貓群算法將貓群分成跟蹤和搜索兩種模式。每只貓即對(duì)應(yīng)問(wèn)題的一個(gè)解。每只貓的屬性由貓的速度、貓的適應(yīng)值、貓?zhí)幱诟櫥蛩阉髂Ｊ降臉?biāo)志值組成。每只貓?zhí)幱诔跏嘉恢?，然后通過(guò)每只貓的標(biāo)志值來(lái)判斷貓?zhí)幱谒阉髂Ｊ竭€是跟蹤模式。若貓?zhí)幱诟櫮Ｊ?，則執(zhí)行跟蹤算子；若貓?zhí)幱谒阉髂Ｊ?，則執(zhí)行搜索算子。最后使得貓?zhí)幱谝粋€(gè)新的位置，并保留最優(yōu)貓直至算法滿足結(jié)束條件。

貓群算法基本步驟如下：

（1）初始化貓群；

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

（3）根據(jù)貓的標(biāo)志值對(duì)貓執(zhí)行相應(yīng)的算子，進(jìn)行位置更新；

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

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

3 改進(jìn)算法

3.1 貓群算法的引入

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

3.2 動(dòng)態(tài)分組機(jī)制

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

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

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

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

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

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

3.4 自適應(yīng)信息素?cái)U(kuò)散機(jī)制

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

Fig.1 Pheromone diffusion range圖1 信息素?cái)U(kuò)散范圍

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

其中，C2為信息素?cái)U(kuò)散因子，是(0,1)之間的一個(gè)常數(shù)；Q為螞蟻k釋放的信息素總量，是一個(gè)常數(shù)。

3.5 3-opt算子

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

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

（1）隨機(jī)生成一條初始路徑T。

（2）在路徑T上隨機(jī)選擇三點(diǎn)斷開(kāi)，形成三條路徑，每條路徑都有起點(diǎn)和終點(diǎn)。

（3）隨機(jī)交換三條路徑的起點(diǎn)和終點(diǎn)，形成一條新的路徑T′。

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

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

3.6 算法描述

步驟1參數(shù)初始化。

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

步驟3搜索螞蟻和跟蹤螞蟻分別按照式（2）和式（8）選擇下一個(gè)需要訪問(wèn)的城市,每選擇一次，螞蟻結(jié)合信息素?cái)U(kuò)散機(jī)制（見(jiàn)式（10））進(jìn)行局部信息素更新。

步驟4m只螞蟻完成一次完整的路徑構(gòu)建后，將產(chǎn)生的m個(gè)解進(jìn)行升序排序，根據(jù)動(dòng)態(tài)分組機(jī)制（見(jiàn)式（7））劃分出跟蹤螞蟻和搜索螞蟻。

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

步驟6重復(fù)步驟3～步驟5 直到達(dá)到最大迭代數(shù)，結(jié)束。

3.7 時(shí)間復(fù)雜度分析

算法1 解決TSP 問(wèn)題的CACS 算法框架

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

4 實(shí)驗(yàn)仿真與結(jié)果分析

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

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

Table 1 Parameters setting表1 參數(shù)設(shè)置

4.2 CACS 個(gè)體分布情況分析

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

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

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

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

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

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

Fig.3 kroA150 comparison of experimental results圖3 kroA150 實(shí)驗(yàn)結(jié)果對(duì)比

Fig.4 d198 cmparison of experimental results圖4 d198 實(shí)驗(yàn)結(jié)果對(duì)比

Fig.5 a280 comparison of experimental results圖5 a280 實(shí)驗(yàn)結(jié)果對(duì)比

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

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

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

圖7 給出參加實(shí)驗(yàn)的13 個(gè)不同規(guī)模城市中達(dá)到標(biāo)準(zhǔn)最優(yōu)解的路徑圖。

4.4 與改進(jìn)蟻群算法以及其他算法進(jìn)行對(duì)比

本文改進(jìn)的算法還與其他改進(jìn)的蟻群算法以及其他智能算法進(jìn)行比較來(lái)驗(yàn)證其性能。表3 中改進(jìn)單種群蟻群算法（ant colony algorithm for heuristic dynamic pheromone update strategy，D-ACS）數(shù)據(jù)來(lái)自于文獻(xiàn)[19]，面向旅行商問(wèn)題改進(jìn)的蟻群算法（improved ant colony algorithm，IACA）數(shù)據(jù)來(lái)自于文獻(xiàn)[20]，改進(jìn)粒子群算法（improved random greedy particle swarm optimization based on Hamming distance,IMRGHPSO）數(shù)據(jù)來(lái)自于文獻(xiàn)[21]，遺傳算法（genetic algorithm，GA）和人工蜂群算法（artificial bee colony algorithm，ABC）數(shù)據(jù)來(lái)自于文獻(xiàn)[22]。從表3 中可看出，CACS 算法所得的解的質(zhì)量明顯優(yōu)于IMRGHPSO、GA 以及ABC 這三種智能算法；與單蟻群的改進(jìn)算法D-ACS以及面向旅行商問(wèn)題改進(jìn)的蟻群算法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é)的實(shí)驗(yàn)對(duì)比分析，本文所提出的融合貓群算法的動(dòng)態(tài)分組蟻群算法與傳統(tǒng)蟻群法、改進(jìn)蟻群算法以及其他智能算法相比均具有一定的優(yōu)勢(shì)，解的質(zhì)量以及收斂速度均有一定程度的提高。

4.5 算法性能分析

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

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

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

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

5 結(jié)束語(yǔ)

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

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