Generative Evolutionary Strategy for Black-box Optimization

Local Generative Surrogate Optimization (L-GSO) is a type of GSN that approaches the problem using a local surrogate network and a local gradient. To better understand this, let’s think of a situation where we need to optimize a target function $F(x)$ within an optimization space $x\in X$ and find the best point $x$. If we identify $x_{0}$ as the optimal point at some stage, L-GSO samples the local space around $x_{0}$ and calculates pairs $[x^{\prime},F(x^{\prime})]$, where $x^{\prime}=x_{0}+\epsilon$ and $|\epsilon|<<1$. It is important that $\epsilon$ is sufficiently small so that we only sample within a space close to $x_{0}$. From this data, L-GSO trains a surrogate network, $C$, which acts as a local surrogate model with information around $x_{0}$ and can generate a local gradient. After training the surrogate network, the generator network $G$ is trained using $C$. Let $p=C(G(z))$, where $x=G(z)$ and $z$ is an input seed. $G$ is trained with a loss function $\mp p$ that either increases or decreases the prediction $p$. Finally, the trained generator suggests a search point $x$, and the iterative process continues.

This way, $G$ is trained to be a generator that produces optimal (or near-optimal) points $x$, assuming that $C$ simulates the local distribution accurately enough. Meanwhile, as the data points are focused within a localized area, the surrogate network can benefit from a stable training data region, which enables accurate gradient prediction. Another advantage is that the data information is retained in the surrogate network $C$, allowing lesser amount of data generation required when predicting the local gradient at new points.

Although the approach of utilizing GSNs in L-GSO is quite innovative, it does have some limitations. The primary constraint is that it is only applicable to single-objective function problems. The optimal point $x_{0}$ mentioned earlier is just a single point. However, if the optimal points (the Pareto front) consist of multiple points, the distance between these optimal points and the data sampling space (which the surrogate network must learn) will no longer be local. This undermines the fundamental premise of L-GSO. Hence, the challenge is that the optimal point of an $n$-objective function features a Pareto front in $n-1$ dimensions. For example, in a two-objective function, the Pareto front forms a line, typically containing infinitely many non-dominated points that are distant from one another. Consequently, the locality of L-GSO becomes unsuitable for $n$-objective problems that require non-dominated sorting [58, 59].

The second problem with this algorithm is that its performance may be significantly influenced by the interaction between the hyperparameters and the test function. Specifically, the combination of the sampling hypercube size $\epsilon$ and the test function characteristics can significantly impact the algorithm’s optimization performance. For instance, if the test function is convex, estimating the local gradient with any $\epsilon$ is generally not a problem; however, this can often be challenging for non-convex functions. Around the local optimum, if $\epsilon$ is smaller than the size of the localized well, the algorithm can hardly escape the local optimum. Conversely, if $\epsilon$ is too large, the local gradient cannot be accurately estimated. The interplay among the type of test function, the location of the local optimum point, and $\epsilon$ is substantial, making it difficult to determine the appropriate value of $\epsilon$ for the test function in advance; thus posing a disadvantage for black-box problems.

Conclusively, L-GSO effectively handles high-dimensional spaces using surrogate networks and improves the stability of surrogate network training through locality. However, it is clear that non-dominated sorting for multi-objective problems is not feasible, and the relationship between the hyperparameter $\epsilon$ and the test function might be too strong.

The Evolutionary Generative Adversarial Network (EGAN) integrates ES to improve GAN performance. Although this method does not focus on black-box optimization, its algorithmic structure is similar to GEO.

Usually, GANs are trained with one generator and one discriminator (critic) network, which alternate. In EGAN, a scenario is considered where there is only one discriminator network; however, with multiple generator networks. The main idea of this study is to rank the generator networks using an evolutionary strategy and keep only the suitable networks. By using the prediction of discriminator $C$ as the fitness score, the generators $G$ that can increase $C(G(z))$ at each iteration survive. This process incorporates ES into the GAN, and it has been established that the introduction of ES reduces mode collapsing, which is a common issue in GANs.

Although EGAN is not directly related to optimization problems, we can gain valuable insights into improving GSN based on EGAN’s concepts. Because the generator and surrogate network structure in GSN is similar to the generator and discriminator network structure in GAN, we can adopt EGAN’s strategy in GSN. This forms the core basis of our research, GEO. However, the main difference between the two algorithms is that GAN operates without evolution, whereas GSN typically diverges and fails when it consists only of a single generator and a surrogate network. In the Methods section, we discuss how the working mechanism of GSN can change owing to the introduction of ES.

