In the last 10 years a major strand of my research within the Essex Brain-Computer Interfaces and Neural Engineering (BCI-NE) laboratory has focused on the idea of combining brain signals (and other physiological and behavioral information) across multiple people to achieve a form of emergent, perceptual and, more generally cognitive, group augmentation, which is more than the sum of the parts.

Smartphones and wearable sensors are increasingly used for personalised prediction and management in healthcare contexts. Personalisation requires tuning/learning a model of the user. However, traditional machine learning approaches for personalised modelling typically require the availability of sufficient personal data of a suitable nature for training, which can be a challenge in such contexts. We propose a parametric transfer learning approach based on the Fisher divergence to address this challenge. This makes it possible to create patient-specific models and make predictions of self-reported well-being scores, when training is performed incrementally on sparse data becoming slowly available over time. This approach allows us to make informed predictions even in the early stages of data collection, by leveraging external information coming from other patients, in the form of a prior used within a Markov-Chain Monte Carlo process. Our approach performs favourably against competing models and standard baselines, particularly when long-term forecasts are required but training data cover only a short period.

Several previous studies have focused on modelling and analysing the collective dynamic behaviour of population-based algorithms. However, an empirical approach for identifying and characterising such a behaviour is surprisingly lacking. In this paper, we present a new model to capture this collective behaviour, and to extract and quantify features associated with it. The proposed model studies the topological distribution of an algorithm's activity from both a genotypic and a phenotypic perspective, and represents population dynamics using multiple levels of abstraction. The model can have different instantiations. Here it has been implemented using a modified version of self-organising maps. These are used to represent and track the population motion in the fitness landscape as the algorithm operates on solving a problem. Based on this model, we developed a set of features that characterise the population's collective dynamic behaviour. By analysing them and revealing their dependency on fitness distributions, we were then able to define an indicator of the exploitation behaviour of an algorithm. This is an entropy-based measure that assesses the dependency on fitness distributions of different features of population dynamics. To test the proposed measures, evolutionary algorithms with different crossover operators, selection pressure levels and population handling techniques have been examined, which lead populations to exhibit a wide range of exploitation-exploration behaviours.

Large sparse symmetric matrices are typical characteristics of the linear systems found in various scientific and engineering disciplines, such as fluid mechanics, structural engineering, finite element analysis, and network analysis. In all such systems, the performance of solvers crucially depends on the sum of the distance of each matrix element from the matrix's main diagonal. This quantity is known as the envelope. In order to reduce the envelope of a matrix, its rows and columns should be reordered properly. The problem of minimizing the envelope size is exceptionally hard and known to be NP-complete. A considerable number of methods have been developed for reducing the envelope among which the Sloan algorithm offered a substantial improvement over previous algorithms. In this paper, a hyper-heuristic approach based on genetic programming, which we term genetic hyper-heuristic, is introduced for evolving an enhanced version of the Sloan algorithm. We also present a local search algorithm and integrate it with the new algorithm produced by our hyper-heuristic to further improve the quality of the solutions. The new algorithms are evaluated on a large set of standard benchmarks against six state-of-the-art algorithms from the literature. Our algorithms outperform all the methods under testing by a wide margin.

We explored the possibility of controlling a spacecraft simulator using an analogue Brain-Computer Interface (BCI) for 2-D pointer control. This is a difficult task, for which no previous attempt has been reported in the literature. Our system relies on an active display which produces event-related potentials (ERPs) in the user's brain. These are analysed in real-time to produce control vectors for the user interface. In tests, users of the simulator were told to pass as close as possible to the Sun. Performance was very promising, on average users managing to satisfy the simulation success criterion in 67.5% of the runs. Furthermore, to study the potential of a collaborative approach to spacecraft navigation, we developed BCIs where the system is controlled via the integration of the ERPs of two users. Performance analysis indicates that collaborative BCIs produce trajectories that are statistically significantly superior to those obtained by single users.

Modeling the behavior of algorithms is the realm of evolutionary algorithm theory. From a practitioner's point of view, theory must provide some guidelines regarding which algorithm/parameters to use in order to solve a particular problem. Unfortunately, most theoretical models of evolutionary algorithms are difficult to apply to realistic situations. However, in recent work (Graff and Poli, 2008, 2010), where we developed a method to practically estimate the performance of evolutionary program-induction algorithms (EPAs), we started addressing this issue. The method was quite general; however, it suffered from some limitations: it required the identification of a set of reference problems, it required hand picking a distance measure in each particular domain, and the resulting models were opaque, typically being linear combinations of 100 features or more. In this paper, we propose a significant improvement of this technique that overcomes the three limitations of our previous method. We achieve this through the use of a novel set of features for assessing problem difficulty for EPAs which are very general, essentially based on the notion of finite difference. To show the capabilities or our technique and to compare it with our previous performance models, we create models for the same two important classes of problems-symbolic regression on rational functions and Boolean function induction-used in our previous work. We model a variety of EPAs. The comparison showed that for the majority of the algorithms and problem classes, the new method produced much simpler and more accurate models than before. To further illustrate the practicality of the technique and its generality (beyond EPAs), we have also used it to predict the performance of both autoregressive models and EPAs on the problem of wind speed forecasting, obtaining simpler and more accurate models that outperform in all cases our previous performance models.

