摘 要：旅行商問題是典型的NP組合優(yōu)化問題。提出一種旅行商問題求解應(yīng)用上的改進遺傳算法。引入貪心算法優(yōu)化初始種群，在輪盤賭選擇基礎(chǔ)上，融入最優(yōu)保存策略和摻雜算子進行選擇操作，以保證群體的多樣性；基于兩點三段隨機交叉算子優(yōu)化交叉結(jié)果，基于啟發(fā)式倒位變異算子提高算法的收斂速度；給出了求解旅行商問題系統(tǒng)的體系結(jié)構(gòu)。實驗結(jié)果表明，改進的遺傳算法具有更好的尋優(yōu)能力。

關(guān)鍵詞：旅行商問題；遺傳算法；貪心算法；組合優(yōu)化；體系結(jié)構(gòu)

DOIDOI：10.11907/rjdk.162168

中圖分類號：TP319

文獻標(biāo)識碼：A文章編號：1672-7800（2016）012-0127-03

0 引言

旅行商問題（Traveling Salesman Problem，TSP）是典型的NP組合優(yōu)化問題，具有重要的理論價值和良好的應(yīng)用背景，諸如半導(dǎo)體電路設(shè)計、公路網(wǎng)絡(luò)建設(shè)、飛機航線安排、連鎖店貨物配送路線等，通過TSP建模均可解決。求解TSP問題方法包括精確算法、近似算法和智能算法。文獻[1]采用遺傳算法基礎(chǔ)上派生出來的分布估計算法求解TSP問題，并將種群進行分級處理，根據(jù)種群級別高低分別采用不同的策略進行交叉和變異操作；文獻[2]在基本遺傳算法基礎(chǔ)上引入外部最優(yōu)個體集，以增加群體多樣性，改善局部搜索能力，采用遞歸分治策略將遺傳算法并行化；文獻[3]采用改進的遺傳算法，按種群中個體適應(yīng)度高低采用不同的交叉和變異算子；文獻[4]提出一種改進的遺傳算法，動態(tài)調(diào)整交叉和變異概率，以降低染色體近親繁殖可能，有效控制了進化過程；文獻[5]結(jié)合遺傳算法和模擬退火算法，提出了一種改進的模擬退火遺傳算法；文獻[6]將蟻群算法和遺傳算法融合，經(jīng)過蟻群算法迭代獲得初始種群解集，再采用改進的遺傳算法尋優(yōu)；文獻[7]在基本遺傳算法基礎(chǔ)上，提出改進型多宇宙量子交叉算子，利用不同宇宙間的信息交流提高算法的搜索效率。

上述求解TSP問題的研究效果很好，但都沒有提到有關(guān)求解系統(tǒng)的設(shè)計問題。本文不但對基本遺傳算法求解TSP問題進行分析并加以改進，還給出了求解TSP問題系統(tǒng)的體系結(jié)構(gòu)。實驗結(jié)果表明，改進的遺傳算法具有更可靠的尋優(yōu)能力，求解系統(tǒng)實用性較好。

1 基本問題描述

1.1 TSP問題

TSP問題可描述為：一個旅行商要到n個城市推銷商品，從一個城市出發(fā)，走一遍余下的n-1個城市再回到起點，要求所走的路程最短，即尋找一條巡回路徑C=（c1，c2，...，cn），使得下列目標(biāo)函數(shù)最小[8]：

1.2 遺傳算法原理及應(yīng)用

遺傳算法是一種隨機并行搜索算法，其基本思想是：首先對個體編碼，生成初始種群，然后開始進化，用適應(yīng)度函數(shù)來判斷個體優(yōu)劣，優(yōu)秀的個體將獲得更多的選擇、交叉和變異機會，一直進化到滿足迭代的終止條件，從而得到最優(yōu)解。該算法具有全局尋優(yōu)能力強、計算過程簡單、處理并行性、魯棒性等優(yōu)點，在組合優(yōu)化問題、模式識別、圖像處理、調(diào)度問題等領(lǐng)域得到了廣泛應(yīng)用[9]。

2 應(yīng)用遺傳算法求解TSP問題

