A General Dichotomy of Evolutionary Algorithms on Monotone Functions

It is known that the (1 + 1)-EA with mutation rate <inline-formula> <tex-math notation="LaTeX">$c/n$ </tex-math></inline-formula> optimizes every monotone function efficiently if <inline-formula> <tex-math notation="LaTeX">$c < 1$ </tex-math></inline-formula>, and needs exponential time on some monotone functions (HotTopic functions) if <inline-formula> <tex-math notation="LaTeX">$c\geq 2.2$ </tex-math></inline-formula>. We study the same question for a large variety of algorithms, particularly for the <inline-formula> <tex-math notation="LaTeX">$(1 + \lambda)$ </tex-math></inline-formula>-EA, <inline-formula> <tex-math notation="LaTeX">$(\mu + 1)$ </tex-math></inline-formula>-EA, <inline-formula> <tex-math notation="LaTeX">$(\mu + 1)$ </tex-math></inline-formula>-GA, their “fast” counterparts, and for the <inline-formula> <tex-math notation="LaTeX">$(1 + (\lambda,\lambda))$ </tex-math></inline-formula>-GA. We find that all considered mutation-based algorithms show a similar dichotomy for HotTopic functions, or even for all monotone functions. For the <inline-formula> <tex-math notation="LaTeX">$(1 + (\lambda,\lambda))$ </tex-math></inline-formula>-GA, this dichotomy is in the parameter <inline-formula> <tex-math notation="LaTeX">$c\gamma $ </tex-math></inline-formula>, which is the expected number of bit flips in an individual after mutation and crossover, neglecting selection. For the fast algorithms, the dichotomy is in <inline-formula> <tex-math notation="LaTeX">$m_{2}/m_{1}$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$m_{1}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$m_{2}$ </tex-math></inline-formula> are the first and second falling moment of the number of bit flips. Surprisingly, the range of efficient parameters is not affected by either population size <inline-formula> <tex-math notation="LaTeX">$\mu $ </tex-math></inline-formula> nor by the offspring population size <inline-formula> <tex-math notation="LaTeX">$\lambda $ </tex-math></inline-formula>. The picture changes completely if crossover is allowed. The genetic algorithms <inline-formula> <tex-math notation="LaTeX">$(\mu + 1)$ </tex-math></inline-formula>-GA and <inline-formula> <tex-math notation="LaTeX">$(\mu + 1)$ </tex-math></inline-formula>-fGA are efficient for arbitrary mutations strengths if <inline-formula> <tex-math notation="LaTeX">$\mu $ </tex-math></inline-formula> is large enough.

Paper

Similar papers

© 2026 NYSGPT2525 LLC