11institutetext: Department of Applied Mathematics I, University of Sevilla,
Sevilla, Spain 11email<EMAIL_ADDRESS>Department of
Quantitative Methods, Universidad Loyola Andalucía, Campus Sevilla, Dos
Hermanas, Seville, Spain
22email: epaluzo@{uloyola,us}.es33institutetext: Cnr-Istituto di Elettronica,
Ingegneria dell’Informazione e delle Telecomunicazioni (CNR-IEIIT), Genoa,
Italy
33email<EMAIL_ADDRESS>44institutetext: Data Science Department,
Biocentis, Milan, Italy
44email<EMAIL_ADDRESS>
# Application of the representative measure approach to assess the reliability
of decision trees in dealing with unseen vehicle collision data

Javier Perera-Lago 11 0009-0009-4536-4020
Víctor Toscano-Durán 11 0009-0006-1316-9026
Eduardo Paluzo-Hidalgo 1122 0000-0002-4280-5945
Sara Narteni 33 0000-0002-0579-647X
Matteo Rucco 44 0000-0003-2561-3340

###### Abstract

Machine learning algorithms are fundamental components of novel data-informed
Artificial Intelligence architecture. In this domain, the imperative role of
representative datasets is a cornerstone in shaping the trajectory of
artificial intelligence (AI) development. Representative datasets are needed
to train machine learning components properly. Proper training has multiple
impacts: it reduces the final model’s complexity, power, and uncertainties. In
this paper, we investigate the reliability of the
$\varepsilon$-representativeness method to assess the dataset similarity from
a theoretical perspective for decision trees. We decided to focus on the
family of decision trees because it includes a wide variety of models known to
be explainable. Thus, in this paper, we provide a result guaranteeing that if
two datasets are related by $\varepsilon$-representativeness, i.e., both of
them have points closer than $\varepsilon$, then the predictions by the
classic decision tree are similar. Experimentally, we have also tested that
$\varepsilon$-representativeness presents a significant correlation with the
ordering of the feature importance. Moreover, we extend the results
experimentally in the context of unseen vehicle collision data for XGboost, a
machine-learning component widely adopted for dealing with tabular data.

###### Keywords:

Decision trees XGboost Representativeness Feature importance

##  1 Introduction

In the contemporary landscape of technological evolution, the imperative role
of representative datasets stands as a cornerstone in shaping the trajectory
of artificial intelligence (AI) development. As AI algorithms increasingly
influence decision-making processes, the need for robust, unbiased, and
comprehensive datasets becomes ever more critical [21]. The frameworks that
provide the guidelines and the technical requirements for engineering
trustworthy data-driven AI systems provide at least two possible
interpretations of representativeness [11, 10, 1, 17, 22, 5, 31]: 1) attribute
coverage and completeness: how much the samples in a dataset describe the
phenomena under observations. The question mark can be interpreted both in
terms of the number of features that have been recorded in the dataset and the
number and sparsity of samples concerning the dynamics of the system. 2)
similarity among datasets: given two or more datasets, how much are they
different, and what is their impact on a data-driven model derived from the
datasets. Attribute coverage and completeness can be measured with different
approaches. Methods such as Population Parity and Disparate Impact quantify
and identify disparities in the distribution of different demographic groups
within a dataset [26, 33]. Statistical techniques like Feature Divergence and
Kernel Density Estimation can be used to assess the similarity between feature
distributions in the dataset and the real-world population [30, 29]. Fairness
Indicators and Counterfactual Fairness detect and mitigate biases in AI models
trained on biased datasets [15, 34]. Outlier Analysis and Clustering
Techniques can be used to identify the points that might compromise dataset
representativeness [6, 20]. Temporal Drift Detection and Cohort Analysis are
explored, shedding light on techniques that ensure the dataset’s
representativeness remains intact as conditions evolve over time [32, 27].
Transfer Learning and Adversarial Training are discussed in adapting models to
diverse domains, mitigating biases associated with domain-specific features
[25, 12]. Crowdsourcing and Expert Evaluation are presented as methods to
incorporate diverse perspectives, providing insights into potential biases and
limitations in the dataset from end-users and domain experts [19, 18].
Intersectional Approaches and Subgroup Analysis are considered, emphasizing
the importance of examining the interaction between multiple demographic
attributes for a more comprehensive assessment of representativeness [9].

On the other hand, assessing the similarity of datasets is crucial for
ensuring that machine learning models trained on these datasets generalize
well to real-world scenarios. Various methods have been developed to measure
the likeness between datasets, to identify potential discrepancies, and to
ensure that the data used for model training accurately represents the target
domain. Metrics such as Wasserstein distance, Jensen-Shannon divergence, and
Bhattacharyya distance offer quantitative measures of dissimilarity between
probability distributions, providing insights into the overall similarity of
datasets [28, 3]. Additionally, domain adaptation techniques, such as Maximum
Mean Discrepancy (MMD) and Kernelized Discrepancy (KMM), focus on aligning
feature distributions between source and target domains, ensuring a seamless
transition from one dataset to another [14, 16]. Understanding and mitigating
dissimilarities between datasets are paramount to building robust and
generalizable machine learning models, as models trained on dissimilar
datasets may exhibit poor performance when deployed in real-world
applications. Therefore, a comprehensive assessment of dataset similarity is
indispensable for fostering reliable and effective AI systems. In this paper,
we use the measure proposed in [13] to quantify the similarity between
datasets and how their difference has an impact on a machine learning
component, decision trees and, in particular, for the eXtreme Gradient
Boosting (aka XGBoost). XGBoost stands out as a powerful and versatile machine
learning algorithm with significant implications for trustworthy AI. Its
importance lies in its ability to enhance model performance across various
tasks, such as classification, regression, and ranking. XGBoost excels in
handling complex datasets, mitigating overfitting, and providing robust
predictions. The algorithm’s interpretability features, such as the ability to
generate feature importance scores and decision trees, contribute to the
transparency of AI models—a crucial aspect for ensuring trustworthiness.
Moreover, XGBoost’s regularized learning objectives and advanced optimization
techniques foster model generalization and prevent overfitting, reinforcing
the reliability of AI systems. The algorithm’s widespread adoption in both
research and industry attests to its effectiveness and underscores its role in
building trustworthy AI models that prioritize accuracy, interpretability, and
generalization [7].

This paper is organized as follows. In Section 2, the main concepts about
decision trees are provided. Then, in Section 3, we discuss the relationship
between the $\varepsilon$-representativeness measure and the predictions of
decision trees proving theoretical results. In Section 4, we explore
experimentally the correlation between $\varepsilon$-representativeness and
the similarity between the explanations provided by decision trees and XGBoost
by the ordering of the feature importance. Finally, conclusions and future
work are discussed in Section 5.

##  2 Classification with decision trees and XGBoost

In this section, we introduce all the needed concepts about classification and
the model family of decision trees. For a further understanding of machine
learning, we refer to [23], and for geometric results for point clouds we
refer to [4].

Let $(X,\lambda_{X})$ be a dataset for classification with
$X\subseteq\mathbb{R}^{d}$ the set of data with size $N$ and
$\lambda_{X}:X\rightarrow\\{1,\dots,c\\}$ the class labelling. For each $x\in
X$, the $j$-th coordinate coordinate of $x$ will be denoted by
$x_{j}\in\mathbb{R}$ and will be called the $j$-th feature of $x$. The
objective of classification is to find a function
$f:\mathbb{R}^{n}\rightarrow\\{1,\dots,c\\}$ that approximates $\lambda_{X}$.
In the literature, there exist different families of functions $f$, such as
artificial neural networks and support vector machines, which are called
models [23]. We will focus on the family of decision trees $\mathcal{T}$ which
are supervised learning models with desirable properties such as that they are
interpretable by definition. The most basic model of the family is decision
trees (DT) (see [23, Section 9.3.3]).

A binary DT is a rooted tree representing a partition of the feature space. It
contains a set of ordered nodes $\\{n_{1},\cdots,n_{r}\\}$ where $n_{1}$ will
be called the root node. A node is said to be internal if it is connected to
two children nodes, opening new branches in the tree. Conversely, terminal
nodes, also known as leaves, do not have children and represent the endpoints
of a branch in the tree. Let $I\subset\\{1,\cdots,r\\}$ be the subset of
indices corresponding to the internal nodes, and $L$ be the subset of indices
corresponding to the terminal nodes. The root node $n_{1}$ is considered an
internal node, so $1\in I$.

Given a data $x\in X$, $x$ traverses the internal nodes of the binary DT from
the root $n_{1}$ to one of the terminal nodes. Each internal node $n_{i}$ is
associated with one of the features $j_{i}\in\\{1,\cdots,n\\}$, and with one
condition in terms of an inequality bounded by a threshold value
$t_{i}\in\mathbb{R}$ that will send the data to one of the two children nodes
based on the inequality. This inequality is called a decision rule. When $x$
reaches an internal node $n_{i}$, it is sent to its left child if
$t_{i}-x_{j_{i}}>0$ and to its right child otherwise. The margin $\mu_{i}>0$
of an internal node $n_{i}$ is the minimum value $|t_{i}-x_{j_{i}}|$ for all
the examples $x\in X$ reaching $n_{i}$. On the other hand, each terminal node
$n_{\ell}$ is associated with an integer $k_{\ell}\in\\{1,\cdots,c\\}$
representing a class label. When $x$ reaches a terminal node $n_{\ell}$, it
finishes its path through the binary DT and is predicted to be in the class
$k_{\ell}$.

There exist different training algorithms for binary DTs. In our case, let us
consider first a binary DT with just one node that splits the dataset into two
subsets based on one of the features. The feature and the splitting condition
are chosen based on minimizing the impurity of the nodes. The impurity of a
node is a measure of the homogeneity of the class labels of the examples that
reach it. A node has maximum impurity when all the class labels are evenly
distributed, and has minimum impurity (it is called a pure node) when all the
labels are the same. Then, the process is iterated recursively until a desired
depth is reached or the impurity can not be improved. There exist different
impurity measures. The most common ones are the entropy and the Gini index
[23, Section 9.3.3].

Let us denote by $N_{i}$ the number of examples from $X$ reaching the node
$n_{i}$. The number of class $k$ examples reaching $n_{i}$ will be denoted by
$N_{i,k}$. Then, let us use the following notation: $p_{i}=N_{i}/N$,
$p_{i,k}=N_{i,k}/N_{i}$. The entropy of a node $n_{i}$ is
$E(n_{i})=-\sum_{k=1}^{c}p_{i,k}\log{p_{i,k}}$, and the Gini index of $n_{i}$
is $G(n_{i})=\sum_{k=1}^{c}p_{i,k}(1-p_{i,k})$. Assume that we fix an impurity
measure and we denote it as $I$. The information gain for an internal node
$n_{i}$ whose two children nodes are $n_{i_{1}}$ and $n_{i_{2}}$ is:

$IG(n_{i})=I(n_{i})-\frac{N_{i_{1}}}{N_{i}}I(n_{i_{1}})-\frac{N_{i_{2}}}{N_{i}}I(n_{i_{2}})$

Feature importance ($FI$) quantifies the impact of a particular feature
$j\in\\{1,\cdots,d\\}$ in decreasing the impurity of the decision tree. It is
calculated as:

