Search

Bakurov, I., Buzzelli, M., Castelli, M., Schettini, R., & Vanneschi, L. (2022). Genetic programming for structural similarity design at multiple spatial scales. In GECCO ’22. Proceedings of the 2022 Genetic and Evolutionary Computation Conference (pp. 911-919). (GECCO 2022 - The Genetic and Evolutionary Computation Conference, July 9-13, Boston, US). Association for Computing Machinery (ACM). ISBN 978-1-4503-9237-2/22/07 ---- Funding Information: FCT Portugal partially supported this work, under the grand SFRH/BD/137277/2018, and through projects BINDER (PTDC/CCI-INF/29168/2017) and AICE (DSAIPA/DS/ 0113/2019). 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. authorsversion published

Bakurov, I., Buzzelli, M., Castelli, M., Schettini, R., & Vanneschi, L. (2020). Parameters optimization of the Structural Similarity Index. In London Imaging Meeting 2020: Future Colour Imaging (1 ed., Vol. 2020, pp. 19-23). (London Imaging Meeting). https://doi.org/10.2352/issn.2694-118X.2020.LIM-13 We exploit evolutionary computation to optimize the handcrafted Structural Similarity method (SSIM) through a datadriven approach. We estimate the best combination of luminance, contrast and structure components, as well as the sliding window size used for processing, with the objective of optimizing the similarity correlation with human-expressed mean opinion score on a standard dataset. We experimentally observe that better results can be obtained by penalizing the overall similarity only for very low levels of luminance similarity. Finally, we report a comparison of SSIM with the optimized parameters against other metrics for full reference quality assessment, showing superior performance on a different dataset. publishersversion published

Bakurov, I., Buzzelli, M., Schettini, R., Castelli, M., & Vanneschi, L. (2022). Structural similarity index (SSIM) revisited: A data-driven approach. Expert Systems with Applications, 189, 1-19. [116087]. [Advanced online publication on 27 October 2021]. https://doi.org/10.1016/j.eswa.2021.116087--------------Funding Information: This work was supported by national funds through the FCT (Funda??o para a Ci?ncia e a Tecnologia), Portugal by the projects GADgET (DSAIPA/DS/0022/2018), BINDER (PTDC/CCIINF/29168/2017), and AICE (DSAIPA/DS/0113/2019). Mauro Castelli acknowledges the financial support from the Slovenian Research Agency, Slovenia (research core funding no. P5-0410). Several contemporaneous image processing and computer vision systems rely upon the full-reference image quality assessment (IQA) measures. The single-scale structural similarity index (SS-SSIM) is one of the most popular measures, and it owes its success to the mathematical simplicity, low computational complexity, and implicit incorporation of Human Visual System’s (HVS) characteristics. In this paper, we revise the original parameters of SSIM and its multi-scale counterpart (MS-SSIM) to increase their correlation with subjective evaluation. More specifically, we exploit the evolutionary computation and the swarm intelligence methods on five popular IQA databases, two of which are dedicated distance-changed databases, to determine the best combination of parameters efficiently. Simultaneously, we explore the effect of different scale selection approaches in the context of SS-SSIM. The experimental results show that with a proper fine-tuning (1) the performance of SS-SSIM and MS-SSIM can be improved, in average terms, by 8% and by 3%, respectively, (2) the SS-SSIM after the so-called standard scale selection achieves similar performance as if applying computationally more expensive state-of-the-art scale selection methods or MS-SSIM; moreover, (3) there is evidence that the parameters learned on a given database can be successfully transferred to other (previously unseen) databases; finally, (4) we propose a new set of reference parameters for SSIM’s variants and provide their interpretation. authorsversion published

Besozzi, D., Manzoni, L., Nobile, M. S., Spolaor, S., Castelli, M., Vanneschi, L., ... Tangherloni, A. (2020). Computational Intelligence for Life Sciences. Fundamenta Informaticae, 171(1-4), 57-80. https://doi.org/10.3233/FI-2020-1872 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. authorsversion published

In this work, we study the influence of the population size on the learning ability of Geometric Semantic Genetic Programming for the task of symbolic regression. A large set of experiments, considering different population size values on different regression problems, has been performed. Results show that, on real-life problems, having small populations results in a better training fitness with respect to the use of large populations after the same number of fitness evaluations. However, performance on the test instances varies among the different problems: in datasets with a high number of features, models obtained with large populations present a better performance on unseen data, while in datasets characterized by a relative small number of variables a better generalization ability is achieved by using small population size values. When synthetic problems are taken into account, large population size values represent the best option for achieving good quality solutions on both training and test instances.

