融合動(dòng)態(tài)鄰域搜索機(jī)制的蟻群系統(tǒng)算法*

郭文強(qiáng) 杜正毅

融合動(dòng)態(tài)鄰域搜索機(jī)制的蟻群系統(tǒng)算法*

郭文強(qiáng) 杜正毅

（新疆財(cái)經(jīng)大學(xué)信息管理學(xué)院，新疆 烏魯木齊 830012）

針對(duì)蟻群算法收斂速度慢，容易陷入局部最優(yōu)解等問(wèn)題，提出一種融合動(dòng)態(tài)鄰域搜索機(jī)制的蟻群系統(tǒng)（DNS-ACS）算法。首先，在蟻群系統(tǒng)算法的基礎(chǔ)上，引入2-opt算子進(jìn)行局部搜索，加快算法收斂速度；然后，動(dòng)態(tài)調(diào)整鄰域搜索范圍和信息素更新規(guī)則，使其跳出局部最優(yōu)，避免早熟現(xiàn)象；最后，利用本文提出的DNS-ACS算法對(duì)16個(gè)經(jīng)典TSP算例進(jìn)行仿真模擬，并與其他算法進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，DNS-ACS算法的求解精度明顯提高，證明了該算法的有效性。

蟻群算法；旅行商問(wèn)題；動(dòng)態(tài)鄰域搜索；信息素更新

0 引言

旅行商問(wèn)題（travelling salesman problem, TSP）是指給定一系列城市和每?jī)勺鞘兄g的距離，求解訪問(wèn)每座城市一次并回到起始城市的最短回路，是一類標(biāo)準(zhǔn)的組合離散優(yōu)化問(wèn)題[1]，也是一個(gè)NP難問(wèn)題。

TSP有精確算法和啟發(fā)式算法2種求解方法。其中，精確算法包括切割平面法、動(dòng)態(tài)規(guī)劃法、分支定界法[2]等，該類方法可有效求得TSP的最優(yōu)解，但需要指數(shù)時(shí)間，不適用于大規(guī)模的TSP；啟發(fā)式方法包括蟻群優(yōu)化算法（ant colony optimization, ACO）[3]、帝國(guó)競(jìng)爭(zhēng)算法[4]、模擬退火法[5]、貓群算法[6]、禁忌搜索算法[7]、粒子群優(yōu)化算法[8]、人工蜂群算法[9]等，該類算法能夠在有限的時(shí)間內(nèi)得到問(wèn)題的滿意解，是解決TSP的常用方法。

蟻群算法是具有代表性的群智能算法之一[10]，由DORIGO Marco于1992年提出，并將其應(yīng)用于解決TSP，取得較好效果。之后，各國(guó)學(xué)者不斷優(yōu)化該算法[11-15]，出現(xiàn)了最大最小蟻群（max min ant colony system, MMAS）算法[16]，蟻群系統(tǒng)（ant colony system, ACS）算法[17]等，這些算法優(yōu)化了信息素更新規(guī)則，一定程度地解決了蟻群算法中信息素積累速度過(guò)快，搜索空間不足的問(wèn)題，但仍然容易陷入局部最優(yōu)。

為此，本文提出融合動(dòng)態(tài)鄰域搜索機(jī)制的蟻群系統(tǒng)（dynamic neighborhood search ant colony system, DNS-ACS）算法。首先，利用2-opt算子改進(jìn)當(dāng)前階段的解；然后，搜索當(dāng)前最優(yōu)解各個(gè)節(jié)點(diǎn)周圍鄰域并記錄鄰域內(nèi)的路徑，在信息素更新階段將信息素按照一定規(guī)則分配到記錄的路徑中；最后，動(dòng)態(tài)調(diào)整信息素釋放量以及鄰域搜索范圍，使算法在前期實(shí)現(xiàn)快速收斂，在后期有效跳出局部最優(yōu)解。

1 蟻群算法

蟻群算法的靈感來(lái)源于螞蟻覓食方式。螞蟻在尋找食物時(shí)，在路徑上遺留一種叫做信息素的化學(xué)物質(zhì)。由于目標(biāo)距離及揮發(fā)因素的影響，蟻群和最近食物之間的路徑存在更多的信息素，從而吸引更多的螞蟻跟隨相同的路徑。一旦食物耗盡，螞蟻就會(huì)放棄這條路徑，伴隨著信息素的揮發(fā)，迫使螞蟻重新開始隨機(jī)尋找另一種食物。

