簇類(lèi)特征城市群間的TSP問(wèn)題研究

王 興

(武漢科技大學(xué)信息科學(xué)與工程學(xué)院，湖北 武漢 430081)

0 引言

旅行商問(wèn)題(traveling salesman problem，TSP)是指尋求N個(gè)城市間遍歷所有城市的最短路徑。該問(wèn)題是一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，所有的路線組合數(shù)為(N-1)!/2。當(dāng)遍歷的城市數(shù)不斷增加，其搜索空間隨著城市數(shù)N的增大而迅速增大，并且遍歷所有城市所需時(shí)間為問(wèn)題規(guī)模的指數(shù)階時(shí)間。針對(duì)該問(wèn)題已經(jīng)提出了多種有效算法，如最近鄰居法、貪婪算法、集群算法等［1－2］。由于群體規(guī)模較大，需要對(duì)較多的個(gè)體進(jìn)行大量的遺傳和演化操作，從而使得演化運(yùn)算過(guò)程進(jìn)展緩慢，難以達(dá)到相應(yīng)的計(jì)算速度要求。

現(xiàn)實(shí)生活中，許多城市在地域上的分布經(jīng)常呈現(xiàn)區(qū)域特征，所以在尋求最優(yōu)路徑時(shí)，應(yīng)首先提取城市的遍布特征，以相應(yīng)地減少全局搜索最優(yōu)解的盲目性;然后再配合使用一些優(yōu)化算法的組合，從而大量節(jié)省最優(yōu)解的尋解時(shí)間。

本文基于上述思想，提出了一種基于平衡聚類(lèi)的TSP演化算法。

1 聚類(lèi)算法

根據(jù)同類(lèi)數(shù)據(jù)集應(yīng)具有相近特性，而不同數(shù)據(jù)集在這些特性上差異較大的假定，將所研究的數(shù)據(jù)集進(jìn)行分類(lèi)，這種研究方法稱(chēng)為聚類(lèi)［3－4］。聚類(lèi)是數(shù)據(jù)挖掘、模式識(shí)別等研究方向的重要研究?jī)?nèi)容之一，傳統(tǒng)的聚類(lèi)算法在識(shí)別數(shù)據(jù)的內(nèi)在結(jié)構(gòu)方面往往指導(dǎo)性不強(qiáng)，從而導(dǎo)致聚類(lèi)算法效率過(guò)低。本文為了加強(qiáng)聚類(lèi)的收斂速度，在使用傳統(tǒng)的聚類(lèi)算法前，采用城市群稀疏度初提取的方法為以后的聚類(lèi)提供相應(yīng)指導(dǎo)。

1.1 城市群稀疏度的提取

隨著當(dāng)今衛(wèi)星航拍技術(shù)的發(fā)展，可以很輕易地得到分布在各個(gè)地區(qū)的貨物配送城市的地圖。這些地圖是提取城市群稀疏度最后的依據(jù)。城市群稀疏度提取的步驟具體如下。

首先將這些貨物配送城市的地理位置量化成具有二維屬性的數(shù)據(jù)空間S=S1×S2。將每維空間均勻地劃分為p份，則共有p×p個(gè)單元網(wǎng)格。所有代表城市的二維地理分布特征數(shù)據(jù)點(diǎn)將遍布在這p×p個(gè)單元網(wǎng)格中。

然后計(jì)算每一個(gè)單元網(wǎng)格的城市分布稀疏度ρ=nij/N(其中nij為第i行j列的單元網(wǎng)格，N為總城市數(shù)量)。與此同時(shí)，確定網(wǎng)格密度的閾值，網(wǎng)格單元的密度閾值參數(shù)在很大程度上影響算法的聚類(lèi)質(zhì)量。在此選取平均密度作為閾值，具體平均密度求解為:

式中:ρij為非空網(wǎng)格密度;M為非空單元網(wǎng)格數(shù)。

最后，判別每一非空單元網(wǎng)格的稀疏性。當(dāng)某一單元網(wǎng)格的密度時(shí)，則判定該單元網(wǎng)格為過(guò)稀疏網(wǎng)格;當(dāng)時(shí)，則判定該單元網(wǎng)格為稀疏網(wǎng)格;當(dāng)時(shí)，則判定該單元網(wǎng)格為密集網(wǎng)格;當(dāng)時(shí)，則判定該單元網(wǎng)格為過(guò)密網(wǎng)格。

