CS81 Lab3: Novelty Search

Due by noon next Wednesday

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

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:

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.

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.

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


When you are done run handin81 to turn in your completed lab work.