1. School of Computer Science and Information Technology, Northeast Normal University, Changchun 130117, China 2. Key Laboratory of Applied Statistics of MOE, Northeast Normal University, Changchun 130117, China
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.
H, Samuel W, Zhuang B Preiss . DTN based dominating set routing for MANET in heterogeneous wireless networking. Mobile Networks and Applications, 2009, 14( 2): 154–164
2
M, Abseher N, Musliu S Woltran . Improving the efficiency of dynamic programming on tree decompositions via machine learning. Journal of Artificial Intelligence Research, 2017, 58: 829–858
3
B, Aoun R, Boutaba Y, Iraqi G Kenward . Gateway placement optimization in wireless mesh networks with QoS constraints. IEEE Journal on Selected Areas in Communications, 2006, 24( 11): 2127–2136
4
A, Potluri C Bhagvati . 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
A A, Alofairi E, Mabrouk I E Elsemman . Constraint-based models for dominating protein interaction networks. IET Systems Biology, 2021, 15( 5): 148–162
6
Y, Jin J K Hao . General swap-based multiple neighborhood tabu search for the maximum independent set problem. Engineering Applications of Artificial Intelligence, 2015, 37: 20–33
7
V, Boginski S, Butenko P M Pardalos . Statistical analysis of financial networks. Computational Statistics & Data Analysis, 2005, 48( 2): 431–443
8
T, Etzion P R J Ostergard . Greedy and heuristic algorithms for codes and colorings. IEEE Transactions on Information Theory, 1998, 44( 1): 382–388
9
I F, Akyildiz I H Kasimoglu . Wireless sensor and actor networks: research challenges. Ad Hoc Networks, 2004, 2( 4): 351–367
10
B, McLaughlan K Akkaya . Coverage-based clustering of wireless sensor and actor networks. In: Proceedings of IEEE International Conference on Pervasive Services. 2007, 45–54
11
K, Erciyes O, Dagdeviren D, Cokuslu D Ozsoyeller . 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
C R, Lin M Gerla . 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
G, Chen F G, Nocetti J S, Gonzalez I Stojmenovic . Connectivity based k-hop clustering in wireless networks. In: Proceedings of the 35th Annual Hawaii International Conference on System Sciences. 2002, 2450–2459
16
M R, Garey D S Johnson . Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1979
17
S, Gaspers M Liedloff . 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
C, Liu Y Song . 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
N, Bourgeois F D, Croce B, Escoffier V T Paschos . Fast algorithms for min independent dominating set. Discrete Applied Mathematics, 2013, 161(4–5): 558–572
20
Y, Liang H, Huang Z Cai . PSO-ACSC: a large-scale evolutionary algorithm for image matting. Frontiers of Computer Science, 2020, 14( 6): 146321
21
Y, Wang S, Cai J, Chen M Yin . SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem. Artificial Intelligence, 2020, 280: 103230
22
C, Chen L, Gao X, Xie Z Wang . 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
P, He J K, Hao Q Wu . 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, doi:
25
L, Liu Y Du . An improved multi-objective evolutionary algorithm for computation offloading in the multi-cloudlet environment. Frontiers of Computer Science, 2021, 15( 5): 155503
26
Y, Wang R, Li Y, Zhou M Yin . A path cost-based grasp for minimum independent dominating set problem. Neural Computing and Applications, 2017, 28( S1): 143–151
27
Y, Wang J, Chen H, Sun M Yin . A memetic algorithm for minimum independent dominating set problem. Neural Computing and Applications, 2018, 30( 8): 2519–2529
28
K Haraguchi . An efficient local search for the minimum independent dominating set problem. In: Proceedings of the 17th International Symposium on Experimental Algorithms. 2018, 13
29
Y, Wang C, Li M Yin . A two phase removing algorithm for minimum independent dominating set problem. Applied Soft Computing, 2020, 88: 105949
30
J, Ding Z, Lü C M, Li L, Shen L, Xu F Glover . 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
L, Moalic A Gondran . Variations on memetic algorithms for graph coloring problems. Journal of Heuristics, 2018, 24( 1): 1–24
32
B, Peng Y, Zhang T C E, Cheng Z, Lü A P Punnen . 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, doi:
34
Q, Sun J, Dou C Zhang . 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
Y, Wang Z, Lü A P Punnen . A fast and robust heuristic algorithm for the minimum weight vertex cover problem. IEEE Access, 2021, 9: 31932–31945
36
Z, Xu K, He C M Li . An iterative path-breaking approach with mutation and restart strategies for the max-sat problem. Computers & Operations Research, 2019, 104: 49–58
37
F Glover . Tabu search—part I. ORSA Journal on Computing, 1989, 1( 3): 190–206
38
T A, Feo M G C Resende . Greedy randomized adaptive search procedures. Journal of Global Optimization, 1995, 6( 2): 109–133
39
M A, Trick D S Johnson . Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11-13, 1993. Boston: American Mathematical Society, 1996
40
Y, Zhou J K, Hao B Duval . Reinforcement learning based local search for grouping problems: A case study on graph coloring. Expert Systems with Applications, 2016, 64: 412–422
41
Y, Wang J K, Hao F, Glover Z, Lü Q Wu . 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
S, Cai K, Su C, Luo A Sattar . NuMVC: an efficient local search algorithm for minimum vertex cover. Journal of Artificial Intelligence Research, 2013, 46: 687–716
44
Q, Wu J K Hao . 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
S Cai . 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
M, López-Ibáñez J, Dubois-Lacoste L P, Cáceres M, Birattari T Stützle . The irace package: iterated racing for automatic algorithm configuration. Operations Research Perspectives, 2016, 3: 43–58
49
M Friedman . 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
S, Garcia F Herrera . 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
C, Luo S, Cai W, Wu Z, Jie K Su . CCLS: an efficient local search algorithm for weighted maximum satisfiability. IEEE Transactions on Computers, 2015, 64( 7): 1830–1843
53
C, Luo S, Cai K, Su W Huang . CCEHC: an efficient local search algorithm for weighted partial maximum satisfiability. Artificial Intelligence, 2017, 243: 26–44
54
X, Liu J, Liang D Y, Liu R, Chen S M Yuan . 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
C, Qian J C, Shi K, Tang Z H Zhou . Constrained monotone k-submodular function maximization using multiobjective evolutionary algorithms with theoretical guarantee. IEEE Transactions on Evolutionary Computation, 2018, 22( 4): 595–608
56
C, Luo H H, Hoos S, Cai Q, Lin H, Zhang D Zhang . 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
Z, Lei S, Cai C, Luo H Hoos . Efficient local search for pseudo Boolean optimization. In: Proceedings of the 24th International Conference on Theory and Applications of Satisfiability Testing. 2021, 332–348
