Preface: From Darwin to an ArtFlowers Garden

Evolution in nature, an outstanding example of natural adaptation processes at work, has resulted in a fantastic diversity of life-forms with amazing capabilities. Populations of organisms, adapting to their particular environmental conditions, form cooperating and competing teams in an evolutionary interplay of selection and variation mechanisms. The growth plans of organisms, encoded in the genomes of cells, vary from generation to generation. Finally those individuals will prevail that—largely because of their specific abilities and features —are best able to cope with their environmental conditions.

From these evolutionary principles of adaptation we can derive a number of concepts and strategies for solving learning tasks and develop optimization problems for artificially intelligent systems. Just as natural populations adapt to their environment by evolution, we can selectively modify problem-solving strategies, encode them as programs (e.g., as computer programs), and progressively adjust these programs to a predefined task representing a set of environmental constraints.

Illustrating Evolutionary Computation with Mathematica consists of an introduction and three major parts. The introduction demonstrates key aspects of evolution through simple yet illustrative examples. (I) The two main streams of evolutionary algorithms, genetic algorithms, and evolution strategies are thoroughly explained and are illustrated by example experiments. (II) Focusing on evolutionary programming and genetic programming, we explain how to automatically “breed” computer programs using principles of evolution. (III) Finally, we demonstrate and explore the close connections between developmental and evolutionary processes. We illustrate these concepts by looking at developmental programs found in nature, which we model and evolve in the form of cellular automata and Lindenmayer systems.

Introduction:The Fascination of Evolution

In the introduction we start with motivating and illustrative examples of evolution-based applications (Chapter 1): string matching by evolution, a simple optimization task; the adaptation of butterfly coloring through selection and mutation; and an example of evolutionary creativity using biomorph figures.

Part II Evolutionary Computation

In Part I, the classic schools of evolutionary algorithms for parameter optimization—genetic algorithms and evolution strategies—are presented. In Chapter 2, we start with a general overview of why evolutionary techniques provide flexible tools for solving real-worldoptimization problems.

In Chapter 3, we focus on (GA), where chromosomes are represented as strings or vectors over a discrete alphabet, analogous to nature’s encoding paradigm. Various types of GAchromosomes—haploid, diploid, and polyploid—and dominancerelations among alleles are explained. We continue with point mutations on various example chromosome structures. Recombinations of GA chromosomes, including meiotic recombination of doublestrands, are demonstrated by examples. Further operators, usuallyconsidered “secondary” operators, are discussed, including inversion, deletion, duplication, and crossing over of nonhomologous chromosomes. We show genetic algorithms in action by demonstrating theeffects of recombination versus mutation. Both operators are alsocompared to the effects caused by other GA operators. The genetic-algorithms’ ability to adapt to variable environmental constraints isshown for a typical parameter optimization task. The final section ongenetic algorithms illustrates a major building block of GA theory, theschema theorem, explaining its controversial mathematical background and potential in understanding the search behavior of genetic-algorithms.

Evolution strategies (ES), presented in Chapter 4, draw their main application area from engineering. Individuals are represented as vectors of real numbers on which various types of mutation and recombination operators are defined. The most important of these operator variants are discussed via a number of examples. Specific selection schemes have been developed for evolution strategy, which we will explain in detail and implement as Mathematica programs. On the basis of these developed programs, we explore the capabilities of evolution strategies to solve multimodal optimization tasks, including multipopulation ES and meta-evolution schemes.

Part II If Darwin Had Been a Programmer…

Whereas the two classic evolution-based algorithms—genetic algo-rithms and evolution strategies—primarily work with linear chromosomes, in the form of bit vectors or numbers, evolutionary programming (Chapter 6) and genetic programming (Chapter 7), introduced in Part II, are concerned with the evolution of finite-state automata and hierarchically structured computer programs, respectively. The idea of “breeding” programs through evolution is enormously fascinating and is already playing a growing role as an alternative method of computer programming. A brief history of approaches using evolutionary principles for the programming of computers is outlined in Chapter 5. Evolutionary programming, one of the first approaches to the application of evolutionary techniques to machine learning and to the automatic design of artificially intelligent systems, is presented in Chapter 6. Genetic programming in its original form, using terms (i.e., simple symbolic expressions) as the geno-typic structures undergoing evolution, is described in Chapter 7. Recombination and mutation operators on these terms are presented, and a simple application example of evolving balanced mobile structures is discussed in more detail. In Chapter 8, a more extended optimization example, the “breeding” of robot control programs, further illustrates the usefulness of the genetic programming approach.

Part III Evolution of Developmental Programs

Although the introduction and Parts I and II of this book focus on evolution at the level of populations, the spectrum of modeling evolutionary processes is extended in Part III.

In Chapter 9, we discuss simulations of pattern formation as observed for growth processes of cell configurations or plant structures. With the help of cellular automata (CA), we explore pattern formation in discrete spaces. Two-dimensional CAs are used to demonstrate the emergence of structures initiated by self-reproduction.

Natural morphogenesis and growth processes are modeled by parallel rewrite systems in the form of Lindenmayer systems (L-systems).

Analogous to genome programs of natural cells, L-systems make possible an implicit encoding of developmental processes. A so-called turtle interpretation of L-systems allows us to simulate and visualize the morphogenesis of plantlike structures through three-dimensional computer models.

Once the fitness of L-systems, encoding developmental programs, can be evaluated, an evolutionary selection scheme can be easily applied. By using genetic programming operators to produce mutations of L-system genomes, we arrive at a system for breeding development programs. Consequently, evolution is simulated on two separate levels: on the level of pattern formation (controlled by an individual genome program) and on the metalevel of populations, comprising competitive sets of developmental programs.

For a simple example of pattern formation with fractal structures, in Chapter 10 we show first results of our approach to evolutionary inference of L-systems. Much more complex L-systems have to be designed for modeling growth, structure formation, and inflorescencesof plants. In Chapter 11, examples of such developmental programsshow how implicit evaluation of the pattern formation processes leadsto evolution-based strategies and concepts for the breeding of virtual plants. In addition to an amazing variety of evolvable plant structures, modifications of genome programs result in a number of mutation effects on the expressed individual plants that can be observed in natural breeding experiments. Finally, we illustrate coevolutionary effects in a plant ecosystem through interactions of multiple individual plants.

Mathematica and Evolvica

This book does not introduce Mathematica as a programming tool. Many of the evolutionary algorithm concepts, however, are illustrated using the Mathematica programming language. Evolvica1 is used to illustrate algorithms, to visualize evolutionary concepts, and to demonstrate evolution-based solutions of optimization tasks by hands-on examples. All of the Evolvica example...