改進型遺傳算法求解TSP問題

石利平

(廣東女子職業技術學院 應用設計系,廣東 廣州 511450)

旅行商問題(traveling salesman problem,TSP)[1]又譯為貨郎擔問題，是求解一個閉合的最短路徑問題。TSP問題可描述為單一旅行商由一個城市出發，通過給定的要去n個城市，已知各城市間的路程，路經每個城市僅1次，最后返回起始城市的最小路徑問題，TSP是NP-Complete問題。生活中的車輛調度、生產線上螺母、城市管道鋪設優化等優化問題，均屬于TSP最短路徑問題，研究如何求解TSP最優問題有著重要的實際意義。

遺傳算法(genetic algorithm，GA)是一種著名的智能優化算法，是現代人工智能領域中的關鍵技術，大量科學實踐也證明遺傳算法在求解TSP問題方面具有比較高的尋優能力[2]。遺傳算法全局尋優能力較強，使用較簡單，采用概率化的搜索技術，搜索方向可以自適應地調整，能自動選擇優化的搜索空間。但是遺傳算法局部搜索能力較差，易出現早收斂和局部最小等問題[3]。本文提出一種基于精英保留選擇策略和自適應選擇變異算子，在選擇、交叉、變異后再引入單向進化逆轉操作的改進的遺傳算法，提高遺傳算法的搜索和求解性能。

1 TSP問題描述

2 標準遺傳算法

1975年遺傳算法[3-4]由美國教授Holland提出。遺傳算法是模擬“物競天擇，適者生存”以及基因遺傳學的生物進化過程的隨機化搜索方法。遺傳算法是以種群個體適應度函數值作為搜索信息，搜索范圍為種群所有的個體。

標準遺傳算法(SGA)其基本流程[2-9]如下：首先構建初始種群，種群由一定數量的所求問題可能解個體組成，然后計算種群各個個體適應度函數值，經過遺傳算法的3種重要操作算子選擇、交叉和變異的多次處理，最終求出最優解。

3 改進的遺傳算法

3.1 編碼

本算法中采用整數排列編碼。在TSP優化問題中，有n座城市，各城市的編號分別為整數1，2，3，…，n，這樣一個染色體就由為n段組成。如TSP問題中有10個城市，那么{1，3，4，2，6，9，10，8，5，7}就是一個合法的染色體，也是一個可能的優化解。

3.2 初始化種群

3.3 適應度函數

種群個體進化后是不是較優秀的問題解，即看其適應性，測評的標準就是適應度函數的值。適應度函數的值是群體進化過程中個體優勝劣汰唯一依據。個體適應度函數值較大，則說明該個體生存競爭能力較強，被選擇進化的可能性高；反之，個體適應度函數值較小，則其個體生存能力較弱，在群體的進化中被淘汰的可能性高。適應度函數可以說是群體進化中的自然生存環境，是模擬生物界進化中優勝劣汰的自然選擇[10]。因此在遺傳算法中，如何合理設計適應度函數是非常重要的。本文中個體的適應度函數為

(1)

式中的D(Vi,Vi+1)表示城市Vi至城市Vi+1的距離,Ri表示第i條路徑。

該適應度函數值是恰好走完n座城市再回到起始城市的距離倒數。染色體優化的目標就是選取盡量大的適應度函數值，適應度函數值越大則染色體越優。

3.4 選擇操作

選擇操作是以一定的選擇概率從當前種群中選擇適應函數值高的生成的新個體，其主要目的盡量使優質基因遺傳給下一代,提高算法計算效率和全局收斂的概率。本文算法個體選擇概率計算方法如下：

對于給定的規模為n的群體Q(n)=(q1,q2,q3,…,qn)，個體qi的適應度函數值為F(qi)，其選擇概率為

(2)

本文算法在選擇操作中加入精英保留策略[6,11]：即為在每代種群中加入一個適應度值大的精英個體，此個體為目前種群最好的個體；種群個體經過變異、交叉進化，若進化后的新一代種群中最好個體優于精英個體，則用最好個體替換精英個體，否則保留此精英個體。這種選擇精英策略會保證父代種群中好的個體不會由于變異或交叉而丟失，子代種群中的最優個體永好于父代種群最優個體差。

3.5 交叉操作

