基于强化学习的距离约束的最大加权目标覆盖问题研究

A Reinforcement Learning Framework for Solving the Maximum Weighted Target Cover Problem with Distance Limitations

摘要: 距离约束的最大加权目标覆盖问题(MaxWTCDL)是一个NP-难组合优化问题。传统的启发式和近似算法在处理此问题时，往往容易陷入局部最优，难以求解。为了解决这些挑战，我们提出了一种基于强化学习的方法来求解MaxWTCDL问题。首先，我们将该问题重新表述为最大预算分组集合覆盖问题(MaxBGSC)的一个特例。我们将该问题建模为马尔可夫决策过程，并采用Q-learning算法来学习有效的传感器移动策略。实验结果表明，所提出的强化学习方法相比传统算法取得了更优越的性能，突显了其在高效解决带有距离约束的复杂覆盖问题方面的潜力。

Abstract: The Maximum Weighted Target Cover Problem with Distance Limitations (MaxWTCDL) is an NP-hard combinatorial optimization problem. Traditional heuristic and approximation algorithms often struggle with this problem due to a tendency to converge to local optima. To address these challenges, we propose a reinforcement learning-based approach for solving the MaxWTCDL problem. Specifically, we reformulate the problem as a special case of the Maximum Budgeted Group Set Cover Problem (MaxBGSC). We model the problem as a Markov Decision Process and employ the Q -learning algorithm to learn effective sensor movement strategies. Experimental results demonstrate that the proposed reinforcement learning method achieves superior performance compared to traditional algorithms, highlighting its potential in efficiently solving complex coverage problems with distance constraints.

1. 引言

目标覆盖问题作为无线传感器网络中的一个基本问题，具有广泛的应用，例如农业监测[1]、环境应用[2]以及工业检查[3]。目标覆盖问题这一主题吸引了许多研究人员的关注，目前已经有许多综述和专著[4]-[7]。已有诸多研究表明，传感器移动所消耗的能量远大于监测所消耗的能量[8] [9]。基于这一观察，许多研究人员针对在满足一定覆盖要求的前提下最小化移动距离的问题展开了研究[10]-[12]，还有一些研究对单个传感器加入了移动距离限制[13]。

在实际场景中，传感器数量有限、传感器能量受限以及环境因素等约束条件常常可能使我们无法实现完全覆盖。在这种情况下，一个很自然的问题就是如何有效地安排有限的资源，以覆盖最关键的目标。基于这样的考虑，Jin等人提出了距离约束的最大加权目标覆盖问题(MaxWTCDL) [14]。给定平面上的一组目标，每个目标都有一个表示其重要程度的权重，MaxWTCDL的目标是在单个移动距离约束和总距离约束下移动移动传感器，使得被覆盖目标的权重最大化。距离约束的最大加权目标覆盖问题(MaxWTCDL)是一个经典的组合优化问题，同时，在2024年被Jin等人证明是NP难问题，目前仅有两种多项式时间的近似算法求解这个问题，分别是贪心算法和随机线性规划算法。

组合优化问题作为计算机科学和运筹学的基本问题在过去几十年中受到了理论和算法设计社区的广泛关注[15]-[18]。解决NP难问题的传统方法包括精确算法、近似算法和启发式算法。多项式时间近似算法通常可以带来质量保证的解，但其优化保证不如精确算法强。特别是对于不适用于多项式近似算法的问题，可能根本不存在优化保证。此外，许多解决组合优化问题的传统算法都涉及到使用手工设计的启发式方法，这些方法会顺序地构建解决方案。这些启发式方法是由领域专家设计的，可能由于问题的复杂性而常常不是最优的[19]。

对此，强化学习(RL)提出了一个很好的替代方案，通过以监督或自监督的方式训练智能体来自动化这些启发式的搜索[20]-[22]。此外，一些研究将强化学习与传统启发式算法结合，通过智能体自动学习启发式规则，显著提升了算法效率和适用性[23]-[25]。

相关工作

强化学习近年来在组合优化领域得到了广泛且有效的应用，这为目标覆盖等类似问题的求解提供了重要的方法论参考。

