Spatially Structured Evolutionary Algorithms: Artificial Evolution in Space and Time

Evolutionary algorithms (EAs) is now a mature problem-solving family of heuristics that has found its way into many important real-life problems and into leading-edge scientific research. Spatially structured EAs have different properties than standard, mixing EAs. By virtue of the structured disposition of the population members they bring about new dynamical features that can be harnessed to solve difficult problems faster and more efficiently. This book describes the state of the art in spatially structured EAs by using graph concepts as a unifying theme…

The field of evolutionary computation (EC) can no longer be considered an esoteric one. Today, after about thirty years of research, a rich corpus of theory exists and many successful real-life applications are witnessing the usefulness of EC heuristics in many fields. EC is a family of population-based methodologies inspired by the interplay of natural selection and variation. However, both the theory and the applications have tended to focus mainly on mixing populations, also called panmictic populations. These are populations in which there is no particular structure: any member of the population is equally likely to “meet” any other member. But Darwin realized long ago that populations may have a spatial structure and that this spatial structure may have an influence on population dynamics. For instance, he remarked how, when they were isolated on islands, some species evolved differently from others that lived in more open environments. If we look around us, we too find that geographical separation factors have helped shape evolution. There are many examples, but one well-documented case is the spread of genomic traits in human populations due to geographical separation followed by migrations and mixing [29]. Also, as early as the 1960s, the book by MacArthur and Wilson [94] used models of geographical separation and migration to explain the spread and extinction of species. Thus, complete panmixia, although it can be achieved in the laboratory, appears only as a limiting case in nature, where spatial-separation effects seem to play an important role.