caa a22 4500 605469660 CHVBK 20210128100323.0 cr unu---uuuuu 210128e20151001xx s 000 0 eng 10.1007/s00500-015-1672-y doi (NATIONALLICENCE)springer-10.1007/s00500-015-1672-y On the statistical distribution of the expected run-time in population-based search algorithms [Elektronische Daten] [David Barrero, Pablo Muñoz, David Camacho, María R-Moreno] 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. Springer-Verlag Berlin Heidelberg, 2015 RTD nationallicence Run-time analysis nationallicence RTD analysis nationallicence Statistical models nationallicence Barrero David Departamento de Automática, Universidad de Alcalá, Alcalá de Henares, Spain aut Muñoz Pablo Departamento de Automática, Universidad de Alcalá, Alcalá de Henares, Spain aut Camacho David Departamento de Informática, Universidad Autonónoma de Madrid, Madrid, Spain aut R-Moreno María Departamento de Automática, Universidad de Alcalá, Alcalá de Henares, Spain aut Soft Computing Springer Berlin Heidelberg 19/10(2015-10-01), 2717-2734 1432-7643 19:10<2717 2015 19 500 https://doi.org/10.1007/s00500-015-1672-y text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s00500-015-1672-y text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Barrero David Departamento de Automática, Universidad de Alcalá, Alcalá de Henares, Spain aut NATIONALLICENCE 700 1- Muñoz Pablo Departamento de Automática, Universidad de Alcalá, Alcalá de Henares, Spain aut NATIONALLICENCE 700 1- Camacho David Departamento de Informática, Universidad Autonónoma de Madrid, Madrid, Spain aut NATIONALLICENCE 700 1- R-Moreno María Departamento de Automática, Universidad de Alcalá, Alcalá de Henares, Spain aut NATIONALLICENCE 773 0- Soft Computing Springer Berlin Heidelberg 19/10(2015-10-01), 2717-2734 1432-7643 19:10<2717 2015 19 500