Geometric Semantic Genetic Programming (GSGP) is an extension of Genetic Programming (GP) that captured the interest of researchers because of its ability to induce a unimodal error surface for any supervised learning problem. Although still a recent development, the Semantic Learning with Inflate and Deflate Mutations (SLIM-GSGP) extension of GSGP has already attracted significant attention due to its novel ability to generate offspring that are smaller than their parents, effectively addressing the problem of steady model growth in GSGP. This paper presents SLIM-DUO, an extension of SLIM-GSGP that integrates the six existing SLIM-GSGP variants into solely two unified formulations: DUO-MUL and DUO-SUM. This integration streamlines benchmarking and hyperparameter exploration while aiming to retain comparable predictive performance at approximately one third of the computational cost. Across five test problems, SLIM-DUO achieves predictive performance comparable to that of SLIM-GSGP, with model size differences that remain within previously observed dataset-dependent variability among SLIM variants. Overall, SLIM-DUO substantially reduces the computational effort required during both the configuration and benchmarking phases, highlighting a favorable balance between model size and computational complexity and preserving solution quality.

Geometric Semantic Genetic Programming (GSGP) is a variant of Genetic Programming (GP) that induces an error surface without local minima for supervised learning tasks. However, GSGP is limited by the fact that its operators produce increasingly large individuals, leading to overly complex models. The slim addresses this issue by introducing a deflate geometric semantic mutation capable of producing offspring smaller than their parents. Preliminary studies show that slim can maintain accuracy comparable to traditional GSGP while generating much smaller models. However, a thorough analysis of this mutation remains lacking. This work fills that gap by conducting a detailed study of the deflate mutation, focusing on its behavior and practical value. Our results show that, when applied at the right stage of evolution, deflate mutation mitigates overfitting and yields compact, accurate models. This is also the first study to explore the timing and interaction of inflate and deflate mutations in slim, demonstrating how deflation enhances generalization and reduces overfitting. We support our conclusions with a comprehensive experimental approach, including comparisons between exclusive use of inflate mutation and alternating it with deflation. We also evaluate numerical indicators such as improvement rate and training effectiveness. The consistency across these methods reinforces our findings and highlights the deflate mutation as a robust regularization strategy. Finally, when compared to established non-evolutionary machine learning methods, SLIM shows competitive performance. Overall, this study confirms SLIM as a promising direction for GP and lays the foundation for future research.

Like other machine learning methods, Genetic Programming (GP) frequently faces the issue of overfitting when applied to supervised learning tasks. Traditional regularization techniques, though well-studied, are challenging to apply to GP due to the free-form nature of the evolved models. This work proposes a novel approach that prevents overfitting while inherently improving the interpretability of GP models. It involves a dual optimization process that minimizes loss while penalizing functional complexity using multi-objective selection mechanisms. The improved complexity measure used in this study approximates the mathematical curvature of a function in linear time. While loss minimization is common in GP, penalizing functional complexity is an additional step aimed at evolving robust and smooth functions, less prone to overfitting and potentially more interpretable. Experimental results demonstrate the effectiveness of the two variants of our method, benchmarked against standard GP and two of the seemingly best overfitting-reduction methods found in the literature. By focusing on both loss and complexity, our approach achieves state-of-the-art generalization on difficult problems and a strong feature selection that improves interpretability, making it a unified improvement of GP.

This paper presents slim_gsgp: an open-source Python library that provides the first ever framework for the Semantic Learning algorithm based on Inflate and deflate Mutation (SLIM-GSGP). Proposed in 2024, SLIM-GSGP is a promising non-bloating variant of Geometric Semantic Genetic Programming (GSGP). slim_gsgp includes all existing SLIM-GSGP variants, as well as traditional GSGP and standard Genetic Programming (GP), facilitating comparative analysis and benchmarking. Additionally, slim_gsgp's parallel computation and semi-modular architecture renders it not only fast but also user-friendly and easily extensible, thereby serving as a valuable resource for researchers aiming to advance this emerging and promising area of research. The source code and documentation can be accessed at https://github.com/DALabNOVA/slim.

The current trend in machine learning is to use powerful algorithms to induce complex predictive models that often fall under the category of “black-box models”. Thanks to this, there is also a growing interest in studying model explainabil-ity and interpretability so that human experts can understand, validate, and correct those models. With the objective of promoting the creation of inherently interpretable models, we present M6GP. This wrapper-based multi-objective automatic feature engineering algorithm combines key components of the M3GP and NSGA-II algorithms. Wrapping M6GP around another machine learning algorithm evolves a set of features optimized for this algorithm while potentially increasing its robustness. We compare our results with M3GP and M4GP, two ancestors from the same algorithm family, and verify that, by using a multi-objective approach, M6GP obtains equal or better results. In addition, by using complexity metrics on the list of objectives, the M6GP models come down to one-fifth of the size of the M3GP models, making them easier to read by comparison.

