This study explores the characteristics of the extensive non-dominated archive generated by evolutionary multi-objective optimization (EMO) algorithms. Our findings reveal that such archives typically contain not only high-quality solutions positioned near the Pareto front, but also less desirable ones that deviate significantly from it. We further evaluate the effectiveness of various subset selection strategies in isolating the high-quality solutions within the archive. The insights gained from this work aim to assist EMO practitioners in gaining a deeper understanding of archive composition and in selecting appropriate subset selection methods to support decision-making.

In the evolutionary multi-objective optimization (EMO) community, performance indicators are increasingly important. This is because the indicators can be used for evaluating and designing EMO algorithms. Among them, the hypervolume indicator is particularly popular because it is Pareto compliant. Recently, researchers have shown that the exact R2 indicator is also Pareto compliant. Some researchers have already investigated the optimal distribution of solutions for the hypervolume indicator. However, only a few studies have examined the optimal distribution of the approximate R2 indicator in the two-dimensional case. In this paper, we show the optimal distributions of solutions for the exact R2 indicator and some variants of the approximate R2 indicator in the three-dimensional case. The visualized optimal distributions are compared with each other and also with the best solution set for MOEA/D. Our analysis and results show that the optimal distribution of the exact R2 indicator is similar to that of the hypervolume indicator. The optimal distributions of the approximate R2 indicator's variants are similar to the best solution set for MOEA/D.

Hypervolume subset selection (HSS) has received significant attention since it has a strong connection with evolutionary multiobjective optimization (EMO), such as environment selection and post-processing to identify representative solutions for decision-makers. The goal of HSS is to find the optimal subset that maximizes the hypervolume (HV) indicator subject to a given cardinality constraint. However, existing HSS algorithms or related methods are not efficient in achieving good performance in high-dimensional objective spaces. This is primarily because HSS problems become NP-hard when the number of objectives exceeds two, and the calculation of HV contribution (HVC) is very time-consuming. To efficiently solve HSS problems while maintaining a good solution quality, we propose a fast and scalable HSS method for many-objective optimization based on the determinantal point process (DPP), named DPP-HSS, which is fully free of HVC calculation. Specifically, DPP-HSS constructs an HV kernel matrix by extracting the convergence and diversity representations of each solution for a given HSS problem. This matrix is then used to build a DPP model. Subsequently, the original HSS problem is reformulated as a new maximization optimization problem based on the constructed model. A greedy DPP-based HSS algorithm is implemented to solve this transformed problem. Extensive experiments show that the proposed DPP-HSS achieves significant speedup and good HV performance in comparison with state-of-the-art HSS algorithms on benchmark problems. Furthermore, DPP-HSS demonstrates very good scalability with respect to the number of objectives.

The use of an unbounded archive (UA) has attracted much attention in the filed of evolutionary multiobjective optimization (EMO) since a solution set selected from the UA is often better than the final population. The size of the UA is very large (e.g., 1 000 000) since it is unbounded and it stores all the examined nondominated solutions during the execution of an EMO algorithm. Thus, an algorithm which can efficiently select a high-quality subset from a large-scale candidate set (e.g., UA) is needed. In this article, we propose a gradient-guided local search hypervolume subset selection (GL-HSS) algorithm to efficiently select a high-quality subset from a large-scale candidate set. In each iteration of GL-HSS, the gradient of the hypervolume (HV) contribution of each selected solution is used to guide the local search. As a result, the proposed algorithm can quickly improve the HV of the selected subset. Experimental results show that, compared to the existing subset selection algorithms, the proposed GL-HSS algorithm can efficiently select high-quality subsets from various large-scale candidate sets.

Subset selection, a fundamental problem in various domains, is to choose a subset of elements from a large candidate set under a given objective or multiple objectives. Pareto optimization for subset selection (POSS) has emerged as a powerful paradigm for addressing subset selection problems. Recently, some POSS variants have been proposed to further improve its performance. In this article, we propose a new POSS variant, named targeted POSS (TPOSS). TPOSS differs from POSS in four aspects: 1) problem formulation; 2) population initialization; 3) mutation; and 4) environmental selection. The main idea of TPOSS is to focus the search on the target region of subset selection with respect to the subset cardinality in order to improve the search efficiency. We conduct comprehensive experiments to compare TPOSS with six state-of-the-art algorithms on three subset selection tasks (i.e., sparse regression, unsupervised feature selection, and hypervolume subset selection) where the size of the candidate sets ranges from 20 to 400. Experimental results show that with respect to the objective value of the best feasible subset, TPOSS outperforms the other algorithms on all the three tasks, which suggests the potential of TPOSS to enhance subset selection in various domains.

Recently, several real-world multi-objective optimization problem suites have been proposed to facilitate the evaluation of the performance of evolutionary multi-objective optimization (EMO) algorithms. In spite of the importance of using real-world problems to evaluate EMO algorithms, their characteristics are not well understood compared to artificial test problems. Thus, there is a need to examine and understand the challenges posed by these real-world problems. In this study, we attempt to explore the characteristics of the most recently proposed real-world application suite (i.e., RWA suite). Six EMO algorithms are evaluated on the RWA suite, including three classic algorithms and three recently-proposed algorithms. Based on the performance comparison results, we systematically analyze the RWA suite in terms of convergence and diversity difficulties.

