Runtime analysis of the (1 + ( λ, λ )) genetic algorithm on random satisfiable 3-CNF formulas
Maxim Buzdalov, Benjamin Doerr · Proceedings of the Genetic and Evolutionary Computation Conference · 2017
The (1 + (λ, λ)) genetic algorithm, first proposed at GECCO 2013, showed a surprisingly good performance on some optimization problems. The theoretical analysis so far was restricted to the OneMax test function, where this GA profited from the perfect fitness-distance correlation. In this work, we conduct a rigorous runtime analysis of this GA on random 3-SAT instances in the planted solution model having at least logarithmic average degree, which are known to have a weaker fitness distance correlation.