赋权图点覆盖问题的蚁群算法求解
Ant Colony Algorithm for Vertex Covering Problem of Weighted Graphs
DOI: 10.12677/CSA.2019.910204, PDF,    国家自然科学基金支持
作者: 孙 森, 陈京荣*, 吴佩雯：兰州交通大学，甘肃 兰州
关键词: 点覆盖；蚁群算法；信息素更新；时间复杂性；Vertex Coverage； Ant Colony Algorithm； Pheromone Updating； Time Complexity
摘要: 点覆盖问题为组合优化中一个经典的NP完全问题。目前，该问题在有效的多项式时间内无法找到最优解。文章针对蚁群算法可能出现的早期停滞问题进行改进，通过对信息素浓度进行限定，信息素浓度不会在好的顶点继续加强，也不会忽略掉潜在的一些搜索区域。该算法有效地避免了局部最优，提高了算法的准确度，得到时间复杂性为0[(n-1)2-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)2-n].
文章引用：孙森, 陈京荣, 吴佩雯. 赋权图点覆盖问题的蚁群算法求解[J]. 计算机科学与应用, 2019, 9(10): 1823-1830. https://doi.org/10.12677/CSA.2019.910204

参考文献

[1] Johnson, D.S. (1979) Approximation Algorithms for Combinatorial Problems. Journal of Computer and System Scienc-es, 9, 256-278. [Google Scholar] [CrossRef] 
[2] 谢政. 网络最优化[M]. 北京: 科学出版社, 2014.
[3] Balaji, S., Swaminathan, V. and Kannan, K. (2010) An Effective Algorithm for Minimum Weighted Vertex Cover Problem. International Journal of Computational and Mathematical Sciences, 4, 34-38.
[4] Niedermeier, R. and Rossmanith, P. (2003) On Efficient Fixed-Parameter Algorithms for Weighted Vertex Cover. Journal of Algorithms, 47, 63-77. [Google Scholar] [CrossRef] 
[5] Chvatal, V. (1979) A Greedy Heuristic for the Set-Covering Problem. Mathematics of Operations Research, 4, 233-235. [Google Scholar] [CrossRef] 
[6] Taoka, S. and Watanabe, T. (2012) Performance Comparison of Ap-proximation Algorithms for the Minimum Weight Vertex Cover Problem. ISCAS, 209, 632-635. [Google Scholar] [CrossRef] 
[7] 寇磊, 崔笑川, 陈京荣. 最小权点覆盖问题的一个近似算法[J]. 数学的实践与认识, 2015, 45(12): 201-206.
[8] 王丽丽, 崔晋川. 求解最小点覆盖问题实例的计算成本的一种度量方法[J]. 数学的实践与认识, 2017, 47(23): 142-149.
[9] 骆伟忠, 蔡昭权. 基于核心化技术的点覆盖改进算法[J]. 计算机工程与科学, 2018, 40(8): 1405-1411.
[10] 郝斌斌, 吕斌, 陈京荣. 基于最小点覆盖的共享单车投放点选取方法[J]. 交通信息安全, 2018, 36(5): 147-152.
[11] Colorni, A., Dorlgo, M. and Maniezzo, V. (1992) An Investigation of Some Properties of an Ant Algorithm. In: Proceedings of the Parallel Problem Solving from Nature Conference, Elsevier Publishing, Brussels, 509-520.
[12] Bonabeau, E., Dorigo, M. and Teraulaz, G. (2000) Inspiration Foe Optimzation from Social Insect Behavior. Nature, 406, 39-42. [Google Scholar] [CrossRef] [PubMed]
[13] 吴佩雯, 陈京荣, 姬璐烨. 基于蚁群算法的赋权图点覆盖问题[J]. 应用数学进展, 2017, 6(9): 1119-1125.
[14] 葛洪伟, 高阳. 基于蚁群算法的集合覆盖问题[J]. 计算机工程与应用, 2007, 43(4): 49-50, 255.
[15] 范辉, 华臻, 李晋江, 原达. 点覆盖问题的蚂蚁算法求解[J]. 计算机工程与应用, 2004, 40(23): 71-73.
[16] Bouamama, S., Blum, C. and Boukerram, A. (2012) A Population-Based Iterated Greedy Algorithm for the Minimum Weight Vertex Cover Problem. Applied Soft Computing Journal, 12, 1632-1639. [Google Scholar] [CrossRef]