For evolutionary multi-objective optimization algorithms (EMOAs), an external archive can be utilized for saving good solutions found throughout the evolutionary process. Recent studies showed that a solution set selected from an external archive is usually superior to the final population. That is, the incorporation of an external archive improves the performance of EMOAs. However, the computation time for maintaining an external archive is long, especially when the archive size is large. To solve this issue, a simple archiving strategy is to save all solutions generated in the last several generations. In this paper, we examine this archiving strategy for three representative EMOAs on artificial test problems (Minus-DTLZ and WFG) and real-world problems (RE). Our results show that archiving the last several generations clearly improves the performance of EMOAs without severely increasing the computation time.

Real-world multi-objective optimization problems usually have multiple constraints. To solve constrained multi-objective optimization problems (CMOPs), researchers have proposed various evolutionary multi-objective optimization (EMO) algorithms with constraint handling techniques. Those EMO algorithms explicitly or implicitly assume the existence of a large infeasible region in the objective space between initial solutions and the Pareto front. As a result, they use some special mechanisms to traverse such an infeasible region (e.g., push-and-pull search). However, it is not clear whether real-world CMOPs have similar characteristics. It is also unclear whether state-of-the-art EMO algorithms that proposed for artificial CMOPs work well on real-world CMOPs. In this paper, we examine the characteristics of some real-world CMOPs. We find that the examined real-world CMOPs have no large infeasible region near the Pareto front. We also compare the performance of some constrained EMO algorithms on artificial CMOPs and real-world CMOPs. Our experimental results show that performance comparison results on real-world CMOPs are clearly different from those on artificial CMOPs. It is also shown that some recently-proposed constrained EMO algorithms are outperformed by NSGA-II with the basic constraint domination principle when they are compared on real-world CMOPs.

Subset selection is always a hot topic in the community of evolutionary multi-objective optimization (EMO) since it is used in mating selection, environmental selection, and final selection. In the first two scenarios, the task of subset selection algorithms is to select a subset from a small candidate set (e.g., population). However, in the last scenario, it is to select a subset from an unbounded archive with all non-dominated solutions examined during the evolutionary process. Most existing subset selection algorithms aim to improve the hypervolume of subsets (i.e., hypervolume subset selection) selected from the archive. However, only a few researchers work on the IGD and IGD+ (two well-known indicators) subset selection in the last scenario. In this paper, we propose a gradient-guided local search algorithm for IGD/IGD+ subset selection problems. The experimental results show that the proposed algorithm is much faster than the existing lazy greedy inclusion IGD/IGD+ subset selection algorithm, and the quality of the selected subsets is competitive with that selected by the existing greedy algorithms.

This paper proposes a framework called GHVC-Net that uses the graph neural network (GNN) model to approximate each solution's hypervolume contribution (HVC). GHVC-Net is permutation invariant and can handle solution sets of arbitrary size, similar to the properties of GNN. Compared to HVC-Net (i.e., a machine learning model for HVC approximation), GHVC-Net achieves better accuracy with less training time. GHVC-Net is also compared with traditional approximation methods, such as line-based and point-based methods, to demonstrate its ability to identify the solution with the smallest (largest) HVC.

An important issue in hypervolume-based evolutionary multi-objective optimization (EMO) algorithms is the specification of a reference point for hypervolume calculation. However, its appropriate specification has not been carefully studied in the literature. Some recent studies have pointed out the importance and difficulty of the reference point specification. Its appropriate specification depends on problem characteristics such as the Pareto front shape and the number of objectives. In this paper, the difficulty of the reference point specification in hypervolume-based EMO algorithms is circumvented by using two reference points. Instead of using only a single reference point, we propose a new hypervolume-based EMO algorithm that can effectively utilize two reference points cooperatively. Experimental results show that the proposed algorithm has good and robust performance on a wide range of test problems. In comparison to hypervolume-based EMO algorithms with only a single reference point, the proposed algorithm can find a wider and more uniformly distributed solution set. On a recently proposed real-world problem suite, the proposed algorithm shows competitive performance in comparison to state-of-the-art algorithms.

Hypervolume contribution is an important concept in evolutionary multiobjective optimization (EMO). It involves hypervolume-based EMO algorithms and hypervolume subset selection algorithms. Its main drawback is that it is computationally expensive in high-dimensional spaces, which limits its applicability to many-objective optimization. Recently, an R2 indicator variant (i.e.,$R_{2}^{\text {HVC}}$indicator) is proposed to approximate the hypervolume contribution. The$R_{2}^{\text {HVC}}$indicator uses line segments along a number of direction vectors for hypervolume contribution approximation. It has been shown that different direction vector sets lead to different approximation qualities. In this article, we propose learning to approximate (LtA), a direction vector set generation method for the$R_{2}^{\text {HVC}}$indicator. The direction vector set is automatically learned from training data. The learned direction vector set can then be used in the$R_{2}^{\text {HVC}}$indicator to improve its approximation quality. The usefulness of the proposed LtA method is examined by comparing it with other commonly used direction vector set generation methods for the$R_{2}^{\text {HVC}}$indicator. Experimental results suggest the superiority of LtA over the other methods for generating high-quality direction vector sets.

