蟻群算法解決ＴＳＰ問題的淺析

摘要：介紹了一種求解復雜組合優(yōu)化問題的新的擬生態(tài)算法—蟻群算法。闡述了該算法的基本原理，以及蟻群算法在TSP問題上的應用，并提出了改進算法，使得算法有更好的全局性。

關鍵詞：蟻群算法；TSP；改進

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)22-724-02

Research on Ant Colony Algorithm for TSP

ZHU Jie

(Scool of Software，Tongji University，Shanghai 201804，China)

Abstract:Ant colony algorithm was a novel simulated ecosystem evolutionary algorithm. After introducing the essence of the ant colony algorithm.this paper its application in the complicated combinatorial opitimization problem such as TSP.Then suggested a improved ant colony algorithm to solve TSP problems more effiently.

Key words:ant colony algorithm;TSP; improved

1 引言

現實生產生活中有很多組合優(yōu)化問題，這類問題隨著規(guī)模的擴大，問題空間呈現組合爆炸的特征，大多數這類問題在多項式時間內無法求解，對這類問題的處理目前多用啟發(fā)式算法來求解。

旅行商(TSP)問題就是典型的組合優(yōu)化問題， 直觀地說，TSP問題就是指一位商人從自己的家鄉(xiāng)出發(fā)。希望能找到一條最短的路徑，途經給定的城市集合中的所有城市，最后返回家鄉(xiāng)。并且每個城市都被訪問一次且僅一次。上世紀50年代中期創(chuàng)立仿生學以來，人們不斷地從生物進化的機理中得到啟發(fā)，提出了許多用于解決復雜組合優(yōu)化問題的新方法，比如神經網絡、遺傳算法、模擬退火算法、進化規(guī)劃算法等，并成功應用于解決實際問題。但由于TSP屬于Np-難問題，在最差情況下精確性算法需要指數級的時間來尋找最優(yōu)解。時間代價太大了。近似算法就是尋求在相對較低的計算成本下．找到好的或接近最優(yōu)解的解答，但是算法不一定保證能夠找到最優(yōu)解。由意大利學者M.Dorigo，V.Maniezzo， A.Colomi于1992年首先提出的蟻群系統(tǒng)(AntColonySystem， ACS)是一種新生的仿生進化算法，適用于求解復雜組合優(yōu)化問題，在解決TSP問題方面取得了較為理想的效果。

2 螞群算法概述

蟻群算法是一種元啟發(fā)式算法，蟻群算法是一種受自然啟發(fā)的基于群體智能的算法。算法模型源于真實螞蟻群體搜尋食物的過程：智能螞蟻(算法中的人工螞蟻)模擬真實螞蟻從巢穴到食物所在地之間搜索最短路徑，在問題的解空間中搜索。螞蟻在覓食過程中通過釋放一種稱為信息素的物質相互傳遞信息。信息素痕跡參數是對這種行為的模擬。一般來說，信息素痕跡參數可以賦予點或邊(TSP中信息素值賦給點)。螞蟻們傾向于朝著信息素濃度高的方向前進，因此由大量螞蟻組成的蟻群的行為便表現出一種信息的正反饋現象，某一路徑上走過的螞蟻越多，則信息素濃度越高，后來者選擇該路徑的概率就越大。

3 基于蟻群算法的TSP求解

給定一個有n個城市的TSP問題，人工螞蟻的數量為m，每個人工螞蟻的行為符合下列規(guī)律：（1）根據路徑上的信息素濃度，以相應的概率來選取下一步路徑；（2）不再選取自己本次循環(huán)已經走過的路徑為下一步路徑，用一個數據結構來控制這一點；（3）當完成了一次循環(huán)后，根據整個路徑長度來釋放相應濃度的信息素，并更新走過的路徑上的信息素濃度。

3.1 蟻群算法的基本模型：

■ (1)

