孫守梅　王敬輝

摘要：自1992年Marco Dorigo提出蟻群算法以來，蟻群算法得到了快速發(fā)展，并廣泛應(yīng)用于車輛調(diào)度問題、車輛路徑問題、分配問題、子集問題、網(wǎng)絡(luò)路由問題蛋白質(zhì)折疊問題、數(shù)據(jù)挖掘、圖像識(shí)別、系統(tǒng)辨識(shí)等。

關(guān)鍵詞：智能算法；蟻群算法；模式識(shí)別

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）10-2353-03

蟻群算法是一種近年來快速發(fā)展起來的一種智能算法。這種算法由Marco Dorigo于1992年提出，其靈感源于蟻群在尋找食物的過程中總是能找到一條從食物到蟻穴之間的最短或最優(yōu)路徑這一現(xiàn)象。蟻群算法具有魯棒性強(qiáng)、全局搜索、并行分布式計(jì)算、易于與其它問題結(jié)合等優(yōu)點(diǎn)。廣泛應(yīng)用于車輛調(diào)度問題、車輛路徑問題、分配問題、子集問題、網(wǎng)絡(luò)路由問題蛋白質(zhì)折疊問題、數(shù)據(jù)挖掘、圖像識(shí)別、系統(tǒng)辨識(shí)等。

1 螞蟻的覓食策略—不等長雙橋?qū)嶒?yàn)

下圖表示螞蟻覓食時(shí)選擇行走路徑的過程，圖1 （a）為螞蟻選擇不同的路徑覓食；圖1 （b）顯示絕大多數(shù)螞蟻選擇了最短的路徑；最終有80%以上的螞蟻?zhàn)罱K選擇了最優(yōu)路徑如圖1 （c）顯示。

該結(jié)果的原因是螞蟻能夠分泌并感知一種信息素，以進(jìn)行信息傳遞。螞蟻會(huì)在途經(jīng)的路徑上留下這種信息素，其它螞蟻和自身都能夠感知這種信息素，并以此指導(dǎo)自己的運(yùn)動(dòng)方向。在該實(shí)驗(yàn)中，選擇最短的路徑的螞蟻先回蟻巢，這樣在最短路徑會(huì)有更多的信息素，從而誘使蟻穴中其它螞蟻選擇短路徑，因此蟻群集的體行為便表現(xiàn)出一種信息正反饋現(xiàn)象。

大量螞蟻的集體行為主要有三點(diǎn)：

1）正反饋： 這是基于信息素的釋放和感知來實(shí)現(xiàn)的。某一路徑上走過的螞蟻越多，信息素就越濃，誘使其它螞蟻選擇短路徑，從而能快速發(fā)現(xiàn)最優(yōu)的解。

2） 負(fù)反饋： 負(fù)反饋是基于信息素的揮發(fā)來實(shí)現(xiàn)的。信息素的濃度隨著時(shí)間的推移不斷下降，從而避免某些路徑上信息素過多，使算法早熟，陷入局部最優(yōu)解。

3） 啟發(fā)式信息： 在蟻群算法中構(gòu)造一個(gè)啟發(fā)信息，它有助于通過搜索過程找到可行解。

2 蟻群算法—商旅問題

蟻群智能算法中把具有簡單功能的工作單元看作螞蟻，即構(gòu)造人工螞群，來優(yōu)先選擇信息素濃度大的路徑，來解決最優(yōu)化問題。 人工蟻群具有一定的記憶能力；同時(shí)，人工蟻群在選擇下一條路徑的時(shí)候并不是盲目的，而是按一定算法規(guī)律有意識(shí)地尋找最短路徑。例如在TSP問題（Travelling Salesman Problem 商旅問題）中，當(dāng)前城市到下一個(gè)城市的距離可以預(yù)先知道。

nTSP問題引入

比如有一位商人，他想訪問中國的某些城市，要求：

1） 所走路程最近。

2） 每個(gè)城市只能訪問一次。

3） 從某城市出發(fā)，最后回到該城市。

nTSP問題引入原因：

1） 直觀，易理理。

2） TSP是典型的組合問題，常用來驗(yàn)證一些算法的有效性。

3） 蟻群算法很適合這類最短路徑問題問題。

n螞蟻具有的特征：

1） 在從城市i到j(luò)的過程中在邊（i，j）上釋放信息素。

2） 禁止螞蟻重復(fù)訪問城市。

3） 訪問下一個(gè)城市的概率是兩城市間和連接兩城市的路徑上存有軌跡量的函數(shù)。

簡單螞蟻算法的流程圖：

1） 蟻群A（t）初始化。

2） 對(duì)每只螞蟻的適應(yīng)度做評(píng)價(jià)。

3） 對(duì)螞蟻所經(jīng)歷的路徑按照一定的比例釋放信息素。

4） 根據(jù)路徑的信息素濃度和自己的判斷選擇合適的路徑。

5） 信息素濃度會(huì)隨著時(shí)間不斷下降。

其中，信息素的濃度用[Q]表示，它是一個(gè)常數(shù)；第[k]只螞蟻在本次循環(huán)中所走過的路徑的總長度用[Lk]表示。

3 TSP問題蟻群算法偽代碼實(shí)現(xiàn)

偽代碼（Pseudocode）是一種算法描述語言。使用偽代碼的目的是為了使被描述的算法可以容易地以任何一種編程語言（Pascal，C，Java，etc）實(shí)現(xiàn)。因此，偽代碼必須結(jié)構(gòu)清晰、代碼簡單、可讀性好，并且類似自然語言。

Proceure AS

for each edge

set initial pheromone value t0

end for

while not stop

for each ant k

randomly choose an initial city

for i=1 to n

choose next city with probability

end for

end for

compute the length Ck of the tour constructed by the kth ant

for each edge

update the pheromone value

end for

end while

print result

end procedure

參考文獻(xiàn)：

[1] 杜立峰，牛永潔. 蟻群算法在MATLAB中的實(shí)現(xiàn).信息技術(shù)[J].2011（6）：115-118.

[2] 張麗，劉希玉，李章泉.基于蟻群算法的聚類優(yōu)化[J].計(jì)算機(jī)工程，2010，36（9）：90-192.

[3] 朱峰，陳莉.一種改進(jìn)的蟻群聚類算法[J].算機(jī)工程與應(yīng)用，2010，45（6）：33-135.

[3] 程曄.基于蟻群優(yōu)化神經(jīng)網(wǎng)絡(luò)的比較購物模型研究[D].安徽理工大學(xué)，2010.

[4] 劉志剛基于敏捷模式的生產(chǎn)車間計(jì)劃與調(diào)度系統(tǒng)研究[D].西安理工大學(xué)，2006.

[5] 改進(jìn)蟻群算法在乳品企業(yè)原奶車輛運(yùn)輸路徑中的應(yīng)用研究[D].東北農(nóng)業(yè)大學(xué)， 2006.

[6] 楊麗.基于低壓載波電力線數(shù)據(jù)傳輸協(xié)議的研究[D].華北電力大學(xué)（河北），2008.

[7] Dorigo M，Maniezzo V，Colomi A.Ant system：optimization by a col— ony of cooperating agents[J].IEEE Transactions on SMC，1996，26 （1）：12-41.

[8] Dofigo M，Gambardella L M.Ant colony system：a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computing，1997（1）：53-66.