Autonomous navigation of Unmanned Aerial Vehicles (UAVs) in large-scale complex environments presents a significant challenge in modern aerospace engineering, as it requires effective decision-making in an environment with limited sensing capacity, dynamic changes, and dense obstacles. Reinforcement Learning (RL) has been applied in sequential control problems, but the manual setting of hyperparameters, including reward functions, often results in suboptimal solutions and inadequate training. To address these limitations, we propose a framework that combines Multi-Objective Evolutionary Algorithms (MOEAs) with RL algorithms. The proposed framework generates a set of non-dominating parameters for the reward function using MOEAs, leading to diverse decision-making preferences, efficient convergence, and improved performance. The framework was tested on the autonomous navigation of UAVs and demonstrated significant improvement compared to traditional RL methods. This work offers a novel perspective on the problem of autonomous UAV navigation in large-scale complex environments and highlights the potential for further improvement through the integration of RL and MOEAs.

In the field of evolutionary multi-objective optimization, it is well known that dominance-based algorithms do not work well on many-objective problems. This is because almost all solutions in a population become non-dominated in early generations. Two approaches have been proposed to decrease the number of non-dominated solutions. One is to increase the dominated region by each solution: dominance modification. The other is to increase the correlation among objectives: objective modification. In this paper, first we show that these two approaches can be viewed as the same approach. We also explain that some regions of the Pareto front are dominated when the dominated region is increased. Next, we numerically examine the effects of dominance modification on the performance of NSGA-II on many-objective test problems. Through computational experiments, we demonstrate that its positive and negative effects are clearly shown by the hypervolume (HV) and inverted generational distance (IGD) indicators, respectively. Then, we discuss why these two indicators emphasize different effects of dominance modification using the optimal distribution of solutions for each indicator. Finally, we explain that objective space normalization is needed in dominance modification whereas it has no effects on the Pareto dominance relation.

In evolutionary multi-objective optimization (EMO), one important procedure is to remove all dominated solutions from a solution set (e.g., solutions in an archive) to obtain an approximated Pareto front, which is called a static nondominance problem. Recently, an unbounded external archive (UEA) is used in EMO algorithms in many studies to store all solutions examined during the evolutionary process. In these studies, the candidate set in the static nondominance problem includes all the examined solutions. Although many methods have been proposed to solve the static nondominance problem, the dominated solution removal is still time-consuming for a large-scale candidate set. To tackle this issue, we propose a simple and general two-phase procedure to improve the efficiency of existing dominated solution removal methods. In the first phase of our procedure, a large-scale candidate set is divided into several subsets. Dominated solutions are removed from each subset independently, and remaining solutions are merged. In the second phase, dominated solutions are removed from the merged set. Compared with directly removing all dominated solutions from the candidate set, our experimental results show that the proposed two-phase procedure can drastically decrease the computation time when the percentage of nondominated solutions in the candidate set is small.

In this paper, we propose STHV-Net to approximate the hyper-volume indicator based on Set Transformer. Set Transformer is an advanced model to process set-form data which concentrates on the interaction of set elements. STHV-Net receives a non-dominated positive solution set of any size and outputs an approximate hyper-volume value of this solution set. The output value is independent of the order of the elements in the input set. The performance of STHV-Net is compared with three existing approximation methods (Monte Carlo, R2 indicator, HV-Net) using two evaluation criteria: approximation errors and computing time. Our experimental results show that STHV-Net is superior to the Monte Carlo method and the R2 indicator method with respect to these two criteria. Compared with HV-Net, our method can obtain lower approximation errors at the cost of a slightly longer computing time. We provide six representative models with different parameter sizes for users who have different preferences about the tradeoff between approximation error and computing time.

The multiobjective evolutionary algorithm based on decomposition (MOEA/D) with the penalty-based boundary intersection (PBI) function (denoted as MOEA/D-PBI) has been frequently used in many studies in the literature. One essential issue in MOEA/D-PBI is its penalty parameter value specification. However, it is not easy to specify the penalty parameter value appropriately. This is because MOEA/D-PBI shows different search behavior when the penalty parameter values are different. The PBI function with a small penalty parameter value is good for convergence. However, the PBI function with a large value of penalty parameter is needed to preserve the diversity and uniformity of solutions. Although some methods for adapting the penalty parameter value for each weight vector have been proposed, they usually lead to slow convergence. In this article, we propose the idea of using two different values of penalty parameter simultaneously in MOEA/D-PBI. Although the idea is simple, the proposed algorithm is able to utilize both the convergence ability of a small penalty parameter value and the diversification ability of a large penalty parameter value of the PBI function. Experimental results demonstrate that the proposed algorithm works well on a wide range of test problems.

Real-world multiobjective optimization problems (MOPs) usually have conflicting and differently-scaled objectives. To deal with such problems, objective space normalization is widely used in multiobjective evolutionary algorithm (MOEA) design, especially, in the design of decomposition-based MOEAs. It has been demonstrated that uniformly-distributed solutions can be obtained for badly-scaled MOPs by decomposition-based MOEAs with objective space normalization. Recently, weight vector scaling has also been used for badly-scaled MOPs. In some studies, it was argued that weight vector scaling and objective space normalization are essentially the same when applied to decomposition-based MOEAs. In this paper, we theoretically and empirically show the relation between objective space normalization and weight vector scaling. Our results demonstrate that similarities and differences between the two methods depend on the choice of a scalarizing function. How the choice between normalization and weight vector scaling affects decomposition-based MOEAs with solution assignment mechanisms is also analyzed.

