求解非連通圖旅行商問題的改進遺傳算法*

孔令夷

(西安郵電大學(xué) 管理工程學(xué)院，陜西 西安 710061)

遺傳算法 GA(Genetic Algorithm)遵循“適者生存”的規(guī)律，通過模仿自然選擇而不斷搜索最優(yōu)解。GA的求解過程包括選擇(Selection)、交叉(Crossover)、變異(Mutation)操作。由于GA對問題的限制不多，對目標函數(shù)的數(shù)學(xué)特性要求也不嚴格，因而相比傳統(tǒng)的運籌規(guī)劃方法，在處理復(fù)雜問題時顯得游刃有余，幾乎都能找到最優(yōu)解。GA的應(yīng)用非常廣泛，適用于處理大多數(shù)科學(xué)與工程復(fù)雜問題，應(yīng)用價值很高。其中旅行商問題具有高度的計算復(fù)雜性，在圖論中最具代表性,已被證明是高維非線性完全問題NPC(Non-deterministic Polynomial Complete Problem)[1-2]，多年來都是理論界與企業(yè)界面臨的難題，如何將智能優(yōu)化算法應(yīng)用于這一難題的全局優(yōu)化求解，也成為了眾多學(xué)者研究的對象[3-4]。

1 問題描述

現(xiàn)實中的旅行商問題一般都會有各種約束或限制，而非連通圖就是一個典型的例子，即旅行商要經(jīng)過的某些目的地(城市)之間存在障礙物，如山川、農(nóng)田等，不能直接連通，只有通過其他地點間接到達。旅行商經(jīng)過的所有地點將構(gòu)成非連通圖，如圖1所示。

本文的研究目的是尋找最短路徑，將旅行商的成本降到最低。該路徑經(jīng)過的所有N個城市，除了起點以外，都要經(jīng)過且只經(jīng)過1次，最終回到起點，符合旅行商遍歷所有城市實現(xiàn)銷售額最大化的實際情形。設(shè)有N個城市的集合 C={c1,c2,…,cN}，每兩個城市之間的距離為 d(ci,cj)∈R+，其中，ci,cj∈C(1≤i,j≤N)

求使目標函數(shù)

最 小 的 路 徑 序 列{cΠ(1),cΠ(2),…,cΠ(N)}， 其 中 П(1), П(2),…,П(N)是 1,2,…,N的全排列。

2 改進遺傳算法設(shè)計

求解旅行商問題的傳統(tǒng)方法存在明顯的缺陷：設(shè)計變量少，與現(xiàn)實不相符；假設(shè)較多，對目標函數(shù)有可微或連續(xù)的諸多限制，在求解中會產(chǎn)生非可行解，難以得到全局最優(yōu)解。傳統(tǒng)求解方法不能很好地模擬實際問題的各種復(fù)雜情境,尤其在非連通圖約束的情況下，運籌規(guī)劃等傳統(tǒng)求解方法更是難以應(yīng)對，無法客觀準確地把實際問題轉(zhuǎn)化為數(shù)學(xué)模型。相比傳統(tǒng)的方法，GA的優(yōu)勢在這種情況下能夠較好地顯示出來：(1)它并不是直接處理路徑中的顯性變量，而是對變量編碼任意組合成串，即染色體，這才是GA處理的對象，可見其對旅行商問題幾乎沒有什么限制。(2)在求最優(yōu)解的過程中，能夠接受各種類型的目標函數(shù)，體現(xiàn)了GA的普適性。(3)傳統(tǒng)求解方法往往是從一個初始解開始，經(jīng)過多次迭代的過程求得最優(yōu)解，求解線路單一。而GA不是沿著一條線，而是基于面上的一代種群求解，容易保留更多優(yōu)良的個體，淘汰較劣個體，幾代遺傳之后可保證得到全局最優(yōu)解；GA的擇優(yōu)去劣過程，只以個體的適應(yīng)度值作為判斷，不需要補充更多信息，操作簡便；GA基于概率論的知識進行遺傳操作，求出具有較高可信度的最優(yōu)解，且不排除進一步的改善，確保了其靈活性。因此，GA適合于求解高維、大樣本、非線性、非結(jié)構(gòu)性的復(fù)雜問題[5]。

傳統(tǒng)遺傳算法 TGA(Traditional Genetic Algorithm)嚴重依賴于參數(shù)設(shè)置和交叉變異算子，存在早熟收斂的缺陷。近年來，國內(nèi)外學(xué)者針對不同約束條件下的旅行商問題,紛紛提出了改進遺傳算法IGA(Improved Genetic Algorithm)。BIERWIRTH C等在對各類交叉操作實驗對比的基礎(chǔ)上,提出了優(yōu)先保留交叉法PPX(Precedence Preservation Crossover)，克服了TGA的上述缺陷[6]。MURATA T等通過仿真實驗，提出平移變異SCM(Shift Change Mutation)，引入局部鄰域搜索，確保子代遺傳質(zhì)量并加快算法收斂[7]。

