解密非凡的蟻群算法
英文原文：Decoding the Remarkable Algorithms of Ants
本文作者：Emily Singer。機器之心編譯出品。參與：微胖，Angulia，鄭勞蕾。
沒有中心化的組織，蟻群何以進行高效地搜尋呢？生物學家 Deborah Gordon 揭開了其中的秘密，或許能改進計算機網絡的能力。本文是《量子雜志》對她的采訪。
</blockquote>蟻群協調能力非凡，它們能筑起穿過叢林的復雜小路，搭建精巧巢穴，以及根據所處環境調整覓食模式，所有這些都無需中央指揮。螞蟻簡單的個體行動產生出復雜的行為模式，斯坦福大學的生物學家 Deborah Gordon 希望揭開這背后的簡單規則。
蟻群特別擅長集體搜索，能自動根據周圍環境情況調整搜索策略，從而高效占領大面積地面。Gordon 發現這些蟻群的搜索算法和互聯網背后的人造算法有相似之處。Gordon 希望能從蟻群解決此類問題的規律中找到一種新算法，從根本上降低大規模計算網絡的成本，提升其性能。
在紐約州冷泉港的社會性昆蟲會議上，我們碰到了 Gordon，稍后她立刻啟程前往墨西哥繼續研究樹蟻尋路算法。以下是我們對話的精簡版。
Gordon：我最初的興趣是發育生物學，研究在沒有任何中央控制的情況下，胚胎如何發育起來。當時，我正在尋找一種類似胚胎的系統，只有通過 這個系統我才能觀察到一切——理解能觀察得到的對象要更容易些。因此，我選擇了蟻群。如今，你可以看到很多發育中的胚胎。我那時可不是這樣。
你研究亞利桑那州的同一個蟻群已經有三十多年了。你從一開始就注意到它們了嗎？
Gordon：沒有。研究之初，我對蟻群之間的差異很感興趣，所以給蟻群做了記號以便來年繼續觀察。結果，我發現一些蟻群一年比一年壯大，所以 我想搞清楚原因。那時，沒人知道一個收獲蟻群能活多久。我每年都回過頭去重新檢查蟻群——五年過去了，然后十年。我沒有選擇，只有繼續研究。
什么讓你印象最為深刻？
Gordon：我印象最深的是蟻群的協調性行動和單只螞蟻的低效、不完整行動形成鮮明對比。易言之，蟻群可以完成很多工作，但是，不存在能干的個體螞蟻。
比如，蟻群真的很擅長集體搜索工作；一群螞蟻能在沒有中央指揮的情況下徹底搜索整片地區。它們通過碰一下對方觸角進行簡單互動。當許多螞蟻擠在 一個小空間，會經常碰見，也傾向于鋪條羊腸小道，大家都擠在一起。當寬敞空間里只有幾只螞蟻時，不經常碰面，螞蟻們也會把路鋪開點，覆蓋更多地面。
就收獲蟻群來說，我們已經知道螞蟻會算出還有多久才會碰到攜帶食物回來的螞蟻，據此決定是否離開蟻穴。這是一種正反饋形式；螞蟻帶回食物的速度 越快，離開蟻穴的螞蟻就越多。僅當交互頻率（rate of interaction）夠高時，螞蟻才會決定離開蟻穴。整個體系幫助蟻群管理覓食行動，除非有足夠多的食物值得出去一趟，否則它們不會離開蟻穴。
為什么你將收獲蟻群的算法稱為「anternet」？
Gordon：我和斯坦福的同事 Balaji Prabhakar 一起工作，目的就是搞清楚收獲蟻群用來管理覓食的算法。他指出，算法和傳輸控制協議相似，后者是用來管理網絡數據交通，確保在有足夠帶寬的情況下，數據不 會丟失。兩個系統都使用了簡單的本地反饋來協調行動。我認為，我們可能找出螞蟻用來解決工程問題的其他算法，這些算法目前還不為人所知。我對這個觀點很感 興趣：進化可能會在不同系統中創造出用來解決相同問題的不同算法。
收獲蟻群
但是，多虧進化產生了有助于蟻群的算法，進化必須在集體層面，而不是個體層面發揮作用。
Gordon：從進化角度來看，蟻群才是真正的個體，是蟻群在繁殖，螞蟻沒有制造出更多的螞蟻，但是蟻群制造出更多的蟻群。如果我們想了解螞蟻行為進化之道，我們就必須觀察蟻群。
單個螞蟻做出的決定是如何改變整個蟻群的行為的？
Gordon：在沙漠中，水是極其有限的。螞蟻身體中的水分會因其外出和四處爬行而被消耗，但能從它們的食物——種子中得到補充，所以它們不得不通過消耗水分（覓食）來補充水分（進食）。沒有哪只螞蟻會為了保存水分決定呆在巢穴內。
但是，螞蟻之間互動的微小差異累加起來，就會形成蟻群覓食行動上的巨大差異，也會影響蟻群后代數量。我們發現自然會傾向于選擇那些節約水資源的 蟻群。我稱之為「克制的獎勵」。我認為這是首個能夠追蹤一個動物種群集體行為進化的研究。一個簡單的身體局部動作之所以被選為螞蟻相遇時的互動方式，是整 個蟻群進化的產物。
進化是否還產生了其他的算法？
Gordon：我和另一位計算機科學家正在研究螞蟻使用的尋路網絡。墨西哥樹蟻巢穴和食物源之間的路徑因為樹木、滕條和其他植物的纏結而顯得異 常復雜。這條小路總會被打斷，比如樹枝忽然斷裂，或者有動物穿過，但它又能輕易地就被修復。它們怎樣在如此短的時間——通常就數分鐘——就在眾多不同的選 擇中選擇了這一條呢？
我們認為它們的策略是：不選擇最短的路徑，而是選擇能夠迅速重建和讓蟻群恢復正常流動的路徑。某種程度上，它們為了彈性，犧牲了人類所謂的效率。目前我們已建立起一個有意義的模型，正在實地工作中測試這個模型。
在計算方面，這會有多重要？
Gordon：計算中，信息數量和維護管理成本之間會有一個平衡。我們對蟻群進化而來的解決方案很感興趣。我們有興趣將螞蟻解決方案與機算機系 統中的尋路算法——在尋求最直或最短路徑時，需要大量的信息——進行類比。比如你在陌生地方開車，路口被堵了。如果帶了地圖，你可以找到其他的路。但是， 如果你沒有任何路線信息、沒有任何地址名稱，怎么辦？
群體搜索就面臨著類似的難題。現在，機器人學研究中，人們對使用最廉價的機器人——僅需盡可能少的信息就能與人類協同工作——很感興趣。這樣的 系統會更具穩健性不容易崩潰。相比派遣一個足夠復雜的機器人去探索火星或者在著火大樓進行搜尋工作，派遣一組即使單個出現故障，團隊仍能正常協作的廉價機 器人更有意義。也許蟻群還進化出許多人類未知的辦法來解決類似問題。我們所能做的就是繼續觀察。
蟻群如何隨著時間而變化？
Gordon：隨著群體越來越衰老，規模越來越大，收獲蟻群行為也會改變。群體行為的某些方面僅取決于集體規模大小。就收獲蟻而言，單個工蟻 （除蟻后外）只能活一年，所以不是螞蟻越來越老，越來越智慧，而是整個蟻群。這個謎團促使我開始研究交互網絡，因為當時我正在尋找某種事情，雖然規模變大 后的蟻群方式還是會用老辦法去做這件事，但會產生不同結果。
比如，我是一只螞蟻，遵循著上述規則，在給定頻率下遇到其他螞蟻時，我會做的事情是X。在大蟻群中，我會遇到更多的螞蟻。如果蟻群的規模變大了，遵循著相同的規則（去做這件事情）也許會產生不同的結果，因為與其他螞蟻互動的頻率發生了改變。
我們身處巨大的網絡之中——互聯網，人類大腦，我也因此對其他系統很感興趣。網絡行為如何隨著網絡規模擴大而變化？
如何變化呢？
Gordon：我發現，年長的蟻群比年輕的蟻群穩定得多。如果你制造一個干擾，比如在他們中間制造一點騷亂——我放了一疊牙簽——年長的蟻群最后忽視了這個擾亂，重新開始覓食。我認為，在這些擁有更多覓食螞蟻的蟻群中，蟻群會優先選擇繼續覓食而不是回應擾亂。
你也正在探索蟻群和神經元的相似之處。
Gordon：一只螞蟻會積累近期互動信息，決定做什么，一個神經元也會積累來自其他神經元的近期刺激，決定是否放電。目前，神經科學已有一個復雜模型框架來理解該系統運作原理。我正在與理論神經科學家合作，把這個框架應用到蟻群上。
你發起了一個「公民科學計劃（ citizen science project）」鼓勵公眾研究不同種類的蟻群，研究新螞蟻種類有什么好處呢？
Gordon：大約 14000 種蟻群中，僅有 50 種被研究過，研究新種類有可能會發現新算法。我們為學生開發了一個小型工具箱來觀察不同種類的蟻群如何進行集體搜尋。當孩子們用工具嘗試觀察不同螞蟻種類時，他們也許能從中發掘一些新東西。
轉載請聯系公眾號：機器之心（almosthuman2014）獲得授權，個人微信號“jiqizhixin2014”
</div>來自: 機器之心本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！