Evolutionary Multi-Criterion Optimization

Computationally expensive simulations play an increasing role in engineering design, but their use in multi-objective optimization is heavily resource constrained. Specialist optimizers, such as ParEGO, exist for this setting, but little knowledge is available to guide their configuration. This paper uses a new implementation of ParEGO to examine three hypotheses relating to a key configuration parameter: choice of scalarising norm. Two hypotheses consider the theoretical trade-off between convergence speed and ability to capture an arbitrary Pareto front geometry. Experiments confirm these hypotheses in the bi-objective setting but the trade-off is largely unseen in many-objective settings. A third hypothesis considers the ability of dynamic norm scheduling schemes to overcome the trade-off. Experiments using a simple scheme offer partial support to the hypothesis in the bi-objective setting but no support in many-objective contexts. Norm scheduling is tentatively recommended for bi-objective problems for which the Pareto front geometry is concave or unknown.

Big Data Optimization is the term used to refer to optimization problems which have to manage very large amounts of data. In this paper, we focus on the parallelization of metaheuristics with the Apache Spark cluster computing system for solving multi-objective Big Data Optimization problems. Our purpose is to study the influence of accessing data stored in the Hadoop File System (HDFS) in each evaluation step of a metaheuristic and to provide a software tool to solve these kinds of problems. This tool combines the jMetal multi-objective optimization framework with Apache Spark. We have carried out experiments to measure the performance of the proposed parallel infrastructure in an environment based on virtual machines in a local cluster comprising up to 100 cores. We obtained interesting results for computational effort and propose guidelines to face multi-objective Big Data Optimization problems.

The inverted generational distance (IGD) is a metric for assessing the quality of approximations to the Pareto front obtained by multi-objective optimization algorithms. The IGD has become the most commonly used metric in the context of many-objective problems, i.e., those with more than three objectives. The averaged Hausdorff distance and $$\textit{IGD}^+$$ are variants of the IGD proposed in order to overcome its major drawbacks. In particular, the IGD is not Pareto compliant and its conclusions may strongly change depending on the size of the reference front. It is also well-known that different metrics assign more importance to various desired features of approximation fronts, and thus, they may disagree when ranking them. However, the precise behavior of the IGD variants is not well-understood yet. In particular, $$\textit{IGD}^+$$, the only IGD variant that is weakly Pareto-compliant, has received significantly less attention. This paper presents an empirical analysis of the IGD variants. Our experiments evaluate how these metrics are affected by the most important factors that intuitively describe the quality of approximation fronts, namely, spread, distribution and convergence. The results presented here already reveal interesting insights. For example, we conclude that, in order to achieve small IGD or $$\textit{IGD}^+$$ values, the approximation front size should match the reference front size.

This publication investigates characteristics of and algorithms for the quite new and complex Bi-Objective Traveling Thief Problem, where the well-known Traveling Salesman Problem and Binary Knapsack Problem interact. The interdependence of these two components builds an interwoven system where solving one subproblem separately does not solve the overall problem. The objective space of the Bi-Objective Traveling Thief Problem has through the interaction of two discrete subproblems some interesting properties which are investigated. We propose different kind of algorithms to solve the Bi-Objective Traveling Thief Problem. The first proposed deterministic algorithm picks items on tours calculated by a Traveling Salesman Problem Solver greedily. As an extension, the greedy strategy is substituted by a Knapsack Problem Solver and the resulting Pareto front is locally optimized. These methods serve as a references for the performance of multi-objective evolutionary algorithms. Additional experiments on evolutionary factory and recombination operators are presented. The obtained results provide insights into principles of an exemplary bi-objective interwoven system and new starting points for ongoing research.

Automatic algorithm configuration (AAC) is becoming an increasingly crucial component in the design of high-performance solvers for many challenging combinatorial optimisation problems. This raises the question how to most effectively leverage AAC in the context of building or optimising multi-objective optimisation algorithms, and specifically, multi-objective local search procedures. Because the performance of multi-objective optimisation algorithms cannot be fully characterised by a single performance indicator, we believe that AAC for multi-objective local search should make use of multi-objective configuration procedures. We test this belief by using MO-ParamILS to automatically configure a highly parametric iterated local search framework for the classical and widely studied bi-objective permutation flowshop problem. To the best of our knowledge, this is the first time a multi-objective optimisation algorithm is automatically configured in a multi-objective fashion, and our results demonstrate that this approach can produce very good results as well as interesting insights into the efficacy of various strategies and components of a flexible multi-objective local search framework.