This manuscript presents an improved version of the Inclusive Genetic Programming (IGP) algorithm. The IGP was developed to promote and maintain the population's genotypic diversity and showed superior performance compared to standard Genetic Programming (GP). In this work, two modifications to the IGP are proposed: first, the diversity promotion and maintenance mechanism is enhanced with information from the phenotype of the individuals rather than only the genotype; second, the Evolutionary Demes Despeciation Algorithm - V2 (EDDA-V2) is used to initialize the population. The phenotype is considered to differentiate the individuals also according to their behaviour rather than only their structure, while EDDA-V2 is employed to start the evolution with a simultaneously diverse and fit population, contrary to traditional initialization techniques. The algorithms incorporating these improvements are called Full Inclusive Genetic Programming (FIGP) and FIGP _E, respectively with and without the EDDA-V2 initialization. The experimental results, performed over eight benchmarks and considering six algorithms, demonstrate the superior performance of FIGP and FIGP _E in comparison to other GP formulations. Moreover, the EDDA-V2 initialization allows for a significant reduction of the computational time.

Geometric semantic genetic programming (GSGP) and linear scaling (LS) have both, independently, shown the ability to outperform standard genetic programming (GP) for symbolic regression. GSGP uses geometric semantic genetic operators, different from the standard ones, without altering the fitness, while LS modifies the fitness without altering the genetic operators. So far, these two methods have already been joined together in only one practical application. However, to the best of our knowledge, a methodological study on the pros and cons of integrating these two methods has never been performed. In this paper, we present a study of GSGP-LS, a system that integrates GSGP and LS. The results, obtained on five hand-tailored benchmarks and six real-life problems, indicate that GSGP-LS outperforms GSGP in the majority of the cases, confirming the expected benefit of this integration. However, for some particularly hard datasets, GSGP-LS overfits training data, being outperformed by GSGP on unseen data. Additional experiments using standard GP, with and without LS, confirm this trend also when standard crossover and mutation are employed. This contradicts the idea that LS is always beneficial for GP, warning the practitioners about its risk of overfitting in some specific cases.

Allowing the population size to variate during the evolution can bring advantages to evolutionary algorithms (EAs), retaining computational effort during the evolution process. Dynamic populations use computational resources wisely in several types of EAs, including genetic programming. However, so far, a thorough study on the use of dynamic populations in Geometric Semantic Genetic Programming (GSGP) is missing. Still, GSGP is a resource-greedy algorithm, and the use of dynamic populations seems appropriate. This paper adapts algorithms to GSGP to manage dynamic populations that were successful for other types of EAs and introduces two novel algorithms. The novel algorithms exploit the concept of semantic neighbourhood. These methods are assessed and compared through a set of eight regression problems. The results indicate that the algorithms outperform standard GSGP, confirming the suitability of dynamic populations for GSGP. Interestingly, the novel algorithms that use semantic neighbourhood to manage variation in population size are particularly effective in generating robust models even for the most difficult of the studied test problems.

Full-reference image quality measures are a fundamental tool to approximate the human visual system in various applications for digital data management: from retrieval to compression to detection of unauthorized uses. Inspired by both the effectiveness and the simplicity of hand-crafted Structural Similarity Index Measure (SSIM), in this work, we present a framework for the formulation of SSIM-like image quality measures through genetic programming. We explore different terminal sets, defined from the building blocks of structural similarity at different levels of abstraction, and we propose a two-stage genetic optimization that exploits hoist mutation to constrain the complexity of the solutions. Our optimized measures are selected through a cross-dataset validation procedure, which results in superior performance against different versions of structural similarity, measured as correlation with human mean opinion scores. We also demonstrate how, by tuning on specific datasets, it is possible to obtain solutions that are competitive with (or even outperform) more complex image quality measures.

In the field of Machine Learning, one of the most common and discussed questions is how to choose an adequate number of data observations, in order to train our models satisfactorily. In other words, find what is the right amount of data needed to create a model, that is neither underfitted nor overfitted, but instead is able to achieve a reasonable generalization ability. The problem grows in importance when we consider Genetic Programming, where fitness evaluation is often rather slow. Therefore, finding the minimum amount of data that enables us to discover the solution to a given problem could bring significant benefits. Using the notion of entropy in a dataset, we seek to understand the information gain obtainable from each additional data point. We then look for the smallest percentage of data that corresponds to enough information to yield satisfactory results. We present, as a first step, an example derived from the state of art. Then, we question a relevant part of our procedure and introduce two case studies to experimentally validate our theoretical hypothesis.

The growing production of digital content and its dissemination across the worldwide web require eficient and precise management. In this context, image quality assessment measures (IQAMs) play a pivotal role in guiding the development of numerous image processing systems for compression, enhancement, and restoration. The structural similarity index (SSIM) is one of the most common IQAMs for estimating the similarity between a pristine reference image and its corrupted variant. The multi-scale SSIM is one of its most popular variants that allows assessing image quality at multiple spatial scales. This paper proposes a two-stage genetic programming (GP) approach to evolve novel multi-scale IQAMs, that are simultaneously more effective and efficient. We use GP to perform feature selection in the first stage, while the second stage generates the final solutions. The experimental results show that the proposed approach outperforms the existing MS-SSIM. A comprehensive analysis of the feature selection indicates that, for extracting multi-scale similarities, spatially-varying convolutions are more effective than dilated convolutions. Moreover, we provide evidence that the IQAMs learned for one database can be successfully transferred to previously unseen databases. We conclude the paper by presenting a set of evolved multi-scale IQAMs and providing their interpretation.

