基于聚類的遺傳算法解決旅行商問題

基于聚類的遺傳算法解決旅行商問題摘要：遺傳算法〔GA〕是解決旅行商問題〔TSPs〕的有效方法，然而，傳統(tǒng)的遺傳算法〔CGA〕對大規(guī)模旅行商問題的求解效果較差。為了克服這個問題，本文提出了兩種基于聚類的改良的遺傳算法，以尋找TSPs的最正確結(jié)果。它的主要過程是聚類、組內(nèi)演進(jìn)和組間連接操作。聚類包括兩種方法來將大規(guī)模TSP劃分為假設(shè)干子問題，一種方法是k-均值〔k-means〕聚類算法，另一種是近鄰傳播〔AP〕聚類算法。每個子問題對應(yīng)于一個組。然后我們使用GA找出每個子問題的最短路徑長度。最后，我們設(shè)計一個有效的連接方法將所有這些組合成為一個，以得到問題的結(jié)果。我們嘗試在基準(zhǔn)實(shí)例上運(yùn)行一組實(shí)驗(yàn)，用來測試基于k-means聚類〔KGA〕和基于AP聚類〔APGA〕遺傳算法的性能。實(shí)驗(yàn)結(jié)果說明了它們有效性和高效的性能。將結(jié)果與其他聚類遺傳算法進(jìn)行比擬，說明KGA和APGA具有更強(qiáng)的競爭力和有效性。關(guān)鍵詞：大規(guī)模旅行商問題；遺傳算法；聚類；k-means聚類；AP聚類一、引言旅行商問題〔TSP〕是在所有城市搜索最短哈密爾頓路線的問題。TSP是眾所周知的NP-hard問題。它有許多現(xiàn)實(shí)世界的應(yīng)用[1,2]，如規(guī)劃調(diào)度、物流配送、計算機(jī)網(wǎng)絡(luò)和VLSI路由。近年來研究人員已經(jīng)研究了不同類型的TSP[3-6]。TSP問題可以用如下方式描述：有座城市，給出城市之間的距離矩陣為。TSP問題的要求是從所有路徑中找到最短路徑。如果被定義為在步驟中訪問的城市，那么路線可以被看作城市從1到的循環(huán)排列。路線的表達(dá)式如下：〔1〕如果對于，距離滿足，那么這種情況是對稱TSP。TSP可以模型化為加權(quán)圖。每個頂點(diǎn)代表一個城市，每個邊緣連接兩個城市。邊的權(quán)重表示兩個相連的城市之間的距離?，F(xiàn)在一個TSP問題實(shí)際上是一個哈密爾頓回路，最優(yōu)的TSP路徑是最短的哈密頓回路。用于求解TSP的算法可以概括為兩類，精確算法和啟發(fā)式算法。精確的算法確保最終解決方案是最優(yōu)的。分支切割算法是這一類中的典型例如[7,8]。這些算法的關(guān)鍵問題是它們相當(dāng)復(fù)雜，并且在計算機(jī)性能方面非常苛刻[9]。自引入模擬退火[10]和禁忌搜索[11]以來，啟發(fā)式算法有可能突破局限，從而找到路徑的局部最優(yōu)解。在過去的二十年中，提出了大量的自然啟發(fā)或群體智能方法，例如蟻群算法[12,13]，粒子群算法[14]和遺傳算法[15,16]來解決TSP問題。遺傳算法〔GA〕是一種通過模擬自然演化過程來搜索最優(yōu)解解決大規(guī)模搜索問題〔例如TSP問題〕的有效方法，GA的目的是通過幾個遺傳操作，如選擇、交叉和突變獲得大規(guī)模搜索問題的近似解。與其他精確搜索算法相比，其優(yōu)點(diǎn)主要是通過使用群體的信息而不是僅僅一個個體來實(shí)現(xiàn)搜索[5]。除了上述內(nèi)容之外，GA通過適應(yīng)度函數(shù)的數(shù)值來評估個體的質(zhì)量，減少當(dāng)使用啟發(fā)式算法時被浸入在局部最優(yōu)解中的風(fēng)險。雖然GA是解決TSPs的有效方法，但是，隨著旅行城市的數(shù)量增長，經(jīng)典遺傳算法效果較差。為了使TSP問題變得更容易并且可以有效地解決大規(guī)模TSP，本文提出了兩種改良的基于聚類的遺傳算法，分別稱為KGA和APGA。首先，KGA和APGA使用聚類方法將大規(guī)模TSP劃分為假設(shè)干子問題，每個子問題對應(yīng)于一個組。在KGA和APGA中分別采用k-means和AP聚類方法。然后，我們使用GA找到每個聚類的最短哈密頓回路。所有這些集群可以并行處理。最后，我們設(shè)計有效的連接方法將這幾個組合并為一個整體，以實(shí)現(xiàn)縮短整個路線的目的。本文的其余內(nèi)容以此方式描述：第二節(jié)提出了兩種聚類方法，包括k-means和近鄰傳播〔AP〕。第三節(jié)描述了基于k-means聚類〔KGA〕的遺傳算法和基于AP聚類〔APGA〕的遺傳算法。然后在第四局部，提供實(shí)驗(yàn)和比擬結(jié)果。最后，我們在第五節(jié)結(jié)束本文。二、聚類方法A、K-means聚類K-means是一種普遍的無監(jiān)督智能算法，由于其簡單性[17]，廣泛應(yīng)用于各種領(lǐng)域，如數(shù)據(jù)挖掘。這個想法是將一組樣本分成幾個組〔簇〕，其中每個對象具有類似于另一個對象的特征。我們選擇群集內(nèi)最遠(yuǎn)的距離并標(biāo)記它。該算法需要隨機(jī)地產(chǎn)生對聚類的個初始中心點(diǎn)的選擇。我們稱之為中心。首先，計算從每個對象到其他聚類中心的距離，并將所有對象劃分為距離最小的組。其次，根據(jù)上一步，重新計算每個集群中心。我們重復(fù)這兩個步驟，直到中心不再改變，以實(shí)現(xiàn)收斂穩(wěn)定。我們使用Euclidean距離來計算頂點(diǎn)和集群之間的距離。聚類的目的是優(yōu)化以下函數(shù)：(2)其中是聚類的數(shù)量，是頂點(diǎn)〔或城市〕的數(shù)量，是頂點(diǎn)的坐標(biāo)，是聚類的坐標(biāo)，是屬于聚類的頂點(diǎn)組。該算法可以通過在空間中移動聚類中心來獲得最短的平方距離。聚類的新中心根據(jù)分配給它的所有頂點(diǎn)不斷更新。計算聚類中心的公式如下：〔3〕其中是包含在簇中的頂點(diǎn)的數(shù)量。算法1給出了K-means聚類算法的偽代碼。1隨機(jī)設(shè)置K個集群中心;2repeat3for每個頂點(diǎn)do4計算每個聚類的距離度量;5將其分配給最近的組6end7重新計算聚類中心位置;8untilstopcriteriaaremet;算法1：K-Means的偽代碼B、AP聚類基于相似性度量的聚類方法已經(jīng)廣泛用于工程系統(tǒng)和科學(xué)數(shù)據(jù)分析中。聚類的一種常見方法是將數(shù)據(jù)分成幾個局部，并找到一組中心，以使數(shù)據(jù)點(diǎn)及其最接近的中心具有最小的平方誤差和。我們從所有實(shí)際存在數(shù)據(jù)點(diǎn)中選擇中心，并將它們命名為“樣本〞。K-Means聚類方法最初使用一組隨機(jī)選擇的樣本，然后迭代地優(yōu)化那些樣本，目的是降低平方誤差的和。K-Means聚類方法最初很容易選擇樣本，所以它總是需要用不同的初始化來優(yōu)化許屢次，并努力獲得更好的解決方案。因此，它僅在組的數(shù)量較少并且至少一個隨機(jī)初始解接近優(yōu)秀解的情況下表現(xiàn)很好。近鄰傳播〔AP〕與K-Means聚類非常不同[18]，它不需要在運(yùn)行算法之前人工設(shè)置聚類的數(shù)量。它將所有數(shù)據(jù)點(diǎn)視為同一時間的潛在樣本，并將其視為每個集群的代表。在AP中的數(shù)據(jù)點(diǎn)之間交換的消息有兩種類型。它交替地使用兩種消息傳遞步驟來更新兩個矩陣：“責(zé)任〞矩陣和“可用性〞矩陣，并且它們中的每一個考慮不同種類的競爭?？梢栽谌魏螘r間組合消息以從點(diǎn)中選擇樣本。“責(zé)任〞矩陣描述了點(diǎn)適合于點(diǎn)的程度，即從到的消息。“可用性〞描述點(diǎn)選擇點(diǎn)作為其聚類中心的程度，將消息從發(fā)送到。點(diǎn)應(yīng)當(dāng)是考慮來自其他相鄰點(diǎn)的支持的例如。和使用以下公式計算：〔4〕〔5〕其中，AP的詳細(xì)描述可參考[19,20]。三、基于聚類的遺傳算法本文提出了兩種改良的聚類遺傳算法，即基于K-means聚類〔KGA〕的遺傳算法和基于AP聚類〔APGA〕的遺傳算法，以有效地解決大規(guī)模TSP問題。首先，KGA和APGA使用聚類方法將大規(guī)模TSP轉(zhuǎn)換成幾個小的子問題，每個子問題對應(yīng)于一個組。在KGA和APGA中分別采用K-means聚類和AP聚類方法。然后，我們使用遺傳算法找到每個聚類的最短哈密頓回路。所有這些組可以并行處理。最后，以縮短整個旅行路線為目標(biāo)，我們設(shè)計了有效的連接方法，將所有組合并為一個整體。A.組內(nèi)演化組內(nèi)演化操作的目的是為每個組中的給定結(jié)點(diǎn)找到最短的哈密頓回路。遺傳算法是一個基于進(jìn)化論的有影響力的技術(shù)，如TSP的問題[21]。在每個組中執(zhí)行遺傳算法，旨在通過選擇、交叉和突變這幾個遺傳操作獲得近似解。與其他精確的傳統(tǒng)搜索算法相比，其優(yōu)點(diǎn)主要是使用循環(huán)群體的信息而不是僅僅一個循環(huán)來執(zhí)行搜索。

