基于蚁群算法的赋权图点覆盖问题
Vertex Covering Problem of Weighted Graphs Based on Ant Colony Algorithm
DOI: 10.12677/AAM.2017.69136, PDF,  被引量    国家自然科学基金支持
作者: 吴佩雯, 陈京荣, 姬璐烨：兰州交通大学数理学院，甘肃 兰州
关键词: 点覆盖；蚁群算法；状态转移规则；赋权图；Point Coverage； Ant Colony Algorithm； State Transition Rule； Weighted Graph
摘要: 点覆盖问题是一个在实际生活中具有重要意义的NP完全问题。蚁群算法为近年来新出现的一种仿生类随机寻优算法。文章运用蚁群算法研究了赋权图的最小点覆盖问题。给出了一个基于蚁群算法的近似算法，得出最小点覆盖问题的近似解。通过修改蚂蚁的状态转移概率公式，简化状态转移规则，建立了相应的数学模型，从而得出求解点覆盖的近似算法，最后进行了实例解析。实验结果表明该算法是行之有效的。
Abstract: Point covering problem is a NP complete problem in real life. Ant colony algorithm is a new bionic stochastic optimization algorithm emerging in recent years. In this paper, the minimum coverage problem of weighting graphs is studied by using the ant colony algorithm. An approximate algo-rithm based on ant colony algorithm is proposed to solve the minimum point covering problem. By modifying the state transition probability formula of ants and simplifying the state transition rules, the corresponding mathematical model is established, and then the approximate algorithm for solving the point coverage is obtained. Finally, an example is analyzed. The experimental results show that the algorithm is effective.
文章引用：吴佩雯, 陈京荣, 姬璐烨. 基于蚁群算法的赋权图点覆盖问题[J]. 应用数学进展, 2017, 6(9): 1119-1125. https://doi.org/10.12677/AAM.2017.69136

参考文献

[1] Johnson, D.S. (1974) Approximation Algorithms for Combinatorial Problems. JCSS, 9, 256-278.
[2] Karp, R.M. (1972) Reducibility among Combinatorial Problems. Plenum Press, New York, 85-100.
[Google Scholar] [CrossRef] 
[3] Garey, M.R. and Andjohnson, D. (1979) Computers and In-tractability. Freeman and Co., New York.
[4] Savage, C. (1982) Depth-First Search and the Vertex Cover Problem. Information Processing Letters, 14, 233-235.
[Google Scholar] [CrossRef] 
[5] Pitt, L. (1985) A Simple Probabilistic Approximation Algo-rithm for Vertex Cover. Department of Computer Science, Yale University, New Haven.
[6] Avis, D. and Imamura, T. (2007) A List Heuristic for Vertex Cover. Operations Research Letters, 35, 201-204.
[Google Scholar] [CrossRef] 
[7] Delbot, F. and Andlaforest, C. (2008) A Better List Heuristic for Vertex Cover. Information Processing Letters, 107, 125-127.
[Google Scholar] [CrossRef] 
[8] Buss, J.F. and Goldsmith, J. (1993) Nondeterminism within P. Springer Berlin Heidelberg, 480(3): 348-359.
[Google Scholar] [CrossRef] 
[9] Khuri, S. and Back, T. (1994) An Evolutionary Heuristic for the Minimum Vertex Cover Problem. Genetic Algorithms within the Framework of Evolutionary Computation, 86-90.
[10] Voß, S. and Fink, A. (2012) A Hybridized Tabu Search Approach for the Minimum Weight Vertex Cover Problem. Journal of Heuristics, 18, 869-876.
[Google Scholar] [CrossRef] 
[11] 周康, 许进. 最小顶点覆盖问题的闭环DNA算法[J]. 计算机工程与应用, 2006, 20(9): 7-9.
[12] 吕健康, 张国基. 求一般图的最小顶点覆盖集问题的混合贪婪算法[J]. 科学技术与工程, 2010, 20(10): 4891-4895.
[13] 郑光勇, 李肯立, 潘果, 徐雨明. 化学反应优化算法求解最小顶点覆盖问题[J]. 小型微型计算机系统, 2015, 36(2): 301-305.
[14] Dorigo, M., Maniezzo, V. and Colorni, A. (1996) Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transaction on Systems, Man, and Cybernetics-Part B, 26, 29-41.
[Google Scholar] [CrossRef] [PubMed]
[15] 陈京荣, 俞建宁, 李引珍. 基于蚁群算法的多属性路径选择模型[J]. 系统工程, 2009, 27(5): 30-34.
[16] 陈烨. 带杂交算子的蚁群算法[J]. 计算机工程, 2001, 27(12): 74-76, 126.
[17] 何小峰, 马良 求解图着色问题的量子蚁群算法[J]. 运筹学学报, 2013, 2(17): 19-26.
[18] Shyu, S.J., Yin, P.-Y. and Lin, B.M.T. (2004) An Ant Colony Optimization Algorithm for the Minimum Weight Vertex Cover Problem. Annals of Operations Research, 131, 283-304.
[Google Scholar] [CrossRef] 

为你推荐