Quasirandom evolutionary algorithms

Motivated by recent successful applications of the concept of quasirandomness, we investigate to what extent such ideas can be used in evolutionary computation. To this aim, we propose different variations of the classical (1+1) evolutionary algorithm, all imitating the property that the (1+1) EA over intervals of time touches all bits roughly the same number of times.

We prove bounds on the optimization time of these algorithms for the simple OneMax function. Surprisingly, none of the algorithms achieves the seemingly obvious reduction of the runtime from Θ(n log n) to O(n). On the contrary, one may even need Ω(n2) time. However, we also find that quasirandom ideas, if implemented correctly, can yield an over 50% speed-up.