Luis Martí

Arsene Fansi-Tchango

Laurent Navarro

Marc Schoenauer

Anomaly Detection with the Voronoi Diagram Evolutionary Algorithm

This paper presents the Voronoi diagram-based evolutionary algorithm (VorEAl). VorEAl partitions input space in abnormal/normal subsets using Voronoi diagrams. Diagrams are evolved using a multiobjective bio-inspired approach in order to conjointly optimize classification metrics while also being able to represent areas of the data space that are not present in the training dataset. As part of the paper VorEAl is experimentally validated and contrasted with similar approaches.

Introduction

Anomalous Internet traffic detection is a major question of computer network security. Intrusion detection systems (IDSs) [START_REF] Northcutt | Network intrusion detection[END_REF] have proposed with the intention of tackling this issue. They are meant to protect a network by providing a line of defense that is able to detect and react to network attacks. Two main approaches are used when building an IDS: i) misuse-based and ii) anomaly-based detection. While the former focuses on detecting attacks that follow a known pattern or signature, the latter is interested in building a model representing the system's normal behavior while assuming all deviated activities to be anomalous or intrusions. Because of that fact anomaly detection has received increasing attention in the recent past.

Anomaly detection has been addressed with different approaches (see [START_REF] Chandola | Anomaly detection: A survey[END_REF] for a survey). Among nature-inspired approaches artificial immune systems (AISs) [START_REF] Kim | Immune system approaches to intrusion detection -a review[END_REF] have received an special attention.

This paper proposes the Voronoi diagram-based evolutionary algorithm (Vo-rEAl). VorEAl is inspired on AISs and the representations that had been proposed for evolutionary shape design consolidating previous progresses made in this direction [START_REF] Martí | VorAIS: A multiobjective Voronoi diagram-based artificial immune system[END_REF]. Its main distinctive feature is that it evolves Voronoi diagrambased representations for normal/abnormal regions of the search space. Such representation offers a flexible and compact alternative to some common representations used in AIS such as hyper-spheres and hyper-rectangles. VorEAl applies a multi-objective approach that takes into account the detection accuracy and other especially devised volume-based methods that promotes the emergence of solutions that also adequately represent areas of the input space where no normal data has been received and, therefore, should represent anomalies. As in any multi-objective approach, the algorithm produces a set of trade-off solutions. VorEAl applies a committee approach that is based on the best (in term of a priori given set of preferences) subset of those solution.

The paper is organized as follows. Section 2 presents the context of AIS and some existing approaches to anomaly detection. Section 3 introduces the Voronoi representation for abnormal and normal input subsets, together with the variation operators and objective functions used to evolve it and VorEAl as a whole. Section 4 introduces our methodology for the experimental validation of VorEAl, also presenting the results of the study and comparing them with other approaches from the literature. Finally, Section 5 discusses the results and sketches some further research directions.

Foundations

There has been a consistent interest by the community on proposing natureinspired approaches to anomaly detection. In this context, AISs have attracted attention as they embody an analogy to the biological immune system. They are particularly appealing for anomaly detection problems as they capture the ability of the biological system of telling apart normal body cells from pathogens. That is, from a computational perspective, they create a model that is able to discriminate between normal (self) and abnormal (non-self) objects. This feature make AISs specially suited to be applied in the context of anomaly-based IDSs.

In order to extend AISs' performance it is necessary to apply algorithms that combine a powerful representation capacity as well as the possibility of adequately adapting that capacity to meet the problem characteristics.

Voronoi diagrams are geometrical constructs that were known by ancient Greeks. Any set of points, known as Voronoi sites, in a given n-dimensional Euclidean space E defines a Voronoi diagram, i.e., a partition of that space into Voronoi cells: the cell corresponding to a given site S is the set of points whose closest site is S. The boundaries between Voronoi cells are the medians of the [S i S j ] segments, for neighbor Voronoi sites S i and S j . Though originally defined in two or three dimensions, there exist several algorithmic procedures to efficiently compute Voronoi diagrams in any dimension.

Voronoi diagrams offer a compact representation for shapes (surfaces in 2D and volumes in 3D, for instance), by attaching to each Voronoi cell (or, equivalently, to the corresponding Voronoi site), a Boolean label. The resulting Voronoi diagram is a partition of the space into 2 subsets: the "true" cells are the shape/volume, and the "false" cells are the outside of the shape/volume. The genotype is here a (variable length) list of labeled Voronoi sites, and the phenotype is the corresponding partition in the space into two subsets. More generally, any piece-wise constant function on the underlying space can be represented by a similar representation by using real-valued labels. Such representation has been successfully used in the context of Evolutionary Optimum Design [START_REF] Hamda | Compact unstructured representations for evolutionary design[END_REF][START_REF] Schoenauer | Shape representation for evolutionary optimization and identification in structural mechanics[END_REF]. In particular, it has been demonstrated that the local complexity of the representation function mutate voronoi(I, ps, p f , pt, p+, p-, η)

