引入動(dòng)態(tài)分化和鄰域誘導(dǎo)機(jī)制的雙蟻群優(yōu)化算法

禹博文　游曉明　劉升

摘 要：為提高傳統(tǒng)蟻群算法在解決旅行商問題時(shí)的優(yōu)化效果，提出了一種引入動(dòng)態(tài)分化和鄰域誘導(dǎo)機(jī)制的雙蟻群優(yōu)化算法。該算法首先引入混沌隨機(jī)策略，在算法初始化階段改變?cè)嫉呢澬牟呗裕钩跏夹畔⑺鼗煦绶植?，以保持種群的多樣性，從而提高解的精度；其次，將蟻群分為孤立蟻群與正常蟻群，兩組螞蟻分別在當(dāng)前最優(yōu)路徑與離群路徑附近搜索；在種群間采取誘導(dǎo)機(jī)制，正常蟻負(fù)責(zé)搜索最優(yōu)路徑，孤立蟻混沌隨機(jī)釋放信息素，將正常蟻群誘導(dǎo)至新的路徑鄰域，從而有效地平衡收斂速度與解的多樣性之間的矛盾。通過對(duì)不同規(guī)模的旅行商問題仿真結(jié)果的比較，驗(yàn)證了所提算法的有效性。

關(guān)鍵詞：旅行商問題； 蟻群優(yōu)化； 動(dòng)態(tài)分化策略； 混沌隨機(jī)； 誘導(dǎo)策略

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2023）10-018-3000-07

doi：10.19734/j.issn.1001-3695.2023.02.0060

Dual-ant colony optimization algorithm with dynamic differentiation and neighborhood induction mechanism

Yu Bowena， You Xiaominga， Liu Shengb

（a.School of Electronic & Electrical Engineering， b.School of Management， Shanghai University of Engineering Science， Shanghai 201620， China）

Abstract：In order to improve the optimization effect of traditional ant colony algorithm in solving traveling salesman problem， this paper developed a dual-ant colony optimization algorithm with dynamic differentiation and neighborhood induction mechanism. Firstly， the algorithm introduced chaotic random strategy， and changed the original greedy strategy in the initialization stage of the algorithm to chaotic distribute the initial pheromone， so as to maintain the diversity of the population and improve the accuracy of the solution. Secondly， the algorithm divided the isolated ants in the ant colony into isolated ant colony and normal ant colony， and the two groups of ants searched around the current optimal path and the outlier path respectively. It adopted the induction mechanism among the populations. Normal ants were responsible for searching the optimal path， and isolated ants released pheromones randomly in chaos to induce the normal ant colony to a new path， thus effectively balancing the contradiction between the convergence rate and the diversity of solutions. The simulation results of different scale TSP show the effectiveness of the proposed algorithm.

Key words：traveling salesman problem; ant colony optimization; dynamic differentiation strategy; chaos random; induction strategy

0 引言

旅行商問題是一種組合優(yōu)化問題，其目的是給定一組城市的坐標(biāo)，求出遍歷所有坐標(biāo)并返回起始位置的一條最短路徑。旅行商問題是一種NP難問題，在運(yùn)籌學(xué)與計(jì)算機(jī)科學(xué)中具有非常重要的地位。目前有許多算法被提出用于解決TSP問題，如模擬退火（simulated annealing，SA）、遺傳算法（genetic algorithm，GA）、螞蟻算法（ant system，AS）［1］等。其中螞蟻算法在TSP上有較好的效果。

螞蟻算法是意大利學(xué)者Dorigo提出的一種啟發(fā)式全局搜索算法，通過模仿自然界中螞蟻釋放信息素尋路的過程實(shí)現(xiàn)路徑搜索。蟻群算法具有分部性、隨機(jī)性、動(dòng)態(tài)性等優(yōu)良性能，并且具有很好的可移植性［2］，能被應(yīng)用在不同種類的問題上。目前被廣泛應(yīng)用于車間調(diào)度［3］、路徑規(guī)劃［4］、路由問題［5］和求解旅行商問題［6］上。傳統(tǒng)螞蟻算法存在一定的局限性。例如蟻群算法在搜索初期缺乏信息素，延遲了算法的收斂速度。在算法的中后期，由于信息素大量積累在部分路徑，導(dǎo)致固定路徑的選擇概率過高，容易使算法陷入局部最優(yōu)，影響解的質(zhì)量。于是Dorigo等人[7]在螞蟻算法的基礎(chǔ)上提出了蟻群算法（ant colony system，ACS）提出了全局信息素更新，加快了求解TSP時(shí)的速度。Stutzle等人［8］在2000年又提出最大—最小蟻群算法（max-min ant system，MMAS），設(shè)置了每條路徑上的信息素上下限，提高了解的質(zhì)量。

