文章提出一种基于深度学习和启发式算法的图卷积网络方法,用于解决某些 NP 困难问题,并在四个 NP 困难问题和五个数据集上进行了评估,结果表明该方法在某些 NP 困难问题上已经达到了高度优化的最新启发式算法的水平,并具有较强的泛化性和扩展性。
Oct, 2018
利用机器学习的分支限界算法,通过比较三个神经网络 —— 图卷积神经网络(GCNN)、GraphSAGE 和图注意力网络(GAT)的结果,在解决有容量限制的车辆路径问题方面展现了潜力。通过训练这些神经网络,以模拟计算代价高昂的 Strong Branching 策略的决策过程。经过严格的实验证明,这种方法可以在较短的计算时间内达到或超过分支限界算法与 Strong Branching 策略的性能,并且所对应的研究结果和方法的源代码在以下网址中可以轻松获得并进行参考。
Oct, 2023
本文提出了一种基于图卷积神经网络的分支定界变量选择新模型,通过模仿学习和强分支专家规则训练,成功解决了组合优化问题。实验结果表明,该方法不仅在分支机制上优于现有的机器学习方法,而且在大问题上也优于现有的专家设计分支规则。
Jun, 2019
本文介绍了一种基于深度学习算法的解决平面欧几里得图中旅行商问题的方法,通过使用图卷积网络构建 TSP 图表示,并通过高度并行化的 Beam Search 非自回归方法输出巡回路径,我们在解决相同节点规模下的问题中比最近提出的自回归深度学习技术表现更好,最终平均优化差距从 50 个节点降低到 0.01%,100 个节点从 2.26%降至 1.39%,尽管相较于标准的运筹学求解器,我们的方法还有所欠缺。
本研究提出了一种新的基于图神经网络的分支启发式方法,用于求解组合优化问题中的最小支配团问题,实验结果表明,该方法相较于最小剩余量策略在分支数上表现更优,为使用图神经网络改进传统的 AI 回溯算法提供了新思路。
Nov, 2022
本文提出了一种聚合图神经网络和指针机制的图指针网络模型来学习分支定界中的变量选择策略,结果表明该模型在求解速度和搜索树大小方面都优于现有的机器学习和专家设计的分支规则。
Jul, 2023
本研究提出了一个开源基准套件,对最大独立集问题进行了深入分析,结果表明现有的机器学习算法未能学习最优解的结构,算法技术仍是获得有效解决方案的关键。
Jan, 2022
本文提出了一种神经组合优化方法,将学习算法与模型架构相结合,以实现在训练过程中看不到的更大规模的问题的推广。通过对零样本推广的原理研究,控制实验提供了第一手数据,并提供了深度学习的新方向。
Jun, 2020
本文介绍了如何使用图神经网络来解决组合优化问题,包括最大割、最小顶点覆盖和最大独立集等一些组合优化问题。通过在问题哈密顿量上应用松弛策略,我们生成了一个可区分的损失函数,并在无监督训练过程结束后对整数变量进行简单的投影。实验表明,我们的方法在解决包含数百万个变量的问题时能够胜任。
Jul, 2021
本文研究如何将深度强化学习和图神经网络应用于无线网络中的电力和信道分配问题,研究结果表明现有结构还不能很好地识别图的结构和特征,并且对于对图产生影响的问题不太适用,但研究还是取得了一些积极进展,比如通过距离编码来增强问题的表示方法。