# B2Opt: Learning to Optimize Black-box Optimization with Little Budget

Xiaobin Li  Kai Wu  Xiaoyu Zhang  Handing Wang  Jing Liu

###### Abstract

Learning to optimize (L2O) has emerged as a powerful framework for black-box
optimization (BBO). L2O learns the optimization strategies from the target
task automatically without human intervention. This paper focuses on obtaining
better performance when handling high-dimensional and expensive BBO with
little function evaluation cost, which is the core challenge of black-box
optimization. However, current L2O-based methods are weak for this due to a
large number of evaluations on expensive black-box functions during training
and poor representation of optimization strategy. To achieve this, 1) we
utilize the cheap surrogate functions of the target task to guide the design
of the optimization strategies; 2) drawing on the mechanism of evolutionary
algorithm (EA), we propose a novel framework called B2Opt, which has a
stronger representation of optimization strategies. Compared to the BBO
baselines, B2Opt can achieve 3 to $10^{6}$ times performance improvement with
less function evaluation cost. We test our proposal in high-dimensional
synthetic functions and two real-world applications. We also find that deep
B2Opt performs better than shallow ones.

Machine Learning, ICML

##  1 Introduction

Many tasks, such as neural architecture search (Elsken et al., 2019) and
hyperparameter optimization (Hutter et al., 2019; Golovin et al., 2017), can
be abstracted as black-box optimization (BBO), which means that although we
can evaluate $f(x)$ for any $x\in X$, we have no access to any other
information about $f$, such as the Hessian and gradients. Moreover, it is
expensive to evaluate $f(x)$ in most cases. Various hand-designed algorithms,
such as genetic algorithms (Mitchell, 1998; Khadka & Tumer, 2018; Zhang & Li,
2007), Bayesian optimization (Snoek et al., 2012; Mutny & Krause, 2018; Li et
al., 2017; Kandasamy et al., 2015; Balandat et al., 2020), and evolution
strategy (ES) (Wierstra et al., 2014; Hansen & Ostermeier, 2001; Auger &
Hansen, 2005; Salimans et al., 2017), have been designed to solve BBO.

Recently, the learning to optimize (L2O) framework (Andrychowicz et al., 2016;
Chen et al., 2022) gives a new insight into optimization. They leverage the
recurrent neural network (RNN), long short-term memory architecture (LSTM)
(Chen et al., 2020, 2017; Li & Malik, 2016; Wichrowska et al., 2017; Bello et
al., 2017), multilayer perceptron (MLP) (Metz et al., 2019), or Transformer
(Gärtner et al., 2022) as the optimizer to develop optimization methods,
aiming at reducing the laborious iterations of hand engineering (Vicol et al.,
2021; Flennerhag et al., 2021; Li & Malik, 2016; Sun et al., 2018). The core
of L2O is constructing a solid mapping from the initial solutions to the
optimal solution. Moreover, several efforts (Cao et al., 2019; Chen et al.,
2017; Lange et al., 2022) have coped with the black-box problems, their
effectiveness may be hindered by the limited representation capabilities of
optimization strategy and a large number of evaluations on expensive black-box
functions. As such, they often deal with low-dimensional problems.

This paper designs a novel L2O framework based on the advantages of Vision
Transformer (Dosovitskiy et al., 2021; Han et al., 2022) and EAs to overcome
the above limitations, termed as B2Opt. Inspired by the mechanism of EAs, we
design a strong model for representing optimization strategies. We design
three modules to realize the mapping from the random population to the optimal
population. To generate potential individuals to approach the optimal
solution, we first design a self-attention (SA)-based crossover module (SAC)
to simulate the crossover operator of EA. Then the output of this module is
input into the proposed feed-forward network (FFN)-based mutation module (FM)
to escape the optimal local solution. Moreover, the residual and selection
module (RSSM) is designed to survive the fittest individuals. RSSM is a
pairwise comparison between the output of SAC, FM, and the input population
regarding their fitness. We develop a B2Opt Block (OB) consisting of SAC, FM,
and RSSM. Finally, we construct B2Opt by stacking OBs to simulate generations
like EAs.

Moreover, to reduce the number of evaluations to an expensive black-box
function, we establish a cheap surrogate function set to train B2Opt. We
construct a set of cheap differentiable functions with similar properties to
the targeted BBO problems. This training set contains the pair of the initial
population and the designed surrogate function. Thus, we can use gradient-
based methods, such as stochastic gradient descent and Adam (Kingma & Ba,
2014), to train B2Opt. In this way, we don’t need to query expensive functions
during training.

We test B2Opt on six standard functions with high dimension, the neural
network training problem, and the planar mechanic arm problem (Wang et al.,
2021). The experimental results demonstrate the top rank of B2Opt and the
strong representation compared with three population-based baselines, Bayesian
optimization, and one learning-to-optimize method (Cao et al., 2019). The
highlights of this paper are shown as follows:

  * •

Compared with the advanced BBO methods, B2Opt can achieve 3-$10^{6}$ times
performance improvement at $\frac{1}{20}$ times the number of function
evaluations. Moreover, B2Opt still obtains good performance even if the
training dataset is low-fidelity compared with the target black-box function.

  * •

We design a new training method to reduce the evaluation cost of expensive
objective functions during training. It uses cheap surrogate functions for
expensive target tasks instead of directly evaluating the target black-box
function.

  * •

We design the B2Opt framework, which has a stronger ability to represent
optimization strategies. It is easier to map random solutions to optimal
solutions with fewer evaluation times during optimization.

##  2 Related Work

##### Meta-Learn Whole BBO Algorithm

Our proposal belongs to this type. (Chen et al., 2017) first explored meta-
learning entire algorithms for low-dimensional BBO. Then, (TV et al., 2020)
proposed RNN-Opt, which learned recurrent neural network (RNN)-based
optimizers for optimizing real parameter single-objective continuous functions
under limited budget constraints. Moreover, they train RNN-Opt with knowledge
of task optima. Swarm-inspired meta-optimizer (Cao et al., 2019) learns in the
algorithmic space of both point-based and population-based optimization
algorithms. (Gomes et al., 2021) employed meta-learning to infer population-
based black-box optimizers that can automatically adapt to specific classes of
tasks. These methods parametrize the optimization algorithm by an RNN
processing the raw solution vectors and their associated fitness.

##### Meta-Learn Part BBO Algorithm

This type only learns some parameters of the algorithm, not the overall
algorithm. (Shala et al., 2020) meta-learn a policy that configured the
mutation step-size parameters of CMA-ES (Hansen & Ostermeier, 2001). LES
(Lange et al., 2022) proposed a self-attention-based search strategy to
discover effective update rules for evolution strategies via meta-learning.

These schemes are all dealing with low-dimensional black-box problems. The
main reason for this is shown as follows: 1) to train the meta-optimizer, a
large number of expensive black-box functions need to be requested, which is
very unrealistic; 2) the established loss function for training the meta-
optimizer is challenging to optimize, resulting in a poor representation of
the optimization strategy. Simple network models can be optimized well, but
the model representation ability could be better; complex network models
cannot be well optimized, resulting in poor representation for optimization
strategy. Thus, we propose B2Opt overcome the above limitations.

Figure 1: Overall architecture of B2Opt and OB. $Nx$ stands for B2Opt is
composed of $Nx$ stacked OBs. These OBs can be set to share weights with each
other or not share weights with each other.

##  3 B2Opt

###  3.1 Problem Definition

A black-box optimization problem can be transformed as a minimization problem,
as shown in Eq. 1, and constraints may exist for corresponding solutions:

$\min\ f(x),s.t.\ x_{i}\in[l_{i},u_{i}]$ (1)

where $x=(x_{1},x_{2},\cdots,x_{d})$ represents the solution of optimization
problem $f$, the lower and upper bounds $l=(l_{1},l_{2},\cdots,l_{d})$ and
$u=(u_{1},u_{2},\cdots,u_{d})$, and $d$ is the dimension of $x$. Suppose $n$
individuals of one population be
$X_{1}=(X_{1,1},X_{1,2},\cdots,X_{1,d}),\cdots,X_{n}=(X_{n,1},X_{n,2},\cdots,X_{n,d})$,
then B2Opt are required to find the population near the optimal solution
$\hat{x}$. Note that we only have a very small number of function evaluations
to achieve. We suppose that $X^{0}$ is the initial population and $X^{t}$ is
the output population.

###  3.2 Self-Attention Crossover Module