針對(duì)算法收斂速度慢的問題，許多學(xué)者在蟻群算法的基礎(chǔ)上作出了改進(jìn)。文獻(xiàn)［9］引入了信息熵理論，通過計(jì)算信息熵判斷蟻群的離散度，根據(jù)系統(tǒng)的離散程度調(diào)整算法參數(shù)提高解的性能。但是在前期信息熵濃度較低時(shí)，不能很好拓展解的多樣性容易導(dǎo)致在前期陷入局部最優(yōu)。文獻(xiàn)［10］利用貪心算法求解蟻群算法的初始解，然后計(jì)算初始解的次優(yōu)解，對(duì)次優(yōu)解也給予一定的信息素獎(jiǎng)勵(lì)，加快了解的收斂速度。同時(shí)在算法后期引入變異操作，選取當(dāng)前最優(yōu)路徑附近的路徑進(jìn)行加權(quán)。然而，根據(jù)貪心算法計(jì)算得出的最優(yōu)解與次優(yōu)解有可能與真實(shí)最優(yōu)解距離較遠(yuǎn)，有可能在算法的初期陷入局部最優(yōu)。在算法容易陷入局部最優(yōu)解的問題上也有許多改進(jìn)算法被提出，文獻(xiàn)［11］融合狼群算法的分級(jí)策略，依據(jù)解的大小將蟻群分為不同等級(jí)的螞蟻，并根據(jù)不同螞蟻的地位分配不同的權(quán)重，使精英螞蟻能夠分泌更多的信息素，對(duì)蟻群起指導(dǎo)作用。文獻(xiàn)［12］在結(jié)合精英蟻群機(jī)制的基礎(chǔ)上加入了頭狼算法，即對(duì)每一個(gè)螞蟻加入搜索半徑，精英蟻選擇搜索半徑內(nèi)的任意一個(gè)節(jié)點(diǎn)進(jìn)行跳變。同時(shí)在陷入局部最優(yōu)后對(duì)局部最優(yōu)節(jié)點(diǎn)的信息素進(jìn)行稀釋，達(dá)到跳出局部最優(yōu)的目的。但精英策略在搜索時(shí)搜索速度較慢，經(jīng)常導(dǎo)致算法的運(yùn)行時(shí)間過長。文獻(xiàn)［13］在精英策略的基礎(chǔ)上增加了自適應(yīng)分組策略，各個(gè)組螞蟻的數(shù)目能夠動(dòng)態(tài)調(diào)整并在組間增加了學(xué)習(xí)策略，但自適應(yīng)分組只是將螞蟻分為數(shù)量不同的組，并沒有對(duì)每組螞蟻進(jìn)行分工。文獻(xiàn)［14］將3opt搜索算法與改進(jìn)蟻群算法相結(jié)合，利用3opt算法的近鄰搜索能力拓展搜索空間，在保證搜索速度的同時(shí)提高了算法的局部搜索能力。文獻(xiàn)［15］提出一種刺激響應(yīng)機(jī)制，根據(jù)不同任務(wù)設(shè)置響應(yīng)閾值，按照不同任務(wù)刺激的大小對(duì)螞蟻進(jìn)行分工，當(dāng)任務(wù)刺激超過某只螞蟻的響應(yīng)閾值后將該螞蟻分配至對(duì)應(yīng)任務(wù)，同時(shí)引入正負(fù)反饋調(diào)節(jié)機(jī)制，根據(jù)種群多樣性利用正負(fù)反饋調(diào)節(jié)螞蟻數(shù)量，平衡了收斂速度與全局搜索能力，但以上幾種算法面對(duì)大規(guī)模TSP時(shí)往往效果不好，收斂速度慢，且容易陷入局部最優(yōu)解。

針對(duì)上述蟻群算法搜索速度慢，在大規(guī)模問題上解的精度不高等問題，本文通過加入以下策略提出一種引入動(dòng)態(tài)分化和鄰域誘導(dǎo)機(jī)制的雙蟻群優(yōu)化算法（ICACO）。在搜索的前期引入混沌隨機(jī)策略［16］，使地圖中的信息素和螞蟻的位置進(jìn)行混沌隨機(jī)更新，取代傳統(tǒng)蟻群算法初始化時(shí)的貪心策略［10］，在搜索前期使信息素隨機(jī)地散布在各條路徑上以增加解的多樣性；其次，提出一種孤立分化機(jī)制，首先，根據(jù)信息素、路徑長度構(gòu)建歸一化模型，按照信息素的分離度使蟻群分為正常種群和分化種群，正常種群沿當(dāng)前信息素最大的路徑探索，孤立種群沿新路徑進(jìn)行搜索，并在新路徑上混沌更新信息素值，一旦發(fā)現(xiàn)更優(yōu)路徑即釋放更多的信息素于更優(yōu)路徑上并將正常種群引導(dǎo)至新的路徑。實(shí)驗(yàn)結(jié)果表明，本文算法相比于原始算法提高了收斂速度和解的質(zhì)量，在大規(guī)模TSP上表現(xiàn)更好。

1 相關(guān)工作

1.1 蟻群算法（ACS）

蟻群算法是一種模擬自然界蟻群覓食行為的啟發(fā)式算法。螞蟻在覓食過程中會(huì)留下信息素，其他螞蟻在前進(jìn)時(shí)會(huì)更大概率選擇信息素濃度較高的路徑。相同時(shí)間內(nèi)在較短路徑上積累的信息素變多，蟻群便找到最短路徑，在旅行商問題上有很好的表現(xiàn)。蟻群算法相對(duì)于最初的螞蟻算法（AS）增加了信息素的局部揮發(fā)。即每只螞蟻?zhàn)哌^一段路徑后，其留下的信息素就會(huì)立即揮發(fā)一部分，而非全體螞蟻?zhàn)哌^后信息素的全局揮發(fā)。其更新規(guī)則為

