Abstract
The minimum independent dominance set (MIDS) problem is an important version of the dominating set with some other applications. In this work, we present an improved master-apprentice evolutionary algorithm for solving the MIDS problem based on a path-breaking strategy called MAE-PB. The proposed MAE-PB algorithm combines a construction function for the initial solution generation and candidate solution restarting. It is a multiple neighborhood-based local search algorithm that improves the quality of the solution using a path-breaking strategy for solution recombination based on master and apprentice solutions and a perturbation strategy for disturbing the solution when the algorithm cannot improve the solution quality within a certain number of steps. We show the competitiveness of the MAE-PB algorithm by presenting the computational results on classical benchmarks from the literature and a suite of massive graphs from real-world applications. The results show that the MAE-PB algorithm achieves high performance. In particular, for the classical benchmarks, the MAE-PB algorithm obtains the best-known results for seven instances, whereas for several massive graphs, it improves the best-known results for 62 instances. We investigate the proposed key ingredients to determine their impact on the performance of the proposed algorithm.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Samuel H, Zhuang W, Preiss B. DTN based dominating set routing for MANET in heterogeneous wireless networking. Mobile Networks and Applications, 2009, 14(2): 154–164
Abseher M, Musliu N, Woltran S. Improving the efficiency of dynamic programming on tree decompositions via machine learning. Journal of Artificial Intelligence Research, 2017, 58: 829–858
Aoun B, Boutaba R, Iraqi Y, Kenward G. Gateway placement optimization in wireless mesh networks with QoS constraints. IEEE Journal on Selected Areas in Communications, 2006, 24(11): 2127–2136
Potluri A, Bhagvati C. Novel morphological algorithms for dominating sets on graphs with applications to image analysis. In: Proceedings of the 15th International Workshop on Combinatorial Image Analysis. 2012, 249–262
Alofairi A A, Mabrouk E, Elsemman I E. Constraint-based models for dominating protein interaction networks. IET Systems Biology, 2021, 15(5): 148–162
Jin Y, Hao J K. General swap-based multiple neighborhood tabu search for the maximum independent set problem. Engineering Applications of Artificial Intelligence, 2015, 37: 20–33
Boginski V, Butenko S, Pardalos P M. Statistical analysis of financial networks. Computational Statistics & Data Analysis, 2005, 48(2): 431–443
Etzion T, Ostergard P R J. Greedy and heuristic algorithms for codes and colorings. IEEE Transactions on Information Theory, 1998, 44(1): 382–388
Akyildiz I F, Kasimoglu I H. Wireless sensor and actor networks: research challenges. Ad Hoc Networks, 2004, 2(4): 351–367
McLaughlan B, Akkaya K. Coverage-based clustering of wireless sensor and actor networks. In: Proceedings of IEEE International Conference on Pervasive Services. 2007, 45–54
Erciyes K, Dagdeviren O, Cokuslu D, Ozsoyeller D. Graph theoretic clustering algorithms in mobile ad hoc networks and wireless sensor networks. Applied and Computational Mathematics, 2007, 6(2): 162–180
Chen Y, Liestman A, Liu J. Clustering algorithms for ad hoc wireless networks. Ad Hoc and Sensor Networks, 2004, 28: 76–90
Lin C R, Gerla M. Adaptive clustering for mobile wireless networks. IEEE Journal on Selected areas in Communications, 1997, 15(7): 1265–1275
Basagni S. Distributed clustering for ad hoc networks. In: Proceedings of the 4th International Symposium on Parallel Architectures, Algorithms, and Networks. 1999, 310–315
Chen G, Nocetti F G, Gonzalez J S, Stojmenovic I. Connectivity based k-hop clustering in wireless networks. In: Proceedings of the 35th Annual Hawaii International Conference on System Sciences. 2002, 2450–2459
Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1979
Gaspers S, Liedloff M. A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs. In: Proceedings of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science. 2006, 78–89
Liu C, Song Y. Exact algorithms for finding the minimum independent dominating set in graphs. In: Proceedings of the 17th International Symposium on Algorithms and Computation. 2006, 439–448
Bourgeois N, Croce F D, Escoffier B, Paschos V T. Fast algorithms for min independent dominating set. Discrete Applied Mathematics, 2013, 161(4–5): 558–572
Liang Y, Huang H, Cai Z. PSO-ACSC: a large-scale evolutionary algorithm for image matting. Frontiers of Computer Science, 2020, 14(6): 146321
Wang Y, Cai S, Chen J, Yin M. SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem. Artificial Intelligence, 2020, 280: 103230
Chen C, Gao L, Xie X, Wang Z. Enjoy the most beautiful scene now: a memetic algorithm to solve two-fold time-dependent arc orienteering problem. Frontiers of Computer Science, 2020, 14(2): 364–377
He P, Hao J K, Wu Q. Grouping memetic search for the colored traveling salesmen problem. Information Sciences, 2021, 570: 689–707
Wang Y, Li X, Wong K C, Chang Y, Yang S. Evolutionary multiobjective clustering algorithms with ensemble for patient stratification. IEEE Transactions on Cybernetics, 2021, doi: https://doi.org/10.1109/TCYB.2021.3069434
Liu L, Du Y. An improved multi-objective evolutionary algorithm for computation offloading in the multi-cloudlet environment. Frontiers of Computer Science, 2021, 15(5): 155503
Wang Y, Li R, Zhou Y, Yin M. A path cost-based grasp for minimum independent dominating set problem. Neural Computing and Applications, 2017, 28(S1): 143–151
Wang Y, Chen J, Sun H, Yin M. A memetic algorithm for minimum independent dominating set problem. Neural Computing and Applications, 2018, 30(8): 2519–2529
Haraguchi K. An efficient local search for the minimum independent dominating set problem. In: Proceedings of the 17th International Symposium on Experimental Algorithms. 2018, 13
Wang Y, Li C, Yin M. A two phase removing algorithm for minimum independent dominating set problem. Applied Soft Computing, 2020, 88: 105949
Ding J, Lü Z, Li C M, Shen L, Xu L, Glover F. A two-individual based evolutionary algorithm for the flexible job shop scheduling problem. In: Proceedings of the AAAI Conference on Artificial Intelligence. 2019, 280
Moalic L, Gondran A. Variations on memetic algorithms for graph coloring problems. Journal of Heuristics, 2018, 24(1): 1–24
Peng B, Zhang Y, Cheng T C E, Lü Z, Punnen A P. A two-individual based path-relinking algorithm for the satellite broadcast scheduling problem. Knowledge-Based Systems, 2020, 196: 105774
Zheng P, Zhang P, Wang J, Zhang J, Yang C, Jin Y. A data-driven robust optimization method for the assembly job-shop scheduling problem under uncertainty. International Journal of Computer Integrated Manufacturing, 2020, doi: https://doi.org/10.1080/0951192X.2020.1803506
Sun Q, Dou J, Zhang C. Robust optimization of flow shop scheduling with uncertain processing time. In: Proceedings of 2020 IEEE International Conference on Mechatronics and Automation. 2020, 512–517
Wang Y, Lü Z, Punnen A P. A fast and robust heuristic algorithm for the minimum weight vertex cover problem. IEEE Access, 2021, 9: 31932–31945
Xu Z, He K, Li C M. An iterative path-breaking approach with mutation and restart strategies for the max-sat problem. Computers & Operations Research, 2019, 104: 49–58
Glover F. Tabu search—part I. ORSA Journal on Computing, 1989, 1(3): 190–206
Feo T A, Resende M G C. Greedy randomized adaptive search procedures. Journal of Global Optimization, 1995, 6(2): 109–133
Trick M A, Johnson D S. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993. Boston: American Mathematical Society, 1996
Zhou Y, Hao J K, Duval B. Reinforcement learning based local search for grouping problems: A case study on graph coloring. Expert Systems with Applications, 2016, 64: 412–422
Wang Y, Hao J K, Glover F, Lü Z, Wu Q. Solving the maximum vertex weight clique problem via binary quadratic programming. Journal of Combinatorial Optimization, 2016, 32(2): 531–549
Xu K, Boussemart F, Hemery F, Lecoutre C. Random constraint satisfaction: easy generation of hard (satisfiable) instances. Artificial Intelligence, 2007, 171(8–9): 514–534
Cai S, Su K, Luo C, Sattar A. NuMVC: an efficient local search algorithm for minimum vertex cover. Journal of Artificial Intelligence Research, 2013, 46: 687–716
Wu Q, Hao J K. A review on algorithms for maximum clique problems. European Journal of Operational Research, 2015, 242(3): 693–709
Rossi R A, Ahmed N K. The network data repository with interactive graph analytics and visualization. In: Proceedings of the 49th AAAI Conference on Artificial Intelligence. 2015, 4292–4293
Cai S. Balance between complexity and quality: local search for minimum vertex cover in massive graphs. In: Proceedings of the 24th International Conference on Artificial Intelligence. 2015, 747–753
Wang Y, Cai S, Yin M. Two efficient local search algorithms for maximum weight clique problem. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence. 2016, 805–811
López-Ibáñez M, Dubois-Lacoste J, Cáceres L P, Birattari M, Stützle T. The irace package: iterated racing for automatic algorithm configuration. Operations Research Perspectives, 2016, 3: 43–58
Friedman M. The use of ranks to avoid the assumption of normality implicit in the analysis of variance. Journal of the American Statistical Association, 1937, 32(200): 675–701
Garcia S, Herrera F. An extension on “statistical comparisons of classifiers over multiple data sets” for all pairwise comparisons. Journal of Machine Learning Research, 2008, 9(12): 2677–2694
Luo C, Cai S, Wu W, Su K. Double configuration checking in stochastic local search for satisfiability. In: Proceedings of the 28th AAAI Conference on Artificial Intelligence. 2014, 2703–2709
Luo C, Cai S, Wu W, Jie Z, Su K. CCLS: an efficient local search algorithm for weighted maximum satisfiability. IEEE Transactions on Computers, 2015, 64(7): 1830–1843
Luo C, Cai S, Su K, Huang W. CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability. Artificial Intelligence, 2017, 243: 26–44
Liu X, Liang J, Liu D Y, Chen R, Yuan S M. Weapon-target assignment in unreliable peer-to-peer architecture based on adapted artificial bee colony algorithm. Frontiers of Computer Science, 2022, 16(1): 161103
Qian C, Shi J C, Tang K, Zhou Z H. Constrained monotone k-submodular function maximization using multiobjective evolutionary algorithms with theoretical guarantee. IEEE Transactions on Evolutionary Computation, 2018, 22(4): 595–608
Luo C, Hoos H H, Cai S, Lin Q, Zhang H, Zhang D. Local search with efficient automatic configuration for minimum vertex cover. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. 2019, 1297–1304
Lei Z, Cai S, Luo C, Hoos H. Efficient local search for pseudo Boolean optimization. In: Proceedings of the 24th International Conference on Theory and Applications of Satisfiability Testing. 2021, 332–348
Acknowledgements
This work was supported by the National Natural Science Foundation of China (Grant Nos. 61806050, 61972063, 61976050), the Fundamental Research Funds for the Central Universities (2412020FZ030, 2412019ZD013, 2412019FZ051), and Jilin Science and Technology Association (QT202005). Thanks Dr. Jianan Wang for offering the technical support of the computing server.
Author information
Authors and Affiliations
Corresponding authors
Additional information
Shiwei Pan received the BS and MS degrees from the Department of Computer Science and Technology, Northeast Normal University, China in 2018 and 2021. His current research interests include heuristic search and combinatorial optimization.
Yiming Ma studied at the School of Computer Science and Information Technology, Northeast Normal University, China, with a master’s degree in Computer Science, and the research direction is heuristic search, local search, algorithmic design, and combinatorial optimization.
Yiyuan Wang is Associate Professor at School of Computer Science and Information Technology, Northeast Normal University, China. He received his PhD degree from Jilin University, China. His research interests include heuristic search, local search, algorithmic design, and combinatorial optimization.
Zhiguo Zhou is Associate Professor of Northeast Normal University and received the PhD degree from the College of Computer Science and Technology, Jilin University, China in 2008. His current research interests include algorithm design and analysis.
Jinchao Ji is a Lecturer at School of Information Science and Technology, Northeast Normal University, China. He received his MS and PhD degrees in Computer Application Technology from Jilin University, China in 2010 and 2013, respectively. His research interests include machine learning, data mining, and artificial intelligence.
Minghao Yin is Professor at School of Computer Science and Information Technology, Northeast Normal University, China. He received his PhD degree in Computer Software and Theory from Jilin University, China. His research interests include heuristic search, data mining, and combinatorial optimization.
Shuli Hu is a Lecturer at Northeast Normal University, China. She received the PhD degree from the Department of Computer Science and Technology, Northeast Normal University, China in 2019. Her current research interests include heuristic search and combinatorial optimization.
Electronic supplementary material
Rights and permissions
About this article
Cite this article
Pan, S., Ma, Y., Wang, Y. et al. An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem. Front. Comput. Sci. 17, 174326 (2023). https://doi.org/10.1007/s11704-022-2023-7
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11704-022-2023-7