Kimura's neutral theory of evolution has inspired researchers from the evolutionary computation community to incorporate neutrality into evolutionary algorithms (EAs) in the hope that it can aid evolution. The effects of neutrality on evolutionary search have been considered in a number of studies, the results of which, however, have been highly contradictory. In this paper, we analyze the reasons for this and make an effort to shed some light on neutrality by addressing them. We consider two very simple forms of neutrality: constant neutrality-a neutral network of constant fitness, identically distributed in the whole search space-and bit-wise neutrality, where each phenotypic bit is obtained by transforming a group of genotypic bits via an encoding function. We study these forms of neutrality both theoretically and empirically (both for standard benchmark functions and a class of random MAX-SAT problems) to see how and why they influence the behavior and performance of a mutation-based EA. In particular, we analyze how the fitness distance correlation of landscapes changes under the effect of different neutral encodings and how phenotypic mutation rates vary as a function of genotypic mutation rates. Both help explain why the behavior of a mutation-based EA may change so radically as problem, form of neutrality, and mutation rate are varied.

Here we propose GP-zip3, a system which uses Genetic Programming to find optimal ways to combine standard compression algorithms for the purpose of compressing files and archives. GP-zip3 evolves programs with multiple components. One component analyses statistical features extracted from the raw data to be compressed (seen as a sequence of 8-bit integers) to divide the data into blocks. These blocks are then projected onto a two-dimensional Euclidean space via two further (evolved) program components. K-means clustering is applied to group similar data blocks. Each cluster is then labelled with the optimal compression algorithm for its member blocks. Once a program that achieves good compression is evolved, it can be used on unseen data without the requirement for any further evolution. GP-zip3 is similar to its predecessor, GP-zip2. Both systems outperform a variety of standard compression algorithms and are faster than other evolutionary compression techniques. However, GP-zip2 was still substantially slower than off-the-shelf algorithms. GP-zip3 alleviates this problem by using a novel fitness evaluation strategy. More specifically, GP-zip3 evolves and then uses decision trees to predict the performance of GP individuals without requiring them to be used to compress the training data. As shown in a variety of experiments, this speeds up evolution in GP-zip3 considerably over GP-zip2 while achieving similar compression results, thereby significantly broadening the scope of application of the approach.

We present a grammar-based genetic programming framework for the solving the timetabling problem via the evolution of constructive heuristics. The grammar used for producing new generations is based on graph colouring heuristics that have previously proved to be effective in constructing timetables as well as different slot allocation heuristics. The framework is tested on a widely used benchmarks in the field of exam time-tabling and compared with highly-tuned state-of-the-art approaches. Results shows that the framework is very competitive with other constructive techniques.

Biological organisms exhibit numerous types of plasticity, where they respond both developmentally and behaviorally to environmental factors. In some organisms, for example, environmental conditions can lead to the developmental expression of genes that would otherwise remain dormant, leading to significant phenotypic variation and allowing selection to act on these otherwise "invisible" genes. In contrast to biological plasticity, the vast majority of evolutionary computation systems, including genetic programming, are rigid and can only adapt to very limited external changes. In this paper we extend the N-gram GP system, a recently introduced estimation of distribution algorithm for program evolution, using Incremental Fitness-based Development (IFD), a novel technique which allows for developmental plasticity in the generation of linear-GP style programs. Tests with a large set of problems show that the new system outperforms the original N-gram GP system and is competitive with standard GP. Analysis of the evolved programs indicates that IFD allows for the generation of more complex programs than standard N-gram GP, with the generated programs often containing several separate sequences of instructions that are reused multiple times, often with variations.

In this paper we prove that for a variety of practical situations, the no-free-lunch (NFL) theorem does not apply to algorithms that search the space of artificial neural networks, such as evolutionary algorithms. We find, in particular, that, while conditions under which NFL applies exist, these require extremely restrictive symmetries on the set of possible problems which are unlikely encountered in practice. In other words, not all algorithms are equally good at finding neural networks that solve problems under all possible performance measures: a superior search algorithm for this domain does exist.

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

Several theoretical analyses of the dynamics of particle swarms have been offered in the literature over the last decade. Virtually all rely on substantial simplifications, often including the assumption that the particles are deterministic. This has prevented the exact characterization of the sampling distribution of the particle swarm optimizer (PSO). In this paper we introduce a novel method that allows us to exactly determine all the characteristics of a PSO sampling distribution and explain how it changes over any number of generations, in the presence stochasticity. The only assumption we make is stagnation, i.e., we study the sampling distribution produced by particles in search for a better personal best. We apply the analysis to the PSO with inertia weight, but the analysis is also valid for the PSO with constriction and other forms of PSO.

Inc* is a general algorithm that can be used in conjunction with any local search heuristic and that has the potential to substantially improve the overall performance of the heuristic. The general idea of the algorithm is the following. Rather than attempting to directly solve a difficult problem, the algorithm dynamically chooses a smaller instance of the problem, and then increases the size of the instance only after the previous simplified instances have been solved, until the full size of the problem is reached. Genetic programming is used to discover new strategies for Inc*. Preliminary experiments on the satisfiability problem (SAT) problem have shown that Inc* is a competitive approach. In this paper we enhance Inc* and we experimentally test it on larger set of benchmarks, including big instances of SAT. Furthermore, we provide an analysis of the algorithmpsilas behaviour.

