基于遺傳算法的多旅行商問題研究
2009-01-01 00:00:00王海龍周輝仁鄭丕諤唐萬生
計算機應用研究 2009年5期
（天津大學 系統工程研究所 天津 300072）
摘 要：針對所有旅行商路徑總和最小為優化標準的多旅行商一類問題，用遺傳算法優化，并提出了矩陣解碼方法。對距離非對稱的多旅行商問題的實例進行了仿真，并對不同交叉算子性能進行了比較。結果表明，該算法是有效的，適用于距離對稱和非對稱的多旅行商問題求解。
關鍵詞：遺傳算法； 多旅行商問題； 優化； 解碼方法
中圖分類號：TP301.6; TP18文獻標志碼：A
文章編號：1001-3695(2009)05-1726-03
Study on multiple traveling salesman problem based on genetic algorithm
WANG Hailong ZHOU Huiren ZHENG Pie TANG Wansheng
(Institute of Systems Engineering Tianjin University Tianjin 300072 China)
Abstract:In order to solve MTSP（multiple traveling salesman problem) that employed totalpathshortest as the evaluating rule this paper used genetic algorithmto optimize it and proposed decoding method with matrix. Simulated asymmetric multiple traveling salesman problems using the different crossover operators. The results suggest that this method is efficient. It is fit for solving symmetric and asymmetric multiple traveling salesman problems.
Key words：genetic algorithm; multiple traveling salesman problem; optimization; decoding method
0 引言
旅行商問題（traveling salesman problem TSP）是一個典型的組合優化難題，它在許多領域都有著廣泛的應用，已被證明屬于NP問題[1]。TSP是指：有N個城市，要求旅行商到達每個城市各一次且僅一次，并回到起點，且要求旅行路線最短。而多旅行商問題（MTSP）是指M個旅行商從同一個城市（或不同城市）出發，分別走一條旅行路線，使得每個城市有且僅有一個旅行商經過（出發城市除外）且總路程最短。有關TSP的研究在現實問題中有很大的使用價值，交通運輸、管道敷設、路線的選擇、計算機網絡的拓撲設計、郵遞員送信等均可抽象成TSP或MTSP[2~5]。
美國Michigan大學的Holland教授提出的遺傳算法（genetic algorithm，GA）是求解復雜的組合優化問題的有效方法，其思想來自于達爾文進化論和門德爾松遺傳學說，它模擬生物進化過程以從龐大的搜索空間中篩選出較優秀的解，是一種高效而且具有強魯棒性方法。因此，遺傳算法在求解TSP和MTSP中得到了廣泛的應用。目前，用遺傳算法求解MTSP大都是距離對稱的MTSP，一般通過附加虛擬城市的方法將MTSP轉換為TSP[5，6]。為了有效地解決所有旅行商的路程最小及距離對稱或非對稱的MTSP，本文用遺傳算法進行優化，通過附加虛擬代號的方法將MTSP轉換為TSP，并且提出了矩陣解碼方法，以便確定每個城市由哪個旅行商經過以及各個旅行商的行走路線，即找到一個最優旅行商分配及行走路線，在各旅行商行走完后，使旅行商路程總和最小。仿真結果證明，本文提出的算法是有效的。
1 多旅行商問題數學模型
以點0表示旅行商的出發城市，稱為源點，點1，…，l表示m個旅行商需要訪問的城市。
定義變量：
在該模型中，式（1）表示使m個旅行商的路程總和最小；式（2）表示各個旅行商的路程；式（3）表示從指定城市0出發，所有城市只有某一個旅行商嚴格訪問一次；式（4）表示任一條弧的終點城市僅有一個起點城市與之相連；式（5）表示任一條弧的起點城市僅有一個終點城市與之相連；式（6）表示消去構成不完整線路的解。
2 遺傳算法設計
將遺傳算法應用于MTSP中的關鍵是采用有效的編碼方式以及適當的解碼方法。遺傳算法對種群重復地進行選擇、交叉、變異等基本遺傳操作，不斷產生出比父代更適應環境的新一代種群，直到滿足要求條件為止。
2.1 個體編碼
假設點0表示旅行商的出發城市，稱為源點，點1，…，l表示m個旅行商需訪問的城市。基于多旅行商問題的特點，用遺傳算法求解MTSP時，可通過附加m-1個虛擬符號的方法將MTSP轉換為TSP。這m-1個虛擬符號分別為l+1，…，l+m-1。在旅行商訪問路徑中出現的每一個虛擬符號均表示旅行商返回出發城市0，從而組成一個回路。每個回路表示MTSP中一個旅行商的訪問路徑。需要注意的是，為了避免出現平凡子路徑，必須假設C00=M，M為一無窮大的正數。
如城市為0，1，…，8且三個旅行商的MTSP的一條染色體編碼為
25739410186
在初始種群或種群的操作運算過程中，可能會出現虛擬符號在一條染色體的兩端及其虛擬符號緊連兩種情況。如染色體出現的第一種情況：
95732410186
則三個旅行商的路徑分別表示為
由于設定了C00=M，M為一無窮大的正數，三個旅行商中路徑的最大值為M。由于是使路程最大的那個旅行商的路程最小，在種群選擇復制過程這樣的染色體會逐漸被淘汰。
如染色體出現的第二種情況：
則三個旅行商的路徑分別表示為
如第一種情況所述，這樣的染色體在種群選擇復制過程也會逐漸被淘汰。
2.2 群體規模選擇
合適的群體規模對遺傳算法的收斂具有重要意義。群體太小難以求得滿意的結果，群體太大則計算復雜。根據經驗，群體規模一般取10～160。
2.3 適值函數
遺傳算法在進行選擇操作時會出現欺騙問題[7]。在遺傳進化的初期，通常會產生一些超常的個體，若按照比例選擇法，這些異常個體因競爭力太突出而控制了選擇過程，影響算法的全局優化性能；在遺傳進化的后期，即算法接近收斂時，由于種群中個體適值差異較小時，繼續優化的潛能降低，可能獲得某個局部最優解。適值函數設計不當有可能造成這種問題的出現。
由于優化目標為最小化總路程，令目標函數作指數變換得到適值函數：
f=α exp(-β×Z)（7）
其中：α、 β為正實數。
2.4 選擇
選擇是用來確定重組或交叉個體，以及備選個體將產生多少個子代個體。選擇的第一步是計算適值，采用按比例的適值分配，是利用比例于各個個體適值的概率決定其子孫的遺留可能性。若某個個體i，其適值為fi，則其被選擇的概率表示為
Pi=fi/∑Mk=1fk（8）
然后對各個染色體計算它們的累積概率：
qi=∑Mi=1pi（9）
第二步用輪盤賭選擇法進行選擇。為了選擇交配個體，需要進行多輪選擇，每一輪產生一個[0，1]均勻隨機數，將該隨機數作為選擇指針來確定備選個體。
2.5 交叉與變異
交叉在遺傳操作中起核心作用，交叉概率較大可增強遺傳算法開辟新搜索空間的能力，但性能好的基因串遭到破壞的可能性較大，算法收斂速度降低，且不穩定；若交叉概率較小，則遺傳算法搜索可能陷入遲鈍狀態。對于MTSP，染色體交叉可以采用基于路徑表示部分匹配交叉（partially matched crossover，PMX）、順序交叉（ordered crossover，OX）和循環交叉（cycle crossover，CX）等[7]。
PMX是Goldberg等人于1985年針對TSP提出的基于路徑表示的交叉操作。部分匹配交叉操作要求隨機選取兩個交叉點，以便確定一個匹配段，根據兩個父個體中兩個交叉點之間的中間段給出的影射關系生成兩個子個體。OX是Davis等人于1985年針對TSP提出的基于路徑表示的交叉操作 該操作能保留排列并融合不同排列的有序結構單元。兩個父體交叉時，通過選擇父個體1的一部分，保存父體2中代碼的相對順序生成子個體。CX是Oliver等人針對TSP提出的交叉操作，循環交叉操作中子個體中的代碼順序是根據任一父個體產生。變異在遺傳操作中屬于輔助性的搜索操作，主要目的是維持群體的多樣性。較低的變異概率可以防止群體中重要的單一基因丟失，但降低了遺傳算法開辟新搜索空間的能力；較高的變異概率將使遺傳操作趨于純粹的隨機搜索，降低了算法的收斂速度和穩定性。對于MTSP，染色體變異可以采用交換變異，即交換兩個隨機位置上的基因。
2.6 解碼
由于該問題為八個旅行城市，城市之間的距離矩陣為8×8的矩陣，設該矩陣為D。由于是增加虛擬符號而不是增加虛擬城市，這里矩陣D不是10×10的矩陣。為了避免出現000的行走路徑，在D中，將城市0與城市0的距離設為很大的數，取值為10 000。這里，先設矩陣D為對稱距離矩陣，對于非對稱距離矩陣下面的解碼方法同樣適用。矩陣D如下所示：
在應用計算機具體編程時可采用如下解碼步驟：
a）由旅行商1的訪問路徑可得
x061=1;x671=1;x701=1
因此，旅行商1的可達矩陣為
同理，旅行商2、3的可達矩陣分別為
b）每個旅行商的行走路程。對于旅行商1，將可達矩陣X1與矩陣D點乘得到矩陣D1，矩陣D1中不為0的數值之和即為旅行商1所訪問城市的路程。設旅行商1、2、3所訪問城市的路程分別為z1、z2、z3。
z1=18+22+21=61
同理可得
z2=9+14+13=36； z3=8+21+13+11=53
c）求得所有旅行商的行走路程：
Z=z1+z2+z3=150
3 實例仿真
以上介紹了遺傳算法優化MTSP的步驟，本章通過TSPLIB中的距離非對稱的數據進行仿真和對不同的交叉算子進行比較。
3.1 17個城市（br17.atsp）的MTSP
br17.atsp數據總共有17個城市，并且其距離是非對稱的。設旅行商數為3，進行仿真。
這里，對于染色體分別采用循環交叉、順序交叉和部分匹配交叉。交叉概率為0.75；變異采用交換變異且變異概率為0.25；種群規模為100；最大迭代次數為200。用MATLAB語言編程，隨機運行10次，所得結果如表1所示。
表1 br17.atsp的仿真結果
操作最優解最差解平均解
CX446049.2
OX425547.2
PMX425547.9
所求的一個最優解路線分別為
16716155498171；
111131023141；
1121。
本實例是一個小規模的MTSP，通過表1的數據可以看出，在上述參數設定情況下，所求的最優結果是42，交叉算子在最優解、最差解和平均解方面采用順序交叉算子相對要優于循環交叉、部分匹配交叉算子，結果相對最差的交叉算子為循環交叉。
3.2 124個城市（kro124p）的MTSP
kro124p數據總共有100個城市，并且其距離是非對稱的。設旅行商數分別為4、8、12，進行仿真。
這里，對于染色體分別采用循環交叉、順序交叉和部分匹配交叉。交叉概率為0.75；變異采用交換變異且變異概率為0.25；種群規模為100；最大迭代次數為800。用MATLAB語言編程，旅行商數分別為4、8、12時各隨機運行10次，所得結果如表2所示。
表2 kro124p的仿真結果
本實例是一個大規模的MTSP，從表2可以看出，在上述參數設定情況下，交叉算子在最優解、最差解和平均解方面采用順序交叉算子相對要優于循環交叉、部分匹配交叉算子，結果相對較差的交叉算子為循環交叉。
4 結束語
本文對最小化所有旅行商路程最大值的多旅行商問題應用遺傳算法進行了研究，并提出一種矩陣解碼
