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

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

2 改進遺傳算法設計
    求解旅行商問題的傳統方法存在明顯的缺陷：設計變量少，與現實不相符；假設較多，對目標函數有可微或連續的諸多限制，在求解中會產生非可行解，難以得到全局最優解。傳統求解方法不能很好地模擬實際問題的各種復雜情境,尤其在非連通圖約束的情況下，運籌規劃等傳統求解方法更是難以應對，無法客觀準確地把實際問題轉化為數學模型。相比傳統的方法，GA的優勢在這種情況下能夠較好地顯示出來：(1)它并不是直接處理路徑中的顯性變量，而是對變量編碼任意組合成串，即染色體，這才是GA處理的對象，可見其對旅行商問題幾乎沒有什么限制。(2)在求最優解的過程中，能夠接受各種類型的目標函數，體現了GA的普適性。(3)傳統求解方法往往是從一個初始解開始，經過多次迭代的過程求得最優解，求解線路單一。而GA不是沿著一條線，而是基于面上的一代種群求解，容易保留更多優良的個體，淘汰較劣個體，幾代遺傳之后可保證得到全局最優解；GA的擇優去劣過程，只以個體的適應度值作為判斷，不需要補充更多信息，操作簡便；GA基于概率論的知識進行遺傳操作，求出具有較高可信度的最優解，且不排除進一步的改善，確保了其靈活性。因此，GA適合于求解高維、大樣本、非線性、非結構性的復雜問題[5]。
    傳統遺傳算法TGA(Traditional Genetic Algorithm)嚴重依賴于參數設置和交叉變異算子，存在早熟收斂的缺陷。近年來，國內外學者針對不同約束條件下的旅行商問題,紛紛提出了改進遺傳算法IGA(Improved Genetic Algorithm)。BIERWIRTH C等在對各類交叉操作實驗對比的基礎上,提出了優先保留交叉法PPX(Precedence Preservation Crossover)，克服了TGA的上述缺陷[6]。MURATA T等通過仿真實驗，提出平移變異SCM(Shift Change Mutation)，引入局部鄰域搜索，確保子代遺傳質量并加快算法收斂[7]。
2.1 編碼方式
    本研究的編碼采用基于旅行商需要遍歷所有城市的次序，這也是最常用的編碼方式，以有限的城市數量作為搜索范圍，有助于提高搜索效率。設S=(1,5,4, 3,2,6,7),可以看成是從城市1出發，依次經過城市5、4、3、2、6、7，最終回到起點的一個路徑。
2.2 初始種群生成
    初始種群的質量對后續的優化求解具有關鍵作用。若按隨機方式產生初始種群，將難以保證其滿足非連通約束，容易產生很多非可行解，從而降低了TGA的效率。擬將其改為綜合隨機法與貪心法來生成初始染色體種群。貪心法是指每一步都求局部最優。
2.3 交叉變異操作
    基于旅行商遍歷城市次序的編碼方式，個體內部基因存在先后關系，若在交叉變異操作中破壞了這種自然關系，則有可能產生大量不可行子代個體，造成早熟收斂或冗余迭代[8-9]。因此擬選用PPX和SCM操作。PPX是隨機產生的兩個父代個體，并產生一個等長的{1,2}隨機串。掃描隨機串，如果第k位是1，則提取第一個父代染色體最左邊的城市號作為子代第k位；如果第k位是2，則提取第二個父代染色體最左邊的城市號，然后刪除兩個父代中的該城市號，重復以上操作，直到隨機串被掃描完。PPX與映射、次序或循環交叉相比，可更好地繼承優良基因。
    SCM操作是指隨機選擇插入碼和插入點，進行平移操作。比如S=(1,5,4,3,2,6,7), 若隨機選取插入碼為6，插入點為5與4之間，則S′=(1,5,6,4,3,2,7)，SCM與對換變異、目標導向變異等相比，更好地保持了基因之間的先后次序，繼承了父代的優良性。
2.4 局部鄰域搜索
    IGA擬引入局部鄰域搜索，這是旅行商問題中常用的一種子代擇優方法,有助于進一步加快算法的收斂，縮短求最優解的運行時間。其操作內容是：以交叉變異操作產生的子代個體為基體，對每個基因采用右鄰基因交換的方法產生新的局部鄰域子代個體。例如S′=(1,5,6,4,3,2,7)，將基因2與其右鄰的基因7交換，就能生成一個新個體S′′=（1,5,6,4,3,7,2）。因此，局部鄰域搜索能產生N-1個局部鄰域子代個體,從中選擇具有最大適應度的鄰域個體與基體再做比較，以適應度大者為更新后的子代基體。
2.5 選擇操作及適應度函數的建立
    選擇操作是對生物進化論“適者生存”思想的體現，越優良的個體具有越大的概率進入下一代，種群性能就會隨著進化而不斷優化。采用輪盤賭法(Roulette Wheel Selection)，保證將種群中最優個體隨機替換掉下一代的某個體，對于IGA能夠不斷尋優具有關鍵作用。
    適應度函數是評價個體優劣的指標。由于本文研究的路徑問題是最小化路徑長度，因此，本研究適應度函數取線性定標，即有：

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

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

    同時,對比兩種算法的極差也能看出，IGA的種群離散程度較小，向最優解的集聚性較高，向最優解的收斂性更好。通過分析，不難發現這主要源于以下兩點：(1)IGA的初始種群質量優于TGA，其可行染色體比例較高，避免大量不滿意染色體生成。(2)IGA的局部搜索提高了子代個體向最優解的收斂性。相比TGA，IGA的求解能力更強、更高效。
    針對非連通圖旅行商路徑問題設計了IGA，采用基于旅行商遍歷城市次序的編碼方式、執行交叉變異操作以及局部鄰域搜索操作,解決了TGA在隨機方式下生成大量非可行解的問題，加速染色體向最優解收斂，實際案例驗證了其求解的高效性。今后的研究可著眼于最優解為非可行解條件下初始種群的再調整，同時設計能向最優解更快收斂的高效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]. 吉林: 吉林大學, 2006.
[3] 黃永青,梁昌勇,張祥德,等.一種小種群自適應遺傳算法研究[J].系統工程理論與實踐,2005,25(11):92-97.
[4] 郟宣耀,王芳.一種改進的小生境遺傳算法[J].重慶郵電學院學報(自然科學版),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] 汪民樂,高曉光,劉 剛.遺傳算法早熟問題的定量分析及其預防策略[J].系統工程與電子技術,2006,28(8):1249-1251.
[9] 陶林波,沈建京,韓強. 一種解決早熟收斂的自適應遺傳算法設計[J]. 微計算機信息, 2006,22(12):268-270.
[10] 康立山,謝云,尤矢勇,等.模擬退火算法[M].北京:科學出版社,1994.