基于空隙編碼遺傳算法的TSP 問題研究

《基于空隙編碼遺傳算法的TSP 問題研究》由會(huì)員分享，可在線閱讀，更多相關(guān)《基于空隙編碼遺傳算法的TSP 問題研究（9頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 基于空隙編碼遺傳算法的TSP問題研究 張倩，劉紅星，徐玲 遼寧工程技術(shù)大學(xué)理學(xué)院，遼寧阜新 （123000） 摘 要：本文提出了遺傳算法解決TSP問題的空隙編碼法，并通過采用空隙編碼法對(duì)TSP問題進(jìn)行編碼，解決了其他編碼方式在交換和突變過程中容易產(chǎn)生不可行解的問題，同時(shí)給出了基于空隙編碼法的遺傳算子的交換和突變方法，簡(jiǎn)化了問題的求解過程。并根據(jù)空隙編碼法的特點(diǎn)，提出了空隙編碼法的二進(jìn)制表現(xiàn)形式，解決了TSP問題應(yīng)用遺傳算法的二進(jìn)制編碼，同時(shí)也定義了適合TSP問題的二進(jìn)制算子的交換和突變的方式，使算法更加簡(jiǎn)化合理。 關(guān)鍵詞：遺傳算法；空隙編碼法；二進(jìn)制表現(xiàn)；TSP問題 1. 引

2、 言 TSP問題是運(yùn)籌學(xué)中的一類組合爆炸問題，由于其各種組成數(shù)量巨大，給問題的求解帶來很大的不便。通過遺傳算法解決TSP問題是近幾十年發(fā)展的很好的方法，但是傳統(tǒng)的應(yīng)用遺傳算法的TSP問題的編碼方法還存在一些不足的地方，比如序號(hào)排列編碼方法在交換和突變的過程中容易產(chǎn)生不可行解，隨機(jī)數(shù)編碼法在產(chǎn)生過程和交換突變過程中容易產(chǎn)生相等的隨機(jī)數(shù)，使問題求解困難。本文通過采用空隙編碼法對(duì)TSP問題進(jìn)行編碼，解決了算子在交換和突變過程中產(chǎn)生不可行解的問題，同時(shí)根據(jù)空隙編碼法的特點(diǎn)給出了TSP問題的二進(jìn)制編碼，使得TSP問題在編碼和求解過程中更加簡(jiǎn)單。 2. 問題概述 2.1 遺傳算法 遺傳算法（Gen

3、etic Algorithms，GA）是20世紀(jì)60年代末期到70年代初期，由美國(guó)Michigan大學(xué)的John Holland與其同事、學(xué)生們研究形成的一套較完整的理論和方法，是試圖解釋自然系統(tǒng)中的生物復(fù)雜適應(yīng)過程入手，模擬生物進(jìn)化的機(jī)制來構(gòu)造人工系統(tǒng)的模型。隨后經(jīng)過近幾十年的發(fā)展，遺產(chǎn)算法作為具有系統(tǒng)優(yōu)化、適應(yīng)和學(xué)習(xí)的高性能計(jì)算和建模方法的研究漸趨成熟。 遺傳算法是從代表問題可能潛在的解集的一個(gè)種群（population）開始的，而一個(gè)種群則由經(jīng)過基因（gene）編碼的一定數(shù)目的個(gè)體(individual)組成。每個(gè)個(gè)體實(shí)際上是染色體(chromosome)帶有特征的實(shí)體。染色體作為遺傳

4、物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個(gè)體的形狀的外部表現(xiàn)。因此，在一開始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。初始種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個(gè)體的適應(yīng)度（fitness）大小選擇（selection）個(gè)體，并借助于自然遺傳學(xué)的遺傳算子（genetic operators）進(jìn)行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。這個(gè)過程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過解碼（

5、decoding），可以作為問題近似最優(yōu)解[5]。 2.2 TSP問題 巡回旅行商問題（Traveling Salesman Problem，TSP），也稱貨郎問題，它屬于NP完全問題，給定一組n個(gè)城市和它們兩兩之間的直達(dá)距離，尋找一條閉合的旅程，使得每個(gè)城市剛好經(jīng)過一次且總的旅行距離最短。 用圖論術(shù)語(yǔ)描述巡回旅行商問題：在有向圖，表示頂點(diǎn)集，，表示邊集合，，每條邊上有非負(fù)權(quán)值，尋找的Hamilton圈，使得的總權(quán)最小[5]。 3. 已經(jīng)存在的TSP問題編碼方法 3.1 編碼 已經(jīng)存在的TSP問題的編碼方式有很多種，其中最常用的三種分別是：序號(hào)排列編碼法、隨機(jī)數(shù)編碼法和剩余序號(hào)編碼

