Jun, 2024

图上最大覆盖问题的深度强化学习方法对比研究

PDF
TL;DR这篇论文通过全面的基准研究，调查了五种最近的深度强化学习方法在最大覆盖问题和影响最大化问题中的有效性和效率，并发现在最大覆盖问题中，Lazy Greedy 算法一直优于所有深度强化学习方法，而在影响最大化问题中，IMM 和 OPIM 算法在大多数场景下表现出优秀性能，但当影响范围几乎不随预算增加而增加时，深度强化学习方法略优于 IMM 和 OPIM 算法。此外，实验结果还突显了在实际场景中应用深度强化学习方法解决最大覆盖问题和影响最大化问题时的一些常见问题，并讨论了提高深度强化学习方法的潜在途径。该基准研究揭示了当前深度强化学习在解决组合优化问题方面可能面临的挑战。
发现论文，激发创造
  • 深度图表示学习与优化用于影响最大化

    该研究提出了一个名为 DeepIM 的新框架，旨在解决学习为基础的影响最大化（IM）方法所面临的困难，该方法可以数据驱动地、端到端地学习多样化的信息传播模式，并设计了一个新的目标函数来推断出在灵活的基于节点中心性的预算约束下的最优种子集。

    May, 2023

  • 通过深度强化学习在大规模图上学习启发式算法

    本文介绍了一种名为 GCOMB 的框架，利用概率贪心机制通过训练图卷积网络 (GCN) 预测一个节点的质量，以此解决图上的组合问题。实验表明，GCOMB 比学术界最先进的组合算法快 100 倍、质量略高。此外，GCOMB 在实际的 Influence Maximization（IM）组合问题上也展现了强大的性能。

    Mar, 2019

  • DISCO: 影响力最大化遇上网络嵌入和深度学习

    本文提出了 DISCO 框架，该框架集成了网络嵌入和深度强化学习技术以解决影响最大化问题。实验结果表明，相对于传统解决方案，DISCO 具有更好的效率和影响范围质量，并且表现出良好的通用性。

    Jun, 2019

  • 在复杂网络中寻找影响因素：一种有效的深度强化学习方法

    为了解决复杂网络中最大化影响力的任务的效率和性能问题，本论文提出了一种名为 DREIM 的深度强化学习模型，它采用图神经网络作为编码器，采用强化学习作为解码器，通过在小型合成图上进行大量训练，在解决质量上超越了传统最佳影响力最大化算法，并展示了其对网络规模的线性可扩展性，从而证明了其优越性。

    Sep, 2023

  • 强化学习的组合探索优化

    在解决复杂优化问题方面，探索式组合优化（ECO-DQN）通过连续改进解决方案，从而有效地学习有效的启发式方法来解决图上的组合优化问题，并在最大割问题上展示了最先进的强化学习性能。

    Sep, 2019

  • 使用强化学习的受限组合优化

    本文提出一个深度强化学习的框架来解决受限的组合优化问题，将受约束的组合问题定义为完全可观的受约束马尔可夫决策过程（CMDP），并提出从不满足的约束产生惩罚信号，以推断作为启发式算法的策略。通过对约束工厂和资源分配问题进行的实验表明，本文的提议对于比较经典的启发式算法、元启发式算法和约束编程（CP）求解器来说，能更快地求得答案。

    Jun, 2020

  • 可逆行动设计与强化学习在组合优化中的应用

    利用图神经网络和深度 Q 学习的强化学习方法，针对组合优化问题提出了一种无需问题特定设计即可实现状态最优化策略搜索的通用模型，并在最大 k-Cut 问题和旅行商问题上实验验证了其优越性。

    Feb, 2021

  • 在图上学习组合优化算法

    本文介绍了结合强化学习和图嵌入的方法，使用元算法来解决 NP-hard 组合优化问题和图上的最小点集覆盖、最大割和旅行商问题等优化问题。

    Apr, 2017

  • 离线强化学习和模仿学习的联系：一则悲观的故事

    提出了一种新的离线强化学习框架，将模仿学习和通用离线强化学习相结合，中心思想是测量从行为策略到专家策略的偏差，进一步研究了针对未知数据分布下的算法设计问题，提出了一种基于悲观策略的下限置信度算法 LCB，在多臂赌博机、情境赌博机和马尔可夫决策过程中进行了有限样本性能研究，结果揭示了一些有关最优性率的令人惊讶的事实。

    Mar, 2021

  • 面向影响最大化的无模型在线学习

    该论文考虑了社交网络中的影响最大化问题，提出了一种可快速从数据中学习的新颖参数化框架并开发了 LinUCB 算法来解决问题。

    Mar, 2017