›› 2018,Vol. 33 ›› Issue (2): 305-322.doi: 10.1007/s11390-017-1781-4

所属专题： Artificial Intelligence and Pattern Recognition

• Artificial Intelligence and Pattern Recognition • 上一篇    下一篇

一种求解最小赋权支配集问题的二进制粒子群算法

Geng Lin1, Jian Guan2   

  1. 1 Department of Mathematics, Minjiang University, Fuzhou 350121, China;
    2 Modern Educational Technology Center, Minjiang University, Fuzhou 350121, China
  • 收稿日期:2017-01-18 修回日期:2017-05-16 出版日期:2018-03-05 发布日期:2018-03-05
  • 作者简介:Geng Lin received his B.S. degree in information and computing sciences, M.S. degree in operations research and cybernetics, and Ph.D. degree in applied mathematics, all from Fuzhou University, Fuzhou, in 2004, 2007, and 2010, respectively. He is currently an associate professor with the Department of Mathematics, Minjiang University, Fuzhou. His research interests include combinatorial optimization and artificial intelligence
  • 基金资助:

    This work is supported partially by the National Natural Science Foundation of China under Grant No. 11301255, the Natural Science Foundation of Fujian Province of China under Grant No. 2016J01025, and the Program for New Century Excellent Talents in Fujian Province University.

A Binary Particle Swarm Optimization for the Minimum Weight Dominating Set Problem

Geng Lin1, Jian Guan2   

  1. 1 Department of Mathematics, Minjiang University, Fuzhou 350121, China;
    2 Modern Educational Technology Center, Minjiang University, Fuzhou 350121, China
  • Received:2017-01-18 Revised:2017-05-16 Online:2018-03-05 Published:2018-03-05
  • Contact: 10.1007/s11390-017-1781-4
  • About author:Geng Lin received his B.S. degree in information and computing sciences, M.S. degree in operations research and cybernetics, and Ph.D. degree in applied mathematics, all from Fuzhou University, Fuzhou, in 2004, 2007, and 2010, respectively. He is currently an associate professor with the Department of Mathematics, Minjiang University, Fuzhou. His research interests include combinatorial optimization and artificial intelligence
  • Supported by:

    This work is supported partially by the National Natural Science Foundation of China under Grant No. 11301255, the Natural Science Foundation of Fujian Province of China under Grant No. 2016J01025, and the Program for New Century Excellent Talents in Fujian Province University.

PDF (PC)

731

最小赋权支配集问题是一个有着广泛应用背景的NP困难问题。目前的启发式算法能够求得高质量的解，但是，随着问题规模的增加，它们的求解时间快速增长。本文提出了一个近似求解最小赋权支配集问题的二进制粒子群算法。该算法基于最小赋权支配集问题的结构特征，设计了一个新的位置更新规则来指导搜索，通过迭代贪心禁忌搜索快速提高解的质量。此外，采用若干个随机策略来多样化搜索和避免早熟收敛。这些方法有效地保持了局部开拓能力和全局收敛能力之间的平衡性。在106组共1060个例子上的数值实验结果表明，本文算法能够在较短时间内找到近似最优解。算法得到的近似解与已知最好解的平均偏差是0.441%。而且，本文算法的平均求解时间低于现存算法的平均求解时间。特别地，随着问题规模的增加，本文算法求解时间增加的速度明显低于现存算法。

Abstract: The minimum weight dominating set problem (MWDSP) is an NP-hard problem with a lot of real-world applications. Several heuristic algorithms have been presented to produce good quality solutions. However, the solution time of them grows very quickly as the size of the instance increases. In this paper, we propose a binary particle swarm optimization (FBPSO) for solving the MWDSP approximately. Based on the characteristic of MWDSP, this approach designs a new position updating rule to guide the search to a promising area. An iterated greedy tabu search is used to enhance the solution quality quickly. In addition, several stochastic strategies are employed to diversify the search and prevent premature convergence. These methods maintain a good balance between the exploration and the exploitation. Experimental studies on 106 groups of 1 060 instances show that FBPSO is able to identify near optimal solutions in a short running time. The average deviation between the solutions obtained by FBPSO and the best known solutions is 0.441%. Moreover, the average solution time of FBPSO is much less than that of other existing algorithms. In particular, with the increasing of instance size, the solution time of FBPSO grows much more slowly than that of other existing algorithms.

[1] Garey M R, Johnson D S. Computers and Intractability:A Guide to the Theory of NP-Completeness. Freeman and Company, 1979, pp.190-203.