SFX(opens in a new window)|View at Publisher| Export | Download | More... IEEE Transactions on Cybernetics Volume 44, Issue 1, January 2014, Article number 6476653, Pages 103-113 Semantic search-based genetic programming and the effect of intron deletion (Article) Castelli, M.a , Vanneschi, L.a , Silva, S.a , Agapitos, A.b , Oneill, M.b a Instituto de Engenharia de Sistemas e Computadores-Investigacao e Desenvolvimento em Lisboa, IST/UTL, Lisboa, Portugal b Natural Computing Research and Applications Group, University College Dublin, IRL, Ireland View references (30) Abstract 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. © 2013 IEEE.

Concrete is a composite construction material made primarily with aggregate, cement, and water. In addition to the basic ingredients used in conventional concrete, high-performance concrete incorporates supplementary cementitious materials, such as fly ash and blast furnace slag, and chemical admixture, such as superplasticizer. Hence, high-performance concrete is a highly complex material and modeling its behavior represents a difficult task. In this paper, we propose an intelligent system based on Genetic Programming for the prediction of high-performance concrete strength. The system we propose is called Geometric Semantic Genetic Programming, and it is based on recently defined geometric semantic genetic operators for Genetic Programming. Experimental results show the suitability of the proposed system for the prediction of concrete strength. In particular, the new method provides significantly better results than the ones produced by standard Genetic Programming and other machine learning methods, both on training and on out-of-sample data. © 2013 Elsevier Ltd. All rights reserved.

Big data knowledge discovery emerged as an important factor contributing to advancements in society at large. Still, researchers continuously seek to advance existing methods and provide novel ones for analysing vast data sets to make sense of the data, extract useful information, and build knowledge to inform decision making. In the last few years, a very promising variant of genetic programming was proposed: geometric semantic genetic programming. Its difference with the standard version of genetic programming consists in the fact that it uses new genetic operators, called geometric semantic operators, that, acting directly on the semantics of the candidate solutions, induce by definition a unimodal error surface on any supervised learning problem, independently from the complexity and size of the underlying data set. This property should improve the evolvability of genetic programming in presence of big data and thus makes geometric semantic genetic programming an extremely promising method for mining vast amounts of data. Nevertheless, to the best of our knowledge, no contribution has appeared so far to employ this new technology to big data problems. This paper intends to fill this gap. For the first time, in fact, we show the effectiveness of geometric semantic genetic programming on several complex real-life problems, characterized by vast amounts of data, coming from several different application domains.

Bloat can be defined as an excess of code growth without a corresponding improvement in fitness. This problem has been one of the most intensively studied subjects since the beginnings of Genetic Programming. This paper begins by briefly reviewing the theories explaining bloat, and presenting a comprehensive survey and taxonomy of many of the bloat control methods published in the literature through the years. Particular attention is then given to the new Crossover Bias theory and the bloat control method it inspired, Operator Equalisation (OpEq). Two implementations of OpEq are described in detail. The results presented clearly show that Genetic Programming using OpEq is essentially bloat free. We discuss the advantages and shortcomings of each different implementation, and the unexpected effect of OpEq on overfitting. We observe the evolutionary dynamics of OpEq and address its potential to be extended and integrated into different elements of the evolutionary process. © Springer Science+Business Media, LLC 2011.

We introduce the special issue on Evolutionary Computation (EC) reporting a non-exhaustive list of topics which have recently attracted much interest from the EC community, with particular regard to the ones dealt with by the papers included in this issue: EC research, hybrid neuro-evolutionary systems and synergies between EC and complex systems. In addition, we introduce a more technological emerging topic: the parallel implementation of evolutionary and Swarm Intelligence algorithms on graphics processor units (GPUs), by which new applications of evolutionary algorithms have been made possible, even in real-time environments.