$FI(j)=\sum_{\begin{subarray}{c}i\in I\\\ j_{i}=j\end{subarray}}N_{i}\cdot
IG(n_{i})$

The goodness of the classification given by $T\in\mathcal{T}$ for the dataset
$(X,\lambda_{X})$ is measured by the accuracy, with formula
$\operatorname{Acc}(T,(X,\lambda_{X}))=\sum_{\ell\in L}p_{\ell}\cdot
p_{\ell,k_{\ell}}$.

A more complex algorithm belonging to $\mathcal{T}$ is called XGBoost [8]. A
thorough description of XGBoost is out of the scope of this paper but, roughly
speaking, it is an ensemble of decision trees, i.e., it combines the
predictions of several binary DTs that are sequentially built, each correcting
errors of the previous one. Then, during the training a gradient descent
optimization algorithm is used.

##  3 Representativeness and decision trees

In this section, we introduce a metric to compare different training datasets
and we show a theoretical result proving the relation between this metric and
the final performance of a binary DT.

Given a dataset $(X,\lambda_{X})$, the ability of a binary DT to predict new
unseen data will depend on the completeness and quality of the information
learned during training. It becomes then a vital task to find measures to
compare datasets expected to induce similar predictions. In [13], a measure
based on computational topology was proposed. This measure is called the
$\varepsilon$-representativeness of a dataset. Given another dataset
$(\tilde{X},\lambda_{\tilde{X}})$ with the cardinality of $\tilde{X}$ smaller
than the one of $X$, we say that $\tilde{x}\in\tilde{X}$ is an
$\varepsilon$-representative of $x\in X$ if
$||\tilde{x}-x||_{\infty}\leq\varepsilon$ and
$\lambda_{X}(x)=\lambda_{\tilde{X}}(\tilde{x})$, and we say that
$(\tilde{X},\lambda_{\tilde{X}})$ is an $\varepsilon$-representative dataset
of $(X,\lambda_{X})$ if for all $x\in X$ there exists $\tilde{x}\in\tilde{X}$
that is an $\varepsilon$-representative of $x$. In general, we will consider
$\tilde{X}$ to be a subset of $X$ but it is not a necessary condition. All the
notations that we defined in the previous section for $(X,\lambda_{X})$ will
have the symbol $\tilde{}$ when we refer to $(\tilde{X},\lambda_{\tilde{X}})$
(for example, we will say that the size of $\tilde{X}$ is $\tilde{N}$). A
dataset $(\tilde{X},\lambda_{\tilde{X}})$ that is representative of
$(X,\lambda_{X})$ is said to be $\gamma$-balanced if each
$\tilde{x}\in\tilde{X}$ is representative of exactly $\gamma$ data examples of
$X$ and each $x\in X$ is represented by a single example
$\tilde{x}\in\tilde{X}$.

Knowing the concept of representativeness, we present the following result:

###### Theorem 3.1

Let $T\in\mathcal{T}$ be a binary DT, $(X,\lambda_{X})$ a dataset and
$(\tilde{X},\lambda_{\tilde{X}})$ a $\gamma$-balanced
$\varepsilon$-representative dataset of $(X,\lambda_{X})$. If
$\varepsilon<M=\min_{i\in I}\mu_{i}$, then

$\operatorname{Acc}(T,(X,\lambda_{X}))=\operatorname{Acc}(T,(\tilde{X},\lambda_{\tilde{X}}))$

###### Proof

Let $x=(x_{1},\cdots,x_{n})^{T}\in X$ and
$\tilde{x}=(\tilde{x}_{1},\cdots,\tilde{x}_{n})^{T}\in\tilde{X}$ be an
$\varepsilon$-representative of $x$. That means that
$|\tilde{x}_{j}-x_{j}|\leq\varepsilon\ \forall j\in\\{1,\cdots,d\\}$. Assume
that $\tilde{x}$ accesses the tree through the root node $n_{1}$ and is sent
to its left child. That means that $0<t_{1}-\tilde{x}_{j_{1}}$. By the
definition of margins, we know that $\mu_{1}\leq t_{1}-\tilde{x}_{j_{1}}$.
Since $\tilde{x}$ is $\varepsilon$-representative of $x$, we have that
$x_{j_{1}}\leq\tilde{x}_{j_{1}}+\varepsilon$. Adding these two last
inequalities, we have that $\mu_{1}-\varepsilon\leq t_{1}-x_{j_{1}}$. Since
$\varepsilon<M\leq\mu_{1}$, then $0<t_{1}-x_{j_{1}}$, meaning that $x$ is also
sent to the left child. Analogously, if we assume that $\tilde{x}$ is sent to
the right child of $n_{1}$, we can show that $x$ is also sent to the right
child. If we apply this same reasoning to all the internal nodes that
$\tilde{x}$ passes through, we see that $x$ follows the same path through the
tree and, consequently, reaches the same terminal node $n_{\ell}$ and is
classified with the same label $k_{\ell}$.

By the definition of $\gamma$-balance, for each $\tilde{x}\in\tilde{X}$ of
class $k$ there are exactly $\gamma$ examples from $X$ of class $k$
$\varepsilon$-represented by $\tilde{x}$, and all of them reach the same
terminal node of $T$. It also follows from the definition of $\gamma$-balance
that $N=\gamma\cdot\tilde{N}$, $N_{j}=\gamma\cdot\tilde{N}_{j}$ and
$N_{j,k}=\gamma\cdot\tilde{N}_{j,k}$. Consequently,
$p_{j}=N_{j}/N=(\gamma\cdot\tilde{N}_{j})/(\gamma\cdot\tilde{N})=\tilde{N}_{j}/\tilde{N}=\tilde{p}_{j}$
and
$p_{j,k}=N_{j,k}/N_{j}=(\gamma\cdot\tilde{N}_{j,k})/(\gamma\cdot\tilde{N}_{j})=\tilde{N}_{j,k}/\tilde{N}_{j}=\tilde{p}_{j,k}$.
Consequently:

$\operatorname{Acc}(T,(X,\lambda_{X}))=\sum_{j\in L}p_{j}\cdot
p_{j,k_{j}}=\sum_{j\in
L}\tilde{p}_{j}\cdot\tilde{p}_{j,k_{j}}=\operatorname{Acc}(T,(\tilde{X},\lambda_{\tilde{X}}))$

∎

It is important to note that this result pertains to the accuracy of a fixed
binary DT when evaluated on both the full dataset and a representative subset.
We cannot guarantee that training will yield a similar DT when using either
the full dataset or its representative subset. However, if the accuracy is
high for the DT trained on the representative dataset, Theorem 3.1 ensures
that its accuracy will also be high on the full dataset.

##  4 Experiments

The experiments developed are organized as follows. Firstly, a $2D$ synthetic
dataset was used as an illustration of the proposed methodology. Then, the
experimentation was extended to the vehicle platooning (also called collision)
dataset [24]. Given a dataset, subsets of the set with different values of
$\varepsilon$-representativeness will be considered and the ordering of the
features based on the importance compared. The results suggest that the lower
values of $\varepsilon$ will produce similar explanations of the input data
and similar decision boundaries. The code for the experiments is available in
a GitHub repository
111https://github.com/Cimagroup/Application_Representative_Measure_Reliability_DT.

###  4.1 Synthetic $2D$ dataset

In this experiment, we used a $2D$ dataset generated using the Python Scikit-
learn package222https://scikit-learn.org/stable/index.html as an example. The
dataset comprises $200$ data distributed in two noisy concentric circles
representing distinct classes as shown in Figure 1.

Figure 1:  Full synthetic dataset generated using Scikit-learn and the two
random subsets. From left to right: (1) the training set; (2) a subset
composed of a $40\%$ of the training set and $\varepsilon=0.756$; (3) a subset
composed of $40\%$ of the training set and $\varepsilon=0.497$. We can also
see the decision boundaries of the binary DTs trained using each set of data.

The methodology followed in the experiments is summarized in the following
steps. The dataset was split into a training set composed of the $75\%$ of the
data and a test set with the remaining $25\%$. Then, two random subsets
containing the $40\%$ of the training set were considered, from now on Subset
1 and Subset 2, and their $\varepsilon$-representativeness was computed,
obtaining $\varepsilon=0.756$ for the Subset 1 and $\varepsilon=0.497$ for the
Subset 2.

A binary DT was trained with the training set and the subsets using the Gini
index and a maximum depth of $4$ obtaining the binary DTs of Figure 2. As we
can see, the resultant decision rules after training the DT with the training
set are similar with a lower value of $\varepsilon$. The accuracy values for
the binary DTs on the test set were: $0.84$ for the train dataset, $0.94$ for
Subset 1, and $0.82$ for Subset 2. To determine the similarities between the
binary DTs, we considered the ordering of the feature importance. The first
feature ranked the most important for both the training set and Subset 2 while
the ordering was the opposite for Subset 1 (See Table 1).

Table 1: Feature importance percentage for the training set, Subset 1, and Subset 2. We can see that the most important feature for the training set and Subset 2 is the same. Data | $x_{1}$ | $x_{2}$
---|---|---
Training set | 40.4 | 59.6
Subset 1 | 50.37 | 49.62
Subset 2 | 18.4 | 81.6

Figure 2:  Binary DTs for the sets in Figure 1. From top to bottom: (1) the
training set; (2) a subset composed of a $40\%$ of the training set and
$\varepsilon=0.756$; (3) a subset composed of $40\%$ of the training set and
$\varepsilon=0.497$.

###  4.2 The collision dataset

In this experiment, we used the binary classification collision Dataset [24]
which consists of predicting whether a platoon of vehicles will collide based
on features such as the number of cars or their speed. It is composed of
107,210 data with 23 numerical features. Each class is composed of 69,348
examples and 37,862 examples, respectively.

We followed a similar methodology to the one proposed for the experiment in
Subsection 4.1. The dataset was split into a training set composed of the
$75\%$ of the data and a test set with the remaining $25\%$. Then, two random
subsets containing the $10\%$ of the training data were considered,
denominated as Subset 1 and Subset 2, and their
$\varepsilon$-representativeness was computed, obtaining $\varepsilon=0.539$
for Subset 1 and $\varepsilon=0.655$ for Subset 2. A binary DT was trained
with the training set and the subsets using the Gini index and a maximum depth
of 10. The following accuracy values were obtained on the test set: $0.874$
for the training dataset, $0.841$ for Subset 1, and $0.84$ for Subset 2.

To determine the similarities between the binary DTs, we considered the
ordering of the feature importance. For comparing the ordering of the feature
importance, we used a metric developed in [2, Section 4.2]. Let $x$ and $y$ be
two ordered sets whose elements are the features of the dataset ordered by
their importance. Then, for each feature, we compute the absolute value of the
difference between the position of the feature in $x$ and $y$. Finally, the
mean of these differences is computed. For Subset 1, we obtained a value of
$1.74$ for this metric, and for Subset 2 the value was $1.83$, where we can
highlight the higher similarity of variable importance for the decision tree
generated by the subset with lower epsilon, that is the Subset 1. The ordering
of the feature importance for the three binary DTs is displayed in Table 2.
Finally, the experiment was repeated for 100 subsets and the Spearman’s
correlation ($Sp$) between the $\varepsilon$-representativeness and the metric
of the ordering of the feature importance was computed obtaining significant
correlation ($Sp=0.51$, $p$-value$=5.2\times 10^{-8}$).

