摘 要：遺傳算法在TSP問題的解決過程中發(fā)揮著較為重要的作用。本文從遺傳算法的基本原理與算法步驟入手，簡述遺傳算法的基本原理及遺傳算法的基本步驟，然后對基于遺傳算法的TSP問題解決方式進行了分析，包括TSP問題建模、TSP問題遺傳算法設計、編碼方式、算子選擇、單點交叉、變異算子、其他參數(shù)等，最后從選擇因子分析和算法測試分析兩方面對基于遺傳算法的TSP問題實驗進行了探究。

關鍵詞：遺傳算法；TSP問題；遺傳操作

中圖分類號：TP18 文獻標識碼：A 文章編號：2096-4706（2019）04-0010-03

Exploration of Solving TSP Problem Based on Genetic Algorithms

YUE Pengqi

（Liaoning Normal University Haihua College，Shenyang 110167，China）

Abstract：Genetic algorithm plays an important role in solving TSP problem. This paper starting with the basic principles and steps of genetic algorithm，briefly describes the basic principles and steps of genetic algorithm，and then analyses the solution of TSP problem based on genetic algorithm，including TSP problem modeling，genetic algorithm design of TSP problem，coding method，operator selection，single point crossover，mutation operator，other parameters，etc. ，finally，the experiment of TSP based on genetic algorithm is explored from two aspects of selection factor analysis and algorithm test analysis.

Keywords：genetic algorithm；TSP problem；genetic operation

0 引 言

旅行商問題（TSP問題）是諸多領域中存在的、多種復雜問題的集中概括。在解決此類問題的過程中，研究者不能借助全局搜索算法確定此類問題的最優(yōu)解。為確定此類算法的最優(yōu)解與次優(yōu)解，一些研究者開始將遺傳算法應用于TSP問題的解決過程之中。遺傳算法是建立在自然界生物適者生存、優(yōu)勝劣汰的遺傳機制基礎之上的全局優(yōu)化算法。這一算法具有良好的自組織性、自適應性與自學習性?，F(xiàn)階段遺傳算法已經(jīng)開始在組合優(yōu)化問題、機器學習問題及自適應控制問題等問題的解決過程中得到應用。利用遺傳算法的基本思想與優(yōu)化原理，構建解決TSP問題的遺傳算法程序，有助于降低TSP問題的解決難度。

1 遺傳算法的基本原理與算法步驟

1.1 遺傳算法的基本原理

遺傳算法是一種基于全局優(yōu)化的隨機搜索算法。通過對這一算法的基本原理進行分析，發(fā)現(xiàn)此種算法可以對自然界生物的自然選擇與遺傳變異過程進行有效模擬，進而在融入適者生存等進化機制的基礎上，讓群體進化到最優(yōu)解。

在應用于實際問題解決過程以后，人們可以利用基于遺傳算法的隨機方式生成若干個與某一問題有關的個體，構建初始種群。在初始種群建構完成以后，研究者需要根據(jù)問題的實際情況構建適應度函數(shù)，并對每一個個體的適應度進行考量，以淘汰一些適應度較低的個體。在經(jīng)過選擇操作、交叉操作和變異操作等一系列遺傳操作以后，研究者可以在新一代更優(yōu)秀的種群形成以后對新一代種群進行處理，進而確定問題的最優(yōu)解與近似最優(yōu)解。一般情況下，遺傳算法主要由以下內容構成：（1）個體編碼；（2）適應度函數(shù)設計；（3）遺傳操作設計；（4）控制參數(shù)的確定。個體編碼是確定初始種群的重要方式。遺傳算法的控制參數(shù)需要包含種群大小、最大進化代數(shù)、交叉概率、變異概率及終止條件等信息。

1.2 遺傳算法的基本步驟

