Traffic in datacenters may follow some pattern: some pairs of servers communicate more frequently than others. Demand-oblivious networks may perform poorly for such workloads, and demand-aware networks optimized for traffic should be used instead. Unfortunately, not all shapes of networks are feasible in real hardware. Practical limitations are usually provided in the form of a topology. For example, a network may be required to be a binary tree, a bounded-degree graph or a Fat tree.

The mathematical runtime analysis of evolutionary algorithms traditionally regards the time an algorithm needs to find a solution of a certain quality when initialized with a random population. In practical applications it may be possible to guess solutions that are better than random ones. We start a mathematical runtime analysis for such situations. We observe that different algorithms profit to a very different degree from a better initialization. We also show that the optimal parameterization of an algorithm can depend strongly on the quality of the initial solutions. To overcome this difficulty, self-adjusting and randomized heavy-tailed parameter choices can be profitable. Finally, we observe a larger gap between the performance of the best evolutionary algorithm we found and the corresponding black-box complexity. This could suggest that evolutionary algorithms better exploiting good initial solutions are still to be found. These first findings stem from analyzing the performance of the \((1+1)\) evolutionary algorithm and the static, self-adjusting, and heavy-tailed \((1+(\lambda,\lambda))\) genetic algorithms on the OneMax benchmark. We are optimistic that the question of how to profit from good initial solutions is interesting beyond these first examples.

Abstract Most evolutionary algorithms have multiple parameters and their values drastically affect the performance. Due to the often complicated interplay of the parameters, setting these values right for a particular problem (parameter tuning) is a challenging task. This task becomes even more complicated when the optimal parameter values change significantly during the run of the algorithm since then a dynamic parameter choice (parameter control) is necessary. In this work, we propose a lazy but effective solution, namely choosing all parameter values (where this makes sense) in each iteration randomly from a suitably scaled power-law distribution. To demonstrate the effectiveness of this approach, we perform runtime analyses of the $$(1+(\lambda ,\lambda ))$$ ( 1 + ( λ , λ ) ) genetic algorithm with all three parameters chosen in this manner. We show that this algorithm on the one hand can imitate simple hill-climbers like the $$(1+1)$$ ( 1 + 1 ) EA, giving the same asymptotic runtime on problems like OneMax, LeadingOnes, or Minimum Spanning Tree. On the other hand, this algorithm is also very efficient on jump functions, where the best static parameters are very different from those necessary to optimize simple problems. We prove a performance guarantee that is comparable to the best performance known for static parameters. For the most interesting case that the jump size k is constant, we prove that our performance is asymptotically better than what can be obtained with any static parameter choice. We complement our theoretical results with a rigorous empirical study confirming what the asymptotic runtime results suggest.

Dynamic Algorithm Configuration (DAC) tackles the question of how to automatically learn policies to control parameters of algorithms in a data-driven fashion. This question has received considerable attention from the evolutionary community in recent years. Having a good benchmark collection to gain structural understanding on the effectiveness and limitations of different solution methods for DAC is therefore strongly desirable. Following recent work on proposing DAC benchmarks with well-understood theoretical properties and ground truth information, in this work, we suggest as a new DAC benchmark the controlling of the key parameter λ in the (1 + (λ, λ)) Genetic Algorithm for solving OneMax problems. We conduct a study on how to solve the DAC problem via the use of (static) automated algorithm configuration on the benchmark, and propose techniques to significantly improve the performance of the approach. Our approach is able to consistently outperform the default parameter control policy of the benchmark derived from previous theoretical work on sufficiently large problem sizes. We also present new findings on the landscape of the parameter-control search policies and propose methods to compute stronger baselines for the benchmark via numerical approximations of the true optimal policies.

Many discrete optimization problems feature plateaus, which are hard to evolutionary algorithms due to the lack of fitness guidance. While higher mutation rates may assist in making a jump from the plateau to some better search point, an algorithm typically performs random walks on a plateau, possibly with some assistance from diversity mechanisms. The vertex cover problem is one of the important NP-hard problems. We found that the recently proposed$(1+(\lambda, \lambda))$genetic algorithm solves certain instances of this problem, including those that are hard to heuristic solvers, much faster than simpler mutation-only evolutionary algorithms. Our theoretical analysis shows that there exists an intricate interplay between the problem structure and the way crossovers are used. It results in a drift towards the points where finding the next improvement is much easier. While this condition is formally proven only on one class of instances and for a subset of search points, experiments show that it is responsible for performance improvements in a much larger range of cases.