遺傳算法已經(jīng)廣泛應(yīng)用于求解組合化問題的近似最優(yōu)解方面，TSP問題是典型的組合優(yōu)化問題。應(yīng)用遺傳算法求解TSP問題基本方法如下：（1）確定編碼方式。用遺傳算法求解TSP問題常用的編碼方式有二進制表示、順序表示、路徑表示、邊表示等，其中路徑表示因自然、直觀且易于加入啟發(fā)式信息，是應(yīng)用最多的一種表示策略。（2）初始化種群。隨機產(chǎn)生初始個體，構(gòu)成指定規(guī)模的初始種群，是應(yīng)用遺傳算法求解TSP問題的常用方法。（3）計算種群中每個個體的適應(yīng)度值。在TSP問題中，目標(biāo)函數(shù)f（C）=∑n-1i=1d（ci，ci+1）+d（cn，c1）是路徑總長度，適應(yīng)度函數(shù)通常取目標(biāo)函數(shù)的倒數(shù)，即F（C）=1/f（C）。（4）選擇算子。目前常用的選擇算子有比例選擇、最優(yōu)保存策略、基于聯(lián)賽的選擇等。（5）交叉算子。按照某一交叉概率pc選擇若干父體并進行配對。針對路徑表示的TSP遺傳算法，常用的交叉算子有部分匹配交叉、貪婪交叉、次序交叉和循環(huán)交叉等。（6）變異算子。按照某一變異概率pm隨機確定變異個體，常用的變異算子包括倒位變異、插入變異、移位變異和2-opt變異等。（7）迭代終止條件。若算法滿足迭代的終止條件，則停止迭代；否則轉(zhuǎn)至第（3）步，利用適應(yīng)度函數(shù)重新計算每個個體的適應(yīng)度值?；具z傳算法存在易陷入局部最優(yōu)、收斂速度慢和優(yōu)化精度低等缺點。改進遺傳算法的目標(biāo)是在提高算法收斂速度的同時確保種群多樣性，從而使尋優(yōu)結(jié)果接近最優(yōu)解[10]。

3 求解TSP問題的改進遺傳算法

3.1 個體路徑編碼表示

路徑表示法是TSP問題最直接的表示方法，本文算法采用此方法進行個體編碼，每個個體就是一次訪問城市的順序排列。編碼串（x1，x2，...，xn）表示從城市x1出發(fā)，依次經(jīng)過城市x2，x3，...，xn，最后回到x1。

3.2 貪心算法優(yōu)化初始種群

針對n個城市的TSP問題，假定種群規(guī)模為N，其中N*0.3個初始個體由貪心算法生成，N*0.7個初始個體隨機產(chǎn)生。N*0.3個初始個體中，每個個體生成的基本思想是：首先隨機地從n個城市中選取一個城市ccurrent作為第1個基因，然后從余下的n-1個城市中找到城市cnext（cnext是距離ccurrent最近的城市）作為第2個基因，再從余下的n-2個城市中找到城市cnext+1（cnext+1是距離cnext最近的城市）作為第3個基因，依次類推，直到遍歷n個城市為止。貪心算法生成的部分種群占比不大，在提高初始種群整體質(zhì)量的同時，不會影響初始種群的多樣性，有助于加速尋優(yōu)速度[11]。

3.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)通常直接由目標(biāo)函數(shù)得出，本文用目標(biāo)函數(shù)的倒數(shù)來表示適應(yīng)度函數(shù)。實際情況中，多個城市間的路徑長度∑n-1i=1d（ci，ci+1）+d（cn，c1）會比較大，倒數(shù)后數(shù)據(jù)將會有3～5位小數(shù)，不利于計算，所以將適應(yīng)度值放大D倍（D∈[10000，1000000]為常量），即適應(yīng)度函數(shù)表達式為：F（C）=D/f（C），其中f（C）為公式（1）表示的目標(biāo)函數(shù)。

3.4 選擇算子

本文改進的選擇算子是基于輪盤賭選擇，融入最優(yōu)保存策略和摻雜算子。最優(yōu)保存策略是直接復(fù)制群體中適應(yīng)度最高的個體到下一代，即個體不進行交叉、變異等操作[11]。摻雜算子是指在每代種群中隨機產(chǎn)生不大于N*0.1（N為種群規(guī)模）個新個體參與遺傳操作[12]。通過改進的選擇算子，在保留最優(yōu)個體的同時引入新個體，提高了算法收斂于全局最優(yōu)的可能性。