Similar to the crossover operator in EAs, we propose a new module based on SA
to generate potential solutions by maximizing information interaction among
individuals in a population. The crossover operator generates a new individual
by $\sum_{i=1}^{n}X_{i}W_{i}^{c}$ (Zhang et al., 2021, 2022). $W_{i}^{c}$ is
the diagonal matrix. If $W_{i}^{c}$ is full of zeros, the $i$th individual has
no contribution. Suppose a population $X$ is arranged in a non-descending
order of fitness, and $F\in R^{n\times 1}$ be the fitness matrix of $X$. Then,
this module can be represented as follows:

$X^{c}=SAC(X,F)$ (2)

where $X^{c}$ is the output population of the SAC module.

Since the object processed by B2Opt is the population, and the order of
individuals in the population does not affect the population distribution, SA
does not require position coding. Standard SA projects the input sequence $X$
into a $d$-dimensional space via the queries ($Q$), keys ($K$), and values
($V$). These three mappings enable the SA module to capture better the
characteristics of the problems encountered during training. In other words,
these three mappings strengthen the ability of SA to focus on specific
problems but do not necessarily make SA have good transferability between
different problems. Therefore, we consider removing these three mappings for
enhanced transferability, and $X^{c}=AX$. $A\in R^{n\times n}$ is a self-
attention matrix that can be learned to maximize inter-individual information
interaction based on individual ranking information. This is why the
population needs to be sorted in non-descending order.

However, designing crossover operations based solely on population ranking
information is a coarse-grained approach. Because this method only considers
the location information of individuals in the population, but does not
consider the fitness relationship between individuals. Therefore, we further
introduce fitness information to assist in learning crossover operators:

$A^{F}=SA(F)=Softmax\left(FW^{Q}(FW^{K})^{T}/sqrt(d_{k})\right)$ (3)

Thus, $X^{c}=AX+A^{F}X$. To better balance the roles of $A$ and $A^{F}$, we
introduce two learnable weights $W_{1}^{c}\in R^{n\times 1}$ and $W_{2}^{c}\in
R^{n\times 1}$. Therefore, the final crossover operation is shown as follows:

$X^{c}=tile(W_{1}^{c})\odot(AX)+tile(W_{2}^{c})\odot(A^{F}X)$ (4)

where $X^{c}\in R^{n\times d}$ is the population obtained by $X$ through the
SAC module; $\odot$ represents Hadamard product; the _tile_ copy function
extends the vector to a matrix.

###  3.3 FFN-based Mutation Module

The mutation operator brings random changes into the population. Specifically,
an individual $X_{i}$ in the population goes through the mutation operator to
form the new individual $\hat{X}_{i}$, formulated as
$\hat{X}_{i}=X_{i}W_{i}^{m}$. $W_{i}^{m}$ is the diagonal matrix. In
Transformer, each patch embedding carries on directional feature
transformation through the FFN module. We take one linear layer as an example:
$X=XW^{F}$, where $W^{F}$ is the weight of the linear layer, and it is applied
to each embedding separately and identically. This equation and the mutation
operator have the same formula format, which inspires us to design a learnable
mutation module FM based on FFN with $ReLU$ activation function:

$X^{m}=FM(X^{c})=(ReLU(XW_{1}^{F}+b_{1}))W_{2}^{F}+b_{2}$ (5)

where $X^{m}$ is the population after the mutation of $X^{c}$. $W_{2}^{F}$ and
$W_{1}^{F}$ represent the weight of the second layer of FFN and the weight of
the first layer of FFN, respectively. $b_{2}$ and $b_{1}$ represent the bias
of the second layer and the first layer of FFN, respectively.

###  3.4 Selection Module

The residual connection in the transformer can be analogized to the selection
operation in EA (Zhang et al., 2021). We combine the residual structure and
selection module (SM) (Anonymous, 2023) to design a learnable selection module
RSSM. The RSSM generates the offspring population according to the following
equation:

$\displaystyle\hat{X}$ $\displaystyle=RSSM(X,X^{c},X^{m})$ (6)
$\displaystyle=Sort(SM(X,tile(W_{1}^{s})\odot X$
$\displaystyle+tile(W_{2}^{s})\odot X^{c}+tile(W_{3}^{s})\odot X^{m}))$

where $\hat{X}$ is the fittest population for the next generation; the
learnable weights $W_{1}^{s}\in R^{n\times 1}$, $W_{2}^{s}\in R^{n\times 1}$,
and $W_{3}^{s}\in R^{n\times 1}$ are the weights for $X$, $X^{c}$, and
$X^{m}$, respectively. $Sort(X)$ represents that $X$ is sorted in non-
descending order of fitness. We use quicksort to sort the population based on
function fitness. These three learnable weight matrices realize the weighted
summation of residual connections, thereby simulating a learnable selection
strategy. Meanwhile, the introduction of residual structure also enhances the
model’s representation ability, enabling B2Opt to form a deep architecture.

SM updates individuals based on a pairwise comparison between the offspring
and input population regarding their fitness. Suppose that $X$ and
$X^{{}^{\prime}}$ are the input populations of SM. We compare the quality of
individuals from $X$ and $X^{{}^{\prime}}$ pairwise based on fitness. A binary
mask matrix indicating the selected individual can be obtained based on the
indicator function $l_{x>0}(x)$, where $l_{x>0}(x)=1$ if $x>0$ and
$l_{x>0}(x)=0$ if $x<0$. SM forms a new population $\hat{X}$ by employing Eq.
7.

$\begin{split}\hat{X}&=tile(l_{x>0}(M_{F^{\prime}}-M_{F}))\odot X\\\
&+tile(1-l_{x>0}(M_{F^{\prime}}-M_{F}))\odot X^{{}^{\prime}}\end{split}$ (7)

where the _tile_ copy function extends the indication vector to a matrix,
$M_{F}(M_{F^{\prime}})$ denotes the fitness matrix of $X(X^{{}^{\prime}})$.

###  3.5 Structure of B2Opt

B2Opt comprises basic $t$ B2Opt blocks (OBs), and parameters can be shared
among these $t$ OBs or not. The overall architecture of B2Opt and OB is shown
in Figure 1. Each OB consists of SAC, FM, and RSSM. $X^{0}\in R^{n\times d}$
represents the initial population input into B2Opt, which needs to be sorted
in non-descending order of fitness. In Eq. 8, $X^{i-1}$ is fed into $OB_{t}$
to get $X^{i}$, where $i\in[1,t]$. B2Opt realizes the mapping from the random
initial population to the target population by stacking $t$ OBs.

$\displaystyle X^{i}=OB(X^{i-1});\ \ \ X^{c}=SAC(X^{i-1},F);$ (8)
$\displaystyle X^{m}=FM(X^{c});\ \ \ X^{i}=RSSM(X^{i-1},X^{c},X^{m})$

###  3.6 Training of B2Opt

##### Goal

We introduce the parameters $\theta$ of B2Opt, which need to be optimized.
Here, we set
$\theta=\\{W_{1}^{c},W_{2}^{c},A,W_{1}^{F},W_{2}^{F},b_{1},b_{2},W_{1}^{s},W_{2}^{s},W_{3}^{s}\\}$.

##### Training Dataset

Before introducing the details of the training dataset, fidelity (Kandasamy et
al., 2016) is defined as follows: Suppose the differentiable surrogate
functions $f_{1},f_{2},\cdots,f_{m}$ are the continuous exact approximations
of the black-box function $f$. We call these approximations fidelity, which
satisfies the following conditions: 1) $f_{1},\cdots,f_{i},\cdots,f_{m}$
approximate $f$. $||f-f_{i}||_{\infty}\leq\zeta_{m}$, where the fidelity bound
$\zeta_{1}>\zeta_{2}>\cdots\zeta_{m}$. 2) Estimating approximation $f_{i}$ is
cheaper than estimating $f$. Suppose the query cost at fidelity is
$\lambda_{i}$, and $\lambda_{1}<\lambda_{2}<\cdots\lambda_{m}$.

Training data is a crucial factor beyond the objective functions. This paper
establishes the training set by constructing a set of differentiable functions
related to the optimization objective. This training dataset only contains
$(X_{0},f_{i}(x|\omega))$, the initial population and objective function,
respectively. The variance of $\omega$ causes the shift in landscapes. The
training dataset is designed as follows: 1) Randomly initialize the input
population $X_{0}$; 2) Randomly produce a shifted objective function
$f_{i}(x|\omega)$ by adjusting the parameter $\omega$; 3) Evaluate $X_{0}$ by
$f_{i}(x|\omega)$; 4) Repeat Steps 1)-3) to generate the corresponding
dataset. We show the designed training and testing datasets as follows:

