? A Binary Particle Swarm Optimization for the Minimum Weight Dominating Set Problem
Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | FAQ
 
Indexed by   SCIE, EI ...
Bimonthly    Since 1986
Journal of Computer Science and Technology 2018, Vol. 33 Issue (2) :305-322    DOI: 10.1007/s11390-017-1781-4
Artificial Intelligence and Pattern Recognition Current Issue | Archive | Adv Search << Previous Articles | Next Articles >>
A Binary Particle Swarm Optimization for the Minimum Weight Dominating Set Problem
Geng Lin1, Jian Guan2
1 Department of Mathematics, Minjiang University, Fuzhou 350121, China;
2 Modern Educational Technology Center, Minjiang University, Fuzhou 350121, China

Abstract
Reference
Related Articles
Download: [PDF 368KB]     Export: BibTeX or EndNote (RIS)  
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.
Articles by authors
Keywordsmetaheuristics   binary particle swarm optimization   tabu search   dominating set problem   combinatorial optimization     
Received 2017-01-18;
Fund:

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.

Corresponding Authors: 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
Cite this article:   
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
URL:  
http://jcst.ict.ac.cn:8080/jcst/EN/10.1007/s11390-017-1781-4
Copyright 2010 by Journal of Computer Science and Technology