Evolutionary and Estimation of Distribution Algorithms for Unconstrained, Constrained, and Multiobjective Noisy Combinatorial Optimisation Problems.

We present an empirical study of a range of evolutionary algorithms applied to various noisy combinatorial optimisation problems. There are three sets of experiments. The first looks at several toy problems, such as OneMax and other linear problems. We find that UMDA and the Paired-Crossover Evolutionary Algorithm (PCEA) are the only ones able to cope robustly with noise, within a reasonable fixed time budget. In the second stage, UMDA and PCEA are then tested on more complex noisy problems: SubsetSum, Knapsack, and SetCover. Both perform well under increasing levels of noise, with UMDA being the better of the two. In the third stage, we consider two noisy multiobjective problems (CountingOnesCountingZeros and a multiobjective formulation of SetCover). We compare several adaptations of UMDA for multiobjective problems with the Simple Evolutionary Multiobjective Optimiser (SEMO) and NSGA-II. We conclude that UMDA, and its variants, can be highly effective on a variety of noisy combinatorial optimisation, outperforming many other evolutionary algorithms.

Quantitative molecular bioluminescence tomography.

SIGNIFICANCE: Bioluminescence imaging and tomography (BLT) are used to study biologically relevant activity, typically within a mouse model. A major limitation is that the underlying optical properties of the volume are unknown, leading to the use of a "best" estimate approach often compromising quantitative accuracy. AIM: An optimization algorithm is presented that localizes the spatial distribution of bioluminescence by simultaneously recovering the optical properties and location of bioluminescence source from the same set of surface measurements. APPROACH: Measured data, using implanted self-illuminating sources as well as an orthotopic glioblastoma mouse model, are employed to recover three-dimensional spatial distribution of the bioluminescence source using a multi-parameter optimization algorithm. RESULTS: The proposed algorithm is able to recover the size and location of the bioluminescence source while accounting for tissue attenuation. Localization accuracies of <1 mm are obtained in all cases, which is similar if not better than current "gold standard" methods that predict optical properties using a different imaging modality. CONCLUSIONS: Application of this approach, using in-vivo experimental data has shown that quantitative BLT is possible without the need for any prior knowledge about optical parameters, paving the way toward quantitative molecular imaging of exogenous and indigenous biological tumor functionality.

Simultaneous diffuse optical and bioluminescence tomography to account for signal attenuation to improve source localization.

Photonics based pre-clinical imaging is an extensively used technique to allow for the study of biologically relevant activity typically within a small-mouse model. Namely, bioluminescent tomography (BLT) attempts to tomographically reconstruct the 3-dimensional spatial light distribution of luminophores within a small animal given surface light measurements and known underlying optical parameters. Often it is the case where these optical parameters are unknown leading to the use of a 'best' guess approach or to direct measurements using either a multi-modal or dedicated system. Using these conventional approaches can lead to both inaccurate results and extending periods of imaging time. This work introduces the development of an algorithm that is used to accurately localize the spatial light distribution from a bioluminescence source within a subject by simultaneously reconstructing both the underlying optical properties and source spatial distribution and intensity from the same set of surface measurements. Through its application in 2- and 3-dimensional, homogeneous and heterogenous numerical models, it is demonstrated that the proposed algorithm is capable of replicating results as compared to 'gold' standard where the absolute optical properties are known. Additionally, the algorithm has been applied to experimental data using a tissue mimicking block phantom, recovering a spatial light distribution that has a localization error of ∼1.53 mm, which is better than previously published results without the need of assumptions regarding the underlying optical properties or source distribution.

Single pixel hyperspectral bioluminescence tomography based on compressive sensing.