2.1 編碼方式

本研究的編碼采用基于旅行商需要遍歷所有城市的次序，這也是最常用的編碼方式，以有限的城市數(shù)量作為搜索范圍，有助于提高搜索效率。設(shè)S=(1,5,4,3,2,6,7),可以看成是從城市1出發(fā)，依次經(jīng)過城市5、4、3、2、6、7，最終回到起點的一個路徑。

2.2 初始種群生成

初始種群的質(zhì)量對后續(xù)的優(yōu)化求解具有關(guān)鍵作用。若按隨機方式產(chǎn)生初始種群，將難以保證其滿足非連通約束，容易產(chǎn)生很多非可行解，從而降低了TGA的效率。擬將其改為綜合隨機法與貪心法來生成初始染色體種群。貪心法是指每一步都求局部最優(yōu)。

2.3 交叉變異操作

基于旅行商遍歷城市次序的編碼方式，個體內(nèi)部基因存在先后關(guān)系，若在交叉變異操作中破壞了這種自然關(guān)系，則有可能產(chǎn)生大量不可行子代個體，造成早熟收斂或冗余迭代[8-9]。因此擬選用PPX和SCM操作。PPX是隨機產(chǎn)生的兩個父代個體，并產(chǎn)生一個等長的{1,2}隨機串。掃描隨機串，如果第k位是1，則提取第一個父代染色體最左邊的城市號作為子代第k位；如果第k位是2，則提取第二個父代染色體最左邊的城市號，然后刪除兩個父代中的該城市號，重復(fù)以上操作，直到隨機串被掃描完。PPX與映射、次序或循環(huán)交叉相比，可更好地繼承優(yōu)良基因。

SCM操作是指隨機選擇插入碼和插入點，進行平移操作。比如S=(1,5,4,3,2,6,7),若隨機選取插入碼為6，插入點為 5與 4之間， 則 S′=(1,5,6,4,3,2,7)，SCM與對換變異、目標導(dǎo)向變異等相比，更好地保持了基因之間的先后次序，繼承了父代的優(yōu)良性。

2.4 局部鄰域搜索

IGA擬引入局部鄰域搜索，這是旅行商問題中常用的一種子代擇優(yōu)方法,有助于進一步加快算法的收斂，縮短求最優(yōu)解的運行時間。其操作內(nèi)容是：以交叉變異操作產(chǎn)生的子代個體為基體，對每個基因采用右鄰基因交換的方法產(chǎn)生新的局部鄰域子代個體。例如S′=(1,5,6,4,3,2,7)，將基因 2與其右鄰的基因 7交換，就能生成一個新個體 S′=（1,5,6,4,3,7,2）。 因此，局部鄰域搜索能產(chǎn)生N-1個局部鄰域子代個體,從中選擇具有最大適應(yīng)度的鄰域個體與基體再做比較，以適應(yīng)度大者為更新后的子代基體。

2.5 選擇操作及適應(yīng)度函數(shù)的建立

選擇操作是對生物進化論“適者生存”思想的體現(xiàn)，越優(yōu)良的個體具有越大的概率進入下一代，種群性能就會隨著進化而不斷優(yōu)化。采用輪盤賭法(Roulette Wheel Selection)，保證將種群中最優(yōu)個體隨機替換掉下一代的某個體，對于IGA能夠不斷尋優(yōu)具有關(guān)鍵作用。

適應(yīng)度函數(shù)是評價個體優(yōu)劣的指標。由于本文研究的路徑問題是最小化路徑長度，因此，本研究適應(yīng)度函數(shù)取線性定標，即有：

式中，α為預(yù)先設(shè)定的常數(shù)；N為城市的數(shù)目；M為包含所有城市的最小正方形的邊長；Td就是根據(jù)式(1)計算得出的實際行進路徑長度，即目標和數(shù)值。

為了避免產(chǎn)生大量非可行解，本研究IGA作如下特殊處理：

為解決這一問題，可通過對非連通城市間距離進行特殊處理，來保證GA的優(yōu)良特性不會受到影響，而且可以更容易地找到該問題的可行解。如上文所述，城市cp,cq之間存在障礙物，假設(shè)個體S包含基因片段(…,cp,cq,…)或者(…,cq,cp, …), 則有：

因此，在特殊處理后，若個體S中存在非連通城市相鄰，則必會出現(xiàn)其適應(yīng)度值小于，隨著進化歷程而逐漸被淘汰，因此就排除了非連通城市相鄰的情況。反之，式(4)若成立，則個體S必定為可行解，用反證法可證出，此處從略。

如果用GA求解非連通圖旅行商問題，求出最優(yōu)解的適應(yīng)度值小于,則可以斷定該最優(yōu)解不成立。

