GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation ConferenceFull Citation in the ACM Digital Library
SESSION: Evolutionary multiobjective optimization
On the one hand, surrogate-assisted evolutionary algorithms are established as a method of choice for expensive black-box optimization problems. On the other hand, the growth in computing facilities has seen a massive increase in potential computational power, granted the users accommodate their approaches with the offered parallelism. While a number of studies acknowledge the impact of parallelism for single-objective expensive optimization assisted by surrogates, extending such techniques to the multi-objective setting has not yet been properly investigated, especially within the state-of-the-art decomposition framework. We first highlight the different degrees of parallelism in existing surrogate-assisted multi-objective evolutionary algorithms based on decomposition (S-MOEA/D). We then provide a comprehensive analysis of the key steps towards a successful parallel S-MOEA/D approach. Through an extensive benchmarking effort relying on the well-established bbob-biobj test functions, we analyze the performance of the different algorithm designs with respect to the problem dimensionality and difficulty, the amount of parallel cores available, and the supervised learning models considered. In particular, we show the difference in algorithm scalability based on the selected surrogate-assisted approaches, the performance impact of distributing the model training task and the efficacy of the designed parallel-surrogate methods.
Both feature selection and hyperparameter tuning are key tasks in machine learning. Hyperparameter tuning is often useful to increase model performance, while feature selection is undertaken to attain sparse models. Sparsity may yield better model interpretability and lower cost of data acquisition, data handling and model inference. While sparsity may have a beneficial or detrimental effect on predictive performance, a small drop in performance may be acceptable in return for a substantial gain in sparseness. We therefore treat feature selection as a multi-objective optimization task. We perform hyperparameter tuning and feature selection simultaneously because the choice of features of a model may influence what hyperparameters perform well.
We present, benchmark, and compare two different approaches for multi-objective joint hyperparameter optimization and feature selection: The first uses multi-objective model-based optimization. The second is an evolutionary NSGA-II-based wrapper approach to feature selection which incorporates specialized sampling, mutation and recombination operators. Both methods make use of parameterized filter ensembles.
While model-based optimization needs fewer objective evaluations to achieve good performance, it incurs computational overhead compared to the NSGA-II, so the preferred choice depends on the cost of evaluating a model on given data.
This paper introduces the mathematical development and algorithm of the Improvement-Directions Mapping (IDM) method, which computes improvement directions to "push" the current solutions toward the true Pareto front. The main idea is to compute normal vectors to the front, as improvement directions in the objective space, to be then transformed into search directions in the variable space through a transformation tensor. The main contributions of the IDM as a local search operator versus previous approaches are the following: 1) It does not require of a priori information about improvement directions or location of the true Pareto front, 2) It uses a local quadratic approximation of the Pareto front to compute the transformation tensor, thus, reducing numerical problems and avoiding abrupt changes in the search direction which could lead to erratic searches. These features allow the IDM to be implemented as a local search operator within any Multi-objective Evolutionary Algorithm (MOEA). The potential of the IDM is shown by hybridizing two well-known multi-objective algorithms: a) MOEA/D + IDM; b) NSGA-II + IDM. In the first approach, IDM "pushes" the offspring population in each iteration. A similar experiment is performed with the second approach. Furthermore, one more experiment evaluates the IDM as a refinement step that is applied to the last Pareto front delivered by NSGA-II.
Data structures for non-dominated sets: implementations and empirical assessment of two decades of advances
Many data structures have been developed over the last two decades for the storage and efficient update of unconstrained sets of mutually non-dominating solutions. Typically, analysis has been provided in the original works for these data structures in terms of worst/average case complexity performance. Often, however, other aspects such as rebalancing costs of underlying data structures, cache sizes, etc., can also significantly affect behaviour. Empirical performance comparison has often (but not always) been limited to run-time comparison with a basic linear list. No comprehensive comparison between the different specialised data structures proposed in the last two decades has thus far been undertaken. We take significant strides in addressing this here. Eight data structures from the literature are implemented within the same overarching open source Java framework. We additionally highlight and rectify some errors in published work --- and offer additional efficiency gains. Run-time performances are compared and contrasted, using data sequences embodying a number of different characteristics. We show that in different scenarios different data structures are preferable, and that those with the lowest big O complexity are not always the best performing. We also find that performance profiles can vary drastically with computational architecture, in a non-linear fashion.
Another difficulty of inverted triangular pareto fronts for decomposition-based multi-objective algorithms
A set of uniformly sampled weight vectors from a unit simplex has been frequently used in decomposition-based multi-objective algorithms. The number of the generated weight vectors is controlled by a user-defined parameter H. In the literature, good results are often reported on test problems with triangular Pareto fronts since the shape of the Pareto fronts is consistent with the distribution of the weight vectors. However, when a problem has an inverted triangular Pareto front, well-distributed solutions over the entire Pareto front are not obtained due to the inconsistency between the Pareto front shape and the weight vector distribution. In this paper, we demonstrate that the specification of H has an unexpected large effect on the performance of decomposition-based multi-objective algorithms when the test problems have inverted triangular Pareto fronts. We clearly explain why their performance is sensitive to the specification of H in an unexpected manner (e.g., H = 3 is bad but H = 4 is good for three-objective problems whereas H = 3 is good but H = 4 is bad for four-objective problems). After these discussions, we suggest a simple weight vector specification method for inverted triangular Pareto fronts.
Effects of dominance resistant solutions on the performance of evolutionary multi-objective and many-objective algorithms
Dominance resistant solutions (DRSs) in multi-objective problems have very good values for some objectives and very bad values for other objectives. Whereas DRSs are far away from the Pareto front, they are hardly dominated by other solutions due to some very good objective values. It is well known that the existence of DRSs severely degrades the search ability of Pareto dominance-based algorithms such as NSGA-II and SPEA2. In this paper, we examine the effect of DRSs on the search ability of NSGA-II on the DTLZ test problems with many objectives. We slightly change their problem formulation to increase the size of the DRS region. Through computational experiments, we show that DRSs have a strong negative effect on the search ability of NSGA-II whereas they have almost no effect on MOEA/D with the PBI function. We also show that a slightly modified NSGA-II for decreasing the negative effect of DRSs works well on many-objective DTLZ test problems (its performance is similar to NSGA-III and MOEA/D). These results suggest that DTLZ is not an appropriate test suite for evaluating many-objective evolutionary algorithms. This issue is further addressed through computational experiments on newly formulated test problems with no distance function.
Despite significant advantages in theory of evolutionary computation, many papers related to evolutionary algorithms still lack proper analysis and limit themselves by rather vague reflections on why making a certain design choice improves the performance. While this seems to be unavoidable when talking about the behavior of an evolutionary algorithm on a practical optimization problem, doing the same for computational complexities of parts of evolutionary algorithms is harmful and should be avoided.
Non-dominated sorting is one of such parts, commonly used in various evolutionary multiobjective algorithms. The complexity of the problem as such is not well-understood, and many algorithms were proposed for solving it in recent years. Unfortunately, the analysis of some of them is imperfect. In this paper, we prove that, contrary to what is claimed by its authors, the algorithm known as Deductive Sort has the worst-case time complexity of Θ(MN3), where M is the number of objectives and N is the population size. However, if one shuffles the input, the worst-case expected running time drops down to O(MN2).
The hypervolume contribution is an important concept in hypervolume-based evolutionary multi-objective optimization algorithms. It describes the loss of the hypervolume when a solution is removed from the current population. Since its calculation is #P-hard in the number of objectives, its approximation is necessary for many-objective optimization problems. Recently, an R2-based hypervolume contribution approximation method was proposed. This method relies on a set of direction vectors for the approximation. However, the influence of different direction vector generation methods on the approximation quality has not been studied yet. This paper aims to investigate this issue. Five direction vector generation methods are investigated, including Das and Dennis's method (DAS), unit normal vector method (UNV), JAS method, maximally sparse selection method with DAS (MSS-D), and maximally sparse selection method with UNV (MSS-U). Experimental results suggest that the approximation quality strongly depends on the direction vector generation method. The JAS and UNV methods show the best performance whereas the DAS method shows the worst performance. The reasons behind the results are also analyzed.
Practitioners often encounter computationally expensive multiobjective optimization problems to be solved in a variety of real-world applications. On the purpose of challenging these problems, we propose a new surrogate-based multiobjective optimization algorithm that does not require a large evaluation budget. It is called Multiobjective Tree-structured Parzen Estimator (MOTPE) and is an extension of the tree-structured Parzen estimator widely used to solve expensive single-objective optimization problems. Our empirical evidences reveal that MOTPE can approximate Pareto fronts of many benchmark problems better than existing methods with a limited budget. In this paper, we discuss furthermore the influence of MOTPE configurations to understand its behavior.
Surrogate-assisted multi-objective combinatorial optimization based on decomposition and walsh basis
We consider the design and analysis of surrogate-assisted algorithms for expensive multi-objective combinatorial optimization. Focusing on pseudo-boolean functions, we leverage existing techniques based on Walsh basis to operate under the decomposition framework of MOEA/D. We investigate two design components for the cheap generation of a promising pool of offspring and the actual selection of one solution for expensive evaluation. We propose different variants, ranging from a filtering approach that selects the most promising solution at each iteration by using the constructed Walsh surrogates to discriminate between a pool of offspring generated by variation, to a substitution approach that selects a solution to evaluate by optimizing the Walsh surrogates in a multi-objective manner. Considering bi-objective NK landscapes as benchmark problems offering different degree of non-linearity, we conduct a comprehensive empirical analysis including the properties of the achievable approximation sets, the anytime performance, and the impact of the order used to train the Walsh surrogates. Our empirical findings show that, although our surrogate-assisted design is effective, the optimal integration of Walsh models within a multi-objective evolutionary search process gives rise to particular questions for which different trade-off answers can be obtained.
Runtime analysis of evolutionary algorithms with biased mutation for the multi-objective minimum spanning tree problem
Evolutionary algorithms (EAs) are general-purpose problem solvers that usually perform an unbiased search. This is reasonable and desirable in a black-box scenario. For combinatorial optimization problems, often more knowledge about the structure of optimal solutions is given, which can be leveraged by means of biased search operators. We consider the Minimum Spanning Tree (MST) problem in a single- and multi-objective version, and introduce a biased mutation, which puts more emphasis on the selection of edges of low rank in terms of low domination number. We present example graphs where the biased mutation can significantly speed up the expected runtime until (Pareto-)optimal solutions are found. On the other hand, we demonstrate that bias can lead to exponential runtime if "heavy" edges are necessarily part of an optimal solution. However, on general graphs in the single-objective setting, we show that a combined mutation operator which decides for unbiased or biased edge selection in each step with equal probability exhibits a polynomial upper bound - as unbiased mutation - in the worst case and benefits from bias if the circumstances are favorable.
Building a surrogate model of an objective function has shown to be effective to assist evolutionary algorithms (EAs) to solve real-world complex optimisation problems which involve either computationally expensive numerical simulations or costly physical experiments. However, their effectiveness mostly focuses on small-scale problems with less than 10 decision variables. The scalability of surrogate assisted EAs (SAEAs) have not been well studied yet. In this paper, we propose a Gaussian process surrogate model assisted EA for medium-scale expensive multi-objective optimisation problems with up to 50 decision variables. There are three distinctive features of our proposed SAEA. First, instead of using all decision variables in surrogate model building, we only use those correlated ones to build the surrogate model for each objective function. Second, rather than directly optimising the surrogate objective functions, the original multi-objective optimisation problem is transformed to a new one based on the surrogate models. Last but not the least, a subset selection method is developed to choose a couple of promising candidate solutions for actual objective function evaluations thus to update the training dataset. The effectiveness of our proposed algorithm is validated on benchmark problems with 10, 20, 50 variables, comparing with three state-of-the-art SAEAs.
On the elicitation of indirect preferences in interactive evolutionary multiple objective optimization
We consider essential challenges related to the elicitation of indirect preference information in interactive evolutionary algorithms for multiple objective optimization. The methods in this stream use holistic judgments provided by the Decision Maker (DM) to progressively bias the evolutionary search toward his/her most preferred region in the Pareto front. We enhance such an interactive process using three targeted developments and illustrate their efficiency in the context of a decomposition-based evolutionary framework. Firstly, we present some active learning strategies for selecting solutions from the current population that should be critically compared by the DM. These strategies implement the paradigm of maximizing the potential information gain derived from the DM's answer. Secondly, we discuss the procedures for deciding when the DM should be questioned for preference information. In this way, we refer to a more general problem of distributing the DM's interactions with the method in a way that ensures sufficient evolutionary pressure. Thirdly, we couple the evolutionary schemes with different types of indirect preferences, including pairwise comparisons, preference intensities, best-of-k judgments, and complete orders of a small subset of solutions. A thorough experimental analysis indicates that the three introduced advancements have a positive impact on the DM-perceived quality of constructed solutions.
Over 30 years, evolutionary multi- and many-objective optimization (EMO/EMaO) algorithms have been extensively applied to find well-distributed Pareto-optimal (PO) solutions in a single run. However, in real-world problems, the PO front may not always be a single continuous hyper-surface, rather several irregularities may exist involving disjointed surfaces, holes within the surface, or patches of mixed-dimensional surfaces. When a set of trade-off solutions are obtained by EMO/EMaO algorithms, there may exist less dense or no solutions (we refer as 'gaps') in certain parts of the front. This can happen for at least two reasons: (i) gaps naturally exist in the PO front, or (ii) no natural gaps exists, but the chosen EMO/EMaO algorithm is not able to find any solution in the apparent gaps. To make a confident judgement, we propose a three-step procedure here. First, we suggest a computational procedure to identify gaps, if any, in the EMO/EMaO-obtained PO front. Second, we propose a computational method to identify well-distributed gap-points in the gap regions. Third, we apply a focused EMO/EMaO algorithm to search for possible representative trade-off points in the gaps. We then propose two metrics to qualitatively establish whether a gap truly exists in the obtained dataset, and if yes, whether the gap naturally exists on the true Pareto-set. Procedures are supported by results on two to five-objective test problems and on a five-objective scheduling problem from a steel-making industry.
Transfer learning for gaussian process assisted evolutionary bi-objective optimization for objectives with different evaluation times
Despite the success of evolutionary algorithms (EAs) for solving multi-objective problems, most of them are based on the assumption that all objectives can be evaluated within the same period of time. However, in many real-world applications, such an assumption is unrealistic since different objectives must be evaluated using different computer simulations or physical experiments with various time complexities. To address this issue, a surrogate assisted evolutionary algorithm along with a parameter-based transfer learning (T-SAEA) is proposed in this work. While the surrogate for the cheap objective can be updated on sufficient training data, the surrogate for the expensive one is updated by either the training data set or a transfer learning approach. To find out the transferable knowledge, a filter-based feature selection algorithm is used to capture the pivotal features of each objective, and then use the common important features as a carrier for knowledge transfer between the cheap and expensive objectives. Then, the corresponding parameters in the surrogate models are adaptively shared to enhance the quality of the surrogate models. The experimental results demonstrate that the proposed algorithm outperforms the compared algorithms on the bi-objective optimization problems whose objectives have a large difference in computational complexities.
The Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D) has shown high-performance levels when solving complicated multi-objective optimization problems. However, its adaptation for dealing with constrained multi-objective optimization problems (cMOPs) keeps being under the scope of recent investigations. This paper introduces a novel selection mechanism inspired by the ε-constraint method, which builds a bi-objective problem considering the scalarizing function (used into the decomposition approach of MOEA/D) and the constraint violation degree as an objective function. During the selection step of MOEA/D, the scalarizing function is considered to choose the best solutions to the cMOP. Preliminary results obtained over a set of complicated test problems drawn from the CF test suite indicate that the proposed algorithm is highly competitive regarding state-of-the-art MOEAs adopted in our comparative study.