Global Optimization of dielectric metasurfaces using a physics-driven neural network (GLOnet) [23, 24, 25, 26, 27] is a study to optimize devices in electromagnetic systems. The study investigates the optimization of device structures within a specific electromagnetic system using neural network techniques.

In this study, $x$ serves as device design parameters, and the goal is to find the optimal value of $x$ that maximizes the objective value $F(x)$ of the simulator $F$. The algorithm finds $x=G(z)$, where $z$ is the input seed, and the generator $G$ is trained by backpropagating the gradient from the simulator. Technically, this is not a black-box optimization, as it receives the analytic gradient information directly from the simulator. Therefore, a surrogate network is not required.

An important implication of the GLOnet study is the necessity for a deep generator network. One might assume that since we have a gradient, we can optimize x through direct gradient descent. However, this study demonstrates that employing a generator network is more advantageous than updating x directly without a generator. In fact, this also holds true for GSN studies. The importance of deep generators is not emphasized in many GSN studies; however, it can be argued that it is omitted because they are inspired by GANs, and the significance of a deep generator is implicitly understood.

First, let’s explain why surrogate training in GSNs is particularly unstable. The structure of GSNs is almost identical to GANs, hence it might seem that, just as GANs are highly successful in the fake data generation task, GSNs should also be successful. However, in practice, when we run a GSN model with just one generator network and one surrogate network, without employing any special tricks, we encounter a situation where they diverge to infinity almost immediately after starting, in most test cases. This is neither the desired result nor can we consider it being optimized. This is why GSN studies incorporate some kind of special trick.

In addition, the crucial difference between GANs and GSNs lies in the presence or absence of true data. GANs rely on fixed true data; for instance, if the task is to generate images of human faces, a large dataset of real human face photos is required. Discriminator networks possess a significant amount of fixed true data initially and learn additional fake data during training, providing a stable training region. Conversely, GSNs, which are used for black-box optimization, do not have true data. Consequently, we must start from scratch, with no prior information. The first Pareto front points that have been explored, and the surrounding points, might correspond to true data. However, the amount of data near the first Pareto front is insufficient because the first Pareto front in the objective problem is constantly changing and data is collected on-the-fly. To draw an analogy, the GAN represents a situation in which the target is anchored by true data, whereas the GSN represents a situation where the target is floating without an anchor.

This is why the critic network (discriminator network) in GANs and the critic network (surrogate network) in GSNs have similar learning structures; however, they yield completely different results. To summarize the erroneous learning process of GSN’s critic network, we describe its workings as follows:

1. 1.

   The critic network begins training with insufficient data.

2. 2.

   The training data has minimal information about the Pareto front, which prevents the network from learning anything meaningful.

3. 3.

   As the critic network is trained improperly, the gradient it provides fails to guide $x$ towards the Pareto front.

4. 4.

   The generator, using incorrect gradient information, produces a point unrelated to the Pareto front when suggesting the next $x$.

5. 5.

   The critic network is then retrained using the poorly generated $x$.

This leads to a vicious cycle between the generator and the critic network, a situation that does not occur in GANs owing to the presence of true data.

One solution to this problem is to create a data region that corresponds to the true data region found in GANs. In optimization problems, the most crucial information is concentrated at the first Pareto front. Hence, it is necessary to sample the area around the first Pareto front and use it as training data for the critic network. L-GSO addresses this issue by intensively sampling only the local region around $x_{0}$, representing the zero-dimensional first Pareto front, and supplying that data to the critic network. However, as mentioned in the related works section, the local sampling method cannot be applied to $n$-objective functions with $n>1$. Consequently, we need an approach that is similar to the local sampling method and can also accommodate the multi-objective target functions.

Hence, we suggest using ES. The idea is to keep generators $G$ that produce $x$ values close to the first Pareto front and discard those that are farther away. By selecting $G$ through a non-dominated sorting process, we ensure that only $[x,G]$ pairs generating search points near the Pareto front survive at each iteration. Even if the critic network initially learns the incorrect region, as iterations progress, the probability of generating a search point $x$ near the Pareto front increases. Eventually, the critic network will have a stable training data region near the Pareto front; thus breaking the vicious cycle and achieving our desired outcome: stability in critic network training for multi-objective targets.

