Multi-objective Optimization-based Selection for Quality-Diversity by Non-surrounded-dominated Sorting

1 Introduction

Generating a set of high-quality and diverse solutions is important in a wide variety of scenarios, such as robotics [Cully et al., 2015; Allard et al., 2022; Salehi et al., 2022], combinatorial optimization [Do et al., 2022; Nikfarjam et al., 2022], multi-agent coordination [Lupu et al., 2021; Xue et al., 2022; Zhang et al., 2023; Yu et al., 2023], and reinforcement learning (RL) [Eysenbach et al., 2018; Parker-Holder et al., 2020;

∗This work was supported by the National Science Foundation of China (62022039, 62276124), and the CCF-Tencent Open Research Fund (CCF-Tencent RAGR20220110). Chao Qian is the corresponding author.

Chalumeau et al., 2023]. For example, it is difficult for one single policy to adapt to a variety of situations when controlling a multi-foot robot, while maintaining a set of diverse policies (i.e., policies having different frequencies of using each foot) can improve robustness, e.g., enabling the robot to recover quickly from damage [Cully et al., 2015].

Evolutionary algorithms (EAs) [B¨ack, 1996; Zhou et al., 2019] are general-purpose heuristic optimization algorithms that maintain a set of solutions, and simulate the natural evolution process by iterative reproduction and selection. Quality-Diversity (QD) algorithms [Cully et al., 2015; Mouret and Clune, 2015; Cully and Demiris, 2018; Chatzilygeroudis et al., 2021] are a specific type of EAs that aim to return a set of high-quality and diverse solutions in a single run. Given an objective function to be maximized and a behavior descriptor vector function, QD algorithms attempt to find a set of solutions that can cover the space of the behavior descriptor and have high objective values. Specifically, a QD algorithm maintains a set of solutions (called an archive), and iteratively performs the following process: selects a subset of parent solutions from the archive, then applies reproduction operators (e.g., crossover and mutation) to generate offspring solutions, and finally uses these offspring solutions to update the archive. The excellent performance of QD algorithms has been demonstrated in many RL tasks, such as exploration [Ecoffet et al., 2021; Miao et al., 2022], robust training [Kumar et al., 2020; Yuan et al., 2023a; Yuan et al., 2023b], policy ensemble [Sheikh et al., 2022], and environment generation [Bhatt et al., 2022].

The parent selection strategy and offspring reproduction operator are critical to the performance of QD algorithms [Cully and Demiris, 2018]. Many recent works have been focusing on developing more efficient reproduction operators [Nilsson and Cully, 2021; Fontaine and Nikolaidis, 2021; Tjanaka et al., 2022] to improve the sample efficiency, while using uniform random selection to select the parent solutions by default, which may, however, be inefficient due to the lack of selection pressure.

Multi-objective Optimization (MO) [Deb, 2011] considers the problems that optimize multiple conflicting objectives simultaneously, and the goal is to obtain a set of Pareto optimal solutions that can represent different trade-offs of the objectives. Thus, it is natural to view different types of behaviors as multiple objectives to optimize, and select the parent solutions based on MO before reproducing offspring solutions in QD [Shen et al., 2020; Villin et al., 2021]. However, MObased selection strategies have not shown satisfactory performance as expected [Wang et al., 2022].

In this paper, we point out the reason of the ineffectiveness of MO-based selection in QD for the first time. That is, optimizing multiple behavior descriptor functions simultaneously can obtain a set of diverse solutions with different preferences over behaviors, but actually only concentrates on a certain area of the behavior space (e.g., maximizing two behavior descriptor functions simultaneously will focus on the upper right part of the behavior space); while the goal of QD is to cover the whole behavior space. Figure 1 gives an example illustration of applying MO-based selection to the most popular QD algorithm, Multi-dimensional Archive of Phenotypic Elites (MAP-Elites, ME) [Cully et al., 2015; Mouret and Clune, 2015]. ME discretizes the behavior space into M cells, each containing at most one solution, obtaining its archive. The goal of ME is to maximize the sum of the objective values of all solutions in the archive, called QD-Score. It can be clearly observed that the previous MO-based selection methods cannot cover the whole behavior space well, and thus can hardly help maximize the QD-Score.