Statistical methods, and in particular Machine Learning, have been increasingly used in the drug development workflow to accelerate the discovery phase and to eliminate possible failures early during clinical developments. In the past, the authors of this paper have been working specifically on two problems: (i) prediction of drug induced toxicity and (ii) evaluation of the target-drug chemical interaction based on chemical descriptors. Among the numerous existing Machine Learning methods and their application to drug development ( see for instance [ F. Yoshida, J.G. Topliss, QSAR model for drug human oral bioavailability, Journal of Medicinal Chemistry 43 (2000) 2575-2585; Frohlich, J. Wegner, F. Sieker, A. Zell, Kernel functions for attributed molecular graphs-a new similarity based approach to ADME prediction in classification and regression, QSAR and Combinatorial Science, 38( 4) ( 2003) 427431; C. W. Andrews, L. Bennett, L. X. Yu, Predicting human oral bioavailability of a compound: development of a novel quantitative structure-bioavailability relationship, Pharmacological Research 17 ( 2000) 639-644; J Feng, L. Lurati, H. Ouyang, T. Robinson, Y. Wang, S. Yuan, S. S. Young, Predictive toxicology: benchmarking molecular descriptors and statistical methods, Journal of Chemical Information Computer Science 43 ( 2003) 1463-1470; T. M. Martin, D. M. Young, Prediction of the acute toxicity (96-h LC50) of organic compounds to the fat head minnow (Pimephales promelas) using a group contribution method, Chemical Research in Toxicology 14( 10) ( 2001) 1378-1385; G. Colmenarejo, A. Alvarez-Pedraglio, J. L. Lavandera, Chemoinformatic models to predict binding affinities to human serum albumin, Journal of Medicinal Chemistry 44 ( 2001) 4370-4378; J. Zupan, P. Gasteiger, Neural Networks in Chemistry and Drug Design: An Introduction, 2nd edition, Wiley, 1999]), we have been specifically concerned with Genetic Programming. A first paper [F. Archetti, E. Messina, S. Lanzeni, L. Vanneschi, Genetic programming for computational pharmacokinetics in drug discovery and development, Genetic Programming and Evolvable Machines 8( 4) ( 2007) 17-26] has been devoted to problem ( i). The present contribution aims at developing a Genetic Programming based framework on which to build specific strategies which are then shown to be a valuable tool for problem ( ii). In this paper, we use target estrogen receptor molecules and genistein based drug compounds. Being able to precisely and efficiently predict their mutual interaction energy is a very important task: for example, it may have an immediate relationship with the efficacy of genistein based drugs in menopause therapy and also as a natural prevention of some tumors. We compare the experimental results obtained by Genetic Programming with the ones of a set of "non-evolutionary'' Machine Learning methods, including Support Vector Machines, Artificial Neural Networks, Linear and Least Square Regression. Experimental results confirm that Genetic Programming is a promising technique from the viewpoint of the accuracy of the proposed solutions, of the generalization ability and of the correlation between predicted data and correct ones. (C) 2009 Elsevier B. V. All rights reserved.

In this paper we study cellular automata (CAs) that perform the computational Majority task. This task is a good example of what the phenomenon of emergence in complex systems is. We take an interest in the reasons that make this particular fitness landscape a difficult one. The first goal is to study the landscape as such, and thus it is ideally independent from the actual heuristics used to search the space. However, a second goal is to understand the features a good search technique for this particular problem space should possess. We statistically quantify in various ways the degree of difficulty of searching this landscape. Due to neutrality, investigations based on sampling techniques on the whole landscape are difficult to conduct. So, we go exploring the landscape from the top. Although it has been proved that no CA can perform the task perfectly, several efficient CAs for this task have been found. Exploiting similarities between these CAs and symmetries in the landscape, we define the Olympus landscape which is regarded as the "heavenly home" of the best local optima known (blok). Then we measure several properties of this subspace. Although it is easier to find relevant CAs in this subspace than in the overall landscape, there are structural reasons that prevent a searcher from finding overfitted CAs in the Olympus. Finally, we study dynamics and performance of genetic algorithms on the Olympus in order to confirm our analysis and to find efficient CAs for the Majority problem with low computational cost. © 2007 Elsevier Ltd. All rights reserved.

International audience; 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.

