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 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.
1. Create a class to implement novelty search
Before trying to implement novelty search, review the details of
the algorithm on pages 12-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, threshold, limit)
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 threshold for how novel an example has to be before it
will be added the archive, and the limit for the maximum size
of 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 distance of a
point p from its k-nearest neighbors in the archive. The
simplest, though very inefficient, way to implement this is to
calculate the distance of p from every point in the archive,
sort these distances, and then sum up and return the first k
(which will be the closest).
- 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, sparseness)
If the size of the
archive is less than the limit, then always add the point p.
Otherwise, when the archive is full, check if the given
sparseness of point p is greater than the threshold.
If so, add this point and also remove the oldest point in 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.
2. Test methods of novelty search on random points in 2d
- In the main program at the bottom of the
file noveltySearch, create an instance of
your Novelty class with a k of 10,
a threshold of 0.3, and a limit of 100.
- Use a for loop to generate 1000 random 2d points, where each value
is in the range [0.0, 0.3], and add them to the archive.
- Use another for loop to generate 1000 random 2d points, where each
value is in the range [0.0, 1.0], and add them to the archive.
- After both loops, save the archive to a file called test.dat.
- At the end of the main program 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 and ensure that the sparseness values match these
- Graph the points that were saved from the archive by doing:
% xgraph -P -nl test.dat
The P flag makes each point large, and the nl flag
indicates that there should be no lines drawn between the points.
- Run your program a number of times, changing
the threshold of the novelty search.
Look at the graph of
the test.dat file after each run. How does the graph change?
- 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 stringest 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
3. Test novelty search on XOR
- Open the file neatXOR.py. This is almost identical to
the file evolveXOR.py from last week. The main difference is
that the eval_fitness function includes an if at the
end to check for when a solution has been found. It then sets the
fitness for that chromosome to a high enough value to trigger the
max_fitness_threshold ending the evolution. It also saves
the network that solved XOR in a file called neat_chromo.
- We will compare standard NEAT to novelty search combined with
NEAT for solving XOR. Let's test standard NEAT first. Run the
program neatXOR.py 10 times and save the results in the
file experimentsXOR. Record the generation in which a
solution was found or 70 (the maximum number of generations) if not
found. Also record the complexity of the solution, which is printed
in the form: (number of hidden nodes, number of connections), at the
end of each run. You can use the program evaluateXOR.py to
test any of the neat_chromo solution files. You can
use xv to look at any of the avg_fitness.svg plots
that are produced. Notice that when using standard NEAT both the
average and best fitness tend to increase over the course of
- Copy the file neatXOR.py to a file
called noveltyXOR.py. Edit the noveltyXOR.py file
- Import your novelty search code.
- Create an instance of your Novelty class
that uses a k of 10, a threshold of 0.3, and
a limit of 150.
- 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, calculate its sparseness, 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.
- Before doing experiments with the novelty version, test it 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. Once you are
conviced it is working, you are reading to run experiments.
- Run the program noveltyXOR.py 10 times and record the
same information as for the previous experiments. Look at some of the
solutions produced as well as the plots of average and best fitness.
Notice that in the fitness plots, novelty search does not display the
same trend of increasing fitness values over time.
- At the bottom of the file experimentsXOR compare the
results. Which method finds solutions more consistently? Which
method finds solutions more quickly? Which method finds less complex
solutions? Is the XOR problem better suited for objective-based
or novelty-based search, why?
Optional: Test novelty search on maze traversal
Before trying to implement maze traversal, read through the details
of the maze experiment that Lehman and Stanley conducted on pages
14-16 of their paper
Abandoning objectives: Evolution through the search for novelty alone.
- They used a robot with 6 range sensors for detecting obstacles and
4 radar sensors for detecting the goal location. Rather than trying
to replicate this experiment exactly we can use the existing framework
of pyrobot to create a similar experiment. The goal location can be
marked with a light. The robot can be equipped with sonar sensors
to detect obstacles and light sensors to detect the goal.
- There is a series of maze-like worlds that already exist in
pyrobot called: LightBehindWall, LightInCorral, LightBehindCorral,
LightEnclosed, and LightInMaze that could be used as a testbed for
maze traversal. These are located
in /usr/local/pyrobot/plugins/worlds/Pyrobot/. You are also
welcome to create your own maze worlds.
- Using the files evolveEnergy.py
and evaluateEnergy.py from last week's lab as models, create
files called neatMaze.py and evaluateMaze.py. In
the file neatMaze.py create a standard objective fitness
function based on the formula given at the bottom of page 15.
Remember that you can use the pyrobot commands setPos to
position the robot at the start of a trial and getPos to find
the robot's position at the end of the trial. Look at the parameter
settings in the appendix of the paper to determine how to configure
NEAT. Test this program. Based on the results presented in the paper,
we would expect that this would only very rarely solve a maze.
- Copy the file neatMaze.py to a file
called noveltyMaze.py. Modify the fitness function so that
it is now a novelty metric based on the robot's end point at the end
of a trial. Look at the appendix of the paper to determine how to
configure novelty search. Test this program. Based on the results
presented in the paper, we would expect that this would find a
solution to the maze almost every time.
When you are done run handin81 to turn in your completed