Robustness of Populations in Stochastic Environments

We consider stochastic versions of OneMax and Leading-Ones and analyze the performance of evolutionary algorithms with and without populations on these problems. It is known that the (1+1) EA on OneMax performs well in the presence of very small noise, but poorly for higher noise levels. We extend these results to LeadingOnes and to many different noise models, showing how the application of drift theory can significantly simplify and generalize previous analyses.

Most surprisingly, even small populations (of size _(log n)) can make evolutionary algorithms perform well for high noise levels, well outside the abilities of the (1+1) EA! Larger population sizes are even more beneficial; we consider both parent and o_spring populations. In this sense, populations are robust in these stochastic settings.