1.2 K-均值聚類(lèi)

K-均值算法是一種得到廣泛使用的聚類(lèi)算法［4］。它是將各個(gè)聚類(lèi)子集內(nèi)的所有數(shù)據(jù)樣本的均值作為該聚類(lèi)的代表點(diǎn)。算法的主要思想是通過(guò)迭代過(guò)程，將數(shù)據(jù)集劃分為不同的類(lèi)別，使評(píng)價(jià)聚類(lèi)性能的準(zhǔn)則函數(shù)達(dá)到最優(yōu)，從而使生成的每個(gè)聚類(lèi)類(lèi)內(nèi)緊湊，類(lèi)間獨(dú)立。

K-均值算法描述如下。

①為每個(gè)聚類(lèi)確定一個(gè)初始聚類(lèi)中心，這樣就有K個(gè)初始聚類(lèi)中心。

②將樣本集中的樣本按照最小距離原則分配到最鄰近聚類(lèi)。

③將每個(gè)聚類(lèi)中的樣本均值作為新的聚類(lèi)中心。

④重復(fù)步驟②～步驟③，直到聚類(lèi)中心不再變化。

⑤結(jié)束，得到K個(gè)聚類(lèi)。

1.3 平衡聚類(lèi)算法

根據(jù)K-均值聚類(lèi)的算法原理可知，一旦當(dāng)聚類(lèi)的樣本點(diǎn)過(guò)多，算法的迭代次數(shù)就迅速增加。因此，可以通過(guò)提前學(xué)習(xí)，提取樣本分布特征來(lái)指導(dǎo)K-均值聚類(lèi)，使其成為一種有監(jiān)督的聚類(lèi)算法。在此提出平衡聚類(lèi)算法。

平衡聚類(lèi)算法的主要思想是以每一個(gè)非空單元網(wǎng)格為基準(zhǔn)，在其8-鄰域內(nèi)開(kāi)通連通區(qū)間。若其8-鄰域內(nèi)存在非空單元網(wǎng)格，則將其連通，并且以新連通的單元網(wǎng)格為基準(zhǔn)，開(kāi)辟新的連通區(qū)間直致無(wú)法開(kāi)辟新的連通區(qū)域?yàn)橹?。此外，若最終形成的連通域的邊緣存在過(guò)密或過(guò)稀的單元網(wǎng)格，將影響到聚類(lèi)中心的預(yù)選取，因此將游離該單元網(wǎng)格;若最終形成了K個(gè)連通域，將K值作為接下來(lái)K-均值聚類(lèi)的類(lèi)簇?cái)?shù)，并計(jì)算每個(gè)連通域的城市分布均值，將其作為K-均值聚類(lèi)的初始聚類(lèi)中心。

2 免疫遺傳算法

傳統(tǒng)的遺傳算法［5－8］是一種具有“生成 +檢測(cè)”的迭代過(guò)程的搜索算法。從理論上分析，迭代過(guò)程中，在保留上一代最佳個(gè)體的前提下，遺傳算法是全局收斂的［9］。然而，在對(duì)算法的實(shí)施過(guò)程中不難發(fā)現(xiàn)，兩個(gè)主要遺傳算法是模擬生物體的免疫系統(tǒng)算子，其都是在一定發(fā)生概率的條件下，隨機(jī)地、沒(méi)有指導(dǎo)地迭代搜索，因此它們?cè)跒槿后w中的個(gè)體提供了進(jìn)化機(jī)會(huì)的同時(shí)，也不可避免地產(chǎn)生了退化現(xiàn)象。在某些情況下，這種退化現(xiàn)象還相當(dāng)明顯。每一個(gè)待求的實(shí)際問(wèn)題都會(huì)有自身一些基本的、顯而易見(jiàn)的特征信息或知識(shí)。遺傳算法的交叉和變異算子卻相對(duì)固定，在求解問(wèn)題時(shí)，可變的靈活程度較小。這對(duì)算法的通用性無(wú)疑是有益的，但卻忽視了問(wèn)題的特征信息對(duì)求解問(wèn)題時(shí)的輔助作用，特別是在求解一些復(fù)雜問(wèn)題時(shí)，這種“忽視”所帶來(lái)的損失往往就比較明顯了。