其中：τ（i，j）為節(jié)點(diǎn)i到j(luò)之間的信息素；ρ是信息素的局部揮發(fā)率；Δτ（i，j）為節(jié)點(diǎn)i與j之間的信息素增量；釋放信息素后，螞蟻按照式（2）選擇下一個(gè)節(jié)點(diǎn)。

其中：pkij表示螞蟻k從節(jié)點(diǎn)i到j(luò)的概率；τij（t）表示節(jié)點(diǎn)i到j(luò)之間t時(shí)刻的信息素總量；η表示節(jié)點(diǎn)i到j(luò)之間距離的倒數(shù);β為權(quán)重因子，代表啟發(fā)信息對(duì)路徑選擇的影響程度，β越大則啟發(fā)信息對(duì)路徑選擇的影響程度越大；allowedk表示螞蟻k還未走過的節(jié)點(diǎn)。所有螞蟻遍歷過一次后進(jìn)行信息素的全局更新，對(duì)所有路徑上的信息素進(jìn)行更新，更新方式如式（5）所示。

其中：α為全局信息素?fù)]發(fā)系數(shù)，代表上一次迭代后信息素的殘留比例；Q為信息素更新權(quán)重;dbest為全局最短路徑；ACS在全局信息素更新時(shí)只留下全局最優(yōu)螞蟻的信息素。并且隨著迭代次數(shù)的增加，最優(yōu)路徑上的信息素不斷累加，會(huì)導(dǎo)致算法陷入局部最優(yōu)。

1.2 動(dòng)態(tài)分級(jí)的改良螞蟻算法

為了解決傳統(tǒng)蟻群算法收斂速度慢的問題，文獻(xiàn)［9］提出一種動(dòng)態(tài)分級(jí)的螞蟻算法，按照分級(jí)因子將螞蟻分為四個(gè)等級(jí)，根據(jù)等級(jí)的高低為螞蟻劃分不同的信息素更新權(quán)重，等級(jí)高的螞蟻可以釋放更多的信息素，同時(shí)又給予等級(jí)低的螞蟻一定的信息素釋放量以增加算法的多樣性。定義分級(jí)因子為

其中：di為螞蟻遍歷所有節(jié)點(diǎn)走過的路徑長度;dmin為當(dāng)前最短路徑。各個(gè)等級(jí)的螞蟻數(shù)量隨迭代次數(shù)調(diào)整，其信息素更新方式與式（5）相同，不同之處在于信息素增量Δτ（i，j），定義為

其中：Q1、Q2、Q3為各個(gè)等級(jí)能釋放的信息素總量，處于第一等級(jí)的螞蟻釋放信息素最多，依次遞減，處于最后一級(jí)的螞蟻禁止釋放信息素；n1、n2、n3為各個(gè)等級(jí)螞蟻的數(shù)量。通過各個(gè)等級(jí)螞蟻數(shù)量的不斷調(diào)整最終達(dá)到算法的平衡。

1.3 Logistic混沌隨機(jī)

混沌隨機(jī)是一種利用混沌映射產(chǎn)生隨機(jī)數(shù)的策略，具有非周期、不收斂的特性，其中應(yīng)用較為廣泛的為Logistic映射，其表達(dá)式為

其中：xn+1、xn為混沌序列值;k為混沌因子。混沌序列的作用在于產(chǎn)生一列非線性、不可預(yù)測(cè)的隨機(jī)數(shù)，這些數(shù)字在k取3.569

2 引入動(dòng)態(tài)分化和鄰域誘導(dǎo)機(jī)制的雙蟻群優(yōu)化算法

2.1 算法的混沌初始化

在蟻群算法的初期，地圖上沒有信息素，導(dǎo)致算法前期搜索速度慢，同時(shí)由于只能利用距離信息初始化算法，導(dǎo)致算法前期易陷入局部最優(yōu)［8］。并且由于傳統(tǒng)產(chǎn)生隨機(jī)數(shù)的策略為偽隨機(jī)策略，在大規(guī)模TSP時(shí)不利于種群的搜索多樣性。所以在蟻群搜索的前期，在各個(gè)城市路徑上混沌更新信息素量，使系統(tǒng)前期各個(gè)路徑上散布隨機(jī)量的信息素，避免蟻群盲目搜索，增加系統(tǒng)的收斂速度。同時(shí)，由于混沌更新的不可預(yù)測(cè)性與隨機(jī)性，避免了傳統(tǒng)蟻群算法根據(jù)貪心算法初始化導(dǎo)致的部分路徑完全不會(huì)被搜索到，增加了系統(tǒng)解的多樣性避免前期陷入局部最優(yōu)。算法具體更新方式如下：

其中：i為當(dāng)前迭代次數(shù)；當(dāng)算法第一次迭代時(shí)，各個(gè)城市間的距離信息作為初始化信息素τ0加上混沌序列產(chǎn)生的隨機(jī)信息素信息，其中q為混沌調(diào)節(jié)因子，用于調(diào)節(jié)系統(tǒng)初始化時(shí)的混沌程度，q越大則系統(tǒng)信息素初始化時(shí)會(huì)更隨機(jī)。式中c為Logistic混沌參數(shù)，c的值越大則混沌程度越大，產(chǎn)生出的隨機(jī)數(shù)更隨機(jī)，n為總城市數(shù)，b為控制因子；當(dāng)?shù)螖?shù)小于n/b定義為初始化階段，在初始化階段系統(tǒng)信息素更新采用混沌更新方式，保證信息素廣泛散播。

