In the community of evolutionary multi-objective optimization (EMO), artificially designed test problems (e.g., DTLZ) are usually used to evaluate the performance of EMO algorithms. To analyze the performance of EMO algorithms on these test problems, researchers usually consider the features of the test problems such as the shape of the Pareto front, the number of objectives, and the number of decision variables. However, a few studies investigate the shape of the feasible region of the test and real-world problems. In this paper, we visualize the feasible regions of some real-world problems in their objective spaces. Our visualization results show that the feasible region shape of most real-world problems is similar to that of WFG and Minus-DTLZ test problems. These observations suggest the usefulness of WFG and Minus-DTLZ as test problems to evaluate EMO algorithms. Our observations are also consistent with reported performance comparison results on DTLZ, WFG, Minus-DTLZ, Minus-WFG and some real-world problem suites in the literature.

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 this paper, we discuss the optimal distributions of solutions for maximizing the minimum crowding distance on linear Pareto fronts of two- and three-objective problems. Our discussions are twofold. One is theoretical discussions to analytically derive the optimal distributions. The other is empirical discussions, which are based on a newly implemented indicator-based algorithm to maximize the minimum crowding distance. First, we show the upper bound on the minimum crowding distance, which is derived from the upper bound on the total crowding distance. Next, we theoretically derive the optimal distributions for maximizing the minimum crowding distance on two-objective linear Pareto fronts. Our analysis shows that two solutions always overlap in the optimal distributions when the population size is an even number. For an odd number population size, the optimal distribution cannot be uniquely specified except for some anchor solutions (i.e., many different distributions are optimal). The theoretically obtained optimal distributions are compared with experimental results by our indicator-based algorithm. Then, we show an example of optimal distributions for a three-objective linear Pareto front where the population size is a multiple of three. Our indicator-based algorithm is also compared with the standard NSGA-II algorithm and its steady-state variant.

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.

Coevolution is a state-of-the-art constraint handling technique (CHT), which optimizes objectives and satisfies constraints by simultaneously evolving two populations. One is the main population which is evolved considering constraints, and the other is the subpopulation evolved by ignoring some or all constraints. Existing coevolutionary algorithms maintain the utilization strategies for the subpopulation throughout the entire search process, which can result in inefficient use of computational resources. To effectively utilize the subpopulation in a coevolutionary algorithm for constrained multiobjective optimization problems (CMOPs), this paper divides its search process into two stages with different search priorities, leveraging the stage-switching mechanism of PPS-MOEA/D. Based on the CCMO framework, we propose several variants with different subpopulation utilization strategies in the second stage, and evaluate their performance on both artificial and real-world CMOPs. Our experimental results reveal that CMOPs can be classified into three categories, each requiring a distinct subpopulation utilization strategy. The results also confirm the usefulness of the two following subpopulation utilization strategies in the second stage: (i) to decrease the number of offspring generated in the subpopulation, and (ii) to enhance the cooperation (connection) between the main population and the subpopulation.

Multi-objective neural architecture search (NAS) aims to find a set of model architectures to achieve different trade-offs between the model performance and the model complexity. The evaluation of the model performance usually requires a time-consuming training process, which is the main bottleneck in a NAS algorithm. To address this issue, many training-free metrics have been proposed in the literature to estimate the model performance without training. In this paper, we examine 13 training-free metrics on a two-objective NAS problem based on NAS-Bench-201. Our results show that the training-free metric which has a high correlation with the model performance does not always generate an estimated Pareto front with high quality. We embed these training-free metrics into four widely-used evolutionary multi-objective optimization algorithms (EMOAs) to solve the two-objective NAS problem. Our results show that the EMOAs with the Synaptic Flow metric obtain the best approximation of the Pareto front among the 13 training-free metrics.

