---
abstract: 'Recently, more and more works have proposed to drive evolutionary algorithms using machine learning models. Usually, the performance of such model based evolutionary algorithms is highly dependent on the training qualities of the adopted models. Since it usually requires a certain amount of data (i.e. the candidate solutions generated by the algorithms) for model training, the performance deteriorates rapidly with the increase of the problem scales, due to the curse of dimensionality. To address this issue, we propose a multi-objective evolutionary algorithm driven by the generative adversarial networks (GANs). At each generation of the proposed algorithm, the parent solutions are first classified into *real* and *fake* samples to train the GANs; then the offspring solutions are sampled by the trained GANs. Thanks to the powerful generative ability of the GANs, our proposed algorithm is capable of generating promising offspring solutions in high-dimensional decision space with limited training data. The proposed algorithm is tested on 10 benchmark problems with up to 200 decision variables. Experimental results on these test problems demonstrate the effectiveness of the proposed algorithm.'
author:
- |
    Cheng He, Shihua Huang, Ran Cheng *IEEE Member*,\
    Kay Chen Tan *IEEE Fellow*, and Yaochu Jin *IEEE Fellow* [^1] [^2] [^3] [^4]
bibliography:
- 'Reference.bib'
title: 'Evolutionary Multi-Objective Optimization Driven by Generative Adversarial Networks [(GANs)]{}'
---

[He : Evolutionary Multi-Objective Optimization Driven by Generative Adversarial Networks]{}

Multi-objective optimization, evolutionary algorithm, machine learning, deep learning, generative adversarial networks

