Search

Parameter estimation (PE) of biological systems is one of the most challenging problems in Systems Biology. Here we present a PE method that integrates particle swarm optimization (PSO) to estimate the value of kinetic constants, and a stochastic simulation algorithm to reconstruct the dynamics of the system. The fitness of candidate solutions, corresponding to vectors of reaction constants, is defined as the point-to-point distance between a simulated dynamics and a set of experimental measures, carried out using discrete-time sampling and various initial conditions. A multi-swarm PSO topology with different modalities of particles migration is used to account for the different laboratory conditions in which the experimental data are usually sampled. The whole method has been specifically designed and entirely executed on the GPU to provide a reduction of computational costs.We show the effectiveness of our method and discuss its performances on an enzymatic kinetics and a prokaryotic gene expression network.

Given the implicitly parallel nature of population-based heuristics, many contributions reporting on parallel and distributed models and implementations of these heuristics have appeared so far. They range from the most natural and simple ones, i.e. fitness-level embarrassingly parallel implementations (where, for instance, each candidate solution is treated as an independent agent and evaluated on a dedicated processor), to many more sophisticated variously interacting multi-population systems. In the last few years, researchers have dedicated a growing attention to Particle Swarm Optimization (PSO), a bio-inspired population based heuristic inspired by the behavior of flocks of birds and shoals of fish, given its extremely simple implementation and its high intrinsical parallelism. Several parallel and distributed models of PSO have been recently defined, showing interesting performances both on benchmarks and real-life applications. In this chapter we report on four parallel and distributed PSO methods that have recently been proposed. They consist 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 show that the proposed repulsive multi-swarm system has a better optimization ability than all the other presented methods on a set of hand-tailored benchmarks and complex real-life applications.

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

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 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 pattern and we can also identify some differences in small details. 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.

The modelling of biochemical systems requires the knowledge of several quantitative parameters (e.g. reaction rates) which are often hard to measure in laboratory experiments. Furthermore, when the system involves small numbers of molecules, the modelling approach should also take into account the effects of randomness on the system dynamics. In this paper, we tackle the problem of estimating the unknown parameters of stochastic biochemical systems by means of two optimization heuristics, genetic algorithms and particle swarm optimization. Their performances are tested and compared on two basic kinetics schemes: the Michaelis-Menten equation and the Brussellator. The experimental results suggest that particle swarm optimization is a suitable method for this problem. The set of parameters estimated by particle swarm optimization allows us to reliably reconstruct the dynamics of the Michaelis-Menten system and of the Brussellator in the oscillating regime. © Springer-Verlag Berlin Heidelberg 2009.

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.

Among the variants of the basic Particle Swarm Optimization (PSO) algorithm as first proposed in 1995, EPSO (Evolutionary PSO), proposed by Miranda and Fonseca, seems to produce significant improvements. We analyze the effects of two modifications introduced in that work (adaptive parameter setting and selection based on an evolution strategies-like approach) separately, reporting results obtained on a set of multimodal benchmark functions, which show that they may have opposite and complementary effects. In particular, using only parameter adaptation when optimizing 'harder' functions yields better results than when both modifications are applied. We also propose a justification for this, based on recent analyses in which particle swarm optimizers are studied as dynamical systems. © 2008 Springer-Verlag Berlin Heidelberg.

We introduce the concept of "minimal" search algorithm for a set of functions to optimize. We investigate the structure of closed under permutation (c.u.p.) sets and we calculate the performance of an algorithm applied to them. We prove that each set of functions based on the distance to a given optimal solution, among which trap functions, onemax or the recently introduced onemix functions, and the NK-landscapes are not c.u.p. and thus the thesis of the sharpened No Free Lunch Theorem does not hold for them. Thus, it makes sense to look for a specific algorithm for those sets. Finally, we propose a method to build a "good" (although not necessarily minimal) search algorithm for a specific given set of problems. The algorithms produced with this technique show better average performance than a genetic algorithm executed on the same set of problems, which was expected given that those algorithms are problem-specific. Nevertheless, in general they cannot be applied for real-life problems, given their high computational complexity that we have been able to estimate. © 2008 Springer-Verlag Berlin Heidelberg.

In this paper we present an empirical study of the Negative Slope Coefficient (NSC) hardness statistic to characterize the difficulty of 3-SAT fitness landscapes for randomly generated problem instances. NSC correctly classifies problem instances with a low ratio of clauses to variables as easy, while instances with a ratio close to the critical point are classified as hard, as expected. Together with previous results on many different problems and fitness landscapes, the present results confirm that NSC is a useful and reliable indicator of problem difficulty. © 2008 Springer-Verlag Berlin Heidelberg.

We define a set of measures that capture some different aspects of neutrality in evolutionary algorithms fitness landscapes from a qualitative point of view. If considered all together, these measures offer a rather complete picture of the characteristics of fitness landscapes bound to neutrality and may be used as broad indicators of problem hardness. We compare the results returned by these measures with the ones of negative slope coefficient, a quantitative measure of problem hardness that has been recently defined and with success rate statistics on a well known genetic programming benchmark: the multiplexer problem. In order to efficaciously study the search space, we use a sampling technique that has recently been introduced and we show its suitability on this problem

Computational methods allowing reliable pharmacokinetics predictions for newly synthesized compounds are critically relevant for drug discovery and development. Here we present an empirical study focusing on various versions of Genetic Programming and other well known Machine Learning techniques to predict Median Oral Lethal Dose (LD50) and Plasma Protein Binding (%PPB) levels. Since these two parameters respectively characterize the harmful effects and the distribution into human body of a drug, their accurate prediction is essential for the selection of effective molecules. The obtained results confirm that Genetic Programming is a promising technique for predicting pharmacokinetics parameters, both from the point of view of the accurateness and of the generalization ability.

To analyse various properties of the search process of genetic programming it is useful to quantify the distance between two individuals. Using operator-based distance measures can make this analysis more accurate and reliable than using distance measures which have no relationship with the genetic operators. This paper extends a recent definition of a distance measure based on subtree crossover for genetic programming. Empirical studies are presented that show the suitability of this measure to dynamically calculate the fitness distance correlation coefficient during the evolution, to construct a fitness sharing system for genetic programming and to measure genotypic diversity in the population. These experiments confirm the accuracy of the new measure and its consistency with the subtree crossover genetic operator

This paper presents an investigation of genetic programming fitness landscapes. We propose a new indicator of problem hardness for tree-based genetic programming, called negative slope coefficient, based on the concept of fitness cloud. The negative slope coefficient is a predictive measure, i.e. it can be calculated without prior knowledge of the global optima. The fitness cloud is generated via a sampling of individuals obtained with the Metropolis-Hastings method. The reliability of the negative slope coefficient is tested on a set of well known and representative genetic programming benchmarks, comprising the binomial-3 problem, the even parity problem and the artificial ant on the Santa Fe trail