References

Drift Analysis and its Applications

Drift analysis is one of the most important and powerful tools used for estimating the computation time of evolutionary algorithms and other randomized search heuristics.

Tutorials

  1. Doerr, B. (2011) Drift Analysis. Proceedings of the 13th annual conference companion on Genetic and evolutionary computation, pp. 1311-1320
  2. Lehre, P.K. (2012) Drift Analysis. Proceedings of the 14th annual conference companion on Genetic and evolutionary computation, pp. 1239-1258

Reports

  1. He, J. (1998). Study on the foundation of evolutionary computation. Postdoc techreport, Department of Computer Science, Harbin Institute of Technology. (in Chinese)
  2. Lehre, P. K., & Witt, C. (2013). General drift analysis with tail bounds. arXiv preprint arXiv:1307.2559.

Journal Articles

  1. Hajek, B. (1982). Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied probability, 502-525.
  2. He, J., & Yao, X. (2001). Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence, 127(1), 57-85.
  3. He, J., & Yao, X. (2003). Towards an analytic framework for analysing the computation time of evolutionary algorithms. Artificial Intelligence, 145(1), 59-97.
  4. He, J., & Yao, X. (2003). Drift analysis in studying the convergence and hitting times of evolutionary algorithms: An overview. Wuhan University Journal of Natural Sciences, 8(1), 143-154.
  5. He, J., & Yao, X. (2004). A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing, 3(1), 21-35.
  6. He, J., & Yao, X. (2004). Time complexity analysis of an evolutionary algorithm for finding nearly maximum cardinality matching. Journal of Computer Science and Technology, 19(4), 450-458.
  7. He, J., Yao, X., & Li, J. (2005). A comparative study of three evolutionary algorithms incorporating different amounts of domain knowledge for node covering problem. Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 35(2), 266-271.
  8. Mitavskiy, B., Rowe, J., & Cannings, C. (2009). 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.
  9. Jansen, T., & Sudholt, D. (2010). Analysis of an asymmetric mutation operator. Evolutionary Computation, 18(1), 1-26.
  10. Giel, O., & Lehre, P. K. (2010). On the Effect of Populations in Evolutionary Multi-Objective Optimisation. Evolutionary Computation, 18(3), 335-356.
  11. Chen, Y., Zou, X., & He, J. (2011). Drift conditions for estimating the first hitting times of evolutionary algorithms. International Journal of Computer Mathematics, 88(1), 37-50.
  12. Jägersküpper, J. (2011). Combining Markov-Chain Analysis and Drift Analysis. Algorithmica, 59(3), 409-424.
  13. Oliveto, P. S., & Witt, C. (2011). Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica, 59(3), 369-386.
  14. Chen, T., Tang, K., Chen, G., & Yao, X. (2012). A large population size can be unhelpful in evolutionary algorithms. Theoretical Computer Science, 436, 54-70.
  15. Ding, L., & Yu, J. (2012). Some techniques for analyzing time complexity of evolutionary algorithms. Transactions of the Institute of Measurement and Control, 34(6), 755-766.
  16. Doerr, B., Johannsen, D., & Winzen, C. (2012). Multiplicative drift analysis. Algorithmica, 64(4), 673-697.
  17. Doerr, B., Johannsen, D., & Winzen, C. (2012). Non-existence of linear universal drift functions. Theoretical Computer Science, 436, 71-86.
  18. Lehre, P. K., & Witt, C. (2012). Black-box search by unbiased variation. Algorithmica, 64(4), 623-642.
  19. Doerr, B., & Goldberg, L. A. (2013). Adaptive drift analysis. Algorithmica, 65(1), 224-250.
  20. Guo, W., Wang, L., Ge, S. S., Ren, H., & Mao, Y. (2014). Drift analysis of mutation operations for biogeography-based optimization. Soft Computing, 1-12.
  21. Lassig, J., & Sudholt, D. (2014). General upper bounds on the runtime of parallel evolutionary algorithms. Evolutionary computation, 22(3), 405-437.
  22. Lehre, P. K., & Yao, X. (2014). Runtime analysis of the (1+ 1) ea on computing unique input output sequences. Information Sciences, 259, 510-531.
  23. Oliveto, P. S., & Witt, C. (2014). On the runtime analysis of the simple genetic algorithm. Theoretical Computer Science, 545, 2-19.
  24. Rowe, J. E., & Sudholt, D. (2014). The choice of the offspring population size in the (1, λ) evolutionary algorithm. Theoretical Computer Science, 545, 20-38.
  25. Doerr, B., & Künnemann, M. (2015). Optimizing linear functions with the (1+ λ) evolutionary algorithm—Different asymptotic runtimes for different instances. Theoretical Computer Science, 561, 3-23. 3-23.
  26. He, J., Chen, T., & Yao, X. (2015). On the easiest and hardest fitness functions. Evolutionary Computation, IEEE Transactions on, 19(2), 295-305.
  27. Lissovoi, A., & Witt, C. (2015). Runtime analysis of ant colony optimization on dynamic shortest path problems. Theoretical Computer Science, 561, 73-85.
  28. Oliveto, P. S., & Witt, C. (2015). Improved time complexity analysis of the Simple Genetic Algorithm. Theoretical Computer Science.