$F^{train}=\\{f_{1}(x|\omega_{1,i}^{train}),\cdots,f_{m}(x|\omega_{m,i}^{train})\\}$
(9)

where $\omega_{m,i}^{train}$ represents the $i$th different values of $\omega$
in the $m$th function $f_{m}$.

##### Loss Function

B2Opt attempts to search for individuals with high quality based on the
available information. The loss function tells how to obtain the parameters of
B2Opt to generate individuals closer to the optimal solution by maximizing the
difference between the initial population and the output population of B2Opt.
The following loss function $l_{i}(X^{0},f(x|\omega),\theta)$ is employed
(Anonymous, 2023),

$l_{i}=\frac{\frac{1}{|X^{0}|}{\sum\limits_{x\in
X^{0}}{f_{i}(x|\omega)}}-\frac{1}{|E_{\theta}(X^{0})|}{\sum\limits_{x\in
E_{\theta}(X^{0})}}f_{i}(x|\omega)}{\left|{\frac{1}{|X^{0}|}{\sum\limits_{x\in
X^{0}}f_{i}(x|\omega)}}\right|}$ (10)

where $\theta$ denotes parameters of B2Opt ($E$). Eq. 10 calculates the
average fitness difference between the input and output, further normalized
within $[0,1]$. To encourage B2Opt to explore the fitness landscape, for
example, the constructed Bayesian posterior distribution over the global
optimum (Cao & Shen, 2020) can be added to Eq. 10. Since the derivatives of
functions in the training dataset are available, we can obtain the gradient
information of Eq. 10 for the training process. Also, we can employ REINFORCE
(Williams, 1992) to approximate these derivatives.

Table 1: The compared results on six functions. The structure of B2Opt is 30 OBs with WS. $d$ | $f$ | DE | ES | CMA-ES | L2O-swarm | Dragonfly | B2Opt
---|---|---|---|---|---|---|---
10 | F4 | 0.13(0.06) | 0.22(0.30) | 4.2e-4(3.5e-4) | 16.92(2.10) | 1.3e3(1.3e3) | 1.2e-4(5e-5)
F5 | 4.99(1.24) | 0.55(0.37) | 0.03(0.01) | 2.97(0.01) | 48.4(9.58) | 8e-3(2e-3)
F6 | 210.2(49.7) | 60.02(48.28) | 61.90(96.25) | 26.83(21.48) | 3.8e8(1.4e8) | 8.93(0.03)
F7 | 17.83(3.59) | 51.53(8.05) | 45.74(17.02) | 4.88(3.55) | 81.1(24.0) | 0.01(0.03)
F8 | 0.21(0.07) | 0.26(0.18) | 7.6e-3(0.01) | 1.02(1.4e-3) | 35.4(22.6) | 1e-5(2e-5)
F9 | 1.90(0.32) | 20.56(0.03) | 0.04(0.02) | 9.06(0.67) | 16.2(3.64) | 0.01(3.4e-3)
100 | F4 | 8.2e3(3.8e2) | 8.9e4(9.5e3) | 7.8e3(1.2e3) | 0.32(0.03) | 1.1e4(3.8e3) | 0.11(0.09)
F5 | 28.2(0.61) | 80.2(2.10) | 78.3(9.18) | 0.28(1.3e-3) | 50(0) | 0.14(0.15)
F6 | 2.4e8(2.3e7) | 2.5e10(4.5e9) | 3.3e8(8.7e7) | 692(108) | 99(0) | 129(346)
F7 | 9410(548) | 8.9e4(1.1e4) | 8050(775) | 85.7(18.6) | 144(13.1) | 24.1(13)
F8 | 3.04(0.14) | 23.0(3.00) | 3(0.22) | 0.16(2.4e-4) | 125(11.3) | 0.02(0.03)
F9 | 18.9(0.14) | 21.4(0.02) | 21.4(0.04) | 2.49(2.5e-3) | 10.5(0.32) | 0.15(0.05)

##### Training B2Opt

We then train B2Opt under a supervised mode. Since the gradient is unnecessary
during the test process, B2Opt can solve BBO problems. To prepare B2Opt to
learn a balanced performance upon different optimization problems, we design a
loss function formulated as follows:

$\underset{\theta}{\arg\min}l_{\Omega}=-\frac{1}{K}\sum_{X^{0}\in\Omega}{l_{i}(X^{0},f_{i}(x|\omega_{i}^{train}),\theta)}$
(11)

We employ Adam (Kingma & Ba, 2014) method with a minibatch $\Omega$ to train
B2Opt upon training dataset.

##### Detailed Training Process

The goal of the training algorithm is to search for parameters ${\theta}^{*}$
of the B2Opt. Before training starts, B2Opt is randomly initialized to get
initial parameters $\theta$. Then the algorithm will perform the following
three steps in a loop until the training termination condition is satisfied:
Step 1, randomly initialize a minibatch $\Omega$ comprised of $K$ populations
$X^{0}$; Step 2, for each $f_{i}\in{F}^{train}$, given training data
$(X^{0},f_{i})$, update $\theta$ by minimizing the $l_{\Omega}$; Step 3, given
$X^{0}$, update $\theta$ by minimizing $-{1}/{m}\sum_{i}l_{\Omega}$, where $m$
is the number of functions in ${F}^{train}$. After completing the training
process, the algorithm will output ${\theta}^{*}$.

##  4 Experiments

###  4.1 Experimental Setup

####  4.1.1 Datasets

##### Synthetic Functions

This paper first employs nine commonly used functions to show the
effectiveness of the proposed B2Opt. The characteristics of these nine
functions are shown in Appendix Tables 6 and 7. Here, B2Opt is trained on
$F^{train}$ is generated based on functions in Table 6, and the target
functions are shown in Table 7. Here, $d=\\{10,100\\}$.

##### Planner Mechanic Arm

We further evaluate the performance of the proposed scheme on the planner
mechanic arm problem (Cully et al., 2015; Vassiliades et al., 2018;
Vassiliades & Mouret, 2018; Mouret & Maguire, 2020), which has been widely
used to evaluate the performance of the BBO algorithms. The optimization goal
of this problem is to minimize the distance from the top of the mechanic arm
to the target position by optimizing a set of lengths and angles. The detailed
problem can be found in Appendix C.2. $r$ represents the distance from the
target point to the origin of the mechanic arm, as shown in Appendix Fig. 7.

##### Neural Network Training

We also evaluate the performance of training a convolutional neural network
with 567 parameters (Howard et al., 2017) using B2Opt on the MNIST
classification task. The structure of this network model is shown in Appendix
Table 9. This task involves a large number of parameters; in order to make
B2Opt stable to train, we replaced SAC with a neural network with the
structure shown in Appendix Table 10. The detailed problem can be found in
Appendix C.3.

####  4.1.2 Baselines

B2Opt is compared with the state-of-the-art BBO methods, including non-L2O and
L2O-based methods.

Standard EA baselines. DE(DE/rand/1/bin) (Das & Suganthan, 2010),
ES(($\mu$,$\lambda$)-ES), and CMA-ES, where DE and ES are implemented based on
Geatpy (Jazzbin, 2020), and CMA-ES is implemented by Pymoo (Blank & Deb,
2020).

Bayesian optimization. Dragonfly (Kandasamy et al., 2020), a representative
algorithm for Bayesian optimization, is employed as a reference.

L2O-based methods. L2O-swarm (Cao et al., 2019) is a representative L2O method
for BBO. We do not compare with (Chen et al., 2017; Lange et al., 2022)
because they require extensive evaluation of expensive objective functions
during the training phase.

We design three B2Opt models, including 3 OBs with WS, 5 OBs without WS, and
30 OBs with WS. 3 OBs with WS represents that B2Opt has 3 OB modules and these
OBs share the weights of each other. The parameters of these methods are shown
in Appendix D.

Table 2: The results of planar mechanical arm. Simple Case (SC): searching for different angles with the fixed lengths. Complex Case (CC): searching for different angles and lengths. | $r$ | DE | ES | CMA-ES | L2O-Swarm | B2Opt | Untrained
---|---|---|---|---|---|---|---
SC | 100 | 1.20(0.64) | 10.6(5.58) | 1.36(0.35) | 40.4(3.89) | 0.30(0.18) | 243(238)
300 | 1.38(0.71) | 44.9(43.3) | 1.38(0.41) | 69.5(3.77) | 0.48(0.37) | 1210(820)
1000 | 93.8(137) | 183(239) | 43.7(110) | 176(7.20) | 26.6(57.4) | 5070(2770)
CC | 100 | 0.81(0.47) | 8.95(6.42) | 0.76(0.20) | 31.9(1.78) | 0.06(0.05) | 243(238)
300 | 6.15(12.2) | 47.8(56.0) | 0.87(0.37) | 89.1(1.96) | 0.50(0.79) | 1210(820)
1000 | 232(233) | 251(258) | 88.4(158) | 262(2.99) | 25.0(55.8) | 5070(2770)