To show that multiobjective optimization problems like the multiobjective shortest path or assignment problems are hard, we often use the theory of $$\mathbf {NP} $$-hardness. In this paper we rigorously investigate the complexity status of some well-known multiobjective optimization problems and ask the question if these problems really are $$\mathbf {NP} $$-hard. It turns out, that most of them do not seem to be and for one we prove that if it is $$\mathbf {NP} $$-hard then this would imply $$\mathbf {P} = \mathbf {NP} $$ under assumptions from the literature. We also reason why $$\mathbf {NP} $$-hardness might not be well suited for investigating the complexity status of intractable multiobjective optimization problems.

Solutions that provide a balance between different objective values in multi-objective optimization can be identified by assessing the curvature of the Pareto front. We analyze how methods based on angles have been utilized in the past for this task and propose a new angle-based measure—angle utility—that ranks points of the Pareto front irrespective of its shape or the number of objectives. An algorithm for finding angle utility optima is presented and a computational study shows that this algorithm is successful in identifying angle utility optima.

Numerical benchmarking of multiobjective optimization algorithms is an important task needed to understand and recommend algorithms. So far, two main approaches to assessing algorithm performance have been pursued: using set quality indicators, and the (empirical) attainment function and its higher-order moments as a generalization of empirical cumulative distributions of function values. Both approaches have their advantages but rely on the choice of a quality indicator and/or take into account only the location of the resulting solution sets and not when certain regions of the objective space are attained. In this paper, we propose the average runtime attainment function as a quantitative measure of the performance of a multiobjective algorithm. It estimates, for any point in the objective space, the expected runtime to find a solution that weakly dominates this point. After defining the average runtime attainment function and detailing the relation to the (empirical) attainment function, we illustrate how the average runtime attainment function plot displays algorithm performance (and differences in performance) for some algorithms that have been previously run on the biobjective bbob-biobj test suite of the COCO platform.

In this work, we propose the Delta-MGA, a specific multiobjective algorithm for solving the allocation of Roadside Units (RSUs) in a Vehicular Network (VANETs). We propose two multiobjective models to solve two different problems. The first one, our objectives are to find the minimum set of RSUs and to maximize the number of covered vehicles. The second one, our objectives are to find the minimum set of RSUs and to maximize the percentage of time that each vehicle remains connected. Our metric is based on Delta Network metric proposed in literature. As far as we concerned, Delta-MGA is the first multiobjective approach to present a deployment strategy for VANETs. We compare our approach with two mono-objective algorithms: (i) Delta-r; (ii) Delta-GA. Our results demonstrate that our approach gets better results when compared with Delta-r algorithm and competitive results when compared with Delta-GA algorithm. Furthermore, the main advantage of Delta-MGA algorithm is that with it is possible to find several different solutions given to the planning authorities diverse alternatives to deploy the RSUs.

Multi-objective optimization problems with more than three objectives, which are also termed as many objective optimization problems, play an important role in the decision making process. For such problems, it is computationally expensive or even intractable to approximate the entire set of optimal solutions. An alternative is to compute a subset of optimal solutions based on the preferences of the decision maker. Commonly, interactive methods from the literature consider the user preferences at every iteration by means of weight vectors or reference points. Besides the fact that mathematical programming techniques only produce one solution at each iteration, they generally require first or second derivative information, that limits its applicability to certain problems. The approach proposed in this paper allows to steer the search into any direction in the objective space for optimization problems of discrete nature. This provides a more intuitive way to set the preferences, which represents a useful tool to explore the regions of interest of the decision maker. Numerical results on multi-objective multi-dimensional knapsack problem instances show the interest of the proposed approach.

We address the problem of outliers detection in a binary outranking relation. These elements are supposed to be rare, dissimilar to the majority of other elements and are likely to influence the outcomes of the considered method. We propose a model based on the distance introduced by De Smet and Montano and extend it to different samplings of the set of alternatives (which are used as a comparison basis). This leads to study the distribution of distance values. The presence of outliers is detected by the identification of bi-modal distributions. We illustrate this on examples based on the Human Development Index, the Environmental Performance Index (where artificial outliers are added) and the Shanghai Ranking of World Universities.