In this paper we propose a new approach for applying genetic programming to lossless data compression based on combining well-known lossless compression algorithms. The file to be compressed is divided into chunks of a predefined length, and GP is asked to find the best possible compression algorithm for each chunk in such a way to minimise the total length of the compressed file. This technique is referred to as ldquoGP-ziprdquo: The compression algorithms available to GP-zip (its function set) are: arithmetic coding (AC), Lempel-Ziv-Welch (LZW), unbounded prediction by partial matching (PPMD), run length encoding (RLE), and Boolean minimization. In addition, two transformation techniques are available: Burrows-Wheeler transformation (BWT) and move to front (MTF). In experimentation with this technique, we show that when the file to be compressed is composed of heterogeneous data fragments (as is the case, for example, in archive files), GP-zip is capable of achieving compression ratios that are superior to those obtained with well-known compression algorithms.

In previous work, we have introduced an effective, resource-efficient and self-adapting hyperheuristic that uses genetic programming (GP) as its method of search in the space of domain-specific metaheuristics. GP employs user-provided, local heuristics from which it produces these metaheuristics (MHs). Here, we show that the hyperheuristic performs even better when working at the subheuristic level, i.e., when building MHs from generic components and specific elementary operations. In particular, this approach supports efficiency of the better MHs. Specifically, these MHs do not excessively iterate local search steps, i.e., their good performance comes from smart patterns of calls of the provided, basic components. Also, a moderate reduction of the maximum allowed MH size does not reduce performance significantly.

In previous work, we have introduced an effective and resource-efficient hyperheuristic that uses Genetic Programming as its search heuristic on the space of heuristics. Here, we show that the hyperheuristic performs better than purely greedy and even only mostly greedy flavours of hill climbing. We also introduce a generic principle that allows the hyperheuristic to automatically find good parameter values for its effective and efficient search.

Hyper-Heuristics are methods to choose and combine heuristics to generate new ones. In this work, we use a grammar-based genetic programming system as a Hyper-Heuristic framework. The framework is used for evolving effective incremental solvers for SAT (Inc*). Tests against well-known local search heuristics on a variety of benchmark problems reveal that the evolved heuristics are superior. Categories and Subject Descriptors

In recent research we proposed GP-zip, a system which uses evolution to find optimal ways to combine standard compression algorithms for the purpose of maximally losslessly compressing files and archives. The system divides files into blocks of predefined length. It then uses a linear, fixed-length representation where each primitive indicates what compression algorithm to use for a specific data block. GP-zip worked well with heterogonous data sets, providing significant improvements in compression ratio compared to some of the best standard compression algorithms. In this paper we propose a substantial improvement, called GP-zip*, which uses a new representation and intelligent crossover and mutation operators such that blocks of different sizes can be evolved. Like GP-zip, GP-zip* finds what the best compression technique to use for each block is. The compression algorithms available in the primitive set of GP-zip* are: Arithmetic coding (AC), Lempel-Ziv-Welch (LZW), Unbounded Prediction by Partial Matching (PPMD), Run Length Encoding (RLE), and Boolean Minimization. In addition, two transformation techniques are available: the Burrows-Wheeler Transformation (BWT) and Move to Front (MTF). Results show that GP-zip* provides improvements in compression ratio ranging from a fraction to several tens of percent over its predecessor.

Our previous work has introduced a {hyperheuristic} (HH) approach based on Genetic Programming (GP). There, GP employs user-given languages where domain-specific local heuristics are used as primitives for producing specialised metaheuristics (MH). Here, we show that the GP-HH works well with simple generic languages over subheuristic primitives, dealing with increases of problem size and reduction of resources. The system produces effective and efficient MHs that deliver best results known in a chosen test domain. We also demonstrate that user-given, modest domain information allows the HH to produce an improvement over a previous best result from the literature.

Based in part on observations about the incremental nature of most state changes in biological systems, we introduce the idea of Memory with Memory in Genetic Programming (GP), where we use "soft" assignments to registers instead of the "hard" assignments used in most computer science (including traditional GP). Instead of having the new value completely overwrite the old value of the register, these soft assignments combine the old and new values.

The parsimony pressure method is perhaps the simplest and most frequently used method to control bloat in genetic programming. In this paper we first reconsider the size evolution equation for genetic programming developed in [26] and rewrite it in a form that shows its direct relationship to Price's theorem. We then use this new formulation to derive theoretical results that show how to practically and optimally set the parsimony coefficient dynamically during a run so as to achieve complete control over the growth of the programs in a population. Experimental results confirm the effectiveness of the method, as we are able to tightly control the average program size under a variety of conditions. These include such unusual cases as dynamically varying target sizes such that the mean program size is allowed to grow during some phases of a run, while being forced to shrink in others.

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

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

In most forms of selection, when multiple individuals are needed for an operation, these are drawn independently from the population. So, for example, in the case of crossover, the probability of a particular pair of parents being selected is given by the product of the selection probabilities of each parent. In this paper we investigate a form of selection where pairs of parents are not selected independently. We show that a particular form of dependent selection, linear selection, leads a genetic algorithm with homologous crossover to become very similar to a genetic algorithm with standard (independent) selection and headless chicken crossover, i.e., it turns crossover into a type of mutation. In the paper we analyse this form of selection theoretically, and we compare it to ordinary selection with crossover and headless chicken crossover in real runs.

