CS81 Lab3: Novelty Search

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.

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 NoveltySearch. Implement the following methods:

• __init__(self, k, limit, threshold)
  Novelty search 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 value.
• 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 point.
• getArchiveSize(self)
  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.

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 this:

  % 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 square.
• 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 tests.

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.
  • 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.
  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.
• 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 results?

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 search.

• 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 called neat_chromo.
• Copy the file neatXOR.py to a file called noveltyXOR.py. Edit the noveltyXOR.py file as follows:
  • Import your novelty search code (remember to omit the .py when importing).
  • Create an instance of your NoveltySearch class that uses a k of 10, a limit of 150, and a threshold of 0.3.
  • 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 called novelty_chromo.
  • 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 lab work.