一種應(yīng)用于旅行商問(wèn)題的萊維飛行轉(zhuǎn)移規(guī)則蟻群優(yōu)化算法

丁增良 陳玨 邱禧荷

摘 要：針對(duì)旅行商問(wèn)題（TSP）提出了一種基于萊維飛行轉(zhuǎn)移規(guī)則的蟻群優(yōu)化算法。該算法結(jié)合了基于萊維飛行和蟻群系統(tǒng)算法（ant colony system，ACS）的轉(zhuǎn)移規(guī)則，形成了一種動(dòng)態(tài)權(quán)重的混合轉(zhuǎn)移規(guī)則，該策略能夠有效地幫助算法跳出局部最優(yōu)，增強(qiáng)全局搜索能力。此外，隨機(jī)多路徑優(yōu)化3-opt策略通過(guò)隨機(jī)抽取部分路徑與當(dāng)前最優(yōu)路徑組合，增加算法的多樣性。當(dāng)算法陷入停滯時(shí)，采用信息素平均隨機(jī)重置策略重置路徑上的信息素濃度，有助于算法跳出局部最優(yōu)。實(shí)驗(yàn)結(jié)果顯示，所提算法在處理多個(gè)不同規(guī)模的TSP實(shí)例時(shí)，與最優(yōu)解的誤差保持在3%以內(nèi)，證明了該算法在TSP中具備出色的收斂性和避免陷入局部最優(yōu)解的能力。

關(guān)鍵詞：蟻群算法；旅行商問(wèn)題；萊維飛行；3-opt

中圖分類號(hào)：TP18?? 文獻(xiàn)標(biāo)志碼：A??? 文章編號(hào)：1001-3695（2024）05-020-1420-08

doi： 10.19734/j.issn.1001-3695.2023.09.0450

Ant colony optimization algorithm based on Lévy flight transfer rule for solving traveling salesman problem

Abstract：This paper proposed an ant colony optimization algorithm based on Lévy flight transition rule for the TSP. The algorithm combined the transition rule based on Lévy flight and ACS， and formed a dynamic weight hybrid transition rule， which could effectively help the algorithm escape from local optima and enhance the global search ability. In addition， the random multi-path optimization 3-opt strategy increased the diversity of the algorithm by randomly extracting some paths and combining them with the current optimal path. When the algorithm stagnated， it used the pheromone average random reset strategy to reset the pheromone concentration on the path， which helped the algorithm escape from local optimal. The experimental results show that the proposed algorithm keeps the error within 3% compared with the optimal solution when dealing with multiple TSP instances of different scales， proving that it has excellent convergence and ability to avoid falling into local optima in the TSP problem.

Key words：ant colony optimization; traveling salesman problem（TSP）; Lévy flight; 3-opt

0 引言

旅行商問(wèn)題是組合優(yōu)化領(lǐng)域中的一個(gè)典型問(wèn)題，在現(xiàn)實(shí)生活中有許多應(yīng)用［1］。比如，在物流配送領(lǐng)域可用于優(yōu)化物流配送路線，減少送貨時(shí)間和成本；在網(wǎng)絡(luò)通信中優(yōu)化數(shù)據(jù)傳輸路線，減少傳輸時(shí)延和網(wǎng)絡(luò)擁塞等。

旅行商問(wèn)題目前主要由啟發(fā)式算法進(jìn)行求解，研究人員提出了眾多啟發(fā)式算法試圖解決TSP。文獻(xiàn)［2］介紹了六種常用的啟發(fā)式算法，包括最鄰近算法、遺傳算法（genetic algorithm，GA）、模擬退火算法、禁忌搜索算法、粒子群算法（particle swarm optimization，PSO）和樹木生理學(xué)優(yōu)化算法，并比較了各算法的性能、準(zhǔn)確性和收斂性。

許多研究人員在這些經(jīng)典啟發(fā)式算法的基礎(chǔ)上進(jìn)行改進(jìn)，以解決旅行商問(wèn)題。比如，陳加俊等人［3］提出一種基于探索-開發(fā)-跳躍策略的單親遺傳算法；禹博文等人［4］提出了一種引入動(dòng)態(tài)分化和鄰域誘導(dǎo)機(jī)制的雙蟻群優(yōu)化算法；Zhang等人［5］在2022年提出了一種具有跳躍基因和啟發(fā)式算子的遺傳算法；Roy等人［6］提出了一種基于多親交叉技術(shù)的新型模因遺傳算法；lhan等人［7］提出了一種基于列表的交叉算子模擬退火算法。

另一方面，研究人員對(duì)許多新型的啟發(fā)式算法進(jìn)行改進(jìn)以應(yīng)用到旅行商問(wèn)題。Gharehchopogh等人［8］在哈里斯鷹優(yōu)化算法（Harris hawk optimization algorithm）的基礎(chǔ)上提出了一種使用隨機(jī)密鑰編碼生成路線的方法來(lái)解決TSP，該方法能夠針對(duì)各種TSP實(shí)例找到最優(yōu)或近似最優(yōu)解。

Zhang等人［9］提出了一種適用于TSP的離散鯨魚優(yōu)化算法，首先將鯨魚優(yōu)化算法進(jìn)行離散改進(jìn)以適應(yīng)TSP，同時(shí)為了增強(qiáng)算法的能力，增加了自適應(yīng)權(quán)值、高斯擾動(dòng)和變鄰域搜索策略，提高了算法的種群多樣性和全局搜索能力，實(shí)驗(yàn)表明該算法能夠有效解決TSP問(wèn)題。

人工蜂群算法是一種模仿蜜蜂采蜜行為的群體智能優(yōu)化算法，其基本思想是將蜂群分為采蜜蜂、觀察蜂和偵察蜂三類，分別承擔(dān)不同職責(zé)，分工合作對(duì)問(wèn)題進(jìn)行計(jì)算求解。Khan等人［10］改進(jìn)了該算法使其適應(yīng)離散問(wèn)題，通過(guò)修改多個(gè)更新規(guī)則和K-opt操作來(lái)解決對(duì)稱和非對(duì)稱的旅行商問(wèn)題（TSP），與文獻(xiàn)中的其他對(duì)比方法相比，該算法的準(zhǔn)確性、效率和一致性方面表現(xiàn)良好。

麻雀搜索算法是一種受麻雀覓食和反捕食行為啟發(fā)的群體智能優(yōu)化算法［11］。離散麻雀搜索算法（discrete sparrow search algorithm，DSSA）是Zhang等人［12］在其基礎(chǔ)上改進(jìn)的離散版本。DSSA使用輪盤選擇生成初始解，使用基于順序的解碼方式來(lái)更新麻雀的位置，使用結(jié)合高斯突變和交換算子的全局?jǐn)_動(dòng)機(jī)制來(lái)平衡勘探和開發(fā)，以及使用2-opt局部搜索來(lái)提高解的質(zhì)量。通過(guò)實(shí)驗(yàn)驗(yàn)證，該方法在解決TSP時(shí)有較好的競(jìng)爭(zhēng)力和魯棒性。

