# A Novel Genetic Algorithm with Hierarchical Evaluation Strategy for
Hyperparameter Optimisation of Graph Neural Networks

Yingfang Yuan2, Wenjun Wang2, George M. Coghill, Wei Pang1 Y.F. Yuan, W.J.
Wang and W. Pang are with the School of Mathematical and Computer Sciences,
Heriot-Watt University, Edinburgh, EH14 4AS, UK.G.M. Goghill is with the
School of Natural and Computer Sciences, University of Aberdeen, Aberdeen,
AB24 3UE, UK.Manuscript received XX XX, 2020; revised XX, XX, 20XX.2 Equal
contribution (co-first authors)1 Corresponding author: Wei Pang (email:
<EMAIL_ADDRESS>
###### Abstract

Graph representation of structured data can facilitate the extraction of
stereoscopic features, and it has demonstrated excellent ability when working
with deep learning systems, the so-called Graph Neural Networks (GNNs).
Choosing a promising architecture for constructing GNNs can be transferred to
a hyperparameter optimisation problem, a very challenging task due to the size
of the underlying search space and high computational cost for evaluating
candidate GNNs. To address this issue, this research presents a novel genetic
algorithm with a hierarchical evaluation strategy (HESGA), which combines the
full evaluation of GNNs with a fast evaluation approach. By using full
evaluation, a GNN is represented by a set of hyperparameter values and trained
on a specified dataset, and root mean square error (RMSE) will be used to
measure the quality of the GNN represented by the set of hyperparameter values
(for regression problems). While in the proposed fast evaluation process, the
training will be interrupted at an early stage, the difference of RMSE values
between the starting and interrupted epochs will be used as a fast score,
which implies the potential of the GNN being considered. To coordinate both
types of evaluations, the proposed hierarchical strategy uses the fast
evaluation in a lower level for recommending candidates to a higher level,
where the full evaluation will act as a final assessor to maintain a group of
elite individuals. To validate the effectiveness of HESGA, we apply it to
optimise two types of deep graph neural networks. The experimental results on
three benchmark datasets demonstrate its advantages compared to Bayesian
hyperparameter optimization.

###### Index Terms:

Graph Neural Network, Hyperparameter Optimization, Genetic Algorithm,
Hierarchical Evaluation Strategy, Difference of RMSEs.

##  I Introduction

Graph can be used to represent features of structured data. Deep learning
equipped with graph models, the so-called graph deep learning approaches, have
recently been used to predict molecular and polymer proprieties [1], and
tremendous success has been achieved in comparison to the traditional
approaches based on semantic SMILES strings [2] only. Among many types of
graph deep learning systems, Graph Convolutional Neural Networks (GNNs)
succeed in deep learning with promising performance and scalability [3].
Generally, a GNN models a set of objects (nodes) as well as their connections
(edges) in the form of topological graphs using stereoscopic features [4],
which is distinct from traditional vector-based machine learning systems.
Thus, GNNs are good at solving graph-related problems, and it can deal with
complex real-world systems in an end-to-end manner [5]. Technically, GNNs can
operate directly on graphs, while in molecular and polymer property prediction
problems, there is a common representation transfer module which bridges the
gap between the SMILES strings and graphs [6]. Fed by the graphs, GNNs can
learn to approximate the desirable properties of molecules or polymers on
various user-specific scenarios or applications.

As with most of the machine learning approaches, GNNs also need a set of
hyperparameters to shape their architectures, and examples of hyperparameters
include the numbers of convolutional layers, filters (kernels), full connected
nodes and training epochs. These hyperparameters will affect the training and
learning performance, i.e., a good configuration of hyperparameters for a GNN
will lead to effective training and accurate predictions, while a poor
configuration will generate otherwise results. Therefore, hyperparameter
optimisation (HPO) for GNN architectures is vital. Recently, Nunes et.al. [7]
compared reinforcement learning based and evolutionary algorithms based
methods for optimising GNN architectures. Moreover, GraphNAS [8] employs a
recurrent network trained with the policy gradient to explore network
architecture. However, in the context of GNN, the HPO research is still
growing [7].

On the other hand, compared with traditional machine learning methods, most of
deep learning models including GNNs have more sophisticated architectures and
are more time-consuming to train. This means HPO for GNN is indeed a very
expensive task: for each trial regarding a configuration of hyperparameters,
it has to complete the full training process to evaluate the quality of this
configuration. Existing HPO methods include grid search [9], random search
[10], Gaussian and Bayesian methods [11], as well as evolutionary approaches
[12] [13] [14], however most of these suffer from the expensive computational
cost.

To address the expensive HPO problem, in this research we aim to develop a
novel genetic algorithm (GA) with two evaluation methods: full and fast
evaluations. Regarding the full evaluation, GNN will be trained on a specified
dataset given a set of hyperparameter values, and root mean square error
(RMSE) on the validation set will be considered as a full score of this
solution. The proposed fast evaluation approach employs the difference of
RMSEs between the early stage and the beginning of training as the fitness
score to approximate the performance of a GNN being fully trained. A
hierarchical evaluation strategy named HES is also proposed for coordinating
these two evaluation methods, in which the fast evaluation operates in a lower
level for recommending candidates, thereafter the full evaluation will act as
a final assessor to maintain a group of elite individuals. Finally, the above
procedures and operations constitute the proposed algorithm termed HESGA.

To assess the effectiveness of the proposed HESGA, we carried out experiments
on three public molecule datasets: EOSL [15], FreeSolv [16], and Lipophilicity
[17], which involve the predictions of three properties: molecular solubility,
hydration free energy, and lipophilicity, respectively. Each dataset has all
the molecules represented by SMILES strings, which can be used to construct
molecular graphs. These constructed graphs were then used as input to GNNs for
the predictive tasks. In this research, we apply HESGA to optimise the
hyperparameters of two types of Graph Neural Networks: Graph Convolution (GC)
[6] and Message Passing Neural Network (MPNN) [18], to improve their learning
performance in terms of RMSE. The promising results compared with benchmarks
[1] show that HESGA has advantages in both achieving good/better solutions
compared to the Bayesian based HPO and require less computational cost than
the original genetic algorithm.

The main contributions of this research are as follows:

  1. 1.

We proposed a fast approach for evaluating GNNs by using the difference of
RMSEs between the early training stage and the very beginning of the training.

  2. 2.

We proposed a novel hierarchical evaluation strategy used together with GA
(HESGA) for hyperparameter optimisation.

  3. 3.

We conducted systematic experiments on three benchmark datasets (ESOL,
FreeSolv, and Lipophilicity) to assess the performance of HESGA on GC and MPNN
models as opposed to the Bayesian method.

The rest of this paper is organized as follows. Section II introduces relevant
work and methods for HPO. In Section III, the details of HESGA is presented.
The experiments are reported and the results are analysed in Section IV. Then
regarding more interesting topics we have a further discussion in Section V.
Finally, Section VI concludes the paper and explores some directions in future
work.

##  II Background and Relevant Methods

###  II-A Grid Search and Random Search

Grid search and random search are two most commonly used approaches for HPO.
Grid-based method initializes the hyperparameter space using grid layout and
tests each point (representing a configuration of hyperparameters) in the
grid. As grid search is performed in an exhaustive manner to evaluate all grid
points, its cost is determined by the resolution of the pre-specified grid
layout. In contrast, random search is supported by a series of defined
probabilistic distributions (e.g. uniform distribution), which suggest a
number of points in trials. It is noted that random search is in general more
practical and efficient than grid search for HPO of neural networks given the
same computational budget [19].

###  II-B Bayesian and Gaussian Approaches

Bayesian optimization can be used to suggest the probabilistic distributions
mentioned in random search. It is assumed that the performance of the learning
model is correlated to its hyperparameters. Thus, we give a higher probability
to the set of hyperparameter values with better performance [11], which means
that it will be allocated with more chances to be sampled further. After
sufficient iterations of calculations, a probability distribution function
similar to the maximum likelihood function can be learned by Bayesian
approaches [20], random forest [21] and other surrogate models. As a result,
the computational cost for model validation will be saved in this way.
Gaussian process is suitable for approximating the distribution of evaluation
results because of their flexibility and traceability [22]. The combination of
Bayesian optimisation with Gaussian process outperforms human expert-level
optimization in many problems [11]. For example, in [23], FABOLAS is poposed
to accelerate Bayesian optimisation of hyperparameters on large datasets, and
this method benefits from sub-sampling. Another successful case is a method
which combines Bayesian optimisation and Hyperband, and it possesses the
features of simplicity, efficiency, robustness and flexibility [24].

###  II-C Evolutionary Computation

Recent years, evolutionary algorithms (EAs) have demonstrated advantages in
solving large-scale, highly non-linear and expensive optimisation problems
[25] [26]. HPO for GNNs is usually expensive [27] in evaluating each of the
feasible architectures. Thus, using EAs to solve HPO problems have been
explored due to their excellent search ability [28].

For using EA, the representation of solutions (encoding) is a key issue, for
which direct acyclic graphs [29] and binary representation [30] have
demonstrated their advantages. Given good representations of hyperparameters,
EA will generate a population of individuals as potential solutions, each of
which will be evaluated by a fitness function. In most cases the fitness
function is the objective function, which in our context means first fully
training a GNN with the specified hyperparameters and then evaluating its
learning performance ( (in terms of RMSE)) as the fitness value. Thereafter,
these individuals are selected by a selection method (e.g., the roulette)
based on their fitness values to be the parents. Through evolutionary
iterations, those GNNs with higher fitness values are more likely to be
maintained in the population, and those fitter solutions will have more chance
to produce offspring. In the end, the best individual will be selected as the
final GNN model.

There are two main issues in evolutionary computation: convergence of the
algorithm and diversity of population. To make the evolutionary search
converge faster, researchers have proposed many methods, including
modification of evolutionary operators [31], using elite archive [32],
ensembles [33] to increase the chance of selecting better parents, and niching
methods [34] for local exploitation [35]. In terms of population diversity,
some approaches have designed for escaping local optima and improving the
performance of exploration [36]. Regarding the above two issues, in this
research we will propose a novel GA with an elite archive for increasing
convergence and a mating selection strategy which allows one parent to be
selected from the whole population for increasing diversity.

##  III Genetic Algorithm with Hierarchical Evaluation Strategy

In many real-world applications GNN suffers from expensive computational cost,
so HPO for GNN is a challenging task, particularly in those cases with huge
hyperparameter search space. Moreover, GA maintains a population of
individuals (as solutions) during the search, which means in one generation
the computational cost may involve evaluating all GNN models in the
population. To address this issue, a surrogate model with lower evaluation
cost [37] or a faster evaluation method [38] can be considered. However, there
is no guarantee that the fitness values generated by such methods would
reliably approximate those obtained from the original evaluation function, and
therefore the HPO results based on such methods may be poor. A good idea is to
combine both the original and fast evaluation strategies together in GA, in
which case we can achieve a tradeoff between performance and computational
cost.

In the rest of this section we will first introduce the motivation of HESGA,
and then we will present the following two detailed processes: (1) fast
evaluation by using difference of RMSEs and (2) the hierarchical evaluation
strategy. Next, the full HESGA is presented with a scalable module for fast
evaluation. At last, the settings for HESGA are presented.

###  III-A Solution Encoding

Take an example by four of the hyperparameters mentioned in the benchmark
problems: batch size ($s_{b}$), the number of filters in convolution layer
($n_{f}$), learning rate ($r_{l}$) and the number of fully connected nodes
($n_{n}$). A binary encoding for these four hyperparameters is shown in Table
I.

TABLE I: Encoding for Hyperparameter and Solution | $s_{b}$ | $n_{f}$ | $r_{l}$ | $n_{n}$
---|---|---|---|---
Binary encoding | [0 0 0]$\sim$[1 1 1] | [0 0 0]$\sim$[1 1 1] | [0 0 0 0]$\sim$[1 1 1 1] | [0 0 0]$\sim$[1 1 1]
Range of hyperparameters | 1$\sim$8 | 1$\sim$8 | 1$\sim$16 | 1$\sim$8
Resolution (step increment) | 32 | 32 | 0.0001 | 64
Full integer ranges | 32$\sim$256 | 32$\sim$256 | 0.0001$\sim$0.0016 | 64$\sim$512

In Table I, three 3-bit binary strings are used to represent the parameters:
$s_{b}$, $n_{f}$, and $n_{n}$, together with the resolutions of 32, 32, and
64, respectively according to the benchmark problems. A 4-bit binary string is
used to represent the learning rate ($r_{l}$) with a resolution (step
increment) of 0.001 accordingly. Thus, we have the feasible ranges for batch
size as $[32\sim 256]$, the number of filters as $[32\sim 256]$, learning rate
as $[0.0001\sim 0.0016]$ and the number of fully connected nodes as $[64\sim
512]$. It is noted that because the binary string “$000$” corresponds to the
decimal integer $0$, but $0$ is not expected by all of the hyperparameters. So
we transfer the mapping from binary to decimal integer by adding the value of
1 upon the decimal integer, e.g. $000$ will be mapped as decimal integer $1$,
$001$ is mapped to $2$, and $111$ will correspond to integer $8$. According to
Table I, an example of encoding a solution is shown in Fig. 1.

Figure 1: An Example Encode of Solution

With the encoding strategy specified, EA will be able to perform effective
search for the optimal individual in the hyperparameter space. In deed, the
performance of EA will be affected by many factors, such as population size,
maximum number of generations, operators for producing offspring, and
population maintenance strategy, etc. However, we believe that with common
parameters, EA will reach the optimal solution with less evaluation times than
grid search and random search [39].

###  III-B Full Evaluation and Fast Evaluation

Regarding full evaluation, a GNN is first represented by a set of
hyperparameter values and then trained on a specified dataset. At the end of
training, the trained GNN will be validated on another specified dataset, and
the RMSE of the validation will be used to measure the quality of the set of
hyperparameter values as full evaluation.

There are already several approaches on developing fast evaluations, such as
partial training [38] [40], and incomplete training [41] [42]. Partial
training with a sub-dataset is good at tackling big datasets and complicated
models. However, when the dataset is not very big, e.g. the dataset FreeSolv
[16] with only $642$ data points, partial training seems not appropriate due
to the lack of data points for training. While the incomplete training with
early stop policy might be helpful for processing such datasets like FreeSolv.
Based on these ideas, a fast evaluation method by using the difference of
RMSEs of validation between the early stage and the very beginning of training
is introduced. In the below Equation 1, F(t) stands for the fitness value at
epoch t during GNN training.

$\Delta F(1,t)=F(1)-F(t).$ (1)

In the above, $\Delta F(1,t)$ is defined as the difference of fitness between
the $1^{st}$ epoch and $t^{th}$epoch. In our experiments, RMSE was used as the
fitness evaluation metric, so $\Delta F(1,t)$ can approximate the rate of
decrease in RMSE. As a heuristic, those individuals in the population with
bigger $\Delta F(1,t)$ values are more promising to achieve smaller RMSE at
the end of their training. We note that this may not be always the case, but
we use this as an approximate value for the final fitness value in order to
reduce the cost for evaluating GNNs. We also note that the number of $t$
epochs will be far less than the number of epochs needed in training, so
$\Delta F(1,t)$ can also be called difference fitness in the early training
stage.

By using this difference fitness, we can offer a fast evaluation to all
individuals in the population, according to their performance in the early
training stage. However, there is a key issue that needs to be addressed: how
to choose the argument $t$. Since some training algorithms would terminate the
training by a fixed maximum number of epochs, while the others might have a
more adaptive criterion for termination, we cannot set a fixed argument $t$
for the fast evaluation. So $10\%^{\sim}20\%$ of the maximum number of epochs
is proposed, which means the fast evaluation will only consume approx.
$10\%^{\sim}20\%$ of the computational cost compared to the full evaluation.

###  III-C Hierarchical Evaluation Strategy

The fast evaluation will only suggest the individuals which have high
probability of achieving better results after full training, but it still
cannot guarantee that this is always the case. Thus, a hierarchical structure
including both fast and full evaluations is designed as shown in Fig. 2.

Figure 2: Hierarchical Evaluation Strategy

In Fig. 2, after population initialization, all the individuals are assessed
by the full evaluation method in Step (1), and in Step (2), those with higher
fitness values are selected and sent to the elite archive accordingly. In
Steps (3) and (4), parents A and B are individually selected by the roulette
method from the elite archive and the whole population. A new population are
generated in Step (5) to replace the old one. In Step (6), all the individuals
in the new population will not take the full evaluation, alternatively they
are assessed by the fast evaluation method, and a small number of candidates
with better fitness values will be selected in Step (7). Further, these
candidates are assessed by the full evaluation method in Step (8), and then in
Step (9), they will update the elite archive depending on if they are better
than some of the individuals in the elite archive. Next, Steps (3) and (4)
will be repeated to generate new offspring, and the whole process will be run
iteratively until the termination criteria are met.

###  III-D Full HESGA and Parameter Settings

The pseudo code of HESGA and the parameter settings are shown in Algorithm 1.

Algorithm 1 HESGA

1: Initialization with solution and population, $n_{pop}$, ${d_{indi}}$

2: gen = 0, $maxgen$, $r_{e}=0.1$, $r_{c}=0.1$, $p_{c}=0.8$, $p_{m}=0.2$,
$ev_{fast}=0$, $ev_{full}=0$

3: population evaluated by full evaluation, update the elite archive,
$ev_{full}+=n_{pop}$,

4: while $gen<maxgen$ do

5: select Parents A and B from the elite archive and the whole population,
respectively, to generate $n_{pop}$ new offspring

6: fast evaluation on the new population, then select $n_{pop}\times r_{c}$
better individuals to enter the candidate group,
$\mathit{ev_{fast}+=n_{pop},}$

7: full evaluation on the candidate group, and update the elite archive,
$\mathit{ev_{full}+=n_{pop}\times r_{c},}$

8: save the best individual of elite archive, $gen++$

9: end while

10: Output the final GNN model decoded from the best individual in the elite
archive

In Algorithm 1, $n_{pop}$ is the size of population, $d_{indi}$ is the
dimension of solution which depends on the resolution as mentioned in Section
III-A, ${gen}$ is the counter for generations, ${maxgen}$ is the maximum
number of generations allowed in one execution, $r{{}_{e}}$ and $r_{c}$ are
the proportions for elite archive and candidates group, $p_{c}$ and $p_{m}$
are the probabilities for crossover and mutation, $ev_{fast}$ and $ev_{full}$
is the counter for the times of fast and full evaluations. In Line 3, the
initial population will be evaluated by the full evaluation method to select
elites, which will be sent to the elite archive. From Line 4 to Line 9, the
loop is executed until the termination conditions are met. In Line 10, the
final GNN model decoded from the best individual in the elite archive will be
the output.

In each loop (Lines $\mathbf{4}\sim\mathbf{9}$), HESGA will first assess the
new offspring by fast evaluation, then the better candidates selected via fast
evaluation will undergo full evaluation process as in Fig. 2. The elite
archive is then updated by the better candidates. This hierarchical evaluation
strategy offers a pre-selection mechanism by the fast evaluation method
proposed and could save around $80\%^{\sim}90\%$ computational cost. On the
other hand, the full evaluation approach acts as a final assessor, which
ensures that the population moves to the right direction towards the objective
function all the time.

###  III-E Evolutionary Operators and Other Settings

We use the classical binary crossover and mutation operators as in [43] [44]
[45] [46], and their mechanisms are demonstrated by the example shown in Fig.
3. In Fig. 3, the position parameter $p$ in both crossover and mutation is a
randomly generated integer in the range of $(1,\textit{len})$, where $len$ is
the solution length (i.e. the number of bits in the binary string).

Figure 3: Binary Crossover and Mutation

The maximum generation and population size are set according to the specific
problems that HESGA aims to solve. As for the population maintenance, the
elite archive is maintained by the fitness sorting method, while the
population does not need a maintenance policy. In elite archive update, when a
better candidate can successfully update the elite archive, the worst one in
the elite archives will be discarded.

##  IV Experiments

In this section, the performance of HESGA will be experimentally investigated
on several datasets mentioned in Section I, and we use two types of deep graph
neural architectures, Graph Convolution (GC) [6] and Message Passing Neural
Network (MPNN) [18] to assess the performance of HESGA. Section IV-A shows the
advantage and disadvantage of the traditional GA for HPO compared with the
default parameter settings. Section IV-B presents the results obtained from
optimising the GC model with the proposed HESGA compared to the Gaussian HPO
method on three datasets, i.e. ESOL [15], FreeSolv [16] and Lipophilicity
[17]. Section IV-C reports the performance of HESGA on MPNN model. All
experiments are performed on a PC with Inter (R) Core i5-8300 CPU, 8GB Memory,
and GeForce GTX 1050 GPU.

###  IV-A Advantage and Disadvantage of the Traditional GA

For a case study on GA to optimize hyperparameters, we use a traditional GA to
optimise the GC model and run it on the FreeSolv dataset. In this experiment,
three parameters: batch size ($s_{b}$), the number of execution epochs
($n_{e}$), and learning rate ($r_{l}$) are optimized by GA. The hyperparameter
optimized by GA are $s_{b}=32$, $n_{e}=240$ and $r_{l}=0.0015$; on the other
hand, the default hyperparameters pre-set in GC are $s_{b}=128$, $n_{e}=100$
and $r_{l}=0.0005$. These two configurations of parameters are used to run GC
for 30 times independently. The average RMSEs of training, validation and
test, as well as their standard deviations are plotted in Fig. 4. More details
about the distribution of RMSE of validation will be presented in Section V-A.

Figure 4: A comparison between GC with optimised hyperparameters and GC with
default hyperparameters

We carried out $t$-test on the RMSE results obtained from GC with optimized
hyperparameters and GC with default hyperparameters, and it shows that these
two groups of RMSEs do not have the same mean value at a significant level of
5%, regarding training, validation and test, respectively. Thus, it is
significant that using GA hyperparameter optimisation approach will improve
the learning performance of GC with respect to the RMSE.

The disadvantage of the traditional GA for HPO is its intolerable
computational cost, especially to those highly expensive problems. So, as
mentioned in Section III, we present HSEGA contains a fast evaluation strategy
for candidate selection.

###  IV-B Experimental Results of HESGA Added on GC Model

To further investigating the performance of our proposed HESGA, in this
section we will apply HESGA to optimise GC model, then this combination is
tested on the ESOL, FreeSolv and Lipophilicity datasets. We record RMSE values
for comparison with GC with Bayesian hyperparameter optimization (BHO). Each
of the experiments was executed by 30 independent trials to obtain statistical
results. In Tables II$\sim$ IV, $n_{f},n_{n},s_{b},n_{e},l_{r}$ stand for the
number of filters, the number of fully connected nodes, batch size, the number
of maximum epoch, and learning rate, respectively. Symbol M_ and Std_ denote
the mean and standard deviation of the corresponding RMSE, respectively. $h$
is the indicator of $t$-test, $h=1$ indicates that the hypothesis of two
population groups have equal mean is rejected with a default significance
level of $5\%$, in the case of which means the two group of samples have
significantly different mean values. In details, M_RMSE obtained by GC+HESGA
will minus the one obtained by GC+BHO, so a negative $t$ value indicates the
former is better, while a positive $t$ value indicates the former is worse.

TABLE II: The Results on ESOL Dataset

ESOL | Hyperparameters | Training Results | Validation Results | Test Results
---|---|---|---|---
GC + BHO |  $n_{f}$ = 128 | M_RMSE | 0.43 | M_RMSE | 1.05 | M_RMSE | 0.97
$n_{n}$ = 256
$s_{b}$ = 128 | Std_RMSE | 0.20 | Std_RMSE | 0.15 | Std_RMSE | 0.01
$r_{l}$ = 0.0005
GC + HSEGA |  $n_{f}$ = 192 | M_RMSE | 0.34 | M_RMSE | 0.89 | M_RMSE | 0.89
$n_{n}$ = 448
$s_{b}$ = 32 | Std_RMSE | 0.07 | Std_RMSE | 0.04 | Std_RMSE | 0.04
$r_{l}$ = 0.0009
| T-test on results
---
(with significance level of $\alpha$ = 5%)
|  $t$ = -2.436, $h$ = 1
---
to reject the
equal mean hypothesis
|  $t$ = -5.624, $h$ = 1
---
to reject the
equal mean hypothesis
|  $t$ = -9.708, $h$ = 1
---
to reject the
equal mean hypothesis

Table II shows very good performance of HESGA on ESOL dataset compared to the
BHO approach, in which our results of average RMSE (M_RMSE) are all
significant less than those of BHO. Moreover, the hyperparameters obtained by
HESGA had more stable RMSE values during 30 independent trials (i.e. less
standard deviation) in both the training and validation dataset.

TABLE III: The Results on FreeSolv Dataset (1)

FreeSolv | Hyperparameters | Training Results | Validation Results | Test Results |
---|---|---|---|---|---
GC + BHO |  $n_{f}$ = 128 | M_RMSE | 0.31 | M_RMSE | 1.35 | M_RMSE | 1.40 |
$n_{n}$ = 256 |
$s_{b}$ = 128 | Std_RMSE | 0.09 | Std_RMSE | 0.15 | Std_RMSE | 0.16 |
$r_{l}$ = 0.0005 |
GC + HSEGA |  $n_{f}$ = 192 | M_RMSE | 0.63 | M_RMSE | 1.29 | M_RMSE | 1.21 |
$n_{n}$ = 512 |
$s_{b}$ = 32 | Std_RMSE | 0.12 | Std_RMSE | 0.13 | Std_RMSE | 0.12 |
$r_{l}$ = 0.0012 |
| T-test on results
---
with significance level of $\alpha$ = 5%
|  $t$ = 12.031, $h$ = 1
---
to reject the
equal mean hypothesis
|  $t$ = -2.117, $h$ = 1
---
to reject the
equal mean hypothesis
|  $t$ = -5.184, $h$ = 1
---
to reject the
equal mean hypothesis

Regarding the FreeSolv dataset, as the results shown in Table III, in the
training dataset our M_RMSE is worse than the one obtained from GC+BHO,
however, in the results on validation and test datasets, our method are
slightly better than GC+BHO. It should be noted that in terms of validation,
these two results are very similar, as the reject $t$-value for d.f. (degree
of freedom) at 30 and at 60 are 2.042 and 2.0, as the $t$ value we got is
-2.117, which is nearly on the boundary of acceptance. It is also noted that,
as we do not know the exact size of RMSE sample group in the reference paper
[1], we suppose it was in the range of 1$\sim$30, thus d.f. at 30 and 60 are
both considered in this work.

TABLE IV: The Results on Lipophilicity Dataset

Lipophilicity | Hyperrarameters | Training Results | Validation Results | Test Results |
---|---|---|---|---|---
GC + BHO |  $n_{f}$ =128 | M_RMSE | 0.471 | M_RMSE | 0.678 | M_RMSE | 0.655 |
$n_{n}$ =256 |
$s_{b}$ = 128 | Std_RMSE | 0.001 | Std_RMSE | 0.04 | Std_RMSE | 0.036 |
$r_{l}$ =0.0005 |
GC + HSEGA |  $n_{f}$ =160 | M_RMSE | 0.24 | M_RMSE | 0.68 | M_RMSE | 0.67 |
$n_{n}$ =192 |
$s_{b}$ =64 | Std_RMSE | 0.02 | Std_RMSE | 0.02 | Std_RMSE | 0.02 |
$r_{l}$ =0.0013 |
| T-test on results
---
with significance level of $\alpha$ = 5%
|  $t$ = -59.840, $h$ = 1
---
to reject the
equal mean hypothesis
|  $t$ = 0.745, $h$ = 0
---
to accept the
equal mean hypothesis
|  $t$ = 1.816, $h$ = 0
---
to accept the
equal mean hypothesis

In tackling the Lipophilicity dataset, the results in Table IV show that the
proposed approach is far better on the training dataset, and not worse than
GC+BHO on validation and test datasets. As the M_RMSE on the training set is
less than that on the validation and test dataset, the proposed HESGA might
have the over-fitting issue, which reduce its performance on validation and
test datasets. Moreover, the Lipophilicity dataset has the biggest size among
the three (more than 4,000 SMILE entries), so it introduces more complicated
computational operations than the other datasets, which makes the execution
very time-consuming.

###  IV-C Experimental Results of HESGA to optimise MPNN Models

As MPNN models is more time-consuming than GC, we only carried out experiments
on FreeSolv dataset, and the detailed results are shown in Table V.

TABLE V: The Results on FreeSolv Dataset (2)

FreeSolv | Hyperarameters | Training Results | Validation Results | Test Results |
---|---|---|---|---|---
MPNN + BHO | T = 2 | M_RMSE | 0.31 | M_RMSE | 1.20 | M_RMSE | 1.15 |
M = 5 |
$s_{b}$ = 16 | Std_RMSE | 0.05 | Std_RMSE | 0.02 | Std_RMSE | 0.12 |
$r_{l}$ = 0.001 |
MPNN + HSEGA | T = 1 | M_RMSE | 0.70 | M_RMSE | 1.15 | M_RMSE | 1.09 |
M = 10 |
$s_{b}$ = 8 | Std_RMSE | 0.13 | Std_RMSE | 0.15 | Std_RMSE | 0.14 |
$r_{l}$ = 0.0012 |
| T-test on results
---
with significance level of $\alpha$ = 10%
|  $t$ = 14.693, $h$ = 1
---
to reject the
equal mean hypothesis
|  $t$ = -1.835, $h$ = 1
---
to reject the
equal mean hypothesis
|  $t$ = -1.842, $h$ = 1
---
to reject the
equal mean hypothesis

As shown in Tab V, we carried out experiments on applying BHO and HESGA to
optimise MPNN models. In terms of validation and test, the results show that
there is no significant difference between the two sample groups with the
significance level at 5%; however, with the significance level of two tailed
5% (i.e. 10%), the equal mean hypothesis was rejected, which indicates that
our algorithm is slightly better. Moreover, it is observed that on the
training dataset the compared algorithm (MPNN + BHO) is far better than ours,
which indicates that there may be a potential overfitting issue in that
approach.

Overall, it seems that there are some cases of overfitting in the experiments
(Tables II$\sim$ V). The experimental results show that all RMSEs on the
training datasets are less than those on validation and test. Particularly,
the RMSE on the validation and test datasets is around two to four times than
that on the training set in GC + BHO on the FreeSolv dataset and MPNN + BHO on
the Lipophilicity dataset. As a result, overfitting might lead to poorer model
performance on validation/test datasets. For example, in Table V, the training
loss of MPNN + BHO is just 50% of that of MPNN + HESGA, but the loss of MPNN +
BHO on the test and validation datasets are worse than that of MPNN + HESGA.

##  V Further Discussions

###  V-A The Distributions of RMSEs

Given the same set of hyperparameter values for a GNN model, the training
results may be still different from time to time, even for the same split of
the datasets, and this is mainly because in each training process, the weight
vectors for a neural network are randomly initialised. As a result, GNN may
produce variate RMSEs as a full evaluation function for GA, which increases
uncertainty in evaluating all individuals in the GA population. Fig. 5 shows
the distribution of RMSE results on the validation set under two given
hyperparameter settings (one is the default parameters and the other is the
hyperparameters optimised by HESGA).

(a) with the hyperparameter solution optimized

(b) with the default parameters pre-set in GC

Figure 5: The Distribution of RMSE Results on the Validation Set by the
Hyperparameters Optimized and the Default Hyperparameters Pre-set in GC

As shown in Fig. 5, the RMSE values are quite variable in 30 independent
trials. One method to alleviate this negative effect is as follws: we
performed experiments on using the average RMSE of several times (e.g. 3 times
in a trial) of running GNN, however it will make the computational cost 3
times more expensive than before. And this is another reason that we need to
develop a fast evaluation strategy for GA.

###  V-B Solution Resolution and Feasible Searching Space

As presented in Section III-A, with a higher resolution of hyperparameters
being set up, we will have to deal with more feasible solution points. On one
hand, lower resolution would alleviate the computational cost by reducing the
number of feasible solutions, but it would be more likely to miss high quality
solutions. On the other hand, a higher resolution of hyperparameter space will
incur heavier computational overheads, but it would be more likely to identify
a better set of hyperparameters compared with lower resolution. For
comparison, we set up a series of experiments on the FreeSolv dataset with a
varying resolutions of 8, 16, 32, 64 for encoding the batch size and the
number of filters. In Table VI, we list the number of feasible solutions
according to the different resolutions.

Figure 6: The RMSE Results of HESGA + GC on FreeSolv Dataset with Varing
Resolutions of Hyperparameters

As shown in Fig. 6, HESGA with lower resolution (bigger step increment) cannot
find the optimal solutions found by those with higher resolution (smaller step
increment). This is mainly because the grid generated in lower resolution is
so coarse for this problem. On the other hand, the resolution of 16 will be
acceptable for this problem as further higher resolution such as the
resolution at 8 will not gain much improvement on the RMSE values. However,
choosing an appropriate resolution may be a problem-specified issue; in the
case of having abundant computational resources, we recommend to use as high
resolution as possible to achieve better performance for GNN.

TABLE VI: Solution Number under Different Resolution

Resolution (step increment) | 8 | 16 | 32 | 64
---|---|---|---|---
Size of binary solution | 19 | 17 | 15 | 13
Solution number | 524288 | 131072 | 32768 | 8192

###  V-C Computational Cost

There are three processes that can affect the computational cost of the
algorithms used in our experiments, 1) full GC evaluation, 2) fast evaluation
of GC, and 3) HESGA.

