The choice of the offspring population size in the (1,λ) EA

ABSTRACT

We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,λ) EA. We establish a sharp threshold at λ = log{\frac{e}{e-1}} n ≈5 log₁₀ n between exponential and polynomial running times on OneMax. For any smaller value, the (1,λ) EA needs exponential time on every function that has only one global optimum. We also consider arbitrary unimodal functions and show that the threshold can shift towards larger offspring population sizes. Finally, we investigate the relationship between the offspring population size and arbitrary mutation rates on OneMax. We get sharp thresholds for λ that decrease with the mutation rate. This illustrates the balance between selection and mutation.

References

1. B. Doerr, D. Johannsen, and C. Winzen. Drift analysis and linear functions revisited. In Genetic and Evolutionary Computation Conference (GECCO '10), pages 1449--1456. ACM Press, 2010.
2. B. Doerr, D. Johannsen, and C. Winzen. Multiplicative drift analysis. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2010), pages 1--8. IEEE, 2010.
3. J. He and X. Yao. A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing, 3(1):21--35, 2004.
4. J. Jägersküpper and T. Storch. When the plus strategy outperforms the comma strategy and when not. In Proceedings of the IEEE Symposium on Foundations of Computational Intelligence, FOCI 2007, pages 25--32. IEEE, 2007.
5. T. Jansen, K. A. De Jong, and I. Wegener. On the choice of the offspring population size in evolutionary algorithms. Evolutionary Computation, 13:413--440, 2005.
6. D. Johannsen. Random Combinatorial Structures and Randomized Search Heuristics. PhD thesis, Universität des Saarlandes, 2010.
7. J. Lässig and D. Sudholt. General scheme for analyzing running times of parallel evolutionary algorithms. In 11th International Conference on Parallel Problem Solving from Nature (PPSN 2010), pages 234--243. Springer, 2010.
8. P. K. Lehre. Fitness-levels for non-elitist populations. In Proceedings of the 13th Annual Genetic and Evolutionary Computation Conference (GECCO '11), pages 2075--2082. ACM Press, 2011.
9. P. K. Lehre. Negative drift in populations. In 11th International Conference on Parallel Problem Solving from Nature (PPSN 2010), pages 244--253. Springer, 2011.
10. P. K. Lehre and X. Yao. On the impact of mutation-selection balance on the runtime of evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 2012. To appear.
11. B. Mitavskiy, J. Rowe, and C. Cannings. Theoretical analysis of local search strategies to optimize network communication subject to preserving the total number of links. International Journal of Intelligent Computing and Cybernetics, 2(2):243--284, 2009.
12. F. Neumann, P. S. Oliveto, and C. Witt. Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In Genetic and Evolutionary Computation Conference (GECCO'09), pages 835--842, 2009.
13. F. Neumann, D. Sudholt, and C. Witt. A few ants are enough: ACO with iteration-best update. In Genetic and Evolutionary Computation Conference (GECCO '10), pages 63--70, 2010.
14. C. P. Niculescu and A. Vernescu. A two-sided estimate of e^χ - (1+^χ⁄_n)ⁿ. Journal of Inequalities in Pure and Applied Mathematics, 5(3), 2004.
15. P. Oliveto. Computational Complexity Analysis of Evolutionary Algorithms for Combinatorial Optimisation. PhD thesis, Univ. Birmingham, 2009.
16. P. S. Oliveto and C. Witt. Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica, 59(3):369--386, 2011.
17. R. J. Quick, V. J. Rayward-Smith, and G. D. Smith. Fitness distance correlation and ridge functions. In Parallel Problem Solving from Nature (PPSN V), pages 77--86. Springer, 1998.
18. D. Sudholt. General lower bounds for the running time of evolutionary algorithms. In 11th International Conference on Parallel Problem Solving from Nature (PPSN 2010), pages 124--133. Springer, 2010.
19. C. Witt. Optimizing Linear Functions with Randomized Search Heuristics - The Robustness of Mutation. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), pages 420--431, 2012.

Index Terms

• Theory of computation

  • Design and analysis of algorithms