解碼螞蟻的非凡演算法

生物學家黛博拉·戈登揭示了螞蟻群如何在沒有中央組織的情況下高效搜尋,這一見解可能會改進計算機網路

來自量子雜誌(在此處查詢原始故事)。

螞蟻能夠進行非凡的協調活動。它們可以在叢林中開闢複雜的路徑,建造精巧的結構,並調整覓食模式以適應其環境,所有這些都無需來自中央來源的命令。斯坦福大學的生物學家黛博拉·戈登希望揭示簡單的規則,這些規則可以透過簡單的個體行動產生複雜的模式。

螞蟻尤其擅長集體搜尋,自動調整其搜尋策略以有效地覆蓋大片區域。戈登發現了螞蟻群用於覓食的演算法與網際網路底層的人工演算法之間的相似之處。鑑於螞蟻已經解決這類問題很長時間了,戈登希望她能發現新的演算法,最終使大規模計算網路更便宜、更高效。


關於支援科學新聞

如果您喜歡這篇文章,請考慮透過以下方式支援我們屢獲殊榮的新聞報道: 訂閱。透過購買訂閱,您正在幫助確保未來有關於塑造我們當今世界的發現和想法的具有影響力的故事。


量子在紐約冷泉港舉行的社會昆蟲會議上會見了戈登,當時她即將前往墨西哥研究樹棲螞蟻的路由演算法。以下是經過編輯和濃縮的對話版本。

量子雜誌:您最初是如何對螞蟻產生興趣的?
黛博拉·戈登:我最初對發育生物學感興趣,並想了解胚胎如何在沒有任何中央控制的情況下發育。我正在尋找像胚胎一樣的系統,只是我可以看到一切——我更容易理解我能看到的東西。我因此選擇了螞蟻。現在,你可以在發育中的胚胎中看到很多東西。但這在我剛開始的時候不是真的。

您已經在亞利桑那州研究同一螞蟻群 30 年了。這是您一開始就打算的嗎?
不是。當我剛開始的時候,我對蟻群之間的差異感興趣,所以我標記了蟻群,以便知道我第二年看到的是同一個蟻群。我注意到一些蟻群一年比一年大,所以我瞭解了蟻群是如何生長的。那時,沒有人知道收割蟻群可以存活多久。我每年都回去檢查蟻群——五年過去了,然後是十年。然後我別無選擇,只能繼續下去。

關於螞蟻,最讓您印象深刻的是什麼?
令我印象深刻的是蟻群的協調反應與單個螞蟻無效且不完整的行動之間的對比。換句話說,蟻群完成了很多工作,但沒有一隻螞蟻自己就很能幹。

例如,螞蟻非常擅長集體搜尋;一群螞蟻可以在沒有任何中央控制的情況下徹底覆蓋搜尋區域。它們透過簡單的互動來做到這一點,只是觸碰觸角。當許多螞蟻在一個狹小的空間裡時,它們會經常相遇,並且傾向於採取曲折的路徑,使它們停留在同一個地方。當很少的螞蟻在一個大的空間裡時,它們不會經常相遇。它們會延伸它們的路徑並覆蓋更多的地面。

對於收割蟻來說,我們已經瞭解到,一隻螞蟻決定是否離開巢穴去覓食取決於它遇到帶著食物進來的螞蟻的速度。這是一種積極的反饋;螞蟻帶著食物進來的速度越快,出去的螞蟻就越多。每隻螞蟻只有當它的互動率足夠高時才決定出去。總的來說,這個系統允許蟻群調節覓食活動,這樣螞蟻就不會出去,除非有足夠的食物值得這樣做。

您將收割蟻演算法稱為“蟻聯網”。為什麼?
我與斯坦福大學的同事巴拉吉·普拉巴卡合作,計算出收割蟻用來調節覓食的演算法。他指出,該演算法類似於傳輸控制協議,該協議調節網際網路上的資料流量,以確保只有在有足夠頻寬的情況下資料才會流出。這兩個系統都使用簡單的、區域性的反饋來調節活動。我認為我們可能會發現螞蟻用來解決我們尚未想到的工程問題的其他演算法。我感興趣的是,進化可能會在不同的系統中產生不同的演算法來解決相同的問題。

但是,為了讓進化產生有助於蟻群的演算法,進化必須在群體層面發揮作用,而不僅僅是在個體層面。
從進化的角度來看,蟻群才是真正的個體,因為它是一個繁殖的蟻群。螞蟻不會製造更多的螞蟻,蟻群才會製造更多的蟻群。因此,如果我們考慮螞蟻行為是如何進化的,我們必須考慮蟻群。

