An adaptive greedy repair operator in a genetic algorithm for the minimum vertex cover problem

Seung-Hyun Moon; Yourim Yoon; Seung-Hyun Moon; Yourim Yoon

doi:10.3934/math.2025600

AIMS Mathematics

2025, Volume 10, Issue 6: 13365-13392. doi: 10.3934/math.2025600

Previous Article Next Article

Research article Special Issues

An adaptive greedy repair operator in a genetic algorithm for the minimum vertex cover problem

Seung-Hyun Moon ¹,
Yourim Yoon ^{2
,
,}

1.
School of Software, Kwangwoon University, 20 Kwangwoon-ro, Nowon-gu, Seoul 01897, Korea
2.
Department of Computer Engineering, Gachon University, 1342 Seongnamdaero, Sujeong-gu, Seongnam-si, Gyeonggi-do 13120, Korea

Received: 14 February 2025 Revised: 01 June 2025 Accepted: 04 June 2025 Published: 10 June 2025
MSC : 68T20

A genetic algorithm (GA) evolves the population of candidate solutions to a particular problem through crossover and mutation operators. Since a newly generated solution may not satisfy the constraints of the given problem, it is common to penalize infeasible solutions or to repair them to feasible solutions. For the minimum vertex cover (MVC) problem, we propose an adaptive greedy repair operator. Our repair operator first repairs an infeasible solution into a feasible one using a randomized greedy algorithm, and then removes unnecessary vertices from the feasible vertex cover, making it a minimal vertex cover. During the repair process, when adding or removing vertices, the degree of exploration and exploitation in the randomized greedy algorithm is adaptively adjusted based on the convergence level of the population. When the population lacks high-quality solutions, the operator strives to generate superior solutions greedily. However, when the solution set has enough high-quality solutions, it explores unexplored choices to break through the limitations of the existing solution set. We compared our GA with a deterministic greedy algorithm, a randomized greedy algorithm, and GAs using various repair operators. Experimental results on benchmark graphs from the Benchmarks with Hidden Optimum Solutions Library (BHOSLIB) demonstrated that the proposed repair operator improved the performance of the GA for the MVC problem.
- genetic algorithm,
- repair operator,
- greedy algorithm,
- approximation algorithm,
- vertex cover
Citation: Seung-Hyun Moon, Yourim Yoon. An adaptive greedy repair operator in a genetic algorithm for the minimum vertex cover problem[J]. AIMS Mathematics, 2025, 10(6): 13365-13392. doi: 10.3934/math.2025600

Related Papers:

Abstract

A genetic algorithm (GA) evolves the population of candidate solutions to a particular problem through crossover and mutation operators. Since a newly generated solution may not satisfy the constraints of the given problem, it is common to penalize infeasible solutions or to repair them to feasible solutions. For the minimum vertex cover (MVC) problem, we propose an adaptive greedy repair operator. Our repair operator first repairs an infeasible solution into a feasible one using a randomized greedy algorithm, and then removes unnecessary vertices from the feasible vertex cover, making it a minimal vertex cover. During the repair process, when adding or removing vertices, the degree of exploration and exploitation in the randomized greedy algorithm is adaptively adjusted based on the convergence level of the population. When the population lacks high-quality solutions, the operator strives to generate superior solutions greedily. However, when the solution set has enough high-quality solutions, it explores unexplored choices to break through the limitations of the existing solution set. We compared our GA with a deterministic greedy algorithm, a randomized greedy algorithm, and GAs using various repair operators. Experimental results on benchmark graphs from the Benchmarks with Hidden Optimum Solutions Library (BHOSLIB) demonstrated that the proposed repair operator improved the performance of the GA for the MVC problem.

References

