基于蚁群算法的赋权图点覆盖问题

Vertex Covering Problem of Weighted Graphs Based on Ant Colony Algorithm

摘要: 点覆盖问题是一个在实际生活中具有重要意义的NP完全问题。蚁群算法为近年来新出现的一种仿生类随机寻优算法。文章运用蚁群算法研究了赋权图的最小点覆盖问题。给出了一个基于蚁群算法的近似算法，得出最小点覆盖问题的近似解。通过修改蚂蚁的状态转移概率公式，简化状态转移规则，建立了相应的数学模型，从而得出求解点覆盖的近似算法，最后进行了实例解析。实验结果表明该算法是行之有效的。

Abstract: Point covering problem is a NP complete problem in real life. Ant colony algorithm is a new bionic stochastic optimization algorithm emerging in recent years. In this paper, the minimum coverage problem of weighting graphs is studied by using the ant colony algorithm. An approximate algo-rithm based on ant colony algorithm is proposed to solve the minimum point covering problem. By modifying the state transition probability formula of ants and simplifying the state transition rules, the corresponding mathematical model is established, and then the approximate algorithm for solving the point coverage is obtained. Finally, an example is analyzed. The experimental results show that the algorithm is effective.

1. 引言

对于无向图 $G=\left(V,E\right)$ 的顶点覆盖是指它的顶点集 $V$ 中存在一个子集 $K$ ，在 $G$ 中任给一条边都至少有一个端点存在 $K$ 中。点覆盖 $K$ 称为 $G$ 的最小点覆盖当且仅当 $G$ 中没有覆盖 $K^{\prime }$ 使得 $\left|K^{\prime }\right|<\left|K\right|$ 。求图 $G$ 的最小点覆盖即为图论中的典型问题——最小点覆盖问题(MVCP) [1] 。最小点覆盖问题是组合优化中一个经典的NP完全问题 [2] 。大量的现实生活中的问题都可以转化为最小点覆盖的问题来求其解决方法。例如：垃圾处理厂的最佳位置，通过监控尽可能少的点来监控一个大型网络，无线传感器网络节点设置问题等。最小点覆盖问题的研究虽然已有很长时间，但是至今人们还没有找到一个多项式算法，所以依然是国内外学者研究的热点问题之一。早期有边删除(Edge Deletion)算法 [3] ，深度优先搜索(Depth First Search)算法 [4] 等。Pitt给出了一个近似比为2的随机算法 [5] 。

Avis等设计了几个算法，其整数规划的近似比为2，匹配算法的近似比为2，贪心算法的近似比为 $\sqrt{\Delta }/2+3/2$ ，其中 $\Delta$ 为图的最大度 [6] 。Delbot等改进了文献 [7] 中的算法，并证明所得算法的近似比都不大于文献 [7] 的结果 [7] 。最小点覆盖问题的参数化算法在1993年被Buss等第一次提出，其时间复杂性为 $O\left(kn+2^k{k}^{2k+2}\right)$ [8] 。点覆盖问题的智能化算法是Khuri等在1994年提出的，其将最小加权点覆盖问题看成一个有约束的组合优化问题并且引入了遗传算法进行求解 [9] 。Stefan等采用禁忌搜索和模拟退火相结合的混合算法来研究最小权点覆盖问题，其结果优于很多启发式逼近算法 [10] 。周康等在闭环DNA算法中通过删除实验得到了最小点覆盖的补集，通过求其补集从而得到其最小点覆盖 [11] 。吕健康等根据顶

点度特点以及贪婪算法的思想设计了混合贪婪算法，并证明了在最坏条件下的时间复杂度为 $O\left({\left|V\right|}^2\right)$ [12] 。郑光勇等针对最小点覆盖的特点设计了化学反应优化算法中的四个重要算子，将化学反应优化算法与求解最小点覆盖问题进行结合设计了一个新的近似算法 [13] 。

