[Submitted on 15 Apr 2020]

Download PDF

Abstract: One of the key difficulties in using estimation-of-distribution algorithms is
choosing the population sizes appropriately: Too small values lead to genetic
drift, which can cause enormous difficulties. In the regime with no genetic
drift, however, often the runtime is roughly proportional to the population
size, which renders large population sizes inefficient.

Based on a recent quantitative analysis which population sizes lead to
genetic drift, we propose a parameter-less version of the compact genetic
algorithm that automatically finds a suitable population size without spending
too much time in situations unfavorable due to genetic drift.

We prove an easy mathematical runtime guarantee for this algorithm and
conduct an extensive experimental analysis on four classic benchmark problems.
The former shows that under a natural assumption, our algorithm has a
performance similar to the one obtainable from the best population size. The
latter confirms that missing the right population size can be highly
detrimental and shows that our algorithm as well as a previously proposed
parameter-less one based on parallel runs avoids such pitfalls. Comparing the
two approaches, ours profits from its ability to abort runs which are likely to
be stuck in a genetic drift situation.