針對(duì)這些問(wèn)題，提出一種新的算法——免疫遺傳算法(immune genetic algorithm，IGA)［10］。該算法借鑒生物免疫系統(tǒng)的自適應(yīng)識(shí)別和排除侵入機(jī)體的抗原性異物等性能，將生物免疫系統(tǒng)的學(xué)習(xí)、記憶、多樣性和識(shí)別的特點(diǎn)引入遺傳算法。在保留遺傳算法優(yōu)良特性的前提下，該算法力圖有選擇、有目的地利用待求問(wèn)題中的一些特征信息或知識(shí)，以抑制其優(yōu)化過(guò)程中出現(xiàn)的退化現(xiàn)象。

2.1 免疫算子

本文所提出的免疫思想主要是在合理提取疫苗的基礎(chǔ)上，通過(guò)接種疫苗和免疫選擇兩個(gè)操作步驟來(lái)完成的。前者是為了提高適應(yīng)度，后者則為了防止群體的退化。

①接種疫苗

設(shè)個(gè)體x，給其接種疫苗是指按照先驗(yàn)知識(shí)來(lái)修改x的某些基因位上的基因，使所得個(gè)體以較大的概率具有更高的適應(yīng)度。首先考慮以下兩種特殊情況:其一，若個(gè)體y的每一基因位上的信息都是錯(cuò)誤的，即每一位碼都與最佳個(gè)體不同，則對(duì)任一個(gè)體x，其轉(zhuǎn)移為y的概率為0;其二，若個(gè)體x的每個(gè)基因位都是正確的，即x已經(jīng)是最佳個(gè)體，則下一代個(gè)體將完全復(fù)制上一代的最佳個(gè)體基因。此外，設(shè)有群體c=(x1，x2，…，xn0)，對(duì) c 接種疫苗是指在c中按比例a隨機(jī)抽取na=an(0＜a≤1)個(gè)個(gè)體而進(jìn)行的操作。疫苗是從對(duì)問(wèn)題的先驗(yàn)知識(shí)中提煉出來(lái)的，它所包含的信息量及其準(zhǔn)確性對(duì)算法的性能起著重要的作用。

②免疫選擇

這一操作分兩步完成。第一步是免疫檢測(cè)，即對(duì)接種了疫苗的個(gè)體進(jìn)行檢測(cè)，若其適應(yīng)度仍不如父代，說(shuō)明在交叉、變異的過(guò)程中出現(xiàn)了嚴(yán)重的退化現(xiàn)象。這時(shí)該個(gè)體將被父代中所對(duì)應(yīng)的個(gè)體所取代;如果子代適應(yīng)度優(yōu)于父代，則進(jìn)行第二步處理。第二步是退

式中:f(xi)為個(gè)體xi的適應(yīng)度;{Tk}為趨近于0的溫度控制序列。

2.2 免疫遺傳算法

免疫遺傳算法流程如圖1所示?；疬x擇，即在目前的子代群體Ek=(x1，…，xn0)中以概率P(xi)選擇個(gè)體xi進(jìn)入新的父代群體。

圖1 免疫遺傳算法流程圖Fig.1 Flowchart of the immune genetic algorithm

3 城市群間貨物配送算例

城市群間貨物配送時(shí)的路徑選擇問(wèn)題是一個(gè)難解問(wèn)題，可以使用演化算法求解。當(dāng)節(jié)點(diǎn)很多時(shí)，使用演化算法則不可避免地要解決計(jì)算速度慢、求解成功率低等問(wèn)題。

本文提出的基于平衡聚類(lèi)的免疫遺傳算法大體上分為兩個(gè)階段:第一階段是要將所有的城市按照地理分布情況聚成K類(lèi)，并找出類(lèi)與類(lèi)間相隔最近的點(diǎn);第二階段是在已聚成的類(lèi)中采用免疫遺傳算法尋求類(lèi)中的最短城市路徑。具體介紹如下。

第一階段:采用平衡聚類(lèi)將樣本城市聚類(lèi)，此處取城市數(shù)量為50，聚類(lèi)數(shù)為3。聚類(lèi)后找出類(lèi)間最短距離，即找到兩類(lèi)間相聚最近的兩點(diǎn)。類(lèi)間最短路徑如圖2所示。

圖2 類(lèi)間最短路徑Fig.2 The shortest route among clusters