蚁群优化算法(Ant Colony Optimization, ACO)是由Dorigo等人在1991年提出的一种源于大自然中生物世界的新的仿生类算法 [14] 。作为一种通用性随机优化方法，它借鉴了昆虫王国中蚂蚁的觅食行为特性，通过蚂蚁的内部搜索机制，在一系列求解困难的组合优化问题中取得了显著成效，其具有鲁棒性、并行分布式计算、易与其他算法结合等特点。蚁群优化算法虽为近年来新兴的一种算法，但在多个领域中有着广泛应用，如通讯网络路由的自主选择、自动控制、路径选择、系统工程、图着色等领域 [15] [16] [17] 。

本文通过修改蚁群算法的启发式函数和状态转移概率公式，得出了基于蚁群算法解决了点赋权图的最小点覆盖问题的一种近似算法。并对算法的有效性进行检验。

2. 蚁群算法解决最小点覆盖问题的基本原理

蚁群优化算法与求解其他的组合优化问题进行比较，其在求解最小点覆盖问题中有着明显的差异，其差异可通过与旅行商问题(Travelling Salesman Problem, TSP)的算法比较看出 [18] 。TSP问题中所要解决的问题是城市之间的一种点排列顺序，但是在MWVC案例中其顶点顺序并不是最重要的。在TSP问题中蚁群算法的启发式函数是静态的，它代表的是城市之间的距离，而城市之间的距离不发生改变故路径的计算方法不会改变。与此相反，在用蚁群算法解决最小权点覆盖问题时，启发式函数为权值和顶点临时度(已经在解决方案中包括但没有被其他点覆盖的边数)的比值。这个比值为动态变化的，因为当有更多的点被覆盖时，该点的临时度产生了变化。这两个差异导致的结果有两方面：一方面蚂蚁的信息素留在了顶点上；另一方面启发式函数是动态更新的。蚁群算法可用于解决启发式函数为动态的和解集是由其子集构成的这类问题。例如，集合划分、最大独立集和最小团、最大边填装等问题。

首先，用动态启发式函数来表示最小点覆盖问题，对问题进行简化。因为蚂蚁在搜索过程中可以从一个顶点移动到任何顶点，因此需作图 $G$ 的完全连通图 $G_c=\left(V,E_c\right)$ ，若该边在图 $G$ 中则其边权值为1，反之为0。

定义 $G_{ck}=\left(V,E_{ck}\right)$ ，这表示 $k$ 个顶点加入到解集后的图，并定义相应的函数： $\psi \left(i,j\right)=Value\left(E_{ck}\left(i,j\right)\right)$

定义动态启发式函数：

${\eta }_{jk}=\frac{{\displaystyle \underset{\left(r,j\right)\in E_c}{\sum }{\psi }_k\left(r,j\right)}}{\omega \left(j\right)}$ (1)

在方程(1)中， $\omega \left(j\right)$ 指点 $j$ 的权值，用方程(1)中启发函数 ${\eta }_{jk}$ 定义状态转移规则方程：