In the community of evolutionary multi-objective optimization (EMO), large-scale multi-objective optimization problems (LSMOPs) with many decision variables have attracted much attention. The main difficulty of LSMOPs lies in their high-dimensional decision space, which slows down the convergence of EMO algorithms towards the Pareto front. To address this issue, many novel variation operators have been proposed to improve the efficiency of EMO algorithms. However, for both conventional EMO algorithms (e.g., NSGA-II) and recently proposed EMO algorithms (e.g., LERD), the polynomial mutation with the mutation probability 1/n, where n is the number of decision variables, is always used. For LSMOPs with a large number of decision variables, the mutation probability 1/n looks too small (e.g., 1/1000). In this paper, we examine different mutation probabilities and find that many existing EMO algorithms with a larger mutation probability (e.g., 10/n) are significantly better than the standard setting (i.e., 1/n) in handling LSMOPs.

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.

In the community of evolutionary multi-objective optimization (EMO), one important issue is the choice of test problems for performance evaluations of EMO algorithms. This is because performance evaluation results of EMO algorithms totally depend on the choice of test problems. This means that the research on new EMO algorithm design is also influenced by the choice of test problems. Recently, researchers have started to use real-world problems for performance evaluation of EMO algorithms. Among them, a real-world problem suite RE has attracted much attention and has been used in many studies. However, most RE problems have been created from real-world constrained problems by using the total constraint violation as an additional objective. That is, the original versions of most RE problems are not unconstrained multi-objective problems. Thus, even when a good solution set is obtained by an EMO algorithm for an RE problem, it can be a poor solution set for its original constrained problem. This is because many well-distributed solutions over the entire Pareto front of the transformed unconstrained problem are usually infeasible solutions of the original constrained problem with some positive total constraint violation values. In this paper, we examine whether good solution sets obtained by EMO algorithms for RE problems are also good solution sets for their original constrained problems. Our experimental results show that good solutions sets for most RE problems include good feasible solution sets for their original constrained problems. However, for a few RE problems, good solution sets obtained by some high performance EMO algorithms do not include good feasible solution sets. Our results show that high-performance EMO algorithms on most RE problems generate good feasible solution sets for their original constrained versions. This observation supports the usefulness of those RE problems as test problems for performance evaluation of EMO algorithms.

Recently, multi-objective evolutionary algorithms (MOEAs) with an unbounded external archive (UEA) have received increasing attention in the evolutionary multi-objective optimization community. Its basic idea is to store all examined solutions during the optimization process and select representative solutions as the final output for the decision-maker (DM). Although many studies have investigated MOEAs with UEA, there is a lack of studies focusing on the final solution selection. Actually, selecting a good solution from UEA that meets the requirements of the DM is a challenging task due to the limited information processing capacity of the human decision-maker. Moreover, in many real-world scenarios, decision-makers often prefer not to evaluate a large number of solutions and may not have clear preferences over objectives. To fill this gap in post-processing for MOEAs with UEA, this paper proposes an interactive final solution selection (IFSS) method for multi-objective optimization. The proposed IFSS method aims to provide a good final solution through several interactions with the DM. In other words, the DM can obtain a satisfying solution after evaluating only a small number of solutions even without providing clearly specific preferences. Furthermore, a calibration strategy is introduced to significantly improve the performance of IFSS by slightly increasing the number of interactions. Extensive experiments are conducted on various test problems to demonstrate the effectiveness of the proposed IFSS method.

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.

Recently, there has been a growing interest in large-scale multiobjective optimization problems within the evolutionary multiobjective optimization (EMO) community. These problems involve hundreds or thousands of decision variables and multiple conflicting objectives, which pose significant challenges for conventional EMO algorithms (EMOAs). It is generally believed that EMOAs have difficulty in efficiently finding good non-dominated solutions as the number of decision variables increases. To address this issue, in this paper, we propose a novel method that incorporates heuristic initialization and knowledge-based mutation into EMOAs for solving large-scale multi-objective 0-1 knapsack problems. Various large-scale multi-objective 0-1 knapsack problems with an arbitrary number of constraints are generated as test problems to evaluate the effectiveness of the proposed method. Experimental results show that the proposed novel initialization and mutation method significantly improves the performance of the original EMOAs in terms of both the convergence speed in early generations and the quality of the final population.

