基于遺傳算法解決TSP問題探索

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

關(guān)鍵詞：遺傳算法；TSP問題；遺傳操作

中圖分類號：TP18 文獻標(biāo)識碼：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問題）是諸多領(lǐng)域中存在的、多種復(fù)雜問題的集中概括。在解決此類問題的過程中，研究者不能借助全局搜索算法確定此類問題的最優(yōu)解。為確定此類算法的最優(yōu)解與次優(yōu)解，一些研究者開始將遺傳算法應(yīng)用于TSP問題的解決過程之中。遺傳算法是建立在自然界生物適者生存、優(yōu)勝劣汰的遺傳機制基礎(chǔ)之上的全局優(yōu)化算法。這一算法具有良好的自組織性、自適應(yīng)性與自學(xué)習(xí)性。現(xiàn)階段遺傳算法已經(jīng)開始在組合優(yōu)化問題、機器學(xué)習(xí)問題及自適應(yīng)控制問題等問題的解決過程中得到應(yīng)用。利用遺傳算法的基本思想與優(yōu)化原理，構(gòu)建解決TSP問題的遺傳算法程序，有助于降低TSP問題的解決難度。

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

1.1 遺傳算法的基本原理

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

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

1.2 遺傳算法的基本步驟

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

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

2.1 TSP問題建模

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

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

2.2 TSP問題遺傳算法設(shè)計

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

2.3 編碼方式

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

2.4 算子選擇

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

2.5 單點交叉

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

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

2.6 變異算子

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

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

2.7 其他參數(shù)

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

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

3.1 選擇因子分析

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

3.2 算法測試分析

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

4 結(jié) 論

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

參考文獻：

[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].山西師范大學(xué)學(xué)報（自然科學(xué)版），2017，31（3）：34-37.

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

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

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

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

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

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

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

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

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

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

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

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

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