Genetic algorithms have largely been tailored towards optimisation problems with a fixed and well-defined search-space; the SAGA (Species Adaptation Genetic Algorithms) framework is introduced for the different domain of long term artificial evolution, where the task domain is ill-defined and can increase in complexity indefinitely. Genotypes should be able to increase in length indefinitely, and evolution will take place in a genetically converged population. Significant changes from normal genetic algorithm practice follow from this.
It is shown that changes in genotype length should be restricted to gradual ones. Appropriate mutation rates are proposed to encourage exploration of the high-dimensional fitness landscape without losing gains already made. Tournament selection, or similar ranking methods, are advocated as a way of maintaining selection pressures at a known rate. A crossover algorithm is introduced, which allows for recombination of genotypes of different lengths without undue confusion. The significance of a developmental process from genotype to phenotype, of co-evolution and of neutral drift through genotype space, are discussed.
As a class of control systems appropriate for evolution, programming languages are dismissed in favour of realtime dynamical recurrent connectionist networks; issues of time, representation and learning in such networks are discussed. A whole complex system, comprised of such a network together with sensory and motor systems, is characterised as a dynamical system with internal state, coupled to a dynamical environment.
Applications of these theoretical frameworks of artificial evolution and of control systems are demonstrated in a series of experiments with mobile robots engaged in navigational tasks using low-bandwidth sensors. Initial experiments are in simulation; the validity of such simulations and the significance of noise is discussed. Then experiments move to a real-world domain, with the use of a specialised piece of hardware which allows the automatic evaluation of populations of mobile robots using real low-bandwidth vision to navigate in a test environment. Evolution of capabilities is demonstrated in a sequence of navigational tasks of increasing complexity.