Evolved swimmers, from Karl Sim's "Evolving Virtual Creatures", SIGGRAPH '94 (source)

Summary

1. Section 3.5 in de Castro's Fundamentals of Natural Computing provides a good introduction to evolutionary computing. Read it, especially section 3.5.1, which covers 'standard genetic algorithms'.
2. Complete the following problems. Complete lab is worth 5 points.
3. Please summarize your answers in one document file (.doc,.pdf) including pictures. Organize this document well, make it clear which questions you are answering and provide appropriate labels where you can. Submit your well-documented code as separate python files. Also, mention in your summary document the names of the relevant python files for each question.
4. Assignment is due by 11am on Thursday, November 17th.
   
   Questions or problems? See my email and office hours information.

1. Write a program based on Algorithm 3.6 in your textbook, which is a pseudocode for a typical genetic algorithm. You will need to refer to variables for things like the array of genotypes in your population, the maximum number of generations, and the per-symbol mutation rate. You can refer to the following functions inside your loops & other control code:
   • init() - Initializes genotype population to random values
   • evaluate(population) - Evaluates the fitness of every genotype in the population and returns an array of fitnesses
     
   • select(population, fitnesses) - Uses fitness values to select successful member(s) of genotype population and reproduce them through recombination and/or mutation
     
   • recombine(father_genotype, mother_genotype, recombination_rate) - Recombines, with a probability specified by the recombination_rate, the two parent genotypes and creates two offsprings
     
   • mutate(genotype, mutation_rate) - Returns a mutated copy of a single passed-in genotype with each symbol of the genotype mutated with a probability specified by the mutation_rate
     
   
   
2. It is time to actually do a real GA run! Using a population size, genome size, and number of iterations of your preference, evolve a textual genotype to contain as many (lowercase) a's as possible. That is, you can use the number of lowercase a's present in a genotype as the fitness function. Your init() should initialize each genotype in your population to consist of a string of random alphabet characters. Each generation, print out the best performing genotype.
   
   
3. This is similar to the last question, except now we are going to be evolving the L-system production rules that we used to generate trees in Lab 2. A good encoding scheme to use — though you are welcome to use another one if you'd like — is to create our genotypes out of ['F','[',']','+', '-', ' '] characters, and interpret this as the production rule for the symbol F. That is, your production rules will be {'F':genotype} with a fixed axiom = 'F'(see L-System 1 specification in Q3 of Lab2, for example). The space (' '), however, would not get interpreted, but rather used to indicate the end of the definition of the production rule, so we could have variable-length rules. Note however that your genotype length should be fixed, only the location of a (' ') in the genotype needs to be interpreted as the end of the definition of the production rule specified by that genotype, thus making the length of the production rule variable. Use either roulette (recommended) or elite selection algorithms.
   
   As for parameters and (most importantly) the fitness function, make these up yourself, but try to create a fitness function that a) has some plausible story of biological significancy, and b) produces interesting, organic shapes. Successful solutions have been previously evolved in 20 generations using a population size of ~50 genotypes, of 10 symbols each, with a per-symbol mutation rate of 0.2 and roulette wheel selection. There, the fitness function was formulated based on the following assumption: successful trees are good at photosynthesis, so we would select for trees with many horizontal leaves. Thus, in our formalism, each genotype was evaluated as a production rule with an angle of 22 degrees, step size of 5, and iteration depth of 4 steps. During the course of evaluation, for every branch that was closed with a ']' character, that branch's horizontal size was added to its net fitness computed until then (up to a maximum of 10 pixels, arguing that leaves generally reside on the ends of branches). Keep in mind you might have to run your GA a couple of times to get good results.
   
   By the way, it helps a lot (both me and you) to draw your 'best-so-far' L-system every GA generation.