EA Part 2: Weasels

Updates


If you completed Part 1 of the project, you may have noticed that even with rather favorable mutation rates, the individual displayed in the GUI over multiple offspring generations did not approach the target smoothly or quickly. In this second part of the project, you will encounter the power that populations provide in the search for and selection of more fit individuals.

Objectives

In this second project deliverable, you will, among other things:

Preliminaries and Definitions

A key to evolutionary systems is natural selection wherein more highly fit individuals survive and/or have more offspring. For this project deliverable, you will write code that probabilistically selects individuals for producing offspring in the next generation. This probabilistic selection assigns to each individual a chance of being selected equal to that individual's fitness divided by the total fitness in the population. Suppose we have ten individuals in our population with corresponding fitnesses as follows: 15, 11, 8, 8, 7, 4, 3, 2, 2, and 0. In this case, we have a total fitness of 60. However, using a uniform prior, we add 1 to the fitness scores of each inidividual giving rise to an effective total fitness of 70. Thus, the first individual would have a 16/70ths chance of getting selected for generating an offspring. The last individual would have a 1/70th chance of getting selected instead of no chance at all.

Provisions

Use the same data-definitions as in Part 1.

Requirements

This is an individual project; working together must be limited to asking specific questions about Racket functionality. Let me stress this -- do not share code and do not discuss your solutions.

As always, follow the design recipe and make sure your code conforms to these specifications. Function names and argument order must be followed precisely. I may test your program with code of my own so errors at testing time will result in significant penalties even if your code ‘works’ with your own tests. In the first project deliverable, I encouraged you to use the abstract functions; in this second deliverable, you are required to use them where appropriate in order to receive full credit.

  1. Probabilistic selection. Write the function, fit-proportional-select, that will propabilistically select a single individual from a population as described above using the uniform prior described in the update. Your function should consume a population and return a single individual from that population.
  2. Most fit individual. Write the function, most-fit-in-pop, that consumes a population and returns the individual with the highest fitness. Ties may be broken arbitrarily.
  3. Next generation generation. Write the function, next-gen, that consumes a population and a target genetic-sequence; the function creates a new population of the same size by probabilistically selecting individuals from the given population as described above, and then for each selected individual, generates an offspring from that individual. As already suggested, an individual with high fitness will tend to be selected multiple times during this process. Thus, we are performing sampling with replacement.
  4. Revisions to the GUI. As before, I want you to organize your code according to the MVC paradigm. The requirements above should appear in your Model section, the added gui-items below should appear in your View section, and the changes to the call-back function should appear in your Control section.
    • desired target: add a text-box where the user may enter the desired target. Note, the user need only type in text -- no parentheses or quotes. Since our alphabet consists of the 26 upper-case letters and space, you might want to either prompt the user to enter caps, or convert the letters to upper-case in your program.
    • number of generations to simulate: add a text-box for entering the number of generations that should simulated when the ‘evolve’ button is pressed.
    • population size: add a text-box for determining the size of the population.
    • show most fit individual and its fitness: whereas in Part 1 you only simulated the evolution of a single individual, now we want to simulate the evolution of an entire population. Thus, your GUI should display only the most-fit individual (with ties broken arbitrarily). Similarly, you should display the fitness value of that individual.
    • show current generation: since you will be simulating multiple generations, add a message-item for displaying the current generation value.
    • call-back function responsibilities: when the ‘evolve’ button is pressed, the call-back function will be responsible for several tasks. First, it should extract the information from the text-boxes (target, number of generations to simulate, and population size). Second, it will generate a random population of the requested size with fitness values reflecting the entered target. Finally, it should run one generation at a time, displaying the most-fit individual and its fitness, as well as the current generation number (counting upwards) for each generation. The displayed text of the most-fit sequence and fitness value should be changing rapidly; this is expected. The simulation should stop if either the requested number of generations has been reached or if the most-fit individual perfectly matches the target (in which case the current generation message should show the number taken to get there).

Submission

Do not forget to include the standard acknowledgements header at the top of your file. To grade this deliverable, I will review your code (including signatures, purpose statements, indentation, etc.), and then attempt to run it and interact with your GUI. Submit a single file named, “P2.rkt”, which should contain your code fulfilling the requirements above as well as your acknowledgements.