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 most multi-objective test problems, the dimensionality of the Pareto set is the same as the dimensionality of the Pareto front. That is, an m-objective test problem with n decision variables usually has an (m-1)-dimensional Pareto front and an (m-1)-dimensional Pareto set. Thanks to this property, the mapping between the Pareto front and the Pareto set is usually a one-to-one mapping. In this paper, we formulate two-objective distance minimization problems in an n-dimensional decision space using Manhattan distance. The two objectives are defined by two target points in the decision space. That is, each objective is to minimize the Manhattan distance from the solution to each target point. The main characteristic feature of our test problems is that the dimensionality of the Pareto set can be arbitrarily specified between 1 and n by the locations of the two target points. For example, the Pareto set dimensionality in a 20-dimensional decision space is an arbitrarily specified integer between 1 and 20. These test problems have multimodality since many points in the Pareto set are mapped to the same single point on the Pareto front. In this paper, we first explain the relation between the locations of the two target points and the Pareto set dimensionality. Then, through computational experiments, we show that our simple test problems pose difficult challenges for both multi-objective algorithms and multi-modal multi-objective algorithms. We also discuss the scalability of the proposed test problems with respect to the number of equivalent Pareto sets and the number of objectives.

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.

For a multi-objective optimization problem, an inverse model approximates a mapping from the objective space to the decision space. Recently, the inverse model has been used in some evolutionary multi-objective optimization algorithms (EMOAs) to generate offspring solutions. In those algorithms, the inverse model is usually built based on the current population and is used to generate offspring solutions around the current population. In this paper, we utilize both the current and previous populations to estimate the locations of future (i.e., improved) solutions in the objective space. The estimated objective vectors are presented to the inverse model to generate improved solutions in the decision space for future generations. Thus, our inverse model is used to generate better solutions than the current solutions instead of generating new solutions by interpolating the current solutions. Based on this idea, a solution generation method is proposed, which can be easily embedded into almost all EMOAs. We embed our method into two standard EMOAs (i.e., NSGA-II and NSGA-III) and two inverse model-based EMOAs (i.e., IM-MOEA and IM-MOEA/D). Our experimental results show that our method improves the performance of these EMOAs in most of the three-objective WFG and LSMOP problems.

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.

Multi-modal multi-objective optimization has become a hot research topic in the evolutionary multi-objective optimization (EMO) community. To support this line of study, many multi-modal multi-objective test problems have been developed to better understand the behavior of each algorithm in achieving a good balance between convergence and diversity in the decision space. However, the trade-off between decision space diversity and objective space diversity has not been well investigated. In this paper, first, we clearly explain that the widely used DTLZ1–4 test problems exhibit multi-modality (i.e., there exists a many-to-one mapping from the Pareto set to the Pareto front) despite their frequent use as standard benchmark problems for multi-objective optimization. Then, we demonstrate that the trade-off between decision space diversity and objective space diversity can be visually examined using the DTLZ1–4 problems with three or more objectives. Using these four test problems, we examine the search behavior of three standard EMO algorithms and three multi-modal multi-objective evolutionary algorithms (MMEAs). Experimental results show that uniformly distributed solutions obtained by the standard EMO algorithms in the objective space do not have good uniformity in the decision space. In contrast, solution sets obtained by different MMEAs show different trade-offs between decision space diversity and objective space diversity.

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.

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.

In this paper, we revisit endless online level generation with the recently proposed experience-driven procedural content generation via reinforcement learning (EDRL) framework. Inspired by an observation that EDRL tends to generate recurrent patterns, we formulate a notion ofstate space closurewhich makes any stochastic state appeared possibly in an infinite-horizon online generation process can be found within a finite-horizon. Through theoretical analysis, we find that even though state space closure arises a concern about diversity, it generalises EDRL trained with a finite-horizon to the infinite-horizon scenario without deterioration of content quality. Moreover, we verify the quality and the diversity of contents generated by EDRL via empirical studies, on the widely usedSuper Mario Bros.benchmark. Experimental results reveal that the diversity of levels generated by EDRL is limited due to the state space closure, whereas their quality does not deteriorate in a horizon which is longer than the one specified in the training. Concluding our outcomes and analysis, future work on endless online level generation via reinforcement learning should address the issue of diversity while assuring the occurrence of state space closure and quality.

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.

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).

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.

Reinforcement learning algorithms have performed well in playing challenging board and video games. More and more studies focus on improving the generalisation ability of reinforcement learning algorithms. The GVGAI Learning Competition aims to develop agents capable of learning to play different game levels that were unseen during training. This paper summarises the five years' GVGAI Learning Competition editions. At each edition, three new games were designed. The training and test levels were designed separately in the first three editions. Since 2020, three test levels of each game were generated by perturbing or combining two training levels. Then, we present a novel reinforcement learning technique with dual-observation for general video game playing, assuming that it is more likely to observe similar local information in different levels rather than global information. Instead of directly inputting a single, raw pixel-based screenshot of the current game screen, our proposed general technique takes the encoded, transformed global and local observations of the game screen as two simultaneous inputs, aiming at learning local information for playing new levels. Our proposed technique is implemented with three state-of-the-art reinforcement learning algorithms and tested on the game set of the 2020 GVGAI Learning Competition. Ablation studies show the outstanding performance of using encoded, transformed dual observations as input.

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.

We introduce a procedural content generation (PCG) framework at the intersections of experience-driven PCG and PCG via reinforcement learning, named ED(PCG)RL, EDRL in short. EDRL is able to teach RL designers to generate endless playable levels in an online manner while respecting particular experiences for the player as designed in the form of reward functions. The framework is tested initially in the Super Mario Bros game. In particular, the RL designers of Super Mario Bros generate and concatenate level segments while considering the diversity among the segments. The correctness of the generation is ensured by a neural net-assisted evolutionary level repairer and the playability of the whole level is determined through AI-based testing. Our agents in this EDRL implementation learn to maximise a quantification of Koster's principle of fun by moderating the degree of diversity across level segments. Moreover, we test their ability to design fun levels that are diverse over time and playable. Our proposed framework is capable of generating endless, playable Super Mario Bros levels with varying degrees of fun, deviation from earlier segments, and playability. EDRL can be generalised to any game that is built as a segment-based sequential process and features a built-in compressed representation of its game content.

Applying latent variable evolution to game level design has become more and more popular as little human expert knowledge is required. However, defective levels with illegal patterns may be generated due to the violation of constraints for level design. A traditional way of repairing the defective levels is programming specific rule-based repairers to patch the flaw. However, programming these constraints is sometimes complex and not straightforward. An autonomous level repairer which is capable of learning the constraints is needed. In this paper, we propose a novel approach, CNet, to learn the probability distribution of tiles giving its surrounding tiles on a set of real levels, and then detect the illegal tiles in generated new levels. Then, an evolutionary repairer is designed to search for optimal replacement schemes equipped with a novel search space being constructed with the help of CNet and a novel heuristic function. The proposed approaches are proved to be effective in our case study of repairing GAN-generated and artificially destroyed levels of Super Mario Bros. game. Our CNet-assisted evolutionary repairer can also be easily applied to other games of which the levels can be represented by a matrix of objects or tiles.