在眾多經(jīng)典的和新型的啟發(fā)式算法中，蟻群算法（ant co-lony optimization，ACO）具有較好的優(yōu)化效果。ACO是一種具有群體智能和隨機(jī)性的元啟發(fā)式算法，已被用于處理許多綜合優(yōu)化問(wèn)題［13］。該算法最早是由Colorni等人［14］參考螞蟻在其群體和食物來(lái)源之間尋找路徑的行為而提出的，后來(lái)的研究以此為基礎(chǔ)，出現(xiàn)了各種各樣的變體。Lee［15］提出了一種將蟻群優(yōu)化算法和遺傳算法相結(jié)合的算法，并應(yīng)用于解決旅行商問(wèn)題。Cheng等人［16］提出了一個(gè)基于分解的多目標(biāo)蟻群優(yōu)化的框架，以解決雙目標(biāo)旅行商問(wèn)題。Ban［17］提出了一種結(jié)合蟻群算法、遺傳算法和鄰域下降與隨機(jī)鄰域排序的混合算法，以解決旅行商問(wèn)題。Dahan等人［18］采用飛行蟻群算法（dynamic flying ant colony optimization，DFACO）來(lái)解決旅行商問(wèn)題的方法。Yang等人［19］提出了一種基于博弈的新型蟻群優(yōu)化算法用于解決旅行商問(wèn)題，其在多個(gè)實(shí)例上表現(xiàn)出優(yōu)越的效果。Dorigo等人［20］指出，近年來(lái)研究ACO算法的主要方向之一是將其與其他元啟發(fā)式方法相融合。

本文從另一個(gè)角度出發(fā)，對(duì)蟻群算法轉(zhuǎn)移規(guī)則進(jìn)行了研究和改進(jìn)。本文算法是基于最大最小蟻群算法（max-min ant system，MMAS）的改進(jìn)。MMAS作為ACO的變體，與原始ACO的不同之處在于：MMAS只允許使用最佳解決方案來(lái)更新信息素軌跡，并使用一種機(jī)制來(lái)限制信息素值的范圍。這種設(shè)計(jì)使得MMAS能夠更有效地利用搜索歷史，從而避免陷入次優(yōu)解。盡管通過(guò)這些策略可以避免過(guò)早收斂，但同時(shí)也可能導(dǎo)致搜索過(guò)程中多樣性和探索性的喪失，從而使算法陷入局部最優(yōu)解。因此，為了解決MMAS的這些局限性，本文基于MMAS提出了一種新的蟻群算法，該算法引入了萊維飛行的混合轉(zhuǎn)移規(guī)則，以更好地平衡開發(fā)和探索，提高算法的性能。

本文采用了多種改進(jìn)策略以增強(qiáng)蟻群算法的性能。首先，提出了一種混合轉(zhuǎn)移規(guī)則的改進(jìn)策略，包括基于貪心、基于萊維飛行和基于概率的轉(zhuǎn)移規(guī)則，并為每種規(guī)則分配了不同的權(quán)重因子，用于控制每種轉(zhuǎn)移規(guī)則被選擇的概率。為了應(yīng)對(duì)基于貪心規(guī)則容易導(dǎo)致螞蟻陷入局部最優(yōu)解的問(wèn)題，本文采用動(dòng)態(tài)權(quán)重線性遞減的方式來(lái)調(diào)整基于貪心規(guī)則的權(quán)重，這種動(dòng)態(tài)權(quán)重的混合轉(zhuǎn)移規(guī)則不僅繼承了MMAS算法的優(yōu)點(diǎn)，還有效地彌補(bǔ)了MMAS算法的不足之處。其次，本文通過(guò)優(yōu)化3-opt技術(shù)，提出了一種具有隨機(jī)路徑優(yōu)化的3-opt策略來(lái)減少回路的總長(zhǎng)度。最后，為了避免算法陷入局部最優(yōu)解，本文提出了信息素平均隨機(jī)重置策略，這一策略有助于保持算法的多樣性，從而更有可能發(fā)現(xiàn)全局最優(yōu)解。

實(shí)驗(yàn)結(jié)果表明，本文提出的改進(jìn)算法在求解TSP實(shí)例時(shí)能取得較好的實(shí)驗(yàn)結(jié)果，對(duì)于不同規(guī)模的TSP實(shí)例其求解精度能保持在一個(gè)較優(yōu)的范圍，與最優(yōu)解的誤差始終保持在3%以內(nèi)。同時(shí)相比于傳統(tǒng)的蟻群算法和其他最新的蟻群算法，本文算法也能取得更好的實(shí)驗(yàn)結(jié)果，證明了這些改進(jìn)策略的共同作用提高了蟻群算法在解決問(wèn)題時(shí)的性能和穩(wěn)定性。

1 相關(guān)工作

1.1 最大最小蟻群算法

MMAS作為ACO的一種，是由Stützle等人［13］在傳統(tǒng)ACO基礎(chǔ)上提出的改進(jìn)算法。本文算法以最大最小原則的蟻群優(yōu)化算法為基礎(chǔ)，算法模擬生成m只螞蟻，并隨機(jī)地將它們分配到n個(gè)城市中。在t時(shí)刻，螞蟻k從城市i轉(zhuǎn)移到城市j的概率Pkij（t）為

其中：τij表示城市i到j(luò)路徑上的信息素濃度；ηij表示從城市i到j(luò)的期望啟發(fā)因子；allowedk表示螞蟻k下一步可以去的城市集合；參數(shù)α和β則用于調(diào)整在計(jì)算概率時(shí)信息素和啟發(fā)信息的相對(duì)權(quán)重。

螞蟻在經(jīng)過(guò)的路徑上釋放一定的信息素，用來(lái)與其他螞蟻交流信息。當(dāng)所有的螞蟻都完成了一次完整的路徑后，根據(jù)每只螞蟻所走過(guò)的路徑長(zhǎng)度來(lái)更新信息素。更新信息素的公式為

其中：ρ表示信息素?fù)]發(fā)率；Δτij表示信息素增量，信息素增量有多種計(jì)算方法，一般選擇將式（3）作為增量的計(jì)算方式；Lk表示螞蟻在本次周游中所走過(guò)的路徑長(zhǎng)度；Q為一個(gè)正常數(shù)，一般設(shè)為1。隨后，檢查更新后的信息素的值是否在［τmin，τmax］，如果信息素的值大于上界，就將其值改為上界值，如果信息素的值小于下界，就將其值改為下界值。其中，τmin表示信息素濃度的下界，τmax表示信息素濃度的上界。

