Preference-based evolutionary multi-objective optimization (PBEMO) is an effective approach for approximating the region of interest (ROI) defined by the preference information from a decision maker. An existing PBEMO algorithm is an ad-hoc extension of a conventional EMO algorithm to approximate a target ROI. However, a tedious trial-and-error process is required to extend a base EMO algorithm for a particular ROI in an ad-hoc manner. To address this issue, this paper proposes a bi-criteria selection framework (BSF) that can extend any (μ + λ)-EMO algorithm for preference-based optimization of any ROI. In environmental selection, first, the proposed BSF defines an approximation of a ROI. Then, two types of selection are performed based on the number of individuals in the approximation. We investigate the effectiveness of the proposed BSF by incorporating it into seven EMO algorithms, including NSGA-II. The results show that BSF can successfully integrate the preference information into conventional EMO algorithms. The results also show that the BSF versions of the EMO algorithms perform similarly to or better than two representative PBEMO algorithms (R-NSGA-II and g-NSGA-II) in most cases.

In evolutionary multi-objective optimization, the indicator-based subset selection problem involves finding a subset of points that maximizes a given quality indicator. Local search is an effective approach for obtaining a high-quality subset in this problem. However, local search requires high computational cost, especially as the size of the point set and the number of objectives increase. To address this issue, this paper proposes a candidate list strategy for local search in the indicator-based subset selection problem. In the proposed strategy, each point in a given point set has a candidate list. During search, each point is only eligible to swap with unselected points in its associated candidate list. This restriction drastically reduces the number of swaps at each iteration of local search. We consider two types of candidate lists: nearest neighbor and random neighbor lists. This paper investigates the effectiveness of the proposed candidate list strategy on various Pareto fronts. The results show that the proposed strategy with the nearest neighbor list can significantly speed up local search on continuous Pareto fronts without significantly compromising the subset quality. The results also show that the sequential use of the two lists can address the discontinuity of Pareto fronts.

The indicator-based subset selection problem (ISSP) involves finding a point subset that minimizes or maximizes a quality indicator. The ISSP is frequently found in evolutionary multi-objective optimization (EMO). An in-depth understanding of the landscape of the ISSP could be helpful in developing efficient subset selection methods and explaining their performance. However, the landscape of the ISSP is poorly understood. To address this issue, this paper analyzes the landscape of the ISSP by using various traditional landscape analysis measures and exact local optima networks (LONs). This paper mainly investigates how the landscape of the ISSP is influenced by the choice of a quality indicator and the shape of the Pareto front. Our findings provide insightful information about the ISSP. For example, high neutrality and many local optima are observed in the results for ISSP instances with the additive ϵ-indicator.

Differential evolution (DE) generally requires parameter control methods (PCMs) for the scale factor and crossover rate. Although a better understanding of PCMs provides a useful clue to designing an efficient DE, their effectiveness is poorly understood in mixed-integer black-box optimization. In this context, this paper benchmarks PCMs in DE on the mixed-integer black-box optimization benchmarking function (bbob-mixint) suite in a componentwise manner. First, we demonstrate that the best PCM significantly depends on the combination of the mutation strategy and repair method. Although the PCM of SHADE is state-of-the-art for numerical black-box optimization, our results show its poor performance for mixed-integer black-box optimization. In contrast, our results show that some simple PCMs (e.g., the PCM of CoDE) perform the best in most cases. Then, we demonstrate that a DE with a suitable PCM performs significantly better than CMA-ES with integer handling for larger budgets of function evaluations. Finally, we show how the adaptation in the PCM of SHADE fails.

Some quality indicators have been proposed for benchmarking preference-based evolutionary multi-objective optimization algorithms using a reference point. Although a systematic review and analysis of the quality indicators are helpful for both benchmarking and practical decision-making, neither has been conducted. In this context, first, this paper reviews existing regions of interest and quality indicators for preference-based evolutionary multi-objective optimization using the reference point. We point out that each quality indicator was designed for a different region of interest. Then, this paper investigates the properties of the quality indicators. We demonstrate that an achievement scalarizing function value is not always consistent with the distance from a solution to the reference point in the objective space. We observe that the regions of interest can be significantly different depending on the position of the reference point and the shape of the Pareto front. We identify undesirable properties of some quality indicators. We also show that the ranking of preference-based evolutionary multi-objective optimization algorithms depends on the choice of quality indicators.

