Reinterpreting no free lunch.

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.

Form invariance and implicit parallelism.

Holland's schema theorem (an inequality) may be viewed as an attempt to understand genetic search in terms of a coarse graining of the state space. Stephens and Waelbroeck developed that perspective, sharpening the schema theorem to an equality. Of particular interest is a "form invariance" of their equations; the form is unchanged by the degree of coarse graining. This paper establishes a similar form invariance for the more general model of Vose et al. and uses the attendant machinery as a springboard for an interpretation and discussion of implicit parallelism.

Patterns of parapatric speciation.

Geographic variation may ultimately lead to the splitting of a subdivided population into reproductively isolated units in spite of migration. Here, we consider how the waiting time until the first split and its location depend on different evolutionary factors including mutation, migration, random genetic drift, genetic architecture, and the geometric structure of the habitat. We perform large-scale, individual-based simulations using a simple model of reproductive isolation based on a classical view that reproductive isolation evolves as a by-product of genetic divergence. We show that rapid parapatric speciation on the time scale of a few hundred to a few thousand generations is plausible even when neighboring subpopulations exchange several individuals each generation. Divergent selection for local adaptation is not required for rapid speciation. Our results substantiates the claims that species with smaller range sizes (which are characterized by smaller local densities and reduced dispersal ability) should have higher speciation rates. If mutation rate is small, local abundances are low, or substantial genetic changes are required for reproductive isolation, then central populations should be the place where most splits take place. With high mutation rates, high local densities, or with moderate genetic changes sufficient for reproductive isolation, speciation events are expected to involve mainly peripheral populations.

Rapid parapatric speciation on holey adaptive landscapes.

A classical view of speciation is that reproductive isolation arises as a by-product of genetic divergence. Here, individual-based simulations are used to evaluate whether the mechanisms implied by this view may result in rapid speciation if the only source of genetic divergence are mutation and random genetic drift. Distinctive features of the simulations are the consideration of the complete process of speciation (from initiation until completion), and of a large number of loci, which was only one order of magnitude smaller than that of bacteria. It is demonstrated that rapid speciation on the time-scale of hundreds of generations is plausible without the need for extreme founder events, complete geographic isolation, the existence of distinct adaptive peaks or selection for local adaptation. The plausibility of speciation is enhanced by population subdivision. Simultaneous emergence of more than two new species from a subdivided population is highly probable. Numerical examples relevant to the theory of centrifugal speciation and to the conjectures about the fate of 'ring species' and 'sexual continuums' are presented.

The simple genetic algorithm and the Walsh transform: Part I, Theory.

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.

The simple genetic algorithm and the Walsh transform: Part II, The inverse.

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.