without sufficient exploration. In rare failure cases this tunnel-vision can lead to many iterations being spent without recognising the potential of an opposite, or hard to find, high-performing region. In our results, the algorithm is able to recover within the allowed budget, falling in line with the better performing version with initial upscaling. However, if the algorithm were stopped early, or a smaller budget given, it would be desirable to have a good balance between predictive model quality and objective performance across a diverse space. This forms a strong justification for the initial upscaling.

<figure><img src="image_14.png" /><figcaption>Fig. 12. Comparison of Prediction Map performance with and without upscaling for various problems</figcaption></figure>

### D. Invalidity modelling

In this paper we implement an SVM model to predict the validity of a point in the search domain. The acquisition function becomes $EJIE^{++}$, actively modelling invalidity, only when an invalid point is found during an attempted evaluation. The PARSEC domain is the only benchmark we considered that features this invalidity.

Table XIII shows a comparison of the average QDS, the number of successful evaluations made $n_e$, and the number of invalid points sampled $n_i$, per run. A value of $\infty$ implies that the algorithm attempts to sample at an invalid point continuously, ending the run as a failure case.

<table><caption>TABLE XIII
MEAN PERFORMANCE WITH AND WITHOUT INVALIDITY MODELLING FOR THE PARSEC DOMAIN WITH COUPLED DESCRIPTORS.</caption><thead><tr><th rowspan="2"></th><th colspan="3">10x10</th><th colspan="3">25x25</th></tr><tr><th>QDS</th><th>n<sub>e</sub></th><th>n<sub>i</sub></th><th>QDS</th><th>n<sub>e</sub></th><th>n<sub>i</sub></th></tr></thead><tbody><tr><td>BOP-Elites<sup>++</sup></td><td>370.09</td><td>1000</td><td>31</td><td>2206.10</td><td>1250</td><td>94</td></tr><tr><td>BOP-Elites<sup>+</sup></td><td>196.20</td><td>237</td><td>&infin;</td><td>1431.05</td><td>344</td><td>&infin;</td></tr><tr><td>SPHEN</td><td>361.21</td><td>1000</td><td>125</td><td>1484.73</td><td>1250</td><td>362</td></tr></tbody></table>

SPHEN, like SAIL, builds an acquisition map using the UCB acquisition function to find valuable points and then randomly samples points from this. The points in the acquisition map are well-distributed in behaviour space and SAIL has only a vanishing probability to select the same point twice in sequential iterations. BOP-Elites, by contrast, always chooses the point that is maximal under the *EJIE* acquisition function. This means that if there arises no disincentive to select a point, it will continue to do so, leading to a complete failure of that algorithm, which we see here.

### E. Complexity and runtime of BOP-Elites

Our BOP-Elites implementation uses the BOTORCH [46] package in Python, and does not use GPUs. The posterior variance prediction step is the most significant contributor to the overall computational complexity in the BOP-Elites algorithm, as the complexity grows as $O(n^2)$, where n is the number of data points collected so far. The quadratic scaling arises from the need for kernel matrix multiplication, a process that is inherently computationally intensive as the number of samples increases. The posterior mean prediction step contributes $O(n)$.

In the initialisation of an expensive coupled problem, we find diverse descriptor values of points in X by rejection sampling over a Sobol set sampled from the descriptor GPs. In order to achieve good diversity and limit the computational cost, this number is set to a maximum of 10,000 posterior samples, where the first $k = 5$ points in each region are kept, and the process stops when each region has $k$ points. As BOTORCH is designed to benefit from batch sampling this step can be computed efficiently.

Pattern search is given a budget of 100 iterations. In each iteration it explores each input dimension. Therefore, each restart has a maximum number of calls to the GPs of $100d(m+1)$, to the m descriptor GPs and the GP for the fitness, with a maximum complexity of $O(100d(m+1)(n+n^2))$ accounting for mean and variance predictions.

In the case of invalidity modelling with an SVM, the current algorithm implements an RBF kernel and therefore, in the prediction step, has a computational complexity of $s \times d$ for the number of support vectors identified s and input dimensions d.

Fig. 13 shows the actual wall clock time of the optimisation of the acquisition function for an indicative BOP-Elites run on 4 10x10 coupled benchmark problems. We can see that the observed time grows quadratically with the number of samples so far.
without sufficient exploration. In rare failure cases this tunnel-vision can lead to many iterations being spent without recognising the potential of an opposite, or hard to find, high-performing region. In our results, the algorithm is able to recover within the allowed budget, falling in line with the better performing version with initial upscaling. However, if the algorithm were stopped early, or a smaller budget given, it would be desirable to have a good balance between predictive model quality and objective performance across a diverse space. This forms a strong justification for the initial upscaling.

<figure><img src="image_14.png" /><figcaption>Fig. 12. Comparison of Prediction Map performance with and without upscaling for various problems</figcaption></figure>

### D. Invalidity modelling

In this paper we implement an SVM model to predict the validity of a point in the search domain. The acquisition function becomes $EJIE^{++}$, actively modelling invalidity, only when an invalid point is found during an attempted evaluation. The PARSEC domain is the only benchmark we considered that features this invalidity.

Table XIII shows a comparison of the average QDS, the number of successful evaluations made $n_e$, and the number of invalid points sampled $n_i$, per run. A value of $\infty$ implies that the algorithm attempts to sample at an invalid point continuously, ending the run as a failure case.

