No free lunch and benchmarks.

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.

Representation invariant genetic operators.

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

Case studies and mathematical models of ecological speciation. 4. Hybrid speciation in butterflies in a jungle.

We build a spatial individual-based multilocus model of homoploid hybrid speciation tailored for a tentative case of hybrid origin of Heliconius heurippa from H. melpomene and H. cydno in South America. Our model attempts to account for empirical patterns and data on genetic incompatibility, mating preferences and selection by predation (both based on coloration patterns), habitat preference, and local adaptation for all three Heliconius species. Using this model, we study the likelihood of recombinational speciation and identify the effects of various ecological and genetic parameters on the dynamics, patterns, and consequences of hybrid ecological speciation. Overall, our model supports the possibility of hybrid origin of H. heurippa under certain conditions. The most plausible scenario would include hybridization between H. melpomene and H. cydno in an area geographically isolated from the rest of both parental species with subsequent long-lasting geographic isolation of the new hybrid species, followed by changes in the species ranges, the secondary contact, and disappearance of H. melpomene-type ecomorph in the hybrid species. However, much more work (both empirical and theoretical) is necessary to be able to make more definite conclusions on the importance of homoploid hybrid speciation in animals.

Dynamics of alliance formation and the egalitarian revolution.

BACKGROUND: Arguably the most influential force in human history is the formation of social coalitions and alliances (i.e., long-lasting coalitions) and their impact on individual power. Understanding the dynamics of alliance formation and its consequences for biological, social, and cultural evolution is a formidable theoretical challenge. In most great ape species, coalitions occur at individual and group levels and among both kin and non-kin. Nonetheless, ape societies remain essentially hierarchical, and coalitions rarely weaken social inequality. In contrast, human hunter-gatherers show a remarkable tendency to egalitarianism, and human coalitions and alliances occur not only among individuals and groups, but also among groups of groups. These observations suggest that the evolutionary dynamics of human coalitions can only be understood in the context of social networks and cognitive evolution. METHODOLOGY/PRINCIPAL FINDINGS: Here, we develop a stochastic model describing the emergence of networks of allies resulting from within-group competition for status or mates between individuals utilizing dyadic information. The model shows that alliances often emerge in a phase transition-like fashion if the group size, awareness, aggressiveness, and persuasiveness of individuals are large and the decay rate of individual affinities is small. With cultural inheritance of social networks, a single leveling alliance including all group members can emerge in several generations. CONCLUSIONS/SIGNIFICANCE: We propose a simple and flexible theoretical approach for studying the dynamics of alliance emergence applicable where game-theoretic methods are not practical. Our approach is both scalable and expandable. It is scalable in that it can be generalized to larger groups, or groups of groups. It is expandable in that it allows for inclusion of additional factors such as behavioral, genetic, social, and cultural features. Our results suggest that a rapid transition from a hierarchical society of great apes to an egalitarian society of hunter-gatherers (often referred to as "egalitarian revolution") could indeed follow an increase in human cognitive abilities. The establishment of stable group-wide egalitarian alliances creates conditions promoting the origin of cultural norms favoring the group interests over those of individuals.

A heuristic technique for CTIS image reconstruction.

An iterative method is presented for computed tomography imaging spectrometer (CTIS) image reconstruction in the presence of both photon noise in the image and postdetection Gaussian system noise. The new algorithm, which assumes the transfer matrix of the system has a particular structure, is evaluated experimentally with the result that it is significantly better, for larger problems, than both the multiplicative algebraic reconstruction technique (MART) and the mixed-expectation image-reconstruction technique (MERT) with respect to accuracy and computation time.

State aggregation and population dynamics in linear systems.

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

Structural search spaces and genetic operators.

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

Group properties of crossover and mutation.

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