Photonics based imaging is a widely utilised technique for the study of biological functions within pre-clinical studies. Specifically, bioluminescence imaging is a sensitive non-invasive and non-contact optical imaging technique that is able to detect distributed (biologically informative) visible and near-infrared activated light sources within tissue, providing information about tissue function. Compressive sensing (CS) is a method of signal processing that works on the basis that a signal or image can be compressed without important information being lost. This work describes the development of a CS based hyperspectral Bioluminescence imaging system that is used to collect compressed fluence data from the external surface of an animal model, due to an internal source, providing lower acquisition times, higher spectral content and potentially better tomographic source localisation. The work demonstrates that hyperspectral surface fluence images of both block and mouse shaped phantom due to internal light sources could be obtained at 30% of the time and measurements it would take to collect the data using conventional raster scanning methods. Using hyperspectral data, tomographic reconstruction of internal light sources can be carried out using any desired number of wavelengths and spectral bandwidth. Reconstructed images of internal light sources using four wavelengths as obtained through CS are presented showing a localisation error of ∼3 mm. Additionally, tomographic images of dual-colored sources demonstrating multi-wavelength light sources being recovered are presented further highlighting the benefits of the hyperspectral system for utilising multi-colored biomarker applications.

Multi-scale stochastic organization-oriented coarse-graining exemplified on the human mitotic checkpoint.

The complexity of biological models makes methods for their analysis and understanding highly desirable. Here, we demonstrate the orchestration of various novel coarse-graining methods by applying them to the mitotic spindle assembly checkpoint. We begin with a detailed fine-grained spatial model in which individual molecules are simulated moving and reacting in a three-dimensional space. A sequence of manual and automatic coarse-grainings finally leads to the coarsest deterministic and stochastic models containing only four molecular species and four states for each kinetochore, respectively. We are able to relate each more coarse-grained level to a finer one, which allows us to relate model parameters between coarse-grainings and which provides a more precise meaning for the elements of the more abstract models. Furthermore, we discuss how organizational coarse-graining can be applied to spatial dynamics by showing spatial organizations during mitotic checkpoint inactivation. We demonstrate how these models lead to insights if the model has different "meaningful" behaviors that differ in the set of (molecular) species. We conclude that understanding, modeling and analyzing complex bio-molecular systems can greatly benefit from a set of coarse-graining methods that, ideally, can be automatically applied and that allow the different levels of abstraction to be related.

Landscape Analysis of a Class of NP-Hard Binary Packing Problems.

This article presents an exploratory landscape analysis of three NP-hard combinatorial optimisation problems: the number partitioning problem, the binary knapsack problem, and the quadratic binary knapsack problem. In the article, we examine empirically a number of fitness landscape properties of randomly generated instances of these problems. We believe that the studied properties give insight into the structure of the problem landscape and can be representative of the problem difficulty, in particular with respect to local search algorithms. Our work focuses on studying how these properties vary with different values of problem parameters. We also compare these properties across various landscapes that were induced by different penalty functions and different neighbourhood operators. Unlike existing studies of these problems, we study instances generated at random from various distributions. We found a general trend where some of the landscape features in all of the three problems were found to vary between the different distributions. We captured this variation by a single, easy to calculate parameter and we showed that it has a potentially useful application in guiding the choice of the neighbourhood operator of some local search heuristics.

Organisation-Oriented Coarse Graining and Refinement of Stochastic Reaction Networks.

Chemical organisation theory is a framework developed to simplify the analysis of long-term behaviour of chemical systems. In this work, we build on these ideas to develop novel techniques for formal quantitative analysis of chemical reaction networks, using discrete stochastic models represented as continuous-time Markov chains. We propose methods to identify organisations, and to study quantitative properties regarding movements between these organisations. We then construct and formalise a coarse-grained Markov chain model of hierarchic organisations for a given reaction network, which can be used to approximate the behaviour of the original reaction network. As an application of the coarse-grained model, we predict the behaviour of the reaction network systems over time via the master equation. Experiments show that our predictions can mimic the main pattern of the concrete behaviour in the long run, but the precision varies for different models and reaction rule rates. Finally, we propose an algorithm to selectively refine the coarse-grained models and show experiments demonstrating that the precision of the prediction has been improved.

Representation invariant genetic operators.