在實際應用過程中，遺傳算法的基本步驟主要涉及到以下幾方面內容：（1）數(shù)據(jù)初始化處理；（2）適應度的計算；（3）遺傳操作的實施；（4）終止條件的判斷。數(shù)據(jù)初始化過程可以被看作是最大進化代數(shù)的生成過程與種群大小的設置過程，這一過程也是初始群體的建構過程。適應度計算過程是對群體中所包含的各個個體的適應度進行計算的過程。在遺傳操作方面，研究者在遺傳算法應用于實際問題解決過程以后，可以借助于選擇運算、交叉運算及變異運算等運算方式確定下一代群體。根據(jù)遺傳算法的實際特點，選擇操作要建立在群體中的個體適應度評估機制的基礎之上。基于個體適應度評估的選擇操作可以讓算法中選用的優(yōu)秀個體遺傳到下一代，或借助配對交叉的方式，將一些產(chǎn)生的個體遺傳到下一代。在交叉操作應用以后，研究者可以根據(jù)交叉概率完成父代個體的部分結構重組，進而生成新的個體。變異操作建立在變異概率的基礎之上，此種操作方式可以讓研究者對選中的個體串的基因值進行調整，以形成新的個體。在進化代數(shù)達到研究者預先設置的最大進化代數(shù)以后，遺傳算法可以將進化過程中得到的具有最大適應度的個體視為輸出最優(yōu)解，此時研究者需要終止計算，完成結果的輸出。

2 基于遺傳算法的TSP問題的解決方式

2.1 TSP問題建模

一般情況下，TSP問題可以通過以下內容進行表述，一片區(qū)域內分布有N個城市，區(qū)域內每個城市之間都有一定的距離，一位旅行商需要訪問這些城市，要求每個城市都要訪問到，且每個城市只能訪問一次，旅行商訪問結束后需要返回出發(fā)的城市，如何安排旅行商的訪問路線，讓旅行商所進過的路徑的總長度最短。

根據(jù)問題的實際內容，研究者首先需要對城市進行編號，如0，1，……n-1。在編號完成以后，研究者可以從不同城市的距離信息入手，構建二維數(shù)組，TSP問題的數(shù)學模型需要包含總路程長度、總城市數(shù)量和兩個不同城市之間的距離等信息。

2.2 TSP問題遺傳算法設計

初始化群體和適應度函數(shù)（含終止條件）的設定是TSP問題遺傳算法設計中的重要內容。根據(jù)前文論述，編碼方法是出于問題研究需要而隨機產(chǎn)生的初始群體。與之相關的適應度函數(shù)多采用求取函數(shù)最大值的函數(shù)。根據(jù)TSP問題的特點，適應度與滾動條的路徑之間具有正相關關系，即個體的適應度越小，個體的路徑越短。在解決TSP問題的過程中，與游歷城市的數(shù)量及與問題內容有關的懲罰系數(shù)函數(shù)也是不可忽視的內容。

2.3 編碼方式

遺傳基因編碼在遺傳算法應用過程中發(fā)揮著較為重要的作用。在遺傳算法應用于TSP問題解決過程以后，編碼可以被看作是交叉操作與變異操作的實用性的主要影響因素。根據(jù)TSP問題的實際情況，研究者可以構建一種以順序表示的遺傳基因編碼方法。在順序表示的遺傳編碼應用于TSP問題解決過程以后，研究者可以按照一定次序，將旅行商行程中所要經(jīng)過的城市編成順序表，如用數(shù)字0～9代表旅行商的旅行路徑。在旅行路徑確定以后，以下編碼方式可以應用于TSP問題的處理過程中：（1）輪盤賭選擇法；（2）隨機聯(lián)賽選擇法；（3）期望值選擇法。其中輪盤賭選擇法是一種較為常用的選擇方式。此種編碼方式可以讓個體的適應度轉化為選中的概率。在輪盤賭選擇方式應用于TSP問題處理過程以后，研究者可以將每個個體視為輪盤中的一小塊扇形，扇形的大小與該染色體被選中的概率之間具有正相關關系。輪盤賭選擇法在TSP問題編碼處理過程中的應用可以讓適應度較大的個體編程輪盤中扇形面積較大的個體，即適應度較強的個體轉化為輪盤中扇形面積較大的個體以后，使一些優(yōu)質個體進入下一代群體的概率有所增加，故而輪盤賭選擇法的應用，可以讓算法更為趨近最優(yōu)解。

