改進遺傳算法求解TSP

張雁翔，祁育仙

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

?

改進遺傳算法求解TSP

張雁翔，祁育仙

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

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

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

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

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

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

1基本問題描述

1.1TSP問題描述

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

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

1.2遺傳算法描述

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

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

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

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

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

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

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

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

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

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

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

2改進遺傳算法

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

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

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

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

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

2.2選擇操作精英保留策略

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

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

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

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

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

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

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

53∣6724∣198

逆轉(zhuǎn)后為：

53∣4276∣198

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

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

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

2.6改進遺傳算法基本流程

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

Step1：種群初始化；

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

圖1　改進遺傳算法流程圖

選擇算子：采用隨機遍歷抽樣選擇，選擇時采用隨機等距的方式選擇個體。

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

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

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

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

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

表1　實驗結(jié)果對比分析

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

圖2　pr136改進GA和SGA進化曲線

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

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

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

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

4結(jié)束語

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

參考文獻

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

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

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

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

[5]劉荷花，崔超，陳晶.一種改進的遺傳算法求解旅行商問題[D].北京理工大學(xué)學(xué)報,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

中圖分類號：TP183

文獻標(biāo)識碼：A

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

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

收稿日期：2015-10-29