變形蟲(也稱為阿米巴)是一種主要由凝膠狀原生質組成的單細胞生物。雖然看起來微不足道,但最新的研究表明它有望解決計算機領域最為挑戰的問題,并有可能和強大的超級計算機一拼高下!
近日研究人員創造性地利用變形蟲來解決旅行商問題(Traveling Salesman Problem ,TSP),通過這種“阿米巴計算機”,研究人員可以獲得TSP問題高質量的近似解,更重要的是,這種算法所需的計算時間只會隨著TSP中城市的數量呈線性增長。研究人員在4-8個城市的問題中驗證了算法的有效性,并發現解的質量不會隨著搜索空間的擴大而下降。
TSP是一個方案優化問題但同時也是最具代表性的NP-Hard問題,其目標是找到幾個城市之間最短的路線,這樣每個城市都只被訪問一次,且回到出發點。
隨著城市數量的增加,計算機解決問題所需的時間呈指數級增長。大量可選路線導致了其復雜性。例如,對于四個城市,只有三條可能的路線。但是對于八個城市來說,可能的路線數量增加到2520條。
在最新研究中,研究人員發現變形蟲可以在短時間內找到TSP的合理(幾乎最優)解決方案,隨著城市數量從4個增加到8個,TSP問題的求解時間只會線性增長。盡管傳統計算機也可以在線性時間內找到近似解,但變形蟲的方法與傳統算法完全不同。科學家解釋說,變形蟲以恒定的速度不斷地將身體凝膠成分重新分布在非固定形態體內,并通過并行而非串行的方法處理光學反饋來研究空間問題。雖然傳統的計算機,特別是對于小問題上,仍然可以比變形蟲更快地解決TSP問題,但是這一新的發現可能會導致新型模擬計算機的發展。
研究中采用的變形蟲是一種瘧原蟲或“真黏液霉菌”,重約12毫克,以燕麥薄片為食。這種變形蟲以大約1毫米/秒的速度反復釋放和收回凝膠,不斷變形。實驗中,研究人員將變形蟲放在星狀芯片的中心,芯片是有64個向外突出的狹窄通道的圓板,然后將芯片放在瓊脂板上。變形蟲被限制在芯片內,但仍然可以進入64個通道。為了最大限度地吸收營養,變形蟲試圖在芯片內部擴張,與盡可能多的瓊脂接觸。然而,變形蟲不喜歡光。光可以選擇性的照亮任一通道,從而迫使變形蟲從被照亮的通道中退出。
為了模擬TSP,星狀芯片中的每個通道代表銷售人員路線中的一個城市。例如,在標記為A - D的四個城市的情況下,如果變形蟲占據了通道A4、B2、C1和D3,那么TSP的相應解決方案是C、B、D、A、C
上圖描述了變形蟲在解決4-8TSP問題時的表現
引導變形蟲走向最佳或接近最佳的解決方案,關鍵在于控制光線。研究人員使用了一個神經網絡模型,系統每六秒鐘更換一次照亮的通道。該模型結合了每對城市之間距離的信息,以及變形蟲在通道中當前位置的反饋。該模型可以通過幾種方法確保變形蟲找到TSP的有效解決方案。例如,一旦變形蟲占據了特定通道的某一部分,比如A3,那么通道A1、A2和所有其他“A”通道就會被照亮,以防止城市A被訪問兩次。此外,B3、C3、D3和所有其他“3”頻道被點亮,以禁止同時訪問多個城市。
實驗中的變形蟲
更容易點亮的通道代表距離更遠的城市而非距離近的城市。例如,假設變形蟲占據了B2通道,并且已經開始等量侵入C3和D3通道,城市B和C之間的距離是100,而城市B和D之間的距離是50。B和C之間的距離更長,更促使系統照亮通道C3,使變形蟲從該通道后退,但變形蟲仍可以繼續進入D3??偟膩碚f,利用變形蟲的自然傾向來建立TSP模型,找到穩態平衡。由于代表較短路線的通道不太可能被點亮,變形蟲可能會在這些通道中擴散開,并繼續探索其他未被點亮的通道,以最大化其在瓊脂板上的表面積。
推進模擬計算機的發展
除了開發真實的變形蟲計算芯片外,研究人員還開發了一種名為變形蟲的計算機模擬系統,模擬變形蟲解決問題的主要策略,如凝膠以恒定的速度并從不同的通道輸出和回收時,要保持凝膠的持續流動。Aono告訴接受采訪時說 :“星狀芯片解決N城市TSP問題的模型中,當變形蟲最終找到最接近的解決方案時,變形蟲身體的總面積變成了N。似乎存在一個‘定律’,變形蟲利用凝膠在非照明通道以恒定速度x運動。即使部分凝膠從點亮的通道退回來,該定律也維持不變?!睌U大身體面積到n來解決問題的時間變成了n/x。這種機制是前文提到的以線性時間解決問題的原因,可以被計算機模型模擬重現。目前研究人員對這種“阿米巴計算機”如何保證近似解質量的機制還不確定,不過阿米巴在每個分支間的空時關系也許就是保證求解質量的關鍵所在。每一個分支都會在對應的通道中振蕩,其中包含了它被光照的“記憶”。這些分支間會表現出協同和失協的過程,并在這一過程中共享信息。在接下來的研究中,研究人員計劃繼續改進阿米巴計算機的計算能力。他們將探索如何利用這種復雜的空時振蕩動力學來提高計算能力,在更短的時間內找到更高質量的解。這個問題的研究將有助于模擬計算機利用電路中電流的空時動力學,建立起更加有效的計算理論和裝置。在未來,研究人員將建立更大的“阿米巴計算機”,將這一裝置將應用在上百個城市TSP問題的求解中,上萬個通道的阿米巴計算機將會十分壯觀!
-
芯片
+關注
關注
456文章
51192瀏覽量
427301 -
計算機
+關注
關注
19文章
7540瀏覽量
88644 -
TSP
+關注
關注
1文章
25瀏覽量
16970
原文標題:阿米巴,真正強大的生物計算機了解一下?
文章出處:【微信號:thejiangmen,微信公眾號:將門創投】歡迎添加關注!文章轉載請注明出處。
發布評論請先 登錄
相關推薦
評論