Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Kongresse
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Veranstaltungskalender Awards MyNewsletter Firmensuche
Kunden Login
Über Einzelzugang informieren
Über Unternehmenszugang informieren
Referenzkunden
Elektrische Antriebe und Energiesysteme 2025 | 26 + 27 März 2025

19. Internationaler MTZ-Fachkongress Zukunftsantriebe

Seien Sie bei der Konferenz dabei! Dort treffen Experten aus der Automobilindustrie, Energieerzeugung und Stromnetzbetrieb auf Vertreter aus Politik und Wissenschaft. Diskutiert werden wichtige Themen der Branche.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

29. Theoretical Analysis of Stochastic Search Algorithms

verfasst von : Per Kristian Lehre, Pietro S. Oliveto

Erschienen in: Handbook of Heuristics

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Theoretical analyses of stochastic search algorithms, albeit few, have always existed since these algorithms became popular. Starting in the 1990s, a systematic approach to analyze the performance of stochastic search heuristics has been put in place. This quickly increasing basis of results allows, nowadays, the analysis of sophisticated algorithms such as population-based evolutionary algorithms, ant colony optimization, and artificial immune systems. Results are available concerning problems from various domains including classical combinatorial and continuous optimization, single and multi-objective optimization, and noisy and dynamic optimization. This chapter introduces the mathematical techniques that are most commonly used in the runtime analysis of stochastic search heuristics in finite, discrete spaces. Careful attention is given to the very popular artificial fitness levels and drift analyses techniques for which several variants are presented. To aid the reader’s comprehension of the presented mathematical methods, these are illustrated by analysis of simple evolutionary algorithms for artificial example functions. The chapter is concluded by providing references to more complex applications and further extensions of the techniques for the obtainment of advanced results.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Parallel Metaheuristic Search
Nächstes Kapitel City Logistics
Literatur
1.
Auger A, Doerr B (eds) (2011) Theory of randomized search heuristics. World scientific
2.
Chen T, He J, Sun G, Chen G, Yao X (2009) A new approach for analyzing average time complexity of population-based evolutionary algorithms on unimodal problems. IEEE Trans Syst Man Cybern B 39(5):1092–1106
3.
Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms. MIT Press, London
4.
5.
Corus D, He J, Jansen T, Oliveto PS, Sudholt D, Zarges C (2017) On easiest functions for mutation operators in bio-inspired optimisation. Algorithmica 78(2):714–740
6.
7.
Corus D, Oliveto PS, Yazdani D (2017) On the runtime analysis of the Opt-IA artificial immune system. In: GECCO’17: proceedings of the 2017 annual conference on Genetic and evolutionary computation, pp 83–90
8.
Dang DC, Lehre PK (2015) Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms. In: Proceedings of the 2015 ACM conference on foundations of genetic algorithms XIII – FOGA’15. ACM Press, New York, pp 62–68
9.
Dang DC, Lehre PK (2015) Simplified runtime analysis of estimation of distribution algorithms. In: Proceedings of the 2015 on genetic and evolutionary computation conference – GECCO’15. ACM, New York, pp 513–518
10.
11.
Doerr B, Winzen C (2014) Reducing the arity in unbiased black-box complexity. Theor Comput Sci 545:108–121
12.
Doerr B, Johannsen D, Winzen C (2010) Drift analysis and linear functions revisited. In: IEEE congress on evolutionary computation (CEC’10), pp 1967–1974
13.
Droste S, Jansen T, Wegener I (2002) On the analysis of the (1+1) evolutionary algorithm. Theor Comput Sci 276:51–81
14.
Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading
15.
He J, Yao X (2001) Drift analysis and average time complexity of evolutionary algorithms. Artif Intell 127(1):57–85
16.
Holland J (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor
17.
Jansen T (2013) Analyzing evolutionary algorithms. The computer science perspective. Springer, Berlin/Heidelberg
18.
Jansen T, Zarges C (2012) Computing longest common subsequences with the b-cell algorithm. In: Coello CAC, Greensmith J, Krasnogor N, Liò P, Nicosia G, Pavone M (eds) Artificial immune systems – proceedings of the 11th international conference, ICARIS 2012, Taormina, 28–31 Aug 2012. Lecture notes in computer science, vol 7597. Springer, pp 111–124
19.
Jansen T, Zarges C (2014) Reevaluating immune-inspired hypermutations using the fixed budget perspective. IEEE Trans Evol Comput 18(5):674–688
20.
Jansen T, Oliveto PS, Zarges C (2011) On the analysis of the immune-inspired b-cell algorithm for the vertex cover problem. In: Liò P, Nicosia G, Stibor T (eds) Artificial immune systems – proceedings of the 10th international conference, ICARIS 2011, Cambridge, 18–21 July 2011. Lecture notes in computer science, vol 6825. Springer, pp 117–131
21.
Johannsen D (2012) Random combinatorial structures and randomized search heuristics. PhD thesis, Univesity of Saarland
22.
Lehre PK (2010) Negative drift in populations. In: Parallel problem solving from nature – PPSN XI, proceedings of the 11th international conference, Kraków, 11–15 Sept 2010, part I, pp 244–253
23.
Lehre PK (2011) Fitness-levels for non-elitist populations. In: Proceedings of the 13th annual conference on Genetic and evolutionary computation – GECCO’11. ACM Press, New York, p 2075
24.
Lehre PK, Witt C (2012) Black-box search by unbiased variation. Algorithmica 64(4): 623–642
25.
Lehre PK, Witt C (2014) Concentrated hitting times of randomized search heuristics with variable drift. In: Ahn H, Shin C (eds) Algorithms and computation – proceedings of the 25th international symposium, ISAAC 2014, Jeonju, 15–17 Dec 2014. Lecture notes in computer science, vol 8889. Springer, pp 686–697
26.
Lissovoi A, Oliveto PS (2018, in press) On the time and space complexity of genetic programming for evolving Boolean conjunctions. In: AAAI-18: proceedings of the thirty-second AAAI conference on artificial intelligence
27.
Lissovoi A, Oliveto PS, Warwicker JA (2017) On the runtime analysis of generalised hyper-heuristics for pseudo-boolean optimisation. In: GECCO’17: proceedings of the 2017 annual conference on genetic and evolutionary computation, pp 849–856
28.
Lyapunov AM (1892) The general problem of the stability if motion (in Russian). Doctoral dissertation, University of Kharkov, Kharkov Mathematical Society, 250 p
29.
Mambrini A, Oliveto PS (2016) On the analysis of simple genetic programming for evolving boolean functions. In: Proceedings of the 2016 European conference on genetic programming – EuroGP’16. Lecture notes in computer science. Springer, pp 99–114
30.
Mitzenmacher M, Upfal E (2005) Probability and computing: randomized algorithms and probabilistic analysis. Cambridge University Press, Cambridge
31.
Motwani R, Raghavan P (1995) Randomized algorithms. Cambridge University Press, Cambridge
32.
Neumann F, Witt C (2010) Bioinspired computation in combinatorial optimization – algorithms and their computational complexity. Springer, Berlin/Heidelberg
33.
Neumann F, O’Reilly UM, Wagner M (2011) Computational complexity analysis of genetic programming – initial results and future directions. In: Riolo R, Vladislavleva E, Moore JH (eds) Genetic programming theory and practice IX. Springer, New York, pp 113–128
34.
Oliveto PS, Sudholt D (2010) On the runtime analysis of stochastic ageing mechanisms. In: GECCO’14: proceedings of the 2014 annual conference on Genetic and evolutionary computation, pp 113–120
35.
Oliveto PS, Witt C (2011) Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica 59(3):369–386
36.
Oliveto PS, Witt C (2012) Erratum: simplified drift analysis for proving lower bounds in evolutionary computation. Technical report. arXiv:1211.7184, arXiv preprint
37.
Oliveto PS, Witt C (2014) On the runtime analysis of the simple genetic algorithm. Theor Comput Sci 545:2–19
38.
Oliveto PS, Witt C (2015) Improved time complexity analysis of the simple genetic algorithm. Theor Comput Sci 605:21–41
39.
Paixao T, Badkobeh G, Barton N, Corus D, Dang DC, Friedrich T, Lehre PK, Sudholt D, Sutton AM, Trubenová B (2015) Toward a unifying framework for evolutionary processes. J Theor Biol 383:28–43
40.
Rudolph G (1998) Finite Markov chain results in evolutionary computation: a tour d’Horizon. Fundamenta Informaticae 35(1):67–89
41.
Sasaki GH, Hajek B (1988) The time complexity of maximum matching by simulated annealing. J Assoc Comput Mach 35(2):387–403
42.
Sudholt D (2010) General lower bounds for the running time of evolutionary algorithms. In: Proceedings of the 11th international conference on parallel problem solving from nature (PPSN XI). Lecture notes in computer science, vol 6238. Springer, pp 124–133
43.
Sudholt D (2015) Parallel evolutionary algorithms. In: Kacprzyk J, Pedrycz W (eds) Handbook of computational intelligence. Springer, Berlin/Heidelberg, pp 929–959
44.
Wegener I (2002) Methods for the analysis of evolutionary algorithms. In: Sarker R, Yao X (eds) Evolutionary optimization. Kluwer Academic, New York, pp 125–141
45.
Witt C (2006) Runtime analysis of the (μ+1) ea on simple pseudo-boolean functions. Evol Comput 14(1):65–86
46.
Witt C (2012) Optimizing linear functions with randomized search heuristics – the robustness of mutation. In: Dürr C, Wilke T (eds) 29th international symposium on theoretical aspects of computer science (STACS 2012). Leibniz international proceedings in informatics (LIPIcs), vol 14, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, pp 420–431
Metadaten
Titel
Theoretical Analysis of Stochastic Search Algorithms
verfasst von
Per Kristian Lehre
Pietro S. Oliveto
Copyright-Jahr
2018
Buch
Handbook of Heuristics

Print ISBN: 978-3-319-07123-7

Electronic ISBN: 978-3-319-07124-4

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-07124-4_35

Premium Partner

    Bildnachweise