УДК 519.712
MSC: 68W20, 68W40, 68Q87, 68T20
DOI: 10.21538/0134-4889-2024-30-4-84-105
Работа выполнена при поддержке Математического центра в Академгородке, соглашение с Министерством науки и высшего образования Российской Федерации № 075-15-2022-282.
Во многих известных эволюционных алгоритмах для задач оптимизации используются элитные особи, которые гарантированно сохраняются в популяции эволюционного алгоритма в силу своего преимущества по целевой функции по сравнению с другими имеющимися особями. Несмотря на то что в живой природе элитных особей не существует, в эволюционных алгоритмах элита обеспечивает постоянное присутствие рекордных решений в популяции и позволяет интенсивно исследовать пространство поиска вблизи таких решений. Тем не менее известны семейства задач, на которых наличие элитных особей затрудняет исследование новых областей пространства решений, препятствует выходу из локальных оптимумов и увеличивает математическое ожидание времени получения глобального оптимума. Эволюционные алгоритмы без элиты, в частности при использовании турнирной и линейной ранжирующей селекции, оказываются эффективными на этих задачах, однако требуют подходящей настройки параметров селекции и мутации. Один из стандартных подходов к анализу эффективности эволюционных алгоритмов основывается на разбиении пространства решений на подмножества (области уровня), пронумерованные в предполагаемом порядке посещения их популяцией ЭА. В настоящей работе рассматривается класс SparseLocalOpt$_{\alpha, \varepsilon}$ задач псевдобулевой оптимизации, в которых объединение семейства областей уровня, в некотором смысле не согласованного по целевой функции, является $\varepsilon$-разреженным множеством, а множества решений, где целевая функция больше, чем в несогласованных областях уровня, имеют плотность не менее $\alpha$. Основным результатом является новая полиномиальная верхняя оценка математического ожидания времени первого достижения глобального оптимума эволюционными алгоритмами без элиты, справедливая для задач из SparseLocalOpt$_{\alpha, \varepsilon}$, где элитные эволюционные алгоритмы неэффективны, т. е. требуют экспоненциального в среднем времени для получения оптимума. Кроме того, показана эффективность эволюционных алгоритмов без элиты на более широком классе задач. Найдены значения настраиваемых параметров для эволюционных алгоритмов с турнирной и линейной ранжирующей селекцией, при которых гарантируется полиномиальная ограниченность времени оптимизации для некоторых $\alpha$ и $\varepsilon$. Приводится пример использования полученных результатов для семейства задач вершинного покрытия на графах "звезда", а также демонстрируется преимущество эволюционных алгоритмов без элиты по сравнению с простейшим алгоритмом, использующим одну элитную особь.
Ключевые слова: эволюционный алгоритм, локальный оптимум, время достижения оптимума, плотность, разреженность
СПИСОК ЛИТЕРАТУРЫ
1. Auger A., Doerr B. Theory of randomized search heuristics: foundations and recent developments. Singapore: World Scientific, 2011. 359 p. (Ser. Theoretical Computer Science; vol. 1). doi: 10.1142/7438
2. Борисовский П. А., Еремеев А. В. О сравнении некоторых эволюционных алгоритмов // Автоматика и телемеханика. 2004. № 3. С. 3–9.
3. Corus D., Dang D.-C., Eremeev A.V., Lehre P.K. Level-based analysis of genetic algorithms and other search processes // IEEE Trans. Evolutionary Computation. 2018. Vol. 22, no. 5. P. 707–719. doi: 10.1109/TEVC.2017.2753538
4. Dang D.-C., Eremeev A.V., Lehre P.K. Escaping local optima with non-elitist evolutionary algorithms // Proc. of AAAI Conf. on Artificial Intelligence (AAAI’2021). 2021. P. 12275–12283. doi: 10.1609/aaai.v35i14.17457
5. Dang D.-C., Eremeev A. V., Lehre P. K. Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys // Proc. of the Genetic and Evolutionary Computation Conf. (GECCO’2021). 2021. P. 1133–1141. doi: 10.1145/3449639.3459398
6. Dang D.-C., Eremeev A. V., Lehre P. K. Corrigendum to “Non-elitist evolutionary algorithms excel in fitness landscapes with sparse deceptive regions and dense valleys” (GECCO 2021). Birmingham: University of Birmingham, 2022. 2 p.
7. Dang D.-C., Eremeev A. V., Lehre P. K., Qin X. Fast non-elitist evolutionary algorithms with power-law ranking selection // Proc. of the Genetic and Evolutionary Computation Conference (GECCO’2022). 2022. P. 1372–1380. doi: 10.1145/3512290.3528873
8. Dang D.-C., Eremeev A. V., Qin X. Empirical evaluation of evolutionary algorithms with power-law ranking selection // Proc. of the 13th IFIP International Conference on Intelligent Information Processing. 2024. P. 217–232. doi: 10.1007/978-3-031-57808-3_16
9. Dang D.-C., Jansen T., Lehre P. K. Populations can be essential in tracking dynamic optima // Algorithmica. 2017. Vol. 78, no. 2. P. 660–680. doi: 10.1007/s00453-016-0187-y
10. Dang D.-C., Lehre P. K. Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms // Proc. of the 2015 Conference on Foundations of Genetic Algorithms (FOGA’2015). 2015. P. 62–68. doi: 10.1145/2725494.2725508
11. Dang D.-C., Lehre P. K. Runtime analysis of non-elitist populations: From classical optimisation to partial information // Algorithmica. 2016. Vol. 75. P. 428–461. doi: 10.1007/s00453-015-0103-x
12. Doerr B. Does comma selection help to cope with local optima? // Proc. of the 2020 Genetic and Evolutionary Computation Conference (GECCO 2020). 2020. P. 1304–1313. doi: 10.1145/3377930.3389823
13. Doerr B., Kötzing T. Multiplicative up-drift // Algorithmica. 2021. Vol. 83, no. 10. P. 3017–3058. doi: 10.1007/s00453-020-00775-7
14. Doerr B., Kötzing T. Multiplicative up-drift // Proc. of the Genetic and Evolutionary Computation Conference (GECCO ’19). NY: Association for Computing Machinery, 2019. P. 1470–1478. doi: 10.1145/3321707.3321819
15. Doerr B., Le H. P., Makhmara R., Nguyen T. D. Fast genetic algorithms // Proc. of the 2017 Genetic and Evolutionary Computation Conference (GECCO 2017). 2017. P. 777–784. doi: 10.1145/3071178.3071301
16. Doerr C., Lengler J. Introducing elitist black-box models: When does elitist behavior weaken the performance of evolutionary algorithms? // Evolutionary Computation. 2017. Vol. 25, no. 4. P. 587–606. doi: 10.1162/evco_a_00195
17. Droste S., Jansen T., Wegener I. Upper and lower bounds for randomized search heuristics in black-box optimization // Theory of Computing Systems. 2006. Vol. 39, no. 4. P. 525–544. doi: 10.1007/s00224-004-1177-z
18. Dubhashi D., Panconesi A. Concentration of measure for the analysis of randomized algorithms. NY: Cambridge University Press, 2009. 195 p. doi: 10.1017/CBO9780511581274
19. Eremeev A. V. Modeling and analysis of genetic algorithm with tournament selection // Proc. of Artificial Evolution (AE 1999). 2000. P. 84-95. (Ser. Lecture Notes in Computer Science; vol. 1829). doi: 10.1007/10721187_6
20. Goldberg D. E. Genetic Algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley, 1989. 412 p.
21. Goldberg D. E., Deb K. A comparative analysis of selection schemes used in genetic algorithms // Foundations of Genetic Algorithms. 1991. P. 69–93.
22. Lehre P. K. Fitness-levels for non-elitist populations // Proc. of the 2011 Genetic and Evolutionary Computation Conference (GECCO 2011). 2011. P. 2075–2082. doi: 10.1145/2001576.200185
23. Lehre P. K., Qin X. Self-adaptation can help evolutionary algorithms track dynamic optima // Proc. of the Genetic and Evolutionary Computation Conference (GECCO’2023). 2023. P. 1619–1627. doi: 10.1145/3583131.3590494
24. Lehre P. K., Qin X. Self-adaptation can improve the noise-tolerance of evolutionary algorithms // Proc. of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA 23). 2023. P. 105–116. doi: 10.1145/3594805.3607128
25. Neumann F., Witt C. Bioinspired computation in combinatorial optimization: Algorithms and their computational complexity. Berlin; Heidelberg: Springer, 2010. 216 p. (Natural Computing Ser.) doi: 10.1007/978-3-642-16544-3
26. Whitley D. The GENITOR algorithm and selection pressure: Why rank-based allocation of reproductive trials is best // Proc. of the Third International Conference on Genetic Algorithms. 1989. P. 116–121.
27. Зубков А. М., Попов Н. Н. Отношение частичного порядка, порожденное распределениями числа занятых ячеек // Мат. заметки. 1982. Т. 32, №1. С. 97–102.
Поступила 26.02.24
После доработки 23.08.2024
Принята к публикации 26.08.2024
Еремеев Антон Валентинович
д-р физ.-мат. наук, доцент
Новосибирский государственный университет
г. Новосибирск;
Омский государственный университет им. Ф.М. Достоевского
г. Омск
e-mail: eremeev@ofim.oscsbras.ru
Ссылка на статью: А.В. Еремеев. Об эффективности эволюционных алгоритмов без элиты в случае разреженности областей уровня, не согласованных по целевой функции // Тр. Ин-та математики и механики УрО РАН. 2024. Т. 30, № 4. С. 84-105
English
A.V. Eremeev. On the efficiency of non-elitist evolutionary algorithms in the case of sparsity of the level sets inconsistent with respect to the objective function
Many known evolutionary algorithms for optimization problems use elite individuals that are guaranteed to be preserved in the population of the evolutionary algorithm due to their advantage with respect to the objective function compared to other individuals. Despite the fact that there are no elite individuals in nature, in evolutionary algorithms the elite ensures the constant presence of record solutions in the population and allows an intensive study of the search space near such solutions. Nevertheless, there are families of problems in which the presence of elite individuals complicates the study of new areas of the solution space, prevents exit from local optima, and increases the mathematical expectation of the time to obtain a global optimum. Non-elitist evolutionary algorithms, in particular, when using tournament and linear ranking selection, are effective for these problems, but require an appropriate adjustment of the selection and mutation parameters. One of the standard approaches to analyzing the efficiency of evolutionary algorithms is based on dividing the solution space into subsets (level sets) numbered in the expected order of their visit by the population of the evolutionary algorithm. In this paper, we consider the class SparseLocalOpt$_{\alpha,\varepsilon}$ of pseudo-Boolean optimization problems in which the union of a family of level sets that are in some sense inconsistent with respect to the objective function is an $\varepsilon$-sparse set, and the solution sets where the objective function is greater than in inconsistent level sets have density at least $\alpha$. The main result is a new polynomial upper bound for the mathematical expectation of the time in which non-elitist evolutionary algorithms first reach the global optimum; this bound holds for problems from SparseLocalOpt$_{\alpha, \varepsilon}$, where elitist evolutionary algorithms are inefficient, i.e., reach the optimum in exponential time on average. In addition, the efficiency of non-elitist evolutionary algorithms is shown on a wider class of problems. The values of adjustable parameters that guarantee the polynomial boundedness of the optimization time for some $\alpha$ and $\varepsilon$ are found for evolutionary algorithms with tournament and linear ranking selection. An example of using the obtained results for a family of vertex covering problems on star graphs is given, and the advantage of non-elitist evolutionary algorithms is demonstrated compared to the simplest algorithm with one elite individual.
Keywords: evolutionary algorithm, local optimum, optimization time, density, sparsity
Received February 26, 2024
Revised August 23, 2024
Accepted August 26, 2024
Funding Agency: The work is supported by the Mathematical Center in Akademgorodok under agreement no. 075-15-2022-282 with the Ministry of Science and Higher Education of the Russian Federation.
Anton Valentinovich Eremeev, Dr. Phys.-Math. Sci., Docent, Novosibirsk State University, Novosibirsk, 630090 Russia; Dostoevsky Omsk State University, Omsk, 644077 Russia, e-mail: eremeev@ofim.oscsbras.ru
Cite this article as: A.V. Eremeev. On the efficiency of non-elitist evolutionary algorithms in the case of sparsity of the level sets inconsistent with respect to the objective function. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2024, vol. 30, no. 4, pp. 84–105.
[References -> on the "English" button bottom right]