[2] Mohanty J P, Mandal C, Reade C, Das A. Construction of minimum connected dominating set in wireless sensor networks using pseudo dominating set. Ad Hoc Networks, 2016, 42:61-73.

[3] Han B, Jia W J. Clustering wireless ad hoc networks with weakly connected dominating set. Journal of Parallel and Distributed Computing, 2007, 67(6):727-737.

[4] Katsaros D, Dimokas N, Tassiulas L. Social network analysis concepts in the design of wireless ad hoc network protocols. IEEE Network, 2010, 24(6):23-29.

[5] Ma T H, Zhou J J, Tang M L Tian Y, Al-Dhelaan A, Al-Rodhaan M, Lee S. Social network and tag sources based augmenting collaborative recommender system. IEICE Trans. Information and Systems, 2015, E98-D(4):902-910.

[6] Wu P, Wen J R, Liu H, Ma W Y. Query selection techniques for efficient crawling of structured Web sources. In Proc. the 22nd Int. Conf. Data Engineering, April 2006.

[7] Zheng Y H, Jeon B, Xu D H, Wu Q M J, Zhang H. Image segmentation by generalized hierarchical fuzzy C-means algorithm. Journal of Intelligent & Fuzzy Systems, 2015, 28(2):961-973.

[8] Li J, Li X L, Yang B, Sun X M. Segmentation-based image copy-move forgery detection scheme. IEEE Trans. Information Forensics and Security, 2015, 10(3):507-518.

[9] Kennedy J, Eberhart R C. Particle swarm optimization. In Proc. IEEE Int. Conf. Neural Networks, Nov.27-Dec.1, 1995, pp.1942-1948.

[10] Kennedy J, Eberhart R C. A discrete binary version of the particle swarm algorithm. In Proc. Int. Conf. Systems Man and Cybernetics, October 1997, pp.4104-4108.

[11] Jolai F, Taghipour M, Javadi B. A variable neighborhood binary particle swarm algorithm for cell layout problem. The International Journal of Advanced Manufacturing Technology, 2011, 55(1/2/3/4):327-339.

[12] Luh G C, Lin C Y, Lin Y S. A binary particle swarm optimization for continuum structural topology optimization. Applied Soft Computing, 2011, 11(2):2833-2844.

[13] Wang B, Peng Q K, Zhao J, Chen X. A binary particle swarm optimization algorithm inspired by multi-level organizational learning behavior. European Journal of Operational Research, 2012, 219(2):224-233.

[14] Wang H S, Yan X F. Optimizing the echo state network with a binary particle swarm optimization algorithm. Knowledge-Based Systems, 2015, 86:182-193.

[15] Zhao X C, Lin W Q, Hao J L, Zuo X Q, Yuan J H. Clustering and pattern search for enhancing particle swarm optimization with Euclidean spatial neighborhood search. Neurocomputing, 2016, 171:966-981.

[16] Bansal J C, Deep K. A modified binary particle swarm optimization for Knapsack Problems. Applied Mathematics and Computation, 2012, 218(22):11042-11061.

[17] Qin J, Li X, Yin Y X. An algorithmic framework of discrete particle swarm optimization. Applied Soft Computing, 2012, 12(3):1125-1130.

[18] Xu L, Qian F, Li Y P, Li Q M, Yang Y W, Xu J. Resource allocation based on quantum particle swarm optimization and RBF neural network for overlay cognitive OFDM system. Neurocomputing, 2016, 173:1250-1256.

[19] Chen G L, Guo W Z, Chen Y Z. A PSO-based intelligent decision algorithm for VLSI floorplanning. Soft Computing, 2010, 14(12):1329-1337.

[20] Coit D W, Smith A E, Tate D M. Adaptive penalty methods for genetic optimization of constrained combinatorial problems. INFORMS Journal on Computing, 1996, 8(2):173-182.

[21] Handoko S D, Keong K C, Ong Y S. Using classification for constrained memetic algorithm:A new paradigm. In Proc. IEEE Int. Conf. Systems Man and Cybernetics, October 2008, pp.547-552.

[22] Kubiak M, Wesolek P. Accelerating local search in a memetic algorithm for the capacitated vehicle routing problem. In Evolutionary Computation in Combinatorial Optimization, Cotta C, Van Hemert J (eds.), Springer-Verlag, 2007, pp.96-107.