Khalil等人(2017)率先提出将图组合优化问题建模为序列决策过程，其框架结合了拟合Q学习与图嵌入技术，通过贪婪策略逐步构造解，并在最小顶点覆盖、最大割及旅行商等经典问题上验证了所习得启发式方法的优越性与泛化能力[26]。

Hu等人(2020)针对多旅行商问题的复杂性，设计了基于共享图神经网络与分布式策略网络的架构，将原问题分解为多个并行的子问题进行求解，其采用的S样本批量训练方法有效提升了学习稳定性，在求解质量与速度上均超越传统方法[27]。

Wang等人(2023)则聚焦于无容量限制的P-中值问题，利用图注意力网络与多对话头机制学习节点表示，并在REINFORCE算法框架下进行训练，取得了质量与效率的较好平衡[28]。

Guo等人(2023)进一步提出了基于交换操作的深度强化学习方法，将设施重定位建模为马尔可夫决策过程，采用近端策略优化进行训练，并结合模仿学习与密度初始化策略，显著提升了求解性能与收敛速度[29]。

受先前工作的启发，我们采用强化学习框架来解决MaxWTCDL问题。我们提出的方法可以自适应地调整传感器的移动策略，以最大化被覆盖的总权重，同时遵守单个和总移动距离约束。

2. 研究问题

2.1. MaxWTCDL问题定义

给定平面上的$n$ 个目标$T=\left\{t_1,t_2,\cdots ,t_n\right\}$ ，其中$n\ge 1$ 为正整数，每个目标$t_j\left(j=1,\cdots ,n\right)$ 具有权重$w_j\left(j=1,\cdots ,n\right)$ ，$m$ 个移动传感器$S=\left\{s_1,s_2,\cdots ,s_m\right\}$ 随机部署在平面上，其中$m\ge 1$ 是正整数，感知半径$r>0$ ，每个传感器的移动距离约束$b>0$ 以及所有传感器的总移动距离约束$B$ ，其中$B>b$ ，MaxWTCDL问题的目标是在距离约束$b$ 和$B$ 内移动移动传感器，使得被覆盖目标的总权重最大化。

为了便于定量分析和计算传感器与目标之间的空间关系，我们将平面建模为二维坐标网格。

Figure 1. Distribution of sensors and targets on a discrete grid

图1. 离散网格上的传感器和目标的分布

在图1中，传感器和目标分布在1000 × 1000的二维离散网格上。红色五角星表示传感器$s_i\left(i=1,2,\cdots ,7\right)$ ，蓝色圆点表示目标$t_j\left(j=1,2,\cdots ,50\right)$ 。蓝色圆点的大小对应于目标$t_j\left(j=1,2,\cdots ,50\right)$ 的权重$w_j$ 。任何网格点$locatio{n}_{xy}\left(x=0,1,\cdots ,1000;y=0,1,\cdots ,1000\right)$ 都是传感器放置的潜在候选点。传感器$s_i\left(i=1,2,\cdots ,7\right)$ 周围半径为$r$ 的红色虚线圆圈表示其覆盖区域；如果目标$t_j\left(j=1,2,\cdots ,50\right)$ 到$s_i$ 的欧几里得距离小于$r$ ，则认为该目标被覆盖。设$d\left(s_i,locatio{n}_{xy}\right)$ 表示传感器$s_i\left(i=1,2,\cdots ,7\right)$ 重新定位到网格点$locatio{n}_{xy}\left(x=0,1,\cdots ,1000;y=0,1,\cdots ,1000\right)$ 所需的移动距离。在单个移动距离约束$b$ 下，每个传感器$s_i\left(i=1,2,\cdots ,7\right)$ 都有一个相应的可移动区域$E_i\left(i=1,2,\cdots ,7\right)$ ，由图1中的绿色虚线圆圈表示。因为传感器的移动收到了总移动距离$B$ 的限制，所以问题的解空间是$E_1\cup E_2\cup \cdots \cup E_7$ 的一个有限离散的子集合。

