In this lab you will implement novelty search, introduced by Joel
Lehman and Kenneth O. Stanley, and combine it with NEAT to conduct an
evolutionary search based on a novelty metric rather than an
objective fitness function. Lehman and Stanley argue that objective
fitness functions can be deceptive, leading the evolutionary search to
local maxima rather than towards the desired goal. In contrast, novelty
search ignores the objective and simply searches for novel behavior,
and therefore cannot be deceived.
Do an update81 to ge the starting point files for this lab.
Create a python class to implement novelty search
Before trying to implement novelty search, review the details of
the algorithm on pages 13-14 of the paper
Abandoning objectives: Evolution through the search for novelty alone.
In the file noveltySearch.py, create a python class called
Implement the following methods:
- __init__(self, k, limit, threshold)
stores an archive of examples from the behavior space. It bases the
novelty metric on the k-nearest neighbors from that archive. Create
class variables to store the archive as an initially empty
list, the k to be used in calculating nearest neighbors,
the limit for the maximum size of the archive, and
the threshold for how novel an example has to be before it
will be added the archive.
- distance(self, p1, p2)
Returns the distance between
points p1 and p2 which are assumed to be lists or
tuples of equal length. To calculate distance, sum up the squared
differences between each component of the points. Return the square
root of this sum. This method should work for points of any length.
- distFromkNearest(self, p)
Returns the sum of the distances of a
point p from its k-nearest neighbors in the archive.
- sparseness(self, p)
Returns the sparseness of the
given point p as defined by equation 1 on page 13 of the
paper. Recall that sparseness is a measure of how unique this point
is relative to the archive of saved examples. Use the
method distFromkNearest as a helper in calculating this
- addToArchive(self, p)
If the size of the
archive is less than k, then always add the point p.
Otherwise check if the sparseness of the given
point p is greater than the threshold. If so, add this point
to the archive. After adding, if the archive size is now greater than
the limit, you should also remove the oldest point in the archive.
This method should return the spareness of the given
Returns the current size of the archive.
- saveArchive(self, filename)
This method saves the
entire archive to the given filename. Write each point on a single
line in the file, with spaces separating each value.
Be sure to comment each method of your class.
Test methods of novelty search on random points in 2d
Create a main program at the bottom of the
file noveltySearch.py. In main do the following:
- In order to easily experiment with the novelty search parameters,
we will set these parameters using command-line arguments. If you
haven't done this in python, you'll need to first import
the sys library at the top of the file. Then you can then
access the command-line arguments using sys.argv, which will
return a list of strings. We want to be able to call our program like
% python noveltySearch.py 10 100 0.3
where the command-line arguments represent
the k, limit, and threshold to be used when
doing novelty search. In main, check whether the correct
number of command-line arguments have been provided. If not, print an
informative message explaining how to properly use the program and
return. Otherwise, create an instance of your NoveltySearch
class with the given k, limit,
and threshold values. Remember you'll need to cast the
strings in sys.argv into the proper types.
- Use a for loop to generate 100 random 2d points, where each value
is in the range [0.0, 1.0], and add them to the archive.
- After this loop, print the size of the archive and save the
archive to a file called test.dat.
- Finally, print the sparseness of several points:
- Point (0.5, 0.5) should have a low sparseness since it is at the center
of the range of random points you generated.
- Point (1, 1) should have a higher sparseness since it is at the
boundary of random points you generated.
- Point (2, 2) should have an even higher sparseness since it is outside
the range of random points you generated.
- Point (5, 5) should have the highest sparseness since it is far
outside the range of random points you generated.
- Run your program using a k of 10, a limit of
100, and a threshold of 0.3 . Then verify that the
sparseness values match these expectations.
- Note the size of the archive that is printed. What percentage of
the points you generated were actually saved?
- Graph the points that were saved from the archive by doing:
% xgraph -lx 0,1 -ly 0,1 -P -nl test.dat
The lx flag indicates the limits for the x-axis,
the ly flag indicates the limits for the y-axis,
the P flag makes each point large, and the nl flag
indicates that there should be no lines drawn between the points. You
should see that the points are spread fairly evenly across the unit
- Run your program several times with the same parameter settings.
You should see that the archive size changes slightly each time and
that the graph of points is different, but similar is how spread out
the points are from one another.
If these basic tests seem to be yielding the expected results, move
on to the next section. Otherwise debug your code and run further
Experiment with novelty search parameters
In order to gain more intuition about how novelty search operates,
you will explore how various parameter settings affect the results.
You will first need to create a more interesting data distribution so
that you can more easily see how parameter settings change the
outcome. In main, add another for loop, after the
first one, to generate 100 random 2d points, where each value is now
in the smaller range of [0.0, 0.5], and add them to the archive.
- Run your program a number of times, changing
the threshold of the novelty search.
Predict what you think will happen to the distribution of points in
the archive. Then look at the graph of the test.dat file
after each run. Do the results match your prediction? Make sure you
understand the results.
- Use 0.0 to allow any point to be added to the archive.
- Use 0.2 to only moderately test the novelty of points that are added.
- Use 0.3 to have a more stringent level of novelty for points.
- Finally try 0.4.
- Run your program a number of times, this time keeping
the threshold fixed at 0.3, while varying k. Again
look at the graph at the end. How does changing k affect the
Test novelty search on NEAT applied to XOR
We will use XOR because it provides a simple example of how
novelty search and NEAT can be combined to solve a problem. However,
note that this simple problem is not the type of complex, deceptive
problem where novelty search is likely to outperform objective
- Open the file neatXOR.py. This is almost identical to
the file evolveXOR.py from last week. The main difference is
that it saves the network that solved XOR in a file
- Copy the file neatXOR.py to a file
called noveltyXOR.py. Edit the noveltyXOR.py file
- Import your novelty search code (remember to omit the .py
- Create an instance of your NoveltySearch class that uses
a k of 10, a limit of 150, and a threshold
- Re-write the function eval_fitness so that it produces a
novelty metric rather than an objective measure. In order to do this
we need to create a representation of the behavior. For XOR this will
be a 4d point containing the output produced by the network on each of
the four inputs. For each chromosome in the population, create this
point, add it to the archive of novelty
search, and then set the fitness of the chromosome to the spareness.
Continue to calculate the error and use it to determine when a
solution has been found. Save the solution in a file
- After the call to pop.epoch(...), save the archive from
novelty search into a file called archive.dat.
- Test noveltyXOR.py to see
if it is giving reasonable results. It should find a solution most of
the time. Use the program evaluateXOR.py to test a few
solutions. Also look at the file archive.dat to see if it
contains a reasonable variety of example behavior.
- Compare the results you are getting using novelty to the results
you get using the original NEAT code. Which method finds solutions
more consistently? Which method finds simpler solutions?
When you are done run handin81 to turn in your completed