Search

In evolutionary multiobjective optimization, the task of the optimizer is to obtain an accurate and useful approximation of the true Pareto-optimal front. Proximity to the front and diversity of solutions within the approximation set are important requirements. Most established multiobjective evolutionary algorithms (MOEAs) have mechanisms that address these requirements. However, in many-objective optimization, where the number of objectives is greater than 2 or 3, it has been found that these two requirements can conflict with one another, introducing problems such as dominance resistance and speciation. In this paper, two diversity management mechanisms are introduced to investigate their impact on overall solution convergence. They are introduced separately, and in combination, and tested on a set of test functions with an increasing number of objectives (6–20). It is found that the inclusion of one of the mechanisms improves the performance of a well-established MOEA in many-objective optimization problems, in terms of both convergence and diversity. The relevance of this for many-objective MOEAs is discussed. [ABSTRACT FROM AUTHOR]

Using surrogate models in evolutionary search provides an efficient means of handling today's complex applications plagued with increasing high-computational needs. Recent surrogate-assisted evolutionary frameworks have relied on the use of a variety of different modeling approaches to approximate the complex problem landscape. From these recent studies, one main research issue is with the choice of modeling scheme used, which has been found to affect the performance of evolutionary search significantly. Given that theoretical knowledge available for making a decision on an approximation model a priori is very much limited, this paper describes a generalization of surrogate-assisted evolutionary frameworks for optimization of problems with objectives and constraints that are computationally expensive to evaluate. The generalized evolutionary framework unifies diverse surrogate models synergistically in the evolutionary search. In particular, it focuses on attaining reliable search performance in the surrogate-assisted evolutionary framework by working on two major issues: 1) to mitigate the 'curse of uncertainty' robustly, and 2) to benefit from the 'bless of uncertainty.' The backbone of the generalized framework is a surrogate-assisted memetic algorithm that conducts simultaneous local searches using ensemble and smoothing surrogate models, with the aims of generating reliable fitness prediction and search improvements simultaneously. Empirical study on commonly used optimization benchmark problems indicates that the generalized framework is capable of attaining reliable, high quality, and efficient performance under a limited computational budget. [ABSTRACT FROM AUTHOR]

In this paper, we prove some convergence properties for a class of ant colony optimization algorithms. In particular, we prove that for any small constant ∈ > 0 and for a sufficiently large number of algorithm iterations t, the probability of finding an optimal solution at least once is P* (t) ≥ 1 -- ∈ and that this probability tends to 1 for t → ∞. We also prove that, after an optimal solution has been found, it takes a finite number of iterations for the pheromone trails associated to the found optimal solution to grow higher than any other pheromone trail and that, for t → ∞, any fixed ant will produce the optimal solution during the tth iteration with probability P ≥ 1 -- ∈ (τ[submin], τ[submax]), where τ[submin] and τ[submax], are the minimum and maximum values that can be taken by pheromone trails. [ABSTRACT FROM AUTHOR]

Algorithms that make use of the gradient, i.e., the direction of maximum improvement, to search for the optimum of a single-objective function have been around for decades. They are commonly accepted to be important and have been applied to tackle single-objective optimization problems in many fields. For multiobjective optimization problems, much less is known about the gradient and its algorithmic use. In this paper, we aim to contribute to the understanding of gradients for numerical, i.e., real-valued, multiobjective optimization. Specifically, we provide an analytical parametric description of the set of all nondominated, i.e., most promising, directions in which a solution can be moved such that the objective values either improve or remain the same. This result completes previous work where this set is described only for one particular case, namely when some of the nondominated directions have positive, i.e., nonimproving, components and the final set can be computed by taking the subset of directions that are all nonpositive. In addition we use our result to assess the utility of using gradient information for multiobjective optimization where the goal is to obtain a Pareto set of solutions that approximates the optimal Pareto set. To this end, we design and consider various multiobjective gradient-based optimization algorithms. One of these algorithms uses the description of the multiobjective gradient provided here. Also, we hybridize an existing multiobjective evolutionary algorithm (MOEA) with the various multiobjective gradient-based optimization algorithms. During optimization, the performance of the gradient-based optimization algorithms is monitored and the available computational resources are redistributed to allow the (currently) most effective algorithm to spend the most resources. We perform an experimental analysis using a few well-known benchmark problems to compare the performance of different optimization methods. The results underline that the use of a population of solutions that is characteristic of MOEAs is a powerful concept if the goal is to obtain a good Pareto set, i.e., instead of only a single solution. This makes it hard to increase convergence speed in the initial phase using gradient information to improve any single solution. However, in the longer run, the use of gradient information does ultimately allow for better fine-tuning of the results and thus better overall convergence. [ABSTRACT FROM PUBLISHER]