To address the above issue of MO-based selection, we propose surrounded dominance, a new concept for solution comparison in MO. Traditionally, a solution Pareto dominates another one if it is not worse on all objectives and is better on at least one objective; thus, the behavior descriptor functions are optimized only in one direction. Now, surrounded dominance is a relationship between a solution and a solution set: a solution is surrounded dominated if for each possible direction of the behavior descriptor functions, there is a solution in the set which Pareto dominates it. Thus, by Non-Surroundeddominated Sorting (NSS), the diverse solutions covering the behavior space well can be selected (as shown in the last subfigure of Figure 1), which can help improve the QD-Score efficiently. Note that the proposed NSS is a general selection method, which can be used in various QD algorithms, e.g., ME [Mouret and Clune, 2015], PGA-ME [Nilsson and Cully, 2021], and OG-ME [Fontaine and Nikolaidis, 2021].

We conduct experiments on synthetic functions and popular benchmarks (i.e., QDGym [Nilsson and Cully, 2021; Flageat et al., 2023], robotic arm [Cully et al., 2015; Fontaine and Nikolaidis, 2021], and Mario environment generation [Bhatt et al., 2022]) to examine the performance of NSS. As expected, the results show that NSS achieves better performance (i.e., QD-Score) than the other MO-based selection methods [Shen et al., 2020; Villin et al., 2021]. Furthermore, it can perform better, even compared with the state-ofthe-art selection methods [Wang et al., 2022].

2 Background

2.1 Quality Diversity

QD algorithms aim to find a diverse set of high-quality solutions of a problem [Cully and Demiris, 2018; Chatzilygeroudis et al., 2021]. Let X denote the solution space, and S ⊆ Rk denote the k-dimensional descriptor space. Given an objective (quality) function f : X → R to be maximized and a behavior descriptor function m : X → S, the goal of QD algorithms is to find solutions that span the k-dimensional descriptor space S while maximizing the objective function f .

Take the most well-known QD algorithm, ME [Cully et al., 2015; Mouret and Clune, 2015], as an example. It maintains an archive by discretizing the descriptor space S into M cells {Si}Mi=1 and storing at most one solution in each cell. ME tries to fill in the cells with as high-quality solutions as possible. That is, the goal of ME can be formalized as maximizing the QD-Score:

where xi denotes the solution contained by the cell Si, i.e., m(xi) ∈ Si. Note that if a cell Si does not have a solution xi, then f(xi) is defined as 0. Without loss of generality, the objective value f(·) is assumed (or converted) to be nonnegative, to prevent solutions from decreasing the QD-Score.

The main procedure of QD algorithms is to iteratively select parent solutions from the archive, generate offspring solutions by reproduction operators, and update the archive. The selection method, a key component of QD algorithms [Cully and Demiris, 2018], aims to address the following question [Chatzilygeroudis et al., 2021]: Given the current archive, how do we select appropriate parent solutions to generate new offspring solutions? Uniform random selection, i.e., selecting parent solutions from the archive uniformly at random, is one of the simplest selection methods and has been widely used in QD algorithms such as [Cully et al., 2015; Nilsson and Cully, 2021; Fontaine and Nikolaidis, 2021; Tjanaka et al., 2022]. Recently, Wang et al. [2022] proposed a clustering-based selection method EDO-CS, which divides the archive into several clusters and then selects good parent solutions from each cluster. They compared different selection methods on various continuous control tasks, showing the state-of-the-art performance of EDO-CS and also demonstrating the importance of an efficient selection method.

2.2 Multi-objective Optimization-based Selection

Another branch of selection methods for QD are based on Multi-objective Optimization (MO), which tries to maximize multiple objective functions f1, . . . , fk : X → R simultaneously, i.e.,

The objective function vector (f1(x), . . . , fk(x)) is also represented as f(x) for convenience. Since the objectives are usually conflicting, two solutions may be incomparable, and the solution comparison is usually based on the Pareto dominance relationship [Deb, 2011], as shown in Definition 1. This also implies that there is no single optimal solution in MO, but rather a set of Pareto optimal solutions.