We use a form of grammar-based linear Genetic Programming (GP) as a hyperheuristic, i.e., a search heuristic on the space of heuristics. This technique is guided by domain- specific languages that one designs taking inspiration from elementary components of specialised heuristics and metaheuristics for a domain. We demonstrate this approach for traveling- salesperson problems for which we test different languages, including one containing a looping construct. Experimentation with benchmark instances from the TSPLIB shows that the GP hyperheuristic routinely and rapidly produces parsimonious metaheuristics that find tours whose lengths are highly competitive with the best real-valued lengths from literature.

In this paper we derive a simpler form of Particle Swarm Optimiser (PSO) which still retains the key properties of the original model. We do so by progressively altering the original model via mathematical transformations which have clear and understandable probabilistic effects. Then we study this new PSO mathematically and compare it to the original PSO. In particular we analyse the stability and the sampling distribution for the new PSO during stagnation. Finally, we test it on 14 standard benchmark problems and with two different communication topologies, with very encouraging results.

We present a novel algorithm for the one- dimension offline bin packing problem with discrete item sizes based on the notion of matching the item-size histogram with the bin-gap histogram. The approach is controlled by a constructive heuristic function which decides how to prioritise items in order to minimise the difference between histograms. We evolve such a function using a form of linear register-based genetic programming system. We test our evolved heuristics and compare them with hand-designed ones, including the well- known best fit decreasing heuristic. The evolved heuristics are human-competitive, generally being able to outperform high- performance human-designed heuristics.

No abstract available.

Recent work has introduced a simulation model of ecological processes in terms of a very simple Particle Swarm algorithm. This abstract model produced qualitatively realistic behaviours, but do these results hold up in a model constrained by more plausible biological assumptions? The objective of this paper is to answer this question.

Recent research [1] has found that standard sub-tree crossover with uniform selection of crossover points, in the absence of fitness pressure, pushes a population of GP trees towards a Lagrange distribution of tree sizes. However, the result applied to the case of single arity function plus leaf node combinations, e.g., unary, binary, ternary, etc trees only. In this paper we extend those findings and show that the same distribution is also applicable to the more general case where the function set includes functions of mixed arities. We also provide empirical evidence that strongly corroborates this generalisation. Both predicted and observed results show a distinct bias towards the sampling of shorter programs irrespective of the mix of function arities used. Practical applications and implications of this knowledge are investigated with regard to search efficiency and program bloat. Work is also presented regarding the applicability of the theory to the traditional 90%-function 10%-terminal crossover node selection policy.

We investigate a form of selection, linear selection, where parents are not selected independently. One form of dependent selection, semi-linear selection, where the parents are jointly selected with a probability proportional to the average of their selection probabilities, leads the GA to behave half-way between an algorithm driven by crossover and one driven by mutation.

We suggest a flavour of linear Genetic Programming indomain-specific languages that acts as a hyperheuristic (HH).

Despite the vast work on neutrality, there are not general conclusions on its effects. In this paper we make an effort to understand how neutrality influences evolution. For this purpose we will use a type of neutrality that allows locality (which is believed to be a desirable feature of neutrality).

Several theoretical analyses of the dynamics of particle swarms have been offered in the literature over the last decade. Virtually all rely on substantial simplifications, including the assumption that the particles are deterministic. This has prevented the exact characterisation of the sampling distribution of the PSO. In this paper we introduce a novel method, which allows one to exactly determine all the characteristics of a PSO's sampling distribution and explain how they change over any number of generations, in the presence stochasticity. The only assumption we make is stagnation, i.e., we study the sampling distribution produced by particles in search for a better personal best. We apply the analysis to the PSO with inertia weight, but the analysis is also valid for the PSO with constriction.

We apply a novel theoretical approach to better understand the behaviour of different types of bare-bones PSOs. It avoids many common but unrealistic assumptions often used in analyses of PSOs. Using finite element grid techniques, it builds a discrete Markov chain model of the BB-PSO which can approximate it on arbitrary continuous problems to any precision. Iterating the chain's transition matrix gives precise information about the behaviour of the BB-PSO at each generation, including the probability of it finding the global optimum or being deceived. The predictions of the model are remarkably accurate and explain the features of Cauchy, Gaussian and other sampling distributions.

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

This is the second part of a two-part paper where we propose, model theoretically and study a general notion of recombination for fixed-length strings where homologous recombination, inversion, gene duplication, gene deletion, diploidy and more are just special cases. In Part I, we derived both microscopic and coarse-grained evolution equations for strings and schemata for a selecto-recombinative GA using generalised recombination, and we explained the hierarchical nature of the schema evolution equations. In this part, we provide a variety of fixed points for evolution in the case where recombination is used alone, thereby generalising Geiringer's theorem. In addition, we numerically integrate the infinite-population schema equations for some interesting problems, where selection and recombination are used together to illustrate how these operators interact. Finally, to assess by how much genetic drift can make a system deviate from the infinite-population-model predictions we discuss the results of real GA runs for the same model problems with generalised recombination, selection and finite populations of different sizes.