I, individual to be mutated. ps ∈ [0, 1], prob. of mutating a site. p f ∈ [0, 1], prob. of mutating a site feature (coordinate). pt ∈ [0, 1], prob. of changing the label of a site. can also be adjusted by evolution: in regions of the space where the shape has a complex boundary, several Voronoi sites will be used, whereas only a few of them will be necessary elsewhere.

p+ ∈ [0, 1], prob. of adding a new site. p-∈ [0, 1], prob. of removing a site. η ∈ (0, ∞], learning rate. for all S ∈ I do if U [0, 1) < ps then for all x ∈ S do if U [0, 1) < p f then x ← mutate log normal(x, η) if U [0, 1) < pt then S. ← switch label(S. ). if U [0, 1) < p+ then I ← I ∪ {random site}. if U [0, 1) < p-then i ← U [1, |I|); I ← I \ {I(i)}. return I, mutated individual.
In the context of classification, the target phenotypes are partitions of the parameter space into positive and negative examples (in the case of 2 classes), and can hence also be represented by Voronoi diagrams with Boolean labels -or with labels taken from a finite alphabet in the case of more than 2 classes.

The Voronoi diagrams-based evolutionary algorithm

We now discuss the building blocks of VorEAl. In particular, we present variation operators, the possible strategies used for evaluating the individuals and how these elements are assembled together to form the algorithm.

Variation operators

The genotypes of Voronoi representations is a variable length list of Voronoi sites (S 1 , . . . , S p ), with p ∈ [P min , P max ], where each site is defined by its n coordinates in E. Each site S has an associated label S. that determines how a point that falls within the corresponding cell is classified.

function crossover voronoi(I1, I2)
I1 and I2, individuals to mate. repeat P ← random hyperplane(I1 ∪ I2). ξ

(1)

1 , ξ (1) 2
← split individual(I1, P ). ξ Mutation Operator Several mutation operators can be designed for such a variablelength representation.

(2) 1 , ξ (2) 2 ← split individual(I2, P ). until ξ (i) k = ∅, ∀i, k O1 = ξ (1) 1 ∪ ξ (2) 2 ; O1. = I1. ; O2 = ξ (2) 1 ∪ ξ (1) 2 ; O2. = I2. . return O1, O2, offspring.
-At the individual level, a Voronoi site can be added, at a randomly chosen position, with a random label; or a randomly chosen Voronoi site can be removed.

-At the site level, Voronoi sites can be moved around in the space -and the well-known self-adaptive Gaussian mutation has been chosen here, inspired by Evolution Strategies (see (1) below); or the label of a Voronoi site can be changed.

In the self-adaptive Gaussian mutation [START_REF] Schwefel | Numerical Optimization of Computer Models[END_REF], each coordinate x of each Voronoi site also "carries" its own variance σ that is used for its Gaussian mutation. Coordinate x undergoes Gaussian mutation with variance σ while σ undergoes a log-normal mutation with learning rate η as follows:

x ← σN (x, 1) and σ ← σe ηN 0,1

The different mutation operators are applied according to different probabilities, following the procedure described in Figure 1.

Crossover Operator

The crossover operator for Voronoi representation should not simply exchange some Voronoi sites between both parents, but should respect the locality of the representation. Voronoi sites that are close to each other should have more chance to stay together than Voronoi sites that are far apart. This is achieved by the geometric crossover that operates on two (randomly selected) parents by creating a random cutting hyperplane, and exchanges the Voronoi sites from both sides of the hyperplane. The Voronoi diagrams are of course reconstructed after the crossover. This procedure is described in detail in Figure 2a. A two-dimensional example is given in Figure 2b.

Objectives and fitness assignment

Anomaly detection can be posed as a particular case of classification problem where data items must be tagged either as "normal" or "anomalous". That relying on a dataset Ψ = x (i) , y (i) where, without loss of generality we can state that x ∈ R n and y (i) ∈ {normal; anomaly} obtain a classifier that correctly detects instances that correspond to each of the two categories. Because of this fact the existing metrics devised to assess the quality of a classification algorithm are also applicable in this context. For this particular problem, the most relevant metrics are accuracy, recall and specificity, although many more could also be of use. Accuracy seems the best choice in the general case, as one wants to correctly identify all examples. But when dealing with anomalies, the dataset is generally highly imbalanced, as normally there are fewer anomalous instances than 'normal' ones. If only the classification accuracy is used, the error contribution of the anomalies will be reduced and hence the model will be biased to not regard them.

