摘要
点覆盖问题为组合优化中一个经典的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].
出处
《计算机科学与应用》
2019年第10期1823-1830,共8页
Computer Science and Application
基金
国家自然科学基金(61463027,61463026),甘肃省自然科学基金(1610RJZA038).
