doi: 10.17586/2226-1494-2020-20-5-701-707


METHOD OF ARTIFICIAL FITNESS LEVELS FOR DYNAMICS ANALYSIS OF EVOLUTIONARY ALGORITHMS 
 

M. V. Buzdalov, D. V. Vinokurov


Read the full article  ';
Article in Russian

For citation:
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


Abstract
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.

Keywords: evolutionary algorithms, runtime analysis, fixed-target analysis, fixed-budget analysis, fitness-level method

Acknowledgements. This research was financially supported by the Russian Foundation for Basic Research and Centre National de la Recherche Scientifique (project No. 20-51-15009).

References
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


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Copyright 2001-2024 ©
Scientific and Technical Journal
of Information Technologies, Mechanics and Optics.
All rights reserved.

Яндекс.Метрика