In many practical optimization problems, evaluation of objectives and constraints often involve computationally expensive procedures. To handle such problems, a metamodel-assisted approach is usually used to complete an optimization run in a reasonable amount of time. A metamodel is an approximate mathematical model of an objective or a constrained function which is constructed with a handful of solutions evaluated exactly. However, when comes to solving multi-objective optimization problems involving numerous constraints, it may be too much to metamodel each and every objective and constrained function independently. The cumulative effect of errors from each metamodel may turn out to be detrimental for the accuracy of the overall optimization procedure. In this paper, we propose a taxonomy of various metamodeling methodologies for multi-objective optimization and provide a comparative study by discussing advantages and disadvantages of each method. The first results presented in this paper are obtained using the well-known Kriging metamodeling approach. Based on our proposed taxonomy and an extensive literature search, we also highlight new and promising methods for multi-objective metamodeling algorithms.

Multiobjective evolutionary algorithm based on decomposition (MOEA/D) is a well established state-of-the-art framework. Major concerns that must be addressed when applying MOEA/D are the choice of an appropriate scalarizing function and setting the values of main control parameters. This study suggests a weighted stress function method (WSFM) for fitness assignment in MOEA/D. WSFM establishes analogy between the stress-strain behavior of thermoplastic vulcanizates and scalarization of a multiobjective optimization problem. The experimental results suggest that the proposed approach is able to provide a faster convergence and a better performance of final approximation sets with respect to quality indicators when compared with traditional methods. The validity of the proposed approach is also demonstrated on engineering problems.

Lately, there is growing emphasis on improving the scalability of multi-objective evolutionary algorithms (MOEAs) so that many-objective problems (characterized by more than three objectives) can be effectively dealt with. Alternatively, the utility of integrating decision maker’s (DM’s) preferences into the optimization process so as to target some most preferred solutions by the DM (instead of the whole Pareto-optimal front), is also being increasingly recognized. The authors here, have earlier argued that despite the promises in the latter approach, its practical utility may be impaired by the lack of—objectivity, repeatability, consistency, and coherence in the DM’s preferences. To counter this, the authors have also earlier proposed a machine learning based decision support framework to reveal the preference-structure of objectives. Notably, the revealed preference-structure may be sensitive to the timing of application of this framework along an MOEA run. In this paper the authors counter this limitation, by integrating a termination criterion with an MOEA run, towards determining the appropriate timing for application of the machine learning based framework. Results based on three real-world many-objective problems considered in this paper, highlight the utility of the proposed integration towards an objective, repeatable, consistent, and coherent decision support for many-objective problems.

For some multi-criteria decision aid methods, the relative ranks of two actions may be inverted when the original set is altered. This phenomenon is known as rank reversal. In this contribution, we formalise rank reversal for the Promethee II method. The aim is not to debate about the legitimacy of such effect but rather to derive the exact conditions for its occurrence when one or more actions are added or removed from/to the original set. These conditions eventually lead us to: (1) assess whether rank reversal between a given pair of actions is, at all, possible, and (2) characterise the evaluations of the actions that have to be added or removed to induce rank reversal. We also propose two metrics that express the “strength” of and the “sensitivity” towards rank reversal. Finally, we show on a toy example how they could be used in a decision making process.

The paper discusses on the role of components of multiobjective metaheuristics in the context of multiobjective discrete/combinatorial optimization. It suggests to separate in three stages the design of an operational solver for this class of optimization problems, featuring a methodology in this context. The arguments are illustrated using the knapsack problem as support, along numerical experiments.

The last decade has seen a growing body of research illustrating the advantages of the evolutionary multiobjective approach to data clustering. The scalability of such an approach, however, is a topic which merits more attention given the unprecedented volumes of data generated nowadays. This paper proposes a reduced-length representation for evolutionary multiobjective clustering. The new encoding explicitly prunes the solution space and allows the search method to focus on its most promising regions. Moreover, it allows us to precompute information in order to alleviate the computational overhead caused by the processing of candidate individuals during optimisation. We investigate the suitability of this proposal in the context of a representative algorithm from the literature: MOCK. Our results indicate that the new reduced-length representation significantly improves the effectiveness and computational efficiency of MOCK specifically, and can be seen as a further step towards a better scalability of evolutionary multiobjective clustering in general.

Maintaining an archive of all non-dominated points is a standard task in multi-objective optimization. Sometimes it is sufficient to store all evaluated points and to obtain the non-dominated subset in a post-processing step. Alternatively the non-dominated set can be updated on the fly. While keeping track of many non-dominated points efficiently is easy for two objectives, we propose an efficient algorithm based on a binary space partitioning (BSP) tree for the general case of three or more objectives. Our analysis and our empirical results demonstrate the superiority of the method over the brute-force baseline method, as well as graceful scaling to large numbers of objectives.

