Evolutionary Algorithms with Mathematica

Christian Jacob

jacob@cpsc.ucalgary.ca

Dept. of Computer Science
The University of Calgary
CANADA

About this Tutorial

The material you will be directed to in the following sections is our first step towards a hypertext tutorial on Evolutionary Algorithms, i.e., on Evolution Strategies, Genetic Algorithms, Genetic Programming, Cellular Automata, Lindenmayer Systems, and the Evolution of L-Systems. All the chapters are set up as Mathematica notebooks that provide interactive hypertext documents including graphics, animations (movies), text, formulas and Mathematica programming examples.

Hyperlinks are marked as underlined text and will bring you to either another location within the current notebook, open a new notebook or open your web browser to follow an http web link.

If you do not have access to Mathematica then you need to install MathReader which is a freely available viewer program to read Mathematica notebooks. The only restriction of MathReader is that you will not be able to execute any Mathematica program code on your own. But, as you will see in the following chapters, the notebooks contain all input and output of the programming examples, so that you will get to know how the presented programs work even without being able to make your own programming experiences. However, everything else, especially hyperlinking or playing the animations will work fine with MathReader. For more details, please see the section about Mathematica below.

The full collection of the tutorial notebooks about Evolutionary Algorithms with Mathematica can be downloaded from the Evolvica web site:

http://www.cpsc.ucalgary.ca/~jacob/Evolvica

From here you will be directed to all the tutorial material currently available, and you will find a few Java applications of Evolutionary Algorithms as well.

About Mathematica …

Mathematica is a computer algebra and programming system developed by Wolfram Research, Inc. In this tutorial we will make extensive use of Mathematica´s programming language as well as the capabilities of the latest release of Mathematica 3.0 to set up hypertext documents. The notebooks presented in this tutorial have been written with Mathematica 3.0, so it is essential to use this latest version of either Mathematica or MathReader to get the most out of it.

However, all the programs explained and used to generate the various evolution examples will run under Mathematica 2.2 versions as well. Actually, all the programs have been written some time before the first release of Mathematica 3.0.

Where to get MathReader

Even if you do not have access to Mathematica up to now you can read all the notebooks with a little helper application called MathReader. This viewer for Mathematica notebooks is either available from Wolfram Research or you may download your personal copy from the following web pages:

MathReader for the Macintosh: 
http://www.wolfram.com/mathreader/macintosh.html

MathReader (Version 2.2) for Windows:
http://www.mathsource.com/cgi-bin/MathSource/General/MathReader/0204-972

MathReader for Windows 95:
http://www.wolfram.com/mathreader/windows95.html

MathReader for SunSPARC:
http://www.wolfram.com/mathematica/MathReader/unix.html

MathReader (Version 2.2) for the X Window System:
http://www.mathsource.com/cgi-bin/MathSource/General/MathReader/0207-177

For more detailed information about Mathematica you should visit the Wolfram Research web site at http://www.wolfram.com.

Outline

Evolution in nature provides fascinating mechanisms for adapting living species to their environments. It is somewhat remarkable that such complex adaptations, taking place over huge time spans (from hundreds to millions of years) are essentially driven by a strikingly simple principle: iterated selection and mutation, as originally formulated by Charles Darwin (Darwin 1859).

All organisms that are able to reproduce, thus transmitting their specific genes to their descendants, have won nature´s implicit »struggle-of-survival« test. The genes are passed on to the next generation, however, with some minor mutations, either due to imperfect copying of the genetic information or due to recombination effects observable among sexually reproducing individuals.

Trying to integrate evolution into algorithmic schemes, is just what many researchers, propagating the field known today as »evolutionary computation« (EC), have been doing for quite a long time (see, e.g., Holland 1975 and Rechenberg 1973). Consequently, many different versions and applications of evolutionary algorithms (EAs) have been developed, most of them belonging to one of three major EA-classes, we will focus on in the sequel of this tutorial:

• Evolution Strategies (ES),
• Genetic Algorithms (GA), and
• Genetic Programming (GP).

However, we will extend the notion of Evolutionary Algorithms a little further, namely from adaptation schemes of populations within their specific environment to development programs of individual organisms. Thus we also consider algorithmic models describing growth processes, structure formation or morphogenesis to fit well into the context of evolutionary algorithms.

In this tutorial we have currently included two of the major classes of evolutionary algorithms on the level of individuals:

• Cellular Automata, which might as well be considered as belonging to the first class of populational EAs, and

• Lindenmayer systems (L-systems), which play an important role in the simulation of morphogenetic processes (especially in the domain of natural plants).

In one of the last sections we will also discuss some first steps towards evolving or breeding of L-systems that encode plantlike structures.

Table of Contents

Fascinating Evolution: Introductory Examples

This chapter demonstrates one of the fundamental principles of evolution: iterated selection and mutation by severalsimple, but yet – hopefully – convincing examples.

Cumulative Selection: »Me thinks it is like a weasel …«

How can iterated selection and mutation help in finding a predefined sequence of characters?

Mimesis: Evolution of Butterfly Mimicry

Butterflies sitting on barks of trees can adapt their wing colours to their preferred environments. A simple simulation shows how this adaptation can be achieved through evolution.

Evolutionary Creativity: Biomorphs

On the basis of »biomorphs«, simple recursive line figures first introduced by R. Dawkins to discuss evolutionary principles, we exemplify the creativity of interactive, open-ended evolution.

Evolution Strategies (ES)

In this chapter we will explore one of the major paradigms of evolutionary algorithms: Evolution Strategies (ES).

ES-Introduction

This section gives a brief introduction to Evolution Strategies, about their origins, their primary characteristics with regard to »chromosomes«, »genetic operators«, selection schemes, and preferred application areas.

ES-Chromosomes

Here we explain the data structures we will use to represent ES-chromosomes in Mathematica and how we implement them. Basically, an ES-chromosome (Overscript[g, ⇀]) is defined as a two-fold vector of the form

(Overscript[g, ⇀]) = ((Overscript[p, ⇀]), (Overscript[s, ⇀])) = (((Subscript[p, 1]), (Subscript[p, 2]), …, (Subscript[p, n])), ((Subscript[s, 1]), (Subscript[s, 2]), …, (Subscript[s, n]))) with (Subscript[p, i]),  (Subscript[s, i])  ∈  ℝ,

where (Overscript[p,  ⇀])  and (Overscript[s,  ⇀])  represent the object and strategy parameters, respectively.

ES-Mutations