Table 2: Ordering of the feature importance for binary DTs and XGBoost trained with the training set and the random subsets. The number indicates the position in the importance order. For example, the most important feature for binary DT trained on the training set is Int_dv7. | DT | XGBoost
---|---|---
| Training set | Subset 1 | Subset 2 | Training set | Subset 1 | Subset 2
F0 | 2 | 4 | 2 | 2 | 3 | 2
d_ms | 10 | 10 | 10 | 10 | 10 | 10
d0 | 6 | 8 | 9 | 5 | 7 | 9
v0 | 23 | 23 | 20 | 23 | 23 | 23
prob | 5 | 5 | 8 | 6 | 5 | 7
Int_dv1 | 15 | 14 | 12 | 13 | 13 | 12
Int_dv2 | 12 | 15 | 19 | 16 | 15 | 21
Int_dv3 | 14 | 17 | 14 | 14 | 14 | 13
Int_dv4 | 7 | 9 | 7 | 9 | 9 | 8
Int_dv5 | 20 | 12 | 21 | 18 | 16 | 19
Int_dv6 | 16 | 16 | 23 | 15 | 17 | 20
Int_dv7 | 1 | 1 | 1 | 1 | 1 | 1
Int_dd2 | 18 | 22 | 16 | 19 | 19 | 14
Int_dd3 | 19 | 18 | 15 | 20 | 20 | 16
Int_dd4 | 3 | 3 | 3 | 4 | 4 | 4
Int_dd5 | 13 | 13 | 13 | 12 | 12 | 15
Int_dd6 | 17 | 21 | 17 | 17 | 18 | 18
Int_dd7 | 11 | 11 | 11 | 11 | 11 | 11
duration | 22 | 20 | 22 | 21 | 22 | 22
freq | 4 | 2 | 4 | 3 | 2 | 3
ampl | 8 | 7 | 6 | 7 | 8 | 6
Fresponse | 21 | 19 | 18 | 22 | 21 | 17
KInt | 9 | 6 | 5 | 8 | 6 | 5

Additionally, we trained Gradient Boosting Classifier(XGBoost) with the
training set and the subsets using the Friedman Mean Squared Error as a
criterion and a maximum depth of 10. The number of boosting stages to perform
was set to 25. The following accuracy values were obtained: $0.912$ for the
training dataset, $0.882$ for Subset 1, and $0.876$ for Subset 2. In this
case, Subset 1 has a similarity of $0.696$ for the feature importance, and
Subset 2 has a similarity value of $1.823$, reaching better similarity with
lower $\varepsilon$. The ordering of the feature importance for the three
XGBoost trained models is displayed in Table 2. Finally, the experiment was
repeated for 100 subsets and the Spearman’s correlation ($Sp$) between the
$\varepsilon$-representativeness and the metric of the ordering of the feature
importance was computed obtaining significant correlation ($Sp=0.673$,
$p$-value$=1.79\times 10^{-14}$).

##  5 Conclusions and future work

The results of this paper are two-fold. Firstly, we proved that similar
accuracy is obtained when certain conditions about representativeness are
satisfied when using binary DTs. Secondly, by experimentation, we have
compared the feature importance ordering for different subsets of the training
data with different values of $\varepsilon$-representativeness reaching a
significant correlation between them. According to our results, representative
sets produce similar explanations of the dataset. Finally, we extend our
experiments to a more complex decision tree algorithm, XGBoost. In the future,
we would like to provide theoretical guarantees regarding the ordering of the
importance of the features and distance-based comparison between the decision
rules of binary DTs.

## Acknowledgements

We want to thank Maurizio Mongelli and Miguel A. Gutierrez-Naranjo for the
insightful discussions and ideas. The work was supported in part by the
European Union HORIZON-CL4-2021-HUMAN-01-01 under grant agreement 101070028
(REXASI-PRO) and by TED2021-129438B-I00 / AEI/10.13039/501100011033 / Unión
Europea NextGenerationEU/PRTR.

## References

  * [1] Arrieta, A.B., Díaz-Rodríguez, N., Del Ser, J., Bennetot, A., Tabik, S., Barbado, A., Garcia, S., Gil-Lopez, S., Molina, D., Benjamins, R., et al.: Explainable artificial intelligence (xai): Concepts, taxonomies, opportunities and challenges toward responsible ai. In: 2019 IEEE international conference on systems, man and cybernetics (SMC). pp. 4184–4191. IEEE (2020)
  * [2] Barrera-Vicent, A., Paluzo-Hidalgo, E., Gutiérrez-Naranjo, M.A.: The metric-aware kernel-width choice for lime. In: Longo, L. (ed.) Joint Proceedings of the xAI-2023 Late-breaking Work, Demos and Doctoral Consortium co-located with the 1st World Conference on eXplainable Artificial Intelligence (xAI-2023), Lisbon, Portugal, July 26-28, 2023. CEUR Workshop Proceedings, vol. 3554, pp. 117–122. CEUR-WS.org (2023), https://ceur-ws.org/Vol-3554/paper21.pdf
  * [3] Bhattacharyya, A.: A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Biometrika 34(3/4), 291–302 (1943)
  * [4] Boissonnat, J.D., Chazal, F., Yvinec, M.: Geometric and Topological Inference. Cambridge Texts in Applied Mathematics, Cambridge University Press (2018)
  * [5] Brundage, e.a.: Toward trustworthy ai development: Mechanisms for supporting verifiable claims. arXiv preprint arXiv:2110.05282 (2021)
  * [6] Chandola, V., Banerjee, A., Kumar, V.: Anomaly detection: A survey. ACM Computing Surveys (CSUR) 41(3), 1–58 (2009)
  * [7] Chen, T., Guestrin, C.: Xgboost: A scalable and accurate implementation of gradient boosting. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining pp. 785–794 (2016)
  * [8] Chen, T., Guestrin, C.: Xgboost: A scalable tree boosting system. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. p. 785–794. KDD ’16, Association for Computing Machinery, New York, NY, USA (2016). https://doi.org/10.1145/2939672.2939785, https://doi.org/10.1145/2939672.2939785
  * [9] Crenshaw, K.: Demarginalizing the intersection of race and sex: A black feminist critique of antidiscrimination doctrine, feminist theory and antiracist politics. University of Chicago Legal Forum pp. 139–167 (1989)
  * [10] Diakopoulos, N.: Accountability in algorithmic decision making: A visual analysis framework. Data Society Research Institute (2016)
  * [11] Floridi, L., Taddeo, M.: Soft ethics, the governance of the digital and the general data protection regulation. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 376(2133), 20180081 (2018)
  * [12] Ganin, Y., Ustinova, E., Ajakan, H., Germain, P., Larochelle, H., Laviolette, F., Lempitsky, V.: Domain-adversarial training of neural networks. Journal of Machine Learning Research 17(1), 2096–2030 (2016)
  * [13] Gonzalez-Diaz, R., Gutiérrez-Naranjo, M.A., Paluzo-Hidalgo, E.: Topology-based representative datasets to reduce neural network training resources. Neural Computing and Applications (2022)
  * [14] Gretton, A., Borgwardt, K.M., Rasch, M.J., Schölkopf, B., Smola, A.: A kernel method for the two-sample-problem. In: Advances in neural information processing systems. pp. 513–520 (2007)
  * [15] Hardt, M., Price, E., Srebro, N.: Equality of opportunity in supervised learning. In: Advances in neural information processing systems. pp. 3315–3323 (2016)
  * [16] Huang, J., Smola, A.J., Gretton, A., Borgwardt, K.M., Schölkopf, B.: Correcting sample selection bias by unlabeled data. Advances in neural information processing systems 19, 601 (2007)
  * [17] Jobin, A., Ienca, M., Vayena, E.: Global data justice. Ethics and Information Technology 21(2), 87–96 (2019)
  * [18] Kittur, A., Chi, E.H., Suh, B.: Crowdsourcing user studies with mechanical turk. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. pp. 453–456 (2013)
  * [19] Kittur, A., Kraut, R.E.: Harnessing the wisdom of crowds in wikipedia: Quality through coordination. In: Proceedings of the 2008 ACM conference on Computer supported cooperative work. pp. 37–46 (2008)
  * [20] Kriegel, H.P., Kröger, P., Schubert, E., Zimek, A.: Outlier detection in axis-parallel subspaces of high-dimensional data. In: Proceedings of the 18th ACM conference on Information and knowledge management. pp. 555–564 (2009)
  * [21] Liang, W., Tadesse, G.A., Ho, D., Fei-Fei, L., Zaharia, M., Zhang, C., Zou, J.: Advances, challenges and opportunities in creating data for trustworthy ai. Nature Machine Intelligence 4(8), 669–677 (2022)
  * [22] Liu, Y., Zhao, Z., Guan, Y., Song, S., Cao, L., Chen, H.: Towards trustworthy ai: A cross-disciplinary survey. arXiv preprint arXiv:1907.02527 (2019)
  * [23] Mohri, M., Rostamizadeh, A., Talwalkar, A.: Foundations of machine learning. MIT press (2018)
  * [24] Mongelli, M., Ferrari, E., Muselli, M., Fermi, A.: Performance validation of vehicle platooning through intelligible analytics. IET Cyber-Physical Systems: Theory & Applications 4(2), 120–127 (2019). https://doi.org/https://doi.org/10.1049/iet-cps.2018.5055, https://ietresearch.onlinelibrary.wiley.com/doi/abs/10.1049/iet-cps.2018.5055
  * [25] Pan, S.J., Yang, Q.: A survey on transfer learning. IEEE Transactions on knowledge and data engineering 22(10), 1345–1359 (2010)
  * [26] Pedreschi, D., Ruggieri, S., Turini, F.: Discrimination-aware data mining. In: Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 560–568 (2008)
  * [27] Rahman, S.M.M.M., Davis, D.: Detecting and mitigating concept drift in an adaptive learning system for personalized news recommendation. Knowledge-Based Systems 166, 132–145 (2019)
  * [28] Rubner, Y., Tomasi, C., Guibas, L.J.: The earth mover’s distance as a metric for image retrieval. International Journal of Computer Vision 40(2), 99–121 (2000)
  * [29] Scott, D.W.: Multivariate density estimation: theory, practice, and visualization. John Wiley & Sons (2015)
  * [30] Sugiyama, M., Suzuki, T., Kanamori, T.: Density-ratio matching under the bregman divergence: a unified framework of density-ratio estimation. Annals of the Institute of Statistical Mathematics 64(5), 1009–1044 (2012)
  * [31] Wachter, S., Mittelstadt, B., Russell, C.: Counterfactual explanations without opening the black box: Automated decisions and the gdpr. In: 2017 IEEE international conference on data science and advanced analytics (DSAA). pp. 520–529. IEEE (2017)
  * [32] Widmer, G., Kubat, M.: Learning in the presence of concept drift and hidden contexts. Machine learning 23(1), 69–101 (1996)
  * [33] Zafar, M.B., Valera, I., Rodriguez, M.G., Gummadi, K.P.: Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In: Proceedings of the 26th International Conference on World Wide Web. pp. 1171–1180 (2017)
  * [34] Zemel, R., Wu, Y., Swersky, K., Pitassi, T., Dwork, C.: Learning fair representations. In: Proceedings of the 30th International Conference on Machine Learning (Vol. 28, No. 3) (2013)