Unified Parkinson’s Disease Rating Scale (UPDRS) assessment is the most used scale for tracking Parkinson’s disease symptom progression. Nowadays, the tracking process requires a patient to undergo invasive and time-consuming specialized examinations in hospital clinics, under the supervision of trained medical staff. Thus, the process is costly and logistically inconvenient for both patients and clinicians. For this reason, new powerful computational tools, aimed at making the process more automatic, cheaper and less invasive, are becoming more and more a necessity. The purpose of this paper is to investigate the use of an innovative intelligent system based on genetic programming for the prediction of UPDRS assessment, using only data derived from simple, self-administered and non-invasive speech tests. The system we propose is called geometric semantic genetic programming and it is based on recently defined geometric semantic genetic operators. Experimental results, achieved using the largest database of Parkinson’s disease speech in existence (approximately 6000 recordings from 42 Parkinson’s disease patients, recruited in a six-month, multi-centre trial), show the appropriateness of the proposed system for the prediction of UPDRS assessment. In particular, the results obtained with geometric semantic genetic programming are significantly better than the ones produced by standard genetic programming and other state of the art machine learning methods both on training and unseen test data.

In a recent contribution we have introduced a new implementation of geometric semantic operators for Genetic Programming. Thanks to this implementation, we are now able to deeply investigate their usefulness and study their properties on complex real-life applications. Our experiments confirm that these operators are more effective than traditional ones in optimizing training data, due to the fact that they induce a unimodal fitness landscape. Furthermore, they automatically limit overfitting, something we had already noticed in our recent contribution, and that is further discussed here. Finally, we investigate the influence of some parameters on the effectiveness of these operators, and we show that tuning their values and setting them “a priori” may be wasted effort. Instead, if we randomly modify the values of those parameters several times during the evolution, we obtain a performance that is comparable with the one obtained with the best setting, both on training and test data for all the studied problems.

This paper presents a new variant of the Harmony Search algorithm, called Geometric Selective Harmony Search. The main differences between the proposed variant and the original formulation of Harmony Search are the integration of a selection procedure in the improvisation phase, a new memory consideration process that makes use of a recombination operator, and the integration of a new mutation operator. We compare Geometric Selective Harmony Search with the original Harmony Search, with another existing variant called Improved Harmony Search, and with two existing selection-based Harmony Search algorithms. The experimental study was conducted on 20 benchmark problems belonging to the CEC 2010 suite, one of the most well-known state-of-the-art benchmark sets. The results show that Geometric Selective Harmony Search outperforms the other studied methods with statistical significance in almost all the considered benchmark problems. © 2014 Elsevier Inc. All rights reserved.

Moraglio et al. have recently introduced new genetic operators for genetic programming, called geometric semantic operators. These operators induce a unimodal fitness landscape for all the problems consisting in matching input data with known target outputs (like regression and classification). This feature facilitates genetic programming evolvability, which makes these operators extremely promising. Nevertheless, Moraglio et al. leave open problems, the most important one being the fact that these operators, by construction, always produce offspring that are larger than their parents, causing an exponential growth in the size of the individuals, which actually renders them useless in practice. In this paper we overcome this limitation by presenting a new efficient implementation of the geometric semantic operators. This allows us, for the first time, to use them on complex real-life applications, like the two problems in pharmacokinetics that we address here. Our results confirm the excellent evolvability of geometric semantic operators, demonstrated by the good results obtained on training data. Furthermore, we have also achieved a surprisingly good generalization ability, a fact that can be explained considering some properties of geometric semantic operators, which makes them even more appealing than before. © 2013 Springer-Verlag.

This paper presents a new genetic programming framework called Evolutionary Reaction Systems. It is based on a recently defined computational formalism, inspired by chemical reactions, called Reaction Systems, and it has several properties that distinguish it from other existing genetic programming frameworks, making it interesting and worthy of investigation. For instance, it allows us to express complex constructs in a simple and intuitive way, and it lightens the final user from the task of defining the set of primitive functions used to build up the evolved programs. Given that Evolutionary Reaction Systems is new and it has small similarities with other existing genetic programming frameworks, a first phase of this work is dedicated to a study of some important parameters and their influence on the algorithm's performance. Successively, we use the best parameter setting found to compare Evolutionary Reaction Systems with other well established machine learning methods, including standard tree-based genetic programming. The presented results show that Evolutionary Reaction Systems are competitive with, and in some cases even better than, the other studied methods on a wide set of benchmarks. © 2013 Springer Science+Business Media New York.

