宗澤宏

蟻群算法（ACA）作為一種仿生進(jìn)化算法，現(xiàn)多應(yīng)用于優(yōu)化領(lǐng)域。它是通過對自然界螞蟻的尋徑方式進(jìn)行仿真分析之后而獲得一種隨機(jī)搜索方法，該方法可用于處理組合優(yōu)化問題。在本文，在對該算法的基本原理進(jìn)行介紹之后，對數(shù)學(xué)模型的構(gòu)建以及算法的進(jìn)一步優(yōu)化進(jìn)行闡釋，最后對其應(yīng)用前景予以預(yù)測。

【關(guān)鍵詞】蟻群算法 仿生進(jìn)化 隨機(jī)搜索

1 引言

在信息量不斷擴(kuò)大的今天，數(shù)據(jù)挖掘技術(shù)所具有的優(yōu)良性能開始凸現(xiàn)。數(shù)據(jù)挖掘技術(shù)的改進(jìn)與優(yōu)化有利于幫助我們從大規(guī)模數(shù)據(jù)中篩選出有用的信息與應(yīng)用模式。對于數(shù)據(jù)挖掘技術(shù)而言，探尋一種更高效的算法是改進(jìn)與優(yōu)化此技術(shù)的核心。

1991年，意大利著名研究學(xué)者M(jìn).Dorigo率先提出了一種新型仿生算法ACA，也就是本文所研究的蟻群算法。在對螞蟻的一系列行為進(jìn)行深入研究之后提出了其基本原理并構(gòu)建了相應(yīng)的數(shù)學(xué)模型——蟻群算法，之后將其用于獲得旅行商問題（TSP）的解釋。

2 蟻群算法的原理

ACA是通過深入研究螞蟻行為而形成的一種自然算法。該算法最突出的特征是螞蟻會通過“信息素” （pheromone）和其他螞蟻保持間接異步聯(lián)系。螞蟻在行動的過程中，會在其走過的路上殘留下一些信息素，這些信息素能夠被同群的螞蟻伙伴所感知，并且會對螞蟻行為產(chǎn)生影響。即在相同時間內(nèi)，離食物愈近的路徑會被更多的螞蟻選擇，所留下的信息素也會愈來愈濃，后期螞蟻選擇此路徑的概率便會更大。該過程會持續(xù)迭代，一直持續(xù)到所有螞蟻都選擇了較短路線。

阿根廷螞蟻在開始覓食時就會自動分泌并殘留費洛蒙（pheromone）痕跡。實驗者準(zhǔn)備了兩個大槽，其中一個放入阿根廷蟻群，另外一個放入食物。之后，在兩個槽之間搭建了一個小橋。

實驗者們在這座橋上進(jìn)行了特別設(shè)計，即在橋的跨距1/4的地方，劃分為兩條路，盡管兩條路都能夠達(dá)到食物槽，不過其路徑距離不同，其中一條路大約是另一條路的2倍。對此，螞蟻們會做出什么樣的選擇呢？

就像預(yù)期的那樣，螞蟻在非常短的時間內(nèi)就明確了最佳路徑。根據(jù)此實驗?zāi)軌蛄私獾?，在進(jìn)行最初探路時期之后，剩下的螞蟻均會選擇路程比較少的那一條路。

實驗最大的發(fā)現(xiàn)是由費洛蒙而繪制出的路線。在更多螞蟻選擇路徑較短的一條路時，費洛蒙的濃度就會愈來愈大，而這就會在無形之中提高后面螞蟻選取此路的概率。其運作模式為：如果兩只螞蟻（螞蟻A和螞蟻B）在同一時刻分別選取了兩條路徑，分別是路徑A和路徑B，其中路徑A要比路徑B稍短。在A螞蟻成功靠近食物槽的時候B螞蟻還在路途之中，而在A螞蟻已成功回到蟻穴時，B螞蟻才靠近食物槽。

那么這樣的話，就處于分叉點上的C螞蟻而言，A螞蟻因為來回走了兩次，所以它所殘留的費洛蒙氣味大約是B螞蟻的兩倍，氣味比較濃即表示這可能會是一條距離較短的路徑。在這種情況迭代數(shù)次之后，費洛蒙氣味的差距會變的愈來愈顯著，導(dǎo)致愈來愈多的螞蟻選擇A路線，也就是比較短的路線。