<table><caption>TABLE XIII
MEAN PERFORMANCE WITH AND WITHOUT INVALIDITY MODELLING FOR THE PARSEC DOMAIN WITH COUPLED DESCRIPTORS.</caption><thead><tr><th rowspan="2"></th><th colspan="3">10x10</th><th colspan="3">25x25</th></tr><tr><th>QDS</th><th>n<sub>e</sub></th><th>n<sub>i</sub></th><th>QDS</th><th>n<sub>e</sub></th><th>n<sub>i</sub></th></tr></thead><tbody><tr><td>BOP-Elites<sup>++</sup></td><td>370.09</td><td>1000</td><td>31</td><td>2206.10</td><td>1250</td><td>94</td></tr><tr><td>BOP-Elites<sup>+</sup></td><td>196.20</td><td>237</td><td>&infin;</td><td>1431.05</td><td>344</td><td>&infin;</td></tr><tr><td>SPHEN</td><td>361.21</td><td>1000</td><td>125</td><td>1484.73</td><td>1250</td><td>362</td></tr></tbody></table>

SPHEN, like SAIL, builds an acquisition map using the UCB acquisition function to find valuable points and then randomly samples points from this. The points in the acquisition map are well-distributed in behaviour space and SAIL has only a vanishing probability to select the same point twice in sequential iterations. BOP-Elites, by contrast, always chooses the point that is maximal under the *EJIE* acquisition function. This means that if there arises no disincentive to select a point, it will continue to do so, leading to a complete failure of that algorithm, which we see here.

### E. Complexity and runtime of BOP-Elites

Our BOP-Elites implementation uses the BOTORCH [46] package in Python, and does not use GPUs. The posterior variance prediction step is the most significant contributor to the overall computational complexity in the BOP-Elites algorithm, as the complexity grows as $O(n^2)$, where n is the number of data points collected so far. The quadratic scaling arises from the need for kernel matrix multiplication, a process that is inherently computationally intensive as the number of samples increases. The posterior mean prediction step contributes $O(n)$.

In the initialisation of an expensive coupled problem, we find diverse descriptor values of points in X by rejection sampling over a Sobol set sampled from the descriptor GPs. In order to achieve good diversity and limit the computational cost, this number is set to a maximum of 10,000 posterior samples, where the first $k = 5$ points in each region are kept, and the process stops when each region has $k$ points. As BOTORCH is designed to benefit from batch sampling this step can be computed efficiently.

Pattern search is given a budget of 100 iterations. In each iteration it explores each input dimension. Therefore, each restart has a maximum number of calls to the GPs of $100d(m+1)$, to the m descriptor GPs and the GP for the fitness, with a maximum complexity of $O(100d(m+1)(n+n^2))$ accounting for mean and variance predictions.

In the case of invalidity modelling with an SVM, the current algorithm implements an RBF kernel and therefore, in the prediction step, has a computational complexity of $s \times d$ for the number of support vectors identified s and input dimensions d.

Fig. 13 shows the actual wall clock time of the optimisation of the acquisition function for an indicative BOP-Elites run on 4 10x10 coupled benchmark problems. We can see that the observed time grows quadratically with the number of samples so far.
<figure><img src="image_15.png" /><figcaption>Fig. 13. Wall clock performance of an indicative run of the BOP-Elites acquisition function on 4 coupled benchmarks, performed on a 3.6GHz CPU with 62GB RAM.</figcaption></figure>

While the raw wall clock time may be higher than other QD algorithms, BOP-Elites is designed for applications where evaluations are expensive. In domains where the actual objective function evaluations are costly (e.g., physical experiments,

expensive simulations), the time spent on model predictions is dwarfed by the real cost of the objective. Therefore the dominant factor in the overall optimisation time is the function evaluations themselves, not the computational overhead, or wall clock performance of the algorithm.

Furthermore, the implementation of BOP-Elites in this paper leaves room for several possible improvements with regard to wall clock performance.

* The pymoo [54] implementation of pattern search is sequential and cannot make use of parallel objective evaluations. Parallelising this step would cut run time by a factor of *d*.

* Our code does not currently run restarts in parallel, however, restarts would be straightforward to parallelise.

* While algorithms like SAIL select batches of points to evaluate each iteration, BOP-Elites uses a sequential point selection process, optimising several points but selecting only one to evaluate. Given BOP-Elites performs multiple restarts, it may be viable to select several points at once if the result from the restarts are sufficiently high performing and diverse from each other.

* Our implementation does not make use of the acceleration available through GPU's and this may reduce runtime.
<figure><img src="image_15.png" /><figcaption>Fig. 13. Wall clock performance of an indicative run of the BOP-Elites acquisition function on 4 coupled benchmarks, performed on a 3.6GHz CPU with 62GB RAM.</figcaption></figure>

While the raw wall clock time may be higher than other QD algorithms, BOP-Elites is designed for applications where evaluations are expensive. In domains where the actual objective function evaluations are costly (e.g., physical experiments,

expensive simulations), the time spent on model predictions is dwarfed by the real cost of the objective. Therefore the dominant factor in the overall optimisation time is the function evaluations themselves, not the computational overhead, or wall clock performance of the algorithm.

Furthermore, the implementation of BOP-Elites in this paper leaves room for several possible improvements with regard to wall clock performance.

* The pymoo [54] implementation of pattern search is sequential and cannot make use of parallel objective evaluations. Parallelising this step would cut run time by a factor of *d*.

* Our code does not currently run restarts in parallel, however, restarts would be straightforward to parallelise.

* While algorithms like SAIL select batches of points to evaluate each iteration, BOP-Elites uses a sequential point selection process, optimising several points but selecting only one to evaluate. Given BOP-Elites performs multiple restarts, it may be viable to select several points at once if the result from the restarts are sufficiently high performing and diverse from each other.

* Our implementation does not make use of the acceleration available through GPU's and this may reduce runtime.