Evolutionära algoritmer har visat sig vara effektiva för att utveckla spelnivåer. Dock finns fortfarande ett behov av nivåer som både uppfyller de krav som spelen har, samt att nivåerna som skapas ska vara så olika som möjligt för att uppmuntra upprepade spelomgångar. För att åstadkomma detta kan man använda Novelty Search. Dock saknar Novelty Search funktioner som gör att populationen vill uppfylla de krav som nivåerna ska ha. Arbetet fokuserar därför på att jämföra två Novelty Search baserade algoritmer som båda uppmuntrar kravuppfyllning: Feasible Infeasible Novelty Search (FINS) och Pareto based Multi-objective evolutionary algorithm (PMOEA) med två mål: krav och Novelty Search. Studien jämför algoritmerna utifrån tre värden: hur stor andel av populationen som följer de ställda kraven, hur bra dessa individer är på att lösa ett nivårelaterat problem samt diversiteten bland dessa individer. Utöver PMOEA och FINS implementeras även en Novelty Search algoritm och en traditionell evolutionär algoritm. Tre experiment genomförs där nivåernas storlek och antalet krav varierade. Resultatet visar att PMOEA var bättre på att skapa fler individer som följde alla kraven och att dessa individer överlag var bättre på att optimera lösningar än vanlig Novelty Search och FINS. Dock hade FINS högre diversitet bland individerna än alla algoritmerna som testades. Studiens svaghet är att resultatet är subjektivt till algoritmernas uppsättning i artefakten, som sådan borde framtida arbeten fokusera på att utforska nya uppsättningar för att generalisera resultatet.

Teaching simulated biped robots to walk is a popular problem in machine learning. However, until this thesis, evolving a biped controller has not been attempted through an indirect encoding, i.e. a compressed representation of the solution, despite the fact that natural bipeds such as humans evolved through such an indirect encoding (i.e. DNA). Thus the promise for indirect encoding is to evolve gaits that rival those seen in nature. In this thesis, an indirect encoding called HyperNEAT evolves a controller for a biped robot in a computer simulation. To most effectively explore the deceptive behavior space of biped walkers, novelty search is applied as a fitness metric. The result is that although the indirect encoding can evolve a stable bipedal gait, the overall neural architecture is brittle to small mutations. This result suggests that some capabilities might be necessary to include beyond indirect encoding, such as lifetime adaptation. Thus this thesis provides fresh insight into the requisite ingredients for the eventual achievement of fluid bipedal walking through artificial evolution.

I present a new approach to evolutionary search called novelty search, wherein only behavioral novelty is rewarded, thereby abstracting evolution as a search for novel forms. This new approach contrasts with the traditional approach of rewarding progress towards the objective through an objective function. Although they are designed to light a path to the objective, objective functions can instead deceive search into converging to dead ends called local optima. As a significant problem in evolutionary computation, deception has inspired many techniques designed to mitigate it. However, nearly all such methods are still ultimately susceptible to deceptive local optima because they still measure progress with respect to the objective, which this dissertation will show is often a broken compass. Furthermore, although novelty search completely abandons the objective, it counterintuitively often outperforms methods that search directly for the objective in deceptive tasks and can induce evolutionary dynamics closer in spirit to natural evolution. The main contributions are to (1) introduce novelty search, an example of an effective search method that is not guided by actively measuring or encouraging objective progress; (2) validate novelty search by applying it to biped locomotion; (3) demonstrate novelty search’s benefits for evolvability (i.e. the ability of an organism to further evolve) in a variety of domains; (4) introduce an extension of novelty search called minimal criteria novelty search that brings a new abstraction of natural evolution to evolutionary computation (i.e. evolution as a search for many ways of iii meeting the minimal criteria of life); (5) present a second extension of novelty search called novelty search with local competition that abstracts evolution instead as a process driven towards diversity with competition playing a subservient role; and (6) evolve a diversity of functional virtual creatures in a single run as a culminating application of novelty search with local competition. Overall these contributions establish novelty search as an important new research direction for the field of evolutionary computation.

