張雁翔，祁育仙

(太原理工大學(xué)信息化管理與建設(shè)中心，山西太原 030024)

?

改進(jìn)遺傳算法求解TSP

張雁翔，祁育仙

(太原理工大學(xué)信息化管理與建設(shè)中心，山西太原 030024)

摘要：針對(duì)遺傳算法收斂速度慢、易陷入早熟的問(wèn)題提出一種改進(jìn)的遺傳算法。在傳統(tǒng)遺傳算法基礎(chǔ)上，引入最近插入法產(chǎn)生高性能的初始種群；選擇操作中加入精英保留策略，保證收斂到全局最優(yōu)；根據(jù)種群進(jìn)化狀況自適應(yīng)調(diào)整交叉概率、變異概率，克服過(guò)早收斂并加快收斂速度；在選擇、交叉、變異之后加入進(jìn)化逆轉(zhuǎn)操作，保留親代較多信息，增強(qiáng)搜索能力；提出一種新的遺傳終止規(guī)則，提高遺傳算法的有效性。經(jīng)過(guò)國(guó)際公認(rèn)的TSPLIB實(shí)驗(yàn)數(shù)據(jù)仿真驗(yàn)證，改進(jìn)后的遺傳算法精確性、有效性和收斂速度均有明顯提高。

關(guān)鍵詞：旅行商問(wèn)題；遺傳算法；最近插入法

旅行商問(wèn)題(traveling salesman problem，TSP)又稱(chēng)為旅行推銷(xiāo)員問(wèn)題、貨郎擔(dān)問(wèn)題，是最著名的NP完全問(wèn)題。TSP并不僅僅是旅行商問(wèn)題，且涉足眾多領(lǐng)域，應(yīng)用十分廣泛，如郵路問(wèn)題、基因組圖譜繪制問(wèn)題和產(chǎn)品的生產(chǎn)安排問(wèn)題等，因此TSP的有效求解具有重要的意義。

目前，人工智能發(fā)展迅速，出現(xiàn)了許多獨(dú)立于問(wèn)題的智能優(yōu)化算法。文獻(xiàn)[1]討論了蟻群算法、遺傳算法、模擬退火算法、禁忌搜索算法、粒子群優(yōu)化算法等求解TSP的優(yōu)缺點(diǎn)及研究進(jìn)程；文獻(xiàn)[2]利用貪心策略指導(dǎo)遺傳操作，提出了貪心遺傳算法，保證算法的有效性；文獻(xiàn)[3]將單親遺傳算法與模擬退火算法相結(jié)合，提高全局尋優(yōu)能力。

本文對(duì)基本遺傳算法(Simple Genetic Algorithm，SGA)求解TSP問(wèn)題進(jìn)行改進(jìn)，實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的遺傳算法具有較高的精確性且收斂速度快。

1基本問(wèn)題描述

1.1TSP問(wèn)題描述

TSP可描述為：已知n個(gè)城市以及他們相互之間的距離，求出某一旅行商經(jīng)過(guò)所有城市并回到出發(fā)點(diǎn)的最短路線(xiàn)[4]。簡(jiǎn)言之，就是搜索自然子集X={1,2,…,n}(X的元素對(duì)n個(gè)城市的編號(hào))的一個(gè)排列π(X)={V1,V2,…,Vn}，使

取最小值，其中d(Vi，Vi+1)表示城市Vi到城市Vi+1的距離。

1.2遺傳算法描述

遺傳算法(genetic algorithm，GA) 靈感來(lái)源于John Holland《自然系統(tǒng)與人工系統(tǒng)中的適應(yīng)性》，其實(shí)質(zhì)是模擬自然界的進(jìn)化過(guò)程，將自然界適者生存規(guī)則與種群內(nèi)部染色體的隨機(jī)信息交換機(jī)制相結(jié)合，是高度并行、隨機(jī)、自適應(yīng)的全局尋優(yōu)搜索算法[5]，具有很強(qiáng)的魯棒性和全局搜索能力，易于其他算法相結(jié)合。目前，遺傳算法已被廣泛應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制等領(lǐng)域，并取得了良好的成果。

1.3基本遺傳算法求解TSP步驟