6、法。 （1）序號(hào)排列編碼方法 將n個(gè)城市分別用進(jìn)行序號(hào)標(biāo)識(shí)，并將的個(gè)整數(shù)的一個(gè)排列作為一個(gè)旅行方案。例如共有8個(gè)城市，整數(shù)的一個(gè)排序就是TSP問題的一個(gè)可行解，它可以作為遺傳算法求解TSP問題的一個(gè)染色體[1]。 （2）隨機(jī)數(shù)編碼法[1] 一種能夠避免出現(xiàn)不可行解的編碼方案是利用隨機(jī)數(shù)編碼。假設(shè)有8個(gè)城市，它們分別對(duì)應(yīng)序號(hào)，編碼方法是在（0，1）內(nèi)產(chǎn)生8個(gè)不相同的隨機(jī)數(shù)作為編碼分類鍵例如隨機(jī)產(chǎn)生一個(gè)染色體 按照隨機(jī)數(shù)大小升序排列為 將的下標(biāo)表示為城市序號(hào)，則得到一個(gè)旅行路線：6，1，3，7，8，4，2，5。 （3）剩余序號(hào)編碼法[1]

7、 設(shè)n個(gè)城市的序號(hào)分別為，我們稱其為固有標(biāo)識(shí)序號(hào)，如果在n個(gè)城市中刪除幾個(gè)城市后，需要對(duì)剩余城市重新賦予序號(hào)，新的序號(hào)應(yīng)遵循原固有標(biāo)識(shí)序號(hào)的排列次序，稱其為剩余序號(hào)。例如8個(gè)城市 刪除城市，則剩余的5個(gè)城市的序號(hào)分別為，城市D的固有序號(hào)為4，在刪除后，它的剩余序號(hào)為3。 剩余序號(hào)的編碼方法為設(shè)n個(gè)城市的一個(gè)訪問路線次序?yàn)椋瑢?duì)于這個(gè)訪問路線，產(chǎn)生一個(gè)染色體，其中，它是在n個(gè)城市中刪除后的剩余序號(hào)。 例如有8個(gè)城市的固有序號(hào)為，給出一個(gè)旅行路線，按照剩余序號(hào)定義，該旅行線路的編碼為 3.2 編碼的不足 對(duì)于序號(hào)排列編碼方法的最大不足是交換和突變的過程中容易產(chǎn)生不可行解；隨機(jī)數(shù)編碼

8、的不足之處是產(chǎn)生隨機(jī)數(shù)的過程中或者在交換突變過程中可能會(huì)使隨機(jī)數(shù)某些值相等，導(dǎo)致不能進(jìn)行排序。剩余序號(hào)發(fā)編碼法解決了以上幾個(gè)不足之處，但是剩余序號(hào)編碼在從編碼到實(shí)際路程順序轉(zhuǎn)換中稍顯繁瑣，而且沒有轉(zhuǎn)換成較為簡(jiǎn)單的二進(jìn)制編碼。 4. 空隙編碼法求解TSP問題 4.1 空隙編碼法 設(shè)n個(gè)城市，對(duì)于任意城市，定義之間的空隙為叫做的前向空隙；定義之間的空隙為叫做的后向空隙；特殊的，的前向空隙為，的后向空隙為。 例如有三個(gè)城市，它的空隙集為，城市與空隙的表現(xiàn)形式如下：

9、 空隙編碼法首先確定一個(gè)編碼順序，然后放置第一個(gè)城市，因?yàn)榉胖玫谝粋€(gè)城市的時(shí)候還沒有空隙，所以第一個(gè)城市不用編碼。但產(chǎn)生兩個(gè)空隙，分別為和，之后按照之前已經(jīng)確定的編碼順序?qū)⒌诙€(gè)城市放入上步產(chǎn)生的兩個(gè)空隙之一，如放入，記空隙的標(biāo)號(hào)0為第二個(gè)城市的編碼，定義其編碼為0，然后依次把城市插入空隙，直至完成。所得到的編碼序列即為一個(gè)利用空隙編碼法所得。 例如有7個(gè)城市，分別為，設(shè)定編碼順序?yàn)?，即先放置A，不需要編碼；之后放置B，假設(shè)B放置在A的前向空隙中，記編碼為0；C放置在A的后向空隙中，編碼為2；D放置在A的前向空隙中，編碼為1；E放置在C的后向空隙中，編碼為4；F放置在A的前向空隙中，編碼為