The global structure of the hyperparameter spaces of neural networks is not well understood and it is therefore not clear which hyperparameter search algorithm will be most effective. In this paper we analyze the landscapes of convolutional neural network architecture search spaces to provide insight into appropriate search algorithms for these spaces. Using a classical fitness landscape analysis approach (fitness distance correlation) and a more recent tool (local optima networks) we study the global structure of these spaces. Our analysis on six image classification datasets reveals that the landscapes are multi-modal, but with relatively few local optima from which it is not hard to escape with a simple perturbation operator. This led us to explore the performance of iterated local search, which we found to more effectively search the training landscapes than three evolutionary algorithm variants. Evolutionary algorithms, however, outperformed iterated local search in terms of generalization on problems with larger discrepancies between the training and testing landscapes.

Livestock is increasingly treated not just as food containers, but as animals that can be susceptible to stress and diseases, affecting, therefore, the production of offspring and the performance of the farm. The breeder needs a simple and useful tool to make the best decisions for his farm, as well as being able to objectively check whether the choices and investments made have improved or worsened its performance. The amount of data is huge but often dispersive: it is therefore essential to provide the farmer with a clear and comprehensible solution, that represents an additional investment. This research proposes a genetic programming approach to predict the yearly number of weaned calves per cow of a farm, namely the measure of its performance. To investigate the efficiency of genetic programming in such a problem, a dataset composed by observations on representative Piedmontese breedings was used. The results show that the algorithm is appropriate, and can perform an implicit feature selection, highlighting important variables and leading to simple and interpretable models.

Fitness landscapes are a useful concept to study the dynamics of meta-heuristics. In the last two decades, they have been applied with success to estimate the optimization power of several types of evolutionary algorithms, including genetic algorithms and genetic programming. However, so far they have never been used to study the performance of machine learning algorithms on unseen data, and they have never been applied to neuroevolution. This paper aims at filling both these gaps, applying for the first time fitness landscapes to neuroevolution and using them to infer useful information about the predictive ability of the method. More specifically, we use a grammar-based approach to generate convolutional neural networks, and we study the dynamics of three different mutations to evolve them. To characterize fitness landscapes, we study autocorrelation and entropic measure of ruggedness. The results show that these measures are appropriate for estimating both the optimization power and the generalization ability of the considered neuroevolution configurations.

Machine Learning (ML) has now become an important and ubiquitous tool in science and engineering, with successful applications in many real-world domains. However, there are still areas in need of improvement, and problems that are still considered difficult with off-the-shelf methods. One such problem is Multi Target Regression (MTR), where the target variable is a multidimensional tuple instead of a scalar value. In this work, we propose a more difficult variant of this problem which we call Unlabeled MTR (uMTR), where the structure of the target space is not given as part of the training data. This version of the problem lies at the intersection of MTR and clustering, an unexplored problem type. Moreover, this work proposes a solution method for uMTR, a hybrid algorithm based on Genetic Programming and RANdom SAmple Consensus (RANSAC). Using a set of benchmark problems, we are able to show that this approach can effectively solve the uMTR problem.

Computational Intelligence (CI) is a computer science discipline encompassing the theory, design, development and application of biologically and linguistically derived computational paradigms. Traditionally, the main elements of CI are Evolutionary Computation, Swarm Intelligence, Fuzzy Logic, and Neural Networks. CI aims at proposing new algorithms able to solve complex computational problems by taking inspiration from natural phenomena. In an intriguing turn of events, these nature-inspired methods have been widely adopted to investigate a plethora of problems related to nature itself. In this paper we present a variety of CI methods applied to three problems in life sciences, highlighting their effectiveness: we describe how protein folding can be faced by exploiting Genetic Programming, the inference of haplotypes can be tackled using Genetic Algorithms, and the estimation of biochemical kinetic parameters can be performed by means of Swarm Intelligence. We show that CI methods can generate very high quality solutions, providing a sound methodology to solve complex optimization problems in life sciences.

Bakurov, I., Castelli, M., Fontanella, F., & Vanneschi, L. (2019). A regression-like classification system for geometric semantic genetic programming. In J. J. Merelo, J. Garibaldi, A. Linares-Barranco, K. Madani, K. Warwick, & K. Warwick (Eds.), Proceedings of the 11th International Joint Conference on Computational Intelligence (IJCCI 2019) (Vol. 1, pp. 40-48). (IJCCI 2019 - Proceedings of the 11th International Joint Conference on Computational Intelligence). SciTePress.

Re, A., Vanneschi, L., & Castelli, M. (2019). Universal learning machine with genetic programming. In J. J. Merelo, J. Garibaldi, A. Linares-Barranco, K. Madani, K. Warwick, & K. Warwick (Eds.), Proceedings of the 11th International Joint Conference on Computational Intelligence (Vol. 1, pp. 115-122). (IJCCI 2019 - Proceedings of the 11th International Joint Conference on Computational Intelligence). Viena: SciTePress.