Hypervolume subset selection (HSS) has received considerable attention in the field of evolutionary multiobjective optimization (EMO). It aims to select a representative subset from a candidate solution set so that the hypervolume (HV) of the selected subset is maximized. A number of HSS methods have been proposed in the literature, attempting to either reduce the computation time of subset selection or improve the subset quality (i.e., the HV of the selected subset). However, when selecting from a large candidate set (e.g., from hundreds of thousands of candidate solutions), most HSS methods fail to strike a balance between the computation time and the subset quality. In this article, we propose a new local search HSS method and its extended version. Three strategies are proposed. The first two strategies are applied to the proposed method to obtain a good subset within a small computation time, and the third one is applied to the extended version to further improve the obtained subset. The experimental results on various candidate sets demonstrate that the proposed method and its extended version are much more efficient and effective than the existing HSS methods.

In this letter, we propose HV-Net, a new method for hypervolume approximation in evolutionary multiobjective optimization. The basic idea of HV-Net is to use DeepSets, a deep neural network with permutation invariant property, to approximate the hypervolume of a nondominated solution set. The input of HV-Net is a nondominated solution set in the objective space, and the output is an approximated hypervolume value of this solution set. The performance of HV-Net is evaluated through computational experiments by comparing it with two commonly used hypervolume approximation methods (i.e., point-based method and line-based method). Our experimental results show that HV-Net outperforms the other two methods in terms of both the approximation error and the runtime, which shows the potential of using deep learning techniques for hypervolume approximation.

An unbounded external archive has been used to store all nondominated solutions found by an evolutionary multiobjective optimization algorithm in some studies. It has been shown that a selected solution subset from the stored solutions is often better than the final population. However, the use of the unbounded archive is not always realistic. When the number of examined solutions is huge, we must prespecify the archive size. In this study, we examine the effects of the archive size on three aspects: 1) the quality of the selected final solution set; 2) the total computation time for the archive maintenance and the final solution set selection; and 3) the required memory size. Unsurprisingly, the increase of the archive size improves the final solution set quality. Interestingly, the total computation time of a medium-size archive is much larger than that of a small-size archive and a huge-size archive (e.g., an unbounded archive). To decrease the computation time, we examine two ideas: 1) periodical archive update and 2) archiving only in later generations. Compared with updating the archive at every generation, the first idea can obtain almost the same final solution set quality using a much shorter computation time at the cost of a slight increase of the memory size. The second idea drastically decreases the computation time at the cost of a slight deterioration of the final solution set quality. Based on our experimental results, some suggestions are given about how to appropriately choose an archiving strategy and an archive size.

Subset selection plays an important role in the field of evolutionary multiobjective optimization (EMO). Especially, in an EMO algorithm with an unbounded external archive (UEA), subset selection is an essential post-processing procedure to select a prespecified number of solutions as the final result. In this article, we discuss the efficiency of greedy subset selection for the hypervolume, inverted generational distance (IGD), and IGD plus (IGD+) indicators. Greedy algorithms usually efficiently handle the subset selection. However, when a large number of solutions are given (e.g., subset selection from tens of thousands of solutions in a UEA), they often become time consuming. Our idea is to use the submodular property, which is known for the hypervolume indicator, to improve their efficiency. First, we prove that the IGD and IGD+ indicators are also submodular. Next, based on the submodular property, we propose an efficient greedy inclusion algorithm for each indicator. We demonstrate through computational experiments that the proposed algorithms are much faster than the standard greedy subset selection algorithms. The proposed algorithms also help the research on performance indicators.

Recently, large-scale multiobjective optimization has received increasing attention from the evolutionary multiobjective optimization (EMO) community. This has led to the emergence of a specialized research area called evolutionary large-scale multiobjective optimization (ELMO). In general, it is believed that multiobjective optimization problems become more difficult as the number of decision variables increases. However, the following two counterintuitive observations are obtained from careful examinations of recent ELMO studies. One is that experimental results on some large-scale multiobjective test problems were improved by increasing the number of decision variables. The other is that better results were obtained for some other large-scale multiobjective test problems by conventional EMO algorithms (EMOAs) than state-of-the-art ELMO algorithms (ELMOAs). These observations suggest that ELMOAs have not always been evaluated on appropriate test problems. Moreover, their performance is not always better than the performance of conventional EMOAs. In this letter, we first re-examine the performance of ELMOAs and conventional EMOAs on a wide variety of scalable multiobjective test problems. Then, counterintuitive experimental results are analyzed using the anytime performance evaluation scheme and distributions of randomly generated initial solutions. Based on the analysis, suggestions on how to handle large-scale multiobjective test problems with counterintuitive results are proposed.

Hypervolume is widely used in the evolutionary multiobjective optimization (EMO) field to evaluate the quality of a solution set. For a solution set with$\mu $solutions on a Pareto front, a larger hypervolume means a better solution set. Investigating the distribution of the solution set with the largest hypervolume is an important topic in EMO, which is the so-called hypervolume-optimal$\mu $-distribution. Theoretical results have shown that the$\mu $solutions are uniformly distributed on a linear Pareto front in two dimensions. However, the$\mu $solutions are not always uniformly distributed on a single-line Pareto front in three dimensions. They are only uniform when the single-line Pareto front has one constant objective. In this article, we further investigate the hypervolume-optimal$\mu $-distribution in three dimensions. We consider the line-based and plane-based Pareto fronts. For the line-based Pareto fronts, we extend the single-line Pareto front to two-line and three-line Pareto fronts, where each line has one constant objective. For the plane-based Pareto fronts, the linear triangular and inverted triangular Pareto fronts are considered. First, we show that the$\mu $solutions are not always uniformly distributed on the line-based Pareto fronts. The uniformity depends on how the lines are combined. Then, we show that a uniform solution set on the plane-based Pareto front is not always optimal for hypervolume maximization. It is locally optimal with respect to a$(\mu +1)$selection scheme. Our results can help researchers in the community to better understand and utilize the hypervolume indicator.