###  4.2 Results

##### Synthetic Functions

The results on six functions are provided in Table 1. B2Opt outperforms three
EA baselines, Dragonfly, and L2O-swarm in all cases but loses once to
Dragonfly in F6 with $d=100$. It should be noted that the number of function
evaluations used by the comparison algorithms is much higher than our method.
But surprisingly, we still have a strong advantage. These cases also show the
excellent generalization ability of B2Opt on more tasks unseen during the
training stage. We think the transferability of B2Opt is proportional to the
fitness landscape similarity between the training set and the problem.
Although new problem attributes are not available in the training set, B2Opt
can still perform better. However, this conclusion only holds when the
similarity between the problem and training dataset is high. The detailed
reasons for the good effect of B2Opt are shown in Appendix F. We plot the
convergence curves of B2Opt (10 OBs with WS), ES, DE, and CMA-ES on F7. B2Opt
converges quickly and can obtain better solutions. B2Opt can only iterate ten
times to get the best solution relative to EA baselines. ES and DE converge
around 100 generations, and CMA-ES shows a slow convergence rate.

Figure 2: The convergence curves of B2Opt and EA baselines. It shows the
convergence curve of these algorithms on F7 in Appendix Table 7.

##### Planner Mechanic Arm

The detailed experimental results are given in Tables 2. B2Opt selects 5 OBs
without WS as the example, which evolves only five generations. Untrained
represents the untrained B2Opt. The results of L2O-Swarm are obtained when
L2O-Swarm converges. DE, ES, and CMA-ES are tested when the maximum
generations are set to 100. EA baselines have 100/5 times as many function
evaluations as B2Opt. However, even in this unfair situation, B2Opt achieves
the best results. We have observed that B2Opt can achieve better results with
deeper architectures. However, it is currently difficult for us to train deep
B2Opt. Moreover, as far as we know, the use of ES to optimize deep models has
been studied a lot (Vicol et al., 2021), which will be an essential research
prospect in the future.

DE, ES, and CMA-ES are tested when the maximum generations are set to 10, 50,
and 100, respectively. The results are shown in Appendix Table 8. The fewer
function evaluations, the greater the advantage of B2Opt.

Table 3: The classification accuracy of four methods on the MNIST dataset. Dataszie represents the proportion of data sets involved in training. Datasize | B2Opt | ES | DE | CMA-ES
---|---|---|---|---
0.25 | 0.69(0.01) | 0.21(0.02) | 0.21(0.01) | 0.44(0.04)
0.5 | 0.80(0.01) | 0.21(0.01) | 0.24(0.01) | 0.47(0.05)
0.75 | 0.85(0.00) | 0.21(0.01) | 0.22(0.02) | 0.45(0.04)
1 | 0.86(0.00) | 0.25(0.02) | 0.23(0.02) | 0.49(0.03)

##### Neural Network Training

The detailed results are shown in Table 3. B2Opt has three OBs that do not
share weights. We use 1000 samples from the MINST dataset to form the training
set and another 1000 samples as the test set. The evaluation metric is test
accuracy. While training, the optimization objective of B2Opt is to minimize
the cross-entropy loss, which is a surrogate function for the metric accuracy.
However, the optimization goal of EAs is to maximize the accuracy on the
training set. We select 25%, 50%, 75%, and 100% data from the training set for
training, respectively, constituting surrogate problems with different
fidelity levels. Even in this unfair case, B2Opt achieves the best results for
all fidelity levels. Fig. 3 shows the convergence of B2Opt and EA baselines
for the same number of evaluations. B2Opt can achieve the best solution with
the least number of evaluations.

Figure 3: Convergence curves of B2Opt and EA baselines on the task of training
a neural network. The X-axis represents the number of evaluations and the
Y-axis represents the test accuracy.

###  4.3 Parameter Analysis

We analyze the effect of the learning rate, deep structure, and weight sharing
between OBs. We consider the performance of different B2Opt architectures. The
experimental results are shown in Table 4. We find that they were sorted from
good to worst by their performance, and the result is 30 OBs with WS$>$5 OBs
without WS$>$3 OBs with WS. Deep architectures have better representation
capabilities and also lead to better performance. However, it is challenging
to train non-weight-sharing B2Opts with more layers due to the difficulty of
training deep architectures. Untrained represents that the parameters of 5 OBs
without WS are randomly initialized. The results show that 5 OBs without WS
outperforms Untrained, which demonstrates the effectiveness of the designed
training process.

Table 4: The performance of different B2Opt structures.

$f$ | Untrained | 5 OBs | 30 OBs | 3 OBs
---|---|---|---|---
|  | without WS | with WS | with WS
F4 | 0.28(0.09) | 0.08(0.03) | 1.2e-4(5e-5) | 8.16(3.44)
F5 | 0.37(0.05) | 0.15(0.03) | 0.008(0.002) | 1.47(0.40)
F6 | 45.8(16.9) | 15.43(2.34) | 8.93(0.03) | 1891(1396)
F7 | 1.08(0.72) | 4.43(1.82) | 0.01(0.03) | 35.72(8.52)
F8 | 0.69(0.09) | 0.06(0.03) | 1e-5(2e-5) | 0.82(0.10)
F9 | 0.85(0.20) | 0.29(0.07) | 0.01(0.003) | 3.28(1.00)

We also find an interesting phenomenon: 5 OBs without WS outperforms 3 OBs
with WS in all cases. Our untrained deep architecture, 5 OBs without WS, can
achieve good results on simple cases, which shows that B2Opt retains the
advantages of Transformer architecture and has strong generalization ability.
We use the untrained 5 OBs with WS to test the complex plannar mechanic arm
problem and find that it performs poorly.

We train B2Opt on F1-F3 with different learning rates ($lr$) and then test
them on the F4-F9 function set. The experimental results are shown in Table 11
(see Appendix E). For 5 OBs without WS, setting $lr=0.01$ achieves the
relatively best performance. Using $lr=0.0001$ would be a good choice for 30
OBs with WS and 3 OBs with WS.

We also explore the impact of the size of the training data set on the
performance of the algorithm and take F4 as an example. It is trained on
various biases of F4 and tested on F4 without bias. The training data set is
$F^{train}=\\{F4(x|\omega_{1,i}^{train}),\cdots,F4(x|\omega_{m,i}^{train})\\}$.
Experimental results show that the size of the training dataset has a
significant impact on the performance of B2Opt. As the amount of training data
increases, the performance of B2Opt increases.

Figure 4: The impact of training dataset size on B2Opt.

Figure 5: Crossover Strategy learned by B2Opt.

###  4.4 Ablation Study

This section considers the performance impact of different parts in B2Opt. We
take B2Opt with 3 OBs and weight sharing as an example, which is trained on
F1-F3 and tested on F4-F9. We remove SAC, FM, RSSM, and RC in B2Opt,
respectively, and denote them as Not SAC, Not FM, Not RSSM, and Not RC. The
experimental results are shown in Table 5. When their results are sorted from
good to worst, the rank is B2Opt $>$ Not FM $>$ Not RC $\approx$ Not SAC
$\approx$ Not RSSM. The role of FM is slightly weaker than that of the other
three modules. Taken as a whole, the parts of SAC, RSSM, and RC are of equal
importance. The absence of these core components can seriously affect the
performance of B2Opt. At the same time, it also shows the effectiveness of the
proposed four modules. The removal of any one of the modules in the crossover,
mutation, and selection of EAs will degrade the performance of EAs. This shows
that B2Opt implements a learnable EA framework that does not require human-
designed parameters.

Table 5: The results of ablation study. $d$ = 10.

$f$ | Not SAC | Not FM | Not RC | Not RSSM | B2Opt
---|---|---|---|---|---
F4 | 52.7(15.0) | 23.3(6.68) | 50.5(6.81) | 271(346) | 3.03(5.82)
F5 | 5.08(0.98) | 2.94(0.41) | 3.75(0.09) | 3.51(1.49) | 1.02(0.20)
F6 | 1e5(9e4) | 1e4(1e4) | 5e4(1e4) | 7e6(1e8) | 4e3(7e4)
F7 | 47.2(5.11) | 19.7(4.27) | 63.4(8.60) | 40.6(8.10) | 44.8(8.34)
F8 | 1.18(0.04) | 1.19(0.07) | 0.87(0.07) | 3.28(1.14) | 0.60(0.17)
F9 | 4.49(1.09) | 3.42(0.78) | 8.36(0.43) | 3.56(0.72) | 3.03(0.70)