RNA inverse folding problem is a bioinformatics problem where the objective is to find an RNA sequence that folds into a given target secondary structure. In this paper, we use evolutionary computation to solve a new and innovative multiobjective definition of this problem. In this new multiobjective definition of the problem, we have considered the similarity between target and predicted structures as a constraint, and three objective functions: 1) partition function (free energy of the ensemble); 2) ensemble diversity; and 3) nucleotides composition. The multiobjective metaheuristic to design RNA sequences (m2dRNAs) proposed in this paper is compared against other RNA inverse folding methods published in the literature, such as RNAinverse, RNA secondary structure designer, inverse folding of RNA, MODENA, NUPACK, fRNAkenstein, dynamics in sequence space optimization, RNAiFOLD, antaRNA, evolutionary RNA design, and Eterna players. After a comprehensive comparative study on two well-known benchmarks (Rfam and Eterna100), we conclude that m2dRNAs is capable of obtaining very promising results in terms of both quality of RNA designs and required runtime. The source code of m2dRNAs is available at http://arco.unex.es/arl/m2dRNAs-source_code.zip.

The multiple sequence alignment is a well-known bioinformatics problem that consists in the alignment of three or more biological sequences (protein or nucleic acid). In the literature, a number of tools have been proposed for dealing with this biological sequence alignment problem, such as progressive methods, consistency-based methods, or iterative methods; among others. These aligners often use a default parameter configuration for all the input sequences to align. However, the default configuration is not always the best choice, the alignment accuracy of the tool may be highly boosted if specific parameter configurations are used, depending on the biological characteristics of the input sequences. In this paper, we propose a characteristic-based framework for multiple sequence aligners. The idea of the framework is, given an input set of unaligned sequences, extract its characteristics and run the aligner with the best parameter configuration found for another set of unaligned sequences with similar characteristics. In order to test the framework, we have used the well-known multiple sequence comparison by log-expectation (MUSCLE) v3.8 aligner with different benchmarks, such as benchmark alignments database v3.0, protein reference alignment benchmark v4.0, and sequence alignment benchmark v1.65. The results shown that the alignment accuracy and conservation of MUSCLE might be greatly improved with the proposed framework, specially in those scenarios with a low percentage of identity. The characteristic-based framework for multiple sequence aligners is freely available for downloading at http://arco.unex.es/arl/fwk-msa/cbf-msa.zip.

Genetic Programming (GP) has been around for over two decades and has been used in a wide range of practical applications producing human competitive results in several domains. In this paper we present a discussion and a proposal of a GP algorithm that could be conveniently implemented on an embedded system, as part of a broader research project that pursues the implementation of a complete GP system in a Field Programmable Gate Array (FPGA). Motivated by the significant time savings associated with such a platform, as well as low power consumption, low maintenance requirements, small size of the system and the possibility of performing several parallel processes. The proposal is focused on the Geometric Semantic Genetic Programming (GSGP) approach that has been recently introduced with promising results. GSGP induces a unimodal fitness landscape, simplifying the search process. The experimental work considers five variants of GSGP, that incorporate local search strategies, optimal mutations and alignment in error space. Best results were obtained by a simple variant that uses both the optimal mutation step and the standard geometric semantic mutation, using three difficult real-world problems to evaluate the methods, outperforming the original GSGP formulation in terms of fitness and empirical convergence.

Initializing the population is a crucial step for genetic programming, and several strategies have been proposed so far. The issue is particularly important for geometric semantic genetic programming, where initialization is known to play a very important role. In this paper, we propose an initialization technique inspired by the biological phenomenon of demes despeciation, i.e. the combination of demes of previously distinct species into a new population. In synthesis, the initial population of geometric semantic genetic programming is created using the best individuals of a set of separate subpopulations, or demes, some of which run standard genetic programming and the others geometric semantic genetic programming for few generations. Geometric semantic genetic programming with this novel initialization technique is shown to outperform geometric semantic genetic programming using the traditional ramped half-and-half algorithm on six complex symbolic regression applications. More specifically, on the studied problems, the proposed initialization technique allows us to generate solutions with comparable or even better generalization ability, and of significantly smaller size than the ramped half-and-half algorithm.

Geometric semantic genetic programming is a hot topic in evolutionary computation and recently it has been used with success on several problems from Biology and Medicine. Given the young age of geometric semantic genetic programming, in the last few years theoretical research, aimed at improving the method, and applicative research proceeded rapidly and in parallel. As a result, the current state of the art is confused and presents some “holes”. For instance, some recent improvements of geometric semantic genetic programming have never been applied to some popular biomedical applications. The objective of this paper is to fill this gap. We consider the biomedical applications that have more frequently been used by genetic programming researchers in the last few years and we systematically test, in a consistent way, using the same parameter settings and configurations, all the most popular existing variants of geometric semantic genetic programming on all those applications. Analysing all these results, we obtain a much more homogeneous and clearer picture of the state of the art, that allows us to draw stronger conclusions.

