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.

A simple Voting algorithm has been shown to be effective at solving the OneMax problem in the presence of high levels of posterior noise in our previous research. In this paper, we extend this analysis to several different noise models, and show that the Voting algorithm remains robust in all of them. We consider the prior noise model and the partial evaluation of randomly selected bits. The Voting algorithm has superior runtime bounds on these problems compared to other published algorithms. We also introduce a new variant of partial evaluation, and further consider the simple model when a comparison-based oracle produces incorrect results with a fixed probability.

In control systems engineering, the selection of controller parameters play an important role in obtaining optimal controller performance. However, it is often not possible to obtain closed-form relationships between the parameters and performance, making the selection process difficult. This paper presents an automated tuning strategy for Model Predictive Controllers (MPC) whereby a meta-cost function is introduced to penalise undesirable behaviour, and subsequently optimised over using black-box search algorithms. To this end, we propose a method of re-parametrising the cost matrices in MPC. This approach results in a box-constrained parametrisation for the matrices, as well as a reduction in the search dimension. The procedure is demonstrated on a diesel engine case study, where we compare the tuning of MPC using the proposed parametrisation to an unbounded parametrisation on a test suite of optimisation algorithms: Simulated Annealing (SA), Particle Swarm Optimisation (PSO), Genetic Algorithms (GA), Nesterov's gradient-free algorithm (NGF) and Covariance Matrix Adaptation Evolution Strategy (CMA-ES). We find that the proposed parametrisation provides a statistically significant advantage on all algorithms tested except CMA-ES, for which the performance was similar. We discuss this latter empirical result in relation to the theoretical invariance properties of CMA-ES.

We study the use of voting mechanisms in populations, and introduce a new Voting algorithm which can solve ONEMAX and JUMP in O(n log n), even for gaps as large as O(n). More significantly, the algorithm solves ONEMAX with added posterior noise in O(n log n), when the variance of the noise distribution is σ2 = O(n) and in O(σ2 log n) when the noise variance is greater than this. We assume only that the noise distribution has finite mean and variance and (for the larger noise case) that it is unimodal. We also examine the performance on arbitrary linear and monotonic functions. The Voting algorithm fails on LEADINGSONES but we give a variant which can solve the problem in O(n log n). We empirically study the use of voting in population based algorithms (UMDA, PCEA and cGA) and show that this can be effective for large population sizes.

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.

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.

This paper analyses a generational evolutionary algorithm using only selection and uniform crossover. With a probability arbitrarily close to one the evolutionary algorithm is shown to solve onemax in O(n log2(n)) function evaluations using a population of size c,n, log(n). We then show that this algorithm can solve onemax with noise variance n again in O(n log2(n)) function evaluations.

We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,λ) EA. We establish a sharp threshold at λ = log{\frac{e}{e-1}} n ≈5 log10 n between exponential and polynomial running times on OneMax. For any smaller value, the (1,λ) EA needs exponential time on every function that has only one global optimum. We also consider arbitrary unimodal functions and show that the threshold can shift towards larger offspring population sizes. Finally, we investigate the relationship between the offspring population size and arbitrary mutation rates on OneMax. We get sharp thresholds for λ that decrease with the mutation rate. This illustrates the balance between selection and mutation.

We formalize the concept of an unbiased black box algorithm, which generalises the idea previously introduced by Lehre and Witt. Our formalization of bias relates to the symmetry group of the problem class under consideration, establishing a connection with previous work on No Free Lunch. Our definition is motivated and justified by a series of results, including the outcome that given a biased algorithm, there exists a corresponding unbiased algorithm with the same expected behaviour (over the problem class) and equal or better worst-case performance. For the case of evolutionary algorithms, it is already known how to construct unbiased mutation and crossover operators, and we summarise those results.

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.

Abstract Since its inception, the "No Free Lunch" theorem (NFL) has concerned the application of symmetry results rather than the symmetries themselves. In our view, the conflation of result and application obscures the simplicity, generality, and power of the symmetries involved. This paper separates result from application, focusing on and clarifying the nature of underlying symmetries. The result is a general set-theoretic version of NFL which speaks to symmetries when arbitrary domains and co-domains are involved. Although our framework is deterministic, we note situations where our deterministic set-theoretic results speak nevertheless to stochastic algorithms.

