赋权图点覆盖问题的蚁群算法求解

Ant Colony Algorithm for Vertex Covering Problem of Weighted Graphs

摘要: 点覆盖问题为组合优化中一个经典的NP完全问题。目前，该问题在有效的多项式时间内无法找到最优解。文章针对蚁群算法可能出现的早期停滞问题进行改进，通过对信息素浓度进行限定，信息素浓度不会在好的顶点继续加强，也不会忽略掉潜在的一些搜索区域。该算法有效地避免了局部最优，提高了算法的准确度，得到时间复杂性为0[(n-1)²-n]的解决方案。

Abstract: Vertex covering problem is a classical NP complete problem in combinatorial optimization. At present, the problem cannot find the optimal solution in the effective polynomial time. This paper improves the early stagnation problem of ant colony algorithm. By limiting the pheromone concentration, the pheromone concentration will not continue to strengthen at the good vertex, nor will it ignore some potential search areas. This algorithm effectively avoids local optimization, improves the accuracy of the algorithm, and obtains a solution with time complexity of 0[(n-1)²-n].

1. 引言

点覆盖是指给定一个无向图，其中V为顶点集，若存在 $V\left(G\right)$ 的一个子集S，使得G中任意一条边的两个端点至少有一个在S中，则S为G的点覆盖集。若图G中不存在点覆盖 $S^{\prime }$，使 $\left|S^{\prime }\right|<\left|S\right|$，则称S为G的一个最小点覆盖集，其中 $\left|S\right|$ 和 $\left|S^{\prime }\right|$ 即集合S和 $S^{\prime }$ 的顶点个数 [1] 。

在运筹学和管理科学领域，点覆盖问题也是NP-hard最常用的问题之一 [2] 。在现实生活中有许多的问题都可以利用最小点覆盖问题原理进行解决。对该问题研究虽然已经有很长时间，但是人们至今没有找到一个多项式算法可以求得其精确解 [3] 。Niedermeier等 [4] 提出当每个点的权值最小为1，n个点总权值最多为k时，可以找到时间复杂度为 $O\left({1.3788}^k+kn\right)$ 的解决方案。Chvatal等 [5] 运用贪婪启发式算法，选取顶点权值与度之比最小的点解决集合覆盖问题。1993年参数化算法第一次用来解决该问题 [6] 。寇磊等 [7] 运用改进的Dijkstra算法解决该问题，并且得出该近似算法的时间复杂度为 $O\left(n^3\right)$。王丽丽等通过线性规划松弛来实现对每个实例中参数k范围的预测，介绍了一种求解该问题实例计算成本的方法 [8] 。骆伟忠等将启发式操作和核心化操作相融合，给出了基于核心化技术的点覆盖问题的改进算法 [9] 。郝斌斌等人研究了一种基于该问题的共享单车投放点选取问题 [10] 。目前对于蚁群算法的研究已经不再仅仅局限于单一的范围中，近年来往往利用遗传算法结合贪婪启发式算法和基于重力的转启发式算法研究最小点覆盖问题并得到近似解。

1992年意大利学者Dorigo等人提出了蚁群算法 [11] 。2000年在国际顶级期刊《Nature》上发表了关于蚁群算法系统的研究综述，首次将蚁群算法推向国际领域，人们开始对蚁群算法进行广泛地研究和应用 [12] 。吴佩雯等人对蚁群算法解决点覆盖问题给出了简单的近似算法 [13] 。葛洪伟等人将SCHF启发函数与蚁群算法相结合得到了一个新的算法对集合问题进行求解 [14] 。

目前蚁群算法研究点覆盖问题还不完善，蚁群算法虽然具有系统性、分布式计算、自组织、正反馈等优势，但是当处理数据量巨大时其会出现求解时间长或者得不到最优解，而且蚂蚁在循环中可能会出现早期停滞问题导致算法陷入局部最优。因此为了避免上述问题的出现，引入信息素浓度限定这一概念，对信息素浓度进行限定，提出了一种改进的蚁群算法。当每个点的权值最小为1时，得到时间复杂性为 $0\left[{\left(n-1\right)}^2\cdot n\right]$ 的解决方案，其中n为图G的顶点数。

2. 基本原理

蚁群算法的灵感来源于现实生活中真正蚂蚁的自然优化机制，它是一种启发式算法。蚂蚁依靠相互协作可以在洞穴和食物源之间找到一条最短路径 [15] 。探究发现这是由于蚂蚁在通过一条路时会留下一种信息素，当其它蚂蚁选择路径时，会依靠信息素浓度判断并找出一条最短路径 [16] 。