In the last few years, geometric semantic genetic programming has incremented its popularity, obtaining interesting results on several real life applications. Nevertheless, the large size of the solutions generated by geometric semantic genetic programming is still an issue, in particular for those applications in which reading and interpreting the final solution is desirable. In this paper, we introduce a new parallel and distributed genetic programming system, with the objective of mitigating this drawback. The proposed system (called MPHGP, which stands for Multi-Population Hybrid Genetic Programming) is composed by two subpopulations, one of which runs geometric semantic genetic programming, while the other runs a standard multi-objective genetic programming algorithm that optimizes, at the same time, training error and the size of the solutions. The two subpopulations evolve independently and in parallel, exchanging individuals at prefixed synchronization instants. The presented experimental results, obtained on five real-life symbolic regression applications, suggest that MPHGP is able to find solutions that are comparable, or even better, than the ones found by geometric semantic genetic programming, both on training and on unseen testing data. At the same time, MPHGP is also able to find solutions that are significantly smaller than the ones found by geometric semantic genetic programming.

Since its introduction, Geometric Semantic Genetic Programming (GSGP) has aroused the interest of numerous researchers and several studies have demonstrated that GSGP is able to effectively optimize training data by means of small variation steps, that also have the effect of limiting overfitting. In order to speed up the search process, in this paper we propose a system that integrates a local search strategy into GSGP (called GSGP-LS). Furthermore, we present a hybrid approach, that combines GSGP and GSGP-LS, aimed at exploiting both the optimization speed of GSGP-LS and the ability to limit overfitting of GSGP. The experimental results we present, performed on a set of complex real-life applications, show that GSGP-LS achieves the best training fitness while converging very quickly, but severely overfits. On the other hand, GSGP converges slowly relative to the other methods, but is basically not affected by overfitting. The best overall results were achieved with the hybrid approach, allowing the search to converge quickly, while also exhibiting a noteworthy ability to limit overfitting. These results are encouraging, and suggest that future GSGP algorithms should focus on finding the correct balance between the greedy optimization of a local search strategy and the more robust geometric semantic operators.

The paper above (ibid., vol. 44, no. 1, pp. 103-113, Jan. 2014), was printed with the incorrect author list as follows: M. Castelli, L. Vanneschi, S. Silva, A. Agapitos, and M. O'Neill. The correct author list is: M. Castelli, L. Vanneschi and S. Silva.

The concept of semantics (in the sense of input-output behavior of solutions on training data) has been the subject of a noteworthy interest in the genetic programming (GP) research community over the past few years. In this paper, we present a new GP system that uses the concept of semantics to improve search effectiveness. It maintains a distribution of different semantic behaviors and biases the search toward solutions that have similar semantics to the best solutions that have been found so far. We present experimental evidence of the fact that the new semantics-based GP system outperforms the standard GP and the well-known bacterial GP on a set of test functions, showing particularly interesting results for noncontinuous (i.e., generally harder to optimize) test functions. We also observe that the solutions generated by the proposed GP system often have a larger size than the ones returned by standard GP and bacterial GP and contain an elevated number of introns, i.e., parts of code that do not have any effect on the semantics. Nevertheless, we show that the deletion of introns during the evolution does not affect the performance of the proposed method.

Reaction systems is a formalism inspired by chemical reactions introduced by Rozenberg and Ehrenfeucht. Recently, an evolutionary algorithm based on this formalism, called Evolutionary Reaction Systems, has been presented. This new algorithm proved to have comparable performances to other well-established machine learning methods, like genetic programming, neural networks and support vector machines on both artificial and real-life problems. Even if the results are encouraging, to make Evolutionary Reaction Systems an established evolutionary algorithm, an in depth analysis of the effect of its parameters on the search process is needed, with particular focus on those parameters that are typical of Evolutionary Reaction Systems and do not have a counterpart in traditional evolutionary algorithms. Here we address this problem for the first time. The results we present show that one particular parameter, between the ones tested, has a great influence on the performances of Evolutionary Reaction Systems, and thus its setting deserves practitioners' particular attention: the number of symbols used to represent the reactions that compose the system. Furthermore, this work represents a first step towards the definition of a set of default parameter values for Evolutionary Reaction Systems, that should facilitate their use for beginners or inexpert practitioners.

Genetic programming (GP) is not a field noted for the rigor of its benchmarking. Some of its benchmark problems are popular purely through historical contingency, and they can be criticized as too easy or as providing misleading information concerning real-world performance, but they persist largely because of inertia and the lack of good alternatives. Even where the problems themselves are impeccable, comparisons between studies are made more difficult by the lack of standardization. We argue that the definition of standard benchmarks is an essential step in the maturation of the field. We make several contributions towards this goal. We motivate the development of a benchmark suite and define its goals; we survey existing practice; we enumerate many candidate benchmarks; we report progress on reference implementations; and we set out a concrete plan for gathering feedback from the GP community that would, if adopted, lead to a standard set of benchmarks.

The NK landscapes are a well known benchmark for genetic algorithms (GAs) in which it is possible to tune the ruggedness of the fitness landscape by simply modifying the value of a parameter K. They have successfully been used in many theoretical studies, allowing researchers to discover interesting properties of the GAs dynamics in presence of rugged landscapes. A similar benchmark does not exist for genetic programming (GP) yet. Nevertheless, during the EuroGP conference debates of the last few years, the necessity of defining new benchmark problems for GP has repeatedly been expressed by a large part of the attendees. This paper is intended to fill this gap, by introducing an extension of the NK landscapes to tree based GP, that we call K landscapes. In this benchmark, epistasis are expressed as growing mutual interactions between the substructures of a tree as the parameter K increases. The fact that the problem becomes more and more difficult as the value of K increases is experimentally demonstrated. Interestingly, we also show that GP "bloats" more and more as K increases.

