Evolutionary Algorithms with Self-adjusting Asymmetric Mutation

Abstract

Evolutionary Algorithms (EAs) and other randomized search heuristics are often considered as unbiased algorithms that are invariant with respect to different transformations of the underlying search space. However, if a certain amount of domain knowledge is available the use of biased search operators in EAs becomes viable. We consider a simple (1+1) EA for binary search spaces and analyze an asymmetric mutation operator that can treat zero- and one-bits differently. This operator extends previous work by Jansen and Sudholt (ECJ 18(1), 2010) by allowing the operator asymmetry to vary according to the success rate of the algorithm. Using a self-adjusting scheme that learns an appropriate degree of asymmetry, we show improved runtime results on the class of functions OneMax${}_a$ describing the number of matching bits with a fixed target $a\in \{0,1{\}}^n$.

arXiv comment16 pages. An extended abstract of this paper will be published in the proceedings of PPSN 2020

References in corpus (5)

• 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
• Self-Adjusting Evolutionary Algorithms for Multimodal Optimization
• Towards a Theory-Guided Benchmarking Suite for Discrete Black-Box Optimization Heuristics: Profiling $(1+\lambda )$ EA Variants on OneMax and LeadingOnes
• Offspring Population Size Matters when Comparing Evolutionary Algorithms with Self-Adjusting Mutation Rates