Although the population size is an important parameter in evolutionary multi-objective optimization (EMO), little is known about its influence on preference-based EMO (PBEMO). The effectiveness of an unbounded external archive (UA) in PBEMO is also poorly understood, where the UA maintains all non-dominated solutions found so far. In addition, existing methods for postprocessing the UA cannot handle the decision maker's preference information. In this context, first, this paper proposes a preference-based postprocessing method for selecting representative solutions from the UA. Then, we investigate the influence of the UA and population size on the performance of PBEMO algorithms. Our results show that the performance of PBEMO algorithms (e.g., R-NSGA-II) can be significantly improved by using the UA and the proposed method. We demonstrate that a smaller population size than commonly used is effective in most PBEMO algorithms for a small budget of function evaluations, even for many objectives. We found that the size of the region of interest is a less important factor in selecting the population size of the PBEMO algorithms on real-world problems.

This paper proposes a two-phase framework with a Bézier simplex-based interpolation method (TPB) for computationally expensive multi-objective optimization. The first phase in TPB aims to approximate a few Pareto optimal solutions by optimizing a sequence of single-objective scalar problems. The first phase in TPB can fully exploit a state-of-the-art single-objective derivative-free optimizer. The second phase in TPB utilizes a Bézier simplex model to interpolate the solutions obtained in the first phase. The second phase in TPB fully exploits the fact that a Bézier simplex model can approximate the Pareto optimal solution set by exploiting its simplex structure when a given problem is simplicial. We investigate the performance of TPB on the 55 bi-objective BBOB problems. The results show that TPB performs significantly better than HMO-CMA-ES and some state-of-the-art meta-model-based optimizers.

Feature-based algorithm selection aims to automatically find the best one from a portfolio of optimization algorithms on an unseen problem based on its landscape features. Feature-based algorithm selection has recently received attention in the research field of black-box numerical optimization. However, there is still room for the analysis of algorithm selection for black-box optimization. Most previous studies have focused only on whether an algorithm selection system can outperform the single-best solver (SBS) in a portfolio. In addition, a benchmarking methodology for algorithm selection systems has not been well investigated in the literature. In this context, this article analyzes algorithm selection systems on the 24 noiseless black-box optimization benchmarking functions. First, we demonstrate that the first successful performance measure is more reliable than the expected runtime measure for benchmarking algorithm selection systems. Then, we examine the influence of randomness on the performance of algorithm selection systems. We also show that the performance of algorithm selection systems can be significantly improved by using sequential least squares programming as a presolver. We point out that the difficulty of outperforming the SBS depends on algorithm portfolios, cross-validation methods, and dimensions. Finally, we demonstrate that the effectiveness of algorithm portfolios depends on various factors. These findings provide fundamental insights for algorithm selection for black-box optimization.

Although exploratory landscape analysis (ELA) has shown its effectiveness in various applications, most previous studies focused only on low- and moderate-dimensional problems. Thus, little is known about the scalability of the ELA approach for large-scale optimization. In this context, first, this paper analyzes the computational cost of features in the flacco package. Our results reveal that two important feature classes (ela_level and ela_meta) cannot be applied to large-scale optimization due to their high computational cost. To improve the scalability of the ELA approach, this paper proposes a dimensionality reduction framework that computes features in a reduced lower-dimensional space than the original solution space. We demonstrate that the proposed framework can drastically reduce the computation time of ela_level and ela_meta for large dimensions. In addition, the proposed framework can make the cell-mapping feature classes scalable for large-scale optimization. Our results also show that features computed by the proposed framework are beneficial for predicting the high-level properties of the 24 large-scale BBOB functions.