In the evolutionary multi-objective optimization (EMO) community, an unbounded external archive has been used in some studies for evaluating the performance of EMO algorithms. Those studies show that the unbounded external archive often includes better solutions than the final population. Thus, it is likely that the search ability of an EMO algorithm can be improved by periodically updating the current population using the unbounded external archive (i.e., by periodically choosing good solutions from all the examined solutions as the current population). However, the usefulness of such a global generation update scheme has not been studied in the literature. In this paper, we examine the effect of the periodical global generation update on the performance of well-known and frequently-used EMO algorithms: NSGA-II, MOEA/D and NSGA-III. We use the PBI function with uniformly distributed weight vectors for the periodical global generation update. In our computational experiments, we obtain clearly improved results by the periodical global generation update. We also examine the effect of the frequency of the global generation update (e.g., every 20 generations) on the performance of each EMO algorithm and its run time.

Hypervolume-based multi-objective evolutionary algorithms (HV-MOEAs) are one of the popular algorithm classes in the evolutionary multi-objective optimization (EMO) community. HV-MOEAs, which can directly optimize the HV of a solution set, are useful in various applications. However, the computation time of HV-MOEAs is very long for many-objective problems since the calculation of the hypervolume contribution (HVC) is computationally expensive. Therefore, a number of approximation methods for the HVC calculation were proposed to reduce its time cost. An R2-based hypervolume contribution approximation (R2-HVC) method was proposed for HVC approximation. However, for HV-MOEAs, the point is to find the worst solution, instead of accurately approximating the HVC of each solution. In this paper, a novel method (i.e., two-stage R2-HVC) is proposed for improving the ability of R2-HVC to correctly identify the worst solution (i.e., the solution with the smallest HVC value) in a solution set. In the proposed method, some candidate solutions are selected based on rough HVC approximation in the first stage, and they are carefully evaluated in the second stage. It is shown through computational experiments that the proposed method performs much better than the original R2-HVC method.

The multi-objective evolutionary algorithm based on decomposition (MOEA/D) is one of the most popular algorithms in the field of evolutionary multi-objective optimization (EMO). Even though MOEA/D has been widely used in many studies, it is likely that the performance of MOEA/D is not always optimized since the same MOEA/D implementation is often used on various problems with different characteristics. However, obtaining an appropriate implementation of MOEA/D for a different problem is not always easy, since there exists a wide variety of choices for the components and parameters in MOEA/D. In this paper, we examine the use of a genetic algorithm-based hyper-heuristic procedure to offline tune MOEA/D on a single test problem, a set of similar test problems, and a set of various test problems. A total of 26 benchmark test problems are used in our study. Experimental results show that the MOEA/D tuned for a set of various test problems does not always perform well. It is also shown that the MOEA/D tuned for a single test problem and for a set of similar test problems always has high performance. Our experimental results strongly suggest the necessity of using a tuning procedure to obtain a different MOEA/D implementation for a different type of problems.

Hypervolume subset selection (HSS) aims to select a subset from a candidate solution set so that the hypervolume of the selected subset is maximized. Due to its NP-hardness nature, the greedy algorithms are the most efficient for solving HSS in many-objective optimization. However, when the number of objectives is large, the calculation of the hypervolume contribution in the greedy HSS is time-consuming, which makes the greedy HSS inefficient. To solve this issue, in this paper we propose a greedy approximated HSS algorithm. The main idea is to use an R2-based hypervolume contribution approximation method in the greedy HSS. In the algorithm implementation, a utility tensor structure is introduced to facilitate the calculation of the hypervolume contribution approximation. In addition, the tensor information in the last step is utilized in the current step to accelerate the calculation. We also apply the lazy strategy in the proposed algorithm to further improve its efficiency. We test the greedy approximated HSS algorithm on 3-10 objective candidate solution sets. The experimental results show that the proposed algorithm is much faster than the state-of-the-art greedy HSS algorithm in many-objective optimization while their hypervolume performance is almost the same.

In this paper, we revisit the distance-based subset selection (DSS) algorithm in evolutionary multi-objective optimization. First, we show one drawback of the DSS algorithm, i.e., a uniformly distributed solution set cannot always be selected. Then, we show that this drawback can be overcome by maximizing the uniformity level of the selected solution set, which is defined by the minimum distance between two solutions in the solution set. Furthermore, we prove that the DSS algorithm is a greedy inclusion algorithm with respect to the maximization of the uniformity level. Based on this conclusion, we generalize DSS as a subset selection problem where the objective is to maximize the uniformity level of the subset. In addition to the greedy inclusion DSS algorithm, a greedy removal algorithm and an iterative algorithm are proposed for the generalized DSS problem. We also extend the Euclidean distance in the original DSS to other widely-used and user-defined distances. We conduct extensive experiments on solution sets over different types of Pareto fronts to compare the three DSS algorithms with different distances. Our results suggest the usefulness of the generalized DSS for selecting a uniform subset. The effect of using different distances on the selected subsets is also analyzed.