设m为蚂蚁的数目， $b_i\left(t\right)$ 表示t时刻在节点i的蚂蚁数目， $m={\displaystyle {\sum }_{i=1}^n{b}_i\left(t\right){\tau }_{ij}\left(t\right)}$ 为某时刻t在路段 $\left(i,j\right)$ 上的信息素，信息素轨迹和参数初始化， ${\tau }_{ij}\left(t_0\right)=C$，(C为常数)，为使算法初期各个蚂蚁更好获得较好的解，将信息素大小设置为 ${\tau }_{\max }$。 ${\eta }_{ij}$ 表示路段 $\left(i,j\right)$ 上的能见度。

计算状态转移规则，将初始节点i置于蚂蚁 $k\left(k=1,2,\cdots ,m\right)$ 的解集 $C_k$ 中，蚂蚁k按状态转移规则选择下一节点j，并将j放入当前解集 $C_k$ 中。

$p_{ij}^k\left(t\right)=\{\begin{array}{l}\frac{{\left[{\tau }_{ij}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{ik}\left(t\right)\right]}^{\beta }}{{{\displaystyle \sum }}_{s\in allowe{d}_k}{\left[{\tau }_{is}\left(t\right)\right]}^{\alpha }{\left[{\eta }_{is}\left(t\right)\right]}^{\beta }},若j\in allowe{d}_k\\ 0,否则\end{array}$ (1)

在公式(1)中 $allowe{d}_k=\left\{0,1,2,\cdots ,n-1\right\}$ 为允许访问下一节点的集合。 $\alpha ,\beta$ 为参数因子，由ant-cycle模型得出的最好的经验结果为 $0\ll \alpha \ll 5$， $0\ll \beta \ll 5$。

在每只蚂蚁走完一步或者完成一次环游，记录最好解，并进行信息素更新。

${\tau }_{ij}\left(t+1\right)=\rho {\tau }_{ij}\left(t\right)+\Delta {\tau }_{ij}^{best}$ (2)

$\Delta {\tau }_{ij}^{best}=\{\begin{array}{l}1/L^{best},若i,j为最优路径\\ 0,否则\end{array}$ (3)

式(3)中 $\rho$ 为信息素的挥发系数，一般 $0<\rho <1$。当达到最大迭代次数或者找寻到最优路径，则算法停止，输出全局最优解。

3. 模型建立

根据最小点覆盖的特点，蚂蚁在搜索过程中是可以从一个点转移到其他任一顶点的，故作图G的完全图 $G_C=\left(V,E_C\right)$，如果一个边是G中的边那么它的权值是1，如果它未出现在原来的图G中，那么它的权值为0。

定义 $G_{ck}=\left(V,E_C\right)$ 为k个顶点加入解集后的图，定义 ${\Psi }_k\left(i,j\right)=Value\left(E_{ck}\left(i,j\right)\right)$。

定义动态启发函数

${\eta }_{jk}=\frac{{{\displaystyle \sum }}_{\left(i,j\right)\in E_c}{\Psi }_k\left(i,j\right)}{\omega \left(j\right)}$ (4)

在式(4)中， $\omega \left(j\right)$ 指顶点j的权值，用启发函数 ${\eta }_{jk}$ 定义状态转移概率方程

$p_j^k=\{\begin{array}{l}1,q<q_0,j={\max }_{i\in A_k}{\tau }_i{\eta }_{ik}^{\beta }\\ 0,q<q_0,j\ne {\max }_{i\in A_k}{\tau }_i{\eta }_{ik}^{\beta }\\ \frac{{\tau }_j{\eta }_{jk}^{\beta }}{{{\displaystyle \sum }}_{\gamma \in A_k}{\tau }_i{\eta }_{ik}^{\beta }},q\ge q_0\end{array}$ (5)

在式(5)中， $q_0$ 是标准参数且q是一个随机变量，它决定每一步选择的类型。 $A_k$ 是可用的顶点的列表。不同于TSP的状态转移规则，它并不取决于最后一个被选择的点，这就是为什么用 ${\tau }_i$ 来代替 ${\tau }_{ij}$。对一个完全指定的蚂蚁群系统全球(当蚂蚁完成它们的所有路径时)，信息素更新为

${\tau }_i\left(t+1\right)=\rho {\tau }_i\left(t\right)+\Delta {\tau }_i^{best}$ (6)

$\Delta {\tau }_{ij}^{best}=1/L^{best}$ (7)

在式(7)中的 $L^{best}$ 为当前迭代最优解。每条路径上的信息素 ${\tau }_i\left(t\right)$ 都限于 $\left[{\tau }_{\min },{\tau }_{\max }\right]$ 范围中。每次迭代之后都应将信息素限定在该范围内。若 ${\tau }_i\left(t\right)\ge {\tau }_{\max }$，则 ${\tau }_i\left(t\right)={\tau }_{\max }$；若 ${\tau }_i\left(t\right)\le {\tau }_{\min }$，则 ${\tau }_i\left(t\right)={\tau }_{\min }$，与此同时要保证 ${\tau }_{\min }>0$。

局部信息素更新的主要目的是为了减少算法陷入局部最优的状态，同时增加短路径上的信息素浓度。在每一步结束时执行局部信息素的更新，更新规则为

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

式(8)中，的值是指被选择的点的度数与权值之间的最佳比。参数 $\phi$ 是被指定的特殊的局部更新规则的值。

4. 算法设计

对点赋权图 $G=\left(V,E\right)$，做出图G的完全图 $G_C=\left(V,E_C\right)$。

首先，定义连接函数

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

由此函数即可确定各边的连接值。对于蚂蚁k，当蚂蚁k访问到i点，则 ${\Psi }_k\left(i,j\right)=0$，其中j表示所有与i相邻的顶点。

然后计算动态启发因子

${\eta }_{jk}=\frac{{{\displaystyle \sum }}_{\left(i,j\right)\in E_c}{\Psi }_k\left(i,j\right)}{\omega \left(j\right)}$ (10)

其中 $\omega \left(j\right)$ 为j点的权值， ${{\displaystyle \sum }}_{\left(i,j\right)\in E_c}{\Psi }_k\left(i,j\right)$ 表示顶点j所关联的所有的边的连接值之和。因此可求出 $\max \left\{{\eta }_{jk}^{\beta }\right\}$。

由此给出蚂蚁k接下来访问新的顶点的状态转移概率

$P_j^k=\{\begin{array}{l}1,j=\max \left\{{\eta }_{jk}^{\beta }\right\}\\ 0,j\ne \max \left\{{\eta }_{jk}^{\beta }\right\}\end{array}$ (11)

对于图G，当所有的连接值均为0时，算法停止。当蚂蚁完成环游，对于所有点i，有 ${{\displaystyle \sum }}_{\left(i,j\right)\in E_c}{\Psi }_k\left(i,j\right)=0$，此时可得到一个点覆盖集 $S_k$。更新初始点，得到n个新的点覆盖集，计算 $\underset{j\in S_k}{\min }\omega \left(j\right)$，则得到图的最小点覆盖集。

算法实现步骤

Step1. 初始化：做出图G的完全图 $G_C=\left(V,E_C\right)$，由连接函数

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

给定的各边连接值，令 $S_k=\left\{v_i\right\}$， $k=\text{1}$；

Step2. 用连接函数 ${\Psi }_k\left(i,j\right)=0$ 更新与i点相关联的所有边的连接值，计算

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

若有 ${\eta }_{jk}=0$ 则输出点覆盖，算法停止。否则，转Step3；

Step3. 计算 $\max \left\{{\eta }_{jk}^{\beta }\right\}$，由

$P_j^k=\{\begin{array}{l}1,j=\max \left\{{\eta }_{jk}^{\beta }\right\}\\ 0,j\ne \max \left\{{\eta }_{jk}^{\beta }\right\}\end{array}$

确定下一个选择的顶点，并将其并入集合 $S_k$，转Step2；

Step4. 计算 $\left|S_k\right|=\underset{j\in S_1}{\min }\omega \left(j\right)$，更新初始点，转Step2；

Step5. 计算 $S=\min \left\{S_1,S_2,\cdots ,S_k,\cdots ,S_n\right\}$，输出最小点覆盖集S，算法停止。由此得出算法的时间复杂度为 $0\left[{\left(n-1\right)}^2\cdot m\right]$，其中n为图G的顶点数，m为蚂蚁数目，若 $m\approx n$，则蚁群算法的时间复杂度为 $0\left[{\left(n-1\right)}^2\cdot n\right]$。

5. 算例分析

求图1的点覆盖来阐释算法的具体执行过程，其中图G是8个顶点，12条边的点赋权图且图2中的图 $G_C$ 是图G的完全图。

Figure 1. Graph G

图1. 图G

Figure 2. Graph G_C

图2. 图G_C

Step1. 由连接函数

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

给定的各边连接值，蚂蚁1以 $v_1$ 为出发点，有 $S_1=\left\{v_1\right\}$，期望启发因子 $\beta$ 赋值为2；

Step2. 用连接函数 ${\Psi }_k\left(i,j\right)=0$ 更新与点 $v_1$ 关联边的连接值，计算 ${\eta }_{jk}^{\beta }$ 有 ${\eta }_{jk}^{\beta }\ne 0$，转Step3；

Step3. 计算 $\max \left\{{\eta }_{jk}^{\beta }\right\}=12.25,j=7$，将其并入集合 $S_1=\left\{v_1,v_7\right\}$，转Step2；

Step2. 用 ${\Psi }_k\left(i,j\right)=0$ 更新 $v_7$ 关联边的连接值，计算 ${\eta }_{jk}^{\beta }$，有 ${\eta }_{jk}^{\beta }\ne 0$，转Step3；

Step3. 计算 $\max \left\{{\eta }_{jk}^{\beta }\right\}=16/9,j=3$，将其并入集合 $S_1=\left\{v_1,v_7,v_3\right\}$，转Step2；

Step2. 用连接函数 ${\Psi }_k\left(i,j\right)=0$ 更新与点 $v_3$ 关联的边的连接值，计算 ${\eta }_{jk}^{\beta }$，有 ${\eta }_{jk}^{\beta }\ne 0$，转Step3；Step3.计算 $\max \left\{{\eta }_{jk}^{\beta }\right\}=4/9,j=5$，将其并入集合 $S_1=\left\{v_1,v_7,v_3,v_5\right\}$，转Step2；

Step2. 用连接函数 ${\Psi }_k\left(i,j\right)=0$ 更新与点 $v_5$ 关联的边的连接值，计算 ${\eta }_{jk}^{\beta }$，有 ${\eta }_{jk}^{\beta }=0$，输出
$S_1=\left\{v_1,v_2,v_3\right\}$；

Step4. 计算 $\left|S_k\right|=\underset{j\in S_1}{\min }\omega \left(j\right)=10$，算法停止；

Step5. 计算 $S=\min \left\{S_1,S_2,\cdots ,S_k,\cdots ,S_n\right\}$ 得 $S=\min \left\{v_1,v_3,v_5,v_7\right\}$，输出最小点覆盖集 $S=\left\{v_1,v_3,v_5,v_7\right\}$，算法停止。

比较表1中点覆盖的点覆盖数和权值，集合 $\left\{v_1,v_3,v_5,v_7\right\}$ 的点覆盖数和权值最小，点覆盖数为4，点覆盖权值为10。该算法点覆盖数和权值没有出现局部最优。

Table 1. Number of point overlays and point overlays of each vertex in figure G

表1. 图G各顶点的点覆盖数及点覆盖值

为使该算例更具代表性，选取 $n=\left|V\right|=3r+4$，图3中最优覆盖有r + 2个点，为 $\left\{B_1,B_2,\cdots ,B_{r+2}\right\}$，用20只蚂蚁对该实例求解，计算结果见表2。

从表2中可知当图规模较小时，蚁群算法的早期停滞问题并没有出现。然而，随着图的复杂程度增加、点数的增多和r的增大，蚁群算法在计算过程中出现了停滞现象，所得结果是存在局部最优现象的。对信息素浓度的限定，有效的避免了该现象的出现，所得结果更加接近最优结果，计算精度方面得到了一定的提升。

Figure 3. Numerical example

图3. 算例

Table 2. The calculation results

表2. 计算结果

6. 结论

蚁群算法相较各种成熟的智能计算方法，仍在实验探索阶段，但从当前的应用效果来看这种新型系统寻优思想对解决一些实际问题表现突出，解决赋权图点覆盖问题是可行的。

本文主要对蚂蚁选择下一顶点的状态转移概率进行改进，同时对信息素浓度进行限定，设置了最大值与最小值，这样可以使信息素浓度不会在好的顶点上继续加强也不会忽略掉一些潜在的搜索区域，使得解决点覆盖问题的精确度更高，运行效率更快。通过实例计算表明该近似算法提高了准确性，所得解更加趋近于最优解。

基金项目

国家自然科学基金(61463027，61463026)，甘肃省自然科学基金(1610RJZA038)。

NOTES

^*通讯作者。