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

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.