
›› 2018,Vol. 33 ›› Issue (2): 305322.doi: 10.1007/s1139001717814
所属专题： Artificial Intelligence and Pattern Recognition
• Artificial Intelligence and Pattern Recognition • 上一篇 下一篇
Geng Lin^{1}, Jian Guan^{2}
Geng Lin^{1}, Jian Guan^{2}
最小赋权支配集问题是一个有着广泛应用背景的NP困难问题。目前的启发式算法能够求得高质量的解，但是，随着问题规模的增加，它们的求解时间快速增长。本文提出了一个近似求解最小赋权支配集问题的二进制粒子群算法。该算法基于最小赋权支配集问题的结构特征，设计了一个新的位置更新规则来指导搜索，通过迭代贪心禁忌搜索快速提高解的质量。此外，采用若干个随机策略来多样化搜索和避免早熟收敛。这些方法有效地保持了局部开拓能力和全局收敛能力之间的平衡性。在106组共1060个例子上的数值实验结果表明，本文算法能够在较短时间内找到近似最优解。算法得到的近似解与已知最好解的平均偏差是0.441%。而且，本文算法的平均求解时间低于现存算法的平均求解时间。特别地，随着问题规模的增加，本文算法求解时间增加的速度明显低于现存算法。
[1] Garey M R, Johnson D S. Computers and Intractability:A Guide to the Theory of NPCompleteness. Freeman and Company, 1979, pp.190203. [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:6173. [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):727737. [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):2329. [5] Ma T H, Zhou J J, Tang M L Tian Y, AlDhelaan A, AlRodhaan M, Lee S. Social network and tag sources based augmenting collaborative recommender system. IEICE Trans. Information and Systems, 2015, E98D(4):902910. [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 Cmeans algorithm. Journal of Intelligent & Fuzzy Systems, 2015, 28(2):961973. [8] Li J, Li X L, Yang B, Sun X M. Segmentationbased image copymove forgery detection scheme. IEEE Trans. Information Forensics and Security, 2015, 10(3):507518. [9] Kennedy J, Eberhart R C. Particle swarm optimization. In Proc. IEEE Int. Conf. Neural Networks, Nov.27Dec.1, 1995, pp.19421948. [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.41044108. [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):327339. [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):28332844. [13] Wang B, Peng Q K, Zhao J, Chen X. A binary particle swarm optimization algorithm inspired by multilevel organizational learning behavior. European Journal of Operational Research, 2012, 219(2):224233. [14] Wang H S, Yan X F. Optimizing the echo state network with a binary particle swarm optimization algorithm. KnowledgeBased Systems, 2015, 86:182193. [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:966981. [16] Bansal J C, Deep K. A modified binary particle swarm optimization for Knapsack Problems. Applied Mathematics and Computation, 2012, 218(22):1104211061. [17] Qin J, Li X, Yin Y X. An algorithmic framework of discrete particle swarm optimization. Applied Soft Computing, 2012, 12(3):11251130. [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:12501256. [19] Chen G L, Guo W Z, Chen Y Z. A PSObased intelligent decision algorithm for VLSI floorplanning. Soft Computing, 2010, 14(12):13291337. [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):173182. [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.547552. [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.), SpringerVerlag, 2007, pp.96107. [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):892907. [24] Alon N, Moshkovitz D, Safra M. Algorithmic construction of sets for krestrictions. ACM Trans. Algorithms, 2006, 2(2):153177. [25] Zou F, Wang Y X, Xu X H, Li X Y, Du H W, Wan P J, Wu W L. New approximations for minimumweighted dominating sets and minimumweighted connected dominating sets on unit disk graphs. Theoretical Computer Science, 2011, 412(3):198208. [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):443450. [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.), SpringerVerlag, 2015, pp.898909. [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):641648. [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.322326. [30] Potluri A, Singh A. Hybrid metaheuristic algorithms for minimum weight dominating set. Applied Soft Computing, 2013, 13(1):7688. [31] Chaurasia S N, Singh A. A hybrid evolutionary algorithm with guided mutation for minimum weight dominating set. Applied Intelligence, 2015, 43(3):512529. [32] Bouamama S, Blum C. A hybrid algorithmic model for the minimum weight dominating set problem. Simulation Modelling Practice and Theory, 2016, 64:5768. [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):97109. [34] García S, Molina D, Lozano M, Herrera F. A study on the use of nonparametric 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):617644. [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):318. [36] Mladenovic N, Urosevic D, PérezBrito D, GarcíaGonzález C G. Variable neighbourhood search for bandwidth reduction. European Journal of Operational Research, 2010, 200(1):1427. [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):899909. [38] Kothari R, Ghosh D. An efficient genetic algorithm for single row facility layout. Optimization Letters, 2014, 8(2):679690. 
No related articles found! 

版权所有 © 《计算机科学技术学报》编辑部 本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn 总访问量： 