TY - GEN

T1 - The (1+(λ,λ)) Genetic Algorithm on the Vertex Cover Problem

T2 - 2022 IEEE Congress on Evolutionary Computation, CEC 2022

AU - Buzdalov, Maxim

N1 - Publisher Copyright:
© 2022 IEEE.

PY - 2022/7/18

Y1 - 2022/7/18

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85138700434&partnerID=8YFLogxK

U2 - 10.1109/CEC55065.2022.9870224

DO - 10.1109/CEC55065.2022.9870224

M3 - Conference Proceeding (Non-Journal item)

AN - SCOPUS:85138700434

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

BT - Proceedings of IEEE Congress on Evolutionary Computation

PB - IEEE Press

Y2 - 18 July 2022 through 23 July 2022

ER -