1.2 轉(zhuǎn)移規(guī)則

轉(zhuǎn)移規(guī)則在蟻群算法中具有關(guān)鍵作用，它決定了螞蟻選擇下一個(gè)節(jié)點(diǎn)的方式。在解決旅行商問(wèn)題中，選擇適當(dāng)?shù)南乱粋€(gè)節(jié)點(diǎn)對(duì)算法性能至關(guān)重要。根據(jù)不同蟻群算法的變體，轉(zhuǎn)移規(guī)則也會(huì)有所不同。其中一種常見的是基于概率的轉(zhuǎn)移規(guī)則，它根據(jù)邊上的信息素濃度和啟發(fā)式信息計(jì)算節(jié)點(diǎn)被選中的概率。然后，根據(jù)輪盤賭法來(lái)隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為將要訪問(wèn)的對(duì)象。這種轉(zhuǎn)移規(guī)則的具體計(jì)算公式如式（1）所示。輪盤賭法的基本思想就是依據(jù)城市的選擇概率將輪盤劃分為多個(gè)扇區(qū)，同時(shí)隨機(jī)生成的隨機(jī)數(shù)大小對(duì)應(yīng)著圖1中的某個(gè)位置，落入哪個(gè)扇區(qū)，就代表選中哪個(gè)城市。

不同的轉(zhuǎn)移規(guī)則各有利弊。基于概率的轉(zhuǎn)移規(guī)則能夠保持一定的隨機(jī)性和多樣性，有助于避免陷入局部最優(yōu)解，但可能導(dǎo)致收斂速度較慢。此外，由于輪盤賭法依賴于生成的隨機(jī)數(shù)大小，這種隨機(jī)性可能引入一定不確定性，影響算法的穩(wěn)定性和可靠性。為彌補(bǔ)算法的不足，Dorigo等人［21］提出了一種偽隨機(jī)比例轉(zhuǎn)移規(guī)則。

該規(guī)則是根據(jù)式（1）基于概率的轉(zhuǎn)移規(guī)則以及基于貪心的轉(zhuǎn)移規(guī)則融合而成，其中p為（0，1）的隨機(jī)數(shù)，用于平衡探索和開發(fā)。當(dāng)p≤q0時(shí)，使用基于貪心的轉(zhuǎn)移規(guī)則，根據(jù)式（4）中的第一個(gè)式子選取具有最大概率的節(jié)點(diǎn)，以提高算法的收斂速度。當(dāng)p>q0時(shí)，采用式（1）代表的另一種轉(zhuǎn)移規(guī)則，并通過(guò)輪盤賭法選擇下一個(gè)節(jié)點(diǎn)，以增強(qiáng)算法的探索性能。盡管偽隨機(jī)比例規(guī)則更好地平衡了探索和開發(fā)，但是改進(jìn)后的蟻群算法仍然存在可能陷入局部最優(yōu)的問(wèn)題。為此，本文提出了一種動(dòng)態(tài)權(quán)重的混合轉(zhuǎn)移規(guī)則，除了前文提到的兩種方法融合形成的偽隨機(jī)比例規(guī)則，還提出了一種基于萊維飛行的轉(zhuǎn)移規(guī)則。

1.3 萊維飛行

萊維飛行是由法國(guó)數(shù)學(xué)家Paul Lévy于20世紀(jì)初提出的一種隨機(jī)過(guò)程。在萊維飛行過(guò)程中，每一步的步長(zhǎng)服從萊維分布，該分布具有重尾分布的特性，即尾部概率較高。因此，萊維飛行通常以較小的步長(zhǎng)進(jìn)行移動(dòng)，但偶爾也會(huì)發(fā)生較大幅度的跳躍。萊維飛行的小步跟蹤特點(diǎn)能夠幫助算法增強(qiáng)局部搜索能力，使算法能夠在較優(yōu)的區(qū)域內(nèi)充分探索，提高解的質(zhì)量。此外，萊維飛行的長(zhǎng)距離跳躍特性擾動(dòng)了穩(wěn)定路徑，有助于算法跳出局部最優(yōu)解，進(jìn)一步增加了解的多樣性。自然界有些現(xiàn)象也呈現(xiàn)出萊維飛行的特征，例如，在某些動(dòng)物的遷徙中會(huì)展現(xiàn)出類似于萊維飛行的現(xiàn)象，表現(xiàn)為在長(zhǎng)距離的遷徙過(guò)程中，會(huì)突然地、不規(guī)則地改變方向和位置。

圖2展示了萊維分布、高斯分布和柯西分布的隨機(jī)數(shù)分布情況。為了更直觀、簡(jiǎn)單地觀察隨機(jī)數(shù)的分布特性，本文采用了二維分布圖的方式進(jìn)行展示。圖中的X坐標(biāo)軸表示三種分布生成的數(shù)值，而Y坐標(biāo)軸則表示隨機(jī)生成的數(shù)值。從圖2可以看出，正態(tài)分布呈現(xiàn)出典型的對(duì)稱分布特征，其尾部相對(duì)較輕。而另外兩種分布則表現(xiàn)出非對(duì)稱的特點(diǎn)，屬于重尾分布。相對(duì)于柯西分布，萊維分布在尾部區(qū)域更為分散，且包含更多數(shù)值。這表明在旅行商問(wèn)題等應(yīng)用中，萊維分布更適合作為改進(jìn)算法的策略，有助于算法在更廣泛的區(qū)域內(nèi)進(jìn)行局部搜索，跳出局部最優(yōu)解，增強(qiáng)算法的探索能力。

式（5）是用Mantegna方法生成隨機(jī)數(shù)的公式，Mantegna方法通過(guò)正態(tài)分布生成隨機(jī)步長(zhǎng)，這些步長(zhǎng)遵循萊維分布，形成了萊維飛行的路徑。

其中：β是一個(gè)參數(shù)，控制了萊維分布的形狀，一般取值為1.5；μ和ν是服從正態(tài)分布的隨機(jī)變量，具體如下：

因此，通過(guò)借鑒具有萊維飛行現(xiàn)象動(dòng)物的運(yùn)動(dòng)方式，一些學(xué)者將其應(yīng)用到各類優(yōu)化算法中。例如，Zhong等人［22］設(shè)計(jì)了一種基于白鯨運(yùn)動(dòng)規(guī)律的元啟發(fā)式算法，稱為白鯨優(yōu)化算法（beluga whale optimization，BWO），用于求解各類優(yōu)化問(wèn)題。

