LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Dang, Duc-Cuong; Lehre, Per Kristian (2016)
Publisher: Springer
Languages: English
Types: Article
Subjects:
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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [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.
    • [11] C. Gie en and T. Kotzing. Robustness of populations in stochastic environments. In Proceedings of the Annual Conference on Genetic and Evolutionary Computation, GECCO'14, pages 1383{1390, New York, NY, USA, 2014. ACM.
    • [12] D. E. Goldberg and K. Deb. A comparative analysis of selection schemes used in genetic algorithms. In Proceedings of Foundations of Genetic Algorithms, FOGA I, pages 69{93. Morgan Kaufmann, 1991.
    • [13] B. Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied Probability, 14(3):502{525, 1982.
    • [14] E. Happ, D. Johannsen, C. Klein, and F. Neumann. Rigorous analyses of tness-proportional selection for optimizing linear functions. In Proceedings of the Annual Conference on Genetic and Evolutionary Computation, GECCO'08, pages 953{960, 2008.
    • [15] J. He and X. Yao. Drift analysis and average time complexity of evolutionary algorithms. Arti cial Intelligence, 127(1):57{85, 2001.
    • [16] J. He and X. Yao. From an individual to a population: an analysis of the rst hitting time of population-based evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 6(5):495{511, 2002.
    • [20] O. Kallenberg. Foundations of Modern Probability. Springer-Verlag, New York, 2002.
    • [21] T. Kotzing, F. Neumann, D. Sudholt, and M. Wagner. Simple max-min ant systems and the optimization of linear pseudo-boolean functions. In Proceedings of Foundations of Genetic Algorithms, FOGA XI, pages 209{ 218, 2011.
    • [22] J. Lassig and D. Sudholt. General scheme for analyzing running times of parallel evolutionary algorithms. In Proceedings of the International Conference on Parallel Problem Solving from Nature, PPSN'10, pages 234{ 243, 2010.
    • [23] P. K. Lehre. Negative drift in populations. In Proceedings of the International Conference on Parallel Problem Solving from Nature, PPSN'10, pages 244{253, Berlin, Heidelberg, 2010. Springer-Verlag.
    • [24] P. K. Lehre. Fitness-levels for non-elitist populations. In Proceedings of the Annual Conference on Genetic and Evolutionary Computation, GECCO'11, pages 2075{2082, New York, NY, USA, 2011. ACM.
    • [25] P. K. Lehre. Drift analysis. In Proceedings of the Annual Conference Companion on Genetic and Evolutionary Computation, GECCO'12, pages 1239{1258, New York, NY, USA, 2012. ACM.
    • [26] P. K. Lehre and X. Yao. On the impact of mutation-selection balance on the runtime of evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 16(2):225{241, 2012.
    • [27] B. L. Miller and D. E. Goldberg. Genetic algorithms, selection schemes, and the varying e ects of noise. Evolutionary Computation, 4:113{131, 1996.
    • [28] D. S. Mitrinovic. Elementary Inequalities. P. Noordho 1964.
    • [34] I. Wegener. Methods for the analysis of evolutionary algorithms on pseudoboolean functions. In Evolutionary Optimization, volume 48, pages 349{ 369. Springer US, 2002.
    • [35] C. Witt. Runtime analysis of the ( + 1) EA on simple pseudo-boolean functions. Evolutionary Computation, 14(1):65{86, 2006.
    • [36] T. Yu, L. Davis, C. Baydar, and R. Roy, editors. Evolutionary Computation in Practice, volume 88 of Studies in Computational Intelligence. Springer, 2008.
    • 1+xnxn .
    • Proof. For any k; ` 2 R with dke
  • No related research data.
  • Discovered through pilot similarity algorithms. Send us your feedback.

Share - Bookmark

Funded by projects

  • EC | SAGE
  • RCUK | The LANCS (Lancaster, Nott...

Related to

  • fet-fp7FET Open: FET Open FET Young Explorers
  • fet-fp7FET Open: Speed of Adaptation in Population Genetics and Evolutionary Computation

Cite this article