Furthermore, as already mentioned, the anomaly detection problem requires that the classifier is not only able to correctly classify the "normal" and "anomalous" instances present in the training dataset but is also capable of detecting when a given input falls in an area that was not covered by data of the training set and, therefore, also can be interpreted as an anomaly.

It is possible to prompt the Voronoi diagrams (individuals) to represent the known data in a form as compact as possible by expressing that as the relation between the volumes of the Voronoi cell and the convex hull of the training data that it contains. Let I = {S i , i = 1 . . . n I } be a Voronoi diagram, and, for each cell C i , let v i ∈ R be its volume and D i the set of data points it contains, i.e., D i = {x ∈ Ψ ; d(x, S i ) ≤ d(x, S j )∀i = j}, d being the n-dimensional Euclidian distance. We can then define the individual compactness as the sum, for each cell, of the ratio of the volume of the convex hulls of D i and the volume of the cell,

C(I) = i volume(convex hull(Di)) vi if |D i | > n, 0 in other case. ( 2
)
It could be hypothesized that the previous formulation can be improved by adding a multiplicative term that counts the number of elements in D i , resulting in the multiplicative compactness

C mult (I) = i (|D i | -n) volume(convex hull(Di)) vi if |D i | > n, 0 in other case. ( 3
)
In both cases, maximizing the compactness will produce cells that contain the data in a form as tight as possible. Those compactness objectives can be complemented by one that promotes the existence of empty cells that represent areas of the input domain that are now present in the training data. Such objective would take care of sites with small D i 's and promote that they become empty as the evolution takes place. A form of representing this is by computing the total volume of cells with an anomaly label of an individual and rate it by the number of elements it contains,

EV(I) = i,Si. =anomaly v i 1 + 2 ln(|D i | + 1) . (4)
Consequently, it is obvious that it is necessary to jointly address all of those objectives. Therefore, a multi-objective optimization approach will empower the algorithm with the capacity to address all the requirements of the task at the same time.

Algorithm description

VorEAl consolidates the previous components as an algorithm that constructs a classification model. The algorithm starts by creating an initial random population P 0 of n pop individuals. At a given iteration t, individuals in the population P t are then mutated and mated using operators described above and thus producing an offspring population P off that consists of n off individuals. At this point, individuals that have not yet been evaluated are presented with the dataset and the values of the different objective functions are calculated. In this work, we compute the accuracy, recall and specificity, but it should be noted that others are available. From the union of P t and P off , the best n pop are selected using the non-dominated sorting selection of NSGA-II [START_REF] Deb | A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[END_REF]. This process repeats until the stopping criterion of the algorithm is met. When that happens, the algorithm has a final population P final from which the best individual(s) can be selected to represent the 'self' of the AIS. This a nontrivial task as it implies taking into account the different conflictive objectives. In this work, we select a committee of individuals P committee ⊆ P final that contains the ρ-percent of P final with the highest accuracy. Hence, the classifier returns the most voted decision among the members of P committee .

The previous discussion and proposal must be complemented by a set of experiments that establish the validity of VorEAl and studies the impacts of the different components presented. That is the focus of this section.

One of the main questions regarding VorEAl is at what point a multiobjective affinity function would actually generate better results at an admissible cost. It could be argued that there exists the possibility that adding more objectives would just make the search process more complex and resource demanding.

An important matter to be clarified was the impact of each of the objectives presented in previous section. For that reason different combinations were tested. In particular, we tested accuracy and compactness (a/c); accuracy, compactness and total empty volume (a/c/t); accuracy and multiplicative compactness (a/m) and accuracy, multiplicative compactness and total empty volume (a/m/t).

In order to provide grounds for comparison with similar approaches as well as well-known approaches, other methods were included in the experiments. In particular, we included the negative selection algorithm (NSA) [START_REF] Ji | Real-valued negative selection algorithm with variable-sized detectors[END_REF] using both variable-sized hyper-spheres and hyper-rectangles. For fair comparisons, we applied the NSA + sp and NSA + re in which non-self training samples are subsequently used to enrich the detector library generated by NSA.

Similarly, we have included in the experiments two well-known classifiers: one-class vector machines (SVMs) [START_REF] Tax | Support vector data description[END_REF] and the naïve Bayes classifier.

