FOGA '19- Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

The expected running time of the classical (1+1) EA on the ONEMAX benchmark function has recently been determined by Hwang et al. (2018) up to additive errors of O((log n)/n). The same approach proposed there also leads to a full asymptotic expansion with errors of the form O(n^-K log n) for any K > 0. This precise result is obtained by matched asymptotics with rigorous error analysis (or by solving asymptotically the underlying recurrences via inductive approximation arguments), ideas radically different from well-established techniques for the running time analysis of evolutionary computation such as drift analysis. This paper revisits drift analysis for the (1+1) EA on ONE MAX and obtains that the expected running time E (T), starting from [n/2] one-bits, is determined by the sum of inverse drifts up to logarithmic error terms, more precisely

[EQUATION]

where Δ(k) is the drift (expected increase of the number of one-bits from the state of n - k ones) and c1, c2 > 0 are explicitly computed constants. This improves the previous asymptotic error known for the sum of inverse drifts from Õ(n^2/3) to a logarithmic error and gives for the first time a non-asymptotic error bound. Using standard asymptotic techniques, the difference between E (T) and the sum of inverse drifts is found to be (e/2) log n + O(1).

We prove the linear convergence of the (1 + 1)-Evolution Strategy (ES) with a success based step-size adaptation on a broad class of functions, including strongly convex functions with Lipschitz continuous gradients, which is often assumed to analyze gradient based methods. Our proof is based on the methodology recently developed to analyze the same algorithm on the spherical function, namely the additive drift analysis on unbounded continuous domain. An upper bound of the expected first hitting time is derived, from which we can conclude that our algorithm converges linearly. We investigate the class of functions that satisfy the assumptions of our main theorem, revealing that strongly convex functions with Lipschitz continuous gradients and their strictly increasing transformation satisfy the assumptions. To the best of our knowledge, this is the first paper showing the linear convergence of the (1+1)-ES on such a broad class of functions. This opens the possibility to compare the (1 + 1)-ES and gradient based methods in theory.

In the first runtime analysis of an estimation-of-distribution algorithm (EDA) on the multimodal jump function class, Hasenöhrl and Sutton (GECCO 2018) proved that the runtime of the compact genetic algorithm with suitable parameter choice on jump functions with high probability is at most polynomial (in the dimension) if the jump size is at most logarithmic (in the dimension), and is at most exponential in the jump size if the jump size is super-logarithmic. The exponential runtime guarantee was achieved with a hypothetical population size that is also exponential in the jump size. Consequently, this setting cannot lead to a better runtime.

In this work, we show that any choice of the hypothetical population size leads to a runtime that, with high probability, is at least exponential in the jump size. This result might be the first non-trivial exponential lower bound for EDAs that holds for arbitrary parameter settings.

We study the use of voting mechanisms in populations, and introduce a new Voting algorithm which can solve ONEMAX and JUMP in O(n log n), even for gaps as large as O(n). More significantly, the algorithm solves ONEMAX with added posterior noise in O(n log n), when the variance of the noise distribution is σ² = O(n) and in O(σ² log n) when the noise variance is greater than this. We assume only that the noise distribution has finite mean and variance and (for the larger noise case) that it is unimodal. We also examine the performance on arbitrary linear and monotonic functions. The Voting algorithm fails on LEADINGSONES but we give a variant which can solve the problem in O(n log n). We empirically study the use of voting in population based algorithms (UMDA, PCEA and cGA) and show that this can be effective for large population sizes.

This paper concerns the theoretical analysis of a multi-recombinative meta-ES with repair by projection applied to a conically constrained problem. Using theoretical results for the mean value dynamics and steady state considerations of the inner ES, approximate closed-form expressions for the mean value dynamics and the steady state behavior of the outer ES are derived. The approximation quality is shown by comparison with real meta-ES runs using isolation periods larger than one. The theoretical results are compared to known theoretical results of the multi-recombinative ES with σ-Self-Adaptation and Cumulative Step-Size adaptation. It is shown that the meta-ES achieves the largest steady state progress for the considered problem at the cost of twice the function evaluations compared to the other variants.

