Genetic Programming Based on Novelty Search

Abstract

Novelty Search (NS) is a unique approach towards search and optimization,where an explicit objective function is replaced by a measureof solution novelty. However, NS has been mostly used in evolutionaryrobotics, its usefulness in classic machine learning problems has beenunexplored. This thesis presents a NS-based Genetic Programming(GP) algorithms for common machine learning problems, with the followingcontributions. It is shown that NS can solve real-world classification,clustering and symbolic regression tasks, validated on realworldbenchmarks and synthetic problems. These results are madepossible by using a domain-specific behavior descriptor, related to theconcept of semantics in GP. Moreover, two new versions of the NS algorithmare proposed, Probabilistic NS (PNS) and a variant of MinimalCriteria NS (MCNS). The former models the behavior of each solutionas a random vector and eliminates all the NS parameters while reducingthe computational overhead of the NS algorithm; the latter uses astandard objective function to constrain and bias the search towardshigh performance solutions. The thesis also discusses the effects of NSon GP search dynamics and code growth. Results show that NS can beused as a realistic alternative for machine learning, and particularly forGP-based classification.