蟻群算法隨機(jī)初始化所有螞蟻，每個(gè)螞蟻搜索一個(gè)潛在的解決方案。在迭代過(guò)程中，蟻群算法為求解路徑的每條邊分配信息素，螞蟻根據(jù)信息素的濃度，移動(dòng)到尚未訪問(wèn)的節(jié)點(diǎn)，構(gòu)建一個(gè)可行的解決方案。在蟻群算法中，螞蟻根據(jù)公式(1)訪問(wèn)下一個(gè)節(jié)點(diǎn)。

式中：

在蟻群系統(tǒng)算法中，螞蟻訪問(wèn)節(jié)點(diǎn)的方式有所改變，訪問(wèn)規(guī)則如公式(2)所示。

式中：

的訪問(wèn)方式按公式(1)進(jìn)行。

蟻群系統(tǒng)算法中，螞蟻訪問(wèn)下一個(gè)節(jié)點(diǎn)時(shí)，利用公式(3)局部更新路徑信息素，這個(gè)過(guò)程稱為局部信息素更新。

式中：

在所有螞蟻訪問(wèn)結(jié)束后，利用公式(4)更新路徑信息素，這個(gè)過(guò)程稱為全局信息素更新。

式中：

式中：

由于算法在搜索階段開始時(shí)，各條路徑的信息素分布均勻，因此在蟻群算法和蟻群系統(tǒng)算法中，前期具有一定的盲目性，導(dǎo)致收斂速度較慢；而后期，算法在路徑上積累了大量的信息素，降低了搜索其他路徑的機(jī)會(huì)。本文在蟻群系統(tǒng)算法的基礎(chǔ)上，提出的DNS-ACS算法在一定程度上解決了這些問(wèn)題。

2 DNS-ACS算法

本文提出的DNS-ACS算法主要進(jìn)行如下改進(jìn)：

1）引入2-opt算子，避免路徑交叉帶來(lái)的距離損耗，實(shí)現(xiàn)算法快速收斂；

2）融合鄰域搜索機(jī)制，通過(guò)搜索鄰域節(jié)點(diǎn)，擴(kuò)大搜索范圍，避免算法陷入局部最優(yōu)；

3）動(dòng)態(tài)調(diào)整鄰域搜索及信息素更新規(guī)則，為尋找最優(yōu)路徑提供合理導(dǎo)向。

2.1 2-opt算子

2-opt算法是局部搜索算法，通過(guò)對(duì)局部解進(jìn)行優(yōu)化，幫助蟻群算法避免局部極小值。本文引入2-opt算子求解TSP[18]，通過(guò)將當(dāng)前解所表示的路徑中已有的兩條邊置換，產(chǎn)生一條新路徑，若新路徑更短，則保留；重復(fù)這個(gè)過(guò)程，直到?jīng)]有發(fā)現(xiàn)更短的路徑為止。2-opt算子的優(yōu)化過(guò)程如圖1所示。

圖1 2-opt算子優(yōu)化過(guò)程示意圖

由圖1可以看出，2-opt算子能夠?qū)⑻摼€部分的路徑優(yōu)化，使優(yōu)化后的路徑更短，有效提升問(wèn)題解的質(zhì)量。

2.2 鄰域搜索機(jī)制

螞蟻在尋找下一個(gè)目標(biāo)節(jié)點(diǎn)時(shí)，符合最優(yōu)解的目標(biāo)往往在螞蟻周圍的相鄰節(jié)點(diǎn)產(chǎn)生。因此，在DNS-ACS算法中，螞蟻經(jīng)過(guò)每個(gè)節(jié)點(diǎn)時(shí)，標(biāo)記周圍距離最近的相鄰節(jié)點(diǎn)，并記錄當(dāng)前節(jié)點(diǎn)與標(biāo)記點(diǎn)之間的路徑，標(biāo)記個(gè)數(shù)為。螞蟻在經(jīng)過(guò)某個(gè)節(jié)點(diǎn)時(shí)，建立鄰域，尋找標(biāo)記點(diǎn)及與當(dāng)前節(jié)點(diǎn)路徑的過(guò)程如圖2所示。

圖2 鄰域搜索機(jī)制示意圖

由圖2可以看出，螞蟻經(jīng)過(guò)每個(gè)節(jié)點(diǎn)時(shí)，會(huì)建立以該節(jié)點(diǎn)為中心，半徑為的鄰域范圍。的計(jì)算公式為

式中：

——當(dāng)前節(jié)點(diǎn)；

2.3 信息素動(dòng)態(tài)更新

