Evolutionary algorithms are inherently parallel optimization methods that have been successfully applied to many critical systems. While our understanding of their performance has steadily progressed, most existing work on distributed evolution assumes a perfect runtime environment. This assumption does not always hold in practice, and it is important to consider how robust such systems are to attack.

Clustering is the process of grouping similar data points into distinct clusters. Graph theoretic techniques for data clustering attempt to find the most efficient way to convert a precomputed similarity graph into a cluster graph, which is a collection of disjoint cliques. In contrast, most existing evolutionary approaches to clustering are based on partitioning data points according to feature vectors. In this paper we present an evolutionary algorithm for tackling data clustering from the graph theoretic perspective. In particular, we adapt a genetic algorithm (the SubPopGA) that maintains a population of solved subgraphs to solve the NP-hard k-Cluster Deletion and k-Cluster Vertex Deletion problems. This adaptation is nontrivial, as it requires modifying the technique to work on induced subgraphs and designing a novel template parent mechanism for uniform crossover. We prove that the resulting SubPopGA has a fixed-parameter tractable running time on both problems. Given an arbitrary graph on n vertices and m edges, we prove that it solves k-Cluster Deletion in O(n34k + mn2 log n) generations in expectation, and the k-Cluster Vertex Deletion problem in O(n35k + n3 log n) in expectation. We also present results from a number of computational experiments that measure the running time of the SubPopGA on real-world biological data sets coming from protein-protein interaction networks.

Abstract The usual approach in runtime analysis is to derive estimates on the number of fitness function evaluations required by a method until a suitable element of the search space is found. One justification for this is that in real applications, fitness evaluation often contributes the most computational effort. A tacit assumption in this approach is that this effort is uniform and static across the search space. However, this assumption often does not hold in practice: some candidates may be far more expensive to evaluate than others. This might occur, for example, when fitness evaluation requires running a simulation or training a machine learning model. Despite the availability of a wide range of benchmark functions coupled with various runtime performance guarantees, the runtime analysis community currently lacks a solid perspective of handling variable fitness cost. Our goal with this paper is to argue for incorporating this perspective into our theoretical toolbox. We introduce two models of handling variable cost: a simple non-adaptive model together with a more general adaptive model. We prove cost bounds in these scenarios and discuss the implications for taking into account costly regions in the search space.

Mutation operators are crucial for evolutionary algorithms to make progress through a search landscape. Sometimes a mutation strategy that works in one part of the landscape is less effective in other regions of the landscape. If nothing is known about the best mutation operator, many strategies (such as self-adaptation, heavy-tailed mutation, variable neighborhood search) exist to overcome this. However, in some cases, some limited information may be available, either a priori or after probing. In this paper, we study the setting of a mixture of binomial distributions for pseudo-Boolean optimization. We show that, when a limited amount of information is available, evolutionary algorithms using mutation based on a mixture of binomial distributions can hill-climb and escape local optima efficiently.

Many optimization problems tackled by evolutionary algorithms are not only computationally expensive but also complicated, with one or more sources of noise. One technique to deal with high computational overhead is parallelization. However, though the existing literature gives good insight about the expected behavior of parallelized evolutionary algorithms, we still lack an understanding of their performance in the presence of noise. This article considers how parallelization might be leveraged together with multi-parent crossover in order to handle noisy problems. We present a rigorous running time analysis of an island model with weakly connected topology tasked with hill climbing in the presence of general additive noise (i.e., noisy OneMax ). Our proofs yield insights into the relationship between the noise intensity and number of required parents. We translate this into positive and negative results for two kinds of multi-parent crossover operators. We then empirically analyze and extend this framework to investigate the tradeoffs between noise impact, optimization time, and limits of computation power to deal with noise.

Randomized search heuristics can sometimes be effective verifiers for combinatorial conjectures. In this paper, we demonstrate how a simple evolutionary algorithm can be used to confirm the antimagic tree conjecture for all trees up to order 25. This conjecture, which has been open for over thirty years, is that every tree except K2 has an antimagic labeling: a bijective edge labeling such that the sum of labels assigned to edges incident to a vertex v is unique for all vertices v ϵ V. Moreover, we formally prove that that simple evolutionary algorithms are guaranteed to find antimagic labelings in expected polynomial time on trees of any order for certain restricted classes (paths, combs, uniform caterpillars, uniform spiders and perfect binary trees).

We present the first parameterized analysis of a standard (1+1) Evolutionary Algorithm on a distribution of vertex cover problems. We show that if the planted cover is at most logarithmic, restarting the (1+1) EA every O(n log n) steps will find a cover at least as small as the planted cover in polynomial time for sufficiently dense random graphs p > 0.71. For superlogarithmic planted covers, we prove that the (1+1) EA finds a solution in fixed-parameter tractable time in expectation.

The usual approach in runtime analysis is to derive estimates on the number of fitness function evaluations required by a method until a suitable element of the search space is found. One justification for this is that in real applications, fitness evaluation often contributes the most computational effort. A tacit assumption in this approach is that this effort is uniform and static across the search space. However, this assumption often does not hold in practice: some candidates may be far more expensive to evaluate than others. This might occur, for example, when fitness evaluation requires running a simulation or training a machine learning model.

We study the multi-objective minimum weight base problem, an abstraction of classical NP-hard combinatorial problems such as the multi-objective minimum spanning tree problem. We prove some important properties of the convex hull of the non-dominated front, such as its approximation quality and an upper bound on the number of extreme points. Using these properties, we give the first run-time analysis of the MOEA/D algorithm for this problem, an evolutionary algorithm that effectively optimizes by decomposing the objectives into single-objective components. We show that the MOEA/D, given an appropriate decomposition setting, finds all extreme points within expected fixed-parameter polynomial time, in the oracle model. Experiments are conducted on random bi-objective minimum spanning tree instances, and the results agree with our theoretical findings. Furthermore, compared with a previously studied evolutionary algorithm for the problem GSEMO, MOEA/D finds all extreme points much faster across all instances.