The quality of solutions in multiobjective evolutionary algorithms (MOEAs) is usually evaluated by objective functions. However, function evaluations (FEs) are usually time-consuming in real-world problems. A large number of FEs limit the application of MOEAs. In this paper, we propose a fuzzy classifier-based selection strategy to reduce the number of FEs of MOEAs. First, all evaluated solutions in previous generations are used to build a fuzzy classifier. Second, the built fuzzy classifier is used to predict each unevaluated solution's label and its membership degree. The reproduction procedure is repeated to generate enough offspring solutions (classified as positive by the classifier). Next, unevaluated solutions are sorted based on their membership degrees in descending order. The same number of solutions as the population size are selected from the top of the sorted unevaluated solutions. Then, the best half of the chosen solutions are selected and stored in the new population without evaluations. The other half solutions are evaluated. Finally, the evaluated solutions are used together with evaluated current solutions for environmental selection to form another half of the new population. The proposed strategy is integrated into two MOEAs. Our experimental results demonstrate the effectiveness of the proposed strategy on reducing FEs.

Subset selection is an important component in evolutionary multiobjective optimization (EMO) algorithms. Clustering, as a classic method to group similar data points together, has been used for subset selection in some fields. However, clustering-based methods have not been evaluated in the context of subset selection from solution sets obtained by EMO algorithms. In this paper, we first review some classic clustering algorithms. We also point out that another popular subset selection method, i.e., inverted generational distance (IGD)-based subset selection, can be viewed as clustering. Then, we perform a comprehensive experimental study to evaluate the performance of various clustering algorithms in different scenarios. Experimental results are analyzed in detail, and some suggestions about the use of clustering algorithms for subset selection are derived. Additionally, we demonstrate that decision maker’s preference can be introduced to clustering-based subset selection.

Hypervolume subset selection is a hot topic in the field of evolutionary multi-objective optimization (EMO) due to the increasing needs of selecting a small set of representative solutions from a large set of non-dominated solutions (e.g., unbounded external archive). To maximize the hypervolume (HV) of the selected subset, a number of HV subset selction (HSS) methods have been proposed. Greedy forward selection (GFS) subset selection method is the most popular one, which has been actively investigated in the literature. However, few studies focus on local search (LS) HSS method, which is similar to the mechanism of SMS-EMOA. The time cost of the LS method is usually high, and the quality of the subset selected by this method is always poor. To address these two issues, in this paper, we first adopt an HV contribution update strategy to the original LS method to significantly reduce its time cost. In addition, two efficient strategies are proposed to improve the performance of the LS method to get a better subset. Finally, experiments are conducted to show the effectiveness of the improved LS method.

The research on large-scale multi- and many-objective optimization has received increasing attention in the evolutionary multi-objective optimization (EMO) community. A number of large-scale EMO algorithms based on different strategies (e.g., divide-and-conquer, coevolution, and dimensionality reduction) have been proposed over the last decade. The performance of the large-scale EMO algorithms was empirically evaluated using several benchmark test suites, including the ZDT, DTLZ, WFG, MaF, UF and LSMOP test suites. Even though these test suites are theoretically scalable to any number of decision variables, they are not necessarily appropriate for examining the performance of large-scale EMO algorithms. In fact, among these benchmark test suites, only the LSMOP test suite is specifically designed to test the performance of large-scale EMO algorithms. In this paper, we propose a new scalable multi- and many-objective test problem for examining large-scale EMO algorithms. The proposed test problem has the following features: 1) the number of objectives and decision variables can be arbitrarily specified; 2) the interaction strength among the objectives can be adjusted by a correlation parameter. The performance of six EMO algorithms is examined on the new test problem. Our experimental results show that the proposed new test problem poses difficulties to some state-of-the-art large-scale EMO algorithms.

Hypervolume subset selection (HSS) aims to select a subset with a fixed size from a candidate solution set so that the hypervolume of the subset is maximized. The greedy HSS (GHSS) is the most efficient way for solving the HSS problem. When we use GHSS, we implicitly assume that well-distributed solutions over the entire Pareto front will be selected. However, the distribution of selected solutions by GHSS has not been studied. In this paper, we investigate this issue by examining selected solution subsets for different reference point specifications in GHSS. First, we show that a sufficiently large reference point is a good choice for GHSS to select a well-distributed subset on a triangular Pareto front. However, it is not easy to properly specify a reference point for an inverted triangular Pareto front. Then, we propose a dynamic reference point specification method for GHSS to select a well-distributed subset for various types of Pareto fronts. Static and dynamic reference point specifications are compared through computational experiments using 3- and 5-objective candidate solution sets from various types of Pareto front shapes. The experimental results demonstrate the effect of different reference point specifications on the subsets selected by GHSS and the usefulness of the dynamic reference point specification for GHSS.