Assuming that evolutionary multiobjective optimization (EMO) mainly deals with set problems, one can identify three core questions in this area of research: 1) how to formalize what type of Pareto set approximation is sought; 2) how to use this information within an algorithm to efficiently search for a good Pareto set approximation; and 3) how to compare the Pareto set approximations generated by different optimizers with respect to the formalized optimization goal. There is a vast amount of studies addressing these issues from different angles, but so far only a few studies can be found that consider all questions under one roof. This paper is an attempt to summarize recent developments in the EMO field within a unifying theory of set-based multiobjective search. It discusses how preference relations on sets can be formally defined, gives examples for selected user preferences, and proposes a general preference-independent hill climber for multiobjective optimization with theoretical convergence properties. Furthermore, it shows how to use set preference relations for statistical performance assessment and provides corresponding experimental results. The proposed methodology brings together preference articulation, algorithm design, and performance assessment under one framework and thereby opens up a new perspective on EMO. [ABSTRACT FROM AUTHOR]

The goal of multiobjective optimization is to find a set of best compromise solutions for typically conflicting objectives. Due to the complex nature of most real-life problems, only an approximation to such an optimal set can obtained within reasonable (computing) time. To compare such approximations, and thereby the performance of multiobjective optimizers providing them, unary quality measures are usually applied. Among these, the hypervolume indicator (or S-metric) is of particular relevance due to its favorable properties. Moreover, this indicator has been successfully integrated into stochastic optimizers, such as evolutionary algorithms, where it serves as guidance criterion for finding good approximations to the Pareto front. Recent results show that computing the hypervolume indicator can be seen as solving a specialized version of Klee's Measure Problem. In general, Klee's Measure Problem can solved with O(n log n + nd/2 log n) comparisons for an input instance of size n in d dimensions; as of this writing, it unknown whether a lower bound higher than Ω (n log n) be proven. In this paper, we derive a lower bound of Ω (n log n) for the complexity of computing the hypervolume indicator any number of dimensions d > 1 by reducing the so-called UNIFORMGAP problem to it. For the 3-D case, we also present matching upper bound of O (n log n) comparisons that is obtained by extending an algorithm for finding the maxima of a point set. [ABSTRACT FROM AUTHOR]

While noise is a phenomenon present in many real-world optimization problems, the understanding of its potential effects on the performance of evolutionary algorithms is still incomplete. This paper investigates the effects of fitness proportionate Gaussian noise for a (1 + 1)-ES with isotropic normal mutations on the quadratic sphere in the limit of infinite search-space dimensionality. It is demonstrated experimentally that the results provide a good approximation for finite space dimensionality. It is shown that overvaluation as a result of failure to reevaluate parental fitness leads to both reduced success probabilities and improved performance. Implications for mutation strength adaptation rules are discussed and optimal resampling rates are computed. [ABSTRACT FROM AUTHOR]

An important issue in multiobjective optimization is the quantitative comparison of the performance of different algorithms. In the case of multiobjective evolutionary algorithms, the outcome is usually an approximation of the Pareto-optimal set, which is denoted as an approximation set, and therefore the question arises of how to evaluate the quality of approximation sets. Most popular are methods that assign each approximation set a vector of real numbers that reflect different aspects of the quality. Sometimes, pairs of approximation sets are considered too. In this study, we provide a rigorous analysis of the limitations underlying this type of quality assessment. To this end, a mathematical framework is developed which allows to classify and discuss existing techniques. [ABSTRACT FROM AUTHOR]