3.5 交叉算子

基本遺傳算法常用的雙點交叉算子，是指在要配對的兩個個體中隨機選擇兩個交叉點，將介于兩點之間的部分基因進行交換，對交換后兩點區(qū)域外出現(xiàn)的重復(fù)節(jié)點，按照原有位置對應(yīng)關(guān)系進行替換，從而得到兩個新染色體。這種交叉方式只是對父個體兩點之間的基因進行交叉，兩點區(qū)域外的基因要么不變，要么由于節(jié)點重復(fù)而盲目地改變，父個體的優(yōu)良基因得不到有效繼承。在兩點交叉基礎(chǔ)上，本文改進的交叉算子采用兩點三段隨機交叉，基本思想是對相互配對的父個體P1、P2隨機產(chǎn)生兩個交叉點，將父個體分成三段，再隨機產(chǎn)生一個介于0～2之間的整數(shù)X，X∪{0，1，2}，交叉操作按照公式（2）進行。

P1，P2前半部分進行交叉，X=0P1，P2中間部分進行交叉，X=1P1，P2后半部分進行交叉，X=2 （2）

假設(shè)父個體為P1=5714236，P2=1435726，交叉過程為：（1）隨機選擇兩個交叉點。假設(shè)P1=57|142|36，P2=14|357|26。（2）確定交叉區(qū)域。假設(shè)X=1，根據(jù)公式（2）中間部分進行交叉。

（3）將P2的中間部分加到P1前面，P1的中間部分加到P2前面，即得到P′1=3575714236，P′2=1421435726。

（4）刪除重復(fù)節(jié)點。P′1的重復(fù)節(jié)點為3、5、7，對于節(jié)點3，比較2-3-6和6-3-5之間的路程d（2-3-6）和d（6-3-5），如果d（2-3-6） >d （6-3-5），就刪除P′1后面的3，否則刪除前面的3。以同樣的方法處理P′1節(jié)點5和7，以及P′2的重復(fù)節(jié)點1、4、2。重復(fù)節(jié)點刪除完成后，得到交叉后的新個體P*1和P*2。改進的交叉算子克服了傳統(tǒng)兩點交叉中父個體兩端的基因要么不改變，要么由于節(jié)點重復(fù)而被盲目改變的缺陷，染色體變化能力得到提高，保證了種群多樣性，同時通過重復(fù)節(jié)點鄰接路徑長度比較，將路程長的重復(fù)節(jié)點刪除，提高了個體質(zhì)量和算法的收斂性。

3.6 變異算子

倒位變異算子是指在父個體中隨機順序地選取兩個城市并記為c*和c#，使c*和c#之間的編碼倒序排列，并將c*和c#相鄰排列，產(chǎn)生一個新個體[13-14]。假設(shè)有父個體P=1 732 564，隨機選擇的兩城市為3和6，則產(chǎn)生的新個體P*=1 736 524。本文改進的變異算子采用啟發(fā)式倒位變異算子，其基本思想是：首先隨機選擇一個城市c，除去c、cRight、cLeft節(jié)點，在剩余節(jié)點中選擇距離c最近的城市c′，再將cRight到c′之間的城市編碼倒位產(chǎn)生新個體。例如上述父個體P=1732564，隨機選擇一個城市7，城市2和4是離城市7最近的兩個城市，若c′選城市2，則倒位后產(chǎn)生的新個體P*=1723564，若c′選城市4，則倒位后產(chǎn)生的新個體P*=1746523。

3.7 改進的遺傳算法流程

為了更加清晰地表述本文提出的算法求解TSP問題流程，用圖1所示流程圖來描述算法。

4 TSP問題求解系統(tǒng)體系結(jié)構(gòu)

求解TSP問題系統(tǒng)包括界面模塊和改進遺傳算法應(yīng)用模塊，系統(tǒng)體系結(jié)構(gòu)如圖2所示。