在蟻群算法中，每只螞蟻經(jīng)過(guò)路徑時(shí)都釋放信息素，導(dǎo)致信息素積累速度過(guò)快。隨著迭代次數(shù)不斷增加，螞蟻容易集中在同一條路徑，導(dǎo)致收斂過(guò)快，結(jié)果誤差偏大。蟻群系統(tǒng)算法通過(guò)局部信息素更新和全局信息素更新，避免了路徑間信息素差異過(guò)大。但由于信息素更新方式是靜態(tài)的，仍難以跳出局部最優(yōu)解。

本文通過(guò)動(dòng)態(tài)調(diào)整鄰域的信息素，使其在加快算法收斂速度的同時(shí)擴(kuò)大搜索范圍，避免早熟現(xiàn)象。該過(guò)程分為2個(gè)步驟。

1）對(duì)現(xiàn)有的最優(yōu)路徑(,)按公式(7)進(jìn)行信息素補(bǔ)償，以加快算法收斂速度。

式中：

即若節(jié)點(diǎn)處于其當(dāng)前鄰域范圍內(nèi)，則信息素的補(bǔ)充值為一個(gè)與領(lǐng)域范圍半徑相關(guān)的固定值；若節(jié)點(diǎn)處于當(dāng)前鄰域范圍外，則信息素的補(bǔ)充值隨兩點(diǎn)距離的增大而減小。

2）為平衡可能存在的更優(yōu)解路徑與現(xiàn)有最優(yōu)路徑之間的信息素差距，向當(dāng)前最優(yōu)路徑節(jié)點(diǎn)鄰域內(nèi)的其他節(jié)點(diǎn)釋放信息素，增加螞蟻前往這些節(jié)點(diǎn)的概率，擴(kuò)大搜索范圍。

首先，利用公式(9)對(duì)某一節(jié)點(diǎn)記錄的各條路徑間的距離進(jìn)行標(biāo)準(zhǔn)化處理；

然后，利用公式(10)對(duì)記錄的路徑進(jìn)行信息素更新。

式中：

2.4 動(dòng)態(tài)鄰域搜索機(jī)制

在鄰域搜索時(shí)，若每次迭代的結(jié)果較上一次有所提升，則表明算法在當(dāng)前環(huán)境下能夠找到更優(yōu)解的可能性較大，應(yīng)適當(dāng)縮小搜索范圍，集中搜索可能出現(xiàn)的更優(yōu)解；若長(zhǎng)時(shí)間最優(yōu)解沒有更新，則表明算法陷入停滯，應(yīng)擴(kuò)大搜索范圍，增加解的多樣性，在更遠(yuǎn)的鄰域內(nèi)使現(xiàn)有解得到更新。本文對(duì)標(biāo)記數(shù)按公式(11)進(jìn)行調(diào)整。

式中：

為避免鄰域范圍過(guò)大或過(guò)小，干擾螞蟻尋優(yōu)過(guò)程，設(shè)定一個(gè)閾值，如公式(12)所示。

式中：

2.5 算法流程

DNS-ACS算法流程圖如圖3所示。

圖3 算法流程圖

3 實(shí)驗(yàn)仿真

3.1 參數(shù)設(shè)置

本實(shí)驗(yàn)采用TSPLIB數(shù)據(jù)庫(kù)中的TSP數(shù)據(jù)集，測(cè)試算法性能。首先，在數(shù)據(jù)集中選取16個(gè)算例，比較ACS、ACS+2-opt、本文DNS-ACS算法；其次，利用8個(gè)數(shù)據(jù)集比較本文DNS-ACS算法與5種文獻(xiàn)[5,19-22]算法性能。參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置

通過(guò)Matlab 2018b實(shí)現(xiàn)DNS-ACS算法，并分別運(yùn)行TSP數(shù)據(jù)集的16個(gè)算例，比較其平均解，誤差率（）以及每次運(yùn)行的最優(yōu)解。

3.2 與傳統(tǒng)算法比較

為驗(yàn)證DNS-ACS算法能有效優(yōu)化TSP，本文利用ACS、ACS+2-opt、DNS-ACS三種算法分別對(duì)TSP算例庫(kù)中的16個(gè)算例進(jìn)行實(shí)驗(yàn)。為保證參數(shù)的一致性，三種算法的參數(shù)都按表1設(shè)置。每種算法在每個(gè)算例中運(yùn)行10次，取最優(yōu)解平均值，并利用公式(13)計(jì)算誤差率，結(jié)果如表2所示。

式中：

——誤差率；

由表2可知：ACS算法僅找到oliver30算例的最優(yōu)解，其他算例都有不同程度的誤差，其中l(wèi)in318算例的誤差率達(dá)到7.93%；ACS+2-opt算法找到9個(gè)算例的最優(yōu)解，其中誤差率高于0.5%的算例有3個(gè)；DNS-ACS算法找到12個(gè)算例的最優(yōu)解，其他算例的誤差率在0.5%以內(nèi)，尋優(yōu)能力明顯優(yōu)于另外2種算法。此外，DNS-ACS算法在每個(gè)算例中的最優(yōu)值，都是3種算法中最小的，證明了該算法的優(yōu)化是有效的。