Newly proposed many-objective algorithms have been almost always compared with NSGA-III for performance evaluation. Since the authors of the NSGA-III paper have not provided any source code, researchers usually use an available implementation in popular optimization platforms. This can lead to unreliable comparison results if different performance of NSGA-III is obtained depending on the choice of a platform. In this paper, we show that the implementations of NSGA-III are slightly different between the two most frequently used EMO optimization platforms: PlatEMO and pymoo. Then, we examine the effect of the implementation difference on the performance of NSGA-III in each platform. Our experimental results show that almost the same results are obtained from the two implementations on the frequently-used DTLZ test problems. However, our experimental results also show that clearly different results are obtained from the two implementations on multi-objective combinatorial optimization problems. Finally, we demonstrate that the weaker performance of the PlatEMO implementation of NSGA-III can be improved by replacing its normalization mechanism with the corresponding mechanism in Pymoo. That is, our experimental results show that small differences in the normalization mechanisms of the two implementations lead to large differences in their performance on multi-objective combinatorial optimization problems.

In real-world applications, multi-objective optimization problems (MOPs) usually have multiple constraints. To solve constrained MOPs (CMOPs), various constraint handling techniques (CHTs) were proposed in the field of evolutionary multi-objective optimization (EMO). A simple CHT with high applicability is to use the total constraint violation as an additional objective. The total constraint violation-based CHT transforms a constrained$(m-1)$-objective MOP to an unconstrained m-objective MOP. This CHT was also used to create a real-world unconstrained multi-objective test suite called RE from real-world constrained problems. Recently, the RE test suite has been frequently used for evaluating EMO algorithms. Only when the additional objective value is zero (i.e., only when the total constraint violation is zero), solutions are feasible in the original constrained MOP. This means that feasible solutions of the original constrained MOP are located on the boundary of the Pareto front of the formulated unconstrained MOP. As a result, the final population of an EMO algorithm on the formulated unconstrained MOP includes many infeasible solutions of the original constrained MOP. This means that good solution sets for the unconstrained MOP are not always good solution sets for the original constrained MOP. In this paper, we propose an improved total constraint violation-based CHT. The core idea is to use not only positive constraint violations but also negative constraint violations. We apply the proposed CHT to real-world constrained MOPs. Experimental results show that the proposed modification improves the quality of feasible solutions obtained by the total constraint violation-based CHT.

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.

External archives have attracted more and more attention in the evolutionary multi-objective optimization (EMO) community. This is because a solution set selected from an external archive is usually better than the final population of an EMO algorithm. Whereas the effects of subset selection from external archives have already been investigated on artificial test problems, its effects on real-world problems have not been examined. In this paper, we examine the effects of subset selection from external archives for ten EMO algorithms on two real-world problem suites. Experimental results show that the performance improvement by subset selection is large for most algorithms and many problems but small for a few algorithms and a few problems (i.e., algorithm dependent and problem dependent).

A long-standing question in the evolutionary multi-objective (EMO) community is how to generate a good initial population for EMO algorithms. Intuitively, as the starting point of optimization, a good initial population can have positive effects on the performance of EMO algorithms. However, in most existing EMO algorithms, one of the commonly-used initialization methods is to randomly generate a set of solutions as an initial population. One possible approach to improve random initialization is to include one or more Pareto optimal (near Pareto optimal) solution(s) in the initial population, which are expected to provide useful information and knowledge on the optimized problem. In this paper, to investigate the effectiveness of this initialization idea, we examine and quantify the effects of including one or more Pareto optimal solution(s) in the initial population on the performance of EMO algorithms. Experimental results demonstrate that it is worthwhile to first obtain and then include some Pareto optimal solutions in the initial population. Through a number of experiments and algorithm behavior analysis, this study provides supports and insights into EMO algorithm design and motivates further research on population initialization for EMO algorithms.

In real-world multi-objective problems, each objective has a totally different scale. However, some frequently-used multi-objective evolutionary algorithms (MOEAs) have no objective space normalization mechanisms. The effect of objective space normalization on the performance of decomposition-based MOEAs (e.g., MOEA/D and NSGA-III) has already been examined for artificial test problems (e.g., DTLZ and WFG) in the literature. In this paper, we examine its practical usefulness for real-world multi-objective problems using various MOEAs. Our experimental results clearly show that objective space normalization is needed not only in decomposition-based MOEAs but also in hypervolume-based MOEAs. We also explain why objective space normalization is needed in these two types of MOEAs.

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.