Recently, Rowe and Aishwaryaprajna (2019) introduced a simple majority vote technique that efficiently solves Jump with large gaps, OneMax with large noise, and any monotone function with a polynomial-size image. In this paper, we identify a pathological condition for this algorithm: the presence of spin-flip symmetry in the problem instance. Spin-flip symmetry is the invariance of a pseudo-Boolean function to complementation. Many important combinatorial optimization problems admit objective functions that exhibit this pathology, such as graph problems, Ising models, and variants of propositional satisfiability. We prove that no population size exists that allows the majority vote technique to solve spin-flip symmetric functions of unitation with reasonable probability. To remedy this, we introduce a symmetry-breaking technique that allows the majority vote algorithm to overcome this issue for many landscapes. This technique requires only a minor modification to the original majority vote algorithm to force it to sample strings in {0,1}n from a dimension n-1 hyperplane. We prove a sufficient condition for a spin-flip symmetric function to possess in order for the symmetry-breaking voting algorithm to succeed, and prove its efficiency on generalized TwoMax, a spin-flip symmetric variant of Jump, and families of constructed 3-NAE-SAT and 2-XOR-SAT formulas. We also prove that the algorithm fails on the one-dimensional Ising model, and suggest different techniques for overcoming this. Finally, we present empirical results that explore the tightness of the runtime bounds and the performance of the technique on randomized satisfiability variants.

Many optimization problems tackled by evolutionary algorithms are not only computationally expensive, but also complicated with one or more sources of noise. One technique to deal with high computational overhead is parallelization. However, though the existing literature gives good insights about the expected behavior of parallelized evolutionary algorithms, we still lack an understanding of their performance in the presence of noise.

A graceful labeling of a graph G = (V, E) is an assignment of labels to the vertices V of G subject to constraints arising from the structure of the graph. A graph is called graceful if it admits a graceful labeling. As a combinatorial problem, it has applications in coding theory, communications networks, and optimizing circuit layouts. Several different approaches, both heuristic and complete, for finding graceful labelings have been developed and analyzed empirically. Most such algorithms have been established in the context of verifying the conjecture that trees are graceful.

Repair operators are often used for constraint handling in constrained combinatorial optimization. We investigate the (1+1) EA equipped with a tailored jump-and-repair operation that can be used to probabilistically repair infeasible offspring in graph problems. Instead of evolving candidate solutions to the entire graph, we expand the genotype to allow the (1+1) EA to develop in parallel a feasible solution together with a growing subset of the instance (an induced subgraph). With this approach, we prove that the EA is able to probabilistically simulate an iterative compression process used in classical fixed-parameter algorithmics to obtain a randomized FPT performance guarantee on two NP-hard graph problems. For k-VertexCover, we prove that the (1+1) EA using focused jump-and-repair can find a k-cover (if one exists) in O(2k n2 log n) iterations in expectation. This leads to an exponential (in k) improvement over the best-known parameterized bound for evolutionary algorithms on VertexCover. For the k-FeedbackVertexSet problem in tournaments, we prove that the EA finds a feasible feedback set in O(2kk!n2 log n) iterations in expectation. This is the first parameterized result for an evolutionary algorithm on this problem. We discuss how to generalize the framework to other parameterized graph problems closed under induced subgraphs and report experimental results that illustrate the behavior of the algorithm on a concrete instance class.

Addressing a complex real-world optimization problem is a challenging task. The chance-constrained knapsack problem with correlated uniform weights plays an important role in the case where dependent stochastic components are considered. We perform runtime analysis of a randomized search algorithm (RSA) and a basic evolutionary algorithm (EA) for the chance-constrained knapsack problem with correlated uniform weights. We prove bounds for both algorithms for producing a feasible solution. Furthermore, we investigate the behaviour of the algorithms and carry out analyses on two settings: uniform profit value and the setting in which every group shares an arbitrary profit profile. We provide insight into the structure of these problems and show how the weight correlations and the different profit profiles influence the runtime behavior of both algorithms in the chance-constrained setting.

Submodular optimization plays a key role in many real-world problems. In many real-world scenarios, it is also necessary to handle uncertainty, and potentially disruptive events that violate constraints in stochastic settings need to be avoided. In this paper, we investigate submodular optimization problems with chance constraints. We provide a first analysis on the approximation behavior of popular greedy algorithms for submodular problems with chance constraints. Our results show that these algorithms are highly effective when using surrogate functions that estimate constraint violations based on Chernoff bounds. Furthermore, we investigate the behavior of the algorithms on popular social network problems and show that high quality solutions can still be obtained even if there are strong restrictions imposed by the chance constraint.

There exist general transforms that convert pseudo-Boolean functions into k-bounded pseudo-Boolean functions, for all k ≥ 2. In addition to these general transforms, there can also exist specialized transforms that can be applied in special cases. New results are presented examining what happens to the "bit flip" neighborhood when transforms are applied. Transforms condense variables in a particular order. We show that different variable orderings produce different results in terms of problem difficulty. We also prove new results about the embedding of the original function in the new k-bounded function. Finally, this paper also looks at how parameter optimization problems can be expressed as high precision k-bounded pseudo-Boolean functions. This paper lays a foundation for the wider application of evolutionary algorithms to k-bounded pseudo-Boolean functions.

