? 一种求解最小赋权支配集问题的二进制粒子群算法
Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | Help
 
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 << Previous Articles | Next Articles >>
一种求解最小赋权支配集问题的二进制粒子群算法
Geng Lin1, Jian Guan2
1 Department of Mathematics, Minjiang University, Fuzhou 350121, China;
2 Modern Educational Technology Center, Minjiang University, Fuzhou 350121, China
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

摘要
参考文献
相关文章
Download: [PDF 368KB]  
摘要 最小赋权支配集问题是一个有着广泛应用背景的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.
Keywordsmetaheuristics   binary particle swarm optimization   tabu search   dominating set problem   combinatorial optimization     
Received 2017-01-18;
本文基金:

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
链接本文:  
http://jcst.ict.ac.cn:8080/jcst/CN/10.1007/s11390-017-1781-4
Copyright 2010 by Journal of Computer Science and Technology