####  V-C1 Full Evaluation of GC

Here we take the GC model as an example. As the GC model will first transfer a
SMILE representation to a molecular fingerprint, we suppose that the
fingerprints have a depth of $R$ and length of $L$, $N$ atoms were used in a
molecular convolutional net [6], and $F$ features (filters) are used. In this
case, in each layer the computational costs of feedforward and backpropagation
process can be estimated by $O(\textit{RNFL}+\textit{RNF}^{2})$ [6]. For
simplicity, $O_{GC}$ stands for $O(\textit{RNFL}+\textit{RNF}^{2})$, which
denotes the cost of GC model with one layer and one epoch of training.

####  V-C2 Fast Evaluation of GC

As mentioned above, approx. 10%$\sim$20% of the maximum number of epochs were
used to get the fast evaluation score, thus the cost will be 10%$\sim$20% of
the full evaluation. As a result, for a number of $n_{e}$ epochs, the time
cost will be $n_{e}\times O_{GC}$ approximately. Suppose the fast evaluation
will use a percentage of $p_{f}$ of the total epochs, and in this case the
cost of fast evaluation will be $p_{f}\times n_{e}\times O_{GC}$.

####  V-C3 Total Cost of HESGA

Suppose we have a GC with one convolution layer, a population of solutions
with size $n_{pop}$, and each individual is trained by $n_{e}$ epoch at most,
the proportion of elite group is $r_{e}$, and the maximum generation is
$maxgen$. The detailed cost of HESGA is listed as follows based on Algorithm
1:

Lines 1$\sim$3: for full evaluations on the whole population, it will cost
$n_{pop}\times n_{e}\times O_{GC}$ approximately.

Lines 4$\sim$9: in one generation, for fast evaluation on the whole new
offspring, it will cost $n_{pop}\times p_{f}\times n_{e}\times O_{GC}$; for
the full evaluation on candidates, it will cost $n_{pop}\times r_{c}\times
n_{e}\times O_{GC}$, thus totally the total cost will be $(p_{f}+r_{c})\times
n_{pop}\times n_{e}\times O_{GC}$. Therefore, for $maxgen$ generations, it
will cost $(p_{f}+r_{c})\times n_{pop}\times n_{e}\times O_{GC}\times maxgen$.
It should be noted here that the cost of sorting and counting operations can
be ignored compared with $O_{GC}$.

As a result, HESGA will cost approximately $[(p_{f}+r_{c})\times
maxgen+1]\times n_{pop}\times n_{e}\times O_{GC}$. Take an example as follows:
suppose we have $n_{pop}=10$, $maxgen=10$, $p_{f}=0.1$, $r_{c}=0.1$,
$n_{e}=100$. In this case, thus running HESGA once will equal to running 3,000
times of single $O_{GC}$ in terms of the computational cost.

###  V-D The Scalability of HESGA

