| 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 models, their analysis, and their empirical behavior are presented in detail. Moreover, there is new material on non-standard networked population structures such as small-world networks. The book should be of interest to advanced undergraduate and graduate students working in evolutionary computation, machine learning, and optimization. It should also be useful to researchers and professionals working in fields where the topological structures of populations and their evolution plays a role.
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. |