|
|
|
An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem |
Shiwei PAN1,2, Yiming MA1,2, Yiyuan WANG1,2, Zhiguo ZHOU1,2( ), Jinchao JI1,2(), Minghao YIN1,2(), Shuli HU1,2 |
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 |
|
|
|
|
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.
|
| Keywords
evolutionary algorithm
combinatorial optimization
minimum independent dominating set
local search
master apprentice
path breaking
|
|
Corresponding Author(s):
Zhiguo ZHOU,Jinchao JI,Minghao YIN
|
|
Just Accepted Date: 30 June 2022
Issue Date: 09 December 2022
|
|
| 1 |
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
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