GEO was developed with the notion that ES complements GSN; however, this idea can also be reversed. As previously mentioned, from the ES perspective, the algorithm consists of mutation and (non-dominated) sorting based on fitness scores, with generator networks being the targets of mutation. In this case, mutation occurs through backpropagation from the critic network, which can be more efficient because the neural network has learned information about the Pareto front. Therefore, from the ES perspective, GSN serves as an auxiliary means to enhance the mutation efficiency of ES.

Conclusively, GEO functions in such a way that GSN complements ES, and ES complements GSN. By doing so, it integrates the strengths of both GSN and ES while mitigating their weaknesses, particularly effectively addressing the instability problem of GSN. Moreover, since both GSN and ES are $\mathcal{O}(N)$ algorithms, GEO is able to maintain $\mathcal{O}(N)$ complexity.

However, it is important to emphasize that both GSN and ES are exploitation-oriented algorithms in terms of exploit and explore strategies. Bayesian optimization, another significant branch of black-box optimization, offers a powerful feature by estimating uncertainty and incorporating it into the next step search. From that perspective, both ES and GSN lack the uncertainty estimation aspect, and even with the addition of supplementary exploration strategies, they may not reach the same level of robust exploration performance as the Bayesian optimization. Consequently, GEO, similar to GSN and ES, cannot guarantee global optimization even though the number of function calls $N$ approaches infinity. Nevertheless, GSN, ES, and GEO are free from the non-linear complexity problem that Bayesian optimization encounters. Hence, it is clear that Bayesian optimization and GEO have distinctly different optimization goals and conditions in which they are best applied.

The following are the operation sequences for GEO in the context of $n$-objective black-box optimization $F=(f_{1},f_{2},...,f_{i},...,f_{n})$. $G$: generator network, $C_{i}$: $i_{th}$ Critic network, $z$: input seed of generator, $x$: search point of search space $X$.

Pretraining steps:

1. 1.

   Prepare a set of generators and $n$ critic networks. Each critic network predicts one corresponding objective. The networks have not been trained yet.

2. 2.

   Prepare the $[x,F(x)]$ training set for initializing the critic network. The Latin Hypercube method[52] is generally recommended as the initial sampling method for search point $x$. However, the generator network can also be initialized using weight initialization techniques for neural networks, such as Xavier or He initialization.

3. 3.

   Store the initialized $[x,F(x)]$ in buffer memory, which has a maximum length.

4. 4.

   Pretrain the critic network using the data stored in buffer memory. For example, $C_{i}$ is trained with $[x,f_{i}(x)]$ pairs.

Main iteration steps:

1. 1.

   Randomly sample a few generators from the generator set (evolution pool).

2. 2.

   Train the generators through backpropagation with the critic network $C_{i}$. The loss function is $-C_{i}(G(z))$ for the maximization problem. The training of the generators also serves as mutation from the ES perspective. Because there are $n$ critic networks, the single-objective mutation is repeated $n$ times; thus implying that for each sampled $G$, we make $n$ mutants.

3. 3.

   Generate new $x^{\prime}=G^{\prime}(z)$ points from the mutated generators $G^{\prime}$.

4. 4.

   Evaluate $F(x^{\prime})$ from the new $x^{\prime}$ and store the pair $[x^{\prime},F(x^{\prime})]$ in the buffer memory. If the buffer memory’s maximum length is exceeded, delete the previously stored data.

5. 5.

   Train the critic networks using the data in the buffer memory.

6. 6.

   Save the $[G^{\prime},F(x^{\prime})]$ pair back to the generator set. $F(x^{\prime})$ corresponds to the multi-objective fitness score.

7. 7.

   The number of generators in the evolution pool has increased with the newly stored mutated $G^{\prime}$. Perform a non-dominated sort on them based on their fitness scores. Predetermine a maximum number for the generator set and retain only the generators with high fitness (top Pareto-front data).

8. 8.

   Repeat the iteration.

The configuration of the critic network might have been designed to allow a single critic network to predict multiple target objectives. However, we separated the critic network independently for each objective to minimize correlation, under the assumption that it is more common for black-box problems to have independent objective targets. By dividing the critic network into $n$ parts and applying backpropagation separately, it behaves as if the single-objective problem is being run $n$ times independently. Nevertheless, it can be used for multi-objective optimization because the results are combined and ranked using non-dominated sorting.

In addition, if the target function is stochastic, age evolution can be incorporated into the non-dominated sorting step. In age evolution, we can store the time order information of generators together and remove a few of the oldest generators before performing non-dominated sorting.

The provided explanation outlines the basic algorithmic structure of GEO. As described, the operation of GEO is achieved when both the ES-direction cycle and the GSN-direction cycle work together simultaneously.