第二階段:在已聚成的每一個(gè)類(lèi)中用免疫遺傳算法尋求最短路徑。此處取類(lèi)一為例。在確定了首尾城市后，即類(lèi)一城市群的路線為{c1，…，c2}。根據(jù)先驗(yàn)知識(shí)抽取免疫疫苗，類(lèi)一中相鄰較近的城市組有(c4，c12)、(c23，c9)、(c42，c18)及(c13，c6)，其示意如圖 3 所示。因此，經(jīng)免疫遺傳算法后類(lèi)一的路徑為{c1，…，c4，c12，…，c23，c9，…，c42，c18，…，c13，c6，…，c2}。以此類(lèi)推其他幾類(lèi)內(nèi)部城市路徑，最終得出所有城市的路徑，其示意圖如圖4所示。

4 算法仿真

采用 CHN144數(shù)據(jù)，在 Core 2 GHz、0.99 GB 內(nèi)存的計(jì)算機(jī)上，分別進(jìn)行傳統(tǒng)遺傳算法及基于平衡聚類(lèi)的免疫遺傳算法的仿真。將兩種算法分別仿真5次，每次仿真得到最優(yōu)解的時(shí)間如表1所示。

表1 數(shù)據(jù)仿真結(jié)果Tab.1 Simulation result

從表1可知，經(jīng)5次仿真后，傳統(tǒng)遺傳算法在尋求到最優(yōu)解時(shí)所耗的平均時(shí)間為27.59 s，而本文算法平均時(shí)間為6.9 s。因此，在具有簇類(lèi)特征的城市群間尋求最短路徑問(wèn)題上，基于平衡聚類(lèi)的免疫遺傳算法的收斂速度較傳統(tǒng)的遺傳算法提高了近3倍。

5 結(jié)束語(yǔ)

本文通過(guò)聚類(lèi)與免疫遺傳算法的結(jié)合，不僅在具有簇類(lèi)特征的城市群貨物配送路徑選擇問(wèn)題上加快了算法的收斂速度，而且還在遺傳算法的基礎(chǔ)上，增加了多樣性保持、免疫記憶和免疫選擇的機(jī)制，這樣能使算法收斂速度更快，而多樣性的保持增強(qiáng)了算法全局搜索能力。通過(guò)對(duì)CHN144數(shù)據(jù)的試驗(yàn)后，證明了本文的基于平衡聚類(lèi)的免疫遺傳算法的可行性，尤其對(duì)于具有明顯稠密度的地理分布的大樣本數(shù)據(jù)，算法的收斂速度較傳統(tǒng)的優(yōu)化算法有更顯著的提高。

［1］熊盛武，李程俊.基于機(jī)群的求解TSP問(wèn)題的分布式演化算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2003，24(6):959 －961.

［2］劉宏兵，熊盛武.基于模糊C-均值聚類(lèi)的TSP演化算法［J］.計(jì)算機(jī)工程與應(yīng)用，2006(8):32－27.

［3］Sun Y，Lu Y.A scalable grid-based clustering algorithm for very large spatial databases［C］//Proceeding of the International Conference on Computational Intelligence and Security，2006:763 －768.

［4］米源，楊燕，李天瑞.基于密度網(wǎng)格的數(shù)據(jù)流聚類(lèi)算法［J］.計(jì)算機(jī)科學(xué)，2011(12):54－59.

［5］Huang Z.Extensions to the k-means algorithm for clustering large data sets with categorical values［J］.Data Mining and Knowledge Discovery II，1998(2):283 － 304.

［6］陳國(guó)良，王煦法，莊鎮(zhèn)泉，等.遺傳算法及其應(yīng)用［M］.北京:人民郵電出版社，1996.

［7］周明，孫樹(shù)棟.遺傳算法原理及其應(yīng)用［M］.北京:國(guó)防工業(yè)出版社，1996.

［8］莉維茨.演化程序—遺傳算法和數(shù)據(jù)編碼的結(jié)合［M］.北京:科學(xué)出版社，2000.

［9］Rudolph G.Convergence analysis of canonical genetic algorithms［J］.IEEE Transactions on Neural Networks，1994，5(1):96 －101.

［10］蔡自興，龔濤.免疫算法研究的進(jìn)展［J］.控制與決策，2004(8):18－23.