Definition 1 (Pareto Dominance). A solution x Pareto dominates x′ (denoted as x ≻ x′ ) if ∀i : fi(x) ≥ fi(x′ ) and ∃i : fi(x) > fi(x′ ). A solution x∗ is Pareto optimal if ∄x ∈ X such that x ≻ x∗ . The set of all Pareto optimal solutions is called Pareto Set (PS). The set of the corresponding objective vectors of PS, i.e., {f(x) | x ∈ PS}, is called Pareto Front (PF).

As the size of PF can be exponentially large, the goal of MO is often to find a set of Pareto optimal solutions, which can approximate the PF well. Furthermore, each Pareto optimal solution represents a unique trade-off between the objectives. Thus, the obtained set of solutions can be seen as diverse from the perspective of multiple objectives, and MO has been naturally used to select diverse parent solutions in QD [Shen et al., 2020; Villin et al., 2021]. There have been three types of MO formulation for parent selection in QD. MOP1 [Villin et al., 2021] treats each behavior descriptor function mi : X →R as an objective, i.e.,

which promotes diversity only. MOP2 [Shen et al., 2020; Villin et al., 2021] considers quality into the MO formulation:

where for each objective [f(x),mi(x)], f(x) is prioritized over mi(x), i.e., x is better than x′ if f(x) > f(x′ ), or f(x) = f(x′ ) ∧ mi(x) > mi(x′ ). MOP3 [Villin et al., 2021] also considers quality, but treats the quality function f as another objective directly, i.e.,

However, these MO-based selection methods do not lead to satisfactory performance of QD. This is because maximizing multiple behavior descriptor functions simultaneously actually only focuses on a certain area of the behavior space, while the goal of QD is to cover the whole behavior space. This has been observed in Figure 1, when MOP1-3 are applied to ME in the QD Hopper environment.

3 Method

In this section, we first introduce a new concept of surrounded dominance for solution comparison in Section 3.1, which considers all the possible directions of the behavior space. Based on this, we propose the Non-Surrounded-dominated Sorting (NSS) for selecting parent solutions in QD in Section 3.2, and analyze its property in Section 3.3. Finally, we use NSS as the selection method of ME, resulting in the algorithm NSS-ME in Section 3.4.

3.1 Surrounded Dominance

As discussed in Section 2.2, the classical MO-based selection methods based on Pareto dominance prefer the solutions in a certain direction of the behavior space (i.e., maximizing all the behavior descriptor functions simultaneously). This issue makes them hard to improve the performance of QD algorithms efficiently, whose goal is to obtain a set of highquality solutions covering the whole behavior space. To address this issue, we propose a new concept called surrounded dominance, which considers all possible directions of the behavior space rather than a certain direction.

Definition 2 (Surrounded Dominance). For a solution x and a solution set A, x is surrounded dominated by A if for each d ∈ D = {-1, 1}k , there exists a solution x′ ∈ A such that x′ ≻ x with respect to the objective vector d ⊙m(·), where ⊙ denotes the element-wise product of two vectors.

Different from classical Pareto dominance, surrounded dominance is a relationship between a solution and a solution set. It uses a vector in {-1, 1}k to represent one direction (where k denotes the number of behavior descriptor functions), and the behavior descriptor vector m(·) = (m1(·), . . . ,mk(·)) is multiplied by this vector for comparison in this direction. A solution x is surrounded dominated by a solution set A if for each direction d ∈ {-1, 1}k , there is a solution x′ in A better than x, i.e., x′ ≻ x with respect to d⊙m(·). That is, the behavior descriptors are considered in all possible directions for comparison.

However, surrounded dominance only considers the behavior descriptor functions m1(·), . . . ,mk(·) (i.e., diversity) but ignores the objective function f(·) (i.e., quality), making it only have the ability of exploring the behavior space but hardly improve the quality of the solutions or spread the high-quality solutions to other areas. To address this issue, we further propose surrounded dominance with quality.

