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

Ant Colony Algorithm for Vertex Covering Problem of Weighted Graphs

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

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)2-n].