Generalization is an important issue in machine learning. In fact, in several applications good results over training data are not as important as good results over unseen data. While this problem was deeply studied in other machine learning techniques, it has become an important issue for genetic programming only in the last few years. In this paper we compare the generalization ability of several different genetic programming frameworks, including some variants of multi-objective genetic programming and operator equalization, a recently defined bloat free genetic programming system. The test problem used is a hard regression real-life application in the field of drug discovery and development, characterized by a high number of features and where the generalization ability of the proposed solutions is a crucial issue. The results we obtained show that, at least for the considered problem, multi-optimization is effective in improving genetic programming generalization ability, outperforming all the other methods on test data.

The classification of cancer patients into risk classes is a very active field of research, with direct clinical applications. We have recently compared several machine learning methods on the well known 70-genes signature dataset. In that study, genetic programming showed promising results, given that it outperformed all the other techniques. Nevertheless, the study was preliminary, mainly because the validation dataset was preprocessed and all its features binarized in order to use logical operators for the genetic programming functional nodes. If this choice allowed simple interpretation of the solutions from the biological viewpoint, on the other hand the binarization of data was limiting, since it amounts to a sizable loss of information. The goal of this paper is to overcome this limitation, using the 70-genes signature dataset with real-valued expression data. The results we present show that genetic programming using the number of incorrectly classified instances as fitness function is not able to outperform the other machine learning methods. However, when a weighted average between false positives and false negatives is used to calculate fitness values, genetic programming obtains performances that are comparable with the other methods in the minimization of incorrectly classified instances and outperforms all the other methods in the minimization of false negatives, which is one of the main goals in breast cancer clinical applications. Also in this case, the solutions returned by genetic programming are simple, easy to understand, and they use a rather limited subset of the available features.

Distances that are bound to (or consistent with) genetic operators are measures that quantify the difficulty of reaching and individual (or a population) starting from another individual (or population) and applying the genetic operator iteratively. Defining distance measures bound to genetic operators is a very important task in evolutionary computation. In fact these distances usually make the analysis of some indicators of the the search process, like for instance population diversity or well-known measures of problem hardness such as fitness distance correlation, more accurate. In this paper, we introduce a distance measure bound to one point standard crossover for genetic algorithms. This measure quantifies the minimum number of crossover operations that have to be applied to a population to tranform it into another population. It is based on the definition of a lattice over some particular schemata that represent the individuals in the population and on the construction of a discrete dynamic system that models the dynamics of the genetic algorithm under the sole effect of crossover. Using this distance measure, it is also possible to build a family of distances between individuals.

The Sharpened No Free Lunch theorem states that all optimization algorithms have the same performance on sets of functions that are closed under permutation, independently of the considered performance measure. However, not all performance measures are informative on how fast or how accurately an algorithm can solve a given problem. In this paper we focus on a particular performance measure, called optimization speed, that quantifies how fast a search algorithm is able to find an optimal solution, and we try to characterize the set of functions on which all possible search algorithms have the same optimization speed. We call fair these sets, and we prove some results about their structure, the number of such sets and the computational complexity of checking fairness.

The goal of this paper is to present four new parallel and distributed particle swarm optimization methods. and to experimentally compare their performances. These methods include a genetic algorithm whose individuals are co-evolving swarms, a different multi-swarm system and their respective variants enriched by adding a repulsive component to the particles. We have tried to carry out this comparison using the benchmark test suite that has been defined for the CEC-2005 numerical optimization competition and we have remarked that it is hard to have a clear picture of the experimental results on that benchmark suite. We believe that this is due to the fact that the CEC-2005 benchmark suite is only composed by either very easy or very hard test functions. For this reason, we introduce two new sets of test functions whose difficulty can be tuned by simply modifying the values of few real-valued parameters. We propose to integrate the CEC-2005 benchmark suite by adding these sets of test functions to it. Experimental results on these two sets of test functions clearly show that the proposed repulsive multi-swarm system outperforms all the other presented methods.

Recent contributions clearly show that eliminating bloat in a genetic programming system does not necessarily eliminate overfitting and vice-versa. This fact seems to contradict a common agreement of many researchers known as the minimum description length principle, which states that the best model is the one that minimizes the amount of information needed to encode it. Another common agreement is that overfitting should be, in some sense, related to the functional complexity of the model. The goal of this paper is to define three measures to respectively quantify bloat, overfitting and functional complexity of solutions and show their suitability on a set of test problems including a simple bidimensional symbolic regression test function and two real-life multidimensional regression problems. The experimental results are encouraging and should pave the way to further investigation. Advantages and drawbacks of the proposed measures are discussed, and ways to improve them are suggested. In the future, these measures should be useful to study and better understand the relationship between bloat, overfitting and functional complexity of solutions.

