This project was done over the summer with a word limit of 2500 words which meant that I had to compress a lot of the background but I’m happy with how the whole thing came out. I’ve posted the introduction here and you can read the rest of it (with it all formatted nicely in LaTeX) here.

Introduction

It is tempting to assume what we have been told throughout our lives is unquestionable. But sometimes questioning conventional wisdom can lead to an interesting conclusion, a truly novel idea.

Objective thinking is ingrained in modern day society. The idea that setting a goal is always the best way forwards is drilled into us from a very early stage in our lives. But when we actually look at great and ambitious achievements, are they really all objective driven? Did Steve Jobs really start out life with the ambition to create a revolutionary new phone?

Achievement can be thought of as a process of discovery [Stanley and Lehman, 2015]. In this way the process of achieving something ambitious can begin to look like a type of search. In search, the presence of local optima pose problems. Can a solution be found to mitigate these local optima in the search, allowing us to achieve our ambitious objectives?

As an example of a problem that suffers from getting stuck in a local optimum, imagine a misty lake with an assortment of stepping stones dotted in the water. The mist makes it impossible for you to see anything outside of a two stone radius around you. Your goal is to try and get from one bank of the lake to the other. A traditional objective view of the problem would suggest you define a measurement that would allow you to gauge how close you are to the other bank at any time. If you try and maximise this measurement, it is very likely you will reach a dead end (which is a local optimum) instead of the other bank.

This paper will introduce a solution first proposed by [Lehman and Stanley, 2011a] known as the novelty search, that does away with an objective and searches for novelty alone. This idea will then be demonstrated with the help of neuroevolution to show how novelty-based search can be advantageous to objective-based search in many tasks.

Although seldom discussed (in some part due to the advent of deep learning), evolutionary computation, of which neuroevolution is a subfield, is making a comeback [Stanley, 2017]. Its suitability for novelty search along with the fact that it is easily parallelisable coupled with the fact that deep neuroevolution can rival deep learning [Such et al., 2017] is what makes the field so interesting at the moment.