The problem with using only a fitness function (i.e. an explicit objective) for evolutionary algorithms: local optima.

In the context of evolutionary algorithms, *deception* describes when the combination of highly-fit components result in a solution further from the global optimum (towards a local optimum). Deception, in combination with sampling error and the ruggedness of a fitness landscape, are the main contributors to the difficulty of an evolutionary computation problem.

This problem can be mitigated by incorporating a *novelty* criteria - the dissimilarity of a new solution against existing solutions. This *novelty search* typically results in better solutions significantly more quickly than the conventional fitness-based approach.

The general approach involves keeping track of previous highly-novel solutions (a "*novel archive*"). The novelty of a solution is the average distance from either neighbors in the novel archive or in the current population. The particular distance measure is problem-dependent.

The paper proposes an additional criteria of *surprise*. Whereas novelty just requires that a solution be sufficiently different from existing ones, surprise also requires deviation from expectations.

One way of understanding the distinction is by viewing surprise as the time derivative of novelty; i.e. novelty is position, surprise is velocity.

To quantify the surprise of a solution, a *surprise archive* is maintained of the past *prediction locality*) groups (if

The *surprise value*

where

see also: Liapis, A., Yannakakis, G. N., & Togelius, J. (2015). [Constrained novelty search: A study on game content generation](http://julian.togelius.com/Liapis2014Constrained.pdf_. Evolutionary computation, 23(1), 101-129.