We argue that HESGA possesses scalability for different problems and datasets.
For example, for a large dataset, the fast evaluation approach can be replaced
by any reasonable approaches, such as partial training by using sampled data
points randomly from the whole dataset, as in [42]. When historical datasets
are available, a fast surrogate model could be built and trained with the
datasets, to approximate the results obtained from the complete training. No
matter what types of fast evaluation approaches are used, the HESGA will
always be a good mechanism to combine both fast and full evaluation to achieve
a trade-off between solution quality and computational cost.

##  VI Conclusion and Future Work

In this research, we proposed HESGA, a novel GA equipped with a hierarchical
evaluation strategy and full and fast evaluation methods, is proposed to
address expensive the HPO problems for GNNs. Experiments are carried out on
three representative datasets in material property prediction problems: ESOL,
FreeSolv, and Lipophilicity datasets; by applying HESGA to optimise the
hyperparameters of GC and MPNN models, two types of commonly used graph deep
neural networks in material design and discovery. Results show that HESGA can
outperform BHO when optimising GC models, meanwhile it achieves comparable
performance to Bayesian approaches to optimising MPNN models. In Section 5, we
also analysed the uncertainty and distributions of RMSE results, the learning
performance in terms of the resolution of the hypereparameter search space,
the computational cost, and the scalability of HESGA.