The number of objectives in real-world problems has increased in recent years and better algorithms are needed to deal efficiently with it. One possible improvement to such algorithms is the use of adaptive operator selection mechanisms in many-objective optimization algorithms. In this work, two adaptive operator selection mechanisms, Probability Matching (PM) and Adaptive Pursuit (AP), are incorporated into the NSGA-III framework to autonomously select the most suitable operator while solving a many-objective problem. Our proposed approaches, NSGA-III$$_{\text {AP}}$$ and NSGA-III$$_{\text {PM}}$$, are tested on benchmark instances from the DTLZ and WFG test suits and on instances of the Protein Structure Prediction Problem. Statistical tests are performed to infer the significance of the results. The preliminary results of the proposed approaches are encouraging.

In this paper, an interactive version of the ParEGO algorithm is introduced for identifying most preferred solutions for computationally expensive multiobjective optimization problems. It enables a decision maker to guide the search with her preferences and change them in case new insight is gained about the feasibility of the preferences. At each interaction, the decision maker is shown a subset of non-dominated solutions and she is assumed to provide her preferences in the form of preferred ranges for each objective. Internally, the algorithm samples reference points within the hyperbox defined by the preferred ranges in the objective space and uses a DACE model to approximate an achievement (scalarizing) function as a single objective to scalarize the problem. The resulting solution is then evaluated with the real objective functions and used to improve the DACE model in further iterations. The potential of the proposed algorithm is illustrated via a four-objective optimization problem related to water management with promising results.

In many real-world applications concerning multi-objective optimization, the true objective functions are not observable. Instead, only noisy observations are available. In recent years, the interest in the effect of such noise in evolutionary multi-objective optimization (EMO) has increased and many specialized algorithms have been proposed. However, evolutionary algorithms are not suitable if the evaluation of the objectives is expensive and only a small budget is available. One popular solution is to use model-based multi-objective optimization (MBMO) techniques. In this paper, we present a first investigation on noisy MBMO. For this purpose we collect several noise handling strategies from the field of EMO and adapt them for MBMO algorithms. We compare the performance of those strategies in two benchmark situations: Firstly, we perform a purely artificial benchmark using homogeneous Gaussian noise. Secondly, we choose a setting from the field of machine learning, where the structure of the underlying noise is unknown.

With recent advancements of multi- or many-objective optimization algorithms, researchers and decision-makers are increasingly faced with the dilemma of choosing the best algorithm to solve their problems. In this paper, we propose a simple hybridization of population-based multi- or many-objective optimization algorithms called fusion of non-dominated fronts using reference points (FNFR) to gain combined benefits of several algorithms. FNFR combines solutions from multiple optimization algorithms during or after several runs and extracts well-distributed solutions from a large set of non-dominated solutions using predefined structured reference points or user-defined reference points. The proposed FNFR is applied to non-dominated solutions obtained by the Generalized Differential Evolution Generation 3 (GDE3), Speed-constrained Multi-objective Particle Swarm Optimization (SMPSO), and the Strength Pareto Evolutionary Algorithm 2 (SPEA2) on seven unconstrained many-objective test problems with three to ten objectives. Experimental results show FNFR is an effective way for combining and extracting (fusion) of well-distributed non-dominated solutions among a large set of solutions. In fact, the proposed method is a solution-level hybridization approach. FNFR showed promising results when selecting well-distributed solutions around a specific region of interest.

The research in evolutionary multi-objective optimization is largely missing a notion of functional landscapes, which could enable a visual understanding of multimodal multi-objective landscapes and their characteristics by connecting decision and objective space. This consequently leads to the negligence of decision space in most algorithmic approaches and an almost complete lack of Exploratory Landscape Analysis (ELA) tools. This paper dares a first step into this unexplored field based on gradient properties of the multi-objective landscape. For a first time, basins of attraction and superpositions of local optima are visualized and thereby made intuitively accessible. With this work, we hope to highlight the importance of detailed decision space analysis in multi-objective optimization and to stimulate further research in that direction.

In multi-objective optimization approaches, considering neutral neighbors during the exploration has already proved its efficiency. The aim of this article is to go further in the comprehensibility of neutrality. In particular, we propose a definition of most promising neutral neighbors and study in details their distribution within neutral neighbors. As the correlation between objectives has an important impact on neighbors distribution, it will be studied. Three permutation problems are used as case studies and conclusions about neutrality encountered in these problems are provided.