表2 DNS-ACS算法與ACS算法、ACS+2-opt算法對(duì)比結(jié)果

注：最優(yōu)解和平均解的結(jié)果四舍五入取整，標(biāo)黑表示達(dá)到已知最優(yōu)解。

本文選擇6個(gè)規(guī)模較大的算例，通過(guò)圖像的形式對(duì)ACS、ACS+2-opt、DNS-ACS三種算法的收斂曲線進(jìn)行對(duì)比，如圖4所示。

圖4 ACS、ACS+2-opt、DNS-ACS三種算法的收斂曲線對(duì)比圖

由圖4可知，DNS-ACS算法的收斂速度較快，求解精度最好，表明該算法對(duì)求解TSP問(wèn)題有明顯效果。

為對(duì)仿真結(jié)果進(jìn)行進(jìn)一步驗(yàn)證，采用DNS-ACS算法求解的最優(yōu)路徑如圖5所示。

圖 5 仿真實(shí)驗(yàn)結(jié)果

由圖5可以看出：采用DNS-ACS算法求解的最優(yōu)路徑是一個(gè)閉環(huán)，其間沒有形成交叉點(diǎn)。

3.3 與其他文獻(xiàn)算法比較

為進(jìn)一步證明DNS-ACS算法的有效性，本文選取文獻(xiàn)[5,19-22]的算法在這8個(gè)算例中進(jìn)行比對(duì)實(shí)驗(yàn)，結(jié)果如表3所示。

表3 DNS-ACS算法與其他文獻(xiàn)算法比對(duì)結(jié)果

注：最優(yōu)解和平均解的結(jié)果四舍五入取整，“—”表示在文獻(xiàn)中沒有相應(yīng)數(shù)據(jù)，標(biāo)黑表示算法中的最優(yōu)解。

由表3可以看出：在這8個(gè)算例中，DNS-ACS算法解的精度較其他算法有明顯提高，從而驗(yàn)證該算法具有較好的優(yōu)化性能。

4 結(jié)語(yǔ)

針對(duì)蟻群算法的不足，本文融入動(dòng)態(tài)鄰域搜索機(jī)制，結(jié)合2-opt算子，并通過(guò)改進(jìn)信息素更新機(jī)制，在加快算法收斂速度的同時(shí)，擴(kuò)大搜索范圍，從而使算法更好地跳出局部最優(yōu)解，實(shí)現(xiàn)算法優(yōu)化。通過(guò)對(duì)TSPLIB數(shù)據(jù)庫(kù)中的16個(gè)算例的比對(duì)，證明該算法的有效性。但是對(duì)于較大規(guī)模的算例，所求得解的精度仍有上升的空間。日后的研究中，將針對(duì)這一問(wèn)題繼續(xù)完善對(duì)算法的優(yōu)化。

[1] DANTZIG G B, FULKERSON D R, JOHNSON S M. On a linear-programming, combinatorial approach to the traveling-salesman problem[J]. Operations Research, 1959,7(1):58-66.

[2] GOUVEIA L, LEITNER M, RUTHMAIR M. Extended formulations and branch-and-cut algorithms for the black-and-white traveling salesman problem[J]. European Journal of Operational Research, 2017:908-928.

[3] WEI Gao. New ant colony optimization algorithm for the traveling salesman problem[J]. International Journal of Compu-tational Intelligence Systems,2020,13(1): 44-55.

[4] ARDALAN Z, KARIMI S, POURSABZI O, et al. A novel imperialist competitive algorithm for generalized traveling sales- man problems[J]. Applied Soft Computing, 2015,26:546- 555.

[5] 陳科勝,鮮思東,郭鵬.求解旅行商問(wèn)題的自適應(yīng)升溫模擬退火算法[J].控制理論與應(yīng)用,2021,38(2):245-254.

[6] 楊進(jìn),鄭允,馬良.改進(jìn)的貓群算法求解TSP[J].計(jì)算機(jī)應(yīng)用研究,2017,34(12):3607-3610.

[7] EZUGWU E S, ADEWUMI A O, FRNCU M E. Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem[J]. Expert Systems with Applications, 2017,77:189-210.

[8] 楊云亭,王鵬.求解旅行商問(wèn)題的多尺度量子自由粒子優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用,2020,40(5):1278-1283.