With the goal to provide absolute lower bounds for the best possible running times that can be achieved by (1 + λ)-type search heuristics on common benchmark problems, we recently suggested a dynamic programming approach that computes optimal expected running times and the regret values inferred when deviating from the optimal parameter choice.Our previous work is restricted to problems for which transition probabilities between different states can be expressed by relatively simple mathematical expressions. With the goal to cover broader sets of problems, we suggest in this work an extension of the dynamic programming approach to settings in which it may be difficult or impossible to compute the transition probabilities exactly, but it is possible to approximate them numerically, up to arbitrary precision, by Monte Carlo sampling.We apply our hybrid Monte Carlo dynamic programming approach to a concatenated jump function and demonstrate how the obtained bounds can be used to gain a deeper understanding into parameter control schemes.

Most evolutionary algorithms have multiple parameters and their values drastically affect the performance. Due to the often complicated interplay of the parameters, setting these values right for a particular problem is a challenging task. This task becomes even more complicated when the optimal parameter values change significantly during the run of the algorithm since then a dynamic parameter choice is necessary.

Most evolutionary algorithms have parameters, which allow a great flexibility in controlling their behavior and adapting them to new problems. To achieve the best performance, it is often needed to control some of the parameters during optimization, which gave rise to various parameter control methods. In recent works, however, similar advantages have been shown, and even proven, for sampling parameter values from certain, often heavy-tailed, fixed distributions. This produced a family of algorithms currently known as "fast evolution strategies" and "fast genetic algorithms".

The heavy-tailed mutation operator proposed in Doerr et al. (GECCO 2017), called fast mutation to agree with the previously used language, so far was successfully used only in purely mutation-based algorithms. There, it can relieve the algorithm designer from finding the optimal mutation rate and nevertheless obtain a performance close to the one that the optimal mutation rate gives.

Runtime analysis aims at contributing to our understanding of evolutionary algorithms through mathematical analyses of their runtimes. In the context of discrete optimization problems, runtime analysis classically studies the time needed to find an optimal solution. However, both from a practical and a theoretical viewpoint, more fine-grained performance measures are needed. Two complementary approaches have been suggested: fixed-budget analysis and fixed-target analysis.

Despite significant advantages in theory of evolutionary computation, many papers related to evolutionary algorithms still lack proper analysis and limit themselves by rather vague reflections on why making a certain design choice improves the performance. While this seems to be unavoidable when talking about the behavior of an evolutionary algorithm on a practical optimization problem, doing the same for computational complexities of parts of evolutionary algorithms is harmful and should be avoided.

Search-based software engineering aims to apply different search-based techniques to software engineering problems. Automation of software development is one such problem. In this paper we evaluate the permutation-based individual encoding for automatic reconstruction of measurement connections in a closed-loop control system using evolutionary algorithm and model checking. Using the permutation-based encoding greatly increases the difficulty of the considered problem, but makes it much closer to the real world scenarios. The results show that even the simple (1+1) evolutionary algorithm can successfully solve the realistic optimization problem with large search space size, although it struggles to find the optimal solution within reasonable time on the hardest problem instance.

Algebraic cryptanalysis studies breaking ciphers by solving algebraic equations. Some of the promising approaches use SAT solvers for this purpose. Although the corresponding satisfiability problems are hard, their difficulty can often be lowered by choosing a set of variables to brute force over, and by solving each of the corresponding reduced problems using a SAT solver, which is called the guess-and-determine attack. In many successful cipher breaking attempts this set was chosen analytically, however, the nature of the problem makes evolutionary computation a good choice.

Automation of software development is an actively researched problem. Search-based software engineering aims to apply various search-based techniques to software engineering problems. Recently we proposed the method for automatic generation of function block application using evolutionary algorithms and model checking and applied it to the problem of automatic generation of data connections in distributed control system. The aim of this paper is to further study this method on the problem of matching of input and output connections in a closed-loop plant-controller system. The computed fitness function distribution shows that the evaluated method successfully determines the correct input and output connections between the controller and the plant. Additionally, we evaluate how the composition of specification requirements in the fitness function affects the performance of the (1+1) evolutionary algorithm. We show that additional liveness formulas can improve the performance of the algorithm, while the introduction of safety formulas significantly decreases it.