Hypervolume subset selection (HSS) is a hot topic in the evolutionary multi-objective optimization (EMO) community since hypervolume is the most widely-used performance indicator. In the literature, most HSS algorithms were designed for small-scale HSS (e.g., environmental selection: select$N$solutions from$2N$solutions where$N$is the population size). Few researchers focus on large-scale HSS as a post-processing procedure in an unbounded external archive framework (i.e., subset selection from all examined solutions). In this paper, we propose a two-stage lazy greedy inclusion HSS (TGI-HSS) algorithm for large-scale HSS. In the first stage of TGI- HSS, a small solution set is selected from a large-scale candidate set using an efficient subset selection method (which is not based on exact hypervolume calculation). In the second stage, the final subset is selected from the small solution set using an existing efficient HSS algorithm. Experimental results show that the computational time can be significantly reduced by the proposed algorithm in comparison with other state-of-the-art HSS algorithms at the cost of only a small deterioration of the selected subset quality.

Population initialization is always needed in evolutionary multi-objective optimization (EMO) algorithms. Intuitively, a well-designed initialization method can help facilitate the evolutionary process and improve the performance of EMO algorithms. However, very few studies have investigated the effects of initialization methods on the performance of EMO algorithms. Many existing EMO algorithms randomly generate an initial population to start the evolutionary process. To fill this research gap and attract more attention from EMO researchers to this important yet under-explored issue, in this paper, we examine the effects of various initialization methods that may become promising alternatives to the commonly-used random initialization method. Each initialization method is evaluated through computational experiments on test problems of various sizes with 5–1000 decision variables. Experimental results clearly demonstrate the advantage of well-designed initialization methods over the random initialization method. This study provides useful insights into EMO algorithm design and motivates further research on population initialization.

Recently, it has been pointed out in many studies that the performance of evolutionary multi-objective optimization (EMO) algorithms can be improved by selecting solutions from all examined solutions stored in an unbounded external archive. This is because in general the final population is not the best subset of the examined solutions. To obtain a good final solution set in such a solution selection framework, subset selection from a large candidate set (i.e., all examined solutions) has been studied. However, since good subsets cannot be obtained from poor candidate sets, a more important issue is how to find a good candidate set, which is the focus of this paper. In this paper, we first visually demonstrate that the entire Pareto front is not covered by the examined solutions through computational experiments using MOEA/D, NSGA-III and SMS-EMOA on DTLZ test problems. That is, the examined solution set stored in the unbounded archive has some large holes (i.e., some uncovered area of the Pareto front). Next, to evaluate the quality of the examined solution set (i.e., to measure the size of the largest hole), we propose the use of a variant of the inverted generational distance (IGD) indicator. Then, we propose a simple modification of EMO algorithms to improve the quality of the examined solution set. Finally, we demonstrate the effectiveness of the proposed modification through computational experiments.

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.

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.

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.

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.

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.

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.

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.

A real-world multiobjective optimization problem (MOP) usually has differently scaled objectives. Objective space normalization has been widely used in multiobjective optimization evolutionary algorithms (MOEAs). Without objective space normalization, most of the MOEAs may fail to obtain uniformly distributed and well-converged solutions on MOPs with differently scaled objectives. Objective space normalization requires information on the Pareto front (PF) range, which can be acquired from the ideal and nadir points. Since the ideal and nadir points of a real-world MOP are usually not knowna priori, many recently proposed MOEAs tend to estimate and update the two points adaptively during the evolutionary process. Different methods to estimate ideal and nadir points have been proposed in the literature. Due to inaccurate estimation of the two points (i.e., inaccurate estimation of the PF range), objective space normalization may deteriorate the performance of an MOEA. Different methods have also been proposed to alleviate the negative effects of inaccurate estimation. This article presents a comprehensive survey of objective space normalization methods, including ideal point estimation methods, nadir point estimation methods, and different methods based on the utilization of the estimated PF range.

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.