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
REFERENCES
1. Auger A., Doerr B. Theory of randomized search heuristics: foundations and recent developments. Ser. Theoretical computer science, vol. 1. Singapore, World Scientific, 2011, 372 p. doi: 10.1142/7438
2. Borisovskii P.A., Eremeev A.V. Comparison of certain evolutionary algorithms Automat. Remote Control, 2004, vol. 65, no. 3, pp. 357–362. doi: 10.1023/B:AURC.0000019365.10288.58
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, pp. 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. In: Proc. of AAAI Conf. Artificial Intelligence (AAAI’ 2021), 2021, vol. 35, no. 14, pp. 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. In: Proc. of the Genetic and Evolutionary Computation Conf. (GECCO ’21), 2021, pp. 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 ’21), Birmingham, University of Birmingham, 2022. P. 1–2.
7. Dang D.-C., Eremeev A.V., Lehre P.K., Qin X. Fast non-elitist evolutionary algorithms with power-law ranking selection. In: Proc. of the Genetic and Evolutionary Computation Conf. (GECCO ’22), Boston Massachusetts, 2022, pp. 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. In: Proc. of the 13th IFIP Inter. Conf. on Intelligent Information Processing, 2024, vol. 703, pp. 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, pp. 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. In: Proc. of the 2015 Conf. on Foundations of Genetic Algorithms (FOGA ’ 2015), 2015, pp. 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, pp. 428–461. doi: 10.1007/s00453-015-0103-x
12. Doerr B. Does comma selection help to cope with local optima? In: Proc. of the 2020 Genetic and Evolutionary Computation Conf. (GECCO ’ 20), 2020, pp. 1304–1313. doi: 10.1145/3377930.3389823
13. Doerr B., Kötzing T. Multiplicative up-drift. Algorithmica, 2021, vol. 83, no. 10, pp. 3017–3058. doi: 10.1007/s00453-020-00775-7
14. Doerr B., Kötzing T. Multiplicative up-drift. In: Proc. of the Genetic and Evolutionary Computation Conference (GECCO ’19), NY: Association for Computing Machinery, 2019, pp. 1470–1478. doi: 10.1145/3321707.3321819
15. Doerr B., Le H.P., Makhmara R., Nguyen T.D. Fast genetic algorithms. In: Proc. of the 2017 Genetic and Evolutionary Computation Conf. (GECCO ’ 17), 2017, pp. 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, pp. 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 Comp. Syst., 2006, vol. 39, no. 4, pp. 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. In: Proc. of Artificial Evolution (AE 1999), Lecture notes in computer science, 2000, vol. 1829, pp. 84–95. doi: 10.1007/10721187_6
20. Goldberg D.E. Genetic algorithms in search, optimization and machine learning. Reading, Mass, Addison-Wesley Pub., 1989, 412 p.
21. Goldberg D.E., Deb K. A comparative analysis of selection schemes used in genetic algorithms. Foundations of genetic algorithms, 1991, vol. 1, pp. 69–93. doi: 10.1016/b978-0-08-050684-5.50008-2
22. Lehre P.K. Fitness-levels for non-elitist populations. In: Proc. of the 2011 Genetic and Evolutionary Computation Conf. (GECCO ’ 2011), 2011, pp. 2075–2082. doi: 10.1145/2001576.200185
23. Lehre P.K., Qin X. Self-adaptation can help evolutionary algorithms track dynamic optima. In: Proc. of the Genetic and Evolutionary Computation Conf. (GECCO ’ 23), 2023, pp. 1619–1627. doi: 10.1145/3583131.3590494
24. Lehre P.K., Qin X. Self-adaptation can improve the noise-tolerance of evolutionary algorithms. In: Proc. of the 17th ACM/SIGEVO Conf. on Foundations of Genetic Algorithms (FOGA’23), 2023, pp. 105–116. doi: 10.1145/3594805.3607128
25. Neumann F., Witt C. Bioinspired computation in combinatorial optimization: algorithms and their computational complexity. Ser. Natural Computing, Berlin, Heidelberg, Springer, 2010, 216 p. 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. In: Proc. of the Third Inter. Conf. on Genetic Algorithms, 1989, pp. 116–121.
27. Zubkov A.M., Popov N.N. Partial order relation generated by distributions of the number of occupied cells. Math. Notes, 1982, vol. 32, no. 1, pp. 528–531. doi: 10.1007/BF01137229
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.
