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

点覆盖问题为组合优化中一个经典的NP完全问题。目前，该问题在有效的多项式时间内无法找到最优解。文章针对蚁群算法可能出现的早期停滞问题进行改进，通过对信息素浓度进行限定，信息素浓度不会在 *通讯作者。

点覆盖是指给定一个无向图(), GV E=，其中V 为顶点集，若存在( )V G 的一个子集S，使得G 中任意一条边的两个端点至少有一个在S 中， 则S 为G 的点覆盖集。

若图G 中不存在点覆盖S′ ， 使SS′ <， 则称S 为G 的一个最小点覆盖集，其中S 和S′ 即集合S 和S′ 的顶点个数[1]。

在运筹学和管理科学领域，点覆盖问题也是NP-hard 最常用的问题之一[2]。在现实生活中有许多的问题都可以利用最小点覆盖问题原理进行解决。对该问题研究虽然已经有很长时间，但是人们至今没有找到一个多项式算法可以求得其精确解[3]。Niedermeier 等[4]提出当每个点的权值最小为1，n 个点总权值最多为k 时，可以找到时间复杂度为()1.3788kOkn+的解决方案。Chvatal 等[5]运用贪婪启发式算法， 选取顶点权值与度之比最小的点解决集合覆盖问题。1993 年参数化算法第一次用来解决该问题[6]。寇磊等[7]运用改进的Dijkstra 算法解决该问题，并且得出该近似算法的时间复杂度为()3O n。王丽丽等通过线性规划松弛来实现对每个实例中参数k 范围的预测，介绍了一种求解该问题实例计算成本的方法[8]。

骆伟忠等将启发式操作和核心化操作相融合，给出了基于核心化技术的点覆盖问题的改进算法[9]。郝斌斌等人研究了一种基于该问题的共享单车投放点选取问题[10]。

目前对于蚁群算法的研究已经不再仅仅局限于单一的范围中，近年来往往利用遗传算法结合贪婪启发式算法和基于重力的转启发式算法研究最小点覆盖问题并得到近似解。

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

目前蚁群算法研究点覆盖问题还不完善，蚁群算法虽然具有系统性、分布式计算、自组织、正反馈等优势，但是当处理数据量巨大时其会出现求解时间长或者得不到最优解，而且蚂蚁在循环中可能会出现早期停滞问题导致算法陷入局部最优。

因此为了避免上述问题的出现， 引入信息素浓度限定这一概念， 对信息素浓度进行限定，提出了一种改进的蚁群算法。当每个点的权值最小为1 时，得到时间复杂性为()201nn⋅−的解决方案，其中n 为图G 的顶点数。

2. 基本原理 蚁群算法的灵感来源于现实生活中真正蚂蚁的自然优化机制，它是一种启发式算法。蚂蚁依靠相互协作可以在洞穴和食物源之间找到一条最短路径[15]。

探究发现这是由于蚂蚁在通过一条路时会留下一种