Since the scale factor and the crossover rate significantly influence the performance of differential evolution (DE), parameter adaptation methods (PAMs) for the two parameters have been well studied in the DE community. Although PAMs can sufficiently improve the effectiveness of DE, PAMs are poorly understood (e.g., the working principle of PAMs). One of the difficulties in understanding PAMs comes from the unclarity of the parameter space that consists of the scale factor and the crossover rate. This paper addresses this issue by analyzing adaptive parameter landscapes in PAMs for DE. First, we propose a concept of an adaptive parameter landscape, which captures a moment in a parameter adaptation process. For each iteration, each individual in the population has its adaptive parameter landscape. Second, we propose a method of analyzing adaptive parameter landscapes using a 1-step-lookahead greedy improvement metric. Third, we examine adaptive parameter landscapes in three PAMs by using the proposed method. Results provide insightful information about PAMs in DE.

Many differential evolution (DE) algorithms with various parameter control methods (PCMs) have been proposed. However, previous studies usually considered PCMs to be an integral component of a complex DE algorithm. Thus, the characteristics and performance of each method are poorly understood. We present an in-depth review of 24 PCMs for the scale factor and crossover rate in DE and a large-scale benchmarking study. We carefully extract the 24 PCMs from their original, complex algorithms and describe them according to a systematic manner. Our review facilitates the understanding of similarities and differences between existing, representative PCMs. The performance of DEs with the 24 PCMs and 16 variation operators is investigated on 24 black-box benchmark functions. Our benchmarking results reveal which methods exhibit high performance when embedded in a standardized framework under 16 different conditions, independent from their original, complex algorithms. We also investigate how much room there is for further improvement of PCMs by comparing the 24 methods with an oracle-based model, which can be considered to be a conservative lower bound on the performance of an optimal method.

Multimodal multiobjective optimization aims to find all Pareto optimal solutions, including overlapping solutions in the objective space. Multimodal multiobjective optimization has been investigated in the evolutionary computation community since 2005. However, it is difficult to survey existing studies in this field because they have been independently conducted and do not explicitly use the term “multimodal multiobjective optimization.” To address this issue, this letter reviews the existing studies of evolutionary multimodal multiobjective optimization, including studies published under names that are different from multimodal multiobjective optimization. Our review also clarifies open issues in this research area.

Multimodal multiobjective optimization is to locate (almost) equivalent Pareto optimal solutions as many as possible. While decomposition-based evolutionary algorithms have good performance for multiobjective optimization, they are likely to perform poorly for multimodal multiobjective optimization due to the lack of mechanisms to maintain the solution space diversity. To address this issue, this article proposes a framework to improve the performance of decomposition-based evolutionary algorithms for multimodal multiobjective optimization. Our framework is based on three operations: 1) assignment; 2) deletion; and 3) addition operations. One or more individuals can be assigned to the same subproblem to handle multiple equivalent solutions. In each iteration, a child is assigned to a subproblem based on its objective vector, i.e., its location in the objective space. The child is compared with its neighbors in the solution space assigned to the same subproblem. The performance of improved versions of six decomposition-based evolutionary algorithms by our framework is evaluated on various test problems regarding the number of objectives, decision variables, and equivalent Pareto optimal solution sets. Results show that the improved versions perform clearly better than their original algorithms.

Although quality indicators play a crucial role in benchmarking evolutionary multiobjective optimization algorithms, their properties are still unclear. One promising approach for understanding quality indicators is the use of the optimal distribution of objective vectors that optimizes each quality indicator. However, it is difficult to obtain the optimal distribution for each quality indicator, especially, when its theoretical property is unknown. Thus, optimal distributions for most quality indicators have not been well investigated. To address these issues, first, we propose a problem formulation of finding the optimal distribution for each quality indicator on an arbitrary Pareto front. Then, we approximate the optimal distributions for nine quality indicators using the proposed problem formulation. We analyze the nine quality indicators using their approximated optimal distributions on eight types of Pareto fronts of three-objective problems. Our analysis demonstrates that uniformly distributed objective vectors over the entire Pareto front are not optimal in many cases. Each quality indicator has its own optimal distribution for each Pareto front. We also examine the consistency among the nine quality indicators.

Since around 2000, it has been considered that elitist evolutionary multi-objective optimization algorithms (EMOAs) always outperform non-elitist EMOAs. This paper revisits the performance of non-elitist EMOAs for bi-objective continuous optimization when using an unbounded external archive. This paper examines the performance of EMOAs with two elitist and one non-elitist environmental selections. The performance of EMOAs is evaluated on the bi-objective BBOB problem suite provided by the COCO platform. In contrast to conventional wisdom, results show that non-elitist EMOAs with particular crossover methods perform significantly well on the bi-objective BBOB problems with many decision variables when using the unbounded external archive. This paper also analyzes the properties of the non-elitist selection.