# Systematic Testing of Genetic Algorithms: A Metamorphic Testing based
Approach

Janette Rounds and Upulee Kanewala  Gianforte School of Computing
Montana State University
Bozeman, Montana 59717
Email<EMAIL_ADDRESS>
Email<EMAIL_ADDRESS>
###### Abstract

Genetic Algorithms are a popular set of optimization algorithms often used to
aid software testing. However, no work has been done to apply systematic
software testing techniques to genetic algorithms because of the stochasticity
and the lack of known outputs for genetic algorithms. Statistical metamorphic
testing is a useful technique for testing programs when the output is unknown
or when the program has random elements. In this paper, we identify 17
metamorphic relations for testing a genetic algorithm and show, through
mutation testing, that these relations are more effective at finding defects
than traditional unit tests based on known outputs. We examined the failure
rates of the system-level relations when initialized with various fitness
functions. We found three relations failed excessively and we then modified
these relations so that they failed less often. We also identified some
metamorphic relations for genetic algorithms that are generalizable across
different types of evolutionary algorithms and showed that our relations had
similar mutation scores between two implementations. This is the first time
statistical metamorphic testing has been applied for testing genetic
algorithms.

###### keywords:

Metamorphic Testing , Genetic Algorithm , Differential Evolution

††journal: Journal of Systems and Software

##  1 Introduction

Genetic Algorithms are a popular optimization technique that have been used in
domains from consumer goods quality assurance [1] and modeling traffic flows
[2] to medical imaging [3] and materials science [4]. Additionally, Genetic
Algorithms are often used to optimize the parameters or structure of other
machine learning algorithms [5]. There has been a significant amount of work
done on using genetic algorithms to test software [6, 7, 8] especially on
using genetic algorithms in mutation testing. However, there is nothing in the
literature about testing the genetic algorithms themselves even though they
are often used for critical applications such as those mentioned above. This
is especially problematic given that genetic algorithm’s are being used as a
tool to help medical diagnoses [9, 10] and in other high-stakes situations.

There has been little work on testing machine learning algorithms in general
[11]. The reasons why so little work has been done in this area are myriad.
The first reason is that most machine learning algorithms incorporate at least
one random element. Random elements are challenging to test because the same
input can produce different results [12].

Furthermore, the correct answer is often unknown. For example, a person can
design a genetic algorithm to optimize land zoning subject to multiple
constraints [13]. In that instance, if the true answer was known, the land
would already have been zoned. If the true answer is in fact known, like many
of the optimization problems we discuss here, the true answer and the answer a
genetic algorithm returns may not match, even if the genetic algorithm is
correct. For example, in the Ackley’s function which we discuss later in this
paper, a genetic algorithm may not find the true global minimum for the
function at (0,…,0) for a number of dimensions. Instead the genetic algorithm
may find one of the many local minima for the Ackleys function and return this
value. Although this local minimum may not be the true answer, the genetic
algorithm still may be correct.

Genetic algorithms are useful tools for approximation. However, they tend not
to return exact answers, but an approximation of a good answer. If a genetic
algorithm returned an exact and correct answer for a problem in which the
answer was known, especially if it returned the same answer several times, we
would probably suspect the genetic algorithm of having a coding error.

To test genetic algorithms we can use a testing technique called metamorphic
testing, first proposed by Chen et. al. [14]. Metamorphic testing involves
defining properties by which we can relate two or more outputs from an
algorithm based on the input. If the outputs of two related inputs do not
follow the property, there is an error in the program under test. Statistical
metamorphic testing [12] is a useful technique when the program under test has
random elements. Instead of an initial and follow-up test case, statistical
metamorphic testing uses an initial and follow-up sample, which is then tested
using statistical hypothesis testing.

We identified 17 metamorphic relations from the literature on genetic
algorithms. We then used mutation testing to demonstrate the effectiveness of
the various relations on two different implementations. We also demonstrated
the effectiveness of three of these relations on two different differential
evolution implementations. We found that traditional deterministic unit tests
were not as effective at finding mutations as metamorphic relations, and that
system-level relations and unit-level relations perform well on different
parts of the genetic algorithm. We also found that our three relations for
differential evolution performed as well or better than the twelve relations
for genetic algorithms.

The rest of this paper is organized as follows: Section 2 contains related
work and background on metamorphic testing, genetic algorithms, and mutation
testing. In Section 3, we discuss our implementation of a genetic algorithm.
In Section 4, we identify 17 metamorphic relations, five for fitness
functions, three for genetic algorithm operators, and nine system-level level
relations. In Section 5, we lay out several experiments we conducted. Finally,
Section 6 contains our conclusions and future work.

##  2 Background and Related Work

Genetic algorithms are often used in software testing. The most common uses of
genetic algorithms are in test case generation [15], multi-objective test case
generation [16], test case prioritization [17], and mutation testing [8].
There has been no work published in the literature on how to test genetic
algorithms. However, Arcuri and Briand [18] state that many randomized
algorithms (like a genetic algorithm) are used in software applications.
Additionally, Arcuri and Briand argue for the use of statistical testing in
software applications that use random algorithms.

Metamorphic testing is a testing technique used when the algorithm is non-
deterministic and/or when there is no way to determine the correct output
[14]. To conduct metamorphic testing, first one defines a metamorphic relation
(or a set of metamorphic relations) for the program under test. A metamorphic
relation is a property by which we can relate two outputs based on the input.
Then, tests are defined for each metamorphic relation. Each test consists of
an initial test case and a follow-up test case based on the metamorphic
relation. Tests are then executed on the program under test. The output of the
initial and follow-up test cases are evaluated to determine if the text cases
follow the metamorphic relation.

When the algorithm is stochastic, one cannot simply check if the result of the
follow-up test is equal to the expected value. The result may be close, but
because of the stochasticity, the result will not be exactly equal. Therefore,
statistical tests are applied to determine whether the difference between the
expected output and the actual output is statistically significant. This is
called statistical a relationship between two samples, an initial and a
follow-up test sample, is specified, usually taking the form of null and
alternative hypotheses. The output of the program generates the samples and is
compared using statistical hypothesis testing.

Genetic Algorithms all consist of an encoding of potential solutions as
chromosomes, e.g. a bit string, and a fitness function [19], which is a
function that evaluates each potential solution and returns a value based on
that evaluation. A generic genetic algorithm has a population of properly
encoded potential solutions which is usually randomly generated, and a
randomized way or ways to change potential solutions to see if the fitness of
that solution improves. Unfit solutions are removed from the population.

Testing a genetic algorithm presents several problems. Genetic algorithms are
randomized algorithms. Each time the genetic algorithm is run, the output of
the algorithm will be different. There is also no way to determine the
”correct” output of a genetic algorithm. In many cases, if the target output
of a genetic algorithm is known, there is often no reason to use a genetic
algorithm at all. Furthermore, if the data provided to the genetic algorithm
is misleading in some way, the output of the genetic algorithm will not match
the desired output. Thus, testing approaches that require one to compare an
output against a true answer will not work for testing a genetic algorithm.

In this paper, we use several problems where the correct answer is already
known in order to demonstrate the process of testing a genetic algorithm.
However, we also provide ways to expand the testing process in the case where
the target answer is unknown.

There has been no published research on how to test genetic algorithms.
However, Xie et al. [20] defined several possible metamorphic relations to use
when testing a machine learning classifier. In machine learning,
classification is the problem of delineating decision boundaries so that all
examples inside of a boundary are of one class. Genetic algorithms have been
shown to be effective classifiers in a multitude of cases [21, 22]. Xie et al.
[20] demonstrated how to test two other machine learning methods, the
k-Nearest Neighbor and the Naive Bayes Classifiers, using metamorphic testing.
Xie et al. also defined several possible metamorphic relations to use when
testing a machine learning classifier. These authors showed that metamorphic
testing is an effective way to test machine learning classifiers. However,
they only tested this approach on WEKA [23], an open source tool for
performing classification, regression and other data mining tasks.

Shin Yoo [24] showed how one could use metamorphic testing to validate a
machine learning approach, called simulated annealing, to an optimization
problem. Optimization problems consist of an objective function, $f(x)$ that
we must either minimize or maximize subject to constraints. Shin Yoo showed
that metamorphic relations can be an effective way to test machine learning
approaches to optimization problems, especially for certain kinds of faults.
Genetic algorithms are another way to approach an optimization problem.

Murphy et.al. [25] showed how an automated metamorphic testing framework can
be used to test support vector machines, decision trees, and ranking
algorithms. The most complex algorithm tested by Murphy et. al. is the
MartiRank algorithm. This algorithm is a type of ensemble method that divides
the data into a series of sub-lists which it then orders according to the
”quality” of the features, similar to a fitness function, except that it is
iteration dependent. At each iteration, the model describes how to divide the
data into lists and updates the quality measure. When all the rankings are
completed, the algorithm reconstructs a final ranking based on the divisions
and quality measures of previous iterations. Murphy et. al. designed an
automated metamorphic testing system to improve the speed at which metamorphic
tests can be developed.

None of these papers test very complicated algorithms. The most complex of
these is the MartiRank algorithm, which is based on a series of simple ranking
algorithms. Genetic algorithms involve many more random components than even
the most complex algorithm tested to date. In addition, Murphy et. al. and Xie
et. al. used the Weka [23] implementation of these algorithms. There is no
Weka implementation for a genetic algorithm. All of this means that there is a
great need for testing genetic algorithms thoroughly and until now there has
been no established way to accomplish this task.

In order to demonstrate the effectiveness of the testing approach outlined in
this paper, we will use mutation testing. Mutation testing is technique that
has been shown to be effective for comparing testing techniques [26]. The
first step in mutation testing is to generate a number of mutants, given the
source code to the program under test. These mutants are identical to the
program under test except that one line has been changed. Next, the test set
is run on each mutant. If the test set detects the changed line (in other
words, if at least one test fails with the changed line where the test passed
without the line being changed), the mutant is said to have been ’killed’. If
the test set does not detect the changed line, the mutant is said to have
’survived’. Compilation and run-time errors and tests that time out are
considered ’killed’ as well. Then, the number of killed mutants is counted and
is divided by the total number of mutants. This gives a mutation score. A
perfect mutation score would be 1, or all of the mutants detected by the test
set. However, a perfect mutation score is usually impossible. Consider the
example of a for loop in a Java program.

⬇

for(int i = 0; i < 10; i++){}

If the code above is the original program and the following is the mutant:

⬇

for(int i = 0; i != 10; i++){}

there would be no way to detect the mutant as it would be functionally
equivalent to the original program. However, most mutants would not be
functionally equivalent and could be detected by the test set, if an
appropriate test exists. Therefore, the goal of mutation testing is to get the
mutation score as close to 1 as is possible by changing tests so that they
detect more mutants. In this paper, we compare the mutation score of different
types of tests in order to determine which tests detect the most number of
faults.

