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. Attach answers as separate Python files to your submission for 'Assignment 3' in Oncourse
4. Assignment is due by 1pm on Wednesday, April 8th
   
   Questions or problems? See my email and office hours information.

1. Write a detailed pseudocode layout for a Python-based 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
   • get_fitness(genotype) - Evaluates fitness of passed-in genotype
   • mutate(genotype) - Returns mutated copy of passed-in genotype
   • get_new_population(genotypes, fitnesses) - Uses fitness values to reproduce successful members of genotype population
   
   
   
2. Its 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. 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 grammars 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 (in other words, you axioms will be {'F':genotype}. The space (' '), however, would not get interpreted, but rather used to indicate the end of the replacement in the production rule, so we could have variable-length rules. 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. I myself had decent luck evolving successful trees 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. Fitness function went like this: I believe that successful trees are good at photosynthesis, so we would select for trees with many horizontal leaves. Thus, in our formalism, I took every genotype, evaluated it as a production rule with an angle of 22 degrees, step size of 5, and interation depth of 4 steps, and for every branch that was closed with a ']' character, added to the genotype's fitness evaluation the branch's horizontal size (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.