Randomized search heuristics have been applied successfully to a plethora of problems. This success is complemented by a large body of theoretical results. Unfortunately, the vast majority of these results regard problems with binary or continuous decision variables -- the theoretical analysis of randomized search heuristics for unbounded integer domains is almost nonexistent. To resolve this shortcoming, we start the runtime analysis of multi-objective evolutionary algorithms, which are among the most successful randomized search heuristics, for unbounded integer search spaces. We analyze single- and full-dimensional mutation operators with three different mutation strengths, namely changes by plus/minus one (unit strength), random changes following a law with exponential tails, and random changes following a power-law. The performance guarantees we prove on a recently proposed natural benchmark problem suggest that unit mutation strengths can be slow when the initial solutions are far from the Pareto front. When setting the expected change right (depending on the benchmark parameter and the distance of the initial solutions), the mutation strength with exponential tails yields the best runtime guarantees in our results -- however, with a wrong choice of this expectation, the performance guarantees quickly become highly uninteresting. With power-law mutation, which is an essentially parameter-less mutation operator, we obtain good results uniformly over all problem parameters and starting points. We complement our mathematical findings with experimental results that suggest that our bounds are not always tight. Most prominently, our experiments indicate that power-law mutation outperforms the one with exponential tails even when the latter uses a near-optimal parametrization. Hence, we suggest to favor power-law mutation for unknown problems in integer spaces.

The mutation process in evolution strategies has been interlinked with the normal distribution since its inception. Many lines of reasoning have been given for this strong dependency, ranging from maximum entropy arguments to the need for isotropy. However, some theoretical results suggest that other distributions might lead to similar local convergence properties. This paper empirically shows that a wide range of evolutionary strategies, from the (1+1)-ES to CMA-ES, show comparable optimization performance when using a mutation distribution other than the standard Gaussian. Replacing it with, e.g., uniformly distributed mutations, does not deteriorate the performance of ES, when using the default adaptation mechanism for the strategy parameters. We observe that these results hold not only for the sphere model but also for a wider range of benchmark problems.

Parameter control refers to the techniques that dynamically adapt the parameter values of the evolutionary algorithm during the optimization process, such as population size, crossover rate, or operator selection. Adaptation can improve the performance and robustness of the algorithm, however, parameter control mechanisms themselves need to be designed and configured carefully. With this article, we contribute a systematic investigation of an adaptive, multi-objective algorithm that is designed for the optimisation of problems in unbounded integer decision spaces. We find that (1) adaptation outperforms the best static configurations by 39–82 %, and (2) performance of the multi-objective algorithm is often independent of the adaptation scheme's initial configuration.

This article introduces a benchmarking framework that allows rigorous evaluation of parallel model-based optimizers for expensive functions. The framework establishes a relationship between estimated costs of parallel function evaluations (on real-world problems) to known sets of test functions. Such real-world problems are not always readily available (e.g., confidentiality and proprietary software). Therefore, new test problems are created by Gaussian process simulation. The proposed framework is applied in an extensive benchmark study to compare multiple state-of-the-art parallel optimizers with a novel model-based algorithm, which combines ideas of an explorative search for global model quality with parallel local searches to increase function exploitation. The benchmarking framework is used to configure good batch size setups for parallel algorithms systematically based on landscape properties. Furthermore, we introduce a proof of concept for a novel automatic batch size configuration. The predictive quality of the batch size configuration is evaluated on a large set of test functions and the functions generated by Gaussian process simulation. The introduced algorithm outperforms multiple state-of-the-art optimizers, especially on multimodal problems. Additionally, it proves to be particularly robust over various problem landscapes, and performs well with all tested batch sizes. Consequently, this makes it well suited for black-box kinds of problems.

AMUSE (Advanced MUSic Explorer) was created 2006 as an open-source Java framework for various music information retrieval tasks like feature extraction, feature processing, classification, and evaluation. In contrast to toolboxes which focus on individual MIR-related algorithms, it is possible with AMUSE, for instance, to extract features with Librosa, process them based on events estimated by MIRtoolbox, classify with WEKA or Keras, and validate the models with own classification performance measures. We present several substantial contributions to AMUSE since its first presentation at ISMIR 2010. They include the annotation editor for single and multiple tracks, the support of multi-label and multi-class classification, and new plugins which operate with Keras, Librosa, and Sonic Annotator. Other integrated methods are the structural complexity processing, chord vector feature, aggregation of features around estimated onset events, and evaluation of time event extractors. Further advancements are a more flexible feature extraction with different parameters like frame sizes, possibility to integrate additional tasks beyond algorithms related to supervised classification, marking of features which can be ignored for a classification task, extension of algorithm parameters with external code (e.g., a structure of a Keras neural net), etc.