[9] CHOONG S S, WONG L P, LIM C P. An artificial bee colony algorithm with a Modified Choice Function for the traveling salesman problem [C]// IEEE International Conference on Sys-tem, Man, and Cybernetics (SMC) 2017. IEEE, 2017.

[10] DORIGO M, MANIEZZO V, COLORNI A. Ant system: optimization by a colony of cooperating agents[J]. IEEE tran-sactions on systems, man and cybernetics. Part B, 1996,26(1): 29-41.

[11] ZHANG Zhaojun, XU Zhaoxiong, LUAN Shengyang, et al. Opposition-based ant colony optimization algorithm for the traveling salesman problem[J]. Mathematics, 2020,8(10):1650.

[12] EBADINEZHAD S. DEACO: adopting dynamic evaporation strategy to enhance ACO algorithm for the traveling salesman problem[J]. Engineering Applications of Artificial Intelligence, 2020,92:103649.

[13] FADL D, KHALIL EL H, HASSAN M, et al. Dynamic flying ant colony optimization (DFACO) for solving the traveling salesman problem[J]. Sensors (Basel, Switzerland),2019,19(8): 1837.

[14] JIANG C, WAN Z, PENG Z. A new efficient hybrid algorithm for large scale multiple traveling salesman problems[J]. Expert Systems with Applications, 2019,139:112867.

[15] 張立毅,肖超,費(fèi)騰.基于細(xì)菌覓食的改進(jìn)蟻群算法[J].計(jì)算機(jī)工程與科學(xué),2018,40(10):1882-1889.

[16] STUTZLE T, HOOS H H. MAX-MIN ant system[J]. Future Generation Computer Systems, 2000, 16(8): 889-914.

[17] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997,1(1):53-66.

[18] 李俊,童釗,王政.一種并行ACS-2-opt算法處理TSP問(wèn)題的方法[J].計(jì)算機(jī)科學(xué),2018,45(S2):138-142.

[19] 陳思遠(yuǎn),林丕源,黃沛杰.指針網(wǎng)絡(luò)改進(jìn)遺傳算法求解旅行商問(wèn)題[J].計(jì)算機(jī)工程與應(yīng)用,2020,56(19):231-236.

[20] 喬?hào)|平,裴杰,李浩,等.改進(jìn)蟻群算法求解TSP問(wèn)題研究[J].機(jī)械設(shè)計(jì)與制造,2019(10):144-149.

[21] 陳穎杰,高茂庭.基于信息素初始分配和動(dòng)態(tài)更新的蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用,2022,58(2):95-101.

[22] 孟靜雯,游曉明,劉升.結(jié)合協(xié)同機(jī)制與動(dòng)態(tài)調(diào)控策略的雙蟻群算法[J].計(jì)算機(jī)科學(xué)與探索,2021,15(11):2206-2221.

Ant Colony System Algorithm Combining Dynamic Neighborhood Search Mechanism

GUO Wenqiang DU Zhengyi

(School of Information Management Xinjiang University of Finance and Economics, Urumqi 830012, China)

Aiming at the problems of slow convergence speed and easy to fall into local optimal solution of ant colony algorithm, an ant colony system (DNS-ACS) algorithm combining dynamic neighborhood search mechanism is proposed. Firstly, based on the ant colony system algorithm, the 2-opt operator is introduced for local search to speed up the convergence speed of the algorithm; Then, dynamically adjust the neighborhood search range and pheromone update rules to make it jump out of the local optimum and avoid premature phenomenon; Finally, the DNS-ACS algorithm proposed in this paper is used to simulate 16 classical TSP examples, and compared with other algorithms. Experimental results show that the accuracy of DNS-ACS algorithm is significantly improved, which proves the effectiveness of the algorithm.

ant colony algorithm; traveling salesman problem; dynamic neighbors search; pheromone update

TP301.6

A

1674-2605(2022)02-0003-08

10.3969/j.issn.1674-2605.2022.02.003

郭文強(qiáng)，男，1975年生，博士，教授，博士生導(dǎo)師，主要研究方向：人工智能、信息安全。E-mail: gwq@xjufe.edu.cn

杜正毅，男，1996年生，碩士研究生，主要研究方向：智能算法。E-mail:1247397930@qq.com

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目（61941205）；天山雪松項(xiàng)目（2020XS07）。

郭文強(qiáng),杜正毅.融合動(dòng)態(tài)鄰域搜索機(jī)制的蟻群系統(tǒng)算法[J].自動(dòng)化與信息工程,2022,43(2):15-22.

GUO Wenqiang, DU Zhengyi. Ant colony system algorithm combining dynamic neighborhood search mechanism[J]. Automation & Information Engineering, 2022,43(2):15-22.