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.
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.
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
Geng Lin, Jian Guan.一种求解最小赋权支配集问题的二进制粒子群算法[J] Journal of Computer Science and Technology , 2018,V33(2): 305-322
Geng Lin, Jian Guan.A Binary Particle Swarm Optimization for the Minimum Weight Dominating Set Problem[J] Journal of Computer Science and Technology, 2018,V33(2): 305-322
 Garey M R, Johnson D S. Computers and Intractability:A Guide to the Theory of NP-Completeness. Freeman and Company, 1979, pp.190-203. 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. 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. 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. 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. 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. 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. 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. Kennedy J, Eberhart R C. Particle swarm optimization. In Proc. IEEE Int. Conf. Neural Networks, Nov.27-Dec.1, 1995, pp.1942-1948. 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. 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. 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. 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. 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. 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. Bansal J C, Deep K. A modified binary particle swarm optimization for Knapsack Problems. Applied Mathematics and Computation, 2012, 218(22):11042-11061. Qin J, Li X, Yin Y X. An algorithmic framework of discrete particle swarm optimization. Applied Soft Computing, 2012, 12(3):1125-1130. 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. 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. 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. 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. 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. 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. Alon N, Moshkovitz D, Safra M. Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms, 2006, 2(2):153-177. 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. 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. 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. 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. 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. Potluri A, Singh A. Hybrid metaheuristic algorithms for minimum weight dominating set. Applied Soft Computing, 2013, 13(1):76-88. Chaurasia S N, Singh A. A hybrid evolutionary algorithm with guided mutation for minimum weight dominating set. Applied Intelligence, 2015, 43(3):512-529. Bouamama S, Blum C. A hybrid algorithmic model for the minimum weight dominating set problem. Simulation Modelling Practice and Theory, 2016, 64:57-68. 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. 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. 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. 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. 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. Kothari R, Ghosh D. An efficient genetic algorithm for single row facility layout. Optimization Letters, 2014, 8(2):679-690.