In this paper, we address the problem of efficiently computing finite-size approximations of the set of -locally optimal solutions of a given multi-objective optimization problem (MOP). Such sets are in particular interesting in the context of multi-objective multimodal optimization (MMO). To this end, we first propose a bounded archiver, ArchiveUpdateLQ,∈B, that is, a modification of a previously proposed unbounded archiver. These archivers can be used as external archivers to in principle any multi-objective evolutionary algorithm (MOEA). In order to reduce the computational cost compared to such archive equipped MOEAs, we propose, in a next step LQ,∈MOEA. This evolutionary algorithm directly uses ArchiveUpdateLQ,∈B for the selection process and hence does not need an external archive for the computation of ∈-locally optimal solutions. We further propose a hybrid of LQ,∈MOEA with a multi-objective continuation method, which significantly improves the accuracy of the obtained solutions in case the gradient information is at hand. Finally, we show some numerical results that demonstrate the benefit of both the bounded archiver and the new MOEAs.

In this article, we address the problem of computing all locally optimal solutions of a given multiobjective problem whose images are sufficiently close to the Pareto front. Such$\epsilon $-locally optimal solutions are particularly interesting in the context of multiobjective multimodal optimization (MMO). To accomplish this task, we first define a new set of interest,$L_{Q,\epsilon }$, that is strongly related to the recently proposed set of$\epsilon $-acceptable solutions. Next, we propose a new unbounded archiver,$ArchiveUpdateL_{Q,\epsilon }$, aiming to capture$L_{Q,\epsilon }$in the limit. This archiver can in principle be used in combination with any multiobjective evolutionary algorithm (MOEA). Further, we equip numerous MOEAs with$ArchiveUpdateL_{Q,\epsilon }$, investigate their performances across several benchmark functions, and compare the enhanced MOEAs with their archive-free counterparts. For our experiments, we utilize the well-established metrics HV, IGDX, and$\Delta _{p}$. Additionally, we propose and use a new performance indicator,$I_{\mathrm { EDR}}$, which results in comparable performances but which is applicable to problems defined in higher dimensions (in particular in decision variable space).

Evolutionary multi-objective optimization (EMO) is a highly active research field that has attracted many researchers and practitioners over the past three decades. Surprisingly, until now the goal of almost all EMO algorithms is to compute a suitable finite size representation of the Pareto set/front of a given MOP or at least a part of it. In other words, the quest is restricted to optimal solutions. In this work, we argue that the entire set of nearly optimal solutions – which includes all optimal ones – is of potential interest for the decision maker as they contain in addition to the optimal solutions alternative realizations or backup solutions. We further make a first effort to reliably compute the set of nearly optimal solutions via EMO algorithms. To this end, we first propose a new set of interest, NQ, and analyze its topology. In a next step, we propose an unbounded archiver that aims to capture NQ,and analyze it with respect to monotonicity and limit behavior. After this, we discuss the related subset selection problem which comes with unbounded archivers leading to four different algorithms. Finally, we numerically investigate the behavior of the archiver and the selection strategies, and present some results when using the archiver as external archiver to three widely used MOEAs indicating the benefit of the new approach.

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.

One important issue in evolutionary multi-objective optimization (EMO) which still leaves room for improvement is the maintenance of the subset of the obtained candidate solutions that forms the approximation of the Pareto front (in short: selection or archiving). Existing archivers that are entirely based on the distances between the candidate solutions are known to reveal cyclic behavior and do hence not tap their full potential. On the other hand, there exist archivers based on ∊-dominance that guarantee monotonic behaviors as well as certain approximation qualities in the limit. For such methods, however, so far the magnitudes of the final archive size heavily depend on several design parameters and cannot be bounded a priori which is desired by many EMO researchers.

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.

Here we address the ambulance location problem for the ambulance fleet of the Red Cross Unit of Tijuana, Mexico, which is a crucial factor for the quality of their emergency medical services (EMS). For this purpose, we first propose an optimization problem which is an adaption of the Multi-source Weber Problem to the problem at hand and which is a continuous location model. Next, we solve this problem on five test instances adapted to the situation in Tijuana by a genetic algorithm and compare the results to the current situation. This comparison indicates that changing the location of the fleet, as suggested by the optimization process and working under the assumptions made in this work, would lead to significant improvements of the EMS provided in Tijuana.

In standard genetic programming (GP), a search is performed over a syntax space defined by the set of primitives, looking for the best expressions that minimize a cost function based on a training set. However, most GP systems lack a numerical optimization method to fine tune the implicit parameters of each candidate solution. Instead, GP relies on more exploratory search operators at the syntax level. This work proposes a memetic GP, tailored for binary classification problems. In the proposed method, each node in a GP tree is weighted by a real-valued parameter, which is then numerically optimized using a continuous transfer function and the Trust Region algorithm is used as a local search method. Experimental results show that potential classifiers produced by GP are improved by the local searcher, and hence the overall search is improved achieving significant performance gains, that are competitive with state-of-the-art methods on well-known benchmarks.