We investigate the properties of widely used constrained multi-objective optimization benchmark problems. A number of Multi-Objective Evolutionary Algorithms (MOEAs) for Constrained Multi-Objective Optimization Problems (CMOPs) have been proposed in the past few years. The C-DTLZ functions and Real-World-Like Problems (RWLPs) have frequently been used for evaluating the performance of MOEAs on CMOPs. In this paper, however, we show that the C-DTLZ functions and widely-used RWLPs have some unnatural problem features. The experimental results show that an MOEA without any Constraint Handling Techniques (CHTs) can successfully find well-approximated nondominated feasible solutions on the C1-DTLZ1, C1-DTLZ3, and C2-DTLZ2 functions. It is widely believed that RWLPs are MOEA-hard problems, and finding the feasible solutions on them is a very hard task. However, we show that the MOEA without any CHTs can find feasible solutions on widely-used RWLPs such as the speed reducer design problem, the two-bar truss design problem, and the water problem. Also, it is seldom that the infeasible solution simultaneously violates multiple constraints in the RWLPs. Due to the above reasons, we conclude that constrained multi-objective optimization benchmark problems need a careful reconsideration.

While a large number of adaptive Differential Evolution (DE) algorithms have been proposed, their Parameter Adaptation Methods (PAMs) are not well understood. We propose a Target function-based PAM simulation (TPAM) framework for evaluating the tracking performance of PAMs. The proposed TPAM simulation framework measures the ability of PAMs to track predefined target parameters, thus enabling quantitative analysis of the adaptive behavior of PAMs. We evaluate the tracking performance of PAMs of widely used five adaptive DEs (jDE, EPSDE, JADE, MDE, and SHADE) on the proposed TPAM, and show that TPAM can provide important insights on PAMs, e.g., why the PAM of SHADE performs better than that of JADE, and under what conditions the PAM of EPSDE fails at parameter adaptation.

While a large number of multi-objective evolutionary algorithms (MOEAs) for many-objective optimization problems (MaOPs) have been proposed in the past few years, an exhaustive benchmarking study has never been performed. Moreover, most previous studies evaluated the performance of MOEAs based on nondominated solutions in the final population at the end of the search. In this paper, we exhaustively investigate the convergence performance of 21 MOEAs using an unbounded external archive that stores all nondominated solutions found during the search process. Surprisingly, the experimental results for the WFG functions with up to six objectives indicate that several recently proposed MOEAs perform significantly worse than classical MOEAs. Moreover, the performance rank among the 21 MOEAs significantly depends on the number of function evaluations. Thus, the previously reported performance of MOEAs on MaOPs as well as the widely used bench-marking methodology must be carefully reconsidered.

In the petroleum industry, accurate oil reservoir models are crucial in the decision making process. One critical step in reservoir modeling is History Matching (HM), where the parameters of a reservoir model are adjusted in order to improve its accuracy and enhance future prediction. Recent works applied evolutionary algorithms (EAs) such as GA, DE and PSO for the HM problem, but they have been limited to classical versions of these algorithms. A significant obstacle to applying EAs to HM is that each call to the fitness function requires an expensive simulation, making it difficult to tune the control parameters for EAs in order to obtain the best performance. We apply and evaluate state-of-the-art, adaptive differential algorithms (SHADE and jDE), as well as non-adaptive evolutionary algorithms (standard DE, PSO) that have been tuned using standard black-box benchmark functions as training instances. Both of these approaches result in significant improvements compared to standard methods in the HM literature. We also apply fitness distance correlation analysis to the search space explored by our algorithms in order to better understand the landscape of the HM problem.