This paper proposes a benchmark for multi-objective optimization based on video game playing. The challenge is to optimize an agent to perform well on several different games, where each objective score corresponds to the performance on a different game. The benchmark is inspired from the quest for general intelligence in the form of general game playing, and builds on the General Video Game AI (GVGAI) framework. As it is based on game-playing, this benchmark incorporates salient aspects of game-playing problems such as discontinuous feedback and a non-trivial amount of stochasticity. We argue that the proposed benchmark thus provides a different challenge from many other benchmarks for multi-objective optimization algorithms currently available. We also provide initial results on categorizing the space offered by this benchmark and applying a standard multi-objective optimization algorithm to it.

Evolutionary algorithms allow for solving a wide range of multi-objective optimization problems. Nevertheless for complex practical problems, including domain knowledge is imperative to achieve good results. In many domains, single-objective expert knowledge is available, but its integration into modern multi-objective evolutionary algorithms (MOEAs) is often not trivial and infeasible for practitioners. In addition to the need of modifying algorithm architectures, the challenge of combining single-objective knowledge to multi-objective rules arises. This contribution takes a step towards a multi-objective optimization framework with defined interfaces for expert knowledge integration. Therefore, multi-objective mutation and local search operators are integrated into the two MOEAs MOEA/D and R-NSGAII. Results from experiments on exemplary machine scheduling problems prove the potential of such a concept and motivate further research in this direction.

Multi-objective optimization with more than three objectives has become one of the most active topics in evolutionary multi-objective optimization (EMO). However, most existing studies limit their experiments up to 15 or 20 objectives, although they claimed to be capable of handling as many objectives as possible. To broaden the insights in the behavior of EMO methods when facing a massively large number of objectives, this paper presents some preliminary empirical investigations on several established scalable benchmark problems with 25, 50, 75 and 100 objectives. In particular, this paper focuses on the behavior of the currently pervasive reference point based EMO methods, although other methods can also be used. The experimental results demonstrate that the reference point based EMO method can be viable for problems with a massively large number of objectives, given an appropriate choice of the distance measure. In addition, sufficient population diversity should be given on each weight vector or a local niche, in order to provide enough selection pressure. To the best of our knowledge, this is the first time an EMO methodology has been considered to solve a massively large number of conflicting objectives.

Integrating user preferences in Evolutionary Multiobjective Optimization (EMO) is currently a prevalent research topic. There is a large variety of preference handling methods (originated from Multicriteria decision making, MCDM) and EMO methods, which have been combined in various ways. This paper proposes a Web Ontology Language (OWL) ontology to model and systematize the knowledge of preference-based multiobjective evolutionary algorithms (PMOEAs). Detailed procedure is given on how to build and use the ontology with the help of Protégé. Different use-cases, including training new learners, querying and reasoning are exemplified and show remarkable benefit for both EMO and MCDM communities.

We study the difficulty of solving different bi-objective formulations of the permutation flowshop scheduling problem by adopting a fitness landscape analysis perspective. Our main goal is to shed the light on how different problem features can impact the performance of Pareto local search algorithms. Specifically, we conduct an empirical analysis addressing the challenging question of quantifying the individual effect and the joint impact of different problem features on the success rate of the considered approaches. Our findings support that multi-objective fitness landscapes enable to devise sound general-purpose features for assessing the expected difficulty in solving permutation flowshop scheduling problems, hence pushing a step towards a better understanding of the challenges that multi-objective randomized search heuristics have to face.

Demand Responsive Transport (DRT) systems emanate as a substitute to face the problem of volatile, or even inconstant, demand, occurring in popular urban transport systems. This paper is focused in the Vehicle Routing Problem with Demand Responsive Transport (VRPDRT), a type of transport which enables passengers to be taken to their destination, as a shared service, trying to minimize the company costs and offer a quality service taking passengers on their needs. A many-objective approach is applied in VRPDRT in which seven different objective functions are used. To solve the problem through traditional multi-objective algorithms, the work proposes the usage of cluster analysis to perform the dimensionaly reduction task. The seven functions are then aggregated resulting in a bi-objective formulation and the algorithms NSGA-II and SPEA 2 are used to solve the problem. The results show that the algorithms achieve statistically different results and NSGA-II reaches a greater number of non-dominated solutions when compared to SPEA 2. Furthermore, the results are compared to an approach proposed in literature that uses another way to reduce the dimensionality of the problem in a two-objective formulation and the cluster analysis procedure is proven to be a competitive methodology in that problem. It is possbile to say that the behavior of the algorithm is modified by the way the dimensionality reduction of the problem is made.