SGA是把問(wèn)題參數(shù)編碼為染色體，利用迭代方式進(jìn)行選擇、交叉、變異等操作逐步交換染色體信息，不斷得到更優(yōu)的群體，同時(shí)以全局并行搜索方式搜索優(yōu)化群體中的最優(yōu)個(gè)體，求得滿(mǎn)足要求的最優(yōu)解。其求解TSP基本步驟為：

1) 確定編碼機(jī)制，初始化種群，解決TSP問(wèn)題時(shí)通常采用整數(shù)編碼，及使用城市序號(hào)編碼，例如，1|3|5|4|2代表對(duì)于5個(gè)城市TSP問(wèn)題的一個(gè)合法染色體。初始化種群采用隨機(jī)法生成目標(biāo)種群。

2) 計(jì)算適應(yīng)度值，設(shè)n個(gè)城市的一個(gè)合法染色體為k1|k2|…|ki|kn，則該個(gè)體的適應(yīng)度值為：

其中Dkikj為城市ki到kj的距離。

即此適應(yīng)度函數(shù)為旅行者按照規(guī)定的路線(xiàn)走完所有路程的距離的倒數(shù)。優(yōu)化的目標(biāo)是所走路程距離最短，即該適應(yīng)度函數(shù)越大，所選染色體越優(yōu)質(zhì)，反之越劣質(zhì)。

4) 交叉操作，使用單點(diǎn)交叉算子，任選兩個(gè)體作為交叉對(duì)象，隨機(jī)產(chǎn)生一個(gè)交叉點(diǎn)，兩個(gè)體在交叉點(diǎn)互換交叉對(duì)象，采用部分映射消除沖突數(shù)字，交叉概率為Pc。

5) 變異操作，變異策略為隨機(jī)選取兩個(gè)點(diǎn)，互換位置。變異概率Pm同生物界一樣，一般取值較小。

6) 迭代終止，循環(huán)進(jìn)行選擇、交叉、變異操作，若滿(mǎn)足最大遺傳代數(shù)則遺傳終止，得出最優(yōu)解。

SGA在進(jìn)化前期收斂速度快，但當(dāng)達(dá)到最優(yōu)解的90%時(shí)，進(jìn)化停滯，無(wú)法跳出局部最優(yōu)，容易出現(xiàn)早熟收斂現(xiàn)象。為了提高搜索能力，克服早熟收斂，加快收斂速度，需要對(duì)算法進(jìn)行改進(jìn)。

2改進(jìn)遺傳算法

2.1最近插入法產(chǎn)生初始種群

GA涉及的染色體大都來(lái)源于初始種群，種群個(gè)體的質(zhì)量影響全局性能，SGA隨機(jī)生成初始種群，適應(yīng)度值普遍偏低，算法效率低。本文采用最近插入法產(chǎn)生初始種群，使種群個(gè)體在初始時(shí)保持較高的適應(yīng)度值，提高收斂速度。最近插入法過(guò)程如下：

1) 隨機(jī)選擇一個(gè)城市為當(dāng)前城市，在剩余城市中選擇距離當(dāng)前城市最近的一個(gè)城市與之構(gòu)成子路線(xiàn)。

2) 比較所有剩余城市到當(dāng)前子路線(xiàn)上每一座城市的距離，選擇距離子路線(xiàn)某一城市相距最近的一個(gè)城市插入子路線(xiàn)。

3) 反復(fù)操作步驟2)，最終將所有城市均插入子路線(xiàn)構(gòu)成一個(gè)完整的路線(xiàn)，表示此路線(xiàn)的一個(gè)染色體就是種群中的一個(gè)個(gè)體。

2.2選擇操作精英保留策略

在選擇操作中加入精英保留策略，即在使用變異、交叉算子之前先選出適應(yīng)度值最大的個(gè)體保存在最優(yōu)解集中，替換子代中適應(yīng)度最差的個(gè)體。目的是保留最好的個(gè)體，避免交叉、變異算子破壞其優(yōu)良性，這樣使得親代的好的個(gè)體不至于由于交叉或者變異操作而丟失，子代種群中的最優(yōu)個(gè)體永遠(yuǎn)不會(huì)比親代最優(yōu)的個(gè)體差。保證了種群的全局最優(yōu)性。

2.3交叉、變異策略的自適應(yīng)