Definition 3 (Surrounded Dominance with Quality). For a solution x and a solution set A, x is surrounded dominated by A if for each d ∈ D = {-1, 1}k , there exists a solution x′ ∈ A such that f(x′ ) > f(x) and x′ ≻ x with respect to the objective vector d ⊙m(·), where ⊙ denotes the elementwise product of two vectors.

That is, a solution x non-surrounded-dominated by a solution set A implies that there exists one direction d ∈ {-1, 1}k such that no solution x′ ∈ A satisfies that f(x′ ) > f(x) and x′ ≻ x with respect to d ⊙ m(·). Thus, by selecting non-surrounded-dominated solutions for reproduction, QD algorithms can either explore new area of the behavior space or improve the quality of explored areas. In the absence of ambiguity, surrounded dominance is defaulted to the version with quality for simplicity. An example for surround dominance is provided in Appendix A.

3.2 Non-surrounded-dominated Sorting

Based on surrounded dominance, we propose the NSS method to sort the solutions in an archive A. Specifically, NSS divides the solutions in A into several hierarchical nonsurrounded-dominated fronts {Pi}i∈I, where Pi denotes the i-th front, and |I| is the total number of fronts. The first front P1 contains the solutions that are not surrounded dominated by A. After determining {Pj}j∈{1,2,...,i}, a solution in A \ {Pj}j∈{1,2,...,i} (i.e., the remaining solution set after removing the solutions in {Pj}j∈{1,2,...,i} from the archive A) is added into Pi+1 if it is not surrounded dominated by A \ {Pj}j∈{1,2,...,i}. According to the definition of surrounded dominance, the solutions in P1 have less-explored or low-quality neighbor area in the behavior space, implying that the offspring solutions generated from the solutions in P1 are more likely to explore the areas of the behavior space that are not reached and spread the high-quality solutions to other areas. Therefore, it is natural to select the solutions from the top-ranked fronts as the parent solutions during the reproduction process of QD algorithms to improve their performance. An example illustration in Figure 1 has clearly shown that NSS can select more diverse solutions in the behavior space than previous MO-based selection methods.

The detailed procedure of NSS is presented in Algorithm 1. For each solution x in the archive A, NSS first initializes a dominance counter vector c(x) ∈ R|D| , where D = {-1, 1}k denotes the direction vector set, k is the number of behavior descriptor functions, and the i-th dimension ci(x) is the number of solutions x′ satisfying that f(x′ ) > f(x) and x′ ≻ x with respect to the i-th direction di ⊙m(·) of the behavior space. Note that di denotes the i-th direction vector in D. Accordingly, NSS initializes |D| dominating sets {Qi(x)}|D| i=1 for each solution x, where Qi(x) contains all the solutions x′ such that f(x) > f(x′ ) and x ≻ x′ with respect to di ⊙m(·). If the dominance counter vector c(x) of a solution x contains 0 elements, x is not surrounded dominated by the archive A according to Definition 3, and thus will be put into P1 in line 2. After determining P1, the dominance counter vectors of the remaining solutions in A \ P1 will be updated by ignoring those solutions in P1, and the solutions with at least one 0 element in their dominance counter vectors will be put into the second front P2. This process will be repeated until all the solutions have been put into the corresponding non-surrounded-dominated fronts, as shown in lines 4-15. In particular, after determining Pi, NSS checks the solutions in the dominating set Qj(x), for each solution x ∈ Pi and each direction dj ∈ D in line 6. If the dominance counter vector c(x′ ) of a solution x′ ∈ Qj(x) does not have 0 elements, i.e., x′ has not been put into the fronts, then its dominance counter cj(x′ ) in the corresponding direction dj will be reduced by 1 in line 8. If cj(x′ ) is reduced to 0, implying that x′ must be not surrounded dominated by the remaining solution set A\{Pj}j∈{1,2,...,i}, then it will be put into the next front Pi+1 in line 10.

Algorithm 1 Non-surrounded-dominated Sorting

Input: archive A

Output: hierarchical non-surrounded-dominated fronts {P1,

P2, . . .} of the archive A

• 1: For each solution x ∈ A, initialize its dominance counter vector c(x) and dominating sets {Qi(x)}|D| i=1 ;
• 2: Put all the solutions whose dominance counter vector has at least one 0 element into P1;

