Due
date: ___________________
General
info: Turn in all code on paper and by email (to dbahr@regis.edu with “CS417 Homework” in the
subject line).
Add
lots of comments to your code. Test every method and every constructor.
_____________________________________________________
This is it! At the end of this homework, your code should
work! Of course we’ll add refinements
later, like tests for super-individuals, elitist algorithms, etc. But your goal for this assignment is to
produce code that functions as a genetic algorithm – no bells and whistles, but
functioning.
Problem #1: Let’s create a class that controls the evolution. We might want to do a basic explicit
evolution, implicit evolution (same as explicit, but fitness is 1.0 if survived
and 0.0 if died), explicit evolution with the elitist approach (stay tuned),
implicit evolution where breeding is only allowed for critters that are
standing near apple trees, or some other kind of evolution (I’m sure you will
be creative for the final project). So
let’s use the strategy pattern for maximum flexibility. First create an abstract “EvolutionStrategy”
class. Create a single abstract “evolvePopulation” method that takes a Population, SelectionStrategy, and GeneManipulator
as parameters. The method should return
a new Population.
Problem #2: Now create an ExplicitEvolutionStrategy
that extends the EvolutionStrategy. Implement the evolvePopulation
method. In this method create a new
Population, and create a loop that fills it with new Phenotypes. The loop should do the following.
a.
Use the selectionStrategy to get some chromosomes.
b.
Call the “performGeneticOperations” method in the GeneManipulator
to do crossover and mutation on the selected chromosomes.
c.
Create a new
Phenotype and add it to your new population.
d.
End the loop when
the new population is the same size as the old population.
Now return your new
population.
Problem #3: We are getting close to being done! We have all the pieces, and we just need to
put them together. To help assemble, we
will create an abstract factory.
Remember that factories create sets of related classes. In this case, the factory creates classes
that are related to the GA problem we are trying to solve, like finding p. Generally, an abstract factory
should have methods that return generic parent classes, like Chromosome, FitnessFunction, GeneticOperator,
etc. That way the concrete factory can return
specific child classes, like BitChromosome, PiFitnessFunction, Crossover, etc.
a.
So create an
abstract class called ALifeFactory.
b.
Add abstract
methods that get the following: a Chromosome, EvolutionStrategy,
FitnessFunction, GeneManipulator, array of GeneticOperators,
Phenotype, Population, and SelectionStrategy. Those are all the pieces that we need to run
a particular simulation.
c.
Also add a method
“getMaximumGeneration” that returns a maximum
generation after which the simulation will end.
Problem #4: Now create a specific factory, the PiFactory. Implement all of the abstract methods so that
they return brand new instances of appropriate classes like BitChromosome,
ExplicitEvolutionStrategy, PiFitnessFunction,
etc. This will also require instance
variables for the maximumGeneration, mutationProbability, chromosomeLength,
populationSize, etc.
Don’t bother with getters and setters for these. Later you may decide to make the constructor
read those variables from a file so that you can alter the simulation without
recompiling (recommended!).
Problem #5: Wow, this is it!
Create a Biosphere class and give it a main. In the main,
a.
Create a PiFactory. “ALifeFactory factory = new PiFactory();”
b.
Get a Population,
EvolutionStrategy, FitnessFunction,
etc.
c.
Use the FitnessEvaluator to assign an initial fitness to every
Phenotype in the initial population.
d.
Now create a loop
that goes until the maximum number of generations.
e.
In the loop,
i. Use the EvolutionStrategy to
evolve the population (gets the population at the next generation).
ii. Use the FitnessEvaluator to
assign a fitness to every Phenotype in the new
population.
iii. Print out or save some stats (like the current
generation, the best critter, the best fitness, the average fitness,
etc.). Optional: for maximum flexibility
in later problems, you may want to make this an abstract SaveData
class that is assigned a concrete implementation by the PiFactory.
iv. Increment the generation.
Problem #6: Run your code!
Make sure it works and turn in some associated statistics like the best
chromosome, the best fitness, the value of p, etc.
Extra Credit (10 points): Use your genetic
algorithm to solve for 0 on the range [-1, 1] with a fitness function of 1 -
|x|. Say what? Why?
Because this is an excellent way to test your code for bugs! Your chromosomes should evolve to be either
1000…00 or 011111…11 (can you see why?).
If you print out your chromosomes, it will be very easy to see if they
are not evolving towards one of these. To keep things manageable, I recommend a
population size of 10, a chromosome length of 10, and at least 100
generations. Small is better for
debugging, though you may need to increase the size of the parameters to get
good results.
Note: Problem #6 (and the extra credit) is VERY
important. Look carefully at your stats
and make sure they are doing what you expect.
Try to nail down any discrepancies and uncertainties. Test all corner cases, like populations of
size 0 and size 1, chromosomes of length 0 and length 1 and length 100 (bigger
than a “long”), etc. Try to fix all bugs
now. In the future our simulations will
become increasingly complicated, and it will be harder to nail down any bugs.
Also note:
your code should work well enough that you can see it evolving p, but don’t expect miracles just yet.
We will make some helpful refinements in the near future that will make
convergence quicker and more certain.