鑒于萊維飛行的良好特性，它也被用于蟻群算法的改進(jìn)，Bansal等人［23］提出了一種改進(jìn)的萊維分布雜交蟻群算法，并在一些基準(zhǔn)函數(shù)上與標(biāo)準(zhǔn)蟻群算法進(jìn)行了比較。Liu等人［24，25］對(duì)轉(zhuǎn)移規(guī)則階段進(jìn)行了改進(jìn)，引入了萊維飛行機(jī)制，該方法通過(guò)動(dòng)態(tài)參數(shù)調(diào)整，增加了解的多樣性和搜索范圍。然而，現(xiàn)有的萊維飛行蟻群算法的研究著重于參數(shù)的動(dòng)態(tài)調(diào)整，缺乏對(duì)旅行商問(wèn)題中如何選擇下一個(gè)節(jié)點(diǎn)的方法的改進(jìn)。對(duì)此，本文提出了一種全新的基于萊維飛行TSP的轉(zhuǎn)移規(guī)則。

2 算法描述

本文從三種從不同的角度對(duì)算法提出了改進(jìn)策略。動(dòng)態(tài)權(quán)重的混合轉(zhuǎn)移規(guī)則用于更好地平衡探索和開發(fā)，加快算法收斂速度的同時(shí)增強(qiáng)算法跳出局部最優(yōu)的能力，提高算法的全局搜索能力；隨機(jī)多路徑優(yōu)化3-opt策略優(yōu)化局部的路徑，降低陷入局部最優(yōu)的可能性；信息素平均重置策略幫助算法在陷入停滯情況時(shí)跳出局部最優(yōu)；然后以MMAS算法為基礎(chǔ)框架，將這三種改進(jìn)策略融合其中，形成了一個(gè)先進(jìn)的蟻群算法。

2.1 動(dòng)態(tài)權(quán)重的混合轉(zhuǎn)移規(guī)則

本文在萊維飛行的基礎(chǔ)上對(duì)蟻群算法的轉(zhuǎn)移規(guī)則進(jìn)行改進(jìn)，提出了一種全新的轉(zhuǎn)移規(guī)則。通常，萊維飛行被廣泛應(yīng)用于處理連續(xù)問(wèn)題，如式（7）所示，對(duì)算法輸出數(shù)據(jù)的處理中采用了Lévy函數(shù)，以促使算法在連續(xù)問(wèn)題領(lǐng)域避免陷入局部最優(yōu)解。

然而，由于數(shù)據(jù)是離散化的，不能直接將該公式用于旅行商問(wèn)題的蟻群算法轉(zhuǎn)移規(guī)則階段，所以需要對(duì)其進(jìn)行改進(jìn)。

為了模擬旅行商在二維空間中的移動(dòng)過(guò)程，假設(shè)旅行商從當(dāng)前城市出發(fā)，按照隨機(jī)方向和一定的步長(zhǎng)前進(jìn)，以達(dá)到新的坐標(biāo)位置。該過(guò)程可以表示為

其中：角度θ由隨機(jī)數(shù)生成；step是通過(guò)Mantegna方法實(shí)現(xiàn)的萊維飛行的步長(zhǎng)。由圖3可知，經(jīng)過(guò)式（8）計(jì)算，得到了一個(gè)新坐標(biāo)點(diǎn)（Xnew，Ynew）。然而，新坐標(biāo)點(diǎn)未必與城市節(jié)點(diǎn)重疊，因此需要進(jìn)一步處理新節(jié)點(diǎn)坐標(biāo)，以確定算法下一個(gè)節(jié)點(diǎn)的位置。

next_node=nearest_node（Xnew，Ynew）（9）

next_node是通過(guò)輸入新節(jié)點(diǎn)坐標(biāo)獲取到下一個(gè)最優(yōu)城市節(jié)點(diǎn)的方法。該方法以新坐標(biāo)（Xnew，Ynew）為圓心，以式（10）的計(jì)算結(jié)果為半徑，在城市集合中尋找數(shù)值最小的城市。如圖3所示，當(dāng)使用傳統(tǒng)方法計(jì)算下一個(gè)城市時(shí)，可能會(huì)選擇移動(dòng)到city 2。但是當(dāng)使用基于萊維飛行的轉(zhuǎn)移規(guī)則時(shí)，可能會(huì)選擇city 1。

其中：X、Y表示未訪問(wèn)節(jié)點(diǎn)集合中每一個(gè)節(jié)點(diǎn)的坐標(biāo)值；pheromone表示當(dāng)前路徑上的信息素水平；visited（end）表示剛剛訪問(wèn)過(guò)的節(jié)點(diǎn)。算法1是next_node方法的偽代碼，該方法可以有效地指導(dǎo)螞蟻選擇下一個(gè)節(jié)點(diǎn)。

算法1 使用新坐標(biāo)獲取下一個(gè)移動(dòng)節(jié)點(diǎn)

為了平衡算法的探索性和開發(fā)性，本文將基于萊維飛行的轉(zhuǎn)移規(guī)則與基于貪心的轉(zhuǎn)移規(guī)則和基于概率的轉(zhuǎn)移規(guī)則進(jìn)行組合，創(chuàng)造一種新的混合轉(zhuǎn)移規(guī)則。

前文已經(jīng)介紹了萊維飛行的特性，它模擬了萊維飛行中的長(zhǎng)距離跳躍，并在全局搜索中起到跳出局部最優(yōu)解的作用，提高了算法的探索范圍和多樣性，增強(qiáng)了全局搜索能力?；谪澬牡霓D(zhuǎn)移規(guī)則則利用局部最優(yōu)信息，選擇具有最大概率的節(jié)點(diǎn)作為下一個(gè)移動(dòng)的節(jié)點(diǎn)，加快了算法的收斂速度，能夠快速收斂到局部最優(yōu)解，增強(qiáng)了局部搜索能力。傳統(tǒng)的基于概率的轉(zhuǎn)移規(guī)則則使用輪盤賭法，根據(jù)節(jié)點(diǎn)上的信息素濃度選擇下一個(gè)節(jié)點(diǎn)，它在動(dòng)態(tài)權(quán)重的混合轉(zhuǎn)移規(guī)則中起到平衡開發(fā)和探索的作用，通過(guò)信息素濃度的引導(dǎo)和一定程度的隨機(jī)性，有助于維持算法的多樣性和全局搜索能力。

在實(shí)際執(zhí)行過(guò)程中，算法需要根據(jù)當(dāng)前情況智能地選擇下一個(gè)節(jié)點(diǎn)的轉(zhuǎn)移規(guī)則。然而，不同的轉(zhuǎn)移規(guī)則在不同情況下可能具有不同的優(yōu)勢(shì)，因此需要?jiǎng)討B(tài)調(diào)整這些規(guī)則的選擇，以確保算法的高效性和全面性。為此，根據(jù)不同的權(quán)重系數(shù)確定了三種轉(zhuǎn)移規(guī)則的選擇概率，并在算法迭代過(guò)程中動(dòng)態(tài)調(diào)整了基于貪心的轉(zhuǎn)移規(guī)則的權(quán)重系數(shù)，以避免算法過(guò)早收斂到局部最優(yōu)解。如式（11）所示本文采用的動(dòng)態(tài)權(quán)重的混合轉(zhuǎn)移規(guī)則。

