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

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

Several methods to incorporate semantic awareness in genetic programming have been proposed in the last few years. These methods cover fundamental parts of the evolutionary process: from the population initialization, through different ways of modifying or extending the existing genetic operators, to formal methods, until the definition of completely new genetic operators. The objectives are also distinct: from the maintenance of semantic diversity to the study of semantic locality; from the use of semantics for constructing solutions which obey certain constraints to the exploitation of the geometry of the semantic topological space aimed at defining easy-to-search fitness landscapes. All these approaches have shown, in different ways and amounts, that incorporating semantic awareness may help improving the power of genetic programming. This survey analyzes and discusses the state of the art in the field, organizing the existing methods into different categories. It restricts itself to studies where semantics is intended as the set of output values of a program on the training data, a definition that is common to a rather large set of recent contributions. It does not discuss methods for incorporating semantic information into grammar-based genetic programming or approaches based on formal methods. The objective is keeping the community updated on this interesting research track, hoping to motivate new and stimulating contributions. © 2014 Springer Science+Business Media New York.

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.

The process of tuning the parameters that characterize evolutionary algorithms is difficult and can be time consuming. This paper presents a self-tuning algorithm for dynamically updating the crossover and mutation probabilities during a run of genetic programming. The genetic operators that are considered in this work are the geometric semantic genetic operators introduced by Moraglio et al. Differently from other existing self-tuning algorithms, the proposed one works by assigning a (different) crossover and mutation probability to each individual of the population. The experimental results we present show the appropriateness of the proposed self-tuning algorithm: on seven different test problems, the proposed algorithm finds solutions of a quality that is better than, or comparable to, the one achieved using the best known values for the geometric semantic crossover and mutation rates for the same problems. Also, we study how the mutation and crossover probabilities change during the execution of the proposed self-tuning algorithm, pointing out an interesting insight: mutation is basically the only operator used in the exploration phase, while crossover is used for exploitation, further improving good quality solutions.

Manzoni, L., Vanneschi, L., & Mauri, G. (2012). A distance between populations for one-point crossover in genetic algorithms. Theoretical Computer Science, 429, 213-221. https://doi.org/10.1016/j.tcs.2011.12.041 Genetic algorithms use transformation operators on the genotypic structures of the individuals to carry out a search. These operators define a neighborhood. To analyze various dynamics of the search process, it is often useful to define a distance in this space. In fact, using an operator-based distance can make the analysis more accurate and reliable than using distances which have no relationship with the genetic operators. In this paper we define a distance which is based on the standard one-point crossover. Given that the population strongly affects the neighborhood induced by the crossover, we first define a crossover-based distance between populations. Successively, we show that it is naturally possible to derive from this function a family of distances between individuals. Finally, we also introduce an algorithm to compute this distance efficiently. published

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 present four new parallel and distributed particle swarm optimization methods consisting in a genetic algorithm whose individuals are co-evolving swarms, an “island model”-based multi-swarm system, where swarms are independent and interact by means of particle migrations at regular time steps, and their respective variants enriched by adding a repulsive component to the particles. We study the proposed methods on a wide set of problems including theoretically hand-tailored benchmarks and complex real-life applications from the field of drug discovery, with a particular focus on the generalization ability of the obtained solutions. We show that the proposed repulsive multi-swarm system has a better optimization ability than all the other presented methods on all the studied problems. Interestingly, the proposed repulsive multi-swarm system is also the one that returns the most general solutions.

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.

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.

Geometric semantic operators are new and promising genetic operators for genetic programming. They have the property of inducing a unimodal error surface for any supervised learning problem, i.e., any problem consisting in finding the match between a set of input data and known target values (like regression and classification). Thanks to an efficient implementation of these operators, it was possible to apply them to a set of real-life problems, obtaining very encouraging results. We have now made this implementation publicly available as open source software, and here we describe how to use it. We also reveal details of the implementation and perform an investigation of its efficiency in terms of running time and memory occupation, both theoretically and experimentally. The source code and documentation are available for download at http://gsgp.sourceforge.net .

Load forecasting is a critical task for all the operations of power systems. Especially during hot seasons, the influence of weather on energy demand may be strong, principally due to the use of air conditioning and refrigeration. This paper investigates the application of Genetic Programming on day-ahead load forecasting, comparing it with Neural Networks, Neural Networks Ensembles and Model Trees. All the experimentations have been performed on real data collected from the Italian electric grid during the summer period. Results show the suitability of Genetic Programming in providing good solutions to this problem. The advantage of using Genetic Programming, with respect to the other methods, is its ability to produce solutions that explain data in an intuitively meaningful way and that could be easily interpreted by a human being. This fact allows the practitioner to gain a better understanding of the problem under exam and to analyze the interactions between the features that characterize it.

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.

In the last few years researchers have dedicated several efforts to the definition of Genetic Programming (GP) [?] systems based on the semantics of the solutions, where by semantics we generally intend the behavior of a program once it is executed on a set of inputs, or more particularly the set of its output values on input training data (this definition has been used, among many others, for instance in [?, ?, ?, ?]). In particular, new genetic operators, called geometric semantic operators, have been proposed by Moraglio et al. [?]. They are defined s follows

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.