In various nuances of evolutionary algorithms it has been observed that variable sized genomes exhibit large degrees of redundancy and corresponding undue growth. This phenomenon is commonly referred to as ldquobloat.rdquo The present contribution investigates the role of crossover operators as the cause for length changes in variable length genetic algorithms and linear GP. Three crossover operators are defined; each is tested with three different fitness functions. The aim of this article is to indicate suitable designs of crossover operators that allow efficient exploration of designs of solutions of a wide variety of sizes, while at the same time avoiding bloat.

A variety of phenomena such as world wide web, social or business interactions are modeled by various kinds of networks (such as the scale free or preferential attachment networks). However, due to the model-specific requirements one may want to rewire the network to optimize the communication among the various nodes while not overloading the number of channels (i.e. preserving the number edges). In the current paper we present a formal framework for this problem and a simple heuristic local search algorithm to cope with it. We estimate the expected single-step improvement of our algorithm, establish the ergodicity of the algorithm (i.e. that the algorithm never gets stuck at a local optima) with probability 1) and we also present a few initial empirical results for the scale free networks.

We investigate the effects of precision on the efficiency of various local search algorithms on 1-D unimodal functions. We present a (1+1)-EA with adaptive step size which finds the optimum in O(log n) steps, where n is the number of points used. We then consider binary and Gray representations with single bit mutations. The standard binary method does not guarantee locating the optimum, whereas using Gray code does so in O((log n)2) steps. A (1+1)-EA with a fixed mutation probability distribution is then presented which also runs in O((log n)2). Moreover, a recent result shows that this is optimal (up to some constant scaling factor), in that there exist unimodal functions for which a lower bound of Ω((log n)2) holds regardless of the choice of mutation distribution. Finally, we show that it is not possible for a black box algorithms to efficiently optimise unimodal functions for two or more dimensions (in terms of the precision used).

Proofs and empirical evidence are presented which show that a subset of algorithms can have identical performance over a subset of functions, even when the subset of functions is not closed under permutation. We refer to these as focused sets. In some cases focused sets correspond to the orbit of a permutation group; in other cases, the focused sets must be computed heuristically. In the smallest case, two algorithms can have identical performance over just two functions in a focused set. These results particularly exploit the case where search is limited to m steps, where m is significantly smaller than the size of the search space.