$p_j^k=\{\begin{array}{l}1,q>q_0,j={\max }_{i\in A_k}\left\{{\tau }_i{\eta }_{ik}^{\beta }\right\}\\ 0,q>q_0,j\ne {\max }_{i\in A_k}\left\{{\tau }_i{\eta }_{ik}^{\beta }\right\}\\ \frac{{\tau }_j{\eta }_{jk}^{\beta }}{{\displaystyle \underset{r\in A_K}{\sum }{\tau }_j{\eta }_{jk}^{\beta }}},q\le q_0\end{array}$ (2)

在方程(2)中， $q_0$ 为指定搜索率的标准参数， $q$ 为随机变量，它决定每一步的选择类型。 $A_k$ 是可用顶点列表。不同于 $TSP$ 的状态转移规则，它与最后被选择的点无关，可用 ${\tau }_i$ 代替 ${\tau }_{ij}$ 。

信息素修正规则的目的是在更短路径上分配更多的信息素。信息素修正规则与真实蚂蚁一致，不仅存储信息素还需要适当挥发他们。

在该系统中信息素更新规则如下。首先，在每个周期完成后，在当前最优解的顶点上留下的信息素强度得到加强。让顶点子集 ${V^{\prime }}_c$ 成为当前最好的解决方案，在顶点 $i$ 上留下的信息素将按照全局更新规则进行更新，如下所示：

${\tau }_i=\{\begin{array}{l}\left(1-\rho \right){\tau }_i+\rho \Delta {\tau }_i,i\in v^{\prime }\\ \left(1-\rho \right){\tau }_i,\text{otherwise}\end{array}$ (3)

$\Delta {\tau }_i=\{\begin{array}{l}0,i\notin V^{\prime }\\ \frac{1}{{\displaystyle \underset{j\in V^{\prime }}{\sum }\omega \left(j\right)}},i\in V^{\prime }\end{array}$ (4)

$\rho \in \left(0,1\right)$ 为一个模拟信息素强度蒸发率的参数。

局部信息素更新规则目的是避免解集陷入局部最优的状态，同时为短路径增加信息素。局部信息素的更新在每个步骤结束时进行。更新规则如下：

${\tau }_i=\left(1-\phi \right){\tau }_i+\phi {\tau }_0$ (5)

${\tau }_0$ 为信息素放在每个顶点的初始值。参数 $\phi$ 是规定的特殊局部更新规则的值。

3. 算法设计

对赋权图 $G=\left(V,E\right)$ ，做出图 $G$ 的完全图 $G_c=\left(V,E_c\right)$ ，使得图 $G$ 的任意两点之间均有边相连。

Step1：定义连接函数 ${\psi }_k$ ：

${\psi }_k\left(i,j\right)=\{\begin{array}{l}1,\left(i,j\right)\in E\\ 0,\left(i,j\right)\in E_c-E\end{array}$

由此函数确定各边的连接值。

Step2：若蚂蚁 $k$ 访问了 $E_c$ 中的某个点，则与该点相连的边连接值修改为0。即： ${\psi }_k\left(i,j\right)=0$ 。

Step3：计算每一点的动态启发因子 ${\eta }_{jk}$ ：

${\eta }_{jk}=\frac{{\displaystyle \underset{\left(r,j\right)\in E_c}{\sum }{\psi }_k\left(r,j\right)}}{\omega (j)}$

其中 $\omega \left(j\right)$ 是 $v_j$ 的权值， ${\displaystyle {\sum }_{\left(r,j\right)\in E_c}{\psi }_k\left(r,j\right)}$ 表示 $E$ 中与 $v_j$ 相连而没有被覆盖的顶点连接值之和。

Step4：对局部信息素进行更新：

${\tau }_i=\left(1-\phi \right){\tau }_i+\phi {\tau }_0$

由此可求出 $\max \{{\tau }_i{\eta }_{jk}^{\beta }\}$ 。

Step5：由状态转移公式计算出蚂蚁 $k$ 选择下一顶点的概率：

$p_j^k=\{\begin{array}{l}1,j={\max }_{i\in A_K}\{{\tau }_i{\eta }_{jk}^{\beta }\}\\ 0,j\ne {\max }_{i\in A_K}\{{\tau }_i{\eta }_{jk}^{\beta }\}\end{array}$

Step6：当完成一次环游时对全局信息素进行更新，更新函数：

${\tau }_i=\{\begin{array}{l}\left(1-\rho \right){\tau }_i+\rho \Delta {\tau }_i,i\in v^{\prime }\\ \left(1-\rho \right){\tau }_i,\text{otherwise}\end{array}$

对于图 $G$ 来说，当所有点的边连接值为0时，算法结束。即当蚂蚁完成所有搜索时，对于全部的点 $i$ ，有 ${\displaystyle {\sum }_{\left(r,j\right)\in E_c}{\psi }_k\left(r,j\right)}=0$ ，此时可得到一个点覆盖集 $S_k$ 。选择不同的初始点，得到不同的解集集。后选择总权值最小的点覆盖集即为图的最小点覆盖集。

4. 算法实例

首先，做出原图的完全图。原图如图1所示，其完全图如图2所示。

其次，对算法中的参数进行赋值。探索率 $q_0=0.1$ ，蒸发率 $\phi =0.1,\rho =0.1$ ，对启发式的影响因素 $\beta =5$ ，信息素的初始值 ${\tau }_0=1/\left(n{\displaystyle {\sum }_{j\in v^{\prime }}\omega \left(j\right)}\right)$ 。

Step1：由连接函数 ${\psi }_k\left(i,j\right)=\{\begin{array}{l}1,\left(i,j\right)\in E\\ 0,\left(i,j\right)\in E_c-E\end{array}$ 给定各边的连接，蚂蚁1以 $v_1$ 为出发点，有 $S_1=\left\{v_1\right\}$ ；

Step2：用连接函数 ${\psi }_k\left(i,j\right)=0$ 更新与点 $v_1$ 关联边的连接值；

Step3：计算 ${\tau }_i{\eta }_{jk}^{\beta }$ ，有 ${\tau }_i{\eta }_{jk}^{\beta }\ne 0$ 转Step4；

Step4：计算 $\max \left\{{\tau }_i{\eta }_{jk}^{\beta }\right\}=0.001$ ， $j=3$ ，将其并入集合 $S_1$ ， $S_1=\left\{v_1,v_3\right\}$ ，转Step2；

Step2：用连接函数 ${\psi }_k\left(i,j\right)=0$ 更新与点 $v_3$ 关联边的连接值；

Step3：进行局部信息素更新，计算 ${\tau }_i{\eta }_{jk}^{\beta }$ ，有 ${\tau }_i{\eta }_{jk}^{\beta }\ne 0$ 转Step4；

Step4：计算 $\max \left\{{\tau }_i{\eta }_{jk}^{\beta }\right\}=0.002$ ， $j=6$ ，将其并入集合 $S_1$ ， $S_1=\left\{v_1,v_2,v_6\right\}$ ，转Step2；

Step2：用连接函数 ${\psi }_k\left(i,j\right)=0$ 更新与点 $v_6$ 关联边的连接值；

Step3：进行局部信息素更新，计算 ${\tau }_i{\eta }_{jk}^{\beta }$ ，有 ${\tau }_i{\eta }_{jk}^{\beta }\ne 0$ 转Step4；

Step4：计算 $\max \left\{{\tau }_i{\eta }_{jk}^{\beta }\right\}=0.004$ ， $j=5$ ，将其并入集合 $S_1$ ， $S_1=\left\{v_1,v_3,v_6,v_5\right\}$ ，转Step2；

Step2：用连接函数 ${\psi }_k\left(i,j\right)=0$ 更新与点 $v_5$ 关联边的连接值；

Step3：进行局部信息素更新，计算 ${\tau }_i{\eta }_{jk}^{\beta }$ ，有 ${\tau }_i{\eta }_{jk}^{\beta }=0$ ，输出 $S_1=\left\{v_1,v_3,v_5,v_6\right\}$ ；

Step5：计算 $|S_1|=\underset{j\in S_1}{\min }\omega \left(j\right)=13$ ，算法停止。

Step6：一次环游完成，对全局信息素进行更新；

Step7：计算 $S=\min \left\{S_1,S_2,\cdots ,S_k,\cdots ,S_n\right\}$ ，输出最小点覆盖集 $S_2=\left\{v_1,v_2,v_5,v_3\right\}$ 。

计算结果如表1所示。

5. 结束语

本文研究了蚁群算法在求解最小点覆盖中的应用。对蚁群算法的模型进行了改进，避免了局部收敛的问题，得到一个点覆盖问题的最优解，使算法简单、可行。

在现实生活中最小点覆盖问题是一个十分重要的并且具有现实意义的难题。蚁群算法是一种近年来新兴的仿生类算法。蚁群算法求解点覆盖问题与其他算法相比具有较好的性能。对于点数较多和较复杂

Figure 1. Original diagram

图1. 原图

Figure 2. Complete diagram

图2. 完全图

Table 1. Calculated results

表1. 计算结果

的图，一般算法的时间复杂性较高，计算复杂。利用蚁群算法求解可通过增加蚂蚁数量来提高精度。从当前来看蚁群算法是求解图最小点覆盖的问题的一个较好算法。

基金项目

国家自然科学基金项目：随机环境下公交优先控制理论与方法研究(61463026)；基于演化博弈理论的城市交通网络路径选择模型与算法研究(61463027)；甘肃省自然科学基金(216177)。