單個螞蟻的決定如何改變整個蟻群的行為?
在沙漠中,水是一個重要的制約因素。螞蟻僅僅在外面四處遊蕩就會失去水分。但它們從吃的種子中獲取水分,所以它們必須花費水分才能獲得水分。沒有哪隻螞蟻單獨決定要節約用水並待在家裡。但是,螞蟻對互動的反應方式上的微小差異可能會累積成蟻群覓食方式上的巨大差異,這反過來會影響蟻群的後代數量。我們發現,自然選擇偏愛節約用水的蟻群。我稱之為“剋制的獎勵”。我認為這是第一個能夠追蹤自然動物群體中集體行為進化的研究。一種簡單、區域性的行為——當一隻螞蟻遇到另一隻螞蟻時如何反應——因為對整個蟻群的結果而被選擇。

進化是否產生了其他演算法?
我正在與另一位計算機科學家合作研究螞蟻使用的路由網路。墨西哥的樹棲螞蟻物種沿著複雜的路徑穿過樹木、藤蔓和其他將巢穴和食物來源連線起來的植被。這些路徑總是會中斷,例如當樹枝折斷或動物穿過路徑時。但是高速公路很容易修復。當有如此多的不同選擇時,它們如何在幾分鐘之內如此迅速地找到新的路線?我們認為它們使用了一種策略,這種策略不會採取最短的路線,而是非常快速地重建路徑並保持流動。在某種程度上,它們為了彈性而犧牲了我們認為的效率。我們認為我們有一個合理的模型,我們正在實地工作中測試它。

這在計算方面有何重要意義?
在計算中,可用資訊量與維護和組織該資訊的成本之間存在權衡。我們對螞蟻為解決這個基本問題而進化的方式感興趣。

在這種情況下,我們對計算機系統中路由演算法的類比感興趣,其中最直或最短的路徑可能需要大量資訊。假設你開車去一個不熟悉的地方,而你想走的出口被封鎖了。如果你有地圖,你可以找到路。但是,如果沒有資訊,你該如何做到這一點?沒有地址?

集體搜尋面臨著類似的問題。在機器人技術中,現在人們非常感興趣的是使用需要儘可能少的資訊並且可以協同工作的最便宜的機器人。像這樣的系統對故障更加穩健。與其傳送一個非常複雜的機器人去探索火星或搜尋燃燒的建築物,不如傳送一群便宜的機器人,即使其中一個出現故障,它們仍然可以作為一個整體工作,這更有意義。螞蟻可能已經進化出許多新的演算法來解決我們尚未想到的這類問題。我們需要做的就是去看看。

螞蟻群如何隨時間變化?
我發現,收割蟻群的行為會隨著年齡的增長和規模的擴大而發生變化。網路行為的某些方面只取決於規模。在收割蟻中,個體工蟻(女王除外)只能存活一年,所以變老、變聰明不是螞蟻,而是蟻群。這是一個難題,它讓我開始思考互動網路,因為我正在尋找螞蟻可以以相同方式進行但如果有更多的螞蟻就會產生不同結果的東西。例如,我是一隻螞蟻,我遵循一條規則,即如果我以一定的速度遇到另一隻螞蟻,我就做x。在一個大型蟻群中,我可能會遇到更多的螞蟻。如果蟻群更大,同樣的規則可能會有不同的結果,因為互動率會發生變化。

我們周圍環繞著巨大的網路——網際網路、我們的大腦——所以這讓我對其他系統產生了興趣。一個網路的行為如何隨著它規模的擴大而擴充套件?

它是如何擴充套件的?
較老的蟻群比年輕的蟻群穩定得多。如果你製造干擾,例如讓它們清理一團亂麻——我放出一小堆牙籤——較老的蟻群最終會忽略這些亂麻,然後回到覓食狀態。我認為在這些蟻群中,由於有大量的覓食者,驅動它們覓食的過程會覆蓋對亂麻的反應。

您還在探索螞蟻與神經元的相似之處。
一隻螞蟻會累積其最近的互動來決定該怎麼做。一個神經元會累積其最近來自其他神經元的刺激來決定是否放電。神經科學已經有了一個複雜的建模框架,可以理解這種系統是如何工作的。我正在與理論神經科學家合作,將這個框架應用於螞蟻。

您發起了一項公民科學專案,鼓勵公眾研究不同種類的螞蟻。研究新螞蟻物種的好處是什麼?
大約 14,000 種螞蟻中,只有 50 種被研究過。如果我們研究新的物種,我們很可能會發現新的演算法。我們為學生開發了一個小型工具包,以瞭解不同種類的螞蟻是如何進行集體搜尋的。如果孩子們用不同的物種嘗試這個,他們可能會對以前沒有人研究過的物種有所發現。

經量子雜誌許可轉載,量子雜誌是 SimonsFoundation.org 的一個編輯獨立的部門,其使命是透過報道數學、物理和生命科學的研究進展和趨勢來提高公眾對科學的理解。

© .