On the Runtime Analysis of Stochastic Ageing Mechanisms

Ageing operators are applied in the field of artificial immune systems (AIS) to increase the diversity of the population during the optimization process. Previous theoretical analyses have shown how static ageing operators can successfully escape local optima by implicitly performing a restart of the algorithm. However, showing naturally that ageing in an AIS is more effective than a conceptually simpler restart strategy has proved to be a hard task. We present a rigorous analysis of stochastic ageing mechanisms and show that superior performance compared to just simple restarts can be achieved. Since standard stochastic pure ageing is only effective for small population sizes, we present a hybrid pure ageing operator that achieves the same performance independent of the population size. For a benchmark function used in dynamic optimisation we rigorously prove that hybrid pure ageing allows to escape local optima beyond restarts while static pure ageing is inefficient. The results also apply to the non-dynamic setting. An analytical general framework for the analysis of standard stochastic pure ageing is presented along the way.