MaxWTCDL问题可以近似表示为0-1整数规划模型。在这个0-1整数规划模型中，$y_k\left(k=1,2,\cdots ,n\right)$ 表示目标$t_k\left(k=1,2,\cdots ,n\right)$ 是否被覆盖，其中$y_k\in \left\{0,1\right\}$ 。$x_{ijz}\left(i=1,2,\cdots ,m;j=1,2,\cdots ,p;z=1,2,\cdots ,q;p,q\in Z_{\ge 1}\right)$ 表示传感器$s_i\left(i=1,2,\cdots ,m\right)$ 是否移动到位置坐标$locatio{n}_{jz}\left(j=1,2,\cdots ,p;z=1,2,\cdots ,q;p,q\in Z_{\ge 1}\right)$ 。符号$d_{ijz}$ 和$g_i$ 的定义可以在第2.3节中找到。

$\max {\displaystyle {\sum }_{k=1}^n{w}_k{y}_k}$

$\text{s}\text{.t}.y_k\le {\displaystyle {\sum }_{i=1}^m{\displaystyle {\sum }_{jz:t_k\in A_{ijz}}{x}_{ijz}}}\forall k=1,2,\cdots ,n$

${\displaystyle {\sum }_{jz:A_{ijz}\in g_i}{x}_{ijz}}\le 1\forall i=1,2,\cdots ,m$

${\displaystyle {\sum }_{i=1}^m{\displaystyle {\sum }_{jz:t_k\in A_{ijz}}{x}_{ijz}\cdot d_{ijz}}}\le B$

$x_{ijz}\in \left\{0,1\right\}\forall i=1,2,\cdots ,m\text{and}{A}_{ijz}\in G_i$

$y_k\in \left\{0,1\right\}\forall k=1,2,\cdots ,n$

2.2. 工作流程

本文在强化学习框架内解决MaxWTCD问题，利用Q-learning算法。所提出方法的具体工作流程如图2所示。

Figure 2. Flowchart of the reinforcement learning algorithm framework

图2. 强化学习算法框架流程图

解决MaxWTCDL问题取决于找到最优的传感器移动策略${\pi }_0$ 。最优移动策略结果是一个传感器移动动作集$g^{\prime }=\left\{{a^{\prime }}_1,{a^{\prime }}_2,\cdots ,{a^{\prime }}_n\right\}$ ，其中${a^{\prime }}_i=\left(1,2,\cdots ,n\right)$ 表示传感器$s_i=\left(1,2,\cdots ,n\right)$ 在策略${\pi }_0$ 下的最优动作结果。每个传感器$s_i$ 在执行动作${a^{\prime }}_i$ 后，获得一个新的分布位置。在第2.3节中，我们将 MaxWTCDL问题重新表述为MaxBGSC的一个特例。在第2.4节中，基于强化学习框架，将研究问题建模为马尔可夫决策过程，并使用Q-learning算法进行求解。

2.3. 最大预算分组集合覆盖(MaxBGSC)问题

假设$T=\left\{t_1,\cdots ,t_n\right\}$ 是要覆盖的元素集合，其中$n\ge 1$ 是正整数。每个目标$t_j\left(j=1,2,\cdots ,50\right)$ 有一个权重$w_j\left(j=1,\cdots ,n\right)$ 。设$g$ 是$T$ 的子集集合，分为$m$ 组$g=g_1\cup g_2\cup \cdots \cup g_m$ ，其中$m\ge 1$ 是正整数。每个子集$A\in g$ 都有一个成本$c\left(A\right)$ 。设$B>0$ 为总预算，$n_1,n_2,\cdots ,n_m$ 为$m$ 个正整数。MaxBGSC的目标是选择一个子集集合$g^{\prime }\subseteq g$ ，使得：

• $c\left(g\right)={\displaystyle {\sum }_{A\in g^{\prime }}c\left(A\right)}\le B$ ；

• 每个组$g_i$ 有$\left|g_i\cap g\right|\le n_i\left(i=1,2,\cdots ,m\right)$ ，且；

• $w\left(C\left(g\right)\right)={\displaystyle {\sum }_{t_j\in C\left(g^{\prime }\right)}{w}_j}$ 最大化。