2.6 算法步驟

(1)初始化。設(shè)置預(yù)定常數(shù)、最大迭代次數(shù)、交叉概率 Pc、變異概率 Pm等參數(shù)。

(2)采用遍歷城市排序的編碼方法，結(jié)合隨機選取與貪心法來生成初始種群。

While(迭代次數(shù)≤最大迭代次數(shù))do

(3)按Pc概率執(zhí)行交叉操作，按 Pm概率執(zhí)行變異操作，再做局部鄰域搜索。

(4)根據(jù) f(S)，用輪盤賭法執(zhí)行選擇操作，確定子代個體，保證優(yōu)良個體保留下來。

(5)求得最大適應(yīng)度值的個體作為最優(yōu)解。

(6)檢驗最優(yōu)解的適應(yīng)度值是否滿足式(4)，若滿足，則可行;否則為非可行解。

End While

3 算法檢驗與分析

使用Matlab R2009a分別對文中IGA和TGA進行編程，在2.53 GHz CPU,2.0 GB內(nèi)存的PC上運行，選取我國31個中心城市的地理數(shù)據(jù)用于算法檢驗[10]。設(shè)交叉概率 Pc=0.2，變異概率Pm=0.5，最大迭代次數(shù)MaxItr=1 000，算法檢驗結(jié)果如表1所示。在求最優(yōu)解方面，IGA的最滿意值為15 383 km，如圖2所示。略優(yōu)于TGA的最滿意值15 387 km，如圖3所示。說明IGA取得了本例的最優(yōu)解，達到了算法改進的目的。究其原因，主要是由于TGA在初始種群生成方面產(chǎn)生了大量不可行解和在交叉變異過程中缺失局部鄰域擇優(yōu)能力。即正是由于IGA引入局部鄰域搜索操作，從而確保了子代個體快速持續(xù)地向最優(yōu)解收斂。

表1 兩種算法的檢驗結(jié)果

圖2 IGA的最滿意值

圖3 TGA的最滿意值

同時,對比兩種算法的極差也能看出，IGA的種群離散程度較小，向最優(yōu)解的集聚性較高，向最優(yōu)解的收斂性更好。通過分析，不難發(fā)現(xiàn)這主要源于以下兩點：(1)IGA的初始種群質(zhì)量優(yōu)于TGA，其可行染色體比例較高，避免大量不滿意染色體生成。(2)IGA的局部搜索提高了子代個體向最優(yōu)解的收斂性。相比TGA，IGA的求解能力更強、更高效。

針對非連通圖旅行商路徑問題設(shè)計了IGA，采用基于旅行商遍歷城市次序的編碼方式、執(zhí)行交叉變異操作以及局部鄰域搜索操作,解決了TGA在隨機方式下生成大量非可行解的問題，加速染色體向最優(yōu)解收斂，實際案例驗證了其求解的高效性。今后的研究可著眼于最優(yōu)解為非可行解條件下初始種群的再調(diào)整，同時設(shè)計能向最優(yōu)解更快收斂的高效IGA。

[1]YANG J H,WU C G,LEE H P,et al.Solving traveling salesman problems using generalized chromosome genetic algorithm[J].Progress in Natural Science,2008,18(7):887-892.

[2]吳春國.廣義染色體遺傳算法與迭代式最小二乘支持向量機回歸算法研究[D].吉林:吉林大學(xué),2006.

[3]黃永青,梁昌勇,張祥德,等.一種小種群自適應(yīng)遺傳算法研究[J].系統(tǒng)工程理論與實踐,2005,25(11):92-97.

[4]郟宣耀,王芳.一種改進的小生境遺傳算法[J].重慶郵電學(xué)院學(xué)報(自然科學(xué)版),2005,17(16):721-723.

[5]ZHAO X C,GAO X S.Affinity genetic algorithm[J].Journal of Heuristics,2007,13(2):133-150.

[6]BIERWIRTH C,MATTFELD D,KOPFER H.On permutation representations for scheduling problems[C].Proceedings of the 4th International Conference on Parallel Problem Solving from Nature.Berlin,Germany:Springer,1996:310-318.

[7]MURATA T,ISHIBUCHI H,TANAKA H.Genetic algorithms for flowshop scheduling problem[J].Computers&Industrial Engineering,1996,30(4):1061-1071.

[8]汪民樂,高曉光,劉 剛.遺傳算法早熟問題的定量分析及其預(yù)防策略[J].系統(tǒng)工程與電子技術(shù),2006,28(8):1249-1251.

[9]陶林波,沈建京,韓強.一種解決早熟收斂的自適應(yīng)遺傳算法設(shè)計[J].微計算機信息,2006,22(12):268-270.

[10]康立山,謝云,尤矢勇,等.模擬退火算法[M].北京:科學(xué)出版社,1994.