In the future, we would like to investigate the following two aspects:

##### Dealing with the over-fitting issue in the experiments

This is an issue observed in both the Bayesian approaches and our HESGA. In
our experiments, the number of epochs ($n_{e}$) is not specified as one
hyperparameter, which might be one reason for overfitting. For an example,
overtraining might cause HPO biases to a perfect fitted model on the training
dataset but this model may perform poorly in validation and test datasets.
Therefore, from our perspective, we would like to investigate how we can
incorporate more hyperparameters in the search space, or to monitor the
overfitting and introduce the penalty item in the evaluation functions.

##### Bi-objective Optimization

As mentioned in Section V-C, the hyperparameters such as the number of epochs
($n_{e}$) and the number of filters ($n_{f}$) are selected to be optimized,
and this will affect the computational cost of HESGA. Suppose the RMSE might
be improved while the cost would be increased at the same time when we
increase $n_{e}$ and $n_{f}$, and in this case a balance between the
performance and cost needs to be considered. In our future work, we will
consider dealing with this balance issue as a bi-objective optimization
problem, and a Pareto-optimal front (PF) [47] is expected to offer more
options of GNN models considering the trade-off between performance and cost.

##  VII Acknowledgement

This research is supported by the Engineering and Physical Sciences Research
Council (EPSRC) funded Project on New Industrial Systems: Manufacturing
Immortality (EP/R020957/1). The authors are also grateful to the Manufacturing
Immortality consortium.