We consider a dynamic bi-objective vehicle routing problem, where a subset of customers ask for service over time. Therein, the distance traveled by a single vehicle and the number of unserved dynamic requests is minimized by a dynamic evolutionary multi-objective algorithm (DEMOA), which operates on discrete time windows (eras). A decision is made at each era by a decision-maker, thus any decision depends on irreversible decisions made in foregoing eras. To understand effects of sequences of decision-making and interactions/dependencies between decisions made, we conduct a series of experiments. More precisely, we fix a set of decision-maker preferences D and the number of eras ntand analyze all |D|ntcombinations of decision-maker options. We find that for random uniform instances (a) the final selected solutions mainly depend on the final decision and not on the decision history, (b) solutions are quite robust with respect to the number of unvisited dynamic customers, and (c) solutions of the dynamic approach can even dominate solutions obtained by a clairvoyant EMOA. In contrast, for instances with clustered customers, we observe a strong dependency on decision-making history as well as more variance in solution diversity.

The concept of structural complexity describes the temporal progress of feature values on different time scales. We apply it to audio features with the goal to classify music files into genres using k-Nearest Neighbors and Random Forest. We use a publicly available data set of 1550 music tracks which are labeled as belonging to one of six different genres (or to none of them). The classification models are trained with the help of eight feature sets that describe different musical aspects (chords, harmony, instruments, timbre, etc.) in order to find out which features are best suited to predict these genres using the structural complexity. We apply evolutionary multi-objective feature selection to measure individual contributions of different structural complexity features for each genre to feature sets with the smallest classification errors. We also introduce a new feature chord vector which is shown to perform significantly better on genre classification with the structural complexity method than the chord features used in a previous work. The statistical analysis of time scales and features leads to several recommendations for the setup of feature processing based on structural complexity.

Parallel evolutionary algorithms have been used for solving multiobjective optimization problems. The aim is to find or approximate the Pareto optimal set in a reasonable time. In this work, we present a new approach that divides the objective search-space into different partitions and assigns each processor its corresponding partition. Each processor will try to find the set of solutions for its partition only. The sub-Pareto fronts will be combined later and the parallelisation approach is based on a mutli-start approach by having independent algorithm on every processor with its own starting points. Experimental results on well known test cases showed that the proposed method outperformed several state-of-the-art evolutionary algorithms regarding convergence to the true Pareto front and gave very competitive results when considering the hypervolume metric. Also, superlinear speedup results were achieved for all test functions.

We analyze the effects of including local search techniques into a multi-objective evolutionary algorithm for solving a bi-objective orienteering problem with a single vehicle while the two conflicting objectives are minimization of travel time and maximization of the number of visited customer locations. Experiments are based on a large set of specifically designed problem instances with different characteristics and it is shown that local search techniques focusing on one of the objectives only improve the performance of the evolutionary algorithm in terms of both objectives. The analysis also shows that local search techniques are capable of sending locally optimal solutions to foremost fronts of the multi-objective optimization process, and that these solutions then become the leading factors of the evolutionary process.

Uncertainty propagation is a technique to incorporate individuals with uncertain fitness estimates in evolutionary algorithms. The Surrogate-Assisted Partial Order-Based Evolutionary Optimisation Algorithm (SAPEO) uses uncertainty propagation of fitness predictions from a Kriging model to reduce the number of function evaluations. The fitness predictions are ranked with partial orders and the corresponding individuals are only evaluated if they are indistinguishable otherwise or the risk of uncertainty propagation exceeds a steadily decreasing error tolerance threshold. In this paper, we investigate the effects of using uncertainty propagation according to SAPEO on single-objective problems. To this end, we present and apply different ways of measuring the deviations of SAPEO from the underlying CMA-ES. We benchmark the algorithms on the BBOB testbed to assess the effects of uncertainty propagation on their performance throughout the runtime of the algorithm on a variety of problems. Additionally, we examine thoroughly the differences per iteration between the evolution paths of SAPEO and CMA-ES based on a model for the rank-one update. The BBOB results suggest that the success of SAPEO generally improves the performance but depends heavily on function and dimension, which is supported by the analysis of the evolution paths.