2.4 算子選擇

算子選擇過程是從舊有種群中選擇生命力較強的個體位串，構建新的種群的過程。這一過程可以被看作是個體根據(jù)特定的適值函數(shù)完成自身復制的過程。在遺傳算法中，適值函數(shù)主要指人們所期望的最大效益的某種量度，這一過程是模仿自然選擇現(xiàn)象的過程，如根據(jù)達爾文的適者生存理念，相對強勢的個體可以在下一代中產(chǎn)生一個或多個子孫，在遺傳算法應用于實際問題解決過程以后，算子選擇可以被看作個體繁衍下一代的過程。因此，遺傳算法可以被看作是達爾文適者生存理念應用于計算機技術領域的產(chǎn)物。根據(jù)前文論述，輪盤賭選擇法可以讓算法更為趨近最優(yōu)解。但是在TSP問題的解決過程中，遺傳算法的全局收斂性也是研究者不可忽視的內容。群體的個體多樣性可以被看作是遺傳算法的全局收斂性的主要影響因素。在算子選擇過程中為遺傳算法的全局收斂性提供保障，可以在增加個體在種群中的分布區(qū)域的基礎上實現(xiàn)遺傳算法的改善，但是這項措施可能會讓計算時間有所增加。

2.5 單點交叉

交叉算子在遺傳算法中發(fā)揮著較為重要的作用。在解決TSP問題的過程中，基于路徑的部分映射交叉是一些研究者關注的內容。在此種映射交叉投入使用以后，研究者需要在已經(jīng)生成的父個體中選擇兩個雜交點，并要在完成段的交換以后，根據(jù)段內城市確定映射。根據(jù)TSP問題解決過程的實際需要，父代個體之中需要填入一些無沖突的城市。針對一些存在路徑?jīng)_突的城市，研究者可以通過執(zhí)行部分映射的方式，在處理沖突后獲取交叉后的兩后代。與之相關的順序交叉與映射交叉操作之間具有一定的相似性。研究者仍然需要在父個體中確定兩個不同的雜交點，并要在交換雜交段的基礎上實現(xiàn)順序交叉。在順序交叉的實施過程中，父代個體中的城市的相對次序可以被看作其他位置的決定因素。根據(jù)遺傳算法的研究現(xiàn)狀，循環(huán)交叉在TSP問題處理過程中的應用也成為了一些研究者關注的內容。在循環(huán)交叉應用以后，研究者需要讓選取的兩個父個體呈現(xiàn)出參照與被參照的關系，在父個體城市重組工作完成以后，研究者需要在利用重組后的個體組建循環(huán)鏈的基礎上，確定不同城市的位置。

通過映射交叉、順序交叉與循環(huán)交叉均關注的城市位置與次序，導致對不同城市之間連接的忽視，會給TSP問題最優(yōu)化方案的科學性帶來不利的影響，在對城市間的位置及城市間的關系進行充分分析以后，一些研究者開始將單點交叉方式應用于此類問題的處理過程。單點交叉是研究者在個體編碼串中隨機設置交叉點，利用該點交換基因串的措施。根據(jù)前文所述，假設兩種父代個體分別為：0265|948371，另外一組父代個體為：0539|268714。在選擇的交叉點為第五個位置的情況下，研究者可以從交叉點開始，完成父代個體基因串的呼喚，此時第一組中間個體可以表示為：0265|268714，第二組中間個體可以表示為：0539|948371。中間個體中的交叉點之后的基因串中與交叉點重復的基因刪除以后，研究者可以在后序補齊所缺基因，并在此基礎上構建以下兩種自帶個體，其中，第一種子代個體可以表示為：0265、871439，第二種子代個體可以表示為0539|487126。通過對上述交叉方式的應用效果進行分析，發(fā)現(xiàn)此種方式可以讓隨機選擇的處理性能有所改善。

