### Abstract

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.

Original language | English |
---|---|

Title of host publication | 2018 Proceedings of the Genetic and Evolutionary Computation Conference |

Publisher | Association for Computing Machinery |

Publication date | 2018 |

Pages | 1499-1506 |

ISBN (Print) | 978-1-4503-5618-3 |

DOIs | |

Publication status | Published - 2018 |

### Keywords

- Estimation-of-distribution algorithms
- Evolutionary algorithms
- Running time analysis
- Theory
- Compact genetic algorithm (cga)

## Cite this

Lengler, J., Sudholt, D., & Witt, C. (2018). Medium step sizes are harmful for the compact genetic algorithm. In

*2018 Proceedings of the Genetic and Evolutionary Computation Conference*(pp. 1499-1506). Association for Computing Machinery. https://doi.org/10.1145/3205455.3205576