On the Efficiency of Nonelitist 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 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. Nonelitist 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) indexed in the expected order of their visit by the population of the evolutionary algorithm. In this paper, we consider the class SparseLocalOpt \({}_{\alpha,\varepsilon}\) $\left[𝛼, 𝜀\right]()$ of pseudo-Boolean optimization problems in which the union of the 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 nonelitist evolutionary algorithms first reach the global optimum; this bound holds for problems from SparseLocalOpt \({}_{\alpha,\varepsilon}\) $\left[𝛼, 𝜀\right]()$ , where elitist evolutionary algorithms are inefficient, i.e., reach the optimum in exponential time on average. In addition, the efficiency of nonelitist 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 the family of vertex cover problems on star graphs is given, and the advantage of nonelitist evolutionary algorithms is demonstrated compared to the simplest algorithm with one elite individual.