iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s00500-015-1672-y
On the statistical distribution of the expected run-time in population-based search algorithms | Soft Computing Skip to main content

Advertisement

Springer Nature Link
Log in

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

  • Foundations
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. ECJ Evolutionary Computation System, http://cs.gmu.edu/~eclab/projects/ecj/.

  2. All the code, configuration files, scripts and datasets needed to reproduce the experiments reported in this paper can be downloaded from https://atc1.aut.uah.es/~david/soco2015.

References

  • Barr R, Golden B, Kelly J, Resende M, Stewart W (1995) Designing and reporting on computational experiments with heuristic methods. J Heuristics 1:9–32

    Article  MATH  Google Scholar 

  • Barrero DF, Camacho D, R-Moreno MD (2010) Confidence intervals of success rates in evolutionary computation. In: Proceedings of the 12th annual conference on genetic and evolutionary computation, GECCO ’10, pp 975–976. ACM, Portland. doi:10.1145/1830483.1830657

  • Barrero DF, Castaño B, R-Moreno MD, Camacho D (2011) Statistical distribution of generation-to-success in GP: application to model accumulated success probability. In: Silva S, Foster JA, Nicolau M, Giacobini M, Machado P (eds) Proceedings of the 14th European conference on genetic programming, EuroGP 2011. LNCS, vol 6621, pp 155–166. Springer, Turin (2011)

  • Chiarandini M, Stützle T (2002) Experimental evaluation of course timetabling algorithms. In: Technical report AIDA-02-05, Intellectics Group, Computer Science Department, Darmstadt University of Technology, Darmstadt

  • Eiben AE, Smith JE (2009) Introduction to evolutionary computing. Chapter: Working with evolutionary algorithms, pp 241–258. Springer, New York

  • Epstein S, Yun X (2010) From unsolvable to solvable: an exploration of simple changes. In: Workshops at the 24th AAAI conference on artificial intelligence

  • Feo T, Resende M, Smith S (1994) A greedy randomized adaptive search procedure for maximum independent set. Oper Res 860–878

  • Frost D, Rish I, Vila L (1997) Summarizing CSP hardness with continuous probability distributions. In: Proceedings of the 14th national conference on artificial intelligence and 9th conference on innovative applications of artificial intelligence, AAAI conference on artificial intelligence, pp 327–333. AAAI Press, New York

  • Gagliolo M, Legrand C (2010) Experimental methods for the analysis of optimization algorithms. Chapter: Algorithm survival analysis, pp 161–184. Springer, New York

  • Hoos H, Stützle T (1998) Characterizing the run-time behavior of stochastic local search. In: Proceedings of the AAAI conference on artificial intelligence

  • Hoos H, Stützle T (1998) Evaluating Las Vegas algorithms—pitfalls and remedies. In: Proceedings of the 14th conference on uncertainty in artificial intelligence (UAI-98), pp 238–245. Morgan Kaufmann, Madison

  • Hoos H, Stützle T (1999) Towards a characterisation of the behaviour of stochastic local search algorithms for SAT. Artif Intell 112(1–2):213–232

    Article  MATH  Google Scholar 

  • Hoos H, Stützle T (2000) Local search algorithms for SAT: an empirical evaluation. J Autom Reason 24(4):421–481

    Article  MATH  Google Scholar 

  • Koza J (1992) Genetic programming: on the programming of computers by means of natural selection. MIT Press, Cambrige

    MATH  Google Scholar 

  • Koza JR (1994) Genetic programming II: automatic discovery of reusable programs. MIT Press, Cambridge

    MATH  Google Scholar 

  • Limpert E, Stahel WA, Abbt M (2001) Log-normal distributions across the sciences: keys and clues. BioScience 51(5):341–352

    Article  Google Scholar 

  • Luke S (2001) When short runs beat long runs. In: Proceedings of the genetic and evolutionary computation conference, pp 74–80. Morgan Kaufmann, San Francisco

  • McDermott J, De Jong K, OReilly UM, White DR, Luke S, Manzoni L, Castelli M, Vanneschi L, Jaskowski W, Krawiec K et al. (2012) Genetic programming needs better benchmarks, p 791. ACM Press, Philadelphia. http://dl.acm.org/citation.cfm?id=2330163.2330273

  • Paterson N, Livesey M (2000) Performance comparison in genetic programming. In: Late breaking papers at the 2000 genetic and evolutionary computation conference, Las Vegas, pp 253–260

  • Ribeiro CC, Rosseti I, Vallejos R (2009) On the use of run time distributions to evaluate and compare stochastic local search algorithms. In: Proceedings of the second international workshop on engineering stochastic local search algorithms., designing, implementing and analyzing effective heuristics, SLS ’09, pp 16–30. Springer, Berlin

  • Stützle T, Hoos H (1999) Analyzing the run-time behaviour of iterated local search for the TSP. In: III Metaheuristics international conference. Kluwer Academic, Angra dos Reis

  • Wilson EB (1927) Probable inference, the law of succession, and statistical inference. J Am Stat Assoc 22:309–316

    Google Scholar 

Download references

Acknowledgments

We would like to thank the comments and suggestions received during the EuroGP 2011 presentation of the early results of this work. This work was supported by the Project of Castilla-La Mancha PEII-2014-015A (PEII11-0079-8929).

Author information

Authors and Affiliations

  1. Departamento de Automática, Universidad de Alcalá, Alcalá de Henares, Spain

    David F. Barrero, Pablo Muñoz & María D. R-Moreno

  2. Departamento de Informática, Universidad Autonónoma de Madrid, Madrid, Spain

    David Camacho

Authors
  1. David F. Barrero
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pablo Muñoz
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. David Camacho
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. María D. R-Moreno
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to David Camacho.

Additional information

Communicated by A. Di Nola.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Barrero, D.F., Muñoz, P., Camacho, D. et al. On the statistical distribution of the expected run-time in population-based search algorithms. Soft Comput 19, 2717–2734 (2015). https://doi.org/10.1007/s00500-015-1672-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-015-1672-y

Keywords

Search

Navigation