The experiments involved six classification benchmarks problems: the 'two spiral', 'crescent and full moon', 'half densities', 'corners', 'outliers' and 'cluster in cluster' problems. They have the advantage that they can be visualized in 2D while still posing a substantial challenge to the algorithm. One key element that must be addressed is the ability of the method to detect anomalies that were present in the original dataset and also those that were not present. Six tests were prepared with that goal in mind by adding random anomaly data in the areas that did not had any data in the training dataset. The resulting training and test datasets can be observed in Figure 3. Besides fixing these parameters we limited the population to 100 individuals and ran the algorithms for 500 generations. The rest of the parameters are tuned using a grid search procedure on a reduced-size problem. The same parameters were used for all problems. The mutation of the parameters were p s = 0.5, p f = 0.5, p t = 0.1, p + = 0.2, p -= 0.1 and η = 0.5, while the mating probability was 0.5, the minimum and maximum number of sites in an individual was set to 20 and 100, respectively and the committee selection percentile (ρ) was set to 5% of the population.

The stochastic nature of the algorithms being analyzed calls for the use of an experimental methodology that relies on statistical hypothesis tests. Using those tests, we are able to determine in a statistical sound way if one algorithm instance outperforms another. The topic of assessing stochastic classification algorithms is studied in depth in [START_REF] García | An extension on "statistical comparisons of classifiers over multiple data sets" for all pairwise comparisons[END_REF]. There, it is shown that the Bergmann-Hommel procedure is the most suitable for our class of problem. In all cases, we have used a base level of significance of 0.05 and we run the same experiment instances 50 times. The results of this experiments are shown as box plots in Figure 4. It can be inferred Table 1: Summary of the outcome of the statistical hypothesis tests for each problem and performance indicator. When an algorithm in the row has been significantly better than the one in the column the corresponding cell is marked with a "+". If it has been worst then the cell contains a "-". Cases where no significant difference was established are identified with a "∼".

Fig. 1 :

 1 Fig. 1: Mutation of a Voronoi diagram.

  (a) Crossover of two Voronoi diagrams, applied with probability pc. (b) Example of crossover of two Voronoi genotype individuals in 2D.

Fig. 2 :

 2 Fig. 2: Crossover operator for Voronoi diagrams.

Fig. 3 :

 3 Fig.3: Training and testing datasets. Test set anomalies present in the test datasets are generated using the procedure described in Section 4.

Acknowledgements

This work has been funded by the project PIA-FSN-P3344-146479. Authors wish to thank the reviewers for their fruitful comments.

• ---+ ---

from those plots that the three-objective form of with accuracy, multiplicative compactness, and total empty volume VorEAl yielded the best results. When many tests are carried out, a comprehensive analysis of the results is rather difficult as it implies cross-examining and comparing the results presented separately. Consequently, we present them in summarized form in Table 1. It should be noted that experiment parameters and results are available online at http://lmarti.com/VorEAl. To further simplify the understanding of results, why we decided to adopt a more integrative representation like the one proposed in [START_REF] Bader | Hypervolume-Based Search for Multiobjective Optimization: Theory and Methods[END_REF]. Figure 5 summarizes the outcome of the hypothesis tests by grouping them by metric and problem, as explained in the previous section. Here it is clearly visible how VorEAl with multiplicative compactness and total empty volume objectives is generally able to yield better results. Finally, as an illustrative example, we show in Figure 5c an example of an evolved Voronoi diagram.

Discussion and conclusion

In this paper we have presented VorEAl, a multi-objective evolutionary algorithm that relies on Voronoi diagrams for representation. VorEAl has been devised with the problem of anomaly detection in mind. The experimental results obtained as part of this work point out that this is a promising direction of work. However, there are many areas that should be further studied and ex- plored. From an algorithmic point of view, we should explore other classification objectives (metrics).

It is important to try other multi-objective fitness assignments, like those based on multi-objective performance indicators or reference points. This last approach is of particular interest as, as we already mentioned, in our case we have an a priori known ideal solution that can be used to guide the search. In parallel, work should the done in understanding and reducing the computational complexity of the algorithm. In this direction, we are already working on creating approximative versions of the volume meant to decrease the computational cost of the computation of the objective functions.


Edgar Galván-López

Efrén Mezura-Montes

Ouassim Ait Elhara
email: ouassim.aitelhara@inria.fr

Marc Schoenauer
email: marc.schoenauer@inria.fr

On the Use of Semantics in Multi-Objective Genetic Programming

Research on semantics in Genetic Programming (GP) has increased dramatically over the last number of years. Results in this area clearly indicate that its use in GP can considerably increase GP performance. Motivated by these results, this paper investigates for the first time the use of Semantics in Muti-Objective GP, within the well-known NSGA-II algorithm. To this end, we propose two forms of incorporating semantics into a MOGP system. Results on challenging (highly) unbalanced binary classification tasks indicate that the adoption of semantics in MOGP is beneficial, in particular when a semantic distance is incorporated into the core of NSGA-II.

Introduction