2.6 變異算子

在遺傳算法實際應用過程中，復制和交叉操作會可能會導致部分遺傳信息丟失。在人工遺傳系統(tǒng)中，變異算子可以有效避免遺傳信息丟失。在一些相對簡單的遺傳算法中，變異主要指某個字符串及某一位的值出現(xiàn)的偶然改變，這種改變形式具有隨機化的特點。變異可以沿著個體字符空間隨機移動。在變異算子與交叉算子共同應用于TSP問題解決過程以后，變異算子可以避免過度成熟而導致的概念丟失問題。

變異可以被看作是一種特殊化的局部隨機搜索形式。變異算子與選擇算子或重組算子的結合，可以為遺傳算法的實效性提供保障，也可以讓遺傳算法的局部隨機搜索能力得到強化。變異算子在TSP問題解決過程中的應用可以為遺傳算法的種群多樣性提供保障，但是就遺傳算法的實際應用情況而言，研究者需要對變異操作的變異率進行嚴格控制。同交叉算子相比，變異算子的設計形式具有一定的靈活性，以簡單化的倒位操作為例，研究者可以借助變異算子，在父個體中隨機選取截斷點。在確定截斷點以后，研究者可以將兩點所夾的子串中的城市進行反序處理，保證算法的實用性。

2.7 其他參數(shù)

遺傳算法應用于TSP問題解決過程以后，初始種群與適應度函數(shù)可以被看作與TSP問題解決方案有關的其他參數(shù)。根據(jù)TSP問題的相關內容，隨機產(chǎn)生種群規(guī)模的數(shù)量可以被看作是初始種群，以TSP問題的目標函數(shù)值的倒數(shù)為適應度函數(shù)的適應度函數(shù)選擇方式也是TSP問題處理過程中常用的適應度函數(shù)確定方式。

3 基于遺傳算法的TSP問題的實驗分析

3.1 選擇因子分析

物流配送問題是TSP問題的反映。在物流配送過程中，相關人員需要沿著可行道路行進。與之相關的坐標系中的兩點之間的距離計算不能采用直連計算的計算方式。道路的擁堵程度、物流配送車輛的行駛速度、車輛的容量空間等因素可以被看作配送工作的主要影響因素。在坐標系中，兩點無法進行直連計算的情況下，研究者需要利用坐標系確定道路位置，進而在建立路徑函數(shù)的基礎上，完成坐標點的計算。針對配送車輛行使速度及道路擁堵程度對物資配送情況的影響，研究者也需要構建擁堵系數(shù)函數(shù)與交通信號燈限行時間函數(shù)。各個路口的實施限行情況與擁堵狀況也是遺傳算法應用以后不可忽視的問題。針對車輛容積的現(xiàn)狀，研究者可以借助于旅行商問題的處理思路解決這一問題，并在對車輛將貨物送到目的地以后返回轉運中心裝載貨物，再次出發(fā)的過程進行模擬。結合問題實際情況，對遺傳算法進行改進。為了讓遺傳算法更接近于物流配送工作的實際情況，研究者可以通過引入可變鄰域所搜索的方式，解決跨道路問題難以通過編譯方式獲取最優(yōu)號碼段的問題。為提升優(yōu)秀子代的選擇效率，研究者也需要在改進適應度函數(shù)與選擇算子的基礎上生成優(yōu)質子代，并從城市編碼定義入手，對相關算法進行改進。

3.2 算法測試分析

