# Evolutionary Statistical System Based on Novelty Search:
## 2 Related Works
### Novelty Search: Paradigm and Applications  
The limitations observed in existing systems led us to consider the selection of other search approaches that may yield improvements in the quality of predictions. Given the particular problems observed in the experimental results of previous works, we determined that a promising approach for this problem could be the _Novelty Search_ (NS) paradigm. In this section, we explain the main ideas and describe related works behind this approach. Metaheuristic search algorithms reward the degree of progress toward a solution, measured by an objective function, usually referred to as a _score_ or _fitness function_ depending on the type of algorithm. This function, together with the neighborhood operators of a particular method, produces what is known as the _fitness landscape_[26]. By changing the algorithm, the fitness function, or both, a given problem may become easier or more difficult to solve, depending on the shape and features of the landscape that they generate. In highly complex problems, the fitness landscape often has features that make the objective function inefficient in guiding the search or may even lead the search away from good solutions [17]. This has led to the creation of alternative strategies that address the limitations inherent to objective-based methods [27]. One of these strategies is NS, introduced in [19]. In this paradigm, the search is driven by a characterization of the behavior of individuals that rewards the dissimilarity of new solutions with respect to other solutions found before. As a consequence, the search process never converges but rather explores many different regions of the space of solutions, which allows the algorithms to discover high fitness solutions that may not be reachable by traditional methods. This exploration power differs from metaheuristic approaches in that it is not driven by randomness, but rather by explicitly searching for novel behaviors. NS has been applied with good results to multiple problems from diverse fields [18; 19; 28; 29; 30; 31]. Initially, the main area of interest for applications of NS consisted of open-ended problems. In this area, the objective is to generate increasingly complex, novel, or creative behaviors; there is no fixed, predetermined solution to be reached. Interestingly, NS has also been proven useful for optimization problems in general, finding global optima in many cases and outperforming traditional metaheuristics when the problems have the quality of being _deceptive_, that is, when the combination of solutions of high fitness leads to solutions of lower fitness and vice versa [31]. In order to guide the search by novelty, all algorithms following this paradigm need to implement a function to evaluate the _novelty score_ of the solutions. Therefore, a _novelty measure_ of the solutions must be defined in the space of behaviors of the solutions. This measure, usually called _dist_ in the literature, is problem-dependent; an example can be the difference between values of the fitness function of two individuals. A frequently used novelty score function is the one presented by [19], which, for an individual \(x\), computes the average distance to its \(k\) closest neighbors:  
\[\rho(x)=\frac{1}{k}\sum_{i=0}^{k-1}dist(x,\mu_{i}), \tag{1}\]  
where \(\mu_{i}\) is the \(i\)-th nearest neighbor of the individual \(x\) according to the distance function \(dist\). In the literature, the parameter \(k\) is usually selected experimentally, but the entire population can also be used [18; 32]. To perform this evaluation, it is not sufficient to select close individuals by considering only the current population; it is also necessary to consider the set of individuals that have been novel in past iterations. To this end, the search incorporates an _archive of novel solutions_ that allows it to keep track of the most novel solutions discovered so far and uses it to compute the novelty score. The novelty values obtained are used to guide the search, replacing the traditional fitness-based score.