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

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

2 改進(jìn)遺傳算法設(shè)計(jì)
    求解旅行商問題的傳統(tǒng)方法存在明顯的缺陷：設(shè)計(jì)變量少，與現(xiàn)實(shí)不相符；假設(shè)較多，對(duì)目標(biāo)函數(shù)有可微或連續(xù)的諸多限制，在求解中會(huì)產(chǎn)生非可行解，難以得到全局最優(yōu)解。傳統(tǒng)求解方法不能很好地模擬實(shí)際問題的各種復(fù)雜情境,尤其在非連通圖約束的情況下，運(yùn)籌規(guī)劃等傳統(tǒng)求解方法更是難以應(yīng)對(duì)，無法客觀準(zhǔn)確地把實(shí)際問題轉(zhuǎn)化為數(shù)學(xué)模型。相比傳統(tǒng)的方法，GA的優(yōu)勢在這種情況下能夠較好地顯示出來：(1)它并不是直接處理路徑中的顯性變量，而是對(duì)變量編碼任意組合成串，即染色體，這才是GA處理的對(duì)象，可見其對(duì)旅行商問題幾乎沒有什么限制。(2)在求最優(yōu)解的過程中，能夠接受各種類型的目標(biāo)函數(shù)，體現(xiàn)了GA的普適性。(3)傳統(tǒng)求解方法往往是從一個(gè)初始解開始，經(jīng)過多次迭代的過程求得最優(yōu)解，求解線路單一。而GA不是沿著一條線，而是基于面上的一代種群求解，容易保留更多優(yōu)良的個(gè)體，淘汰較劣個(gè)體，幾代遺傳之后可保證得到全局最優(yōu)解；GA的擇優(yōu)去劣過程，只以個(gè)體的適應(yīng)度值作為判斷，不需要補(bǔ)充更多信息，操作簡便；GA基于概率論的知識(shí)進(jìn)行遺傳操作，求出具有較高可信度的最優(yōu)解，且不排除進(jìn)一步的改善，確保了其靈活性。因此，GA適合于求解高維、大樣本、非線性、非結(jié)構(gòu)性的復(fù)雜問題[5]。
    傳統(tǒng)遺傳算法TGA(Traditional Genetic Algorithm)嚴(yán)重依賴于參數(shù)設(shè)置和交叉變異算子，存在早熟收斂的缺陷。近年來，國內(nèi)外學(xué)者針對(duì)不同約束條件下的旅行商問題,紛紛提出了改進(jìn)遺傳算法IGA(Improved Genetic Algorithm)。BIERWIRTH C等在對(duì)各類交叉操作實(shí)驗(yàn)對(duì)比的基礎(chǔ)上,提出了優(yōu)先保留交叉法PPX(Precedence Preservation Crossover)，克服了TGA的上述缺陷[6]。MURATA T等通過仿真實(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)過城市5、4、3、2、6、7，最終回到起點(diǎn)的一個(gè)路徑。
2.2 初始種群生成
    初始種群的質(zhì)量對(duì)后續(xù)的優(yōu)化求解具有關(guān)鍵作用。若按隨機(jī)方式產(chǎn)生初始種群，將難以保證其滿足非連通約束，容易產(chǎn)生很多非可行解，從而降低了TGA的效率。擬將其改為綜合隨機(jī)法與貪心法來生成初始染色體種群。貪心法是指每一步都求局部最優(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è)等長的{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擬引入局部鄰域搜索，這是旅行商問題中常用的一種子代擇優(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)化。采用輪盤賭法(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)。由于本文研究的路徑問題是最小化路徑長度，因此，本研究適應(yīng)度函數(shù)取線性定標(biāo)，即有：

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

2.6 算法步驟
　(1)初始化。設(shè)置預(yù)定常數(shù)、最大迭代次數(shù)、交叉概率Pc、變異概率Pm等參數(shù)。
    (2)采用遍歷城市排序的編碼方法，結(jié)合隨機(jī)選取與貪心法來生成初始種群。
　While(迭代次數(shù)≤最大迭代次數(shù))do
    (3)按Pc概率執(zhí)行交叉操作，按Pm概率執(zhí)行變異操作，再做局部鄰域搜索。
    (4)根據(jù)f(S)，用輪盤賭法執(zhí)行選擇操作，確定子代個(gè)體，保證優(yōu)良個(gè)體保留下來。
    (5)求得最大適應(yīng)度值的個(gè)體作為最優(yōu)解。
　(6)檢驗(yàn)最優(yōu)解的適應(yīng)度值是否滿足式(4)，若滿足，則可行;否則為非可行解。
    End While
3 算法檢驗(yàn)與分析
　使用Matlab R2009a分別對(duì)文中IGA和TGA進(jìn)行編程，在2.53 GHz CPU, 2.0 GB內(nèi)存的PC上運(yùn)行，選取我國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的最滿意值為15 383 km，如圖2所示。略優(yōu)于TGA的最滿意值15 387 km，如圖3所示。說明IGA取得了本例的最優(yōu)解，達(dá)到了算法改進(jìn)的目的。究其原因，主要是由于TGA在初始種群生成方面產(chǎn)生了大量不可行解和在交叉變異過程中缺失局部鄰域擇優(yōu)能力。即正是由于IGA引入局部鄰域搜索操作，從而確保了子代個(gè)體快速持續(xù)地向最優(yōu)解收斂。

    同時(shí),對(duì)比兩種算法的極差也能看出，IGA的種群離散程度較小，向最優(yōu)解的集聚性較高，向最優(yōu)解的收斂性更好。通過分析，不難發(fā)現(xiàn)這主要源于以下兩點(diǎn)：(1)IGA的初始種群質(zhì)量優(yōu)于TGA，其可行染色體比例較高，避免大量不滿意染色體生成。(2)IGA的局部搜索提高了子代個(gè)體向最優(yōu)解的收斂性。相比TGA，IGA的求解能力更強(qiáng)、更高效。
    針對(duì)非連通圖旅行商路徑問題設(shè)計(jì)了IGA，采用基于旅行商遍歷城市次序的編碼方式、執(zhí)行交叉變異操作以及局部鄰域搜索操作,解決了TGA在隨機(jī)方式下生成大量非可行解的問題，加速染色體向最優(yōu)解收斂，實(shí)際案例驗(yàn)證了其求解的高效性。今后的研究可著眼于最優(yōu)解為非可行解條件下初始種群的再調(diào)整，同時(shí)設(shè)計(jì)能向最優(yōu)解更快收斂的高效IGA。
參考文獻(xiàn)
[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] 吳春國. 廣義染色體遺傳算法與迭代式最小二乘支持向量機(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 algori-thms 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] 陶林波,沈建京,韓強(qiáng). 一種解決早熟收斂的自適應(yīng)遺傳算法設(shè)計(jì)[J]. 微計(jì)算機(jī)信息, 2006,22(12):268-270.
[10] 康立山,謝云,尤矢勇,等.模擬退火算法[M].北京:科學(xué)出版社,1994.