A General Dichotomy of Evolutionary Algorithms on Monotone Functions

It is known that the evolutionary algorithm $(1+1)$-EA with mutation rate $c/n$ optimises every monotone function efficiently if $c<1$, and needs exponential time on some monotone functions (HotTopic functions) if $c\geq 2.2$. We study the same question for a large variety of algorithms, particularly for $(1+λ)$-EA, $(μ+1)$-EA, $(μ+1)$-GA, their fast counterparts like fast $(1+1)$-EA, and for $(1+(λ,λ))$-GA. We find that all considered mutation-based algorithms show a similar dichotomy for HotTopic functions, or even for all monotone functions. For the $(1+(λ,λ))$-GA, this dichotomy is in the parameter $cγ$, 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 $m_2/m_1$, where $m_1$ and $m_2$ 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 $μ$ nor by the offspring population size $λ$. The picture changes completely if crossover is allowed. The genetic algorithms $(μ+1)$-GA and fast $(μ+1)$-GA are efficient for arbitrary mutations strengths if $μ$ is large enough.