Genetic programming researchers have shown a growing interest in the study of gene regulatory networks in the last few years. Our team has also contributed to the field, by defining two systems for the automatic reverse engineering of gene regulatory networks called GRNGen and GeNet. In this paper, we revise this work by describing in detail the two approaches and empirically comparing them. The results we report, and in particular the fact that GeNet can be used on large networks while GRNGen cannot, encourage us to pursue the study of GeNet in the future. We conclude the paper by discussing the main research directions that we are planning to investigate to improve GeNet. © 2013 Springer Science+Business Media New York.

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. © 2012 ACM.

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. © 2012 ACM.

In the recent years many bio-inspired computational methods were defined and successfully applied to real life problems. Examples of those methods are particle swarm optimization, ant colony, evolutionary algorithms, and many others. At the same time, computational formalisms inspired by natural systems were defined and their suitability to represent different functions efficiently was studied. One of those is a formalism known as reaction systems. The aim of this work is to establish, for the first time, a relationship between evolutionary algorithms and reaction systems, by proposing an evolutionary version of reaction systems. In this paper we show that the resulting new genetic programming system has better, or at least comparable performances to a set of well known machine learning methods on a set of problems, also including real-life applications. Furthermore, we discuss the expressiveness of the solutions evolved by the presented evolutionary reaction systems. © 2012 Springer-Verlag.

Numerous studies can be found in literature concerning the idea of learning cellular automata (CA) rules that perform a given task by means of machine learning methods. Among these methods, genetic algorithms (GAs) have often been used with excellent results. Nevertheless, few attention has been dedicated so far to the generality and robustness of the learned rules. In this paper, we show that when GAs are used to evolve asynchronous one-dimensional CA rules, they are able to find more general and robust solutions compared to the more usual case of evolving synchronous CA rules.

Being able to predict the human oral bioavailability for a potential new drug is extremely important for the drug discovery process. This problem has been addressed by several prediction tools, with Genetic Programming providing some of the best results ever achieved. In this paper we use the newest developments of Genetic Programming, in particular the latest bloat control method, Operator Equalisation, to find out how much improvement we can achieve on this problem. We show examples of some actual solutions and discuss their quality, comparing them with previously published results. We identify some unexpected behaviours related to overfitting, and discuss the way for further improving the practical usage of the Genetic Programming approach. Copyright © 2012 Inderscience Enterprises Ltd.

In the first part of the chapter, evolutionary algorithms are briefly described, especially genetic algorithms and genetic programming, with sufficient detail so as to prepare the ground for the second part. The latter presents in more detail two specific applications. The first is about an important financial problem: the portfolio allocation problem. The second one deals with a biochemical problem related to drug design and efficacy. © 2008, IGI Global.

This work introduces a new technique for features construction in classification problems by means of multi objective genetic programming (MOGP). The final goal is to improve the generalization ability of the final classifier. MOGP can help in finding solutions with a better generalization ability with respect to standard genetic programming as stated in [1]. The main issue is the choice of the criteria that must be optimized by MOGP. In this work the construction of new features is guided by two criteria: the first one is the entropy of the target classes as in [7] while the second is inspired by the concept of margin used in support vector machines. © Springer-Verlag Berlin Heidelberg 2011

We present a new reverse-engineering framework for gene regulatory network reconstruction. It works on temporal series of gene activation data and, using genetic programming, it extracts the activation functions of the different genes from those data. Successively, the gene regulatory network is reconstructed exploiting the automatic feature selection performed by genetic programming and its dynamics can be simulated using the previously extracted activation functions. The framework was tested on the well-known IRMA gene regulatory network, a simple network composed by five genes in the yeast Saccharomyces cerevisiae, defined in 2009 as a simplified biological model to benchmark reverse-engineering approaches. We show that the performances of the proposed framework on this benchmark network are encouraging.

