东芝的新算法可快速为复杂问题提供高度准确的解决方案

东芝公司和东芝数字解决方案公司(统称东芝)，它们是大规模优化问题解决方案的行业领导者，今天宣布了弹道模拟分叉算法(bSB)和离散模拟分叉算法(dSB)，这些新算法远远超过了性能东芝先前的模拟分叉算法(SB)。新算法将用于在组合管理，药物开发和物流管理等不同领域中找到高度复杂问题的解决方案。

前SB在2019年4月推出，为寻找组合优化问题的解决方案提供了新平台，比其他方法高出10倍。东芝现在通过两种新算法扩展了这一成就将诸如准量子隧穿效应之类的创新方法应用于性能改进，从而使他们能够针对挑战其前身能力的大规模组合优化问题获得最佳解决方案(精确解决方案)。在一台16 GPU的机器上实施，dSB可以在30分钟内找到百万位问题的近乎最佳的解决方案，这是迄今为止科学论文中报道的全球最大规模的组合问题，对于典型的计算而言，这需要14个月的时间基于CPU的计算机。研究结果于2月3日发表在在线学术期刊《科学进展》上。

新算法具有不同的特征。bSB经过优化并以运行速度命名，并在短时间内找到了良好的近似解决方案。与以前报告的绝热模拟分叉算法(aSB)相比，它产生的错误更少，因此返回的结果更快，更准确。它在被称为弹道仿真分叉机(bSBM)的现场可编程门阵列(FPGA)上实现，可很好地解决2,000位问题，比以前的aSB机(aSBM)快10倍(图1)。

dSB是一种高精度算法。尽管是在经典计算机中实现的，但是它比当前的量子机器更快地找到了最佳解决方案。它的名称源于用运动方程中的离散变量替换连续变量。这表现出一种准量子隧穿效应，该效应突破了经典力学基础上方法的局限性，从而达到了2000位问题的最佳解决方案。

东芝已经在FPGA上实现了dSB，并构建了一个分立的模拟分叉机(dSBM)，就获得各种问题的最佳解决方案所需的计算时间而言，该分叉机的速度比其他机器要高(图2)。

dSBM在16-GPU机器上实施，解决了100万比特的问题，这是科学论文中所报道的最大问题，并在30分钟内达到了几乎最佳的解决方案，比基于CPU的模拟退火机快20,000倍，计算将需要14个月的时间(图3)。

在将这两种算法应用于实际问题时，东芝为需要立即响应的应用程序建议使用bSB，为要求高精度的应用程序建议使用dSB，即使这需要花费更长的时间。

东芝希望新算法能够解决投资组合，药物开发和交付路线规划等领域的组合优化问题，从而为行业，企业和复杂的决策带来更高的效率。

东芝公司研究与发展中心首席科学家Hayato Goto在评论算法时说：“我们面临着许多现实世界的问题，我们必须在众多选择中找到最佳解决方案，并且我们还必须应对组合爆炸，其中的组合模式成倍增加的数量在规模增加的问题，这就是为什么研究专用计算机的组合优化正在开展全球。我们的目标是开发一种软件解决方案-algorithms可以解决大快速准确地解决大规模组合优化问题，并有助于实现更高的效率。”

东芝将在2021年内提供新开发的模拟分叉算法，作为基于GPU的云服务以及在FPGA上实现的本地版本。

　　免责声明：本文由用户上传，与本网站立场无关。财经信息仅供读者参考，并不构成投资建议。投资者据此操作，风险自担。 如有侵权请联系删除！