丁增良 陳玨 邱禧荷

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

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

中圖分類號：TP18?? 文獻標志碼：A??? 文章編號：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 引言

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

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

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

1.1 最大最小蟻群算法

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

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

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

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

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

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

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

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

1.3 萊維飛行

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

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

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

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

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

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

2 算法描述

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

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

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

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

為了模擬旅行商在二維空間中的移動過程，假設旅行商從當前城市出發(fā)，按照隨機方向和一定的步長前進，以達到新的坐標位置。該過程可以表示為

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

next_node=nearest_node（Xnew，Ynew）（9）

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

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

算法1 使用新坐標獲取下一個移動節(jié)點

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

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

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

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

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

2.2 局部優(yōu)化策略

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

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

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

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

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

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

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

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

2.2.2 信息素平均隨機重置策略

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

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

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

算法2 信息素平均隨機重置策略

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

2.3 LFACO算法流程

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

3 實驗與結(jié)果分析

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

3.1 實驗參數(shù)設置

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

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

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

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

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

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

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

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

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

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

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

3.3 LFACO實驗結(jié)果

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

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

3.4 與其他算法的對比

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

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

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

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

3.4.2 與最新改進的蟻群算法對比

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

4 結(jié)束語

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

參考文獻：

［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］陳加俊，譚代倫. 求解旅行商問題的探索-開發(fā)-跳躍策略單親遺傳算法 ［J］. 計算機應用研究，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］禹博文，游曉明，劉升. 引入動態(tài)分化和鄰域誘導機制的雙蟻群優(yōu)化算法 ［J］. 計算機應用研究，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.