Computing the longest common subsequence of two sequences is one of the most studied algorithmic problems. In this work we focus on a particular variant of the problem, called repetition free longest common subsequence (RF-LCS), which has been proved to be NP-hard. We propose a hybrid genetic algorithm, which combines standard genetic algorithms and estimation of distribution algorithms, to solve this problem. An experimental comparison with some well-known approximation algorithms shows the suitability of the proposed technique. © 2013 Elsevier B.V. All rights reserved.

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.

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.

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

In this paper a method to increase the optimization ability of genetic algorithms (GAs) is proposed. To promote population diversity, a fraction of the worst individuals of the current population is replaced by individuals from an older population. To experimentally validate the approach we have used a set of well-known benchmark problems of tunable difficulty for GAs. Standard GA with and without elitism and steady state GA have been augmented with the proposed method. The obtained results show that the algorithms augmented with the proposed method perform better than the not-augmented algorithms or have the same performances. Furthermore, the proposed method depends on two parameters: one of them regulates the size of the fraction of the population replaced and the other one decides the "age" of the population used for the replacement. Experimental results indicate that better performances have been achieved with high values of the former parameter and low values of the latter one. © 2011 Springer-Verlag

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

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.

In this paper a method to increase the optimization ability of genetic algorithms (GAs) is proposed. To promote population diversity, a fraction of the worst individuals of the current population is replaced by individuals from an older population. To experimentally validate the approach we have used a set of well-known benchmark problems of tunable difficulty for GAs, including trap functions and NK landscapes. The obtained results show that the proposed method performs better than standard GAs without elitism for all the studied test problems and better than GAs with elitism for the majority of them.

It is approximately 50 years since the first computational experiments were conducted in what has become known today as the field of Genetic Programming (GP), twenty years since John Koza named and popularised the method, and ten years since the first issue appeared of the Genetic Programming & Evolvable Machines journal. In particular, during the past two decades there has been a significant range and volume of development in the theory and application of GP, and in recent years the field has become increasingly applied. There remain a number of significant open issues despite the successful application of GP to a number of challenging real-world problem domains and progress in the develop- ment of a theory explaining the behavior and dynamics of GP. These issues must be addressed for GP to realise its full potential and to become a trusted mainstream member of the computational problem solving toolkit. In this paper we outline some of the challenges and open issues that face researchers and practitioners of GP. We hope this overview will stimulate debate, focus the direction of future research to deepen our understanding of GP, and further the development of more powerful problem solving algorithms. Science Foundation Ireland Embargo until April 2011 - AV April 2011 ke - AS 04/11/2010 ab - TS 18.11.10

We present a framework based on genetic algorithms to automatically generate cellular automata rules under four different asynchronous update models (fixed random sweep, random new sweep, clock and independent random ordering). We consider four different rules (18, 56, 110 and 180) with well known dynamics under synchronous update scheme. We try to reconstruct the same dynamics by means of a genetic algorithm using asynchronous update schemes. We show that in many cases it is impossible, by means of an asynchronous update scheme, to perfectly reconstruct these dynamics. Nevertheless, we show that the genetic algorithm finds the rules that more closely approximate the target behavior and the dynamics of the rules found by the genetic algorithm are rather similar to the target ones. In particular, we can always recognize a similar patter and we can also identify some differences in small details, which can be minimal (as for rule 18) or rather visible (as for rule 110). This paves the way to a deeper investigation on this track: does using asynchronous updates allow us to find more stable rules, i.e. rules that are less affected by noise, and thus do not overfit training data? This question remains open and answering it is one of the main goals of our current research.

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.

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). © 2008 IEEE.

The success of a drug treatment is strongly correlated with the ability of a molecule to reach its target in the patient's organism without inducing toxic effects. Moreover the reduction of cost and time associated with drug discovery and development is becoming a crucial requirement for pharmaceutical industry. Therefore computational methods allowing reliable predictions of newly synthesized compounds properties are of outmost relevance. In this paper we discuss the role of genetic programming in predictive pharmacokinetics, considering the estimation of adsorption, distribution, metabolism, excretion and toxicity processes (ADMET) that a drug undergoes into the patient's organism. We compare genetic programming with other well known machine learning techniques according to their ability to predict oral bioavailability (%F), median oral lethal dose (LD50) and plasma-protein binding levels (%PPB). Since these parameters respectively characterize the percentage of initial drug dose that effectively reaches the systemic blood circulation, the harmful effects and the distribution into the organism of a drug, they are essential for the selection of potentially good molecules. Our results suggest that genetic programming is a valuable technique for predicting pharmacokinetics parameters, both from the point of view of the accuracy and of the generalization ability.

Model checking is a way of analysing programs and program-like structures to decide whether they satisfy a list of temporal logic statements describing desired behaviour. In this paper we apply this to the fitness checking stage in an evolution strategy for learning finite state machines. We give experimental results consisting of learning the control program for a vending machine.

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 explores distance measures based on genetic operators for genetic programming using tree structures. The consistency between genetic operators and distance measures is a crucial point for analytical measures of problem difficulty, such as fitness distance correlation, and for measures of population diversity, such as entropy or variance. The contribution of this paper is the exploration of possible definitions and approximations of operator-based edit distance measures. In particular, we focus on the subtree crossover operator. An empirical study is presented to illustrate the features of an operator-based distance. This paper makes progress toward improved algorithmic analysis by using appropriate measures of distance and similarity.