蟻群算法、遺傳算法及微粒群算法在TSP中的對(duì)比研究

張宇 姚海霞 唐丹洋 鐘曉娟 蔡燕 內(nèi)江師范學(xué)院物理與電子信息工程學(xué)院

引言

旅行者問題，旨在解決最優(yōu)路線，是一個(gè)經(jīng)典的路徑優(yōu)化問題。TSP是指一個(gè)旅行商為了去N個(gè)不同的城市，需要去每一個(gè)城市，只去一次，然后回到原來的城市，形成一個(gè)圈，從許多可能的路徑中找出最短的路徑。TSP是一種組合優(yōu)化問題，具有廣泛的實(shí)際背景和應(yīng)用價(jià)值，可應(yīng)用于監(jiān)測(cè)山體險(xiǎn)情的無線傳感器網(wǎng)絡(luò)系統(tǒng)的設(shè)計(jì)，解決傳統(tǒng)監(jiān)測(cè)方法中精度有限、能耗高等問題，實(shí)現(xiàn)數(shù)據(jù)采集量大，精度高、低功耗和可靠性高等優(yōu)點(diǎn)。

由于旅行商問題具有重要的現(xiàn)實(shí)意義，相應(yīng)地提出了求解旅行商問題的算法。最早的解決方案是線性規(guī)劃，后來產(chǎn)生了多種算法來解決旅行者問題。其中，它大致可分為精確算法、近似算法和智能算法。但是，近年來，出現(xiàn)了許多新的智能算法，如粒子群算法、蟻群算法和遺傳算法。

1 TSP模型

TSP從其描述上來講是很簡單的一個(gè)問題，給定n個(gè)城市和各個(gè)城市間的距離，尋找到一條遍歷n個(gè)城市且各個(gè)城市只被訪問一次的路徑，并使得總路徑距離越短越好.其數(shù)學(xué)描述如下：

設(shè) G=(V，E)為賦權(quán)圖，V={1，2，…，n}為頂點(diǎn)集，E為邊集，各頂點(diǎn)距離為Cij，已知Cij＞0，且 i，j∈ V，并設(shè)定

那么整個(gè)TSP問題的數(shù)學(xué)模型表示如下：

式中，k屬于V的全部非空子集；|k|屬于集合k中包含圖G的全部頂點(diǎn)的個(gè)數(shù)。

2 蟻群算法

2.1 蟻群算法基本原理

蟻群算法（aca）是學(xué)習(xí)螞蟻通過釋放信息素覓食的模擬進(jìn)化算法，最初是由m.dorigo等人提出的。蟻群算法是生物界常用的求解最優(yōu)路徑的算法，它利用了螞蟻的覓食特點(diǎn)。通過觀察，我們發(fā)現(xiàn)螞蟻在覓食的過程中總會(huì)找到最短最優(yōu)的路徑。研究發(fā)現(xiàn)，螞蟻在覓食過程中會(huì)分泌出一種揮發(fā)性物質(zhì)。路徑越短，阻塞越少，覓食越快，揮發(fā)性物質(zhì)越少，信息源濃度越高，這種最優(yōu)路徑形成的就越快。

2.2 蟻群算法求解TSP的數(shù)學(xué)模型

一般來說，城市的數(shù)目是n，所有蟻群的數(shù)量是m，城市i和j之間的距離是 dij(i，j=1，2，…，n)，t時(shí)刻城市i和 j連接路徑上的信息素濃度是相同的。螞蟻k(k=1，2，...m）按照城市間連接路徑上信息素的濃度確定下一個(gè)要到達(dá)的城市，用Pijk(t)表示到達(dá)下一個(gè)城市的幾率，公式表示為：

3 遺傳算法

3.1 遺傳算法基本原理

遺傳算法類似于自然進(jìn)化，是模擬達(dá)爾文的自然選擇和自然生物進(jìn)化理論的計(jì)算模型。通過作用于染色體上的基因?qū)ふ液玫娜旧w來求解問題。與自然界相似，遺傳算法對(duì)求解問題的本身無所知，它所需要的僅是對(duì)算法所產(chǎn)生的每個(gè)染色體進(jìn)行評(píng)價(jià)，并基于適應(yīng)值來選擇染色體，使適應(yīng)性好的染色體有更多的繁殖機(jī)會(huì)。在遺傳算法中，通過隨機(jī)方式產(chǎn)生若干個(gè)所求解問題的數(shù)字編碼，即染色體，形成初始群體。通過適應(yīng)度函數(shù)給每個(gè)個(gè)體個(gè)數(shù)值評(píng)價(jià)，淘汰低適應(yīng)度的個(gè)體。選擇高適應(yīng)度的個(gè)體參加遺傳操作，經(jīng)過遺傳操作后的個(gè)體集合形成下一代新的種群。模擬生命的進(jìn)化一代一代一代地演化，直到滿足最后的期望條件。

3.2 遺傳算法求解TSP的數(shù)學(xué)模型