This paper presents a parameter tuning study of Differential Evolution (DE) algorithms, including both standard DE as well as variants of the state-of-the-art adaptive DE, SHADE for both cheap and expensive optimization scenarios. Using the algorithm configuration tool SMAC, the DE variants are tuned independently for three different scenarios: expensive (102× D evaluations), medium (104× D evaluations), cheap (105× D evaluations), where D is the benchmark problem dimensionality. Each of these tuned parameter settings is then tested under both cheap and expensive scenarios, which enables us to analyze the effect of both the tuning and test scenario on the performance of the tuned algorithm. We evaluate restarting variants of DE (R-DE), as well as restarting variants of SHADE (R-SHADE) and L-SHADE (RL-SHADE). For the parameter tuning phase, we use the CEC2014 benchmarks as training problems, and for the testing phase, we use all 24 problems from the BBOB benchmark set. We also compare these DE variants with state-of-the-art restart CMA-ES variants (HCMA, BIPOPCMA-ES, and IPOP-CMA-ES). For both cheap and expensive scenarios, DE algorithms perform very well for low-dimensional problems. In particular, for the expensive scenario, the simple, restarting DE (R-DE) performs quite well, and on the cheap scenario, RL-SHADE performs well.

SHADE is an adaptive DE which incorporates success-history based parameter adaptation and one of the state-of-the-art DE algorithms. This paper proposes L-SHADE, which further extends SHADE with Linear Population Size Reduction (LPSR), which continually decreases the population size according to a linear function. We evaluated the performance of L-SHADE on CEC2014 benchmarks and compared its search performance with state-of-the-art DE algorithms, as well as the state-of-the-art restart CMA-ES variants. The experimental results show that L-SHADE is quite competitive with state-of-the-art evolutionary algorithms.

Most state-of-the-art Differential Evolution (DE) algorithms are adaptive DEs with online parameter adaptation. We investigate the behavior of adaptive DE on a class of hybrid functions, where independent groups of variables are associated with different component objective functions. An experimental evaluation of 3 state-of-the-art adaptive DEs (JADE, SHADE, jDE) shows that hybrid functions are "adaptive-DE-hard". That is, adaptive DEs have significant failure rates on these new functions. In-depth analysis of the adaptive behavior of the DEs reveals that their parameter adaptation mechanisms behave in a pathological manner on this class of problems, resulting in over-adaptation for one of the components of the hybrids and poor overall performance. Thus, this class of deceptive benchmarks pose a significant challenge for DE.

Differential Evolution is a simple, but effective approach for numerical optimization. Since the search efficiency of DE depends significantly on its control parameter settings, there has been much recent work on developing self-adaptive mechanisms for DE. We propose a new, parameter adaptation technique for DE which uses a historical memory of successful control parameter settings to guide the selection of future control parameter values. The proposed method is evaluated by comparison on 28 problems from the CEC2013 benchmark set, as well as CEC2005 benchmarks and the set of 13 classical benchmark problems. The experimental results show that a DE using our success-history based parameter adaptation method is competitive with the state-of-the-art DE algorithms.

This paper presents a large-scale, empirical evaluation of a Random, Heterogeneous Island-Model (RHIM) for evolutionary algorithms (EAs), where the control parameter values are independently, randomly assigned for each island that has recently been proposed by Gong and Fukunaga as a method for configuring island-model evolutionary algorithms in situations where it is not possible to expend the resources to carefully tune control parameters for a particular application. We apply RHIM to standard DE, JADE (an adaptive DE), and real-coded genetic algorithms. Evaluations are performed on standard black-box function optimization benchmarks, as well as combinatorial optimization problems (the TSP and QAP). The search efficiency of RHIM is compared to manual tuning of parameter settings for each benchmark problem. Our results with up to 256 islands, show that the search efficiency of RHIM, a method which does not involve any parameter tuning, tends to becomes increasingly competitive with manual parameter tuning as the number of islands increases. The consistent, relatively good performance of RHIM when applied to a variety of EAs on numerous, different benchmark problems suggest that it can be an effective, default method for configuring island-model EAs.

This paper evaluates the performance of Success-History based Adaptive DE (SHADE) on the benchmark set for the CEC2013 Competition on Real-Parameter Single Objective Optimization. SHADE is an adaptive differential algorithm which uses a history-based parameter adaptation scheme. Experimental results on 28 problems from the CEC2013 benchmarks for 10, 30, and 50 dimensions are presented, including measurements of algorithmic complexity. In addition, we investigate the parameter adaptation behavior of SHADE on these instances.