1.一种基于深度强化学习的网络全覆盖路径集选择方法,其特征在于,包括:步骤一:根据路径集的大小和冗余度建立优化目标,然后根据边缘节点特性、全覆盖特性和无环特性建立约束,得到网络全覆盖路径集选择模型;
步骤二:将网络全覆盖路径集选择模型转化为马尔可夫决策过程,确定状态空间、动作空间表示,并根据路径集的冗余度设计奖励信号函数;
步骤三:采用Actor‑Critic算法训练一个actor网络和critic网络,actor网络根据当前生成的路径选择下一条链路,然后采用mask机制保证生成的路径的无环性;critic网络通过actor网络与环境交互收集的数据学习一个价值函数,进而帮助actor网络进行策略更新;
步骤四:训练完成后,智能体通过actor网络逐步生成路径,当整个网络被覆盖时,得到网络全覆盖路径集。
2.根据权利要求1所述的一种基于深度强化学习的网络全覆盖路径集选择方法,其特征在于:步骤一中所述的优化目标为最小化路径集P的大小与网络G关于路径集P的冗余度之和,对应的优化目标表达式为:其中,P表示所生成的路径的集合;α、β为平衡因子; 表示网络G关于路径集P的冗余度, 的表达式如下:其中,V为网络G的节点集合, 为链路luv关于路径集P的冗余度, 的表达式如下:其中, 表示如果节点u和节点v之间存在链路相连,并且路径pi包含链路luv,则否则
3.根据权利要求1所述的一种基于深度强化学习的网络全覆盖路径集选择方法,其特征在于:步骤一中所述的边缘节点特性表示路径集P中的路径pi的起始节点和终止节点必须是网络的边缘节点,边缘节点特性对应的约束条件表达式如下:其中, 表示如果节点v(v∈V)在路径pi上,则 否则 hv表示如果节点v是一个边缘节点,则hv=1,否则hv=0;dv表示节点v的度。
4.根据权利要求1所述的一种基于深度强化学习的网络全覆盖路径集选择方法,其特征在于:步骤一中所述的全覆盖特性表示路径集P中的链路必须覆盖整个网络G的链路集合LG,全覆盖特性对应的约束条件表达式如下:其中, 表示如果节点u和节点v之间存在链路相连,并且路径pi包含链路luv,则否则
5.根据权利要求1所述的一种基于深度强化学习的网络全覆盖路径集选择方法,其特征在于:步骤一中所述的无环特性表示路径集P中的路径pi必须为简单路径,不能包含环,无环特性对应的约束条件表达式如下:其中, 表示如果节点v(v∈V)在路径pi上,则 否则 表示如果节点u和节点v之间存在链路相连,并且路径pi包含链路luv,则 否则
6.根据权利要求1所述的一种基于深度强化学习的网络全覆盖路径集选择方法,其特征在于:步骤二中所述的状态空间的表达式如下:其中, 表示当前正在构建的路径的最后一条链路, 表示当前正在构建的路径集的大小, 表示当前已经访问过的链路的数目, 表示当前正在构建的路径。
7.根据权利要求1所述的一种基于深度强化学习的网络全覆盖路径集选择方法,其特征在于:步骤二中所述的动作空间的表达式如下:A={a1,a2,a3,...,aN}
其中N为网络中链路的数目,动作ai表示基于当前正在构建的路径选取第i条链路,并加入到当前路径形成一条新的路径。
8.根据权利要求1所述的一种基于深度强化学习的网络全覆盖路径集选择方法,其特征在于:步骤二中所述的奖励信号函数的表达式如下:其中,M表示当前正在构建的路径集, 表示网络G的边缘节点集合, 表示网络G被路径集M所包含的链路集合,LG表示网络G的链路集合。
9.根据权利要求1所述的一种基于深度强化学习的网络全覆盖路径集选择方法,其特征在于:步骤三中所述的mask机制是指对actor网络输出的下一条链路被选择的概率分布pθ(st)进行mask处理,保证选择的下一条链路与当前构建路径形成的新路径不包含环,从而获得所有的有效链路的概率分布 最后重新归一化 其表达式如下:其中, 为概率分布 的第i个分量,Eva表示与当前构建的路径相连并且不构成环的链路的集合; 为概率分布pθ(st)的第i个分量,表示基于当前的路径生成方案选择第i条链路的概率。