Background The ability to accurately classify cancer patients into risk classes, i.e. to predict the outcome of the pathology on an individual basis, is a key ingredient in making therapeutic decisions. In recent years gene expression data have been successfully used to complement the clinical and histological criteria traditionally used in such prediction. Many "gene expression signatures" have been developed, i.e. sets of genes whose expression values in a tumor can be used to predict the outcome of the pathology. Here we investigate the use of several machine learning techniques to classify breast cancer patients using one of such signatures, the well established 70-gene signature. Results We show that Genetic Programming performs significantly better than Support Vector Machines, Multilayered Perceptrons and Random Forests in classifying patients from the NKI breast cancer dataset, and comparably to the scoring-based method originally proposed by the authors of the 70-gene signature. Furthermore, Genetic Programming is able to perform an automatic feature selection. Conclusions Since the performance of Genetic Programming is likely to be improvable compared to the out-of-the-box approach used here, and given the biological insight potentially provided by the Genetic Programming solutions, we conclude that Genetic Programming methods are worth further investigation as a tool for cancer patient classification based on gene expression data.

The relationship between generalization and solutions functional complexity in genetic programming (GP) has been recently investigated. Three main contributions are contained in this paper: (1) a new measure of functional complexity for GP solutions, called Graph Based Complexity (GBC) is defined and we show that it has a higher correlation with GP performance on out-of-sample data than another complexity measure introduced in a recent publication. (2) A new measure is presented, called Graph Based Learning Ability (GBLA). It is inspired by the GBC and its goal is to quantify the ability of GP to learn "difficult" training points; we show that GBLA is negatively correlated with the performance of GP on out-of-sample data. (3) Finally, we use the ideas that have inspired the definition of GBC and GBLA to define a new fitness function, whose suitability is empirically demonstrated. The experimental results reported in this paper have been obtained using three real-life multidimensional regression problems.

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.

We consider the theoretical results in GP so far and prospective areas for the future. We begin by reviewing the state of the art in genetic programming (GP) theory including: schema theories, Markov chain models, the distribution of functionality in program search spaces, the problem of bloat, the applicability of the no-free-lunch theory to GP, and how we can estimate the difficulty of problems before actually running the system. We then look at how each of these areas might develop in the next decade, considering also new possible avenues for theory, the challenges ahead and the open issues. © Springer Science+Business Media, LLC 2010.

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. © 2010 IEEE.

Generalization is an important issue in colorimetric characterization of devices. We propose a framework based on Genetic Algorithms to select training samples from large datasets. Even though the framework is general, and can be used in principle for any dataset, we use two well known datasets as case studies: training samples are selected from the Macbeth ColorCheckerDC dataset and the trained models are tested on the Kodak Q60 photographic standard dataset. The presented experimental results show that the proposed framework has better, or at least comparable, performances than a set of other computational methods defined so far for the same goal (Hardeberg, Cheung, CIC and Schettini). Even more importantly, the proposed framework has the ability to optimize the training samples and the characterizing polynomial's coefficients at the same time. © 2010 Springer-Verlag Berlin Heidelberg.

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. Copyright 2009 ACM.

Predicting the toxicity of new potential drugs is a fundamental step in the drug design process. Recent contributions have shown that, even though Genetic Programming is a promising method for this task, the problem of predicting the toxicity of molecular compounds is complex and difficult to solve. In particular, when executed for predicting drug toxicity, Genetic Programming undergoes the well-known phenomenon of bloat, i.e. the growth in code size during the evolutionary process without a corresponding improvement in fitness. We hypothesize that this might cause overfitting and thus prevent the method from discovering simpler and potentially more general solutions. For this reason, in this paper we investigate two recently defined variants of the operator equalization bloat control method for Genetic Programming. We show that these two methods are bloat free also when executed on this complex problem. Nevertheless, overfitting still remains an issue. Thus, contradicting the generalized idea that bloat and overfitting are strongly related, we argue that the two phenomena are independent from each other and that eliminating bloat does not necessarily eliminate overfitting. © 2009 Springer Berlin Heidelberg.

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. Copyright 2009 ACM.

This paper presents a research in the context of pedestrian dynamics according to Situated Cellular Agent (SCA), a Multi-Agent Systems approach whose roots are on Cellular Automata (CA). The aim of this work is to apply Genetic Programming (GP) approach, a well known Machine Learning method belonging to the family of Evolutionary Algorithms, to generate suitable behavioral rules for pedestrians in an evacuation scenario. The main contribution of this work is in the design of a testset of GP generated behaviors to represent basic behavioral models of evacuees populating a only locally known environment, a typical scenario for CA-based models. © 2008 Springer-Verlag Berlin Heidelberg.