10、2；G放置在C的后向空隙中，編碼為5，編碼結(jié)束。所以，當(dāng)順序?yàn)闀r(shí)，編碼為。過程如下所示： 空隙0 空隙1 A 第一步： 放置A，不需要編碼 產(chǎn)生新空隙0，1 第二步： B A 空隙0 空隙1 空隙2

11、 看上圖，B放置在A的前向空隙 0上，產(chǎn)生新空隙0，1，2 B A C 空隙0 空隙1 空隙2 空隙3 第三步： 看上圖，C放置在A的后向空 隙2上，產(chǎn)

12、生新空隙0，1，2，3 第四步： . . . . . . 第五步： . . . . . . B D F A C E 空隙0 空隙1 空隙2 空隙3 空隙4 空隙5 空隙6 第六步： F放在A的前向空隙2上， 產(chǎn)生新

13、空隙0，1，2，3，4，5，6 B D F A C G E 第七步： 如上圖，G放在C的后向空隙 5上，編碼結(jié)束 4.2 空隙編碼法的二進(jìn)制表現(xiàn)形式 二進(jìn)制編碼方式對(duì)于初始群體的產(chǎn)生和交換突變運(yùn)算比較方便，結(jié)合空隙編碼法的編碼特點(diǎn)，導(dǎo)出基于空隙編碼

14、法編碼的二進(jìn)制表示形式。 針對(duì)上述例子，當(dāng)放置第一個(gè)城市A的時(shí)候，產(chǎn)生兩個(gè)空隙，當(dāng)放置第二個(gè)城市B的時(shí)候，產(chǎn)生三個(gè)空隙，所以，當(dāng)放置第n個(gè)城市的時(shí)候，產(chǎn)生個(gè)空隙。針對(duì)上述問題，可以得到如下表格。 表1 空隙編碼法二進(jìn)制表現(xiàn)形式依據(jù) 放置城市Vi后 A B C D E F 產(chǎn)生的空隙數(shù) 2 3 4 5 6 7 空隙標(biāo)號(hào)范圍 01 012 0123 01234 012345 0123456 二進(jìn)制位數(shù) 1 2 2 3 3 3 即當(dāng)放置城市D后，一共可以得到5個(gè)空隙，每個(gè)空隙從前到后的依次標(biāo)號(hào)為0，1，2，3

15、，4，用二進(jìn)制數(shù)表示0~4四個(gè)數(shù)需要用3位二進(jìn)制數(shù)。所以針對(duì)此問題，可以用一個(gè)14位的二進(jìn)制數(shù)對(duì)一個(gè)方案進(jìn)行編碼，第一位二進(jìn)制數(shù)表示B的空隙編碼法編碼，第2~3位二進(jìn)制數(shù)表示C的空隙編碼法編碼，第4~5位二進(jìn)制數(shù)表示D的空隙編碼法編碼，第6~8位二進(jìn)制數(shù)表示E的空隙編碼法編碼，第9~11位二進(jìn)制數(shù)表示F的空隙編碼法編碼，第12~14位二進(jìn)制數(shù)表示G的空隙編碼法編碼。 當(dāng)放置城市B后，空隙標(biāo)號(hào)為0，1，2，而兩位二進(jìn)制數(shù)表示的范圍為0~3，所以編碼的時(shí)候C的空隙編碼法編碼范圍為0~2，當(dāng)大于2的時(shí)候，人為的調(diào)整為2。即城市的空隙編碼法編碼范圍為，當(dāng)二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)時(shí)大于，令此數(shù)等于或等于

16、0。 4.3 空隙編碼法及其二進(jìn)制表現(xiàn)形式的初始群體產(chǎn)生方法 （1） 空隙編碼法 由表1可知，當(dāng)放置城市之后，產(chǎn)生的空隙標(biāo)號(hào)范圍為，對(duì)于一個(gè)空隙編碼法編碼,的范圍為。所以可以按照此種規(guī)格產(chǎn)生任意符合條件的初始群體。 （2） 空隙編碼法的二進(jìn)制表現(xiàn)形式 因?yàn)榭障毒幋a法的二進(jìn)制表現(xiàn)形式產(chǎn)生的二進(jìn)制數(shù)可能超過空隙標(biāo)號(hào)范圍，所以用空隙編碼法的二進(jìn)制表現(xiàn)形式產(chǎn)生初始群體的時(shí)候按照以下幾個(gè)步驟： a.產(chǎn)生符合實(shí)際問題位數(shù)的二進(jìn)制數(shù) b.按實(shí)際問題對(duì)二進(jìn)制數(shù)進(jìn)行位數(shù)劃分，看每個(gè)劃分區(qū)間是否滿足該區(qū)間的空隙標(biāo)號(hào)的最大標(biāo)號(hào)范圍，如果不滿足，丟棄此染色體。 4.4 空隙編碼

