基于TSP問(wèn)題的仿生算法比較

文/劉云飛

1 引言

TSP問(wèn)題自1759年被歐拉提出來(lái)后，一直成為一個(gè)困擾著數(shù)學(xué)界的難題。TSP問(wèn)題是一個(gè)組合優(yōu)化的問(wèn)題，本身具有NPC計(jì)算復(fù)雜性，因?yàn)樵谟?jì)算機(jī)出現(xiàn)之前的數(shù)學(xué)計(jì)算比較復(fù)雜，人們可用于解決TSP問(wèn)題的工具較為落后，TSP問(wèn)題的精確結(jié)果僅僅局限于小規(guī)模數(shù)據(jù)。隨著計(jì)算機(jī)計(jì)算的發(fā)展，計(jì)算量已經(jīng)不再是困擾TSP問(wèn)題求解難度的主要因素，可用于求解TSP問(wèn)題的算法增速劇烈，但是每種算法的精確度都具有一定的差別。參考文獻(xiàn)[1]中作者對(duì)現(xiàn)今求解TSP問(wèn)題的算法進(jìn)行分類，分為仿生算法和非仿生算法，并通過(guò)實(shí)驗(yàn)比較兩種算法的求解精確度，最終發(fā)現(xiàn)對(duì)規(guī)模不大的TSP問(wèn)題，仿生算法和非仿生算法的計(jì)算準(zhǔn)確度相差不大，但是在問(wèn)題規(guī)模很大時(shí)，非仿生算法求解準(zhǔn)確度與仿生算法相去較大。本文將針對(duì)不同規(guī)模的TSP問(wèn)題，對(duì)常見(jiàn)的仿生算法進(jìn)行尋優(yōu)對(duì)比，尋找對(duì)TSP問(wèn)題求解較為敏感的仿生優(yōu)化算法。

2 TSP問(wèn)題簡(jiǎn)介

TSP問(wèn)題可以這樣描述：已知n 個(gè)城市各城市間的距離, 某一旅行商從某個(gè)城市出發(fā)訪問(wèn)每個(gè)城市一次且僅一次, 最后回到出發(fā)城市,怎樣安排才使其所走路線最短。

其數(shù)學(xué)模型可以表示為：

對(duì)于T個(gè)城市問(wèn)題，為每個(gè)城市進(jìn)行編號(hào)，假設(shè)m、n為任意兩個(gè)城市編號(hào)，0≤m≤T，0≤n≤T。kmn為城市m到城市n的距離，TSP問(wèn)題的實(shí)質(zhì)就是尋找一條最優(yōu)路徑，使得該路徑中每個(gè)城市遍歷一次，且路徑長(zhǎng)度最短。

目標(biāo)函數(shù)：minS=∑m≠nkmnxmn

3 TSP問(wèn)題求解算法簡(jiǎn)介-仿生算法

雖然仿生算法對(duì)求解TSP問(wèn)題結(jié)果較好，但是不同的仿生算法之間也有差別。在用仿生算法解決TSP問(wèn)題時(shí)，遺傳算法、免疫算法和蟻群算法是經(jīng)常被選用的，這三種智能算法在求解尋優(yōu)過(guò)程中分別具備各自的特點(diǎn)：

3.1 遺傳算法

遺傳算法（genetic algorithm GA）是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過(guò)程而形成的自適應(yīng)全局優(yōu)化搜索算法，它最早是由美國(guó)的J.H.Holland教授提出，該算法起始于20世紀(jì)60年代對(duì)自然和人工自適應(yīng)系統(tǒng)方面的研究。遺傳算法借鑒了達(dá)爾文的進(jìn)化論和孟德?tīng)柕倪z傳學(xué)說(shuō)，通過(guò)模擬自然界物種的進(jìn)化機(jī)制，在算法運(yùn)行過(guò)程中自動(dòng)獲取和積累有關(guān)搜索空間的數(shù)據(jù)，并自適應(yīng)的控制搜索過(guò)程以求得最優(yōu)解。

表1：burmal14（已知最優(yōu)路徑距離：30.8785）

表2：att48（已知最優(yōu)路徑距離：33522）

表3：kroA100（已知最優(yōu)路徑距離：21282）

遺傳算法是一種常用的優(yōu)化算法，編碼技術(shù)簡(jiǎn)單，遺傳操作易于理解，使用“適者生存”的原則，采用選擇、交叉和變異等操作，通過(guò)模擬自然界物種進(jìn)化原理，一代代的把“最優(yōu)個(gè)體”遺傳下去。該算法從種群中進(jìn)行選擇，搜索過(guò)程不受函數(shù)約束條件的限制，可以避免陷入局部次優(yōu)解以及保證算法的簡(jiǎn)易性。但是當(dāng)解決結(jié)構(gòu)復(fù)雜和搜索空間較大的優(yōu)化問(wèn)題時(shí)，該算法搜索時(shí)間比較長(zhǎng)，易出現(xiàn)早熟問(wèn)題。而且對(duì)初始種群的選擇很敏感，不同的初始種群的選取會(huì)直接影響解的質(zhì)量和算法效率。

3.2 免疫算法