2.2 孤立分化策略

2.2.1 孤立策略

傳統(tǒng)蟻群搜索的過程存在一定的盲目性，每只螞蟻都只在信息素濃度最高的路徑上搜索，這導(dǎo)致算法只聚焦于搜索最優(yōu)解而忽視了其他路徑，其他路徑有可能蘊(yùn)涵著真正的最優(yōu)解。在大規(guī)模TSP問題中該問題尤其突出。在所有螞蟻遍歷完各城市后，會(huì)得到此次遍歷路線的總長度，每一只螞蟻得到的路線和總長度不同。在算法后期，大多數(shù)螞蟻會(huì)選擇相同的路線，部分螞蟻會(huì)選擇新的路線，即使新路線的路徑長度大于次優(yōu)路線長度，這些新路線中可能包含全局最優(yōu)路徑的一部分，本節(jié)利用孤立種群策略挑選出走新路線的種群形成孤立種群，然后將信息素與其他個(gè)體不同的路線片段提取并加強(qiáng)該路徑上的信息素，提高算法的路徑選擇能力。

孤立種群判定：

在系統(tǒng)經(jīng)過一定次數(shù)迭代后，將對(duì)原始種群進(jìn)行動(dòng)態(tài)分化，迭代次數(shù)如式（11）所示。

其中：T1為左閾值，T2為右閾值；Lx是第x只螞蟻?zhàn)哌^的路徑長度，Ly是第y只螞蟻?zhàn)哌^的路徑長度；m為螞蟻總數(shù)。將所有螞蟻?zhàn)哌^的路徑按路徑長短從小到大排列，走過路徑超過左右閾值的個(gè)體被認(rèn)定為孤立個(gè)體。

2.2.2 分化策略

當(dāng)孤立種群確定后，螞蟻將分為正常種群和孤立種群，正常種群仍然按照原始路徑搜索，孤立種群按照式（16）進(jìn)行信息素更新，孤立種群在新路徑的周圍搜索，擴(kuò)大了解的范圍。當(dāng)發(fā)現(xiàn)比當(dāng)前最優(yōu)路徑更短的路徑時(shí)，蟻群將釋放更多的信息素在更優(yōu)路徑上。孤立種群在最優(yōu)路徑的周圍利用Logistic混沌釋放隨機(jī)量的信息素，直到更優(yōu)路徑的產(chǎn)生，并將蟻群引導(dǎo)到新的位置。孤立種群信息素更新方式為

誘導(dǎo)機(jī)制：

在對(duì)原始蟻群進(jìn)行分化后，孤立種群將按照式（16）釋放信息素。為了更好地?cái)U(kuò)大搜索空間，本文提出一種誘導(dǎo)機(jī)制，當(dāng)孤立種群找到更優(yōu)路徑后，將原始路徑上的信息素清空，加強(qiáng)孤立種群所釋放出的信息素濃度并將其擴(kuò)散，將原始種群引導(dǎo)至孤立種群所發(fā)現(xiàn)的新路徑周圍，施行誘導(dǎo)機(jī)制后信息素分布如圖4所示。在種群分化后，首先將孤立種群所走過的路線進(jìn)行one-hot編碼［17］，然后與原始路徑上的信息素相乘，使信息素矩陣只保留孤立種群所留下的信息素，如圖5所示。誘導(dǎo)公式如式（17）所示。

其中：τ為所有路線上的信息素;Li為按照one-hot編碼后孤立種群走過的路徑矩陣，即將每一步中孤立種群選擇的路徑置1，未選擇的路徑置0，使孤立種群釋放的信息素?cái)U(kuò)散至鄰域，將蟻群引入新的路徑。

2.3 算法流程

a）初始化算法各參數(shù)：最大迭代次數(shù)imax、各個(gè)種群螞蟻數(shù)量m，與α、β、ρ、c等參數(shù)，讀入城市位置數(shù)據(jù)。

b）利用混沌序列產(chǎn)生隨機(jī)數(shù)量的信息素分配到各條路徑，再利用混沌序列產(chǎn)生每只螞蟻起始位置。

c）每只螞蟻按照位置更新公式進(jìn)行搜索，找到一條完整路徑。記錄當(dāng)前迭代最短路徑長度。

d）計(jì)算路徑不變代數(shù)是否超過閾值G，若超過則啟動(dòng)孤立分化，選擇出孤立種群。

e）分化后的孤立種群按照新的信息素更新方式釋放信息素。

f）孤立種群找到更優(yōu)路徑時(shí)按照誘導(dǎo)機(jī)制將原始種群誘導(dǎo)至新的路徑搜索。

g）判斷是否達(dá)到結(jié)束條件，若未達(dá)到則返回步驟b）否則結(jié)束算法并記錄結(jié)果。

算法流程如圖6所示。

