On the statistical distribution of the expected run-time in population-based search algorithms

Run-time analysis is a method that characterizes the run-time behaviour of an algorithm. It has been successfully used to analyse metaheuristics and stochastic local search algorithms. Some studies on genetic programming and related stochastic search algorithms suggested the existence of a rationale behind the run-time behaviour which could be exploited to better understand the algorithm looking at its run-time response. Under that hypothesis, this paper presents empirical evidence suggesting common statistical properties in the run-time of several types of population-based search algorithms, including genetic algorithms, genetic programming, grammatical evolution, differential evolution or particle swarm optimization. In this analysis, only the run-time of runs that were able to find a solution are considered; unsuccessful runs are not included in the analysis. The run-time to find a solution, measured by the number of evaluations, of some well-known evolutionary algorithms is empirically obtained, finding that it usually can be approximated using a lognormal distribution, with the exception of some difficult problems, which are better approximated by an exponential. We also show that the algorithm parameter settings might influence the yielding run-time statistical distribution; in particular, when there is no selective pressure, the run-time, measured as the number of evaluations to find a solution, follows a Weibull distribution instead of a lognormal one. Finally, we outline a framework using a simple theoretical discrete-time model, showing that the geometrically distributed run-time is a consequence of the lack of memory in the algorithm.