Runtime Analysis of the $(1+(\lambda ,\lambda ))$ Genetic Algorithm on Random Satisfiable 3-CNF Formulas

Abstract

The $(1+(\lambda ,\lambda ))$ genetic algorithm, first proposed at GECCO 2013, showed a surprisingly good performance on so me 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. We prove that this GA with fixed not too large population size again obtains runtimes better than $\Theta (n\log n)$, which is a lower bound for most evolutionary algorithms on pseudo-Boolean problems with unique optimum. However, the self-adjusting version of the GA risks reaching population sizes at which the intermediate selection of the GA, due to the weaker fitness-distance correlation, is not able to distinguish a profitable offspring from others. We show that this problem can be overcome by equipping the self-adjusting GA with an upper limit for the population size. Apart from sparse instances, this limit can be chosen in a way that the asymptotic performance does not worsen compared to the idealistic OneMax case. Overall, this work shows that the $(1+(\lambda ,\lambda ))$ GA can provably have a good performance on combinatorial search and optimization problems also in the presence of a weaker fitness-distance correlation.

An extended abstract of this report will appear in the proceedings of the 2017 Genetic and Evolutionary Computation Conference (GECCO 2017)

Cited by in corpus (14)

• Probabilistic Tools for the Analysis of Randomized Optimization Heuristics
• Theory of Parameter Control for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choices
• The (1+$\lambda$) Evolutionary Algorithm with Self-Adjusting Mutation Rate
• A Survey on Recent Progress in the Theory of Evolutionary Algorithms for Discrete Optimization
• A Rigorous Runtime Analysis of the $(1+(\lambda ,\lambda ))$ GA on Jump Functions
• The $(1+(\lambda ,\lambda ))$ Genetic Algorithm for Permutations
• Hyper-Parameter Tuning for the (1+(λ,λ)) GA
• Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution
• First Steps Towards a Runtime Analysis When Starting With a Good Solution
• The $(1+(\lambda ,\lambda ))$ Global SEMO Algorithm
• The 1/5-th Rule with Rollbacks: On Self-Adjustment of the Population Size in the $(1+(\lambda ,\lambda ))$ GA
• Improving Time and Memory Efficiency of Genetic Algorithms by Storing Populations as Minimum Spanning Trees of Patches
• Better Fixed-Arity Unbiased Black-Box Algorithms
• Multi-parameter Control for the $(1+(\lambda ,\lambda ))$-GA on OneMax via Deep Reinforcement Learning