3 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證和分析本文算法的有效性，選取TSPLIB中幾個(gè)典型問題進(jìn)行仿真測(cè)試與傳統(tǒng)蟻群算法ACS、ACS+3opt進(jìn)行比較，并與其他同類算法進(jìn)行比較。在小規(guī)模和大規(guī)模問題上分別選取不同的算法進(jìn)行對(duì)比，以驗(yàn)證算法在面對(duì)大規(guī)模問題時(shí)的有效性。同時(shí)針對(duì)算法的收斂速度，將算法與基本蟻群算法（ACS）和ACS+3opt算法在三種不同規(guī)模的TSP上進(jìn)行比較，對(duì)比本文算法與其他算法的收斂速度與結(jié)果。

3.1 實(shí)驗(yàn)環(huán)境設(shè)置

本文實(shí)驗(yàn)環(huán)境為：Windows 10操作系統(tǒng)，利用MATLAB 2018a進(jìn)行仿真。為了驗(yàn)證算法在各個(gè)規(guī)模TSP問題中的有效性，選擇分別與傳統(tǒng)蟻群算法ACS與ACS+3opt算法進(jìn)行不同規(guī)模的TSP進(jìn)行測(cè)試。同時(shí)選擇與目前最新的改進(jìn)型蟻群算法文獻(xiàn)［9，10，18，19］進(jìn)行對(duì)比，分析比較本文算法的改進(jìn)。實(shí)驗(yàn)中算法參數(shù)設(shè)置如表1所示。

3.2 與傳統(tǒng)算法對(duì)比結(jié)果

首先設(shè)置與ACS和ACS+3opt算法進(jìn)行對(duì)比。將各個(gè)算法運(yùn)行10次，比較每種算法在求解TSP時(shí)的最優(yōu)解、平均解、最小誤差百分比與收斂時(shí)間。其中平均值向下取整，最小誤差百分比保留兩位小數(shù)，設(shè)置最大迭代次數(shù)為5 000，收斂時(shí)間為算法開始到最終收斂所用時(shí)間，以秒為單位。結(jié)果如表2所示。

通過對(duì)比可以看出本文算法在應(yīng)對(duì)小規(guī)模問題時(shí)有很好的表現(xiàn)，在各個(gè)算例中均能找到最優(yōu)解或與最優(yōu)解之間最小誤差小于1%，并且可以看出實(shí)驗(yàn)結(jié)果的平均解與最優(yōu)解之間誤差較小，證明了算法的穩(wěn)定性。在Eil51、Eil76等小規(guī)模問題上，ACS、ACS+3opt與ICACO均能找到最優(yōu)路徑，但I(xiàn)CACO平均解的質(zhì)量優(yōu)于ACS、ACS+3opt。通過在更大規(guī)模旅行商問題上與基本蟻群算法的對(duì)比可以看出，隨著旅行商問題的規(guī)模增大，ACS、ACS+3opt的精度有所下降，而本文算法保持了很好的精度，最優(yōu)解仍然保持在1%以內(nèi)的精度，算法的最優(yōu)解與平均解均優(yōu)于ACS和ACS+3opt算法。在算法的收斂時(shí)間對(duì)比上，在小規(guī)模TSP問題eil51、eil76、rat99上ACS與ACS+3opt算法的收斂速度快于ICACO，隨著TSP的規(guī)模不斷增大到100以上時(shí)，由于動(dòng)態(tài)分化策略能夠有效地加快收斂速度ICACO的收斂速度逐漸超過ACO與ACO+3opt，并且隨著問題規(guī)模的增大，ICACO的收斂速度也越來越高于ACO、ACO+3opt，這是由于隨著問題規(guī)模的增大ACO與ACO+3opt不可避免地陷入局部最優(yōu)，導(dǎo)致算法的尋優(yōu)能力不足，難以找到更優(yōu)解，而ICACO由于存在鄰域誘導(dǎo)機(jī)制，可以幫助種群在大規(guī)模問題上更好地拓展解空間避免陷入局部最優(yōu)。

3.3 與最新改進(jìn)算法對(duì)比結(jié)果

為了保證實(shí)驗(yàn)的客觀性，將ICACO與目前最新的改進(jìn)算法在TSP上進(jìn)行對(duì)比，對(duì)比結(jié)果如表3所示。表中“-”表示該文未做該實(shí)驗(yàn)。由表3可以看出在與當(dāng)今最新的算法比較時(shí)，本文算法仍然有很好的表現(xiàn)。在大中小規(guī)模的TSP問題中本文算法最優(yōu)結(jié)果均優(yōu)于其他算法，在各個(gè)問題中均能保證誤差在1%左右，隨著TSP問題的規(guī)模逐漸增大，許多算法已經(jīng)無法找到結(jié)果并且平均解很差。本文算法在處理大規(guī)模問題時(shí)使用了孤立分化機(jī)制，大規(guī)模問題中各個(gè)算法往往難以避免陷入局部最優(yōu)，本文算法通過加入誘導(dǎo)機(jī)制，在種群陷入局部最優(yōu)后可以跳出局部最優(yōu)，增加解的多樣性，提高解的質(zhì)量從而找到更優(yōu)解。其中部分實(shí)驗(yàn)路徑結(jié)果如圖7所示。

3.4 與其他多種群蟻群算法對(duì)比

為了體現(xiàn)本文算法的有效性，本文選擇了其他多種群蟻群算法進(jìn)行對(duì)比分析。其中文獻(xiàn)［13］為自適應(yīng)分組蟻群算法，根據(jù)迭代情況將種群分為不同大小的種群，文獻(xiàn)［15］將螞蟻分為常規(guī)螞蟻和拓展螞蟻，分別負(fù)責(zé)搜索效率與搜索廣度。