其中$C\left(g\right)={\displaystyle {\cup }_{A\in g^{\prime }}A}$ 是被$g^{\prime }$ 覆盖的元素集合。

MaxWTCDL问题可以看作是MaxBGSC问题的一个特例。每个传感器$s_i\left(i=1,2,\cdots ,m\right)$ 对应于一组子集$g_i=\left\{A_{i00},A_{i01},\cdots ,A_{ipq}\right\}$ ，其中$A_{ixy}\left(i=1,2,\cdots ,m;x=0,1,\cdots ,p;y=0,1,\cdots ,q;p,q\in Z_{\ge 1}\right)$ 表示在移动距离约束条件$b>0$ 下，传感器$s_i\left(i=1,2,\cdots ,m\right)$ 可以移动到位置$locatio{n}_{ij}\left(i=1,2,\cdots ,p;j=1,2,\cdots ,q;p,q\in Z_{\ge 1}\right)$ 然后覆盖所有距离小于$r$ 的目标。定义$A_{ijz}\left(i=1,2,\cdots ,m;j=1,2,\cdots ,p;z=1,2,\cdots ,q;p,q\in Z_{\ge 1}\right)$ 对应的成本为：

$c\left(A_{ixy}\right)=\{\begin{array}{ll}{d}_{ijz},\hfill & \text{if}{d}_{ijz}\le b\hfill \\ +\infty ,\hfill & \text{if}{d}_{ijz}>b\hfill \end{array}$

这里，$d_{ijz}\left(i=1,2,\cdots ,m;j=1,2,\cdots ,p;z=1,2,\cdots ,q;p,q\in Z_{\ge 1}\right)$ 表示传感器$s_i\left(i=1,2,\cdots ,m\right)$ 初始位置到$locatio{n}_{xy}\left(x=1,2,\cdots ,p;y=1,2,\cdots ,q;p,q\in Z_{\ge 1}\right)$ 的欧几里得距离。如果$d_{ixy}\le b$ ，这意味着$s_i$ 可以移动到$locatio{n}_{xy}$ ，因此$c\left(A_{ixy}\right)$ 等于$d_{ixy}$ 。如果$d_{ixy}>b$ ，这意味着$s_i$ 无法移动到$locatio{n}_{xy}$ ，因此$c\left(A_{ixy}\right)$ 等于$+\infty$ 。设$n_1=n_2=\cdots =n_m=1$ ，且$g=g_1\cup g_2\cup \cdots \cup g_m$ 。

在这种情况下，选择满足约束条件$c\left(g^{\prime }\right)\le B$ 的子集$g^{\prime }\subseteq g$ 等价于所有传感器$s_i\left(i=1,2,\cdots ,m\right)$ 在其可移动区域$E_i\left(i=1,2,\cdots ,m\right)$ 内执行动作$A_{ixy}\left(i=1,2,\cdots ,m;x=0,1,\cdots ,p;y=0,1,\cdots ,q;p,q\in Z_{\ge 1}\right)$ ，对应于产生所有距离成本${\displaystyle {\sum }_{i=1}^{m}c\left(A_{ixy}\right)}\le B$ 。

2.4. $\mathcal{Q}$ -Learning强化学习算法

$\mathcal{Q}$ -Learning是一种无模型强化学习算法，用于在没有先验环境信息的情况下在给定环境中找到最优策略。它允许智能体在环境中不断尝试、探索和学习，根据收到的奖励反馈调整对动作价值的评估，从而逐渐找到最优动作策略。

2.4.1. 算法框架

我们在强化学习框架内将我们的研究问题制定为马尔可夫决策过程(MDP)。MDP的关键组成部分定义如下：

• 状态空间$\mathcal{S}$ ：状态空间$\mathcal{S}$ 包含系统的所有可能状态。在本研究中，时间步$t$ 的状态$s_t\in S$ 由所有目标和传感器的位置定义，因为目标是不可移动的，状态$s_t$ 主要是由传感器来决定的。因为连续的空间是太难以建模，本文一般对空间采用离散化处理的方式，例子说明如章节2.1所示。传感器移动受到移动距离$b$ 和$B$ 的限制，所以传感器的移动空间是$E_1\cup E_2\cup \cdots \cup E_m$ 的一个有限离散的子集合。

• 动作空间$\mathcal{A}$ ：动作空间$\mathcal{A}$ 由给定状态下任何传感器的所有可行移动组成。动作$a_t\in \mathcal{A}\left(s_t\right)$ 对应于特定传感器的移动决策，受单个移动距离限制$b$ 和总移动距离预算$B$ 的约束。

• 奖励函数$ℛ$ ：奖励函数$R\left(s,a\right)$ 产生在状态$s$ 采取动作$a$ 后的即时奖励。在我们的设置中，奖励定义为状态从$s$ 转移到$s^{\prime }$ 后，被覆盖目标总权重的增量收益：$R\left(s,a\right)={\displaystyle {\sum }_{k\in c\left(s^{\prime }\right)}{w}_k}-{\displaystyle {\sum }_{k\in c\left(s\right)}{w}_k}$ ，其中$c\left(s\right)$ 表示状态$s$ 下被覆盖目标的集合。

• $\mathcal{Q}$ 值：$\mathcal{Q}$ 值$\mathcal{Q}\left(s,a\right)$ 表示在状态$s$ 采取动作$a$ 并此后遵循策略$\pi$ 的预期累积折扣奖励：

$\mathcal{Q}\left(s,a\right)=E_{\pi }\left[{\displaystyle \sum }_{l=0}^{\infty }{\gamma }^k{R}_{t+k+1}|S_t=s,A_t=a\right]$

其中$R_i$ 是在时间步$i$ 收到的奖励，$\gamma \in \left[0,1\right)$ 是平衡即时和未来奖励重要性的折扣因子。

• 策略$\pi$ ：策略$\pi \left(a|s\right)$ 定义了在状态$s$ 采取动作$a$ 的概率。在这项工作中，我们采用源自$\mathcal{Q}$ -learning算法的$\epsilon$ -贪婪策略进行动作选择。

2.4.2. 算法步骤

$\mathcal{Q}$ -Learning算法在马尔可夫决策过程框架内运行。其核心机制涉及智能体迭代更新$\mathcal{Q}$ 值以逼近最优状态–动作价值函数，进而指导最优策略的推导。更新公式如下：

$\mathcal{Q}\left(s,a\right)\leftarrow \left(1-\alpha \right)\cdot \mathcal{Q}\left(s,a\right)+\alpha \left[r+\gamma \cdot \underset{a^{\prime }}{\max }\mathcal{Q}\left(s^{\prime },a^{\prime }\right)\right]$

其中$\alpha$ 是学习率$\left(0<\alpha \le 1\right)$ ，控制新信息覆盖旧$\mathcal{Q}$ 值的程度。较大的$\alpha$ 赋予最近的经验更多权重，而较小的$\alpha$ 则保留过去的估计。

在我们的实验设置中，状态空间$\mathcal{S}$ 和动作空间$\mathcal{A}$ 如第2.4.1节所定义实例化，结合了距离约束$b$ 和$B$ 。

在初始化期间，建立一个$\mathcal{Q}$ 表，行表示$S$ 中的状态，列表示$A$ 中的动作。所有$\mathcal{Q}$ 值初始化为0，反映了智能体对环境奖励的初始估计，这将通过学习得到细化。学习率$\alpha$ 和折扣因子$\gamma$ 也在 此阶段设置。

在每一回合中，智能体从初始状态$s_0$ 开始，并根据$\epsilon$ -贪婪策略选择动作$a$ 。以概率$\epsilon$ ，它选择随机动作进行探索；否则，它选择具有最高$\mathcal{Q}$ -值的动作，$a=\arg {\max }_a\mathcal{Q}\left(s,a\right)$ ，以利用当前知识。智能体在环境中执行动作$a$ ，这会返回即时奖励$r$ 和新状态$s^{\prime }$ 。与我们的奖励函数定义一致，奖励$r$ 等于由状态转换导致的被覆盖目标总权重的变化。然后使用方程$\mathcal{Q}\left(s,a\right)$ 更新状态-动作对$\left(s,a\right)$ 的$\mathcal{Q}$ 值。最后，当前状态设置为$s^{\prime }$ 以进行下一个决策步骤。

经过充分的探索和经验，$\mathcal{Q}$ 值保证收敛到其最优值。最优$\mathcal{Q}$ 函数${\mathcal{Q}}^{*}$ 满足贝尔曼最优方程：

${\mathcal{Q}}^{*}\left(s,a\right)=E_{\pi }\left[R\left(s,a\right)+\gamma \cdot \underset{a^{\prime }}{\max }\mathcal{Q}\left(s^{\prime },a^{\prime }\right)\right]$

3. 实验与结果分析

3.1. 实验数据与设定

在本研究中，为了评估算法性能，在二维平面$\left[0,1000\right]\times \left[0,1000\right]$ 上随机生成$m$ 个传感器和$n$ 个目标。传感器和目标均服从均匀分布，目标的权重系数在区间$\left[1,10\right]$ 内均匀分布。传感器覆盖半径设置为$r_s=50$ ，每个传感器的最大移动距离约束为$b=250$ ，所有传感器的总移动距离约束为$B=2000$ 。

本文建立了多个实验数据集，以评估每种算法模型在不同场景下的性能，从而对其鲁棒性进行比较分析。对于传感器和目标的数量关系，分别按照$m:n=1:5$ 和$m:n=1:10$ 的比例配置了六组实验数据：

• 比例$m:n=10:50,20:100$ ，和30:150下的三组数据集；

• 比例$m:n=10:100,20:200$ ，和30:300下的三组数据集。

对此，我们可以明确得到各个传感器的坐标，根据传感器的最大移动距离约束为$b=250$ ，可以得到各个传感器$s_i\left(i=1,2,\cdots ,m\right)$ 都有一个相应的可移动区域 $E_i\left(i=1,2,\cdots ,m\right)$ ，从而可以得到一个传感器移动的“候选位置”集合，即解空间，为$E_1\cup E_2\cup \cdots \cup E_m$ 的一个有限离散的子集合。

本文的实验模型算法主要包括六种类型：Gurobi求解器、$\mathcal{Q}$ -Learning算法、贪婪算法(Greedy)、遗传算法(GA)、模拟退火算法(SA)和粒子群优化算法(PSO)。

Obj.表示优化问题中最优解的目标函数值。对于MaxWTCDL问题，它是被覆盖目标的权重之和。Gap.定义为使用特定方法获得的目标函数值与最优目标函数值之间的差值。在本研究中，特定方法获得的差距定义为：

$Gap=\frac{Ob{j}_{\text{gurobi}}-Obj}{Ob{j}_{\text{gurobi}}}$

其中$Ob{j}_{\text{gurobi}}$ 表示Gurobi求解器获得的最优解的目标函数值，Obj表示使用特定算法获得的最优解的目标函数值。

3.2. 实验结果

(a) 初始随机分布 (b) Q-learning后的覆盖结果

Figure 3. $\mathcal{Q}$ -Learning algorithm in sensor deployment optimization ($m=10,n=50$ )

图3. 传感器部署优化中的$\mathcal{Q}$ -Learning算法($m=10,n=50$ )

(a) 初始随机分布 (b) Q-learning后的覆盖结果

Figure 4. $\mathcal{Q}$ -Learning algorithm in sensor deployment optimization ($m=20,n=100$ )

图4. 传感器部署优化中的$\mathcal{Q}$ -Learning算法($m=20,n=100$ )

(a) 初始随机分布 (b) Q-learning后的覆盖结果

Figure 5. $\mathcal{Q}$ -Learning algorithm in sensor deployment optimization ($m=30,n=150$ )

图5. 传感器部署优化中的$\mathcal{Q}$ -Learning算法($m=30,n=150$ )

Table 1. Performance comparison of optimization algorithms for sensor deployment ($m:n=1:5$ )

表1. 传感器部署优化算法的性能比较($m:n=1:5$ )

算法	$m=10,n=50$			$m=20,n=100$			$m=30,n=150$
	Obj.	Gap (%)	Time (h)	Obj.	Gap (%)	Time (h)	Obj.	Gap (%)	Time (h)
Gurobi	104	0.00	0.11	326	0.00	2.31	566	0.00	5.21
Q-learning	104	0.00	0.40	324	0.61	1.12	551	2.65	2.88
Greedy	104	0.00	0.30	296	9.26	0.66	486	14.13	1.23
GA	104	0.00	0.49	296	9.26	2.55	532	6.01	8.91
SA	104	0.00	0.48	300	7.22	2.87	518	8.48	12.80
PSO	89	14.42	0.41	283	15.19	1.84	515	9.01	10.15

图3、图4和图5展示了三种不同规模下优化前后传感器网络的比较。可以直观地观察到，经Q-learning算法优化后，传感器网络的分布得到了显著改善，从而获得了更好的覆盖性能。

根据上述的表1，可以得到不同的算法模型在传感器与目标的数量关系比例为1:5的三种场景下的实验结果。在求解最优目标覆盖结果上，Q-learning算法很接近Gurobi求解器，并且优于四种元启发式算法。相较于元启发式算法，Q-learning算法也有明显优势。

Table 2. Performance comparison of optimization algorithms for sensor deployment ($m:n=1:10$ )

表2. 传感器部署优化算法的性能比较($m:n=1:10$ )

算法	$m=10,n=100$			$m=20,n=200$			$m=30,n=300$
	Obj.	Gap (%)	Time (h)	Obj.	Gap (%)	Time (h)	Obj.	Gap (%)	Time (h)
Gurobi	195	0.00	0.11	479	0.00	3.98	826	0.00	8.31
Q-learning	192	1.54	0.67	469	2.09	2.14	815	1.33	3.27
Greedy	186	4.62	0.33	431	10.02	0.80	690	16.46	1.22
GA	186	4.62	0.59	456	4.80	5.15	760	7.99	15.13
SA	188	3.59	0.66	458	4.38	6.46	768	7.02	17.78
PSO	188	3.59	0.57	454	5.22	5.57	748	9.44	14.12

(a) 初始随机分布 (b) Q-learning后的覆盖结果

Figure 6. $\mathcal{Q}$ -Learning algorithm in sensor deployment optimization ($m=10,n=100$ )

图6. 传感器部署优化中的$\mathcal{Q}$ -Learning算法($m=10,n=100$ )

(a) 初始随机分布 (b) Q-learning后的覆盖结果

Figure 7. $\mathcal{Q}$ -Learning algorithm in sensor deployment optimization ($m=20,n=200$ )

图7. 传感器部署优化中的$\mathcal{Q}$ -Learning算法($m=20,n=200$ )

(a) 初始随机分布 (b) Q-learning后的覆盖结果

Figure 8. $\mathcal{Q}$ -Learning algorithm in sensor deployment optimization ($m=30,n=300$ )

图8. 传感器部署优化中的$\mathcal{Q}$ -Learning算法($m=30,n=300$ )

图6、图7和图8展示了三种不同规模$\left(m,n=10,100;20,200;30,300\right)$ 下优化前后传感器网络的比较。显然，Q-learning算法显著提高了传感器网络的覆盖性能。

根据上述的表2，可以得到不同的算法模型在传感器与目标的数量关系比例为1:10的三种场景下的实验结果。在求解最优目标覆盖结果上，Q-learning算法很接近Gurobi求解器，并且优于四种元启发式算法。相较于元启发式算法，Q-learning算法也有明显优势。

4. 结论

基于强化学习算法框架，我们创新性地使用Q-Learning算法来解决MaxWTCDL问题。通过实验证明，该算法能够自适应地调整传感器移动策略，以在满足单个和总移动距离约束的同时，最大化目标覆盖的权重之和。与传统算法相比，本文提出的Q-Learning强化学习算法在解决本文研究问题方面具有更好的性能。

NOTES

^*通讯作者。