We use evolutionary computation (EC) to automatically find problems which demonstrate the strength and weaknesses of modern search heuristics. In particular, we analyze particle swarm optimization (PSO), differential evolution (DE), and covariance matrix adaptation-evolution strategy (CMA-ES). Each evolutionary algorithm is contrasted with the others and with a robust nonstochastic gradient follower (i.e., a hill climber) based on Newton-Raphson. The evolved benchmark problems yield insights into the operation of PSOs, illustrate benefits and drawbacks of different population sizes, velocity limits, and constriction (friction) coefficients. The fitness landscapes made by genetic programming reveal new swarm phenomena, such as deception, thereby explaining how they work and allowing us to devise better extended particle swarm systems. The method could be applied to any type of optimizer.

An exact microscopic model for the dynamics of a genetic algorithm with generalized recombination is presented. Generalized recombination is a new model for the exchange of genetic material from parents to offspring that generalizes and subsumes standard operators, such as homologous crossover, inversion and duplication, and in which a particular gene in the offspring may originate from any parental gene. It is shown that the dynamics naturally coarse grains, the appropriate effective degrees of freedom being schemata that act as building blocks. It is shown that the Schema dynamics has the same functional form as that of strings and we derive a corresponding exact Schema theorem. To exhibit the qualitatively new phenomena that can occur in the presence of generalized recombination, and to understand the biases of the operator, we derive a complete, exact solution for a two-locus model without selection, showing how the dynamical behavior is radically different to that of homologous crossover. Inversion is shown to potentially introduce oscillations in the dynamics, while gene duplication leads to an asymmetry between homogeneous and heterogeneous strings. All nonhomologous operators lead to allele ldquodiffusionrdquo along the chromosome. We discuss how inferences from the two-locus results extend to the case of a recombinative genetic algorithm with selection and more than two loci providing evidence from an integration of the exact dynamical equations for more than two loci.

The Kolmogorov complexity (KC) of a string is defined as the length of the shortest program that can print that string and halts. This measure of complexity is often used in optimization to indicate expected function difficulty. While it is often used, there are known counterexamples. This paper investigates the applicability of KC as an estimator of problem difficulty for optimization in the black box scenario. In particular we address the known counterexamples (e.g., pseudorandom functions, the NIAH) and explore the connection of KC to the NFLTs. We conclude that high KC implies hardness however, while easy fitness functions have low KC the reverse is not necessarily true.

Particle swarm optimiser and genetic algorithm populations are macro-organisms, which perceive their environment as if filtered via a kernel. The kernel assimilates each individual's sensory abilities so that the collective moves using a greedy hill-climbing strategy. This model is fitted to data collected in real PSO and GA runs by using genetic programming to evolve the kernel. In nature animals tend to live within groups. The social interactions effectively transform the fitness selection landscape seen by an isolated individual. In some cases a group behaves (or even can be said to think) like a single organism. Kernels provide a lens which coarse-grains or averages individual senses and so may help explain joint actions and social responses. The original multi-modal problem is smoothed by convolving it with a problem specific filter designed by GP. Because populations see the transformed social fitness landscape, they can pass over local optima. GP can give a good fit between the predicted behaviour of the macroscopic organism and the actual runs.

In recent work we have formulated a model of emergent coordinated behaviour for a population of interacting entities. The model is a modified spring mass model where masses can perceive the environment and generate external forces. As a result of the interactions the population behaves like a single organism moving under the effect the vector sum of the external forces generated by each entity. When such forces are proportional to the gradient of a resource distribution f(x), the resultant force controlling the single emergent organism is proportional to the gradient of a modified food distribution. This is the result of applying a filtering kernel to f(x). The kernel is typically a low-pass filter. This model can be applied to genetic algorithms (GAs) and other population-based search algorithms. For example, in previous research, we have found kernels (via genetic programming) that allow the single organism model to track the motion of the centre of mass of GAs and particle swarm optimisers accurately for many generations. In this paper we corroborate this model in several ways. Firstly, we provide a mathematical proof that on any problem and for any crossover operator, the effect of crossover is that of reducing the amplitude of the derivatives (slopes) of the population distribution. This implies that a GA perceives an effective fitness landscape which is a smoothed, low-pass filtered version of the original. Then, taking inspiration from this result and our active mass-spring model, we propose a class of fitness functions, OneMix, where there is an area of the landscape with high frequency variations. This area contains the global optimum but a genetic algorithm with high crossover probability should not be able "see" it due to its low-pass behaviour. So, a GA with strong crossover should be deceived and attracted towards a local optimum, while with low crossover probability this should not happen. This is, indeed, what happens as we demonstrate with a variety of empirical runs and with infinite-population model simulations. Finally, following our earlier approach, we also evolved kernels for OneMix, obtaining again a good fit between the behaviour of the "single-organism" hill-climber and the GA.

The No-Free-Lunch theorems (NFLTs) are criticized for being too general to be of any relevance to the real world scenario. This paper investigates, both formally and empirically, the implications of the NFLTs for realistic search algorithms. In the first part of the paper, by restricting ourselves to a specific performance measure, we derive a new NFL result for a class of problems which is not closed under permutations. In the second part, we discuss properties of this set which are likely to be true for realistic search algorithms. We provide empirical support for this in [1].

