首页>>生活 >>内容

用于解决现实世界组合优化问题的新型基于多策略的退火器

发布时间:2023-02-19 10:35:38编辑:愉快的缘分来源:

东京工业大学的研究人员设计了一种可扩展到多芯片系统并具有多策略机制的全连接退火器,以快速有效地解决与现实场景相关的广泛组合优化(CO)问题。该退火炉名为Amorphica,具有根据特定目标CO问题微调参数的能力,在物流、金融、机器学习等方面具有潜在应用。

用于解决现实世界组合优化问题的新型基于多策略的退火器

现代世界已经习惯了在我们家门口高效地交付货物。但是您是否知道实现这样的效率需要解决一个数学问题,即所有目的地之间的最佳路线是什么?这被称为“旅行商问题”,属于一类称为“组合优化”(CO)问题的数学问题。

随着目的地数量的增加,可能的路线数量呈指数增长,基于穷举搜索最佳路线的蛮力方法变得不切实际。相反,采用一种称为“退火计算”的方法来快速找到最佳路线,而无需进行详尽搜索。

然而,东京工业大学研究人员进行的一项数值研究表明,虽然存在许多退火计算方法,但没有一种方法适用于解决广泛的CO问题。因此,需要一种以多种退火方法为特征的退火机制(多策略机制)来针对各种此类问题。

幸运的是,由东京工业大学(TokyoTech)的助理教授KazushiKawamura和MasatoMotomura教授领导的同一个研究小组报告了一种新的退火炉,该退火炉具有这种多策略方法或“变质退火”。他们的发现发表在ProceedingofISSCC2023上,并将在即将举行的2023年国际固态电路会议上发表。

“在退火计算中,CO问题表示为(伪)自旋向量的能量函数。我们从最初随机化的自旋向量配置开始,然后随机更新它以通过减少其(伪)来找到最小能量状态温度。这与金属的退火过程密切相关,在该过程中,热金属以受控方式冷却下来,”Kawamura博士解释道。“我们名为Amorphica的退火炉具有多种退火方法,包括我们团队提出的一种新方法。这使其能够针对手头的特定CO问题采用退火方法。”

该团队设计Amorphica是为了解决以前退火炉的局限性,即它们的适用性仅限于少数CO问题。这首先是因为这些退火炉是局部连接退火炉,这意味着它们只能处理具有局部自旋间耦合的自旋模型。另一个原因是它们在退火方法和参数控制方面不具有灵活性。这些问题在Amorphica中通过采用全连接自旋模型并结合精细可控的退火方法和参数得到了解决。此外,该团队引入了一种称为“比例控制并行退火”的新退火策略,以提高现有退火方法的收敛速度和稳定性。

此外,Amorphica可以扩展为多芯片、全连接​​系统,减少芯片间数据传输。在针对GPU测试Amorphica时,研究人员发现它的速度提高了58倍,而功耗仅为(1/500),这意味着它的能效提高了约30k倍。

“有了像Amorphica这样的全连接退火炉,我们现在可以处理任意拓扑结构和自旋间耦合密度,即使它们是不规则的。这反过来又可以让我们解决现实世界中的CO问题,例如相关问题到物流、金融和机器学习,”Motomura教授总结道。