A General Dichotomy of Evolutionary Algorithms on Monotone Functions
Johannes Lengler · Lecture notes in computer science · 2018
It is known that the $$(1 + 1)$$ -EA with mutation rate c/n optimises every monotone function efficiently if $$c c_0 = 2.13692..$$ . We study the same question for a large variety of algorithms, particularly for $$(1 + \lambda )$$ -EA, $$(\mu + 1)$$ -EA, $$(\mu + 1)$$ -GA, their fast counterparts like fast $$(1 + 1)$$ -EA, and for $$(1 + (\lambda ,\lambda ))$$ -GA. We prove that all considered mutation-based algorithms show a similar dichotomy for HotTopic functions, or even for all monotone functions. For the $$(1 + (\lambda ,\lambda ))$$ -GA, this dichotomy is in the parameter $$c\gamma $$ , 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 $$\mu $$ nor by the offspring population size $$\lambda $$ . The picture changes completely if crossover is allowed. The genetic algorithms $$(\mu + 1)$$ -GA and $$(\mu + 1)$$ -fGA are efficient for arbitrary mutations strengths if $$\mu $$ is large enough.