3: Let i = 1; 4: while Pi ̸= ∅ do 5: Let Pi+1 ← ∅; 6: for all x ∈ Pi, j ∈ {1, 2, . . . , |D|}, x′ ∈ Qj(x) do 7: if c(x′ ) does not have 0 elements then 8: cj (x′ ) ← cj (x′ ) - 1; 9: if cj(x′ ) = 0 then 10: Pi+1 ← Pi+1 ∪ {x′ } 11: end if 12: end if 13: end for 14: i ← i + 1 15: end while 16: return {Pj}j∈{1,2,...,i-1}

3.3 Property of NSS

Let Aopt denote the optimal archive, which consists of the highest-quality solution for each point in the behavior space. Next, we prove in Theorem 1 that a surrounded dominated solution will not appear in Aopt, implying that considering only non-surrounded-dominated solutions by the NSS-based selection will not miss good solutions. The proof utilizes a behavior-quality function gAopt : S →R as follows:

where xb is the solution having behavior b in Aopt, i.e., xb ∈ Aopt and m(xb) = b. It also relies on an assumption that gAopt is quasi-concave, which intuitively means that the further away from the optimal behavior (i.e., the behavior with the highest quality), the worse the quality of the behavior. This assumption often holds in QD problems. For example, in QD Walker [Nilsson and Cully, 2021], the goal is to make the agent walk fast, where the quality is measured by the agent's forward speed, and the two-dimensional behavior vector function is described by the fraction of time each foot was touching the ground during an episode. Obviously, the agent can walk fast only when the fractions of time are appropriate; the greater the fractions deviate from the appropriate values, the slower the agent walks.

Theorem 1. A surrounded dominated solution will not appear in the optimal archive Aopt.

Proof. Assume that a solution x in the optimal archive Aopt is surrounded dominated by an archive A. According to the definition of surrounded dominance, i.e., Definition 3, we have for each direction di ∈ D, there exists a solution xi such that f(xi) > f(x) and xi ≻ x with respect to the objective vector di ⊙m(·). Let B = {x1, . . . , x|D|}. It is obvious that m(x) is in the convex hull of the set {m(x′ ) | x′ ∈ B}.

Algorithm 2 NSS-ME

Parameter: number T of total generations, number N of selected solutions in each generation

Output: archive A

• 1: Let A← ∅, t ← 1; 2: while t ≤ T do 3: if t = 1 then 4: B(t) o ←Randomly Generate(N) 5: else 6: B(t) p ←NSS Select(A,N); 7: B(t) o ←Reproduction(B(t) p ) 8: end if 9: Evaluate(B(t) o ); 10: Update Archive(A, B(t) o ); 11: t ← t + 1 12: end while 13: return A

Let fBmin = minx′∈B f(x′ ). By the quasi-concave assumption of the behavior-quality function gAopt in Eq. (6), the upper-level behavior set SfBmin of gAopt with respect to the threshold fBmin is a convex set. Since f(x′ ) ≥ fBmin for any x′ ∈ B, the convex hull of {m(x′ ) | x′ ∈ B} must be a subset of SfBmin . Thus, we have m(x) ∈ SfBmin , implying f(x) ≥ fBmin = minx′∈B f(x′ ), contradicting ∀x′ ∈ B : f(x) < f(x′ ). Thus, the theorem holds.

3.4 NSS-based QDAlgorithms

Finally, we apply NSS-based selection to the most popular framework ME of QD algorithms, resulting in NSS-ME, as presented in Algorithm 2. We will use NSS-ME to examine the effectiveness of NSS in the experiments.