Consider a self-organized system of heterogeneous reconfigurable agents solving a multi-objective task. In this paper we analyze an evolutionary approach to make such a system adaptable. In principle, this system is comparable to a multi-objective genetic algorithm, however, requires asynchronous generations and decentralized evaluation- and selection processes. The primary objective of this paper is to introduce the proposed system, to provide several interesting theoretic properties and a primary experimental analysis. The heritable material (genes) compromises a parameter set that encodes an agents configuration and can be communicated between agents. We introduce partial redundancy into the system by supplying a certain number of agents with two parameter sets instead of one. These agents are denoted as redundant and are free to chose which of their two parameter sets is applied. A special focus lies on two strategies for the agents to derive a fitness value based on their property set(s) and the respective objective functions of the multi-objective task suitable for decentralized systems. A slightly more sophisticated approach with weights for each of the objectives performs just as good as a simple method where agents pick the best or respectively worst objective value. The results show that systems with low redundancy tend to lose a lot of diversity, however, redundant systems are slower in their adaptive process.

Due to the excessive cost of Monte Carlo simulation, metamodel is now frequently used to accelerate the process of robustness estimation. In this paper, we explore the use of multiple metamodels for robustness evaluation in multi-objective evolutionary robust optimization under parametric uncertainty. The concept is to build several different metamodel types, and employ cross-validation to pick the best metamodel or to create an ensemble of metamodels. Three types of metamodel were investigated: sparse polynomial chaos expansion (PCE), Kriging, and 2$$^\text {nd}$$ order polynomial regression (PR). Numerical study on robust optimization of two test problems was performed. The result shows that the ensemble approach works well when all the constituent metamodel is sufficiently accurate, while the best scheme is more favored when there is a constituent metamodel with poor quality. Moreover, besides the accuracy, we found that it is also important to preserve the trend and smoothness of the decision variables-robustness relationship. PR, which is the less accurate metamodel from all, can found a better representation of the Pareto front than the sparse PCE.

The multiobjective scheduling problem on unrelated parallel machines is tackled by predator-prey techniques. Several objectives adopted in the literature were considered and the corresponding best aligned dispatch rules were associated with the predators. Also, we suggest and analyse modifications in the movement operator, in the number of predators, and in the influence of the objectives in the selection/replacement procedures. Numerical comparisons with the popular NSGA-II were performed and good results were obtained by the predator-prey techniques.

Scalarizing functions play a crucial role in multi-objective evolutionary algorithms (MOEAs) based on decomposition and the R2 indicator, since they guide the population towards nearly optimal solutions, assigning a fitness value to an individual according to a predefined target direction in objective space. This paper presents a general review of weighted scalarizing functions without constraints, which have been proposed not only within evolutionary multi-objective optimization but also in the mathematical programming literature. We also investigate their scalability up to 10 objectives, using the test problems of Lamé Superspheres on the MOEA/D and MOMBI-II frameworks. For this purpose, the best suited scalarizing functions and their model parameters are determined through the evolutionary calibrator EVOCA. Our experimental results reveal that some of these scalarizing functions are quite robust and suitable for handling many-objective optimization problems.

The increase of complexity in virtual product design requires high-quality optimization algorithms capable to find the global parameter solution for a given problem. The representation, which defines the encoding of the design and the mapping from parameter space to design space, is a key aspect for the performance of the optimization process. To initialize representations for a high performing optimization we utilize the concept of evolvability. Our interpretation of this concept consists of three performance criteria, namely variability, regularity, and improvement potential, where regularity and improvement potential characterize conflicting goals. In this article we address the generation of initial representation setups trading off between these two conflicting criteria for design optimization. We analyze Pareto-optimal compromises for deformation representations with radial basis functions in two test scenarios: fitting of 1D height fields and fitting of 3D face scans. We use the Pareto front as a ground-truth to show the feasibility of a single-objective optimization targeting one preference-based trade-off. Based on the results of both optimization approaches we propose two heuristic methods, Lloyd sampling and orthogonal least squares sampling, targeting representations with high regularity and high improvement potential at the two ends of the Pareto front. Thereby, we overcome the time consuming process of an evolutionary optimization to set up high-performing representations for these two cases.