在組內(nèi)使用有序編碼方案。使用此方案，每個結(jié)點(diǎn)都被編號為從1到該群體結(jié)點(diǎn)總數(shù)量中的唯一整數(shù)。染色體是以整數(shù)排列，表示交通路徑。我們將組中結(jié)點(diǎn)的編號排列在基因片段上，染色體可以被認(rèn)為是所有基因片段的排列，并且每個基因片段代表組。每個聚類中使用的遺傳算法的過程如下：1隨機(jī)生成初始群體;2計算適宜度值并保存最小值;3repeat4選擇下一代的父母;5執(zhí)行交叉算子操作6執(zhí)行變異算子操作8untilstopcriteriaaremet;9輸出最正確途徑;所有這些集群可以并行處理。這一步的結(jié)果是將結(jié)點(diǎn)聚類為組。B.組間連接有效地解決TSP問題的目的是找到最短的旅行路線。在上一步中，我們獲得的是每個組中給定結(jié)點(diǎn)的最短哈密頓回路，然后在這一步我們需要考慮如何連接所有的組，并實(shí)現(xiàn)所有結(jié)點(diǎn)的連接。連接兩個組就是確定哪些路徑將從每個組中的最短哈密頓回路中刪除，以及哪些路徑將被連接以將兩個相鄰組組合成一個。假設(shè)，是與兩組最接近的結(jié)點(diǎn)，對于，與是與相鄰的兩個結(jié)點(diǎn)，同樣對于，和是與相鄰的兩個結(jié)點(diǎn)。給出和，為了連接兩個組為一個，我們需要選擇兩個結(jié)點(diǎn)、來刪除及連接邊緣。如何選擇它們，我們參考公式(1):(1)其中，。重復(fù)此過程，直到所有組被合并為一個整體，實(shí)現(xiàn)所有結(jié)點(diǎn)的連接。以上方案如圖1所示：圖1.組合集群的過程不同的組合中的組合序列將導(dǎo)致不同的交通布線路徑，尋找最短的路徑是我們的目的。因此，當(dāng)群體數(shù)量較大時，我們考慮設(shè)計一個修改的遺傳算法進(jìn)行整體優(yōu)化，以縮短整個交通路線。有序編碼方案也用于整體優(yōu)化。然而，不同于代表交通路徑的染色體，在這個過程中，我們在組之間梳理編碼序列。換句話說，我們需要優(yōu)化聚類的序列并找到最好的組合序列。在該序列之后，前兩個組被組合成一個，然后新生成的組與第三組組合……逐步完成。最后，所有這些組被合并成一個整體，并且得出最優(yōu)路徑。以上算法的整個過程如下：1Input一個軌道交通布線問題;2采用K-means或AP將軌道交通布線問題聚類為k個子問題；3For每個子問題,do:4repeat5選擇下一代的父母;6執(zhí)行交叉算子;7執(zhí)行變異算子;8untilstopcriteriaaremet;9Output子問題的哈密爾頓回路;10End11利用GA尋求最正確組合序列;12將所有這些哈密爾頓回路結(jié)合到最正確序列之后的一個整體路徑中;13Output最短路徑.四、實(shí)驗(yàn)在本節(jié)中，我們進(jìn)行廣泛的實(shí)驗(yàn)來評估KGA和APGA的有效性，其中KGA表示K-means聚類與遺傳算法的組合，APGA表示親和力增殖聚類與遺傳算法的組合。我們將它們應(yīng)用于來自TSPLIB[22]的標(biāo)準(zhǔn)測試實(shí)例，并比擬它們的性能。此外，在相同條件下，我們還將結(jié)果與通過經(jīng)典遺傳算法〔CGA〕和其他相關(guān)聚類遺傳算法獲得的結(jié)果進(jìn)行比擬。所提出的KGA和APGA對于每個測試實(shí)例獨(dú)立運(yùn)行20次。表I給出了20個獨(dú)立運(yùn)行的每個基準(zhǔn)問題和統(tǒng)計的實(shí)驗(yàn)結(jié)果，包括路線長度值的最正確值、平均值和標(biāo)準(zhǔn)偏差〔std〕。如表I所述，通過KGA獲得的平均值分別小于通過APGA獲得的對于att532，d657，rat783，u2319和pcb3038獲得的平均值，這說明KGA在這些測試問題上表現(xiàn)優(yōu)于APGA。同時，APGA在其他測試實(shí)例〔包括pcb442，u2152和rl5915〕上的性能優(yōu)于KGA。一般來說，KGA在優(yōu)化旅行路線方面表現(xiàn)與APGA類似或稍好一點(diǎn)。然而，K-means聚類對中心的初始選擇相當(dāng)敏感，并且聚類的數(shù)量需要預(yù)先設(shè)置。然后我們喜歡APGA來解決這種類型的TSP。表IKGA和APGA的比照問題最正確KGAAPGA平均值最小值標(biāo)準(zhǔn)偏差時間花費(fèi)(s)平均值最小值標(biāo)準(zhǔn)時間花費(fèi)(s)pcb4425077862129.161461.5279.35.061955.661946.2257.87.3rat57567737647.097820.56263.25.27814.357925.44156.24.6d6574891256785.356738.243.55.156801.556784.147.98.4rat78388069882.99822.044.66.69997.19934.739.610.7u21526425375689.375184.4297.419.575571.873825.21807.349.6u2319234256243336.3242605.5412.725.0245704.4249980.11066.568.9pcb3038137694159777.9159182.2906.795.2161086.5160284.71116.5133.6rl5915565530786908.3780619.97590.980.5656647.9619020.95895.5188.6此外，我們將所提出的KGA，APGA與其他相關(guān)工作，包括經(jīng)典遺傳算法〔CGA〕和兩級遺傳算法〔TLGA〕進(jìn)行比擬[3]。這四種算法的比擬示于表II中。通過CGA和TLGA獲得的實(shí)驗(yàn)結(jié)果從[3]中引用。除了進(jìn)化迭代的次數(shù)，其他參數(shù)是相同的。表II中的結(jié)果說明，在小的進(jìn)化迭代中，尤其是對于APGA，KGA和APGA的效果都比CGA和TLGA好得多。換句話說，在相同的其他參數(shù)下導(dǎo)出最正確游歷，KGA和APGA比CGA和TLGA需要更少的計算本錢。KGA和APGA是高效的。此外，APGA可以產(chǎn)生比其他三種算法更少迭代的更短的路線。圖2顯示了巡回長度與測試問題迭代次數(shù)的演變。在CGA方面，KGA和APGA顯示出比普通算法明顯的優(yōu)勢。APGA可以獲得更好的初始解決方案。這些結(jié)果說明，基于聚類的算法在迭代方面收斂比CGA快得多。換句話說，KGA和APGA需要比CGA更少的迭代來解決TSP。從圖2和表II中，我們可以得出結(jié)論，KGA和APGA比CGA更加有效，并且它們在有限時間內(nèi)對于大TSP獲得更合理的行程中表現(xiàn)良好。圖3繪制了KGA與不同的收斂。是組的數(shù)量。從圖中可以看出，隨著的增加，KGA的收斂速