The no-free-lunch theorems (NFLTs) do not consider explicitly the structure of problems. In [1] we gave a formal definition of structure. We showed that many metaheuristics have identical performance on problems which belong to the same structural class. In this paper, we define a notion of a distance between fitness functions. We argue that an algorithm cannot be efficient on a class of problems if the distance between the fitness function associated with instances of that class is too big. In [2] we corroborate our ideas using several problems.

Metaheuristics have often been shown to be effective for difficult combinatorial optimization problems. The reason for that, however, remains unclear. A framework for a theory of metaheuristics crucially depends on a formal representative model of such algorithms. This paper unifies/reconciles in a single framework the model of a black box algorithm coming from the no-free-lunch research (e.g. Wolpert et al. [25], Wegener [23]) with the study of fitness landscape. Both are important to the understanding of meta-heuristics, but they have so far been studied separately. The new model is a natural environment to study meta-heuristics.

The effects of neutrality on evolutionary search have been considered in a number of interesting studies, the results of which, however, have been contradictory. Some researchers have found neutrality to be beneficial to aid evolution whereas others have argued that the presence of neutrality in the evolutionary process is useless. We believe that this confusion is due to several reasons: many studies have based their conclusions on performance statistics (e.g., on whether or not a system with neutrality could solve a particular problem faster than a system without neutrality) rather than a more in-depth analysis of population dynamics, studies often consider problems, representations and search algorithms that are relatively complex and so results represent the compositions of multiple effects (e.g., bloat or spurious attractors in genetic programming), there is not a single definition of neutrality and different studies have added neutrality to problems in radically different ways. In this paper, we try to shed some light on neutrality by addressing these problems. That is, we use the simplest possible definition of neutrality (a neutral network of constant fitness, identically distributed in the whole search space), we consider one of the simplest possible algorithms (a mutation based, binary genetic algorithm) applied to two simple problems (a unimodal landscape and a deceptive landscape), and analyse both performance figures and, critically, population flows from and to the neutral network and the basins of attraction of the optima.

We propose a new crossover that generalizes cycle crossover to permutations with repetitions and naturally suits partition problems. We tested it on graph partitioning problems obtaining excellent results.

March 01 2006 Editorial for the Special Issue on the Best of GECCO 2004 In Special Collection: CogNet Riccardo Poli, Riccardo Poli Search for other works by this author on: This Site Google Scholar Marc Schoenauer Marc Schoenauer December 2005 Search for other works by this author on: This Site Google Scholar Author and Article Information Riccardo Poli Marc Schoenauer December 2005 Online Issn: 1530-9304 Print Issn: 1063-6560 © 2006 Massachusetts Institute of Technology2006 Evolutionary Computation (2006) 14 (1): v. https://doi.org/10.1162/evco.2006.14.1.v Cite Icon Cite Permissions Share Icon Share Facebook Twitter LinkedIn MailTo Views Icon Views Article contents Figures & tables Video Audio Supplementary Data Peer Review Search Site Citation Riccardo Poli, Marc Schoenauer; Editorial for the Special Issue on the Best of GECCO 2004. Evol Comput 2006; 14 (1): v. doi: https://doi.org/10.1162/evco.2006.14.1.v Download citation file: Ris (Zotero) Reference Manager EasyBib Bookends Mendeley Papers EndNote RefWorks BibTex toolbar search Search Dropdown Menu toolbar search search input Search input auto suggest filter your search All ContentAll JournalsEvolutionary Computation Search Advanced Search This content is only available as a PDF. © 2006 Massachusetts Institute of Technology2006 Article PDF first page preview Close Modal You do not currently have access to this content.

This is the first part of a two-part paper where we propose, model theoretically and study a general notion of recombination for fixed-length strings, where homologous recombination, inversion, gene duplication, gene deletion, diploidy and more are just special cases. The analysis of the model reveals that the notion of schema emerges naturally from the model's equations. In Part I, after describing and characterising the notion of generalised recombination, we derive both microscopic and coarse-grained evolution equations for strings and schemata and illustrate their features with simple examples. Also, we explain the hierarchical nature of the schema evolution equations and show how the theory presented here generalises past work in evolutionary computation. In Part II, the study provides a variety of fixed points for evolution in the case where recombination is used alone, which generalise Geiringer's theorem. In addition, we numerically integrate the infinite-population schema equations for some interesting problems, where selection and recombination are used together to illustrate how these operators interact. Finally, to assess by how much genetic drift can make a system deviate from the infinite-population-model predictions we discuss the results of real GA runs for the same model problems with generalised recombination, selection and finite populations of different sizes.

The permutation closure of a single function is the finest level of granularity at which a no-free-lunch result can hold (Schumacher et al., 2001). Using the information landscape framework which was introduced in "Information Landscapes" by Borenstein and Poli (2005), we are able to identify the unique properties of each closure. In particular, we associate each closure with the amount of information its members contain. This allows us to compute bounds on the expected performance of an algorithm on members of that closure. Moreover, we suggest a new way to measure the Kolmogorov complexity of a landscape. This allows us to associate each permutation closure with a particular Kolmogorov complexity.