##  3 Genetic Algorithm Implementation

Most often genetic algorithms used in classification are included as part of a
larger solution. For example, a common use of genetic algorithms is to train
the weights of a neural network. Genetic algorithms in an optimization context
usually do not use any other algorithms. Additionally, it is trivial to turn a
minimization problem into a maximization problem. This is important for the
future generalization of the testing technique we develop here. Therefore we
implemented a genetic algorithm that optimizes a function.

Input : $popSize$, $killRate$, $mutRate$, $\delta$, $maxGen$

Output : the best solution from $P_{t}$

Randomly initialize population $(P_{0})$;

Evaluate fitness for $P_{0}$;

while  _$t <maxGen$ and best fitness $>\delta$_ do

$Child_{t}$ = selection $P_{t-1}$;

$Child_{t}^{\prime}$ = crossover $Child_{t}$;

$Child_{t}^{\prime\prime}$ = mutate $Child_{t}^{\prime}$;

Evaluate fitness for $Child_{t}^{\prime\prime}$;

$P_{t}=$ replace $P_{t-1},Child_{t}^{\prime\prime}$;

$t+=1$;

end while

Algorithm 1 Genetic Algorithm

A typical example of a genetic algorithm can be seen in Algorithm 1. The
generic genetic algorithm takes as input a fitness function, a population size
and a fraction of the population to be replaced at each time step, a mutation
rate and a fitness threshold [19]. The output will be a set of real numbers
that produce the “best” output of the fitness function. The first step is to
randomly initialize potential solutions, and then evaluate the fitness of each
potential solutions. Then while the termination criteria are unmet, a number
of potential solutions are selected from the population, recombined to form
children and then mutated. Selection, crossover (also called recombination),
and mutation are considered the operators for the genetic algorithm. Then each
child’s fitness is evaluated and some number in the original population will
be replaced by the child.

Our genetic algorithm uses uniform crossover with 2 parents and fitness
proportionate selection. Fitness proportionate selection associates a
probability of selection with a particular individual in the population [27].
If $fit_{t}$ is the fitness of individual $t$, the probability of selection is

$p_{t}=\frac{fit_{t}}{\sum_{j=1}^{N}fit_{j}}$

where $N$ is the number of individuals in the population. Fitness
proportionate selection tends to be relatively slow [28] and has a risk of
slow convergence [19]. Uniform crossover allows parents to contribute
individual genes to a child individual rather than sequences of genes. This
eliminates positional bias [19] which was necessary as positional bias could
interfere with certain metamorphic relations. The probability that a parent
will contribute a particular gene to the child is $p_{t}=\frac{1}{a}$ where
$a$ represents the number of parents.

When designing a genetic algorithm for optimization, if there is a single
objective function and no constraints, creating a fitness function is very
simple. We simply use the objective function itself as a measure of fitness.
It is also trivial to regularize the output. In this project we will test both
stochastic and deterministic objective functions.

In addition to implementing our own Genetic Algorithm, we contacted Strasser
et.al. [29] who allowed us to use their Factored Evolutionary Algorithms
framework (FEA framework) as an additional implementation to test.

###  3.1 Differential Evolution

Differential Evolution (DE) is another evolutionary algorithm that was
designed for continuous spaces. DE centers around creating offspring by
conducting crossover on parents and what is known as a “trial vector” [30]. A
trial vector is similar to the child concept in genetic algorithms. A trial
vector is generated by choosing 3 individuals – call them $x_{i}(t)$,
$x_{2}(t)$, and $x_{3}(t)$ – from the population, without replacement, where
$x_{2}$, and $x_{3}$ are randomly selected. The trial vector, $u_{i}$, is then

$u_{i}(t)=x_{i}(t)+\beta(x_{2}(t)-x_{3}(t))$ (1)

The subtraction term generates what is known as a “difference vector”, where
the $beta$ multiplier is some user-defined positive number. Crossover then
combines $x_{i}(t)$ and $u_{i}(t)$ into an offspring, which has the effect of
“pushing” $x_{i}$ in a particular direction in the search space. There are
multiple forms this crossover can take; we chose to implement binomial
crossover, which is similar to uniform crossover in a genetic algorithm.

Because of the representation of our chromosomes, we used binomial crossover.
We used a single difference vector, and to select the target vector we used
random selection. As such our differential evolution algorithm could be
described as $DE/random/1/binomial$. We implemented differential evolution
ourselves and used the differential evolution algorithm from the FEA
framework.

###  3.2 Test Problems

There are a variety of established test problems used in order to assess the
ability of the genetic algorithm to optimize. For the purposes of this
project, we wanted problems that were continuous and scalable to more than
three dimensions. Differential evolution operates almost exclusively in
continuous spaces. Although the current genetic algorithm will be able to
optimize in discrete and categorical spaces, we wanted problems that would
also work for the differential evolution algorithm. We need problems that are
scalable to more than three dimensions because most real-world problems in
machine learning have feature spaces (or numbers of dimensions) much greater
than three.

We ran the genetic algorithm on a variety of problems in order to show how the
metamorphic relations would change, or remain constant depending on the
problem. To that end, we wanted at least one random function. We also wanted
at least one function with multiple local minima, because local minima have a
tendency to ”trap” genetic algorithms. For this project, we selected three
test problems from the literature [31], Ackleys function, the Quartic
function, and the Rosenbrock function. Ackleys function is a continuous,
deterministic, scalable function that has multiple local minima. This function
fulfills our requirement for a function with multiple local minima.

$f(x_{1},...,x_{D})=-20*e^{-0.2\sqrt{\frac{1}{D}\sum_{i=1}^{D}x_{i}^{2}}}-e^{\frac{1}{D}\sum_{i=1}^{D}cos(2\pi*x_{i})}+20+e$
(2)

The Quartic function is a continuous, scalable, stochastic function that,
because of the random element, may or may not have local minima. This function
fulfills our requirement for a random function.

$f(x_{1},...,x_{D})=\sum_{i=1}^{D}i*x_{i}^{4}+random[0,1)$ (3)

The Rosenbrock function is a continuous, deterministic, scalable function with
a single minimum. This function has neither a random element, nor multiple
local minima. This means it is a useful function for comparisons against both
the Quartic and Ackleys functions.

$f(x_{1},...,x_{D})=\sum_{i=1}^{D-1}\big{(}100(x_{i+1}-x_{i}^{2})^{2}+(x_{i}-1)^{2}\big{)}$
(4)

Class | LOC | # of tests | # of trad. tests | # of MRs
---|---|---|---|---
Chromosome | 22 | 3 | 2 | 1
Fitness Function | 14 | 1 | 0 | 1
Ackleys | 17 | 7 | 5 | 2
Quartic | 11 | 6 | 3 | 3
Rosenbrock | 18 | 6 | 5 | 1
Genetic Algorithm | 112 | 14 | 5 | 9
Differential Evolution | 82 | 5 | 2 | 3
Total | 271 | 42 | 22 | 20
Total without DE | 189 | 37 | 20 | 17
Table 1: Lines of code, number of tests written, number of deterministic tests
and number of tests written using metamorphic relations.

The genetic algorithm we implemented is organized as follows: We used three
fitness functions in this work, Ackleys, Quartic and Rosenbrock functions. The
Chromosome class encapsulates a potential solution to a particular problem.
The Genetic Algorithm class is the biggest class by far. It contains a list of
Chromosomes which represent the population. It also contains all the operators
for the Genetic Algorithm, a multitude of getters and setters, and the genetic
algorithm itself, modeled on the genetic algorithm we outlined in Algorithm 1.

The Differential Evolution class is similar to the Genetic Algorithm class.
For most analyses, the Differential Evolution class was not included.

The FEA framework is a much bigger program, containing over 5000 lines of
code. For comparison, our implementation used only 271 lines of code. However,
much of the FEA framework code implements other algorithms such as Particle
Swarm Optimization or other test problems such as the Rastrigrin Function. The
lines of code directly relating the the genetic algorithm, the differential
evolution algorithm or the three fitness functions only amounts to 245 lines
of code. The FEA framework can be loosely organized into the genetic
algorithm, the fitness functions and the differential evolution algorithm.

##  4 Metamorphic Relations

In this section we lay out 17 metamorphic relations. Three of these relations
also applied to differential evolution.

###  4.1 Metamorphic Relations for Fitness Functions

The fitness functions are very different from the rest of the genetic
algorithm because we do have the true answers for two of the functions. For
Ackleys function, the minimum output is 0, and this occurs when the input is
(0,0,…,0) for all dimensions. The maximum value of Ackleys function is
approximately 22.3. Since there are many peaks in Ackleys function, there are
many different sets of inputs that could reach this value. In two dimensions,
one of those input sets is at (-21.6, 31.5) when the number of dimensions is
2. For the Rosenbrock function, the minimum output is 0. This occurs when the
input is (1,1,…,1) for all dimensions. The maximum output is approximately
$8.6490961*10^{7}$. These values were tested using deterministic unit tests.

##### Relation 1.1

Unit tests for the Quartic function were tested using metamorphic relations.
Since the Quartic function adds a random number $\in[0,1)$ for each dimension,
we do not know what the exact value of the Quartic function will be. However,
we do know that the minimum value without the random numbers would be 0. We
also know that the random numbers will all be strictly less than 1. Therefore,
we know that the minimum value $MV$ for the Quartic function will be $0\leq
MV<d$ where $d$ is the number of dimensions. In certain circumstances, other
inputs will cause the output to be in this range. The follow up test will be
$(d-1)$ 0’s and the last input value is 1. This input will produce a result
always larger than $(d)$ 0’s. As an example, in 4 dimensions, the initial test
case would be (0,0,0,0) and the follow-up test case would be (0,0,0,1). With
these inputs, the output from the initial test case would always be less than
the output from the follow-up test case.

##### Relation 1.2

The maximum value the Quartic function would take if the random elements were
not added is $2.68435456*\frac{d(d+1)}{2}$. This happens at (1.28, 1.28, …,
1.28), or (-1.28, -1.28, …, -1.28) for all dimensions. The random number
generator includes 0, so the maximum value is always greater than or equal to
this number. Since there are $d$ random numbers added, and the random numbers
are pulled from a uniform distribution, the mean maximum value will be
$2.68435456*\frac{d(d+1)}{2}+\frac{d}{2}$ and the variance is $\frac{d}{12}$.
For this test, since we have fairly complete knowledge of the distribution, we
could have used simple statistical tests. However, we used statistical
metamorphic testing [12] because it is not always possible to know the
distribution of the fitness function. To perform the statistical metamorphic
tests, we generated two samples, each with 20 observations, by running the
Quartic function on the input (1.28, 1.28, …, 1.28) 20 times for each sample
(e.g (1.28, 1.28) for 2 dimensions) and recording the output of the function.
Our null hypothesis was that the mean of the two samples would not be equal to
each other. Our alternative hypothesis was that the means would be equal to
each other.

##### Relation 1.3