Genetic Programming as an automated method to evolve suitable computer programs for a predefined task can also be applied to multi-objective optimization problems. Originally, Genetic Programming uses tree structures for the representation of a computer program, but further development also enabled a graph based representation called Cartesian Genetic Programming. In the last years, Cartesian Genetic Programming has also been applied to multi-objective optimization problems. For example, we use this representation to determine smaller mathematical expressions or image processing filters with a maximum number of operators. Previous research showed that algorithm stagnation is a common issue in Cartesian Genetic Programming. This behavior comes along with a decrease of diversity in the population and increases the computational effort to find a suitable solution. In this paper, we combine the multi-objective search for smaller genetic programs with an efficient diversity preservation technique. A modified version of the popular NSGA-II algorithm is presented to evolve small programs with a lower amount of fitness evaluations and a higher success rate.

Game balancing is an important part of the (computer) game design process, in which designers adapt a game prototype so that the resulting gameplay is as entertaining as possible. In industry, the evaluation of a game is often based on costly playtests with human players. It suggests itself to automate this process using artificial players for the prediction of gameplay and outcome. In this paper, the feasibility of automatic balancing is investigated for the card game top trumps using simulation- and deck-based objectives. Additionally, the necessity of a multi-objective approach is asserted by assessing the only published (single-objective) method. We apply a multi-objective evolutionary algorithm to obtain decks that optimise objectives developed to express the fairness and the excitement of a game of top trumps, e.g. win rate and average number of tricks. The results are compared with decks from published top trumps games using the aforementioned objectives. The possibility to generate decks better or at least as good as decks from published top trumps decks in terms of these objectives is demonstrated. Our results indicate that automatic balancing with the presented approach is feasible even for more complex games such as real-time strategy games.

Power and performance tradeoff optimization is one of the most significant issues on heterogeneous multiprocessor or multicomputer systems (HMCSs) with dynamically variable voltage. In this paper, the problem is defined as energy-constrained performance optimization and performance-constrained energy optimization. Task scheduling for precedence-constrained parallel applications represented by a directed acyclic graph (DAG) in HMCSs is an NP-HARD problem. Over the last three decades, several task scheduling techniques have been developed for energy-aware scheduling. However, it is impossible for a single task scheduling technique to outperform all other techniques for all types of applications and situations. Motivated by these observations, hyperheuristic framework is introduced. Moreover, a quantum-inspired high-level learning strategy is proposed to improve the performance of this framework. Meanwhile, a fast solution evaluation technique is designed to reduce the computational burden for each iteration step. Experimental results show that the fast solution evaluation technique can improve average algorithm search speed by 38 percent and that the proposed algorithm generally exhibits outstanding convergence performance.

The majority of algorithms can be controlled or adjusted by parameters. Their values can substantially affect the algorithms' performance. Since the manual exploration of the parameter space is tedious -- even for few parameters -- several automatic procedures for parameter tuning have been proposed. Recent approaches also take into account some characteristic properties of the problem instances, frequently termed instance features.

We evaluate the performance of a multi-objective evolutionary algorithm on a class of dynamic routing problems with a single vehicle. In particular we focus on relating algorithmic performance to the most prominent characteristics of problem instances. The routing problem considers two types of customers: mandatory customers must be visited whereas optional customers do not necessarily have to be visited. Moreover, mandatory customers are known prior to the start of the tour whereas optional customers request for service at later points in time with the vehicle already being on its way. The multi-objective optimization problem then results as maximizing the number of visited customers while simultaneously minimizing total travel time. As an a-posteriori evaluation tool, the evolutionary algorithm aims at approximating the related Pareto set for specifically designed benchmarking instances differing in terms of number of customers, geographical layout, fraction of mandatory customers, and request times of optional customers. Conceptional and experimental comparisons to online heuristic procedures are provided.