###  4.5 Visualization Analysis

The tested model is 5 OBs with WS trained on F1-F3 with $d=100$. The
population size is set to 100.

Visual Analysis of SAC The crossover strategies learned by the five SAC are
shown in Fig. 5. For the presentation, we select individuals with fitness
rankings 1st, 50th, and 100th. The horizontal axis represents the fitness
ranking of individuals, and the vertical axis represents the attention (weight
when performing crossover) on these individuals. OB1 tends to crossover with
lower-ranked individuals, showing a preference for exploration. From OB1 to
OB5, the bias of SAC gradually changes from exploration to exploitation.

Figure 6: Mutation strategy learned by B2Opt for F5.

Visual Analysis of FM We visualize the FM of B2Opt to explore its behavior. As
a reference, we use polynomial mutation in genetic algorithms. Given the input
population (input), the mutated population (OB1) is obtained through OB1; the
new population (mutpolyn) is obtained by performing polynomial mutation on the
input population. We visualize F4-F9 and observe the following phenomena:

1) The population generated by performing polynomial mutation is more evenly
distributed on the landscape. However, most of the solutions produced by FM in
B2Opt are concentrated in ”areas with greater potential”, which are closer to
the optimal solution. Moreover, the population distribution generated by our
scheme also takes diversity into account. The non-optimal solution area is
also more comprehensive than that of polynomial mutation, which is more
conducive to jumping out of the local solution.

2) The population produced by performing polynomial mutation moves slightly
compared to the original population. However, FM can guide the input
population to make big moves toward the optimal solution, which significantly
accelerates the algorithm’s convergence.

This shows that B2Opt can use the information of the objective function to
design the mutation strategy automatically, making it more applicable to the
target optimization task, which is consistent with our motivation.

##  5 Conclusions

The better performance than that of EA baselines, Bayesian optimization, and
the L2O-based method demonstrates the effectiveness of B2Opt. Moreover, B2Opt
can be well adapted to unseen BBO. Meanwhile, we experimentally demonstrate
that the proposed three modules have positive effects. However, B2Opt still
has room for improvement.

1) In the loss function, we do not effectively consider the diversity of the
population, and the population can be regularized in the future;

2) The training set seriously affects the performance of B2Opt. If the
similarity between the training set and the optimization objective is low, it
will cause the performance of B2Opt to degrade drastically. Building the
dataset as relevant to the target as possible is essential.

