– EVOLVICA –

Illustrating Evolutionary Computation

with Mathematica

© Christian Jacob

Department of Computer Science
The University of Calgary
CANADA

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

Morgan Kaufmann Publishers
San Francisco, CA
2001

See the flower grow  ...

– EVOLVICA –

Keywords

Evolutionary algorithms, evolution strategies, genetic algorithms, genetic programming, cellular automata, Lindenmayer systems, evolution and co-evolution of developmental systems, models of competition and cooperation, complex adaptive systems, agent-based evolutionary computation

Table of Contents

Fascinating Evolution: Introductory Examples

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

.	Cumulative Selection: "Me thinks it is like a weasel …"

.  Mimesis: Evolution of Butterfly Mimicry

.	Evolutionary Creativity: Biomorphs

Evolutionary Algorithms for Optimization

In this section, we give a short introduction to adaptive systems, to the preconditions of evolution, and to evolution as adaptive systems. Finally, a basic scheme for evolutionary algorithms is presented.

.	Adaptive Systems and Evolution

.	Preconditions for Evolution to Occur

.	Evolution as a Reproductive Plan

GA: Genetic Algorithms

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

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

.	Polyploid GA-Chromosomes

Haploid Chromosomes

s = ((Subscript[s, 1]),  ... , (Subscript[s, n])) with (Subscript[s, i]) ∈ A, 
    1 ≤ i ≤ n,

Diploid Chromosomes and Dominance

.	Point-Mutation on GA-Chromosomes

Mutation on Haploid Chromosomes

((Subscript[s, i])^′)={({{s ∈ 
                  A - {(Subscript[s, i])}, if (Subscript[χ, [0, 1]]) ≤ 
                  (Subscript[p, m])}, {(Subscript[s, i]), otherwise}})}.

Mutation on Diploid Chromosomes

Mutation on RNA-Chromosomes

Mutation with Faces

.	Recombinations of GA Chromosomes

Recombination on GA-Chromosomes

Meiotic Recombination with diploid Chromosomes

Recombination with Faces

.	Further Genetic Operators

Inversion

Deletion

Duplication

Crossover between non-homologous Chromosomes

.	Selection

.	Evolution Schemes

.	Genetic Algorithms in Action

Visualizing the Genotypes (binary alphabet)

Visualizing the Genotypes (m-ary alphabet)

Mutation versus Recombination

Comparison of Genetic Operators (Summary)

GA-Evolution with Changing Environments

.	Schemata

Patterns describing genotypic building blocks

Schematheorem

Schemata Experiments

ES: Evolution Strategies

In this chapter we will explore another major school of evolutionary algorithms: Evolution Strategies (ES).

.	ES-Introduction

.	ES-Chromosomes

.	ES-Mutations

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

ES-mutations and selection: The basic idea

Mutating object parameters

Stepsize adaptation

.	ES-Recombinations

Introduction

Discrete and intermediate recombination

Local and global recombinations

Examples

.	ES-Selection and Evolution Scheme

Introduction

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

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

Meta-Evolution Strategies

.	Evolution Strategies in Action

Introduction

Multi-modal parameter optimization

Three competing sub-populations on their way up …

Discovering all maxima: ■ Part1, ■ Part 2, ■ Part 3

Programming by Evolution

There are no notebooks available for Chapter 5 in the book..

EP: Evolutionary Programming

.	 Evolution of Finite State Automata

GP: Genetic Programming

In this chapter we explore the "automatic programming" of computers by evolution. We start with a brief history of evolutionary programming by presenting approaches of how to use evolution mechanisms to "breed" computer programs. The genetic programming approach, where terms or simple symbolic expressions are used to encode data structures, is discussed in more detail and demonstrated by example of evolving balanced mobiles. Finally, further variants of genetic programming are outlined.

.	GP with Tree Genomes: Introduction

.	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

Evolvica – Evolution with Symbolic Expressions

This chapter describes the genetic programming system Evolvica and its concepts using symbolic expressions and template- or pattern-based genetic operators.

.	Templates defining Building Blocks

Generating Expressions over Templates

Expression Generation with Weighted Templates

.	Templates as Filters – Extraction of Contextsensitive Substructures

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

.	Evolving AntTrackers

Experiment Setup

Analysis of an evolution experiment

Computer Models of Developmental Programs

In this chapter we discuss cellular automata (CA) and the evolution of CA rules by means of genetic programming. Lindenmayer-systems are introduced as an alternative way of describing structure formation processes. We also demonstrate how genetic programming can be used to evolve and design L-systems that exhibit certain characteristics.

.	Cellular Automata

Pattern formation in one dimension

Morphogenesis and selfreproduction

Mutation and selfreproduction

.	Lindenmayer-Systems

Modeling growth with L-systems

Turtle - Interpretation : Describing structures in 3D space

Bracketed L-Systems: Modeling branching structures

Unfolding of parametrized fractal structures

Evolutionary Inference of L-Systems

.	 Evolution of Fractal Structures

Evolving 2D Fractal Structures

Artificial Plant Evolution

.	Genetic L-System Programming

L-Systems for Plantlike Structures

Growth Modeling of Lychnis coronaria

Breeding ArtFlowers

.	 Evolution of Plant Ecosystems

Setting the EVOLVICA Directory ...

In case you want to try out the implemented Evolvica functions, some of the Evolvica notebooks require the definition of the directory where THIS NOTEBOOK resides in.

Please enter the directory path of this notebook (IEC-Evolvica.nb) here:

Below are examples of how to set the directory path under different operating systems:

For Macintosh or Unix Systems:

\(EvolvicaDirectory = 
      ToFileName[{"", "Cube OS X", "Users", "jacob", "Documents", "EVOLvica"}, "EvolvicaNotebooks"]\)

For Windows Systems:

\(EvolvicaDirectory = 
      ToFileName[{"", "C:", "My Documents", "Summer CPSC", "Evolvica", "EvolvicaNotebooks"}, "EvolvicaNotebooks"]\)

While the cursor is still in the above cell, evaluate the cell by hitting SHIFT-RETURN or select Kernel -> Evaluation -> Evalute Cells from the menu.

Do the same with the following cell. If you do not get an error message (such as "Cannot set current directory ...") your Evolvica directory has been set successfully.

SetDirectory[EvolvicaDirectory]

Note: It is assumed that you did not change the recommended Evolvica directory structure, i.e., you haven't altered the directory hierarchy of the notebooks you downloaded from the IEC website.