SGA中交叉概率Pc和變異概率Pm是不變的，導(dǎo)致后期搜索遲鈍，進(jìn)化停滯，自適應(yīng)控制可以有效地改善后期收斂速度，在進(jìn)化過(guò)程中自適應(yīng)的改變Pc、Pm的大小，將進(jìn)化過(guò)程分為漸進(jìn)和突變兩個(gè)不同的階段：漸進(jìn)階段強(qiáng)交叉、弱變異，擴(kuò)大整體搜索范圍，突變階段弱交叉、強(qiáng)變異，使優(yōu)良基因結(jié)構(gòu)得以保存，且防止陷入局部最優(yōu)，自適應(yīng)調(diào)節(jié)公式為：

式中，fi為個(gè)體i的適應(yīng)度值，favg和fmax分別為當(dāng)前種群所有個(gè)體的平均適應(yīng)度值和最大適應(yīng)度值，pc1=0.9，pm1=0.001。

2.4進(jìn)化逆轉(zhuǎn)操作

TSP的關(guān)鍵是碼串的順序，交叉算子和變異算子會(huì)使子代維持種群的多樣性，但是難以繼承親代較多的優(yōu)良基因，在選擇、交叉、變異之后引進(jìn)進(jìn)化逆轉(zhuǎn)操作可以改善GA的局部搜索能力。本文的逆轉(zhuǎn)算子是單方向性(朝著好的進(jìn)化方向)的，只有經(jīng)逆轉(zhuǎn)后，適應(yīng)度值有提高的才會(huì)保留下來(lái)，否則逆轉(zhuǎn)無(wú)效。

例如：隨機(jī)選取兩個(gè)[1，9]區(qū)間內(nèi)的整數(shù)r1和r2，確定兩個(gè)斷裂點(diǎn)，將兩斷裂點(diǎn)內(nèi)數(shù)據(jù)進(jìn)行逆轉(zhuǎn)，如，r1=3，r2=7

53∣6724∣198

逆轉(zhuǎn)后為：

53∣4276∣198

2.5遺傳迭代終止規(guī)則

在SGA中，當(dāng)?shù)磷畲筮z傳代數(shù)時(shí)迭代終止，由此得出的進(jìn)化過(guò)程會(huì)由于最大遺傳代數(shù)選擇的不合適使進(jìn)化后期進(jìn)行不必要的循環(huán)迭代，出現(xiàn)進(jìn)化停滯。為了避免此現(xiàn)象，本文提出一種新的終止規(guī)則。

本文規(guī)定，若連續(xù)Q代內(nèi)都滿(mǎn)足條件|fgmax-f(g-1)max|≤ε，其中ε為適當(dāng)小的正數(shù)，fgmax為第g代種群內(nèi)個(gè)體的最大適應(yīng)度值，f(g-1)max為第g-1代種群內(nèi)個(gè)體的最大適應(yīng)度值。

2.6改進(jìn)遺傳算法基本流程

改進(jìn)后遺傳算法求解TSP流程圖如圖1所示?；玖鞒虨椋?/p>

Step1：種群初始化；

Step2：對(duì)種群各個(gè)體進(jìn)行適應(yīng)度值計(jì)算，循環(huán)進(jìn)行選擇、交叉、變異和進(jìn)化逆轉(zhuǎn)操作，直至達(dá)到終止條件。

圖1　改進(jìn)遺傳算法流程圖

選擇算子：采用隨機(jī)遍歷抽樣選擇，選擇時(shí)采用隨機(jī)等距的方式選擇個(gè)體。

交叉算子：采用部分映射雜交，根據(jù)當(dāng)前進(jìn)化情況自適應(yīng)調(diào)整交叉概率。

變異算子：隨機(jī)選取兩個(gè)點(diǎn)，將其對(duì)換位置。根據(jù)當(dāng)前進(jìn)化情況自適應(yīng)調(diào)整變異概率。

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

本文采用MATLAB語(yǔ)言對(duì)改進(jìn)遺傳算法設(shè)計(jì)實(shí)現(xiàn)。并用TSP樣本案例庫(kù)TSPLIB中的部分?jǐn)?shù)據(jù)進(jìn)行仿真分析。實(shí)驗(yàn)環(huán)境為：windows 7系統(tǒng)，2G內(nèi)存，Matlab R2010b平臺(tái)。

