Seminars in Modena --- An Introduction to Evolutionary Computation

Course Overview

This short course will consist of eight 90-minute lectures in English. The first half of the course will be an introduction to the best-known methodologies in evolutionary computation: genetic algorithms, genetic programming, evolution strategies and evolutionary programming. In the second half of the course, I will describe some of my recent research in various theoretical areas of evolutionary computation. I will present results from work on fitness landscapes, genetic algorithms, crossover and artificial life. Source materials for these lectures can be found in the publications that are referenced below (all available as postscript).

If you plan to attend any or all of these lectures, you should keep an eye on this page. I will update it as I know more details of what I will cover. I will also add references and other information as the course proceeds.

The lectures will be conducted as informally as possible. However, I will expect attendees to be serious in their approach to and thinking about the course content. Questions will be welcome at any time, and we will have a short break in the middle of each lecture. Students with programming experience and access to computers will be encouraged to implement an evolutionary algorithm of their own.

If you have questions about the course content, please feel free to mail me. You can find some information on my research by following links from my home page. For details on my stay in Modena (course times and locations etc.), please contact David Lane (

Resources and Background Reading

A simple way to get a feel for the subjects covered in my lectures is to read about them on the web. Probably the best starting place (there are links to all sorts of things from here) is Mark Smucker's collection of materials concerning Evolutionary Computation and Artificial Life. You could also have a look at the The Santa Fe Institute's home page, especially their research pages.

Summary of Lecture Topics

  1. Introduction to Evolutionary Computation (10:30, Wednesday April 17, 1996)
  2. Genetic Algorithms (10:30, Thursday April 18, 1996)
  3. Genetic Programming (16:00, Friday April 19, 1996)

  4. Evolutionary Programming and Evolution Strategies (14:00, Monday April 22, 1996)
  5. Fitness Landscapes (10:30, Tuesday April 23, 1996)
  6. Fitness Distance Correlation (10:30, Wednesday April 24, 1996)

  7. Crossover, Macromutation and Population-based Search (14:00, Monday April 29, 1996)
  8. Artificial Life and Echo (10:30, Tuesday April 30, 1996)

Lecture 1:

Introduction to Evolutionary Computation

In the first lecture we will briefly touch on many aspects of the material that will be dealt with in depth in later lectures. Topics will include
Lecture 2:

Genetic Algorithms

This lecture will provide an introduction to genetics algorithms (GAs). We will examine the simple GA and discuss various extensions to this algorithm that have appeared over the years. Probably the most interesting and important of these, genetic programming, will be the subject of lecture 3.

I will touch on (at least) the following topics:

Almost certainly, I will have to provide some introduction to how I prefer to think about these algorithms (in terms of fitness landscapes created by representation, operator, fitness function and other choices). This will be the subject of lecture 5.

Lecture 3:

Genetic Programming

Genetic programming refers to a genetic algorithm that uses lisp S-expressions as data structures. The algorithm therefore explicitly operates on programs. Specially constructed crossover operators are used to maintain the grammatical validity of the S-expressions. This method, largely developed and promoted by John Koza (follow this link to tons of information), has achieved remarkable success on a wide range of test problems. It has been the subject of two (large) books and has recently been the subject of a lot of attention in the evolutionary computation community. After a description of the method, I will give an overview of results in genetic programming and lead a discussion about its merits.
Lecture 4:

Evolutionary Programming and Evolution Strategies

Evolutionary Programming is probably the oldest and, unfortunately, least-well-known of the family of evolutionary algorithms. In its original form, finite state automata were evolved via mutations that added states and transitions to the automata description. Later, and independently, evolutionary programming came to closely resemble evolution strategies. In very recent years, there has been a resurgence of interest in evolutionary programming, its connection with evolution strategies has been noticed and these methods (with GAs) form what we loosely call the evolutionary algorithms.

I will give some history of these approaches and describe how they are used. Also I will outline the situations in which these algorithms appear to be superior to GAs and discuss why and when we would expect this.

Lecture 5:

Fitness Landscapes

In this lecture, I will give an overview of a perspective on search algorithms (encompassing all the evolutionary algorithms) that I developed in my Ph.D. dissertation (follow that link for an abstract of the dissertation). The major component of this perspective is that of a "fitness landscape".

I will address topics such as

Lecture 6:

Fitness Distance Correlation

The material for this lecture will be based directly on a paper I presented at the 6th International Conference on Genetic Algorithms (July 1995). Here is a postscript copy of the paper. A measure of search difficulty, fitness distance correlation (FDC), will be introduced and examined in relation to genetic algorithm (GA) performance. In many cases, this correlation can be used to predict the performance of a GA on problems with known global maxima. It correctly classifies easy deceptive problems as easy and difficult non-deceptive problems as difficult, indicates when Gray coding will prove better than binary coding, and is consistent with the surprises encountered when GAs were used on the Tanese and royal road functions. The FDC measure is a consequence of an investigation into the connection between GAs and heuristic search.

Lecture 7:

Crossover, Macromutation and Population-based Search

The material for this lecture will be based directly on a paper I presented at the 6th International Conference on Genetic Algorithms (July 1995). Here is a postscript copy of the paper.

A major reason for the maintenance of a population in a Genetic Algorithm (GA) is the hope of increased performance via direct communication of information between individuals. This communication is achieved through the use of a crossover operator. If crossover is not a useful method for this exchange, the GA may not, on average, perform any better than a variety of simpler algorithms that are not population-based. I will present a simple method for testing the usefulness of crossover for a particular problem instance. This allows the identification of situations in which crossover is apparently useful but is actually only producing gains that could be obtained, or exceeded, with macromutation and no population.

Lecture 8:

Artificial Life and Echo

In the final lecture of the series, I will describe some of the more experimental approaches to evolutionary systems. The algorithms (a very loose use of the word) employed in these systems typically allow a far richer array of system behaviours. As a result, they are often more interesting and, of course, harder to understand.

One well-known artificial life project is John Holland's (the "father" of GAs) Echo system. Echo is a simulation tool developed to investigate mechanisms which regulate diversity and information-processing in systems comprised of many interacting adaptive agents, or complex adaptive systems (CAS). Echo agents interact via combat, mating and trade to develop strategies for ensuring survival in resource-limited environments. Individual genotypes are encodings of rules for interactions. In a typical simulation, populations of these genomes evolve complicated networks of interactions and resource flows. Resulting networks may be thought of as resembling species communities in ecological systems. Flexibly defined parameters and initial conditions enable researchers to conduct a range of what-if experiments.

I will give a reasonably thorough overview of Echo, talk about issues in the modeling of complex adaptive systems, and also discuss some research results on patterns of species abundance in Echo.

Terry Jones (terry <AT>