Mutation is considered the major ES-operator for variations on the chromosomes.
Mutations of the object and strategy parameters are accomplished in different ways. Basically, ES-mutation on a chromosome \(TraditionalForm
      \`g\&⇀ = \((p\&⇀, \ s\&⇀)\)\) can be described as follows:

(Subscript[(Overscript[g, ⇀]), mut]) = ((Overscript[p, ⇀])+(Subscript[N, 0])((Overscript[s, ⇀])), α((Overscript[s, ⇀]))).

Here (Subscript[N, 0]) denotes normal distribution with mean zero, and α defines a function for adapting the strategy parameters.

ES-mutations and selection: The basic idea

What are the main characteristics of the ES-mutation-selection scheme?

Mutating object parameters

How does mutation performed on object parameters work? What are the most commonly used mutations?

Stepsize adaptation

How can the variances that control mutation step sizes be tuned to better evolutionary performance?

ES-Recombinations

Recombination operators compose new chromosomes from according parts of two or more chromosomes, thus mimicking natural recombination mechanisms observed on cellular genomes. For the binary case, where two ES-chromosomes, \(TraditionalForm
      \`a\&⇀ = 
        \((p\&⇀\_a, s\&⇀\_a)\)\) and \(TraditionalForm
      \`b\&⇀ = 
        \((p\&⇀\_b, s\&⇀\_b)\)\), are to be recombined by an operator (Subscript[ω, rec]) we can describe the composition of a new chromosome ω´ as follows:

ω´=(Subscript[ω, rec])((Overscript[a, ⇀]), 
            (Overscript[b, ⇀]))=\(\((\(p\&⇀\) ´, \(s\&⇀\) ´)\) = 
            \((\((p\_1\^′, …, p\_n\^′)\), 
              \((s\_1\^′, …, s\_n\^′)\))\)\).

Each element of the object and strategy parameter vectors is a recombination of the respective entries of (Overscript[a, ⇀]) and (Overscript[b, ⇀]):

((Subscript[p, i])^′) = (Subscript[ρ, p])((Subscript[p, ai]), (Subscript[p, bi])) and \(TraditionalForm
      \`\(\(s\_i\^′ = \(ρ\_s\)(s\_ai, s\_bi))\).\)\)

Here the functions (Subscript[ρ, p]) and (Subscript[ρ, s]) define the component-wise recombinations for the object and strategy parameters, respectively.

The following sections about ES-recombinations will discuss these functions for discrete and intermediate recombinations as well as different combination schemes (local and global), and will finally extend the binary case to multi-recombinations among more than two chromosomes.

Discrete and intermediate recombination

Some commonly used recombination mappings on the »genes« of ES-chromosomes are explained.

Local and global recombinations

Constraints on the domain of the recombination operators lead to quite different effects with regard to mixing of genetic information.

Examples

Further examples show the great variety of the discussed recombination schemes.

ES-Selection and Evolution Scheme

In this section we will discuss several variants of evolutionary schemes as defined in the context of Evolution Strategies. Here you will find explanations of the formal ES-notation that turns out to be quite flexible in characterizing different evolution processes (including GAs and GP). All of these ES-evolution models are further illustrated with the help of a graphical notation.

Introduction

Here we present a graphical notation used to explain the basic algorithmic schemes of Evolution Strategies.

(μ+λ)-ES and (μ, λ)-ES

Starting from the most simple (1+1)-Evolution Strategy with one parent producing a single offspring, the selection-mutation scheme is extended to more general Plus- and Comma-schemes with μ parents (possibly) competing with λ mutated offspring.

(μ / ρ \(TraditionalForm\`\(\(, \&+\)\ \)\)λ)-ES: Evolution Strategy and Recombination

Extending the set of ES-operators by recombination leads to the ES-schemes discussed in this section.

Meta-Evolution Strategies

Independently evolving subpopulations that, from time to time, exchange »genetic material« and compete against one another for resources act as evolving meta-individuals.

Evolution Strategies in Action

Exploring the basic dynamics of evolutionary processes as defined by Evolution Strategies is the main topic of this section. ES-schemes will be used to solve parameter optimization problems within multi-modal domains. Two simple examples will demonstrate how Evolution Strategies can be used to search for global maxima. First, it will be shown how three populations independently evolve to areas of better fitness; finally, an example for meta-evolution on subpopulations is presented.

The following ES experiments are conducted as parameter optimizations within a two-dimensional, multi-modal objective function. The task is to find the location of the global maximum.

Multi-modal parameter optimization

We compare three evolution runs according to a (10 / 2,  20)-ES in search of a global maximum.

Three competing sub-populations on their way up …

An experiment according to a (((3 + 3 (((10/2 + 5))^5)))^5)-ES demonstrates the power of meta-evolutions.

Discovering all maxima … 
(Part1, Part 2, Part 3)

Three independent populations step by step will find their way to the top three locations overlooking the »mountain region«.

Concluding Remarks and Further References

Genetic Algorithms (GA)

In this chapter we will explore another major paradigm of evolutionary algorithms: Genetic Algorithms (GAs). We will have a look at various kinds of GA chromosome structures, their main genetic operators, the basic evolution scheme, and on some GA-evolution experiments in the domain of parameter optimization.

Finally, this chapter on Genetic Algorithms concludes with a brief discussion of GA-building blocks, the Schema Theorem, and a few experiments on GA-schemata.

GA-Introduction

This section gives a brief overview of Genetic Algorithms, about their origins, their primary characteristics with regard to chromosomes, genetic operators, and selection schemes.

Polyploid GA-Chromosomes

Haploid Chromosomes

Diploid Chromosomes and Dominance

The interpretation of double-stranded chromosomes rises the question of which of two competing alleles should be expressed in the phenotype.

Point-Mutation on GA-Chromosomes

Mutation on haploid Chromosomes

Mutation on polyploid Chromosomes

Mutation on RNA-Chromosomes

On the basis of rule-based programming we show a simple simulation of the translation process from RNA-nucleotide bases to amino acids.

Mutation with Faces

GA-Recombination

Recombination on Lists

Recombination on GA-Chromosomes

Meiotic Recombination with diploid Chromosomes

Recombination with Faces

Further Genetic Operators

Inversion

Deletion

Duplication

Crossover between non-homologous Chromosomes

Selection and Evolution Scheme

Genetic Algorithms in Action

Visualizing the Genotypes

Decoding

Mutation versus Recombination

A visual comparison of a pure selection-mutation scheme versus a selection-recombination scheme reveals the main characteristics of mutating and recombining genetic operators.

Comparison of Genetic Operators

GA-Evolution with Changing Environment

Part 1: Ascent to higher regions

Part 2: Reaction on change of the objective function

Part 3: Continued evolution with Comma-GA-Strategy

Part 4: Finally, Plus-GA-Strategy again

Schemata

Patterns describing genotypic building blocks

Schematheorem

Experiments

Concluding Remarks and Further References

Genetic Programming (GP)

Terms as Genotypic Structures

Recombination on Terms

Mutation on Terms

GP-Evolutionscheme

GP in Action: Evolving Balanced Mobiles

Mobiles: Encoding, visualization, and evaluation

GP-evolution of balanced mobiles

Concluding Remarks and Further References

Evolvica – Evolution with Symbolic Expressions

Templates defining Building Blocks

Generating Expressions over Templates

Expression Generation with Weighted Templates

Templates as Filters – Contextsensitive Substructure Identification

Templates identifying substructures

Hierarchical extraction of substructures

Embedded structures within structures

Selective Genetic Operators

Mutation

Recombination

Duplication

Deletion

Permutation and Inversion

Encapsulation and Decapsulation

Pattern extraction

Evolutionscheme

Evolving AntTrackers

Experiment setup

Analysis of an evolution experiment

Concluding Remarks and Further References

Evolution Programs

Cellular Automata

Pattern formation in one dimension

Morphogenesis and selfreproduction

Mutation and selfreproduction

Lindenmayer-Systems

Modeling growth with L-systems

Lindenmayer systems are used to model elementary growth processes like cell divisions within a cellular layer. This section also serves as an introduction to the basic concepts of L-systems and their variants, from deterministic, context-free to parametrized, stochastic and context-sensitive L-systems.

Turtle-Interpretation – Describing structures in 3D space

Bracketed L-Systems: Modeling branching structures

Unfolding of parametrized fractal structures

Genetic L-System Programming

L-Systems for Plantlike Structures

A few examples of Lindenmayer systems that encode growth programs for plants are presented here. The L-systems used here heavily rely on turtle interpretations.

Breeding ArtFlowers

L-systems, encoded as symbolic expressions are subject to evolution on the basis of Genetic Programming. Some first GLP-examples use L-systems that describe structure formations of plants.

Concluding Remarks and Further References

References

Web Site

http://www.cpsc.ucalgary.ca/~jacob

jacob@cpsc.ucalgary.ca