Genetic Programming (GP) [START_REF] Koza | Genetic Programming: On the Programming of Computers by Means of Natural Selection[END_REF] has been successfully used in a range of different challenging problems (see Koza's article on human competitive results for a comprehensive review [START_REF] Koza | Human-competitive results produced by genetic programming[END_REF]). Despite its proven success, it also suffers from some limitations and researchers have been interested in making GP more robust by studying various elements of the search process, and also, by e.g., considering other GP forms [START_REF] Galván-López | Efficient graph-based genetic programming representation with multiple outputs[END_REF].

One of these elements that has relatively recently attracted the attention of researchers is the study of semantics in GP, resulting in a dramatic increase in the number of related publications (e.g., [START_REF] Beadle | Semantically driven crossover in genetic programming[END_REF][START_REF] Galván-López | Using semantics in the selection mechanism in genetic programming: A simple method for promoting semantic diversity[END_REF][START_REF] Krawiec | Locally geometric semantic crossover: a study on the roles of semantics and homology in recombination operators[END_REF][START_REF] Mcphee | Semantic building blocks in genetic programming[END_REF]).

Semantics is a broad concept that has been studied in different fields making it hard to give a precise definition of the concept. Moreover, the way semantics have been adopted in canonical GP varies significantly e.g., Beadle and Johnson [START_REF] Beadle | Semantically driven crossover in genetic programming[END_REF] used reduced ordered binary decision trees on Boolean problems to study semantics, whereas Uy's work on semantics has focused on repeatedly applying crossover to encourage semantic difference between parents and offspring (see [START_REF] Vanneschi | A survey of semantic methods in genetic programming[END_REF] for a summary of works carried out in semantics).

This work uses a popular version of semantics GP, as originally proposed in [START_REF] Mcphee | Semantic building blocks in genetic programming[END_REF], and used in recent works from the first author [START_REF] Galván-López | Using semantics in the selection mechanism in genetic programming: A simple method for promoting semantic diversity[END_REF][START_REF] Uy | Semanticallybased crossover in genetic programming: application to real-valued symbolic regression[END_REF], in which the semantics of a (sub)tree is defined as the vector of output values computed by this (sub)tree for each set of input values in turn (a.k.a. each fitness case in most cases). Several semantic-based approaches have been proposed for GP which take semantics into account when e.g., choosing and modifying subtrees, such as the one that has been demonstrated beneficial in [START_REF] Uy | Semanticallybased crossover in genetic programming: application to real-valued symbolic regression[END_REF] and it is adopted too in this work.

To the best of our knowledge, however, there is no scientific study on the adoption of semantics in Evolutionary Multi-Objective Optimisation at large [START_REF] Deb | Multi-Objective Optimization Using Evolutionary Algorithms[END_REF], and in Multi-objective GP in particular, and this paper intends to start filling this important research area.

The goal of this paper is to incorporate semantics into a Multi-Objective GP paradigm by using the well-known NSGA-II. To this end, we studied two different forms of incorporating semantics into NSGA-II: (a) one based on a relatively simple, efficient and straightforward semantic-based single-objective GP approach, and (b) one based on the adoption of a semantic distance into the core of the NSGA-II algorithm.

This paper is organised as follows. In Section 2, we introduce our proposed approaches. Section 3 provides details on the experimental setup used. The results presented in this paper are discussed in Section 4, and finally, conclusions and future work are drawn in Section 5.

Semantics in Multi-Objective Genetic Programming

As indicated in Section 1, following [START_REF] Mcphee | Semantic building blocks in genetic programming[END_REF], the semantics of a GP tree describes the behavior of the tree when various values are given to the input variables. In the case of a fitness based on the computation of several fitness cases, the semantics of a GP individual is a vector of size the number of fitness cases, one value for each fitness case. For instance, in the case of the problems used in this work (unbalanced data sets introduced in Section 3), the semantics of a GP individual is the vector of real-valued outputs of the tree for each of the total examples in the data set. In this work, the semantic distance between two trees is the number of outputs that are different between their semantics. Commonly, when computing the semantic distance, two outputs are considered different if their absolute difference is greater than a given threshold [START_REF] Galván-López | Using semantics in the selection mechanism in genetic programming: A simple method for promoting semantic diversity[END_REF][START_REF] Uy | Semanticallybased crossover in genetic programming: application to real-valued symbolic regression[END_REF]. In this work, we set the threshold at 0.5. It is clear that two trees can be syntactically very different while behaving identically. What matters, as far as solving the problem at hand, is in fact the behavior of a tree: its response to given input values. These arguments support the use of semantics, and at least, partly explain the benefits of using semantics in GP as reported in [START_REF] Galván-López | Using semantics in the selection mechanism in genetic programming: A simple method for promoting semantic diversity[END_REF][START_REF] Uy | Semanticallybased crossover in genetic programming: application to real-valued symbolic regression[END_REF].

Evolutionary Multi-Objective Optimisation

Multi-objective optimisation (MO) is concerned with the simultaneous optimisation of several objectives. When these are in conflict, no single solution exists, and trade-offs between the objectives must be sought. The optimal trade-offs are the solutions for which no objective can be further improved without degrading another objective. This idea is captured in the Pareto dominance relation: a point x in the search space is said to Pareto-dominate another point y if x is at least as good as y on all objectives and strictly better on at least one objective.

The set of optimal trade-off solutions of a MO problem can then be defined as the set of points of the search space that are not dominated by any other point, and is called the Pareto set of the problem at hand. The goal of Pareto MO is to identify the Pareto set, or a good approximation of it. The Pareto front is the image of the Pareto set in the objective space.

Evolutionary multi-objective optimisation (EMO) [START_REF] Deb | Multi-Objective Optimization Using Evolutionary Algorithms[END_REF] is based on the following: by replacing the single-objective selection steps, based on the comparison of fitness values, by some Pareto-based comparison, one turns a single-objective evolutionary optimisation algorithm into a multi-objective evolutionary optimization algorithm, but because Pareto dominance is not a total order, some additional criterion must be added to Pareto dominance so as to allow the comparison of any pair of points of the search space.

In NSGA-II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF], the Pareto-based comparison uses the non-dominated sorting procedure: all non-dominated individuals in the population are assigned Rank 1 and excluded from this comparison, the remaining non-dominated individuals are assigned Rank 2, and so on. The secondary criterion is the crowding distance that promotes diversity among the individuals having the same Pareto rank: in objective space, for each objective, the individuals in the population are ordered, and the partial crowding distance for each of them is the difference in fitness between its immediate neighbours. The crowding distance is the sum of these partial crowding distances for all objectives. Intuitively, it can be seen as the Manhattan distance between the extremal vertices of the largest hypercube containing the point at hand and no other point of the population. Selecting points with the largest crowding distance amounts to favour the low-density regions of the objective space, thus favouring behavioural diversity.