界面模塊主要由城市布局選擇和優(yōu)化結(jié)果顯示兩部分組成。本文提出的改進遺傳算法用改進遺傳算法應(yīng)用模塊來實現(xiàn)，此模塊主要由路徑編碼、貪心優(yōu)化初始種群、適應(yīng)度函數(shù)、最優(yōu)保存策略和摻雜算子選擇、兩點三段隨機交叉算子和啟發(fā)式倒位變異算子實現(xiàn)等幾部分組成。

5 實驗及結(jié)果分析

依據(jù)標(biāo)準(zhǔn)的CHN144城市坐標(biāo)數(shù)據(jù)，分別用基本遺傳算法（SGA）和本文改進的遺傳算法（IGA）對CHN144中的城市進行20次隨機實驗。采用C語言編程，實驗控制參數(shù)設(shè)置如下：種群規(guī)模N=150，交叉概率pc=0.9，變異概率pm=0.2，終止條件中最優(yōu)個體保持代數(shù)M=200，實驗結(jié)果見表1。

實驗結(jié)果表明，本文IGA算法在收斂性上要明顯好于SGA算法，且IGA算法的最優(yōu)解和平均解都優(yōu)于SGA算法，進一步說明了用貪心算法優(yōu)化初始種群和用最優(yōu)保存策略及在選擇操作中引入摻雜算子，在利用局部尋優(yōu)能力改善種群質(zhì)量、加速尋優(yōu)速度、提高算法搜索效率方面有著重要作用。IGA算法采用的兩點三段隨機交叉操作及啟發(fā)式倒位變異操作，較好解決了群體多樣性和收斂速度的矛盾，使算法具有較強的魯棒性。

6 結(jié)語

TSP問題是計算機、物流等領(lǐng)域許多復(fù)雜問題的抽象模型，具有良好的應(yīng)用前景，對TSP問題進行研究具有重要意義。本文針對TSP問題提出了改進的遺傳算法，并給出了求解系統(tǒng)的體系結(jié)構(gòu)。仿真實驗表明，對144個城市求解TSP問題得到的結(jié)果優(yōu)于基本遺傳算法。本文改進的遺傳算法可應(yīng)用于任何類型的優(yōu)化操作中，通用性好、實用價值高。

參考文獻：

[1] 晏雨.改進的遺傳算法和分布估計算法求解TSP問題[D].重慶：重慶理工大學(xué)，2013.

[2] 王建忠，唐紅.TSP問題的一種快速求解算法[J].微電子學(xué)與計算機，2011，28（1）：7-10.

[3] 張芳琴.改進遺傳算法在TSP組合優(yōu)化問題中的應(yīng)用[J].高師理科學(xué)刊，2014，34（5）：1-4.

[4] 姜群，晏雨.改進的遺傳算法在TSP問題中的應(yīng)用[J].重慶理工大學(xué)學(xué)報：自然科學(xué)版，2012，26（9）：96-99.

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

[6] 于瑩瑩，陳燕，李桃迎.改進的蟻群遺傳算法求解旅行商問題[J].計算機仿真，2013，30（11）：317-320.

[7] 楊玉，李慧，戴紅偉.改進量子交叉遺傳算法在TSP問題中的應(yīng)用[J].南京師范大學(xué)學(xué)報：工程技術(shù)版，2012，12（3）：43-48.

[8] 候建花.TSP遺傳算法的改進及其并行化研究[D].成都：成都理工大學(xué)，2004.

[9] 蔣然，張光桃.基于預(yù)分類的逆變異分類器算法[J].軟件， 2015， 36（2）： 39-44.

[10] 于瑩瑩，陳燕，李桃迎.改進的遺傳算法求解旅行商問題[J].控制與決策，2014，29（8）：1483-1488.

[11] 周澤巖，張喜.基于改進遺傳算法的TSP問題求解的研究[J].物流技術(shù)，2012，31（9）：220-223.

[12] 陳智軍.一種改進的求解TSP問題的遺傳算法[J].軟件導(dǎo)刊，2011，10（2）：52-54.

[13] 謝勝利，唐敏，董金祥.求解TSP問題的一種改進的遺傳算法[J].計算機工程與應(yīng)用，2002（8）：58-60，245.

[14] 杜宗宗.基于遺傳算法的移動機器人路徑規(guī)劃研究[D].無錫：江南大學(xué)，2009.

（責(zé)任編輯：杜能鋼）