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

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

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

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

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

工作原理

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

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

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

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

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

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

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

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