The NSGA-II proceeds as follows. From a given population of size N , N offspring are created using standard variation operators (crossover and mutation). Parents and offspring are merged, and the resulting population, of size 2N , is ordered using non-dominated sorting and crowding distance, as explained above. The best N according to this ranking are selected to survive at next generation.

Because the underlying idea within NSGA-II is to favour behavioral diversity, but only considering the fitness as a whole, it can be hoped that introducing semantics in NSGA-II can only enforce this idea.

Incorporating Semantics in MOPG

In this work, we investigated two ways of incorporating semantics into a MOGP system (recall we use NSGA-II). One natural form to do so is to use semantics as commonly adopted in canonical GP (e.g., semantically-based crossover [START_REF] Uy | Semanticallybased crossover in genetic programming: application to real-valued symbolic regression[END_REF]). In our study, we adopted the semantics in the selection tournament mechanism [START_REF] Galván-López | Using semantics in the selection mechanism in genetic programming: A simple method for promoting semantic diversity[END_REF] due to its simplicity and efficiency. Briefly, the idea is to create offspring that are semantically different from their parents when tournament selection is applied: the first parent is selected as usual and the second parent is selected if it is semantically different and fitter than the already selected parent, if this is not satisfied for any individual in the pool, one is chosen at random. We call this NSGA-II Semantics in Selection (SiS).

The second proposed way to add semantics to NSGA-II is to replace the crowding distance (see above) with a semantic-based indicator called Semanticbased Crowding Distance (SCD). This is computed the following way: a pivot is chosen, being the individual from the first Pareto front (rank 1) that is the furthest away from the other individuals of this front using the crowding distance. For each point, its semantic distance with the pivot is computed. Similarly to the crowding distance, the SCD is computed as the average of the semantic distance differences with its closest neighbours in each direction. The higher values of this SCD are favored during the selection step of NSGA-II. This allows us to have a set of individuals that are spread in the semantic space, therefore, promoting semantic diversity, the same way NSGA-II promotes diversity ('spreadness') in the objective space. It is worth pointing out that this approach also works when there is only one front. This variant of NSGA-II will be called Distance-based Semantics (DBS) in the following.

MOGP Configuration and Experimental Design

To study the effects of semantics in MOGP, we used challenging binary (highly) unbalanced classification problems taken from the specialised literature [START_REF] Asuncion | UCI machine learning repository[END_REF]. These problems are of different nature and complexity (e.g., from a few number of features up to dozens of them, and these include real, binary and integer-value features, from relatively low to highly unbalanced data). Table 1 shows the sizes of both majority and minority classes for each of these problems along with details about the data used in our study. We used the data as 'it is' (e.g., we did not try to balance the classes out). We used half of each problem to train our MOGP systems and the other half to test it.