[23] Lin G, Zhu W X, Ali M M. An effective hybrid memetic algorithm for the minimum weight dominating set problem. IEEE Trans. Evolutionary Computation, 2016, 20(6):892-907.

[24] Alon N, Moshkovitz D, Safra M. Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms, 2006, 2(2):153-177.

[25] Zou F, Wang Y X, Xu X H, Li X Y, Du H W, Wan P J, Wu W L. New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs. Theoretical Computer Science, 2011, 412(3):198-208.

[26] Zhu X, Wang W, Shan S, Wang Z, Wu W L. A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs. Journal of Combinatorial Optimization, 2012, 23(4):443-450.

[27] Li J, Jin Y F. A PTAS for the weighted unit disk cover problem. In Automata Languages and Programming, Halldórsson M M, Iwama K, Kobayashi N, Speckmann B (eds.), Springer-Verlag, 2015, pp.898-909.

[28] Wang Z, Wang W, Kim J M, Thuraisingham B, Wu W L. PTAS for the minimum weighted dominating set in growth bounded graphs. Journal of Global Optimization, 2012, 54(3):641-648.

[29] Jovanovic R, Tuba M, Simian D. Ant colony optimization applied to minimum weight dominating set problem. In Proc. the 12th WSEAS Int. Conf. Automatic Control Modelling & Simulation, May 2010, pp.322-326.

[30] Potluri A, Singh A. Hybrid metaheuristic algorithms for minimum weight dominating set. Applied Soft Computing, 2013, 13(1):76-88.

[31] Chaurasia S N, Singh A. A hybrid evolutionary algorithm with guided mutation for minimum weight dominating set. Applied Intelligence, 2015, 43(3):512-529.

[32] Bouamama S, Blum C. A hybrid algorithmic model for the minimum weight dominating set problem. Simulation Modelling Practice and Theory, 2016, 64:57-68.

[33] Hedar A R, Ismail R. Simulated annealing with stochastic local search for minimum dominating set problem. International Journal of Machine Learning and Cybernetics, 2012, 3(2):97-109.

[34] García S, Molina D, Lozano M, Herrera F. A study on the use of non-parametric tests for analyzing the evolutionary algorithms' behaviour:A case study on the CEC' 2005 Special Session on Real Parameter Optimization. Journal of Heuristics, 2009, 15(6):617-644.

[35] Derrac J, García S, Molina D, Herrera F. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm and Evolutionary Computation 2011, 1(1):3-18.

[36] Mladenovic N, Urosevic D, Pérez-Brito D, García-González C G. Variable neighbourhood search for bandwidth reduction. European Journal of Operational Research, 2010, 200(1):14-27.

[37] Guan J, Lin G. Hybridizing variable neighborhood search with ant colony optimization for solving the single row facility layout problem. European Journal of Operational Research, 2016, 248(3):899-909.

[38] Kothari R, Ghosh D. An efficient genetic algorithm for single row facility layout. Optimization Letters, 2014, 8(2):679-690.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 陈昉; 施伯乐;. A Conservative Multiversion Locking-Graph Scheduler Algorithm[J]. , 1991, 6(2): 161 -166 .
[2] 周哈阳;. Analogical Learning and Automated Rule Constructions[J]. , 1991, 6(4): 316 -328 .
[3] 武君胜; 吴广茂;. Element-Partition-Based Methods for Visualization of 3D Unstructured Grid Data[J]. , 1998, 13(5): 417 -425 .
[4] 吕卫锋; 张玉平;. Experimental Study on Strategy of CombiningSAT Algorithms[J]. , 1998, 13(6): 608 -614 .
[5] 周巢尘;. An Overview of Duration Calculus[J]. , 1998, 13(6): 552 .
[6] 陈海明;. Function Definition Language FDL andIts Implementation[J]. , 1999, 14(4): 414 -421 .
[7] 舒炎泰; 薛飞; 金志刚;. The Impact of Self-Similar Traffic on Network Delay[J]. , 1999, 14(6): 585 -589 .
[8] 马军; 杨波; 马绍汉;. A Practical Algorithm for the Minimum Rectilinear Steiner Tree[J]. , 2000, 15(1): 96 -99 .
[9] 马宗民; ZHANG W.J; MA W.Y;. Extending the Relational Model to Deal with Probabilistic Data[J]. , 2000, 15(3): 230 -240 .
[10] . 作为概念内涵的逻辑句子[J]. , 2005, 20(3): 338 -344 .
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：