Here we address the problem of computing finite size Hausdorff approximations of the Pareto front of four-objective optimization problems by means of evolutionary computing. Since many applications desire an approximation evenly spread along the Pareto front and approximations that are good in the Hausdorff sense are typically evenly spread along the Pareto front we consider three different evolutionary multi-objective algorithms tailored to that purpose, where two of them are based on the Part and Selection Algorithm (PSA). Finally, we present some numerical results indicating the strength of the novel methods.

In this paper we investigate the ability of selection methods to enforce niching on multi modal problems. Using theoretical properties where possible, and relying on a sound experimental analysis, we show that the conventional single-objective optimization and novelty search are extreme cases of selection, striving only for quality or diversity. However, in between these well known cases, there are many more possibilities, of which we review eight (including the aforementioned two). Multiobjective selection approaches provide a well-balanced trade-off' between exploration and exploitation. For the multiobjectivization, we recommend to use nearest-better-neighbor information instead of the common nearest-neighbor approaches.

Evolutionary algorithms (EAs) are random optimization methods inspired by genetics and natural selection, resembling simulated annealing. We develop a method that can be used to find a meaningful tradeoff between the difficulty of the analysis and the algorithms' efficiency. Since the case of a discrete search space has been studied extensively, we develop a new stochastic model for the continuous n-dimensional case. Our model uses renewal processes to find global convergence conditions. A second goal of the paper is the analytical estimation of the computation time of EA with uniform mutation inside the (hyper)-sphere of volume 1, minimizing a quadratic function.

The Pareto front of a multiobjective optimization problem can be approximated neatly by some versions of evolutionary algorithms. The quality of the approximation can be measured by the hypervolume that is dominated by the approximation. Open questions concern the existence of population-based evolutionary algorithms whose population converge to an approximation of the Pareto front with maximal dominated hypervolume for a given reference point and, if applicable, the convergence velocity. Here, the existence of such an algorithm is proven by providing a concrete example that converges to the maximal dominated hypervolume geometrically fast.

Exploratory Landscape Analysis subsumes a number of techniques employed to obtain knowledge about the properties of an unknown optimization problem, especially insofar as these properties are important for the performance of optimization algorithms. Where in a first attempt, one could rely on high-level features designed by experts, we approach the problem from a different angle here, namely by using relatively cheap low-level computer generated features. Interestingly, very few features are needed to separate the BBOB problem groups and also for relating a problem to high-level, expert designed features, paving the way for automatic algorithm selection.

Island models are popular ways of parallelizing evolutionary algorithms as they can decrease the parallel running time at low communication costs and lead to an increased population diversity. This in particular provides a good setting for crossover as this operator relies on a good diversity between parents. We consider the effect of recombining migrants with individuals on the target island. We rigorously prove, for a test function in pseudo-Boolean optimization, exponential performance gaps between island models with strongly connected topologies and a panmictic (mu+1)-EA as long as the migration interval is not too small. We then choose vertex cover as a classical NP-hard problem. By considering instances with a clear building block structure we prove that, also in this more practical setting, island models with a particular topology drastically outperform panmictic populations. Both the theoretical and empirical results show that for strongly connected topologies, such as ring, the performance drops by decreasing the migration interval, while this is not the case for topologies connected weakly such as the single receiver model.

Feature selection is an important prerequisite for music classification which in turn is becoming more and more ubiquitous since entering the digital music age. Automated classification into genres or even personal categories is currently envisioned even for standard mobile devices. However, classifiers often fail to work well with all available features, and simple greedy methods often fail to select good feature sets, making feature selection for music classification a natural field of application for evolutionary approaches in general, and multi-objective evolutionary algorithms in particular. In this work, we study the potential of applying such a multi-objective evolutionary optimization algorithm for feature selection with different objective sets. The result is promising, thus calling for deeper investigations of this approach.

In this paper, we show that sequential parameter optimization (SPO), a method that was designed for (offline) parameter tuning, can be successfully used as a controller for multistart approaches of evolutionary algorithms (EA). We demonstrate this by replacing the restart heuristic of the IPOP-CMA-ES with the SPO algorithm. Experiments on the BBOB 2010 test cases suggest that the performance is at least competitive while the approach provides more options, e.g. setting more than one parameter at once. Essentially, we argue that SPO is a generalization of the IPOP heuristic and that the distinction between tuning and control is---although often useful---an artificial one.