We use evolutionary computation (EC) to automatically find problems which demonstrate the strength and weaknesses of modern search heuristics. In particular we analyse particle swarm optimization (PSO) and differential evolution (DE). Both evolutionary algorithms are contrasted with a robust deterministic gradient based searcher (based on Newton-Raphson). The fitness landscapes made by genetic programming (GP) are used to illustrate difficulties in GAs and PSOs thereby explaining how they work and allowing us to devise better extended particle swarm systems (XPS)

An Internet Java Applet http://www.cs.essex.ac.uk/staff/poli/SoloPong/ allows users anywhere to play the Solo Pong game. We compare people's performance to a hand coded "optimal" player and programs automatically produced by computational intelligence. The computational intelligence techniques are: genetic programming, including a hybrid of GP and a human designed algorithm, and a particle swarm optimiser. The computational intelligence approaches are not fine tuned. GP and PSO find good players. Evolutionary computation (EC) is able to beat both human designed code and human players.

The relationship between search space, distances and genetic operators for syntactic trees is little understood. Geometric crossover and geometric mutation are representation-independent operators that are well-defined once a notion of distance over the solution space is defined. In this paper we apply this geometric framework to the syntactic tree representation and show how the well-known structural distance is naturally associated with homologous crossover and sub-tree mutation

In this paper we propose, model theoretically and study a general notion of recombination for fixed-length strings where homologous crossover, inversion, gene duplication, gene deletion, diploidy and more are just special cases. The analysis of the model reveals similarities and differences between genetic systems based on these operations. It also reveals that the notion of schema emerges naturally from the model's equations even for the strangest of recombination operations. The study provides a variety of fixed points for the case where recombination is used alone, which generalise Geiringer's manifold.

A generalised form of recombination, wherein an offspring can be formed from any of the genetic material of the parents, is analysed in the context of a two-locus recombinative GA. A complete, exact solution, is derived, showing how the dynamical behaviour is radically different to that of homologous crossover. Inversion is shown to potentially introduce oscillations in the dynamics, while gene duplication leads to an asymmetry between homogeneous and heterogeneous strings. All non-homologous operators lead to allele "diffusion" along the chromosome. We discuss how inferences from the two-locus results extend to the case of a recombinative GA with selection and more than two loci.

In [15] we introduced the information landscape as a new concept of a landscape. We showed that for a landscape of a small size, information landscape theory can be used to predict the performance of a GA without running the algorithm. Based on this framework, here we develop a new theoretical model to study search algorithms in general. Particularly, we are able to infer important properties of a search algorithm without having knowledge about its specific operators. We give an example of this technique for a simple GA.

In [20] we introduced a new concept of a landscape: the information landscape. We showed that for problems of very small size (e.g. a 3-bit problem), it can be used to generally and accurately predict the performance of a GA. Based on this framework, in this paper we develop a method to predict GA hardness on realistic landscapes. We give empirical results which support our approach.

We give a new interpretation to the concept of landscape. This allows us to develop a new theoretical model to study search algorithms. Particularly, we are able to quantify the amount and quality of information embedded in a landscape and to predict the performance of a search algorithm over it. We conclude presenting empirical results for a simple genetic algorithm which strongly support this idea.

Particle Swarm Optimisation (PSO) uses a population of particles that fly over the fitness landscape in search of an optimal solution. The particles are controlled by forces that encourage each particle to fly back both towards the best point sampled by it and towards the swarm's best point, while its momentum tries to keep it moving in its current direction.Previous research started exploring the possibility of evolving the force generating equations which control the particles through the use of genetic programming (GP).We independently verify the findings of the previous research and then extend it by considering additional meaningful ingredients for the PSO force-generating equations, such as global measures of dispersion and position of the swarm. We show that, on a range of problems, GP can automatically generate new PSO algorithms that outperform standard human-generated as well as some previously evolved ones.

This paper presents a backward-chaining version of GP.

This is the first part of a two-part paper which introduces a general schema theory for genetic programming (GP) with subtree-swapping crossover. The theory is based on a Cartesian node reference system which makes it possible to describe programs as functions over the space N(2) and allows one to model the process of selection of the crossover points of subtree-swapping crossovers as a probability distribution over N(4). In Part I, we present these notions and models and show how they can be used to calculate useful quantities. In Part II we will show how this machinery, when integrated with other definitions, such as that of variable-arity hyperschema, can be used to construct a general and exact schema theory for the most commonly used types of GP.

This paper is the second part of a two-part paper which introduces a general schema theory for genetic programming (GP) with subtree-swapping crossover (Part I (Poli and McPhee, 2003)). Like other recent GP schema theory results, the theory gives an exact formulation (rather than a lower bound) for the expected number of instances of a schema at the next generation. The theory is based on a Cartesian node reference system, introduced in Part I, and on the notion of a variable-arity hyperschema, introduced here, which generalises previous definitions of a schema. The theory includes two main theorems describing the propagation of GP schemata: a microscopic and a macroscopic schema theorem. The microscopic version is applicable to crossover operators which replace a subtree in one parent with a subtree from the other parent to produce the offspring. Therefore, this theorem is applicable to Koza's GP crossover with and without uniform selection of the crossover points, as well as one-point crossover, size-fair crossover, strongly-typed GP crossover, context-preserving crossover and many others. The macroscopic version is applicable to crossover operators in which the probability of selecting any two crossover points in the parents depends only on the parents' size and shape. In the paper we provide examples, we show how the theory can be specialised to specific crossover operators and we illustrate how it can be used to derive other general results. These include an exact definition of effective fitness and a size-evolution equation for GP with subtree-swapping crossover.