遺傳算法應用于物流配送TSP問題的解決過程以后，研究者也需要在道路關鍵點完成各個路口之間道路連接情況的鄰接矩陣構建，為了確定兩個路口之間的最近道路距離與最短路徑，研究者可以將Dijkstra算法應用于實際計算過程之中。雖然這一算法的應用可以為主路徑的有效性提供保障，但是在實際應用過程中，算法所設計的最短路徑與設計最短路徑之間可能存在一定的偏差，故而混合路徑方案設計是解決二者偏差的可行措施。針對兩個目標點距離較近時可能出現(xiàn)的繞路問題，研究者需要借助于一定范圍內的直角路線方案，為路線方案的有效性提供保障。為保證路徑結果的視覺效果在實際路徑結果多次途經(jīng)主干路的情況下，研究者可以通過路徑圖與直連結果圖相結合的方式，保證路線圖的美觀性。

4 結 論

遺傳算法在實際求解過程中可以獲得某一穩(wěn)定的近似最優(yōu)解。初始化群體和適應度函數(shù)（含終止條件）的設定是TSP問題遺傳算法設計中的重要內容。以TSP問題的目標函數(shù)值的倒數(shù)為適應度函數(shù)的適應度函數(shù)選擇方式也是TSP問題處理過程中常用的適應度函數(shù)確定方式。在實際環(huán)境下，算法的全局優(yōu)化能力仍然是研究者所要關注的內容。在物理配送方面的TSP問題的解決過程中，選擇因子的靈活應用有助于提升遺傳算法的實用性。

參考文獻：

[1] Chvátal V，Cook W，Dantzig G B，et al.Solution of a Large-Scale Traveling-SalesmanProblem [J].50Years of Integer Programming1958-2008，2010.

[2] John J. Grefenstette. Proceedings of the First International Conference on Genetic Algorithms and their Applications [M].S.l.：Taylor and Francis，2013.

[3] 鄧慧允，張清泉.蟻群算法與遺傳算法在TSP中的對比研究 [J].山西師范大學學報（自然科學版），2017，31（3）：34-37.

[4] 蔣然.改進遺傳算法在TSP問題中的應用 [J].軟件導刊，2016，15（12）：127-129.

[5] 陸游，何嘉.基于并行優(yōu)化與訪存優(yōu)化遺傳算法的TSP問題求解方法 [J].四川文理學院學報，2017（2）：11-17.

[6] 李月.基于遺傳算法的免疫算法對TSP問題的改進與研究 [J].中國傳媒大學學報（自然科學版），2017（4）：58-63.

[7] 饒衛(wèi)振，王新華，金淳，等.一類求解TSP構建型算法的通用改進策略 [J].中國科學：信息科學，2015，45（8）：60-79.

[8] 史小明.淺談MATLAB下的遺傳算法優(yōu)化軟件設計 [J].數(shù)字技術與應用，2017（6）：146+149.

[9] 宋海聲，呂耕耕，劉岸果.一種基于分層模型的TSP構建算法 [J].微型機與應用，2017，36（6）：13-15+21.

[10] 伍建偉，劉夫云，李嶠.MATLAB遺傳算法函數(shù)ga優(yōu)化實例 [J].機械工程與自動化，2017（2）：61-63.

[11] 武海峰.基于Matlab的遺傳算法程序設計探討 [J].電腦迷，2017（1）：4.

[12] 袁明珠.Matlab遺傳算法工具箱在約束非線性懲罰函數(shù)中的應用 [J].軟件工程，2017，20（1）：37-39.

[13] 姚明海，王娜，趙連朋.改進的模擬退火和遺傳算法求解TSP問題 [J].計算機工程與應用，2013，49（14）：60-65.

[14] 趙功勛，郭海濱，蘇利.基于遺傳算法的工程項目資源均衡優(yōu)化及其MATLAB實現(xiàn)[J].工程經(jīng)濟，2016，26（12）：59-64.

[15] 宗德才，王康康.一種混合局部搜索算法的遺傳算法求解旅行商問題 [J].計算機應用與軟件，2015，32（3）：266-270+305.

作者簡介：岳鵬齊（1997.04-），男，漢族，遼寧錦州人，本科在讀，研究方向：計算機科學與技術。