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

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

引言

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

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

1 TSP模型

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

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

那么整個TSP問題的數學模型表示如下：

式中，k屬于V的全部非空子集；|k|屬于集合k中包含圖G的全部頂點的個數。

2 蟻群算法

2.1 蟻群算法基本原理

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

2.2 蟻群算法求解TSP的數學模型

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

3 遺傳算法

3.1 遺傳算法基本原理

遺傳算法類似于自然進化，是模擬達爾文的自然選擇和自然生物進化理論的計算模型。通過作用于染色體上的基因尋找好的染色體來求解問題。與自然界相似，遺傳算法對求解問題的本身無所知，它所需要的僅是對算法所產生的每個染色體進行評價，并基于適應值來選擇染色體，使適應性好的染色體有更多的繁殖機會。在遺傳算法中，通過隨機方式產生若干個所求解問題的數字編碼，即染色體，形成初始群體。通過適應度函數給每個個體個數值評價，淘汰低適應度的個體。選擇高適應度的個體參加遺傳操作，經過遺傳操作后的個體集合形成下一代新的種群。模擬生命的進化一代一代一代地演化，直到滿足最后的期望條件。

3.2 遺傳算法求解TSP的數學模型

針對該問題，構造一個選擇因子，其通過對可選節點集中節點的計算，盡量選擇靠近終點方向的節點，節約時間與資源。由于節點靠近終點的方向和高程值無關，在此僅考慮節點的橫、縱坐標計算選擇因子。當前節點用qi表示，Ui為qj可選節點集，m為Ui中節點的數量，qj∈Ui，用Gij表示從qi通往終點時途經qj的選擇因子，計算公式如下：

在進行節點選擇時，分別計算可選節點集中各節點的選擇因子，以其中每個節點選擇因子的值作為其抽樣概率，使用輪盤賭方式進行下一節點的選擇。當節點接近終點時，其選擇因子的值越大，被選擇的幾率就越大。

4 微粒群算法

4.1 微粒群算法基本原理

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

4.2 微粒群算法算法求解TSP的數學模型

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

5 分析比較

表一 三種算法指標對比

6 總結

通過查找各種文獻資料比較發現，蟻群算法與遺傳算法和粒子群算法相比，該算法的計算結果更為精確，平均傳輸時延基本相似，但網絡的平均能耗有明顯提高。此外，蟻群算法具有可靠性高、適應性強、精確度高等優點。蟻群優化算法的自組織性、動態性和多徑性使其特別適合于無線傳感器網絡中的節點路由選擇。相對比于遺傳算法和微粒群算法，蟻群算法更適合于監測山體險情的無線傳感器網絡的設計。