ПРИМЕНЕНИЕ МЕТОДА УРОВНЕЙ ПРИСПОСОБЛЕННОСТИ ДЛЯ АНАЛИЗА ДИНАМИКИ РАБОТЫ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ

Буздалов М.В., Винокуров Д.В. Применение метода уровней приспособленности для анализа динамики работы эволюционных алгоритмов // Научно-технический вестник информационных технологий, механики и оптики. 2020. Т. 20. № 5. С. 701–707. doi: 10.17586/2226-1494-2020-20-5-701-707

Предмет исследования. В области теории эволюционных алгоритмов в настоящее время становится акту- альным анализ не только времени их работы, но и динамики. Двумя наиболее распространенными методами анализа динамики являются: анализ достижимой приспособленности при ограничении на время работы (fixed- budget analysis) и анализ времени работы, необходимого для достижения заданной цели (fixed-target analysis). До сих пор теоретические исследования систематически выполнялись только для первого из них. Настоящая работа направлена на устранение этого недостатка. Метод. Доказана теорема о том, что если для комбинации эволюционного алгоритма и задачи оптимизации ранее были доказаны оценки времени работы с помощью так называемого метода уровней приспособленности, то из необходимых для этого предпосылок автоматически следуют оценки динамики работы эволюционного алгоритма для рассматриваемой задачи. Основные результаты. В результате применения данной теоремы получены верхние оценки времени работы, которое необходимо для достижения заданной цели следующих пар алгоритмов и задач: эволюционные алгоритмы семейства (1 + 1) на задачах LeadingOnes и OneMax, эволюционный алгоритм (μ + 1) на задаче OneMax. Данные оценки повторяют или уточняют существующие результаты, но получают их существенно более простым способом. Практическая значимость. Результаты работы позволяют упростить получение оценок динамики работы эволюционных алгоритмов. Подобные оценки являются более содержательным критерием для выбора эволюционного алгоритма с целью решения практической задачи, чем оценка времени нахождения оптимального решения, так как последнее на практике чаще всего недостижимо.

1. Lengler J. Drift analysis // Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. Springer, 2020. P. 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. P. 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 [Электронный ресурс]. URL: https://arxiv.org/abs/1810.05281 (дата обращения: 27.06.2020).

5. Jansen T., Zarges C. Performance analysis of randomised search heuristics operating with a fixed budget // Theoretical Computer Science. 2014. V. 545. P. 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. P. 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. P. 52–61. doi: 10.1145/2725494.2725506

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

9. Pinto E.C., Doerr C. Towards a more practice-aware runtime analysis of evolutionary algorithms [Электронный ресурс]. URL: https://arxiv.org/abs/1812.00493 (дата обращения: 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. P. 2068–2071. doi: 10.1145/3319619.3326906

11. Doerr B. Analyzing randomized search heuristics via stochastic domination // Theoretical Computer Science. 2019. V. 773. P. 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. V. 6238. P. 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. V. 8672. P. 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. V. 567. P. 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. V. 48. P. 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. V. 17. N 3. P. 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. V. 75. N 3. P. 529–553. doi: 10.1007/s00453-015-0019-5

18. Spivey M.Z. Combinatorial sums and finite differences // Discrete Mathematics. 2007. V. 307. N 24. P. 3130–3146. doi: 10.1016/j.disc.2007.03.052

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