At the beginning, the archive A is created as an empty set in line 1, and the N offspring solutions B(1) o are randomly generated in line 4. After that, in each generation t (where t > 1), NSS-ME first selects N parent solutions B(t) p from the archive A by NSS Select(A,N) in line 6, which selects N solutions from the top-ranked non-surrounded-dominated fronts of A obtained by NSS in Algorithm 1. Let {Pi}i∈I denote the non-surrounded-dominated fronts of A, and let j ∗ = max{j ≥ 0 | ∑ji=1 |Pi| ≤ N}. The N parent solutions B(t) p consists of {Pi}i∈{1,2,...,j ∗ } and N - ∑j ∗ i=1 |Pi| solutions randomly selected from Pj ∗+1. The offspring solutions B(t) o are then generated via reproduction operators in line 7, such as Gaussian mutation in ME [Mouret and Clune, 2015], objective gradient in OG-ME [Fontaine and Nikolaidis, 2021], and policy gradient in PGA-ME [Nilsson and Cully, 2021; Flageat et al., 2023]. After evaluating B(t) o , NSS-ME updates the archive A based on the rules of ME methods [Mouret and Clune, 2015; Nilsson and Cully, 2021]. That is, each solution x ∈ B(t) o is placed in its corresponding cell in the behavior space according to its behavior m(x). If the cell is empty, x is kept directly; otherwise, the one with a higher quality between x and the solution occupying the cell is kept.

4 Experiments

To examine the performance of NSS, we conduct experiments on synthetic functions and several complex tasks, including QDGym, robotic arm, and Mario environment generation. We consider the following three main metrics for evaluation.

• QD-Score: The total sum of objective (quality) values across all solutions in the archive, as defined in Eq. (1). It reflects both the quality and diversity of the solutions, and is the most important metric to evaluate a QD algorithm [Pugh et al., 2016; Cully and Demiris, 2018].
• Coverage: The total number of solutions in the archive. It can measure the exploration ability of a QD algorithm.
• Best Performance: The largest objective value of solutions in the archive. It can measure the exploitation ability of a QD algorithm.

For each task, we will compare NSS with other parent selection methods under the same implementation of ME for fair comparison. We run each method multiple times independently, and report the average results. The detailed settings of experiments are provided in Appendix B. Our code is available at https://github.com/lamda-bbo/NSS.

4.1 Synthetic Functions

First, we conduct experiments on a simple synthetic function to show the advantage of NSS over other MO-based selection methods intuitively. We define a 2-dimensional behavior descriptor vector function adopted from [Fontaine and Nikolaidis, 2021]: the first and second dimensions are the sum of the first and second half of the elements of a real-valued vector solution, respectively. The objective function is defined as the sum of the distance between each element of the solution and the average of the half the element belongs to. We compare NSS with random selection and previous MO-based methods, including MOP1, MOP2, and MOP3 in Eqs. (3)- (5) [Shen et al., 2020; Villin et al., 2021]. All of these selection methods use ME [Mouret and Clune, 2015] as the framework and all the other components are set to the same.

As shown in Figure 2, NSS achieves the highest QD-Score and fills the largest number of cells in the behavior descriptor space, demonstrating its superior overall performance and exploration ability. Although MOP2 and MOP3 have a little higher best performance than NSS, they cannot cover the behavior space well, and their QD-Scores are extremely low. MOP1 performs badly in all three metrics. These previous MO-based selection methods are even worse than random selection on QD-Score and archive coverage. Figure 3 also visualizes the archives obtained by different MO-based methods. We can clearly observe that the solutions obtained by MOP1-3 are concentrated in the upper right corner of the behavior space, while NSS can cover the behavior space well.

4.2 Complex Tasks

QDGym. It is a popular benchmark to evaluate QD algorithms [Nilsson and Cully, 2021; Tjanaka et al., 2022; Flageat et al., 2023]. We conduct experiments on four different environments, i.e., QD Hopper, Walker, HalfCheetah, and Ant. These tasks aim to generate a set of policies that move forward as fast as possible and are diverse in the frequency of feet use. Thus, the objective function is determined by the agent's forward speed, and the behavior descriptor functions are defined as the fraction of time each foot was touching the ground during an episode. The ME framework here uses the implementation in [Mouret and Clune, 2015]. In addition, we also conduct the experiments with PGA-ME [Nilsson and Cully, 2021; Flageat et al., 2023], achieving similar results which are shown in Appendix C.1 due to space limitation.