17、法及其二進(jìn)制表現(xiàn)形式的交換方法 （1） 空隙編碼法 對(duì)于空隙編碼法編碼，其交換方式可以采用節(jié)段交換，單點(diǎn)或者多點(diǎn)都可以，但是要保證只有對(duì)應(yīng)位的空隙編碼法編碼可以交換。如取交換點(diǎn)在第三位，則從第四位可以開始交換，得到 （2） 空隙編碼法的二進(jìn)制表現(xiàn)形式 對(duì)于空隙編碼法的二進(jìn)制表現(xiàn)形式，交換的方法可以使用任何二進(jìn)制編碼的交換方式，但是空隙編碼法的二進(jìn)制表現(xiàn)形式可能產(chǎn)生某個(gè)區(qū)間的最大數(shù)超過該區(qū)間空隙標(biāo)號(hào)的最大范圍，對(duì)于這種情況，使超過空隙標(biāo)號(hào)范圍的區(qū)間重置為該區(qū)間空隙標(biāo)號(hào)的最大數(shù)或最小數(shù)。 4.5 空隙編碼法

18、及其二進(jìn)制表現(xiàn)形式的突變方法 （1）空隙編碼法 空隙編碼法編碼的突變方式可以單點(diǎn)突變和多點(diǎn)突變，只要保證空隙編碼法編碼突變點(diǎn)的突變范圍在該點(diǎn)允許的范圍即可。 （2）空隙編碼法的二進(jìn)制表現(xiàn)形式 空隙編碼法的二進(jìn)制表現(xiàn)形式的突變方法可以采用二進(jìn)制編碼的任何突變方法，只是突變之后檢查每個(gè)區(qū)間的范圍是否滿足該區(qū)間的范圍條件，如果不滿足，重置該區(qū)間為該區(qū)間允許的最大范圍或最小范圍。 5. 算例分析 假設(shè)有A，B，C，D，E五個(gè)城市，每個(gè)城市之間的距離如下表所示： 表2 各個(gè)城市之間距離表 城市/距離 A B C D E A 0 3 4 3 5 B 3

19、0 6 5 10 C 4 6 0 8 6 D 3 5 8 0 9 E 5 10 6 9 0 用基于空隙編碼法和空隙編碼法的二進(jìn)制表現(xiàn)形式編碼法的遺傳算法解決此問題。 5.1 基于空隙編碼法編碼方式的遺傳算法 初始群體的選擇，交換概率和突變概率的選擇對(duì)于實(shí)際問題會(huì)產(chǎn)生很大的影響，本題為TSP問題中的一個(gè)很小規(guī)模的路徑選舉，所以本題中選取交換概率，突變概率，交換方法選為節(jié)段交換，突變方法選為單點(diǎn)突變。 （1）產(chǎn)生初始群體 默認(rèn)編碼順序?yàn)锳，B，C，D，E隨機(jī)產(chǎn)生四個(gè)初始個(gè)體 （2）定義適應(yīng)度為經(jīng)過此路徑的權(quán)重和的倒數(shù)。

20、 （3）復(fù)制適應(yīng)度高的個(gè)體，淘汰適應(yīng)度低的個(gè)體，即為復(fù)制淘汰，新群體為 （4）交換操作，因?yàn)榻粨Q概率為，即與交換，與交換。采用節(jié)段交換，可以隨機(jī)產(chǎn)生一個(gè)位置，比如產(chǎn)生的數(shù)為2，即從第三位開始進(jìn)行節(jié)段交換。 至此產(chǎn)生四個(gè)新個(gè)體，分別為。 （5）突變操作，群體個(gè)數(shù)為4，個(gè)體長(zhǎng)度為4，突變概率為，采用單點(diǎn)突變，即系統(tǒng)隨機(jī)選取三個(gè)個(gè)體，每個(gè)個(gè)體突變一位。得到突變后的新個(gè)體為 （6）重復(fù)上述步驟，直到找到最優(yōu)解。在實(shí)際問題中，也可

