王 興

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

0 引言

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

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

1 聚類算法

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

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

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

1.2 K-均值聚類

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

K-均值算法描述如下。

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

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

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

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

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

1.3 平衡聚類算法

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

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

2 免疫遺傳算法

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

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

2.1 免疫算子

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

①接種疫苗

設(shè)個(gè)體x，給其接種疫苗是指按照先驗(yàn)知識(shí)來修改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ì)問題的先驗(yàn)知識(shí)中提煉出來的，它所包含的信息量及其準(zhǔn)確性對(duì)算法的性能起著重要的作用。

②免疫選擇

這一操作分兩步完成。第一步是免疫檢測(cè)，即對(duì)接種了疫苗的個(gè)體進(jìn)行檢測(cè)，若其適應(yīng)度仍不如父代，說明在交叉、變異的過程中出現(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所示。火選擇，即在目前的子代群體Ek=(x1，…，xn0)中以概率P(xi)選擇個(gè)體xi進(jìn)入新的父代群體。

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

3 城市群間貨物配送算例

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

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

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

圖2 類間最短路徑Fig.2 The shortest route among clusters

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

4 算法仿真

采用 CHN144數(shù)據(jù)，在 Core 2 GHz、0.99 GB 內(nèi)存的計(jì)算機(jī)上，分別進(jìn)行傳統(tǒng)遺傳算法及基于平衡聚類的免疫遺傳算法的仿真。將兩種算法分別仿真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。因此，在具有簇類特征的城市群間尋求最短路徑問題上，基于平衡聚類的免疫遺傳算法的收斂速度較傳統(tǒng)的遺傳算法提高了近3倍。

5 結(jié)束語

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

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

［2］劉宏兵，熊盛武.基于模糊C-均值聚類的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ù)流聚類算法［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］周明，孫樹棟.遺傳算法原理及其應(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.