点覆盖问题是指在无向图G=(V,E)中顶点集V中存在一个子集K,在G中任给一条边都至少有一个端点存在K中。最小点覆盖问题是在图中用尽可能少的点覆盖所有边,该问题是一个经典的组合优化领域中的NP完全问题。对最小点覆盖问题的求解可以应用到生活中许多方面,例如:网络节点选择问题、垃圾场和停车场的选址问题、共享单车投放问题等。因其应用广泛所以备受关注。关于该问题求解方法的主要研究方向为直接算法、参数化算法以及智能化算法等三方面。最早使用蚁群算法进行求解的就是组合优化类问题,并且在组合优化领域中关于该算法的研究最多、应用最广。论文从蚁群算法出发研究点覆盖问题,主要工作如下:(1)将TSP问题与最小点覆盖问题进行对比发现两个不同之处:TSP问题中顶点的选择与其排列顺序有关,而最小点覆盖问题中排列顺序不影响最后结果;TSP问题中的启发式函数为静态的而最小点覆盖问题中是动态更新的。根据这两个不同点将蚁群算法解决TSP问题进行改进从而得到蚁群算法解决最小点覆盖问题。(2)虽然蚁群算法具有系统性、分布式计算、鲁棒性强、正反馈性等优势,但是当处理数据量巨大时会出现求解时间长或者得不到最优解的情况,而且蚂蚁在循环中可能会因早期停滞问题的出现从而导致算法陷入局部最优。为了防止这种情况的出现使用最大最小蚁群算法进行求解。该算法通过对信息素浓度进行限定使其不会在好的顶点上变得更强,也不会使过弱的点被忽略,避免了算法出现局部最优的现象。通过计算表明该算法的精确度较高。(3)为了避免算法中存在的局部最优解停滞问题提出一种杂交蚁群算法来解决该问题。该算法的主要目的是对最优解进行校正。这种杂交概念是直接怀疑最优解中的某些元素不好,在搜索过程中直接指向可疑的搜索区域,通过减少可疑点的信息素更新值来指导搜索。设置怀疑准则对点进行筛选,然后使用校正规则对顶点进行校正。通过算例表明引入怀疑准则对最优解进行了优化。