Skip to main content
main-content

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

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

share
TEILEN

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.
Literatur
1.
Zurück zum Zitat Auger A, Doerr B (eds) (2011) Theory of randomized search heuristics. World scientific Auger A, Doerr B (eds) (2011) Theory of randomized search heuristics. World scientific
2.
Zurück zum Zitat 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 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.
Zurück zum Zitat Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms. MIT Press, London Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms. MIT Press, London
5.
Zurück zum Zitat 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 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
7.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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
11.
Zurück zum Zitat Doerr B, Winzen C (2014) Reducing the arity in unbiased black-box complexity. Theor Comput Sci 545:108–121 Doerr B, Winzen C (2014) Reducing the arity in unbiased black-box complexity. Theor Comput Sci 545:108–121
12.
Zurück zum Zitat Doerr B, Johannsen D, Winzen C (2010) Drift analysis and linear functions revisited. In: IEEE congress on evolutionary computation (CEC’10), pp 1967–1974 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.
Zurück zum Zitat Droste S, Jansen T, Wegener I (2002) On the analysis of the (1+1) evolutionary algorithm. Theor Comput Sci 276:51–81 Droste S, Jansen T, Wegener I (2002) On the analysis of the (1+1) evolutionary algorithm. Theor Comput Sci 276:51–81
14.
Zurück zum Zitat Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading Goldberg DE (1989) Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading
15.
Zurück zum Zitat He J, Yao X (2001) Drift analysis and average time complexity of evolutionary algorithms. Artif Intell 127(1):57–85 He J, Yao X (2001) Drift analysis and average time complexity of evolutionary algorithms. Artif Intell 127(1):57–85
16.
Zurück zum Zitat Holland J (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor Holland J (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor
17.
Zurück zum Zitat Jansen T (2013) Analyzing evolutionary algorithms. The computer science perspective. Springer, Berlin/Heidelberg Jansen T (2013) Analyzing evolutionary algorithms. The computer science perspective. Springer, Berlin/Heidelberg
18.
Zurück zum Zitat 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 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.
Zurück zum Zitat Jansen T, Zarges C (2014) Reevaluating immune-inspired hypermutations using the fixed budget perspective. IEEE Trans Evol Comput 18(5):674–688 Jansen T, Zarges C (2014) Reevaluating immune-inspired hypermutations using the fixed budget perspective. IEEE Trans Evol Comput 18(5):674–688
20.
Zurück zum Zitat 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 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.
Zurück zum Zitat Johannsen D (2012) Random combinatorial structures and randomized search heuristics. PhD thesis, Univesity of Saarland Johannsen D (2012) Random combinatorial structures and randomized search heuristics. PhD thesis, Univesity of Saarland
22.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Lehre PK, Witt C (2012) Black-box search by unbiased variation. Algorithmica 64(4): 623–642 Lehre PK, Witt C (2012) Black-box search by unbiased variation. Algorithmica 64(4): 623–642
25.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Lyapunov AM (1892) The general problem of the stability if motion (in Russian). Doctoral dissertation, University of Kharkov, Kharkov Mathematical Society, 250 p Lyapunov AM (1892) The general problem of the stability if motion (in Russian). Doctoral dissertation, University of Kharkov, Kharkov Mathematical Society, 250 p
29.
Zurück zum Zitat 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 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.
Zurück zum Zitat Mitzenmacher M, Upfal E (2005) Probability and computing: randomized algorithms and probabilistic analysis. Cambridge University Press, Cambridge Mitzenmacher M, Upfal E (2005) Probability and computing: randomized algorithms and probabilistic analysis. Cambridge University Press, Cambridge
31.
Zurück zum Zitat Motwani R, Raghavan P (1995) Randomized algorithms. Cambridge University Press, Cambridge Motwani R, Raghavan P (1995) Randomized algorithms. Cambridge University Press, Cambridge
32.
Zurück zum Zitat Neumann F, Witt C (2010) Bioinspired computation in combinatorial optimization – algorithms and their computational complexity. Springer, Berlin/Heidelberg Neumann F, Witt C (2010) Bioinspired computation in combinatorial optimization – algorithms and their computational complexity. Springer, Berlin/Heidelberg
33.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Oliveto PS, Witt C (2011) Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica 59(3):369–386 Oliveto PS, Witt C (2011) Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica 59(3):369–386
36.
Zurück zum Zitat Oliveto PS, Witt C (2012) Erratum: simplified drift analysis for proving lower bounds in evolutionary computation. Technical report. arXiv:1211.7184, arXiv preprint Oliveto PS, Witt C (2012) Erratum: simplified drift analysis for proving lower bounds in evolutionary computation. Technical report. arXiv:1211.7184, arXiv preprint
37.
Zurück zum Zitat Oliveto PS, Witt C (2014) On the runtime analysis of the simple genetic algorithm. Theor Comput Sci 545:2–19 Oliveto PS, Witt C (2014) On the runtime analysis of the simple genetic algorithm. Theor Comput Sci 545:2–19
38.
Zurück zum Zitat Oliveto PS, Witt C (2015) Improved time complexity analysis of the simple genetic algorithm. Theor Comput Sci 605:21–41 Oliveto PS, Witt C (2015) Improved time complexity analysis of the simple genetic algorithm. Theor Comput Sci 605:21–41
39.
Zurück zum Zitat 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 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.
Zurück zum Zitat Rudolph G (1998) Finite Markov chain results in evolutionary computation: a tour d’Horizon. Fundamenta Informaticae 35(1):67–89 Rudolph G (1998) Finite Markov chain results in evolutionary computation: a tour d’Horizon. Fundamenta Informaticae 35(1):67–89
41.
Zurück zum Zitat Sasaki GH, Hajek B (1988) The time complexity of maximum matching by simulated annealing. J Assoc Comput Mach 35(2):387–403 Sasaki GH, Hajek B (1988) The time complexity of maximum matching by simulated annealing. J Assoc Comput Mach 35(2):387–403
42.
Zurück zum Zitat 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 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.
Zurück zum Zitat Sudholt D (2015) Parallel evolutionary algorithms. In: Kacprzyk J, Pedrycz W (eds) Handbook of computational intelligence. Springer, Berlin/Heidelberg, pp 929–959 Sudholt D (2015) Parallel evolutionary algorithms. In: Kacprzyk J, Pedrycz W (eds) Handbook of computational intelligence. Springer, Berlin/Heidelberg, pp 929–959
44.
Zurück zum Zitat 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 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.
Zurück zum Zitat Witt C (2006) Runtime analysis of the ( μ+1) ea on simple pseudo-boolean functions. Evol Comput 14(1):65–86 Witt C (2006) Runtime analysis of the ( μ+1) ea on simple pseudo-boolean functions. Evol Comput 14(1):65–86
46.
Zurück zum Zitat 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 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
DOI
https://doi.org/10.1007/978-3-319-07124-4_35

Premium Partner