Abstract
Although widely applied in optimisation, relatively little has been proven rigorously about the role and behaviour of populations in randomised search processes. This paper presents a new method to prove upper bounds on the expected optimisation time of population-based randomised search heuristics that use non-elitist selection mechanisms and unary variation operators. Our results follow from a detailed drift analysis of the population dynamics in these heuristics. This analysis shows that the optimisation time depends on the relationship between the strength of the selective pressure and the degree of variation introduced by the variation operator. Given limited variation, a surprisingly weak selective pressure suffices to optimise many functions in expected polynomial time. We derive upper bounds on the expected optimisation time of non-elitist evolutionary algorithms (EA) using various selection mechanisms, including fitness proportionate selection. We show that EAs using fitness proportionate selection can optimise standard benchmark functions in expected polynomial time given a sufficiently low mutation rate. As a second contribution, we consider an optimisation scenario with partial information, where fitness values of solutions are only partially available. We prove that non-elitist EAs under a set of specific conditions can optimise benchmark functions in expected polynomial time, even when vanishingly little information about the fitness values of individual solutions or populations is available. To our knowledge, this is the first runtime analysis of randomised search heuristics under partial information.
We’re sorry, something doesn't seem to be working properly.
Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.
References
Auger, A., Auger, A., Doerr, B.: Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific Publishing Co., Inc., River Edge (2011)
Chen, T., He, J., Sun, G., Chen, G., Yao, X.: A new approach for analyzing average time complexity of population-based evolutionary algorithms on unimodal problems. IEEE Trans. Syst. Man Cybernet. Part B 39(5), 1092–1106 (2009)
Chiong, R., Weise, T., Michalewicz, Z. (eds.): Variants of Evolutionary Algorithms for Real-World Applications. Springer, Berlin (2012)
Corus, D., Dang, D.-C., Eremeev, A.V., Lehre, P.K.: Level-based analysis of genetic algorithms and other search processes. In: Proceedings of the International Conference on Parallel Problem Solving from Nature, PPSN’14, Ljubljana, Slovenia, pp. 912–921. Springer International Publishing, Berlin (2014)
Dang, D.-C., Lehre, P.K.: Evolution under partial information. In: Proceedings of the Annual Conference on Genetic and Evolutionary Computation, GECCO’14, pp. 1359–1366 (2014)
Dang, D.-C., Lehre, P.K.: Refined upper bounds on the expected runtime of non-elitist populations from fitness-levels. In: Proceedings of the Annual Conference on Genetic and Evolutionary Computation, GECCO’14, pp. 1367–1374. ACM, New York (2014)
Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64(4), 673–697 (2012)
Droste, S.: Analysis of the (1+1) EA for a dynamically bitwise changing OneMax. In: Proceedings of the 2003 International Conference on Genetic and Evolutionary Computation, GECCO’03, pp 909–921. Springer, Berlin (2003)
Droste, S.: Analysis of the (1+1) EA for a noisy OneMax. In: Proceedings of the 2004 International Conference on Genetic and Evolutionary Computation, GECCO’04, pp. 1088–1099. Springer, Berlin (2004)
Dubhashi, D., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, New York (2009)
Gießen, C., Kötzing, T.: Robustness of populations in stochastic environments. In: Proceedings of the Annual Conference on Genetic and Evolutionary Computation, GECCO’14, pp. 1383–1390. ACM, New York (2014)
Goldberg, D.E., Deb, K.: A comparative analysis of selection schemes used in genetic algorithms. In: Proceedings of Foundations of Genetic Algorithms, FOGA I, pp. 69–93. Morgan Kaufmann (1991)
Hajek, B.: Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probab. 14(3), 502–525 (1982)
Happ, E., Johannsen, D., Klein, C., Neumann, F.: Rigorous analyses of fitness-proportional selection for optimizing linear functions. In: Proceedings of the Annual Conference on Genetic and Evolutionary Computation, GECCO’08, pp. 953–960 (2008)
He, J., Yao, X.: Drift analysis and average time complexity of evolutionary algorithms. Artif. Intell. 127(1), 57–85 (2001)
He, J., Yao, X.: From an individual to a population: an analysis of the first hitting time of population-based evolutionary algorithms. IEEE Trans. Evol. Comput. 6(5), 495–511 (2002)
Jansen, T.: Analyzing Evolutionary Algorithms—The Computer Science Perspective. Natural Computing Series. Springer, Berlin (2013)
Jin, Y.: Surrogate-assisted evolutionary computation: recent advances and future challenges. Swarm Evol. Comput. 1(2), 61–70 (2011)
Jin, Y., Branke, J.: Evolutionary optimization in uncertain environments—a survey. IEEE Trans. Evol. Comput. 9(3), 303–317 (2005)
Kallenberg, O.: Foundations of Modern Probability. Springer, New York (2002)
Kötzing, T., Neumann, F., Sudholt, D., Wagner, M.: Simple max-min ant systems and the optimization of linear pseudo-boolean functions, In: Proceedings of Foundations of Genetic Algorithms, FOGA XI, pp. 209–218 (2011)
Lässig, J., Sudholt, D.: General scheme for analyzing running times of parallel evolutionary algorithms. In: Proceedings of the International Conference on Parallel Problem Solving from Nature, PPSN’10, pp. 234–243 (2010)
Lehre, P.K.: Negative drift in populations. In: Proceedings of the International Conference on Parallel Problem Solving from Nature, PPSN’10, pp. 244–253. Springer, Berlin (2010)
Lehre, P.K.: Fitness-levels for non-elitist populations. In: Proceedings of the Annual Conference on Genetic and Evolutionary Computation, GECCO’11, pp. 2075–2082. ACM, New York (2011)
Lehre, P.K.: Drift analysis. In: Proceedings of the Annual Conference Companion on Genetic and Evolutionary Computation, GECCO’12, pp. 1239–1258. ACM, New York (2012)
Lehre, P.K., Yao, X.: On the impact of mutation-selection balance on the runtime of evolutionary algorithms. IEEE Trans. Evol. Comput. 16(2), 225–241 (2012)
Miller, B.L., Goldberg, D.E.: Genetic algorithms, selection schemes, and the varying effects of noise. Evol. Comput. 4, 113–131 (1996)
Mitrinović, D.S.: Elementary Inequalities. P. Noordhoff Ltd, Groningen (1964)
Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)
Neumann, F., Oliveto, P.S., Witt, C.: Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In: Proceedings of the Annual Conference on Genetic and Evolutionary Computation, GECCO’09, pp. 835–842 (2009)
Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity. Springer-Verlag New York Inc, New York (2010)
Rowe, J.E., Sudholt, D.: The choice of the offspring population size in the \((1, \lambda )\) evolutionary algorithm. Theor. Comput. Sci. 545, 20–38 (2014)
Sudholt, D.: A new method for lower bounds on the running time of evolutionary algorithms. IEEE Trans. Evol. Comput. 17(3), 418–435 (2013)
Wegener, I.: Methods for the analysis of evolutionary algorithms on pseudo-boolean functions. In: Evolutionary Optimization, vol. 48, pp. 349–369. Springer, New York (2002)
Witt, C.: Runtime analysis of the (\(\mu \) + 1) EA on simple pseudo-boolean functions. Evolutionary Computation 14(1), 65–86 (2006)
Yu, T., Davis, L., Baydar, C., Roy, R. (eds.): Evolutionary Computation in Practice, volume 88 of Studies in Computational Intelligence. Springer, Berlin (2008)
Acknowledgments
The authors are grateful to the anonymous reviewers of the conferences and of the journal for their corrections and constructive comments that improve the quality and the presentation of the paper. The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under Grant Agreement No. 618091 (SAGE) and from the British Engineering and Physical Science Research Council (EPSRC) Grant No. EP/F033214/1 (LANCS).
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
Lemma 27
(Chernoff’s Inequality, see [10]) If \(X = \sum _{i=1}^{m} X_i\), where \(X_i\in \{0,1\},i\in [m],\) are independent random variables, then \(\Pr \left( X \le (1-\varepsilon ){\mathbf {E}}\left[ X\right] \right) \le \exp \left( -\varepsilon ^2 {\mathbf {E}}\left[ X\right] /2\right) \) for any \(\varepsilon \in [0,1]\).
Lemma 28
(Chebyshev’s Inequality, see [29]) For any random variable X with finite expected value \(\mu \) and finite non-zero variance \(\sigma ^2\), it holds that \(\Pr \left( |X - \mu | \ge d\sigma \right) \le 1/d^2\) for any \(d > 0\).
Lemma 29
(Bernoulli’s inequality, see [28]) For any integer \(n\ge 0\) and any real number \(x\ge -1\), it holds that \((1+x)^n\ge 1+nx\).
Lemma 30
(Jensen’s inequality, see [28]) For any function f(x) convex in \([\alpha ,\beta ]\) and \(a_i \in [\alpha ,\beta ]\) with \(i \in [n]\),
Lemma 31
For \(n \in {\mathbb {N}}\) and \(x\ge 0\), we have \(1 - (1 - x)^n \ge 1 - e^{-xn} \ge \frac{xn}{1 + xn}\).
Proof
From \(e^x\ge x+1\), it follows that \(1 - (1 - x)^n \ge 1 - e^{-nx} \ge 1 - (1+x)^{-n} = 1 - 1/\left( 1 + \sum _{k=1}^{n} {n \atopwithdelims ()k} x^k\right) \). Note that \(x^{k} \ge 0\) for all \(x\ge 0\), thus any partial sum of \(\sum _{k=1}^{n} {n \atopwithdelims ()k} x^k\) provides a valid lower bound.
The result is obtained for the single term \(k=1\). \(\square \)
Lemma 32
For all \(x\in {\mathbb {R}}\), \(e^{2x} \ge (x+1)e^x > x e^x\) and for \(x>0\), \(e^{2x}/x > e^x\).
Proof
Multiplying \(e^x\) to \(e^x - x \ge 1 > 0\) and adding \(xe^{x}\) to both sides give the first result, then dividing them by \(x>0\) provides the second one. \(\square \)
Lemma 33
For all \(x\ge 0\), \(x \ge \ln (1+x) \ge x(1-x/2)\).
Proof
For each inequality, it suffices to first show that the gap between the (supposedly) larger side and the (supposedly) smaller one is non-decreasing in x, e.g., by looking at the derivative, then show that the initial gap is 0 at \(x=0\). \(\square \)
Lemma 34
Let X and Y be identically distributed independent random variables with integer support, finite expected value \(\mu \) and finite non-zero variance \(\sigma ^2\), it holds that
Proof
For any \(k, \ell \in {\mathbb {R}}\) with \(\lceil k \rceil \le \lfloor \ell \rfloor \), we have
The second last equality is due to Lemma 30 with the convex function \(f(x) = x^2\). It suffices to pick \(k = \mu - d \sigma \) and \(\ell = \mu + d \sigma \), so that by Lemma 28, we get
\(\square \)
Rights and permissions
About this article
Cite this article
Dang, DC., Lehre, P.K. Runtime Analysis of Non-elitist Populations: From Classical Optimisation to Partial Information. Algorithmica 75, 428–461 (2016). https://doi.org/10.1007/s00453-015-0103-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-015-0103-x