• Contribute
• What's New
• Submit News

Melanie Mitchell received a Ph.D. in Computer Science from the University of Michigan in 1990. Her dissertation work with Douglas Hofstadter was on cognitive modeling of high-level perception and analogy-making. In 1990 she was awarded a Junior Fellowship in the University of Michigan Society of Fellows, with a two-year joint appointment as an Assistant Professor in the Electrical Engineering and Computer Science Department at the University of Michigan. From 1992 to 1999 she was Research Professor at the Santa Fe Institute, and directed the Institute's program in Adaptive Computation. She is currently a Staff Member in the Biophysics Group at the Los Alamos National Laboratory, and a member of the external faculty of the Santa Fe Institute.

Mitchell is also the author of the excellent book, An Introduction to Genetic Algorithms.

I attended the University of Michigan for graduate school in computer science. I went there to work with Douglas Hofstadter on computer modeling of analogy-making. John Holland was a professor in that department, and I took his course on genetic algorithms and other topics. It was fascinating and I got hooked. I started attending the meetings of his graduate seminar. One of his students, Reiko Tanese, was working on a thesis on GAs and had some rather puzzling results. Stephanie Forrest and I got interested and worked together to figure out what was going on with these results. We ended up publishing a paper on it a few years later -- this was my first paper in the field of genetic algorithms. This work expanded into what became our work on so-called "Royal Road" functions. My interests in science often start out with someone else's puzzling and unexplained results -- while trying to figure out why they got those results, I end up working on a much broader version of the problem.

G5: What is your favourite method of implementing a Genetic Algorithm? Why? (By this I mean things like crossover method, parent/child/population management, but also programming language etc).

I don't really have a favorite method -- I've used several different techniques in my experiments with GAs and found that different techniques work well on different problems. My favorite programming language by far is Lisp, but for reasons of economy, efficiency, portability, and so on, I've ended up doing most of my work in C.

G5: GAs (and especially their offshoot Genetic Programming) can be quite complicated to program (or at least optimize for your specific problem). If you have to give 3-4 tips to someone in order to optimize their problems, what would they be?

A few tips:

• Use a representation that is "natural" for your problem (e.g., don't force everything into bit strings; use real-numbers if that's more natural).
• Use elitism (always preserve the best one or few individuals from the previous population).
• Use a ranking or tournament selection scheme rather than fitness-proportionate selection, which tends to produce too much convergence too quickly.
• Don't be afraid to mix other algorithms with your GA. E.g., if hill-climbing is a reasonable option, try running the GA for a while, then taking the best solution and hill-climbing from it to improve it.

These and other tips are discussed further in Chapter 5 of my book, An Introduction to Genetic Algorithms (MIT Press). Another good book for practical advice on GAs is Davis's book "Handbook of Genetic Algorithms".

G5: What other paradigms in AI do you think GAs work in best with. Do you think this might be reflection on 'reality'?

Evolving computer programs (e.g., genetic programming) seems to be more successful than many people had thought. GAs also seem quite promising for various molecular biology applications, such as molecular design. GAs in a test tube, otherwise known as "applied molecular evolution" or "directed evolution", seem quite promising as well. This is where you evolve actual molecules in a test tube in a directed way, with some kind of fitness criteria (e.g., "binds well to a particular substance") and selection (done by the experimenter) based on those criteria. I don't know much about recent results using GAs to evolve neural networks but know that some people have had success in that area.

G5: In your book "An Introduction to Genetic Algorithms" you say that GA theorists should look towards Mathematical Genetics for interesting advancements. What kind of advancements do you see from the cooperations of these two fields?

I think mathematical genetics approaches might give some insight as to why GAs behave the ways they do. For example, van Nimwegen, Crutchfield, and collaborators at the Santa Fe Institute have used approaches similar to those in mathematical genetics to explain why GAs sometimes show punctuated equilibrium-type behavior. I would hope that mathematical genetics approaches will yield some insights into questions such as when and why crossover is useful, and when and why coevolutionary approaches are useful. Mark Feldman and colleagues at Stanford have already made some progress on the first question. People in the evolution strategies community have looked into the theory of certain types of coevolution (e.g., coevolving the mutation rate with the genome) using techniques related to mathematical genetics.

G5: What have been the most interesting applications of GAs to a problem you have seen?

See my book! :) There are lots and lots of interesting applications out there. I talked about a few of them in my book, but there are of course many more. One I didn't mention in my book but that I really like is Karl Sims' work on evolving swimmers and competitors in various environments. What makes his work most interesting is that he has used advanced computer graphics to animate what is going on so one has a true feel for evolution at work. This is the kind of illustration that I hope will convince evolution-doubters that natural selection really can work!