Searching for the unexpected : evolution through surprise

Abstract

In this dissertation we present a new approach called surprise search that realises the concept of surprise for the serendipitous discovery in a computational search space. Inspired by the notion of surprise in computational creativity, surprise search seeks unconventional solutions and equips computational creators with the ability to search for unexpected outcomes. This new approach contrasts the traditional paradigm of rewarding progress towards the objective, and rewards unexpected discoveries to handle hard and deceptive problems. According to the literature in computational creativity, surprise is a key element for the discovery of highly creative and unconventional solutions. Furthermore, theories of intrinsic motivation situate surprise, along with novelty, as primary factors for the elicitation of interest, for the enhancement of learning, and for enabling discovery. This thesis tests the hypothesis that surprise can be an effective drive for the discovery of solutions in hard and deceptive testbeds and it also examines how surprise may complement other forms of divergent search such as novelty and quality diversity algorithms. The main contributions of this work include: (1) the introduction of surprise search; (2) the validation of surprise search for problem-solving; (3) the exploration of how surprise can be effectively coupled with novelty search; (4) and the testing of the effectiveness of surprise as a reward for quality diversity. The fi ndings of this thesis support the idea that deviation from expected behaviours can be a powerful alternative for divergent search and quality diversity with key benefi ts over state-of-the-art evolutionary approaches.