In this work we present an evolutionary framework for colorimetric characterization of scanners. The problem consists in finding a mapping from the RGB space (where points indicate how a color stimulus is produced by a given device) to their corresponding values in the CIELAB space (where points indicate how the color is perceived in standard, i.e. device independent, viewing conditions). The proposed framework is composed by two phases: in the first one we use genetic programming for assessing a characterizing polynomial; in the second one we use genetic algorithms to assess suitable coefficients of that polynomial. Experimental results are reported to confirm the effectiveness of our framework with respect to a set of methods in the state of the art. © 2008 Springer-Verlag Berlin Heidelberg.

This chapter represents a first attempt to characterize the fitness landscapes of real-life Genetic Programming applications by means of a predictive algebraic difficulty indicator. The indicator used is the Negative Slope Coefficient, whose efficacy has been recently empirically demonstrated on a large set of hand-tailored theoretical test functions and well known GP benchmarks. The real-life problems studied belong to the field of Biomedical applications and consist of automatically assessing a mathematical relationship between a set of molecular descriptors from a given dataset of drugs and some important pharmacokinetic parameters. The parameters considered here are Human Oral Bioavailability, Median Oral Lethal Dose, and Plasma Protein Binding levels. The availability of good prediction tools for pharmacokinetics parameters like these is critical for optimizing the efficiency of therapies, maximizing medical success rate and minimizing toxic effects. The experimental results presented in this chapter show that the Negative Slope Coefficient seems to be a reasonable tool to characterize the difficulty of these problems, and can be used to choose the most effective Genetic Programming configuration (fitness function, representation, parameters' values) from a set of given ones.

International audience; We study in detail the fitness landscape of a difficult cellular automata computational task: the majority problem. Our results show why this problem landscape is so hard to search, and we quantify the large degree of neutrality found in various ways. We show that a particular subspace of the solution space, called the "Olympus", is where good solutions concentrate, and give measures to quantitatively characterize this subspace.

This paper presents a machine learning system to handle traffic control applications. The input of the system is a set of image sequences coming from a fixed camera. The system can be divided into two main subsystems: the first one, based on Artificial Neural Networks classifies the typology of vehicles moving within a limited image area for each frame of the sequence; the second one, based on Genetic Algorithms, takes as input the frame-by-frame classifications and reconstructs the global traffic scenario by counting the number of vehicles of each typology. This task is particularly hard when the frame rate is low. The results obtained by our system are reliable even for very low frame rate (i.e. four frames per second). Our system is currently used by a company for real-time traffic control.

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.

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.

The paper presents an empirical study aiming at evaluating and comparing several Machine Learning (ML) classification techniques in the automatic recognition of known patterns. The main motivations of this work is to select best performing classification techniques where target classes are based on the occurrence of known patterns in configurations of a forest system modeled according to Cellular Automata. Best performing ML classifiers will be adopted for the study of ecosystem dynamics within an interdisciplinary research collaboration between computer scientists biologists and ecosystem managers (Cellular Automata For Forest Ecosystems - CAFFE project). One of the main aims of the CAFFE project is the development of an analysis method based on recognition in CA state configurations of spatial patterns whose interpretations are inspired by the Chinese Go game.

This paper introduces the concepts of error vector and error space, directly bound to semantics, one of the hottest topics in genetic programming. Based on these concepts, we introduce the notions of optimally aligned individuals and optimally coplanar individuals. We show that, given optimally aligned, or optimally coplanar, individuals, it is possible to construct a globally optimal solution analytically. Thus, we introduce a genetic programming framework for symbolic regression called Error Space Alignment GP (ESAGP) and two of its instances: ESAGP-1, whose objective is to find optimally aligned individuals, and ESAGP-2, whose objective is to find optimally coplanar individuals. We also discuss how to generalize the approach to any number of dimensions. Using two complex real-life applications, we provide experimental evidence that ESAGP-2 outperforms ESAGP-1, which in turn outperforms both standard GP and geometric semantic GP. This suggests that “adding dimensions” is beneficial and encourages us to pursue the study in many different directions, that we summarize in the final part of the manuscript

In this paper we present an ongoing research that aims at providing an interpretation and detection method for spatial patterns supporting ecosystem management in the study of forest systems according to a distributed modeling and simulation approach. To this aim an innovative analysis method inspired by the Chinese Go game is under design. The originality of the approach concerns the detection within system configurations of known patterns whose interpretations are well–known by expert Go players.

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.