變形蟲（也稱為阿米巴）是一種主要由凝膠狀原生質(zhì)組成的單細(xì)胞生物。雖然看起來微不足道，但最新的研究表明它有望解決計(jì)算機(jī)領(lǐng)域最為挑戰(zhàn)的問題，并有可能和強(qiáng)大的超級計(jì)算機(jī)一拼高下！

近日研究人員創(chuàng)造性地利用變形蟲來解決旅行商問題（Traveling Salesman Problem ，TSP），通過這種“阿米巴計(jì)算機(jī)”，研究人員可以獲得TSP問題高質(zhì)量的近似解，更重要的是，這種算法所需的計(jì)算時間只會隨著TSP中城市的數(shù)量呈線性增長。研究人員在4-8個城市的問題中驗(yàn)證了算法的有效性，并發(fā)現(xiàn)解的質(zhì)量不會隨著搜索空間的擴(kuò)大而下降。

TSP是一個方案優(yōu)化問題但同時也是最具代表性的NP-Hard問題，其目標(biāo)是找到幾個城市之間最短的路線，這樣每個城市都只被訪問一次，且回到出發(fā)點(diǎn)。

隨著城市數(shù)量的增加，計(jì)算機(jī)解決問題所需的時間呈指數(shù)級增長。大量可選路線導(dǎo)致了其復(fù)雜性。例如，對于四個城市，只有三條可能的路線。但是對于八個城市來說，可能的路線數(shù)量增加到2520條。

在最新研究中，研究人員發(fā)現(xiàn)變形蟲可以在短時間內(nèi)找到TSP的合理(幾乎最優(yōu))解決方案，隨著城市數(shù)量從4個增加到8個，TSP問題的求解時間只會線性增長。盡管傳統(tǒng)計(jì)算機(jī)也可以在線性時間內(nèi)找到近似解，但變形蟲的方法與傳統(tǒng)算法完全不同。科學(xué)家解釋說，變形蟲以恒定的速度不斷地將身體凝膠成分重新分布在非固定形態(tài)體內(nèi)，并通過并行而非串行的方法處理光學(xué)反饋來研究空間問題。雖然傳統(tǒng)的計(jì)算機(jī)，特別是對于小問題上，仍然可以比變形蟲更快地解決TSP問題，但是這一新的發(fā)現(xiàn)可能會導(dǎo)致新型模擬計(jì)算機(jī)的發(fā)展。

工作原理

研究中采用的變形蟲是一種瘧原蟲或“真黏液霉菌”，重約12毫克，以燕麥薄片為食。這種變形蟲以大約1毫米/秒的速度反復(fù)釋放和收回凝膠，不斷變形。實(shí)驗(yàn)中，研究人員將變形蟲放在星狀芯片的中心，芯片是有64個向外突出的狹窄通道的圓板，然后將芯片放在瓊脂板上。變形蟲被限制在芯片內(nèi)，但仍然可以進(jìn)入64個通道。為了最大限度地吸收營養(yǎng)，變形蟲試圖在芯片內(nèi)部擴(kuò)張，與盡可能多的瓊脂接觸。然而，變形蟲不喜歡光。光可以選擇性的照亮任一通道，從而迫使變形蟲從被照亮的通道中退出。

為了模擬TSP，星狀芯片中的每個通道代表銷售人員路線中的一個城市。例如，在標(biāo)記為A - D的四個城市的情況下，如果變形蟲占據(jù)了通道A4、B2、C1和D3，那么TSP的相應(yīng)解決方案是C、B、D、A、C

上圖描述了變形蟲在解決4-8TSP問題時的表現(xiàn)

引導(dǎo)變形蟲走向最佳或接近最佳的解決方案，關(guān)鍵在于控制光線。研究人員使用了一個神經(jīng)網(wǎng)絡(luò)模型，系統(tǒng)每六秒鐘更換一次照亮的通道。該模型結(jié)合了每對城市之間距離的信息，以及變形蟲在通道中當(dāng)前位置的反饋。該模型可以通過幾種方法確保變形蟲找到TSP的有效解決方案。例如，一旦變形蟲占據(jù)了特定通道的某一部分，比如A3，那么通道A1、A2和所有其他“A”通道就會被照亮，以防止城市A被訪問兩次。此外，B3、C3、D3和所有其他“3”頻道被點(diǎn)亮，以禁止同時訪問多個城市。

實(shí)驗(yàn)中的變形蟲

更容易點(diǎn)亮的通道代表距離更遠(yuǎn)的城市而非距離近的城市。例如，假設(shè)變形蟲占據(jù)了B2通道，并且已經(jīng)開始等量侵入C3和D3通道，城市B和C之間的距離是100，而城市B和D之間的距離是50。B和C之間的距離更長，更促使系統(tǒng)照亮通道C3，使變形蟲從該通道后退，但變形蟲仍可以繼續(xù)進(jìn)入D3。總的來說，利用變形蟲的自然傾向來建立TSP模型，找到穩(wěn)態(tài)平衡。由于代表較短路線的通道不太可能被點(diǎn)亮，變形蟲可能會在這些通道中擴(kuò)散開，并繼續(xù)探索其他未被點(diǎn)亮的通道，以最大化其在瓊脂板上的表面積。

推進(jìn)模擬計(jì)算機(jī)的發(fā)展

除了開發(fā)真實(shí)的變形蟲計(jì)算芯片外，研究人員還開發(fā)了一種名為變形蟲的計(jì)算機(jī)模擬系統(tǒng)，模擬變形蟲解決問題的主要策略，如凝膠以恒定的速度并從不同的通道輸出和回收時，要保持凝膠的持續(xù)流動。Aono告訴接受采訪時說 :“星狀芯片解決N城市TSP問題的模型中，當(dāng)變形蟲最終找到最接近的解決方案時，變形蟲身體的總面積變成了N。似乎存在一個‘定律’，變形蟲利用凝膠在非照明通道以恒定速度x運(yùn)動。即使部分凝膠從點(diǎn)亮的通道退回來，該定律也維持不變。”擴(kuò)大身體面積到n來解決問題的時間變成了n/x。這種機(jī)制是前文提到的以線性時間解決問題的原因，可以被計(jì)算機(jī)模型模擬重現(xiàn)。目前研究人員對這種“阿米巴計(jì)算機(jī)”如何保證近似解質(zhì)量的機(jī)制還不確定，不過阿米巴在每個分支間的空時關(guān)系也許就是保證求解質(zhì)量的關(guān)鍵所在。每一個分支都會在對應(yīng)的通道中振蕩，其中包含了它被光照的“記憶”。這些分支間會表現(xiàn)出協(xié)同和失協(xié)的過程，并在這一過程中共享信息。在接下來的研究中，研究人員計(jì)劃繼續(xù)改進(jìn)阿米巴計(jì)算機(jī)的計(jì)算能力。他們將探索如何利用這種復(fù)雜的空時振蕩動力學(xué)來提高計(jì)算能力，在更短的時間內(nèi)找到更高質(zhì)量的解。這個問題的研究將有助于模擬計(jì)算機(jī)利用電路中電流的空時動力學(xué)，建立起更加有效的計(jì)算理論和裝置。在未來，研究人員將建立更大的“阿米巴計(jì)算機(jī)”，將這一裝置將應(yīng)用在上百個城市TSP問題的求解中，上萬個通道的阿米巴計(jì)算機(jī)將會十分壯觀！