Operator equalisation was recently proposed as a new bloat control technique for genetic programming. By controlling the distribution of program lengths inside the population, it can bias the search towards smaller or larger programs. In this paper we propose a new implementation of operator equalisation and compare it to a previous version, using a hard real-world regression problem where bloat and overfitting are major issues. The results show that both implementations of operator equalisation are completely bloat-free, producing smaller individuals than standard genetic programming, without compromising the generalization ability. We also show that the new implementation of operator equalisation is more efficient and exhibits a more predictable and reliable behavior than the previous version. We advance some arguable ideas regarding the relationship between bloat and overfitting, and support them with our results.

A new model of Genetic Programming with variable size population is presented in this paper and applied to the reconstruction of target functions in dynamic environments (i.e. problems where target functions change with time). The suitability of this model is tested on a set of benchmarks based on some well known symbolic regression problems. Experimental results confirm that our variable size population model finds solutions of the same quality as the ones found by standard Genetic Programming, but with a smaller amount of computational effort.

Generalization is a very important issue in Machine Learning. In this paper, we present a new idea for improving Genetic Programming generalization ability. The idea is based on a dynamic two-layered selection algorithm and it is tested on a real-life drug discovery regression application. The algorithm begins using root mean squared error as fitness and the usual tournament selection. A list of individuals called ``repulsors'' is also kept in memory and initialized as empty. As an individual is found to overfit the training set, it is inserted into the list of repulsors. When the list of repulsors is not empty, selection becomes a two-layer algorithm: individuals participating to the tournament are not randomly chosen from the population but are themselves selected, using the average dissimilarity to the repulsors as a criterion to be maximized. Two kinds of similarity/dissimilarity measures are tested for this aim: the well known structural (or edit) distance and the recently defined subtree crossover based similarity measure. Although simple, this idea seems to improve Genetic Programming generalization ability and the presented experimental results show that Genetic Programming generalizes better when subtree crossover based similarity measure is used, at least for the test problems studied in this paper.

Fitness-Proportional Negative Slope Coefficient is a fitness landscapes measure that has recently been introduced as a potential indicator of problem hardness for optimisation. It is inspired to an older measure, the Negative Slope Coefficient, and it has been theoretically modelled. Preliminary experiments have suggested that it may be a good predictor of problem hardness. However, this measure has not undergone any convincing and comprehensive empirical testing. Our objective is to fill this gap. So, we perform empirical tests using a large set of invertible functions of unitation. We find that while this measure may correctly predict the degree of evolvability of a landscape, this does not necessarily correlate with the difficulty of problems. Some landscapes may show, for example, limited evolvability and yet be easy to solve because either solutions are already present in the initial population or the computational resources provided exceed evolvability obstacles. Or it may be impossible to solve them irrespective of their evolvability simply because they are far too vast for the computational resources provided. These situations are hardly captured by the Fitness-Proportional Negative Slope Coefficient.

One of the most complete techniques that can be used to digitize an artefact is to generate its photo-textured 3D model, which combines high precision metrical information with a faithful color description of the object surfaces. In this work we focus on how to obtain reliable color information by colorimetrically characterizing the color sensors of the imaging device. To this end, a novel target based characterization procedure is proposed that exploits empirical polynomial modeling for colorimetric data estimation. Experimental results are reported and discussed.

The crossover bias theory for bloat [18] is a recent result which predicts that bloat is caused by the sampling of short, unfit programs. This theory is clear and simple, but it has some weaknesses: (1) it implicitly assumes that the population is large enough to allow sampling of all relevant program sizes (although it does explain what to expect in the many practical cases where this is not true, e.g., because the population is small); (2) it does not explain what is meant by its assumption that short programs are unfit.

Elitism is commonly used in generational GP to ensure that the best individuals discovered in a generation are not lost, and are made available for possible further improvements to new generations. Using two GP systems and four problems, we show how elitism reduces the growth of mean program size.

In evolutionary algorithms, distance metrics between solutions are often useful for many aspects of guiding and understanding the search process. A good distance measure should reflect the capability of the search: if two solutions are found to be close in distance, or similarity, they should also be close in the search algorithm sense, i.e., the variation operator used to traverse the search space should easily transform one of them into the other. This paper explores such a distance for genetic programming syntax trees. Distance measures are discussed, defined and empirically investigated. The value of such measures is then validated in the context of analysis (fitness-distance correlation is analyzed during population evolution) as well as guiding search (results are improved using our measure in a fitness sharing algorithm) and diversity (new insights are obtained as compared with standard measures).

The Negative Slope Coefficient (nsc) is an empirical measure of problem hardness based on the analysis of offspring-fitness vs. parent-fitness scatterplots. The nsc has been tested empirically on a large variety problems showing considerable reliability in distinguishing easy from hard problems. However, neither a theoretical justification nor a theoretical analysis of the nsc have ever been given. This paper presents a modification of nsc, the fitness-proportional negative slope coefficient (fpncs), for which it is possible to give a theoretical explanation and analysis. To illustrate the approach we compute fpnsc theoretically for the class of invertible functions of unitation, and for two mutation operators. We apply the theory to compute fpnsc for three benchmark functions: Onemax, Trap and Onemix. We then compare the predictions of fpnsc with the success probability recorded in actual runs. The results suggest that fpnsc is able to broadly discriminate between easy and hard GA problems.

No abstract available.