Hypervolume is widely used as a performance indicator in the field of evolutionary multiobjective optimization (EMO). It is used not only for performance evaluation of EMO algorithms (EMOAs) but also in indicator-based EMOAs to guide the search. Since its initial proposal in the late 1990s, a wide variety of studies have been done on various topics, including hypervolume calculation, optimal μ-distribution, subset selection, hypervolume-based EMOAs, and extensions of the hypervolume indicator. However, currently there is no work to systematically survey the hypervolume indicator for these topics whereas it has been frequently used in the EMO field. This article aims to fill this gap and provide a comprehensive survey on the hypervolume indicator. We expect that this survey will help EMO researchers to understand the hypervolume indicator more deeply and thoroughly, and promote further utilization of the hypervolume indicator in the EMO field.

Evolutionary algorithms have been widely used to solve multi-objective optimization problems. Usually, the final population of an evolutionary algorithm is used as the output of multi-objective optimization. However, a current new trend is to select a pre-specified number of solutions from an unbounded external archive (UEA) as the final output of multi-objective optimization. Some subset selection methods have been proposed in the literature such as hypervolume-based and IGD-based selection. Recently, a distance-based subset selection (DSS) method was proposed for efficient subset selection from a large external archive. Whereas DSS efficiently finds a set of uniformly distributed solutions, it has some difficulties in the handling of solutions in the UEA as we demonstrate in this paper. To improve the performance of the DSS method, we propose a modified DSS method based on the IGD+distance instead of the Euclidean distance. Experimental results on various benchmark problems show that the modified DSS method performs better than or equal to the original DSS method on most test problems.

Subset selection is a popular topic in recent years and a number of subset selection methods have been proposed. Among those methods, hypervolume subset selection is widely used. Greedy hypervolume subset selection algorithms can achieve good approximations to the optimal subset. However, when the candidate set is large (e.g., an unbounded external archive with a large number of solutions), the algorithm is very time-consuming. In this paper, we propose a new lazy greedy algorithm exploiting the submodular property of the hypervolume indicator. The core idea is to avoid unnecessary hypervolume contribution calculation when finding the solution with the largest contribution. Experimental results show that the proposed algorithm is hundreds of times faster than the original greedy inclusion algorithm and several times faster than the fastest known greedy inclusion algorithm on many test problems.

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.

In general, performance comparison results of optimization algorithms depend on the parameter specifications in each algorithm. For fair comparison, it may be needed to use the best specifications for each algorithm instead of using the same specifications for all algorithms. This is because each algorithm has its best specifications. However, in the evolutionary multi-objective optimization (EMO) field, performance comparison has usually been performed under the same parameter specifications for all algorithms. Especially, the same population size has always been used. In this paper, we discuss this practice from a viewpoint of fair comparison of EMO algorithms. First, we demonstrate that performance comparison results depend on the population size. Next, we explain a new trend of performance comparison where each algorithm is evaluated by selecting a pre-specified number of solutions from the examined solutions (i.e., by selecting a solution subset with a pre-specified size). Then, we discuss the selected subset size specification. Through computational experiments, we show that performance comparison results do not strongly depend on the selected subset size while they depend on the population size.

In the evolutionary multi-objective optimization (EMO) community, hypervolume (HV) has been frequently used to evaluate the performance of EMO algorithms. The HV is a Pareto compliant indicator which can simultaneously evaluate both the convergence of solutions to the Pareto front and their diversity. No other Pareto compliant indicator is known. In the EMO community, it is implicitly assumed that a set of uniformly distributed solutions over the entire Pareto front including its boundary has the best HV value. This is true for a linear Pareto front of a two-objective problem when a reference point for HV calculation is not too close to the Pareto front. In this paper, we numerically examine this issue for three-objective problems. We perform computational experiments to search for the optimal distribution of a small number of solutions for HV maximization. This is to visually explain the characteristic features of the optimal distribution. Our experimental results clearly show that a set of uniformly distributed solutions is not always optimal for HV maximization. It is also shown that the optimal distribution for HV maximization is often inconsistent with our intuition. For example, a set of ten solutions systematically generated by Das and Dennis method is not optimal.

In machine learning field, feature selection can be treated as a bi-objective optimization problem. It is reported that a decomposition-based evolutionary multi-objective optimization algorithm (i.e., MOEA/D-STAT) has good diversity performance when coping with feature selection. However, feature selection is also a time-consuming problem considering a large dataset it involves. The computation time can be easily reduced by introducing the parallelization into MOEA/D-STAT, thanks to the decomposition idea of MOEA/D. To the best of our knowledge, this is the first attempt to implement the parallelization of MOEA/D-STAT for feature selection. In this paper, we consider both master-slave models and island models, which are two different approaches of parallelization. In the master-slave models, different offspring assignment mechanisms are considered. In the island models, different island size specification mechanisms are examined. Our experimental results show that the master-slave models can achieve higher speedup and better performance than the island models.

In the evolutionary multi-objective optimization (EMO) community, it is usually assumed that the final population is presented to the decision maker as the result of the execution of an EMO algorithm. Recently, an unbounded external archive was used to evaluate the performance of EMO algorithms in some studies where a pre-specified number of solutions are selected from all the examined non-dominated solutions. In this framework, which is referred to as the solution selection framework, the final population does not have to be a good solution set. Thus, the solution selection framework offers higher flexibility to the design of EMO algorithms than the final population framework. In this paper, we examine the design of multi-objective evolutionary algorithm based on decomposition (MOEA/D) under these two frameworks. First, we show that the performance of MOEA/D is improved by linearly changing the reference point specification during its execution through computational experiments with various combinations of initial and final specifications. Robust and high performance of the solution selection framework is observed. Then, we examine the use of a genetic algorithm-based offline hyper-heuristic method to find the best configuration of MOEA/D in each framework. Finally, we further discuss solution selection after the execution of an EMO algorithm in the solution selection framework.

