基于深度强化学习的最短路阻断方法和装置

1.一种基于深度强化学习的最短路阻断方法，其特征在于，所述方法包括：获取网络图；所述网络图中的节点为具备通讯功能的网络设备，起始节点和目标节点直接包含多条连接链路，所述网络设备由于攻击方攻击通讯功能损坏时，选择其他最短路径进行通讯；所述网络图表示为G(N,A)，N表示节点集合，A表示链路集合，K＝{α 1 ,α 2 ,…,α k }表示攻击方的有序阻断集合，α i 表示阻断网络图G中的第i个节点，L(G)为网络图G中所有链路的长度之和，L(G\{α 1 ,α 2 ,…,α k })表示按照有序阻断集合K＝{α 1 ,α 2 ,…,α k }的排列顺序依次阻断网络图G中的节点之后，图中的最短路径长度；采用编码器将所述网络图映射至低维向量空间，得到动作表示向量和图状态表示向量；其中，所述动作表示向量是对节点的位置信息、属性信息以及与其他节点的连接关系编码得到的；所述图状态表示向量是通过虚拟节点进行编码得到的，所述虚拟节点与所述网络图中节点相连，并且汇集所述网络图中节点的信息；所述编码器为图神经网络，根据所述图神经网络采用信息汇集方式对所述网络图的图结构进行特征传播，得到图状态表示向量；其中，第n传播轮次时，节点汇集n跳邻居节点的信息；将所述动作表示向量作为强化学习的动作，所述图状态表示向量作为强化学习的状态，输入至解码器中，通过解码器将所述动作和状态建模为深度Q网络，并对所述深度Q网络进行训练，在输入待阻断网络图后，输出所述待阻断网络图的最优阻断方案；对所述最优阻断方案的评价为：ANPL值越小，最优阻断方案越优。 2.根据权利要求1所述的方法，其特征在于，所述通过解码器将所述动作和状态建模为深度Q网络，包括：通过解码器将所述动作和状态建模为深度Q网络为：其中，W 4 ∈R p×1 ，W 5 ∈R p×1 是深度Q网络中可学习参数，z a ，z st ∈R 1×p 分别为所述动作和状态。 3.根据权利要求1所述的方法，其特征在于，所述方法包括：构建用于训练所述深度Q网络的损失函数；所述损失函数包括：学习损失和图重构损失。 4.根据权利要求2所述的方法，其特征在于，构建用于训练所述深度Q网络的损失函数，包括：基于贝尔曼方程，构建用于训练所述深度Q网络的损失函数为：其中，θ Q ＝{θ E ,θ D }，θ E ＝{W 1 ，W 2 ，W 3 }为编码器的学习参数，θ D ＝{W 4 ，W 5 }为解码器的学习参数，α是超参数，γ是折扣因子， 表示目标网络的参数，n是图重构损失中的节点个数，s i,j 表示节点i和节点j是否相连，y i 和y j 则是其表示向量。 5.一种基于深度强化学习的最短路阻断装置，其特征在于，所述装置包括：图获取模块，用于获取网络图；所述网络图中的节点为具备通讯功能的网络设备，起始节点和目标节点直接包含多条连接链路，所述网络设备由于攻击方攻击通讯功能损坏时，选择其他最短路径进行通讯；所述网络图表示为G(N,A)，N表示节点集合，A表示链路集合，K＝{α 1 ,α 2 ,…,α k }表示攻击方的有序阻断集合，α i 表示阻断网络图G中的第i个节点，L(G)为网络图G中所有链路的长度之和，L(G\{α 1 ,α 2 ,…,α k })表示按照有序阻断集合K＝{α 1 ,α 2 ,…,α k }的排列顺序依次阻断网络图G中的节点之后，图中的最短路径长度；编码模块，用于采用编码器将所述网络图映射至低维向量空间，得到动作表示向量和图状态表示向量；其中，所述动作表示向量是对节点的位置信息、属性信息以及与其他节点的连接关系编码得到的；所述图状态表示向量是通过虚拟节点进行编码得到的，所述虚拟节点与所述网络图中节点相连，并且汇集所述网络图中节点的信息；所述编码器为图神经网络，根据所述图神经网络采用信息汇集方式对所述网络图的图结构进行特征传播，得到图状态表示向量；其中，第n传播轮次时，节点汇集n跳邻居节点的信息；解码模块，用于将所述动作表示向量作为强化学习的动作，所述图状态表示向量作为强化学习的状态，输入至解码器中，通过解码器将所述动作和状态建模为深度Q网络，并对所述深度Q网络进行训练，在输入待阻断网络图后，输出所述待阻断网络图的最优阻断方案；对所述最优阻断方案的评价为：ANPL值越小，最优阻断方案越优。 6.根据权利要求5所述的装置，其特征在于，所述解码模块还用于通过解码器将所述动作和状态建模为深度Q网络为：其中，W 4 ∈R p×1 ，W 5 ∈R p×1 是深度Q网络中可学习参数，z a ，z st ∈R 1×p 分别为所述动作和状态。 7.一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，其特征在于，所述处理器执行所述计算机程序时实现权利要求1至4中任一项所述方法的步骤。 8.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1至4中任一项所述的方法的步骤。