其中：r是一個(gè)隨機(jī)數(shù)；w1、w2、w3分別為基于貪心的轉(zhuǎn)移規(guī)則、基于萊維飛行的轉(zhuǎn)移規(guī)則和基于概率的轉(zhuǎn)移規(guī)則的權(quán)重因子。為了在算法早期快速達(dá)到一個(gè)較優(yōu)的解，并在后期減小基于貪心的轉(zhuǎn)移規(guī)則的權(quán)重，避免陷入局部最優(yōu)，本文對(duì)w1權(quán)重因子采用了隨算法迭代而線性遞減的方法。

在選擇遞減策略時(shí)，有線性遞減和非線性遞減兩種方法。線性遞減方法會(huì)隨著算法迭代次數(shù)的增加，按照線性比例逐漸減小權(quán)重，這種方法可以在算法中保持一種相對(duì)穩(wěn)定且簡(jiǎn)單的探索與開發(fā)之間的平衡。盡管線性遞減不能像非線性遞減方法那樣根據(jù)算法的不同迭代階段來(lái)調(diào)整權(quán)重減少的速度，比如加速或減緩收斂速度，但它能夠更穩(wěn)定地控制權(quán)重的變化，避免突然的權(quán)重變化對(duì)整體算法性能造成的不穩(wěn)定性影響。與此同時(shí)，非線性遞減方法也會(huì)增加算法在混合轉(zhuǎn)移規(guī)則方面主導(dǎo)的開發(fā)與探索的復(fù)雜性，可能需要增加參數(shù)進(jìn)行實(shí)驗(yàn)調(diào)整，并對(duì)算法的探索與開發(fā)的影響進(jìn)行詳細(xì)分析。綜上，本文選擇了線性遞減的方式。

2.2 局部?jī)?yōu)化策略

2.2.1 隨機(jī)多路徑優(yōu)化3-opt策略

3-opt是旅行商問(wèn)題中常見的優(yōu)化策略，它通過(guò)斷開路徑中不相鄰的三個(gè)節(jié)點(diǎn)之間的連接，并嘗試以不同的方式重新連接這些節(jié)點(diǎn)，以改善路徑的質(zhì)量。在3-opt策略中，涉及到三個(gè)節(jié)點(diǎn)的斷開和重連操作，共有八種不同的連接方式，如圖4所示，包括初始的路徑連接方式，如圖4所示。針對(duì)不同的連接方式，計(jì)算它們所對(duì)應(yīng)的路徑長(zhǎng)度，并選取路徑長(zhǎng)度最短的一條連接路徑作為新的路徑方案。

為了提高算法整體性能，本文提出了一種隨機(jī)路徑優(yōu)化的3-opt算法。該算法的步驟如下：

a）對(duì)當(dāng)前迭代中的所有路徑按長(zhǎng)度進(jìn)行排序，取最短路徑作為該策略的優(yōu)化路徑之一。

b）從剩余路徑中隨機(jī)抽取若干條路徑與上一步的最短路徑形成待優(yōu)化路徑集合。

c）對(duì)集合中的每條路徑執(zhí)行3-opt操作，即通過(guò)重新連接路徑段來(lái)生成更優(yōu)的新路徑。

d）將優(yōu)化后的路徑加入到當(dāng)前迭代的所有路徑集合中，并重新排序，選出當(dāng)前的最優(yōu)路徑。

該算法通過(guò)隨機(jī)抽取部分路徑與當(dāng)前最優(yōu)路徑組合，增加了搜索空間的多樣性，降低了算法陷入局部最優(yōu)解的可能性，增強(qiáng)了全局搜索的能力。

2.2.2 信息素平均隨機(jī)重置策略

盡管采用了各種策略避免算法陷入局部最優(yōu)策略，但仍然存在陷入局部最優(yōu)解的風(fēng)險(xiǎn)。為了平衡蟻群算法的探索和利用能力，并避免算法陷入局部最優(yōu)解，本文為算法增加了信息素重置策略。信息素重置策略是在算法運(yùn)行一定次數(shù)的迭代后執(zhí)行，旨在調(diào)節(jié)路徑上的信息素的濃度，引導(dǎo)螞蟻搜索更好的方向。

本文設(shè)計(jì)了一種新的信息素重置策略——信息素平均隨機(jī)重置策略。算法偽代碼如算法2所示。該策略的設(shè)計(jì)基于路徑上信息素的平均值計(jì)算，并將其與（0，1）的隨機(jī)數(shù)相乘，以實(shí)現(xiàn)信息素的重置，這種策略不是每次迭代都進(jìn)行，而是當(dāng)算法停滯一定的迭代次數(shù)才能觸發(fā)，這樣既保留了信息素重置策略的優(yōu)勢(shì)，又避免了過(guò)度重置信息素導(dǎo)致的負(fù)面影響。該策略的創(chuàng)新性在于平均重置的思想，并不是直接將信息素初始化為一個(gè)固定的值，而是通過(guò)路徑信息素重置為（0，1）的隨機(jī)數(shù)乘以先前計(jì)算的平均值。這在一定程度上保持了原本的環(huán)境信息，并引入了一定程度的隨機(jī)性，有助于避免在隨后的算法迭代中陷入局部最優(yōu)解，如式（12）所示。

T=rand（citys，citys）×τave（12）

算法2 信息素平均隨機(jī)重置策略

總的來(lái)說(shuō)，信息素平均隨機(jī)重置策略在蟻群算法中起到了關(guān)鍵作用，有助于算法在迭代停滯時(shí)跳出當(dāng)前的局部最優(yōu)狀態(tài)，保持在搜索空間的多樣性，防止早熟收斂，從而更有可能發(fā)現(xiàn)全局最優(yōu)解。此外，算法中設(shè)定的迭代次數(shù)觸發(fā)條件確保了重置不會(huì)頻繁發(fā)生，避免了該策略對(duì)正常的算法優(yōu)化產(chǎn)生過(guò)度影響。

2.3 LFACO算法流程

LFACO（Lévy flight-based ant colony optimization algorithm）在MMAS的基礎(chǔ)上進(jìn)行改進(jìn)，主要對(duì)轉(zhuǎn)移規(guī)則、3-opt策略和信息素重置策略等方面進(jìn)行改進(jìn)，算法流程如圖5所示。當(dāng)滿足終止條件時(shí)，程序?qū)⒔Y(jié)束，并輸出最短路徑。

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