也就是說，蟻群已慢慢摸索出了距離較短的路徑，能夠快速地在兩點之間選取最短路線。另外，對于螞蟻而言，這并非其自身意愿，它們并不沒有興趣對路線進(jìn)行比對。其實，這是以蟻群為單位而做出的最理想的方案，即讓所有螞蟻輪番上陣，通過費洛蒙持續(xù)“強(qiáng)化”其最初的成功并導(dǎo)引其他螞蟻走向“最初的成功”，向人們展示了強(qiáng)大的自我控制和組織能力。

專家根據(jù)上述原理，利用虛擬“人工蟻群”的方法對蟻群外出覓食的整個過程進(jìn)行仿真分析，以此獲得最佳路徑，并以此為依據(jù)提出了蟻群算法（Ant Colony Algorithm，簡稱 ACA）。

3 蟻群算法的實際應(yīng)用

蟻群算法在現(xiàn)實中應(yīng)用較為普遍。可應(yīng)用于多種問題的處理與解決，比如聚類問題、車輛調(diào)度問題以及路由問題等。其中，路由問題是蟻群算法最典型的應(yīng)用：在一個網(wǎng)絡(luò)信號由初始城市傳輸至目標(biāo)城市時，該信號往往需要穿越數(shù)個節(jié)點。每穿行一個節(jié)點時，這個信號要做出一個選擇——下一步將穿過哪個節(jié)點使得信號的傳播過程中代價最小。這就是路由的選擇問題。此問題包含兩個基本任務(wù)：

（1） 收集狀態(tài)信息并更新。

（2） 基于收集的信息為新的請求找到一條最佳路徑。

一個基于蟻群算法的計算機(jī)程序可以解決路由選擇問題。該計算機(jī)程序模擬出電子螞蟻，讓這些電子螞蟻通過線路，感知線路的速度以及擁擠的程度并收集這些信息。類似于真實的螞蟻會在道路上留下信息素，這些電子螞蟻會把它們收集到的信息，即線路的速度及擁擠度，轉(zhuǎn)化為電子代碼留在它們通過的道路上。在通過迭代，加強(qiáng)最優(yōu)路徑上電子信息。最終，使網(wǎng)絡(luò)信號沿著電子信息素加強(qiáng)程度最高的線路傳播。這樣，網(wǎng)絡(luò)信號就成功地選擇出傳播速度最快的路線。在1990年代，惠普企業(yè)以及英國電信公司對該問題展開了深度剖析和研究。

4 蟻群算法的優(yōu)缺點分析

群算法具有如下一些優(yōu)點：

（1）具有良好的通用性，并且對于能夠轉(zhuǎn)變?yōu)檫B通圖結(jié)構(gòu)的大部分路徑優(yōu)化問題亦具有較強(qiáng)的處理能力；

（2）支持正負(fù)反饋，可借助正反饋功能通過局部解完成全局解的構(gòu)造工作，另外，可借助負(fù)反饋功能防止算法進(jìn)入局部最優(yōu)模式；

（3）支持間接通訊，并具有典型的自組織特征，螞蟻間不存在直接聯(lián)系，它們是利用路徑上所存在的信息素完成信息間接的傳遞，另外其自組織功能能夠充分發(fā)揮群體力量共同處理問題。

不過傳統(tǒng)的蟻群算法并非完美無缺，它亦存在不足之處，比如：

（1）該算法的大部分搜素時間用于解的構(gòu)造，使得搜索時間較長，效率不高；

（2）在問題規(guī)模較大時，極易產(chǎn)生停滯問題，并進(jìn)入局部最優(yōu)解狀態(tài)。

5 蟻群算法的改進(jìn)

蟻群算法需從下述三個方面進(jìn)行改進(jìn)和優(yōu)化：

（1）對選擇下一節(jié)點概率的改進(jìn)。主要目的是為了增強(qiáng)選擇概率的自適應(yīng)性，使選擇概率能以一定概率選擇較優(yōu)解；

（2）對信息素的更新規(guī)則予以優(yōu)化。主要目的是為了使信息素的分配更加合理，換言之，防止出現(xiàn)信息素分配產(chǎn)生過大或者過小等極端現(xiàn)象。

（3）把蟻群算法與其他相關(guān)算法相結(jié)合。

6 未來展望

當(dāng)前ACA的一系列模型并未全部歸入相同框架之內(nèi)，另外，與離散域相比，針對ACA在連續(xù)域的研究不是很多，因此針對收斂性的證明以及理論研究還需有長的一條路要走。

7 結(jié)束語

蟻群算法是一種典型的仿生學(xué)算法，極富實用價值，發(fā)展前景明朗。值得專家學(xué)者們深入研究。

作者單位

鄭州外國語學(xué)校 河南省鄭州市 450000