One of the metamorphic relations often mentioned is changing the order of the
attributes [20]. For Ackleys function, this is a valid metamorphic relation
that we use in the testing process. As an example, an initial input of (6.4,
2.5, 1.25) and a follow-up input of (1.25, 2.5, 1.28) will both produce an
output of 13.24197384. However, for the Quartic function and the Rosenbrock
function, this is invalid. Consider the following example for the Quartic
function in 3 dimensions. The first input is (0.25, 0.5, 1.28). This produces
a result of 9.94196993. The second input is (1.28, 0.5, 0.25). As you can see,
only the order changes between the two inputs. However, the output for the
second input is 4.64107331, less than half the output of the first example.

##### Relation 1.4

Another metamorphic relation for the Quartic and Rosenbrock functions is to
compare the maximum output of the fitness functions given some potential
solution inside of the range of expected values, given some potential solution
outside of the range of expected values, and finally the first solution again.
The fitness function class will adjust the maximum output if some solution
produces a higher output than is currently the case. This happens so that we
do not get a fitness greater than the maximum fitness. The fitness should
change between the first and the last test, and the fitness of the first test
should be higher. This does not apply to the Ackleys function because the
values outside the range of expected values are not necessarily higher or
lower than those inside the range. Again, we used statistical metamorphic
testing in this relation. We generated 2 samples, each with 20 observations.
The initial sample was generated by feeding the maximum input (e.g. (30, 30,
30) for 3 dimensions in the Rosenbrock function) into the function 20 times.
Next we ran the function with a single input that was larger than the maximum
input (e.g. (80, 80, 80) in 3 dimensions for the Rosenbrock function).
Finally, we generated the follow-up sample by running the function on the same
input as the initial sample. Our null hypothesis was that the mean of the two
samples would be equal to each other, while our alternative hypothesis was
that the mean of the initial sample would be greater than the mean of the
follow-up sample.

##### Relation 1.5

Since all of our fitness functions can generalize to more than three
dimensions, another metamorphic relation for the fitness functions is to
create a fitness function object for two dimensions and input a good solution
in two dimensions, say (1,1) for the Rosenbrock function. The follow-up test
would be to create a fitness function object for greater than two dimensions
and input the same good solution, simply with more dimensions, e.g. (1,1,1,1)
for the Rosenbrock function. The scaled fitness for the test and the follow-up
test will be the same.

###  4.2 Metamorphic relations for genetic algorithm operators

####  4.2.1 Metamorphic relations for mutation

##### Relation 2.1

Let us assume that the mutation rate is 1. Let us also assume that we have a
solution with $m$ dimensions. We then run our mutation operator on our
solution. Each observation of a value in the mutated solution will be
different from the corresponding un-mutated observation by some amount. This
amount will be greater than or equal to 0 and less than 0.1. The average
amount will be 0.05. An example input initial test case would be the randomly
generated solution (3, 27, 6, 14, 30, 16, 1, 16, 10, 29) for 10 dimensions. We
then run the mutation operator, with the mutation rate set to 0.1 on this
solution and record the difference between the input and the output. The
follow-up test case would use another randomly generated solution with the
mutation operator set to 0.9 and the difference between the input and output
of the mutation operator would be recorded. Our null hypothesis was that the
mean difference between the input and output for the two test cases would be
equal. Our alternative hypothesis was that the mean difference for the follow-
up test case when the mutation rate was set to 0.9 would be greater than the
mean difference for the initial test case.

####  4.2.2 Metamorphic relations for crossover

##### Relation 2.2

The crossover operator takes as input a set of ’parent’ solutions $parents$
and outputs a ’child’ solution that is a combination of elements of the parent
solutions. For each dimension in the solution, the probability that the parent
will contribute their value for that dimension is $\frac{1}{|parents|}$. Given
a set of parents that are unique (i.e. no common elements between the
parents), we can determine which element of the child solution came from which
parent. This relation also used statistical metamorphic testing. With parents
(1,2,3,4) and (5,6,7,8), our initial test case would set the crossover rate to
0.5 and run the crossover operator 20 times, generating 20 children. The
follow-up test case would set the crossover rate to 1 and again generate 20
children. We would then calculate the proportion of elements in each child
that came from the first parent. Our null hypothesis was that the average
proportion for the initial sample would be equal to the average proportion for
the follow-up sample. Our alternative hypothesis was that the average
proportion for the initial sample would be greater than the average proportion
for the follow-up sample. This metamorphic relation also applies to
Differential Evolution.

####  4.2.3 Metamorphic relations for selection

Our implementation of the genetic algorithm uses fitness proportionate
selection. This means that each solution’s fitness is scaled by the total
fitness of the population. These scaled fitnesses all add up to 1. More
specifically, this algorithm uses roulette wheel selection. This means that we
create a scaled fitness vector, and we select a potential solution based on
these scaled fitness vectors. Smaller fitness values are more likely to be
selected, but in order to maintain diversity in our population of solutions,
there must be some chance that solutions with higher fitness can be selected.

##### Relation 2.3

This metamorphic relation involves running the selection operator several
times on two populations, one that contains several copies of the ideal
solution, and one that does not but is identical in every other way. For an
example with the Rosenbrock fitness function and 2 dimensions, our initial
test case might have the individuals (2,3), (5,10), (27, 8), (17, 11), and
(29, 2). The follow-up test case might have the individuals (3,4), (5,10),
(17,11), (1,1), and (1,1). The average fitness for the initial test case would
be worse than the average fitness for the follow-up test case. If the ideal
solution is unknown, a good solution, as determined by the fitness function,
could be used instead of the ideal solution.

###  4.3 System-level metamorphic relations

##### Relation 3.1

The number of generations we allow the genetic algorithm to run is a crucial
parameter. If we increase the number of generations, the average fitness will
improve, unless the fitness threshold is reached, and the algorithm exits
early. One way to prevent the early exit is to select a test problem that has
many local optima so as to prevent early convergence, such as the Ackley’s
function. An example initial test case is setting the number of generations to
50. An example follow-up test case would be setting the number of generations
to 5000. This relation applies to Differential Evolution.

##### Relation 3.2

Another crucial parameter is the population size. As the population size
increases, the average fitness will also improve. This is because with
increased individuals in the population, we increase the chance that one of
those individuals will encounter the true solution. For an initial test case,
we used a population size of 5. The population size for the follow-up test
case was 500. The average fitness for the follow-up test case will be better
(lower) than the average fitness for the initial test case. Interestingly, for
Differential Evolution smaller population sizes improve average fitness more
than larger population sizes (assuming some low number of iterations and/or a
problem with many local minima). This could be because the decreased diversity
of the population leads to a faster decrease in fitness. Alternatively, there
could be an interaction between the population size and another important
parameter, $\beta$ that influences the ideal size of the population. We used
the same initial and follow-up test cases for differential evolution. The
average fitness for the follow-up test case will be worse (larger) than the
average fitness for the initial test case.

##### Relation 3.3

Finally, if we increase the threshold parameter, the average fitness will be
worse, but the average number of iterations run by the algorithm will
decrease. This is because when the threshold is set at a higher value the
algorithm reaches the threshold relatively quickly and exits. When the
threshold is set at a lower value, the algorithm continues searching until it
reaches the lower value, so the fitness will be lower (better). Our initial
test case was 0.5 and our follow-up test case was 0.05. The average fitness
for the initial test case was greater than the average fitness for the follow-
up test case. The average number of iterations run for the initial test case
was less than the average number of iterations run for the follow-up test
case.

Figure 1: Fitness for the best solution at each iteration when the parameters
are varied. When fitness decreases, the solution is improving.

The other two parameters, mutation rate and replacement rate, are much more
difficult to define relations for. In Differential Evolution, $\beta$ and the
crossover rate can be seen as approximate substitutions for mutation and
replacement rates. As you can see from Figure 1, when both of these parameters
are at 0, we will see no improvement in total fitness in the population over
the generations. As we increase the parameters, we will see improvements in
the total fitness and the best fitness will be reached in fewer iterations. At
a certain point, total fitness will oscillate. If the oscillations are small,
we should still see convergence towards our ideal solution. However, these
oscillations, no matter how small, will lead to a greater number of
generations needed to find the ideal solution. This point where total fitness
begins to oscillate is not easily identifiable and is thought to depend on the
problem. We can see that in this instance, unstable oscillations occur when
the mutation rate is at 0.8 and the replacement rate is at 2. When the
unstable oscillations occur, overall fitness increases rather than decreasing.
It is unclear how the mutation rate and replacement rate interact to speed or
slow the rates of convergence towards the best solution in general. However,
we can still define some metamorphic relations for mutation rate and
replacement rate.

##### Relation 3.4

When both parameters are at 0, the average fitness will be worse than if both
parameters are at 0.5. This is because the final solution depends only on the
randomly initialized potential solutions, rather than the changes made to
those solutions. This applies to crossover and $\beta$ in Differential
Evolution.

##### Relation 3.5

On the other hand, if both parameters at 1 the average fitness does not follow
the same behavior. We think this is because each time mutation happens, the
solution will only change by a small amount. Recombination never adds new
solutions. Thus each solution is only being changed by a small amount. It is
possible that the mutation operator can be changed so that setting both
parameters equal to 1 will be roughly equivalent to a random search. This
relation was tested in section 5.4, but was not tested in the remainder of the
experiments.

##### Relation 3.6

If we hold mutation rate constant at 0, and increase the replacement rate to
0.5, the average fitness of the best solution in the population will be better
than when both mutation rate and replacement rate are at 0. Performing
Relation 3.6 with mutation and replacement rate switched, however, does not
produce the same results. This is because mutation happens only when a
potential solution is selected, so the mutation rate depends on the selection
rate.

##### Relation 3.7

If however, we hold the recombination rate constant at some low number, say
0.1, and set the mutation rate at 0 and 0.5, for example, the average fitness
for the best solution will be better when the mutation rate is at 0.5 than
when the mutation rate is set at 0.

##### Relation 3.8

For this reason, the common wisdom in the genetic algorithm literature is that
mutation rate should be set lower than the replacement rate [32]. If this
common wisdom holds, one metamorphic relation for mutation is to run the whole
algorithm when the parameters follow this common wisdom, and then run the
algorithm again when the values for the parameters are swapped. The average
fitness for the best solution when the parameters follows this common wisdom
should be better than when the parameters do not follow this common wisdom.
However, when the values are 0.1 and 0.8, this is not the case. Much of the
time, the swapped parameters (i.e. the mutation rate set higher than the
replacement rate), performed better than the parameters that followed the
common wisdom. This high rate of failure is one reason this test was not used
in the analyses, other than in section 5.4.

##### Relation 3.9

On the other hand, we can test this type of interaction between the
replacement and mutation rates by using the values 0 and any other number
strictly greater than 0 and less than or equal to 1. In that case, the
algorithm should behave like Relation 3.6 with the parameters switched. In
other words, the average best fitness for this algorithm will be no better
than when both parameters are set at 0.

###  4.4 Deterministic unit tests

We implemented several unit tests for both the genetic algorithm and
differential evolution that did not use metamorphic relations. These relations
included testing initialization, selecting the best chromosome from the
population, that fitness is changed when the update fitness function was
called, and checking constant and known values. These were used for
comparisons against the metamorphic relations. The scope of these
deterministic tests is limited, but testing many parts of a genetic algorithm
is difficult, if not impossible, without metamorphic testing.

##  5 Experiments