交叉是很重要的操作算子，目的是將選擇得到的優質個體進行交叉得到更優質新個體。交叉概率取值范圍一般建議0.4～0.99[9]。

本文采用精英個體與選擇后得的新個體進行部分映射雜交操作，交叉的位置隨機產生，即隨機產生交叉區域。假設城市數為10，交叉操作算法如下：

(1) 選擇父代種群最優個體與一新個體；

(2) 隨機產生2個交叉位置n1和n2，n1∈[1,10],n2∈[1,10]，對這2個位置中間的數據進行交叉操作;

(3) 交叉后產生的新個體城市編號如有重復，采用部分映射方法消除重復，不重復的編號保留。

這種交叉方法可確保較大可能地保護好父代個體中的優質基因模式,從而使優質染色體遺傳到下一代當中,有利于提高遺傳算法的性能。

3.6 變異

變異操作是遺傳算法的重要操作之一，是將問題解編碼串中的某些位的編碼與該解中其他位編碼調換位置，形成一新個體。變異操作決定遺傳算法的局部搜索能力，維持群體的多樣性，避免早熟現象出現。遺傳算法中,常以變異概率Pm對個體基因進行突變來實現產生新個體。為確保種群進化的穩定性，變異概率一般取較小值。種群進化后期,群體最優個體的適應度值與種群平均適應度值很接近，此時個體基因塊也都非常相似，如果算法變異概率依然保持不變，那么遺傳進化過程中個體間競爭性就會大大減弱，種群個體進化速度降低，種群多樣性變弱，易造成局部收斂。為減少這種情況發生，本文采用一種自適應的變異概率[8-9]計算方法：

(3)

式3中Pm-max為最大變異概率,本文中取0.05；Pm-min為最小變異概率，這里取0.001，F為要變異個體的適應度，Fmax為種群中最大的適應度值，Favg為當前種群平均適應度值。

使用公式(3)選取變異概率時，當個體的適應度大于或等于此時種群的平均適應度時，該個體的變異概率就越小，則該個體發生變異的可能性越小，這樣可更好地保證適應度高的優質個體遺傳下去。當個體的適應度小于種群的平均適應度時，則其變異概率大，使其進化為優質個體可能性更大，這種思想與優勝劣汰的遺傳機制一致。

本文中變異操作是隨機產生2個變異位置n1和n2，n1∈[1,10]，n2∈[1,10]，將這2個位置對換，比如n1=3，n2=8,個體{1，3，4，2，6，9，10，8，5，7，}變異后得到新個體為{1，3，8，2，6，9，10，4，5，7}。

3.7 進化逆轉操作

進化逆轉操作能改善遺傳算法的局部搜索能力。在選擇、交叉、變異遺傳進化之后引入進化逆轉操作。逆轉算法如下：先隨機產生2個隨機整數n1和n2(n1∈[1,10]，n2∈[1,10])，確定2個位置，將TSP可能解路徑排列中對應的城市交換位置，假如n1=2，n2=5，逆轉后TSP環游路線排列{V1,V8,V6,V3,V2,V5,V7,V10,V4,V9}，計算新個體的適應度值，如其適應度值優于逆轉前的，則保留該新個體，否則保留原來個體。進化逆轉后，適應度值提高的個體才接受下來，否則保留原個體。本算法中逆轉是單方向的，只接受向好的適應度逆轉。設有10座城市，一個TSP可能解路徑排列為{V1,V2,V3,V6,V8,V5,V7,V10,V4,V9}。主要代碼如下：

SelPath=PathL(D,Selch) %計算被選個體的路徑長度，D為各城市的距離矩陣

InvCh=SelCh; % Selch是選擇要逆轉的個體

%InvCh是逆轉后的個體

for i=1:row

pos1=randsrc(1,1,[1:col]);

pos2=randsrc(1,1,[1:col]);

mininv=min([pos1 pos2]);

maxinv=max([pos1 pos2]);

InvCh(i,mininv:maxin)=InvCh(i,maxinv:-1:mininv);

end

InvPath=PathL(D,InvCh);%計算逆轉后路徑長度

index=InvPath

SelCh(index,:)= InvCh (index,:);

4 解決TSP問題優化的遺傳算法流程

改進的遺傳算法流程圖如圖1所示。

圖1 改進的遺傳算法流程圖

