北海道大学 一种单细胞变形虫生物，是一种真粘液霉菌多头绒泡菌的疟原虫
信用:Masashi Aono 受单细胞变形虫高效觅食行为的启发，北海道大学和日本变形虫能源公司的研究人员开发了一种模拟计算机，用于寻找旅行推销员问题(一个典型的组合优化问题)的可靠而快速的解决方案
许多现实世界的应用任务，如物流和自动化中的计划和调度，在数学上被公式化为组合优化问题
传统的数字计算机，包括超级计算机，不足以在实际允许的时间内解决这些复杂的问题，因为它们需要评估的候选解决方案的数量随着问题的大小而显著增加——也称为组合爆炸
因此，近年来，包括量子退火器在内的被称为伊辛机器的新计算机得到了积极的发展
然而，这些机器需要复杂的预处理来将每一个任务转换成它们能够处理的形式，并且存在提供不满足某些约束和要求的非法解决方案的风险，从而导致实际应用的主要障碍
使用新开发的“电子变形虫”可以避免这些障碍，这是一种受单细胞变形虫生物启发的模拟计算机
众所周知，变形虫通过变形身体来最大限度地获取营养
研究表明，该方法可以找到旅行商问题的近似解
e
在给定一定数量城市的地图的情况下，问题是找到访问每个城市一次并返回出发城市的最短路线
这一发现启发了北海道大学的星矢·卡塞教授，他利用模拟电路来模拟变形虫的电子动力学，正如《科学报告》杂志所描述的那样
“变形虫核心在电子环境下寻找解决方案，在这种环境下，横杆交叉点的电阻值代表了TSP的约束和要求，”Kasai说
使用横杆，城市布局可以很容易地通过更新电阻值来改变，而不需要复杂的预处理
电子变形虫的电路图(左:变形虫芯，右:电阻横杆)
信用:变形虫能源 斋藤贤三博士
D
Kasai实验室的一名学生在实验板上制作了电路，并成功地为4个城市的TSP找到了最短路径
他用电路模拟器评估了大规模问题的性能
然后，该电路可靠地找到了高质量的合法解决方案，其路由长度比通过随机采样获得的平均长度短得多
此外，找到高质量的法律解决方案所需的时间仅与城市数量成线性增长
将搜索时间与典型的TSP算法“2-opt”进行比较，随着城市数量的增加，电子阿米巴变得更加有利
“模拟电路很好地再现了变形虫独特而有效的优化能力，这是生物体通过自然选择获得的，”Kasai说
电子变形虫的搜索性能是城市数量的函数
(左)由电子变形虫(红点)获得的路线长度通过随机取样计算的平均长度来标准化
(右)电子变形虫(红点)和2-opt的解搜索时间在常规计算机(白圈)上运行，其中纵轴代表10个城市TSP结果的增量
信用:Masashi Aono 阿米巴能源公司负责推广阿米巴启发的计算机的实际应用的Masashi Aono说:“由于模拟计算机由简单紧凑的电路组成，它可以解决许多输入、约束和请求动态变化的现实问题，并可以作为节能微芯片嵌入物联网设备。”
来源：由phyica.com整理转载自PH，转载请保留出处和链接！