To generate classifiers via MOGP, we defined our terminal and function in the same manner as in [START_REF] Bhowan | Evolving diverse ensembles using genetic programming for classification with unbalanced data[END_REF]. The terminal set consists of example features. The function set consists of a conditional if function and the typical four standard arithmetic operators, and so, the function set is defined by F = {if, +, -, * , /}, where the latter operator is protected division, which returns the numerator if the denominator is zero. The if function takes three arguments: if the first is negative, the second argument is returned, otherwise the last argument is returned. These functions are used to build a classifier (e.g., mathematical expression) that returns a single value for a given input (data example to be classified). This number is mapped onto a set of class labels using zero as the class threshold. In our studies, an example is assigned to the minority class if the output of the classifier is greater or equal to zero. It is assigned to the majority class, otherwise.

The common form to measure the fitness in classification is the overall classification accuracy: using the four outcomes for binary classification shown in Table 2 and assuming the minority class is the positive class, we have that the accuracy is given by Acc = T P +T N T P +T N +F P +F N . The drawback with Acc is that it can bias the evolutionary search towards the majority class [START_REF] Bhowan | Evolving diverse ensembles using genetic programming for classification with unbalanced data[END_REF]. As mentioned also in [START_REF] Bhowan | Evolving diverse ensembles using genetic programming for classification with unbalanced data[END_REF], a better approach is to treat each objective (class) 'separately' using MOGP. To this end, we use in the fitness function of our MOGP the true positive rate (T P R = T P T P +F N ) and the true negative rate (T N R = T N T N +F P ) to measure the accuracy for the minority and majority class, respectively.

The experiments were conducted using a steady state approach with tournament selection (Size 2 for NSGA-II and NSGA-II DBS and Size 7 for NSGA-II SiS to encourage semantic difference via this operator). We used the traditional 90/10 crossover operator and subtree mutation. To initialise our population and to apply mutation, we used the ramped half-and-half method (initial and final depth set at 1 and 5, respectively). To control bloat a maximum depth of 8 was specified (where root was considered of depth 0) or a maximum number of 800 nodes was used. Crossover and mutation rates were 60% and 40%, respectively. To obtain meaningful results, we performed 50 independent runs for each of the MOGP approaches for each of the problems used in this work.

Results and Discussion

Front Hyperarea

