Abstract Indicator-based (multi-objective) diversity optimization aims at finding a set of near (Pareto)optimal solutions that maximizes a diversity indicator, where diversity is typically interpreted as the number of essentially different solutions. Whereas, in the first diversity-oriented evolutionary multi-objective optimization algorithm, the NOAH algorithm by Ulrich and Thiele, the Solow Polasky Diversity (SP Diversity, also known as Magnitude [1]) served as a metric, other diversity indicators could be considered. We examine the parameter-free Max-Min Diversity and the Riesz $$s$$ s -Energy, which features uniformly distributed solution sets. Focusing on multi-objective diversity optimization, we discuss different diversity indicators from the perspective of indicator-based evolutionary algorithms with multiple objectives. We examine theoretical, computational, and practical properties of these indicators, such as monotonicity in species, twinning, monotonicity in distance, strict monotonicity in distance, uniformity of maximizing point sets, computational effort for a set of size $$n$$ n , single-point contributions, subset selection, and submodularity. We present new theorems—including a proof of the NP-hardness of the Riesz $$s$$ s -Energy Subset Selection Problem—and consolidate existing results from the literature. In the experiments, we apply these indicators in the NOAH algorithm to analyze search dynamics via an example. We study how optimizing one indicator impacts others and propose NOAH-specific modifications for the Max-Min indicator.

A common goal in evolutionary multiobjective optimization is to find suitable finite-size approximations of the Pareto front of a given multiobjective optimization problem. While many multiobjective evolutionary algorithms (MOEAs) have proven to be very efficient in finding good Pareto front approximations, they may need quite a few resources or may even fail to obtain optimal or nearly optimal approximations. Hereby, optimality is implicitly defined by the chosen performance indicator. In this work, we propose a set-based Newton method for the Hausdorff approximations of the Pareto front to be used within MOEAs. To this end, we first generalize the previously proposed Newton step for the performance indicator to treat constrained problems for general reference sets. To approximate the target Pareto front, we propose a particular strategy for generating the reference set that utilizes the data gathered by the evolutionary algorithm during its run. Finally, we show the benefit of the Newton method as a postprocessing step on several benchmark test functions and different base evolutionary algorithms.

Abstract A building spatial design (BSD) determines external and internal walls and ceilings of a building. The design space has a hierarchical structure, in which decisions on the existence or non-existence of spatial components determine the existence of variables related to these spaces, such as sizing and angles. In the optimization of BSDs it is envisioned to optimize various performance indicators from multiple disciplines in concert, such as structural, functional, thermal, and daylight performance. Existing representations of design spaces suffer from severe limitations, such as only representing orthogonal designs or representing the structures in parametric superstructure, allowing only for limited design variations. This paper proposes prism nets - a new way of representing the search space of BSDs based on triangulations defining space filling collections of triangular prisms that can be combined via coloring parameters to spaces. Prism nets can accommodate for non-orthogonal designs and are flexible in terms of topological variations. We follow the guidelines for representation and operator design proposed in the framework of metric-based evolutionary algorithms. The main contribution of the paper is a detailed discussion of the search space representation and corresponding mutation operators. Moreover, a proof of concept example demonstrates the integration into multi-objective evolutionary algorithms and provides first results on a simple, but reproducible, benchmark problem.

In this paper, we propagate the use of a set-based Newton method that enables computing a finite size approximation of the Pareto front (PF) of a given twice continuously differentiable bi-objective optimization problem (BOP). To this end, we first derive analytically the Hessian matrix of the hypervolume indicator, a widely used performance indicator for PF approximation sets. Based on this, we propose the hypervolume Newton method (HNM) for hypervolume maximization of a given set of candidate solutions. We first address unconstrained BOPs and focus further on first attempts for the treatment of inequality constrained problems. The resulting method may even converge quadratically to the optimal solution, however, this property is-as for all Newton methods-of local nature. We hence propose as a next step a hybrid of HNM and an evolutionary strategy in order to obtain a fast and reliable algorithm for the treatment of such problems. The strengths of both HNM and hybrid are tested on several benchmark problems and comparisons of the hybrid to state-of-the-art evolutionary algorithms for hypervolume maximization are presented.

We continue recent work on the definition of multimodality in multiobjective optimization (MO) and the introduction of a test bed for multimodal MO problems. This goes beyond well-known diversity maintenance approaches but instead focuses on the landscape topology induced by the objective functions. More general multimodal MO problems are considered by allowing ellipsoid contours for single-objective subproblems. An experimental analysis compares two MO algorithms, one that explicitly relies on hypervolume gradient approximation, and one that is based on local search, both on a selection of generated example problems. We do not focus on performance but on the interaction induced by the problems and algorithms, which can be described by means of specific characteristics explicitly designed for the multimodal MO setting. Furthermore, we widen the scope of our analysis by additionally applying visualization techniques in the decision space. This strengthens and extends the foundations for Exploratory Landscape Analysis (ELA) in MO.

