Simple Genetic Algorithms

There's a rather broad field of research that's generally called Evolutionary Programming (although naming conventions are a bit political). Within EP are any number of techniques, like Evolutionary Strategies, Genetic Programming, the Genetic Algorithm, and so on. The main thing to grok is that in some way all of these techniques use evolution, specifically the idea of evolving populations via some sort exchange of genetic material between individuals, as a computational metaphor. The exact techniques used vary widely, as do the goals of the users and even the fundamental reasoning behind them.

We're going to have a look at one of the simpler approaches, the simple genetic algorithm. The more-or-less standard procedure for running the simple genetic algorithm is:

some basic vocabulary:
allele: the basic genetic unit, expressed as some trait
chromosome: a collection of alleles that make up an individual's genotype
genotype: the encoded description of an individual
phenotype: the individual as expressed by the genotype
fitness function: criteria used to evaluate whether one member of a population is "better" than another
roulette wheel selection: random selection of parents from the current pool of chromosomes
tournament selection: individuals compete (via the fitness function) to be parents
demetic selection: dividing the population into semi-isolated groups to encourage speciation
elitism: determines how many individuals from a population are replaced with each generation

The hardest part about using genetic algorithms is defining your fitness function, particularly when there's no concrete problem you're trying to solve. This is really the mapping problem in disguise. What is it, exactly, that you're evolving? And how are you going to decide that one member of your population is "better" than another? This is an interesting problem, as it leads into all sorts of good stuff, like psychoacoustics and human perception, source identification, sound categorization, signal analysis, etc.

One of the nice things about using GAs is that they're interesting at many levels; you can get in really deeply and do a very thorough job of creating your model, but even a very simple model can yield interesting results.

The C++ code we looked at in class today is available here.

back to the main page

douglas irving repetto
Last modified: Tue Sep 4 15:37:07 EDT 2001