孔令夷

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

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

1 問(wèn)題描述

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

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

求使目標(biāo)函數(shù)

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

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

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

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

2.1 編碼方式

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

2.2 初始種群生成

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

2.3 交叉變異操作

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

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

2.4 局部鄰域搜索

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

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

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

適應(yīng)度函數(shù)是評(píng)價(jià)個(gè)體優(yōu)劣的指標(biāo)。由于本文研究的路徑問(wèn)題是最小化路徑長(zhǎng)度，因此，本研究適應(yīng)度函數(shù)取線(xiàn)性定標(biāo)，即有：

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

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

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

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

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

2.6 算法步驟

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

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

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

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

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

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

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

End While

3 算法檢驗(yàn)與分析

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

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

圖2 IGA的最滿(mǎn)意值

圖3 TGA的最滿(mǎn)意值

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

針對(duì)非連通圖旅行商路徑問(wèn)題設(shè)計(jì)了IGA，采用基于旅行商遍歷城市次序的編碼方式、執(zhí)行交叉變異操作以及局部鄰域搜索操作,解決了TGA在隨機(jī)方式下生成大量非可行解的問(wèn)題，加速染色體向最優(yōu)解收斂，實(shí)際案例驗(yàn)證了其求解的高效性。今后的研究可著眼于最優(yōu)解為非可行解條件下初始種群的再調(diào)整，同時(shí)設(shè)計(jì)能向最優(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]吳春國(guó).廣義染色體遺傳算法與迭代式最小二乘支持向量機(jī)回歸算法研究[D].吉林:吉林大學(xué),2006.

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

[4]郟宣耀,王芳.一種改進(jìn)的小生境遺傳算法[J].重慶郵電學(xué)院學(xué)報(bào)(自然科學(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]汪民樂(lè),高曉光,劉 剛.遺傳算法早熟問(wèn)題的定量分析及其預(yù)防策略[J].系統(tǒng)工程與電子技術(shù),2006,28(8):1249-1251.

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

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