Conference Papers

  1. He, J., & Yao, X. (2003, December). An analysis of evolutionary algorithms for finding approximation solutions to hard optimisation problems. In Evolutionary Computation, 2003. CEC'03. The 2003 Congress on (Vol. 3, pp. 2004-2010). IEEE.
  2. He, J., Yao, X., & Zhang, Q. (2004, June). To understand one-dimensional continuous fitness landscapes by drift analysis. In Evolutionary Computation, 2004. CEC2004. Congress on (Vol. 2, pp. 1248-1253). IEEE.
  3. Jägersküpper, J. (2008). A blend of Markov-chain and drift analysis. In Parallel Problem Solving from Nature–PPSN X (pp. 41-51). Springer Berlin Heidelberg.
  4. Doerr, B., & Goldberg, L. A. (2010). Drift analysis with tail bounds. In Parallel Problem Solving from Nature, PPSN XI (pp. 174-183). Springer Berlin Heidelberg.
  5. Doerr, B., & Goldberg, L. A. (2010). Adaptive drift analysis. In Parallel Problem Solving from Nature, PPSN XI (pp. 32-41). Springer Berlin Heidelberg.
  6. Lehre, P. K. (2010). Negative drift in populations. In Parallel Problem Solving from Nature, PPSN XI (pp. 244-253). Springer Berlin Heidelberg.
  7. Doerr, B., Fouz, M., & Witt, C. (2011, July). Sharp bounds by probability-generating functions and variable drift. In Proceedings of the 13th annual conference on Genetic and evolutionary computation (pp. 2083-2090). ACM.
  8. Doerr, B., Hota, A., & Kötzing, T. (2012, July). Ants easily solve stochastic shortest path problems. In Proceedings of the 14th annual conference on Genetic and evolutionary computation (pp. 17-24). ACM. .
  9. Kötzing, T., & Molter, H. (2012). ACO beats EA on a dynamic pseudo-boolean function. In Parallel Problem Solving from Nature-PPSN XII (pp. 113-122). Springer Berlin Heidelberg.
  10. Rowe, J. E., & Sudholt, D. (2012, July). The choice of the offspring population size in the (1, λ) EA. In Proceedings of the 14th annual conference on Genetic and evolutionary computation (pp. 1349-1356). ACM.
  11. Witt, C. (2012). Optimizing linear functions with randomized search heuristics-the robustness of mutation. In STACS'12 (29th Symposium on Theoretical Aspects of Computer Science) (Vol. 14, pp. 420-431). LIPIcs.
  12. Doerr, B., Jansen, T., Witt, C., & Zarges, C. (2013, July). A method to derive fixed budget results from expected optimisation times. In Proceedings of the 15th annual conference on Genetic and evolutionary computation (pp. 1581-1588). ACM.
  13. Doerr, B., & Kunnemann, M. (2013, June). Royal road functions and the (1+ λ) Evolutionary Algorithm: Almost no speed-up from larger offspring populations. In Evolutionary Computation (CEC), 2013 IEEE Congress on (pp. 424-431). IEEE.
  14. Doerr, B., & K?nnemann, M. (2013, July). How the (1+ λ) Evolutionary Algorithm optimizes linear functions. In Proceedings of the 15th annual conference on Genetic and evolutionary computation (pp. 1589-1596). ACM.
  15. Mitavskiy, B., & He, J. (2013, June). Combining drift analysis and generalized schema theory to design efficient hybrid and/or mixed strategy EAs. In Evolutionary Computation (CEC), 2013 IEEE Congress on (pp. 2028-2036). IEEE.
  16. Oliveto, P. S., & Witt, C. (2013, July). Improved runtime analysis of the simple genetic algorithm. In Proceedings of the 15th annual conference on Genetic and evolutionary computation (pp. 1621-1628). ACM.
  17. Xu, W. D., Huang, H., Luo, J., & Zhan, H. X. (2013, July). A variant of Variable-Drift theorem for continuous (1+ 1)-Evolutionary Algorithm. In Machine Learning and Cybernetics (ICMLC), 2013 International Conference on (Vol. 1, pp. 469-475). IEEE.
  18. Corus, D., Dang, D. C., Eremeev, A. V., & Lehre, P. K. (2014). Level-based analysis of genetic algorithms and other search processes. In Parallel Problem Solving from Nature–PPSN XIII (pp. 912-921). Springer International Publishing.
  19. Doerr, B., & Férey, G. (2014, July). Monotonic functions in EC: anything but monotone! In Proceedings of the 2014 conference on Genetic and evolutionary computation (pp. 753-760). ACM. .
  20. Kötzing, T. (2014, July). Concentration of first hitting times under additive drift. In Proceedings of the 2014 conference on Genetic and evolutionary computation (pp. 1391-1398). ACM.
  21. Sutton, A. M., & Neumann, F. (2014). Runtime Analysis of Evolutionary Algorithms on Randomly Constructed High-Density Satisfiable 3-CNF Formulas. In Parallel Problem Solving from Nature–PPSN XIII (pp. 942-951). Springer International Publishing.
  22. Antipov, D., Buzdalov, M., & Doerr, B. (2015). Runtime Analysis of (1+ 1) Evolutionary Algorithm Controlled with Q-learning Using Greedy Exploration Strategy on OneMax+ ZeroMax Problem. In Evolutionary Computation in Combinatorial Optimization (pp. 160-172). Springer International Publishing.
  23. Corus, D., He, J., Jansen, T., Oliveto, P. S., Sudholt, D., & Zarges, C. (2015, July). On Easiest Functions for Somatic Contiguous Hypermutations And Standard Bit Mutations. In Proceedings of the 2015 on Genetic and Evolutionary Computation Conference (pp. 1399-1406). ACM.
  24. Gießen, C., & Witt, C. (2015, July). Population Size vs. Mutation Strength for the (1+ λ) EA on OneMax. In Proceedings of the 2015 on Genetic and Evolutionary Computation Conference (pp. 1439-1446). ACM.