Evolutionary algorithms have successfully been applied to evolve problem instances that exhibit a significant difference in performance for a given algorithm or a pair of algorithms inter alia for the Traveling Salesperson Problem (TSP). Creating a large variety of instances is crucial for successful applications in the blooming field of algorithm selection. In this paper, we introduce new and creative mutation operators for evolving instances of the TSP. We show that adopting those operators in an evolutionary algorithm allows for the generation of benchmark sets with highly desirable properties: (1) novelty by clear visual distinction to established benchmark sets in the field, (2) visual and quantitative diversity in the space of TSP problem characteristics, and (3) significant performance differences with respect to the restart versions of heuristic state-of-the-art TSP solvers EAX and LKH. The important aspect of diversity is addressed and achieved solely by the proposed mutation operators and not enforced by explicit diversity preservation.

Extracting a priori knowledge informing about the landscape underlying an unknown optimization problem has been proved extremely useful for different purposes, such as designing finely-tuned algorithms and automated solving techniques. Focusing on continuous domains, substantial progress has been achieved with the development of the so-called exploratory landscape analysis (ELA) approach, which provides a unified methodology for integrating features into sophisticated machine learning techniques. In particular, much efforts have been devoted to the systematic design of algorithm selection models aiming at improving existing state-of-art solvers. Nonetheless, designing the ELA features themselves is a bottleneck that can prevent further advances. The contribution of this paper is thereby two fold. Firstly, we consider the design of insightful features on the basis of the search tree constructed by the so-called SOO global optimizer, which is shown to imply an informative sampling of the search space using a limited budget. Secondly, we provide empirical evidence on the relevance of the proposed features and their potential in complementing existing ELA features for both predicting high-level problem properties, and selecting algorithms from a portfolio of available solvers. Our empirical findings are based on a comprehensive analysis using the diverse set of BBOB functions and solvers from the COCO platform.

Pseudo-Boolean monotone functions are unimodal functions which are trivial to optimize for some hillclimbers, but are challenging for a surprising number of evolutionary algorithms. A general trend is that evolutionary algorithms are efficient if parameters like the mutation rate are set conservatively, but may need exponential time otherwise. In particular, it was known that the (1 + 1)-EA and the (1 + λ)-EA can optimize every monotone function in pseudolinear time if the mutation rate is c/n for some c < 1, but that they need exponential time for some monotone functions for c > 2.2. The second part of the statement was also known for the (µ + 1)-EA.

In this paper we show that the first statement does not apply to the (µ + 1)-EA. More precisely, we prove that for every constant c > 0 there is a constant µ0 ∈ N such that the (µ + 1)-EA with mutation rate c/n and population size µ0 ≤ µ ≤ n needs superpolynomial time to optimize some monotone functions. Thus, increasing the population size by just a constant has devastating effects on the performance. This is in stark contrast to many other benchmark functions on which increasing the population size either increases the performance significantly, or affects performance only mildly.

The reason why larger populations are harmful lies in the fact that larger populations may temporarily decrease selective pressure on parts of the population. This allows unfavorable mutations to accumulate in single individuals and their descendants. If the population moves sufficiently fast through the search space, then such unfavorable descendants can become ancestors of future generations, and the bad mutations are preserved. Remarkably, this effect only occurs if the population renews itself sufficiently fast, which can only happen far away from the optimum. This is counter-intuitive since usually optimization becomes harder as we approach the optimum. Previous work missed the effect because it focused on monotone functions that are only deceptively close to the optimum.

The edge coloring problem asks for an assignment of colors to edges of a graph such that no two incident edges share the same color and the number of colors is minimized. It is known that all graphs with maximum degree Δ can be colored with Δ or Δ + 1 colors, but it is NP-hard to determine whether Δ colors are sufficient.

We present the first runtime analysis of evolutionary algorithms (EAs) for the edge coloring problem. Simple EAs such as RLS and (1+1) EA efficiently find (2Δ - 1)-colorings on arbitrary graphs and optimal colorings for even and odd cycles, paths, star graphs and arbitrary trees. A partial analysis for toroids also suggests efficient runtimes in bipartite graphs with many cycles. Experiments support these findings and investigate additional graph classes such as hypercubes, complete graphs and complete bipartite graphs. Theoretical and experimental results suggest that simple EAs find optimal colorings for all these graph classes in expected time O(Δℓ²m log m), where m is the number of edges and ℓ is the length of the longest simple path in the graph.

Resampling methods, based on averaging the fitness of several clones, are the classical solution for dealing with noise. Population control has been proposed as a different tool for faster convergence of evolution strategies when the variance does not vanish around the optimum. However, we show that convergence may not hold even in the case of centered noise and construct a counterexample with variance dissymmetry, i.e. more variance on one side of the optimum than on the other. We propose a fix termed consistent population control and formally derive uniform constraints on deviations between averages and expectations within the proposed algorithm under either subgaussianity or finite variance assumptions on measurement noise. We prove convergence guarantees of consistent population control, verify it experimentally and show the effectiveness of population control in direct policy search, either with our fix or, in overparameterized cases, without our fix.

