Assoc ProfessorMiguel Nicolau

Genetic Programming (GP) has been widely applied to classification problems. However, like other artificial intelligence methods, GP can also be hindered by poor generalisation. To address this problem, we propose a new margin-based loss fitness function for binary classification tasks, named "Logistic Loss" (LL). We discuss the behaviour of Accuracy (ACC), Hinge Loss (HL), and LL, and argue that LL can enhance model generalisation by disregarding outliers and through continuous margin optimisation. Through grammar-based GP, Grammatical Evolution, we evaluate the performance and generalisation of models evolved with different fitness functions on four real-world and ten synthetic datasets, comparing them with traditional logistic classification methods and conducting statistical analysis of the results. The findings demonstrate that in most cases, the LL-evolved models generally yield statistically better performance and better generalisation than the HL-evolved and the ACC-evolved models.

Interpretability is increasingly crucial in artificial intelligence, especially in domains like medicine, where genetic programming, particularly grammatical evolution (GE), can produce models that are potentially interpretable. However, optimizing for predictive accuracy often results in complex expressions that can reduce interpretability. Large language models (LLMs) offer a promising approach to simplify and interpret complex model expressions. Here, we propose incorporating an LLM-guided local search operator into GE to enhance model interpretability in symbolic regression and test this approach for medical prediction. The operator leverages the semantic reasoning and domain knowledge encoded in LLMs to refine candidate expressions through a parallel search mechanism complementary to traditional fitness-driven evolution. Our experiments, conducted on a clinical dataset for glycated hemoglobin prediction, showed that three LLM-guided variants improve interpretability compared to baseline GE, with two showing signs of possible overfitting and the other generalizing better. LLM-generated individuals demonstrated evolutionary viability throughout evolution and direct contribution to the final solutions. Comparison of proprietary and local LLMs revealed challenges with adherence to instructions and creative exploration in smaller models. These results indicate that the proposed approach is a promising strategy for obtaining simpler, more interpretable, and more plausible models.

In this paper we investigate the fitness landscape and evolutionary dynamics of typical genetic algorithms, applied to a well-known problem. For certain settings, we observe that the population can "evolve to extinction", that is after fast progress over early generations, the population fitness can suddenly drop and never recover. We investigate the settings which give rise to this and show how to avoid it in practice, e.g. by varying selection pressure. However our focus is on understanding the root cause. We identify that the cause is a combination of (1) non-uniform initialisation, leading to evolutionary dynamics driven by a diffusion process; and (2) a cliff-edge landscape in which invalid individuals are neighbours of the global optimum. Based on this, we identify other scenarios where these properties can occur. In particular, we identify that non-uniform initialisation is natural in asymmetric search spaces, which we define as search spaces lacking the property of vertex transitivity.

Parkinson's Disease (PD) is a progressive neurodegenerative disorder of the nervous system with a high rate of misdiagnosis. In this paper, we propose a Grammatical Evolution (GE) approach for classifying PD patients, that uses hinge loss as a surrogate fitness function. We compare our approach to standard GE using accuracy as its fitness function. Our results demonstrate that the surrogate fitness approach consistently produces models with better accuracy and reduced complexity. These results highlight the potential of using our approach as a powerful tool for developing trustworthy AI applications in the medical domain.

We propose to embed time series in a latent space where pairwise Euclidean distances (EDs) between samples are equal to pairwise dissimilarities in the original space, for a given dissimilarity measure. To this end, we use auto-encoder (AE) and encoder-only neural networks to learn elastic dissimilarity measures, e.g., dynamic time warping (DTW), that are central to time series classification (Bagnall et al., 2017). The learned representations are used in the context of one-class classification (Mauceri et al., 2020) on the datasets of UCR/UEA archive (Dau et al., 2019). Using a 1-nearest neighbor (1NN) classifier, we show that learned representations allow classification performance that is close to that of raw data, but in a space of substantially lower dimensionality. This implies substantial and compelling savings in terms of computational and storage requirements for nearest neighbor time series classification.

The sudden arrival of the COVID-19 pandemic caused chaos in a multitude of industries and sectors. In many universities around the world, the resulting restrictions forced the closure of campuses, and with face-to-face examinations cancelled, a rapid adaptation of assessment strategies was needed. To adapt to this scenario, we developed a software tool to assist in the design of unique examinations for each student, when using online quizzes. Results from its application to a large cohort of students validate the approach taken, in terms of fairness of assessment, grade distribution, and foul play deterrence. This paper describes the developed approach, its advantages and limitations, and plans for future refinement.

