组合优化Combinatorial optimization问题,广泛存在于科学和工业过程。现代深度学习deep learning工具,以前所未有的规模处理了这些问题,不外,结合统计理学学见解的统一框架,仍然很迫切。
近期,美国 亚马逊AWS 量子处理方法实验室(Amazon Quantum Solutions Lab) Martin J. A. Schuetz,J. Kyle Brubaker,Helmut G. Katzgraber,在Nature Machine Intelligence上发帖,报告演示了图神经网络graph neural networks处理组合优化问题。
该办法广泛适用于二次无约束二元优化问题形式的典型NP-hard问题,如最大割maximum cut、最小顶点覆盖minimum vertex cover、最大独立集,以及多项式无约束二元优化问题形式的Ising Spin Glasses及其高阶推广许多方面。
同期,一种驰豫策略relaxation strategy应用于问题哈密顿量,以生成可微分的损失函数,该损失函数可用来训练图神经网络,并在无监督训练过程完成后,简单投影应用于整数变量。标准最大割集和最大独立集问题的数值结果验证了这一办法。
科研发掘,图神经网络优化器性能,相当或优于现有解算器,并且能够扩展到超过现有技术水平,以处理拥有数百万变量的问题。
Combinatorial optimization with physics-inspired graph neural networks
基于理学图神经网络的组合优化。
图1:组合优化图神经网络graph neural networks,GNN办法示意图。
图2:受理学学启发图神经网络GNN优化器的端到端工作流程图。
图3:n=100节点的随机3-正则图的最大割MaxCut示例解。
图4:最大割MaxCut数值结果。
图5:最大独立集maximum independent set,MIS问题的数值结果。
该项科研,提出并分析了一种多功能、可扩展的通用求解器,该求解器由图神经网络GNNS供给支持,并借鉴了统计理学学理念。该办法适用于任何k-局部伊辛k-local Ising模型,包含典型NP-hard组合优化问题,如最大割、最大团、最小顶点覆盖或最大独立集问题等66。从伊辛Ising公式出发,去掉决策变量上的完整性约束,并将驰豫策略relaxation strategy应用于问题哈密顿量,以生成可微损失函数,该损失函数对图神经网络GNN的节点暗示,进行无监督训练。而后,针对图中的每一个顶点,图神经网络GNN训练以生成软分配,预测属于两个类之一的可能性。为了找到与原始问题公式一致二元(双色)标记,采用简单的投影启发式projection heuristics 。
总体而言,这种办法,能够与现有专用求解器竞争,例如设计用于处理最大切割问题的Goemans–Williamson算法,并有可能利用统计理学学的丰富工具箱,例如包含相变科研。在当前中等规模量子时代,该办法能够做为新兴量子技术(包含专用量子6和量子启发退火20)的广泛适用、可扩展基准,同期不受资源限制,亦不局限于QUB形式,相干伊辛机Ising machines亦是如此。
展望:
1、为更好地理解图神经网络GNN,在组合优化环境中的局限性,进一步科研是有序的、系统的图神经网络GNN,与一大类优化问题的最先进解算器,进行基准测试,同期利用图神经网络GNN实现全部全局,包含例如Graphsage或Graph Attention Networks(GATS),以潜在地利用重视力机制,提高图神经网络GNN ansatz,该重视力机制,使得顶点能够在聚合过程时期,对相邻描述neighbour representations进行加权。
2、当在设备集群上,以小批量方式利用分布式训练时,所提出的图神经网络GNN办法,应该能够适应数亿个节点的问题规模,从而挑战几个现有解算器的能力。尽管日前实例,重点触及随机初始化过程,初始节点嵌入问题,但在将来,运用预先训练的权重(迁移学习)起步训练过程,能够加强处理问题的时间。
3、随机投影randomized projection方法,有望潜在地加强优化器性能,或贪心后处理greedy post-processing,加强这些策略,该后处理例程,经过一系列局部位翻转,检测局部最优性。
4、该办法能够推广到超图hypergraphsPUBO问题,其中超边hyper-edges 能够包括两个以上的节点,而不需要资源密集型度缩减方法,这与资源受限QUBO求解器相反。还有潜在的应用,涵盖了多体相互功效的现实世界优化问题,如在调度 scheduling 问题,或化学发掘问题。
总之,设备学习、运筹学和理学学之间的交叉融合,开辟了许多新兴的科研方向,最后目的是进一步加强处理组合优化问题的能力。
文献链接:https://www.nature.com/articles/s42256-022-00468-6
DOI: https://doi.org/10.1038/s42256-022-00468-6
本文译自Nature。