Seminars in Modena --- An Introduction to Evolutionary Computation

Course Overview

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 (lane@unimo.it).

Resources and Background Reading

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)

• The biological inspiration for these algorithms.
• The history of these algorithms.
• What it means for an algorithm to be "evolutionary" or "adaptive".
• How these algorithms can be viewed as search or optimization algorithms.
• How these algorithms can be examined from a statistical point of view.
• How necessary it is to maintain the biological metaphor.

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

• Fitness functions.
• Crossover (one-point, two-point, multi-point, uniform, etc.).
• Mutation.
• The relative importance of crossover and mutation.
• Selection methods (roulette wheel, tournament etc.).
• Fitness scaling.
• Elitism.
• Representation.
• Implicit parallelism, schema processing and the schema theorem.

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.

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.

I will address topics such as

• What is (formally and informally) a fitness landscape?
• Historical uses of fitness landscapes.
• How we can define fitness landscapes for operators other than mutation. This will be the subject of lecture 7 when we look at what I call "crossover landscapes".
• Is it useful to think in terms of fitness landscapes?
• Statistical approaches to the study of fitness landscapes.
• What (qualitatively and quantitatively) makes a fitness landscape difficult (or easy) to search? These two questions will be the subject of lecture 6.

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.

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.

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.