When dealing with a new time series classification problem, modellers do not know in advance which features could enable the best classification performance. We propose an evolutionary algorithm based on grammatical evolution to attain a data-driven feature-based representation of time series with minimal human intervention. The proposed algorithm can select both the features to extract and the sub-sequences from which to extract them. These choices not only impact classification performance but also allow understanding of the problem at hand. The algorithm is tested on 30 problems outperforming several benchmarks. Finally, in a case study related to subject authentication, we show how features learned for a given subject are able to generalise to subjects unseen during the extraction phase.

Supervised learning by means of Genetic Programming (GP) aims at the evolutionary synthesis of a model that achieves a balance between approximating the target function on the training data and generalising on new data. The model space searched by the Evolutionary Algorithm is populated by compositions of primitive functions defined in a function set. Since the target function is unknown, the choice of function set’s constituent elements is primarily guided by the makeup of function sets traditionally used in the GP literature. Our work builds upon previous research of the effects of protected arithmetic operators (i.e. division, logarithm, power) on the output value of an evolved model for input data points not encountered during training. The scope is to benchmark the approximation/generalisation of models evolved using different function set choices across a range of 43 symbolic regression problems. The salient outcomes are as follows. Firstly, Koza’s protected operators of division and exponentiation have a detrimental effect on generalisation, and should therefore be avoided. This result is invariant of the use of moderately sized validation sets for model selection. Secondly, the performance of the recently introduced analytic quotient operator is comparable to that of the sinusoidal operator on average, with their combination being advantageous to both approximation and generalisation. These findings are consistent across two different system implementations, those of standard expression-tree GP and linear Grammatical Evolution. We highlight that this study employed very large test sets, which create confidence when benchmarking the effect of different combinations of primitive functions on model generalisation. Our aim is to encourage GP researchers and practitioners to use similar stringent means of assessing generalisation of evolved models where possible, and also to avoid certain primitive functions that are known to be inappropriate.

In the context of Genetic Programming Symbolic Regression, we empirically investigate the prior on the output prediction, that is, the distribution of the output prior to observing data. We distinguish between the prior due to initialisation and due to evolutionary search. We also investigate the effect on the prior of maximum tree depth and the effect of different function sets and different independent variable distributions. We find that priors are highly diffuse and sometimes include support for extreme values. We compare priors to values for dependent variables observed in benchmarks and real-world problems, finding that mismatches occur and can affect algorithm behaviour and performance. As a further application of our results, we investigate the behaviour of mutation operators in semantic space.

Modern genetic programming (GP) operates within the statistical machine learning (SML) framework. In this framework, evolution needs to balance between approximation of an unknown target function on the training data and generalization, which is the ability to predict well on new data. This paper provides a survey and critical discussion of SML methods that enable GP to generalize.

This paper proposes latent representation models for improving network anomaly detection. Well-known anomaly detection algorithms often suffer from challenges posed by network data, such as high dimension and sparsity, and a lack of anomaly data for training, model selection, and hyperparameter tuning. Our approach is to introduce new regularizers to a classical autoencoder (AE) and a variational AE, which force normal data into a very tight area centered at the origin in the nonsaturating area of the bottleneck unit activations. These trained AEs on normal data will push normal points toward the origin, whereas anomalies, which differ from normal data, will be put far away from the normal region. The models are very different from common regularized AEs, sparse AE, and contractive AE, in which the regularized AEs tend to make their latent representation less sensitive to changes of the input data. The bottleneck feature space is now used as a new data representation. A number of one-class learning algorithms are used for evaluating the proposed models. The experiments testify that our models help these classifiers to perform efficiently and consistently on high-dimensional and sparse network datasets, even with relatively few training points. More importantly, the models can minimize the effect of model selection on these classifiers since their performance is insensitive to a wide range of hyperparameter settings.

Program synthesis is a complex problem domain tackled by many communities via different methods. In the last few years, a lot of progress has been made with Genetic Programming (GP) on solving a variety of general program synthesis problems for which a benchmark suite has been introduced. While Genetic Programming is capable of finding correct solutions for many problems contained in a general program synthesis problems benchmark suite, the actual success rate per problem is low in most cases. In this paper, we analyse certain aspects of the benchmark suite and the computational effort required to solve its problems. A subset of problems on which GP performs poorly is identified. This subset is analysed to find measures to increase success rates for similar problems. The paper concludes with suggestions to refine performance on program synthesis problems.

This paper provides a taxonomical identification survey of classes in discrete optimization challenges that can be found in the literature including a proposed pipeline for benchmarking, inspired by previous computational optimization competitions. Thereby, a Black-Box Discrete Optimization Benchmarking (BB-DOB) perspective is presented for the BB-DOB@GECCO Workshop. It is motivated why certain classes together with their properties (like deception and separability or toy problem label) should be included in the perspective. Moreover, guidelines on how to select significant instances within these classes, the design of experiments setup, performance measures, and presentation methods and formats are discussed.

