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