基于遺傳算法的小規模TSP問題研究分析

□ 王港華

(蘭州交通大學 交通運輸學院,甘肅 蘭州 730000)

1 引言

1.1 研究背景及意義

我國物流業進入快速發展期是在“一帶一路”倡議提出之后，現代服務屬于新興第三產業，極大促進了我國現代城市的發展。現代物流不僅刺激了國民經濟的提升、促進了社會的發展，且由于經濟全球化的作用，發展潛力更大、發展空間更廣。然而，隨著物流體系的不斷擴大和貨物種類、流量的急速增加，傳統物流低下的配送效率已經無法滿足當今社會的發展，其過程很容易造成材料的過多消耗，人力、物力資源等過度浪費。互聯網的出現和發展使得電子商務逐漸成為主導，許多新型物流企業、物流中心、物流園區等相繼出現，改變了學者對我國現代物流發展模式的研究。快速發展的人工智能、區塊鏈以及大數據能夠對物流信息進行實時分析、處理以及網絡傳輸，并且能夠對體系運營做到自動管理。供應鏈整合、物流綜合化和集成物流等先進技術使得企業物流和社會物流成為全新的有機結合體。國外學者從不同角度、不同方面分析了供應鏈配送網絡的主要因素對現代物流發展的影響作用；部分學者從城市層面，依據地區經濟增長和運輸需求，結合相關地區環境，總結出各個因素相互關聯后對物流體系的影響，供應鏈管理思想和物流供應是其中的重要組成部分。

根據國內外市場復雜多變的現狀，國內很多大型物流企業紛紛大膽創新，積極面對困難，調整發展策略，與經濟“新常態”相結合，加快供應鏈整合，現代物流無疑為公司的發展開辟了新的有效途徑，企業的快速發展有利于加強生產和銷售，合理優化管理方式，促進經濟持續快速發展。

然而，由于近年來我國經濟普遍低迷，特別是新冠疫情后物流業承受的壓力空前巨大，企業經營困難，物流業轉型發展面臨重大挑戰。且國內物流業的發展還存在許多問題，其中最重要的是沒有充分認識發展物流業的重要性、物流行業的技術設備整體水平較低、高水平人才的嚴重缺失、高成本、低附加值以及物流發展無序、對于信息技術的發展相對落后等。在這種情況下，高效率的物流配送方式、科學有效的管理方法、最優的配送路徑是強化服務、降低成本的重要措施。在此背景下，深入研究物流運輸路線優化中的許多實際問題，結合合理高效的物流路線，提高效率、降低成本是重中之重。

1.2 研究現狀

車輛路徑問題(Vehicle Routing Problem，VRP)是研究物流配送問題中最具前景的問題之一，是物流配送的關鍵環節，也是提高物流效率的重要手段。VRP問題于1959年由Dantzig和Ramser提出，指的是有k輛貨車從配送中心向客戶運輸貨物，在滿足所有客戶需求的基礎上，達到運輸路程最短、運輸成本最低、耗費時間最少等目的。由VRP的定義可知旅行商問題(Traveling Salesman Problem，TSP)是VRP的特例，其模型適用于大部分經過簡化處理的優化領域內的問題，如物流配送[1]、網絡通訊、車輛路徑規劃[2]、智能交通控制、管道鋪設、電力系統輸電線路規劃等方面。

求解TSP問題時應用最廣泛的算法主要是遺傳算法(Genetic Algorithm,GA)和蟻群算法(Ant Colony Optimization，ACO)，已被眾多學者深入研究。周頔提出基于多種群多策略，且帶有參數自適應調整的混合遺傳-蟻群(HPSGAO)算法，利用遺傳策略和螞蟻策略的有效組合得到信息分配的最優解[3]，通過10個TSP問題的仿真實驗證明HPSGAO算法能以較快的收斂速度和較高的求解精度求解TSP問題。針對蟻群算法求解TSP收斂速度慢的問題，魏曉雨[4]改進了信息素更新策略，對蟻群算法進行優化，使算法的尋優能力更優，但并未考慮解的多樣性。鄭娟毅等[5]將蟻群算法與遺傳算法結合，解決了蟻群算法對信息素的強依賴性導致的局部最優解現象以及遺傳算法存在的全局搜索性能強但收斂速度慢等問題，仿真結果表明所提出的算法在求解不同規模的旅行商問題時具有更強的全局搜索性及快速收斂性。呂鵬和張憲華[6]基于改進遺傳算法對航空快遞配送類的TSP問題進行研究，有效解決了航空快遞配送的線路規劃問題，具有一定實用價值。徐佳等[7]提出生物信息啟發式遺傳算法(BHGA)，通過增量最小算法得到優質初始種群，采用基因逆轉變異算子提高算法的搜索能力和種群基因的多樣性，實驗結果說明該算法在中小規模TSP中求解效果較好且結果穩定。