針對(duì)該問題，構(gòu)造一個(gè)選擇因子，其通過對(duì)可選節(jié)點(diǎn)集中節(jié)點(diǎn)的計(jì)算，盡量選擇靠近終點(diǎn)方向的節(jié)點(diǎn)，節(jié)約時(shí)間與資源。由于節(jié)點(diǎn)靠近終點(diǎn)的方向和高程值無關(guān)，在此僅考慮節(jié)點(diǎn)的橫、縱坐標(biāo)計(jì)算選擇因子。當(dāng)前節(jié)點(diǎn)用qi表示，Ui為qj可選節(jié)點(diǎn)集，m為Ui中節(jié)點(diǎn)的數(shù)量，qj∈Ui，用Gij表示從qi通往終點(diǎn)時(shí)途經(jīng)qj的選擇因子，計(jì)算公式如下：

在進(jìn)行節(jié)點(diǎn)選擇時(shí)，分別計(jì)算可選節(jié)點(diǎn)集中各節(jié)點(diǎn)的選擇因子，以其中每個(gè)節(jié)點(diǎn)選擇因子的值作為其抽樣概率，使用輪盤賭方式進(jìn)行下一節(jié)點(diǎn)的選擇。當(dāng)節(jié)點(diǎn)接近終點(diǎn)時(shí)，其選擇因子的值越大，被選擇的幾率就越大。

4 微粒群算法

4.1 微粒群算法基本原理

微粒群算法，又稱粒子群優(yōu)化(Particle Swarm Optimization，PSO)，是由J.Kennedy 和 R.C.Eberhart等于1995年開發(fā)的一種演化計(jì)算技術(shù)，來源于對(duì)一個(gè)簡化社會(huì)模型的模擬。根據(jù)對(duì)環(huán)境的適應(yīng)度將群體中的個(gè)體移動(dòng)到好的區(qū)域。然而它不對(duì)個(gè)體使用演化算法，而是將每個(gè)個(gè)體看作是D維搜索空間中的一個(gè)沒有體積的微粒（點(diǎn)），在搜索空間中以一定的速度飛行，這個(gè)速度根據(jù)它本身的飛行經(jīng)驗(yàn)和同伴的飛行經(jīng)驗(yàn)來動(dòng)態(tài)調(diào)整。PSO算法屬于進(jìn)化算法的一種，和遺傳算法相似，它也是從隨機(jī)解出發(fā)，通過迭代尋找最優(yōu)解，這種算法以其實(shí)現(xiàn)容易、精度高、收斂快等優(yōu)點(diǎn)引起了學(xué)術(shù)界的重視，并且在解決實(shí)際問題中展示了其優(yōu)越性。

4.2 微粒群算法算法求解TSP的數(shù)學(xué)模型

設(shè)城市的個(gè)數(shù)為 n，X=(x1，x2，...xn )表示相應(yīng)問題的解序列，即表示粒子在解空間中的位置。定義交換子SO(i1，i2)為節(jié)點(diǎn) xi1，xi2的交換，則 X’＝X＋SO(i1，i2)定義為解 X 經(jīng)算子SO(i1，i2)作用后的新解。交換子的有序集合定義為交換序，記為S ＝ (SO1，SO2，...SOn)，其 中 SO1，SO2，...SOn是 交 換 子。交 換 序在位置X上的作用定義為交換子依次作用于X，即X＝X＋S＝[(X+SO1)+SO2]+...+SOk]。不同的交換序作用于同一解上可能產(chǎn)生相同的新解，有相同效果的交換序稱為等價(jià)交換序。若干個(gè)交換序可合并成一個(gè)新的交換序，定義為兩個(gè)交換序的合并算子，設(shè)交換序SO1和SO2按照先后順序作用于解X上，得到新解X’。假設(shè)另外有一個(gè)交換序SO′作用于X到相同的解X’，即X＋SO′＝X＋()，也就是說SO′和屬于同一等價(jià)集。在交換序等價(jià)集中，擁有最少交換子的交換序稱為該等價(jià)集的基本交換序。定義位置X與位置Y的減法為速度V，即X-Y=VX=Y+V，V是一基本交換序，速度V1與速度V2的加法和定義為等價(jià)的基本交換序。速度的倍數(shù)CV定義為integer(c)個(gè)V相加，再與V的前integer((c-integer(c))k)個(gè)交換子求和，其中k為V中交換子的個(gè)數(shù)，integer(c)為向下取整函數(shù)。用于求解TSP的粒子群算法模型為：

5 分析比較

表一 三種算法指標(biāo)對(duì)比

6 總結(jié)

通過查找各種文獻(xiàn)資料比較發(fā)現(xiàn)，蟻群算法與遺傳算法和粒子群算法相比，該算法的計(jì)算結(jié)果更為精確，平均傳輸時(shí)延基本相似，但網(wǎng)絡(luò)的平均能耗有明顯提高。此外，蟻群算法具有可靠性高、適應(yīng)性強(qiáng)、精確度高等優(yōu)點(diǎn)。蟻群優(yōu)化算法的自組織性、動(dòng)態(tài)性和多徑性使其特別適合于無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)路由選擇。相對(duì)比于遺傳算法和微粒群算法，蟻群算法更適合于監(jiān)測(cè)山體險(xiǎn)情的無線傳感器網(wǎng)絡(luò)的設(shè)計(jì)。