The $(1+(\lambda,\lambda))$ Genetic Algorithm on the Vertex Cover Problem: Crossover Helps Leaving Plateaus
Maxim Buzdalov · 2022 IEEE Congress on Evolutionary Computation (CEC) · 2022
Many discrete optimization problems feature plateaus, which are hard to evolutionary algorithms due to the lack of fitness guidance. While higher mutation rates may assist in making a jump from the plateau to some better search point, an algorithm typically performs random walks on a plateau, possibly with some assistance from diversity mechanisms. The vertex cover problem is one of the important NP-hard problems. We found that the recently proposed$(1+(\lambda, \lambda))$genetic algorithm solves certain instances of this problem, including those that are hard to heuristic solvers, much faster than simpler mutation-only evolutionary algorithms. Our theoretical analysis shows that there exists an intricate interplay between the problem structure and the way crossovers are used. It results in a drift towards the points where finding the next improvement is much easier. While this condition is formally proven only on one class of instances and for a subset of search points, experiments show that it is responsible for performance improvements in a much larger range of cases.