Supervised learning by means of Genetic Programming aims at the evolutionary synthesis of a model that achieves a balance between approximating the target function on the training data and generalising on new data. In this study we benchmark the approximation / generalisation of models evolved using different function set setups, across a range of symbolic regression problems. Results show that Koza's protected division and power should be avoided, and operators such as analytic quotient and sine should be used instead.

The use of semantic information in genetic programming operators has shown major improvements in recent years, especially in the regression and boolean domain. As semantic information is domain specific, using it in other areas poses certain problems. Semantic operators require being adapted for the problem domain they are applied to. An attempt to create a semantic crossover for program synthesis has been made with rather limited success, but the results have provided insights about using semantics in program synthesis. Based on this initial attempt, this paper presents an improved version of semantic operators for program synthesis, which contains a small but significant change to the overall functionality, as well as a novel measure for the comparison of the semantics of subtrees. The results show that the improved semantic crossover is superior to the previous semantic operator in the program synthesis domain.

For a drug to be approved for human use, its safety and efficacy need to be evidenced through clinical trials. At present, patient recruitment is a major bottleneck in conducting clinical trials. Pharma and contract research organisations (CRO) are actively looking into optimisation of different aspects of patient recruitment. One of the avenues to approach this business problem is to improve the quality of selection of investigators/sites at the start of a trial. This study builds upon previous work that used Grammatical Evolution (GE) to evolve classification models to predict the future patient enrolment performance of investigators/sites considered for a trial. Selection of investigators/sites, depending on the business context, could benefit from the use of either especially conservative or more liberal predictive models. To address this business need, decision-tree type classifiers were evolved utilising different fitness functions to drive GE. The functions compared were classical accuracy, balanced accuracy and F-measure with different values of parameter beta. The issue of models’ generalisability was addressed by introduction of a validation procedure. The predictive power of the resultant GE-evolved models on the test set was compared with performance of a range of machine learning algorithms widely used for classification. The results of the study demonstrate that flexibility of GE induced classification models can be used to address business needs in the area of patient recruitment in clinical trials.

Behaviour Trees are control structures with many applications in computer science, including robotics, control systems, and computer games. They allow the specification of controllers from very broad behaviour definitions (close to the root of the tree) down to very specific technical implementations (near the leaves); this allows them to be understood and extended by both behaviour designers and technical programmers. This chapter describes the process of applying Grammatical Evolution (GE) to evolve Behaviour Trees for a real-time video-game: the Mario AI Benchmark. The results obtained show that these structures are quite amenable to artificial evolution using GE, and can provide a good balance between long-term (pathfinding) and short-term (reactiveness to hazards and power-ups) planning within the same structure.

Program synthesis is a problem domain that due to its importance is tackled by many different fields, one being Genetic Programming. Two variants, Grammar-Guided Genetic Programming (G3P) and PushGP, have been applied to a vast general program synthesis benchmark suite and solved a variety of problems although with varying success rates. While G3P achieved higher success rates on some problems, PushGP was able to find solutions to more problem instances. Reason why G3P fails at some problems might be missing functionality in the grammars or knowledge that has to discovered during the runs. In this paper the current shortcomings of G3P are analysed and the papers contributions include an example of extending grammars for program synthesis, a fairer comparison between PushGP and G3P with a more similar function set as well as new results on problems that have not been solved with G3P and one that has not been solved with PushGP.

Semantic information has been used to create operators that improve performance in genetic programming. As different problem domains have different semantics, extracting semantics and calculating semantic similarity is of tantamount importance to use semantic operators for each domain. To date researchers have struggled to effectively do this beyond the boolean and regression problem domain. In this paper, a semantic similarity-based crossover is tested in the problem domain of program synthesis. For this purpose, a similarity measure based on the execution trace of a program is introduced. Subtree crossover as well as semantic similarity-based crossover are analysed on performance and semantic aspects. The goal is to introduce the Semantic Similarity-based Crossover in the program synthesis domain and to study the effects of using semantic locality. The results show that semantic crossover produces more semantically different children as well as more children that are better than their parents compared to subtree crossover.

A frequently overlooked consideration when using Grammatical Evolution (GE) is grammar design. This is because there is an infinite number of grammars that can specify the same syntax. There are, however, certain aspects of grammar design that greatly affect the speed of convergence and quality of solutions generated with GE. In this chapter, general guidelines for grammar design are presented. These are domain-independent, and can be used when applying GE to any problem. An extensive analysis of their effect and results across a large set of experiments are reported.