Back to Search
Start Over
A General Dichotomy of Evolutionary Algorithms on Monotone Functions.
- Source :
- IEEE Transactions on Evolutionary Computation; Dec2020, Vol. 24 Issue 6, p995-1009, 15p
- Publication Year :
- 2020
-
Abstract
- It is known that the (1 + 1)-EA with mutation rate $c/n$ optimizes 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 the $(1 + \lambda)$ -EA, $(\mu + 1)$ -EA, $(\mu + 1)$ -GA, their “fast” counterparts, and for the $(1 + (\lambda,\lambda))$ -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 + (\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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 1089778X
- Volume :
- 24
- Issue :
- 6
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Evolutionary Computation
- Publication Type :
- Academic Journal
- Accession number :
- 147400882
- Full Text :
- https://doi.org/10.1109/TEVC.2019.2917014