Runtime analysis of non-elitist populations: from classical optimisation to partial information

Article English OPEN
Dang, Duc-Cuong ; Lehre, Per Kristian (2016)

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.\ud \ud 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.
  • References (30)
    30 references, page 1 of 3

    [1] A. Auger, A. Auger, and B. Doerr. Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scienti c Publishing Co., Inc., River Edge, NJ, USA, 2011.

    [2] T. Chen, J. He, G. Sun, G. Chen, and X. Yao. A new approach for analyzing average time complexity of population-based evolutionary algorithms on unimodal problems. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 39(5):1092{1106, 2009.

    [3] R. Chiong, T. Weise, and Z. Michalewicz, editors. Variants of Evolutionary Algorithms for Real-World Applications. Berlin/Heidelberg: SpringerVerlag, 2012.

    [4] D. Corus, D.-C. Dang, A. V. Eremeev, and P. K. Lehre. Level-based analysis of genetic algorithms and other search processes. In Proceedings of the International Conference on Parallel Problem Solving from Nature, PPSN'14, pages 912{921, Ljubljana, Slovenia, 2014. Springer International Publishing.

    [5] D.-C. Dang and P. K. Lehre. Evolution under partial information. In Proceedings of the Annual Conference on Genetic and Evolutionary Computation, GECCO'14, pages 1359{1366, 2014.

    [6] D.-C. Dang and P. K. Lehre. Re ned upper bounds on the expected runtime of non-elitist populations from tness-levels. In Proceedings of the Annual Conference on Genetic and Evolutionary Computation, GECCO'14, pages 1367{1374, New York, NY, USA, 2014. ACM.

    [7] B. Doerr, D. Johannsen, and C. Winzen. Algorithmica, 64(4):673{697, 2012.

    [8] S. Droste. 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, pages 909{921, Berlin, Heidelberg, 2003. Springer-Verlag.

    [9] S. Droste. Analysis of the (1+1) EA for a noisy OneMax. In Proceedings of the 2004 International Conference on Genetic and Evolutionary Computation, GECCO'04, pages 1088{1099, Berlin, Heidelberg, 2004. SpringerVerlag.

    [10] D. Dubhashi and A. Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, NY, USA, 2009.

  • Similar Research Results (3)
  • Metrics
    No metrics available
Share - Bookmark