最早的免疫系統(tǒng)模型是由Jerne于1973年提出的，他依據(jù)Burnet的克隆選擇學(xué)說(shuō)，開(kāi)創(chuàng)了獨(dú)特型網(wǎng)絡(luò)理論，給出了免疫系統(tǒng)的數(shù)學(xué)框架，并利用微分方程模型模擬了淋巴細(xì)胞的動(dòng)態(tài)變化。現(xiàn)實(shí)的生物免疫系統(tǒng)是一種復(fù)雜的自適應(yīng)系統(tǒng)，免疫系統(tǒng)能夠在病原體入侵人體時(shí)識(shí)別出病原體，并且產(chǎn)生針對(duì)該病原體的抗體，抗體可以將病原體消滅，并在消滅病原體后依然殘存在人體內(nèi)，當(dāng)同一種病原體再次入侵人體時(shí)，病原體會(huì)被體內(nèi)存留的抗體消滅，免疫系統(tǒng)的這種學(xué)習(xí)、記憶和模式識(shí)別的能力可用于解決科學(xué)和工程問(wèn)題。

與其它算法相比，免疫算法具有利用自身產(chǎn)生多樣性和維持機(jī)制的能力，可以確保種群的多樣性，這解決了一般尋優(yōu)過(guò)程中經(jīng)常出現(xiàn)的 “早熟”問(wèn)題，利于獲取全局最優(yōu)解。

3.3 蟻群算法

蟻群算法(Ant Colony Optimization, ACO)是由意大利學(xué)者M(jìn).Dorigo.V.Maniezzo和A.Colorni于20世紀(jì)90年代初通過(guò)模擬自然界中螞蟻集體尋徑行為而提出的一種基于種群的啟發(fā)式隨機(jī)搜索算法，該算法在智能理論研究領(lǐng)域具有重要地位。

螞蟻可以在沒(méi)有任何參照的情況下找到從巢到食物的最短路徑，并且可以在路徑被阻擋時(shí)自適應(yīng)地搜索到新的最短路徑。根本原因是螞蟻在尋找食物時(shí)可以在它們尋找的路徑上釋放一種特殊的分泌物——信息素。隨著時(shí)間的推移，信息素蒸發(fā)導(dǎo)致濃度降低，而在最短路徑上的螞蟻可以比其它路徑上的螞蟻更快地返回，提升路徑上的信息素濃度，從而形成一種正反饋機(jī)制。蟻群算法易于與其它算法相結(jié)合，具備求解復(fù)雜問(wèn)題的能力，但是由于前期解過(guò)多，造成蟻群算法搜索算法較慢。

4 實(shí)驗(yàn)結(jié)果對(duì)比

為了比較不同的仿生算法對(duì)TSP問(wèn)題求解的精確度，本文使用burmal14、att48和kroA100對(duì)不同的仿生算法進(jìn)行了實(shí)驗(yàn)，這三組實(shí)驗(yàn)數(shù)據(jù)來(lái)源TSPLIB[7]。實(shí)驗(yàn)環(huán)境 為：pc機(jī) -intel(R) Core(TM) i5-2450M CPU@2.50GHz，Windows7 64旗艦版。實(shí)驗(yàn)軟件為：MATLAB R2014b。實(shí)驗(yàn)結(jié)果如表1所示。

通過(guò)表2、表3分析實(shí)驗(yàn)結(jié)果，我們得出如下結(jié)論：

（1）對(duì)于小規(guī)模TSP問(wèn)題，如14個(gè)城市最短路徑問(wèn)題，遺傳算法、免疫算法和蟻群算法的尋優(yōu)能力都很強(qiáng)，幾乎每一次運(yùn)行都可尋找到最優(yōu)路徑。

（2）對(duì)于規(guī)模較大的TSP問(wèn)題，三種仿生算法的尋優(yōu)能力是有所差異的。由于遺傳算法全局搜索能力較強(qiáng)，因此在解決48個(gè)和100個(gè)城市最短路徑的問(wèn)題時(shí)，同樣10次的運(yùn)行結(jié)果，遺傳算法總是可以尋找到比其他兩種算法距離更短的路徑。但由于遺傳算法的每次尋優(yōu)具有一定的概率性，尋優(yōu)穩(wěn)定性的能力不如蟻群算法，這也導(dǎo)致它的平均路徑長(zhǎng)度與蟻群算法在相差不大情況下，標(biāo)準(zhǔn)誤差卻遠(yuǎn)遠(yuǎn)大于蟻群算法。

（3）通過(guò)實(shí)驗(yàn)數(shù)據(jù)對(duì)比，我們不難發(fā)現(xiàn)免疫算法在尋優(yōu)的過(guò)程中具有記憶性，每代的最短路徑會(huì)記錄下來(lái)，與下一代隨機(jī)生成的個(gè)體。

5 結(jié)語(yǔ)

通過(guò)本次實(shí)驗(yàn)，我們不難發(fā)現(xiàn)遺傳算法、免疫算法和蟻群算法在TSP問(wèn)題中各有優(yōu)缺點(diǎn)，遺傳算法的全局性保證了它尋優(yōu)結(jié)果的準(zhǔn)確性，蟻群算法的魯棒性保證了它尋優(yōu)結(jié)果的穩(wěn)定性。因此在大規(guī)模TSP問(wèn)題的尋優(yōu)中，我們應(yīng)該優(yōu)先考慮采用遺傳算法和蟻群算法的聯(lián)合尋優(yōu)，利用遺傳算法的隨機(jī)搜索、快速性和全局性產(chǎn)生TSP問(wèn)題所需的初始種群，然后，充分利用蟻群算法的并行性和正反饋機(jī)制來(lái)修正尋優(yōu)算法，提升尋優(yōu)算法的求解效率和求解精度，這種聯(lián)合尋優(yōu)算法不僅適用于TSP問(wèn)題，也可推廣至求解其它NP問(wèn)題。