We study the ability of a simple mutation-only evolutionary algorithm to solve propositional satisfiability formulas with inherent community structure. We show that the community structure translates to good fitness-distance correlation properties, which implies that the objective function provides a strong signal in the search space for evolutionary algorithms to locate a satisfying assignment efficiently. We prove that when the formula clusters into communities of size s ∈ ω(logn) ∩O(nε/(2ε+2)) for some constant 0

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.

Due to their randomized nature, many nature-inspired heuristics are robust to some level of noise in the fitness evaluations. A common strategy to increase the tolerance to noise is to re-evaluate the fitness of a solution candidate several times and to then work with the average of the sampled fitness values. In this work, we propose to use the median instead of the mean. Besides being invariant to rescalings of the fitness, the median in many situations turns out to be much more robust than the mean. We show that when the noisy fitness is ϵ-concentrated, then a logarithmic number of samples suffice to discover the undisturbed fitness (via the median of the samples) with high probability. This gives a simple metaheuristic approach to transform a randomized optimization heuristics into one that is robust to this type of noise and that has a runtime higher than the original one only by a logarithmic factor. We show further that ϵ-concentrated noise occurs frequently in standard situations. We also provide lower bounds showing that in two such situations, even with larger numbers of samples, the average-resample strategy cannot efficiently optimize the problem in polynomial time.

The runtime analysis of evolutionary algorithms using crossover as search operator has recently produced remarkable results indicating benefits and drawbacks of crossover and illustrating its working principles. Virtually all these results are restricted to upper bounds on the running time of the crossover-based algorithms. This work addresses this lack of lower bounds and rigorously bounds the optimization time of simple algorithms using uniform crossover on the search space {0, 1}n from below via two novel techniques called decoupling and family graphs. First, a simple steady-state crossover-based evolutionary algorithm without selection pressure is analyzed and shown that after O(µ log µ) generations, bit positions are sampled almost independently with marginal probabilities corresponding to the fraction of one-bits at the corresponding position in the initial population. Afterwards, a crossover-based algorithm using tournament selection is analyzed by a novel generalization of the family tree technique originally introduced for mutation-only EAs. Using these so-called family graphs, almost tight lower bounds on the optimization time on the OneMax benchmark function are shown.

The hardness of formulas at the solubility phase transition of random propositional satisfiability (SAT) has been intensely studied for decades both empirically and theoretically. Solvers based on stochastic local search (SLS) appear to scale very well at the critical threshold, while complete backtracking solvers exhibit exponential scaling. On industrial SAT instances, this phenomenon is inverted: backtracking solvers can tackle large industrial problems, where SLS-based solvers appear to stall. Industrial instances exhibit sharply different structure than uniform random instances. Among many other properties, they are often heterogeneous in the sense that some variables appear in many while others appear in only few clauses. We conjecture that the heterogeneity of SAT formulas alone already contributes to the trade-off in performance between SLS solvers and complete backtracking solvers. We empirically determine how the run time of SLS vs. backtracking solvers depends on the heterogeneity of the input, which is controlled by drawing variables according to a scale-free distribution. Our experiments reveal that the efficiency of complete solvers at the phase transition is strongly related to the heterogeneity of the degree distribution. We report results that suggest the depth of satisfying assignments in complete search trees is influenced by the level of heterogeneity as measured by a power-law exponent. We also find that incomplete SLS solvers, which scale well on uniform instances, are not affected by heterogeneity. The main contribution of this paper utilizes the scale-free random 3-SAT model to isolate heterogeneity as an important factor in the scaling discrepancy between complete and SLS solvers at the uniform phase transition found in previous works.

In the context of black box optimization, one of the most common ways to handle deceptive attractors is to periodically restart the algorithm. In this paper, we explore the benefits of combining the simple (1 + 1) Evolutionary Algorithm (EA) with the Luby Universal Strategy - the (1 + 1) EAu, a meta-heuristic that does not require parameter tuning.

Jump functions were originally introduced as benchmarks on which recombinant evolutionary algorithms can provably outperform those that use mutation alone. To optimize a jump function, an algorithm must be able to execute an initial hill-climbing phase, after which a point across a large gap must be generated. Standard GAs mix mutation and crossover to achieve both behaviors. It seems likely that other techniques, such as estimation of distribution algorithms (EDAs) may exhibit such behavior, but an analysis is so far missing.