21、以規(guī)定算法的代數(shù)為終止條件。 5.2 基于空隙編碼法二進(jìn)制表現(xiàn)方法的遺傳算法 對(duì)于此方法，選取交換概率為，突變概率為，初始群體為4。采用默認(rèn)編碼順序A，B，C，D，E，根據(jù)此問題，可由8個(gè)二進(jìn)制數(shù)表示一個(gè)染色體的編碼，其中第1位表示B的編碼，第2~3位表示C的編碼，第4~5位表示D的編碼，第6~8位表示E的編碼。 （1）產(chǎn)生初始群體 產(chǎn)生四個(gè)初始群體，分別為 計(jì)算個(gè)體每個(gè)區(qū)間是否超過最大空隙標(biāo)號(hào)的允許范圍，可知=（1，1，1，1，0，1，0，0）在C的空隙編碼法編碼（1，1）超過該區(qū)間空隙標(biāo)號(hào)的允許范圍（該區(qū)間空隙標(biāo)號(hào)范圍為0，1，2），刪除染色體，重新生成一個(gè)染色體=（1，0，

22、1，1，0，1，0，0），所以產(chǎn)生的初始群體為 （2）定義適應(yīng)度為經(jīng)過此路徑的權(quán)重和的倒數(shù)。 （3）復(fù)制適應(yīng)度高的個(gè)體，淘汰適應(yīng)度低的個(gè)體，即為復(fù)制淘汰，新群體為 （4）交換操作，因?yàn)榻粨Q概率為，即與交換，與交換。采用節(jié)段交換，可以隨機(jī)產(chǎn)生一個(gè)位置，比如產(chǎn)生的數(shù)為3，即從第四位開始進(jìn)行節(jié)段交換。 （5）突變操作，群體個(gè)數(shù)為4，個(gè)體長(zhǎng)度為8，突變概率，采用單點(diǎn)突變，即系統(tǒng)隨機(jī)選取三個(gè)個(gè)體。若每個(gè)個(gè)體突變的位置相同，則使突變后

23、產(chǎn)生的個(gè)體在某個(gè)區(qū)域超出該區(qū)域允許范圍的概率增大，所以突變采用每個(gè)個(gè)體不同位置的突變。 =（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） 檢查每個(gè)區(qū)域的允許范圍，可以發(fā)現(xiàn)=（0，1，1，1，1，1，0，0）在C的空隙編碼法區(qū)域編碼（1，1）超出該區(qū)域空隙標(biāo)號(hào)的允許范圍（該區(qū)間空隙標(biāo)號(hào)范圍為0，1，2），將其超出允許范圍的部分重置為（0，0），即=（0，0，0，1，1，1，0，0）。所以突變后的新個(gè)體為 =（0，0，0，1，1，1，0，0）

24、 =（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）重復(fù)上述步驟，直到找到最優(yōu)解。在實(shí)際問題中，也可以規(guī)定算法的代數(shù)為終止條件。 6. 總結(jié) 本文通過采用空隙編碼法對(duì)TSP問題進(jìn)行編碼，成功的解決了其他一些TSP問題編碼方法所產(chǎn)生的不足，并通過空隙編碼法的特點(diǎn)成功的給出了TSP的問題的二進(jìn)制編碼方式，通過重新定義二進(jìn)制編碼的交換和突變方法，使TSP問題的解決方法更加完善。同時(shí)對(duì)于二進(jìn)制編碼的交換和突變方法還應(yīng)該有更加優(yōu)于本文的方法，在實(shí)際的應(yīng)用中，讀者可以加入自己的方法，使問題的解法更加完善。

25、 參考文獻(xiàn) [1] 郭嗣琮.《信息科學(xué)中的軟計(jì)算方法》[M]，沈陽(yáng)：東北大學(xué)出版社，2001。 [2] 田景文，高美娟.《人工神經(jīng)網(wǎng)絡(luò)算法研究與應(yīng)用》[M]，北京：北京理工大學(xué)出版社，2006。 [3] 周培德.《算法設(shè)計(jì)與分析》[M]，北京：清華大學(xué)出版社，2005。 [4] 張文修，梁怡.《遺傳算法的數(shù)學(xué)基礎(chǔ)》[M]，西安：西安交通大學(xué)出版社，2006。 [5] 李敏強(qiáng),寇紀(jì)淞,林丹,李書全.《遺傳算法的基本理論與應(yīng)用》[M]，北京：科學(xué)出版社，2004。 Gap-coded genetic algorithms b

26、ased on TSP Problem Zhang Qian，Liu Hongxing，Xu Ling Department of Basic Science, Liaoning Technical University, Fuxin 123000 Abstract This 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

27、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 c

28、oding 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