We computed the hyperarea or hypervolume [START_REF] Coello | Evolutionary Algorithms for Solving Multi-Objective Problems (Genetic and Evolutionary Computation[END_REF] of the evolved Paretoapproximated fronts as a measure to determine which MOGP paradigm is better on the used tasks. The hyperarea is calculated by taking the sum of the areas of individual trapezoids fitted under each front solution in objective-space. Thus, the higher the value, the better the performance. Such measure was chosen because its popularity in the area as well as its theoretical foundations [START_REF] Lehre | Theoretical foundations of evolutionary computation hypervolumebased multiobjective optimization: Theoretical foundations and practical implications[END_REF].

Table 3 reports the average hyperarea computed over all runs along with its standard deviation (±). We also computed the Pareto-optimal (PO) front with respect to all MOGP runs, i.e., the PO front is the set of non-dominated solutions from all Pareto-approximated fronts evolved from 50 independent runs. Table 3. Average (± standard deviation) hyperarea, where the reference point is (0,0), of evolved Pareto-approximated fronts, Pareto optimal (PO) front for the three MOGP used in this work: NSGA-II, NSGA-II SiS and NSGA-II DBS, over 50 runs. In Table 3, the better hyperarea (average and PO) is highlighted in boldface for each of the four problems used in this work. We computed the statistical significance test on the average hyperarea using the common Wilcoxon Test technique at 90% level of significance independently comparing each of the semantic-based approaches (NSGA-II SiS, NSGA-II DBS) against NSGA-II.

Methods

Hyperarea

According to this table, in three out of the four problems, both semanticbased MOGP approaches achieve a higher hyperarea of the PO front compared to the NSGA-II. Moreover, the NSGA-II DBS is statistically better (indicated in boldface) than the NSGA-II on two classification problems and not statistically different on the remaining problems. Furthermore, NSGA-II SiS is not statistically different on any of the problems compared to NSGA-II. This appears to suggest that the adoption of semantics into a MOGP approach should be in one of the pillars of the MO approach.

Evolved Solutions and Pareto-optimal Front

We now turn our attention on the accuracy achieved by all evolved solutions over 50 runs for each of the problems used in this work. Due to space constraints and for clarity purposes, we only show in Figure 1 accuracy values evolved by the NSGA-II and the NSGA-II DBS. In some problems (e.g., Ion), it is relatively easy to see how the NSGA-II DBS, shown in the centre of the figure, is able to find more unique values. To better interpret the results, we also show in the right-hand of the figure, the difference between those values exclusively found either by NSGA-II or NSGA-II DBS. That is, for the NSGA-II, we plotted those values that were not found by the NSGA-II DBS, and vice versa. NSGA-II DBS (indicated by a blue cross 'x' symbol) is able to find more values close to the frontier side of all evolved solutions on Ion, Spect and Yeast 1 problems compared to NSGA-II (indicated by a red plus '+' symbol).

Figure 2 shows the Pareto fronts for each of the MOGP approaches used in each of the problems employed in this work. As it can be seen, little difference is observed among the three methods on the Yeast problems, which is in accordance to the results reported in Table 3. The advantage of the semantic-based MOGP approaches can be observed in the rest of the problems.

Bloat

There are a mixture of reports that indicate that either semantics prevent bloat (e.g., dramatic increase of programs' length without observing a corresponding improvement in fitness) e.g., [START_REF] Galván-López | Using semantics in the selection mechanism in genetic programming: A simple method for promoting semantic diversity[END_REF] or exacerbates it e.g., [START_REF] Uy | On the roles of semantic locality of crossover in genetic programming[END_REF]. To shed some light on this, we also plotted the average length of programs evolved by each of the MOGP approaches on only two problems (Ion and Yeast 2 ) due to space constrains. This is shown in Figure 3.

As it can be seen from this figure, it is clear that the semantic-based approaches tend to produce slightly shorter programs compared to canonical NSGA-II on the Yeast 2 problem and the same tendency was observed for Yeast 1 and Spect problems (not shown in the figure). Surprisingly, NSGA-II SiS is indeed able to produce much shorter programs compared to the other two methods on the Ion problem. This is aligned to the results reported in [START_REF] Galván-López | Using semantics in the selection mechanism in genetic programming: A simple method for promoting semantic diversity[END_REF], where the authors pointed out that SiS is capable of producing shorter programs compared to, for example, the well-known semantically-based crossover [START_REF] Uy | Semanticallybased crossover in genetic programming: application to real-valued symbolic regression[END_REF].

From this, we believe that researchers tend to report mixed results on bloat because its appearance is dependant on both: problem and approach used, and so, no general conclusions can be drawn on this.

Conclusions and Future Work

In genetic programming, semantics is commonly defined as the meaning (behaviour) of syntactically correct programs. In canonical GP, it is said that two individuals are semantically different if their output vectors are different, they are considered semantically similar, otherwise.

In this work we adopted two forms of semantics in Multi-Objective GP. One was the adoption of Semantics in Selection (SiS) adapted from canonical GP to NSGA-II. The other approach, named Distance-based Semantics (DBS), consisted in using a semantic distance into the core of the NSGA-II mechanism.

We have learned that semantic-based NSGA-II behaves better than NSGA-II on the unbalanced binary classification problems used in this work. We also learned that the NSGA-II DBS behaves better compared to NSGA-II SiS. We believe that the reason behind this is because the concept of semantic distance is used into the very core of the NSGA-II. There are multiple research areas that we will consider in the near future. An in-depth analysis is required to know why DBS is better than SiS. Given the encouraging results, it is worth considering to study the effects of semantics in other parts of a MOGP algorithm (e.g., ranking system). It is also necessary to study the adoption of semantics and its impact in other well-known MO approaches.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Performance on the classification task in each of the four problems used in this work achieved by NSGA-II (indicated with a black star symbol), NSGA-II SiS (indicated with a blue circle symbol) and NSGA-II Distance-based Semantics (indicated with a red square symbol).

Table 1 .

 1 Binary unbalanced classification data sets used in our research. Table adapted from[START_REF] Bhowan | Evolving diverse ensembles using genetic programming for classification with unbalanced data[END_REF].

	Data set Classes		Number of examples	Imb. Features
		Positive/Negative (Brief description) Total	Positive	Negative Ratio No. Type
	Ion	Good/bad (ionsphere radar signal)	351 126 (35.8%) 225 (64.2%) 1:3 34 Real
	Spect	Abnormal/normal (cardiac tom. scan) 267 55 (20.6%) 212 (79.4%) 1:4 22 Binary
	Yeast1 mit/other (protein sequence)	1482 244 (16.5%) 1238 (83.5%) 1:6 8 Real
	Yeast2 me3/other (protein sequence)	1482 163 (10.9%) 1319 (89.1%) 1:9 8 Real

Table 2 .

 2 Confusion Matrix.

		Predicted object Predicted non-object
	Actual object	True Positive (TP) False Negative (FN)
	Actual non-object False Positive (FP) True Negative (TN)

Acknowledgements EGL's research is funded by the Irish Research Council and by Marie Curie Actions. The authors would like to thank the reviewers.