通過表4可以看出，在各個(gè)小于100規(guī)模的TSP上本文算法性能都優(yōu)于對(duì)比算法，在ch130數(shù)據(jù)集上最優(yōu)路徑文獻(xiàn)［15］算法優(yōu)于本文算法但本文算法的平均解優(yōu)于文獻(xiàn)［15］算法。從表4可以看出， 由于文獻(xiàn)［13］算法只將螞蟻進(jìn)行分組而未對(duì)其進(jìn)行不同分工，導(dǎo)致算法解的精度不足，而ICACO將螞蟻動(dòng)態(tài)分組，調(diào)整不同種群螞蟻的數(shù)量的同時(shí)設(shè)置不同的搜索路線和信息素釋放方式，保證兩種螞蟻相互合作，在加快算法收斂速度的同時(shí)提高解的質(zhì)量。文獻(xiàn)［15］算法雖然將螞蟻進(jìn)行不同分工，但并沒有提出跳出局部最優(yōu)的機(jī)制，在算法后期容易陷入局部最優(yōu)，降低解的精度，而ICACO通過鄰域誘導(dǎo)機(jī)制，在孤立蟻發(fā)現(xiàn)更優(yōu)路線后將種群誘導(dǎo)至新路線附近，加強(qiáng)對(duì)新路線的搜索，在算法后期能夠很好地提高解的精度。

表4顯示了對(duì)比結(jié)果，缺失的數(shù)據(jù)用“-”代替。

3.5 算法性能分析

3.5.1 算法多樣性分析

為了證明本文算法增加解的多樣性的有效性，通過對(duì)比算法在處理TSP問題時(shí)每一代路徑的長度，對(duì)算法的多樣性進(jìn)行分析。實(shí)驗(yàn)結(jié)果如圖8所示。

通過對(duì)比算法在運(yùn)行TSP時(shí)每一代路徑長度與總路徑長度可以看出，算法在陷入局部最優(yōu)時(shí)，利用孤立分化策略增加解的多樣性，隨著算法后期不可避免地陷入停滯，孤立個(gè)體數(shù)也在不斷增大，算法的解空間也在逐漸增大，最終在算法4 500次迭代后找到了優(yōu)化解，保證了算法在搜索后期能夠跳出局部最優(yōu)找到更優(yōu)解。

3.5.2 算法收斂性分析

為了比較算法在收斂速度上的提高，選擇在rand400、eil51兩個(gè)規(guī)模的TSP上與ACS、ACS+3opt算法進(jìn)行實(shí)時(shí)收斂過程對(duì)比，為保證實(shí)驗(yàn)準(zhǔn)確性選擇相同數(shù)量的螞蟻數(shù)，在小規(guī)模問題的測(cè)試中將迭代次數(shù)設(shè)為5 000次，將大規(guī)模問題的最大迭代次數(shù)設(shè)為2 000次。實(shí)驗(yàn)結(jié)果如圖9所示。

通過對(duì)比三種算法在大小兩個(gè)規(guī)模上的運(yùn)行結(jié)果，可以看出本文算法在搜索初期就能很快收斂，最優(yōu)路徑快速迭代，算法不斷找到更優(yōu)解且具有較好的搜索能力。在大規(guī)模問題rd400上可以更明顯地看出，ACS、ACS+3opt算法在搜索初期就陷入了局部最優(yōu)，而本文算法在搜索初期采用混沌初始化策略，有效避免了算法在初期陷入早熟。同時(shí)在搜索的后期可以看出ACS算法在迭代到一定次數(shù)以后便無法找到更優(yōu)路徑，過早陷入局部最優(yōu)使得在大規(guī)模問題時(shí)無能為力。而ACS+3opt算法仍不能避免算法在初期就陷入早熟，算法初期的多樣性較差，而在算法后期雖然有一定的跳出局部最優(yōu)解的能力，但由于搜索能力不足同樣導(dǎo)致算法陷入局部最優(yōu)。本文算法在每次迭代初始化時(shí)采用混沌隨機(jī)機(jī)制使搜索能力得到加強(qiáng)，同時(shí)引入孤立分化機(jī)制使迭代后期最優(yōu)路徑長度仍能不斷下降，找到更優(yōu)路徑，有較強(qiáng)的跳出局部最優(yōu)能力使得算法面對(duì)大規(guī)模問題時(shí)有較強(qiáng)的魯棒性。通過對(duì)比三種算法的收斂結(jié)果，可以看出本文算法很好地平衡了收斂速度與精度，初期搜索結(jié)果快速下降，大大加快了搜索速度，同時(shí)后期可以有效地跳出局部最優(yōu)提高解的精度。

3.5.3 改進(jìn)策略有效性分析

為分析改進(jìn)算法中各個(gè)策略的有效性，設(shè)置算法ICACO-1、ICACO-2與ICACO算法進(jìn)行對(duì)比實(shí)驗(yàn)，對(duì)每個(gè)改進(jìn)策略進(jìn)行有效性分析。對(duì)比算法使用策略如表5所示。通過在不同數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)，將結(jié)果總結(jié)在表6中。其中ICACO-1只使用鄰域誘導(dǎo)機(jī)制，不對(duì)螞蟻進(jìn)行分化，所有螞蟻都設(shè)置為正常種群，當(dāng)有螞蟻找到更優(yōu)路徑后就會(huì)將所有螞蟻引至新路徑。ICACO-2只使用動(dòng)態(tài)分化策略，將螞蟻分化為正常蟻與孤立蟻，不使用鄰域誘導(dǎo)策略進(jìn)行信息素矩陣更新。

