The (1+(λ,λ)) Genetic Algorithm on the Vertex Cover Problem: Crossover Helps Leaving Plateaus

Maxim Buzdalov*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

1 Citation (SciVal)
55 Downloads (Pure)

Abstract

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+(λ, λ)) 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.

Original languageEnglish
Title of host publicationProceedings of IEEE Congress on Evolutionary Computation
PublisherIEEE Press
ISBN (Electronic)9781665467087
DOIs
Publication statusPublished - 18 Jul 2022
Event2022 IEEE Congress on Evolutionary Computation, CEC 2022 - Padua, Italy
Duration: 18 Jul 202223 Jul 2022

Publication series

Name2022 IEEE Congress on Evolutionary Computation, CEC 2022 - Conference Proceedings

Conference

Conference2022 IEEE Congress on Evolutionary Computation, CEC 2022
Country/TerritoryItaly
CityPadua
Period18 Jul 202223 Jul 2022

Fingerprint

Dive into the research topics of 'The (1+(λ,λ)) Genetic Algorithm on the Vertex Cover Problem: Crossover Helps Leaving Plateaus'. Together they form a unique fingerprint.

Cite this