The case-specific tuning of parameters of optimization metaheuristics like evolutionary algorithms almost always leads to significant improvements in performance. But if the evaluation of the objective function is computationally expensive, which is typically the case for real-worlds problems, an extensive parameter tuning phase on the original problem is prohibitive. Therefore we have developed another approach: Provided that a (computationally cheap) surrogate model is available that reflects the structural characteristics of the original problem then the parameter tuning can be run on the surrogate problem before using the best parameters thereby identified for the metaheuristic when optimizing the original problem. In this experimental study we aim to assess how many function evaluations on the original problem are necessary to build a surrogate model endowed with the characteristics of the original problem and to develop a methodology that measures to which extent such a matching has been achieved.

Music classification is a complex problem which has gained high relevance for organizing large music collections. Different parameters concerning feature extraction, selection, processing and classification have a strong impact on the categorization quality. Since it is very difficult to design a deterministic approach which provides the efficient parameter tuning, we haven chosen a heuristic approach. In our work we apply and compare different evolution strategies for the optimization of feature selection and consolidation using three pre-defined personal user categories. Concepts of local search operators with domain-specific knowledge and self-adaptation are examined. Several suggestions based on an empirical study are discussed and ideas for future work are given.

In the recent past, hybrid metaheuristics became famous as successful optimization methods. The motivation for the hybridization is a notion of combining the best of two worlds: evolutionary black box optimization and local search. Successful hybridizations in large combinatorial solution spaces motivate to transfer the idea of combining the two worlds to continuous domains as well. The question arises: Can local search also improve the convergence to the Pareto front in continuous multiobjective solutions spaces? We introduce a relay and a concurrent hybridization of the successful multiobjective optimizer SMS-EMOA and local optimization methods like Hooke & Jeeves and the Newton method. The concurrent approach is based on a parameterized probability function to control the local search. Experimental analyses on academic test functions show increased convergence speed as well as improved accuracy of the solution set of the new hybridizations.

This paper offers a classification of the main representatives of interactive classical and evolutionary methods. After a crossfertilization of these two fields a new hybrid interactive reference point method is designed. The method combines the reference point idea with the relative speed of a (1+1) - EA and is implemented with a graphical user interface. Finally, it is validated on two well-known real-world test problems.

While scalarization approaches to multi- criteria optimization become infeasible in the case of many objectives, for few objectives the benefits of population- based methods compared to a set of independent single- objective optimization trials on scalarized functions are not obvious. The multi-objective covariance matrix adaptation evolution strategy (MO-CMA-ES) is a powerful algorithm for real-valued multi-criteria optimization. This population- based approach combines mutation and strategy adaptation from the elitist CMA-ES with multi-objective selection. We empirically compare the steady-state MO-CMA-ES with different scalarization algorithms, in which the elitist CMA-ES is used as single-objective optimizer. Although only bicriteria benchmark problems are considered, the MO-CMA-ES performs best in the overall comparison. However, if the scalarized problems have a structure that can easily be exploited by the CMA-ES and that is less apparent in the vector-valued fitness function, the CMA- ES with scalarization outperforms the population-based approach.

For solving multimodal problems by means of evolutionary algorithms, one often resorts to multistarts or niching methods. The latter approach the question: ‘What is else where?’ by an implicit second criterion in order to keep populations distributed over the search space. Induced by a practical problem that appears to be simple but is not easily solved, a multiobjective algorithm is proposed for solving multimodal problems. It employs an explicit diversity criterion as second objective. Experimental comparison with standard methods suggests that the multiobjective algorithm is fast and reliable and that coupling it with a local search technique is straightforward and leads to enormous quality gain. The combined algorithm is still fast and may be especially valuable for practical problems with costly target function evaluations.

A general framework of quantum-inspired multi-objective evolutionary algorithms as well as one of its sufficient convergence conditions to Pareto optimal set is proposed.

Robotic manipulation of daily-life objects is an essential requirement in service robotic applications. In that context image based visual servoing is a means to position the end-effector in order to manipulate objects of unknown pose. This contribution proposes a 6 DOF visual servoing scheme that relies on the pixel coordinates, scale and orientation of SIFT features. The control is based on geometric moments computed over an alterable set of redundant SIFT feature correspondences between the current and the reference view. The method is generic as it does not depend on a geometric object model but automatically extracts SIFT features from images of the object. The foundation of visual servoing on generic SIFT features renders the method robust with respect to loss of redundant features caused by occlusion or changes in view point. The moment based representation establishes an approximate one-to-one relationship between visual features and degrees of motion. This property is exploited in the design of a decoupled controller that demonstrates superior performance in terms of convergence and robustness compared with an inverse image Jacobian controller. Several experiments with a robotic arm equipped with a monocular eye-in-hand camera demonstrate that the approach is efficient and reliable.

