單細胞的變形蟲，竟然可以解決經典的計算問題
變形蟲——一種主要由膠質原生質構成的單細胞生物——被證實具有一種獨特的計算能力，能用來解決「旅行推銷員問題」。有朝一日，這或許會成為成取代傳統計算機所使用的方法。
在日本慶應義塾大學，青野真士（Masashi Aono）教授領導的一個研究團隊，將變形蟲用來解決組合優化中的一個問題——旅行推銷員問題（TSP）。這個問題所說的是，給定一系列城市和每個城市之間的距離，求解這幾個城市之間最短的路線，使得每個城市恰好被訪問一次，且起點和終點是相同的。
這是一個屬於NP-困難的問題，這意味著隨著城市數量的增加，計算機解決它所需要的時間呈指數級增長。它之所以複雜是因為存在大量可能的解決方案。例如，當考慮的城市數量是4個時，那麼可能的路線只有三條；但如果考慮的城市數量為8，那麼可能的路線數量就會增加到2520條。
在這項新的研究中，研究人員發現，一種變形蟲可以找到合理的（幾乎是最優的）解決旅行推銷員問題的方案，並且隨著「城市」數量從4到8的增加，所用的時間呈線性增長。雖然傳統的計算機也可以在線性時間內找到近似解，但其演算法與變形蟲完全不同。
科學家解釋說，變形蟲通過以恆定的速率不斷地將凝膠重新分布在它那沒有固定形狀的身體中，以及並行而不是串列地處理光學反饋來探索溶液空間。
雖然傳統的計算機仍然能夠比變形蟲更快速地解決旅行推銷員問題（特別是對於那些「城市」數量較小的問題），但這一新的結果是非常有趣的，它或許能發展出新型的模擬計算機，這種模擬計算機可以在線性時間內得到大得多的計算複雜的問題的近似解。（模擬計算機是一種計算機類型，它使用物理現象不斷變化的性質，比如電氣、機械、液壓等物理量，來模擬正在解決的問題。與之相對，數字計算機隨著數值的變化符號地表示不同的數量。模擬計算機不使用離散值，而是使用連續值。）
變形蟲如何工作
科學家使用的變形蟲是一種瘧原蟲（或「真正的黏液黴菌」），它重約12毫克，以燕麥片為食。它無定形的身體會不斷地變換形狀，以約1毫米/秒的速率反覆供應和收回凝膠，製造出像偽足一樣的附肢。
實驗中，研究人員把變形蟲放在星形薄片的中心，這是一種圓形的薄片，有64個狹窄的通道向外突出。將這種薄片放在瓊脂上面，變形蟲會被限制在薄片內，但仍然可以移動到64個通道中。
基於變形蟲的計算系統。（a）變形蟲類生物，多頭絨泡菌（Physarum polycephalum）被放置在塗有金塗層的64通道星形薄片上，置於營養豐富的瓊脂平板上。由於瘧原蟲被營養物質吸引而對金屬表現出厭惡，它會待在有瓊脂的薄片內。利用攝像機進行透射光成像時，瘧原蟲和薄片從下方被橙色表面光源照亮；這種光並不影響生物體的行為。（b）通道中瘧原蟲分支的典型時間演化，紅色和藍色的曲線表明，瘧原蟲的偽足類附肢的大小因為光刺激的缺失和存在而生長和收縮。| 圖片來源：[2]
為了最大限度地吸收營養，變形蟲會試圖在薄片內擴張，以儘可能多地接觸到瓊脂。然而，變形蟲不喜歡光，而研究人員可以選擇性地照亮每個通道，所以就有可能迫使變形蟲從被照亮的通道中退散。
為了對旅行推銷員問題進行建模，星形薄片中的每個通道代表推銷員路線上的一個有序的城市。例如，對於有四個城市標記為A-D的情況，如果變形蟲佔據A4、B2、C1和D3通道，則旅行推銷員問題對應的解決方案是C、B、D、A、C。
城市數量n為4、5、6 、7、8的旅行推銷員問題的例子。每張地圖被設計成使得城市間距離的可能長度形成一種類似單峰分布，其平均值約為150，最短路徑為100（藍色），最長路徑為200。這是估計搜索能力對n的依賴性的一種自然方法。實驗中變形蟲採取的路徑是紅色的那條。| 圖片來源：[2]
將變形蟲引向最優或接近最優解決方案的關鍵在於控制光線。為了做到這一點，研究人員使用了一種神經網路模型，在這種模型中，系統每隔六秒鐘就會更新被照亮的通道。這種模型將兩個城市之間距離的信息與變形蟲在通道中當前位置的反饋結合了起來。
這個模型以幾種方式確保了變形蟲找到旅行推銷員問題的有效解決方案。例如，一旦變形蟲佔據了某一特定通道的某一部分，比如A3，那麼A1、A2和所有其他「A」通道就會被照亮，以防止A城市被訪問兩次。此外，B3、C3、D3和所有其他「3」頻道也都被照亮，以防止同時訪問多個城市。
模型通過將照亮代表距離較遠城市的通道變得更容易，將城市之間的距離考慮了進去。例如如果變形蟲佔據了通道B2，並將以等量地侵入通道C3和D3，其中城市B和C之間的距離為100，而B和D之間的距離為50。那麼B和C之間因相距較遠而最終導致系統照亮通道C3，使得變形蟲從該通道撤退，但允許它繼續移動到D3。
基於變形蟲計算系統的旅行推銷員問題解決方案。（a-e）是城市數量n為4、5、6 、7、8的旅行推銷員問題的例子。左側面板顯示初始狀態的透射光圖像。所有分支的瘧原蟲（暗橙色）即將進入通道（淡黃色）。藍色部分表示被照亮的區域。右側面板顯示了由瘧原蟲的細長分支發現的令人滿意的短行程的數字處理圖像，其中每個紅色和黃色像素分別表示，瘧原蟲在相應區域的厚度增加或者減少。| 圖片來源：[2]
總的來說，用變形蟲來模擬旅行推銷員問題是利用了變形蟲尋求穩定平衡的自然傾向。由於代表較短路線的通道不太可能被照亮，變形蟲可能會在這些通道中擴散，並繼續探索其他未被照亮的通道，使得它在瓊脂上的表面積最大化。
研究人員還開發了一種名為AmoebaTSP（變形蟲旅行推銷員問題）的計算機模擬，來模擬變形蟲如何解決這一問題的一些主要特徵，包括凝膠從各種通道以恆定速率供應和撤出時的持續移動。
青野說：「在我們用於求解n個城市的旅行推銷員問題的星形薄片中，當變形蟲最終找到一個近似解時，變形蟲身體的總面積就會變成n。這似乎存在一個『定律』，變形蟲提供凝膠資源，以恆定的速率（比如x）在未被照亮的通道中擴散。即使某些凝膠資源會從被照亮的通道反彈回來，這個定律也會保持不變。那麼擴展身體面積n（解）所需的時間就是n/x。這種機制就是線性時間的起源，我們的計算機模擬模型也再現了這一機制。「
未來，研究人員計划進一步提高變形蟲的計算能力。
來自慶應義塾大學的另一位合著者Kim Song-Ju說：「我們將進一步研究這些複雜的時空振蕩動力學能如何提高計算性能，從而在更短的時間內找到更高質量的解決方案。如果能夠清楚這一點，這些知識將有助於創造出新的能充分利用電路中電流的時空動力學的模擬計算機。」
當然，在傳統的數字計算機上運行一些線性時間的其他演算法，我們可以得到旅行推銷員問題的近似解。另一方面，當在傳統計算機上運行模擬模型（AmoebaTSP或其拓展版本）時，模擬和並行時空動力學需要的是非線性時間來模擬它們作為數字和串列過程。因此，我們正試圖通過以線性或更短的時間在模擬計算機上運行我們的模型，以此來獲得比傳統方法更高質量的解決方案。
研究人員還預計，通過製造更大的薄片，變形蟲將能夠解決數百個城市間的旅行推銷員問題，儘管那時這將需要數萬個通道。
參考鏈接：
[1]https://phys.org/news/2018-12-amoeba-approximate-solutions-np-hard-problem.html
[2]https://royalsocietypublishing.org/doi/10.1098/rsos.180396
TAG:原理 |