Simultaneous optimization of several physiochemical properties is an important task in the drug design process. Molecule optimization formulated as optimization problems usually provide several conflicting objectives. The number of molecular properties as well as the cost-intensive methods of molecule property prediction are stringent requirements to in silico aided drug design process. Numerical approximations of the physiochemical molecule properties are challenging and in vitro methods are still essential. The objective of an in silico aided drug design process is the evolution of a multi-objective evolutionary process with the potential of a selected number of improved molecule identification within a very low iteration number for a further efficient laboratory examinations. This paper presents design perspectives of a multi-objective evolutionary process that identifies a wide variety of genetic different but selected number of optimized molecules within a low number of generations. Its search behavior is compared to NSGA-II. Furthermore, limitations of the proposed algorithm are demonstrated with regard to its performance in many-objective molecular optimization and potential concepts of adaptations for this purpose are discussed.

Over the last few decades we have experienced a plethora of successful optimization concepts, algorithms, techniques and softwares. Each trying to excel in its own niche. Logically, combining a carefully selected subset of them may deliver a novel approach that brings together the best of some those previously independent worlds. The span of applicability of the new approach and the magnitude of improvement are completely dependent on the selected techniques and the level of perfection in weaving them together. In this study, we combine NSGA-III with local search and use the recently proposed Karush-Kuhn-Tucker Proximity Measure (KKTPM) to guide the whole process. These three carefully selected building blocks are intended to perform well on several levels. Here, we focus on Diversity and Convergence (DC-NSGA-III), hence we use Local Search and KKTPM respectively, in the course of a multi/many objective algorithm (NSGA-III). The results show how DC-NSGA-III can significantly improve performance on several standard multi- and many-objective optimization problems.

In Simulation-based Evolutionary Multi-objective Optimization, the number of simulation runs is very limited, since the complex simulation models require long execution times. With the help of preference information, the optimization result can be improved by guiding the optimization towards relevant areas in the objective space with, for example, the Reference Point-based NSGA-II algorithm (R-NSGA-II) [4]. Since the Pareto-relation is the primary fitness function in R-NSGA-II, the algorithm focuses on exploring the objective space with high diversity. Only after the population has converged close to the Pareto-front does the influence of the reference point distance as secondary fitness criterion increase and the algorithm converges towards the preferred area on the Pareto-front.In this paper, we propose a set of extensions of R-NSGA-II which adaptively control the algorithm behavior, in order to converge faster towards the reference point. The adaption can be based on criteria such as elapsed optimization time or the reference point distance, or a combination thereof. In order to evaluate the performance of the adaptive extensions of R-NSGA-II, a performance metric for reference point-based EMO algorithms is used, which is based on the Hypervolume measure called the Focused Hypervolume metric [12]. It measures convergence and diversity of the population in the preferred area around the reference point. The results are evaluated on two benchmark problems of different complexity and a simplistic production line model.

MR-Sort (Majority Rule Sorting) is a multiple criteria sorting method which assigns an alternative a to category $$C^h$$ when a is better than the lower limit of $$C^h$$ on a weighted majority of criteria, and this is not true with the upper limit of $$C^h$$. We enrich the descriptive ability of MR-Sort by the addition of coalitional vetoes which operate in a symmetric way as compared to the MR-Sort rule w.r.t. to category limits, using specific veto profiles and veto weights. We describe a heuristic algorithm to learn such an MR-Sort model enriched with coalitional veto from a set of assignment examples, and show how it performs on real datasets.

This paper investigates a curious case of informed initialization technique to solve difficult multi-objective optimization (MOP) problems. The initial population was injected with non-exact (i.e. approximated) nadir objective vectors, which are the boundary solutions of a Pareto optimal front (PF). The algorithm then successively improves those boundary solutions and utilizes them to generate non-dominated solutions targeted to the vicinity of the PF along the way. The proposed technique was ported to a standard Evolutionary Multi-objective Optimization (EMO) algorithm and tested on a wide variety of benchmark MOP problems. The experimental results suggest that the proposed approach is very helpful in achieving extremely fast convergence, especially if an experimenter’s goal is to find a set of well distributed trade-off solutions within a fix-budgeted solution evaluations (SEs). The proposed approach also ensures a more focused exploration of the underlying search space.

We investigate the impact of three control parameters (the population size $$\mu $$, the number of children $$\lambda $$, and the number of reference points H) on the performance of Nondominated Sorting Genetic Algorithm III (NSGA-III). In the past few years, many efficient Multi-Objective Evolutionary Algorithms (MOEAs) for Many-Objective Optimization Problems (MaOPs) have been proposed, but their control parameters have been poorly analyzed. The recently proposed NSGA-III is one of most promising MOEAs for MaOPs. It is widely believed that NSGA-III is almost parameter-less and requires setting only one control parameter (H), and the value of $$\mu $$ and $$\lambda $$ can be set to $$\mu = \lambda \approx H$$ as described in the original NSGA-III paper. However, the experimental results in this paper show that suitable parameter settings of $$\mu $$, $$\lambda $$, and H values differ from each other as well as their widely used parameter settings. Also, the performance of NSGA-III significantly depends on them. Thus, the usually used parameter settings of NSGA-III (i.e., $$\mu = \lambda \approx H$$) might be unsuitable in many cases, and $$\mu $$, $$\lambda $$, and H require a particular parameter tuning to realize the best performance of NSGA-III.