基于以上內容，在此將遺傳算法與蟻群算法進行比較，最終用實例驗證所選算法對解決小規模TSP問題的合理有效性。

2 TSP問題和算法概述

2.1 TSP問題

旅行商問題是路徑規劃、組合優化等領域中的經典NP-hard問題[8]，即已知有n個城市，各城市之間互相聯通，且城市間的距離已知。一位旅行商從起點城市出發依次經過剩余城市，每個城市只經過一次，最后回到起點城市，制定最優路線使其所經歷的總路程最短。數學模型[9]定義如下：

(1)

(2)

(3)

∑i,j∈Sxi,j≤R-1,2≤|R|≤n-2,R?{1,2,…,n}

(4)

xi,j∈{0,1}，(i,j=1,2,…,n)

(5)

(1)為目標函數，di,j表示城市i，j之間的距離；(2)和(3)表示旅行商經過每個城市有且只有一次；(4)即旅行商不能重復經過任何一個城市；(5)是決策變量約束，1表示已經過的城市，0表示未經過的城市。

2.2 算法概述

2.2.1 ACO算法

蟻群算法又稱螞蟻算法，通常用來尋求最優路徑。1992年，Marco Dorigo在其博士論文中提出，通過模擬螞蟻在自然界協同工作和尋找食物的運動規律，在運動過程中引入信息素來尋找最優路徑。設螞蟻數量為m，城市x與城市y之間的距離為dxy(x,y=1,…,n)；λxy(t)表示能見度，稱為起發信息函數，等于距離的倒數，即t時刻能見度隨城市x與城市y之間的距離變近而增加，變遠而降低。各路徑上的信息素初始值相等，運動過程中螞蟻k(k=1,…,m)判別運動方向的主要依據是路徑上的信息素。某一時刻螞蟻k從元素x走到元素y(即從城市x走到城市y)的概率由信息素和局部啟發信息共同決定，也稱為隨機比例規則。當m只螞蟻完成一次路徑遍歷，即算法迭代一次后進行信息素更新。

2.2.2 GA算法

1975年Michigan大學的John Holland教授提出遺傳算法，其主要參考了生物界的進化規律，是從中演化而來的一種隨即搜索算法[10]。一般來說，遺傳算法主要通過選擇、交叉、突變等來模擬生物種群的進化過程，使個體之間不斷重組，并多次重復這個過程，不斷更新種群遺傳因子池和進化，選擇出更優秀的個體，從而無限接近適應度最高、最理想的水平。

遺傳算法的隨機性常體現在特定的進化過程中，但它對整個問題進行搜索時并不是完全隨機的。該算法主要利用父代的遺傳信息進行迭代再生過程來預估后代，實現對子代個體集合的預測，從中篩選出性能有所提升的優秀子代集合，最終實現預定的滿意度。當算法迭代收斂至最優時，表明問題已求得最優解。其算法基本流程如圖1所示。

圖1 遺傳算法流程圖

2.2.3 算法對比

在求解TSP問題實驗中選擇采用隨機數據來最大化模擬實際情況，初始城市坐標數據來源于隨機數。隨機產生10個100以內的點(用x表示橫坐標，y表示縱坐標)表示10個城市，雖然每次出發的起點不確定，但有些路徑在形成閉合回路后為同一路徑，路徑數據一致，應被視為相同回路，為篩選出重復路徑，需設計一個回路排重算法以保證路徑的唯一性，基本思想是列出所有可能形成回路的路徑中10個城市的所有組合序列進行兩兩比較，刪除重復路徑只保留一條，最后輸出最終篩選出的所有路徑以供后續實驗所用。

在TSP問題的求解過程中，問題規模的大小對算法運行的時間有較大影響，比較不同算法在同一問題規模下的運行時間以及運行時間會隨著問題規模的增加而如何變化，得出具體實際應用時應選擇的最佳算法。實驗迭代次數為1000次，在城市個數都為20的情況下，蟻群算法耗費的平均時間約為0.50s，遺傳算法耗費的平均時間約為0.48s。再將問題規模即城市個數增加到100，根據兩種算法運行所得出的數據繪制出問題規模與運行時間的關系圖，如圖2所示。

從圖2中可看出，兩種算法的運行時間隨著城市個數的增加而呈現出逐漸增大的趨勢，但在遺傳算法(GA)中，城市個數與運行時間大致呈線性關系，而蟻群算法(ACO)中城市個數與運行時間的曲線走勢更趨向于二次函數。總體來說，雖然遺傳算法運行時間沒有蟻群算法穩定，但遺傳算法的運行時間要比蟻群算法的運行時間低。根據既有研究可知，從規模與時間、正確性以及穩定性三個方面進行對比后發現，遺傳算法的正確率高于蟻群算法且穩定性也更高[10]。故在此文中使用遺傳算法。

圖2 城市個數與運行時間的關系

2.3 遺傳算法求解TSP問題基本操作