We analyze a simple random process in which a token is moved in the interval $A={0,dots,n$: Fix a probability distribution $mu$ over ${1,dots,n$. Initially, the token is placed in a random position in $A$. In round $t$, a random value $d$ is chosen according to $mu$. If the token is in position $ageq d$, then it is moved to position $a-d$. Otherwise it stays put. Let $T$ be the number of rounds until the token reaches position 0. We show tight bounds for the expectation of $T$ for the optimal distribution $mu$. More precisely, we show that $min_mu{E_mu(T)=Thetaleft((log n)^2 ight)$. For the proof, a novel potential function argument is introduced. The research is motivated by the problem of approximating the minimum of a continuous function over $[0,1]$ with a ``blind'' optimization strategy.

No abstract available.

The bacterium Escherichia coli has the capacity to respond to a wide range of environmental inputs, which have the potential to change suddenly and rapidly. Although the functions of many of its signal transduction and gene regulation networks have been identified, E.Coli's capacity for perceptual categorization, especially for discrimination between complex temporal patterns of chemical inputs, has been experimentally neglected. Real-time computations on time-varying inputs can be undertaken by a system possessing a high dimensional analog fading memory, i.e. a liquid-state machine (LSM). For example, the cortical microcolumn is hypothesized to be a LSM. A model of the gene regulation network (GRN) of E.Coli was assessed for its LSM properties for a range of increasingly complex stimuli. Cooperativity between transcription factors (TFs) is necessary for complex temporal discriminations. However, the low recurrence within the GRNs autonomous dynamics decreases its capacity for a rich fading memory, and hence for integrating temporal sequence information. We conclude that coupling of the GRN with signal transduction networks possessing cross-talk, and with metabolic networks is expected to increase the extent of non-autonomous recurrence and hence to facilitate enhanced LSM properties.

The frequency with which various elements of the search space of a given evolutionary algorithm are sampled is affected by the family of recombination (reproduction) operators. The original Geiringer theorem tells us the limiting frequency of occurrence of a given individual under repeated application of crossover alone for the classical genetic algorithm. Recently, Geiringer's theorem has been generalized to include the case of linear GP with homologous crossover (which can also be thought of as a variable length GA). In the current paper we prove a general theorem which tells us that under rather mild conditions on a given evolutionary algorithm, call it A, the stationary distribution of a certain Markov chain of populations in the absence of selection is unique and uniform. This theorem not only implies the already existing versions of Geiringer's theorem, but also provides a recipe of how to obtain similar facts for a rather wide class of evolutionary algorithms. The techniques which are used to prove this theorem involve a classical fact about random walks on a group and may allow us to compute and/or estimate the eigenvalues of the corresponding Markov transition matrix which is directly related to the rate of convergence towards the unique limiting distribution.

The particle swarm optimization algorithm has been shown to be a competitive heuristic to solve multi-objective optimization problems. Also, fitness sharing concepts have shown to be significant when used by multi-objective optimization methods. In this paper we introduce an algorithm that makes use of these two main concepts, particle swarm optimization and fitness sharing to tackle multi-objective optimization problems.

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.

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.

Representations are formalized as encodings that map the search space to the vertex set of a graph. We define the notion of bit equivalent encodings and show that for such encodings the corresponding Walsh coefficients are also conserved. We focus on Gray codes as particular types of encoding and present a review of properties related to the use of Gray codes. Gray codes are widely used in conjunction with genetic algorithms and bit-climbing algorithms for parameter optimization problems. We present new convergence proofs for a special class of unimodal functions; the proofs show that a steepest ascent bit climber using any reflected Gray code representation reaches the global optimum in a number of steps that is linear with respect to the encoding size. There are in fact many different Gray codes. Shifting is defined as a mechanism for dynamically switching from one Gray code representation to another in order to escape local optima. Theoretical results that substantially improve our understanding of the Gray codes and the shifting mechanism are presented. New proofs also shed light on the number of unique Gray code neighborhoods accessible via shifting and on how neighborhood structure changes during shifting. We show that shifting can improve the performance of both a local search algorithm as well as one of the best genetic algorithms currently available.

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.

We compare the behavior of a GA with and without crossover. A simple GA with crossover can have two stable fixed points (bistability) on the single-peak landscapes for string lengths at least 8. There are catastrophic transitions from one to two and back to one stable fixed point as the mutation rate increases. Crossover also causes the fixed-point population distribution to change. For a fixed point near the peak, there are fewer copies of the optimum string, more copies of near-optimum strings, and less copies of far-from-optimum strings. An example is given where average population fitness decreases to the minimum possible population fitness for the with-crossover GA, while the average population fitness increases for the without-crossover GA. The primary tool in obtaining these results is the Vose dynamical system model.

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.

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.

We define an abstract normed vector space where the genetic operators are elements. This is used to define the disturbance of the generational operator G as the distance between the crossover and mutation operator (combined) and the identity. This quantity appears in a bound on the variance of fixed-point populations, and in a bound on the force //v - G(v)// that applies to the optimal population v. When analyzed for the case of fixed-length binary strings, a connection is shown between these measures and the size of the search space. Guides for parameter settings are given, if population convergence is required as the string length tends to infinity.

Abstract (developmental) genetic representations are schemes where each genotype encodes a program for the construction of a phenotype. A new method for contriving abstract genetic representations is presented, based upon Kauffman's ideas regarding biological development [13-16]. Phenogenesis is controlled by genotype via cell replication and differentiation. Comparison is made with the earlier published methods of Gruau [9] and Kitano [18]. It is argued that greater expressive power is obtained using Kauffman networks. The new method was tested in the artificial evolution of morphology and finally successfully applied to the synthesis of structure in dynamical neural networks.