螞蟻能找到最近的路

引　子

著名的旅行推銷商問題

假設(shè)您準備去全國10個城市推銷您的新產(chǎn)品，從北京出發(fā)，途徑上海、蘭州、大連等城市，每個城市只經(jīng)過一次，再返回北京，怎么走路途最短、最省事?您也許覺得這事很簡單，筆算一下或者拿地圖量一下不就得出結(jié)果了么?您可以按照這個思路嘗試一下，將會發(fā)現(xiàn)事情不像您想的那么簡單。因為，所有可能的路線就有10X9X8XTX6X5X4X3X2X1=3628800條!

這么多路線，即使用計算機計算，也需要耗費極長的時間。這就是組合優(yōu)化問題中有名的旅行推銷商問題，由意大利數(shù)學家孟戈于1930年首次提出，其實質(zhì)就是要找出一條既行遍所有城市，又使總的行程最小的路線。

神奇的螞蟻算法

馬科·多利戈于1992年在他的博士論文中引入了螞蟻算法。螞蟻算法思想的萌芽至今不過短短17年的時間，然而這種新型的優(yōu)化算法很快就得到了廣泛的認可，對它的研究已從歐洲的一個實驗室迅速傳播到全球千千萬萬個實驗室。下面我們簡要介紹螞蟻算法的思想：

螞蟻算法利用的最基本的原理是螞蟻會在行走的過程中釋放信息素——信息素可以是螞蟻的氣味或分泌物。通過一個簡單的例子，您就會明白信息素的作用何在：假設(shè)有兩條路通向食物。剛開始的時候，這兩條路徑上的螞蟻數(shù)目一樣多。當一只螞蟻沿著較短的路徑到達食物并返回時，由于路徑較短，所以螞蟻來回的時間短，這就意味著重復的頻率快，因此在單位時間里，與較長的路徑相比較，在較短的路徑上走過的螞蟻就多，從而灑下的信息素自然也更多。因此會有越來越多的螞蟻傾向于選擇信息素較多——即被走過的次數(shù)較多的路徑。直到最終，所有螞蟻都“不約而同”地選擇同一條路徑，即最短的路徑。

讓螞蟻幫你找到最佳路線

那么，是否我們也可以像螞蟻一樣，通過在走過的路徑上釋放“信息素”來尋找到最優(yōu)的路徑?當然可以。以本文開頭的10個城市推銷巡游為例，首先設(shè)置如下參數(shù)：各個城市之間的距離，初始時刻各條路徑上的信息量，還有螞蟻的數(shù)目。對于旅行推銷商問題，螞蟻要在走過的路徑上留下信息素，螞蟻數(shù)目過多，會使各個城市之間的路徑上的信息素數(shù)量平均化，不利于快速找到最佳解；但是如果螞蟻數(shù)目過少，會使從未被搜索到的路徑上的信息量減小到接近于0，可能最終找到的是一個次優(yōu)解。所以在具體的實踐中，針對具體問題來對螞蟻的數(shù)目作出折中的選擇。

接著，螞蟻開始巡游各個城市。假設(shè)從北京出發(fā)，那么就需要計算下一步要走的是上海、廣州，還是其他城市?這是根據(jù)北京到各個城市的轉(zhuǎn)移函數(shù)來計算的。轉(zhuǎn)移函數(shù)是到各個城市的路徑上的信息素的函數(shù)。顯然到哪個城市信息素比較高，哪個城市被選擇的概率就比較大。這就需要用到我們上文設(shè)置的初始時刻的信息量，初始時刻的信息量可以設(shè)為各城市之間距離的倒數(shù)，也可以設(shè)為一般的常數(shù)，根據(jù)具體情況有不同的設(shè)置。

在所有螞蟻根據(jù)轉(zhuǎn)移函數(shù)選擇了“下一個城市”并且走過所有城市，即完成了一次循環(huán)之后，記下這次循環(huán)得到的最優(yōu)解，就是所有螞蟻得出的10個城市巡游路線中最短的那條路線。同時要對所有路徑上的信息素進行調(diào)整。在實際的螞蟻尋食過程中，隨著時間推移，留在各個路徑上的信息素必然會部分地揮發(fā)，因此在螞蟻算法中更新路徑上的信息素時要考慮各個路徑上信息素的部分消逝。具體地，以城市甲乙之間的路徑為例，將甲乙路徑上揮發(fā)后剩下的信息素，再加上本次循環(huán)中所有走過該路徑的螞蟻留在該路徑上的信息素，就得到更新后的信息素。舉例來說，第一只螞蟻留在甲乙路徑上的信息素可以考慮甲乙路徑的長短、以及這只螞蟻走過的10個城市的總路線長度來確定。也就是說，甲乙路徑長度越短、走過甲乙路徑的螞蟻越多、含有甲乙路徑的路線的長度越短，甲乙路徑上的信息素就越多。從而，在下一個循環(huán)中，從城市甲出發(fā)，到城市乙的轉(zhuǎn)移函數(shù)也越大，城市乙被選擇的幾率也更大。

然后所有螞蟻從北京(也可以是其他城市)開始，根據(jù)更新的信息素再次巡游10個城市。以多次循環(huán)中最短的路線作為10個城市巡游的最優(yōu)解。

未來展望

上面介紹了旅行推銷商問題以及解決該問題的一種新穎算法——螞蟻算法。旅行推銷商問題在許多領(lǐng)域中有著十分廣泛的應(yīng)用，例如郵遞員投遞路線選擇、推銷員推銷路線選擇、生產(chǎn)作業(yè)排序、物流運輸路線選擇、航空飛行科目排序、vLsi芯片設(shè)計和機器人控制等。由于螞蟻算法的很多問題還有待解決，比如如何克服局部最優(yōu)化、參數(shù)如何選取等，因此目前尚處于理論研究階段，還沒有真正地登上實際應(yīng)用的舞臺。但是，我們相信，理論研究會為實際的應(yīng)用扎下深厚堅實的基礎(chǔ)——理論研究就像一棵大樹的根，只有根堅固、牢靠、扎得深，土地上才能長得枝繁葉茂。

責任編輯尹瑩瑩