### Abstract

In the theory community of evolutionary computation, linear pseudo-boolean functions are often regarded as easy problems since all of them can be optimized in expected time O(n log n) by simple unbiased algorithms. However, results from genetic algorithms and estimation-of-distribution algorithms indicate that these algorithms treat different linear functions differently. More precisely, an effect called "domino convergence" is described in the literature, which means that bits of large weight in the linear function are optimized earlier than bits of low weight. Hence, different linear functions may lead to rather different expected optimization times. The present paper conducts a study of domino convergence. By rigorous runtime analyses, it is shown that domino convergence is mostly a consequence of the crossover underlying genetic algorithms and EDAs. Here a performance gap of order Ω(n/log n) between different linear functions is proved. In simple mutation-only EAs the effect of domino convergence is much less pronounced, with the typical performance gap being logarithmic in the population size. The effect disappears when population size 1 is used and the algorithm is reduced to hillclimbing. Different selection mechanisms, including cut and tournament selection are investigated and their impact on domino convergence is analyzed.

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

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

Publisher | Association for Computing Machinery |

Publication date | 2018 |

Pages | 1539-1546 |

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

DOIs | |

Publication status | Published - 2018 |

Event | 2018 Genetic and Evolutionary Computation Conference - Kyoto Terrsa, Kyoto, Japan Duration: 15 Jul 2018 → 19 Jul 2018 |

### Conference

Conference | 2018 Genetic and Evolutionary Computation Conference |
---|---|

Location | Kyoto Terrsa |

Country | Japan |

City | Kyoto |

Period | 15/07/2018 → 19/07/2018 |

### Keywords

- Theory
- Genetic algorithms
- Estimation of distribution algorithms
- Run-time analysis

## Cite this

Witt, C. (2018). Domino convergence: Why one should hill-climb on linear functions. In

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