Understanding operator bias in evolutionary computation is important because it is possible for the operator's biases to work against the intended biases induced by the fitness function. Developments in genetic programming (GP) schema theory can be used to better understand the biases induced by the standard subtree crossover when GP is applied to variable-length linear structures. In this paper, we use the schema theory to better understand the biases induced on linear structures by two common GP subtree mutation operators: FULL and GROW mutation. In both cases, we find that the operators do have quite specific biases and typically strongly oversample shorter strings.

A new general genetic programming (GP) schema theory for headless chicken crossover and subtree mutation is presented. The theory gives an exact formulation for the expected number of instances of a schema at the next generation, either in terms of microscopic quantities or in terms of macroscopic ones. This paper gives examples which show how the theory can be specialised to specific operators.

The article first illustrates the motivations of the author for teaching evolutionary computation and supervising students interested in this field. Then it describes the evolutionary computation course taught by the author at the School of Computer Science of The University of Birmingham (UK) for the last four years (1995-9). Finally, the paper describes the lessons learnt from doing this.

Genetic algorithms (GAs) are powerful search techniques that are used to solve difficult problems in many disciplines. Unfortunately, they can be very demanding in terms of computation load and memory. Parallel genetic algorithms (PGAs) are parallel implementations of GAs which can provide considerable gains in terms of performance and scalability. PGAs can easily be implemented on networks of heterogeneous computers or on parallel mainframes. We review the state of the art on PGAs and propose a new taxonomy also including a new form of PGA (the dynamic deme model) which was recently developed.

Dynamic Demes is a novel method for the parallelisation of evolutionary algorithms. It was derived as a combination of two other parallelisation algorithms: the master-slave distributed fitness evaluation model and the static subpopulation model. The authors present the algorithm, perform a theoretical analysis of its performance and present experimental results where Dynamic Demes was compared with other algorithms.

We review the main results obtained in the theory of schemata in genetic programming (GP), emphasizing their strengths and weaknesses. Then we propose a new, simpler definition of the concept of schema for GP, which is closer to the original concept of schema in genetic algorithms (GAs). Along with a new form of crossover, one-point crossover, and point mutation, this concept of schema has been used to derive an improved schema theorem for GP that describes the propagation of schemata from one generation to the next. We discuss this result and show that our schema theorem is the natural counterpart for GP of the schema theorem for GAs, to which it asymptotically converges.

A computational method is reported which allows the fully automated recovery of the three-dimensional shape of the cardiac left ventricle from a reduced set of apical echo views. Two typically ill-posed problems have been faced: 1) the detection of the left ventricle contours in each view, and 2) the integration of the detected contour points (which form a sparse and partially inconsistent data set) into a single surface representation. The authors' solution to these problems is based on a careful integration of standard computer vision algorithms with neural networks. Boundary detection comprises three steps: edge detection, edge grouping, and edge classification. The first and second steps (which are typical early-vision tasks not involving specific domain-knowledge) have been performed through fast, well-established algorithms of computer vision. The higher level task of left ventricle-edge discrimination, which involves the exploitation of specific knowledge about the left ventricle silhouette, has been performed by feedforward neural networks. Following the most recent results in the field of computer vision, the first step in solving the problem of recovering the ventricle surface has been the adoption of a physically inspired model of it. Basically, the authors have modeled the left ventricle surface as a closed, thin, elastic surface and the data as a set of radial springs acting on it. The recovery process is equivalent to the settling of the surface-plus-springs system into a stable configuration of minimum potential energy. The finite element discretization of this model leads directly to an analog neural-network implementation. The efficiency of such an implementation has been remarkably enhanced through a learning algorithm which embeds specific knowledge about the shape of the left ventricle in the network. Experiments using clinical echographic sequences are described. Four apical views (each with a different rotation of the probe) have been acquired during a heartbeat from a set of seven normal subjects. These images have been utilized to set the various processing modules and test their capabilities.

The authors describe a method for contour-based segmentation of anatomical structures in tomographic images. The method requires three steps. First the authors manually trace one or more 2D contours of a structure of interest. Such contours are then used as training examples in designing a nonlinear edge-detector using a genetic algorithm. Finally, by applying the edge detector to the whole dataset the authors perform a 3D segmentation and surface reconstruction. Results obtained on magnetic resonance images of the brain are also reported.>

The coronary tree expert (CORTEX) analyzer, which is a vision system for the description of the bidimensional shape and position of coronary vessels using standard nonsubtracted radiographic images, is described. A bottom-up approach was used to deal with the typical characteristics of medical images, such as structural and nonstructural noise and complexity and variability of biological shapes. On these grounds, grouping criteria were utilized to produce intermediate image representations with an increasing complexity in a hierarchical manner (from edge points to curves, segments, bars, and finally to vessels and their mutual relations). In this way, uncertain, inconsistent, and deficient information was efficiently processed. The evaluation of CORTEX segmentation is also performed according to a signal-detection-theory-like approach.>