Self-adaptive mutations are known to endow evolutionary algorithms (EA) with the ability of locating local optima quickly and accurately, whereas it was unknown whether these local optima are finally global optima provided that the EA runs long enough. In order to answer this question, it is assumed that the (1+1)-EA with self-adaptation is located in the vicinity P of a local solution with objective function value /spl epsi/. In order to exhibit convergence to the global optimum with probability one, the EA must generate an offspring that is an element of the lower level set S containing all solutions (including a global one) with objective function value less than /spl epsi/. In case of multimodal objective functions, these sets P and S are generally not adjacent, i.e., min{/spl par/x-y/spl par/:x/spl isin/P, y/spl isin/S}>0, so that the EA has to surmount the barrier of solutions with objective function values larger than /spl epsi/ by a lucky mutation. It will be proven that the probability of this event is less than one even under an infinite time horizon. This result implies that the EA can get stuck at a nonglobal optimum with positive probability. Some ideas of how to avoid this problem are discussed as well.

We present four abstract evolutionary algorithms for multi-objective optimization and theoretical results that characterize their convergence behavior. Thanks to these results it is easy to verify whether or not a particular instantiation of these abstract evolutionary algorithms offers the desired limit behavior. Several examples are given.

The self-adaptation of the mutation distribution is a distinguishing feature of evolutionary algorithms that optimize over continuous variables. It is widely recognized that self-adaptation accelerates the search for optima and enhances the ability to locate optima accurately, but it is generally unclear whether these optima are global ones or not. Here, it is proven that the probability of convergence to the global optimum is less than one in general, even if the objective function is continuous.

The theory of evolutionary computation has been enhanced rapidly during the last decade. This survey is the attempt to summarize the results regarding the limit and finite time behavior of evolutionary algorithms with finite search spaces and discret

The standard choice for mutating an individual of an evolutionary algorithm with continuous variables is the normal distribution; however other distributions, especially some versions of the multivariate Cauchy distribution, have recently gained increased popularity in practical applications. Here the extent to which Cauchy mutation distributions may affect the local convergence behavior of evolutionary algorithms is analyzed. The results show that the order of local convergence is identical for Gaussian and spherical Cauchy distributions, whereas nonspherical Cauchy mutations lead to slower local convergence. As a by-product of the analysis, some recommendations for the parametrization of the self-adaptive step size control mechanism can be derived.

It is shown by means of Markov chain analysis that unimodal binary long-path problems can be solved by mutation and elitist selection in a polynomially bounded number of trials on average.

The main objective of this paper is to analyze the (1, λ) evolution strategy by use of stochastic approximation methods. Both constant and decreasing step size algorithms are studied. Convergence and estimation error bounds for the (1, λ) evolution strategy are developed. First the algorithm is converted to a recursively defined scheme of stochastic approximation type. Then the analysis is carried out by using the analytic tools from stochastic approximation. In lieu of examining the discrete iterates, suitably scaled sequences are defined. These interpolated sequences are then studied in detail. It is shown that the limits of the sequences have natural connections to certain continuous time dynamical systems.

This paper analyzes the convergence properties of the canonical genetic algorithm (CGA) with mutation, crossover and proportional reproduction applied to static optimization problems. It is proved by means of homogeneous finite Markov chain analysis that a CGA will never converge to the global optimum regardless of the initialization, crossover, operator and objective function. But variants of CGA's that always maintain the best solution in the population, either before or after selection, are shown to converge to the global optimum due to the irreducibility property of the underlying original nonconvergent CGA. These results are discussed with respect to the schema theorem.

Simulated annealing and single-trial versions of evolution strategies possess a close relationship when they are designed for optimization over continuous variables. Analytical investigations of their differences and similarities lead to a cross-fertilization of both approaches, resulting in new theoretical results, new parallel population-based algorithms, and a better understanding of the interrelationships.