由表6可以看出，在小規(guī)模問題eil51、eil76、kroA100上ICACO、ICACO-1、ICACO-2均能找到最優(yōu)解，而當(dāng)數(shù)據(jù)集規(guī)模增大，ICACO-2在eil101、pr107、ch130數(shù)據(jù)集上的表現(xiàn)優(yōu)于ICACO-1，表明將種群動(dòng)態(tài)分化為正常蟻與孤立蟻能夠有效地拓展搜索范圍，使算法在搜索階段具有很好的性能。當(dāng)數(shù)據(jù)集規(guī)模提升到400以上時(shí)算法容易陷入局部最優(yōu)，而ICACO-1在kroA200、rd400、fl417、pr439數(shù)據(jù)集上的表現(xiàn)優(yōu)于ICACO-2，表明鄰域誘導(dǎo)機(jī)制在大規(guī)模問題上能夠有效幫助算法避免陷入局部最優(yōu)。而同時(shí)使用動(dòng)態(tài)分化機(jī)制和鄰域誘導(dǎo)策略的ICACO由于孤立蟻的存在，在解的精度上比單獨(dú)使用正常蟻進(jìn)行搜索的ICACO-1提高了50%左右。實(shí)驗(yàn)結(jié)果ICACO在各個(gè)數(shù)據(jù)集上的表現(xiàn)都比單獨(dú)使用一種策略的算法優(yōu)秀，表明動(dòng)態(tài)分化機(jī)制和鄰域誘導(dǎo)策略能夠很好地幫助算法提高搜索能力。

3.5.4 算法復(fù)雜度分析

表7中n為節(jié)點(diǎn)數(shù);m為螞蟻總數(shù);m1為孤立螞蟻數(shù);m2為正常種群個(gè)數(shù);i為最大迭代次數(shù)。通過表7可知，ICACO的時(shí)間復(fù)雜度為O（i×n2×m），由此可以看出動(dòng)態(tài)分化機(jī)制和鄰域誘導(dǎo)機(jī)制沒有額外增加算法的時(shí)間復(fù)雜度。

4 結(jié)束語

本文分析了現(xiàn)有蟻群算法與幾種改進(jìn)蟻群算法，針對(duì)其不足之處提出了一種引入動(dòng)態(tài)分化和鄰域誘導(dǎo)機(jī)制的雙蟻群優(yōu)化算法。該算法首先將螞蟻位置和路徑上的信息素進(jìn)行混沌隨機(jī)，加快了算法的搜索速度；其次通過孤立分化策略將螞蟻分為原始種群和孤立種群，提高了解的多樣性。實(shí)驗(yàn)結(jié)果表明本文算法在TSP求解上效果良好，尤其針對(duì)大規(guī)模TSP時(shí)也具有很好的表現(xiàn)，但在更大規(guī)模的TSP上仍存在收斂速度慢等問題。下一步的研究方向是利用多種群博弈策略解決更大規(guī)模TSP。

參考文獻(xiàn)：

[1]Dorigo M， Maniezzo V， Colorni A. Ant system： optimization by a co-lony of cooperating agents［J］.IEEE Trans on Systems， Man， and Cybernetics， Part B，1996，26（1）：29-41.

［2]張宏宏，甘旭升，李雙峰，等.復(fù)雜低空環(huán)境下考慮區(qū)域風(fēng)險(xiǎn)評(píng)估的無人機(jī)航路規(guī)劃［J］.儀器儀表學(xué)報(bào)，2021，42（1）：257-266.（Zhang Honghong， Gan Xusheng， Li Shuangfeng， et al. UAV route planning considering regional risk assessment under complex low altitude environment［J］.Chinese Journal of Scientific Instrument，2021，42（1）：257-266.）

［3]李燚，唐倩，劉聯(lián)超，等.基于改進(jìn)蟻群算法的汽車混流裝配調(diào)度模型求解［J］.中國機(jī)械工程，2021，32（9）：1126-1133.（Li Yan， Tang Qian， Liu Lianchao， et al. An improved ACO algorithm for automobile mixed-flow assembly scheduling problems［J］.China Mechanical Engineering，2021，32（9）：1126-1133.）

［4]包漢，祝海濤，劉迪.基于±3σ正態(tài)概率區(qū)間分族遺傳蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃研究［J］.控制與決策，2021，36（12）：2861-2870.（Bao Han， Zhu Haitao， Liu Di. Path planning of a mobile robot based on ±3σ normal probability interval population division using the genetic ant-colony algorithm［J］.Control and Decision，2021，36（12）：2861-2870.）

［5]孫明杰，周林，于云龍，等.無人機(jī)自組網(wǎng)中基于蟻群優(yōu)化的多態(tài)感知路由算法［J］.系統(tǒng)工程與電子技術(shù)，2021，43（9）：2562-2572.（Sun Mingjie， Zhou Lin， Yu Yunlong， et al. Ant colony optimization based polymorphism-aware routing algorithm for Ad hoc UAV network［J］.System Engineering and Electronics，2021，43（9）：2562-2572.）