本文的仿真環(huán)境為MATLAB 2021b，CPU為AMD Ryzen 7 5800H with Radeon Graphics，16 GB內(nèi)存，操作系統(tǒng)為Windows 11。為了驗(yàn)證LFACO的優(yōu)化性能，本文從TSPLIB中選擇了多個(gè)城市規(guī)模在51～439的TSP實(shí)例進(jìn)行測(cè)試。在TSPLIB的實(shí)例中，大部分使用歐幾里德距離來(lái)計(jì)算城市之間的距離，這種計(jì)算方式根據(jù)城市的橫坐標(biāo)和縱坐標(biāo)計(jì)算城市之間的直線距離，簡(jiǎn)單快速，降低了計(jì)算負(fù)擔(dān)。因此，本文也采用了歐幾里德距離來(lái)求解TSP。

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

算法參數(shù)的取值是影響元啟發(fā)式算法獲得良好性能的重要因素。其中，LFACO有以下幾個(gè)固定值，螞蟻數(shù)量m決定了算法的搜索規(guī)模，一般取10～50；全局信息素?fù)]發(fā)因子ρ決定了信息素的揮發(fā)速度，一般在0～1；局部信息素?fù)]發(fā)因子ξ；最大迭代次數(shù)iter是算法運(yùn)行結(jié)束的一個(gè)標(biāo)志；信息素啟發(fā)因子α代表信息素對(duì)選擇下一城市的影響程度；期望啟發(fā)因子β大小反映了蟻群在搜索最優(yōu)路徑時(shí)先驗(yàn)性和確定性因素的作用強(qiáng)度，其值越大，選擇局部最優(yōu)路徑的可能性就越大。

信息素啟發(fā)因子和期望啟發(fā)因子是一對(duì)高度相關(guān)的參數(shù)，它們決定了算法在全局最優(yōu)性能和快速收斂性能之間的平衡。因此，這兩個(gè)參數(shù)的影響和作用是相互協(xié)調(diào)、緊密相關(guān)的，為了獲得優(yōu)質(zhì)的最優(yōu)解，算法必須在這兩個(gè)參數(shù)之間找到平衡。為了達(dá)到這個(gè)目標(biāo)，本文進(jìn)行了對(duì)比實(shí)驗(yàn)，分別使用不同的信息素啟發(fā)因子和期望啟發(fā)因子值作為算法的輸入?yún)?shù)，選取eil51和pr226兩個(gè)TSP實(shí)例進(jìn)行求解。根據(jù)圖6顯示，當(dāng)α=1，β=5時(shí)，實(shí)驗(yàn)解的質(zhì)量較高，因此選擇這組參數(shù)值作為信息素啟發(fā)因子和期望啟發(fā)因子的最優(yōu)值。

為了確定合適的動(dòng)態(tài)權(quán)重混合轉(zhuǎn)移規(guī)則的相關(guān)參數(shù)，本文針對(duì)三種不同的轉(zhuǎn)移規(guī)則，通過(guò)一系列的實(shí)驗(yàn)測(cè)試，采用不同的權(quán)重因子，對(duì)性能進(jìn)行評(píng)估。為了保證實(shí)驗(yàn)的可靠性，確保實(shí)驗(yàn)結(jié)果的差異是不同權(quán)重因子對(duì)算法性能造成的影響，本文保持算法的其他參數(shù)恒定，僅對(duì)權(quán)重因子大小進(jìn)行調(diào)整。此外，為了提高研究的普適性，減少實(shí)驗(yàn)的誤差與偏差，本文選用了st70、rat99和pr152三種TSP測(cè)試實(shí)例。

為了綜合評(píng)價(jià)三種轉(zhuǎn)移規(guī)則對(duì)算法的收斂性能和最優(yōu)解質(zhì)量的影響，本文采用了最優(yōu)迭代次數(shù)Topt和最短路徑長(zhǎng)度Lbest作為評(píng)價(jià)指標(biāo)。將這兩個(gè)指標(biāo)按照一定的權(quán)重相加，得到一個(gè)表征綜合性能的分?jǐn)?shù)，該分?jǐn)?shù)越小，表示性能越好，具體如式（13）所示。圖7展示了不同轉(zhuǎn)移規(guī)則組合下的綜合性能分?jǐn)?shù)變化，其中縱坐標(biāo)是綜合性能分?jǐn)?shù)，橫坐標(biāo)的每組數(shù)字分別代表基于貪心的轉(zhuǎn)移規(guī)則（w1）、基于萊維飛行的轉(zhuǎn)移規(guī)則（w2）和基于概率的轉(zhuǎn)移規(guī)則（w3）的權(quán)重。由于蟻群算法本身具有隨機(jī)性，每次求解的結(jié)果會(huì)有一定的波動(dòng)，所以將三次求解的結(jié)果求平均值，得到最終確定的權(quán)重因子為w1=0.6，w2=0.2，w3=0.2。

score=0.8×Lbest+0.2×Topt（13）

綜上所述，LFACO算法的參數(shù)設(shè)置如表1所示。

3.2 動(dòng)態(tài)權(quán)重的混合轉(zhuǎn)移規(guī)則分析

為驗(yàn)證動(dòng)態(tài)權(quán)重的混合轉(zhuǎn)移規(guī)則的適用性，對(duì)LFACO與不包括動(dòng)態(tài)權(quán)重的混合轉(zhuǎn)移規(guī)則的改進(jìn)算法，以及去除其他兩種改進(jìn)策略只保留混合轉(zhuǎn)移規(guī)則的改進(jìn)算法進(jìn)行了實(shí)驗(yàn)對(duì)比分析。其中，去除改進(jìn)策略后的替代策略均采用與經(jīng)典MMAS算法相同的策略。實(shí)驗(yàn)以不同規(guī)模大小的數(shù)據(jù)集為例，分別為ch150、pr152、pr264和rat575。相比于其他兩種改進(jìn)算法，LFACO通過(guò)式（11）更好地平衡了開發(fā)和探索。

圖8為三種算法的收斂對(duì)比，從圖中可以看到，曲線是呈不斷下降的趨勢(shì)，說(shuō)明這三種算法都能有效地尋找TSP實(shí)例的最優(yōu)解。在算法迭代的初期，三種算法可以快速收斂到一個(gè)較小值附近，這歸因于三種算法所包含的基于貪心的轉(zhuǎn)移規(guī)則。與式（4）代表的偽隨機(jī)比例規(guī)則相比，混合轉(zhuǎn)移規(guī)則在引入基于萊維飛行的轉(zhuǎn)移規(guī)則后具備了更出色的全局搜索能力。在算法前期，例如圖8 （a）在迭代200次以內(nèi)時(shí)，LFACO的收斂曲線可能暫時(shí)處于劣勢(shì)，但是最終這四張圖中的LFACO都求得了三者之中最優(yōu)的收斂值。