In the field of multi-objective optimization algorithms, multi-objective Bayesian Global Optimization (MOBGO) is an important branch, in addition to evolutionary multi-objective optimization algorithms. MOBGO utilizes Gaussian Process models learned from previous objective function evaluations to decide the next evaluation site by maximizing or minimizing an infill criterion. A commonly used criterion in MOBGO is the Expected Hypervolume Improvement (EHVI), which shows a good performance on a wide range of problems, with respect to exploration and exploitation. However, so far, it has been a challenge to calculate exact EHVI values efficiently. This paper proposes an efficient algorithm for the exact calculation of the EHVI for in a generic case. This efficient algorithm is based on partitioning the integration volume into a set of axis-parallel slices. Theoretically, the upper bound time complexities can be improved from previously $$O (n^2)$$ and $$O(n^3)$$ , for two- and three-objective problems respectively, to $$\varTheta (n\log n)$$ , which is asymptotically optimal. This article generalizes the scheme in higher dimensional cases by utilizing a new hyperbox decomposition technique, which is proposed by Dächert et al. (Eur J Oper Res 260(3):841–855, 2017). It also utilizes a generalization of the multilayered integration scheme that scales linearly in the number of hyperboxes of the decomposition. The speed comparison shows that the proposed algorithm in this paper significantly reduces computation time. Finally, this decomposition technique is applied in the calculation of the Probability of Improvement (PoI).

In almost no other field of computer science, the idea of using bio-inspired search paradigms has been so useful as in solving multiobjective optimization problems. The idea of using a population of search agents that collectively approximate the Pareto front resonates well with processes in natural evolution, immune systems, and swarm intelligence. Methods such as NSGA-II, SPEA2, SMS-EMOA, MOPSO, and MOEA/D became standard solvers when it comes to solving multiobjective optimization problems. This tutorial will review some of the most important fundamentals in multiobjective optimization and then introduce representative algorithms, illustrate their working principles, and discuss their application scope. In addition, the tutorial will discuss statistical performance assessment. Finally, it highlights recent important trends and closely related research fields. The tutorial is intended for readers, who want to acquire basic knowledge on the mathematical foundations of multiobjective optimization and state-of-the-art methods in evolutionary multiobjective optimization. The aim is to provide a starting point for researching in this active area, and it should also help the advanced reader to identify open research topics.

In optimization with expensive black box evaluations, the expected improvement algorithm (also called efficient global optimization) is a commonly applied method. It uses Gaussian Processes (or Kriging) to build a model of the objective function and uses the expected improvement as an infill criterion, taking into account both — predictive mean and variance. It has been generalized to multi-objective optimization using the expected hypervolume improvement, which measures the expected gain in the hypervolume indicator of a Pareto front approximation. However, this criterion assumes an unbounded objective space even if it is often known a-priori that the objective function values are within a prescribed range, e.g., lower bounded by zero. To take advantage of such a-priori knowledge, this paper introduces the truncated expected hypervolume improvement and a multiobjective efficient global optimization method that is based on it. In this paper it is shown how to compute the truncated expected hypervolume improvement exactly and efficiently. Then it is tested as an infill criterion in efficient global optimization. It is shown that it can effectively make use of a-priori knowledge and achieve better results in cases where such knowledge is given. The usefulness of the new approach is demonstrated in benchmark examples and applications from robust PID (proportionalintegral-derivative) controller optimization. The empirical studies in this paper are confined to the bi-objective case.

The expected improvement (EI) is a well established criterion in Bayesian global optimization (BGO) and metamodel assisted evolutionary computation, both applied in optimization with costly function evaluations. Recently, it has been adopted in different ways to multiobjective optimization. A promising approach to formulate the expected improvement in this context, is to base it on the hypervolume indicator. Given the Bayesian model of the optimization landscape, the EI in hypervolume computes the expected gain in attained hypervolume for a given input point. Although a formulation of this expected improvement is relatively straightforward, its computation and mathematical properties are still to be investigated. This paper will outline and derive an algorithm for the exact computation of the proposed hypervolume-based EI. Moreover, this paper establishes monotonicity properties of the expected improvement. In particular the effect of the predictive distribution's variance on the hypervolume-based EI and elementary properties of the EI landscape are studied. The monotonicity properties will reveal regions where Pareto front approximations can be improved as well as underexplored regions that are favored by the hypervolume based expected improvement. A first numerical example is included that illustrates the behavior of the hypervolume-based EI in the multiobjective BGO framework.

Algorithms that search for robust optima often evaluate the effective fitness (robust fitness) based on stochastic approximation schemes. In this setting, finding robust optima can be recast as an optimization problem with an/a uncertain/noisy objective function. This paper studies whether state-of-the-art uncertainty handling techniques, proposed in the context of optimizing noisy objective functions, can be applied for finding robust optima. In this paper, the UH-CMA-ES is modified to handle approximations of the effective fitness. This modified approach, named RO-UH-CMA-ES, is evaluated empirically and compared to other schemes that aim to find robust optima. The experiments on multiple benchmark problems show that the RO-UH-CMA-ES yields comparable results for multi-modal problems and it outperforms other schemes on unimodal problems.

This paper presents a study for using Kriging metamodeling in combination with Covariance Matrix Adaptation Evolution Strategies (CMA-ES) to find robust solutions. A general, archive based, framework is proposed for integrating Kriging within CMA-ES, including a method to utilize the covariance matrix of the CMA-ES in a straightforward way to improve the accuracy of the Kriging predictions without introducing much additional computational cost. Moreover, it adopts an elegant way to select appropriate archive points for building a local metamodel. The study shows that this Kriging metamodeling scheme for finding robust solutions outperforms common, straightforward approaches and is very useful when there is a limited budget of function evaluations. Though using the covariance matrix can improve the prediction quality, it has no significant effect on the overall quality of the optimization results.