Automatically assessing the value of bioavailability from the chemical structure of a molecule is a very important issue in biomedicine and pharmacology. In this paper, we present an empirical study of some well known Machine Learning techniques, including various versions of Genetic Programming, which have been trained to this aim using a dataset of molecules with known bioavailability. Genetic Programming has proven the most promising technique among the ones that have been considered both from the point of view of the accurateness of the solutions proposed, of the generalization capabilities and of the correlation between predicted data and correct ones. Our work represents a first answer to the demand for quantitative bioavailability estimation methods proposed in literature, since the previous contributions focus on the classification of molecules into classes with similar bioavailability.

Cooperative coevolution has proven to be a promising technique for solving complex combinatorial optimization problems. In this paper, we present four different strategies which involve cooperative coevolution of a genetic program and of a population of constants evolved by a genetic algorithm. The genetic program evolves expressions that solve a problem, while the genetic algorithm provides "good" values for the numeric terminal symbols used by those expressions. Experiments have been performed on three symbolic regression problems and on a "real-world" biomedical application. Results are encouraging and confirm that our coevolutionary algorithms can be used effectively in different domains.

Neutrality of some boolean parity fitness landscapes is investigated in this paper. Compared with some well known contributions on the same issue, we define some new measures that help characterizing neutral landscapes, we use a new sampling methodology, which captures some features that are disregarded by uniform random sampling, and we introduce new genetic operators to define the neighborhood of tree structures. We compare the fitness landscape induced by two different sets of functional operators (SNand and SXorNot). The different characteristics of the neutral networks seem to justify the different difficulties of these landscapes for genetic programming.

In this paper we propose a memetic algorithm in which a local search step, also based on evolutionary principles, is added to a conventional evolutionary algorithm. In particular, we have considered a basic experimental setup in which a genetic algorithm (GA) is used to optimize the numeric terminals of programs evolved using genetic programming (GP). We present results obtained in testing our approach on symbolic regression problems and compare them to results obtained on the same problems by similar approaches which incorporated non-evolutionary local search optimization. The paper presents a set of results obtained with a basic scheme in which GP and GA steps alternate with prefixed frequency. We also present some preliminary results obtained with a more complex, general and potentially more performing scheme in which the same idea has been translated into a coevolutionary environment. In this coevolutionary scheme, the fitness of GA individuals, which encode numerical values, is proportional to the fitness that is globally achieved by GP individuals which use them as terminals. We envision this as the simplest possible implementation of a general coevolutionary scheme in which heterogeneous populations evolve, driven by a fitness function that reflects their capability to either solve the main problem or to contribute to other individuals that are tackling it.

We present an approach to genetic programming difficulty based on a statistical study of program fitness landscapes. The fitness distance correlation is used as an indicator of problem hardness and we empirically show that such a statistic is adequate in nearly all cases studied here. However, fitness distance correlation has some known problems and these are investigated by constructing an artificial landscape for which the correlation gives contradictory indications. Although our results confirm the usefulness of fitness distance correlation, we point out its shortcomings and give some hints for improvement in assessing problem hardness in genetic programming.

New techniques for dynamically changing the size of populations during the execution of genetic programming systems are proposed. Two models are presented, allowing to add and suppress individuals on the basis of some particular events occurring during the evolution. These models allow to find solutions of better quality, to save considerable amounts of computational effort and to find optimal solutions more quickly, at least for the set of problems studied here, namely the artificial ant on the Santa Fe trail, the even parity 5 problem and one instance of the symbolic regression problem. Furthermore, these models have a positive effect on the well known problem of bloat and act without introducing additional computational cost.

A new technique for saving computing resources when using genetic programming is presented in this work. Instead of directly fighting bloat $the main factor explaining the large computational cost required for the evaluation of generations - by acting on individuals, we apply a new operator to the whole population: the plague. By removing some individuals every generation, we compensate for the increase in size of individuals, thus saving computing time when looking for solutions.

This paper presents a study that evaluates the influence of the parallel genetic programming (GP) models in maintaining diversity in a population. The parallel models used are the cellular and the multipopulation one. Several measures of diversity are considered to gain a deeper understanding of the conditions under which the evolution of both models is successful. Three standard test problems are used to illustrate the different diversity measures and analyze their correlation with performance. Results show that diversity is not necessarily synonym of good convergence.

The fitness distance correlation coefficient has been shown to be a reasonable measure to quantify problem difficulty in genetic algorithms and genetic programming for a wide set of problems. In this paper we present an hand-tailored function for which fitness distance correlation fails to correctly predict problem difficulty in genetic programming. This counterexample proves that fitness distance correlation, although reliable, is not an infallible measure to quantify problem difficulty.

In this paper we present a study of parallel and distributed genetic programming models and their relationships with the bloat phenomenon. The experiments that we have performed have also allowed us to find an interesting link between the number of processes, subpopulations and the model we should use when applying parallelism to GP. We study the synchronous and asynchronous version of the island-model in GP domain.

We present an environment for distributed genetic programming using MPI. Genetic programming is a stochastic evolutionary learning methodology that can greatly benefit from parallel/distributed implementations. We describe the distributed system, as well as a user-friendly graphical interface to the tool. The usefulness of the distributed setting is demonstrated by the results obtained to date on several difficult problems, two of which are described in the text.