一種應用于旅行商問題的萊維飛行轉移規則蟻群優化算法

丁增良 陳玨 邱禧荷

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

關鍵詞：蟻群算法；旅行商問題；萊維飛行；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 引言

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

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

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

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

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

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

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

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

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

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

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

1 相關工作

1.1 最大最小蟻群算法

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

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

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

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

1.2 轉移規則

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

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

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

1.3 萊維飛行

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

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

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

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

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

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

2 算法描述

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

2.1 動態權重的混合轉移規則

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

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

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

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

next_node=nearest_node（Xnew，Ynew）（9）

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

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

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

為了平衡算法的探索性和開發性，本文將基于萊維飛行的轉移規則與基于貪心的轉移規則和基于概率的轉移規則進行組合，創造一種新的混合轉移規則。

前文已經介紹了萊維飛行的特性，它模擬了萊維飛行中的長距離跳躍，并在全局搜索中起到跳出局部最優解的作用，提高了算法的探索范圍和多樣性，增強了全局搜索能力。基于貪心的轉移規則則利用局部最優信息，選擇具有最大概率的節點作為下一個移動的節點，加快了算法的收斂速度，能夠快速收斂到局部最優解，增強了局部搜索能力。傳統的基于概率的轉移規則則使用輪盤賭法，根據節點上的信息素濃度選擇下一個節點，它在動態權重的混合轉移規則中起到平衡開發和探索的作用，通過信息素濃度的引導和一定程度的隨機性，有助于維持算法的多樣性和全局搜索能力。

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

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

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

2.2 局部優化策略

2.2.1 隨機多路徑優化3-opt策略

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 LFACO算法流程

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

3 實驗與結果分析

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

3.1 實驗參數設置

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

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

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

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

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

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

3.2 動態權重的混合轉移規則分析

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

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

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

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

3.3 LFACO實驗結果

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

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

3.4 與其他算法的對比

3.4.1 與經典蟻群算法對比

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

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

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

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

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

4 結束語

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

參考文獻：

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