改進(jìn)遺傳算法在TSP問題中的應(yīng)用

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

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

DOIDOI：10.11907/rjdk.162168

中圖分類號(hào)：TP319

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

0 引言

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

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

1 基本問題描述

1.1 TSP問題

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

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

遺傳算法是一種隨機(jī)并行搜索算法，其基本思想是：首先對(duì)個(gè)體編碼，生成初始種群，然后開始進(jìn)化，用適應(yīng)度函數(shù)來判斷個(gè)體優(yōu)劣，優(yōu)秀的個(gè)體將獲得更多的選擇、交叉和變異機(jī)會(huì)，一直進(jìn)化到滿足迭代的終止條件，從而得到最優(yōu)解。該算法具有全局尋優(yōu)能力強(qiáng)、計(jì)算過程簡(jiǎn)單、處理并行性、魯棒性等優(yōu)點(diǎn)，在組合優(yōu)化問題、模式識(shí)別、圖像處理、調(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問題常用的編碼方式有二進(jìn)制表示、順序表示、路徑表示、邊表示等，其中路徑表示因自然、直觀且易于加入啟發(fā)式信息，是應(yīng)用最多的一種表示策略。（2）初始化種群。隨機(jī)產(chǎn)生初始個(gè)體，構(gòu)成指定規(guī)模的初始種群，是應(yīng)用遺傳算法求解TSP問題的常用方法。（3）計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度值。在TSP問題中，目標(biāo)函數(shù)f（C）=∑n-1i=1d（ci，ci+1）+d（cn，c1）是路徑總長(zhǎng)度，適應(yīng)度函數(shù)通常取目標(biāo)函數(shù)的倒數(shù)，即F（C）=1/f（C）。（4）選擇算子。目前常用的選擇算子有比例選擇、最優(yōu)保存策略、基于聯(lián)賽的選擇等。（5）交叉算子。按照某一交叉概率pc選擇若干父體并進(jìn)行配對(duì)。針對(duì)路徑表示的TSP遺傳算法，常用的交叉算子有部分匹配交叉、貪婪交叉、次序交叉和循環(huán)交叉等。（6）變異算子。按照某一變異概率pm隨機(jī)確定變異個(gè)體，常用的變異算子包括倒位變異、插入變異、移位變異和2-opt變異等。（7）迭代終止條件。若算法滿足迭代的終止條件，則停止迭代；否則轉(zhuǎn)至第（3）步，利用適應(yīng)度函數(shù)重新計(jì)算每個(gè)個(gè)體的適應(yīng)度值?；具z傳算法存在易陷入局部最優(yōu)、收斂速度慢和優(yōu)化精度低等缺點(diǎn)。改進(jìn)遺傳算法的目標(biāo)是在提高算法收斂速度的同時(shí)確保種群多樣性，從而使尋優(yōu)結(jié)果接近最優(yōu)解[10]。

3 求解TSP問題的改進(jìn)遺傳算法

3.1 個(gè)體路徑編碼表示

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

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

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

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

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

3.4 選擇算子

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

3.5 交叉算子

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

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

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

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

（4）刪除重復(fù)節(jié)點(diǎn)。P′1的重復(fù)節(jié)點(diǎn)為3、5、7，對(duì)于節(jié)點(diǎn)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é)點(diǎn)5和7，以及P′2的重復(fù)節(jié)點(diǎn)1、4、2。重復(fù)節(jié)點(diǎn)刪除完成后，得到交叉后的新個(gè)體P*1和P*2。改進(jìn)的交叉算子克服了傳統(tǒng)兩點(diǎn)交叉中父?jìng)€(gè)體兩端的基因要么不改變，要么由于節(jié)點(diǎn)重復(fù)而被盲目改變的缺陷，染色體變化能力得到提高，保證了種群多樣性，同時(shí)通過重復(fù)節(jié)點(diǎn)鄰接路徑長(zhǎng)度比較，將路程長(zhǎng)的重復(fù)節(jié)點(diǎn)刪除，提高了個(gè)體質(zhì)量和算法的收斂性。

3.6 變異算子

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

3.7 改進(jìn)的遺傳算法流程

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

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

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

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

5 實(shí)驗(yàn)及結(jié)果分析

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

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

6 結(jié)語

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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