In this article, a new hypervolume-based evolutionary multiobjective optimization algorithm (EMOA), namely, R2HCA-EMOA (R2-based hypervolume contribution approximation EMOA), is proposed for many-objective optimization. The core idea of the algorithm is to use an R2 indicator variant to approximate the hypervolume contribution. The basic framework of the proposed algorithm is the same as SMS-EMOA. In order to make the algorithm computationally efficient, a utility tensor structure is introduced for the calculation of the R2 indicator variant. Moreover, a normalization mechanism is incorporated into R2HCA-EMOA to enhance the performance of the algorithm. Through experimental studies, R2HCA-EMOA is compared with three hypervolume-based EMOAs and several other state-of-the-art EMOAs on 5-, 10-, and 15-objective DTLZ, WFG problems, and their minus versions. Our results show that R2HCA-EMOA is more efficient than the other hypervolume-based EMOAs, and is superior to all the compared state-of-the-art EMOAs.

In this letter, a new hypervolume contribution approximation method is proposed which is formulated as an R2 indicator. The basic idea of the proposed method is to use different line segments only in the hypervolume contribution region for the hypervolume contribution approximation. Comparing with a traditional method which is based on the R2 indicator to approximate the hypervolume, the new method can directly approximate the hypervolume contribution and will utilize all the direction vectors only in the hypervolume contribution region. The new method, the traditional method, and the Monte Carlo sampling method together with two exact methods are compared through comprehensive experiments. Our results show the advantages of the new method over the other methods. Comparing with the other two approximation methods, the new method achieves the best performance for comparing hypervolume contributions of different solutions and identifying the solution with the smallest hypervolume contribution. Comparing with the exact methods, the new method is computationally efficient in high-dimensional spaces where the exact methods are impractical to use.

Performance of evolutionary multi-objective and many-objective optimization algorithms is usually evaluated by computational experiments on a number of test problems. Thus, performance comparison results depend on the choice of test problems. For fair comparison, it is needed to use a wide variety of test problems with various characteristics. However, most of well-known and frequently-used scalable test problems have the same type of Pareto fronts called "regular" Pareto fronts: Their shape is triangular. In this paper, we discuss the reality of this type of Pareto fronts. First, we show that a triangular Pareto front has some unrealistic properties as the Pareto front of a real-world multi-objective problem. Next, we examine the shape of the Pareto fronts of some other multi-objective test problems with independently generated objectives (i.e., with objectives that are not derived from a pre-specified shape of Pareto fronts). It is shown that the Pareto fronts of those test problems are inverted triangular (i.e., not regular). Then, we demonstrate that the shape of Pareto fronts (i.e., triangular or inverted triangular) has large effects on the performance of decomposition-based and hypervolume-based algorithms. Finally, we show difficulties of hypervolume-based performance evaluation for many-objective problems with inverted triangular Pareto fronts.

Recently, multimodal multiobjective optimization has started to attract a lot of attention. Its task is to find multiple Pareto optimal solution sets in the decision space, which are equivalent in the objective space. In some applications, it is important to find multiple global and local Pareto optimal solution sets in the decision space, which have similar quality in the objective space. In evolutionary computation, a wide variety of test problems with various characteristics are needed for fair comparison of different algorithms. However, we have only a small number of test problems for multimodal multiobjective optimization. In this paper, we propose a scalable multimodal multiobjective test problem with respect to the five parameters: (i) the number of objectives, (ii) the number of decision variables, (iii) the number of equivalent Pareto optimal solution sets in the decision space, (iv) the number of local Pareto fronts, and (v) the number of local Pareto optimal solution sets in the decision space for each local Pareto front. Our proposal is the first scalable test problem with respect to all of these five parameters.

Many real-world optimization problems are challenging because the evaluation of solutions is computationally expensive. As a result, the number of function evaluations is limited. Surrogate-assisted evolutionary algorithms are promising approaches to tackle this kind of problems. However, their performance highly depends on the number of objectives. Thus, they may not be suitable for many-objective optimization. This paper proposes a novel hybrid algorithm for computationally expensive many-objective optimization, called C-M-EA. The proposed approach combines two surrogate-assisted evolutionary algorithms during the search process. We compare the performance of the proposed approach with seven multi-objective evolutionary algorithms. Our experimental results show that our approach is competitive for solving computationally expensive many-objective optimization problems.

In this paper, a new R2 indicator is proposed for better hypervolume approximation. First the fact that the original R2 indicator is not a good approximation for the hypervolume is illustrated by examples. Then the new R2 indicator is derived based on the Divergence theorem and Riemann sum approximation. The difference between the original R2 and the new R2 is only the added exponential in the new R2 where the exponential is the same as the dimensionality of the objective space (i.e., the number of objectives). The new R2, the original R2 and some other R2 variants are compared through comprehensive numerical studies on different solution sets under different scenarios. The results show the superiority of the proposed new R2 indicator over other R2 variants for the hypervolume approximation, where the new R2 indicator achieves the best linear relation with the true hypervolume.