在圖8 （c）中，迭代次數(shù)100～300，即使改進(jìn)算法具有信息素平均隨機(jī)重置策略，仍陷入局部最優(yōu)并未跳出。與此同時(shí)，LFACO和去除其他兩種改進(jìn)策略只保留混合轉(zhuǎn)移規(guī)則的改進(jìn)算法通過(guò)混合轉(zhuǎn)移規(guī)則持續(xù)收斂。

總體來(lái)看，圖8（a）～（d）的收斂曲線最終結(jié)果基本都是LFACO大于去除其他兩種改進(jìn)策略只保留混合轉(zhuǎn)移規(guī)則的改進(jìn)算法，大于不包括混合轉(zhuǎn)移規(guī)則的改進(jìn)算法，體現(xiàn)了混合轉(zhuǎn)移規(guī)則的優(yōu)越性。尤其對(duì)于大規(guī)模城市數(shù)據(jù)集，LFACO的表現(xiàn)明顯優(yōu)于其他兩種算法，其曲線始終保持在較低位置，充分證明了LFACO在全局和局部搜索能力方面的出色表現(xiàn)。

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

LFACO的實(shí)驗(yàn)結(jié)果如表2所示。在表中，BKS代表了每個(gè)TSP實(shí)例的十個(gè)解決方案中的最優(yōu)解長(zhǎng)度。best和worst分別表示算法在每個(gè)TSP實(shí)例的十個(gè)解決方案中的最佳和最差實(shí)驗(yàn)結(jié)果，average則表示了這十個(gè)解決方案的平均值。Mr表示平均誤差率，它反映了average與BKS之間的相對(duì)誤差；Er表示誤差率，它反映了best與BKS之間的相對(duì)誤差。

從表2可以看出，eil51、eil76、kroA100、kroB100和kroB150的實(shí)驗(yàn)結(jié)果均達(dá)到了BKS。對(duì)于其他數(shù)據(jù)集，盡管并未達(dá)到BKS，但是誤差均小于3%。圖9顯示了部分LFACO計(jì)算的TSP實(shí)例的最優(yōu)解決方案。總的來(lái)說(shuō)，LFACO對(duì)于TSP表現(xiàn)出了較好的性能。

3.4 與其他算法的對(duì)比

3.4.1 與經(jīng)典蟻群算法對(duì)比

表3為經(jīng)典算法ACS和MMAS與LFACO對(duì)比實(shí)驗(yàn)時(shí)的參數(shù)設(shè)置。圖10為與ACS的多樣性對(duì)比。表4對(duì)比了LFACO與傳統(tǒng)的ACS和MMAS在不同規(guī)模的TSP實(shí)例上的優(yōu)化性能，其中粗體數(shù)字代表每個(gè)類別中的最佳結(jié)果。從表中數(shù)據(jù)可以明顯看出，LFACO在除了pr439的best結(jié)果之外，在其他所有的類別中都顯著優(yōu)于ACS和MMAS。而MMAS在pr439的best結(jié)果中，僅比LFACO多優(yōu)化了68個(gè)距離單位。因此，本文可以得出結(jié)論，LFACO在大多數(shù)的TSP實(shí)例上都能夠獲得更優(yōu)質(zhì)的解決方案，相比于傳統(tǒng)的ACS和MMAS，具有更強(qiáng)的優(yōu)化性能。

如圖11所示，可以清晰地觀察到LFACO在所選的TSP實(shí)例中能夠快速地收斂到最優(yōu)解或接近最優(yōu)解，并且表現(xiàn)出良好的穩(wěn)定性。除了eil76實(shí)例外，LFACO的收斂曲線都位于其他兩種算法的曲線之下。在eil76實(shí)例中，MMAS的曲線在前200次迭代內(nèi)短暫地位于LFACO的下方，但隨后被LFACO超越。在tsp225實(shí)例中，由于城市規(guī)模的擴(kuò)大，在大約400次迭代之間，LFACO經(jīng)歷了一段停滯期。然而，由于信息素平均隨機(jī)重置策略的應(yīng)用，算法成功擺脫了局部最優(yōu)解，最終獲得了更小的最優(yōu)解。綜上所述，圖11表明LFACO具有強(qiáng)大的搜索能力和較快的收斂速度。

接下來(lái)將LFACO與傳統(tǒng)的MMAS的多樣性進(jìn)行比較。本文使用信息熵作為多樣性指標(biāo)，數(shù)值越大表示多樣性越高。在圖10中，選取數(shù)據(jù)集pr152和lin318進(jìn)行實(shí)驗(yàn)。從圖中可以觀察到，在pr152的實(shí)驗(yàn)中，兩種算法的波動(dòng)都相對(duì)穩(wěn)定。然而，總體而言，LFACO的多樣性要優(yōu)于ACS。在lin318中，LFACO的波動(dòng)范圍較大，但總體上仍相對(duì)穩(wěn)定，并且隨著迭代次數(shù)的增加而緩慢上升。相比之下，ACS在算法迭代的早期保持了較好的多樣性，但是不夠穩(wěn)定，并且隨著迭代次數(shù)的增加，多樣性逐漸下降。綜上所述，LFACO在多樣性方面表現(xiàn)更好。

3.4.2 與最新改進(jìn)的蟻群算法對(duì)比

表5列出了LFACO與其他最新改進(jìn)的蟻群算法的比較實(shí)驗(yàn)結(jié)果，包括HAACO［26］和GSACO［27］。HAACO是一種自適應(yīng)的異構(gòu)蟻群優(yōu)化算法，結(jié)合了信息素適應(yīng)策略、異構(gòu)蟻群結(jié)構(gòu)和3-opt局部搜索策略，用于解決旅行商問(wèn)題。GSACO是一種使用自適應(yīng)貪婪策略的蟻群優(yōu)化算法。表中顯示了七種不同規(guī)模的TSP實(shí)例的實(shí)驗(yàn)結(jié)果，可以看出，LFACO的數(shù)據(jù)均優(yōu)于GSACO和HAACO。

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