We introduce generalized offline orthant search, an algorithmic framework that can be used to solve many problems coming from evolutionary multiobjective optimization using a common well-optimized algorithmic core and relatively cheap reduction procedures. The complexity of the core procedure is O(n · (log n)k-1) for n points of dimension k, and it has a good performance in practice.

The (1 + (λ, λ)) genetic algorithm, first proposed at GECCO 2013, showed a surprisingly good performance on some optimization problems. The theoretical analysis so far was restricted to the OneMax test function, where this GA profited from the perfect fitness-distance correlation. In this work, we conduct a rigorous runtime analysis of this GA on random 3-SAT instances in the planted solution model having at least logarithmic average degree, which are known to have a weaker fitness distance correlation.

We present an algorithm for incremental non-dominated sorting, a procedure to use with steady-state multiobjective algorithms, with the complexity of O(N(log N)M−2) for a single insertion, where N is the number of points and M is the number of objectives. This result generalizes the previously known O(N) algorithm designed for two objectives.

Automation of software development process has been a concern for a long time. Genetic programming is a well-known technique which uses evolutionary computation to generate or improve a computer program for a specific task without human participation. We consider the method which applies model checking and evolutionary computation towards the automatic generation of function block control applications for industrial automation systems. As a first step, we evaluate the effectiveness of a fitness function based on the number of satisfied computation tree logic formulas in UPPAAL query language for a manually created UPPAAL model. Results show that such fitness function and the (1+1) evolutionary algorithm can be successfully applied to generation of the required data connections in the IEC 61499 function block application.

The binary ε-indicator is often used to assess the quality of solutions in multiobjective optimization, and to perform optimization as well. It is normally evaluated using a straightforward θ(nmk) algorithm, where n and m are the number of solutions in the arguments, and k is the number of objectives. This is considered to be fast compared to, for example, the hypervolume indicator, which is #P-hard. However, there are efficient algorithms for the latter, especially for small values of k, while the ε-indicator evaluation is too slow already for n,m > 104 and for any k.

We analyze the unrestricted black-box complexity of the Jump function classes for different jump sizes. For upper bounds, we present three algorithms for small, medium, and extreme jump sizes. We prove a matrix lower bound theorem which is capable of giving better lower bounds than the classic information theory approach. Using this theorem, we prove lower bounds that almost match the upper bounds. For the case of extreme jump functions, which apart from the optimum reveal only the middle fitness value(s), we use an additional lower bound argument to show that any black-box algorithm does not gain significant insight about the problem instance from the first [Formula: see text] fitness evaluations. This, together with our upper bound, shows that the black-box complexity of extreme jump functions is [Formula: see text].

We perform theoretical analysis for a previously proposed method of enhancing performance of an evolutionary algorithm with reinforcement learning. The method adaptively chooses between auxiliary objectives in a single-objective evolutionary algorithm using reinforcement learning. We consider the Q-learning algorithm with ε-greedy strategy (ε > 0), using a benchmark problem based on ONEMAX. For the evolutionary algorithm, we consider the Random Local Search. In our setting, ONEMAX problem should be solved in the presence of the obstructive ZEROMAX objective. This benchmark tests the ability of the reinforcement learning algorithm to ignore such an inefficient objective. It was previously shown that in the case of the greedy strategy (ε = 0), the considered algorithm performs on the described benchmark problem in the best possible time for a conventional evolutionary algorithm. However, the ε-greedy strategy appears to perform in exponential time. Furthermore, every selection algorithm which selects an inefficient auxiliary objective with probability of at least δ is shown to be asymptotically inefficient when δ > 0 is a constant.

There exist optimization problems with the target objective, which is to be optimized, and several extra objectives, which can be helpful in the optimization process. The EA+RL method is designed to control optimization algorithms which solve problems with extra objectives. The method is based on the use of reinforcement learning for adaptive online selection of objectives.

