|
|
DSP-Transformer：基于注意力机制的最小支配集问题求解方法
|
Abstract:
最小支配集问题在计算机科学与网络优化领域具有广泛应用，但其NP-完全性使得传统启发式方法计算成本高且难以泛化。本文提出了DSP-Transformer，一种基于Transformer结构的深度强化学习求解方法，通过编码器–解码器架构与近似策略优化方法，高效求解最小支配集问题。由于注意力机制更适合捕获图上的潜在关系，相较于传统基于消息传递机制的编码器，本方法在性能上也有显著提升。实验结果表明，该方法在T1基准数据集和ER随机图合成数据集上的表现优于传统启发式算法，能够提供更优质的解，同时显著减少计算成本。DSP-Transformer预训练后可泛化到更大规模的图实例，无需每次重新搜索，展现出深度学习在求解组合优化问题中的巨大潜力。
The Minimum Dominating Set Problem has widespread applications in computer science and network optimization. However, its NP-completeness makes traditional heuristic methods computationally expensive and difficult to generalize. In this paper, we propose DSP-Transformer, a deep reinforcement learning approach based on the Transformer architecture, which efficiently solves DSP through an encoder-decoder framework and approximate policy optimization. Since the attention mechanism is better suited for capturing latent relationships in graphs, our approach achieves significant performance improvements over traditional message-passing-based encoders. Experimental results demonstrate that DSP-Transformer outperforms conventional heuristic algorithms on both the T1 benchmark dataset and ER random graphs, providing higher-quality solutions while significantly reducing computational costs. Once pretrained, DSP-Transformer can generalize to larger graph instances without requiring repeated searches, highlighting the potential of deep learning in tackling combinatorial optimization problems.
| [1] | Du, D.-Z. and Wan, P.-J. (2012) Connected Dominating Set: Theory and Applications. Springer Science & Business Media. |
| [2] | Haynes, T. W. Hedetniemi, S. and Slater, P. (2013) Fundamentals of Domination in Graphs. CRC Press. https://doi.org/10.1201/9781482246582 |
| [3] | Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C. and Yu, P.S. (2021) A Comprehensive Survey on Graph Neural Networks. IEEE Transactions on Neural Networks and Learning Systems, 32, 4-24. https://doi.org/10.1109/tnnls.2020.2978386 |
| [4] | Silver, D., Huang, A., Maddison, C.J., Guez, A., Sifre, L., van den Driessche, G., et al. (2016) Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature, 529, 484-489. https://doi.org/10.1038/nature16961 |
| [5] | Sutton, R.S. and Barto, A.G. (2018) Reinforcement Learning: An Introduction, 2nd Edition, The MIT Press. |
| [6] | Ore, O. (1962) Theory of Graphs. American Mathematical Society. https://books.google.com.sg/books?id=g85UAAAAYAAJ |
| [7] | Bondy, J.A. and Murty, U.S.R. (2010) Graph Theory. Springer. |
| [8] | Haynes, T.W., Hedetniemi, S.T. and Henning, M.A. (2020) Topics in Domination in Graphs. Springer. https://link.springer.com/book/10.1007/978-3-030-51117-3 |
| [9] | Tarr, J. (2010) Domination in Graphs. USF Tampa Graduate Theses and Dissertations. https://digitalcommons.usf.edu/etd/1786 |
| [10] | Alanko, S., Crevals, S., Isopoussu, A., Östergård, P. and Pettersson, V. (2011) Computing the Domination Number of Grid Graphs. The Electronic Journal of Combinatorics, 18, 1-18. https://doi.org/10.37236/628 |
| [11] | Anand, R., Aggarwal, D. and Kumar, V. (2017) A Comparative Analysis of Optimization Solvers. Journal of Statistics and Management Systems, 20, 623-635. https://doi.org/10.1080/09720510.2017.1395182 |
| [12] | Hopfield, J.J. and Tank, D.W. (1985) “Neural” Computation of Decisions in Optimization Problems. Biological Cybernetics, 52, 141-152. https://doi.org/10.1007/bf00339943 |
| [13] | Bello, I., Pham, H., Le, Q.V., Norouzi, M. and Bengio, S. (2016) Neural Combinatorial Optimization with Reinforcement Learning. arXiv: 1611.09940. https://doi.org/10.48550/arXiv.1611.09940 |
| [14] | Vinyals, O., Fortunato, M. and Jaitly, N. (2015) Pointer Networks. Advances in Neural Information Processing Systems 28 (NIPS 2015). https://papers.nips.cc/paper/2015/hash/29921001f2f04bd3baee84a12e98098f-Abstract.html |
| [15] | Deudon, M., Cournut, P., Lacoste, A., Adulyasak, Y. and Rousseau, L. (2018) Learning Heuristics for the TSP by Policy Gradient. Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Delft, 26-29 June 2018, 170-181. https://doi.org/10.1007/978-3-319-93031-2_12 |
| [16] | Chen, X. and Tian, Y. (2019) Learning to Perform Local Rewriting for Combinatorial Optimization. Proceedings of the 33rd International Conference on Neural Information Processing Systems, Vancouver, 8-14 December 2019, 6281-6292. |
| [17] | Chen, M., Liu, S. and He, W. (2024) Learn to Solve Dominating Set Problem with GNN and Reinforcement Learning. Applied Mathematics and Computation, 474, Article 128717. https://doi.org/10.1016/j.amc.2024.128717 |
| [18] | Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., et al. (2017) Attention Is All You Need. Proceedings of the 31st International Conference on Neural Information Processing Systems, Long Beach, 4-9 December 2017, 6000-6010. https://proceedings.neurips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf |
| [19] | Kool, W., van Hoof, H. and Welling, M. (2019) Attention, Learn to Solve Routing Problems! arXiv: 1803.08475. https://doi.org/10.48550/arXiv.1803.08475 |
| [20] | Schulman, J., Wolski, F., Dhariwal, P., Radford, A. and Klimov, O. (2017) Proximal Policy Optimization Algorithms. arXiv: 1707.06347. https://doi.org/10.48550/arXiv.1707.06347 |
| [21] | Erdös, P. and Rényi, A. (2011) On the Evolution of Random Graphs. In: Newman, M., Barabási, A.-L. and Watts, D.J., Eds., The Structure and Dynamics of Networks, Princeton University Press, 38-82. https://doi.org/10.1515/9781400841356.38 |
| [22] | Dai, H., Khalil, E.B., Zhang, Y., Dilkina, B. and Song, L. (2017) Learning Combinatorial Optimization Algorithms over Graphs. arXiv: 1704.01665. https://doi.org/10.48550/ARXIV.1704.01665 |
| [23] | Jovanovic, R., Tuba, M. and Simian, D. (2010) Ant Colony Optimization Applied to Minimum Weight Dominating Set Problem. Proceedings of the 12th WSEAS International Conference on Automatic Control, Modelling & Simulation, Catania, 29-31 May 2010, 322-326. |