■表示螞蟻下一步允許選擇的城市。α表示外激素的相對重要性（α≥0 ），β表示啟發(fā)信息的相對重要性(β≥0 )。

隨著時間的推移，可能會出現兩種情況：1)先前留下的外激素逐漸消失；2)殘留的外激素過多，從而淹沒了啟發(fā)信息。為了避免這兩種情況，在每一只螞蟻從起點到達終點后，必須對殘留的外激素進行更新。用參數ρ(0≤ρ≤1)來表示外激素物質的保留率，則1-ρ就表示外激素的揮發(fā)率，經過m個時間單位后，螞蟻完成一次循環(huán)，各路徑上的信息量要根據以下式子作調整:

■

■

■表示在本次循環(huán)中留在路徑ij上的信息量，■表示螞蟻k在路段ij上留下的殘留外激素濃度。

■式中為dij為表示相鄰兩個城市間的距離。

3.2 蟻群算法的實現步驟如下

步驟1：初始化相關參數，如螞蟻的數目。

步驟2：將螞蟻隨機或均勻分布到各個城市。

步驟3：每只螞蟻通過訪問各個城市而形成一個解，并在訪問的過程中，將已訪問到的城市保留在i中。在城市i中每只螞蟻要從沒有訪問的城市中選擇訪問下一個城市j時須根據概率公式(1)進行選擇，如此循環(huán)，直到所有的螞蟻訪問完所有的城市。

步驟4：計算每只螞蟻行走的總路徑長度Lk，并保存最優(yōu)解。

3.3 算法設計思想

蟻群算法實現的關鍵是信息素的釋放和更新。以及螞蟻個體依據信息素進行路徑選擇的策略，在分析蟻群算法在后期容易陷入局部最優(yōu)解的原因后，不難發(fā)現這是由正反饋現象所引起的。在每次循環(huán)結束時，對信息素進行全局更新，從而增強了目前最優(yōu)路徑對螞蟻的”吸引力”。在TSP問題中應用蟻群算法進行求解最短路徑，在城市數量不多時，得出的結果是令人滿意的。在前期，這“吸引力”對算法起到了很好的加速作用。然而，它也會導致算法過早停滯。若單純地調低信息素的權重。會削弱正反饋的機制的作用，很難使信息素集中分布。螞蟻也就失去了選路的參照，退化為簡單的以路徑為參照的搜索。本算法改進的地方是對局部信息素和全局信息素進行了區(qū)分。采用不同的更新策略，根據發(fā)現解的情況動態(tài)地調整選擇概率．在加速收斂發(fā)現最優(yōu)和防止停滯之間找到平衡。在每次循環(huán)結束時，進行全局更新的信息素與螞蟻自己釋放的局部信息素不同。每次循環(huán)結束時，只有最優(yōu)螞蟻(找到目前最優(yōu)路徑的的螞蟻)才更新全局信息素，全局信息素用表示。而局部信息素是每只螞蟻在每移動一步后，都進行局部信息素的更新，螞蟻k從城市i移動到城市j的概率公式變?yōu)椋?/p>

■

τij(t)表示t時刻在城市i和城市j連線上的局部更新的信息素濃度，λij(t)表示t時刻在城市i和城市j連線上的全局更新的信息素濃度。α表示局部信息素τij的重要性，δ表示全局信息素λij的重要性， ρ是τ和λ的權重。

■

權重p是可變的，在[0，1]間取值。用于控制兩種信息素的比重。當發(fā)現更優(yōu)的解時，減少p的值以增加全局信息索的權重，從而有利于更快的發(fā)現其附近的解；若迭代多次而沒有發(fā)現新解，則增加P的值削弱全局信息素的權重，從而擴大搜索的范圍。

局部信息素的更新:■

Δτ為常數，信息素初始值。

全局信息素的更新：■

■，Cbs表示最優(yōu)螞蟻所走過的路徑長度。

4 結論