We investigate the effect of crossover in the context of parameterized complexity on a well-known fixed-parameter tractable combinatorial optimization problem known as the closest string problem. We prove that a multi-start (μ+1) solves arbitrary length-n instances of closest string in 2O(d2+d log k). poly(n) steps in expectation. Here, k is the number of strings in the input set, and d is the value of the optimal solution. This confirms that the multi-start (μ+1) runs in randomized fixed-parameter tractable (FPT) time with respect to the above parameterization. On the other hand, if the crossover operation is disabled, we show there exist instances that require nΩ(log(d+k) steps in expectation. The lower bound asserts that crossover is a necessary component in the FPT running time.

Population diversity is essential for avoiding premature convergence in genetic algorithms (GAs) and for the effective use of crossover. Yet the dynamics of how diversity emerges in populations are not well understood. We use rigorous runtime analysis to gain insight into population dynamics and GA performance for the (μ + 1) GA and the Jump test function. We show that the interplay of crossover followed by mutation may serve as a catalyst leading to a sudden burst of diversity. This leads to significant improvements of the expected optimization time compared to mutation-only algorithms like the (1 + 1) evolutionary algorithm. Moreover, increasing the mutation rate by an arbitrarily small constant factor can facilitate the generation of diversity, leading to even larger speedups. Experiments were conducted to complement our theoretical findings and further highlight the benefits of crossover on the function class.

Recently, a number of non-uniform random satisfiability models have been proposed that are closer to practical satisfiability problems in some characteristics. In contrast to uniform random Boolean formulas, scale-free formulas have a variable occurrence distribution that follows a power law. It has been conjectured that such a distribution is a more accurate model for some industrial instances than the uniform random model. Though it seems that there is already an awareness of a threshold phenomenon in such models, there is still a complete picture lacking. In contrast to the uniform model, the critical density threshold does not lie at a single point, but instead exhibits a functional dependency on the power-law exponent. For scale-free formulas with clauses of length k=2, we give a lower bound on the phase transition threshold as a function of the scaling parameter. We also perform computational studies that suggest our bound is tight and investigate the critical density for formulas with higher clause lengths. Similar to the uniform model, on formulas with k>=3, we find that the phase transition regime corresponds to a set of formulas that are difficult to solve by backtracking search.

Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. The worst-case hardness of SAT lies at the core of computational complexity theory. The average-case analysis of SAT has triggered the development of sophisticated rigorous and non-rigorous techniques for analyzing random structures. Despite a long line of research and substantial progress, nearly all theoretical work on random SAT assumes a uniform distribution on the variables. In contrast, real-world instances often exhibit large fluctuations in variable occurrence. This can be modeled by a scale-free distribution of the variables, which results in distributions closer to industrial SAT instances. We study random k-SAT on n variables, $m=Θ(n)$ clauses, and a power law distribution on the variable occurrences with exponent $β$. We observe a satisfiability threshold at $β=(2k-1)/(k-1)$. This threshold is tight in the sense that instances with $β\le(2k-1)/(k-1)-\varepsilon$ for any constant $\varepsilon>0$ are unsatisfiable with high probability (w.h.p.). For $β\geq(2k-1)/(k-1)+\varepsilon$, the picture is reminiscent of the uniform case: instances are satisfiable w.h.p. for sufficiently small constant clause-variable ratios $m/n$; they are unsatisfiable above a ratio $m/n$ that depends on $β$.

Noise is pervasive in real-world optimization, but there is still little understanding of the interplay between the operators of randomized search heuristics and explicit noise-handling techniques, such as statistical resampling. In this paper, we report on several statistical models and theoretical results that help to clarify this reciprocal relationship for a collection of randomized search heuristics on noisy functions. We consider the optimization of pseudo-Boolean functions under additive posterior Gaussian noise and explore the trade-off between noise reduction and the computational cost of resampling. We first perform experiments to find the optimal parameters at a given noise intensity for a mutation-only evolutionary algorithm, a genetic algorithm employing recombination, an estimation of distribution algorithm (EDA), and an ant colony optimization algorithm. We then observe how the optimal parameter depends on the noise intensity for the different algorithms. Finally, we locate the point where statistical resampling costs more than it is worth in terms of run time. We find that the EA requires the highest number of resamples to obtain the best speed-up, whereas crossover reduces both the run time and the number of resamples required. Most surprisingly, we find that EDA-like algorithms require no resampling, and can handle noise implicitly.

Practical optimization problems frequently include uncertainty about the quality measure, for example, due to noisy evaluations. Thus, they do not allow for a straightforward application of traditional optimization techniques. In these settings, randomized search heuristics such as evolutionary algorithms are a popular choice because they are often assumed to exhibit some kind of resistance to noise. Empirical evidence suggests that some algorithms, such as estimation of distribution algorithms (EDAs) are robust against a scaling of the noise intensity, even without resorting to explicit noise-handling techniques such as resampling. In this paper, we want to support such claims with mathematical rigor. We introduce the concept of graceful scaling in which the run time of an algorithm scales polynomially with noise intensity. We study a monotone fitness function over binary strings with additive noise taken from a Gaussian distribution. We show that myopic heuristics cannot efficiently optimize the function under arbitrarily intense noise without any explicit noise-handling. Furthermore, we prove that using a population does not help. Finally, we show that a simple EDA called the compact genetic algorithm can overcome the shortsightedness of mutation-only heuristics to scale gracefully with noise. We conjecture that recombinative genetic algorithms also have this property.

Population diversity is essential for the effective use of any crossover operator. We compare seven commonly used diversity mechanisms and prove rigorous run time bounds for the (μ+1) GA using uniform crossover on the fitness function Jumpk. All previous results in this context only hold for unrealistically low crossover probability pc=O(k/n), while we give analyses for the setting of constant pc < 1 in all but one case. Our bounds show a dependence on the problem size~$n$, the jump length k, the population size μ, and the crossover probability pc. For the typical case of constant k > 2 and constant pc, we can compare the resulting expected optimisation times for different diversity mechanisms assuming an optimal choice of μ:

Recently, ant colony optimization (ACO) algorithms have proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses have focused on combinatorial problems such as path finding. We rigorously analyze an ACO algorithm optimizing linear pseudo-Boolean functions under additive posterior noise. We study noise distributions whose tails decay exponentially fast, including the classical case of additive Gaussian noise. Without noise, the classical [Formula: see text] EA outperforms any ACO algorithm, with smaller [Formula: see text] being better; however, in the case of large noise, the [Formula: see text] EA fails, even for high values of [Formula: see text] (which are known to help against small noise). In this article, we show that ACO is able to deal with arbitrarily large noise in a graceful manner; that is, as long as the evaporation factor [Formula: see text] is small enough, dependent on the variance [Formula: see text] of the noise and the dimension n of the search space, optimization will be successful. We also briefly consider the case of prior noise and prove that ACO can also efficiently optimize linear functions under this noise model.

With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3-SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann [PPSN 2014, 942--951] in three ways. First, we reduce the upper bound by a linear factor and prove that the (1+1) EA obtains optimal solutions in time $O(n \log n)$ with high probability on asymptotically almost all high-density satisfiable 3-CNF formulas. Second, we extend the range of densities for which this bound holds to satisfiable formulas of at least logarithmic density. Finally, we complement these mathematical results with numerical experiments that summarize the behavior of the (1+1) EA on formulas along the density spectrum, and suggest that the implicit constants hidden in our bounds are low. Our proofs are based on analyzing the run of the algorithm by establishing a fitness-distance correlation. This approach might be of independent interest and we are optimistic that it is useful for the analysis of randomized search heuristics in various other settings. To our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.

Recently Ant Colony Optimization (ACO) algorithms have been proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses focus on combinatorial problems, such as path finding.

Bit-flip mutation is a common mutation operator for evolutionary algorithms applied to optimize functions over binary strings. In this paper, we develop results from the theory of landscapes and Krawtchouk polynomials to exactly compute the probability distribution of fitness values of a binary string undergoing uniform bit-flip mutation. We prove that this probability distribution can be expressed as a polynomial in p, the probability of flipping each bit. We analyze these polynomials and provide closed-form expressions for an easy linear problem (Onemax), and an NP-hard problem, MAX-SAT. We also discuss a connection of the results with runtime analysis.

The theory of evolutionary computation (EC) has experienced rapid and productive growth in recent years. New proof techniques and novel theoretical frameworks have allowed advances in our understanding of the processes and structures inherent in evolutionary optimization. As a result, the frontiers of our knowledge have been expanded further than ever before. Some recent trends in this field, which are covered in this issue, include developments in the understanding of the behavior of evolutionary algorithms (EAs) in dynamic environments rather than just static settings, a theoretical appreciation of the advantages arising from the parallelization of evolutionary algorithms through a greater comprehension of the underlying dynamics, and an understanding of algorithm behavior on broad function classes, including -hard problems.The primary goal of this special issue is to provide extended and polished versions of diverse examples of the best theoretical work presented at conferences in 2014, and to serve as a forum for researchers to advance the theoretical understanding of evolutionary computation methods. The papers included in this special issue span a plurality of topics and offer the reader a cross section of recent outstanding work in EC theory.In dynamic optimization the objective function changes over time, and optimization algorithms face the additional challenge of tracking these changes to be successful. The article “Analysis of Randomised Search Heuristics for Dynamic Optimisation,” by Thomas Jansen and Christine Zarges, presents a novel analytical framework for the analysis of randomized search heuristics on dynamic problems inspired by the fixed-budget computations perspective. The authors introduce a new interesting class of bi-stable dynamic functions where the optimum oscillates between two complementary strings, and apply the framework to analyze and compare the performance of evolutionary algorithms and artificial immune systems on the novel class of functions.Over three decades ago, László Lovász observed that in discrete optimization, submodularity is the counterpart to convexity. However, in contrast to the focus on convex functions in continuous evolutionary optimization, so far submodular functions have received comparatively little attention from EC theoreticians studying discrete functions. The article “Maximizing Submodular Functions under Matroid Constraints by Evolutionary Algorithms,” by Tobias Friedrich and Frank Neumann, addresses this gap by analyzing the performance of evolutionary algorithms on different classes of submodular functions. The maximization of submodular functions is -hard in general, and the authors present several approximation results for monotone submodular and nonmonotone symmetric submodular functions under different kinds of matroid constraints.The idea behind parallel evolutionary algorithms is to evolve multiple subpopulations in parallel and allow interprocess communication at given time intervals. During these migration phases, fractions of each subpopulation can be shared among the subpopulations. There is very little understanding of how the migration frequency affects algorithmic performance, so setting the migration interval parameter appropriately may be difficult. In the article “Design and Analysis of Schemes for Adapting Migration Intervals in Parallel Evolutionary Algorithms,” Andrea Mambrini and Dirk Sudholt propose two schemes to automatically adapt the migration interval of parallel EAs during execution and provide a rigorous analytical framework that yields upper bounds on the expected runtime and expected communication effort of the parallel EAs with different migration topologies for various function classes.In the field of genetic programming, a long-standing open problem is how to address the issue of bloat, the emergence during evolution of solution elements that do not contribute significantly or at all to program fitness or semantics but increase program complexity. The article “On the Performance of Different Genetic Programming Approaches for the SORTING Problem,” by Markus Wagner, Frank Neumann, and Tommaso Urli, tackles the issue of bloat control in the context of sorting. As a basis for their study, they consider program trees and use some measure of sortedness of an in-order traversal to evaluate their fitness. The authors investigate single- and multiobjective variants of genetic programming algorithms with and without bloat control mechanisms, give rigorous upper bounds on their running times, and complement the study with experiments.The topic of constraint handling has recently gained traction in the continuous domain. The article “Markov Chain Analysis of Cumulative Step-Size Adaptation on a Linear Constrained Problem,” by Alexandre Chotard, Anne Auger, and Nikolaus Hansen, presents a rigorous analysis of a (1,)-Evolution Strategy using resampling on a linear function with a linear constraint. The authors prove the previously assumed property that a Markov chain, describing the behavior of the algorithm, exhibits stability in cases with constant step-size and with cumulative step-size adaptation with cumulation parameter equal to 1. This property characterizes the divergence of the algorithm with constant step-size and the geometric divergence or convergence with step-size adaptation, implying fast convergence of Monte Carlo simulations of the divergence rate.In their seminal 2006 paper, Droste, Jansen, and Wegener introduced the concept of black box complexity in order to establish a complexity theory for general-purpose randomized search heuristics. Generally speaking, the black box complexity of a problem is a lower bound on the number of function evaluations needed by any black box algorithm to solve it. Recently, black box models have been refined and developed extensively, allowing the hardness of objective function classes to be more precisely understood. The article “Unbiased Black Box Complexities of Jump Functions,” by Benjamin Doerr, Carola Doerr, and Timo Kötzing, analyzes the unbiased black box complexity of a Jump function class where in each function a local optimum is k bits in distance from the global optimum. The authors provide polynomial upper bounds on the black box complexity of Jump for different sizes of the gap. In particular, they show that an unbiased polynomial-time black box algorithm exists even when almost all of the search space is a plateau of constant fitness.The guest editors would like to thank the authors for their contributions, the referees for their careful reviewing and constructive comments, and the editor-in-chief, Hans-Georg Beyer, for his support in preparing this special issue.

Hill climbing algorithms are at the core of many approaches to solve optimization problems. Such algorithms usually require the complete enumeration of a neighborhood of the current solution. In the case of problems defined over binary strings of length n, we define the r-ball neighborhood as the set of solutions at Hamming distance r or less from the current solution. For r ll n this neighborhood contains Θ(nr) solutions. In this paper efficient methods areintroduced to locate improving moves in the r-ball neighborhood for problems that can be written as a sum of a linear number of subfunctions depending on a bounded number of variables. NK-landscapes and MAX-kSAT are examples of these problems. If the number of subfunctions depending on any given variable is also bounded, then we prove that the method can explore the neighborhood in constant time, despite the fact that the number of solutions in the neighborhood is polynomial in n. We develop a hill climber based on our exploration method and we analyze its efficiency and efficacy using experiments with NKq-landscapes instances.

The (1+1) EA is a simple evolutionary algorithm that is known to be efficient on linear functions and on some combinatorial optimization problems. In this paper, we rigorously study its behavior on two easy combinatorial problems: finding the 2-coloring of a class of bipartite graphs, and constructing satisfying assignments for a class of satisfiable 2-CNF Boolean formulas. We prove that it is inefficient on both problems in the sense that the number of iterations the algorithm needs to minimize the cost functions is superpolynomial with high probability. Our motivation is to better understand the influence of problem instance structure on the runtime character of a simple evolutionary algorithm. We are interested in what kind of structural features give rise to so-called metastable states at which, with probability 1 - o(1), the (1+1) EA becomes trapped and subsequently has difficulty leaving. Finally, we show how to modify the (1+1) EA slightly in order to obtain a polynomial-time performance guarantee on both problems.

Parameterized runtime analysis seeks to understand the influence of problem structure on algorithmic runtime. In this paper, we contribute to the theoretical understanding of evolutionary algorithms and carry out a parameterized analysis of evolutionary algorithms for the Euclidean traveling salesperson problem (Euclidean TSP). We investigate the structural properties in TSP instances that influence the optimization process of evolutionary algorithms and use this information to bound their runtime. We analyze the runtime in dependence of the number of inner points k. In the first part of the paper, we study a [Formula: see text] EA in a strictly black box setting and show that it can solve the Euclidean TSP in expected time [Formula: see text] where A is a function of the minimum angle [Formula: see text] between any three points. Based on insights provided by the analysis, we improve this upper bound by introducing a mixed mutation strategy that incorporates both 2-opt moves and permutation jumps. This strategy improves the upper bound to [Formula: see text]. In the second part of the paper, we use the information gained in the analysis to incorporate domain knowledge to design two fixed-parameter tractable (FPT) evolutionary algorithms for the planar Euclidean TSP. We first develop a [Formula: see text] EA based on an analysis by M. Theile, 2009, "Exact solutions to the traveling salesperson problem by a population-based evolutionary algorithm," Lecture notes in computer science, Vol. 5482 (pp. 145-155), that solves the TSP with k inner points in [Formula: see text] generations with probability [Formula: see text]. We then design a [Formula: see text] EA that incorporates a dynamic programming step into the fitness evaluation. We prove that a variant of this evolutionary algorithm using 2-opt mutation solves the problem after [Formula: see text] steps in expectation with a cost of [Formula: see text] for each fitness evaluation.

Recently, Sutton and Neumann [1] have studied evolutionary algorithms for the Euclidean traveling salesman problem by parameterized runtime analyses taking into account the number of inner points k and the number of cities n. They have shown that simple evolutionary algorithms are XP-algorithms for the problem, i.e., they obtain an optimal solution in expected time O(ng(k)) where g(k) is a function only depending on k. We extend these investigations and design two evolutionary algorithms for the Euclidean Traveling Salesperson problem that run in expected time g(k) · poly(n) where k is a parameter denoting the number inner points for the given TSP instance, i.e., they are fixed-parameter tractable evolutionary algorithms for the Euclidean TSP parameterized by the number of inner points. While our first approach is mainly of theoretical interest, our second approach leverages problem structure by directly searching for good orderings of the inner points and provides a novel and highly effective way of tackling this important problem. Our experimental results show that searching for a permutation on the inner points is a significantly powerful practical strategy.

We propose a new construction procedure for ant colony optimization (ACO) algorithms working on the Euclidean traveling salesperson problem (TSP) that preserves the ordering on the convex hull of the points in the instance. The procedure is inspired by theoretical analyses for simple evolutionary algorithms that are provably more efficient on instances where the number of inner points of the instance is not too large. We integrate the construction procedure into the well-known MaxMin Ant System (MMAS) and empirically show that it leads to more efficient optimization on instances where the number of inner points is not too high.

Using the hypervolume indicator to guide the search of evolutionary multi-objective algorithms has become very popular in recent years. We contribute to the theoretical understanding of these algorithms by carrying out rigorous runtime analyses. We consider multi-objective variants of the problems OneMax and LeadingOnes called OMM and LOTZ, respectively, and investigate hypervolume-based algorithms with population sizes that do not allow coverage of the entire Pareto front. Our results show that LOTZ is easier to optimize than OMM for hypervolume-based evolutionary multi-objective algorithms which is contrary to the results on their single-objective variants and the well-studied (1+1)~EA.

The frequency distribution of a fitness function over regions of its domain is an important quantity for understanding the behavior of algorithms that employ randomized sampling to search the function. In general, exactly characterizing this distribution is at least as hard as the search problem, since the solutions typically live in the tails of the distribution. However, in some cases it is possible to efficiently retrieve a collection of quantities (called moments) that describe the distribution. In this paper, we consider functions of bounded epistasis that are defined over length-n strings from a finite alphabet of cardinality q. Many problems in combinatorial optimization can be specified as search problems over functions of this type. Employing Fourier analysis of functions over finite groups, we derive an efficient method for computing the exact moments of the frequency distribution of fitness functions over Hamming regions of the q-ary hypercube. We then use this approach to derive equations that describe the expected fitness of the offspring of any point undergoing uniform mutation. The results we present provide insight into the statistical structure of the fitness function for a number of combinatorial problems. For the graph coloring problem, we apply our results to efficiently compute the average number of constraint violations that lie within a certain number of steps of any coloring. We derive an expression for the mutation rate that maximizes the expected fitness of an offspring at each fitness level. We also apply the results to the slightly more complex frequency assignment problem, a relevant application in the domain of the telecommunications industry. As with the graph coloring problem, we provide formulas for the average value of the fitness function in Hamming regions around a solution and the expectation-optimal mutation rate.

We contribute to the theoretical understanding of evolutionary algorithms and carry out a parameterized analysis of evolutionary algorithms for the Euclidean traveling salesperson problem (Euclidean TSP). We exploit structural properties related to the optimization process of evolutionary algorithms for this problem and use them to bound the runtime of evolutionary algorithms. Our analysis studies the runtime in dependence of the number of inner points $k$ and shows that simple evolutionary algorithms solve the Euclidean TSP in expected time O(nk(2k-1)!). Moreover, we show that, under reasonable geometric constraints, a locally optimal 2-opt tour can be found by randomized local search in expected time $O(n2kk!).

This paper contributes to the rigorous understanding of genetic programming algorithms by providing runtime complexity analyses of the well-studied Max problem. Several experimental studies have indicated that it is hard to solve the Max problem with crossover-based algorithms. Our analyses show that different variants of the Max problem can provably be solved using simple mutation-based genetic programming algorithms.

We investigate the MAX-2-SAT problem and study evolutionary algorithms by parameterized runtime analysis. The parameterized runtime analysis of evolutionary algorithms has been initiated recently and reveals new insights into which type of instances of NP-hard combinatorial optimization problems are hard to solve by evolutionary computing methods. We show that a variant of the (1+1) EA is a fixed-parameter evolutionary algorithm with respect to the standard parameterization for MAX-2-SAT. Furthermore, we study how the dependencies between the variables affect problem difficulty and present fixed-parameter evolutionary algorithms for the MAX-(2,3)-SAT problem where the studied parameter is the diameter of the variable graph.

When the epistasis of the fitness function is bounded by a constant, we show that the expected fitness of an offspring of the (1+1)-EA can be efficiently computed for any point. Moreover, we show that, for any point, it is always possible to efficiently retrieve the "best" mutation rate at that point in the sense that the expected fitness of the resulting offspring is maximized. On linear functions, it has been shown that a mutation rate of 1/n is provably optimal. On functions where epistasis is bounded by a constant k, we show that for sufficiently high fitness, the commonly used mutation rate of 1/n is also best, at least in terms of maximizing the expected fitness of the offspring. However, we find for certain ranges of the fitness function, a better mutation rate can be considerably higher, and can be found by solving for the real roots of a degree-k polynomial whose coefficients contain the nonzero Walsh coefficients of the fitness function. Simulation results on maximum k-satisfiability problems and NK-landscapes show that this expectation-maximized mutation rate can cause significant gains early in search.

A tool supporting the automatic identification of programming idioms specific to the construction of C++ generic libraries is presented. The goal is to assist developers in understanding the complex syntactic elements of these libraries. Large C++ generic libraries are notorious for being extremely difficult to comprehend due to their use of advanced language features and idiomatic nature. To facilitate automated identification, the idioms are equated to micropatterns, which can be evaluated by a fact extractor. These micropattern instances act as beacons for the idioms being identified. The method is applied to study a number of widely used open source C++ generic libraries.

Local search algorithms for MAX-k-SAT must often explore large regions of mutually connected equal moves, or plateaus, typically by taking random walks through the region. In this paper, we develop a surrogate plateau "gradient" function using a Walsh transform of the objective function. This function gives the mean value of the objective function over localized volumes of the search space. This information can be used to direct search through plateaus more quickly. The focus of this paper is on demonstrating that formal analysis of search space structure can direct existing algorithms in a more principled manner than random walks. We show that embedding the gradient computation into a hill-climbing local search for MAX-k-SAT improves its convergence profile.

The autocorrelation function and related correlation length are statistical quantities that capture the ruggedness of the fitness landscape: a measure that is directly related to the hardness of a problem for certain heuristic search algorithms. Typically, these quantities are estimated empirically by sampling along a random walk. In this paper, we show that a polynomial-time Walsh decomposition of the k-satisfiability evaluation function allows us to compute the exact autocorrelation function and correlation length for any given k-satisfiability instance. We also use the decomposition to compute a theoretical expectation for the autocorrelation function and correlation length over the ensemble of instances generated uniformly at random. We find that this expectation is invariant to the constrainedness of the problem as measured by the ratio of clauses to variables. However, we show that filtered problems, which are typically used in local search studies, have a bias that causes a significant deviation from the expected correlation structure of unfiltered, uniformly generated problems.

This paper introduces a new component based model that makes it relatively simple to prove that certain types of landscapes are elementary. We use the model to reconstruct proofs for the Traveling Salesman Problem, Graph Coloring and Min-Cut Graph Partitioning. The same model is then used to efficiently compute the average values over particular partial neighborhoods for these same problems. For Graph Coloring and Min-Cut Graph Partitioning, this computation can be used to focus search on those moves that are most likely to yield an improving move, ignoring moves that cannot yield an improving move. Let x be a candidate solution with objective function value f(x). The mean value of the objective function over the entire landscape is denoted f. Normally in an elementary landscape one can only be sure that a neighborhood includes an improving move (assuming minimization) if f(x) > f. However, by computing the expected value of an appropriate partial neighborhood it is sometimes possible to know that an improving move exists in the partial neighborhood even when f(x) < f.

A source code model that supports the static analysis of C++ templates and template metaprograms is presented. Analogous to techniques for object-oriented and procedural software (e.g., the abstraction of call graphs, inheritance hierarchies, etc.), this model provides a basis for maintenance concerns such as program comprehension, fact extraction, and impact analysis of generic code. The source code model is used to derive the template instantiation graph, and potential applications of this model discussed. An application to reverse engineer this model from source code is described.

The landscape formalism unites a finite candidate solution set to a neighborhood topology and an objective function. This construct can be used to model the behavior of local search on combinatorial optimization problems. A landscape is elementary when it possesses a unique property that results in a relative smoothness and decomposability to its structure. In this paper we explain elementary landscapes in terms of the expected value of solution components which are transformed in the process of moving from an incumbent solution to a neighboring solution. We introduce new results about the properties of elementary landscapes and discuss the practical implications for search algorithms.

An automated approach to the identification of C++0x concepts in function templates is described. Concepts are part of a new language feature appearing in the next standard for C++ (i.e., C++0x). Concept identification is the enumeration of constraints on the sets of types over which templates can be instantiated. The approach analyzes template source code and computes a set of viable concept instances describing the implied data abstraction of the template parameters. The approach is evaluated on generic algorithms defined in the C++ Standard Template Library (STL). The evaluation demonstrates the effectiveness of the approach. The approach can be used to assist in reengineering existing generic libraries to C++0x. Additionally, it has the potential to assist in the validation of concept hierarchies and interface definition in generic libraries.

Recent results show that the Differential Evolution algorithm has significant difficulty on functions that are not linearly separable. On such functions, the algorithm must rely primarily on its differential mutation procedure which, unlike its recombination strategy, is rotationally invariant. We conjecture that this mutation strategy lacks sufficient selective pressure when appointing parent and donor vectors to have satisfactory exploitative power on non-separable functions. We find that imposing pressure in the form of rank-based differential mutation results in a significant improvement of exploitation on rotated benchmarks.

An in-depth investigation of C preprocessor usage for portability and configuration management is presented. Three heavily-ported and widely used C++ libraries are examined. A core set of header files responsible for configuration management is identified in each system. Then macro usage is extracted and analyzed both manually and with the help of program analysis tools. The configuration structure of each library is discussed in details and commonalities between the systems, including conventions and patterns are discussed. A common configuration architecture for managing portability concerns is derived and presented.

Heterogeneous distributed computing systems often must operate in an environment where system parameters are subject to uncertainty. Robustness can be defined as the degree to which a system can function correctly in the presence of parameter values different from those assumed. We present a methodology for quantifying the robustness of resource allocations in a dynamic environment where task execution times are stochastic. The methodology is evaluated through measuring the robustness of three different resource allocation heuristics within the context of a stochastic dynamic environment. A Bayesian regression model is fit to the combined results of the three heuristics to demonstrate the correlation between the stochastic robustness metric and the presented performance metric. The correlation results demonstrated the significant potential of the stochastic robustness metric to predict the relative performance of the three heuristics given a common objective function.

Particle Swarm Optimization (PSO) is a population-based optimization method in which search points employ a cooperative strategy to move toward one another. In this paper we show that PSO appears to work well on optimization functions. On more complex optimization problems, PSO tends to converge too quickly and then fail to make further progress. We contend that most benchmarks for PSO have classically been demonstrated on single-funnel functions. However, in practice, optimization tasks are more complex and possess higher problem dimensionality. We present empirical results that support our conjecture that PSO performs well on single-funnel functions but tends to stagnate on more complicated landscapes.

This paper presents a hybrid approach to detect source-code clones that combines evolutionary algorithms and clustering. A case-study is conducted on a small C++ code base. The preliminary investigation indicates that such an approach is effective in detecting groups of source-code clones.

The concept of model slicing is introduced as a means to support maintenance through the understanding, querying, and analysis of large UML models. The specific models being examined are class models as defined in the Unified Modeling Language (UML). Model slicing is analogous to classical program slicing. Since UML class models do not explicitly embody any behavioral aspect by themselves, models slices are computed in a context-free manner. The paper defines and formalizes the concept of context-free model slicing. A concrete application of model slicing in software maintenance is presented to support the usefulness and validity of the method.