This work presents an asymmetric quadratic approximation model and an $\epsilon$-archiving algorithm. The model allows to construct, under local convexity assumptions, descriptors for local optima points in continuous functions. A descriptor can be used to extract confidence radius information. The $\epsilon$-archiving algorithm is designed to maintain and update a set of such asymmetric descriptors, spaced at some given threshold distance. An in-depth analysis is conducted on the stability and performance of the asymmetric model, comparing the results with the ones obtained by a quadratic polynomial approximation. A series of different applications are possible in areas such as dynamic and robust optimization.

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.

The Hausdorff distance dHis a widely used tool to measure the distance between different objects in several research fields. Possible reasons for this might be that it is a natural extension of the well-known and intuitive distance between points and/or the fact that dHdefines in certain cases a metric in the mathematical sense. In evolutionary multiobjective optimization (EMO) the task is typically to compute the entire solution set-the so-called Pareto set-respectively its image, the Pareto front. Hence, dHshould, at least at first sight, be a natural choice to measure the performance of the outcome set in particular since it is related to the terms spread and convergence as used in EMO literature. However, so far, dHdoes not find the general approval in the EMO community. The main reason for this is that dHpenalizes single outliers of the candidate set which does not comply with the use of stochastic search algorithms such as evolutionary strategies. In this paper, we define a new performance indicator, Δp, which can be viewed as an “averaged Hausdorff distance” between the outcome set and the Pareto front and which is composed of (slight modifications of) the well-known indicators generational distance (GD) and inverted generational distance (IGD). We will discuss theoretical properties of Δp(as well as for GD and IGD) such as the metric properties and the compliance with state-of-theart multiobjective evolutionary algorithms (MOEAs), and will further on demonstrate by empirical results the potential of Δpas a new performance indicator for the evaluation of MOEAs.

The design of resource efficient integrated circuits (ICs) requires solving a minimization problem which consists of more than one objective given as measures of the available resources. This multi-objective optimization problem (MOP) can be solved on the smallest unit of the IC, the standard cells, to improve the performance of the entire circuit. In this work, transistor sizing of an IC is approached via a multi-objective approach which includes the use of multi-objective evolutionary algorithms (MOEAs). We compare the performance of two MOEAs on a four-dimensional MOP of a particular standard cell. The results indicate that evolutionary strategies are suitable for the treatment of such problems and advantageous against other rather classical methods.

In this paper, we study the influence of the number of objectives of a continuous multiobjective optimization problem on its hardness for evolution strategies which is of particular interest for many-objective optimization problems. To be more precise, we measure the hardness in terms of the evolution (or convergence) of the population toward the set of interest, the Pareto set. Previous related studies consider mainly the number of nondominated individuals within a population which greatly improved the understanding of the problem and has led to possible remedies. However, in certain cases this ansatz is not sophisticated enough to understand all phenomena, and can even be misleading. In this paper, we suggest alternatively to consider the probability to improve the situation of the population which can, to a certain extent, be measured by the sizes of the descent cones. As an example, we make some qualitative considerations on a general class of uni-modal test problems and conjecture that these problems get harder by adding an objective, but that this difference is practically not significant, and we support this by some empirical studies. Further, we address the scalability in the number of objectives observed in the literature. That is, we try to extract the challenges for the treatment of many-objective problems for evolution strategies based on our observations and use them to explain recent advances in this field.

In this work we present a simple way to introduce gradient-based information as a means to improve the search performed by a multi-objective evolutionary algorithm (MOEA). Our proposal can be easily incorporated into any MOEA, and is able to improve its performance when solving continuous bi-objective problems. We propose a novel mechanism to control the balance between the local search, and the global search performed by a MOEA. We discuss the advantages of the proposed method and its possible use when dealing with more objectives. Finally, we provide some guidelines regarding the use of our proposed approach.

In many applications it can be advantageous for the decision maker to have multiple options available for a possible realization of the project. One way to increase the number of interesting choices is in certain cases to consider in addition to the optimal solution x∗also nearly optimal or approximate solutions which differ in the design space from x∗by a certain value. In this paper we address the efficient computation and discretization of the set E of ∊-approximate solutions for scalar optimization problems. For this we will suggest two strategies to archive and update the data coming from the generation process of the search procedure, and will use Differential Evolution coupled with the new archivers for the computation of E. Finally, we will demonstrate the behavior of the archiver empirically on some academic functions as well as on two models related to space mission design.