A genetic algorithm is invariant with respect to a set of representations if it runs the same no matter which of the representations is used. We formalize this concept mathematically, showing that the representations generate a group that acts upon the search space. Invariant genetic operators are those that commute with this group action. We then consider the problem of characterizing crossover and mutation operators that have such invariance properties. In the case where the corresponding group action acts transitively on the search space, we provide a complete characterization, including high-level representation-independent algorithms implementing these operators.

Molecular circuits for associative learning in single-celled organisms.

We demonstrate how a single-celled organism could undertake associative learning. Although to date only one previous study has found experimental evidence for such learning, there is no reason in principle why it should not occur. We propose a gene regulatory network that is capable of associative learning between any pre-specified set of chemical signals, in a Hebbian manner, within a single cell. A mathematical model is developed, and simulations show a clear learned response. A preliminary design for implementing this model using plasmids within Escherichia coli is presented, along with an alternative approach, based on double-phosphorylated protein kinases.

Markov models of integrating spheres for hyperspectral imaging.

Theoretical models of the signal detected by a CCD camera during hyperspectral imaging with an integrating sphere are derived using Markov chains with absorbing states. The models provide analytical expressions that describe the real reflectance of the sample as a function of the detected signal at each pixel of the image. Validation of the models was done by using reflectance standards and tissue phantoms. The models provide accurate analytical solutions for samples and spheres that are near-Lambertian reflectors.

State aggregation and population dynamics in linear systems.

We consider complex systems that are composed of many interacting elements, evolving under some dynamics. We are interested in characterizing the ways in which these elements may be grouped into higher-level, macroscopic states in a way that is compatible with those dynamics. Such groupings may then be thought of as naturally emergent properties of the system. We formalize this idea and, in the case that the dynamics are linear, prove necessary and sufficient conditions for this to happen. In cases where there is an underlying symmetry among the components of the system, group theory may be used to provide a strong sufficient condition. These observations are illustrated with some artificial life examples.

Structural search spaces and genetic operators.

In a previous paper (Rowe et al., 2002), aspects of the theory of genetic algorithms were generalised to the case where the search space, omega, had an arbitrary group action defined on it. Conditions under which genetic operators respect certain subsets of omega were identified, leading to a generalisation of the term schema. In this paper, search space groups with more detailed structure are examined. We define the class of structural crossover operators that respect certain schemata in these groups, which leads to a generalised schema theorem. Recent results concerning the Fourier (or Walsh) transform are generalised. In particular, it is shown that the matrix group representing omega can be simultaneously diagonalised if and only if omega is Abelian. Some results concerning structural crossover and mutation are given for this case.

Viscous populations and their support for reciprocal cooperation.

Viscous populations (those whose members are spatially distributed and have limited mobility and locality of interaction and mating) have been proposed to support the evolution of reciprocal cooperation among self-interested individuals. Here we present a model of such a population and describe how its examination yielded the realization that different classes of viscous populations exist with differing levels of support for reciprocal cooperation. Specifically we find from our model that, in a spatially distributed population with increased viscosity, the reciprocally cooperative tit-for-tat strategy may not be globally stable due to a corresponding increase in local population density.

Kin selection may inhibit the evolution of reciprocation.

Kin selection and reciprocal cooperation provide two candidate explanations for the evolution of cooperation. Models of the evolution of cooperation have typically focussed on one or the other mechanism, despite claims that kin selection could pave the way for the evolution of reciprocal cooperation. We describe a computer simulation model that explicitly supports both kin selection and reciprocal cooperation. The model simulates a viscous population of discrete individuals with social interaction taking the form of the Prisoner's Dilemma and selection acting on performance in these interactions. We recount how the analytical and empirical study of this model led to the conclusion that kin selection may actually inhibit the evolution of effective strategies for establishing reciprocal cooperation.

Group properties of crossover and mutation.

It is supposed that the finite search space omega has certain symmetries that can be described in terms of a group of permutations acting upon it. If crossover and mutation respect these symmetries, then these operators can be described in terms of a mixing matrix and a group of permutation matrices. Conditions under which certain subsets of omega are invariant under crossover are investigated, leading to a generalization of the term schema. Finally, it is sometimes possible for the group acting on omega to induce a group structure on omega itself.