Introduction {#sec:introduction}
============

Multi-objective optimization problems (MOPs) refer to the optimization problems with multiple conflicting objectives [@app-network], e.g., structure learning for deep neural networks [@liu2018structure], energy efficiency in building design [@app-build], and cognitive space communication [@ferreira2017multi]. The mathematical formulation of the MOPs is presented as follows [@deb2014multi]: $$\begin{aligned}
\label{eq:MOP}
\text{Minimize}& F(\mathbf{\mathbf{x}})=\!(f_1(\mathbf{x}),f_2(\mathbf{x}),\dots,f_M(\mathbf{x}))&\\
\text{subject to}&\mathbf{x}\in X, \nonumber\end{aligned}$$ where $X$ is the search space of decision variables, $M$ is the number of objectives, and $\mathbf{x}$$=$$(x_1,\dots,x_D)$ is the decision vector with $D$ denoting the number of decision variables [@tian2017effectiveness].

Different from the single-objective optimization problems with single global optima, there exist multiple optima that trade off between different conflicting objectives in an MOP [@PD]. In multi-objective optimization, the Pareto dominance relationship is usually adopted to distinguish the qualities of two different solutions [@ENS]. A solution $\mathbf{x}_A$ is said to Pareto dominate anther solution $\mathbf{x}_B$ ($\mathbf{x}_A\prec \mathbf{x}_B$) *iff* $$\left\{
\begin{array}{lr}
 \forall i\in 1,2,\dots,M, f_i(\mathbf{x}_A) \leq  f_i(\mathbf{x}_B)\\
 \exists j\in 1,2,\dots,M, f_j(\mathbf{x}_A) <  f_j(\mathbf{x}_B).
\end{array}
\right.$$ The collection of all the Pareto optimal solutions in the decision space is called the Pareto optimal set (PS), and the projection of the PS in the objective space is called the Pareto optimal front (PF). The goal of multi-objective optimization is to obtain a set of solutions for approximating the PF in terms of both convergence and diversity, where each solution should be close to the PF and the entire set should be evenly spread over the PF.

To solve MOPs, a variety of multi-objective evolutionary algorithms (MOEAs) have been proposed, which can be roughly classified into three categories [@RVEA]: the dominance-based algorithms (e.g. the elitist non-dominated sorting genetic algorithm (NSGA-II) [@NSGA-II] and the improved strength Pareto EA (SPEA2) [@SPEA2]); the decomposition-based MOEAs (e.g., the MOEA/D [@MOEAD] and MOEA/D using differential evolution (MOEA/D-DE) [@MOEADDE]); and the performance indicator-based algorithms (e.g., the $\mathcal{S}$-metric selection evolutionary multi-objective optimization algorithm (SMS-EMOA) [@SMSEMOA] and the indicator based EA (IBEA) [@IBEA]). There are also some MOEAs not falling into the three categories, such as the third generation differential algorithm (GDE3) [@GDE3], the memetic Pareto achieved evolution strategy (M-PAES) [@knowles2000m], and the two-archive based MOEA (Two-Arc)  [@praditwong2006new], etc.

![The general framework of MOEAs.[]{data-label="fig:EA"}](EAframework.eps){width="0.75\linewidth"}

In spite of the various technical details adopted in different MOEAs, most of them share a common framework as displayed in Fig. \[fig:EA\]. Each generation in the main loop of the MOEAs consists of three operations: offspring reproduction, fitness assignment, and environmental selection [@eiben2015evolutionary]. To be specific, the algorithms start from the population initialization; then the offspring reproduction operation will generate offspring solutions; afterwards, the generated offspring solutions are evaluated using the real objective functions; finally, the environmental selection will select some high-quality candidate solutions to survive as the population of the next generation. In conventional MOEAs, since the reproduction operations are usually based on stochastic mechanisms (e.g. crossover or mutation), the algorithms are unable to explicitly learn from the environments (i.e. the fitness landscapes).

For instance, conventional EAs use the mating selection strategy to select some promising parent solutions based on their fitness values, and then randomly crossover two of them to generate offspring solutions. For conventional crossover operators such as SBX [@PM], the offspring solutions will distribute around the vertices of a hyper-rectangle in parallel with the axes of decision variables, and its longest diagonal is the line segment of the two chosen parent solutions. If the PS of an MOP is not parallel with any axis of decision variable, especially when the PS has a 45$^\circ$ angle to all of the axes (e.g. IMF1 to IMF3 problems in [@IM-MOEA]), there is only a little chance that the offspring solutions will fall around the PS, resulting in the inefficiency of conventional crossover in offspring generation. An example of the SBX based offspring generation in a 2-D decision space is given in \[fig:rotate\], where the generated offspring solutions $\mathbf{s}_1, \mathbf{s}_2$ are far from their parents $\mathbf{p}_1,\mathbf{p}_2$ and the PS.

![An example of the genetic operator (SBX [@PM]) based offspring generation in a 2-D decision space, where $\mathbf{p}_1$ and $\mathbf{p}_2$ denote the parent solutions, and $\mathbf{s}_1$ and $\mathbf{s}_2$ denote the offspring solutions.[]{data-label="fig:rotate"}](rotate.eps){width="0.7\linewidth"}

To address the above issue, a number of recent works have been dedicated to designing EAs with learning ability, known as the model based evolutionary algorithms (MBEAs) [@MBEA; @zhang2011evolutionary]. The basic idea of MBEAs is to replace the heuristic operations or the objective functions with computationally efficient machine learning models, where the candidate solutions sampled from the population are used as training data. Generally, the models are used for the following three main purposes when adopted in MOEAs.

First, the models are used to approximate the real objective functions of the MOP during the fitness assignment process. MBEAs of this type are also known as the surrogate-assisted EAs [@Jin2000On], which use computationally cheap machine learning models to approximate the computationally expensive objective functions [@jin2009systems]. They aim to solve computationally expensive MOPs using a few real objective function evaluations as possible [@jin2011review; @SA2017]. A number of surrogate-assisted MOEAs were proposed in the past decades, e.g., the $S$-metric selection-based EA (SMS-EGO) [@SMS-EGO], the Pareto rank learning based MOEA [@seah2012pareto], and the MOEA/D with Gaussian process (GP) [@GP] (MOEA/D-EGO) [@MOEADEGO].

Second, the models are used to predict the dominance relationship [@ParetoSVM] or the ranking of candidate solutions [@lu2012classification; @bhatt2015novel] during the reproduction or environmental selection process. For example, in the classification based pre-selection MOEA (CPS-MOEA) [@CPSMOEA], a k-nearest neighbor (KNN) [@KNN] model is adopted to classify the candidate solutions into *positive* and *negative* classes. Then the *positive* candidate solutions are selected to survival [@zhang2018preselection]. Similarly, the classification based surrogate-assisted EA (CSEA) used a feedforward neural network [@svozil1997introduction] to predict the dominance classes of the candidate solutions in evolutionary multi-objective optimization [@CSEA].

Third, the models are used to generate promising candidate solutions during the offspring reproduction process. The MBEAs of this type mainly include the multi-objective estimation of distribution algorithms (MEDAs) [@EDA] as well as the inverse modeling based algorithms [@giagkiozis2014pareto]. [The MEDAs estimate the distribution of promising candidate solutions by training and sampling models in the decision space [@karshenas2013multiobjective]. Instead of generating offspring solutions via crossover or mutation from the parent solutions, the MEDAs explore the decision space of potential solutions by building and sampling explicit probabilistic models of the promising candidate solutions [@eda-initial; @sun2018improved].]{} Typical algorithms include the Bayesian multi-objective optimization algorithm (BMOA) [@BMOA], the naive mixture-based multi-objective iterated density estimation EA (MIDEA) [@MIDEA], the multi-objective Bayesian optimization algorithm (mBOA) [@mBOA], and the regularity model based MEDA (RM-MEDA) [@RM-MEDA], etc. For example, in the covariance matrix adaptation based MOEA/D (MOEA/D-CMA) [@MOEADCMA], the covariance matrix adaptation model [@loshchilov2013cma] is adopted for offspring reproduction. As for the inverse modeling based algorithms, they sample points in the objective space and then build inverse models to map them back to the decision space, e.g., the Pareto front estimation method [@giagkiozis2014pareto], the Pareto-adaptive $\epsilon$-dominance-based algorithm ($pa\lambda$-MyDE) [@hernandez2007pareto], the reference indicator-based MOEA (RIB-EMOA) [@martinez2014using], and the MOEA using GP based inverse modeling (IM-MOEA) [@IM-MOEA].

Despite that existing MBEAs have shown promising performance on a number of MOPs, their performance deteriorates rapidly as the number of decision variables increases. There are mainly two difficulties when applying existing MBEAs to multi-objective optimization. First, the requirement of training data for building and updating the machine learning models increases exponentially as the number of decision variables becomes larger, i.e., the MBEAs severely suffer from the curse of dimensionality  [@cd; @wang2015memetic]. Second, since there are multiple objectives involved in MOPs, it is computationally expensive to employ multiple models for sampling different objectives.

The generative adversarial networks (GANs) are generative models which have been successfully applied in many areas, e.g., image generation [@GAN], unsupervised representation learning [@radford2015unsupervised], and image super-resolution [@ledig2017photo]. They are capable of learning the regression distribution over the given/target data in an adversarial manner. [Meanwhile, the candidate solutions can be seen as samples by the distribution of the PS in evolutionary multi-objective optimization. Under mild conditions, a PS is an ($M$$-$1)-dimensional manifold, given that $M$ is the number of the objectives [@IM-MOEA]. Hence, there are two main motivations of using GANs for reproduction in evolutionary multi-objective optimization. First, it is intuitive to sample candidate solutions using GANs for the estimation of the distribution of the solution set in multi-objective optimization. Second, it is a natural character of GANs that the samples can be divided into fake and real ones, which is somehow consistent with the nature that the candidate solutions can be divided in multi-objective optimization (i.e. dominated and non-dominated solutions).]{} Furthermore, it is naturally suitable to drive evolutionary multi-objective optimization using GANs due to the following reasons. First, the pairwise generator and discriminator in GANs are capable of distinguishing and sampling promising candidate solutions, which is particularly useful in multi-objective optimization in terms of the Pareto dominance relationship. Second, thanks to the adversarial learning mechanism, the GANs are able to learn high-dimensional distributions efficiently with limited training data. By taking such advantages of GANs, we propose a GAN-based MOEA, termed GMOEA. To the best of our knowledge, it is the first time that the GANs are used for driving evolutionary multi-objective optimization. The main new contributions of this work can be summarized as follows:

1.  In contrast to conventional MBEAs which are merely dependent on given data (i.e. the candidate solutions), the GANs are able to reuse the data generated by themselves. To take such an advantage, in GMOEA, we propose a classification strategy to classify the candidate solutions into *real* and *fake* samples which are reused as training data. This is particularly meaningful for data enhancement in high-dimensional decision space.

2.  We sample a multivariate normal Gaussian distribution as the input of the GANs in the proposed GMOEA. Specifically, the distribution is learned from the promising candidate solutions which approximate the non-dominated front obtained at each generation.

The rest of this paper is organized as follows. In Section \[sec:related\], we briefly review the background of the GANs and other related works. The details of the proposed GMOEA are presented in Section \[sec:algorithm\]. Experimental settings and comparisons of GMOEA with the state-of-the-art MOEAs on the benchmark problems are presented in Section \[sec:result\]. Finally, conclusions are drawn in Section \[sec:conclusion\].

Background {#sec:related}
==========

Generative Adversarial Networks
-------------------------------

The generative adversarial networks have achieved considerable success as a framework of generative models [@GAN]. In general, the GANs produce a model distribution $P_{\hat{\mathbf{x}}}$ (i.e. the distribution of the fake/generated data) that mimics a target distribution $P_{\mathbf{x}}$ (i.e. the distribution of the real/given data).

A pair of GANs consist of a generator and a discriminator, where the generator maps Gaussian noise $\mathbf{z}$ ($\mathbf{z}\in P_{\mathbf{z}}$) to a model distribution $G(\mathbf{z})$ and the discriminator outputs probability $D(\mathbf{x})$ with $\mathbf{x} \in P_{\mathbf{x}}$ $\bigwedge$ $\mathbf{x} \notin P_{\hat{\mathbf{x}}}$. Generally speaking, the discriminator seeks to maximize probability $D(\mathbf{x})$ ($\mathbf{x}\in P_{\mathbf{x}}$) and minimize probability $D(G(\mathbf{z}))$, while the generator aims to generate more realistic samples to maximize probability $D(G(\mathbf{z}))$, trying to cheat the discriminator. To be more specific, those two networks are trained in an adversarial manner using the min-max value function $V$: $$\begin{aligned}
\label{eq:GAN}
    &\min\limits_{G} \max\limits_{D}V(D, G) =\\
    &\mathbb{E}_{\mathbf{x}\in{P_{\mathbf{x}}}}[logD(\mathbf{x})] + \mathbb{E}_{\mathbf{z}  \in {P_{\mathbf{z}}}}[log(1-D(G(\mathbf{z})))].\end{aligned}$$

Algorithm \[al:miniBP\] presents the detailed procedures of the training process. First, a number of $m$ samples are sampled from a Gaussian distribution and the given data (target distribution), respectively. Second, the discriminator is updated using the gradient descending method according to: $$\label{eq:dis2}
\bigtriangledown \theta_d \frac{1}{m} \sum_{i=1}^m[logD(\mathbf{x}_i) + log\left(1-D(G(\mathbf{z}_i))\right)].$$ Sequentially, the generator is updated using the gradient descending method according to: $$\label{eq:gen2}
\bigtriangledown \theta_g \frac{1}{m} \sum_{i=1}^m[log\left(1-D(G(\mathbf{z}_i))\right),$$ where $\mathbf{z}_i$ is a vector randomly sampled from a Gaussian distribution. The above procedures are repeated for a number of iterations [@kingma2014adam].

  \
$P_{\mathbf{x}}$ (given data), $P_{\mathbf{z}}$ (Gaussian noise), $m$ (batch size). /\*\*\*\*\* Update the discriminator \*\*\*\*/ Randomly sample $m$ samples $\{\mathbf{z}_1,\dots,\mathbf{z}_m\}$ from $P_{\mathbf{z}}$ Randomly sample $m$ samples $\{ \mathbf{x}_1,...,\mathbf{x}_m \}$ from $P_{\mathbf{x}}$ Update the discriminator according to (\[eq:dis2\]) /\*\*\*\*\*\* Update the generator \*\*\*\*\*\*/ Sample $m$ samples $\{\mathbf{z}_1,\dots,\mathbf{z}_m\}$ from $P_{\mathbf{z}}$ Update the generator according to (\[eq:gen2\])

Improved Strength Pareto Based Selection {#sec:spea2}
----------------------------------------

The improved strength Pareto based EA (SPEA2) [@SPEA2] is improved from its original version (SPEA) [@SPEA] by incorporating a tailored fitness assignment strategy, a density estimation technique, and an enhanced truncation method. In the tailored fitness assignment strategy, the dominance relationship between the pairwise candidate solutions are first detected, and then a strength value is assigned to each candidate solution. This value indicates the number of candidate solutions it dominates: $$\label{eq:dominance}
Str(\mathbf{x}_i)=|\{j| j\in P\wedge \mathbf{x}_i \prec \mathbf{x}_j \}|,$$ where $P$ is the population and $\mathbf{x}_i,\mathbf{x}_j$ are the candidate solutions in it. Besides, the raw fitness can be obtained as: $$\label{eq:rf}
Raw(\mathbf{x}_i)=\sum^N_{j\in P \wedge \mathbf{x}_j \prec \mathbf{x}_i}{Str(\mathbf{x}_j)}.$$ Moreover, the additional density information, termed $Den$, is used to discriminate the candidate solutions having identical raw fitness values. The density of a candidate solution is defined as: $$\label{eq:df}
Den(\mathbf{x}_i)=\frac{1}{\sigma^k_i+2},$$ where $k$ is the square root of the population size, and $\sigma^k_i$ denotes the $k$th nearest Euclidean distance from $\mathbf{x}_j$ to the candidate solutions in the population. Finally, the fitness can be calculated as $$\label{eq:fit}
Fit(\mathbf{x}_i)= Raw(\mathbf{x}_i)+Den(\mathbf{x}_i).$$

[The environmental selection of SPEA2 aims to select $N$ solutions from population $P$. It first selects all the candidate solutions with $Fit$$<$$1$ into set $A$. If the size of $A$ is smaller than $N$, $N$ solutions with the best $Fit$ are selected from $P$; otherwise, a truncation procedure is invoked to iteratively remove candidate solutions from $A$ until its size equals to $N$, where the candidate solution with the minimum Euclidean distance to the solutions in $A$ is removed each time.]{}

Since the density information is well used, the environmental selection in SPEA2 maintains a set of diverse candidate solutions. In this work, we adopt it for solution classification and environmental selection in our proposed GMOEA, where the details will be presented in Section \[sec:algorithm\].B.

The Proposed Algorithm {#sec:algorithm}
======================

The main scheme of the proposed GMOEA is presented in Algorithm \[al:framework\]. First, a population $P$ of size $N$ and a pair of GANs are randomly initialized, respectively. Then the candidate solutions in $P$ are classified into two different datasets with equal size (labeled as *fake* and *real*) and used to train the GANs. Next, a set $Q$ of $N$ offspring solutions is generated by the proposed hybrid reproduction strategy. Afterwards, $N$ candidate solutions are selected from the combination of $P$ and $Q$ by environmental selection. Finally, the solution classification, model training, offspring reproduction, and environmental selection are repeated until the termination criterion is satisfied. We will not enter the details of the environmental selection as it is similar to the solution classification, except that the environmental selection takes [$N$ solutions from the combination of $P$ and $Q$ as input (instead of selecting half of the solutions from $P$ only)]{} and only outputs the *real* solutions.

  \
$N$ (population size), $m$ (batch size for training the GAN) $P\leftarrow$ Initialize a population of size $N$ $GAN\leftarrow$ Initialize the GANs $\mathbf{X}\leftarrow \text{Solution Classification}$ [/\*Half of the solutions in $P$ are classified as *fake* samples\*/]{} $\mathbf{net} \leftarrow \text{Model Training}$ [/\*Use $\mathbf{X}$ to train the model\*/]{} $Q\leftarrow \text{Offspring Reproduction}$ [/\*Generate $N$ offspring solutions by the proposed reproduction method\*/]{} $P\leftarrow \text{Environmental Selection}$ [/\*Select $N$ solutions from the combination of $P$ and $Q$\*/]{} $P_0$

Solution Classification
-----------------------

Solution classification is used to divide the population into two different datasets (*real* and *fake*) for training the GANs. The *real* solutions are those better-converged and evenly distributed candidate solutions; by contrast, the *fake* ones are those of relatively poor qualities. We use the environmental selection strategy as introduced in Section \[sec:spea2\] to select half of the candidate solutions in the current population as *real* samples and the rest as *fake* ones.

[ $N$ (number of fake sample), $P$ (population).]{} $Fit\leftarrow$ Calculate the fitness values of candidate solutions in $P$ according to (\[eq:fit\]) $A\leftarrow \arg\limits_{\mathbf{x}_i\in P}{Fit(\mathbf{x}_i)<1}$ $\leftarrow$ Select $N$ candidate solutions with the minimal $Fit$ Delete $\arg\min\limits_{\mathbf{x}_j\in A}{\min{dis(\mathbf{x}_j, A\backslash \mathbf{x}_j)}}$ in $A$ $A\leftarrow$ *real* $P\backslash A\leftarrow$ *fake*

The pseudo codes of the solution classification are presented in Algorithm \[al:select\]. Generally, the purpose of solution classification is to select a set of high-quality candidate solutions in terms of convergence and diversity. The first term is intuitive, which aims to enhance the selection pressure for pushing the population towards the PF. The second term aims to satisfy the identity independent distribution assumption for better generalization of the GANs [@DL].

Model Training
--------------

The structures of the generator and discriminator adopted in this work are feedforward neural networks [@ANN] with two hidden layers and one hidden layer (the number of neurons in each layer is $D$), respectively. [Here we adopt this simple structure for the following two reasons. First, if a more powerful model is adopted, the amount of training data should be increased, resulting in the rapid increase in the computational cost in terms of both CPU time and the number of function evaluations. For the MOPs we try to solve in this work, the current model is good enough. Second, in the area of evolutionary optimization, similar simple networks have also been validated in other recent works, e.g.  [@CSEA; @zhang2018computational]. We surmise that it is due to fact that the problem scales in evolutionary optimization are much smaller than those in other applications such as image processing, such that a simple network will work properly.]{} The general scheme of the GANs is given in Fig. \[fig:GANs\], where the distributions of the *real* and *fake* datasets are denoted as $P_{\mathbf{r}}$ and $P_{\mathbf{f}}$, respectively. The activation functions of the output layers in these two networks are sigmoid functions to ensure that the output values vary in $[0, 1]$. Here, we propose a novel training method to take advantage of the labeled samples.

![The general scheme of model training in the proposed GMOEA.[]{data-label="fig:GANs"}](GANs.eps){width="\linewidth"}

First, the mean vector and covariance matrix of the *real* samples are calculated by: $$\label{eq:mean}
\begin{aligned}
\boldsymbol{\mu}&= \frac{\sum_{i=1}^{\lfloor N/2\rfloor}{\mathbf{r}_i}}{\lfloor N/2\rfloor},\\
\boldsymbol{\Sigma} &= \frac{\sum_{i=1}^{\lfloor N/2\rfloor}{(\mathbf{r}_i-\boldsymbol{\mu})(\mathbf{r}_i}-\boldsymbol{\mu})^\text{T}}{\lfloor N/2\rfloor-1},\\
\end{aligned}$$ where $\mathbf{r}_i$ is the $i$th member of the *real* dataset and $N$ is the population size. Then the GANs are trained for several iterations. At each iteration, the discriminator is updated using three different types of training data, i.e., the *real* samples, the *fake* samples, and the samples generated by the generator. The loss function for training the discriminator is given as follows: $$\label{eq:d1}
\begin{split}
&\max\limits_{D} V(D) = \mathbb{E}_{\mathbf{r}\in{P_{\mathbf{r}}}}[log(D(\mathbf{r}))] + \\
&\mathbb{E}_{\mathbf{f}  \in {P_{\mathbf{f}}}}[log(1-D(\mathbf{f}))]+ \mathbb{E}_{\mathbf{z}  \in {P_{\mathbf{z}}}}[log(1-D(G(\mathbf{z})))],
\end{split}$$ where $D(\mathbf{r})$, $D(\mathbf{r})$ and $D(G(\mathbf{z}))$ denote the outputs of the discriminator with the *real* sample, the *fake* sample and the sample generated by the generator being the inputs, respectively. The input of the generator is vector $\mathbf{z}$ sampled from a multivariate normal distribution. Finally, the generator is updated according to (\[eq:gen2\]) using the samples generated by itself. [Note that we have greedily used the imbalanced training set, aiming to enhance the convergence of GMOEA by pushing the target distribution away from the $\textit{fake}$ distribution. In other words, we prefer a model with higher accuracy in distinguishing the fake samples, such that there is a clear margin between the target distribution and the fake one.]{}

[ $\mathbf{X}$ (given data), $m$ (number of samplings).]{} $\boldsymbol{\mu}\leftarrow mean{(P_{\mathbf{r}})}$ /\*Mean vector of the data\*/ $\boldsymbol {\Sigma}\leftarrow cov(P_{\mathbf{r}})$ /\*Covariance matrix of the data\*/ Randomly sample $m$ samples $\{ \mathbf{x}_1,...,\mathbf{x}_m \}$ from $\mathbf{X}$ $\{\mathbf{z}_1,\dots,\mathbf{z}_m\}\leftarrow multivariate\_normal(m, \boldsymbol{\mu}, \boldsymbol {\Sigma})$ Update the discriminator according to (\[eq:d1\]) $\{\mathbf{z}_1,\dots,\mathbf{z}_m\}\leftarrow multivariate\_normal(m, \boldsymbol{\mu}, \boldsymbol {\Sigma})$ Update the generator according to (\[eq:gen2\])

The detailed procedure of the model training in GMOEA is given in Algorithm \[al:GAN\]. Here, we use the multivariate normal Gaussian distribution [@balakrishnan2014continuous], which is specified by its mean vector and covariance matrix, to generate training data. The mean vector represents the location where samples are most likely to be generated, and the covariance indicates the level to which two variables are correlated. This modification is inspired by the generative method in variational auto-encoder (VAE) [@VAE], which aims to generate data that approximates the given distribution. More importantly, this modification will potentially reduce the amount of data required for training the generator, since the distributions of $P_{\mathbf{z}}$ and $G(\mathbf{z})$ are similar.

Offspring Reproduction
----------------------

In this work, we adopt a hybrid reproduction strategy for offspring generation in GMOEA, which aims at balancing the exploitation and exploration of the proposed algorithm. The general idea of the proposed reproduction strategy is simple and efficient. At each generation, $N$ offspring solutions will be generated either by the GAN model or the genetic operators (i.e. crossover and mutation) with equal probability. [Since there is a risk of mode collapse in training a GAN model [@arjovsky2017wasserstein], the trained model may generate some poor solutions. To remedy this issue, we propose to mix the candidate solutions generated by both the GAN model and genetic operators as training data.]{}

To generate a candidate solution using the GANs, we first calculate the mean vector $\boldsymbol{\mu}$ and covariance matrix $\boldsymbol{\Sigma}$ of the *real* samples according to (\[eq:mean\]). Then, a $D$-dimensional vector $\mathbf {x}$ is sampled with each element being independently sampled from a continuous uniform distribution $U(0,1)$. Afterwards, a $D$-dimensional vector $\mathbf{y}$ satisfying the multivariate normal distribution is generated according to the following probability density function: $$\label{eq:PDF}
\mathbf{y} =\frac{\exp{\left(-{\frac {1}{2}}(\mathbf {x} - \boldsymbol{\mu})^{\mathrm {T} }{\boldsymbol{\Sigma}}^{-1}(\mathbf {x} - \boldsymbol{\mu}) \right)}}{\sqrt{(2\pi )^{D}|\boldsymbol{\Sigma}|}},$$ where $D$ denotes the dimensionality of the decision space. Finally, the output of the generator, $G(\mathbf{y})$, is restricted according to the lower and upper boundaries (i.e., $\mathbf{l}$ and $\mathbf{u}$) of the decision space as follows: $$\mathbf{x'}=G(\mathbf{y})(\mathbf{u}-\mathbf{l})+\mathbf{l},$$ where $\mathbf{x'}$ is the candidate solution generated by the GANs.

Experimental Study {#sec:result}
==================

To empirically examine the performance of the proposed GMOEA, we mainly conduct two different experiments to examine the properties of our proposed GMOEA. Among these experiments, six representative MOEAs are compared, namely, NSGA-II [@NSGA-II], MOEA/D-DE [@MOEADDE], MOEA/D-CMA [@MOEADCMA], IM-MOEA[@IM-MOEA], GDE3 [@GDE3], and SPEA2 [@SPEA2]. NSGA-II and SPEA2 are selected as they both adopt crossover and mutation operators for offspring generation. MOEA/D-DE and GDE3 are selected as they both adopt the differential evolution operator. MOEA/D-CMA is chosen as it is a representative MBEA, which uses the covariance matrix adaptation evolution strategy for multi-objective optimization. Besides, IM-MOEA is selected as it is an MBEA using the inverse models to generate offspring solutions for multi-objective optimization. The two experiments are summarized as follows:

-   The effectiveness of our proposed training method is examined according to the qualities of the offspring solutions generated by the GANs which are trained by different methods.

-   The general performance of our proposed GMOEA is compared with the six algorithms on ten IMF problems with up to 200 decision variables.

In the remainder of this section, we first present a brief introduction to the experimental settings of all the compared algorithms. Then the test problems and performance indicators are described. Afterwards, each algorithm is run for 20 times on each test problem independently. Then the Wilcoxon rank sum test  [@haynes2013wilcoxon] is used to compare the results obtained by the proposed GMOEA and the compared algorithms at a significance level of 0.05. Symbols ‘$+$’, ‘$-$’, and ‘$\approx$’ indicate the compared algorithm is significantly better than, significantly worse than, and statistically tied by GMOEA, respectively.

Experimental settings
---------------------

For fair comparisons, we adopt the recommended parameter settings for the compared algorithms that have achieved the best performance as reported in the literature. The six compared algorithms are implemented in PlatEMO using Matlab [@PlatEMO], and our proposed GMOEA is implemented in Pytorch using Python 3.6. All the algorithms are run on a PC with Intel Core i9 3.3 GHz processor, 32 GB of RAM, and 1070Ti GPU. *1) Reproduction Operators.* In this work, the simulated binary crossover (SBX) [@review-book] and the polynomial mutation (PM) [@PM] are adopted for offspring generation in NSGA-II and SPEA2. The distribution index of crossover is set to $n_c$$=$20 and the distribution index of mutation is set to $n_m$$=$20, as recommended in [@review-book]. The crossover probability $p_c$ is set to 1.0 and the mutation probability $p_m$ is set to $1/D$, where $D$ is the number of decision variables. In MOEA/D-DE, MOEA/D-CMA, and GDE3, the differential evolution (DE) operator [@DE] and PM are used for offspring generation. Meanwhile, the control parameters are set to $CR$$=$1, $F$$=$0.5, $p_m$$=$$1/D$, and $\eta$$=$20 as recommended in [@MOEADDE].

*2) Population Size.* The population size is set to 100 for test instances with two objectives and 105 for test instances with three objectives.

*(3) Specific Parameter Settings in Each Algorithm.* In MOEA/D-DE, the neighborhood size is set to 20, the probability of choosing parents locally is set to 0.9, and the maximum number of candidate solutions replaced by each offspring solution is set to 2. In MOEA/D-CMA, the number of groups is set to 5. As for IM-MOEA, the number of reference vectors is set to 10 and the size of random groups is set to 3.

[In our proposed GMOEA, the training parameter settings of the GANs are fixed, where the batch size is set to 32, the learning rates for our discriminator and generator are 0.0001 and 0.0004 respectively, the total number of iterations is set to 625 (i.e. $200\times 100/32$), and the Adam optimizer [@Adam] with $\beta_{1}$$=$0.5, $\beta_{2}$$=$0.999 is used to train our GAN. Note that the specified model in GMOEA is suitable for the benchmark investigated in this work, and its structure can be revised accordingly to fit different problems.]{}

*(4) Termination Condition.* The total number of FEs is adopted as the termination condition for all the test instances. The number of FEs is set to 5000 for test problems with 30 decision variables, 10000 for problems with 50 decision variables, 15000 for problems with 100 decision variables, and 30000 for problems with 200 decision variables.

Test Problems and Performance Indicators
----------------------------------------

In this work, we adapt ten problems selected from [@IM-MOEA], termed IMF1 to IMF10. Among these test problems, the number of objectives is three in IMF4, IMF8 and two in the rest ones.

We adopt two different performance indicators to assess the qualities of the obtained results. The first one is IGD [@IGD], which can assess both the convergence and distribution of the obtained solution set. Suppose that $P^*$ is a set of relatively evenly distributed reference points [@RPgeneration] in the PF and $\Omega$ is the set of the obtained non-dominated solutions. The IGD can be mathematically defined as follows. $$\label{eq:IGD}
\text{IGD}(P^*,\Omega)=\frac{\sum_{\mathbf{x}\in P^*}dis(\mathbf{x},\Omega)}{|P^*|},$$ where $dis(\mathbf{x},\Omega)$ is the minimum Euclidean distance between $\mathbf{x}$ and points in $\Omega$, and $|P^*|$ denotes the number of elements in $P^*$. The set of reference points required for calculating IGD values are relatively evenly selected from the PF of each test problem, and a set size closest to 10000 is used in this paper.

The second performance indicator is the hypervolume (HV) indicator [@HV]. Generally, hypervolume is favored because it captures in a single scalar both the closeness of the solutions to the optimal set and the spread of the solutions across objective space. Given a solution set $\Omega$, the HV value of $\Omega$ is defined as the area covered by $\Omega$ with respect to a set of predefined reference points $P^*$ in the objective space: $$\label{eq:HV}
\text{HV}(\Omega,P^*)=\lambda (H(\Omega,P^*)),$$ where $$H(\Omega,P^*)=\{z\in Z|\exists x\in P,\exists r\in P^*:f(x)\leq z \leq r\} \nonumber,$$ and $\lambda$ is the Lebesgue measure with $$\lambda (H(\Omega,P^*))=\int_{\mathbb{P^*}^n}1_{H(\Omega,P^*)}(z)dz\nonumber,$$ where $1_{H(\Omega,P^*)}$ is the characteristic function of $H(\Omega,P^*)$.

Note that, a smaller value of IGD will indicate better performance of the algorithm; in contrast, a greater value of HV will indicate better performance of the algorithm.

Effectiveness of the Model Training Method
------------------------------------------

To verify the effectiveness of our proposed model training method in GMOEA, we compare the offspring solutions generated by our modified GANs [(where the data augmentation via multivariate Gaussian model is adopted)]{} and the original GANs during the optimization of IMF4 and IMF7. We select IMF4 since its PS is complicated, and this problem is difficult for existing MOEAs to maintain diversity. IMF7 with 200 decision variables is tested to examine the effectiveness of our proposed training method in solving MOPs with high-dimensional decision variables. The numbers of FEs for these two problems are set to 5000 and 30000, respectively. Besides, each test instance is tested for 10 independent runs to obtain the statistic results. In each independent run, we sample the offspring solutions every 10 iterations for IMF4 and every 50 iterations for IMF7.

![image](GANModify_IM4.eps){width="\linewidth"}

Fig. \[fig:compare2\] presents the offspring solutions obtained on tri-objective IMF4. It can be observed that the original GANs tend to generate offspring solutions in a smaller region of the objective space (e.g., near the top center in Fig. \[fig:compare2\]). By contrast, our modified GANs have generated a set of widely spread offspring solutions with better convergence in most iterations. Fig. \[fig:compare3\] presents the offspring solutions obtained on IMF7 with 200 decision variables. It can be observed that our modified GANs have generated a set of better-converged and spreading offspring solutions; by contrast, the original GANs have generated offspring solutions mostly in the left corner.

![image](GANModify_IM7.eps){width="0.95\linewidth"}

It can be concluded from the three comparisons that our proposed training method is effective in diversity maintenance and convergence enhancement, even on MOPs with complicated PSs and up to 200 decision variables.

![The trajectories of generator and discriminator’s training losses of the original GAN (with multivariate Gaussian model disabled) and our modified GAN during the evolution, respectively.[]{data-label="fig:traject"}](trajectory_Ori.eps "fig:"){width="0.85\linewidth"} ![The trajectories of generator and discriminator’s training losses of the original GAN (with multivariate Gaussian model disabled) and our modified GAN during the evolution, respectively.[]{data-label="fig:traject"}](trajectory_Ours.eps "fig:"){width="0.85\linewidth"}

[ Furthermore, we display the trajectories of generator and discriminator’s training losses during the evolution in Fig. \[fig:traject\], where GMOEA is adopted to optimize IMF1 with 30 decision variables. In this figure, the horizontal denotes the epoch number from the first generation to the last generation of the evolution, where each epoch is averaged over 20 independent runs. It can be observed that the training loss of each discriminator rises while the training loss of each generator drops; nevertheless, the generator in our modified GAN trends to have a lower and more stable training loss than that of the original GAN. It can be attributed to the fact that the generator in our modified GAN generates more realistic samples that the discriminator cannot distinguish, and thus the generator is powerful in generating promising samples. This is consistent with the design principle of offspring generators (i.e. generating promising candidate solutions) in EAs. ]{}

General Performance
-------------------

The statistical results of the IGD and HV values achieved by the seven compared MOEAs on IMF1 to IMF10 are summarized in Table \[tab:IMMOEA-IGD\] and Table \[tab:IMMOEA-HV\], respectively. Our proposed GMOEA has performed the best on these ten problems, followed by IM-MOEA, NSGA-II, and MOEA/D-CMA. It can be concluded from these two tables that GMOEA shows an overall better performance compared with the model-free MOEAs, i.e., NSGA-II, MOEA/D-DE, GDE3, and SPEA2, on IMF problems. Meanwhile, GMOEA has shown a competitive performance in compared with MOEA/D-CMA and IM-MOEA on these IMF problems.

’$+$’, ’$-$’ and ’$\approx$’ indicate that the result is significantly better, significantly worse and statistically similar to that obtained by GMOEA, respectively.

\[tab:IMMOEA-IGD\]

’$+$’, ’$-$’ and ’$\approx$’ indicate that the result is significantly better, significantly worse and statistically similar to that obtained by GMOEA, respectively.

\[tab:IMMOEA-HV\]

The final non-dominated solutions achieved by the compared algorithms on bi-objective IMF3 and tri-objective IMF8 with 200 decision variables in the runs associated with the median IGD value are plotted in Fig. \[fig:IMF3\] and Fig. \[fig:IMF8\], respectively. It can be observed that GMOEA has achieved the best results on these problems, where the obtained non-dominated solutions are best converged.

![image](IMF3.eps){width="\linewidth"}

![image](IMF8.eps){width="\linewidth"}

The convergence profiles of the seven compared algorithms on nine IMF problems with 200 decision variables are given in Fig \[fig:IMF\_Convergence\]. It can be observed that GMOEA converges faster than the other six compared algorithms on most problems. The results have demonstrated the superiority of our proposed GMOEA over the six compared algorithms on MOPs with up to 200 decision variables in terms of convergence speed.

![The statistics of the runtime results achieved by the original IBEA and GMOEA.[]{data-label="fig:runtime"}](runtime.eps "fig:"){width="0.8\linewidth"}\

Conclusion {#sec:conclusion}
==========

In this work, we have proposed an MOEA driven by the GANs, termed GMOEA, for solving MOPs with up to 200 decision variables. Due to the learning and generative abilities of the GANs, GMOEA is effective in solving these problems.

The GANs in GMOEA are adopted for generating promising offspring solutions under the framework of MBEAs. In GMOEA, we first classify candidate solutions in the current population into two different datasets, where some high-quality candidate solutions are labeled as *real* samples and the rest ones are labeled as *fake* samples. Since the GANs mimic the distribution of target data, the distribution of *real* samples should consider two issues. The first issue is the diversity of training data, which ensures that the data could represent the general distribution of the expected solutions. The second issue is the convergence of training data, which ensures that the generated samples could satisfy the target of minimizing all the objectives.

A novel training method is proposed in GMOEA to take full advantage of the two datasets. During the training, both the *real* and *fake* datasets, as well as the data generated by the generator, are used to train the discriminator. It is highlighted that the proposed training method is demonstrated to be powerful and effective. Only a relatively small amount of training data is used for training the GANs (a total number of 100 samples for an MOP with 2 objectives and 105 samples for MOPs with 3 objectives). Besides, we also introduce an offspring reproduction strategy to further improve the performance of our proposed GMOEA. By hybridizing the classic stochastic reproduction and generating sampling based reproduction, the exploitation and exploration can be balanced.

To assess the performance of our proposed GMOEA, a number of empirical comparisons have been conducted on a set of MOPs with up to 200 decision variables. The general performance of our proposed GMOEA is compared with six representative MOEAs, namely, NSGA-II, MOEA/D-DE, MOEA/D-CMA, IM-MOEA, GDE3, and SPEA2. The statistical results demonstrate the superiority of GMOEA in solving MOPs with relatively high-dimensional decision variables.

This work demonstrates that the MOEA driven by the GAN is promising in solving MOPs. Therefore, it deserves further efforts to introduce more efficient generative models. Besides, the extension of our proposed GMOEA to MOPs with more than three objectives (many-objective optimization problems) is highly desirable. Moreover, its applications to real-world optimization problems are also meaningful.

[^1]: C. He, S. Huang, and R. Cheng are with the Shenzhen Key Laboratory of Computational Intelligence, University Key Laboratory of Evolving Intelligent Systems of Guangdong Province, Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China. E-mail: chenghehust@gmail.com, shihuahuang95@gmail.com, ranchengcn@gmail.com. (*Corresponding author: Ran Cheng*)

[^2]: K. C. Tan is with the Department of Computer Science, City University of Hong Kong, Hong Kong. E-mail: kaytan@cityu.edu.hk.

[^3]: Y. Jin is with the Department of Computer Science, University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom. Email: yaochu.jin@surrey.ac.uk.

[^4]: This work was supported in part by the National Key R$\&$D Program of China grant (No. 2017YFC0804002), in part by the National Natural Science Foundation of China (No. 61903178 and 61906081) , in part by the Program for Guangdong Introducing Innovative and Entrepreneurial Teams grant (No. 2017ZT07X386), in part by the Shenzhen Peacock Plan grant (No. KQTD2016112514355531), in part by the Science and Technology Innovation Committee Foundation of Shenzhen grant (No. ZDSYS201703031748284), and in part by the Program for University Key Laboratory of Guangdong Province grant (No. 2017KSYS008).