5 仿真實驗及結果

本文選用國際上通用的TSPLIB測試庫中數據的Barma14和Eli51數據進行測試。barma14數據的14個城市坐標如下：

(16.47,96.10),(16.47,94.44),(20.09,92.54),(22.39,93.37),( 25.23,97.24),(22.00,96.05),(20.47,97.02),(17.20,96.38),(16.30,97.38),(14.05,98.12),(16.53,97.38),( 21.52,95.59),(19.41,97.13),( 20.09,92.55)。

Eli5數據的51個城市坐標如下：

(37,52)(49,49)(52,64)(20,26)(40,30)(21,47)(17,63)(31,62)(52,33)(51,21)(42,41)(31,32)(5,25)(12,42)(36,16)(52,41)(27,23)(17,33)(13,13)(57,58)(62,42)(42,57)(16,57)(8,52)(7,38)(27,68)(30,48)(43,67)(58,48)(58,27)(37,69)(38,46)(46,10)(61,33)(62,63)(63,69)(32,22)(45,35)(59,15)(5,6)(10,17)(21,10)(5,64)(30,15)(39,10)(32,39)(25,32)(25,55)(48,28)(56,37)(30,40)。

分別使用標準遺傳算法和本文中改進算法對TSP問題進行求解，兩種算法基本參數一致，各重復執行20次，仿真結果如表1所示。

表1 遺傳算法運行結果比較

從表1的仿真結果可知，本文算法求最優解的能力明顯強于SGA算法。當TSP問題中城市數較少時，本文算法每次都能找到最優解；當城市數較多時，本文算法能找到近似最優解，求得的近似最優解比SGA算法求的近似最優解更接近于TSPLB所提供的最優解。本文算法求得兩種數據下的最優路徑分別如圖2和圖3所示。

圖2 改進算法求解barma14最優解軌道

圖3 改進算法求解Eli51最優解

6 結束語

通過對遺傳算法對選擇算子的改進，引入了精英保留策略，使優質個體在進化后盡最大可能保留；在變異操作中采用一種自適應算法選擇變異算子，提高變異質量和算法的搜索效果。在選擇、交叉、變異后再引入單向進化逆轉操作，使子代繼承親代優質基因機會提高，提高算法搜索最優解的能力。仿真結果表明，優化后的遺傳算法搜索最優解能力提高，且收斂快。但此算法也存在一定的局限性，當TSP問題的規模比較大，算法一般只能求解最優解的近似解。以后研究方向是將優化的遺傳算法與其他算法相結合，如粒子群算法、模擬退火等算法[7,11]，使TSP城市數比較大時，也能求出接近的最優解。

[1] Dorado M，Manifesto V，Colonic A.Ant system：optimization by a colony of cooperating gents[J].IEEE Transactions on Systems，Man，and Cybernetics-Part B，1996，26(1)：29-41.

[2] 馬永杰,云文霞.遺傳算法研究進展[J].計算機應用研究，2012,29(4):1201-1206.

[3] Holland J H.Adaptation in natural and artificial systems [M].Ann Author: University of Michigan Press，Ml，1975.

[4] Simians M,Pataki L M.Genetic Algorithms: A Survey[J].IEEE Computer,1994,27(6):17-26.

[5] 趙明,宋曉宇,董潔,等.利用遺傳算法求解應急物資調度優化問題[J].沈陽建筑大學學報:自然科學版，2012,28(5):944-948.

[6] 劉全,王曉燕,傅啟明,等.雙精英協同進化遺傳算法[J].軟件學報,2012(4):765-775.

[7] 王銀年,葛洪偉.求解TSP問題的改進模擬退火遺傳算法[J].計算機工程與應用,2012,23(4):765 -775.

[8] 李晶皎，趙越，王驕,等.自適應記憶遺傳算法研究[EB/OL].[2013-11-20].http://www.cnki.net/kcms/detail/61.1450.TP.20131129.1020.052.html.

[9] 曹道友.基于改進遺傳算法的應用研究[D].合肥:安徽大學，2010：13-14.

[10] 傅穎勛.遺傳算法的研究與改進[D].北京:北京郵電大學，2010:5-7.

[11] 賈建芳，楊瑞峰，王莉.混合遺傳粒子群優化算法的研究[J].自動化儀表，2013,34(9):1-3.