Takeover Time Curves in Random and Small-World Structured Populations

We present discrete stochastic mathematical models for the growth curves of synchronous and asynchronous evolutionary algorithms with populations structured according to a random graph. We show that, to a good approximation, randomly structured and panmictic populations have the same growth behavior. Furthermore, we show that global selection intensity depends on the update policy. The validity of the models is confirmed by a comparison with experimental results of simulations. We also present experimental results on small-world and scale-free population graph topologies. We show that they lead to qualitatively similar results. However, the different nature of the nodes can be exploited to obtain a more varied evolutionary behavior.