[1]	S. Shyu, P. Y. Yin, B. Lin, An ant colony optimization algorithm for the minimum weight vertex cover problem, Ann. Oper. Res., 131 (2004), 283–304. https://doi.org/10.1023/B:ANOR.0000039523.95673.33 doi: 10.1023/B:ANOR.0000039523.95673.33
[2]	H. Tamura, H. Sugawara, M. Sengoku, S. Shinoda, Multiple cover problem on undirected flow networks, Electron. Comm. JPN. 3, 84 (2001), 67–74. https://doi.org/10.1002/1520-6440(200101)84:1<67::AID-ECJC7>3.0.CO;2-%23 doi: 10.1002/1520-6440(200101)84:1<67::AID-ECJC7>3.0.CO;2-%23
[3]	V. V. Gusev, The vertex cover game: Application to transport networks, Omega, 97 (2020), 102102. https://doi.org/10.1016/j.omega.2019.08.009 doi: 10.1016/j.omega.2019.08.009
[4]	A. Hossain, E. Lopez, S. M. Halper, D. P. Cetnar, A. C. Reis, D. Strickland, et al., Automated design of thousands of nonrepetitive parts for engineering stable genetic systems, Nat. Biotechnol., 38 (2020), 1466–1475. https://doi.org/10.1038/s41587-020-0584-2 doi: 10.1038/s41587-020-0584-2
[5]	A. C. Reis, S. M. Halper, G. E. Vezeau, D. P. Cetnar, A. Hossain, P. R. Clauer, et al., Simultaneous repression of multiple bacterial genes using nonrepetitive extra-long sgrna arrays, Nat. Biotechnol., 37 (2019), 1294–1301. https://doi.org/10.1038/s41587-019-0286-9 doi: 10.1038/s41587-019-0286-9
[6]	M. R. Garey, D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, W. H. Freeman & Co., USA, 1990.
[7]	C. H. Papadimitriou, M. Yannakakis, Optimization, approximation, and complexity classes, J. Comput. Syst. Sci., 43 (1991), 425–440. https://doi.org/10.1016/0022-0000(91)90023-X
[8]	K. Subhash, D. Minzer, M. Safra, Pseudorandom sets in Grassmann graph have near-perfect expansion, in Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science, 2018,592–601. https://doi.org/10.1109/FOCS.2018.00062
[9]	S. Khot, O. Regev, Vertex cover might be hard to approximate to within $2-\epsilon$, J. Comput. Syst. Sci., 74 (2008), 335–349. https://doi.org/10.1016/j.jcss.2007.06.019 doi: 10.1016/j.jcss.2007.06.019
[10]	C. H. Papadimitriou, K. Steiglitz, Combinatorial optimization: Algorithms and complexity, Prentice-Hall, Inc., USA, 1982.
[11]	W. Gao, T. Friedrich, F. Neumann, C. Hercher, Randomized greedy algorithms for covering problems, in Proceedings of the Genetic and Evolutionary Computation Conference, 2018,309–315. https://doi.org/10.1145/3205455.3205542
[12]	S. Bouamama, C. Blum, A. Boukerram, A population-based iterated greedy algorithm for the minimum weight vertex cover problem, Appl. Soft Comput., 12 (2012), 1632–1639. https://doi.org/10.1016/j.asoc.2012.02.013 doi: 10.1016/j.asoc.2012.02.013
[13]	S. Cai, J. Lin, C. Luo, Finding a small vertex cover in massive sparse graphs: Construct, local search, and preprocess, J. Artif. Intell. Res., 59 (2017), 463–494. https://doi.org/10.1613/jair.5443 doi: 10.1613/jair.5443
[14]	R. Jovanovic, A. P. Sanfilippo, S. Voß, Fixed set search applied to the multi-objective minimum weighted vertex cover problem, J. Heuristics, 28 (2022), 481–508. https://doi.org/10.1007/s10732-022-09499-z doi: 10.1007/s10732-022-09499-z
[15]	S. Khuri, T. Bäck, An evolutionary heuristic for the minimum vertex cover problem, in Genetic Algorithms within the Framework of Evolutionary Computation–Proc. of the KI-94 Workshop, Saarbrücken, Germany, 1994, 86–90.
[16]	A. Karci, A. Arslan, Bidirectional evolutionary heuristic for the minimum vertex-cover problem, Comput. Electr. Eng., 29 (2003), 111–120. https://doi.org/10.1016/S0045-7906(01)00018-0 doi: 10.1016/S0045-7906(01)00018-0
[17]	A. Singh, A. K. Gupta, A hybrid heuristic for the minimum weight vertex cover problem, Asia Pac. J. Oper. Res., 23 (2006), 273–285. https://doi.org/10.1142/S0217595906000905 doi: 10.1142/S0217595906000905
[18]	B. Nagy, P. Szokol, A genetic algorithm for the minimum vertex cover problem with interval-valued fitness, Acta Polytech. Hung., 18 (2021), 105–123. https://doi.org/10.12700/APH.18.4.2021.4.6 doi: 10.12700/APH.18.4.2021.4.6
[19]	J. H. Holland, Genetic algorithms, Sci. Am., 267 (1992), 66–73.
[20]	P. O. Lewis, A genetic algorithm for maximum-likelihood phylogeny inference using nucleotide sequence data, Mol. Biol. Evol., 15 (1998), 277–283. https://doi.org/10.1093/oxfordjournals.molbev.a025924. doi: 10.1093/oxfordjournals.molbev.a025924
[21]	S. L. K. Pond, D. Posada, M. B. Gravenor, C. H. Woelk, S. D. Frost, Automated phylogenetic detection of recombination using a genetic algorithm, Mol. Biol. Evol., 23 (2006), 1891–1901. https://doi.org/10.1093/molbev/msl051 doi: 10.1093/molbev/msl051
[22]	B. Chowdhury, G. Garai, A review on multiple sequence alignment from the perspective of genetic algorithm, Genomics, 109 (2017), 419–431. https://doi.org/10.1016/j.ygeno.2017.06.007 doi: 10.1016/j.ygeno.2017.06.007
[23]	L. Bateni, F. Asghari, Bankruptcy prediction using logit and genetic algorithm models: A comparative analysis, Comput. Econ., 55 (2020), 335–348. https://doi.org/10.1007/s10614-016-9590-3 doi: 10.1007/s10614-016-9590-3
[24]	C. B. Kalayci, O. Polat, M. A. Akbay, An efficient hybrid metaheuristic algorithm for cardinality constrained portfolio optimization, Swarm Evol. Comput., 54 (2020), 100662. https://doi.org/10.1016/j.swevo.2020.100662 doi: 10.1016/j.swevo.2020.100662
[25]	S.-H. Moon, Y. Yoon, Genetic mean reversion strategy for online portfolio selection with transaction costs, Mathematics, 10 (2022), 1073. https://doi.org/10.3390/math10071073 doi: 10.3390/math10071073
[26]	C. R. Reeves, A genetic algorithm for flowshop sequencing, Comput. Oper. Res., 22 (1995), 5–13. https://doi.org/10.1016/0305-0548(93)E0014-K doi: 10.1016/0305-0548(93)E0014-K
[27]	Y. Yoon, Y. H. Kim, B. R. Moon, A theoretical and empirical investigation on the Lagrangian capacities of the 0-1 multidimensional knapsack problem, Eur. J. Oper. Res., 218 (2012), 366–376. https://doi.org/10.1016/j.ejor.2011.11.011 doi: 10.1016/j.ejor.2011.11.011
[28]	D. Orvosh, L. Davis, Using a genetic algorithm to optimize problems with feasibility constraints, in Proceedings of the First IEEE Conference on Evolutionary Computation (CEC), vol. 2, 1994,548–553. https://doi.org/10.1109/ICEC.1994.350001
[29]	S. Salcedo-Sanz, A survey of repair methods used as constraint handling techniques in evolutionary algorithms, Comput. Sci. Rev., 3 (2009), 175–192. https://doi.org/10.1016/j.cosrev.2009.07.001 doi: 10.1016/j.cosrev.2009.07.001
[30]	F. Samanipour, J. Jelovica, Adaptive repair method for constraint handling in multi-objective genetic algorithm based on relationship between constraints and variables, Appl. Soft Comput., 90 (2020), 106143. https://doi.org/10.1016/j.asoc.2020.106143 doi: 10.1016/j.asoc.2020.106143
[31]	C. Quan, P. Guo, A local search method based on edge age strategy for minimum vertex cover problem in massive graphs, Expert Syst. Appl., 182 (2021), 115185. https://doi.org/10.1016/j.eswa.2021.115185 doi: 10.1016/j.eswa.2021.115185
[32]	Y. Zhang, S. Wang, C. Liu, E. Zhu, TIVC: An efficient local search algorithm for minimum vertex cover in large graphs, Sensors, 23 (2023), 7831. https://doi.org/10.3390/s23187831 doi: 10.3390/s23187831
[33]	R. Rossi, N. Ahmed, The network data repository with interactive graph analytics and visualization, in Proceedings of the AAAI conference on artificial intelligence, 29 (2015). https://doi.org/10.1609/aaai.v29i1.9277
[34]	A. Eiben, C. Schippers, On evolutionary exploration and exploitation, Fundam. Inform., 35 (1998), 35–50.
[35]	H. G. Beyer, On the "explorative power" of ES/EP-like algorithms, in Evolutionary Programming Ⅶ (eds. V. W. Porto, N. Saravanan, D. Waagen and A. E. Eiben), Springer Berlin Heidelberg, Berlin, Heidelberg, 1998,323–334. https://doi.org/10.1007/BFb0040785
[36]	B. L. Miller, D. E. Goldberg, Genetic algorithms, tournament selection, and the effects of noise, Complex Syst., 9 (1995), 193–212.
[37]	T. Bui, B. Moon, A new genetic approach for the traveling salesman problem, in Proceedings of the First IEEE Conference on Evolutionary Computation. (CEC), 1 (1994), 7–12. https://doi.org/10.1109/ICEC.1994.350051
[38]	M. Buzdalov, The (1+($\lambda$, $\lambda$)) genetic algorithm on the vertex cover problem: Crossover helps leaving plateaus, in Proceedings of the 2022 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2022, 1–10. https://doi.org/10.1109/CEC55065.2022.9870224

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)