The performance of base-line Evolutionary Algorithms (EAs) on combinatorial problems has been studied rigorously. From the theoretical viewpoint, the literature extensively investigates the linear problems, while the theoretical analysis of the non-linear problems is still far behind. In this paper, variations of the Packing While Travelling (PWT) - also known as the non-linear knapsack problem - are studied as an attempt to analyse the behaviour of EAs on non-linear problems from theoretical perspective. We investigate PWT for two cities and n items with correlated weights and profits, using single-objective and multi-objective algorithms. Our results show that RLS_swap, which differs from the classical RLS by having the ability to swap two bits in one iteration, finds the optimal solution in O(n³) expected time. We also study an enhanced version of GSEMO, which a specific selection operator to deal with exponential population size, and prove that it finds the Pareto front in the same asymptotic expected time. In the case of uniform weights, (1 + 1) EA is able to find the optimal solution in expected time O(n² log (max{n,p_max})), where p_max is the largest profit of the given items. We also perform an experimental analysis to complement our theoretical investigations and provide additional insights into the runtime behavior.

The Minimum Spanning Tree problem is a well-known combinatorial optimization problem, which has attracted much attention from the researchers in the field of evolutionary computing. Within the paper, a constrained version of the problem named Depth Restricted (1-2)-Minimum Spanning Tree problem is considered in the context of evolutionary algorithms, which had been shown to be NP-hard. We separately investigate the expected time (i.e., the expected number of fitness evaluations) of the (1+1) EA, the Multi-Objective Evolutionary Algorithm and its two variants adapted to the constrained version, to obtain an approximate solution with ratio 2 or 3/2 with respect to several different fitness functions. In addition, we observe a close connection between the constrained version and the Set Cover problem, and present a simple evolutionary algorithm for the 3-Set Cover problem. Based on the approximate solution returned by our evolutionary algorithm for the 3-Set Cover problem, an approximate solution with ratio better than 3/2 for the constrained version can be constructed.

The area of runtime analysis has made important contributions to the theoretical understanding of evolutionary algoirthms for stochastic problems in recent years. Important real-world applications involve chance constraints where the goal is to optimize a function under the condition that constraints are only violated with a small probability. We rigorously analyze the runtime of the (1+1) EA for the chance-constrained knapsack problem. In this setting, the weights are stochastic, and the objective is to maximize a linear profit function while minimizing the probability of a constraint violation in the total weight. We investigate a number of special cases for this problem, paying attention to how the structure of the chance constraint influences the runtime behavior of the (1+1) EA. Our results reveal that small changes to the profit value can result in hard-to-escape local optima.

We introduce a new benchmark problem called Deceptive Leading Blocks (DLB) to rigorously study the runtime of the Univariate Marginal Distribution Algorithm (UMDA) in the presence of epistasis and deception. We show that simple Evolutionary Algorithms (EAs) outperform the UMDA unless the selective pressure µ/λ is extremely high, where µ and λ are the parent and offspring population sizes, respectively. More precisely, we show that the UMDA with a parent population size of µ = Ω (log n) has an expected runtime of e^Ω(µ) on the DLB problem assuming any selective pressure [EQUATION], as opposed to the expected runtime of O (nλ log λ + n³) for the non-elitist (µ, λ) EA with µ/λ ≤ 1/e. These results illustrate inherent limitations of univariate EDAs against deception and epistasis, which are common characteristics of real-world problems. In contrast, empirical evidence reveals the efficiency of the bi-variate MIMIC algorithm on the DLB problem. Our results suggest that one should consider EDAs with more complex probabilistic models when optimising problems with some degree of epistasis and deception.

We conduct a rigorous runtime analysis of the (1 + (λ, λ)) evolutionary algorithm with standard parameter settings, that is, a mutation rate of p = λ/n and a crossover bias of c = 1/λ when optimizing the classic LeadingOnes benchmark function. We show that, for all λ ∈ [1..n/2], the runtime is Θ(n²/λ) iterations and Θ(n²) fitness evaluations. This is, asymptotically, the same number of iterations as for the (1 + λ) EA and the same number of fitness evaluations as for the (1 + λ) EA for any value of λ = O(n). We also extend our results to parameter control techniques and prove that for any dynamic choice of λ the bound of Θ(n²) fitness evaluations still holds.