［6]Pan Han， You Xiaoming， Liu Sheng， et al. Pearson correlation coefficient-based pheromone refactoring mechanism for multi-colony ant colony optimization［J］.Applied Intelligence，2020，51（2）：1-23.

［7]Dorigo M， Gambardella L M. Ant colony system： a cooperative lear-ning approach to the traveling salesman problem［J］.IEEE Trans on Evolutionary Computation，1997，1（1）：53-66.

［8]Stutzle T， Hoos H H. Max-min ant system［J］.Future Generation Computer Systems，2000，16（8）：889-914.

［9]陳佳，游曉明，劉升，等.結(jié)合信息熵的多種群博弈蟻群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2019，55（16）：170-178.（Chen Jia， You Xiao-ming， Liu Sheng， et al. Entropy-game based multi-population ant colony optimization［J］.Computer Engineering and Applications，2019，55（16）：170-178.）

［10]陳穎杰，高茂庭.基于信息素初始分配和動(dòng)態(tài)更新的蟻群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2022，58（2）：95-101.（Chen Yingjie， Gao Maoting. Pheromone initialization and dynamic update based ant colony algorithm［J］.Computer Engineering and Applications，2022，58（2）：95-101.）

［11]陳佳，游曉明，劉升，等.動(dòng)態(tài)分級(jí)的改良螞蟻算法及其應(yīng)用研究［J］.計(jì)算機(jī)應(yīng)用研究，2019，36（2）：380-384.（Chen Jia， You Xiao-ming， Liu Sheng， et al. Research on dynamic hierarchical ant optimization algorithm and its application［J］.Application Research of Computers，2019，36（2）：380-384.）

［12]張毅，權(quán)浩，文家富.基于獨(dú)狼蟻群混合算法的移動(dòng)機(jī)器人路徑規(guī)劃［J］.華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2020，48（1）：127-132.（Zhang Yi， Quan Hao， Wen Jiafu. Mobile robot path planning based on the wolf ant colony hybrid algorithm［J］.Huazhong University of Science & Technology：Natural Science Edition，2020，48（1）：127-132.）

［13]卜冠南，劉建華，姜磊，等.一種自適應(yīng)分組的蟻群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2021，57（6）：67-73.（Bu Guannan， Liu Jianhua， Jiang Lei， et al. An ant colony algorithm with adaptive grouping［J］.Computer Engineering and Applications，2021，57（6）：67-73.）

［14]Gülcü瘙塁， Mahi M， BaykanK， et al. A parallel cooperative hybrid method based on ant colony optimization and 3-opt algorithm for solving traveling salesman problem［J］.Soft Computing，2018，22（5）：1669-1685.

［15]馮振輝，肖人彬.基于混合反饋機(jī)制的擴(kuò)展蟻群算法［J］.控制與決策，2022，37（12）：3160-3170.（Feng Zhenhui， Xiao Renbin. Extended ant colony algorithm based on mixed feedback mechanism［J］.Control and Decision，2022，37（12）：3160-3170.）

［16]馬小陸，袁書生，王兵，等.均勻分布Logistic混沌序列的RRT路徑規(guī)劃算法研究［J］.機(jī)械科學(xué)與技術(shù)，2022，41（4）：610-618.（Ma Xiaolu， Yuan Shusheng， Wang Bing， et al. Research on RRT path planning algorithm for uniformly distributed Logistic chaotic sequence［J］.Mechanical Science and Technology for Aerospace Engineering，2022，41（4）：610-618.）

［17]梁杰，陳嘉豪，張雪芹，等.基于獨(dú)熱編碼和卷積神經(jīng)網(wǎng)絡(luò)的異常檢測(cè)［J］.清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2019，59（7）：523-529.（Liang Jie， Chen Jiahao， Zhang Xueqin， et al. One-hot encoding and convolutional neural network based anomaly detection［J］.Journal of Tsinghua University：Science and Technology Edition，2019，59（7）：523-529.）

［18]Tuani A F， Keedwell E， Collett M. Heterogenous adaptive ant colony optimization with 3-opt local search for the travelling salesman pro-blem［J］.Applied Soft Computing，2020，97（PB）：106720.

［19]Huang Yao， Shen Xiaoning， You Xuan. A discrete shuffled frog-leaping algorithm based on heuristic information for traveling salesman problem［J］.Applied Soft Computing，2021.102：107085.

收稿日期：2023-02-28；修回日期：2023-04-17

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（61673258，61075115）；上海市自然科學(xué)基金資助項(xiàng)目（19ZR1421600）

作者簡介：禹博文（1997-），男，河南鄭州人，碩士研究生，主要研究方向?yàn)橹悄芩惴?、機(jī)器學(xué)習(xí)、人工智能；游曉明（1963-），女（通信作者），江蘇興化人，教授，碩導(dǎo)，博士，主要研究方向?yàn)槿褐悄芟到y(tǒng)、分布式并行處理、進(jìn)化算法（yxm6301@163.com）；劉升（1966-），男，湖北大冶人，教授，碩導(dǎo)，博士，主要研究方向?yàn)榱孔訂l(fā)式進(jìn)化算法、分布式并行處理、進(jìn)化算法.