通过深度强化学习实现网络解体的多目标优化

《Reliability Engineering & System Safety》：Multi-objective optimization of network disintegration via deep reinforcement learning

多目标网络分解问题需同时优化分解效果与成本，传统方法存在效率低、难以动态适应等局限。本文提出基于深度强化学习的DRL-MND方法，通过神经网络与Actor-Critic算法结合，有效解决Pareto最优解搜索、大规模网络计算及动态结构适应问题，实验表明其效率、解集多样性和扩展性显著优于NSGA-II等经典算法。

　　

李若哲|袁浩|任邦邦|陈涛|罗学山|邓叶

国防科技大学信息系统工程国家重点实验室，中国湖南长沙410073

引言

随着网络科学的迅速发展，复杂网络被广泛用于描述自然界和人类社会中具有网络结构和属性的交互系统[1]。例如社交媒体网络[2]、交通网络[3]、电力网络[4]等。这些网络对人类的生产和生活有益，许多研究致力于维护它们的稳定性和完整性[5]、[6]。然而，也有一些有害的网络，如金融危机网络[7]、传染病传播网络[8]和恐怖组织网络[9]。对于这些网络，我们应该控制并摧毁它们，以减少它们对社会构成的威胁。因此，关于网络瓦解的研究具有重要的实际价值，并且正受到越来越多的关注。

网络瓦解问题是在给定网络中通过移除特定的一组节点或边来最大化削弱网络功能。网络瓦解的本质在于在给定的约束和瓦解目标下，识别出最需要移除的一组节点或边，这可以被视为“关键节点检测”问题的一个变体[10]，也是一个组合优化问题。目前，已经进行了许多研究来通过分析网络结构来寻找关键节点，例如无向网络[11]、有向网络[12]、空间网络[13]、部分观测网络[14]等。此外，瓦解方法也在不断更新，以提高瓦解的效率。它从最初的基于中心性的瓦解策略[15]发展到基于启发式算法的精心设计的瓦解策略[16]，最终发展到基于机器学习的瓦解策略[17]、[18]。

尽管有许多现有工作从分析网络拓扑或改进算法的角度来解决网络瓦解问题，但这些工作最初主要集中在单目标问题上，其中瓦解效果被视为唯一的目标函数[19]、[20]、[21]。实际上，对于决策者来说，选择能够最大化削弱网络功能性的瓦解策略至关重要。此外，最小化瓦解成本也是一个重要的目标。例如，通过攻击一个拥有许多联系的领导者来拆解恐怖组织网络会产生重大影响，但也会带来显著的风险和费用[22]。相反，针对低级别成员进行攻击成本较低，但效果微弱，几乎不会削弱网络的功能性。这两个目标应该同时考虑并优化。因此，本文关注多目标网络瓦解（MND）问题，旨在通过平衡瓦解效果及其相关成本来高效确定最优的瓦解策略。

然而，在尝试解决MND问题时会出现几个挑战：i) 如何找到在瓦解成本和瓦解效果之间取得良好权衡的帕累托最优解？ 这两个目标本质上是相互冲突的。换句话说，最小化瓦解成本往往无法最大化瓦解效果（见第3节中的图2）。传统的网络瓦解方法只能解决单目标优化问题，但很难优化具有两个相互冲突优化目标的问题。ii) 如何在大规模网络瓦解场景中快速生成最优的瓦解策略？ 目前，现有研究主要采用启发式算法来解决具有多个相互冲突目标的网络瓦解问题[23]、[24]。然而，这种方法在寻求近似解时需要大量迭代来更新种群或进行搜索，特别是对于高维问题。这个过程通常会导致优化的运行时间延长。iii) 如何以动态的方式生成瓦解策略？ 现实中的恶意网络结构并不是静态不变的；相反，它不断调整以适应新的情况。例如，在恐怖组织中，成员会根据需要加入或离开网络。一旦网络结构发生微小变化，传统的MND问题启发式方法可能需要重复搜索解决方案，甚至修改算法才能获得满意的结果，这通常被称为“没有免费的午餐”定理。总之，设计一种具有快速解决时间、优秀解决方案质量和强大可扩展性的多目标网络瓦解方法是吸引人且具有挑战性的。

为了解决上述挑战，受到最近在组合优化问题上的深度强化学习（DRL）进展的启发[25]、[26]、[27]，我们提出了一种称为DRL-MND的方法来解决MND问题。总体而言，本工作的主要贡献总结如下：

•

我们将MND问题建模为一个非线性优化问题，在这个问题中，瓦解效果被最大化，同时瓦解成本被最小化，这更适用于现实世界的情况。

•

据我们所知，这是首次尝试应用DRL方法来解决MND问题。所提出的方法通过将深度神经网络与Actor-Critic算法协同整合，有效地在各种约束下寻找最优解。

•

一旦问题实例发生微小变化，传统方法通常需要从头开始搜索，这对于需要紧急解决方案的大规模场景来说并不实际。相比之下，我们的方法对问题变化具有鲁棒性。一旦模型训练完成，它可以有效地解决具有未知网络结构和规模的问题。

•

实验结果表明，所提出的DRL-MND在解决方案多样性、可扩展性和计算效率方面显著优于传统的启发式方法，特别是在大规模MND问题上。

本文的结构如下。我们在第2节介绍了初步知识和相关工作。第3节阐述了MND问题的表述。第4节详细介绍了DRL-MND。第5节展示了一系列实验结果。最后，第6节提出了结论和未来研究的方向。

章节片段

初步知识和相关工作

在本节中，我们介绍了多目标组合优化的基本概念和符号。然后，我们从两个主要方面介绍了相关工作：为解决复杂网络瓦解问题而开发的算法以及DRL在多目标组合优化中的应用。

多目标网络瓦解问题

在本节中，我们首先介绍了详细的MND问题模型，该模型旨在同时优化瓦解效果和成本。然后，我们分析了这个问题模型的复杂性。

提出的DRL-MND方法

在本节中，我们提出了DRL-MND，这是一种简单高效的基于DRL的方法来解决MND问题。首先，我们提出了DRL-MND的总体框架，包括几个重要的解决步骤。接下来，我们重点介绍了神经网络（包括编码器、解码器和注意力机制）如何输出最优解。最后，我们详细介绍了模型参数的训练方法。

性能评估

在本节中，我们首先介绍了实验设置，包括数据集、DRL-MND的参数和基准测试。然后，我们进行了广泛的实验来评估DRL-MND的性能。所有算法都是用Python实现的，所有实验都在配备RTX 3090 GPU、i9-12900K CPU和64 GB RAM的计算机上运行。

结论与讨论

本研究提出了一个多目标复杂网络瓦解模型，旨在在最小化异质相关成本的同时最大化网络瓦解效果。由于传统启发式方法（如NSGA-II）依赖于大量的迭代搜索和庞大的解种群，我们开发了一种基于DRL的方法，称为DRL-MND。实验结果表明，DRL-MND在合成数据和真实数据上的解决方案质量与NSGA-II和NSGA-III相当。

CRediT作者贡献声明

李若哲：写作 – 审稿与编辑，撰写原始草稿，可视化，软件，方法论，概念化。袁浩：写作 – 审稿与编辑，方法论，形式分析。任邦邦：写作 – 审稿与编辑，项目管理，方法论，资金获取，概念化。陈涛：写作 – 审稿与编辑。罗学山：写作 – 审稿与编辑。邓叶：写作 – 审稿与编辑。

利益冲突声明

作者声明他们没有已知的可能会影响本文所述工作的竞争性财务利益或个人关系。