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

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

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