①編碼策略。如何進行編碼會直接影響到算法的進化性能以及算法效率的高低，還會影響到遺傳算子的設計方式。編碼方法的主要標準是完備性(completeness)、健全性(soundness)和非冗余性(nonredundancy)[11]。

②初始種群的設計。當選擇、交叉、變異等遺傳算子被選定時，初始種群生成策略的優劣會在很大程度上影響到算法的運行效率以及整體的收斂性能。大部分情況下的初始種群是隨機產生的，然后根據問題要求對初始種群的規模進行設定，首先隨機產生一定數量的個體，再從這些個體中挑選出較優秀的個體組成初始種群，然后進行多次迭代，直至得到設定數目的最優初始種群[11]。

③適應度函數的選擇。適應度函數是群體中個體生存機會選擇的評價指標，它的形式直接決定群體進化行為，且適應度函數一般是由目標函數轉變而來[12]。此處問題目標是路徑總長度最短，所以適應度函數f(x)通過取倒數得到

(6)

(7)

P(x)表示旅行商無重復地經過所有城市并且回到起點城市時所產生的總距離，d(pi,pi+1)表示旅行商經歷的路徑中城市i到相鄰城市i+1的距離。

④遺傳操作。遺傳操作包括選擇、交叉和變異，可使問題的解逐代優化，接近最優解。此過程是根據具體問題選擇一定個數的個體參與進化，選擇的個體數越小，越容易造成算法早熟收斂。個體被選擇的概率與個體適應度標準呈正相關，隨著適應度標準的增高，個體被選擇的概率也會逐漸增加，根據遺傳的特性可知，適應度越高的種群，往往遺傳到下一代種群的概率也就越大。反之，適應度越低，進行遺傳的概率也就越低。選擇概率的大小也會影響算法收斂的快慢，選擇概率越大，算法收斂越快；選擇概率越小則會出現降低個體同質化的同時，降低算法性能的現象，故在處理算法的收斂性和效率時，通常采取折衷的辦法來考慮問題。輪盤賭為常用的選擇算子[13]。

交叉操作是遺傳算法的核心，直接決定了遺傳算法性能的優劣，同時算法的搜索能力也通過交叉操作得到極大提高。交叉方式在設計時主要考慮兩方面的問題：減少因交叉方式的隨機性，破壞優秀個體，還有可能會增加多樣性個體產生的問題的發生，另一問題就是要避免個體同質化[14]。

變異算子是以很小的變異概率(通常取0-0.2)隨機將染色體中的基因運用一定方式進行替換，形成新的染色體，與基因突變機理相似，這樣基本上對算法局部搜索性能的高低有了一定的決定性[15]。在TSP問題中將一個算子在兩個隨機整數對應的編號城市間進行隨機多次對換，目的是為了增強進化活力，以一定概率更新個體基因。

種群中的個體在遺傳算法的中后期大都逼近最優解，只依賴交叉操作很難產生新的個體，變異操作可以增加個體多樣性，對個體同質化問題也可以很好地解決，從而使得算法能夠全面地、有效地解決所求問題。

3 實例分析

3.1 問題描述

假定某配送中心及其服務客戶分布在二維坐標內，配送中心所在位置為(3,4)，服務客戶坐標如表1所示(MAXC=12)。

配送車輛配載貨物后從配送中心出發，需配送每一個客戶，并最終返回配送中心，求解車輛的最短行駛距離。

表1 配送客戶坐標信息

3.2 求解過程及結果分析

利用表1中的數據在EXCEL中繪制散點圖，如圖3所示。

圖3 客戶分布散點圖

在MATLAB中導入數據，得到交叉、變異概率分別為0.8%、0.2%，迭代次數為150，通過運行程序得到最優配送順序。

圖4是以1(3,4)為配送中心(即始發點)的最優配送路徑圖，最優配送順序為：1-2-3-4-5-7-10-13-12-11-9-8-6-1，最優配送里程為227.0663。圖5是上述問題的收斂曲線圖。

經過分析可知，遺傳算法在求解問題時不具有唯一性，由于遺傳算法的隨機性，其計算的結果也有區別，需要經過多次分析計算，選出最優解。通過對實例的求解發現，遺傳算法很適合小規模TSP問題的分析計算求解，其迭代次數與個體數目成正比，個體數目越多，則需要更多次迭代才能得到最優解。

圖4 遺傳算法最優路徑圖

圖5 遺傳算法收斂曲線

4 總結與展望

旅行商問題是一個NP-hard問題，具有廣闊的應用前景和很高的科研價值以及很重要的現實研究應用意義。遺傳算法是智能算法中解決此類問題的一個重要分支，通過實例驗證，在實際求解過程中可以利用遺傳算法獲得某一穩定的近似最優解，但存在難以對局部空間搜索的缺點，導致搜索進行到進化后期時效率偏低，進而使得所得到的解可能不是最優解。而常用的局部搜索由于高復雜性等原因，難較精細地對個體領域進行搜索，針對此問題還有很大的研究空間。