自蟻群算法提出來后，已經吸引了眾多研究者對該算法進行研究，并成功地將其運用在解決組合優(yōu)化問題上，如TSP，QAP(quadratic assignment problem)，JSP(job—shop scheduling problem)等。對于許多組合優(yōu)化問題，能夠用一個圖來闡述將要解決的問題；能定義一種正反饋過程如問題中的殘留信息；問題結構本身能夠提供解題用的啟發(fā)式信息；能夠建立約束機制：這些使用蟻群算法就能夠得到解決。由于蟻群算法具有信息正反饋和并行計算的特點，其求解能力要在一定程度上好于其它一些啟發(fā)式算法。但是蟻群算法也有一些不足之處，容易陷入局部最優(yōu)從而出現過早停滯是該算法的主要缺點。

最后，本文提出了一種改進的蟻群優(yōu)化算法，大膽引入了全局和局部信息素概念，采用了不同的更新策略和動態(tài)的路徑選擇概率．使得在搜索的中后期能更有效地發(fā)現全局最優(yōu)解。在前期加強全局信息素的作用，從而加速收斂；在中后期，逐漸削弱全局信息素在路徑選擇中的作用，達到擴大搜索區(qū)域的目的。

參考文獻：

[1] 陳宏建，陳峻，徐曉華，等.改進的增強型蟻群算法田[J].計算機工程，2005，31(2):176-178.

[2] Gutjahr W J.A graph-based An t System and its convergence[J].Future Generation Computer System，2000，16(8)，873-888.

[3] Liang G S，Chou，17 U，HAN T C.Cluster analysis based on fuzzy equivalence relation[J].European Journal of Operational Re·search，2005，166(1):160-171．

[4] Ai exy U，Verena S P，Wolfgang S H.，et a1.Cluster analysis of individuals with similar trends of fat intake during childhood and adolescence:a new approach to analyzing dietary data[J].Nutrition Research，2005，25(3):251，260．

[5] Arulampalam S.， Maskell S.， Gordon N.， et al. A tutorial on particle filters for on-linenon-linear/non-gaussian bayesian tracking[J].IEEE Transactions on Signal Processing， 2002，50(2):174-188.

[6] Mutapi F.， Mduluza T.，RODDAM A W．Cluster analysis of schistosome-specific an tibody responses artitions the population into distinct epidemiological groups[J].Immunology Letters，2005，96(2):231，240．

（上接第725頁）

[7] 段海濱．蟻群算法原理及其應用[M].北京:科學出版社，2005．

[8] 秦玲.蟻群算法的改進與應用[D].揚州:揚州大學，2004.

[9] Gendron B．Parallel computing in combinatorial optimization[M]．Pisa：[s.n]，2005．[10] D. Haehnel， W. Burgard， D. Fox， K.P. Fishkin， and M. Philipose， \"Mapping and localization with RFID technology，\" IEEE Int. Conf. Robotics and Automation， pp.1015–1020， 2004.

[10] Yuan H，Parrill A．Cluster analysis and three．Dimensional QSAR studies of HIV-1 integrase inhibitors[J]．Journal Of Molecu?lar Graphics and Modelling，2005，23(4):317，328．

[11] 胡小兵，黃席樾.對一類帶聚類特征TSP問題的蟻群算法求解[J].系統(tǒng)仿真學報，2004(9):2683-2686.

[12] 張宗永，孫靜，譚家華.蟻群算法的改進及其應用[J].上海交通大學報，2002，56(11):1 564-1 566．

[13] 馬良，項培軍.螞蟻算法在組合優(yōu)化中的應用[J].管理科學學報，2001，4(2):52-57.

[14] 段海濱，王道波.蟻群算法的全局收斂性研究及改進[J].系統(tǒng)工程與電子技術，2004，26(10):1506-1509.

[15] 李士勇.蟻群優(yōu)化算法及其應用研究進展[J].計算機側最與控制，2003，11(12):911-913.917.