To estimate performance of computer science algorithms reliably, one has to create worst-case execution time tests. For certain algorithms this task can be difficult. To reduce the amount of human effort, authors attempt using search-based optimization techniques, such as genetic algorithms. Our previous paper addressed test generation for several maximum flow algorithms. Genetic algorithms were applied for test generation and showed promising results. However, one of the aspects of maximum flow algorithm implementation was missing in that paper: parallel edges (edges which share source and target vertices) were not merged into one single edge (which is allowed in solving maximum flow problems). In this paper, parallel edge merging is implemented and new results are reported. A surprising fact is shown that fitness functions and choices of genetic operators which were the most efficient in the previous paper are much less efficient in the new setup and vice versa. What is more, the set of maximum flow algorithms, for which significantly better tests are generated, changed completely as well.

We propose a new algorithm for incremental nondominated sorting of two-dimensional points. The data structure which stores non-dominating layers is based on a tree of Cartesian trees. If there are N points in M layers, the running time for of an insertion is O(M(1 + log(N=M)) + log M log(N= log M)), which is O(N) in the worst case. This algorithm can be a basic building block for efficient implementations of steady-state multiobjective algorithms such as NSGA-II.

Genetic algorithms (GAs) are widely used in multi-objective optimization for solving complex problems. There are two distinct approaches for GA design: generational and steady-state algorithms. Most of the current state-of-the-art GAs are generational, although there is an increasing interest to steady-state algorithms as well. However, for algorithms based on non-dominated sorting, most of steady-state implementations have higher computation complexity than their generational counterparts, which limits their applicability. We present a fast implementation of a steady-state version of the NSGA-II algorithm for two dimensions. This implementation is based on a data structure which has O(N) complexity for single solution insertion and deletion in the worst case. The experimental results show that our implementation works noticeably faster than steady-state NSGA-II implementations which use fast non-dominated sorting.

We present our asynchronous implementation of the LM-CMA-ES algorithm, which is a modern evolution strategy for solving complex large-scale continuous optimization problems. Our implementation brings the best results when the number of cores is relatively high and the computational complexity of the fitness function is also high. The experiments with benchmark functions show that it is able to overcome its origin on the Sphere function, reaches certain thresholds faster on the Rosenbrock and Ellipsoid function, and surprisingly performs much better than the original version on the Rastrigin function.

There exist optimization problems with the target objective, which is to be optimized, and several extra objectives, which may or may not be helpful in the optimization process. This paper considers the case when it is possible to find an optimum of the target objective by optimizing either the target objective or a single extra objective. An algorithm is presented that uses a single instance of an underlying single-objective optimization algorithm to optimize different objectives at different iterations and restarts the optimization algorithm between optimizing different objectives. This algorithm has the expected running time of at most 4 K min O T O until an optimum of the target objective is found, where T O is the expected running time of the underlying optimization algorithm to find an optimum of the target objective by optimizing the objective O. An impact of not using restarts between iterations is also discussed.

The problem of protein conformation motion modeling is an open problem in the structural computational biology. It is difficult to solve it using methods of molecular dynamics or quantum physics because these methods deal with time intervals of nanoseconds or microseconds, while conformation motions take time of millisecond order. In addition, these methods cannot take external forces into consideration. To deal with these problems, numerous approximated and coarse-grained methods are developed, which use ideas from geometry and motion planning. We present a new coarse-grained method of modeling the protein motion between two given conformations. The method is based on optimization of a cost function similar to the one in the Monge-Kantorovich mass transfer problem. The optimization is performed using sep-CMA-ES, which makes the running time of an iteration linear in the number of amino acids in a protein. The proposed method is compared with some of the existing methods on several molecules. It is shown that the results of the proposed method are more accurate than of the other methods.

Consider optimization problems, where a target objective should be optimized. Some auxiliary objectives can be used to obtain the optimum of the target objective in less number of objective evaluations. We call such auxiliary objective a supporting one. Usually there is no prior knowledge about properties of auxiliary objectives, some objectives can be obstructive as well. What is more, an auxiliary objective can be both supporting and obstructive at different stages of the target objective optimization. Thus, an adaptive online method of objective selection is needed. Earlier, we proposed a method for doing that, which is based on reinforcement learning. In this paper, a new algorithm for adaptive online selection of optimization objectives is proposed. The algorithm meets the interface of a reinforcement learning agent, so it can be fit into the previously proposed framework. The new algorithm is applied for solving some benchmark problems with single-objective evolutionary algorithms. Specifically, Leading Ones with OneMax auxiliary objective is considered, as well as the MH-IFF problem. Experimental results are presented. The proposed algorithm outperforms Q-learning and random objective selection on the considered problems.