## References

  * Andrychowicz et al. (2016) Andrychowicz, M., Denil, M., Gomez, S., Hoffman, M. W., Pfau, D., Schaul, T., Shillingford, B., and De Freitas, N.  Learning to learn by gradient descent by gradient descent.  In _Advances in Neural Information Processing Systems_ , pp. 3981–3989, 2016.
  * Anonymous (2023) Anonymous.  DECN: Evolution inspired deep convolution network for black-box optimization.  In _Submitted to The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=Ur_qORZ6-9R.  under review.
  * Auger & Hansen (2005) Auger, A. and Hansen, N.  A restart cma evolution strategy with increasing population size.  In _2005 IEEE Congress on Evolutionary Computation_ , volume 2, pp. 1769–1776, 2005.
  * Balandat et al. (2020) Balandat, M., Karrer, B., Jiang, D., Daulton, S., Letham, B., Wilson, A. G., and Bakshy, E.  Botorch: a framework for efficient monte-carlo bayesian optimization.  _Advances in neural information processing systems_ , 33:21524–21538, 2020.
  * Bello et al. (2017) Bello, I., Zoph, B., Vasudevan, V., and Le, Q. V.  Neural optimizer search with reinforcement learning.  In _International Conference on Machine Learning_ , pp. 459–468. PMLR, 2017.
  * Blank & Deb (2020) Blank, J. and Deb, K.  pymoo: Multi-objective optimization in python.  _IEEE Access_ , 8:89497–89509, 2020.
  * Cao & Shen (2020) Cao, Y. and Shen, Y.  Bayesian active learning for optimization and uncertainty quantification in protein docking.  _Journal of Chemical Theory and Computation_ , 16(8):5334–5347, 2020.
  * Cao et al. (2019) Cao, Y., Chen, T., Wang, Z., and Shen, Y.  Learning to optimize in swarms.  _Advances in Neural Information Processing Systems_ , 32:15044–15054, 2019.
  * Chen et al. (2020) Chen, T., Zhang, W., Jingyang, Z., Chang, S., Liu, S., Amini, L., and Wang, Z.  Training stronger baselines for learning to optimize.  In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H. (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 7332–7343. Curran Associates, Inc., 2020.
  * Chen et al. (2022) Chen, T., Chen, X., Chen, W., Heaton, H., Liu, J., Wang, Z., and Yin, W.  Learning to optimize: A primer and a benchmark.  _Journal of Machine Learning Research_ , 23:1–59, 2022\.
  * Chen et al. (2017) Chen, Y., Hoffman, M. W., Colmenarejo, S. G., Denil, M., Lillicrap, T. P., Botvinick, M., and Freitas, N.  Learning to learn without gradient descent by gradient descent.  In _International Conference on Machine Learning_ , pp. 748–756. PMLR, 2017.
  * Cully et al. (2015) Cully, A., Clune, J., Tarapore, D., and Mouret, J.-B.  Robots that can adapt like animals.  _Nature_ , 521:503–507, 2015.
  * Das & Suganthan (2010) Das, S. and Suganthan, P. N.  Differential evolution: A survey of the state-of-the-art.  _IEEE transactions on Evolutionary Computation_ , 15(1):4–31, 2010.
  * Dosovitskiy et al. (2021) Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  In _International Conference on Learning Representations_ , 2021.
  * Elsken et al. (2019) Elsken, T., Metzen, J. H., and Hutter, F.  Neural architecture search: A survey.  _The Journal of Machine Learning Research_ , 20(1):1997–2017, 2019.
  * Flennerhag et al. (2021) Flennerhag, S., Schroecker, Y., Zahavy, T., van Hasselt, H., Silver, D., and Singh, S.  Bootstrapped meta-learning.  _arXiv preprint arXiv:2109.04504_ , 2021.
  * Golovin et al. (2017) Golovin, D., Solnik, B., Moitra, S., Kochanski, G., Karro, J., and Sculley, D.  Google vizier: A service for black-box optimization.  In _Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining_ , pp. 1487–1495, 2017.
  * Gomes et al. (2021) Gomes, H. S., Léger, B., and Gagné, C.  Meta learning black-box population-based optimizers.  _arXiv preprint arXiv:2103.03526_ , 2021.
  * Gärtner et al. (2022) Gärtner, E., Metz, L., Andriluka, M., Freeman, C. D., and Sminchisescu, C.  Transformer-based learned optimization, 2022.
  * Han et al. (2022) Han, K., Wang, Y., Chen, H., Chen, X., Guo, J., Liu, Z., Tang, Y., Xiao, A., Xu, C., Xu, Y., et al.  A survey on vision transformer.  _IEEE transactions on Pattern Analysis and Machine Intelligence_ , 2022.
  * Hansen & Ostermeier (2001) Hansen, N. and Ostermeier, A.  Completely derandomized self-adaptation in evolution strategies.  _Evolutionary Computation_ , 9(2):159–195, 2001\.
  * Howard et al. (2017) Howard, A., Zhu, M., Chen, B., Kalenichenko, D., Wang, W., Weyand, T., Andreetto, M., and Adam, H.  Mobilenets: Efficient convolutional neural networks for mobile vision applications.  _arXiv: Computer Vision and Pattern Recognition_ , 2017.
  * Hutter et al. (2019) Hutter, F., Kotthoff, L., and Vanschoren, J.  _Automated machine learning: methods, systems, challenges_.  Springer Nature, 2019.
  * Jazzbin (2020) Jazzbin.  Geatpy: The genetic and evolutionary algorithm toolbox with high performance in python, 2020.
  * Kandasamy et al. (2015) Kandasamy, K., Schneider, J., and Póczos, B.  High dimensional bayesian optimisation and bandits via additive models.  In _International conference on machine learning_ , pp. 295–304. PMLR, 2015.
  * Kandasamy et al. (2016) Kandasamy, K., Dasarathy, G., Oliva, J. B., Schneider, J., and Póczos, B.  Gaussian process bandit optimisation with multi-fidelity evaluations.  _Advances in neural information processing systems_ , 29, 2016.
  * Kandasamy et al. (2020) Kandasamy, K., Vysyaraju, K. R., Neiswanger, W., Paria, B., Collins, C. R., Schneider, J., Poczos, B., and Xing, E. P.  Tuning hyperparameters without grad students: Scalable and robust bayesian optimisation with dragonfly.  _Journal of Machine Learning Research_ , 21(81):1–27, 2020.
  * Khadka & Tumer (2018) Khadka, S. and Tumer, K.  Evolution-guided policy gradient in reinforcement learning.  In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.
  * Kingma & Ba (2014) Kingma, D. P. and Ba, J.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Lange et al. (2022) Lange, R. T., Schaul, T., Chen, Y., Zahavy, T., Dallibard, V., Lu, C., Singh, S., and Flennerhag, S.  Discovering evolution strategies via meta-black-box optimization.  _arXiv preprint arXiv:2211.11260_ , 2022.
  * Li et al. (2017) Li, C., Gupta, S., Rana, S., Nguyen, V., Venkatesh, S., and Shilton, A.  High dimensional bayesian optimization using dropout.  In _IJCAI’17_. AAAI Press, 2017.
  * Li & Malik (2016) Li, K. and Malik, J.  Learning to optimize.  _arXiv preprint arXiv:1606.01885_ , 2016.
  * Metz et al. (2019) Metz, L., Maheswaranathan, N., Nixon, J., Freeman, D., and Sohl-Dickstein, J.  Understanding and correcting pathologies in the training of learned optimizers.  In _International Conference on Machine Learning_ , pp. 4556–4565. PMLR, 2019.
  * Mitchell (1998) Mitchell, M.  _An introduction to genetic algorithms_.  MIT press, 1998.
  * Mouret & Maguire (2020) Mouret, J.-B. and Maguire, G.  Quality diversity for multi-task optimization.  _Proceedings of the 2020 Genetic and Evolutionary Computation Conference_ , 2020.
  * Mutny & Krause (2018) Mutny, M. and Krause, A.  Efficient high dimensional bayesian optimization with additivity and quadrature fourier features.  In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.
  * Salimans et al. (2017) Salimans, T., Ho, J., Chen, X., Sidor, S., and Sutskever, I.  Evolution strategies as a scalable alternative to reinforcement learning.  _arXiv preprint arXiv:1703.03864_ , 2017.
  * Shala et al. (2020) Shala, G., Biedenkapp, A., Awad, N., Adriaensen, S., Lindauer, M., and Hutter, F.  Learning step-size adaptation in cma-es.  In _International Conference on Parallel Problem Solving from Nature_ , pp. 691–706. Springer, 2020.
  * Snoek et al. (2012) Snoek, J., Larochelle, H., and Adams, R. P.  Practical bayesian optimization of machine learning algorithms.  In Pereira, F., Burges, C., Bottou, L., and Weinberger, K. (eds.), _Advances in Neural Information Processing Systems_ , volume 25. Curran Associates, Inc., 2012.
  * Sun et al. (2018) Sun, H., Chen, X., Shi, Q., Hong, M., Fu, X., and Sidiropoulos, N. D.  Learning to optimize: Training deep neural networks for interference management.  _IEEE Transactions on Signal Processing_ , 66(20):5438–5453, 2018.  doi: 10.1109/TSP.2018.2866382.
  * TV et al. (2020) TV, V., Malhotra, P., Narwariya, J., Vig, L., and Shroff, G.  Meta-learning for black-box optimization.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pp. 366–381. Springer, 2020.
  * Vassiliades & Mouret (2018) Vassiliades, V. and Mouret, J.-B.  Discovering the elite hypervolume by leveraging interspecies correlation.  _Proceedings of the Genetic and Evolutionary Computation Conference_ , 2018.
  * Vassiliades et al. (2018) Vassiliades, V., Chatzilygeroudis, K., and Mouret, J.-B.  Using centroidal voronoi tessellations to scale up the multidimensional archive of phenotypic elites algorithm.  _IEEE Transactions on Evolutionary Computation_ , 22:623–630, 2018.
  * Vicol et al. (2021) Vicol, P., Metz, L., and Sohl-Dickstein, J.  Unbiased gradient estimation in unrolled computation graphs with persistent evolution strategies.  In _International Conference on Machine Learning_ , pp. 10553–10563. PMLR, 2021.
  * Wang et al. (2021) Wang, C., Liu, J., Wu, K., and Wu, Z.  Solving multi-task optimization problems with adaptive knowledge transfer via anomaly detection.  _IEEE Transactions on Evolutionary Computation_ , 2021.
  * Wichrowska et al. (2017) Wichrowska, O., Maheswaranathan, N., Hoffman, M. W., Colmenarejo, S. G., Denil, M., Freitas, N., and Sohl-Dickstein, J.  Learned optimizers that scale and generalize.  In _International Conference on Machine Learning_ , pp. 3751–3760. PMLR, 2017.
  * Wierstra et al. (2014) Wierstra, D., Schaul, T., Glasmachers, T., Sun, Y., Peters, J., and Schmidhuber, J.  Natural evolution strategies.  _Journal of Machine Learning Research_ , 15(1):949–980, 2014.
  * Williams (1992) Williams, R. J.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine learning_ , 8(3):229–256, 1992.
  * Zhang et al. (2021) Zhang, J., Xu, C., Li, J., Chen, W., Wang, Y., Tai, Y., Chen, S., Wang, C., Huang, F., and Liu, Y.  Analogous to evolutionary algorithm: Designing a unified sequence model.  In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), _Advances in Neural Information Processing Systems_ , volume 34, pp. 26674–26688. Curran Associates, Inc., 2021.
  * Zhang et al. (2022) Zhang, J., Li, X., Wang, Y., Wang, C., Yang, Y., Liu, Y., and Tao, D.  Eatformer: Improving vision transformer inspired by evolutionary algorithm.  _arXiv preprint arXiv:2206.09325_ , 2022.
  * Zhang & Li (2007) Zhang, Q. and Li, H.  Moea/d: A multiobjective evolutionary algorithm based on decomposition.  _IEEE Transactions on Evolutionary Computation_ , 11(6):712–731, 2007.

##  Appendix A Vision Transformer

We mainly introduce the core part of Vision Transformer, such as the multi-
head self-attention layer (MSA), feed-forward network (FFN), layer
normalization (LN), and residual connection (RC).

##### MSA

MSA fuses several SA operations to handle the queries ($Q$), keys ($K$), and
values ($V$) that jointly attend to information from different representation
subspaces. MSA is formulated as follows:
$MultiHead(Q,K,V)=Concat(H_{1},H_{2},\cdots H_{h})W^{O}$. where $Concat$ means
concatenation operation. The head feature $H_{i}$ can be formulated as:

$\displaystyle H_{i}$ $\displaystyle=SA(QW_{i}^{Q},KW_{i}^{K},VW_{i}^{V})$
$\displaystyle=Softmax\left(QW_{i}^{Q}(KW_{i}^{K})^{T}/sqrt(d_{k})\right)VW_{i}^{V}=AVW_{i}^{V}$

where $W_{i}^{Q}\in R^{d_{m}\times d_{q}}$, $W_{i}^{K}\in R^{d_{m}\times
d_{k}}$, and $W_{i}^{V}\in R^{d_{m}\times d_{v}}$ are parameter matrices for
queries, keys, and values, respectively; $W^{O}\in R^{hd_{v}\times d_{m}}$
maps each head feature $H_{i}$ to the output. Moreover, $d_{m}$ is the input
dimension, while $d_{q}$, $d_{k}$, and $d_{v}$ are hidden dimensions of the
corresponding projection subspace; $h$ is the head number. $A\in R^{l\times
l}$ is the attention matrix of $h$th head, $l$ is the sequence length.

##### FFN

FFN employs two cascaded linear transformations with a ReLU activation to
handle $X$, which is shown as: $FFN(X)=max(0,XW_{1}+b_{1})W_{2}+b_{2}$, where
$W_{1}$ and $W_{2}$ are weights of two linear layers, and $b_{1}$ and $b_{2}$
are corresponding biases.

##### LN

LN is applied before each layer of MSA and FFN, and the output of LN is
calculated by $X+[MSA|FFN](LN(X))$.

##  Appendix B Preliminary EAs

