An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem

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.

Graphical abstract

Keywords

evolutionary algorithm / combinatorial optimization / minimum independent dominating set / local search / master apprentice / path breaking

References

[1] 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

[2] 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

[3] 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

[4] 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

[5] Alofairi A A, Mabrouk E, Elsemman I E . Constraint-based models for dominating protein interaction networks. IET Systems Biology, 2021, 15( 5): 148–162

[6] 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

[7] Boginski V, Butenko S, Pardalos P M . Statistical analysis of financial networks. Computational Statistics & Data Analysis, 2005, 48( 2): 431–443

[8] Etzion T, Ostergard P R J . Greedy and heuristic algorithms for codes and colorings. IEEE Transactions on Information Theory, 1998, 44( 1): 382–388

[9] Akyildiz I F, Kasimoglu I H . Wireless sensor and actor networks: research challenges. Ad Hoc Networks, 2004, 2( 4): 351–367

[10] 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

[11] 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

[12] Chen Y, Liestman A, Liu J. Clustering algorithms for ad hoc wireless networks. Ad Hoc and Sensor Networks, 2004, 28: 76−90

[13] Lin C R, Gerla M . Adaptive clustering for mobile wireless networks. IEEE Journal on Selected areas in Communications, 1997, 15( 7): 1265–1275

[14] Basagni S. Distributed clustering for ad hoc networks. In: Proceedings of the 4th International Symposium on Parallel Architectures, Algorithms, and Networks. 1999, 310–315

[15] 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

[16] Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1979

[17] 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

[18] 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

[19] 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

[20] Liang Y, Huang H, Cai Z . PSO-ACSC: a large-scale evolutionary algorithm for image matting. Frontiers of Computer Science, 2020, 14( 6): 146321

[21] 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

[22] 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

[23] He P, Hao J K, Wu Q . Grouping memetic search for the colored traveling salesmen problem. Information Sciences, 2021, 570: 689–707

[24] 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,

[25] 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

[26] 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

[27] 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

[28] 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

[29] Wang Y, Li C, Yin M . A two phase removing algorithm for minimum independent dominating set problem. Applied Soft Computing, 2020, 88: 105949

[30] 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

[31] Moalic L, Gondran A . Variations on memetic algorithms for graph coloring problems. Journal of Heuristics, 2018, 24( 1): 1–24

[32] 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

[33] 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,

[34] 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

[35] 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

[36] 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

[37] Glover F . Tabu search—part I. ORSA Journal on Computing, 1989, 1( 3): 190–206

[38] Feo T A, Resende M G C . Greedy randomized adaptive search procedures. Journal of Global Optimization, 1995, 6( 2): 109–133

[39] Trick M A, Johnson D S. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11-13, 1993. Boston: American Mathematical Society, 1996

[40] 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

[41] 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

[42] 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

[43] 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

[44] Wu Q, Hao J K . A review on algorithms for maximum clique problems. European Journal of Operational Research, 2015, 242( 3): 693–709

[45] 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

[46] 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

[47] 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

[48] 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

[49] 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

[50] 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

[51] 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

[52] 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

[53] 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

[54] 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

[55] 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

[56] 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

[57] 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

RIGHTS & PERMISSIONS

Higher Education Press