Efficiency of evolutionary algorithms can be increased by using auxiliary objectives. The method which is called EA+RL is considered. In this method a reinforcement learning (RL) algorithm is used to select objectives in evolutionary algorithms (EA) during optimization. In earlier studies, reinforcement learning algorithms for stationary environments were used in the EA+RL method. However, if behavior of auxiliary objectives change during the optimization process, it can be better to use reinforcement learning algorithms which are specially developed for non-stationary environments. In our previous work we proposed a new reinforcement learning algorithm to be used in the EA+RL method. In this work we propose an improved version of that algorithm. The new algorithm is applied to a non-stationary problem and compared with the methods which were used in other studies. It is shown that the proposed method achieves optimal value more often and obtains higher values of the target objective than the other algorithms.

In this paper a method of adaptive selection of helper-objectives in evolutionary algorithms, which was previously applied to model problems only, is applied to generation of test cases for programming challenge tasks. The method is based on reinforcement learning. Experiments show that the proposed method performs equally well compared to the best helper-objectives selected by hand.

Worst-case execution time tests can be tricky to create for various computer science algorithms. To reduce the amount of human effort, authors suggest using search-based optimization techniques, such as genetic algorithms. This paper addresses difficult test generation for several maximum flow algorithms from the augmenting path family. The presented results show that the genetic approach is reasonably good for the well-studied algorithms and superior for the capacity scaling algorithms. Moreover, tests which are generated against one algorithm seem to be hard for other algorithms of this family.

A first step towards analyzing runtime complexity of an evolutionary algorithm adaptively adjusted using reinforcement learning is made. We analyze the previously proposed EA + RL method that enhances single-objective optimization by selecting efficient auxiliary fitness functions. Precisely, Random Mutation Hill Climber adjusted with Q-learning using greedy exploration strategy is considered. We obtain both lower and upper bound for the number of fitness function evaluations needed for this EA + RL implementation to solve a modified OneMax problem. It turns out that EA + RL with an inefficient auxiliary fitness function performs on par with a conventional evolutionary algorithm, namely in Θ(N log N) fitness function evaluations, where N is the size of the OneMax problem. In other words, we show that reinforcement learning successfully ignores inefficient fitness function. A lower bound for the ε-greedy exploration strategy for ε > 0 is analyzed as well.

A single-objective optimization problem can be solved more efficiently by introducing some helper-objectives and running a multi-objective evolutionary algorithm. But what objectives should be used at each optimization stage? This paper describes a new method of adaptive helper-objectives selection in multi-objective evolutionary algorithms. The proposed method is applied to the Job-Shop scheduling problem and compared with the previously known approach, which was specially developed for the Job-Shop problem. A comparison with the previously proposed method of adaptive helper-objective selection based on reinforcement learning is performed as well.

In this paper, an automated method for generation of tests against inefficient solutions for programming challenge tasks on graph theory is proposed. The method is based on the use of (1+1) evolution strategy and is able to defeat several kinds of inefficient solutions. The proposed method was applied to a task from the Internet problem archive, the Timus Online Judge.

In this paper further investigation of the previously proposed method of speeding up single-objective evolutionary algorithms is done. The method is based on reinforcement learning which is used to choose auxiliary fitness functions. The requirements for this method are formulated. The compliance of the method with these requirements is illustrated on model problems such as Royal Roads problem and H-IFF optimization problem. The experiments confirm that the method increases the efficiency of evolutionary algorithms.

In this paper a previously proposed method of choosing auxiliary fitness functions is applied to adaptive selection of helper-objectives. Helper-objectives are used in evolutionary computation to enhance the optimization of the primary objective. The method based on choosing between objectives of a single-objective evolutionary algorithm with reinforcement learning is briefly described. It is tested on a model problem. From the results of the experiment, it can be concluded that the method allows to automatically select the most effective helper-objectives and ignore the ineffective ones. It is also shown that the proposed method outperforms multi-objective evolutionary algorithms, that were used with helper-objectives originally.