Robotic Arm. It aims to find a set of joint angle solutions for a robotic arm that allows the end effector positions to cover its reachable space [Cully et al., 2015; Fontaine and Nikolaidis, 2021]. The objective function is defined as the variance of the joint angles, and the behavior descriptor functions are defined as the positions of the end effector. All the parent selection methods on this task use OG-ME [Fontaine and Nikolaidis, 2021] as the framework.

Mario Environment Generation. The QD algorithms can be used to generate a set of diverse environments [Fontaine et al., 2021; Bhatt et al., 2022]. We conduct experiments on Mario environment generation, which aims to generate a set of Mario environments with diverse properties. The generated environments are evaluated by simulating a pre-trained agent in the environments provided in [Bhatt et al., 2022]. The objective function is defined as the completion rate. The two behavior descriptor functions are defined as the number of tiles of a certain type that are in the upper half of the 2D grid, and the number of jumps of the agent, respectively. We use the implementation of ME in [Mouret and Clune, 2015].

Besides random selection and MOP1-3 compared in Section 4.1, we run three more parent selection methods here. NSLC [Lehman and Stanley, 2011] considers both the novelty score and local quality score (i.e., the number of neighbors that a solution outperforms), and selects parent solutions from the corresponding Pareto front obtained by NSGAII [Deb et al., 2002]. Curiosity-based selection [Cully and Demiris, 2018] calculates the curiosity score based on the history information (i.e., increases the score if the offspring solution improves the QD-Score; otherwise, decreases it), and selects the solutions with higher curiosity scores. EDOCS [Wang et al., 2022] divides the archive into several clusters and then selects good parent solutions from each cluster. It has been shown that EDO-CS achieves state-of-the-art performance in many tasks [Wang et al., 2022]. For these three methods, we use their recommended hyperparameters.

The results are shown in Table 1. Instead of simply showing the QD-Score of the returned archive, we use QD-Score AUC [Tjanaka et al., 2022],

where T is the total number of generations, and λ is the number of evaluated solutions per generation. That is, the QDScore AUC measures the area under the QD-Score curve, which quantifies the optimization efficiency of a QD algorithm. It can be observed from Table 1 that NSS has the best average rank, EDO-CS is the runner-up, and the previous MO-based selection methods (i.e., MOP1-3) performs the worst (even worse than random selection). We also perform the Wilcoxon rank-sum test with significance level 0.05, and the row '+/-/≈' shows the clear advantage of NSS over other methods. For the running time, NSS-based selection costs 0.0618s per generation on QD HalfCheetah, which is much faster than 0.2918s of EDO-CS, which requires clustering for selection. The complete results about running time are shown in Appendix C.2. Figure 4 visualizes the archives obtained by different methods on QD Hopper, which clearly demonstrates the superiority of NSS. Compared with other methods, NSS can cover a large area of the behavior space, and generate more high-quality solutions. More visualization results are shown in Appendix C.3.

4.3 Additional Results

In our experiments, we have used surrounded dominance with quality in Definition 3 when implementing NSS-based selection. Here, we conduct ablation study to compare it with the version without quality (i.e., using surrounded dominance in Definition 2). Figure 5 shows that NSS archives higher QD-Score and best performance, validating the importance of considering the quality in surrounded dominance.

Furthermore, we analyze the influence of the number N of selected solutions in each generation. Figure 6 shows that a too small or too large N may lead to relatively worse performance, but the performance is overall not very sensitive to N. Note that N is a hyperparameter that comes with the ME framework, while NSS is a selection method without additional hyperparameters. On the contrary, other competitive selection methods (i.e., NSLC, Curiosity and EDO-CS) have additional hyperparameters, e.g., Curiosity requires to decide the reward and penalty values of curiosity score. The ablation study on the number M of cells is provided in Appendix C.4.

5 Conclusion

The parent selection methods play an important role in QD algorithms. This paper analyzes why classical MO-based selection fails, and then proposes the NSS-based selection method by considering all directions in the behavior space. Experiments on synthetic functions and several complex tasks show the superiority of NSS. NSS can be incorporated into various QD algorithms, which can be beneficial in real-world applications. Improving the scalability of NSS w.r.t the number of behavior descriptor functions is an interesting future work.