## References

  * [1] Z. Wu, B. Ramsundar, E. N. Feinberg, J. Gomes, C. Geniesse, A. S. Pappu, K. Leswing, and V. Pande, “Moleculenet: a benchmark for molecular machine learning,” _Chemical science_ , vol. 9, no. 2, pp. 513–530, 2018.
  * [2] D. Weininger, “Smiles, a chemical language and information system. 1. introduction to methodology and encoding rules,” _Journal of chemical information and computer sciences_ , vol. 28, no. 1, pp. 31–36, 1988.
  * [3] Q. Long, Y. Jin, G. Song, Y. Li, and W. Lin, “Graph structural-topic neural network,” in _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2020, pp. 1065–1073.
  * [4] J. Zhou, G. Cui, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun, “Graph neural networks: A review of methods and applications,” _arXiv preprint arXiv:1812.08434_ , 2018.
  * [5] H. Cai, V. W. Zheng, and K. C.-C. Chang, “A comprehensive survey of graph embedding: Problems, techniques, and applications,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 30, no. 9, pp. 1616–1637, 2018.
  * [6] D. K. Duvenaud, D. Maclaurin, J. Iparraguirre, R. Bombarell, T. Hirzel, A. Aspuru-Guzik, and R. P. Adams, “Convolutional networks on graphs for learning molecular fingerprints,” in _Advances in neural information processing systems_ , 2015, pp. 2224–2232.
  * [7] M. Nunes and G. L. Pappa, “Neural architecture search in graph neural networks,” in _Brazilian Conference on Intelligent Systems_. Springer, 2020, pp. 302–317.
  * [8] Y. Gao, H. Yang, P. Zhang, C. Zhou, and Y. Hu, “Graph neural architecture search,” in _IJCAI_ , vol. 20, 2020, pp. 1403–1409.
  * [9] M. Claesen and B. De Moor, “Hyperparameter search in machine learning,” _arXiv preprint arXiv:1502.02127_ , 2015.
  * [10] M. Schumer and K. Steiglitz, “Adaptive step size random search,” _IEEE Transactions on Automatic Control_ , vol. 13, no. 3, pp. 270–276, 1968.
  * [11] J. Snoek, H. Larochelle, and R. P. Adams, “Practical bayesian optimization of machine learning algorithms,” in _Advances in neural information processing systems_ , 2012, pp. 2951–2959.
  * [12] C. Di Francescomarino, M. Dumas, M. Federici, C. Ghidini, F. M. Maggi, W. Rizzi, and L. Simonetto, “Genetic algorithms for hyperparameter optimization in predictive business process monitoring,” _Information Systems_ , vol. 74, pp. 67–83, 2018.
  * [13] D. Orive, G. Sorrosal, C. E. Borges, C. Martín, and A. Alonso-Vicario, “Evolutionary algorithms for hyperparameter tuning on neural networks models,” in _Proceedings of the 26th european modeling & simulation symposium. Burdeos, France_, 2014, pp. 402–409.
  * [14] X. Xiao, M. Yan, S. Basodi, C. Ji, and Y. Pan, “Efficient hyperparameter optimization in deep learning using a variable length genetic algorithm,” _arXiv preprint arXiv:2006.12703_ , 2020.
  * [15] J. S. Delaney, “Esol: estimating aqueous solubility directly from molecular structure,” _Journal of chemical information and computer sciences_ , vol. 44, no. 3, pp. 1000–1005, 2004.
  * [16] D. L. Mobley and J. P. Guthrie, “Freesolv: a database of experimental and calculated hydration free energies, with input files,” _Journal of computer-aided molecular design_ , vol. 28, no. 7, pp. 711–720, 2014.
  * [17] M. Wenlock and N. Tomkinson, “Experimental in vitro DMPK and physicochemical data on a set of publicly disclosed compounds,” 2015. [Online]. Available: https://doi.org/10.6019/chembl3301361
  * [18] O. Vinyals, S. Bengio, and M. Kudlur, “Order matters: Sequence to sequence for sets,” _arXiv preprint arXiv:1511.06391_ , 2015.
  * [19] J. Bergstra and Y. Bengio, “Random search for hyper-parameter optimization,” _The Journal of Machine Learning Research_ , vol. 13, no. 1, pp. 281–305, 2012.
  * [20] M. Wistuba, N. Schilling, and L. Schmidt-Thieme, “Scalable gaussian process-based transfer surrogates for hyperparameter optimization,” _Machine Learning_ , vol. 107, no. 1, pp. 43–78, 2018.
  * [21] K. Eggensperger, M. Feurer, F. Hutter, J. Bergstra, J. Snoek, H. Hoos, and K. Leyton-Brown, “Towards an empirical foundation for assessing bayesian optimization of hyperparameters,” in _NIPS workshop on Bayesian Optimization in Theory and Practice_ , vol. 10, 2013, p. 3.
  * [22] J. Snoek, O. Rippel, K. Swersky, R. Kiros, N. Satish, N. Sundaram, M. Patwary, M. Prabhat, and R. Adams, “Scalable bayesian optimization using deep neural networks,” in _International conference on machine learning_ , 2015, pp. 2171–2180.
  * [23] A. Klein, S. Falkner, S. Bartels, P. Hennig, and F. Hutter, “Fast bayesian optimization of machine learning hyperparameters on large datasets,” in _Artificial Intelligence and Statistics_. PMLR, 2017, pp. 528–536.
  * [24] S. Falkner, A. Klein, and F. Hutter, “Bohb: Robust and efficient hyperparameter optimization at scale,” _arXiv preprint arXiv:1807.01774_ , 2018.
  * [25] K. Deb, _Multi-objective optimization using evolutionary algorithms_. John Wiley & Sons, 2001, vol. 16.
  * [26] C. A. C. Coello, G. B. Lamont, D. A. Van Veldhuizen _et al._ , _Evolutionary algorithms for solving multi-objective problems_. Springer, 2007, vol. 5.
  * [27] L. Ma, J. Cui, and B. Yang, “Deep neural architecture search with deep graph bayesian optimization,” in _2019 IEEE/WIC/ACM International Conference on Web Intelligence (WI)_ , 2019, pp. 500–507.
  * [28] S. R. Young, D. C. Rose, T. P. Karnowski, S.-H. Lim, and R. M. Patton, “Optimizing deep learning hyper-parameters through an evolutionary algorithm,” in _Proceedings of the Workshop on Machine Learning in High-Performance Computing Environments_ , 2015, pp. 1–5.
  * [29] M. Suganuma, S. Shirakawa, and T. Nagao, “A genetic programming approach to designing convolutional neural network architectures,” in _Proceedings of the genetic and evolutionary computation conference_ , 2017, pp. 497–504.
  * [30] L. Xie and A. Yuille, “Genetic cnn,” in _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , Oct 2017.
  * [31] Q. Zhu, Q. Lin, Z. Du, Z. Liang, W. Wang, Z. Zhu, J. Chen, P. Huang, and Z. Ming, “A novel adaptive hybrid crossover operator for multiobjective evolutionary algorithm,” _Information Sciences_ , vol. 345, pp. 177–198, 2016.
  * [32] Q. Zhu, Q. Lin, W. Chen, K.-C. Wong, C. A. C. Coello, J. Li, J. Chen, and J. Zhang, “An external archive-guided multiobjective particle swarm optimization algorithm,” _IEEE transactions on cybernetics_ , vol. 47, no. 9, pp. 2794–2808, 2017.
  * [33] W. Wang, S. Yang, Q. Lin, Q. Zhang, K.-C. Wong, C. A. C. Coello, and J. Chen, “An effective ensemble framework for multiobjective optimization,” _IEEE Transactions on Evolutionary Computation_ , vol. 23, no. 4, pp. 645–659, 2018.
  * [34] Q. Lin, Z. Liu, Q. Yan, Z. Du, C. A. C. Coello, Z. Liang, W. Wang, and J. Chen, “Adaptive composite operator selection and parameter control for multiobjective evolutionary algorithm,” _Information Sciences_ , vol. 339, pp. 332–352, 2016.
  * [35] M. Li, S. Yang, and X. Liu, “Pareto or non-pareto: Bi-criterion evolution in multiobjective optimization,” _IEEE Transactions on Evolutionary Computation_ , vol. 20, no. 5, pp. 645–665, 2015.
  * [36] S. Yang, W. Wang, Q. Lin, and J. Chen, “A novel pso-de co-evolutionary algorithm based on decomposition framework,” in _International conference on smart computing and communication_. Springer, 2016, pp. 381–389.
  * [37] T. Chugh, C. Sun, H. Wang, and Y. Jin, “Surrogate-assisted evolutionary optimization of large problems,” in _High-Performance Simulation-Based Optimization_. Springer, 2020, pp. 165–187.
  * [38] L. Frachon, W. Pang, and G. M. Coghill, “Immunecs: Neural committee search by an artificial immune system,” _arXiv preprint arXiv:1911.07729_ , 2019.
  * [39] E. Bochinski, T. Senst, and T. Sikora, “Hyper-parameter optimization for convolutional neural network committees based on evolutionary algorithms,” in _2017 IEEE International Conference on Image Processing (ICIP)_ , 2017, pp. 3924–3928.
  * [40] B. Zoph, V. Vasudevan, J. Shlens, and Q. V. Le, “Learning transferable architectures for scalable image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 8697–8710.
  * [41] A. Zela, A. Klein, S. Falkner, and F. Hutter, “Towards automated deep learning: Efficient joint neural architecture and hyperparameter search,” _arXiv preprint arXiv:1807.06906_ , 2018.
  * [42] E. Real, A. Aggarwal, Y. Huang, and Q. V. Le, “Regularized evolution for image classifier architecture search,” in _Proceedings of the aaai conference on artificial intelligence_ , vol. 33, 2019, pp. 4780–4789.
  * [43] K. Deb, R. B. Agrawal _et al._ , “Simulated binary crossover for continuous search space,” _Complex systems_ , vol. 9, no. 2, pp. 115–148, 1995.
  * [44] S. M. Lim, A. B. M. Sultan, M. N. Sulaiman, A. Mustapha, and K. Leong, “Crossover and mutation operators of genetic algorithms,” _International Journal of Machine Learning and Computing_ , vol. 7, no. 1, pp. 9–12, 2017.
  * [45] M. Mitchell, “An introduction to genetic algorithms mit press,” _Cambridge, Massachusetts. London, England_ , vol. 1996, 1996.
  * [46] D. Whitley, “A genetic algorithm tutorial,” _Statistics and computing_ , vol. 4, no. 2, pp. 65–85, 1994.
  * [47] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: Nsga-ii,” _IEEE transactions on evolutionary computation_ , vol. 6, no. 2, pp. 182–197, 2002.