The field of evolutionary computation is inspired by the achievements of natural evolution, in which there is no final objective. Yet the pursuit of objectives is ubiquitous in simulated evolution because evolutionary algorithms that can consistently achieve established benchmarks are lauded as successful, thus reinforcing this paradigm. A significant problem is that such objective approaches assume that intermediate stepping stones will increasingly resemble the final objective when in fact they often do not. The consequence is that while solutions may exist, searching for such objectives may not discover them. This problem with objectives is demonstrated through an experiment in this dissertation that compares how images discovered serendipitously during interactive evolution in an online system called Picbreeder cannot be rediscovered when they become the final objective of the very same algorithm that originally evolved them. This negative result demonstrates that pursuing an objective limits evolution by selecting offspring only based on the final objective. Furthermore, even when high fitness is achieved, the experimental results suggest that the resulting solutions are typically brittle, piecewise representations that only perform well by exploiting idiosyncratic features in the target. In response to this problem, the dissertation next highlights the importance of leveraging human insight during search as an alternative to articulating explicit objectives. In particular, a new approach called novelty-assisted interactive evolutionary computation (NA-IEC) combines human intuition with a method called novelty search for the first time to facilitate the serendipitous discovery of agent behaviors. iii In this approach, the human user directs evolution by selecting what is interesting from the on-screen population of behaviors. However, unlike in typical IEC, the user can then request that the next generation be filled with novel descendants, as opposed to only the direct descendants of typical IEC. The result of such an approach, unconstrained by a priori objectives, is that it traverses key stepping stones that ultimately accumulate meaningful domain knowledge. To establishes this new evolutionary approach based on the serendipitous discovery of key stepping stones during evolution, this dissertation consists of four key contributions: (1) The first contribution establishes the deleterious effects of a priori objectives on evolution. The second (2) introduces the NA-IEC approach as an alternative to traditional objective-based approaches. The third (3) is a proof-of-concept that demonstrates how combining human insight with novelty search finds solutions significantly faster and at lower genomic complexities than fully-automated processes, including pure novelty search, suggesting an important role for human users in the search for solutions. Finally, (4) the NA-IEC approach is applied in a challenge domain wherein leveraging human intuition and domain knowledge accelerates the evolution of solutions for the nontrivial octopus-arm control task. The culmination of these contributions demonstrates the importance of incorporating human insights into simulated evolution as a means to discovering better solutions more rapidly than traditional approaches.

[ES] La búsqueda novedosa es un nuevo paradigma de los algoritmos de optimización, evolucionarios y bioinspirados, que está basado en la idea de forzar la búsqueda del óptimo global en aquellas partes inexploradas del dominio de la función que no son atractivas para el algoritmo, con la intención de evitar estancamientos en óptimos locales. La búsqueda novedosa se ha aplicado al algoritmo de optimización de enjambre de partículas, obteniendo un nuevo algoritmo denominado algoritmo de enjambre novedoso (NS). NS se ha aplicado al conjunto de pruebas sintéticas CEC2005, comparando los resultados con los obtenidos por otros algoritmos del estado del arte. Los resultados muestran un mejor comportamiento de NS en funciones altamente no lineales, a cambio de un aumento en la complejidad computacional. En lo que resta de trabajo, el algoritmo NS se ha aplicado en diferentes modelos, específicamente en el diseño de un motor de combustión interna, en la estimación de demanda de energía mediante gramáticas de enjambre, en la evolución del cáncer de vejiga de un paciente concreto y en la evolución del COVID-19. Cabe remarcar que, en el estudio de los modelos de COVID-19, se ha tenido en cuenta la incertidumbre, tanto de los datos como de la evolución de la enfermedad. / [CA] La cerca nova és un nou paradigma dels algoritmes d'optimització, evolucionaris i bioinspirats, que està basat en la idea de forçar la cerca de l'òptim global en les parts inexplorades del domini de la funció que no són atractives per a l'algoritme, amb la intenció d'evitar estancaments en òptims locals. La cerca nova s'ha aplicat a l'algoritme d'optimització d'eixam de partícules, obtenint un nou algoritme denominat algoritme d'eixam nou (NS). NS s'ha aplicat al conjunt de proves sintètiques CEC2005, comparant els resultats amb els obtinguts per altres algoritmes de l'estat de l'art. Els resultats mostren un millor comportament de NS en funcions altament no lineals, a canvi d'un augment en la complexitat computacional. En el que resta de treball, l'algoritme NS s'ha aplicat en diferents models, específicament en el disseny d'un motor de combustió interna, en l'estimació de demanda d'energia mitjançant gramàtiques d'eixam, en l'evolució del càncer de bufeta d'un pacient concret i en l'evolució del COVID-19. Cal remarcar que, en l'estudi dels models de COVID-19, s'ha tingut en compte la incertesa, tant de les dades com de l'evolució de la malaltia. / [EN] Novelty Search is a recent paradigm in evolutionary and bio-inspired optimization algorithms, based on the idea of forcing to look for those unexplored parts of the domain of the function that might be unattractive for the algorithm, with the aim of avoiding stagnation in local optima. Novelty Search has been applied to the Particle Swarm Optimization algorithm, obtaining a new algorithm named Novelty Swarm (NS). NS has been applied to the CEC2005 benchmark, comparing its results with other state of the art algorithms. The results show better behaviour in high nonlinear functions at the cost of increasing the computational complexity. During the rest of the thesis, the NS algorithm has been used in different models, specifically the design of an Internal Combustion Engine, the prediction of energy demand estimation with Grammatical Swarm, the evolution of the bladder cancer of a specific patient and the evolution of COVID-19. It is also remarkable that, in the study of COVID-19 models, uncertainty of the data and the evolution of the disease has been taken in account. / Martínez Rodríguez, D. (2021). Optimization Algorithm Based on Novelty Search Applied to the Treatment of Uncertainty in Models [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/178994