The crossover, mutation, and selection operators form the basic framework of
EAs. EA starts with a randomly generated initial population. Then, genetic
operations such as crossover and mutation will be carried out. After the
fitness evaluation of all individuals in the population, a selection operation
is performed to identify fitter individuals to undergo reproduction to
generate offspring. Such an evolutionary process will be repeated until
specific predefined stopping criteria are satisfied.

##### Crossover

The crossover operator generates a new individual $\hat{X_{i}}$ by Eq. 12, and
$cr$ is the probability of the crossover operator.

$\hat{X}_{i,k}^{c}=\left\\{\begin{matrix}X_{j,k}&rand(0,1)<cr\\\
X_{i,k}&otherwise\end{matrix}\right.$ (12)

where $k\in[1,\cdots,d]$. This operator is commonly conducted on $n$
individuals. After an expression expansion, we re-formulate Eq. 12 as
$\sum_{i=1}^{n}X_{i}W_{i}^{c}$ (Zhang et al., 2021). $W_{i}^{c}$ is the
diagonal matrix. If $W_{i}^{c}$ is full of zeros, the $i$th individual has no
contribution.

##### Mutation

The mutation operator brings random changes into the population. Specifically,
an individual $X_{i}$ in the population goes through the mutation operator to
form the new individual $\hat{X}_{i}$, formulated as follows:

$\hat{X}_{i,k}^{m}=\left\\{\begin{matrix}rand(l_{k},u_{k})&rand(0,1)<mr\\\
\hat{X}_{i,k}^{c}&otherwise\end{matrix}\right.$ (13)

where $mr$ is the probability of mutation operator and $k\in[1,\cdots,d]$.
Similarly, 13 can be re-formulated as $X_{i}W_{i}^{m}$, where $W_{i}^{m}$ is
the diagonal matrix.

##### Selection

We introduce the binary tournament mating selection operator in Eq. 14. The
selection operator survives individuals of higher quality for the next
generation until the number of individuals is chosen.

$p_{i}=\left\\{\begin{matrix}1&f(X_{i})<f(X_{k})\\\
0&f(X_{i})>f(X_{k})\end{matrix}\right.,\ \ (X_{i},X_{k})\in X,$ (14)

where $p_{i}$ reflects the probability that $X_{i}$ is selected for the next
generation, and $(X_{i},X_{k})$ in Eq. 14 are randomly selected from the
population $X\cup\hat{X}^{m}$.

##  Appendix C Datasets

###  C.1 Synthetic Functions

Table 6: Training functions. ID | Functions | Range
---|---|---
F1 | $\sum_{i}{|w_{i}sin(x_{i}-b_{i})|}$ | $x\in[-10,10],b\in[-10,10]$
F2 | $\sum_{i}{|x_{i}-b_{i}|}$ | $x\in[-10,10],b\in[-10,10]$
F3 | $\sum_{i}{|(x_{i}-b_{i})+(x_{i+1}-b_{i+1})|}+\sum_{i}{|x_{i}-b_{i}|}$ | $x\in[-10,10],b\in[-10,10]$
Table 7: Testing Functions. ID |  Functions | Range
---|---|---
F4(Sphere) |  $\sum_{i}z_{i}^{2},z_{i}=x_{i}-b_{i}$ | $x\in[-100,100],b\in[-50,50]$
F5 |  $ax\\{|z_{i}|,1\leq i\leq D\\},z_{i}=x_{i}-b_{i}$ | $x\in[-100,100],b\in[-50,50]$
F6(Rosenbrock) |  $\sum\limits_{i=1}^{D-1}(100(z_{i}^{2}-z_{i+1})^{2}+{(z_{i}-1)}^{2}),z_{i}=x_{i}-b_{i}$ | $x\in[-100,100],b\in[-50,50]$
F7(Rastrigin) |  $\sum\limits_{i=1}^{D}(z_{i}^{2}-10\cos(2\pi z_{i})+10),z_{i}=x_{i}-b_{i}$ | $x\in[-5,5],b\in[-2.5,2.5]$
F8(Griewank) |  $\sum\limits_{i=1}^{D}{\frac{z_{i}^{2}}{4000}}-\prod_{i=1}^{D}\cos(\frac{z_{i}}{\sqrt{i}})+1,z_{i}=x_{i}-b_{i}$ | $x\in[-600,600],b\in[-300,300]$
F9(Ackley) |  $-20\exp(-0.2\sqrt{\frac{1}{D}\sum_{i=1}^{D}z_{i}^{2}})-\exp(\frac{1}{D}\sum_{i=1}^{D}\cos(2\pi z_{i}))+20+\exp(1),z_{i}=x_{i}-b_{i}$ | $x\in[-32,32],b\in[-16,16]$

###  C.2 Planner Mechanic Arm Problem

The optimization goal of this problem is to search for a set of lengths
$L=(L_{1},L_{2},\cdots,L_{n})$ and a set of angles
$\alpha=(\alpha_{1},\alpha_{2},\cdots,\alpha_{n})$ so that the distance
$f(L,\alpha,p)$ from the top of the mechanic arm to the target position $p$ is
the smallest, where $n$ represents the number of segments of the mechanic arm,
and $L_{i}\in(l_{i},u_{i})$ and $\alpha_{i}\in(-\Pi,\Pi)$ represent the length
and angle of the $i$th mechanic arm, respectively. Typically, $d$ is
calculated as follows:

$f(L,\alpha,p)=\sqrt{\left(\sum_{i=1}^{n}\cos(\alpha_{i})L_{i}-p_{x}\right)^{2}+\left(\sum_{i=1}^{n}\sin(\alpha_{i})L_{i}-p_{y}\right)^{2}}$
(15)

where $p_{x}$ and $p_{y}$ represent the x-coordinate and y-coordinate of the
target point, respectively.

Here, $n=100$, $l_{i}=0$ and $u_{i}=10$. We design two groups of experiments.
1) Simple case. We fixed the length of each mechanic arm as $l_{i}=10$ and
only searched for the optimal $\alpha$. 2) Complex case. We need to search for
$L$ and $\alpha$ simultaneously. We randomly selected 600 target points within
the range of $r\leq 1000$ to form a set $S$, where $r$ represents the distance
from the target point to the origin of the mechanic arm, as shown in Fig. 7.
During the training process of B2Opt, a sample point set $s$ is re-extracted
from $S$ for training every $T$ training cycle. In the testing process, we
extracted 128 target points ($S^{test}$) in the range of $r\leq 100$, $r\leq
300$, and $r\leq 1000$, respectively, for testing. The purpose of testing in
three different regions is to explore the generalization performance of B2Opt
further. We evaluate the generalization ability of the algorithm by
$\left(\sum_{s}^{S^{test}}f(L,\alpha,s)\right)/|S^{test}|$.

Figure 7: Planar Mechanical Arm.

DE, ES, and CMA-ES are tested when the maximum generations $Maxgen$ is set to
10, 50, and 100, respectively. We find that B2Opt outperforms all baselines.

Table 8: The results of planar mechanical arm on searching for different
angles with the fixed lengths. Maxgen=10
---
$r$ | DE | ES | CMA-ES | L2O-Swarm | B2Opt
100 | 2.96(1.63) | 11.2(4.70) | 236(46.8) | 40.4(3.89) | 0.30(0.18)
300 | 11.3(14.7) | 45.3(43.3) | 243(125) | 69.5(3.77) | 0.48(0.37)
1000 | 227(226) | 257(246) | 397(321) | 176(7.20) | 26.6(57.4)
Maxgen=50
$r$ | DE | ES | CMA-ES | L2O-Swarm | B2Opt
100 | 1.28(0.60) | 10.7(5.91) | 2.42(0.65) | 40.4(3.89) | 0.30(0.18)
300 | 1.54(0.89) | 42.0(41.0) | 4.06(6.54) | 69.5(3.77) | 0.48(0.37)
1000 | 110(152) | 193(235) | 103(182) | 176(7.20) | 26.6(57.4)
Maxgen=100
$r$ | DE | ES | CMA-ES | L2O-Swarm | B2Opt
100 | 1.20(0.64) | 10.6(5.58) | 1.36(0.35) | 40.4(3.89) | 0.30(0.18)
300 | 1.38(0.71) | 44.9(43.3) | 1.38(0.41) | 69.5(3.77) | 0.48(0.37)
1000 | 93.8(137) | 183(239) | 43.7(110) | 176(7.20) | 26.6(57.4)

###  C.3 Neural Network Training

Table 9 shows the neural network structure used for MNIST image classification
in this task. B2Opt and baselines are tasked with solving the parameters of
this neural network to maximize test accuracy. The network does not use any
bias, and the total number of parameters is 567. If the neural network is
directly optimized by the SGD algorithm, the network can achieve about 90$\%$
test accuracy, which proves that the network architecture is effective. Table
10 shows the lightweight convolution module used to replace the SAC module in
this task, where reflection padding 1 represents one reflection padding, and
similarly, reflection padding 2 represents two reflection padding. This
substitution is made because we expect B2Opt to perform more stably during
training for this task.

Table 9: The small-scale classification neural network for MNIST. layer id |  layer type |  padding |  stride |  kernel size
---|---|---|---|---
1 |  depth-wise convolution |  no padding | 1 |  1*5*5
2 |  point-wise convolution |  no padding | 1 |  3*1*1*1
3 |  ReLu |  None |  None |  None
4 |  max pooling |  no padding | 2 |  2*2
5 |  depth-wise convolution |  no padding | 1 |  3*5*5
6 |  point-wise convolution |  no padding | 1 |  16*3*1*1
7 |  ReLu |  None |  None |  None
8 |  max pooling |  no padding | 2 |  2*2
9 |  depth-wise convolution |  no padding | 1 |  16*4*4
10 |  point-wise convolution |  no padding | 1 |  10*16*1*1
11 |  softmax |  None |  None |  None
Table 10: The designed convolution module to replace SAC. layer id |  layer type |  padding |  stride |  kernel size
---|---|---|---|---
1 |  depth-wise convolution |  reflection padding 1 |  1 |  567*3*3
2 |  ReLu |  None |  None |  None
3 |  depth-wise convolution |  reflection padding 1 |  1 |  567*3*3
4 |  ReLu |  None |  None |  None
5 |  depth-wise convolution |  reflection padding 1 |  1 |  567*3*3
6 |  ReLu |  None |  None |  None
7 |  depth-wise convolution |  reflection padding 1 |  1 |  567*3*3

##  Appendix D Parameters

B2Opt. For example, 30 OBs with WS contains 30 OBs, and each OB consists of 1
SAC, 1 FM, and 1 RSSM. In 30 OBs with WS, these 30 OBs share parameters. 5 OBs
without WS has 5 OBs, and no parameters are shared among them. During the
training process, B2Opt is iterated for 1000 epochs. The initial learning rate
($lr$) was set to 0.01 and $lr$ = $lr\times 0.9$ each 100 cycles. The 2-norm
of the gradient is clipped so that it is not larger than 10. The bias of the
function is regenerated each epoch, and a new batch of random initial
populations is generated.

Baselines. The number of generations of the reference algorithms is set to
100. The population size of ES, DE, and CMA-ES is set to 100. For all cases,
we choose the optimal hyperparameters. To ensure validity, all experimental
results are averaged over 10 runs. All experiments were performed on a
Ubuntu20.04 PC with Intel(R) Core I7 (TM) I3-8100 CPU at 3.60GHz and NVIDIA
GeForce GTX 1060.

For ES and DE, the population size is set to 100, and the maximum number of
generations is set to 100, $\lambda=0.5$, $cr=0.5$, $F=0.5$, and the rest of
the parameters are the default ones set by geatpy. For CMA-ES, the maximum
number of generations is set to 100, $\sigma=0.1$, and the rest of the
parameters take pymoo’s default values.

##  Appendix E Effect of Learning rate on B2Opt

We train B2Opt on the F1-F3 function set with different learning rates, and
then test it on the F4-F9 function set. The experimental results are shown in
Table 11. 5 OBs without WS and 30 OBs with WS perform poorly when the learning
rate is 0.1, which may be because the learning rate is too large, which
affects the convergence of B2Opt during the training process. For 5 OBs
without WS, setting the learning rate to 0.01 achieves relatively best
performance. Using a learning rate of 0.0001 would be a good choice for 30 OBs
with WS and 3 OBs with WS. However, our experiments are coarse-grained. The
learning rate has a greater impact on B2Opt. Then using Auto-ML to search for
the optimal hyperparameter combination of the model is expected to achieve
better performance.

Table 11: Ablation study on learning rate. 5 OBs without WS
---
$lr$ | F4 | F5 | F6 | F7 | F8 |  F9
0.1 | 0.93(7.42) | 0.31(0.49) | 2.04e7(2.03e8) | 15.3(6.4) | 0.36(0.16) |  0.61(0.18)
0.01 | 0.01(0.003) | 0.05(0.02) | 9.57(0.22) | 1.62(0.60) | 0.03(0.01) | 0.06(0.03)
0.001 | 0.88(3.41) | 0.36(0.12) | 226(1750) | 6.18(2.66) | 0.56(0.16) | 1.36(0.36)
0.0001 | 0.06(0.03) | 0.13(0.03) | 13.6(2.11) | 0.83(0.50) | 0.17(0.04) |  0.28(0.10)
30 OBs with WS
0.1 | 1.64(1.19) | 0.85(1.59) | 493(3110) | 28.4(4.35) | 0.47(0.11) |  2.82(0.5)
0.01 | 0.05(0.30) | 0.09(0.03) | 39.2(240) | 1.05(1.40) | 0.01(0.06) | 0.28(0.07)
0.001 | 1.01e-3(0.001) | 0.02(0.01) | 9.03(0.18) | 0.03(0.02) | 0.003(0.001) | 0.03(0.01)
0.0001 | 1.50e-3(0.001) | 0.016(0.004) | 9.01(0.13) | 0.02(0.02) | 0.006(0.002) |  0.02(0.0.01)
3 OBs with WS
0.1 | 3.04(5.55) | 0.98(0.4) | 1150(7930) | 43.3(8.87) | 0.64(0.12) |  2.43(0.98)
0.01 | 29.9(47.7) | 2.68(1.30) | 6.24e4(4.87e5) | 40.4(8.52) | 1.05(0.06) | 4.45(0.85)
0.001 | 1.82(1.20) | 0.76(0.32) | 654(4780) | 7.00(7.11) | 0.79(0.13) | 1.91(0.53)
0.0001 | 0.39(0.21) | 0.33(0.07) | 46.8(79.4) | 2.22(2.41) | 0.66(0.09) |  0.59(0.19)

##  Appendix F Discussion

We train B2Opt on F1-F3 and make it successful on F4-F9.

From the expression of the functions, F1-F3 are low-fidelity surrogate
functions of the target functions F4-F9. F1-F3 contain the information of
objective functions (F4-F9). For example, F7 can be decomposed into
$\sum\limits_{i=1}^{D}z_{i}^{2}-\sum\limits_{i=1}^{D}10\cos(2\pi
z_{i})+\sum\limits_{i=1}^{D}10,z_{i}=x_{i}-b_{i}$. F2 is the low-fidelity
surrogate function of $\sum\limits_{i=1}^{D}z_{i}^{2}$. F1 is the low-fidelity
surrogate function of $\sum\limits_{i=1}^{D}10\cos(2\pi z_{i})$. For other
functions in F4-F9, we can find similar surrogate functions from F1-F3. B2Opt
can use this information to maximize the matching degree between the learned
optimization strategy and the objective function. However, F6 is less similar
to F1-F3 than F4, F5, and F7-F9. Herefore, although the performance of B2Opt
on F6 is better than that of the comparison algorithm, it still needs
improvement.

From the perspective of landscape features, F1-F3 include the following
features: unimodal, multimodal, separable, and non-separable. The landscape
features included in F4-F9 are as follows:

  * •

F4: Unimodal, Separable

  * •

F5: Unimodal, Separable

  * •

F6: Multimodal, Non-separable, Having a very narrow valley from local optimum
to global optimum

  * •

F7: Multimodal, Separable, Asymmetrical, Local optima’s number is huge

  * •

F8: Multi-modal, Non-separable, Rotated

  * •

F9: Multi-modal, Non-separable, Asymmetrical

The landscape features of F4 and F5 can be found in F1-F3. F6-F9 all have new
features. The interference strength of different characteristics to landscape
is arranged as follows: Having a very narrow valley from local optimum to
global optimum$>$Asymmetrical, Local optima’s number is
huge$>$Asymmetrical$>$Rotated. Therefore, B2Opt has the best generalization
performance on F4, F5, and F8, the second-best generalization performance on
F7 and F9, and the worst on F6.

(a)  (b)

(c)

(d)

(e)

Figure 8: Mutation strategy learned by B2Opt for (a) F4, (b) F6, (c) F7, (d)
F8, and (e) F9.