In order to conduct mutation testing, we used the PIT mutation testing tool
[33]. Although the PIT tool does not include source code of the mutants, it
does include the line number where the mutation happened and the type of
mutation (e.g. negated conditional, replaced addition with subtraction). PIT
reports each mutant that survived, was killed, timed out or was not covered
for each class. For each test, 182 mutants were generated. PIT uses Line
coverage to assess mutants not covered by test cases. The PIT mutation tool
generates the following types of mutants:

  * 1.

Replaced operator ($+,-,*,/$) with another operator.

  * 2.

Changed conditional boundary.

  * 3.

Negated conditional.

  * 4.

Changed increment.

  * 5.

Mutated return value.

  * 6.

Removed call to other function.

Unless otherwise specified by the metamorphic relation, the parameters for the
genetic algorithm were as follows:

  * 1.

$popSize=50$.

  * 2.

$mutRate=0.1$.

  * 3.

$killRate=0.4$.

  * 4.

$\delta=0$.

  * 5.

$maxGen=1000$.

Statements | Total | Deterministic | Total | Function | System | Total
---|---|---|---|---|---|---
Covered | Tests | Tests | MRs | Level MRs | Level MRs | Lines
Our Implementation | 243 | 87 | 169 | 136 | 165 | 194
FEA Framework | 125 | 119 | 125 | 124 | 125 | 245
Table 2: Statement Coverage for each set of tests, reported as a ratio between
lines of code covered over total lines of code, leaving aside the differential

###  5.1 Overall results

Relation 2.3 detected a fault in our original implementation of the genetic
algorithm. The fault in the selection function occurred because we were
prioritizing higher fitness, rather than lower fitness. Once we had fixed this
error, we generated mutation scores for all types of tests. As shown in Table
3, the overall mutation score is 85% for all the tests written. Several
classes received a mutation score of 100%. The vast majority of mutants that
were not killed were due to there being no coverage, or tests, for the code
that was changed (44 of the 59 mutants that were not killed). This is a
problem that can be easily remedied with more tests.

| All Tests | Deterministic Tests | All Relations
---|---|---|---
Genetic | 90/117 | 20/117 | 90/117
Algorithm | 77% | 17% | 77%
Chromosome | 14/15 | 8/15 | 11/15
| 93% | 53% | 73%
Fitness | 9/11 | 5/11 | 7/11
Function | 81% | 46% | 64%
Ackleys | 13/14 | 11/14 | 12/14
Function | 93% | 79% | 86%
Quartic | 8/8 | 0/8 | 8/8
Function | 100% | 0% | 100%
Rosenbrock | 18/18 | 16/18 | 18/18
Function | 100% | 89% | 100%
Combined | 104/132 | 28/132 | 101/132
Gen. Algo. | 79% | 21% | 77%
Combined | 48/51 | 32/51 | 45/51
Fit. Func. | 94% | 63% | 88%
Total | 152/182 | 60/182 | 147/182
| 84% | 33% | 81%
Table 3: Mutation scores for the genetic algorithm implementation comparing
deterministic tests and all tests involving metamorphic relations. We report
totals by class and then totals for the all classes with Genetic Algorithm
components (Genetic Algorithm and Chromosome) and all classes for fitness
function components (Fitness Function, Ackleys Function, Quartic Function, and
Rosenbrock Function)

###  5.2 Deterministic and Metamorphic Comparison

We next divided the tests into deterministic and metamorphic tests. All tests
were run again and the mutation score was calculated for each type of test.
For the deterministic tests, the mutation score was 33%, as seen in Table 3.
This is quite low, due at least in part to not being able to test the random
elements of the genetic algorithm. The mutation score for metamorphic testing
was 81%. Part of the reason for the big disparity was potentially due to the
fact that we have identified two different types of metamorphic tests,
function-level and system-level metamorphic relations.

| All Relations | Function-Level | System-Level
---|---|---|---
Genetic | 90/117 | 48/117 | 74/117
Algorithm | 77% | 41% | 64%
Chromosome | 11/15 | 11/15 | 11/15
| 73% | 73% | 73%
Fitness | 7/11 | 7/11 | 6/11
Function | 64% | 64% | 55%
Ackleys | 12/14 | 12/14 | 8/14
Function | 86% | 86% | 57%
Quartic | 8/8 | 8/8 | 8/8
Function | 100% | 100% | 100%
Rosenbrock | 18/18 | 18/18 | 7/18
Function | 100% | 100% | 39%
Combined | 101/132 | 59/132 | 85/132
Gen. Algo. | 77% | 45% | 64%
Combined | 45/51 | 45/51 | 29/51
Fit. Func. | 88% | 88% | 57%
Total | 147/182 | 104/182 | 114/182
| 81% | 57% | 63%
Table 4: Mutation scores for the genetic algorithm implementation comparing
function-level and system-level tests. We report totals by class and then
totals for the all classes with Genetic Algorithm components (Genetic
Algorithm and Chromosome) and all classes for fitness function components
(Fitness Function, Ackleys Function, Quartic Function, and Rosenbrock
Function)

###  5.3 System-level and Function-level comparison

Since the deterministic tests were implemented only at the function level and
there were no system-level deterministic tests, we divided the metamorphic
relations into system-level and function level tests. The mutation score for
the function level metamorphic relations was 0.577, from Table 4. This was
higher than the deterministic tests. We were originally concerned that this
was due to differences in coverage of the different types of tests. However if
we approximate a normalization by dividing the number of mutants killed by the
lines of code covered, we see that the deterministic tests only scored 0.588,
while the function level metamorphic relations obtained a score of 0.772 (the
best possible score would be 1.055). This means that the deterministic tests
had a lower mutation score, even when measured relative to statement coverage.
The mutation score for the system-level relations was even higher than for the
function-level relations, at 0.648. Most of what is driving that number is the
higher coverage for the genetic algorithm class. As you can see in Table 4,
when separated out by class, the whole algorithm relations had a mutation
score of 0.638 for the Genetic Algorithm class, while the function-level
relations only had a mutation score of 0.414. On every other class, the
function-level relations had higher mutation scores.

###  5.4 System-level Tests with Different Fitness Functions

Finally, we examined the failure rates of the whole algorithm tests. We
expected that some small number of tests would fail if the tests were run a
sufficient number of times, given the nature of statistical tests. However, we
suspected we were seeing too many failures for statistical likelihood. If this
was due to an actual error in the genetic algorithm, we expected that the test
failure would be consistent. The failures we were seeing occurred
inconsistently. One potential cause of this was the fact that we were using
the Ackleys function to set up the tests for several metamorphic relations.
Ackleys function has many local optima. We hypothesize that if there were more
failures than expected, these failures were due to the Ackleys Function
getting stuck in local optima and not converging towards a global optima.

We restricted the set of tests run to the system-level metamorphic relations,
specifically to Relations 3.1, 3.2, 3.3, 3.4, 3.5, and 3.8. We ran each set of
relations ten times. We then changed the fitness functions for each relation
and ran the relations another ten times. For example, we would run Relation
3.1 ten times with Ackleys function, then ten times with the Quartic function,
and finally ten times with the Rosenbrock function. If statistical tests were
causing the failures, we expected that failure would occur less than one time
for each fitness function with each relation.

| 3.1 | 3.2 | 3.3 | 3.4 | 3.5 | 3.8
---|---|---|---|---|---|---
Ackleys | 7 | 0 | 0 | 0 | 2 | 8
Quartic | 6 | 0 | 0 | 0 | 3 | 5
Rosenbrock | 0 | 0 | 0 | 0 | 4 | 5
Table 5: Number of failures in ten runs for each relation when the fitness
function is varied

As you can see from Table 5, only 3 relations failed at all, and all the
failing relations failed much more than we would expect given a 95% confidence
interval. Relations 3.2, 3.3 and 3.4 succeeded consistently. We restricted our
further tests to Relations 3.1, 3.5 and 3.8. Relation 3.1 failed only when run
with Ackleys and Quartic functions. This fit our hypothesis that failing tests
were getting stuck in local optima. We ran this relation 20 more times with
just the Rosenbrock function and found that it did not fail in any of those
runs. However, running Relations 3.5 and 3.8 with the Rosenbrock function did
not alter the amount of failures seen. One option for Relation 3.5 was to
increase the average alteration made to each value performed by the mutation
operator, in hopes that it would improve the failure rate. However, this would
require altering Relation 2.1 to match. Instead we developed Relations 3.6 and
3.7 to substitute for this relation. Relation 3.8 was the most problematic
relation, also probably requiring a change to the mutation operator. We
identified Relation 3.9 to replace Relation 3.8. After we replaced the faulty
relations, we ran Relations 3.1, 3.2, 3.3, 3.4, 3.6, 3.7, and 3.9 another
twenty times each, and saw no more failures.

###  5.5 FEA framework

We used the same tests and relations for the FEA framework as we did for our
implementation. The authors of [29] had previously constructed 70 unit tests
for the FEA framework. All but 2 of the unit tests were irrelevant to the
genetic algorithm, fitness functions and differential evolution. As you can
see in Table 6 the whole algorithm relations achieved the highest mutation
score in the genetic algorithm classes, while the unit level relations
achieved higher mutation scores for the fitness function classes. Both types
of relation had higher mutation scores than the deterministic unit tests.
Since more deterministic tests were implemented, but the mutation scores for
the relations was higher, we can surmise that the metamorphic relations were
far more effective than the deterministic unit tests. When we compared the
results of our implementation to the FEA framework we found lower mutation
scores for the FEA framework, as seen in Table 8. This suggests that we were
possibly targeting our relations to the implementation. However, the mutation
scores for the metamorphic relations were still higher than the mutation
scores for the deterministic tests, suggesting that these relations are still
more effective at detecting errors than deterministic tests.

| Initial | All Tests | Deterministic Tests | All Relations
---|---|---|---|---
Genetic | 0/89 | 62/89 | 35/89 | 62/89
Algorithm | 0% | 70% | 39% | 70%
Fitness | 24/71 | 47/71 | 35/71 | 43/71
Functions | 33% | 66% | 49% | 60%
Total | 24/160 | 109/160 | 70/160 | 105/160
| 15% | 68% | 44% | 66%
Table 6: Mutation scores for the FEA framework comparing initial results, deterministic tests and all tests involving metamorphic relations | All Relations | Function-Level | System-Level
---|---|---|---
Genetic | 62/89 | 37/89 | 62/89
Algorithm | 70% | 42% | 70%
Fitness | 43/71 | 39/71 | 36/71
Functions | 60% | 54% | 50%
Total | 105/160 | 76/160 | 98/160
| 66% | 48% | 61%
Table 7: Mutation scores for the FEA framework comparing function-level and system-level tests. | Initial | All | Deterministic | MRs | Function MRs | System MRs
---|---|---|---|---|---|---
FEA | 15% | 68% | 44% | 66% | 48% | 61%
framework |  |  |  |  |  |
Our | 0% | 83% | 33% | 81% | 58% | 64%
impl. |  |  |  |  |  |
Table 8: Comparison between mutation scores for our implementation and the FEA
framework

###  5.6 Differential Evolution

