基于hga的最小旅行時間多旅行商問題研究
周輝仁1，唐萬生1，魏穎輝2
（1天津大學系統工程研究所，天津300072;2遼寧科技學院管理系，遼寧本溪117022）
摘 要：為了解決最小化旅行時間的多旅行商一類問題，提出了一種遞階遺傳算法和矩陣解碼方法。該算法根據問題的特點，采用一種遞階編碼方案，此編碼與多旅行商問題一一對應。用遞階遺傳算法優化多旅行商問題不需設計專門的遺傳算子，操作簡單，并且解碼方法適于求解距離矩陣對稱和距離矩陣非對稱的多旅行商問題。計算結果表明，遞階遺傳算法是有效的，能適用于優化最小化完成時間的多旅行商問題。
關鍵詞：遞階遺傳算法；多旅行商問題；最小完成時間；解碼方法
中圖分類號：tp 27 文獻標識碼ia
1引 言
旅行商問題( tsp)是一個典型的組合優化難題，它在許多領域都有著廣泛的應用，已被證明屬于np問題jij。有關tsp問題的研究在現實問題中有很大的使用價值。諸如：交通運輸、管道鋪設、路線的選擇、計算機網絡的拓撲設計、郵遞員送信等，都可抽象成tsp或mtsp問題[2-5]。為了有效地解決最小旅行時間、距離矩陣對稱或者非對稱的多旅行商問題，本文提出了一種遞階遺傳算法和矩陣解碼方法，以便確定每個城市由哪個旅行商經過以及各個旅行商的行走路線，即找到一個****旅行商分配及行走路線，在各旅行商行走完后，使耗用時間****的那個旅行商的時間最小。仿真結果證明，本文提出的算法魯棒性好、運行效率高，具有實際應用的價值。
2 mtsp數學模型
所謂tsp問題是指：有ⅳ個城市，要求旅行商到達每個城市各一次，且僅一次，并回到起點，且要求旅行路線最短。而多路旅行商問題( mtsp)是指m個旅行商從同一個城市（或不同城市）出發，分別走一條旅行路線，使得每個城市有且僅有一個旅行商經過（出發城市除外），且總路程最短。
以點0表示旅行商的出發城市，稱為源點，點l…，z表示m個旅行商需訪問的城市。
定義變量：
約束條件為
式中，s為支路消去約束，即消去構成不完整路線的解，具體方法可參見文獻[6]。
在該模型中，式(1)表示使m個旅行商中的旅行時間****的那個最小化；式(2)表示各個旅行商的耗用時間；式(3)表示從指定城市o出發，所有城市只有某一個旅行商嚴格訪問一次；式(4)表示任一條弧的終點城市僅有一個起點城市與之相連；式(5)表示任一條弧的起點城市僅有一個終點城市與之相連；式(6)表示消去構成不完整線路的解。
3遞階遺傳算法
在生物學領域，染色體的結構是一系列基因按層次排列而成的，一些基因控制著另一些基因。染色體可表示為包括控制基因和參數基因的遞階結構，參數基因處于****級，控制基因處于上級，下級基因串受上級基因的控制。在基因編碼時，控制基因常采用整數編碼，不同整數信息表示對應的基因處于不同的激活狀態，而與該基因相聯系的低級基因申則處于對應的狀態。為計算方便和加強遺傳算法在解空間的搜索能力，參數基因采用實數編碼，每個基因用一個實數代表。這樣定義染色體結構的遺傳算法稱為遞階遺傳算法，它比傳統遺傳算法包含更多的信息，因而能處理更復雜的問題。目前，遞階遺傳算法已在神經網絡、模糊系統、車間調度等得到了較好的應用。
4遞階遺傳算法設計
基于多旅行商問題的特點，可以設計成二級遞階染色體結構描述多旅行商問題的結構和參數，控制基因中的每一個等位基因表示城市，參數基因中的每一個等位基因表示所路過的旅行商。對于給定問題，其控制基因和參數基因個數是確定的，都為城市個數，控制基因取值為1至(z—1)中互相等的整數，參數基因取值為1至m中的整數，m為旅行商個數，因此優化多旅行商問題只需確定基因信息。
|
