On the efficiency of non-elitist evolutionary algorithms in the case of sparsity of the level sets inconsistent with respect to the objective function

A. V. Eremeev

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 30 (2024) no. 4, pp. 84-105

Résumé

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.

Détail

Keywords: evolutionary algorithm, local optimum, optimization time, density, sparsity.

Bibliographie

[1] Auger A., Doerr B., Theory of randomized search heuristics: foundations and recent developments, Ser. Theoretical Computer Science, 1, World Scientific, Singapore, 2011, 359 pp. | DOI | MR | Zbl

[2] Borisovskii P. A., Eremeev A. V., “O sravnenii nekotorykh evolyutsionnykh algoritmov”, Avtomatika i telemekhanika, 2004, no. 3, 3–9 | MR | Zbl

[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, 22:5 (2018), 707–719 | DOI

[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, 12275–12283 | DOI

[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, 1133–1141 | DOI | MR

[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), University of Birmingham, Birmingham, 2022, 2 pp. | MR

[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, 1372–1380 | DOI | MR

[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, 217–232 | DOI

[9] Dang D.-C., Jansen T., Lehre P. K., “Populations can be essential in tracking dynamic optima”, Algorithmica, 78:2 (2017), 660–680 | DOI | MR | Zbl

[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, 62–68 | DOI | MR | Zbl

[11] Dang D.-C., Lehre P. K., “Runtime analysis of non-elitist populations: From classical optimisation to partial information”, Algorithmica, 75 (2016), 428–461 | DOI | MR | Zbl

[12] Doerr B., “Does comma selection help to cope with local optima?”, Proc. of the 2020 Genetic and Evolutionary Computation Conference (GECCO 2020), 2020, 1304–1313 | DOI | MR

[13] Doerr B., K{ö}tzing T., “Multiplicative up-drift”, Algorithmica, 83:10 (2021), 3017–3058 | DOI | MR | Zbl

[14] Doerr B., Kötzing T., “Multiplicative up-drift”, Proc. of the Genetic and Evolutionary Computation Conference (GECCO '19), Association for Computing Machinery, NY, 2019, 1470–1478 | DOI | MR

[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, 777–784 | DOI

[16] Doerr C., Lengler J., “Introducing elitist black-box models: When does elitist behavior weaken the performance of evolutionary algorithms?”, Evolutionary Computation, 25:4 (2017), 587–606 | DOI | MR

[17] Droste S., Jansen T., Wegener I., “Upper and lower bounds for randomized search heuristics in black-box optimization”, Theory of Computing Systems, 39:4 (2006), 525–544 | DOI | MR | Zbl

[18] Dubhashi D., Panconesi A., Concentration of measure for the analysis of randomized algorithms, Cambridge University Press, NY, 2009, 195 pp. | DOI | MR | Zbl

[19] Eremeev A. V., “Modeling and analysis of genetic algorithm with tournament selection”, Proc. of Artificial Evolution (AE 1999), Ser. Lecture Notes in Computer Science, 1829, 2000, 84–95 | DOI | Zbl

[20] Goldberg D. E., Genetic Algorithms in search, optimization and machine learning, Addison-Wesley, Reading, MA, 1989, 412 pp. | Zbl

[21] Goldberg D. E., Deb K., “A comparative analysis of selection schemes used in genetic algorithms”, Foundations of Genetic Algorithms, 1991, 69–93 | MR

[22] Lehre P. K., “Fitness-levels for non-elitist populations”, Proc. of the 2011 Genetic and Evolutionary Computation Conference (GECCO 2011), 2011, 2075–2082 | DOI

[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, 1619–1627 | DOI | MR

[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, 105–116 | DOI | MR | Zbl

[25] Neumann F., Witt C., Bioinspired computation in combinatorial optimization: Algorithms and their computational complexity, Natural Computing Ser., Springer, Berlin; Heidelberg, 2010, 216 pp. | DOI | MR | Zbl

[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, 116–121

[27] Zubkov A. M., Popov N. N., “Otnoshenie chastichnogo poryadka, porozhdennoe raspredeleniyami chisla zanyatykh yacheek”, Mat. zametki, 32:1 (1982), 97–102 | MR | Zbl