|
© 2004. Indiana University and Michael Gasser. www.indiana.edu/~gasser/Q530/Assignments/hw5.html 9 Nov 2004 |
|
In this assignment you will implement evolution in a population of critters, using a genetic
algorithm.
You will be working with the Genome and Evolver classes.
You can submit the two files separately.
Go to the Vincent page for the class to upload the files.
As in the last assignment, each critter has the ability to touch all 6 cells around it and to
know the texture of these cells.
There are four textures: EMPTY, SOFT (for plants), FUZZY (for critters that can't mate), and
HARD (for critters that can mate).
(There are no rocks in the world we will work with.)
Also as in the last assignment, the brain's sense() method returns an array, though this time they are integers, either 0.0 or 1.0.
The representation of the sensory input assigns 4 positions in the array
to each touchable cell, one position for each of the 4 distinguishable textures, 24 positions in all.
The numbers in the array returned by sense() represent the cells around the critter starting from the cell in front of it and moving clockwise around it.
So the first 4 numbers represent the cell in front of the critter, the second 4 numbers represent the cell that is 60 degrees clockwise from the critter's heading, etc.
After calling sense(), the critter chooses an action on the basis of the state
that it gets.
It makes the decision either randomly (set in the world file or with the "Decide randomly"
button) or using the knowledge that is encoded in its genome.
When the decision is made according to the genome, it is deterministic, unlike in the Q learning assignments, unless there is a tie.
Each critter has its own genome, corresponding to the memory in the last two assignments.
The genome is an array of booleans, representing bits.
State positions (cells around the critter), state values (textures), and actions are represented locally in the genome, but states are represented in distributed fashion.
That is, each state takes the form of a state value for each state position, and
for each of these combinations, the genome specifies values for
all possible actions.
I'll refer to each value for the association between a state position, state value, and action as a "trait".
The default number of possible trait values is 4 (0 to 3), and each of
these is represented using two bits in the genome.
Thus the length of each genome is
(number of state positions) * (number of state values) * (number of actions) * (number of bits per trait).
For the default values of each of these quantities given in propDefaults, this is
6 * 4 * 7 * 2 = 336 genes.
Given a particular state returned by the touch sensor, for each possible action the genome provides a value (trait) for each of the state positions (cells). So the value associated with each action in the state is the sum of these values (six of them in the default case), and the "best action" for the state is the action with the highest sum. In case of a tie, the genome randomly picks an action.
As before, the execution of an action results in a reinforcement. If the reinforcement is negative, the action can only be successfully executed if the critter has enough strength to compensate for the reinforcement. The reinforcement is added to the critter's strength, which is not allowed to exceed its initial value (100) or to go below 0.
Critters can mate, as well as eat, move, and turn, though, as with eating, mating is not an explicit (selected) action.
Critters can be in a "matable" or non-"matable" state.
When they are matable, they appear magenta and can be distinguished by
touch sensors from non-matable critters.
Matable critters can mate with other matable critters.
Matability depends on strength (which must be greater than -mateCost)
and how recently the critter either mated last or was born (affected by the parameter
matingRefractory).
When a matable critter attempts to a cell with another matable critter, mating is initiated (in the
Evolver class).
The two weakest critters in the population are selected.
The genomes of these critters are replaced by the result of applying crossover to the
genomes of the mating parents.
Mutation is the applied to these new genomes.
Finally, reincarnation is completed; the offspring are given the initial settings that
new critters get.
This version of the program performs evolution (incomplete until you've done your part)
if evolve is true in the world file.
Otherwise it performs Q learning using neural nets, as in the last assignment.
The documentation for the classes, especially Genome, Evolver,
and Utils, should tell you about the methods you need.
In addition, this version of the program has three new kinds of windows to help you see what is going on.
Critter's strength,
To close this window, uncheck "Show strengths frame" or click on its close box.
Touch) that can appear in a state position.
Within each of these state value cells, there are positions for each of the
seven possible actions.
The locations of these positions correspond to moving forward
(at the top), turning in one of the 5 directions, and resting (in the center).
The size of the circle in each of these regions represents the strength encoded
in the genome for the given state location, state value, and action.
Remember that the choice of an action in a given state
depends on the sum of all of these values for the six state values in the six state positions.
To close a genome window, click in its close box.
There are also four new buttons. The two buttons at the bottom control whether decisions are made randomly or "intelligently", that is, according to the memory (for learning) or the genome (for evolution) and whether initial genomes are "perfect", that is, specifically designed for optimal actions with a touch sensor, or random (as they should be for evolution). The "Reinitialize" button creates a new population from scratch, using whatever values are in the world file that was loaded when the program was started up, note that the values represented by the two buttons at the bottom have priority over whatever is in the world file. The "Change props" button reloads the values in the world file, without creating a new population. You can use this see how evolved critters fare in a harsher environment.
Start by downloading the version of the program that you will use for this assignment.
Also download the completed program if you want to see how it should work when it is done.
Use the world file evol1.
You might want to copy it because you will be editing some of the parameters in it.
getBestTrait() in Genome.
While working on this method, you will want to set the perfectGenomes parameter
to true.
(You can either do this in the world file or with the button.)
First make sure you are familiar with the other methods in this class; you will need
some of them for getBestTrait().
You will also probably need binaryToInt() in Utils.
Do not go on to the next part until you are sure this works.
crossover() and mutate() in Evolver.
These are both called in mate(), which you don't have to change.
Both methods are already there, but they do nothing.
Again you will need to call some of the methods in Genome.
evol1
specify a relatively nasty world that an evolving population of critters normally
fails to survive in.
However, as you can test, a population that decides randomly can survive.
But adjusting some of the parameters in the world file, show how you
can create a more benign world in which evolving critters can survive and how
you can incrementally change the world to be more and more challenging but also
tolerable by your evolving population.
In comments at the top of one of your Java files, or in a separate text file,
explain how you did this, summarizing the results.
|
© 2004. Indiana University and Michael Gasser. www.indiana.edu/~gasser/Q530/Assignments/hw5.html 9 Nov 2004 |
|