分別使用改進(jìn)GA和SGA對(duì)國(guó)際公認(rèn)的TSPLIB實(shí)驗(yàn)數(shù)據(jù)仿真驗(yàn)證后，得出實(shí)驗(yàn)結(jié)果對(duì)比如表1，可以得出，改進(jìn)后的遺傳算法相對(duì)于SGA不僅可以搜索到最優(yōu)解，而且收斂到最優(yōu)解的速度也較快，有效性高，SGA容易陷入局部最優(yōu)，如pr136。

表1　實(shí)驗(yàn)結(jié)果對(duì)比分析

改進(jìn)的GA可以產(chǎn)生高性能的初始種群，且可以在較短的代數(shù)內(nèi)收斂至全局最優(yōu)，當(dāng)進(jìn)化停滯時(shí)，新的終止條件可以避免算法進(jìn)行無(wú)效的進(jìn)化，提高有效性，如圖2所示。

圖2　pr136改進(jìn)GA和SGA進(jìn)化曲線(xiàn)

采用改進(jìn)GA對(duì)TSPLIB中部分?jǐn)?shù)據(jù)進(jìn)行仿真得出各數(shù)據(jù)最優(yōu)路線(xiàn)圖如圖3至圖5。

圖3　chn31最優(yōu)路線(xiàn)軌跡圖

圖4　eil76最優(yōu)路線(xiàn)軌跡圖

圖5　tsp225最優(yōu)路線(xiàn)軌跡圖

4結(jié)束語(yǔ)

本文對(duì)傳統(tǒng)的遺傳算法進(jìn)行了改進(jìn)，使用最近插入法生成部分初始種群；加入精英保留策略，自適應(yīng)調(diào)整交叉、變異概率，加入了進(jìn)化逆轉(zhuǎn)算子；提出了一種新的遺傳終止條件。通過(guò)實(shí)驗(yàn)仿真顯示，改進(jìn)遺傳算法在搜索最優(yōu)能力、有效性和收斂速度方面都有明顯的提高。

參考文獻(xiàn)

[1]高海昌，馮博琴，朱利.智能優(yōu)化算法求解TSP問(wèn)題[J].控制與決策,2006,21(3):241-247.

[2]魏英姿，趙明揚(yáng)，黃雪梅，等.求解TS問(wèn)題的貪心遺傳算法[J].計(jì)算機(jī)工程,2004,30(19):19-20.

[3]曹恒智，余先川.單親遺傳模擬退火及在組合優(yōu)化問(wèn)題中的應(yīng)用[J].北京郵電大學(xué)學(xué)報(bào),2008,31(3):38-41.

[4]William J,Cook.Traveling Salesman:Mathematics at the Limits of Computation[M].隋春寧,譯.北京:人民郵電出版社,2013:10.

[5]劉荷花，崔超，陳晶.一種改進(jìn)的遺傳算法求解旅行商問(wèn)題[D].北京理工大學(xué)學(xué)報(bào),2013,33(4):390-393.

An Improved Genetic Algorithm for Solving TSP

Zhang Yanxiang, Qi Yuxian

(CenterofInformationManagementandDevelopment,TaiyuanUniversityofTechnology,TaiyuanShanxi030024,China)

Abstract:For the problem of slow convergence speed and easy to fall into precocity with genetic algorithm, an improved genetic algorithm is proposed. Based on simple genetic algorithm, the paper obtains the high-performance initial population with nearest insertion heuristic algorithm, introduces elitism in selection operation to globally optimal solution, adjusts the crossover and mutation probability adaptively according to the evolution situation to overcome the premature convergence and accelerate the convergence speed, performs the reverse evolution after selection, crosser and mutation operation which can keep more parental information and enhance search capabilities. A new genetic termination rules is built in order to increase the effectiveness of genetic algorithm. Through the TSPLIB experimental data simulation, the improved genetic algorithm is improved obviously on accuracy, validity and convergence speed.

Key words:travelling salesman problem (TSP); genetic algorithm; nearest insertion

中圖分類(lèi)號(hào)：TP183

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1674- 4578(2016)01- 0028- 03

作者簡(jiǎn)介：張雁翔(1976- )，女，山西長(zhǎng)治人，工程師，碩士。

收稿日期：2015-10-29