The liner shipping fleet repositioning problem (LSFRP) is a central optimization problem within the container shipping industry. Several approaches exist for solving this problem using exact and heuristic techniques, however all of them use a single objective function for determining an optimal solution. We propose a multi-objective approach based on a simulated annealing heuristic so that repositioning coordinators can better balance profit making with cost-savings and environmental sustainability. As the first multi-objective approach in the area of liner shipping routing, we show that giving more options to decision makers need not be costly. Indeed, our approach requires no extra runtime than a weighted objective heuristic and provides a rich set of solutions along the Pareto front.

In this paper, we propose a novel approach (SAPEO) to support the survival selection process in evolutionary multi-objective algorithms with surrogate models. The approach dynamically chooses individuals to evaluate exactly based on the model uncertainty and the distinctness of the population. We introduce multiple SAPEO variants that differ in terms of the uncertainty they allow for survival selection and evaluate their anytime performance on the BBOB bi-objective benchmark. In this paper, we use a Kriging model in conjunction with an SMS-EMOA for SAPEO. We compare the obtained results with the performance of the regular SMS-EMOA, as well as another surrogate-assisted approach. The results open up general questions about the applicability and required conditions for surrogate-assisted evolutionary multi-objective algorithms to be tackled in the future.

Many evolutionary algorithms are designed to solve black-box multi-objective optimization problems (MOPs) using stochastic operators, where neither the form nor the gradient information of the problem is accessible. In some real-world applications, e.g. surrogate-based global optimization, the gradient of the objective function is accessible. In this case, it is straightforward to use a gradient-based multi-objective optimization algorithm to achieve fast convergence speed and the stability of the solution. In a relatively recent approach, the hypervolume indicator gradient in the decision space is derived, which paves the way for the method for maximizing the hypervolume indicator of a fixed size population. In this paper, several mechanisms which originated in the field of evolutionary computation are proposed to make this gradient ascent method applicable. Specifically, the well-known non-dominated sorting is used to help steering the dominated points. The principle of the so-called cumulative step-size control that is originally proposed for evolution strategies is adapted to control the step-size dynamically. The resulting algorithm is called Hypervolume Indicator Gradient Ascent Multi-objective Optimization (HIGA-MO). The proposed algorithm is tested on ZDT problems and its performance is compared to other methods of moving the dominated points as well as to some evolutionary multi-objective optimization algorithms that are commonly used.

We give a definition for step size optimality in multiobjective optimization and visualize the optimal step sizes for a few two-dimensional example constellations. After that, we try to engineer a step size adaptation mechanism that also works in the real world. For this mechanism, we employ the self-adaptation of mutation strength, which is simple and well-known from single-objective optimization. The resulting approach obtains better results than simulated binary crossover and polynomial mutation on the bi-objective BBOB testbed.

The Expected Hypervolume Improvement (EHVI) is a frequently used infill criterion in surrogate-assisted multi-criterion optimization. It needs to be frequently called during the execution of such algorithms. Despite recent advances in improving computational efficiency, its running time for three or more objectives has remained in $$O(n^d)$$ for $$d\ge 3$$, where d is the number of objective functions and n is the size of the incumbent Pareto-front approximation. This paper proposes a new integration scheme, which makes it possible to compute the EHVI in $$\varTheta (n \log n)$$ optimal time for the important three-objective case ($$d=3$$). The new scheme allows for a generalization to higher dimensions and for computing the Probability of Improvement (PoI) integral efficiently. It is shown, both theoretically and empirically, that the hidden constant in the asymptotic notation is small. Empirical speed comparisons were designed between the C++ implementations of the new algorithm (which will be in the public domain) and those recently published by competitors, on randomly-generated non-dominated fronts of size 10, 100, and 1000. The experiments include the analysis of batch computations, in which only the parameters of the probability distribution change but the incumbent Pareto-front approximation stays the same. Experimental results show that the new algorithm is always faster than the other algorithms, sometimes over $$10^4$$ times faster.