We study the intricate dynamics of the Compact Genetic Algorithm (cGA) on OneMax, and how its performance depends on the step size 1/K, that determines how quickly decisions about promising bit values are fixed in the probabilistic model. It is known that cGA and UMDA, a related algorithm, run in expected time O(n log n) when the step size is just small enough (K = Θ(n log n)) to avoid wrong decisions being fixed. UMDA also shows the same performance in a very different regime (equivalent to K = Θ(log n) in the cGA) with much larger steps sizes, but for very different reasons: many wrong decisions are fixed initially, but then reverted efficiently. We show that step sizes in between these two optimal regimes are harmful as they yield larger runtimes: we prove a lower bound of Ω(K1/3n+n log n) for the cGA on OneMax for K = O(n/log2 n). For K = Ω(log3 n) the runtime increases with growing K before dropping again to O(Kn + n log n) for K = Ω(n log n). This suggests that the expected runtime for cGA is a bimodal function in K with two very different optimal regions and worse performance in between.
|Title of host publication||2018 Proceedings of the Genetic and Evolutionary Computation Conference|
|Publisher||Association for Computing Machinery|
|Publication status||Published - 2018|
- Estimation-of-distribution algorithms
- Evolutionary algorithms
- Running time analysis
- Compact genetic algorithm (cga)