Recently, a convergence proof of stochastic search algorithms toward finite size Pareto set approximations of continuous multi-objective optimization problems has been given. The focus was on obtaining a finite approximation that captures the entire solution set in some suitable sense, which was defined by the concept of epsilon-dominance. Though bounds on the quality of the limit approximation-which are entirely determined by the archiving strategy and the value of epsilon-have been obtained, the strategies do not guarantee to obtain a gap free approximation of the Pareto front. That is, such approximations A can reveal gaps in the sense that points f in the Pareto front can exist such that the distance of f to any image point F(a), a epsilon A, is "large." Since such gap free approximations are desirable in certain applications, and the related archiving strategies can be advantageous when memetic strategies are included in the search process, we are aiming in this work for such methods. We present two novel strategies that accomplish this task in the probabilistic sense and under mild assumptions on the stochastic search algorithm. In addition to the convergence proofs, we give some numerical results to visualize the behavior of the different archiving strategies. Finally, we demonstrate the potential for a possible hybridization of a given stochastic search algorithm with a particular local search strategy-multi-objective continuation methods-by showing that the concept of epsilon-dominance can be integrated into this approach in a suitable way.

In this paper, we propose and investigate a new local search strategy for multiobjective memetic algorithms. More precisely, we suggest a novel iterative search procedure, known as theHill Climber with Sidestep(HCS), which is designed for the treatment of multiobjective optimization problems, and show further two possible ways to integrate the HCS into a given evolutionary strategy leading to new memetic (or hybrid) algorithms. The pecularity of the HCS is that it is intended to be capable both moving toward and along the (local) Pareto set depending on the distance of the current iterate toward this set. The local search procedure utilizes the geometry of the directional cones of such optimization problems and works with or without gradient information. Finally, we present some numerical results on some well-known benchmark problems, indicating the strength of the local search strategy as a standalone algorithm as well as its benefit when used within a MOEA. For the latter we use the state of the art algorithms Nondominated Sorting Genetic Algorithm-II and Strength Pareto Evolutionary Algorithm 2 as base MOEAs.

This work introduces a hybrid between an elitist multi-objective evolutionary algorithm and a gradient-based descent method, which is applied only to certain (selected) solutions. Our proposed approach requires a low number of objective function evaluations to converge to a few points in the Pareto front. Then, the rest of the Pareto front is reconstructed using a method based on rough sets theory, which also requires a low number of objective function evaluations. Emphasis is placed on the effectiveness of our proposed hybrid approach when increasing the number of decision variables, and a study of the scalability of our approach is also presented.

In this paper we develop evolutionary strategies for numerical continuation which we apply to scalar and multi-objective optimization problems. To be more precise, we will propose two different methods-an embedding algorithm and a multi-objectivization approach-which are designed to follow an implicitly defined curve where the aim can be to detect the endpoint of the curve (e.g., a root finding problem) or to approximate the entire curve (e.g., the Pareto set of a multi-objective optimization problem). We demonstrate that the novel approaches are very robust in finding the set of interest (point or curve) on several examples.

In this work we study the convergence of generic stochastic search algorithms toward the entire set of approximate solutions of continuous multi-objective optimization problems. Since the dimension of the set of interest is typically equal to the dimension of the parameter space, we focus on obtaining a finite and tight approximation, measured by the Hausdorff distance. Under mild assumptions about the process to generate new candidate solutions, the limit approximation set will be determined entirely by the archiving strategy. We propose and investigate a novel archiving strategy theoretically and empirically. For this, we analyze the convergence behavior of the algorithm, yielding bounds on the obtained approximation quality as well as on the cardinality of the resulting approximation, and present some numerical results.

In this paper we propose a novel iterative search procedure for multi-objective optimization problems. The iteration process -- though derivative free -- utilizes the geometry of the directional cones of such optimization problems, and is capable both of moving toward and along the (local) Pareto set depending on the distance of the current iterate toward this set. Next, we give one possible way of integrating this local search procedure into a given EMO algorithm resulting in a novel memetic strategy. Finally, we present some numerical results on some well-known benchmark problems indicating the strength of both the local search strategy as well as the new hybrid approach.

Recently, a convergence proof of stochastic search algorithms toward finite size Pareto set approximations of continuous multi-objective optimization problems has been given. The focus was on obtaining a finite approximation that captures the entire solution set in some suitable sense, which was defined by the concept of ε-dominance. Though bounds on the quality of the limit approximation -- which are entirely determined by the archiving strategy and the value of ε -- have been obtained, the strategies do not guarantee to obtain a gap-free Pareto front approximation. Since such approximations are desirable in certain applications, and the related archiving strategies can be advantageous when memetic strategies are included into the search process, we are aiming in this work for such methods. We present two novel strategies that accomplish this task in the probabilistic sense and under mild assumptions on the stochastic search algorithm. In addition to the convergence proofs we give somenumerical results to visualize the behavior of the different archiving strategies.

In this paper we introduce line search strategies originating from continuous optimization for the realization of the guidance mechanism in particle swarm optimization for scalar optimization problems. Since these techniques are well-suited for-but not restricted to-local search the resulting algorithm can be considered to be memetic. Further, we will use the same techniques for the construction of a new variant of a hill climber. We will discuss possible realizations and will finally present some numerical results indicating the strength of the two algorithms