基于空隙編碼遺傳算法的TSP問題研究張倩，劉紅星，徐玲遼寧工程技術大學理學院，遼寧阜新 （123000）摘 要：本文提出了遺傳算法解決TSP問題的空隙編碼法，并通過采用空隙編碼法對TSP問題進行編碼，解決了其他編碼方式在交換和突變過程中容易產(chǎn)生不可行解的問題，同時給出了基于空隙編碼法的遺傳算子的交換和突變方法，簡化了問題的求解過程。并根據(jù)空隙編碼法的特點，提出了空隙編碼法的二進制表現(xiàn)形式，解決了TSP問題應用遺傳算法的二進制編碼，同時也定義了適合TSP問題的二進制算子的交換和突變的方式，使算法更加簡化合理。關鍵詞：遺傳算法；空隙編碼法；二進制表現(xiàn)；TSP問題1. 引 言TSP問題是運籌學中的一類組合爆炸問題，由于其各種組成數(shù)量巨大，給問題的求解帶來很大的不便。通過遺傳算法解決TSP問題是近幾十年發(fā)展的很好的方法，但是傳統(tǒng)的應用遺傳算法的TSP問題的編碼方法還存在一些不足的地方，比如序號排列編碼方法在交換和突變的過程中容易產(chǎn)生不可行解，隨機數(shù)編碼法在產(chǎn)生過程和交換突變過程中容易產(chǎn)生相等的隨機數(shù)，使問題求解困難。本文通過采用空隙編碼法對TSP問題進行編碼，解決了算子在交換和突變過程中產(chǎn)生不可行解的問題，同時根據(jù)空隙編碼法的特點給出了TSP問題的二進制編碼，使得TSP問題在編碼和求解過程中更加簡單。2. 問題概述2.1 遺傳算法遺傳算法（Genetic Algorithms，GA）是20世紀60年代末期到70年代初期，由美國Michigan大學的John Holland與其同事、學生們研究形成的一套較完整的理論和方法，是試圖解釋自然系統(tǒng)中的生物復雜適應過程入手，模擬生物進化的機制來構造人工系統(tǒng)的模型。隨后經(jīng)過近幾十年的發(fā)展，遺產(chǎn)算法作為具有系統(tǒng)優(yōu)化、適應和學習的高性能計算和建模方法的研究漸趨成熟。遺傳算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經(jīng)過基因（gene）編碼的一定數(shù)目的個體(individual)組成。每個個體實際上是染色體(chromosome)帶有特征的實體。染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個體的形狀的外部表現(xiàn)。因此，在一開始需要實現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。初始種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應度（fitness）大小選擇（selection）個體，并借助于自然遺傳學的遺傳算子（genetic operators）進行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼（decoding），可以作為問題近似最優(yōu)解5。2.2 TSP問題巡回旅行商問題（Traveling Salesman Problem，TSP），也稱貨郎問題，它屬于NP完全問題，給定一組n個城市和它們兩兩之間的直達距離，尋找一條閉合的旅程，使得每個城市剛好經(jīng)過一次且總的旅行距離最短。用圖論術語描述巡回旅行商問題：在有向圖，表示頂點集，表示邊集合，每條邊上有非負權值，尋找的Hamilton圈，使得的總權最小5。3. 已經(jīng)存在的TSP問題編碼方法3.1 編碼已經(jīng)存在的TSP問題的編碼方式有很多種，其中最常用的三種分別是：序號排列編碼法、隨機數(shù)編碼法和剩余序號編碼法。（1）序號排列編碼方法 將n個城市分別用進行序號標識，并將的個整數(shù)的一個排列作為一個旅行方案。例如共有8個城市，整數(shù)的一個排序就是TSP問題的一個可行解，它可以作為遺傳算法求解TSP問題的一個染色體1。（2）隨機數(shù)編碼法1 一種能夠避免出現(xiàn)不可行解的編碼方案是利用隨機數(shù)編碼。假設有8個城市，它們分別對應序號，編碼方法是在（0，1）內(nèi)產(chǎn)生8個不相同的隨機數(shù)作為編碼分類鍵例如隨機產(chǎn)生一個染色體 按照隨機數(shù)大小升序排列為 將的下標表示為城市序號，則得到一個旅行路線：6，1，3，7，8，4，2，5。（3）剩余序號編碼法1 設n個城市的序號分別為，我們稱其為固有標識序號，如果在n個城市中刪除幾個城市后，需要對剩余城市重新賦予序號，新的序號應遵循原固有標識序號的排列次序，稱其為剩余序號。例如8個城市刪除城市，則剩余的5個城市的序號分別為，城市D的固有序號為4，在刪除后，它的剩余序號為3。剩余序號的編碼方法為設n個城市的一個訪問路線次序為，對于這個訪問路線，產(chǎn)生一個染色體，其中，它是在n個城市中刪除后的剩余序號。例如有8個城市的固有序號為，給出一個旅行路線，按照剩余序號定義，該旅行線路的編碼為3.2 編碼的不足對于序號排列編碼方法的最大不足是交換和突變的過程中容易產(chǎn)生不可行解；隨機數(shù)編碼的不足之處是產(chǎn)生隨機數(shù)的過程中或者在交換突變過程中可能會使隨機數(shù)某些值相等，導致不能進行排序。剩余序號發(fā)編碼法解決了以上幾個不足之處，但是剩余序號編碼在從編碼到實際路程順序轉(zhuǎn)換中稍顯繁瑣，而且沒有轉(zhuǎn)換成較為簡單的二進制編碼。4. 空隙編碼法求解TSP問題4.1 空隙編碼法設n個城市，對于任意城市，定義之間的空隙為叫做的前向空隙；定義之間的空隙為叫做的后向空隙；特殊的，的前向空隙為，的后向空隙為。例如有三個城市，它的空隙集為，城市與空隙的表現(xiàn)形式如下： 空隙編碼法首先確定一個編碼順序，然后放置第一個城市，因為放置第一個城市的時候還沒有空隙，所以第一個城市不用編碼。但產(chǎn)生兩個空隙，分別為和，之后按照之前已經(jīng)確定的編碼順序?qū)⒌诙€城市放入上步產(chǎn)生的兩個空隙之一，如放入，記空隙的標號0為第二個城市的編碼，定義其編碼為0，然后依次把城市插入空隙，直至完成。所得到的編碼序列即為一個利用空隙編碼法所得。例如有7個城市，分別為，設定編碼順序為，即先放置A，不需要編碼；之后放置B，假設B放置在A的前向空隙中，記編碼為0；C放置在A的后向空隙中，編碼為2；D放置在A的前向空隙中，編碼為1；E放置在C的后向空隙中，編碼為4；F放置在A的前向空隙中，編碼為2；G放置在C的后向空隙中，編碼為5，編碼結束。所以，當順序為時，編碼為。過程如下所示：空隙0 空隙1A第一步： 放置A，不需要編碼 產(chǎn)生新空隙0，1第二步：B A 空隙0 空隙1 空隙2 看上圖，B放置在A的前向空隙 0上，產(chǎn)生新空隙0，1，2 B A C 空隙0 空隙1 空隙2 空隙3第三步： 看上圖，C放置在A的后向空 隙2上，產(chǎn)生新空隙0，1，2，3 第四步： . . . . . .第五步： . . . . . .B D F A C E 空隙0 空隙1 空隙2 空隙3 空隙4 空隙5 空隙6第六步： F放在A的前向空隙2上， 產(chǎn)生新空隙0，1，2，3，4，5，6 B D F A C G E第七步： 如上圖，G放在C的后向空隙 5上，編碼結束4.2 空隙編碼法的二進制表現(xiàn)形式二進制編碼方式對于初始群體的產(chǎn)生和交換突變運算比較方便，結合空隙編碼法的編碼特點，導出基于空隙編碼法編碼的二進制表示形式。針對上述例子，當放置第一個城市A的時候，產(chǎn)生兩個空隙，當放置第二個城市B的時候，產(chǎn)生三個空隙，所以，當放置第n個城市的時候，產(chǎn)生個空隙。針對上述問題，可以得到如下表格。表1 空隙編碼法二進制表現(xiàn)形式依據(jù)放置城市Vi后ABCDEF產(chǎn)生的空隙數(shù)234567空隙標號范圍010120123012340123450123456二進制位數(shù)122333 即當放置城市D后，一共可以得到5個空隙，每個空隙從前到后的依次標號為0，1，2，3，4，用二進制數(shù)表示04四個數(shù)需要用3位二進制數(shù)。所以針對此問題，可以用一個14位的二進制數(shù)對一個方案進行編碼，第一位二進制數(shù)表示B的空隙編碼法編碼，第23位二進制數(shù)表示C的空隙編碼法編碼，第45位二進制數(shù)表示D的空隙編碼法編碼，第68位二進制數(shù)表示E的空隙編碼法編碼，第911位二進制數(shù)表示F的空隙編碼法編碼，第1214位二進制數(shù)表示G的空隙編碼法編碼。當放置城市B后，空隙標號為0，1，2，而兩位二進制數(shù)表示的范圍為03，所以編碼的時候C的空隙編碼法編碼范圍為02，當大于2的時候，人為的調(diào)整為2。即城市的空隙編碼法編碼范圍為，當二進制數(shù)轉(zhuǎn)換為十進制數(shù)時大于，令此數(shù)等于或等于0。4.3 空隙編碼法及其二進制表現(xiàn)形式的初始群體產(chǎn)生方法（1） 空隙編碼法由表1可知，當放置城市之后，產(chǎn)生的空隙標號范圍為，對于一個空隙編碼法編碼,的范圍為。所以可以按照此種規(guī)格產(chǎn)生任意符合條件的初始群體。（2） 空隙編碼法的二進制表現(xiàn)形式 因為空隙編碼法的二進制表現(xiàn)形式產(chǎn)生的二進制數(shù)可能超過空隙標號范圍，所以用空隙編碼法的二進制表現(xiàn)形式產(chǎn)生初始群體的時候按照以下幾個步驟： a.產(chǎn)生符合實際問題位數(shù)的二進制數(shù) b.按實際問題對二進制數(shù)進行位數(shù)劃分，看每個劃分區(qū)間是否滿足該區(qū)間的空隙標號的最大標號范圍，如果不滿足，丟棄此染色體。4.4 空隙編碼法及其二進制表現(xiàn)形式的交換方法（1） 空隙編碼法 對于空隙編碼法編碼，其交換方式可以采用節(jié)段交換，單點或者多點都可以，但是要保證只有對應位的空隙編碼法編碼可以交換。如取交換點在第三位，則從第四位可以開始交換，得到 （2） 空隙編碼法的二進制表現(xiàn)形式 對于空隙編碼法的二進制表現(xiàn)形式，交換的方法可以使用任何二進制編碼的交換方式，但是空隙編碼法的二進制表現(xiàn)形式可能產(chǎn)生某個區(qū)間的最大數(shù)超過該區(qū)間空隙標號的最大范圍，對于這種情況，使超過空隙標號范圍的區(qū)間重置為該區(qū)間空隙標號的最大數(shù)或最小數(shù)。4.5 空隙編碼法及其二進制表現(xiàn)形式的突變方法（1）空隙編碼法空隙編碼法編碼的突變方式可以單點突變和多點突變，只要保證空隙編碼法編碼突變點的突變范圍在該點允許的范圍即可。（2）空隙編碼法的二進制表現(xiàn)形式 空隙編碼法的二進制表現(xiàn)形式的突變方法可以采用二進制編碼的任何突變方法，只是突變之后檢查每個區(qū)間的范圍是否滿足該區(qū)間的范圍條件，如果不滿足，重置該區(qū)間為該區(qū)間允許的最大范圍或最小范圍。5. 算例分析假設有A，B，C，D，E五個城市，每個城市之間的距離如下表所示：表2 各個城市之間距離表城市/距離ABCDEA03435B306510C46086D35809E510690用基于空隙編碼法和空隙編碼法的二進制表現(xiàn)形式編碼法的遺傳算法解決此問題。5.1 基于空隙編碼法編碼方式的遺傳算法初始群體的選擇，交換概率和突變概率的選擇對于實際問題會產(chǎn)生很大的影響，本題為TSP問題中的一個很小規(guī)模的路徑選舉，所以本題中選取交換概率，突變概率，交換方法選為節(jié)段交換，突變方法選為單點突變。（1）產(chǎn)生初始群體 默認編碼順序為A，B，C，D，E隨機產(chǎn)生四個初始個體 （2）定義適應度為經(jīng)過此路徑的權重和的倒數(shù)。 （3）復制適應度高的個體，淘汰適應度低的個體，即為復制淘汰，新群體為（4）交換操作，因為交換概率為，即與交換，與交換。采用節(jié)段交換，可以隨機產(chǎn)生一個位置，比如產(chǎn)生的數(shù)為2，即從第三位開始進行節(jié)段交換。 至此產(chǎn)生四個新個體，分別為。（5）突變操作，群體個數(shù)為4，個體長度為4，突變概率為，采用單點突變，即系統(tǒng)隨機選取三個個體，每個個體突變一位。得到突變后的新個體為 （6）重復上述步驟，直到找到最優(yōu)解。在實際問題中，也可以規(guī)定算法的代數(shù)為終止條件。5.2 基于空隙編碼法二進制表現(xiàn)方法的遺傳算法對于此方法，選取交換概率為，突變概率為，初始群體為4。采用默認編碼順序A，B，C，D，E，根據(jù)此問題，可由8個二進制數(shù)表示一個染色體的編碼，其中第1位表示B的編碼，第23位表示C的編碼，第45位表示D的編碼，第68位表示E的編碼。（1）產(chǎn)生初始群體產(chǎn)生四個初始群體，分別為計算個體每個區(qū)間是否超過最大空隙標號的允許范圍，可知=（1，1，1，1，0，1，0，0）在C的空隙編碼法編碼（1，1）超過該區(qū)間空隙標號的允許范圍（該區(qū)間空隙標號范圍為0，1，2），刪除染色體，重新生成一個染色體=（1，0，1，1，0，1，0，0），所以產(chǎn)生的初始群體為（2）定義適應度為經(jīng)過此路徑的權重和的倒數(shù)。 （3）復制適應度高的個體，淘汰適應度低的個體，即為復制淘汰，新群體為 （4）交換操作，因為交換概率為，即與交換，與交換。采用節(jié)段交換，可以隨機產(chǎn)生一個位置，比如產(chǎn)生的數(shù)為3，即從第四位開始進行節(jié)段交換。 （5）突變操作，群體個數(shù)為4，個體長度為8，突變概率，采用單點突變，即系統(tǒng)隨機選取三個個體。若每個個體突變的位置相同，則使突變后產(chǎn)生的個體在某個區(qū)域超出該區(qū)域允許范圍的概率增大，所以突變采用每個個體不同位置的突變。 =（0，1，1，1，1，1，0，0） =（0，0，1，1，0，0，1，0） =（0，1，0，1，1，1，0，0） =（1，0，1，1，0，0，1，1）檢查每個區(qū)域的允許范圍，可以發(fā)現(xiàn)=（0，1，1，1，1，1，0，0）在C的空隙編碼法區(qū)域編碼（1，1）超出該區(qū)域空隙標號的允許范圍（該區(qū)間空隙標號范圍為0，1，2），將其超出允許范圍的部分重置為（0，0），即=（0，0，0，1，1，1，0，0）。所以突變后的新個體為 =（0，0，0，1，1，1，0，0） =（0，0，1，1，0，0，1，0） =（0，1，0，1，1，1，0，0） =（1，0，1，1，0，0，1，1）（6）重復上述步驟，直到找到最優(yōu)解。在實際問題中，也可以規(guī)定算法的代數(shù)為終止條件。6. 總結 本文通過采用空隙編碼法對TSP問題進行編碼，成功的解決了其他一些TSP問題編碼方法所產(chǎn)生的不足，并通過空隙編碼法的特點成功的給出了TSP的問題的二進制編碼方式，通過重新定義二進制編碼的交換和突變方法，使TSP問題的解決方法更加完善。同時對于二進制編碼的交換和突變方法還應該有更加優(yōu)于本文的方法，在實際的應用中，讀者可以加入自己的方法，使問題的解法更加完善。參考文獻1 郭嗣琮.信息科學中的軟計算方法M，沈陽：東北大學出版社，2001。 2 田景文，高美娟.人工神經(jīng)網(wǎng)絡算法研究與應用M，北京：北京理工大學出版社，2006。 3 周培德.算法設計與分析M，北京：清華大學出版社，2005。4 張文修，梁怡.遺傳算法的數(shù)學基礎M，西安：西安交通大學出版社，2006。5 李敏強,寇紀淞,林丹,李書全.遺傳算法的基本理論與應用M，北京：科學出版社，2004。Gap-coded genetic algorithms based on TSP ProblemZhang Qian，Liu Hongxing，Xu LingDepartment of Basic Science, Liaoning Technical University, Fuxin 123000AbstractThis paper presents a genetic algorithm to solve the TSP problem gap coding method, and through the use of gap coding method of encoding TSP problem to solve other encoding process in the exchange and mutation prone infeasible problems, while the gap is given based on the encoding method of genetic exchange and mutation operator method, to simplify the problem solving process. And in accordance with the characteristics of gap coding method proposed gap coding method of binary forms, solve the TSP problem using a genetic algorithm for binary encoding, but also defines the TSP problem for the exchange of the binary operator and mutation of the ways in which algorithm is more a reasonable simplification.Keywords: Genetic algorithms; gap coding method; binary performance; TSP problem