METHOD OF ARTIFICIAL FITNESS LEVELS FOR DYNAMICS ANALYSIS OF EVOLUTIONARY ALGORITHMS 

 

Buzdalov M.V., Vinokurov D.V. Method of artificial fitness levels for dynamics analysis of evolutionary algorithms. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2020, vol. 20, no. 5, pp. 701–707 (in Russian). doi: 10.17586/2226-1494-2020-20-5-701-707

Subject of Research. Currently, in the theory of evolutionary computation, it becomes relevant to analyze not just the runtime of evolutionary algorithms, but also their dynamics. The two most common methods for dynamics analysis are: fixed-budget analysis, which studies an algorithm reachable fitness in condition of operation time limit, and fixed- target analysis, which studies the time that an algorithm needs to reach some fixed fitness value. Until now, theoretical studies were systematically carried out only for the first type of analysis. The present work is focused on removal of this disadvantage. Method. We proved the following theorem: if the bounds on optimization time for some evolutionary algorithm on some problem are already proven using artificial fitness levels, than the bounds on this algorithm dynamics on the considered problem derive automatically from the same preconditions. Main Results. Using this theorem, we obtain the upper bounds on fixed-target runtime for the following pairs of algorithms and problems: the family of (1 + 1) evolutionary algorithms on LeadingOnes and OneMax functions, and (μ + 1) evolutionary algorithm on OneMax. These bounds either repeat or refine the existing results, but in a much simpler way. Practical Relevance. The main practical achievement of this paper is that it simplifies the proving of bounds on the dynamics of evolutionary algorithms. In turn, these bounds could be more meaningful for choosing between different evolutionary algorithms for some problem than the time for reaching the optimum, as the latter is mostly infeasible in practice.

1. Lengler J. Drift analysis. Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. Springer, 2020, pp. 89–131. doi: 10.1007/978-3-030-29414-4_2

2. Doerr B. A tight runtime analysis for the cGA on jump functions: EDAs can cross fitness valleys at no extra cost. Proc. Genetic and Evolutionary Computation Conference (GECCO), 2019, pp. 1488–1496. doi: 10.1145/3321707.3321747

3. Hansen N., Auger A., Ros R., Mersmann O., Tušar T., Brockhoff D. COCO: A platform for comparing continuous optimizers in a black-box setting. Optimization Methods and Software, 2020, in press. doi: 10.1080/10556788.2020.1808977

4. Doerr C., Wang H., Ye F., van Rijn S., Bäck T. IOHprofiler: A benchmarking and profiling tool for iterative optimization heuristics. Available at: https://arxiv.org/abs/1810.05281 (accessed: 27.06.2020).

5. Jansen T., Zarges C. Performance analysis of randomised search heuristics operating with a fixed budget. Theoretical Computer Science, 2014, vol. 545, pp. 39–58. doi: 10.1016/j.tcs.2013.06.007

6. Doerr B., Jansen T., Witt C., Zarges C. A method to derive fixed budget results from expected optimisation times. Proc. 15th Genetic and Evolutionary Computation Conference (GECCO 2013), 2013, pp. 1581–1588. doi: 10.1145/2463372.2463565

7. Lengler J., Spooner N. Fixed budget performance of the (1+1) EA on linear functions. Proc. 13th Foundations of Genetic Algorithms (FOGA), 2015, pp. 52–61. doi: 10.1145/2725494.2725506

8. Witt C. Runtime analysis of the (μ+1) EA on simple pseudo-Boolean functions. Evolutionary Computation, 2006, vol. 14, no. 1, pp. 65–86. doi: 10.1162/106365606776022751

9. Pinto E.C., Doerr C. Towards a more practice-aware runtime analysis of evolutionary algorithms. Available at: https://arxiv.org/abs/1812.00493 (accessed: 27.06.2020).

10. Vinokurov D., Buzdalov M., Buzdalova A., Doerr B., Doerr C. Fixed-target runtime analysis of the (1+1) EA with resampling. Proc. Genetic and Evolutionary Computation Conference Companion (GECCO’19), 2019, pp. 2068–2071. doi: 10.1145/3319619.3326906

11. Doerr B. Analyzing randomized search heuristics via stochastic domination. Theoretical Computer Science, 2019, vol. 773, pp. 115–137. doi: 10.1016/j.tcs.2018.09.024

12. Böttcher S., Doerr B., Neumann F. Optimal fixed and adaptive mutation rates for the LeadingOnes problem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2010, vol. 6238, pp. 1–10. doi: 10.1007/978-3-642-15844-5_1

13. Badkobeh G., Lehre P.K., Sudholt D. Unbiased black-box complexity of parallel search. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2014, vol. 8672, pp. 892–901. doi: 10.1007/978-3-319-10762-2_88

14. Doerr B., Doerr C, Ebel F. From black-box complexity to designing new genetic algorithms. Theoretical Computer Science, 2015, vol. 567, pp. 87–104. doi: 10.1016/j.tcs.2014.11.028

15. Wegener I. Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. International Series in Operations Research & Management Science, 2003, vol. 48, pp. 349–369. doi: 10.1007/0-306-48041-7_14

16. Sudholt D. A new method for lower bounds on the running time of evolutionary algorithms. IEEE Transactions on Evolutionary Computation, 2013, vol. 17, no. 3, pp. 418–435. doi: 10.1109/TEVC.2012.2202241

17. Doerr B., Doerr C. The impact of random initialization on the runtime of randomized search heuristics. Algorithmica, 2016, vol. 75, no. 3, pp. 529–553. doi: 10.1007/s00453-015-0019-5

18. Spivey M.Z. Combinatorial sums and finite differences. Discrete Mathematics, 2007, vol. 307, no. 24, pp. 3130–3146. doi: 10.1016/j.disc.2007.03.052

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License