变形虫——一种主要由胶质原生质构成的单细胞生物——被证实具有一种独特的计算能力，能用来解决“旅行推销员问题”。有朝一日，这或许会成为成取代传统计算机所使用的方法。
在日本庆应义塾大学，青野真士（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
