IT思维

公众号/将门创投

From：phys.org  编译：Kathy

变形虫（也称为阿米巴）是一种主要由凝胶状原生质组成的单细胞生物。虽然看起来微不足道，但最新的研究表明它有望解决计算机领域最为挑战的问题，并有可能和强大的超级计算机一拼高下！

近日研究人员创造性地利用变形虫来解决旅行商问题（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。

总的来说，利用变形虫的自然倾向来建立TSP模型，找到稳态平衡。由于代表较短路线的通道不太可能被点亮，变形虫可能会在这些通道中扩散开，并继续探索其他未被点亮的通道，以最大化其在琼脂板上的表面积。

推进模拟计算机的发展

除了开发真实的变形虫计算芯片外，研究人员还开发了一种名为变形虫的计算机模拟系统，模拟变形虫解决问题的主要策略，如凝胶以恒定的速度并从不同的通道输出和回收时，要保持凝胶的持续流动。

Aono告诉接受采访时说 :“星状芯片解决N城市TSP问题的模型中，当变形虫最终找到最接近的解决方案时，变形虫身体的总面积变成了N。似乎存在一个‘定律’，变形虫利用凝胶在非照明通道以恒定速度x运动。即使部分凝胶从点亮的通道退回来，该定律也维持不变。”扩大身体面积到n来解决问题的时间变成了n/x。这种机制是前文提到的以线性时间解决问题的原因，可以被计算机模型模拟重现。

目前研究人员对这种“阿米巴计算机”如何保证近似解质量的机制还不确定，不过阿米巴在每个分支间的空时关系也许就是保证求解质量的关键所在。每一个分支都会在对应的通道中振荡，其中包含了它被光照的“记忆”。这些分支间会表现出协同和失协的过程，并在这一过程中共享信息。

在接下来的研究中，研究人员计划继续改进阿米巴计算机的计算能力。他们将探索如何利用这种复杂的空时振荡动力学来提高计算能力，在更短的时间内找到更高质量的解。这个问题的研究将有助于模拟计算机利用电路中电流的空时动力学，建立起更加有效的计算理论和装置。在未来，研究人员将建立更大的“阿米巴计算机”，将这一装置将应用在上百个城市TSP问题的求解中，上万个通道的阿米巴计算机将会十分壮观！

Ref：

Paper：https://royalsocietypublishing.org/doi/10.1098/rsos.180396
From:https://phys.org/news/2018-12-amoeba-approximate-solutions-np-hard-problem.html

logofrom:https://mikrobenzirkus.com/