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

石利平

(廣東女子職業(yè)技術(shù)學(xué)院 應(yīng)用設(shè)計(jì)系,廣東 廣州 511450)

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

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

1 TSP問題描述

2 標(biāo)準(zhǔn)遺傳算法

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

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

3 改進(jìn)的遺傳算法

3.1 編碼

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

3.2 初始化種群

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

種群個(gè)體進(jìn)化后是不是較優(yōu)秀的問題解，即看其適應(yīng)性，測(cè)評(píng)的標(biāo)準(zhǔn)就是適應(yīng)度函數(shù)的值。適應(yīng)度函數(shù)的值是群體進(jìn)化過程中個(gè)體優(yōu)勝劣汰唯一依據(jù)。個(gè)體適應(yīng)度函數(shù)值較大，則說明該個(gè)體生存競(jìng)爭(zhēng)能力較強(qiáng)，被選擇進(jìn)化的可能性高；反之，個(gè)體適應(yīng)度函數(shù)值較小，則其個(gè)體生存能力較弱，在群體的進(jìn)化中被淘汰的可能性高。適應(yīng)度函數(shù)可以說是群體進(jìn)化中的自然生存環(huán)境，是模擬生物界進(jìn)化中優(yōu)勝劣汰的自然選擇[10]。因此在遺傳算法中，如何合理設(shè)計(jì)適應(yīng)度函數(shù)是非常重要的。本文中個(gè)體的適應(yīng)度函數(shù)為

(1)

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

該適應(yīng)度函數(shù)值是恰好走完n座城市再回到起始城市的距離倒數(shù)。染色體優(yōu)化的目標(biāo)就是選取盡量大的適應(yīng)度函數(shù)值，適應(yīng)度函數(shù)值越大則染色體越優(yōu)。

3.4 選擇操作

選擇操作是以一定的選擇概率從當(dāng)前種群中選擇適應(yīng)函數(shù)值高的生成的新個(gè)體，其主要目的盡量使優(yōu)質(zhì)基因遺傳給下一代,提高算法計(jì)算效率和全局收斂的概率。本文算法個(gè)體選擇概率計(jì)算方法如下：

對(duì)于給定的規(guī)模為n的群體Q(n)=(q1,q2,q3,…,qn)，個(gè)體qi的適應(yīng)度函數(shù)值為F(qi)，其選擇概率為

(2)

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

3.5 交叉操作

交叉是很重要的操作算子，目的是將選擇得到的優(yōu)質(zhì)個(gè)體進(jìn)行交叉得到更優(yōu)質(zhì)新個(gè)體。交叉概率取值范圍一般建議0.4～0.99[9]。

本文采用精英個(gè)體與選擇后得的新個(gè)體進(jìn)行部分映射雜交操作，交叉的位置隨機(jī)產(chǎn)生，即隨機(jī)產(chǎn)生交叉區(qū)域。假設(shè)城市數(shù)為10，交叉操作算法如下：

(1) 選擇父代種群最優(yōu)個(gè)體與一新個(gè)體；

(2) 隨機(jī)產(chǎn)生2個(gè)交叉位置n1和n2，n1∈[1,10],n2∈[1,10]，對(duì)這2個(gè)位置中間的數(shù)據(jù)進(jìn)行交叉操作;

(3) 交叉后產(chǎn)生的新個(gè)體城市編號(hào)如有重復(fù)，采用部分映射方法消除重復(fù)，不重復(fù)的編號(hào)保留。

這種交叉方法可確保較大可能地保護(hù)好父代個(gè)體中的優(yōu)質(zhì)基因模式,從而使優(yōu)質(zhì)染色體遺傳到下一代當(dāng)中,有利于提高遺傳算法的性能。

3.6 變異

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

(3)

式3中Pm-max為最大變異概率,本文中取0.05；Pm-min為最小變異概率，這里取0.001，F(xiàn)為要變異個(gè)體的適應(yīng)度，F(xiàn)max為種群中最大的適應(yīng)度值，F(xiàn)avg為當(dāng)前種群平均適應(yīng)度值。

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

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

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

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

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

InvCh=SelCh; % Selch是選擇要逆轉(zhuǎn)的個(gè)體

%InvCh是逆轉(zhuǎn)后的個(gè)體

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);%計(jì)算逆轉(zhuǎn)后路徑長(zhǎng)度

index=InvPath

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

4 解決TSP問題優(yōu)化的遺傳算法流程

改進(jìn)的遺傳算法流程圖如圖1所示。

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

5 仿真實(shí)驗(yàn)及結(jié)果

本文選用國(guó)際上通用的TSPLIB測(cè)試庫中數(shù)據(jù)的Barma14和Eli51數(shù)據(jù)進(jìn)行測(cè)試。barma14數(shù)據(jù)的14個(gè)城市坐標(biāo)如下：

(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數(shù)據(jù)的51個(gè)城市坐標(biāo)如下：

(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)。

分別使用標(biāo)準(zhǔn)遺傳算法和本文中改進(jìn)算法對(duì)TSP問題進(jìn)行求解，兩種算法基本參數(shù)一致，各重復(fù)執(zhí)行20次，仿真結(jié)果如表1所示。

表1 遺傳算法運(yùn)行結(jié)果比較

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

圖2 改進(jìn)算法求解barma14最優(yōu)解軌道

圖3 改進(jìn)算法求解Eli51最優(yōu)解

6 結(jié)束語

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

[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ìn)展[J].計(jì)算機(jī)應(yīng)用研究，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] 趙明,宋曉宇,董潔,等.利用遺傳算法求解應(yīng)急物資調(diào)度優(yōu)化問題[J].沈陽建筑大學(xué)學(xué)報(bào):自然科學(xué)版，2012,28(5):944-948.

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

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

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

[9] 曹道友.基于改進(jìn)遺傳算法的應(yīng)用研究[D].合肥:安徽大學(xué)，2010：13-14.

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

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