We extend previous results concerning black box search algorithms, presenting new theoretical tools related to no free lunch (NFL) where functions are restricted to some benchmark (that need not be permutation closed), algorithms are restricted to some collection (that need not be permutation closed) or limited to some number of steps, or the performance measure is given. Minimax distinctions are considered from a geometric perspective, and basic results on performance matching are also presented.

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.

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.

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.

This paper is the first part of a two-part series. It proves a number of direct relationships between the Fourier transform and the simple genetic algorithm. (For a binary representation, the Walsh transform is the Fourier transform). The results are of a theoretical nature and are based on the analysis of mutation and crossover. The Fourier transform of the mixing matrix is shown to be sparse. An explicit formula is given for the spectrum of the differential of the mixing transformation. By using the Fourier representation and the fast Fourier transform, one generation of the infinite population simple genetic algorithm can be computed in time O(cllog2(3)), where c is arity of the alphabet and l is the string length. This is in contrast to the time of O(c3l) for the algorithm as represented in the standard basis. There are two orthogonal decompositions of population space that are invariant under mixing. The sequel to this paper will apply the basic theoretical results obtained here to inverse problems and asymptotic behavior.

This paper continues the development, begun in Part I, of the relationship between the simple genetic algorithm and the Walsh transform. The mixing scheme (comprised of crossover and mutation) is essentially "triangularized" when expressed in terms of the Walsh basis. This leads to a formulation of the inverse of the expected next generation operator. The fixed points of the mixing scheme are also determined, and a formula is obtained giving the fixed point corresponding to any starting population. Geiringer's theorem follows from these results in the special case corresponding to zero mutation.

A complete generalization of the Vose genetic algorithm model from the binary to higher cardinality case is provided. Boolean AND and EXCLUSIVE-OR operators are replaced by multiplication and addition over rings of integers. Walsh matrices are generalized with finite Fourier transforms for higher cardinality usage. Comparison of results to the binary case are provided.

This paper speaks to the inherent emergent behavior of genetic search. For completeness and generality, a class of stochastic search algorithms, random heuristic search, is reviewed. A general convergence theorem for this class is then proved. Since the simple genetic algorithm (GA) is an instance of random heuristic search, a corollary is a result concerning GAs and time to convergence.

The infinite- and finite-population models of the simple genetic algorithm are extended and unified, The result incorporates both transient and asymptotic GA behavior. This leads to an interpretation of genetic search that partially explains population trajectories. In particular, the asymptotic behavior of the large-population simple genetic algorithm is analyzed.

The infinite population simple genetic algorithm is a discrete dynamical system model of a genetic algorithm. It is conjectured that trajectories in the model always converge to fixed points. This paper shows that an arbitrarily small perturbation of the fitness will result in a model with a finite number of fixed points. Moreover, every sufficiently small perturbation of fimess preserves the finiteness of the fixed point set. These results allow proofs and constructions that require finiteness of the fixed point set. For example, applying the stable manifold theorem to a fixed point requires the hyperbolicity of the differential of the transition map of the genetic algorithm, which requires (among other things) that the fixed point be isolated.

The original schema theorem (an inequality) has been replaced by an equality that determines the expected next generation for a simple genetic algorithm. This has made possible the computation of the trajectory of expected next generations. Visualization of these evolutionary trajectories beginning from different initial populations has led to the discovery of fractal structures.

A general form of stochastic search is described (random heuristic search), and some of its general properties are proved. This provides a framework in which the simple genetic algorithm (SGA) is a special case. The framework is used to illuminate relationships between seemingly different probabilistic perspectives of SGA behavior. Next, the SGA is formalized as an instance of random heuristic search. The formalization then used to show expected population fitness is a Lyapunov function in the infinite population model when mutation is zero and fitness is linear. In particular, the infinite population algorithm must converge, and average population fitness increases from one generation to the next. The consequence for a finite population SGA is that the expected population fitness increases from one generation to the next. Moreover, the only stable fixed point of the expected next population operator corresponds to the population consisting entirely of the optimal string. This result is then extended by way of a perturbation argument to allow nonzero mutation.

Let xi be a random variable over a finite set with an arbitrary probability distribution. Improvements to a fast method of generating sample values for xi in constant time are suggested. The proposed modification reduces the time required for initialization to O(n). For a simple genetic algorithm, this improvement changes an O(g n 1n n) algorithm into an O(g n) algorithm (where g is the number of generations, and n is the population size).>

Functions are partially characterized as easy or hard for genetic algorithms to optimize. The failure modes of inappropriate embedding, crossover disruption, and deceptiveness are introduced, analyzed, and resolved in part. Virtually all optimizable (by any method) real valued functions defined on a finite domain are shown to be theoretically easy for genetic algorithms given appropriately chosen representations. Unfortunately, problems that are easy in theory can be difficult in practice because of sampling error. Also, the transformations required to induce favorable representations are generally arbitrary permutations, and the space of permutations is so large that search for good ones is intractable. The space of inversions is amenable to search, but inversions are insufficiently powerful to overcome deceptiveness. On the other hand, affine transformations (over the diadic group) are shown to be sufficiently powerful to transform at least selected deceptive problems into easy ones. These new results should be useful in guiding empirical studies and are expected to provide a foundation for further theoretical analysis.