通过二维材料增强的模拟退火算法，解决组合优化「大问题」

编辑/绿萝

组合优化是在一个有限的对象集中找出最优对象的一类问题，这是一组非常复杂的问题，以至于使用穷举搜索找到最佳解决方案往往是不可行的。这些问题出现在供应链管理、航空公司调度、工业资源分配、人工智能、应用数学和理论计算机科学的各种应用中。

一个著名的例子是旅行推销员问题，推销员必须从 A 市到 B 市再到 C 市到 D 市，但他必须找到最优路线，在最短的时间内访问每个城市一次，然后返回家中。

必须有人解决这些问题，但从计算的角度来看，运行这些算法所需的资源量是巨大的。

来自宾夕法尼亚州立大学的研究人员提出了一种解决方案，该解决方案将模拟退火算法（SA）与称为内存计算的技术相结合。研究人员建议使用模拟退火算法来寻找伊辛自旋玻璃系统的基态。与使用蛮力试验的穷举搜索相比，使用 SA 的 4 × 4 铁磁、反铁磁和自旋玻璃系统的搜索加速 > 800 倍。

该研究以「An Annealing Accelerator for Ising Spin Systems Based on In-Memory Complementary 2D FETs」为题，发布在《Advanced Materials》上。

SA 在存在多个局部最小值的离散问题中是一种出色的优化技术。SA 提供了一个简单的框架，可以在具有任意能源格局的系统上实施，并且它在统计上保证了最佳解决方案。

SA 从物理退火中汲取灵感，将材料加热到其再结晶温度以上，以允许原子重新排列，然后缓慢冷却，以提高其结晶度并达到低能状态。SA 采用随机搜索，允许高能跃迁（「爬山」）以与温度相关的概率来逃避局部最优。

伊辛自旋玻璃系统（Ising spin glass systems）具有自旋无序和「挫折」等特性，并提供了具有大量亚稳态和基态简并性的谨慎组合问题。旋转玻璃是实现 SA 的理想系统。

在这项工作中，研究人员使用基于超薄体二维半导体的内存互补场效应晶体管（FET）探索 SA，即 p 型 WSe2 和 n 型 MoS2 FET。

首先，与在低温下运行的量子计算机不同，其演示是基于室温的，其次，研究人员利用模拟亚阈值传导和模拟可编程性来设计独特的计算原语和退火时间表，与大型忆阻交叉阵列相比，它们实现了更好的能量和面积效率。

此外，这项工作进一步推动了基于 2D FET 的内存计算平台的开发。据我们所知，这是使用新兴材料和设备对 Ising 自旋玻璃系统进行 SA 硬件加速的首次演示。

SA 的硬件实现需要：（1）用于随机自旋翻转的随机数生成器；（2）一个计算单元；（3）一个计算单元来确定「爬山」的成本；（4）硬件机制相当于冶金中的退火/冷却计划。

「为了实现模拟退火，我们在硬件中执行某些计算操作，」该研究的合著者工程科学和力学博士生 Amritanand Sebastian 说。「硬件是使用基于 2D 材料的晶体管实现的。除了执行计算之外，这些晶体管还可以存储信息。我们利用这种内存计算能力，以便以有效的方式执行模拟退火。」

该方法有几个优点：

首先，使用基于 2D 材料的晶体管可以实现超低功耗运行，从而节省能源；

然后，这项工作中使用的乘法器电路非常独特，使我们能够有效地计算自旋系统的能量；

最后，与模拟退火的许多实现不同，实现该工作所需的硬件不需要随着问题的大小而扩展。

可以观察到，旋转玻璃系统中的「挫败感」。值得注意的是，与使用 BFT 的穷举搜索相比，SA 加速了搜索，需要数量级的低自旋翻转事件。铁磁、反铁磁和自旋玻璃系统的最高加速度分别为≈1365×、≈1260×和≈1310×，而收敛到其基态的系统的平均加速度分别为 ≈850×，≈900×，≈810×。

使用 2D 材料来实现这一目的是有意义的，因为 2D 材料通常具有未来电子产品的潜力，并且可能是硅技术的替代品。

「我们都知道硅技术正在老化，即使它仍然是一种非常难以抗衡的非常粗糙的技术，」Das 说。「但我们也知道，20 年后，我们可能不得不增强硅技术，如果不能完全取代它的话。二维材料的独特功能非常适合我们在这项研究中的目的，使其成为在某一时刻取代硅的主要候选材料之一。」

论文链接：https://doi.org/10.1002/adma.202107076

参考内容：https://techxplore.com/news/2022-01-big-problems-algorithms-2d-materials.html