螞蟻的「群體智慧」既能規劃最佳路線，還能破解河內塔

文：安柏瑞吉（Ben Abridge）

讓昆蟲規劃路線

真正的合作可說是人類獨有的行為，但是就連一些不起眼的昆蟲也會表現出某種未經思考、類似合作的行為，使得牠們能進行一些非常複雜的工作，例如尋找通往某個目的地的最短路徑。

可是，你要怎麼和昆蟲較量呢？

假如你是推銷員，住在馬克菲爾德的亞士頓（Ashton-in-Makerfield，簡稱A地），那裡是大曼徹斯特從前的一個煤礦鎮）。某一天，你需要去波爾頓（Bolton，簡稱B地）、察爾頓哈迪（Chorlton-cum-Hardy，簡稱C地）、鄧納姆梅西（Dunham Massey，簡稱D地）和東沃靈頓（East Warrington，簡稱E地）推銷，最後回到亞士頓的家。

下面的地圖顯示各個地點之間的交通時間，單位是分鐘。我們讓情形簡化一下，假設這些時間是固定的，不會隨交通狀況而變。所以該用什麼順序造訪這些地點，才能把交通時間縮到最短？

請注意：即使是為了縮短交通時間，也不可經過同一個地點超過一次以上。

解答

這個問題最佳解答的總交通時間是90分鐘。

你的答案很接近嗎？假如沒有，讓我告訴你通常能得到不錯答案的策略（至少類似這個題目的小型問題都適用，不過未必是最佳解）：最鄰近法。你每次重新上路時，只要排除去過的地方，然後選交通時間最短的地方就好（你住的城鎮當然要放在最後）。這樣得到的路線是A→B→D→C→E→A或A→B→D→E→C→A（差別是從D出發之後，選擇距離10分鐘路程的C或E），這兩條路線都得到110分鐘（20 + 10 + 10+ 40 + 30）的結果。你得到不錯的路線之後，看看能不能靠著試誤嘗試，省下20分鐘的時間。

解出來了嗎？最後一個提示：如果你從「最鄰近法」路線的第二條（A→ B→D→E→C→ A）開始，只要把其中兩站的順序調換，就能得到最短路線。

沒錯！把D和E調換，就得到 A→B→E→D→C→A，交通時間總計90分鐘（20+20+10+10+30）。

數學家研究旅行推銷員問題已經超過50年，但仍然沒有一個解決辦法保證可以得到最佳路線，他們只能土法煉鋼，比對每條可能的路線，但城市的數目逐一增加之後，這樣的解法很快就不再可行了（只要50座城市，就有870億條可能路線）。其實專家大多認為，不可能有演算法能求出最佳路線。

科學家尋找比較理想的近似解法的時候，愈來愈倚重動物世界提供的靈感。有個方法根據的是遺傳學。首先產生一些隨機的路線，大部分沒什麼用處，不過最佳（也就是最短的）路線會和隨機的「突變」來「配對」（通常是取路線中的兩段互換）。大約100代之後，這個程序通常會得到很不錯的路線，即使數量遠比較大（例如25個城市）的問題也行得通。

另一個辦法是靠螞蟻。螞蟻的神奇之處，在於牠們有某種集體智慧（或稱群體智慧）。個別的螞蟻很像腦中個別的細胞，只能執行非常簡單的任務，不過牠們可以和其他螞蟻聯手，表現出複雜的行為。因此，許多方面來看，像一個生物體一樣發揮作用的是蟻群，而不是個別的螞蟻。個別的螞蟻都不「知道」需要建造蟻巢或蒐集食物；這樣的「情報」只存在於蟻群整體的層次（許多研究者用「共同的胃」這樣的名詞，來解釋螞蟻的覓食和攝食行為）。

集體智慧最著名的例子，或許是螞蟻如何找到蟻巢通往特定食物來源的最短路線。個別螞蟻無法找出最短路線，但整體蟻群很快就能辦到。螞蟻隨機探索蟻巢附近的區域，一路上留下費洛蒙蹤跡。螞蟻正好找到一些食物時，會沿著自己外出路上留下的費洛蒙蹤跡，把一些食物帶回巢。另一隻螞蟻遇到這條強化兩次的路線之後，隨著蹤跡找到食物（可能直接找到，也可能走反方向，徒勞無功回巢，端看螞蟻沿著路線走時是否剛好選到正確方向）。接著這隻螞蟻把一點食物搬回巢，進一步強化費洛蒙的蹤跡。個別螞蟻只「知道」要沿著遇到費洛蒙最強的路線走；但集體蟻群「知道」通往食物的最佳路線。

義大利人工智慧研究者多里哥（Marco Dorigo）從這裡得到靈感：蟻群（至少是電腦模擬的蟻群）或許可以替旅行推銷員問題找出更理想的解決辦法。把每隻虛擬的螞蟻隨機放到不同的起始城市，然後讓牠朝隨機選出沒去過的城市走去（如果都去過了，就回到起始的城市）。這些虛擬螞蟻一路上會留下虛擬的費洛蒙蹤跡。厲害的來了，這些虛擬螞蟻和真螞蟻不同，虛擬螞蟻全程只有固定量的費洛蒙，會平均散布在路上。因此如果牠走的路線比較短，留下的蹤跡比較強；走的路線長，分配到的費洛蒙就散布得比較稀薄，留下的蹤跡比較淡。第一趟走完之後，每隻螞蟻會再次出發，不過這次會沿著牠遇到費洛蒙蹤跡最強烈的路線走。

這種程序跑過幾百次之後，雖然有時無法找出最佳解，但虛擬螞蟻找出的那條路線已經和數學家找到的不相上下了。

我們只有一個句子可以形容：小蟻立大功。

螞蟻會玩河內塔？

前一單元的旅行推銷員問題不是由真的螞蟻解出來的，解出問題的是由螞蟻行為得到啟發而開發出的電腦演算法。這樣令你發毛或是搔癢難耐嗎？別擔心。該來更進「蟻」步（好啦，我不鬧了），讓你和真的螞蟻比一比了，特別是澳洲的阿根廷蟻（這不是矛盾修辭法，阿根廷蟻是當地的入侵種）。