We ran five tests from the genetic algorithm on the differential evolution
algorithm on each implementation. Two of these tests were deterministic while
the remaining three were metamoprhic relations. Tests performed much better
than expected on the differential evolution algorithm, given that all but one
of the tests was virtually identical to the genetic algorithm tests. The
mutation scores for all tests for the FEA framework implementation of
differential evolutions was 95% while for our implementation the mutation
score for all tests was 86%. This was the opposite of the genetic algorithm
tests in that the FEA framework tests performed better than the tests on our
implementation. Additionally, in the FEA framework, differential evolution
tests outperformed our implementation of the genetic algorithm in terms of
mutation score, while our implementation of the genetic algorithm slightly
outperformed our implementation of differential evolution. This increase in
performance is intriguing, although it probably can be attributed to
differential evolution being a simpler program with fewer random elements.

| All | Deterministic | MRs
---|---|---|---
FEA | 37/39 | 19/39 | 31/39
framework | 95% | 49% | 79%
Our | 50/58 | 7/58 | 42/58
impl. | 86% | 12% | 72%
Table 9: Comparison between mutation scores for our implementation and the FEA
framework on the differential evolution algorithm

##  6 Conclusions

###  6.1 Contributions

In this work we identified metamorphic relations of genetic algorithms, and
genetic algorithm operators. Additionally, we have identified metamorphic
relations of genetic algorithms that translate to differential evolution, and
may be more illustrative in differential evolution than in genetic algorithms.
We defined 17 metamorphic relations, five for the fitness functions, three for
the genetic algorithm operators and nine for the whole algorithm.

We compared the metamorphic relations to the deterministic unit tests for the
genetic algorithm. We found that metamorphic relations for our implementation
had a mutation score of 81% while traditional deterministic unit tests had a
mutation score of 33%. We also compared the function-level metamorphic
relations to the system-level metamorphic relations on the genetic algorithm
for our implementation. Function-level metamorphic relations had a mutation
score of 57% while system-level metamorphic relations had a mutation score of
63%. For the FEA framework, the mutation score for the metamorphic relations
was 66% while the mutation score for the deterministic tests was 44%. When
comparing system-level and function-level metamorphic relations for the FEA
framework, the mutation score for system-level metamorphic relations was 61%.
The mutation score for the function-level metamorphic relations was 48%.
Additionally, we modified two relations that failed more often than was
statistically likely on both implementations of the genetic algorithm when no
fault was present. Finally, we used 5 tests, two deterministic unit tests and
three metamorphic relations, on the differential evolution algorithm. The
mutation score for the metamorphic relations was 79% for the FEA framework and
72% for our implementation. The mutation score for the deterministic tests was
49% for the FEA framework and 12% for our implementation.

These comparisons demonstrated the effectiveness of the metamorphic testing
approach when testing genetic algorithms. We assessed the mutation score
relative to the statement coverage, and found that function-level metamorphic
relations performed better than function-level deterministic tests, despite
there being more deterministic tests. This result was consistent across both
genetic algorithm implementations we tested. We examined the failure rates of
the system-level relations when initialized with various fitness functions. We
found one relation that only performed well when paired with a particular
fitness function. Additionally, we found two relations that do not perform
well no matter the fitness function. We developed two new relations to replace
these problematic ones.

###  6.2 Future Work

Future work for metamorphic testing on genetic algorithms would include
identifying individual metamorphic relations that are either more
generalizable, or kill more mutants than other metamorphic relations. We also
plan to test these relations on different types of operators and different
purposes for a genetic algorithm. We plan to develop relations for other
operators, purposes, or algorithms. We can then also test those relations on
this genetic algorithm implementation. We would like to identify types of
mutants that survive more often, in order to identify metamorphic relations
that are able to target these mutants, or show that these mutants are more
likely to be equivalent. Finally, any future work would have to include the
identification of more metamorphic relations, and the implementation of more
tests.

## References

  * Lee et al. [2016] C. Lee, K. Choy, G. Ho, C. Lam,  A slippery genetic algorithm-based process mining system for achieving better quality assurance in the garment industry,  Expert Systems with Applications 46 (2016) 236–248.
  * Chiappone et al. [2016] S. Chiappone, O. Giuffrè, A. Granà, R. Mauro, A. Sferlazza,  Traffic simulation models calibration using speed–density relationship: An automated procedure based on genetic algorithm,  Expert Systems with Applications 44 (2016) 147–155.
  * Pareek and Patidar [2016] N. K. Pareek, V. Patidar,  Medical image protection using genetic algorithm operations,  Soft Computing 20 (2016) 763–772.
  * Davis et al. [2016] J. B. A. Davis, S. L. Horswell, R. L. Johnston,  The application of a parallel genetic algorithm to the global optimisation of gas-phase and supported gold-iridium nanoalloys,  The Journal of Physical Chemistry C (2016).
  * Perreault et al. [2015] L. J. Perreault, M. Thornton, R. Goodman, J. W. Sheppard,  A swarm-based approach to learning phase-type distributions for continuous time bayesian networks,  in: Computational Intelligence, 2015 IEEE Symposium Series on, IEEE, 2015, pp. 1860–1867.
  * Jones et al. [1996] B. Jones, H.-H. Sthamer, D. Eyres,  Automatic structural testing using genetic algorithms,  Software Engineering Journal 11 (1996) 299–306.
  * Wegener et al. [1997] J. Wegener, H. Sthamer, B. F. Jones, D. E. Eyres,  Testing real-time systems using genetic algorithms,  Software Quality Journal 6 (1997) 127–135.
  * Rao and Govindarajulu [2015] C. P. Rao, P. Govindarajulu,  Genetic algorithm for automatic generation of representative test suite for mutation testing,  International Journal of Computer Science and Network Security (IJCSNS) 15 (2015) 11\.
  * Tan et al. [2003] K. C. Tan, Q. Yu, C. Heng, T. H. Lee,  Evolutionary computing for knowledge discovery in medical diagnosis,  Artificial Intelligence in Medicine 27 (2003) 129–154.
  * Pena-Reyes and Sipper [1999] C. A. Pena-Reyes, M. Sipper,  A fuzzy-genetic approach to breast cancer diagnosis,  Artificial intelligence in medicine 17 (1999) 131–155.
  * Xie et al. [2009] X. Xie, J. Ho, C. Murphy, G. Kaiser, B. Xu, T. Y. Chen,  Application of metamorphic testing to supervised classifiers,  in: Quality Software, 2009. QSIC’09. 9th International Conference on, IEEE, 2009, pp. 135–144.
  * Guderlei and Mayer [2007] R. Guderlei, J. Mayer,  Statistical metamorphic testing testing programs with random output by means of statistical hypothesis tests and metamorphic testing,  in: Quality Software, 2007. QSIC’07. Seventh International Conference on, IEEE, 2007, pp. 404–409.
  * Stewart et al. [2004] T. J. Stewart, R. Janssen, M. van Herwijnen,  A genetic algorithm approach to multiobjective land use planning,  Computers & Operations Research 31 (2004) 2293–2313.
  * Chen and Yiu [1998] S. C. C. Chen, Tsong Y., S. M. Yiu,  Metamorphic testing: a new approach for generating next test cases (1998).
  * Geronimo et al. [2012] L. D. Geronimo, F. Ferrucci, A. Murolo, F. Sarro,  A parallel genetic algorithm based on hadoop mapreduce for the automatic generation of junit test suites,  in: Software Testing, Verification and Validation (ICST), 2012 IEEE Fifth International Conference on, IEEE, 2012, pp. 785–793.
  * Henard et al. [2013] C. Henard, M. Papadakis, G. Perrouin, J. Klein, Y. L. Traon,  Multi-objective test generation for software product lines,  in: Proceedings of the 17th International Software Product Line Conference, ACM, 2013, pp. 62–71.
  * Sharma et al. [????] C. Sharma, S. Sabharwal, R. Sibal,  Applying genetic algorithm for prioritization of test case scenarios derived from uml diagrams,  arXiv preprint arXiv:1410.4838 (????).
  * Arcuri and Briand [2014] A. Arcuri, L. Briand,  A hitchhiker’s guide to statistical tests for assessing randomized algorithms in software engineering,  Software Testing, Verification and Reliability 24 (2014) 219–250.
  * Mitchell et al. [1997] T. M. Mitchell, et al., Machine learning. wcb, 1997.
  * Xie et al. [2011] X. Xie, J. W. Ho, C. Murphy, G. Kaiser, B. Xu, T. Y. Chen,  Testing and validating machine learning classifiers by metamorphic testing,  Journal of Systems and Software 84 (2011) 544–558.
  * Ishibuchi et al. [1997] H. Ishibuchi, T. Murata, I. Türksen,  Single-objective and two-objective genetic algorithms for selecting linguistic rules for pattern classification problems,  Fuzzy Sets and Systems 89 (1997) 135–150.
  * Corcoran and Sen [1994] A. L. Corcoran, S. Sen,  Using real-valued genetic algorithms to evolve rule sets for classification,  in: Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence., Proceedings of the First IEEE Conference on, IEEE, 1994, pp. 120–124.
  * Hall et al. [2009] M. Hall, E. Frank, G. Holmes, B. Pfahringer, P. Reutemann, I. H. Witten,  The weka data mining software: an update,  ACM SIGKDD explorations newsletter 11 (2009) 10–18.
  * Yoo [2010] S. Yoo,  Metamorphic testing of stochastic optimisation,  in: Software Testing, Verification, and Validation Workshops (ICSTW), 2010 Third International Conference on, IEEE, 2010, pp. 192–201.
  * Murphy et al. [2009] C. Murphy, K. Shen, G. Kaiser,  Automatic system testing of programs without test oracles,  in: Proceedings of the eighteenth international symposium on Software testing and analysis, ACM, 2009, pp. 189–200.
  * Andrews et al. [2005] J. H. Andrews, L. C. Briand, Y. Labiche,  Is mutation an appropriate tool for testing experiments?[software testing],  in: Software Engineering, 2005. ICSE 2005. Proceedings. 27th International Conference on, IEEE, 2005, pp. 402–411.
  * Hancock [1994] P. J. Hancock,  An empirical comparison of selection methods in evolutionary algorithms,  in: AISB Workshop on Evolutionary Computing, Springer, 1994, pp. 80–94.
  * Goldberg and Deb [1991] D. E. Goldberg, K. Deb,  A comparative analysis of selection schemes used in genetic algorithms,  Foundations of genetic algorithms 1 (1991) 69–93.
  * Strasser et al. [2016] S. Strasser, J. Sheppard, N. Fortier, R. Goodman,  Factored evolutionary algorithms,  in: IEEE Transactions on Evolutionary Computation, 2016, p. Under review.
  * Storn and Price [1995] R. Storn, K. Price, Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces, volume 3, ICSI Berkeley, 1995.
  * Jamil and Yang [2013] M. Jamil, X.-S. Yang,  A literature survey of benchmark functions for global optimisation problems,  International Journal of Mathematical Modelling and Numerical Optimisation 4 (2013) 150–194.
  * Deb and Agrawal [1998] K. Deb, S. Agrawal,  Understanding interactions among genetic algorithm parameters.,  in: FOGA, 1998, pp. 265–286.
  * Coles [2012] H. Coles, Pit mutation testing, 2012\.