在旅行商問(wèn)題背景下，本文提出了一種基于MMAS的改進(jìn)算法，該算法采用了萊維飛行策略和動(dòng)態(tài)權(quán)重的混合轉(zhuǎn)移規(guī)則。通過(guò)動(dòng)態(tài)調(diào)整權(quán)重因子，使得算法在不同階段能夠靈活地選擇三種轉(zhuǎn)移規(guī)則的組合，從而提高了算法的收斂性能和解的質(zhì)量。此外，算法還采用了隨機(jī)多路徑優(yōu)化的3-opt策略和隨機(jī)信息素重置策略，進(jìn)一步提升了性能。研究階段包括理論分析和實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)在MATLAB環(huán)境中使用多個(gè)TSP實(shí)例進(jìn)行，首先，確定了合適的算法參數(shù)，包括混合轉(zhuǎn)移規(guī)則的權(quán)重因子，通過(guò)單獨(dú)的實(shí)驗(yàn)驗(yàn)證進(jìn)行確定。然后，在TSP數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并與傳統(tǒng)的蟻群算法以及其他最新改進(jìn)的蟻群算法進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果表明，LFACO在解的質(zhì)量、收斂速度和避免陷入局部最優(yōu)方面都具有顯著優(yōu)勢(shì)。然而，本文算法在處理大規(guī)模TSP實(shí)例時(shí)仍有改進(jìn)的空間。未來(lái)的研究將繼續(xù)優(yōu)化算法性能，并將其擴(kuò)展到更復(fù)雜的組合優(yōu)化問(wèn)題，如車輛路徑規(guī)劃。

參考文獻(xiàn)：

［1］Liu Meijiao，Li Yanhui，Li Ang，et al. A slime mold-ant colony fusion algorithm for solving traveling salesman problem ［J］. IEEE Access，2020，8： 202508-202521.

［2］Halim A H，Ismail I. Combinatorial optimization： comparison of heuristic algorithms in travelling salesman problem ［J］. Archives of Computational Methods in Engineering，2019，26： 367-380.

［3］陳加俊，譚代倫. 求解旅行商問(wèn)題的探索-開發(fā)-跳躍策略單親遺傳算法 ［J］. 計(jì)算機(jī)應(yīng)用研究，2023，40（5）： 1375-1380. （Chen Jiajun，Tan Dailun. Partheno-genetic algorithm based on explore-develop-jump strategy for solving traveling salesman problem ［J］. Application Research of Computers，2023，40（5）： 1375-1380.）

［4］禹博文，游曉明，劉升. 引入動(dòng)態(tài)分化和鄰域誘導(dǎo)機(jī)制的雙蟻群優(yōu)化算法 ［J］. 計(jì)算機(jī)應(yīng)用研究，2023，40（10）： 3000-3006. （Yu Bowen，You Xiaoming，Liu Sheng. Dual-ant colony optimization algorithm with dynamic differentiation and neighborhood induction mechanism ［J］. Application Research of Computers，2023，40（10）： 3000-3006.）

［5］Zhang Panli，Wang Jiquan，Tian Zhanwei，et al. A genetic algorithm with jumping gene and heuristic operators for traveling salesman problem ［J］. Applied Soft Computing，2022，127： 109339.

［6］Roy A，Manna A，Maity S. A novel memetic genetic algorithm for solving traveling salesman problem based on multi-parent crossover technique ［J］. Decision Making： Applications in Management and Engineering，2019，2（2）： 100-111.

［7］lhan ，Gkmen G. A list-based simulated annealing algorithm with crossover operator for the traveling salesman problem ［J］. Neural Computing and Applications，2022，34： 7627-7652.

［8］Gharehchopogh F S，Abdollahzadeh B. An efficient Harris hawk optimization algorithm for solving the travelling salesman problem ［J］. Cluster Computing，2022，25（3）： 1981-2005.

［9］Zhang Jin，Li Hong，Liu Qing. An improved whale optimization algorithm for the traveling salesman problem ［J］. Symmetry，2020，13（1）： 48.

［10］Khan I，Maiti M K. A swap sequence based artificial bee colony algorithm for traveling salesman problem ［J］. Swarm and Evolutionary Computation，2019，44： 428-438.

［11］Xue Jiankai，Shen Bo. A novel swarm intelligence optimization approach： sparrow search algorithm ［J］. Systems Science & Control Engineering，2020，8（1）： 22-34.

［12］Zhang Zhen，Han Yang. Discrete sparrow search algorithm for symmetric traveling salesman problem ［J］. Applied Soft Computing，2022，118： 108469.

［13］Stützle T，Hoos H H. MAX-MIN ant system ［J］. Future Generation Computer Systems，2000，16（8）： 889-914.

［14］Colorni A，Dorigo M，Maniezzo V. Distributed optimization by ant co-lonies ［C］// Proc of the 1st European Conference on Artificial Life. 1991： 134-142.

［15］Lee Z J. A hybrid algorithm applied to travelling salesman problem ［C］// Proc of IEEE International Conference on Networking，Sensing and Control.Piscataway，NJ： IEEE Press，2004： 237-242.

［16］Cheng J，Zhang Gexiang，Li Zhidan，et al. Multi-objective ant colony optimization based on decomposition for bi-objective traveling salesman problems ［J］. Soft Computing，2012，16： 597-614.

［17］Ban Habang. The hybridization of ACO+GA and RVNS algorithm for solving the time-dependent traveling salesman problem ［J］. Evolutionary Intelligence，2022，15（1）： 309-328.

［18］Dahan F，El Hindi K，Mathkour H，et al. Dynamic flying ant colony optimization （DFACO） for solving the traveling salesman problem ［J］. Sensors，2019，19（8）： 1837.

［19］Yang Kang，You Xiaoming，Liu Shen，et al. A novel ant colony optimization based on game for traveling salesman problem ［J］. Applied Intelligence，2020，50： 4529-4542.

［20］Dorigo M，Stützle T. Ant colony optimization： overview and recent advances ［M］. Berlin： Springer International Publishing，2019.

［21］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.

［22］Zhong Changting，Li Gang，Meng Zeng. Beluga whale optimization： a novel nature-inspired metaheuristic algorithm ［J］. Knowledge-Based Systems，2022，251： 109215.

［23］Bansal S R，Goel R K，Maini R. An improved ant colony algorithm based on Lévy flight distribution ［J］. Advances in Mathematics： Scientific Journal，2020，9（6）： 3907-3916.

［24］Liu Yahui，Cao Buyang. A novel ant colony optimization algorithm with Lévy flight ［J］. IEEE Access，2020，8： 67205-67213.

［25］Liu Yahui，Cao Buyang，Li Hehua. Improving ant colony optimization algorithm with epsilon greedy and Lévy flight ［J］. Complex & Intelligent Systems，2021，7： 1711-1722.

［26］Tuani A F，Keedwell E，Collett M. Heterogenous adaptive ant colony optimization with 3-opt local search for the travelling salesman problem ［J］. Applied Soft Computing，2020，97： 106720.

［27］Li Wei，Xia Le，Huang Ying，et al. An ant colony optimization algorithm with adaptive greedy strategy to optimize path problems ［J］. Journal of Ambient Intelligence and Humanized Computing，2022，13： 1557-1571.